1 /*******************************************************************************
2 *
3 * HEADER: hash
4 *
5 ********************************************************************************
6 *
7 * DESCRIPTION: Generic hash table routines
8 *
9 ********************************************************************************
10 *
11 * Copyright (c) 2002-2020 Marcus Holland-Moritz. All rights reserved.
12 * This program is free software; you can redistribute it and/or modify
13 * it under the same terms as Perl itself.
14 *
15 *******************************************************************************/
16 
17 /**
18  *  \file hash.h
19  *  \brief Generic implementation of Hash Tables
20  */
21 #ifndef _UTIL_HASH_H
22 #define _UTIL_HASH_H
23 
24 /**
25  *  Maximum allowed hash size
26  *
27  *  This controls the maximum number of hash buckets,
28  *  currently 2^16 = 65536.
29  */
30 #define MAX_HASH_TABLE_SIZE 16
31 
32 /**
33  *  Compute hash sum and string length
34  *
35  *  The HASH_STR_LEN() macro computes the hash sum and
36  *  string length of a zero terminated string.
37  *
38  *  \param hash         Variable that will receive the
39  *                      hash sum.
40  *
41  *  \param str          Pointer to the zero terminated
42  *                      string.
43  *
44  *  \param len          Variable that will receive the
45  *                      string length.
46  *
47  *  \see HASH_STRING() and HASH_DATA()
48  *  \hideinitializer
49  */
50 #define HASH_STR_LEN( hash, str, len )         \
51         do {                                   \
52           register int         _len = 0;       \
53           register const char *_str = str;     \
54           register HashSum     _hash = 0;      \
55                                                \
56           while( *_str ) {                     \
57             _len++;                            \
58             _hash += *_str++;                  \
59             _hash += (_hash << 10);            \
60             _hash ^= (_hash >> 6);             \
61           }                                    \
62                                                \
63           _hash += (_hash << 3);               \
64           _hash ^= (_hash >> 11);              \
65           (hash) = (_hash + (_hash << 15));    \
66           (len)  = _len;                       \
67         } while(0)
68 
69 /**
70  *  Compute hash sum
71  *
72  *  The HASH_STRING() macro computes the hash sum
73  *  of a zero terminated string.
74  *
75  *  \param hash         Variable that will receive the
76  *                      hash sum.
77  *
78  *  \param str          Pointer to the zero terminated
79  *                      string.
80  *
81  *  \see HASH_STR_LEN() and HASH_DATA()
82  *  \hideinitializer
83  */
84 #define HASH_STRING( hash, str )               \
85         do {                                   \
86           register const char *_str = str;     \
87           register HashSum     _hash = 0;      \
88                                                \
89           while( *_str ) {                     \
90             _hash += *_str++;                  \
91             _hash += (_hash << 10);            \
92             _hash ^= (_hash >> 6);             \
93           }                                    \
94                                                \
95           _hash += (_hash << 3);               \
96           _hash ^= (_hash >> 11);              \
97           (hash) = (_hash + (_hash << 15));    \
98         } while(0)
99 
100 /**
101  *  Compute hash sum of arbitrary data
102  *
103  *  The HASH_DATA() macro computes the hash sum
104  *  of a an arbitrary data memory block.
105  *
106  *  \param hash         Variable that will receive the
107  *                      hash sum.
108  *
109  *  \param len          Length of the data block.
110  *
111  *  \param data         Pointer to the data block.
112  *
113  *  \see HASH_STR_LEN() and HASH_STRING()
114  *  \hideinitializer
115  */
116 #define HASH_DATA( hash, len, data )           \
117         do {                                   \
118           register const char *_data = data;   \
119           register int         _len  = len;    \
120           register HashSum     _hash = 0;      \
121                                                \
122           while( _len-- ) {                    \
123             _hash += *_data++;                 \
124             _hash += (_hash << 10);            \
125             _hash ^= (_hash >> 6);             \
126           }                                    \
127                                                \
128           _hash += (_hash << 3);               \
129           _hash ^= (_hash >> 11);              \
130           (hash) = (_hash + (_hash << 15));    \
131         } while(0)
132 
133 /**
134  *  Hash Table Handle
135  */
136 typedef struct _hashTable * HashTable;
137 typedef const struct _hashTable * ConstHashTable;
138 
139 /**
140  *  Hash Sum
141  */
142 typedef unsigned long HashSum;
143 
144 /**
145  *  Hash Node
146  */
147 typedef struct _hashNode *HashNode;
148 typedef const struct _hashNode *ConstHashNode;
149 
150 struct _hashNode {
151   HashNode  next;
152   void     *pObj;
153   HashSum   hash;
154   int       keylen;
155   char      key[1];
156 };
157 
158 /**
159  *  Hash Table Iterator
160  */
161 typedef struct _hashIterator {
162   ConstHashNode pNode;
163   HashNode *pBucket;
164   int remain;
165 #ifdef DEBUG_UTIL_HASH
166   ConstHashTable table;
167   unsigned orig_state;
168 #endif
169 } HashIterator;
170 
171 /**
172  *  Destructor Function Pointer
173  */
174 typedef void (* HTDestroyFunc)(void *);
175 
176 /**
177  *  Cloning Function Pointer
178  */
179 typedef void * (* HTCloneFunc)(const void *);
180 
181 HashTable  HT_new_ex( int size, unsigned long flags );
182 void       HT_delete( HashTable table );
183 void       HT_flush( HashTable table, HTDestroyFunc destroy );
184 void       HT_destroy( HashTable table, HTDestroyFunc destroy );
185 HashTable  HT_clone( ConstHashTable table, HTCloneFunc func );
186 
187 int        HT_resize( HashTable table, int size );
188 int        HT_size( ConstHashTable table );
189 int        HT_count( ConstHashTable table );
190 
191 HashNode   HN_new( const char *key, int keylen, HashSum hash );
192 void       HN_delete( HashNode node );
193 
194 int        HT_storenode( HashTable table, HashNode node, void *pObj );
195 void *     HT_fetchnode( HashTable table, HashNode node );
196 void *     HT_rmnode( HashTable table, HashNode node );
197 
198 int        HT_store( HashTable table, const char *key, int keylen, HashSum hash, void *pObj );
199 void *     HT_fetch( HashTable table, const char *key, int keylen, HashSum hash );
200 void *     HT_get( ConstHashTable table, const char *key, int keylen, HashSum hash );
201 int        HT_exists( ConstHashTable table, const char *key, int keylen, HashSum hash );
202 
203 void       HI_init(HashIterator *it, ConstHashTable table);
204 int        HI_next(HashIterator *it, const char **ppKey, int *pKeylen, void **ppObj);
205 
206 /* hash table flags */
207 #define HT_AUTOGROW            0x00000001
208 #define HT_AUTOSHRINK          0x00000002
209 #define HT_AUTOSIZE            (HT_AUTOGROW|HT_AUTOSHRINK)
210 
211 /* debug flags */
212 #define DB_HASH_MAIN           0x00000001
213 
214 #ifdef DEBUG_UTIL_HASH
215 void HT_dump( ConstHashTable table );
216 int  SetDebugHash( void (*dbfunc)(const char *, ...), unsigned long dbflags );
217 #else
218 #define SetDebugHash( func, flags ) 0
219 #endif
220 
221 /**
222  *  Constructor
223  *
224  *  Using the HT_new() function you create an empty hash table.
225  *
226  *  \param size         Hash table base size. You can specify
227  *                      any value between 1 and 16. Depending
228  *                      on how many elements you plan to store
229  *                      in the hash table, values from 6 to 12
230  *                      can be considered useful. The number
231  *                      of buckets created is 2^size, so if
232  *                      you specify a size of 10, 1024 buckets
233  *                      will be created and the empty hash
234  *                      table will consume about 4kB of memory.
235  *                      However, 1024 buckets will be enough
236  *                      to very efficiently manage 100000 hash
237  *                      elements.
238  *
239  *  \return A handle to the newly created hash table.
240  *
241  *  \see HT_new_ex(), HT_delete() and HT_destroy()
242  */
243 #define HT_new( size ) HT_new_ex( size, 0 )
244 
245 /**
246  *  Loop over all hash elements.
247  *
248  *  The HT_foreach() macro is actually only a shortcut for the
249  *  following loop:
250  *
251  *  \code
252  *  for( HT_reset(table); HT_next(table, (char **)&(pKey), NULL, (void **)&(pObj)); ) {
253  *    // do something with pKey and pObj
254  *  }
255  *  \endcode
256  *
257  *  It is safe to use HT_foreach() even if \a hash table handle is NULL.
258  *  In that case, the loop won't be executed.
259  *
260  *  \param pKey         Variable that will receive a pointer
261  *                      to the current hash key string.
262  *
263  *  \param pObj         Variable that will receive a pointer
264  *                      to the current object.
265  *
266  *  \param iter         Pointer to hash iterator object.
267  *
268  *  \param table        Handle to an existing hash table.
269  *
270  *  \see HT_reset() and HT_next()
271  *  \hideinitializer
272  */
273 #define HT_foreach(pKey, pObj, iter, table) \
274           for (HI_init(&iter, table); HI_next(&iter, &(pKey), NULL, (void **)&(pObj)); )
275 
276 /**
277  *  Loop over all hash keys.
278  *
279  *  Like HT_foreach(), just that the value parameter isn't used.
280  *
281  *  It is safe to use HT_foreach_keys() even if \a hash table handle is NULL.
282  *  In that case, the loop won't be executed.
283  *
284  *  \param pKey         Variable that will receive a pointer
285  *                      to the current hash key string.
286  *
287  *  \param iter         Pointer to hash iterator object.
288  *
289  *  \param table        Handle to an existing hash table.
290  *
291  *  \see HT_foreach() and HT_foreach_values()
292  *  \hideinitializer
293  */
294 #define HT_foreach_keys(pKey, iter, table) \
295           for (HI_init(&iter, table); HI_next(&iter, &(pKey), NULL, NULL); )
296 
297 /**
298  *  Loop over all hash values.
299  *
300  *  Like HT_foreach(), just that the key parameter isn't used.
301  *
302  *  It is safe to use HT_foreach_values() even if \a hash table handle is NULL.
303  *  In that case, the loop won't be executed.
304  *
305  *  \param pObj         Variable that will receive a pointer
306  *                      to the current object.
307  *
308  *  \param iter         Pointer to hash iterator object.
309  *
310  *  \param table        Handle to an existing hash table.
311  *
312  *  \see HT_foreach() and HT_foreach_keys()
313  *  \hideinitializer
314  */
315 #define HT_foreach_values(pObj, iter, table) \
316           for (HI_init(&iter, table); HI_next(&iter, NULL, NULL, (void **)&(pObj)); )
317 
318 #endif
319