dict.c revision 345c9b5195383c7b2d2d9db308e824259323803f 
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_find_entry(Dict *d, const void *key)
108{
109	unsigned int hash;
110	unsigned int bucketpos;
111	struct dict_entry *entry;
112
113	debug(DEBUG_FUNCTION, "dict_find_entry()");
114
115	hash = d->key2hash(key);
116	bucketpos = hash % DICTTABLESIZE;
117
118	assert(d);
119	for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
120		if (hash != entry->hash) {
121			continue;
122		}
123		if (!d->key_cmp(key, entry->key)) {
124			break;
125		}
126	}
127	return entry ? entry->value : NULL;
128}
129
130void
131dict_apply_to_all(Dict *d,
132		  void (*func) (void *key, void *value, void *data), void *data) {
133	int i;
134
135	debug(DEBUG_FUNCTION, "dict_apply_to_all()");
136
137	if (!d) {
138		return;
139	}
140	for (i = 0; i < DICTTABLESIZE; i++) {
141		struct dict_entry *entry = d->buckets[i];
142		while (entry) {
143			func(entry->key, entry->value, data);
144			entry = entry->next;
145		}
146	}
147}
148
149/*****************************************************************************/
150
151unsigned int
152dict_key2hash_string(const void *key)
153{
154	const char *s = (const char *)key;
155	unsigned int total = 0, shift = 0;
156
157	assert(key);
158	while (*s) {
159		total = total ^ ((*s) << shift);
160		shift += 5;
161		if (shift > 24)
162			shift -= 24;
163		s++;
164	}
165	return total;
166}
167
168int
169dict_key_cmp_string(const void *key1, const void *key2)
170{
171	assert(key1);
172	assert(key2);
173	return strcmp((const char *)key1, (const char *)key2);
174}
175
176unsigned int
177dict_key2hash_int(const void *key)
178{
179	return (unsigned long)key;
180}
181
182int
183dict_key_cmp_int(const void *key1, const void *key2)
184{
185	return key1 - key2;
186}
187
188Dict *
189dict_clone2(Dict * old, void * (*key_clone)(void *, void *),
190	    void * (*value_clone)(void *, void *), void * data)
191{
192	Dict *d;
193	int i;
194
195	debug(DEBUG_FUNCTION, "dict_clone()");
196
197	d = malloc(sizeof(Dict));
198	if (!d) {
199		perror("malloc()");
200		exit(1);
201	}
202	memcpy(d, old, sizeof(Dict));
203	for (i = 0; i < DICTTABLESIZE; i++) {	/* better use memset()? */
204		struct dict_entry *de_old;
205		struct dict_entry **de_new;
206
207		de_old = old->buckets[i];
208		de_new = &d->buckets[i];
209		while (de_old) {
210			void * nkey, * nval;
211			*de_new = malloc(sizeof(struct dict_entry));
212			if (!*de_new) {
213				perror("malloc()");
214				exit(1);
215			}
216			memcpy(*de_new, de_old, sizeof(struct dict_entry));
217
218			/* The error detection is rather weak :-/ */
219			nkey = key_clone(de_old->key, data);
220			if (nkey == NULL && de_old->key != NULL) {
221				perror("key_clone");
222			err:
223				/* XXX Will this actually work?  We
224				 * simply memcpy the old dictionary
225				 * over up there.  */
226				dict_clear(d);
227				free(de_new);
228				return NULL;
229			}
230
231			nval = value_clone(de_old->value, data);
232			if (nval == NULL && de_old->value != NULL) {
233				perror("value_clone");
234				goto err;
235			}
236
237			(*de_new)->key = nkey;
238			(*de_new)->value = nval;
239			de_new = &(*de_new)->next;
240			de_old = de_old->next;
241		}
242	}
243	return d;
244}
245
246struct wrap_clone_cb
247{
248	void * (*key_clone)(void *);
249	void * (*value_clone)(void *);
250};
251
252static void *
253value_clone_1(void * arg, void * data)
254{
255	return ((struct wrap_clone_cb *)data)->value_clone(arg);
256}
257
258static void *
259key_clone_1(void * arg, void * data)
260{
261	return ((struct wrap_clone_cb *)data)->key_clone(arg);
262}
263
264Dict *
265dict_clone(Dict * old, void * (*key_clone)(void *),
266	   void * (*value_clone)(void *))
267{
268	struct wrap_clone_cb cb = { key_clone, value_clone };
269	return dict_clone2(old, &key_clone_1, &value_clone_1, &cb);
270}
271