dict.c revision 2d45b1a8e26a36a9f85dc49e721c4390ca93dc40 
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 *dict_init(unsigned int (*key2hash) (void *),
34		       int (*key_cmp) (void *, void *))
35{
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 dict_clear(struct dict *d)
53{
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 dict_enter(struct dict *d, void *key, void *value)
69{
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 *dict_find_entry(struct dict *d, void *key)
100{
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{
121	int i;
122
123	if (!d) {
124		return;
125	}
126	for (i = 0; i < DICTTABLESIZE; i++) {
127		struct dict_entry *entry = d->buckets[i];
128		while (entry) {
129			func(entry->key, entry->value, data);
130			entry = entry->next;
131		}
132	}
133}
134
135/*****************************************************************************/
136
137unsigned int dict_key2hash_string(void *key)
138{
139	const char *s = (const char *)key;
140	unsigned int total = 0, shift = 0;
141
142	assert(key);
143	while (*s) {
144		total = total ^ ((*s) << shift);
145		shift += 5;
146		if (shift > 24)
147			shift -= 24;
148		s++;
149	}
150	return total;
151}
152
153int dict_key_cmp_string(void *key1, void *key2)
154{
155	assert(key1);
156	assert(key2);
157	return strcmp((const char *)key1, (const char *)key2);
158}
159
160unsigned int dict_key2hash_int(void *key)
161{
162	return (unsigned long)key;
163}
164
165int dict_key_cmp_int(void *key1, void *key2)
166{
167	return key1 - key2;
168}
169