dict.c revision 77fbb8ff4ba461c11af3678a0db7cf6a47738ff4 
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <assert.h>
5
6#include "common.h"
7
8/*
9  Dictionary based on code by Morten Eriksen <mortene@sim.no>.
10*/
11
12struct dict_entry {
13	unsigned int hash;
14	void *key;
15	void *value;
16	struct dict_entry *next;
17};
18
19/* #define DICTTABLESIZE 97 */
20#define DICTTABLESIZE 997	/* Semi-randomly selected prime number. */
21/* #define DICTTABLESIZE 9973 */
22/* #define DICTTABLESIZE 99991 */
23/* #define DICTTABLESIZE 999983 */
24
25struct dict {
26	struct dict_entry *buckets[DICTTABLESIZE];
27	unsigned int (*key2hash) (const void *);
28	int (*key_cmp) (const void *, const void *);
29};
30
31Dict *
32dict_init(unsigned int (*key2hash) (const void *),
33	  int (*key_cmp) (const void *, const void *))
34{
35	Dict *d;
36	int i;
37
38	debug(DEBUG_FUNCTION, "dict_init()");
39
40	d = malloc(sizeof(Dict));
41	if (!d) {
42		perror("malloc()");
43		exit(1);
44	}
45	for (i = 0; i < DICTTABLESIZE; i++) {	/* better use memset()? */
46		d->buckets[i] = NULL;
47	}
48	d->key2hash = key2hash;
49	d->key_cmp = key_cmp;
50	return d;
51}
52
53void
54dict_clear(Dict *d) {
55	int i;
56	struct dict_entry *entry, *nextentry;
57
58	debug(DEBUG_FUNCTION, "dict_clear()");
59	assert(d);
60	for (i = 0; i < DICTTABLESIZE; i++) {
61		for (entry = d->buckets[i]; entry != NULL; entry = nextentry) {
62			nextentry = entry->next;
63			free(entry);
64		}
65		d->buckets[i] = NULL;
66	}
67	free(d);
68}
69
70int
71dict_enter(Dict *d, void *key, void *value) {
72	struct dict_entry *entry, *newentry;
73	unsigned int hash;
74	unsigned int bucketpos;
75
76	debug(DEBUG_FUNCTION, "dict_enter()");
77
78	hash = d->key2hash(key);
79	bucketpos = hash % DICTTABLESIZE;
80
81	assert(d);
82	newentry = malloc(sizeof(struct dict_entry));
83	if (!newentry) {
84		perror("malloc");
85		exit(1);
86	}
87
88	newentry->hash = hash;
89	newentry->key = key;
90	newentry->value = value;
91	newentry->next = NULL;
92
93	entry = d->buckets[bucketpos];
94	while (entry && entry->next)
95		entry = entry->next;
96
97	if (entry)
98		entry->next = newentry;
99	else
100		d->buckets[bucketpos] = newentry;
101
102	debug(3, "new dict entry at %p[%d]: (%p,%p)", d, bucketpos, key, value);
103	return 0;
104}
105
106void *
107dict_remove(Dict *d, void *key)
108{
109	assert(d != NULL);
110	debug(DEBUG_FUNCTION, "dict_remove(%p)", key);
111
112	unsigned int hash = d->key2hash(key);
113	unsigned int bucketpos = hash % DICTTABLESIZE;
114
115	struct dict_entry **entryp;
116	for (entryp = &d->buckets[bucketpos]; (*entryp) != NULL;
117	     entryp = &(*entryp)->next) {
118		struct dict_entry *entry = *entryp;
119		if (hash != entry->hash)
120			continue;
121		if (d->key_cmp(key, entry->key) == 0) {
122			*entryp = entry->next;
123			return entry->value;
124		}
125	}
126	return NULL;
127}
128
129void *
130dict_find_entry(Dict *d, const void *key)
131{
132	unsigned int hash;
133	unsigned int bucketpos;
134	struct dict_entry *entry;
135
136	debug(DEBUG_FUNCTION, "dict_find_entry()");
137
138	hash = d->key2hash(key);
139	bucketpos = hash % DICTTABLESIZE;
140
141	assert(d);
142	for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
143		if (hash != entry->hash) {
144			continue;
145		}
146		if (!d->key_cmp(key, entry->key)) {
147			break;
148		}
149	}
150	return entry ? entry->value : NULL;
151}
152
153void
154dict_apply_to_all(Dict *d,
155		  void (*func) (void *key, void *value, void *data), void *data) {
156	int i;
157
158	debug(DEBUG_FUNCTION, "dict_apply_to_all()");
159
160	if (!d) {
161		return;
162	}
163	for (i = 0; i < DICTTABLESIZE; i++) {
164		struct dict_entry *entry = d->buckets[i];
165		while (entry) {
166			func(entry->key, entry->value, data);
167			entry = entry->next;
168		}
169	}
170}
171
172/*****************************************************************************/
173
174unsigned int
175dict_key2hash_string(const void *key)
176{
177	const char *s = (const char *)key;
178	unsigned int total = 0, shift = 0;
179
180	assert(key);
181	while (*s) {
182		total = total ^ ((*s) << shift);
183		shift += 5;
184		if (shift > 24)
185			shift -= 24;
186		s++;
187	}
188	return total;
189}
190
191int
192dict_key_cmp_string(const void *key1, const void *key2)
193{
194	assert(key1);
195	assert(key2);
196	return strcmp((const char *)key1, (const char *)key2);
197}
198
199unsigned int
200dict_key2hash_int(const void *key)
201{
202	return (unsigned long)key;
203}
204
205int
206dict_key_cmp_int(const void *key1, const void *key2)
207{
208	return key1 - key2;
209}
210
211Dict *
212dict_clone2(Dict * old, void * (*key_clone)(void *, void *),
213	    void * (*value_clone)(void *, void *), void * data)
214{
215	Dict *d;
216	int i;
217
218	debug(DEBUG_FUNCTION, "dict_clone()");
219
220	d = malloc(sizeof(Dict));
221	if (!d) {
222		perror("malloc()");
223		exit(1);
224	}
225	memcpy(d, old, sizeof(Dict));
226	for (i = 0; i < DICTTABLESIZE; i++) {	/* better use memset()? */
227		struct dict_entry *de_old;
228		struct dict_entry **de_new;
229
230		de_old = old->buckets[i];
231		de_new = &d->buckets[i];
232		while (de_old) {
233			void * nkey, * nval;
234			*de_new = malloc(sizeof(struct dict_entry));
235			if (!*de_new) {
236				perror("malloc()");
237				exit(1);
238			}
239			memcpy(*de_new, de_old, sizeof(struct dict_entry));
240
241			/* The error detection is rather weak :-/ */
242			nkey = key_clone(de_old->key, data);
243			if (nkey == NULL && de_old->key != NULL) {
244				perror("key_clone");
245			err:
246				/* XXX Will this actually work?  We
247				 * simply memcpy the old dictionary
248				 * over up there.  */
249				dict_clear(d);
250				free(de_new);
251				return NULL;
252			}
253
254			nval = value_clone(de_old->value, data);
255			if (nval == NULL && de_old->value != NULL) {
256				perror("value_clone");
257				goto err;
258			}
259
260			(*de_new)->key = nkey;
261			(*de_new)->value = nval;
262			de_new = &(*de_new)->next;
263			de_old = de_old->next;
264		}
265	}
266	return d;
267}
268
269struct wrap_clone_cb
270{
271	void * (*key_clone)(void *);
272	void * (*value_clone)(void *);
273};
274
275static void *
276value_clone_1(void * arg, void * data)
277{
278	return ((struct wrap_clone_cb *)data)->value_clone(arg);
279}
280
281static void *
282key_clone_1(void * arg, void * data)
283{
284	return ((struct wrap_clone_cb *)data)->key_clone(arg);
285}
286
287Dict *
288dict_clone(Dict * old, void * (*key_clone)(void *),
289	   void * (*value_clone)(void *))
290{
291	struct wrap_clone_cb cb = { key_clone, value_clone };
292	return dict_clone2(old, &key_clone_1, &value_clone_1, &cb);
293}
294