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