"Fossies" - the Fresh Open Source Software Archive

Member "fusesmb-0.8.7/hash.h" (22 Jul 2005, 9228 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.h" 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.h,v 1.22.2.7 2000/11/13 01:36:45 kaz Exp $
   18  * $Name: kazlib_1_20 $
   19  */
   20 
   21 #ifndef HASH_H
   22 #define HASH_H
   23 
   24 #include <limits.h>
   25 #ifdef KAZLIB_SIDEEFFECT_DEBUG
   26 #include "sfx.h"
   27 #endif
   28 
   29 /*
   30  * Blurb for inclusion into C++ translation units
   31  */
   32 
   33 #ifdef __cplusplus
   34 extern "C" {
   35 #endif
   36 
   37 typedef unsigned long hashcount_t;
   38 #define HASHCOUNT_T_MAX ULONG_MAX
   39 
   40 typedef unsigned long hash_val_t;
   41 #define HASH_VAL_T_MAX ULONG_MAX
   42 
   43 extern int hash_val_t_bit;
   44 
   45 #ifndef HASH_VAL_T_BIT
   46 #define HASH_VAL_T_BIT ((int) hash_val_t_bit)
   47 #endif
   48 
   49 /*
   50  * Hash chain node structure.
   51  * Notes:
   52  * 1. This preprocessing directive is for debugging purposes.  The effect is
   53  *    that if the preprocessor symbol KAZLIB_OPAQUE_DEBUG is defined prior to the
   54  *    inclusion of this header,  then the structure shall be declared as having
   55  *    the single member   int __OPAQUE__.   This way, any attempts by the
   56  *    client code to violate the principles of information hiding (by accessing
   57  *    the structure directly) can be diagnosed at translation time. However,
   58  *    note the resulting compiled unit is not suitable for linking.
   59  * 2. This is a pointer to the next node in the chain. In the last node of a
   60  *    chain, this pointer is null.
   61  * 3. The key is a pointer to some user supplied data that contains a unique
   62  *    identifier for each hash node in a given table. The interpretation of
   63  *    the data is up to the user. When creating or initializing a hash table,
   64  *    the user must supply a pointer to a function for comparing two keys,
   65  *    and a pointer to a function for hashing a key into a numeric value.
   66  * 4. The value is a user-supplied pointer to void which may refer to
   67  *    any data object. It is not interpreted in any way by the hashing
   68  *    module.
   69  * 5. The hashed key is stored in each node so that we don't have to rehash
   70  *    each key when the table must grow or shrink.
   71  */
   72 
   73 typedef struct hnode_t {
   74     #if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)   /* 1 */
   75     struct hnode_t *hash_next;      /* 2 */
   76     const void *hash_key;       /* 3 */
   77     void *hash_data;            /* 4 */
   78     hash_val_t hash_hkey;       /* 5 */
   79     #else
   80     int hash_dummy;
   81     #endif
   82 } hnode_t;
   83 
   84 /*
   85  * The comparison function pointer type. A comparison function takes two keys
   86  * and produces a value of -1 if the left key is less than the right key, a
   87  * value of 0 if the keys are equal, and a value of 1 if the left key is
   88  * greater than the right key.
   89  */
   90 
   91 typedef int (*hash_comp_t)(const void *, const void *);
   92 
   93 /*
   94  * The hashing function performs some computation on a key and produces an
   95  * integral value of type hash_val_t based on that key. For best results, the
   96  * function should have a good randomness properties in *all* significant bits
   97  * over the set of keys that are being inserted into a given hash table. In
   98  * particular, the most significant bits of hash_val_t are most significant to
   99  * the hash module. Only as the hash table expands are less significant bits
  100  * examined. Thus a function that has good distribution in its upper bits but
  101  * not lower is preferrable to one that has poor distribution in the upper bits
  102  * but not the lower ones.
  103  */
  104 
  105 typedef hash_val_t (*hash_fun_t)(const void *);
  106 
  107 /*
  108  * allocator functions
  109  */
  110 
  111 typedef hnode_t *(*hnode_alloc_t)(void *);
  112 typedef void (*hnode_free_t)(hnode_t *, void *);
  113 
  114 /*
  115  * This is the hash table control structure. It keeps track of information
  116  * about a hash table, as well as the hash table itself.
  117  * Notes:
  118  * 1.  Pointer to the hash table proper. The table is an array of pointers to
  119  *     hash nodes (of type hnode_t). If the table is empty, every element of
  120  *     this table is a null pointer. A non-null entry points to the first
  121  *     element of a chain of nodes.
  122  * 2.  This member keeps track of the size of the hash table---that is, the
  123  *     number of chain pointers.
  124  * 3.  The count member maintains the number of elements that are presently
  125  *     in the hash table.
  126  * 4.  The maximum count is the greatest number of nodes that can populate this
  127  *     table. If the table contains this many nodes, no more can be inserted,
  128  *     and the hash_isfull() function returns true.
  129  * 5.  The high mark is a population threshold, measured as a number of nodes,
  130  *     which, if exceeded, will trigger a table expansion. Only dynamic hash
  131  *     tables are subject to this expansion.
  132  * 6.  The low mark is a minimum population threshold, measured as a number of
  133  *     nodes. If the table population drops below this value, a table shrinkage
  134  *     will occur. Only dynamic tables are subject to this reduction.  No table
  135  *     will shrink beneath a certain absolute minimum number of nodes.
  136  * 7.  This is the a pointer to the hash table's comparison function. The
  137  *     function is set once at initialization or creation time.
  138  * 8.  Pointer to the table's hashing function, set once at creation or
  139  *     initialization time.
  140  * 9.  The current hash table mask. If the size of the hash table is 2^N,
  141  *     this value has its low N bits set to 1, and the others clear. It is used
  142  *     to select bits from the result of the hashing function to compute an
  143  *     index into the table.
  144  * 10. A flag which indicates whether the table is to be dynamically resized. It
  145  *     is set to 1 in dynamically allocated tables, 0 in tables that are
  146  *     statically allocated.
  147  */
  148 
  149 typedef struct hash_t {
  150     #if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
  151     struct hnode_t **hash_table;        /* 1 */
  152     hashcount_t hash_nchains;           /* 2 */
  153     hashcount_t hash_nodecount;         /* 3 */
  154     hashcount_t hash_maxcount;          /* 4 */
  155     hashcount_t hash_highmark;          /* 5 */
  156     hashcount_t hash_lowmark;           /* 6 */
  157     hash_comp_t hash_compare;           /* 7 */
  158     hash_fun_t hash_function;           /* 8 */
  159     hnode_alloc_t hash_allocnode;
  160     hnode_free_t hash_freenode;
  161     void *hash_context;
  162     hash_val_t hash_mask;           /* 9 */
  163     int hash_dynamic;               /* 10 */
  164     #else
  165     int hash_dummy;
  166     #endif
  167 } hash_t;
  168 
  169 /*
  170  * Hash scanner structure, used for traversals of the data structure.
  171  * Notes:
  172  * 1. Pointer to the hash table that is being traversed.
  173  * 2. Reference to the current chain in the table being traversed (the chain
  174  *    that contains the next node that shall be retrieved).
  175  * 3. Pointer to the node that will be retrieved by the subsequent call to
  176  *    hash_scan_next().
  177  */
  178 
  179 typedef struct hscan_t {
  180     #if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
  181     hash_t *hash_table;     /* 1 */
  182     hash_val_t hash_chain;  /* 2 */
  183     hnode_t *hash_next;     /* 3 */
  184     #else
  185     int hash_dummy;
  186     #endif
  187 } hscan_t;
  188 
  189 extern hash_t *hash_create(hashcount_t, hash_comp_t, hash_fun_t);
  190 extern void hash_set_allocator(hash_t *, hnode_alloc_t, hnode_free_t, void *);
  191 extern void hash_destroy(hash_t *);
  192 extern void hash_free_nodes(hash_t *);
  193 extern void hash_free(hash_t *);
  194 extern hash_t *hash_init(hash_t *, hashcount_t, hash_comp_t,
  195     hash_fun_t, hnode_t **, hashcount_t);
  196 extern void hash_insert(hash_t *, hnode_t *, const void *);
  197 extern hnode_t *hash_lookup(hash_t *, const void *);
  198 extern hnode_t *hash_delete(hash_t *, hnode_t *);
  199 extern int hash_alloc_insert(hash_t *, const void *, void *);
  200 extern void hash_delete_free(hash_t *, hnode_t *);
  201 
  202 extern void hnode_put(hnode_t *, void *);
  203 extern void *hnode_get(hnode_t *);
  204 extern const void *hnode_getkey(hnode_t *);
  205 extern hashcount_t hash_count(hash_t *);
  206 extern hashcount_t hash_size(hash_t *);
  207 
  208 extern int hash_isfull(hash_t *);
  209 extern int hash_isempty(hash_t *);
  210 
  211 extern void hash_scan_begin(hscan_t *, hash_t *);
  212 extern hnode_t *hash_scan_next(hscan_t *);
  213 extern hnode_t *hash_scan_delete(hash_t *, hnode_t *);
  214 extern void hash_scan_delfree(hash_t *, hnode_t *);
  215 
  216 extern int hash_verify(hash_t *);
  217 
  218 extern hnode_t *hnode_create(void *);
  219 extern hnode_t *hnode_init(hnode_t *, void *);
  220 extern void hnode_destroy(hnode_t *);
  221 
  222 #if defined(HASH_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
  223 #ifdef KAZLIB_SIDEEFFECT_DEBUG
  224 #define hash_isfull(H) (SFX_CHECK(H)->hash_nodecount == (H)->hash_maxcount)
  225 #else
  226 #define hash_isfull(H) ((H)->hash_nodecount == (H)->hash_maxcount)
  227 #endif
  228 #define hash_isempty(H) ((H)->hash_nodecount == 0)
  229 #define hash_count(H) ((H)->hash_nodecount)
  230 #define hash_size(H) ((H)->hash_nchains)
  231 #define hnode_get(N) ((N)->hash_data)
  232 #define hnode_getkey(N) ((N)->hash_key)
  233 #define hnode_put(N, V) ((N)->hash_data = (V))
  234 #endif
  235 
  236 #ifdef __cplusplus
  237 }
  238 #endif
  239 
  240 #endif