1 /*++
2 /* NAME
3 /* binhash 3
4 /* SUMMARY
5 /* hash table manager
6 /* SYNOPSIS
7 /* #include <binhash.h>
8 /*
9 /* typedef struct {
10 /* .in +4
11 /* void *key;
12 /* ssize_t key_len;
13 /* void *value;
14 /* /* private fields... */
15 /* .in -4
16 /* } BINHASH_INFO;
17 /*
18 /* BINHASH *binhash_create(size)
19 /* ssize_t size;
20 /*
21 /* BINHASH_INFO *binhash_enter(table, key, key_len, value)
22 /* BINHASH *table;
23 /* const void *key;
24 /* ssize_t key_len;
25 /* void *value;
26 /*
27 /* char *binhash_find(table, key, key_len)
28 /* BINHASH *table;
29 /* const void *key;
30 /* ssize_t key_len;
31 /*
32 /* BINHASH_INFO *binhash_locate(table, key, key_len)
33 /* BINHASH *table;
34 /* const void *key;
35 /* ssize_t key_len;
36 /*
37 /* void binhash_delete(table, key, key_len, free_fn)
38 /* BINHASH *table;
39 /* const void *key;
40 /* ssize_t key_len;
41 /* void (*free_fn)(void *);
42 /*
43 /* void binhash_free(table, free_fn)
44 /* BINHASH *table;
45 /* void (*free_fn)(void *);
46 /*
47 /* void binhash_walk(table, action, ptr)
48 /* BINHASH *table;
49 /* void (*action)(BINHASH_INFO *info, void *ptr);
50 /* void *ptr;
51 /*
52 /* BINHASH_INFO **binhash_list(table)
53 /* BINHASH *table;
54 /* DESCRIPTION
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.
61 /*
62 /* binhash_create() creates a table of the specified size and returns a
63 /* pointer to the result. The lookup keys are saved with mymemdup().
64 /*
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.
69 /*
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().
73 /*
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.
76 /*
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
80 /* the key.
81 /*
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
85 /* with the entry.
86 /*
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.
90 /*
91 /* binhash_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 /* RESTRICTIONS
95 /* A callback function should not modify the hash table that is
96 /* specified to its caller.
97 /* DIAGNOSTICS
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.
101 /* SEE ALSO
102 /* mymalloc(3) memory management wrapper
103 /* LICENSE
104 /* .ad
105 /* .fi
106 /* The Secure Mailer license must be distributed with this software.
107 /* AUTHOR(S)
108 /* Wietse Venema
109 /* IBM T.J. Watson Research
110 /* P.O. Box 704
111 /* Yorktown Heights, NY 10598, USA
112 /*--*/
113
114 /* C library */
115
116 #include <sys_defs.h>
117 #include <string.h>
118
119 /* Local stuff */
120
121 #include "mymalloc.h"
122 #include "msg.h"
123 #include "binhash.h"
124
125 /* binhash_hash - hash a string */
126
binhash_hash(const void * key,ssize_t len,size_t size)127 static size_t binhash_hash(const void *key, ssize_t len, size_t size)
128 {
129 size_t h = 0;
130 size_t g;
131
132 /*
133 * From the "Dragon" book by Aho, Sethi and Ullman.
134 */
135
136 while (len-- > 0) {
137 h = (h << 4U) + *(unsigned const char *) key++;
138 if ((g = (h & 0xf0000000)) != 0) {
139 h ^= (g >> 24U);
140 h ^= g;
141 }
142 }
143 return (h % size);
144 }
145
146 /* binhash_link - insert element into table */
147
148 #define binhash_link(table, elm) { \
149 BINHASH_INFO **_h = table->data + binhash_hash(elm->key, elm->key_len, table->size);\
150 elm->prev = 0; \
151 if ((elm->next = *_h) != 0) \
152 (*_h)->prev = elm; \
153 *_h = elm; \
154 table->used++; \
155 }
156
157 /* binhash_size - allocate and initialize hash table */
158
binhash_size(BINHASH * table,size_t size)159 static void binhash_size(BINHASH *table, size_t size)
160 {
161 BINHASH_INFO **h;
162
163 size |= 1;
164
165 table->data = h = (BINHASH_INFO **) mymalloc(size * sizeof(BINHASH_INFO *));
166 table->size = size;
167 table->used = 0;
168
169 while (size-- > 0)
170 *h++ = 0;
171 }
172
173 /* binhash_create - create initial hash table */
174
binhash_create(ssize_t size)175 BINHASH *binhash_create(ssize_t size)
176 {
177 BINHASH *table;
178
179 table = (BINHASH *) mymalloc(sizeof(BINHASH));
180 binhash_size(table, size < 13 ? 13 : size);
181 return (table);
182 }
183
184 /* binhash_grow - extend existing table */
185
binhash_grow(BINHASH * table)186 static void binhash_grow(BINHASH *table)
187 {
188 BINHASH_INFO *ht;
189 BINHASH_INFO *next;
190 ssize_t old_size = table->size;
191 BINHASH_INFO **h = table->data;
192 BINHASH_INFO **old_entries = h;
193
194 binhash_size(table, 2 * old_size);
195
196 while (old_size-- > 0) {
197 for (ht = *h++; ht; ht = next) {
198 next = ht->next;
199 binhash_link(table, ht);
200 }
201 }
202 myfree((void *) old_entries);
203 }
204
205 /* binhash_enter - enter (key, value) pair */
206
binhash_enter(BINHASH * table,const void * key,ssize_t key_len,void * value)207 BINHASH_INFO *binhash_enter(BINHASH *table, const void *key, ssize_t key_len, void *value)
208 {
209 BINHASH_INFO *ht;
210
211 if (table->used >= table->size)
212 binhash_grow(table);
213 ht = (BINHASH_INFO *) mymalloc(sizeof(BINHASH_INFO));
214 ht->key = mymemdup(key, key_len);
215 ht->key_len = key_len;
216 ht->value = value;
217 binhash_link(table, ht);
218 return (ht);
219 }
220
221 /* binhash_find - lookup value */
222
binhash_find(BINHASH * table,const void * key,ssize_t key_len)223 void *binhash_find(BINHASH *table, const void *key, ssize_t key_len)
224 {
225 BINHASH_INFO *ht;
226
227 #define KEY_EQ(x,y,l) (((unsigned char *) x)[0] == ((unsigned char *) y)[0] && memcmp(x,y,l) == 0)
228
229 if (table != 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))
232 return (ht->value);
233 return (0);
234 }
235
236 /* binhash_locate - lookup entry */
237
binhash_locate(BINHASH * table,const void * key,ssize_t key_len)238 BINHASH_INFO *binhash_locate(BINHASH *table, const void *key, ssize_t key_len)
239 {
240 BINHASH_INFO *ht;
241
242 if (table != 0)
243 for (ht = table->data[binhash_hash(key, key_len, table->size)]; ht; ht = ht->next)
244 if (key_len == ht->key_len && KEY_EQ(key, ht->key, key_len))
245 return (ht);
246 return (0);
247 }
248
249 /* binhash_delete - delete one entry */
250
binhash_delete(BINHASH * table,const void * key,ssize_t key_len,void (* free_fn)(void *))251 void binhash_delete(BINHASH *table, const void *key, ssize_t key_len, void (*free_fn) (void *))
252 {
253 if (table != 0) {
254 BINHASH_INFO *ht;
255 BINHASH_INFO **h = table->data + binhash_hash(key, key_len, table->size);
256
257 for (ht = *h; ht; ht = ht->next) {
258 if (key_len == ht->key_len && KEY_EQ(key, ht->key, key_len)) {
259 if (ht->next)
260 ht->next->prev = ht->prev;
261 if (ht->prev)
262 ht->prev->next = ht->next;
263 else
264 *h = ht->next;
265 table->used--;
266 myfree(ht->key);
267 if (free_fn)
268 (*free_fn) (ht->value);
269 myfree((void *) ht);
270 return;
271 }
272 }
273 msg_panic("binhash_delete: unknown_key: \"%s\"", (char *) key);
274 }
275 }
276
277 /* binhash_free - destroy hash table */
278
binhash_free(BINHASH * table,void (* free_fn)(void *))279 void binhash_free(BINHASH *table, void (*free_fn) (void *))
280 {
281 if (table != 0) {
282 ssize_t i = table->size;
283 BINHASH_INFO *ht;
284 BINHASH_INFO *next;
285 BINHASH_INFO **h = table->data;
286
287 while (i-- > 0) {
288 for (ht = *h++; ht; ht = next) {
289 next = ht->next;
290 myfree(ht->key);
291 if (free_fn)
292 (*free_fn) (ht->value);
293 myfree((void *) ht);
294 }
295 }
296 myfree((void *) table->data);
297 table->data = 0;
298 myfree((void *) table);
299 }
300 }
301
302 /* binhash_walk - iterate over hash table */
303
binhash_walk(BINHASH * table,void (* action)(BINHASH_INFO *,void *),void * ptr)304 void binhash_walk(BINHASH *table, void (*action) (BINHASH_INFO *, void *),
305 void *ptr) {
306 if (table != 0) {
307 ssize_t i = table->size;
308 BINHASH_INFO **h = table->data;
309 BINHASH_INFO *ht;
310
311 while (i-- > 0)
312 for (ht = *h++; ht; ht = ht->next)
313 (*action) (ht, ptr);
314 }
315 }
316
317 /* binhash_list - list all table members */
318
binhash_list(table)319 BINHASH_INFO **binhash_list(table)
320 BINHASH *table;
321 {
322 BINHASH_INFO **list;
323 BINHASH_INFO *member;
324 ssize_t count = 0;
325 ssize_t i;
326
327 if (table != 0) {
328 list = (BINHASH_INFO **) mymalloc(sizeof(*list) * (table->used + 1));
329 for (i = 0; i < table->size; i++)
330 for (member = table->data[i]; member != 0; member = member->next)
331 list[count++] = member;
332 } else {
333 list = (BINHASH_INFO **) mymalloc(sizeof(*list));
334 }
335 list[count] = 0;
336 return (list);
337 }
338