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