dict.c revision 3219f320604810532a4938dda8f9dfadb0e840f3 
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)\n", d, bucketpos, key,
96	      value);
97	return 0;
98}
99
100void *dict_find_entry(struct dict *d, void *key)
101{
102	unsigned int hash = d->key2hash(key);
103	unsigned int bucketpos = hash % DICTTABLESIZE;
104	struct dict_entry *entry;
105
106	assert(d);
107	for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
108		if (hash != entry->hash) {
109			continue;
110		}
111		if (!d->key_cmp(key, entry->key)) {
112			break;
113		}
114	}
115	return entry ? entry->value : NULL;
116}
117
118void
119dict_apply_to_all(struct dict *d,
120		  void (*func) (void *key, void *value, void *data), void *data)
121{
122	int i;
123
124	if (!d) {
125		return;
126	}
127	for (i = 0; i < DICTTABLESIZE; i++) {
128		struct dict_entry *entry = d->buckets[i];
129		while (entry) {
130			func(entry->key, entry->value, data);
131			entry = entry->next;
132		}
133	}
134}
135
136/*****************************************************************************/
137
138unsigned int dict_key2hash_string(void *key)
139{
140	const char *s = (const char *)key;
141	unsigned int total = 0, shift = 0;
142
143	assert(key);
144	while (*s) {
145		total = total ^ ((*s) << shift);
146		shift += 5;
147		if (shift > 24)
148			shift -= 24;
149		s++;
150	}
151	return total;
152}
153
154int dict_key_cmp_string(void *key1, void *key2)
155{
156	assert(key1);
157	assert(key2);
158	return strcmp((const char *)key1, (const char *)key2);
159}
160
161unsigned int dict_key2hash_int(void *key)
162{
163	return (unsigned long)key;
164}
165
166int dict_key_cmp_int(void *key1, void *key2)
167{
168	return key1 - key2;
169}
170