1 /* Copyright (c) 2000, 2010, Oracle and/or its affiliates.
2 Copyright (c) 2011, 2013, Monty Program Ab.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */
16
17 /* The hash functions used for saveing keys */
18 /* One of key_length or key_length_offset must be given */
19 /* Key length of 0 isn't allowed */
20
21 #include "mysys_priv.h"
22 #include <m_string.h>
23 #include <m_ctype.h>
24 #include "hash.h"
25
26 #define NO_RECORD ~((my_hash_value_type) 0)
27 #define LOWFIND 1
28 #define LOWUSED 2
29 #define HIGHFIND 4
30 #define HIGHUSED 8
31
32 typedef struct st_hash_info {
33 uint32 next; /* index to next key */
34 my_hash_value_type hash_nr;
35 uchar *data; /* data for current entry */
36 } HASH_LINK;
37
38 static uint my_hash_mask(my_hash_value_type hashnr,
39 size_t buffmax, size_t maxlength);
40 static void movelink(HASH_LINK *array,uint pos,uint next_link,uint newlink);
41 static int hashcmp(const HASH *hash, HASH_LINK *pos, const uchar *key,
42 size_t length);
43
my_hash_sort(CHARSET_INFO * cs,const uchar * key,size_t length)44 my_hash_value_type my_hash_sort(CHARSET_INFO *cs, const uchar *key,
45 size_t length)
46 {
47 ulong nr1= 1, nr2= 4;
48 cs->coll->hash_sort(cs, (uchar*) key, length, &nr1, &nr2);
49 return (my_hash_value_type) nr1;
50 }
51
52 /**
53 @brief Initialize the hash
54
55 @details
56
57 Initialize the hash, by defining and giving valid values for
58 its elements. The failure to allocate memory for the
59 hash->array element will not result in a fatal failure. The
60 dynamic array that is part of the hash will allocate memory
61 as required during insertion.
62
63 @param[in,out] hash The hash that is initialized
64 @param[in[ growth_size size incrememnt for the underlying dynarray
65 @param[in] charset The character set information
66 @param[in] size The hash size
67 @param[in] key_offest The key offset for the hash
68 @param[in] key_length The length of the key used in
69 the hash
70 @param[in] get_key get the key for the hash
71 @param[in] free_element pointer to the function that
72 does cleanup
73 @param[in] flags flags set in the hash
74 @return indicates success or failure of initialization
75 @retval 0 success
76 @retval 1 failure
77 */
78 my_bool
my_hash_init2(HASH * hash,uint growth_size,CHARSET_INFO * charset,ulong size,size_t key_offset,size_t key_length,my_hash_get_key get_key,my_hash_function hash_function,void (* free_element)(void *),uint flags)79 my_hash_init2(HASH *hash, uint growth_size, CHARSET_INFO *charset,
80 ulong size, size_t key_offset, size_t key_length,
81 my_hash_get_key get_key,
82 my_hash_function hash_function,
83 void (*free_element)(void*), uint flags)
84 {
85 my_bool res;
86 DBUG_ENTER("my_hash_init");
87 DBUG_PRINT("enter",("hash:%p size: %u", hash, (uint) size));
88
89 hash->records=0;
90 hash->key_offset=key_offset;
91 hash->key_length=key_length;
92 hash->blength=1;
93 hash->get_key=get_key;
94 hash->hash_function= hash_function ? hash_function : my_hash_sort;
95 hash->free=free_element;
96 hash->flags=flags;
97 hash->charset=charset;
98 res= init_dynamic_array2(&hash->array, sizeof(HASH_LINK), NULL, size,
99 growth_size, MYF((flags & HASH_THREAD_SPECIFIC ?
100 MY_THREAD_SPECIFIC : 0)));
101 DBUG_RETURN(res);
102 }
103
104
105 /*
106 Call hash->free on all elements in hash.
107
108 SYNOPSIS
109 my_hash_free_elements()
110 hash hash table
111
112 NOTES:
113 Sets records to 0
114 */
115
my_hash_free_elements(HASH * hash)116 static inline void my_hash_free_elements(HASH *hash)
117 {
118 uint records= hash->records;
119 if (records == 0)
120 return;
121
122 /*
123 Set records to 0 early to guard against anyone looking at the structure
124 during the free process
125 */
126 hash->records= 0;
127
128 if (hash->free)
129 {
130 HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);
131 HASH_LINK *end= data + records;
132 do
133 {
134 (*hash->free)((data++)->data);
135 } while (data < end);
136 }
137 }
138
139
140 /*
141 Free memory used by hash.
142
143 SYNOPSIS
144 my_hash_free()
145 hash the hash to delete elements of
146
147 NOTES: Hash can't be reused without calling my_hash_init again.
148 */
149
my_hash_free(HASH * hash)150 void my_hash_free(HASH *hash)
151 {
152 DBUG_ENTER("my_hash_free");
153 DBUG_PRINT("enter",("hash:%p elements: %ld",
154 hash, hash->records));
155
156 my_hash_free_elements(hash);
157 hash->free= 0;
158 delete_dynamic(&hash->array);
159 hash->blength= 0;
160 DBUG_VOID_RETURN;
161 }
162
163
164 /*
165 Delete all elements from the hash (the hash itself is to be reused).
166
167 SYNOPSIS
168 my_hash_reset()
169 hash the hash to delete elements of
170 */
171
my_hash_reset(HASH * hash)172 void my_hash_reset(HASH *hash)
173 {
174 DBUG_ENTER("my_hash_reset");
175 DBUG_PRINT("enter",("hash:%p", hash));
176
177 my_hash_free_elements(hash);
178 reset_dynamic(&hash->array);
179 /* Set row pointers so that the hash can be reused at once */
180 hash->blength= 1;
181 DBUG_VOID_RETURN;
182 }
183
184 /* some helper functions */
185
186 /*
187 This function is char* instead of uchar* as HPUX11 compiler can't
188 handle inline functions that are not defined as native types
189 */
190
191 static inline char*
my_hash_key(const HASH * hash,const uchar * record,size_t * length,my_bool first)192 my_hash_key(const HASH *hash, const uchar *record, size_t *length,
193 my_bool first)
194 {
195 if (hash->get_key)
196 return (char*) (*hash->get_key)(record,length,first);
197 *length=hash->key_length;
198 return (char*) record+hash->key_offset;
199 }
200
201 /* Calculate pos according to keys */
202
my_hash_mask(my_hash_value_type hashnr,size_t buffmax,size_t maxlength)203 static uint my_hash_mask(my_hash_value_type hashnr, size_t buffmax,
204 size_t maxlength)
205 {
206 if ((hashnr & (buffmax-1)) < maxlength)
207 return (uint) (hashnr & (buffmax-1));
208 return (uint) (hashnr & ((buffmax >> 1) -1));
209 }
210
my_hash_rec_mask(HASH_LINK * pos,size_t buffmax,size_t maxlength)211 static inline uint my_hash_rec_mask(HASH_LINK *pos,
212 size_t buffmax, size_t maxlength)
213 {
214 return my_hash_mask(pos->hash_nr, buffmax, maxlength);
215 }
216
217
218
219 /* for compilers which can not handle inline */
220 static
221 #if !defined(__USLC__) && !defined(__sgi)
222 inline
223 #endif
rec_hashnr(HASH * hash,const uchar * record)224 my_hash_value_type rec_hashnr(HASH *hash,const uchar *record)
225 {
226 size_t length;
227 uchar *key= (uchar*) my_hash_key(hash, record, &length, 0);
228 return hash->hash_function(hash->charset, key, length);
229 }
230
231
my_hash_search(const HASH * hash,const uchar * key,size_t length)232 uchar* my_hash_search(const HASH *hash, const uchar *key, size_t length)
233 {
234 HASH_SEARCH_STATE state;
235 return my_hash_first(hash, key, length, &state);
236 }
237
my_hash_search_using_hash_value(const HASH * hash,my_hash_value_type hash_value,const uchar * key,size_t length)238 uchar* my_hash_search_using_hash_value(const HASH *hash,
239 my_hash_value_type hash_value,
240 const uchar *key,
241 size_t length)
242 {
243 HASH_SEARCH_STATE state;
244 return my_hash_first_from_hash_value(hash, hash_value,
245 key, length, &state);
246 }
247
248
249 /*
250 Search after a record based on a key
251
252 NOTE
253 Assigns the number of the found record to HASH_SEARCH_STATE state
254 */
255
my_hash_first(const HASH * hash,const uchar * key,size_t length,HASH_SEARCH_STATE * current_record)256 uchar* my_hash_first(const HASH *hash, const uchar *key, size_t length,
257 HASH_SEARCH_STATE *current_record)
258 {
259 uchar *res;
260 DBUG_ASSERT(my_hash_inited(hash));
261
262 res= my_hash_first_from_hash_value(hash,
263 hash->hash_function(hash->charset, key,
264 length ? length :
265 hash->key_length),
266 key, length, current_record);
267 return res;
268 }
269
270
my_hash_first_from_hash_value(const HASH * hash,my_hash_value_type hash_value,const uchar * key,size_t length,HASH_SEARCH_STATE * current_record)271 uchar* my_hash_first_from_hash_value(const HASH *hash,
272 my_hash_value_type hash_value,
273 const uchar *key,
274 size_t length,
275 HASH_SEARCH_STATE *current_record)
276 {
277 HASH_LINK *pos;
278 DBUG_ENTER("my_hash_first_from_hash_value");
279
280 if (hash->records)
281 {
282 uint flag= 1;
283 uint idx= my_hash_mask(hash_value,
284 hash->blength, hash->records);
285 do
286 {
287 pos= dynamic_element(&hash->array,idx,HASH_LINK*);
288 if (!hashcmp(hash,pos,key,length))
289 {
290 DBUG_PRINT("exit",("found key at %d",idx));
291 *current_record= idx;
292 DBUG_RETURN (pos->data);
293 }
294 if (flag)
295 {
296 flag=0; /* Reset flag */
297 if (my_hash_rec_mask(pos, hash->blength, hash->records) != idx)
298 break; /* Wrong link */
299 }
300 }
301 while ((idx=pos->next) != NO_RECORD);
302 }
303 *current_record= NO_RECORD;
304 DBUG_RETURN(0);
305 }
306
307 /* Get next record with identical key */
308 /* Can only be called if previous calls was my_hash_search */
309
my_hash_next(const HASH * hash,const uchar * key,size_t length,HASH_SEARCH_STATE * current_record)310 uchar* my_hash_next(const HASH *hash, const uchar *key, size_t length,
311 HASH_SEARCH_STATE *current_record)
312 {
313 HASH_LINK *pos;
314 uint idx;
315
316 if (*current_record != NO_RECORD)
317 {
318 HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*);
319 for (idx=data[*current_record].next; idx != NO_RECORD ; idx=pos->next)
320 {
321 pos=data+idx;
322 if (!hashcmp(hash,pos,key,length))
323 {
324 *current_record= idx;
325 return pos->data;
326 }
327 }
328 *current_record= NO_RECORD;
329 }
330 return 0;
331 }
332
333
334 /* Change link from pos to new_link */
335
movelink(HASH_LINK * array,uint find,uint next_link,uint newlink)336 static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink)
337 {
338 HASH_LINK *old_link;
339 do
340 {
341 old_link=array+next_link;
342 }
343 while ((next_link=old_link->next) != find);
344 old_link->next= newlink;
345 return;
346 }
347
348 /*
349 Compare a key in a record to a whole key. Return 0 if identical
350
351 SYNOPSIS
352 hashcmp()
353 hash hash table
354 pos position of hash record to use in comparison
355 key key for comparison
356 length length of key
357
358 NOTES:
359 If length is 0, comparison is done using the length of the
360 record being compared against.
361
362 RETURN
363 = 0 key of record == key
364 != 0 key of record != key
365 */
366
hashcmp(const HASH * hash,HASH_LINK * pos,const uchar * key,size_t length)367 static int hashcmp(const HASH *hash, HASH_LINK *pos, const uchar *key,
368 size_t length)
369 {
370 size_t rec_keylength;
371 uchar *rec_key= (uchar*) my_hash_key(hash, pos->data, &rec_keylength, 1);
372 return ((length && length != rec_keylength) ||
373 my_strnncoll(hash->charset, (uchar*) rec_key, rec_keylength,
374 (uchar*) key, rec_keylength));
375 }
376
377
378 /**
379 Write a hash-key to the hash-index
380
381 @return
382 @retval 0 ok
383 @retval 1 Duplicate key or out of memory
384 */
385
my_hash_insert(HASH * info,const uchar * record)386 my_bool my_hash_insert(HASH *info, const uchar *record)
387 {
388 int flag;
389 size_t idx, halfbuff, first_index;
390 size_t length;
391 my_hash_value_type current_hash_nr, UNINIT_VAR(rec_hash_nr),
392 UNINIT_VAR(rec2_hash_nr);
393 uchar *UNINIT_VAR(rec_data),*UNINIT_VAR(rec2_data), *key;
394 HASH_LINK *data,*empty,*UNINIT_VAR(gpos),*UNINIT_VAR(gpos2),*pos;
395
396 key= (uchar*) my_hash_key(info, record, &length, 1);
397 current_hash_nr= info->hash_function(info->charset, key, length);
398
399 if (info->flags & HASH_UNIQUE)
400 {
401 if (my_hash_search_using_hash_value(info, current_hash_nr, key, length))
402 return(TRUE); /* Duplicate entry */
403 }
404
405 flag=0;
406 if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array)))
407 return(TRUE); /* No more memory */
408
409 data=dynamic_element(&info->array,0,HASH_LINK*);
410 halfbuff= info->blength >> 1;
411
412 idx=first_index=info->records-halfbuff;
413 if (idx != info->records) /* If some records */
414 {
415 do
416 {
417 my_hash_value_type hash_nr;
418 pos=data+idx;
419 hash_nr= pos->hash_nr;
420 if (flag == 0) /* First loop; Check if ok */
421 if (my_hash_mask(hash_nr, info->blength, info->records) != first_index)
422 break;
423 if (!(hash_nr & halfbuff))
424 { /* Key will not move */
425 if (!(flag & LOWFIND))
426 {
427 if (flag & HIGHFIND)
428 {
429 flag= LOWFIND | HIGHFIND;
430 /* key shall be moved to the current empty position */
431 gpos= empty;
432 rec_data= pos->data;
433 rec_hash_nr= pos->hash_nr;
434 empty=pos; /* This place is now free */
435 }
436 else
437 {
438 flag= LOWFIND | LOWUSED; /* key isn't changed */
439 gpos= pos;
440 rec_data= pos->data;
441 rec_hash_nr= pos->hash_nr;
442 }
443 }
444 else
445 {
446 if (!(flag & LOWUSED))
447 {
448 /* Change link of previous LOW-key */
449 gpos->data= rec_data;
450 gpos->hash_nr= rec_hash_nr;
451 gpos->next= (uint) (pos-data);
452 flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
453 }
454 gpos= pos;
455 rec_data= pos->data;
456 rec_hash_nr= pos->hash_nr;
457 }
458 }
459 else
460 { /* key will be moved */
461 if (!(flag & HIGHFIND))
462 {
463 flag= (flag & LOWFIND) | HIGHFIND;
464 /* key shall be moved to the last (empty) position */
465 gpos2= empty;
466 empty= pos;
467 rec2_data= pos->data;
468 rec2_hash_nr= pos->hash_nr;
469 }
470 else
471 {
472 if (!(flag & HIGHUSED))
473 {
474 /* Change link of previous hash-key and save */
475 gpos2->data= rec2_data;
476 gpos2->hash_nr= rec2_hash_nr;
477 gpos2->next= (uint) (pos-data);
478 flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
479 }
480 gpos2= pos;
481 rec2_data= pos->data;
482 rec2_hash_nr= pos->hash_nr;
483 }
484 }
485 }
486 while ((idx=pos->next) != NO_RECORD);
487
488 if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
489 {
490 gpos->data= rec_data;
491 gpos->hash_nr= rec_hash_nr;
492 gpos->next= NO_RECORD;
493 }
494 if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
495 {
496 gpos2->data= rec2_data;
497 gpos2->hash_nr= rec2_hash_nr;
498 gpos2->next= NO_RECORD;
499 }
500 }
501
502 idx= my_hash_mask(current_hash_nr, info->blength, info->records + 1);
503 pos= data+idx;
504 /* Check if we are at the empty position */
505 if (pos == empty)
506 {
507 pos->next=NO_RECORD;
508 }
509 else
510 {
511 /* Move conflicting record to empty position (last) */
512 empty[0]= pos[0];
513 /* Check if the moved record was in same hash-nr family */
514 gpos= data + my_hash_rec_mask(pos, info->blength, info->records + 1);
515 if (pos == gpos)
516 {
517 /* Point to moved record */
518 pos->next= (uint32) (empty - data);
519 }
520 else
521 {
522 pos->next= NO_RECORD;
523 movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data));
524 }
525 }
526 pos->data= (uchar*) record;
527 pos->hash_nr= current_hash_nr;
528 if (++info->records == info->blength)
529 info->blength+= info->blength;
530 return(0);
531 }
532
533
534 /**
535 Remove one record from hash-table.
536
537 @fn hash_delete()
538 @param hash Hash tree
539 @param record Row to be deleted
540
541 @notes
542 The record with the same record ptr is removed.
543 If there is a free-function it's called if record was found.
544
545 hash->free() is guarantee to be called only after the row has been
546 deleted from the hash and the hash can be reused by other threads.
547
548 @return
549 @retval 0 ok
550 @retval 1 Record not found
551 */
552
my_hash_delete(HASH * hash,uchar * record)553 my_bool my_hash_delete(HASH *hash, uchar *record)
554 {
555 uint pos2,idx,empty_index;
556 my_hash_value_type pos_hashnr, lastpos_hashnr;
557 size_t blength;
558 HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty;
559 DBUG_ENTER("my_hash_delete");
560 if (!hash->records)
561 DBUG_RETURN(1);
562
563 blength=hash->blength;
564 data=dynamic_element(&hash->array,0,HASH_LINK*);
565 /* Search after record with key */
566 pos= data + my_hash_mask(rec_hashnr(hash, record), blength, hash->records);
567 gpos = 0;
568
569 while (pos->data != record)
570 {
571 gpos=pos;
572 if (pos->next == NO_RECORD)
573 DBUG_RETURN(1); /* Key not found */
574 pos=data+pos->next;
575 }
576
577 if ( --(hash->records) < hash->blength >> 1) hash->blength>>=1;
578 lastpos=data+hash->records;
579
580 /* Remove link to record */
581 empty=pos; empty_index=(uint) (empty-data);
582 if (gpos)
583 gpos->next=pos->next; /* unlink current ptr */
584 else if (pos->next != NO_RECORD)
585 {
586 empty=data+(empty_index=pos->next);
587 pos[0]= empty[0];
588 }
589
590 if (empty == lastpos) /* last key at wrong pos or no next link */
591 goto exit;
592
593 /* Move the last key (lastpos) */
594 lastpos_hashnr= lastpos->hash_nr;
595 /* pos is where lastpos should be */
596 pos= data + my_hash_mask(lastpos_hashnr, hash->blength, hash->records);
597 if (pos == empty) /* Move to empty position. */
598 {
599 empty[0]=lastpos[0];
600 goto exit;
601 }
602 pos_hashnr= pos->hash_nr;
603 /* pos3 is where the pos should be */
604 pos3= data + my_hash_mask(pos_hashnr, hash->blength, hash->records);
605 if (pos != pos3)
606 { /* pos is on wrong posit */
607 empty[0]=pos[0]; /* Save it here */
608 pos[0]=lastpos[0]; /* This should be here */
609 movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index);
610 goto exit;
611 }
612 pos2= my_hash_mask(lastpos_hashnr, blength, hash->records + 1);
613 if (pos2 == my_hash_mask(pos_hashnr, blength, hash->records + 1))
614 { /* Identical key-positions */
615 if (pos2 != hash->records)
616 {
617 empty[0]=lastpos[0];
618 movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index);
619 goto exit;
620 }
621 idx= (uint) (pos-data); /* Link pos->next after lastpos */
622 }
623 else idx= NO_RECORD; /* Different positions merge */
624
625 empty[0]=lastpos[0];
626 movelink(data,idx,empty_index,pos->next);
627 pos->next=empty_index;
628
629 exit:
630 (void) pop_dynamic(&hash->array);
631 if (hash->free)
632 (*hash->free)((uchar*) record);
633 DBUG_RETURN(0);
634 }
635
636
637 /**
638 Update keys when record has changed.
639 This is much more efficient than using a delete & insert.
640 */
641
my_hash_update(HASH * hash,uchar * record,uchar * old_key,size_t old_key_length)642 my_bool my_hash_update(HASH *hash, uchar *record, uchar *old_key,
643 size_t old_key_length)
644 {
645 uint new_index, new_pos_index, org_index, records, idx;
646 size_t length, empty, blength;
647 my_hash_value_type hash_nr;
648 HASH_LINK org_link,*data,*previous,*pos;
649 uchar *new_key;
650 DBUG_ENTER("my_hash_update");
651
652 new_key= (uchar*) my_hash_key(hash, record, &length, 1);
653 hash_nr= hash->hash_function(hash->charset, new_key, length);
654
655 if (HASH_UNIQUE & hash->flags)
656 {
657 HASH_SEARCH_STATE state;
658 uchar *found;
659
660 if ((found= my_hash_first_from_hash_value(hash, hash_nr, new_key, length,
661 &state)))
662 {
663 do
664 {
665 if (found != record)
666 DBUG_RETURN(1); /* Duplicate entry */
667 }
668 while ((found= my_hash_next(hash, new_key, length, &state)));
669 }
670 }
671
672 data=dynamic_element(&hash->array,0,HASH_LINK*);
673 blength=hash->blength; records=hash->records;
674
675 /* Search after record with key */
676
677 idx= my_hash_mask(hash->hash_function(hash->charset, old_key,
678 (old_key_length ? old_key_length :
679 hash->key_length)),
680 blength, records);
681 org_index= idx;
682 new_index= my_hash_mask(hash_nr, blength, records);
683 previous=0;
684 for (;;)
685 {
686 if ((pos= data+idx)->data == record)
687 break;
688 previous=pos;
689 if ((idx=pos->next) == NO_RECORD)
690 DBUG_RETURN(1); /* Not found in links */
691 }
692
693 if (org_index == new_index)
694 {
695 data[idx].hash_nr= hash_nr; /* Hash number may have changed */
696 DBUG_RETURN(0); /* Record is in right position */
697 }
698
699 org_link= *pos;
700 empty=idx;
701
702 /* Relink record from current chain */
703
704 if (!previous)
705 {
706 if (pos->next != NO_RECORD)
707 {
708 empty=pos->next;
709 *pos= data[pos->next];
710 }
711 }
712 else
713 previous->next=pos->next; /* unlink pos */
714
715 /* Move data to correct position */
716 if (new_index == empty)
717 {
718 /*
719 At this point record is unlinked from the old chain, thus it holds
720 random position. By the chance this position is equal to position
721 for the first element in the new chain. That means updated record
722 is the only record in the new chain.
723 */
724 if (empty != idx)
725 {
726 /*
727 Record was moved while unlinking it from the old chain.
728 Copy data to a new position.
729 */
730 data[empty]= org_link;
731 }
732 data[empty].next= NO_RECORD;
733 data[empty].hash_nr= hash_nr;
734 DBUG_RETURN(0);
735 }
736 pos=data+new_index;
737 new_pos_index= my_hash_rec_mask(pos, blength, records);
738 if (new_index != new_pos_index)
739 { /* Other record in wrong position */
740 data[empty]= *pos;
741 movelink(data,new_index,new_pos_index, (uint) empty);
742 org_link.next=NO_RECORD;
743 data[new_index]= org_link;
744 data[new_index].hash_nr= hash_nr;
745 }
746 else
747 { /* Link in chain at right position */
748 org_link.next=data[new_index].next;
749 data[empty]=org_link;
750 data[empty].hash_nr= hash_nr;
751 data[new_index].next= (uint) empty;
752 }
753 DBUG_RETURN(0);
754 }
755
756
my_hash_element(HASH * hash,size_t idx)757 uchar *my_hash_element(HASH *hash, size_t idx)
758 {
759 if (idx < hash->records)
760 return dynamic_element(&hash->array,idx,HASH_LINK*)->data;
761 return 0;
762 }
763
764
765 /*
766 Replace old row with new row. This should only be used when key
767 isn't changed
768 */
769
my_hash_replace(HASH * hash,HASH_SEARCH_STATE * current_record,uchar * new_row)770 void my_hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record,
771 uchar *new_row)
772 {
773 if (*current_record != NO_RECORD) /* Safety */
774 dynamic_element(&hash->array, *current_record, HASH_LINK*)->data= new_row;
775 }
776
777
778 /**
779 Iterate over all elements in hash and call function with the element
780
781 @param hash hash array
782 @param action function to call for each argument
783 @param argument second argument for call to action
784
785 @notes
786 If one of functions calls returns 1 then the iteration aborts
787
788 @retval 0 ok
789 @retval 1 iteration aborted becasue action returned 1
790 */
791
my_hash_iterate(HASH * hash,my_hash_walk_action action,void * argument)792 my_bool my_hash_iterate(HASH *hash, my_hash_walk_action action, void *argument)
793 {
794 uint records, i;
795
796 records= hash->records;
797
798 for (i= 0 ; i < records ; i++)
799 {
800 if ((*action)(dynamic_element(&hash->array, i, HASH_LINK *)->data,
801 argument))
802 return 1;
803 }
804 return 0;
805 }
806
807
808 #if !defined(DBUG_OFF) || defined(MAIN)
809
my_hash_check(HASH * hash)810 my_bool my_hash_check(HASH *hash)
811 {
812 int error;
813 uint i,rec_link,found,max_links,seek,links,idx;
814 uint records;
815 size_t blength;
816 HASH_LINK *data,*hash_info;
817
818 records=hash->records; blength=hash->blength;
819 data=dynamic_element(&hash->array,0,HASH_LINK*);
820 error=0;
821
822 for (i=found=max_links=seek=0 ; i < records ; i++)
823 {
824 size_t length;
825 uchar *key= (uchar*) my_hash_key(hash, data[i].data, &length, 0);
826 if (data[i].hash_nr != hash->hash_function(hash->charset, key, length))
827 {
828 DBUG_PRINT("error", ("record at %d has wrong hash", i));
829 error= 1;
830 }
831
832 if (my_hash_rec_mask(data + i, blength, records) == i)
833 {
834 found++; seek++; links=1;
835 for (idx=data[i].next ;
836 idx != NO_RECORD && found < records + 1;
837 idx=hash_info->next)
838 {
839 if (idx >= records)
840 {
841 DBUG_PRINT("error",
842 ("Found pointer outside array to %d from link starting at %d",
843 idx,i));
844 error=1;
845 }
846 hash_info=data+idx;
847 seek+= ++links;
848 if ((rec_link= my_hash_rec_mask(hash_info,
849 blength, records)) != i)
850 {
851 DBUG_PRINT("error", ("Record in wrong link at %d: Start %d "
852 "Record:%p Record-link %d",
853 idx, i, hash_info->data, rec_link));
854 error=1;
855 }
856 else
857 found++;
858 }
859 if (links > max_links) max_links=links;
860 }
861 }
862 if (found != records)
863 {
864 DBUG_PRINT("error",("Found %u of %u records", found, records));
865 error=1;
866 }
867 if (records)
868 DBUG_PRINT("info",
869 ("records: %u seeks: %d max links: %d hitrate: %.2f",
870 records,seek,max_links,(float) seek / (float) records));
871 DBUG_ASSERT(error == 0);
872 return error;
873 }
874 #endif
875
876 #ifdef MAIN
877
878 #define RECORDS 1000
879
test_get_key(uchar * data,size_t * length,my_bool not_used)880 uchar *test_get_key(uchar *data, size_t *length,
881 my_bool not_used __attribute__((unused)))
882 {
883 *length= 2;
884 return data;
885 }
886
887
main(int argc,char ** argv)888 int main(int argc __attribute__((unused)),char **argv __attribute__((unused)))
889 {
890 uchar records[RECORDS][2], copy[2];
891 HASH hash_test;
892 uint i;
893 MY_INIT(argv[0]);
894 DBUG_PUSH("d:t:O,/tmp/test_hash.trace");
895
896 printf("my_hash_init\n");
897 if (my_hash_init2(&hash_test, 100, &my_charset_bin, 20,
898 0, 0, (my_hash_get_key) test_get_key, 0, 0, HASH_UNIQUE))
899 {
900 fprintf(stderr, "hash init failed\n");
901 exit(1);
902 }
903
904 printf("my_hash_insert\n");
905 for (i= 0 ; i < RECORDS ; i++)
906 {
907 int2store(records[i],i);
908 my_hash_insert(&hash_test, records[i]);
909 my_hash_check(&hash_test);
910 }
911 printf("my_hash_update\n");
912 for (i= 0 ; i < RECORDS ; i+=2)
913 {
914 memcpy(copy, records[i], 2);
915 int2store(records[i],i + RECORDS);
916 if (my_hash_update(&hash_test, records[i], copy, 2))
917 {
918 fprintf(stderr, "hash update failed\n");
919 exit(1);
920 }
921 my_hash_check(&hash_test);
922 }
923 printf("my_hash_delete\n");
924 for (i= 0 ; i < RECORDS ; i++)
925 {
926 if (my_hash_delete(&hash_test, records[i]))
927 {
928 fprintf(stderr, "hash delete failed\n");
929 exit(1);
930 }
931 my_hash_check(&hash_test);
932 }
933 my_hash_free(&hash_test);
934 printf("ok\n");
935 my_end(MY_CHECK_ERROR);
936 return(0);
937 }
938 #endif /* MAIN */
939