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