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