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