hash.h

   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