1/* 2 * Hash Table Data Type 3 * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net> 4 * 5 * Free Software License: 6 * 7 * All rights are reserved by the author, with the following exceptions: 8 * Permission is granted to freely reproduce and distribute this software, 9 * possibly in exchange for a fee, provided that this copyright notice appears 10 * intact. Permission is also granted to adapt this software to produce 11 * derivative works, as long as the modified versions carry this copyright 12 * notice and additional notices stating that the work has been modified. 13 * This source code may be translated into executable form and incorporated 14 * into proprietary software; there is no requirement for such software to 15 * contain a copyright notice related to this source. 16 * 17 * $Id: hash.c,v 1.4 2009-11-19 10:37:43 franklahm Exp $ 18 * $Name: $ 19 */ 20#define NDEBUG 21#include <stdlib.h> 22#include <stddef.h> 23#include <assert.h> 24#include <string.h> 25#define HASH_IMPLEMENTATION 26#include "hash.h" 27 28#ifdef KAZLIB_RCSID 29static const char rcsid[] = "$Id: hash.c,v 1.4 2009-11-19 10:37:43 franklahm Exp $"; 30#endif 31 32#define INIT_BITS 6 33#define INIT_SIZE (1UL << (INIT_BITS)) /* must be power of two */ 34#define INIT_MASK ((INIT_SIZE) - 1) 35 36#define next hash_next 37#define key hash_key 38#define data hash_data 39#define hkey hash_hkey 40 41#define table hash_table 42#define nchains hash_nchains 43#define nodecount hash_nodecount 44#define maxcount hash_maxcount 45#define highmark hash_highmark 46#define lowmark hash_lowmark 47#define compare hash_compare 48#define function hash_function 49#define allocnode hash_allocnode 50#define freenode hash_freenode 51#define context hash_context 52#define mask hash_mask 53#define dynamic hash_dynamic 54 55#define table hash_table 56#define chain hash_chain 57 58static hnode_t *hnode_alloc(void *context); 59static void hnode_free(hnode_t *node, void *context); 60static hash_val_t hash_fun_default(const void *key); 61static hash_val_t hash_fun2(const void *key); 62static int hash_comp_default(const void *key1, const void *key2); 63 64int hash_val_t_bit; 65 66/* 67 * Compute the number of bits in the hash_val_t type. We know that hash_val_t 68 * is an unsigned integral type. Thus the highest value it can hold is a 69 * Mersenne number (power of two, less one). We initialize a hash_val_t 70 * object with this value and then shift bits out one by one while counting. 71 * Notes: 72 * 1. HASH_VAL_T_MAX is a Mersenne number---one that is one less than a power 73 * of two. This means that its binary representation consists of all one 74 * bits, and hence ``val'' is initialized to all one bits. 75 * 2. While bits remain in val, we increment the bit count and shift it to the 76 * right, replacing the topmost bit by zero. 77 */ 78 79static void compute_bits(void) 80{ 81 hash_val_t val = HASH_VAL_T_MAX; /* 1 */ 82 int bits = 0; 83 84 while (val) { /* 2 */ 85 bits++; 86 val >>= 1; 87 } 88 89 hash_val_t_bit = bits; 90} 91 92/* 93 * Verify whether the given argument is a power of two. 94 */ 95 96static int is_power_of_two(hash_val_t arg) 97{ 98 if (arg == 0) 99 return 0; 100 while ((arg & 1) == 0) 101 arg >>= 1; 102 return (arg == 1); 103} 104 105/* 106 * Compute a shift amount from a given table size 107 */ 108 109static hash_val_t compute_mask(hashcount_t size) 110{ 111 assert (is_power_of_two(size)); 112 assert (size >= 2); 113 114 return size - 1; 115} 116 117/* 118 * Initialize the table of pointers to null. 119 */ 120 121static void clear_table(hash_t *hash) 122{ 123 hash_val_t i; 124 125 for (i = 0; i < hash->nchains; i++) 126 hash->table[i] = NULL; 127} 128 129/* 130 * Double the size of a dynamic table. This works as follows. Each chain splits 131 * into two adjacent chains. The shift amount increases by one, exposing an 132 * additional bit of each hashed key. For each node in the original chain, the 133 * value of this newly exposed bit will decide which of the two new chains will 134 * receive the node: if the bit is 1, the chain with the higher index will have 135 * the node, otherwise the lower chain will receive the node. In this manner, 136 * the hash table will continue to function exactly as before without having to 137 * rehash any of the keys. 138 * Notes: 139 * 1. Overflow check. 140 * 2. The new number of chains is twice the old number of chains. 141 * 3. The new mask is one bit wider than the previous, revealing a 142 * new bit in all hashed keys. 143 * 4. Allocate a new table of chain pointers that is twice as large as the 144 * previous one. 145 * 5. If the reallocation was successful, we perform the rest of the growth 146 * algorithm, otherwise we do nothing. 147 * 6. The exposed_bit variable holds a mask with which each hashed key can be 148 * AND-ed to test the value of its newly exposed bit. 149 * 7. Now loop over each chain in the table and sort its nodes into two 150 * chains based on the value of each node's newly exposed hash bit. 151 * 8. The low chain replaces the current chain. The high chain goes 152 * into the corresponding sister chain in the upper half of the table. 153 * 9. We have finished dealing with the chains and nodes. We now update 154 * the various bookeeping fields of the hash structure. 155 */ 156 157static void grow_table(hash_t *hash) 158{ 159 hnode_t **newtable; 160 161 assert (2 * hash->nchains > hash->nchains); /* 1 */ 162 163 newtable = realloc(hash->table, 164 sizeof *newtable * hash->nchains * 2); /* 4 */ 165 166 if (newtable) { /* 5 */ 167 hash_val_t mask = (hash->mask << 1) | 1; /* 3 */ 168 hash_val_t exposed_bit = mask ^ hash->mask; /* 6 */ 169 hash_val_t chain; 170 171 assert (mask != hash->mask); 172 173 for (chain = 0; chain < hash->nchains; chain++) { /* 7 */ 174 hnode_t *low_chain = NULL, *high_chain = NULL, *hptr, *next; 175 176 for (hptr = newtable[chain]; hptr != NULL; hptr = next) { 177 next = hptr->next; 178 179 if (hptr->hkey & exposed_bit) { 180 hptr->next = high_chain; 181 high_chain = hptr; 182 } else { 183 hptr->next = low_chain; 184 low_chain = hptr; 185 } 186 } 187 188 newtable[chain] = low_chain; /* 8 */ 189 newtable[chain + hash->nchains] = high_chain; 190 } 191 192 hash->table = newtable; /* 9 */ 193 hash->mask = mask; 194 hash->nchains *= 2; 195 hash->lowmark *= 2; 196 hash->highmark *= 2; 197 } 198 assert (hash_verify(hash)); 199} 200 201/* 202 * Cut a table size in half. This is done by folding together adjacent chains 203 * and populating the lower half of the table with these chains. The chains are 204 * simply spliced together. Once this is done, the whole table is reallocated 205 * to a smaller object. 206 * Notes: 207 * 1. It is illegal to have a hash table with one slot. This would mean that 208 * hash->shift is equal to hash_val_t_bit, an illegal shift value. 209 * Also, other things could go wrong, such as hash->lowmark becoming zero. 210 * 2. Looping over each pair of sister chains, the low_chain is set to 211 * point to the head node of the chain in the lower half of the table, 212 * and high_chain points to the head node of the sister in the upper half. 213 * 3. The intent here is to compute a pointer to the last node of the 214 * lower chain into the low_tail variable. If this chain is empty, 215 * low_tail ends up with a null value. 216 * 4. If the lower chain is not empty, we simply tack the upper chain onto it. 217 * If the upper chain is a null pointer, nothing happens. 218 * 5. Otherwise if the lower chain is empty but the upper one is not, 219 * If the low chain is empty, but the high chain is not, then the 220 * high chain is simply transferred to the lower half of the table. 221 * 6. Otherwise if both chains are empty, there is nothing to do. 222 * 7. All the chain pointers are in the lower half of the table now, so 223 * we reallocate it to a smaller object. This, of course, invalidates 224 * all pointer-to-pointers which reference into the table from the 225 * first node of each chain. 226 * 8. Though it's unlikely, the reallocation may fail. In this case we 227 * pretend that the table _was_ reallocated to a smaller object. 228 * 9. Finally, update the various table parameters to reflect the new size. 229 */ 230 231static void shrink_table(hash_t *hash) 232{ 233 hash_val_t chain, nchains; 234 hnode_t **newtable, *low_tail, *low_chain, *high_chain; 235 236 assert (hash->nchains >= 2); /* 1 */ 237 nchains = hash->nchains / 2; 238 239 for (chain = 0; chain < nchains; chain++) { 240 low_chain = hash->table[chain]; /* 2 */ 241 high_chain = hash->table[chain + nchains]; 242 for (low_tail = low_chain; low_tail && low_tail->next; low_tail = low_tail->next) 243 ; /* 3 */ 244 if (low_chain != NULL) /* 4 */ 245 low_tail->next = high_chain; 246 else if (high_chain != NULL) /* 5 */ 247 hash->table[chain] = high_chain; 248 else 249 assert (hash->table[chain] == NULL); /* 6 */ 250 } 251 newtable = realloc(hash->table, 252 sizeof *newtable * nchains); /* 7 */ 253 if (newtable) /* 8 */ 254 hash->table = newtable; 255 hash->mask >>= 1; /* 9 */ 256 hash->nchains = nchains; 257 hash->lowmark /= 2; 258 hash->highmark /= 2; 259 assert (hash_verify(hash)); 260} 261 262 263/* 264 * Create a dynamic hash table. Both the hash table structure and the table 265 * itself are dynamically allocated. Furthermore, the table is extendible in 266 * that it will automatically grow as its load factor increases beyond a 267 * certain threshold. 268 * Notes: 269 * 1. If the number of bits in the hash_val_t type has not been computed yet, 270 * we do so here, because this is likely to be the first function that the 271 * user calls. 272 * 2. Allocate a hash table control structure. 273 * 3. If a hash table control structure is successfully allocated, we 274 * proceed to initialize it. Otherwise we return a null pointer. 275 * 4. We try to allocate the table of hash chains. 276 * 5. If we were able to allocate the hash chain table, we can finish 277 * initializing the hash structure and the table. Otherwise, we must 278 * backtrack by freeing the hash structure. 279 * 6. INIT_SIZE should be a power of two. The high and low marks are always set 280 * to be twice the table size and half the table size respectively. When the 281 * number of nodes in the table grows beyond the high size (beyond load 282 * factor 2), it will double in size to cut the load factor down to about 283 * about 1. If the table shrinks down to or beneath load factor 0.5, 284 * it will shrink, bringing the load up to about 1. However, the table 285 * will never shrink beneath INIT_SIZE even if it's emptied. 286 * 7. This indicates that the table is dynamically allocated and dynamically 287 * resized on the fly. A table that has this value set to zero is 288 * assumed to be statically allocated and will not be resized. 289 * 8. The table of chains must be properly reset to all null pointers. 290 */ 291 292hash_t *hash_create(hashcount_t maxcount, hash_comp_t compfun, 293 hash_fun_t hashfun) 294{ 295 hash_t *hash; 296 297 if (hash_val_t_bit == 0) /* 1 */ 298 compute_bits(); 299 300 hash = malloc(sizeof *hash); /* 2 */ 301 302 if (hash) { /* 3 */ 303 hash->table = malloc(sizeof *hash->table * INIT_SIZE); /* 4 */ 304 if (hash->table) { /* 5 */ 305 hash->nchains = INIT_SIZE; /* 6 */ 306 hash->highmark = INIT_SIZE * 2; 307 hash->lowmark = INIT_SIZE / 2; 308 hash->nodecount = 0; 309 hash->maxcount = maxcount; 310 hash->compare = compfun ? compfun : hash_comp_default; 311 hash->function = hashfun ? hashfun : hash_fun_default; 312 hash->allocnode = hnode_alloc; 313 hash->freenode = hnode_free; 314 hash->context = NULL; 315 hash->mask = INIT_MASK; 316 hash->dynamic = 1; /* 7 */ 317 clear_table(hash); /* 8 */ 318 assert (hash_verify(hash)); 319 return hash; 320 } 321 free(hash); 322 } 323 324 return NULL; 325} 326 327/* 328 * Select a different set of node allocator routines. 329 */ 330 331void hash_set_allocator(hash_t *hash, hnode_alloc_t al, 332 hnode_free_t fr, void *context) 333{ 334 assert (hash_count(hash) == 0); 335 assert ((al == 0 && fr == 0) || (al != 0 && fr != 0)); 336 337 hash->allocnode = al ? al : hnode_alloc; 338 hash->freenode = fr ? fr : hnode_free; 339 hash->context = context; 340} 341 342/* 343 * Free every node in the hash using the hash->freenode() function pointer, and 344 * cause the hash to become empty. 345 */ 346 347void hash_free_nodes(hash_t *hash) 348{ 349 hscan_t hs; 350 hnode_t *node; 351 hash_scan_begin(&hs, hash); 352 while ((node = hash_scan_next(&hs))) { 353 hash_scan_delete(hash, node); 354 hash->freenode(node, hash->context); 355 } 356 hash->nodecount = 0; 357 clear_table(hash); 358} 359 360/* 361 * Obsolescent function for removing all nodes from a table, 362 * freeing them and then freeing the table all in one step. 363 */ 364 365void hash_free(hash_t *hash) 366{ 367#ifdef KAZLIB_OBSOLESCENT_DEBUG 368 assert ("call to obsolescent function hash_free()" && 0); 369#endif 370 hash_free_nodes(hash); 371 hash_destroy(hash); 372} 373 374/* 375 * Free a dynamic hash table structure. 376 */ 377 378void hash_destroy(hash_t *hash) 379{ 380 assert (hash_val_t_bit != 0); 381 assert (hash_isempty(hash)); 382 free(hash->table); 383 free(hash); 384} 385 386/* 387 * Initialize a user supplied hash structure. The user also supplies a table of 388 * chains which is assigned to the hash structure. The table is static---it 389 * will not grow or shrink. 390 * 1. See note 1. in hash_create(). 391 * 2. The user supplied array of pointers hopefully contains nchains nodes. 392 * 3. See note 7. in hash_create(). 393 * 4. We must dynamically compute the mask from the given power of two table 394 * size. 395 * 5. The user supplied table can't be assumed to contain null pointers, 396 * so we reset it here. 397 */ 398 399hash_t *hash_init(hash_t *hash, hashcount_t maxcount, 400 hash_comp_t compfun, hash_fun_t hashfun, hnode_t **table, 401 hashcount_t nchains) 402{ 403 if (hash_val_t_bit == 0) /* 1 */ 404 compute_bits(); 405 406 assert (is_power_of_two(nchains)); 407 408 hash->table = table; /* 2 */ 409 hash->nchains = nchains; 410 hash->nodecount = 0; 411 hash->maxcount = maxcount; 412 hash->compare = compfun ? compfun : hash_comp_default; 413 hash->function = hashfun ? hashfun : hash_fun_default; 414 hash->dynamic = 0; /* 3 */ 415 hash->mask = compute_mask(nchains); /* 4 */ 416 clear_table(hash); /* 5 */ 417 418 assert (hash_verify(hash)); 419 420 return hash; 421} 422 423/* 424 * Reset the hash scanner so that the next element retrieved by 425 * hash_scan_next() shall be the first element on the first non-empty chain. 426 * Notes: 427 * 1. Locate the first non empty chain. 428 * 2. If an empty chain is found, remember which one it is and set the next 429 * pointer to refer to its first element. 430 * 3. Otherwise if a chain is not found, set the next pointer to NULL 431 * so that hash_scan_next() shall indicate failure. 432 */ 433 434void hash_scan_begin(hscan_t *scan, hash_t *hash) 435{ 436 hash_val_t nchains = hash->nchains; 437 hash_val_t chain; 438 439 scan->table = hash; 440 441 /* 1 */ 442 443 for (chain = 0; chain < nchains && hash->table[chain] == NULL; chain++) 444 ; 445 446 if (chain < nchains) { /* 2 */ 447 scan->chain = chain; 448 scan->next = hash->table[chain]; 449 } else { /* 3 */ 450 scan->next = NULL; 451 } 452} 453 454/* 455 * Retrieve the next node from the hash table, and update the pointer 456 * for the next invocation of hash_scan_next(). 457 * Notes: 458 * 1. Remember the next pointer in a temporary value so that it can be 459 * returned. 460 * 2. This assertion essentially checks whether the module has been properly 461 * initialized. The first point of interaction with the module should be 462 * either hash_create() or hash_init(), both of which set hash_val_t_bit to 463 * a non zero value. 464 * 3. If the next pointer we are returning is not NULL, then the user is 465 * allowed to call hash_scan_next() again. We prepare the new next pointer 466 * for that call right now. That way the user is allowed to delete the node 467 * we are about to return, since we will no longer be needing it to locate 468 * the next node. 469 * 4. If there is a next node in the chain (next->next), then that becomes the 470 * new next node, otherwise ... 471 * 5. We have exhausted the current chain, and must locate the next subsequent 472 * non-empty chain in the table. 473 * 6. If a non-empty chain is found, the first element of that chain becomes 474 * the new next node. Otherwise there is no new next node and we set the 475 * pointer to NULL so that the next time hash_scan_next() is called, a null 476 * pointer shall be immediately returned. 477 */ 478 479 480hnode_t *hash_scan_next(hscan_t *scan) 481{ 482 hnode_t *next = scan->next; /* 1 */ 483 hash_t *hash = scan->table; 484 hash_val_t chain = scan->chain + 1; 485 hash_val_t nchains = hash->nchains; 486 487 assert (hash_val_t_bit != 0); /* 2 */ 488 489 if (next) { /* 3 */ 490 if (next->next) { /* 4 */ 491 scan->next = next->next; 492 } else { 493 while (chain < nchains && hash->table[chain] == NULL) /* 5 */ 494 chain++; 495 if (chain < nchains) { /* 6 */ 496 scan->chain = chain; 497 scan->next = hash->table[chain]; 498 } else { 499 scan->next = NULL; 500 } 501 } 502 } 503 return next; 504} 505 506/* 507 * Insert a node into the hash table. 508 * Notes: 509 * 1. It's illegal to insert more than the maximum number of nodes. The client 510 * should verify that the hash table is not full before attempting an 511 * insertion. 512 * 2. The same key may not be inserted into a table twice. 513 * 3. If the table is dynamic and the load factor is already at >= 2, 514 * grow the table. 515 * 4. We take the bottom N bits of the hash value to derive the chain index, 516 * where N is the base 2 logarithm of the size of the hash table. 517 */ 518 519void hash_insert(hash_t *hash, hnode_t *node, const void *key) 520{ 521 hash_val_t hkey, chain; 522 523 assert (hash_val_t_bit != 0); 524 assert (node->next == NULL); 525 assert (hash->nodecount < hash->maxcount); /* 1 */ 526 assert (hash_lookup(hash, key) == NULL); /* 2 */ 527 528 if (hash->dynamic && hash->nodecount >= hash->highmark) /* 3 */ 529 grow_table(hash); 530 531 hkey = hash->function(key); 532 chain = hkey & hash->mask; /* 4 */ 533 534 node->key = key; 535 node->hkey = hkey; 536 node->next = hash->table[chain]; 537 hash->table[chain] = node; 538 hash->nodecount++; 539 540 assert (hash_verify(hash)); 541} 542 543/* 544 * Find a node in the hash table and return a pointer to it. 545 * Notes: 546 * 1. We hash the key and keep the entire hash value. As an optimization, when 547 * we descend down the chain, we can compare hash values first and only if 548 * hash values match do we perform a full key comparison. 549 * 2. To locate the chain from among 2^N chains, we look at the lower N bits of 550 * the hash value by anding them with the current mask. 551 * 3. Looping through the chain, we compare the stored hash value inside each 552 * node against our computed hash. If they match, then we do a full 553 * comparison between the unhashed keys. If these match, we have located the 554 * entry. 555 */ 556 557hnode_t *hash_lookup(hash_t *hash, const void *key) 558{ 559 hash_val_t hkey, chain; 560 hnode_t *nptr; 561 562 hkey = hash->function(key); /* 1 */ 563 chain = hkey & hash->mask; /* 2 */ 564 565 for (nptr = hash->table[chain]; nptr; nptr = nptr->next) { /* 3 */ 566 if (nptr->hkey == hkey && hash->compare(nptr->key, key) == 0) 567 return nptr; 568 } 569 570 return NULL; 571} 572 573/* 574 * Delete the given node from the hash table. Since the chains 575 * are singly linked, we must locate the start of the node's chain 576 * and traverse. 577 * Notes: 578 * 1. The node must belong to this hash table, and its key must not have 579 * been tampered with. 580 * 2. If this deletion will take the node count below the low mark, we 581 * shrink the table now. 582 * 3. Determine which chain the node belongs to, and fetch the pointer 583 * to the first node in this chain. 584 * 4. If the node being deleted is the first node in the chain, then 585 * simply update the chain head pointer. 586 * 5. Otherwise advance to the node's predecessor, and splice out 587 * by updating the predecessor's next pointer. 588 * 6. Indicate that the node is no longer in a hash table. 589 */ 590 591hnode_t *hash_delete(hash_t *hash, hnode_t *node) 592{ 593 hash_val_t chain; 594 hnode_t *hptr; 595 596 assert (hash_lookup(hash, node->key) == node); /* 1 */ 597 assert (hash_val_t_bit != 0); 598 599 if (hash->dynamic && hash->nodecount <= hash->lowmark 600 && hash->nodecount > INIT_SIZE) 601 shrink_table(hash); /* 2 */ 602 603 chain = node->hkey & hash->mask; /* 3 */ 604 hptr = hash->table[chain]; 605 606 if (hptr == node) { /* 4 */ 607 hash->table[chain] = node->next; 608 } else { 609 while (hptr->next != node) { /* 5 */ 610 assert (hptr != 0); 611 hptr = hptr->next; 612 } 613 assert (hptr->next == node); 614 hptr->next = node->next; 615 } 616 617 hash->nodecount--; 618 assert (hash_verify(hash)); 619 620 node->next = NULL; /* 6 */ 621 return node; 622} 623 624int hash_alloc_insert(hash_t *hash, const void *key, void *data) 625{ 626 hnode_t *node = hash->allocnode(hash->context); 627 628 if (node) { 629 hnode_init(node, data); 630 hash_insert(hash, node, key); 631 return 1; 632 } 633 return 0; 634} 635 636void hash_delete_free(hash_t *hash, hnode_t *node) 637{ 638 hash_delete(hash, node); 639 hash->freenode(node, hash->context); 640} 641 642/* 643 * Exactly like hash_delete, except does not trigger table shrinkage. This is to be 644 * used from within a hash table scan operation. See notes for hash_delete. 645 */ 646 647hnode_t *hash_scan_delete(hash_t *hash, hnode_t *node) 648{ 649 hash_val_t chain; 650 hnode_t *hptr; 651 652 assert (hash_lookup(hash, node->key) == node); 653 assert (hash_val_t_bit != 0); 654 655 chain = node->hkey & hash->mask; 656 hptr = hash->table[chain]; 657 658 if (hptr == node) { 659 hash->table[chain] = node->next; 660 } else { 661 while (hptr->next != node) 662 hptr = hptr->next; 663 hptr->next = node->next; 664 } 665 666 hash->nodecount--; 667 assert (hash_verify(hash)); 668 node->next = NULL; 669 670 return node; 671} 672 673/* 674 * Like hash_delete_free but based on hash_scan_delete. 675 */ 676 677void hash_scan_delfree(hash_t *hash, hnode_t *node) 678{ 679 hash_scan_delete(hash, node); 680 hash->freenode(node, hash->context); 681} 682 683/* 684 * Verify whether the given object is a valid hash table. This means 685 * Notes: 686 * 1. If the hash table is dynamic, verify whether the high and 687 * low expansion/shrinkage thresholds are powers of two. 688 * 2. Count all nodes in the table, and test each hash value 689 * to see whether it is correct for the node's chain. 690 */ 691 692int hash_verify(hash_t *hash) 693{ 694 hashcount_t count = 0; 695 hash_val_t chain; 696 hnode_t *hptr; 697 698 if (hash->dynamic) { /* 1 */ 699 if (hash->lowmark >= hash->highmark) 700 return 0; 701 if (!is_power_of_two(hash->highmark)) 702 return 0; 703 if (!is_power_of_two(hash->lowmark)) 704 return 0; 705 } 706 707 for (chain = 0; chain < hash->nchains; chain++) { /* 2 */ 708 for (hptr = hash->table[chain]; hptr != NULL; hptr = hptr->next) { 709 if ((hptr->hkey & hash->mask) != chain) 710 return 0; 711 count++; 712 } 713 } 714 715 if (count != hash->nodecount) 716 return 0; 717 718 return 1; 719} 720 721/* 722 * Test whether the hash table is full and return 1 if this is true, 723 * 0 if it is false. 724 */ 725 726#undef hash_isfull 727int hash_isfull(hash_t *hash) 728{ 729 return hash->nodecount == hash->maxcount; 730} 731 732/* 733 * Test whether the hash table is empty and return 1 if this is true, 734 * 0 if it is false. 735 */ 736 737#undef hash_isempty 738int hash_isempty(hash_t *hash) 739{ 740 return hash->nodecount == 0; 741} 742 743static hnode_t *hnode_alloc(void *context _U_) 744{ 745 return malloc(sizeof *hnode_alloc(NULL)); 746} 747 748static void hnode_free(hnode_t *node, void *context _U_) 749{ 750 free(node); 751} 752 753 754/* 755 * Create a hash table node dynamically and assign it the given data. 756 */ 757 758hnode_t *hnode_create(void *data) 759{ 760 hnode_t *node = malloc(sizeof *node); 761 if (node) { 762 node->data = data; 763 node->next = NULL; 764 } 765 return node; 766} 767 768/* 769 * Initialize a client-supplied node 770 */ 771 772hnode_t *hnode_init(hnode_t *hnode, void *data) 773{ 774 hnode->data = data; 775 hnode->next = NULL; 776 return hnode; 777} 778 779/* 780 * Destroy a dynamically allocated node. 781 */ 782 783void hnode_destroy(hnode_t *hnode) 784{ 785 free(hnode); 786} 787 788#undef hnode_put 789void hnode_put(hnode_t *node, void *data) 790{ 791 node->data = data; 792} 793 794#undef hnode_get 795void *hnode_get(hnode_t *node) 796{ 797 return node->data; 798} 799 800#undef hnode_getkey 801const void *hnode_getkey(hnode_t *node) 802{ 803 return node->key; 804} 805 806#undef hash_count 807hashcount_t hash_count(hash_t *hash) 808{ 809 return hash->nodecount; 810} 811 812#undef hash_size 813hashcount_t hash_size(hash_t *hash) 814{ 815 return hash->nchains; 816} 817 818static hash_val_t hash_fun_default(const void *key) 819{ 820 static unsigned long randbox[] = { 821 0x49848f1bU, 0xe6255dbaU, 0x36da5bdcU, 0x47bf94e9U, 822 0x8cbcce22U, 0x559fc06aU, 0xd268f536U, 0xe10af79aU, 823 0xc1af4d69U, 0x1d2917b5U, 0xec4c304dU, 0x9ee5016cU, 824 0x69232f74U, 0xfead7bb3U, 0xe9089ab6U, 0xf012f6aeU, 825 }; 826 827 const unsigned char *str = key; 828 hash_val_t acc = 0; 829 830 while (*str) { 831 acc ^= randbox[(*str + acc) & 0xf]; 832 acc = (acc << 1) | (acc >> 31); 833 acc &= 0xffffffffU; 834 acc ^= randbox[((*str++ >> 4) + acc) & 0xf]; 835 acc = (acc << 2) | (acc >> 30); 836 acc &= 0xffffffffU; 837 } 838 return acc; 839} 840 841/* From http://www.azillionmonkeys.com/qed/hash.html */ 842#undef get16bits 843#if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \ 844 || defined(_MSC_VER) || defined (__BORLANDC__) || defined (__TURBOC__) 845#define get16bits(d) (*((const uint16_t *) (d))) 846#endif 847 848#if !defined (get16bits) 849#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \ 850 +(uint32_t)(((const uint8_t *)(d))[0]) ) 851#endif 852 853static hash_val_t hash_fun2(const void *key) 854{ 855 int len, rem; 856 const unsigned char *data = key; 857 hash_val_t hash = 0, tmp = 0; 858 859 len = strlen((char *)data); 860 861 rem = len & 3; 862 len >>= 2; 863 864 /* Main loop */ 865 for (;len > 0; len--) { 866 hash += get16bits (data); 867 tmp = (get16bits (data+2) << 11) ^ hash; 868 hash = (hash << 16) ^ tmp; 869 data += 2*sizeof (uint16_t); 870 hash += hash >> 11; 871 } 872 873 /* Handle end cases */ 874 switch (rem) { 875 case 3: hash += get16bits (data); 876 hash ^= hash << 16; 877 hash ^= data[sizeof (uint16_t)] << 18; 878 hash += hash >> 11; 879 break; 880 case 2: hash += get16bits (data); 881 hash ^= hash << 11; 882 hash += hash >> 17; 883 break; 884 case 1: hash += *data; 885 hash ^= hash << 10; 886 hash += hash >> 1; 887 } 888 889 /* Force "avalanching" of final 127 bits */ 890 hash ^= hash << 3; 891 hash += hash >> 5; 892 hash ^= hash << 4; 893 hash += hash >> 17; 894 hash ^= hash << 25; 895 hash += hash >> 6; 896 897 return hash; 898} 899 900static int hash_comp_default(const void *key1, const void *key2) 901{ 902 return strcmp(key1, key2); 903} 904 905#ifdef KAZLIB_TEST_MAIN 906 907#include <stdio.h> 908#include <ctype.h> 909#include <stdarg.h> 910 911typedef char input_t[256]; 912 913static int tokenize(char *string, ...) 914{ 915 char **tokptr; 916 va_list arglist; 917 int tokcount = 0; 918 919 va_start(arglist, string); 920 tokptr = va_arg(arglist, char **); 921 while (tokptr) { 922 while (*string && isspace((unsigned char) *string)) 923 string++; 924 if (!*string) 925 break; 926 *tokptr = string; 927 while (*string && !isspace((unsigned char) *string)) 928 string++; 929 tokptr = va_arg(arglist, char **); 930 tokcount++; 931 if (!*string) 932 break; 933 *string++ = 0; 934 } 935 va_end(arglist); 936 937 return tokcount; 938} 939 940static char *dupstring(char *str) 941{ 942 int sz = strlen(str) + 1; 943 char *new = malloc(sz); 944 if (new) 945 memcpy(new, str, sz); 946 return new; 947} 948 949static hnode_t *new_node(void *c) 950{ 951 static hnode_t few[5]; 952 static int count; 953 954 if (count < 5) 955 return few + count++; 956 957 return NULL; 958} 959 960static void del_node(hnode_t *n, void *c) 961{ 962} 963 964int main(void) 965{ 966 input_t in; 967 hash_t *h = hash_create(HASHCOUNT_T_MAX, 0, hash_fun2); 968 hnode_t *hn; 969 hscan_t hs; 970 char *tok1, *tok2, *val; 971 const char *key; 972 int prompt = 0; 973 974 char *help = 975 "a <key> <val> add value to hash table\n" 976 "d <key> delete value from hash table\n" 977 "l <key> lookup value in hash table\n" 978 "n show size of hash table\n" 979 "c show number of entries\n" 980 "t dump whole hash table\n" 981 "+ increase hash table (private func)\n" 982 "- decrease hash table (private func)\n" 983 "b print hash_t_bit value\n" 984 "p turn prompt on\n" 985 "s switch to non-functioning allocator\n" 986 "q quit"; 987 988 if (!h) 989 puts("hash_create failed"); 990 991 for (;;) { 992 if (prompt) 993 putchar('>'); 994 fflush(stdout); 995 996 if (!fgets(in, sizeof(input_t), stdin)) 997 break; 998 999 switch(in[0]) { 1000 case '?': 1001 puts(help); 1002 break; 1003 case 'b': 1004 printf("%d\n", hash_val_t_bit); 1005 break; 1006 case 'a': 1007 if (tokenize(in+1, &tok1, &tok2, (char **) 0) != 2) { 1008 puts("what?"); 1009 break; 1010 } 1011 key = dupstring(tok1); 1012 val = dupstring(tok2); 1013 1014 if (!key || !val) { 1015 puts("out of memory"); 1016 free((void *) key); 1017 free(val); 1018 } 1019 1020 if (!hash_alloc_insert(h, key, val)) { 1021 puts("hash_alloc_insert failed"); 1022 free((void *) key); 1023 free(val); 1024 break; 1025 } 1026 break; 1027 case 'd': 1028 if (tokenize(in+1, &tok1, (char **) 0) != 1) { 1029 puts("what?"); 1030 break; 1031 } 1032 hn = hash_lookup(h, tok1); 1033 if (!hn) { 1034 puts("hash_lookup failed"); 1035 break; 1036 } 1037 val = hnode_get(hn); 1038 key = hnode_getkey(hn); 1039 hash_scan_delfree(h, hn); 1040 free((void *) key); 1041 free(val); 1042 break; 1043 case 'l': 1044 if (tokenize(in+1, &tok1, (char **) 0) != 1) { 1045 puts("what?"); 1046 break; 1047 } 1048 hn = hash_lookup(h, tok1); 1049 if (!hn) { 1050 puts("hash_lookup failed"); 1051 break; 1052 } 1053 val = hnode_get(hn); 1054 puts(val); 1055 break; 1056 case 'n': 1057 printf("%lu\n", (unsigned long) hash_size(h)); 1058 break; 1059 case 'c': 1060 printf("%lu\n", (unsigned long) hash_count(h)); 1061 break; 1062 case 't': 1063 hash_scan_begin(&hs, h); 1064 while ((hn = hash_scan_next(&hs))) 1065 printf("%s\t%s\n", (char*) hnode_getkey(hn), 1066 (char*) hnode_get(hn)); 1067 break; 1068 case '+': 1069 grow_table(h); /* private function */ 1070 break; 1071 case '-': 1072 shrink_table(h); /* private function */ 1073 break; 1074 case 'q': 1075 exit(0); 1076 break; 1077 case '\0': 1078 break; 1079 case 'p': 1080 prompt = 1; 1081 break; 1082 case 's': 1083 hash_set_allocator(h, new_node, del_node, NULL); 1084 break; 1085 default: 1086 putchar('?'); 1087 putchar('\n'); 1088 break; 1089 } 1090 } 1091 1092 return 0; 1093} 1094 1095#endif 1096