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