25#include <drizzled/my_hash.h>
26#include <drizzled/charset.h>
31const uint32_t NO_RECORD= UINT32_MAX;
38static uint32_t hash_mask(uint32_t hashnr, uint32_t buffmax, uint32_t maxlength);
39static void movelink(
HASH_LINK *array, uint32_t pos, uint32_t next_link, uint32_t newlink);
40static int hashcmp(
const HASH *hash,
HASH_LINK *pos,
const unsigned char *key,
size_t length);
42static 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))
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;
80static inline void hash_free_elements(
HASH *hash)
87 (*hash->free)((data++)->data);
103void hash_free(
HASH *hash)
105 hash_free_elements(hash);
112static inline const unsigned char*
113hash_key(
const HASH *hash,
const unsigned char *record,
size_t *length,
117 return (*hash->get_key)(record,length,first);
118 *length=hash->key_length;
119 return record+hash->key_offset;
124static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)
126 if ((hashnr & (buffmax-1)) < maxlength)
return (hashnr & (buffmax-1));
127 return (hashnr & ((buffmax >> 1) -1));
130static uint32_t hash_rec_mask(
const HASH *hash,
HASH_LINK *pos,
131 uint32_t buffmax, uint32_t maxlength)
134 const unsigned char *key= hash_key(hash,pos->data,&length,0);
135 return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
142unsigned int rec_hashnr(
HASH *hash,
const unsigned char *record)
145 const unsigned char *key= hash_key(hash,record,&length,0);
146 return calc_hash(hash,key,length);
150unsigned char* hash_search(
const HASH *hash,
const unsigned char *key,
153 HASH_SEARCH_STATE state;
154 return hash_first(hash, key, length, &state);
164unsigned char* hash_first(
const HASH *hash,
const unsigned char *key,
166 HASH_SEARCH_STATE *current_record)
174 idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),
175 hash->blength,hash->records);
178 pos= dynamic_element(&hash->array,idx,
HASH_LINK*);
179 if (!hashcmp(hash,pos,key,length))
181 *current_record= idx;
188 if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
193 while ((idx=pos->next) != NO_RECORD);
195 *current_record= NO_RECORD;
201static void movelink(
HASH_LINK *array, uint32_t find,
202 uint32_t next_link, uint32_t newlink)
207 old_link=array+next_link;
209 while ((next_link=old_link->next) != find);
210 old_link->next= newlink;
233static int hashcmp(
const HASH *hash,
HASH_LINK *pos,
const unsigned char *key,
236 size_t rec_keylength;
237 const unsigned char *rec_key= hash_key(hash, pos->data, &rec_keylength,1);
238 return ((length && length != rec_keylength) ||
239 my_strnncoll(hash->charset, rec_key, rec_keylength,
240 key, rec_keylength));
246bool my_hash_insert(
HASH *info,
const unsigned char *record)
250 uint32_t halfbuff,hash_nr,first_index;
251 unsigned char *ptr_to_rec=NULL,*ptr_to_rec2=NULL;
252 HASH_LINK *data,*empty,*gpos=NULL,*gpos2=NULL,*pos;
254 if (HASH_UNIQUE & info->flags)
256 const unsigned char *key= hash_key(info, record, &idx, 1);
257 if (hash_search(info, key, idx))
265 data=dynamic_element(&info->array,0,
HASH_LINK*);
266 halfbuff= info->blength >> 1;
268 idx= first_index= info->records-halfbuff;
270 if (idx != info->records)
275 hash_nr=rec_hashnr(info,pos->data);
278 if (hash_mask(hash_nr,info->blength,info->records) != first_index)
280 if (!(hash_nr & halfbuff))
283 if (!(flag & LOWFIND))
287 flag=LOWFIND | HIGHFIND;
290 ptr_to_rec=pos->data;
297 flag=LOWFIND | LOWUSED;
299 ptr_to_rec=pos->data;
304 if (!(flag & LOWUSED))
307 gpos->data=ptr_to_rec;
308 gpos->next= (uint32_t) (pos-data);
309 flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
312 ptr_to_rec=pos->data;
318 if (!(flag & HIGHFIND))
320 flag= (flag & LOWFIND) | HIGHFIND;
322 gpos2 = empty; empty=pos;
323 ptr_to_rec2=pos->data;
327 if (!(flag & HIGHUSED))
330 gpos2->data=ptr_to_rec2;
331 gpos2->next=(uint32_t) (pos-data);
332 flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
335 ptr_to_rec2=pos->data;
339 while ((idx=pos->next) != NO_RECORD);
341 if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
343 gpos->data=ptr_to_rec;
344 gpos->next=NO_RECORD;
346 if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
348 gpos2->data=ptr_to_rec2;
349 gpos2->next=NO_RECORD;
354 idx=hash_mask(rec_hashnr(info,record),info->blength,info->records+1);
358 pos->data=(
unsigned char*) record;
365 gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
368 pos->data=(
unsigned char*) record;
369 pos->next=(uint32_t) (empty - data);
373 pos->data=(
unsigned char*) record;
375 movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data));
378 if (++info->records == info->blength)
379 info->blength+= info->blength;
TODO: Rename this file - func.h is stupid.