7
/* #include <binhash.h>
14
/* /* private fields... */
18
/* BINHASH *binhash_create(size)
21
/* BINHASH_INFO *binhash_enter(table, key, key_len, value)
27
/* char *binhash_find(table, key, key_len)
32
/* BINHASH_INFO *binhash_locate(table, key, key_len)
37
/* void binhash_delete(table, key, key_len, free_fn)
41
/* void (*free_fn)(char *);
43
/* void binhash_free(table, free_fn)
45
/* void (*free_fn)(char *);
47
/* void binhash_walk(table, action, ptr)
49
/* void (*action)(BINHASH_INFO *info, char *ptr);
52
/* BINHASH_INFO **binhash_list(table)
55
/* This module maintains one or more hash tables. Each table entry
56
/* consists of a unique binary-valued lookup key and a generic
57
/* character-pointer value.
58
/* The tables are automatically resized when they fill up. When the
59
/* values to be remembered are not character pointers, proper casts
60
/* should be used or the code will not be portable.
62
/* binhash_create() creates a table of the specified size and returns a
63
/* pointer to the result. The lookup keys are saved with strdup().
65
/* binhash_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 binhash_locate()
68
/* for updating an existing entry. The key is copied; the value is not.
70
/* binhash_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 binhash_locate().
74
/* binhash_locate() returns a pointer to the entry that was stored
75
/* for the given key, or a null pointer if it was not found.
77
/* binhash_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 value that was stored under
82
/* binhash_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 value that was stored
87
/* binhash_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.
91
/* binhash_list() returns a null-terminated list of pointers to
92
/* all elements in the named table. The list should be passed to
95
/* A callback function should not modify the hash table that is
96
/* specified to its caller.
98
/* The following conditions are reported and cause the program to
99
/* terminate immediately: memory allocation failure; an attempt
100
/* to delete a non-existent entry.
102
/* mymalloc(3) memory management wrapper
106
/* The Secure Mailer license must be distributed with this software.
109
/* IBM T.J. Watson Research
111
/* Yorktown Heights, NY 10598, USA
116
#include <sys_defs.h>
121
#include "mymalloc.h"
125
/* binhash_hash - hash a string */
127
static unsigned binhash_hash(const char *key, int len, unsigned size)
133
* From the "Dragon" book by Aho, Sethi and Ullman.
137
h = (h << 4) + *key++;
138
if ((g = (h & 0xf0000000)) != 0) {
146
/* binhash_link - insert element into table */
148
#define binhash_link(table, elm) { \
149
BINHASH_INFO **h = table->data + binhash_hash(elm->key, elm->key_len, table->size);\
151
if ((elm->next = *h) != 0) \
157
/* binhash_size - allocate and initialize hash table */
159
static void binhash_size(BINHASH *table, unsigned size)
165
table->data = h = (BINHASH_INFO **) mymalloc(size * sizeof(BINHASH_INFO *));
173
/* binhash_create - create initial hash table */
175
BINHASH *binhash_create(int size)
179
table = (BINHASH *) mymalloc(sizeof(BINHASH));
180
binhash_size(table, size < 13 ? 13 : size);
184
/* binhash_grow - extend existing table */
186
static void binhash_grow(BINHASH *table)
190
unsigned old_size = table->size;
191
BINHASH_INFO **h = table->data;
192
BINHASH_INFO **old_entries = h;
194
binhash_size(table, 2 * old_size);
196
while (old_size-- > 0) {
197
for (ht = *h++; ht; ht = next) {
199
binhash_link(table, ht);
202
myfree((char *) old_entries);
205
/* binhash_enter - enter (key, value) pair */
207
BINHASH_INFO *binhash_enter(BINHASH *table, const char *key, int key_len, char *value)
211
if (table->used >= table->size)
213
ht = (BINHASH_INFO *) mymalloc(sizeof(BINHASH_INFO));
214
ht->key = mymemdup(key, key_len);
215
ht->key_len = key_len;
217
binhash_link(table, ht);
221
/* binhash_find - lookup value */
223
char *binhash_find(BINHASH *table, const char *key, int key_len)
227
#define KEY_EQ(x,y,l) (x[0] == y[0] && memcmp(x,y,l) == 0)
230
for (ht = table->data[binhash_hash(key, key_len, table->size)]; ht; ht = ht->next)
231
if (key_len == ht->key_len && KEY_EQ(key, ht->key, key_len))
236
/* binhash_locate - lookup entry */
238
BINHASH_INFO *binhash_locate(BINHASH *table, const char *key, int key_len)
242
#define KEY_EQ(x,y,l) (x[0] == y[0] && memcmp(x,y,l) == 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))
251
/* binhash_delete - delete one entry */
253
void binhash_delete(BINHASH *table, const char *key, int key_len, void (*free_fn) (char *))
257
BINHASH_INFO **h = table->data + binhash_hash(key, key_len, table->size);
259
#define KEY_EQ(x,y,l) (x[0] == y[0] && memcmp(x,y,l) == 0)
261
for (ht = *h; ht; ht = ht->next) {
262
if (key_len == ht->key_len && KEY_EQ(key, ht->key, key_len)) {
264
ht->next->prev = ht->prev;
266
ht->prev->next = ht->next;
272
(*free_fn) (ht->value);
277
msg_panic("binhash_delete: unknown_key: \"%s\"", key);
281
/* binhash_free - destroy hash table */
283
void binhash_free(BINHASH *table, void (*free_fn) (char *))
286
unsigned i = table->size;
289
BINHASH_INFO **h = table->data;
292
for (ht = *h++; ht; ht = next) {
296
(*free_fn) (ht->value);
300
myfree((char *) table->data);
302
myfree((char *) table);
306
/* binhash_walk - iterate over hash table */
308
void binhash_walk(BINHASH *table, void (*action) (BINHASH_INFO *, char *),
311
unsigned i = table->size;
312
BINHASH_INFO **h = table->data;
316
for (ht = *h++; ht; ht = ht->next)
321
/* binhash_list - list all table members */
323
BINHASH_INFO **binhash_list(table)
327
BINHASH_INFO *member;
332
list = (BINHASH_INFO **) mymalloc(sizeof(*list) * (table->used + 1));
333
for (i = 0; i < table->size; i++)
334
for (member = table->data[i]; member != 0; member = member->next)
335
list[count++] = member;
337
list = (BINHASH_INFO **) mymalloc(sizeof(*list));
added
removed
src/util/binhash.c
