1 /* $NetBSD: binhash.c,v 1.2 2017/02/14 01:16:49 christos Exp $ */ 2 3 /*++ 4 /* NAME 5 /* binhash 3 6 /* SUMMARY 7 /* hash table manager 8 /* SYNOPSIS 9 /* #include <binhash.h> 10 /* 11 /* typedef struct { 12 /* .in +4 13 /* void *key; 14 /* ssize_t key_len; 15 /* void *value; 16 /* /* private fields... */ 17 /* .in -4 18 /* } BINHASH_INFO; 19 /* 20 /* BINHASH *binhash_create(size) 21 /* ssize_t size; 22 /* 23 /* BINHASH_INFO *binhash_enter(table, key, key_len, value) 24 /* BINHASH *table; 25 /* const void *key; 26 /* ssize_t key_len; 27 /* void *value; 28 /* 29 /* char *binhash_find(table, key, key_len) 30 /* BINHASH *table; 31 /* const void *key; 32 /* ssize_t key_len; 33 /* 34 /* BINHASH_INFO *binhash_locate(table, key, key_len) 35 /* BINHASH *table; 36 /* const void *key; 37 /* ssize_t key_len; 38 /* 39 /* void binhash_delete(table, key, key_len, free_fn) 40 /* BINHASH *table; 41 /* const void *key; 42 /* ssize_t key_len; 43 /* void (*free_fn)(void *); 44 /* 45 /* void binhash_free(table, free_fn) 46 /* BINHASH *table; 47 /* void (*free_fn)(void *); 48 /* 49 /* void binhash_walk(table, action, ptr) 50 /* BINHASH *table; 51 /* void (*action)(BINHASH_INFO *info, void *ptr); 52 /* void *ptr; 53 /* 54 /* BINHASH_INFO **binhash_list(table) 55 /* BINHASH *table; 56 /* DESCRIPTION 57 /* This module maintains one or more hash tables. Each table entry 58 /* consists of a unique binary-valued lookup key and a generic 59 /* character-pointer value. 60 /* The tables are automatically resized when they fill up. When the 61 /* values to be remembered are not character pointers, proper casts 62 /* should be used or the code will not be portable. 63 /* 64 /* binhash_create() creates a table of the specified size and returns a 65 /* pointer to the result. The lookup keys are saved with mymemdup(). 66 /* 67 /* binhash_enter() stores a (key, value) pair into the specified table 68 /* and returns a pointer to the resulting entry. The code does not 69 /* check if an entry with that key already exists: use binhash_locate() 70 /* for updating an existing entry. The key is copied; the value is not. 71 /* 72 /* binhash_find() returns the value that was stored under the given key, 73 /* or a null pointer if it was not found. In order to distinguish 74 /* a null value from a non-existent value, use binhash_locate(). 75 /* 76 /* binhash_locate() returns a pointer to the entry that was stored 77 /* for the given key, or a null pointer if it was not found. 78 /* 79 /* binhash_delete() removes one entry that was stored under the given key. 80 /* If the free_fn argument is not a null pointer, the corresponding 81 /* function is called with as argument the value that was stored under 82 /* the key. 83 /* 84 /* binhash_free() destroys a hash table, including contents. If the free_fn 85 /* argument is not a null pointer, the corresponding function is called 86 /* for each table entry, with as argument the value that was stored 87 /* with the entry. 88 /* 89 /* binhash_walk() invokes the action function for each table entry, with 90 /* a pointer to the entry as its argument. The ptr argument is passed 91 /* on to the action function. 92 /* 93 /* binhash_list() returns a null-terminated list of pointers to 94 /* all elements in the named table. The list should be passed to 95 /* myfree(). 96 /* RESTRICTIONS 97 /* A callback function should not modify the hash table that is 98 /* specified to its caller. 99 /* DIAGNOSTICS 100 /* The following conditions are reported and cause the program to 101 /* terminate immediately: memory allocation failure; an attempt 102 /* to delete a non-existent entry. 103 /* SEE ALSO 104 /* mymalloc(3) memory management wrapper 105 /* LICENSE 106 /* .ad 107 /* .fi 108 /* The Secure Mailer license must be distributed with this software. 109 /* AUTHOR(S) 110 /* Wietse Venema 111 /* IBM T.J. Watson Research 112 /* P.O. Box 704 113 /* Yorktown Heights, NY 10598, USA 114 /*--*/ 115 116 /* C library */ 117 118 #include <sys_defs.h> 119 #include <string.h> 120 121 /* Local stuff */ 122 123 #include "mymalloc.h" 124 #include "msg.h" 125 #include "binhash.h" 126 127 /* binhash_hash - hash a string */ 128 129 static size_t binhash_hash(const void *key, ssize_t len, size_t size) 130 { 131 size_t h = 0; 132 size_t g; 133 134 /* 135 * From the "Dragon" book by Aho, Sethi and Ullman. 136 */ 137 138 while (len-- > 0) { 139 h = (h << 4U) + *(unsigned const char *) key++; 140 if ((g = (h & 0xf0000000)) != 0) { 141 h ^= (g >> 24U); 142 h ^= g; 143 } 144 } 145 return (h % size); 146 } 147 148 /* binhash_link - insert element into table */ 149 150 #define binhash_link(table, elm) { \ 151 BINHASH_INFO **_h = table->data + binhash_hash(elm->key, elm->key_len, table->size);\ 152 elm->prev = 0; \ 153 if ((elm->next = *_h) != 0) \ 154 (*_h)->prev = elm; \ 155 *_h = elm; \ 156 table->used++; \ 157 } 158 159 /* binhash_size - allocate and initialize hash table */ 160 161 static void binhash_size(BINHASH *table, size_t size) 162 { 163 BINHASH_INFO **h; 164 165 size |= 1; 166 167 table->data = h = (BINHASH_INFO **) mymalloc(size * sizeof(BINHASH_INFO *)); 168 table->size = size; 169 table->used = 0; 170 171 while (size-- > 0) 172 *h++ = 0; 173 } 174 175 /* binhash_create - create initial hash table */ 176 177 BINHASH *binhash_create(ssize_t size) 178 { 179 BINHASH *table; 180 181 table = (BINHASH *) mymalloc(sizeof(BINHASH)); 182 binhash_size(table, size < 13 ? 13 : size); 183 return (table); 184 } 185 186 /* binhash_grow - extend existing table */ 187 188 static void binhash_grow(BINHASH *table) 189 { 190 BINHASH_INFO *ht; 191 BINHASH_INFO *next; 192 ssize_t old_size = table->size; 193 BINHASH_INFO **h = table->data; 194 BINHASH_INFO **old_entries = h; 195 196 binhash_size(table, 2 * old_size); 197 198 while (old_size-- > 0) { 199 for (ht = *h++; ht; ht = next) { 200 next = ht->next; 201 binhash_link(table, ht); 202 } 203 } 204 myfree((void *) old_entries); 205 } 206 207 /* binhash_enter - enter (key, value) pair */ 208 209 BINHASH_INFO *binhash_enter(BINHASH *table, const void *key, ssize_t key_len, void *value) 210 { 211 BINHASH_INFO *ht; 212 213 if (table->used >= table->size) 214 binhash_grow(table); 215 ht = (BINHASH_INFO *) mymalloc(sizeof(BINHASH_INFO)); 216 ht->key = mymemdup(key, key_len); 217 ht->key_len = key_len; 218 ht->value = value; 219 binhash_link(table, ht); 220 return (ht); 221 } 222 223 /* binhash_find - lookup value */ 224 225 void *binhash_find(BINHASH *table, const void *key, ssize_t key_len) 226 { 227 BINHASH_INFO *ht; 228 229 #define KEY_EQ(x,y,l) (((unsigned char *) x)[0] == ((unsigned char *) y)[0] && memcmp(x,y,l) == 0) 230 231 if (table != 0) 232 for (ht = table->data[binhash_hash(key, key_len, table->size)]; ht; ht = ht->next) 233 if (key_len == ht->key_len && KEY_EQ(key, ht->key, key_len)) 234 return (ht->value); 235 return (0); 236 } 237 238 /* binhash_locate - lookup entry */ 239 240 BINHASH_INFO *binhash_locate(BINHASH *table, const void *key, ssize_t key_len) 241 { 242 BINHASH_INFO *ht; 243 244 if (table != 0) 245 for (ht = table->data[binhash_hash(key, key_len, table->size)]; ht; ht = ht->next) 246 if (key_len == ht->key_len && KEY_EQ(key, ht->key, key_len)) 247 return (ht); 248 return (0); 249 } 250 251 /* binhash_delete - delete one entry */ 252 253 void binhash_delete(BINHASH *table, const void *key, ssize_t key_len, void (*free_fn) (void *)) 254 { 255 if (table != 0) { 256 BINHASH_INFO *ht; 257 BINHASH_INFO **h = table->data + binhash_hash(key, key_len, table->size); 258 259 for (ht = *h; ht; ht = ht->next) { 260 if (key_len == ht->key_len && KEY_EQ(key, ht->key, key_len)) { 261 if (ht->next) 262 ht->next->prev = ht->prev; 263 if (ht->prev) 264 ht->prev->next = ht->next; 265 else 266 *h = ht->next; 267 table->used--; 268 myfree(ht->key); 269 if (free_fn) 270 (*free_fn) (ht->value); 271 myfree((void *) ht); 272 return; 273 } 274 } 275 msg_panic("binhash_delete: unknown_key: \"%s\"", (char *) key); 276 } 277 } 278 279 /* binhash_free - destroy hash table */ 280 281 void binhash_free(BINHASH *table, void (*free_fn) (void *)) 282 { 283 if (table != 0) { 284 ssize_t i = table->size; 285 BINHASH_INFO *ht; 286 BINHASH_INFO *next; 287 BINHASH_INFO **h = table->data; 288 289 while (i-- > 0) { 290 for (ht = *h++; ht; ht = next) { 291 next = ht->next; 292 myfree(ht->key); 293 if (free_fn) 294 (*free_fn) (ht->value); 295 myfree((void *) ht); 296 } 297 } 298 myfree((void *) table->data); 299 table->data = 0; 300 myfree((void *) table); 301 } 302 } 303 304 /* binhash_walk - iterate over hash table */ 305 306 void binhash_walk(BINHASH *table, void (*action) (BINHASH_INFO *, void *), 307 void *ptr) { 308 if (table != 0) { 309 ssize_t i = table->size; 310 BINHASH_INFO **h = table->data; 311 BINHASH_INFO *ht; 312 313 while (i-- > 0) 314 for (ht = *h++; ht; ht = ht->next) 315 (*action) (ht, ptr); 316 } 317 } 318 319 /* binhash_list - list all table members */ 320 321 BINHASH_INFO **binhash_list(table) 322 BINHASH *table; 323 { 324 BINHASH_INFO **list; 325 BINHASH_INFO *member; 326 ssize_t count = 0; 327 ssize_t i; 328 329 if (table != 0) { 330 list = (BINHASH_INFO **) mymalloc(sizeof(*list) * (table->used + 1)); 331 for (i = 0; i < table->size; i++) 332 for (member = table->data[i]; member != 0; member = member->next) 333 list[count++] = member; 334 } else { 335 list = (BINHASH_INFO **) mymalloc(sizeof(*list)); 336 } 337 list[count] = 0; 338 return (list); 339 } 340