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