1 /*	$NetBSD: htable.c,v 1.1.1.2 2010/06/17 18:07:14 tron 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 /*		char	*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 /*	char	*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)(char *);
39 /*
40 /*	void	htable_free(table, free_fn)
41 /*	HTABLE	*table;
42 /*	void	(*free_fn)(char *);
43 /*
44 /*	void	htable_walk(table, action, ptr)
45 /*	HTABLE	*table;
46 /*	void	(*action)(HTABLE_INFO *, char *ptr);
47 /*	char	*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 the current element.
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 /* LICENSE
110 /* .ad
111 /* .fi
112 /*	The Secure Mailer license must be distributed with this software.
113 /* AUTHOR(S)
114 /*	Wietse Venema
115 /*	IBM T.J. Watson Research
116 /*	P.O. Box 704
117 /*	Yorktown Heights, NY 10598, USA
118 /*--*/
119 
120 /* C library */
121 
122 #include <sys_defs.h>
123 #include <string.h>
124 
125 /* Local stuff */
126 
127 #include "mymalloc.h"
128 #include "msg.h"
129 #include "htable.h"
130 
131 /* htable_hash - hash a string */
132 
133 static unsigned htable_hash(const char *s, unsigned size)
134 {
135     unsigned long h = 0;
136     unsigned long g;
137 
138     /*
139      * From the "Dragon" book by Aho, Sethi and Ullman.
140      */
141 
142     while (*s) {
143 	h = (h << 4U) + *s++;
144 	if ((g = (h & 0xf0000000)) != 0) {
145 	    h ^= (g >> 24U);
146 	    h ^= g;
147 	}
148     }
149     return (h % size);
150 }
151 
152 /* htable_link - insert element into table */
153 
154 #define htable_link(table, element) { \
155      HTABLE_INFO **_h = table->data + htable_hash(element->key, table->size);\
156     element->prev = 0; \
157     if ((element->next = *_h) != 0) \
158 	(*_h)->prev = element; \
159     *_h = element; \
160     table->used++; \
161 }
162 
163 /* htable_size - allocate and initialize hash table */
164 
165 static void htable_size(HTABLE *table, unsigned size)
166 {
167     HTABLE_INFO **h;
168 
169     size |= 1;
170 
171     table->data = h = (HTABLE_INFO **) mymalloc(size * sizeof(HTABLE_INFO *));
172     table->size = size;
173     table->used = 0;
174 
175     while (size-- > 0)
176 	*h++ = 0;
177 }
178 
179 /* htable_create - create initial hash table */
180 
181 HTABLE *htable_create(int size)
182 {
183     HTABLE *table;
184 
185     table = (HTABLE *) mymalloc(sizeof(HTABLE));
186     htable_size(table, size < 13 ? 13 : size);
187     table->seq_element = 0;
188     return (table);
189 }
190 
191 /* htable_grow - extend existing table */
192 
193 static void htable_grow(HTABLE *table)
194 {
195     HTABLE_INFO *ht;
196     HTABLE_INFO *next;
197     unsigned old_size = table->size;
198     HTABLE_INFO **h = table->data;
199     HTABLE_INFO **old_entries = h;
200 
201     htable_size(table, 2 * old_size);
202 
203     while (old_size-- > 0) {
204 	for (ht = *h++; ht; ht = next) {
205 	    next = ht->next;
206 	    htable_link(table, ht);
207 	}
208     }
209     myfree((char *) old_entries);
210 }
211 
212 /* htable_enter - enter (key, value) pair */
213 
214 HTABLE_INFO *htable_enter(HTABLE *table, const char *key, char *value)
215 {
216     HTABLE_INFO *ht;
217 
218     if (table->used >= table->size && table->seq_element == 0)
219 	htable_grow(table);
220     ht = (HTABLE_INFO *) mymalloc(sizeof(HTABLE_INFO));
221     ht->key = mystrdup(key);
222     ht->value = value;
223     htable_link(table, ht);
224     return (ht);
225 }
226 
227 /* htable_find - lookup value */
228 
229 char   *htable_find(HTABLE *table, const char *key)
230 {
231     HTABLE_INFO *ht;
232 
233 #define	STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
234 
235     if (table)
236 	for (ht = table->data[htable_hash(key, table->size)]; ht; ht = ht->next)
237 	    if (STREQ(key, ht->key))
238 		return (ht->value);
239     return (0);
240 }
241 
242 /* htable_locate - lookup entry */
243 
244 HTABLE_INFO *htable_locate(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);
254     return (0);
255 }
256 
257 /* htable_delete - delete one entry */
258 
259 void    htable_delete(HTABLE *table, const char *key, void (*free_fn) (char *))
260 {
261     if (table) {
262 	HTABLE_INFO *ht;
263 	HTABLE_INFO **h = table->data + htable_hash(key, table->size);
264 
265 #define	STREQ(x,y) (x == y || (x[0] == y[0] && strcmp(x,y) == 0))
266 
267 	for (ht = *h; ht; ht = ht->next) {
268 	    if (STREQ(key, ht->key)) {
269 		if (ht->next)
270 		    ht->next->prev = ht->prev;
271 		if (ht->prev)
272 		    ht->prev->next = ht->next;
273 		else
274 		    *h = ht->next;
275 		table->used--;
276 		myfree(ht->key);
277 		if (free_fn && ht->value)
278 		    (*free_fn) (ht->value);
279 		myfree((char *) ht);
280 		return;
281 	    }
282 	}
283 	msg_panic("htable_delete: unknown_key: \"%s\"", key);
284     }
285 }
286 
287 /* htable_free - destroy hash table */
288 
289 void    htable_free(HTABLE *table, void (*free_fn) (char *))
290 {
291     if (table) {
292 	unsigned i = table->size;
293 	HTABLE_INFO *ht;
294 	HTABLE_INFO *next;
295 	HTABLE_INFO **h = table->data;
296 
297 	while (i-- > 0) {
298 	    for (ht = *h++; ht; ht = next) {
299 		next = ht->next;
300 		myfree(ht->key);
301 		if (free_fn && ht->value)
302 		    (*free_fn) (ht->value);
303 		myfree((char *) ht);
304 	    }
305 	}
306 	myfree((char *) table->data);
307 	table->data = 0;
308 	myfree((char *) table);
309     }
310 }
311 
312 /* htable_walk - iterate over hash table */
313 
314 void    htable_walk(HTABLE *table, void (*action) (HTABLE_INFO *, char *),
315 		            char *ptr) {
316     if (table) {
317 	unsigned i = table->size;
318 	HTABLE_INFO **h = table->data;
319 	HTABLE_INFO *ht;
320 
321 	while (i-- > 0)
322 	    for (ht = *h++; ht; ht = ht->next)
323 		(*action) (ht, ptr);
324     }
325 }
326 
327 /* htable_list - list all table members */
328 
329 HTABLE_INFO **htable_list(HTABLE *table)
330 {
331     HTABLE_INFO **list;
332     HTABLE_INFO *member;
333     int     count = 0;
334     int     i;
335 
336     if (table != 0) {
337 	list = (HTABLE_INFO **) mymalloc(sizeof(*list) * (table->used + 1));
338 	for (i = 0; i < table->size; i++)
339 	    for (member = table->data[i]; member != 0; member = member->next)
340 		list[count++] = member;
341     } else {
342 	list = (HTABLE_INFO **) mymalloc(sizeof(*list));
343     }
344     list[count] = 0;
345     return (list);
346 }
347 
348 /* htable_sequence - dict(3) compatibility iterator */
349 
350 HTABLE_INFO *htable_sequence(HTABLE *table, int how)
351 {
352     if (table == 0)
353 	return (0);
354 
355     switch (how) {
356     case HTABLE_SEQ_FIRST:			/* start new sequence */
357 	table->seq_bucket = table->data;
358 	table->seq_element = table->seq_bucket[0];
359 	break;
360     case HTABLE_SEQ_NEXT:			/* next element */
361 	if (table->seq_element) {
362 	    table->seq_element = table->seq_element->next;
363 	    break;
364 	}
365 	/* FALLTHROUGH */
366     default:					/* terminate sequence */
367 	return (table->seq_element = 0);
368     }
369 
370     while (table->seq_element == 0
371 	   && ++(table->seq_bucket) < table->data + table->size)
372 	table->seq_element = table->seq_bucket[0];
373     return (table->seq_element);
374 }
375 
376 #ifdef TEST
377 #include <vstring_vstream.h>
378 #include <myrand.h>
379 
380 int 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