drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
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
29namespace drizzled {
30
31const uint32_t NO_RECORD= UINT32_MAX;
32
33const int LOWFIND= 1;
34const int LOWUSED= 2;
35const int HIGHFIND= 4;
36const int HIGHUSED= 8;
37
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);
41
42static 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
51void
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
80static 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
103void 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
112static inline const unsigned char*
113hash_key(const HASH *hash, const unsigned char *record, size_t *length,
114 bool first)
115{
116 if (hash->get_key)
117 return (*hash->get_key)(record,length,first);
118 *length=hash->key_length;
119 return record+hash->key_offset;
120}
121
122/* Calculate pos according to keys */
123
124static uint32_t hash_mask(uint32_t hashnr,uint32_t buffmax,uint32_t maxlength)
125{
126 if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
127 return (hashnr & ((buffmax >> 1) -1));
128}
129
130static uint32_t hash_rec_mask(const HASH *hash, HASH_LINK *pos,
131 uint32_t buffmax, uint32_t maxlength)
132{
133 size_t length;
134 const unsigned char *key= hash_key(hash,pos->data,&length,0);
135 return hash_mask(calc_hash(hash,key,length),buffmax,maxlength);
136}
137
138
139
140static
141inline
142unsigned int rec_hashnr(HASH *hash,const unsigned char *record)
143{
144 size_t length;
145 const unsigned char *key= hash_key(hash,record,&length,0);
146 return calc_hash(hash,key,length);
147}
148
149
150unsigned char* hash_search(const HASH *hash, const unsigned char *key,
151 size_t length)
152{
153 HASH_SEARCH_STATE state;
154 return hash_first(hash, key, length, &state);
155}
156
157/*
158 Search after a record based on a key
159
160 NOTE
161 Assigns the number of the found record to HASH_SEARCH_STATE state
162*/
163
164unsigned char* hash_first(const HASH *hash, const unsigned char *key,
165 size_t length,
166 HASH_SEARCH_STATE *current_record)
167{
168 HASH_LINK *pos;
169 uint32_t flag,idx;
170
171 flag=1;
172 if (hash->records)
173 {
174 idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length),
175 hash->blength,hash->records);
176 do
177 {
178 pos= dynamic_element(&hash->array,idx,HASH_LINK*);
179 if (!hashcmp(hash,pos,key,length))
180 {
181 *current_record= idx;
182 return (pos->data);
183 }
184 if (flag)
185 {
186 /* Reset flag */
187 flag=0;
188 if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx)
189 /* Wrong link */
190 break;
191 }
192 }
193 while ((idx=pos->next) != NO_RECORD);
194 }
195 *current_record= NO_RECORD;
196 return 0;
197}
198
199/* Change link from pos to new_link */
200
201static void movelink(HASH_LINK *array, uint32_t find,
202 uint32_t next_link, uint32_t newlink)
203{
204 HASH_LINK *old_link;
205 do
206 {
207 old_link=array+next_link;
208 }
209 while ((next_link=old_link->next) != find);
210 old_link->next= newlink;
211 return;
212}
213
214/*
215 Compare a key in a record to a whole key. Return 0 if identical
216
217 SYNOPSIS
218 hashcmp()
219 hash hash table
220 pos position of hash record to use in comparison
221 key key for comparison
222 length length of key
223
224 NOTES:
225 If length is 0, comparison is done using the length of the
226 record being compared against.
227
228 RETURN
229 = 0 key of record == key
230 != 0 key of record != key
231*/
232
233static int hashcmp(const HASH *hash, HASH_LINK *pos, const unsigned char *key,
234 size_t length)
235{
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));
241}
242
243
244/* Write a hash-key to the hash-index */
245
246bool my_hash_insert(HASH *info,const unsigned char *record)
247{
248 int flag;
249 size_t idx;
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;
253
254 if (HASH_UNIQUE & info->flags)
255 {
256 const unsigned char *key= hash_key(info, record, &idx, 1);
257 if (hash_search(info, key, idx))
258 /* Duplicate entry */
259 return true;
260 }
261
262 flag=0;
263 empty=(HASH_LINK*)info->array.alloc();
264
265 data=dynamic_element(&info->array,0,HASH_LINK*);
266 halfbuff= info->blength >> 1;
267
268 idx= first_index= info->records-halfbuff;
269 /* If some records */
270 if (idx != info->records)
271 {
272 do
273 {
274 pos=data+idx;
275 hash_nr=rec_hashnr(info,pos->data);
276 /* First loop; Check if ok */
277 if (flag == 0)
278 if (hash_mask(hash_nr,info->blength,info->records) != first_index)
279 break;
280 if (!(hash_nr & halfbuff))
281 {
282 /* Key will not move */
283 if (!(flag & LOWFIND))
284 {
285 if (flag & HIGHFIND)
286 {
287 flag=LOWFIND | HIGHFIND;
288 /* key shall be moved to the current empty position */
289 gpos=empty;
290 ptr_to_rec=pos->data;
291 /* This place is now free */
292 empty=pos;
293 }
294 else
295 {
296 /* key isn't changed */
297 flag=LOWFIND | LOWUSED;
298 gpos=pos;
299 ptr_to_rec=pos->data;
300 }
301 }
302 else
303 {
304 if (!(flag & LOWUSED))
305 {
306 /* Change link of previous LOW-key */
307 gpos->data=ptr_to_rec;
308 gpos->next= (uint32_t) (pos-data);
309 flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
310 }
311 gpos=pos;
312 ptr_to_rec=pos->data;
313 }
314 }
315 else
316 {
317 /* key will be moved */
318 if (!(flag & HIGHFIND))
319 {
320 flag= (flag & LOWFIND) | HIGHFIND;
321 /* key shall be moved to the last (empty) position */
322 gpos2 = empty; empty=pos;
323 ptr_to_rec2=pos->data;
324 }
325 else
326 {
327 if (!(flag & HIGHUSED))
328 {
329 /* Change link of previous hash-key and save */
330 gpos2->data=ptr_to_rec2;
331 gpos2->next=(uint32_t) (pos-data);
332 flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
333 }
334 gpos2=pos;
335 ptr_to_rec2=pos->data;
336 }
337 }
338 }
339 while ((idx=pos->next) != NO_RECORD);
340
341 if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
342 {
343 gpos->data=ptr_to_rec;
344 gpos->next=NO_RECORD;
345 }
346 if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
347 {
348 gpos2->data=ptr_to_rec2;
349 gpos2->next=NO_RECORD;
350 }
351 }
352 /* Check if we are at the empty position */
353
354 idx=hash_mask(rec_hashnr(info,record),info->blength,info->records+1);
355 pos=data+idx;
356 if (pos == empty)
357 {
358 pos->data=(unsigned char*) record;
359 pos->next=NO_RECORD;
360 }
361 else
362 {
363 /* Check if more records in same hash-nr family */
364 empty[0]=pos[0];
365 gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1);
366 if (pos == gpos)
367 {
368 pos->data=(unsigned char*) record;
369 pos->next=(uint32_t) (empty - data);
370 }
371 else
372 {
373 pos->data=(unsigned char*) record;
374 pos->next=NO_RECORD;
375 movelink(data,(uint32_t) (pos-data),(uint32_t) (gpos-data),(uint32_t) (empty-data));
376 }
377 }
378 if (++info->records == info->blength)
379 info->blength+= info->blength;
380 return 0;
381}
382
383} /* namespace drizzled */
TODO: Rename this file - func.h is stupid.