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