"Fossies" - the Fresh Open Source Software Archive

Member "fusesmb-0.8.7/hash.c" (22 Jul 2005, 28255 Bytes) of package /linux/privat/old/fusesmb-0.8.7.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "hash.c" see the Fossies "Dox" file reference documentation.

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