Drizzled Public API Documentation

my_hash.cc
1 /* -*- mode: c++; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2  * vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3  *
4  * Copyright (C) 2008 Sun Microsystems, Inc.
5  *
6  * This program is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; version 2 of the License.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18  */
19 
20 /* The hash functions used for saving keys */
21 /* One of key_length or key_length_offset must be given */
22 /* Key length of 0 isn't allowed */
23 
24 #include <config.h>
25 #include <drizzled/my_hash.h>
26 #include <drizzled/charset.h>
27 #include <vector>
28 
29 namespace drizzled {
30 
31 const uint32_t NO_RECORD= UINT32_MAX;
32 
33 const int LOWFIND= 1;
34 const int LOWUSED= 2;
35 const int HIGHFIND= 4;
36 const int HIGHUSED= 8;
37 
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);
41 
42 static uint32_t calc_hash(const HASH *hash, const unsigned char *key, size_t length)
43 {
44  uint32_t nr1=1, nr2=4;
45  hash->charset->coll->hash_sort(hash->charset, key,length, &nr1, &nr2);
46  return nr1;
47 }
48 
49 #define dynamic_element(array,array_index,type) ((type)((array)->buffer) +(array_index))
50 
51 void
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,
54  hash_get_key get_key,
55  hash_free_key free_element, uint32_t flags)
56 {
57  hash->records=0;
58  hash->array.init(sizeof(HASH_LINK), size, growth_size);
59  hash->key_offset=key_offset;
60  hash->key_length=key_length;
61  hash->blength=1;
62  hash->get_key=get_key;
63  hash->free=free_element;
64  hash->flags=flags;
65  hash->charset=charset;
66 }
67 
68 
69 /*
70  Call hash->free on all elements in hash.
71 
72  SYNOPSIS
73  hash_free_elements()
74  hash hash table
75 
76  NOTES:
77  Sets records to 0
78 */
79 
80 static inline void hash_free_elements(HASH *hash)
81 {
82  if (hash->free)
83  {
84  HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);
85  HASH_LINK *end= data + hash->records;
86  while (data < end)
87  (*hash->free)((data++)->data);
88  }
89  hash->records=0;
90 }
91 
92 
93 /*
94  Free memory used by hash.
95 
96  SYNOPSIS
97  hash_free()
98  hash the hash to delete elements of
99 
100  NOTES: Hash can't be reused without calling hash_init again.
101 */
102 
103 void hash_free(HASH *hash)
104 {
105  hash_free_elements(hash);
106  hash->free= 0;
107  hash->array.free();
108 }
109 
110 /* some helper functions */
111 
112 /*
113  This function is char* instead of unsigned char* as HPUX11 compiler can't
114  handle inline functions that are not defined as native types
115 */
116 
117 static inline char*
118 hash_key(const HASH *hash, const unsigned char *record, size_t *length,
119  bool first)
120 {
121  if (hash->get_key)
122  return (char*) (*hash->get_key)(record,length,first);
123  *length=hash->key_length;
124  return (char*) record+hash->key_offset;
125 }
126 
127 /* Calculate pos according to keys */
128 
129 static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)
130 {
131  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
132  return (hashnr & ((buffmax >> 1) -1));
133 }
134 
135 static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
136  uint32_t buffmax, uint32_t maxlength)
137 {
138  size_t length;
139  unsigned char *key= (unsigned char*) hash_key(hash,pos->data,&length,0);
140  return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
141 }
142 
143 
144 
145 static
146 inline
147 unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
148 {
149  size_t length;
150  unsigned char *key= (unsigned char*) hash_key(hash,record,&length,0);
151  return calc_hash(hash,key,length);
152 }
153 
154 
155 unsigned char* hash_search(const HASH *hash, const unsigned char *key,
156  size_t length)
157 {
158  HASH_SEARCH_STATE state;
159  return hash_first(hash, key, length, &state);
160 }
161 
162 /*
163  Search after a record based on a key
164 
165  NOTE
166  Assigns the number of the found record to HASH_SEARCH_STATE state
167 */
168 
169 unsigned char* hash_first(const HASH *hash, const unsigned char *key,
170  size_t length,
171  HASH_SEARCH_STATE *current_record)
172 {
173  HASH_LINK *pos;
174  uint32_t flag,idx;
175 
176  flag=1;
177  if (hash->records)
178  {
179  idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),
180  hash->blength,hash->records);
181  do
182  {
183  pos= dynamic_element(&hash->array,idx,HASH_LINK*);
184  if (!hashcmp(hash,pos,key,length))
185  {
186  *current_record= idx;
187  return (pos->data);
188  }
189  if (flag)
190  {
191  /* Reset flag */
192  flag=0;
193  if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
194  /* Wrong link */
195  break;
196  }
197  }
198  while ((idx=pos->next) != NO_RECORD);
199  }
200  *current_record= NO_RECORD;
201  return 0;
202 }
203 
204 /* Change link from pos to new_link */
205 
206 static void movelink(HASH_LINK *array, uint32_t find,
207  uint32_t next_link, uint32_t newlink)
208 {
209  HASH_LINK *old_link;
210  do
211  {
212  old_link=array+next_link;
213  }
214  while ((next_link=old_link->next) != find);
215  old_link->next= newlink;
216  return;
217 }
218 
219 /*
220  Compare a key in a record to a whole key. Return 0 if identical
221 
222  SYNOPSIS
223  hashcmp()
224  hash hash table
225  pos position of hash record to use in comparison
226  key key for comparison
227  length length of key
228 
229  NOTES:
230  If length is 0, comparison is done using the length of the
231  record being compared against.
232 
233  RETURN
234  = 0 key of record == key
235  != 0 key of record != key
236 */
237 
238 static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,
239  size_t length)
240 {
241  size_t rec_keylength;
242  unsigned char *rec_key= (unsigned char*) hash_key(hash, pos->data,
243  &rec_keylength,1);
244  return ((length && length != rec_keylength) ||
245  my_strnncoll(hash->charset, rec_key, rec_keylength,
246  key, rec_keylength));
247 }
248 
249 
250 /* Write a hash-key to the hash-index */
251 
252 bool my_hash_insert(HASH *info,const unsigned char *record)
253 {
254  int flag;
255  size_t idx;
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;
259 
260  if (HASH_UNIQUE & info->flags)
261  {
262  unsigned char *key= (unsigned char*) hash_key(info, record, &idx, 1);
263  if (hash_search(info, key, idx))
264  /* Duplicate entry */
265  return true;
266  }
267 
268  flag=0;
269  empty=(HASH_LINK*)info->array.alloc();
270 
271  data=dynamic_element(&info->array,0,HASH_LINK*);
272  halfbuff= info->blength >> 1;
273 
274  idx= first_index= info->records-halfbuff;
275  /* If some records */
276  if (idx != info->records)
277  {
278  do
279  {
280  pos=data+idx;
281  hash_nr=rec_hashnr(info,pos->data);
282  /* First loop; Check if ok */
283  if (flag == 0)
284  if (hash_mask(hash_nr,info->blength,info->records) != first_index)
285  break;
286  if (!(hash_nr & halfbuff))
287  {
288  /* Key will not move */
289  if (!(flag & LOWFIND))
290  {
291  if (flag & HIGHFIND)
292  {
293  flag=LOWFIND | HIGHFIND;
294  /* key shall be moved to the current empty position */
295  gpos=empty;
296  ptr_to_rec=pos->data;
297  /* This place is now free */
298  empty=pos;
299  }
300  else
301  {
302  /* key isn't changed */
303  flag=LOWFIND | LOWUSED;
304  gpos=pos;
305  ptr_to_rec=pos->data;
306  }
307  }
308  else
309  {
310  if (!(flag & LOWUSED))
311  {
312  /* Change link of previous LOW-key */
313  gpos->data=ptr_to_rec;
314  gpos->next= (uint32_t) (pos-data);
315  flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
316  }
317  gpos=pos;
318  ptr_to_rec=pos->data;
319  }
320  }
321  else
322  {
323  /* key will be moved */
324  if (!(flag & HIGHFIND))
325  {
326  flag= (flag & LOWFIND) | HIGHFIND;
327  /* key shall be moved to the last (empty) position */
328  gpos2 = empty; empty=pos;
329  ptr_to_rec2=pos->data;
330  }
331  else
332  {
333  if (!(flag & HIGHUSED))
334  {
335  /* Change link of previous hash-key and save */
336  gpos2->data=ptr_to_rec2;
337  gpos2->next=(uint32_t) (pos-data);
338  flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
339  }
340  gpos2=pos;
341  ptr_to_rec2=pos->data;
342  }
343  }
344  }
345  while ((idx=pos->next) != NO_RECORD);
346 
347  if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
348  {
349  gpos->data=ptr_to_rec;
350  gpos->next=NO_RECORD;
351  }
352  if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
353  {
354  gpos2->data=ptr_to_rec2;
355  gpos2->next=NO_RECORD;
356  }
357  }
358  /* Check if we are at the empty position */
359 
360  idx=hash_mask(rec_hashnr(info,record),info->blength,info->records+1);
361  pos=data+idx;
362  if (pos == empty)
363  {
364  pos->data=(unsigned char*) record;
365  pos->next=NO_RECORD;
366  }
367  else
368  {
369  /* Check if more records in same hash-nr family */
370  empty[0]=pos[0];
371  gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
372  if (pos == gpos)
373  {
374  pos->data=(unsigned char*) record;
375  pos->next=(uint32_t) (empty - data);
376  }
377  else
378  {
379  pos->data=(unsigned char*) record;
380  pos->next=NO_RECORD;
381  movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data));
382  }
383  }
384  if (++info->records == info->blength)
385  info->blength+= info->blength;
386  return 0;
387 }
388 
389 } /* namespace drizzled */