dict.c revision bc8caf0ca16c8cb87bc8288c7a49ee164d075ead 
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	d = malloc(sizeof(struct 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(struct dict *d) {
54	int i;
55	struct dict_entry *entry, *nextentry;
56
57	assert(d);
58	for (i = 0; i < DICTTABLESIZE; i++) {
59		for (entry = d->buckets[i]; entry != NULL; entry = nextentry) {
60			nextentry = entry->next;
61			free(entry);
62		}
63		d->buckets[i] = NULL;
64	}
65	free(d);
66}
67
68int
69dict_enter(struct dict *d, void *key, void *value) {
70	struct dict_entry *entry, *newentry;
71	unsigned int hash = d->key2hash(key);
72	unsigned int bucketpos = hash % DICTTABLESIZE;
73
74	assert(d);
75	newentry = malloc(sizeof(struct dict_entry));
76	if (!newentry) {
77		perror("malloc");
78		exit(1);
79	}
80
81	newentry->hash = hash;
82	newentry->key = key;
83	newentry->value = value;
84	newentry->next = NULL;
85
86	entry = d->buckets[bucketpos];
87	while (entry && entry->next)
88		entry = entry->next;
89
90	if (entry)
91		entry->next = newentry;
92	else
93		d->buckets[bucketpos] = newentry;
94
95	debug(3, "new dict entry at %p[%d]: (%p,%p)", d, bucketpos, key, value);
96	return 0;
97}
98
99void *
100dict_find_entry(struct dict *d, void *key) {
101	unsigned int hash = d->key2hash(key);
102	unsigned int bucketpos = hash % DICTTABLESIZE;
103	struct dict_entry *entry;
104
105	assert(d);
106	for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
107		if (hash != entry->hash) {
108			continue;
109		}
110		if (!d->key_cmp(key, entry->key)) {
111			break;
112		}
113	}
114	return entry ? entry->value : NULL;
115}
116
117void
118dict_apply_to_all(struct dict *d,
119		  void (*func) (void *key, void *value, void *data), void *data) {
120	int i;
121
122	if (!d) {
123		return;
124	}
125	for (i = 0; i < DICTTABLESIZE; i++) {
126		struct dict_entry *entry = d->buckets[i];
127		while (entry) {
128			func(entry->key, entry->value, data);
129			entry = entry->next;
130		}
131	}
132}
133
134/*****************************************************************************/
135
136unsigned int
137dict_key2hash_string(void *key) {
138	const char *s = (const char *)key;
139	unsigned int total = 0, shift = 0;
140
141	assert(key);
142	while (*s) {
143		total = total ^ ((*s) << shift);
144		shift += 5;
145		if (shift > 24)
146			shift -= 24;
147		s++;
148	}
149	return total;
150}
151
152int
153dict_key_cmp_string(void *key1, void *key2) {
154	assert(key1);
155	assert(key2);
156	return strcmp((const char *)key1, (const char *)key2);
157}
158
159unsigned int
160dict_key2hash_int(void *key) {
161	return (unsigned long)key;
162}
163
164int
165dict_key_cmp_int(void *key1, void *key2) {
166	return key1 - key2;
167}
168
169struct dict *
170dict_clone(struct dict *old, void * (*key_clone)(void*), void * (*value_clone)(void*)) {
171	struct dict *d;
172	int i;
173
174	d = malloc(sizeof(struct dict));
175	if (!d) {
176		perror("malloc()");
177		exit(1);
178	}
179	memcpy(d, old, sizeof(struct dict));
180	for (i = 0; i < DICTTABLESIZE; i++) {	/* better use memset()? */
181		struct dict_entry *de_old;
182		struct dict_entry **de_new;
183
184		de_old = old->buckets[i];
185		de_new = &d->buckets[i];
186		while (de_old) {
187			*de_new = malloc(sizeof(struct dict_entry));
188			if (!*de_new) {
189				perror("malloc()");
190				exit(1);
191			}
192			memcpy(*de_new, de_old, sizeof(struct dict_entry));
193			(*de_new)->key = key_clone(de_old->key);
194			(*de_new)->value = value_clone(de_old->value);
195			de_new = &(*de_new)->next;
196			de_old = de_old->next;
197		}
198	}
199	return d;
200}
201