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