1/* $NetBSD$ */ 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/* char *key; 14/* int key_len; 15/* char *value; 16/* /* private fields... */ 17/* .in -4 18/* } BINHASH_INFO; 19/* 20/* BINHASH *binhash_create(size) 21/* int size; 22/* 23/* BINHASH_INFO *binhash_enter(table, key, key_len, value) 24/* BINHASH *table; 25/* const char *key; 26/* int key_len; 27/* char *value; 28/* 29/* char *binhash_find(table, key, key_len) 30/* BINHASH *table; 31/* const char *key; 32/* int key_len; 33/* 34/* BINHASH_INFO *binhash_locate(table, key, key_len) 35/* BINHASH *table; 36/* const char *key; 37/* int key_len; 38/* 39/* void binhash_delete(table, key, key_len, free_fn) 40/* BINHASH *table; 41/* const char *key; 42/* int key_len; 43/* void (*free_fn)(char *); 44/* 45/* void binhash_free(table, free_fn) 46/* BINHASH *table; 47/* void (*free_fn)(char *); 48/* 49/* void binhash_walk(table, action, ptr) 50/* BINHASH *table; 51/* void (*action)(BINHASH_INFO *info, char *ptr); 52/* char *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 strdup(). 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 129static unsigned binhash_hash(const char *key, int len, unsigned size) 130{ 131 unsigned long h = 0; 132 unsigned long g; 133 134 /* 135 * From the "Dragon" book by Aho, Sethi and Ullman. 136 */ 137 138 while (len-- > 0) { 139 h = (h << 4U) + *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 161static void binhash_size(BINHASH *table, unsigned 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 177BINHASH *binhash_create(int 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 188static void binhash_grow(BINHASH *table) 189{ 190 BINHASH_INFO *ht; 191 BINHASH_INFO *next; 192 unsigned 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((char *) old_entries); 205} 206 207/* binhash_enter - enter (key, value) pair */ 208 209BINHASH_INFO *binhash_enter(BINHASH *table, const char *key, int key_len, char *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 225char *binhash_find(BINHASH *table, const char *key, int key_len) 226{ 227 BINHASH_INFO *ht; 228 229#define KEY_EQ(x,y,l) (x[0] == 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 240BINHASH_INFO *binhash_locate(BINHASH *table, const char *key, int key_len) 241{ 242 BINHASH_INFO *ht; 243 244#define KEY_EQ(x,y,l) (x[0] == y[0] && memcmp(x,y,l) == 0) 245 246 if (table != 0) 247 for (ht = table->data[binhash_hash(key, key_len, table->size)]; ht; ht = ht->next) 248 if (key_len == ht->key_len && KEY_EQ(key, ht->key, key_len)) 249 return (ht); 250 return (0); 251} 252 253/* binhash_delete - delete one entry */ 254 255void binhash_delete(BINHASH *table, const char *key, int key_len, void (*free_fn) (char *)) 256{ 257 if (table != 0) { 258 BINHASH_INFO *ht; 259 BINHASH_INFO **h = table->data + binhash_hash(key, key_len, table->size); 260 261#define KEY_EQ(x,y,l) (x[0] == y[0] && memcmp(x,y,l) == 0) 262 263 for (ht = *h; ht; ht = ht->next) { 264 if (key_len == ht->key_len && KEY_EQ(key, ht->key, key_len)) { 265 if (ht->next) 266 ht->next->prev = ht->prev; 267 if (ht->prev) 268 ht->prev->next = ht->next; 269 else 270 *h = ht->next; 271 table->used--; 272 myfree(ht->key); 273 if (free_fn) 274 (*free_fn) (ht->value); 275 myfree((char *) ht); 276 return; 277 } 278 } 279 msg_panic("binhash_delete: unknown_key: \"%s\"", key); 280 } 281} 282 283/* binhash_free - destroy hash table */ 284 285void binhash_free(BINHASH *table, void (*free_fn) (char *)) 286{ 287 if (table != 0) { 288 unsigned i = table->size; 289 BINHASH_INFO *ht; 290 BINHASH_INFO *next; 291 BINHASH_INFO **h = table->data; 292 293 while (i-- > 0) { 294 for (ht = *h++; ht; ht = next) { 295 next = ht->next; 296 myfree(ht->key); 297 if (free_fn) 298 (*free_fn) (ht->value); 299 myfree((char *) ht); 300 } 301 } 302 myfree((char *) table->data); 303 table->data = 0; 304 myfree((char *) table); 305 } 306} 307 308/* binhash_walk - iterate over hash table */ 309 310void binhash_walk(BINHASH *table, void (*action) (BINHASH_INFO *, char *), 311 char *ptr) { 312 if (table != 0) { 313 unsigned i = table->size; 314 BINHASH_INFO **h = table->data; 315 BINHASH_INFO *ht; 316 317 while (i-- > 0) 318 for (ht = *h++; ht; ht = ht->next) 319 (*action) (ht, ptr); 320 } 321} 322 323/* binhash_list - list all table members */ 324 325BINHASH_INFO **binhash_list(table) 326BINHASH *table; 327{ 328 BINHASH_INFO **list; 329 BINHASH_INFO *member; 330 int count = 0; 331 int i; 332 333 if (table != 0) { 334 list = (BINHASH_INFO **) mymalloc(sizeof(*list) * (table->used + 1)); 335 for (i = 0; i < table->size; i++) 336 for (member = table->data[i]; member != 0; member = member->next) 337 list[count++] = member; 338 } else { 339 list = (BINHASH_INFO **) mymalloc(sizeof(*list)); 340 } 341 list[count] = 0; 342 return (list); 343} 344