The world's most popular open source database
mysql/src/5.1-dbg/libmysql/hash.c
Go to the documentation of this file.00001 /* Copyright (C) 2000 MySQL AB 00002 00003 This program is free software; you can redistribute it and/or modify 00004 it under the terms of the GNU General Public License as published by 00005 the Free Software Foundation; either version 2 of the License, or 00006 (at your option) any later version. 00007 00008 This program is distributed in the hope that it will be useful, 00009 but WITHOUT ANY WARRANTY; without even the implied warranty of 00010 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00011 GNU General Public License for more details. 00012 00013 You should have received a copy of the GNU General Public License 00014 along with this program; if not, write to the Free Software 00015 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ 00016 00017 /* The hash functions used for saveing keys */ 00018 /* One of key_length or key_length_offset must be given */ 00019 /* Key length of 0 isn't allowed */ 00020 00021 #include "mysys_priv.h" 00022 #include <m_string.h> 00023 #include <m_ctype.h> 00024 #include "hash.h" 00025 00026 #define NO_RECORD ((uint) -1) 00027 #define LOWFIND 1 00028 #define LOWUSED 2 00029 #define HIGHFIND 4 00030 #define HIGHUSED 8 00031 00032 typedef struct st_hash_info { 00033 uint next; /* index to next key */ 00034 byte *data; /* data for current entry */ 00035 } HASH_LINK; 00036 00037 static uint hash_mask(uint hashnr,uint buffmax,uint maxlength); 00038 static void movelink(HASH_LINK *array,uint pos,uint next_link,uint newlink); 00039 static int hashcmp(const HASH *hash, HASH_LINK *pos, const byte *key, 00040 uint length); 00041 00042 static uint calc_hash(const HASH *hash, const byte *key, uint length) 00043 { 00044 ulong nr1=1, nr2=4; 00045 hash->charset->coll->hash_sort(hash->charset,(uchar*) key,length,&nr1,&nr2); 00046 return nr1; 00047 } 00048 00049 my_bool 00050 _hash_init(HASH *hash,CHARSET_INFO *charset, 00051 uint size,uint key_offset,uint key_length, 00052 hash_get_key get_key, 00053 void (*free_element)(void*),uint flags CALLER_INFO_PROTO) 00054 { 00055 DBUG_ENTER("hash_init"); 00056 DBUG_PRINT("enter",("hash: 0x%lx size: %d",hash,size)); 00057 00058 hash->records=0; 00059 if (my_init_dynamic_array_ci(&hash->array,sizeof(HASH_LINK),size,0)) 00060 { 00061 hash->free=0; /* Allow call to hash_free */ 00062 DBUG_RETURN(1); 00063 } 00064 hash->key_offset=key_offset; 00065 hash->key_length=key_length; 00066 hash->blength=1; 00067 hash->get_key=get_key; 00068 hash->free=free_element; 00069 hash->flags=flags; 00070 hash->charset=charset; 00071 DBUG_RETURN(0); 00072 } 00073 00074 00075 /* 00076 Call hash->free on all elements in hash. 00077 00078 SYNOPSIS 00079 hash_free_elements() 00080 hash hash table 00081 00082 NOTES: 00083 Sets records to 0 00084 */ 00085 00086 static inline void hash_free_elements(HASH *hash) 00087 { 00088 if (hash->free) 00089 { 00090 HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*); 00091 HASH_LINK *end= data + hash->records; 00092 while (data < end) 00093 (*hash->free)((data++)->data); 00094 } 00095 hash->records=0; 00096 } 00097 00098 00099 /* 00100 Free memory used by hash. 00101 00102 SYNOPSIS 00103 hash_free() 00104 hash the hash to delete elements of 00105 00106 NOTES: Hash can't be reused without calling hash_init again. 00107 */ 00108 00109 void hash_free(HASH *hash) 00110 { 00111 DBUG_ENTER("hash_free"); 00112 DBUG_PRINT("enter",("hash: 0x%lx", hash)); 00113 00114 hash_free_elements(hash); 00115 hash->free= 0; 00116 delete_dynamic(&hash->array); 00117 DBUG_VOID_RETURN; 00118 } 00119 00120 00121 /* 00122 Delete all elements from the hash (the hash itself is to be reused). 00123 00124 SYNOPSIS 00125 my_hash_reset() 00126 hash the hash to delete elements of 00127 */ 00128 00129 void my_hash_reset(HASH *hash) 00130 { 00131 DBUG_ENTER("my_hash_reset"); 00132 DBUG_PRINT("enter",("hash: 0x%lxd",hash)); 00133 00134 hash_free_elements(hash); 00135 reset_dynamic(&hash->array); 00136 /* Set row pointers so that the hash can be reused at once */ 00137 hash->blength= 1; 00138 DBUG_VOID_RETURN; 00139 } 00140 00141 /* some helper functions */ 00142 00143 /* 00144 This function is char* instead of byte* as HPUX11 compiler can't 00145 handle inline functions that are not defined as native types 00146 */ 00147 00148 static inline char* 00149 hash_key(const HASH *hash, const byte *record, uint *length, 00150 my_bool first) 00151 { 00152 if (hash->get_key) 00153 return (*hash->get_key)(record,length,first); 00154 *length=hash->key_length; 00155 return (byte*) record+hash->key_offset; 00156 } 00157 00158 /* Calculate pos according to keys */ 00159 00160 static uint hash_mask(uint hashnr,uint buffmax,uint maxlength) 00161 { 00162 if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1)); 00163 return (hashnr & ((buffmax >> 1) -1)); 00164 } 00165 00166 static uint hash_rec_mask(const HASH *hash, HASH_LINK *pos, 00167 uint buffmax, uint maxlength) 00168 { 00169 uint length; 00170 byte *key= (byte*) hash_key(hash,pos->data,&length,0); 00171 return hash_mask(calc_hash(hash,key,length),buffmax,maxlength); 00172 } 00173 00174 00175 00176 /* for compilers which can not handle inline */ 00177 static 00178 #if !defined(__USLC__) && !defined(__sgi) 00179 inline 00180 #endif 00181 unsigned int rec_hashnr(HASH *hash,const byte *record) 00182 { 00183 uint length; 00184 byte *key= (byte*) hash_key(hash,record,&length,0); 00185 return calc_hash(hash,key,length); 00186 } 00187 00188 00189 gptr hash_search(const HASH *hash, const byte *key, uint length) 00190 { 00191 HASH_SEARCH_STATE state; 00192 return hash_first(hash, key, length, &state); 00193 } 00194 00195 /* 00196 Search after a record based on a key 00197 00198 NOTE 00199 Assigns the number of the found record to HASH_SEARCH_STATE state 00200 */ 00201 00202 gptr hash_first(const HASH *hash, const byte *key, uint length, 00203 HASH_SEARCH_STATE *current_record) 00204 { 00205 HASH_LINK *pos; 00206 uint flag,idx; 00207 DBUG_ENTER("hash_first"); 00208 00209 flag=1; 00210 if (hash->records) 00211 { 00212 idx=hash_mask(calc_hash(hash,key,length ? length : hash->key_length), 00213 hash->blength,hash->records); 00214 do 00215 { 00216 pos= dynamic_element(&hash->array,idx,HASH_LINK*); 00217 if (!hashcmp(hash,pos,key,length)) 00218 { 00219 DBUG_PRINT("exit",("found key at %d",idx)); 00220 *current_record= idx; 00221 DBUG_RETURN (pos->data); 00222 } 00223 if (flag) 00224 { 00225 flag=0; /* Reset flag */ 00226 if (hash_rec_mask(hash,pos,hash->blength,hash->records) != idx) 00227 break; /* Wrong link */ 00228 } 00229 } 00230 while ((idx=pos->next) != NO_RECORD); 00231 } 00232 *current_record= NO_RECORD; 00233 DBUG_RETURN(0); 00234 } 00235 00236 /* Get next record with identical key */ 00237 /* Can only be called if previous calls was hash_search */ 00238 00239 gptr hash_next(const HASH *hash, const byte *key, uint length, 00240 HASH_SEARCH_STATE *current_record) 00241 { 00242 HASH_LINK *pos; 00243 uint idx; 00244 00245 if (*current_record != NO_RECORD) 00246 { 00247 HASH_LINK *data=dynamic_element(&hash->array,0,HASH_LINK*); 00248 for (idx=data[*current_record].next; idx != NO_RECORD ; idx=pos->next) 00249 { 00250 pos=data+idx; 00251 if (!hashcmp(hash,pos,key,length)) 00252 { 00253 *current_record= idx; 00254 return pos->data; 00255 } 00256 } 00257 *current_record= NO_RECORD; 00258 } 00259 return 0; 00260 } 00261 00262 00263 /* Change link from pos to new_link */ 00264 00265 static void movelink(HASH_LINK *array,uint find,uint next_link,uint newlink) 00266 { 00267 HASH_LINK *old_link; 00268 do 00269 { 00270 old_link=array+next_link; 00271 } 00272 while ((next_link=old_link->next) != find); 00273 old_link->next= newlink; 00274 return; 00275 } 00276 00277 /* 00278 Compare a key in a record to a whole key. Return 0 if identical 00279 00280 SYNOPSIS 00281 hashcmp() 00282 hash hash table 00283 pos position of hash record to use in comparison 00284 key key for comparison 00285 length length of key 00286 00287 NOTES: 00288 If length is 0, comparison is done using the length of the 00289 record being compared against. 00290 00291 RETURN 00292 = 0 key of record == key 00293 != 0 key of record != key 00294 */ 00295 00296 static int hashcmp(const HASH *hash, HASH_LINK *pos, const byte *key, 00297 uint length) 00298 { 00299 uint rec_keylength; 00300 byte *rec_key= (byte*) hash_key(hash,pos->data,&rec_keylength,1); 00301 return ((length && length != rec_keylength) || 00302 my_strnncoll(hash->charset, (uchar*) rec_key, rec_keylength, 00303 (uchar*) key, rec_keylength)); 00304 } 00305 00306 00307 /* Write a hash-key to the hash-index */ 00308 00309 my_bool my_hash_insert(HASH *info,const byte *record) 00310 { 00311 int flag; 00312 uint halfbuff,hash_nr,first_index,idx; 00313 byte *ptr_to_rec,*ptr_to_rec2; 00314 HASH_LINK *data,*empty,*gpos,*gpos2,*pos; 00315 00316 LINT_INIT(gpos); LINT_INIT(gpos2); 00317 LINT_INIT(ptr_to_rec); LINT_INIT(ptr_to_rec2); 00318 00319 flag=0; 00320 if (!(empty=(HASH_LINK*) alloc_dynamic(&info->array))) 00321 return(TRUE); /* No more memory */ 00322 00323 data=dynamic_element(&info->array,0,HASH_LINK*); 00324 halfbuff= info->blength >> 1; 00325 00326 idx=first_index=info->records-halfbuff; 00327 if (idx != info->records) /* If some records */ 00328 { 00329 do 00330 { 00331 pos=data+idx; 00332 hash_nr=rec_hashnr(info,pos->data); 00333 if (flag == 0) /* First loop; Check if ok */ 00334 if (hash_mask(hash_nr,info->blength,info->records) != first_index) 00335 break; 00336 if (!(hash_nr & halfbuff)) 00337 { /* Key will not move */ 00338 if (!(flag & LOWFIND)) 00339 { 00340 if (flag & HIGHFIND) 00341 { 00342 flag=LOWFIND | HIGHFIND; 00343 /* key shall be moved to the current empty position */ 00344 gpos=empty; 00345 ptr_to_rec=pos->data; 00346 empty=pos; /* This place is now free */ 00347 } 00348 else 00349 { 00350 flag=LOWFIND | LOWUSED; /* key isn't changed */ 00351 gpos=pos; 00352 ptr_to_rec=pos->data; 00353 } 00354 } 00355 else 00356 { 00357 if (!(flag & LOWUSED)) 00358 { 00359 /* Change link of previous LOW-key */ 00360 gpos->data=ptr_to_rec; 00361 gpos->next=(uint) (pos-data); 00362 flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED); 00363 } 00364 gpos=pos; 00365 ptr_to_rec=pos->data; 00366 } 00367 } 00368 else 00369 { /* key will be moved */ 00370 if (!(flag & HIGHFIND)) 00371 { 00372 flag= (flag & LOWFIND) | HIGHFIND; 00373 /* key shall be moved to the last (empty) position */ 00374 gpos2 = empty; empty=pos; 00375 ptr_to_rec2=pos->data; 00376 } 00377 else 00378 { 00379 if (!(flag & HIGHUSED)) 00380 { 00381 /* Change link of previous hash-key and save */ 00382 gpos2->data=ptr_to_rec2; 00383 gpos2->next=(uint) (pos-data); 00384 flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED); 00385 } 00386 gpos2=pos; 00387 ptr_to_rec2=pos->data; 00388 } 00389 } 00390 } 00391 while ((idx=pos->next) != NO_RECORD); 00392 00393 if ((flag & (LOWFIND | LOWUSED)) == LOWFIND) 00394 { 00395 gpos->data=ptr_to_rec; 00396 gpos->next=NO_RECORD; 00397 } 00398 if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND) 00399 { 00400 gpos2->data=ptr_to_rec2; 00401 gpos2->next=NO_RECORD; 00402 } 00403 } 00404 /* Check if we are at the empty position */ 00405 00406 idx=hash_mask(rec_hashnr(info,record),info->blength,info->records+1); 00407 pos=data+idx; 00408 if (pos == empty) 00409 { 00410 pos->data=(byte*) record; 00411 pos->next=NO_RECORD; 00412 } 00413 else 00414 { 00415 /* Check if more records in same hash-nr family */ 00416 empty[0]=pos[0]; 00417 gpos=data+hash_rec_mask(info,pos,info->blength,info->records+1); 00418 if (pos == gpos) 00419 { 00420 pos->data=(byte*) record; 00421 pos->next=(uint) (empty - data); 00422 } 00423 else 00424 { 00425 pos->data=(byte*) record; 00426 pos->next=NO_RECORD; 00427 movelink(data,(uint) (pos-data),(uint) (gpos-data),(uint) (empty-data)); 00428 } 00429 } 00430 if (++info->records == info->blength) 00431 info->blength+= info->blength; 00432 return(0); 00433 } 00434 00435 00436 /****************************************************************************** 00437 ** Remove one record from hash-table. The record with the same record 00438 ** ptr is removed. 00439 ** if there is a free-function it's called for record if found 00440 ******************************************************************************/ 00441 00442 my_bool hash_delete(HASH *hash,byte *record) 00443 { 00444 uint blength,pos2,pos_hashnr,lastpos_hashnr,idx,empty_index; 00445 HASH_LINK *data,*lastpos,*gpos,*pos,*pos3,*empty; 00446 DBUG_ENTER("hash_delete"); 00447 if (!hash->records) 00448 DBUG_RETURN(1); 00449 00450 blength=hash->blength; 00451 data=dynamic_element(&hash->array,0,HASH_LINK*); 00452 /* Search after record with key */ 00453 pos=data+ hash_mask(rec_hashnr(hash,record),blength,hash->records); 00454 gpos = 0; 00455 00456 while (pos->data != record) 00457 { 00458 gpos=pos; 00459 if (pos->next == NO_RECORD) 00460 DBUG_RETURN(1); /* Key not found */ 00461 pos=data+pos->next; 00462 } 00463 00464 if ( --(hash->records) < hash->blength >> 1) hash->blength>>=1; 00465 lastpos=data+hash->records; 00466 00467 /* Remove link to record */ 00468 empty=pos; empty_index=(uint) (empty-data); 00469 if (gpos) 00470 gpos->next=pos->next; /* unlink current ptr */ 00471 else if (pos->next != NO_RECORD) 00472 { 00473 empty=data+(empty_index=pos->next); 00474 pos->data=empty->data; 00475 pos->next=empty->next; 00476 } 00477 00478 if (empty == lastpos) /* last key at wrong pos or no next link */ 00479 goto exit; 00480 00481 /* Move the last key (lastpos) */ 00482 lastpos_hashnr=rec_hashnr(hash,lastpos->data); 00483 /* pos is where lastpos should be */ 00484 pos=data+hash_mask(lastpos_hashnr,hash->blength,hash->records); 00485 if (pos == empty) /* Move to empty position. */ 00486 { 00487 empty[0]=lastpos[0]; 00488 goto exit; 00489 } 00490 pos_hashnr=rec_hashnr(hash,pos->data); 00491 /* pos3 is where the pos should be */ 00492 pos3= data+hash_mask(pos_hashnr,hash->blength,hash->records); 00493 if (pos != pos3) 00494 { /* pos is on wrong posit */ 00495 empty[0]=pos[0]; /* Save it here */ 00496 pos[0]=lastpos[0]; /* This should be here */ 00497 movelink(data,(uint) (pos-data),(uint) (pos3-data),empty_index); 00498 goto exit; 00499 } 00500 pos2= hash_mask(lastpos_hashnr,blength,hash->records+1); 00501 if (pos2 == hash_mask(pos_hashnr,blength,hash->records+1)) 00502 { /* Identical key-positions */ 00503 if (pos2 != hash->records) 00504 { 00505 empty[0]=lastpos[0]; 00506 movelink(data,(uint) (lastpos-data),(uint) (pos-data),empty_index); 00507 goto exit; 00508 } 00509 idx= (uint) (pos-data); /* Link pos->next after lastpos */ 00510 } 00511 else idx= NO_RECORD; /* Different positions merge */ 00512 00513 empty[0]=lastpos[0]; 00514 movelink(data,idx,empty_index,pos->next); 00515 pos->next=empty_index; 00516 00517 exit: 00518 VOID(pop_dynamic(&hash->array)); 00519 if (hash->free) 00520 (*hash->free)((byte*) record); 00521 DBUG_RETURN(0); 00522 } 00523 00524 /* 00525 Update keys when record has changed. 00526 This is much more efficent than using a delete & insert. 00527 */ 00528 00529 my_bool hash_update(HASH *hash,byte *record,byte *old_key,uint old_key_length) 00530 { 00531 uint idx,new_index,new_pos_index,blength,records,empty; 00532 HASH_LINK org_link,*data,*previous,*pos; 00533 DBUG_ENTER("hash_update"); 00534 00535 data=dynamic_element(&hash->array,0,HASH_LINK*); 00536 blength=hash->blength; records=hash->records; 00537 00538 /* Search after record with key */ 00539 00540 idx=hash_mask(calc_hash(hash, old_key,(old_key_length ? 00541 old_key_length : 00542 hash->key_length)), 00543 blength,records); 00544 new_index=hash_mask(rec_hashnr(hash,record),blength,records); 00545 if (idx == new_index) 00546 DBUG_RETURN(0); /* Nothing to do (No record check) */ 00547 previous=0; 00548 for (;;) 00549 { 00550 00551 if ((pos= data+idx)->data == record) 00552 break; 00553 previous=pos; 00554 if ((idx=pos->next) == NO_RECORD) 00555 DBUG_RETURN(1); /* Not found in links */ 00556 } 00557 org_link= *pos; 00558 empty=idx; 00559 00560 /* Relink record from current chain */ 00561 00562 if (!previous) 00563 { 00564 if (pos->next != NO_RECORD) 00565 { 00566 empty=pos->next; 00567 *pos= data[pos->next]; 00568 } 00569 } 00570 else 00571 previous->next=pos->next; /* unlink pos */ 00572 00573 /* Move data to correct position */ 00574 pos=data+new_index; 00575 new_pos_index=hash_rec_mask(hash,pos,blength,records); 00576 if (new_index != new_pos_index) 00577 { /* Other record in wrong position */ 00578 data[empty] = *pos; 00579 movelink(data,new_index,new_pos_index,empty); 00580 org_link.next=NO_RECORD; 00581 data[new_index]= org_link; 00582 } 00583 else 00584 { /* Link in chain at right position */ 00585 org_link.next=data[new_index].next; 00586 data[empty]=org_link; 00587 data[new_index].next=empty; 00588 } 00589 DBUG_RETURN(0); 00590 } 00591 00592 00593 byte *hash_element(HASH *hash,uint idx) 00594 { 00595 if (idx < hash->records) 00596 return dynamic_element(&hash->array,idx,HASH_LINK*)->data; 00597 return 0; 00598 } 00599 00600 00601 /* 00602 Replace old row with new row. This should only be used when key 00603 isn't changed 00604 */ 00605 00606 void hash_replace(HASH *hash, HASH_SEARCH_STATE *current_record, byte *new_row) 00607 { 00608 if (*current_record != NO_RECORD) /* Safety */ 00609 dynamic_element(&hash->array, *current_record, HASH_LINK*)->data= new_row; 00610 } 00611 00612 00613 #ifndef DBUG_OFF 00614 00615 my_bool hash_check(HASH *hash) 00616 { 00617 int error; 00618 uint i,rec_link,found,max_links,seek,links,idx; 00619 uint records,blength; 00620 HASH_LINK *data,*hash_info; 00621 00622 records=hash->records; blength=hash->blength; 00623 data=dynamic_element(&hash->array,0,HASH_LINK*); 00624 error=0; 00625 00626 for (i=found=max_links=seek=0 ; i < records ; i++) 00627 { 00628 if (hash_rec_mask(hash,data+i,blength,records) == i) 00629 { 00630 found++; seek++; links=1; 00631 for (idx=data[i].next ; 00632 idx != NO_RECORD && found < records + 1; 00633 idx=hash_info->next) 00634 { 00635 if (idx >= records) 00636 { 00637 DBUG_PRINT("error", 00638 ("Found pointer outside array to %d from link starting at %d", 00639 idx,i)); 00640 error=1; 00641 } 00642 hash_info=data+idx; 00643 seek+= ++links; 00644 if ((rec_link=hash_rec_mask(hash,hash_info,blength,records)) != i) 00645 { 00646 DBUG_PRINT("error", 00647 ("Record in wrong link at %d: Start %d Record: 0x%lx Record-link %d", idx,i,hash_info->data,rec_link)); 00648 error=1; 00649 } 00650 else 00651 found++; 00652 } 00653 if (links > max_links) max_links=links; 00654 } 00655 } 00656 if (found != records) 00657 { 00658 DBUG_PRINT("error",("Found %ld of %ld records")); 00659 error=1; 00660 } 00661 if (records) 00662 DBUG_PRINT("info", 00663 ("records: %ld seeks: %d max links: %d hitrate: %.2f", 00664 records,seek,max_links,(float) seek / (float) records)); 00665 return error; 00666 } 00667 #endif
Generated on Sat Sep 9 00:49:57 2006 for MySQL 5.1 by
1.4.7
© 1995-2008 MySQL AB, 2008- Sun Microsystems, Inc.