dict.c revision cd8976dbee947f152c3a322503a1063c6359da76 
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <assert.h>
5
6#include "debug.h"
7
8/*
9  Dictionary based on code by Morten Eriksen <mortene@sim.no>.
10*/
11
12#include "dict.h"
13
14struct dict_entry {
15	unsigned int hash;
16	void *key;
17	void *value;
18	struct dict_entry *next;
19};
20
21/* #define DICTTABLESIZE 97 */
22#define DICTTABLESIZE 997	/* Semi-randomly selected prime number. */
23/* #define DICTTABLESIZE 9973 */
24/* #define DICTTABLESIZE 99991 */
25/* #define DICTTABLESIZE 999983 */
26
27struct dict {
28	struct dict_entry *buckets[DICTTABLESIZE];
29	unsigned int (*key2hash) (void *);
30	int (*key_cmp) (void *, void *);
31};
32
33struct dict *
34dict_init(unsigned int (*key2hash) (void *),
35		       int (*key_cmp) (void *, void *)) {
36	struct dict *d;
37	int i;
38
39	debug(DEBUG_FUNCTION, "dict_init()");
40
41	d = malloc(sizeof(struct dict));
42	if (!d) {
43		perror("malloc()");
44		exit(1);
45	}
46	for (i = 0; i < DICTTABLESIZE; i++) {	/* better use memset()? */
47		d->buckets[i] = NULL;
48	}
49	d->key2hash = key2hash;
50	d->key_cmp = key_cmp;
51	return d;
52}
53
54void
55dict_clear(struct dict *d) {
56	int i;
57	struct dict_entry *entry, *nextentry;
58
59	debug(DEBUG_FUNCTION, "dict_clear()");
60	assert(d);
61	for (i = 0; i < DICTTABLESIZE; i++) {
62		for (entry = d->buckets[i]; entry != NULL; entry = nextentry) {
63			nextentry = entry->next;
64			free(entry);
65		}
66		d->buckets[i] = NULL;
67	}
68	free(d);
69}
70
71int
72dict_enter(struct dict *d, void *key, void *value) {
73	struct dict_entry *entry, *newentry;
74	unsigned int hash;
75	unsigned int bucketpos;
76
77	debug(DEBUG_FUNCTION, "dict_enter()");
78
79	hash = d->key2hash(key);
80	bucketpos = hash % DICTTABLESIZE;
81
82	assert(d);
83	newentry = malloc(sizeof(struct dict_entry));
84	if (!newentry) {
85		perror("malloc");
86		exit(1);
87	}
88
89	newentry->hash = hash;
90	newentry->key = key;
91	newentry->value = value;
92	newentry->next = NULL;
93
94	entry = d->buckets[bucketpos];
95	while (entry && entry->next)
96		entry = entry->next;
97
98	if (entry)
99		entry->next = newentry;
100	else
101		d->buckets[bucketpos] = newentry;
102
103	debug(3, "new dict entry at %p[%d]: (%p,%p)", d, bucketpos, key, value);
104	return 0;
105}
106
107void *
108dict_find_entry(struct dict *d, void *key) {
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(struct 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(void *key) {
153	const char *s = (const char *)key;
154	unsigned int total = 0, shift = 0;
155
156	assert(key);
157	while (*s) {
158		total = total ^ ((*s) << shift);
159		shift += 5;
160		if (shift > 24)
161			shift -= 24;
162		s++;
163	}
164	return total;
165}
166
167int
168dict_key_cmp_string(void *key1, void *key2) {
169	assert(key1);
170	assert(key2);
171	return strcmp((const char *)key1, (const char *)key2);
172}
173
174unsigned int
175dict_key2hash_int(void *key) {
176	return (unsigned long)key;
177}
178
179int
180dict_key_cmp_int(void *key1, void *key2) {
181	return key1 - key2;
182}
183
184struct dict *
185dict_clone(struct dict *old, void * (*key_clone)(void*), void * (*value_clone)(void*)) {
186	struct dict *d;
187	int i;
188
189	debug(DEBUG_FUNCTION, "dict_clone()");
190
191	d = malloc(sizeof(struct dict));
192	if (!d) {
193		perror("malloc()");
194		exit(1);
195	}
196	memcpy(d, old, sizeof(struct 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			*de_new = malloc(sizeof(struct dict_entry));
205			if (!*de_new) {
206				perror("malloc()");
207				exit(1);
208			}
209			memcpy(*de_new, de_old, sizeof(struct dict_entry));
210			(*de_new)->key = key_clone(de_old->key);
211			(*de_new)->value = value_clone(de_old->value);
212			de_new = &(*de_new)->next;
213			de_old = de_old->next;
214		}
215	}
216	return d;
217}
218