xref: /netbsd-src/external/ibm-public/postfix/dist/src/util/htable.c (revision c48c605c14fd8622b523d1d6a3f0c0bad133ea89)
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