1 /* $NetBSD: htable.c,v 1.1.1.2 2010/06/17 18:07:14 tron 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 /* char *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 /* char *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)(char *); 39 /* 40 /* void htable_free(table, free_fn) 41 /* HTABLE *table; 42 /* void (*free_fn)(char *); 43 /* 44 /* void htable_walk(table, action, ptr) 45 /* HTABLE *table; 46 /* void (*action)(HTABLE_INFO *, char *ptr); 47 /* char *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 the current element. 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 /* LICENSE 110 /* .ad 111 /* .fi 112 /* The Secure Mailer license must be distributed with this software. 113 /* AUTHOR(S) 114 /* Wietse Venema 115 /* IBM T.J. Watson Research 116 /* P.O. Box 704 117 /* Yorktown Heights, NY 10598, USA 118 /*--*/ 119 120 /* C library */ 121 122 #include <sys_defs.h> 123 #include <string.h> 124 125 /* Local stuff */ 126 127 #include "mymalloc.h" 128 #include "msg.h" 129 #include "htable.h" 130 131 /* htable_hash - hash a string */ 132 133 static unsigned htable_hash(const char *s, unsigned size) 134 { 135 unsigned long h = 0; 136 unsigned long g; 137 138 /* 139 * From the "Dragon" book by Aho, Sethi and Ullman. 140 */ 141 142 while (*s) { 143 h = (h << 4U) + *s++; 144 if ((g = (h & 0xf0000000)) != 0) { 145 h ^= (g >> 24U); 146 h ^= g; 147 } 148 } 149 return (h % size); 150 } 151 152 /* htable_link - insert element into table */ 153 154 #define htable_link(table, element) { \ 155 HTABLE_INFO **_h = table->data + htable_hash(element->key, table->size);\ 156 element->prev = 0; \ 157 if ((element->next = *_h) != 0) \ 158 (*_h)->prev = element; \ 159 *_h = element; \ 160 table->used++; \ 161 } 162 163 /* htable_size - allocate and initialize hash table */ 164 165 static void htable_size(HTABLE *table, unsigned size) 166 { 167 HTABLE_INFO **h; 168 169 size |= 1; 170 171 table->data = h = (HTABLE_INFO **) mymalloc(size * sizeof(HTABLE_INFO *)); 172 table->size = size; 173 table->used = 0; 174 175 while (size-- > 0) 176 *h++ = 0; 177 } 178 179 /* htable_create - create initial hash table */ 180 181 HTABLE *htable_create(int size) 182 { 183 HTABLE *table; 184 185 table = (HTABLE *) mymalloc(sizeof(HTABLE)); 186 htable_size(table, size < 13 ? 13 : size); 187 table->seq_element = 0; 188 return (table); 189 } 190 191 /* htable_grow - extend existing table */ 192 193 static void htable_grow(HTABLE *table) 194 { 195 HTABLE_INFO *ht; 196 HTABLE_INFO *next; 197 unsigned old_size = table->size; 198 HTABLE_INFO **h = table->data; 199 HTABLE_INFO **old_entries = h; 200 201 htable_size(table, 2 * old_size); 202 203 while (old_size-- > 0) { 204 for (ht = *h++; ht; ht = next) { 205 next = ht->next; 206 htable_link(table, ht); 207 } 208 } 209 myfree((char *) old_entries); 210 } 211 212 /* htable_enter - enter (key, value) pair */ 213 214 HTABLE_INFO *htable_enter(HTABLE *table, const char *key, char *value) 215 { 216 HTABLE_INFO *ht; 217 218 if (table->used >= table->size && table->seq_element == 0) 219 htable_grow(table); 220 ht = (HTABLE_INFO *) mymalloc(sizeof(HTABLE_INFO)); 221 ht->key = mystrdup(key); 222 ht->value = value; 223 htable_link(table, ht); 224 return (ht); 225 } 226 227 /* htable_find - lookup value */ 228 229 char *htable_find(HTABLE *table, const char *key) 230 { 231 HTABLE_INFO *ht; 232 233 #define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0)) 234 235 if (table) 236 for (ht = table->data[htable_hash(key, table->size)]; ht; ht = ht->next) 237 if (STREQ(key, ht->key)) 238 return (ht->value); 239 return (0); 240 } 241 242 /* htable_locate - lookup entry */ 243 244 HTABLE_INFO *htable_locate(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); 254 return (0); 255 } 256 257 /* htable_delete - delete one entry */ 258 259 void htable_delete(HTABLE *table, const char *key, void (*free_fn) (char *)) 260 { 261 if (table) { 262 HTABLE_INFO *ht; 263 HTABLE_INFO **h = table->data + htable_hash(key, table->size); 264 265 #define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0)) 266 267 for (ht = *h; ht; ht = ht->next) { 268 if (STREQ(key, ht->key)) { 269 if (ht->next) 270 ht->next->prev = ht->prev; 271 if (ht->prev) 272 ht->prev->next = ht->next; 273 else 274 *h = ht->next; 275 table->used--; 276 myfree(ht->key); 277 if (free_fn && ht->value) 278 (*free_fn) (ht->value); 279 myfree((char *) ht); 280 return; 281 } 282 } 283 msg_panic("htable_delete: unknown_key: \"%s\"", key); 284 } 285 } 286 287 /* htable_free - destroy hash table */ 288 289 void htable_free(HTABLE *table, void (*free_fn) (char *)) 290 { 291 if (table) { 292 unsigned i = table->size; 293 HTABLE_INFO *ht; 294 HTABLE_INFO *next; 295 HTABLE_INFO **h = table->data; 296 297 while (i-- > 0) { 298 for (ht = *h++; ht; ht = next) { 299 next = ht->next; 300 myfree(ht->key); 301 if (free_fn && ht->value) 302 (*free_fn) (ht->value); 303 myfree((char *) ht); 304 } 305 } 306 myfree((char *) table->data); 307 table->data = 0; 308 myfree((char *) table); 309 } 310 } 311 312 /* htable_walk - iterate over hash table */ 313 314 void htable_walk(HTABLE *table, void (*action) (HTABLE_INFO *, char *), 315 char *ptr) { 316 if (table) { 317 unsigned i = table->size; 318 HTABLE_INFO **h = table->data; 319 HTABLE_INFO *ht; 320 321 while (i-- > 0) 322 for (ht = *h++; ht; ht = ht->next) 323 (*action) (ht, ptr); 324 } 325 } 326 327 /* htable_list - list all table members */ 328 329 HTABLE_INFO **htable_list(HTABLE *table) 330 { 331 HTABLE_INFO **list; 332 HTABLE_INFO *member; 333 int count = 0; 334 int i; 335 336 if (table != 0) { 337 list = (HTABLE_INFO **) mymalloc(sizeof(*list) * (table->used + 1)); 338 for (i = 0; i < table->size; i++) 339 for (member = table->data[i]; member != 0; member = member->next) 340 list[count++] = member; 341 } else { 342 list = (HTABLE_INFO **) mymalloc(sizeof(*list)); 343 } 344 list[count] = 0; 345 return (list); 346 } 347 348 /* htable_sequence - dict(3) compatibility iterator */ 349 350 HTABLE_INFO *htable_sequence(HTABLE *table, int how) 351 { 352 if (table == 0) 353 return (0); 354 355 switch (how) { 356 case HTABLE_SEQ_FIRST: /* start new sequence */ 357 table->seq_bucket = table->data; 358 table->seq_element = table->seq_bucket[0]; 359 break; 360 case HTABLE_SEQ_NEXT: /* next element */ 361 if (table->seq_element) { 362 table->seq_element = table->seq_element->next; 363 break; 364 } 365 /* FALLTHROUGH */ 366 default: /* terminate sequence */ 367 return (table->seq_element = 0); 368 } 369 370 while (table->seq_element == 0 371 && ++(table->seq_bucket) < table->data + table->size) 372 table->seq_element = table->seq_bucket[0]; 373 return (table->seq_element); 374 } 375 376 #ifdef TEST 377 #include <vstring_vstream.h> 378 #include <myrand.h> 379 380 int 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