1 /* $NetBSD: htable.c,v 1.4 2023/12/23 20:30:46 christos 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 /* void *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 /* void *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)(void *);
39 /*
40 /* void htable_free(table, free_fn)
41 /* HTABLE *table;
42 /* void (*free_fn)(void *);
43 /*
44 /* void htable_walk(table, action, ptr)
45 /* HTABLE *table;
46 /* void (*action)(HTABLE_INFO *, void *ptr);
47 /* void *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 an element before it is visited.
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 /* hash_fnv(3) Fowler/Noll/Vo hash function
110 /* LICENSE
111 /* .ad
112 /* .fi
113 /* The Secure Mailer license must be distributed with this software.
114 /* AUTHOR(S)
115 /* Wietse Venema
116 /* IBM T.J. Watson Research
117 /* P.O. Box 704
118 /* Yorktown Heights, NY 10598, USA
119 /*
120 /* Wietse Venema
121 /* Google, Inc.
122 /* 111 8th Avenue
123 /* New York, NY 10011, USA
124 /*--*/
125
126 /* C library */
127
128 #include <sys_defs.h>
129 #include <string.h>
130
131 /* Local stuff */
132
133 #include "mymalloc.h"
134 #include "msg.h"
135 #include "htable.h"
136
137 /* htable_hash - hash a string */
138
139 #ifndef NO_HASH_FNV
140 #include "hash_fnv.h"
141
142 #define htable_hash(s, size) (hash_fnvz(s) % (size))
143
144 #else
145
htable_hash(const char * s,size_t size)146 static size_t htable_hash(const char *s, size_t size)
147 {
148 size_t h = 0;
149 size_t g;
150
151 /*
152 * From the "Dragon" book by Aho, Sethi and Ullman.
153 */
154
155 while (*s) {
156 h = (h << 4U) + *(unsigned const char *) s++;
157 if ((g = (h & 0xf0000000)) != 0) {
158 h ^= (g >> 24U);
159 h ^= g;
160 }
161 }
162 return (h % size);
163 }
164
165 #endif
166
167 /* htable_link - insert element into table */
168
169 #define htable_link(table, element) { \
170 HTABLE_INFO **_h = table->data + htable_hash(element->key, table->size);\
171 element->prev = 0; \
172 if ((element->next = *_h) != 0) \
173 (*_h)->prev = element; \
174 *_h = element; \
175 table->used++; \
176 }
177
178 /* htable_size - allocate and initialize hash table */
179
htable_size(HTABLE * table,size_t size)180 static void htable_size(HTABLE *table, size_t size)
181 {
182 HTABLE_INFO **h;
183
184 size |= 1;
185
186 table->data = h = (HTABLE_INFO **) mymalloc(size * sizeof(HTABLE_INFO *));
187 table->size = size;
188 table->used = 0;
189
190 while (size-- > 0)
191 *h++ = 0;
192 }
193
194 /* htable_create - create initial hash table */
195
htable_create(ssize_t size)196 HTABLE *htable_create(ssize_t size)
197 {
198 HTABLE *table;
199
200 table = (HTABLE *) mymalloc(sizeof(HTABLE));
201 htable_size(table, size < 13 ? 13 : size);
202 table->seq_bucket = table->seq_element = 0;
203 return (table);
204 }
205
206 /* htable_grow - extend existing table */
207
htable_grow(HTABLE * table)208 static void htable_grow(HTABLE *table)
209 {
210 HTABLE_INFO *ht;
211 HTABLE_INFO *next;
212 size_t old_size = table->size;
213 HTABLE_INFO **h = table->data;
214 HTABLE_INFO **old_entries = h;
215
216 htable_size(table, 2 * old_size);
217
218 while (old_size-- > 0) {
219 for (ht = *h++; ht; ht = next) {
220 next = ht->next;
221 htable_link(table, ht);
222 }
223 }
224 myfree((void *) old_entries);
225 }
226
227 /* htable_enter - enter (key, value) pair */
228
htable_enter(HTABLE * table,const char * key,void * value)229 HTABLE_INFO *htable_enter(HTABLE *table, const char *key, void *value)
230 {
231 HTABLE_INFO *ht;
232
233 if (table->used >= table->size)
234 htable_grow(table);
235 ht = (HTABLE_INFO *) mymalloc(sizeof(HTABLE_INFO));
236 ht->key = mystrdup(key);
237 ht->value = value;
238 htable_link(table, ht);
239 return (ht);
240 }
241
242 /* htable_find - lookup value */
243
htable_find(HTABLE * table,const char * key)244 void *htable_find(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->value);
254 return (0);
255 }
256
257 /* htable_locate - lookup entry */
258
htable_locate(HTABLE * table,const char * key)259 HTABLE_INFO *htable_locate(HTABLE *table, const char *key)
260 {
261 HTABLE_INFO *ht;
262
263 #define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
264
265 if (table)
266 for (ht = table->data[htable_hash(key, table->size)]; ht; ht = ht->next)
267 if (STREQ(key, ht->key))
268 return (ht);
269 return (0);
270 }
271
272 /* htable_delete - delete one entry */
273
htable_delete(HTABLE * table,const char * key,void (* free_fn)(void *))274 void htable_delete(HTABLE *table, const char *key, void (*free_fn) (void *))
275 {
276 if (table) {
277 HTABLE_INFO *ht;
278 HTABLE_INFO **h = table->data + htable_hash(key, table->size);
279
280 #define STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
281
282 for (ht = *h; ht; ht = ht->next) {
283 if (STREQ(key, ht->key)) {
284 if (ht->next)
285 ht->next->prev = ht->prev;
286 if (ht->prev)
287 ht->prev->next = ht->next;
288 else
289 *h = ht->next;
290 table->used--;
291 myfree(ht->key);
292 if (free_fn && ht->value)
293 (*free_fn) (ht->value);
294 myfree((void *) ht);
295 return;
296 }
297 }
298 msg_panic("htable_delete: unknown_key: \"%s\"", key);
299 }
300 }
301
302 /* htable_free - destroy hash table */
303
htable_free(HTABLE * table,void (* free_fn)(void *))304 void htable_free(HTABLE *table, void (*free_fn) (void *))
305 {
306 if (table) {
307 ssize_t i = table->size;
308 HTABLE_INFO *ht;
309 HTABLE_INFO *next;
310 HTABLE_INFO **h = table->data;
311
312 while (i-- > 0) {
313 for (ht = *h++; ht; ht = next) {
314 next = ht->next;
315 myfree(ht->key);
316 if (free_fn && ht->value)
317 (*free_fn) (ht->value);
318 myfree((void *) ht);
319 }
320 }
321 myfree((void *) table->data);
322 table->data = 0;
323 if (table->seq_bucket)
324 myfree((void *) table->seq_bucket);
325 table->seq_bucket = 0;
326 myfree((void *) table);
327 }
328 }
329
330 /* htable_walk - iterate over hash table */
331
htable_walk(HTABLE * table,void (* action)(HTABLE_INFO *,void *),void * ptr)332 void htable_walk(HTABLE *table, void (*action) (HTABLE_INFO *, void *),
333 void *ptr) {
334 if (table) {
335 ssize_t i = table->size;
336 HTABLE_INFO **h = table->data;
337 HTABLE_INFO *ht;
338
339 while (i-- > 0)
340 for (ht = *h++; ht; ht = ht->next)
341 (*action) (ht, ptr);
342 }
343 }
344
345 /* htable_list - list all table members */
346
htable_list(HTABLE * table)347 HTABLE_INFO **htable_list(HTABLE *table)
348 {
349 HTABLE_INFO **list;
350 HTABLE_INFO *member;
351 ssize_t count = 0;
352 ssize_t i;
353
354 if (table != 0) {
355 list = (HTABLE_INFO **) mymalloc(sizeof(*list) * (table->used + 1));
356 for (i = 0; i < table->size; i++)
357 for (member = table->data[i]; member != 0; member = member->next)
358 list[count++] = member;
359 } else {
360 list = (HTABLE_INFO **) mymalloc(sizeof(*list));
361 }
362 list[count] = 0;
363 return (list);
364 }
365
366 /* htable_sequence - dict(3) compatibility iterator */
367
htable_sequence(HTABLE * table,int how)368 HTABLE_INFO *htable_sequence(HTABLE *table, int how)
369 {
370 if (table == 0)
371 return (0);
372
373 switch (how) {
374 case HTABLE_SEQ_FIRST: /* start new sequence */
375 if (table->seq_bucket)
376 myfree((void *) table->seq_bucket);
377 table->seq_bucket = htable_list(table);
378 table->seq_element = table->seq_bucket;
379 return (*(table->seq_element)++);
380 case HTABLE_SEQ_NEXT: /* next element */
381 if (table->seq_element && *table->seq_element)
382 return (*(table->seq_element)++);
383 /* FALLTHROUGH */
384 default: /* terminate sequence */
385 if (table->seq_bucket) {
386 myfree((void *) table->seq_bucket);
387 table->seq_bucket = table->seq_element = 0;
388 }
389 return (0);
390 }
391 }
392
393 #ifdef TEST
394 #include <vstring_vstream.h>
395 #include <myrand.h>
396
main(int unused_argc,char ** unused_argv)397 int main(int unused_argc, char **unused_argv)
398 {
399 VSTRING *buf = vstring_alloc(10);
400 ssize_t count = 0;
401 HTABLE *hash;
402 HTABLE_INFO **ht_info;
403 HTABLE_INFO **ht;
404 HTABLE_INFO *info;
405 ssize_t i;
406 ssize_t r;
407 int op;
408
409 /*
410 * Load a large number of strings and delete them in a random order.
411 */
412 hash = htable_create(10);
413 while (vstring_get(buf, VSTREAM_IN) != VSTREAM_EOF)
414 htable_enter(hash, vstring_str(buf), CAST_INT_TO_VOID_PTR(count++));
415 if (count != hash->used)
416 msg_panic("%ld entries stored, but %lu entries exist",
417 (long) count, (unsigned long) hash->used);
418 for (i = 0, op = HTABLE_SEQ_FIRST; htable_sequence(hash, op) != 0;
419 i++, op = HTABLE_SEQ_NEXT)
420 /* void */ ;
421 if (i != hash->used)
422 msg_panic("%ld entries found, but %lu entries exist",
423 (long) i, (unsigned long) hash->used);
424 ht_info = htable_list(hash);
425 for (i = 0; i < hash->used; i++) {
426 r = myrand() % hash->used;
427 info = ht_info[i];
428 ht_info[i] = ht_info[r];
429 ht_info[r] = info;
430 }
431 for (ht = ht_info; *ht; ht++)
432 htable_delete(hash, ht[0]->key, (void (*) (void *)) 0);
433 if (hash->used > 0)
434 msg_panic("%ld entries not deleted", (long) hash->used);
435 myfree((void *) ht_info);
436 htable_free(hash, (void (*) (void *)) 0);
437 vstring_free(buf);
438 return (0);
439 }
440
441 #endif
442