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 /* void *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 /* void *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)(void *);
37 /*
38 /* void htable_free(table, free_fn)
39 /* HTABLE *table;
40 /* void (*free_fn)(void *);
41 /*
42 /* void htable_walk(table, action, ptr)
43 /* HTABLE *table;
44 /* void (*action)(HTABLE_INFO *, void *ptr);
45 /* void *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
htable_hash(const char * s,size_t size)131 static size_t htable_hash(const char *s, size_t size)
132 {
133 size_t h = 0;
134 size_t 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
htable_size(HTABLE * table,size_t size)163 static void htable_size(HTABLE *table, size_t 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
htable_create(ssize_t size)179 HTABLE *htable_create(ssize_t 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
htable_grow(HTABLE * table)191 static void htable_grow(HTABLE *table)
192 {
193 HTABLE_INFO *ht;
194 HTABLE_INFO *next;
195 size_t 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((void *) old_entries);
208 }
209
210 /* htable_enter - enter (key, value) pair */
211
htable_enter(HTABLE * table,const char * key,void * value)212 HTABLE_INFO *htable_enter(HTABLE *table, const char *key, void *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
htable_find(HTABLE * table,const char * key)227 void *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
htable_locate(HTABLE * table,const char * key)242 HTABLE_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
htable_delete(HTABLE * table,const char * key,void (* free_fn)(void *))257 void htable_delete(HTABLE *table, const char *key, void (*free_fn) (void *))
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((void *) ht);
278 return;
279 }
280 }
281 msg_panic("htable_delete: unknown_key: \"%s\"", key);
282 }
283 }
284
285 /* htable_free - destroy hash table */
286
htable_free(HTABLE * table,void (* free_fn)(void *))287 void htable_free(HTABLE *table, void (*free_fn) (void *))
288 {
289 if (table) {
290 ssize_t 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((void *) ht);
302 }
303 }
304 myfree((void *) table->data);
305 table->data = 0;
306 if (table->seq_bucket)
307 myfree((void *) table->seq_bucket);
308 table->seq_bucket = 0;
309 myfree((void *) table);
310 }
311 }
312
313 /* htable_walk - iterate over hash table */
314
htable_walk(HTABLE * table,void (* action)(HTABLE_INFO *,void *),void * ptr)315 void htable_walk(HTABLE *table, void (*action) (HTABLE_INFO *, void *),
316 void *ptr) {
317 if (table) {
318 ssize_t 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
htable_list(HTABLE * table)330 HTABLE_INFO **htable_list(HTABLE *table)
331 {
332 HTABLE_INFO **list;
333 HTABLE_INFO *member;
334 ssize_t count = 0;
335 ssize_t 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
htable_sequence(HTABLE * table,int how)351 HTABLE_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((void *) 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((void *) 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
main(int unused_argc,char ** unused_argv)380 int main(int unused_argc, char **unused_argv)
381 {
382 VSTRING *buf = vstring_alloc(10);
383 ssize_t count = 0;
384 HTABLE *hash;
385 HTABLE_INFO **ht_info;
386 HTABLE_INFO **ht;
387 HTABLE_INFO *info;
388 ssize_t i;
389 ssize_t 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_VOID_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("%ld entries found, but %lu entries exist",
403 (long) i, (unsigned long) hash->used);
404 ht_info = htable_list(hash);
405 for (i = 0; i < hash->used; i++) {
406 r = myrand() % hash->used;
407 info = ht_info[i];
408 ht_info[i] = ht_info[r];
409 ht_info[r] = info;
410 }
411 for (ht = ht_info; *ht; ht++)
412 htable_delete(hash, ht[0]->key, (void (*) (void *)) 0);
413 if (hash->used > 0)
414 msg_panic("%ld entries not deleted", (long) hash->used);
415 myfree((void *) ht_info);
416 htable_free(hash, (void (*) (void *)) 0);
417 vstring_free(buf);
418 return (0);
419 }
420
421 #endif
422