dict.c revision 8d1b92ba755f6d6229f5e230fc43d958b13836f8 
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_clone(Dict *old, void * (*key_clone)(void*), void * (*value_clone)(void*)) {
184	Dict *d;
185	int i;
186
187	debug(DEBUG_FUNCTION, "dict_clone()");
188
189	d = malloc(sizeof(Dict));
190	if (!d) {
191		perror("malloc()");
192		exit(1);
193	}
194	memcpy(d, old, sizeof(Dict));
195	for (i = 0; i < DICTTABLESIZE; i++) {	/* better use memset()? */
196		struct dict_entry *de_old;
197		struct dict_entry **de_new;
198
199		de_old = old->buckets[i];
200		de_new = &d->buckets[i];
201		while (de_old) {
202			*de_new = malloc(sizeof(struct dict_entry));
203			if (!*de_new) {
204				perror("malloc()");
205				exit(1);
206			}
207			memcpy(*de_new, de_old, sizeof(struct dict_entry));
208			(*de_new)->key = key_clone(de_old->key);
209			(*de_new)->value = value_clone(de_old->value);
210			de_new = &(*de_new)->next;
211			de_old = de_old->next;
212		}
213	}
214	return d;
215}
216