25 #include <drizzled/my_hash.h>
26 #include <drizzled/charset.h>
31 const uint32_t NO_RECORD= UINT32_MAX;
35 const int HIGHFIND= 4;
36 const int HIGHUSED= 8;
38 static uint32_t hash_mask(uint32_t hashnr, uint32_t buffmax, uint32_t maxlength);
39 static void movelink(HASH_LINK *array, uint32_t pos, uint32_t next_link, uint32_t newlink);
40 static int hashcmp(
const HASH *hash, HASH_LINK *pos,
const unsigned char *key,
size_t length);
42 static uint32_t calc_hash(
const HASH *hash,
const unsigned char *key,
size_t length)
44 uint32_t nr1=1, nr2=4;
45 hash->charset->coll->hash_sort(hash->charset, key,length, &nr1, &nr2);
49 #define dynamic_element(array,array_index,type) ((type)((array)->buffer) +(array_index))
52 _hash_init(HASH *hash,uint32_t growth_size,
const charset_info_st *
const charset,
53 uint32_t size,
size_t key_offset,
size_t key_length,
55 hash_free_key free_element, uint32_t flags)
58 hash->array.init(
sizeof(HASH_LINK), size, growth_size);
59 hash->key_offset=key_offset;
60 hash->key_length=key_length;
62 hash->get_key=get_key;
63 hash->free=free_element;
65 hash->charset=charset;
80 static inline void hash_free_elements(HASH *hash)
84 HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);
85 HASH_LINK *end= data + hash->records;
87 (*hash->free)((data++)->data);
103 void hash_free(HASH *hash)
105 hash_free_elements(hash);
118 hash_key(
const HASH *hash,
const unsigned char *record,
size_t *length,
122 return (
char*) (*hash->get_key)(record,length,first);
123 *length=hash->key_length;
124 return (
char*) record+hash->key_offset;
129 static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)
131 if ((hashnr & (buffmax-1)) < maxlength)
return (hashnr & (buffmax-1));
132 return (hashnr & ((buffmax >> 1) -1));
135 static uint32_t hash_rec_mask(
const HASH *hash, HASH_LINK *pos,
136 uint32_t buffmax, uint32_t maxlength)
139 unsigned char *key= (
unsigned char*) hash_key(hash,pos->data,&length,0);
140 return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
147 unsigned int rec_hashnr(HASH *hash,
const unsigned char *record)
150 unsigned char *key= (
unsigned char*) hash_key(hash,record,&length,0);
151 return calc_hash(hash,key,length);
155 unsigned char* hash_search(
const HASH *hash,
const unsigned char *key,
158 HASH_SEARCH_STATE state;
159 return hash_first(hash, key, length, &state);
169 unsigned char* hash_first(
const HASH *hash,
const unsigned char *key,
171 HASH_SEARCH_STATE *current_record)
179 idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),
180 hash->blength,hash->records);
183 pos= dynamic_element(&hash->array,idx,HASH_LINK*);
184 if (!hashcmp(hash,pos,key,length))
186 *current_record= idx;
193 if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
198 while ((idx=pos->next) != NO_RECORD);
200 *current_record= NO_RECORD;
206 static void movelink(HASH_LINK *array, uint32_t find,
207 uint32_t next_link, uint32_t newlink)
212 old_link=array+next_link;
214 while ((next_link=old_link->next) != find);
215 old_link->next= newlink;
238 static int hashcmp(
const HASH *hash, HASH_LINK *pos,
const unsigned char *key,
241 size_t rec_keylength;
242 unsigned char *rec_key= (
unsigned char*) hash_key(hash, pos->data,
244 return ((length && length != rec_keylength) ||
245 my_strnncoll(hash->charset, rec_key, rec_keylength,
246 key, rec_keylength));
252 bool my_hash_insert(HASH *info,
const unsigned char *record)
256 uint32_t halfbuff,hash_nr,first_index;
257 unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
258 HASH_LINK *data,*empty,*gpos=NULL,*gpos2=NULL,*pos;
260 if (HASH_UNIQUE & info->flags)
262 unsigned char *key= (
unsigned char*) hash_key(info, record, &idx, 1);
263 if (hash_search(info, key, idx))
269 empty=(HASH_LINK*)info->array.alloc();
271 data=dynamic_element(&info->array,0,HASH_LINK*);
272 halfbuff= info->blength >> 1;
274 idx= first_index= info->records-halfbuff;
276 if (idx != info->records)
281 hash_nr=rec_hashnr(info,pos->data);
284 if (hash_mask(hash_nr,info->blength,info->records) != first_index)
286 if (!(hash_nr & halfbuff))
289 if (!(flag & LOWFIND))
293 flag=LOWFIND | HIGHFIND;
296 ptr_to_rec=pos->data;
303 flag=LOWFIND | LOWUSED;
305 ptr_to_rec=pos->data;
310 if (!(flag & LOWUSED))
313 gpos->data=ptr_to_rec;
314 gpos->next= (uint32_t) (pos-data);
315 flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
318 ptr_to_rec=pos->data;
324 if (!(flag & HIGHFIND))
326 flag= (flag & LOWFIND) | HIGHFIND;
328 gpos2 = empty; empty=pos;
329 ptr_to_rec2=pos->data;
333 if (!(flag & HIGHUSED))
336 gpos2->data=ptr_to_rec2;
337 gpos2->next=(uint32_t) (pos-data);
338 flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
341 ptr_to_rec2=pos->data;
345 while ((idx=pos->next) != NO_RECORD);
347 if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
349 gpos->data=ptr_to_rec;
350 gpos->next=NO_RECORD;
352 if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
354 gpos2->data=ptr_to_rec2;
355 gpos2->next=NO_RECORD;
360 idx=hash_mask(rec_hashnr(info,record),info->blength,info->records+1);
364 pos->data=(
unsigned char*) record;
371 gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
374 pos->data=(
unsigned char*) record;
375 pos->next=(uint32_t) (empty - data);
379 pos->data=(
unsigned char*) record;
381 movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data));
384 if (++info->records == info->blength)
385 info->blength+= info->blength;
TODO: Rename this file - func.h is stupid.