"Fossies" - the Fresh Open Source Software Archive 
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