1 /* $NetBSD: htable.c,v 1.3 2022/10/08 16:12:50 christos Exp $ */ 2 3 /*++ 4 /* NAME 5 /* htable 3 6 /* SUMMARY 7 /* hash table manager 8 /* SYNOPSIS 9 /* #include <htable.h> 10 /* 11 /* typedef struct { 12 /* .in +4 13 /* char *key; 14 /* void *value; 15 /* /* private fields... */ 16 /* .in -4 17 /* } HTABLE_INFO; 18 /* 19 /* HTABLE *htable_create(size) 20 /* int size; 21 /* 22 /* HTABLE_INFO *htable_enter(table, key, value) 23 /* HTABLE *table; 24 /* const char *key; 25 /* void *value; 26 /* 27 /* char *htable_find(table, key) 28 /* HTABLE *table; 29 /* const char *key; 30 /* 31 /* HTABLE_INFO *htable_locate(table, key) 32 /* HTABLE *table; 33 /* const char *key; 34 /* 35 /* void htable_delete(table, key, free_fn) 36 /* HTABLE *table; 37 /* const char *key; 38 /* void (*free_fn)(void *); 39 /* 40 /* void htable_free(table, free_fn) 41 /* HTABLE *table; 42 /* void (*free_fn)(void *); 43 /* 44 /* void htable_walk(table, action, ptr) 45 /* HTABLE *table; 46 /* void (*action)(HTABLE_INFO *, void *ptr); 47 /* void *ptr; 48 /* 49 /* HTABLE_INFO **htable_list(table) 50 /* HTABLE *table; 51 /* 52 /* HTABLE_INFO *htable_sequence(table, how) 53 /* HTABLE *table; 54 /* int how; 55 /* DESCRIPTION 56 /* This module maintains one or more hash tables. Each table entry 57 /* consists of a unique string-valued lookup key and a generic 58 /* character-pointer value. 59 /* The tables are automatically resized when they fill up. When the 60 /* values to be remembered are not character pointers, proper casts 61 /* should be used or the code will not be portable. 62 /* 63 /* htable_create() creates a table of the specified size and returns a 64 /* pointer to the result. The lookup keys are saved with mystrdup(). 65 /* htable_enter() stores a (key, value) pair into the specified table 66 /* and returns a pointer to the resulting entry. The code does not 67 /* check if an entry with that key already exists: use htable_locate() 68 /* for updating an existing entry. 69 /* 70 /* htable_find() returns the value that was stored under the given key, 71 /* or a null pointer if it was not found. In order to distinguish 72 /* a null value from a non-existent value, use htable_locate(). 73 /* 74 /* htable_locate() returns a pointer to the entry that was stored 75 /* for the given key, or a null pointer if it was not found. 76 /* 77 /* htable_delete() removes one entry that was stored under the given key. 78 /* If the free_fn argument is not a null pointer, the corresponding 79 /* function is called with as argument the non-zero value stored under 80 /* the key. 81 /* 82 /* htable_free() destroys a hash table, including contents. If the free_fn 83 /* argument is not a null pointer, the corresponding function is called 84 /* for each table entry, with as argument the non-zero value stored 85 /* with the entry. 86 /* 87 /* htable_walk() invokes the action function for each table entry, with 88 /* a pointer to the entry as its argument. The ptr argument is passed 89 /* on to the action function. 90 /* 91 /* htable_list() returns a null-terminated list of pointers to 92 /* all elements in the named table. The list should be passed to 93 /* myfree(). 94 /* 95 /* htable_sequence() returns the first or next element depending 96 /* on the value of the "how" argument. Specify HTABLE_SEQ_FIRST 97 /* to start a new sequence, HTABLE_SEQ_NEXT to continue, and 98 /* HTABLE_SEQ_STOP to terminate a sequence early. The caller 99 /* must not delete an element before it is visited. 100 /* RESTRICTIONS 101 /* A callback function should not modify the hash table that is 102 /* specified to its caller. 103 /* DIAGNOSTICS 104 /* The following conditions are reported and cause the program to 105 /* terminate immediately: memory allocation failure; an attempt 106 /* to delete a non-existent entry. 107 /* SEE ALSO 108 /* mymalloc(3) memory management wrapper 109 /* hash_fnv(3) Fowler/Noll/Vo hash function 110 /* LICENSE 111 /* .ad 112 /* .fi 113 /* The Secure Mailer license must be distributed with this software. 114 /* AUTHOR(S) 115 /* Wietse Venema 116 /* IBM T.J. Watson Research 117 /* P.O. Box 704 118 /* Yorktown Heights, NY 10598, USA 119 /* 120 /* Wietse Venema 121 /* Google, Inc. 122 /* 111 8th Avenue 123 /* New York, NY 10011, USA 124 /*--*/ 125 126 /* C library */ 127 128 #include <sys_defs.h> 129 #include <string.h> 130 131 /* Local stuff */ 132 133 #include "mymalloc.h" 134 #include "msg.h" 135 #include "htable.h" 136 137 /* htable_hash - hash a string */ 138 139 #ifndef NO_HASH_FNV 140 #include "hash_fnv.h" 141 142 #define htable_hash(s, size) (hash_fnv((s), strlen(s)) % (size)) 143 144 #else 145 146 static size_t htable_hash(const char *s, size_t size) 147 { 148 size_t h = 0; 149 size_t g; 150 151 /* 152 * From the "Dragon" book by Aho, Sethi and Ullman. 153 */ 154 155 while (*s) { 156 h = (h << 4U) + *(unsigned const char *) s++; 157 if ((g = (h & 0xf0000000)) != 0) { 158 h ^= (g >> 24U); 159 h ^= g; 160 } 161 } 162 return (h % size); 163 } 164 165 #endif 166 167 /* htable_link - insert element into table */ 168 169 #define htable_link(table, element) { \ 170 HTABLE_INFO **_h = table->data + htable_hash(element->key, table->size);\ 171 element->prev = 0; \ 172 if ((element->next = *_h) != 0) \ 173 (*_h)->prev = element; \ 174 *_h = element; \ 175 table->used++; \ 176 } 177 178 /* htable_size - allocate and initialize hash table */ 179 180 static void htable_size(HTABLE *table, size_t size) 181 { 182 HTABLE_INFO **h; 183 184 size |= 1; 185 186 table->data = h = (HTABLE_INFO **) mymalloc(size * sizeof(HTABLE_INFO *)); 187 table->size = size; 188 table->used = 0; 189 190 while (size-- > 0) 191 *h++ = 0; 192 } 193 194 /* htable_create - create initial hash table */ 195 196 HTABLE *htable_create(ssize_t size) 197 { 198 HTABLE *table; 199 200 table = (HTABLE *) mymalloc(sizeof(HTABLE)); 201 htable_size(table, size < 13 ? 13 : size); 202 table->seq_bucket = table->seq_element = 0; 203 return (table); 204 } 205 206 /* htable_grow - extend existing table */ 207 208 static void htable_grow(HTABLE *table) 209 { 210 HTABLE_INFO *ht; 211 HTABLE_INFO *next; 212 size_t old_size = table->size; 213 HTABLE_INFO **h = table->data; 214 HTABLE_INFO **old_entries = h; 215 216 htable_size(table, 2 * old_size); 217 218 while (old_size-- > 0) { 219 for (ht = *h++; ht; ht = next) { 220 next = ht->next; 221 htable_link(table, ht); 222 } 223 } 224 myfree((void *) old_entries); 225 } 226 227 /* htable_enter - enter (key, value) pair */ 228 229 HTABLE_INFO *htable_enter(HTABLE *table, const char *key, void *value) 230 { 231 HTABLE_INFO *ht; 232 233 if (table->used >= table->size) 234 htable_grow(table); 235 ht = (HTABLE_INFO *) mymalloc(sizeof(HTABLE_INFO)); 236 ht->key = mystrdup(key); 237 ht->value = value; 238 htable_link(table, ht); 239 return (ht); 240 } 241 242 /* htable_find - lookup value */ 243 244 void *htable_find(HTABLE *table, const char *key) 245 { 246 HTABLE_INFO *ht; 247 248 #define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0)) 249 250 if (table) 251 for (ht = table->data[htable_hash(key, table->size)]; ht; ht = ht->next) 252 if (STREQ(key, ht->key)) 253 return (ht->value); 254 return (0); 255 } 256 257 /* htable_locate - lookup entry */ 258 259 HTABLE_INFO *htable_locate(HTABLE *table, const char *key) 260 { 261 HTABLE_INFO *ht; 262 263 #define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0)) 264 265 if (table) 266 for (ht = table->data[htable_hash(key, table->size)]; ht; ht = ht->next) 267 if (STREQ(key, ht->key)) 268 return (ht); 269 return (0); 270 } 271 272 /* htable_delete - delete one entry */ 273 274 void htable_delete(HTABLE *table, const char *key, void (*free_fn) (void *)) 275 { 276 if (table) { 277 HTABLE_INFO *ht; 278 HTABLE_INFO **h = table->data + htable_hash(key, table->size); 279 280 #define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0)) 281 282 for (ht = *h; ht; ht = ht->next) { 283 if (STREQ(key, ht->key)) { 284 if (ht->next) 285 ht->next->prev = ht->prev; 286 if (ht->prev) 287 ht->prev->next = ht->next; 288 else 289 *h = ht->next; 290 table->used--; 291 myfree(ht->key); 292 if (free_fn && ht->value) 293 (*free_fn) (ht->value); 294 myfree((void *) ht); 295 return; 296 } 297 } 298 msg_panic("htable_delete: unknown_key: \"%s\"", key); 299 } 300 } 301 302 /* htable_free - destroy hash table */ 303 304 void htable_free(HTABLE *table, void (*free_fn) (void *)) 305 { 306 if (table) { 307 ssize_t i = table->size; 308 HTABLE_INFO *ht; 309 HTABLE_INFO *next; 310 HTABLE_INFO **h = table->data; 311 312 while (i-- > 0) { 313 for (ht = *h++; ht; ht = next) { 314 next = ht->next; 315 myfree(ht->key); 316 if (free_fn && ht->value) 317 (*free_fn) (ht->value); 318 myfree((void *) ht); 319 } 320 } 321 myfree((void *) table->data); 322 table->data = 0; 323 if (table->seq_bucket) 324 myfree((void *) table->seq_bucket); 325 table->seq_bucket = 0; 326 myfree((void *) table); 327 } 328 } 329 330 /* htable_walk - iterate over hash table */ 331 332 void htable_walk(HTABLE *table, void (*action) (HTABLE_INFO *, void *), 333 void *ptr) { 334 if (table) { 335 ssize_t i = table->size; 336 HTABLE_INFO **h = table->data; 337 HTABLE_INFO *ht; 338 339 while (i-- > 0) 340 for (ht = *h++; ht; ht = ht->next) 341 (*action) (ht, ptr); 342 } 343 } 344 345 /* htable_list - list all table members */ 346 347 HTABLE_INFO **htable_list(HTABLE *table) 348 { 349 HTABLE_INFO **list; 350 HTABLE_INFO *member; 351 ssize_t count = 0; 352 ssize_t i; 353 354 if (table != 0) { 355 list = (HTABLE_INFO **) mymalloc(sizeof(*list) * (table->used + 1)); 356 for (i = 0; i < table->size; i++) 357 for (member = table->data[i]; member != 0; member = member->next) 358 list[count++] = member; 359 } else { 360 list = (HTABLE_INFO **) mymalloc(sizeof(*list)); 361 } 362 list[count] = 0; 363 return (list); 364 } 365 366 /* htable_sequence - dict(3) compatibility iterator */ 367 368 HTABLE_INFO *htable_sequence(HTABLE *table, int how) 369 { 370 if (table == 0) 371 return (0); 372 373 switch (how) { 374 case HTABLE_SEQ_FIRST: /* start new sequence */ 375 if (table->seq_bucket) 376 myfree((void *) table->seq_bucket); 377 table->seq_bucket = htable_list(table); 378 table->seq_element = table->seq_bucket; 379 return (*(table->seq_element)++); 380 case HTABLE_SEQ_NEXT: /* next element */ 381 if (table->seq_element && *table->seq_element) 382 return (*(table->seq_element)++); 383 /* FALLTHROUGH */ 384 default: /* terminate sequence */ 385 if (table->seq_bucket) { 386 myfree((void *) table->seq_bucket); 387 table->seq_bucket = table->seq_element = 0; 388 } 389 return (0); 390 } 391 } 392 393 #ifdef TEST 394 #include <vstring_vstream.h> 395 #include <myrand.h> 396 397 int main(int unused_argc, char **unused_argv) 398 { 399 VSTRING *buf = vstring_alloc(10); 400 ssize_t count = 0; 401 HTABLE *hash; 402 HTABLE_INFO **ht_info; 403 HTABLE_INFO **ht; 404 HTABLE_INFO *info; 405 ssize_t i; 406 ssize_t r; 407 int op; 408 409 /* 410 * Load a large number of strings and delete them in a random order. 411 */ 412 hash = htable_create(10); 413 while (vstring_get(buf, VSTREAM_IN) != VSTREAM_EOF) 414 htable_enter(hash, vstring_str(buf), CAST_INT_TO_VOID_PTR(count++)); 415 if (count != hash->used) 416 msg_panic("%ld entries stored, but %lu entries exist", 417 (long) count, (unsigned long) hash->used); 418 for (i = 0, op = HTABLE_SEQ_FIRST; htable_sequence(hash, op) != 0; 419 i++, op = HTABLE_SEQ_NEXT) 420 /* void */ ; 421 if (i != hash->used) 422 msg_panic("%ld entries found, but %lu entries exist", 423 (long) i, (unsigned long) hash->used); 424 ht_info = htable_list(hash); 425 for (i = 0; i < hash->used; i++) { 426 r = myrand() % hash->used; 427 info = ht_info[i]; 428 ht_info[i] = ht_info[r]; 429 ht_info[r] = info; 430 } 431 for (ht = ht_info; *ht; ht++) 432 htable_delete(hash, ht[0]->key, (void (*) (void *)) 0); 433 if (hash->used > 0) 434 msg_panic("%ld entries not deleted", (long) hash->used); 435 myfree((void *) ht_info); 436 htable_free(hash, (void (*) (void *)) 0); 437 vstring_free(buf); 438 return (0); 439 } 440 441 #endif 442