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