dict.c revision 9a2ad351a1c3215dc596ff3e2e3fd4bc24445a6b 
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 *), int (*key_cmp)(void *, void *)) {
35	struct dict * d;
36	int i;
37
38	d = malloc(sizeof(struct dict));
39	if (!d) {
40		perror("malloc()");
41		exit(1);
42	}
43	for (i = 0; i < DICTTABLESIZE; i++) { /* better use memset()? */
44		d->buckets[i] = NULL;
45	}
46	d->key2hash = key2hash;
47	d->key_cmp = key_cmp;
48	return d;
49}
50
51void
52dict_clear(struct dict * d) {
53	int i;
54	struct dict_entry * entry, * nextentry;
55
56	assert(d);
57	for (i = 0; i < DICTTABLESIZE; i++) {
58		for (entry = d->buckets[i]; entry != NULL; entry = nextentry) {
59			nextentry = entry->next;
60			free(entry);
61		}
62		d->buckets[i] = NULL;
63	}
64	free(d);
65}
66
67int
68dict_enter(struct dict * d, void * key, void * value) {
69	struct dict_entry * entry, * newentry;
70	unsigned int hash = d->key2hash(key);
71	unsigned int bucketpos = hash % DICTTABLESIZE;
72
73	assert(d);
74	newentry = malloc(sizeof(struct dict_entry));
75	if (!newentry) {
76		perror("malloc");
77		exit(1);
78	}
79
80	newentry->hash  = hash;
81	newentry->key   = key;
82	newentry->value = value;
83	newentry->next  = NULL;
84
85	entry = d->buckets[bucketpos];
86	while (entry && entry->next) entry = entry->next;
87
88	if (entry) entry->next = newentry;
89	else d->buckets[bucketpos] = newentry;
90
91	debug(3, "new dict entry at %p[%d]: (%p,%p)", d, bucketpos, key, value);
92	return 0;
93}
94
95void *
96dict_find_entry(struct dict * d, void * key) {
97	unsigned int hash = d->key2hash(key);
98	unsigned int bucketpos = hash % DICTTABLESIZE;
99	struct dict_entry * entry;
100
101	assert(d);
102	for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
103		if (hash != entry->hash) {
104			continue;
105		}
106		if (!d->key_cmp(key, entry->key)) {
107			break;
108		}
109	}
110	return entry ? entry->value : NULL;
111}
112
113void
114dict_apply_to_all(struct dict * d, void (*func)(void *key, void *value, void *data), void *data) {
115	int i;
116
117	if (!d) {
118		return;
119	}
120	for (i = 0; i < DICTTABLESIZE; i++) {
121		struct dict_entry * entry = d->buckets[i];
122		while (entry) {
123			func(entry->key, entry->value, data);
124			entry = entry->next;
125		}
126	}
127}
128
129/*****************************************************************************/
130
131unsigned int
132dict_key2hash_string(void * key) {
133	const char * s = (const char *)key;
134	unsigned int total = 0, shift = 0;
135
136	assert(key);
137	while (*s) {
138		total = total ^ ((*s) << shift);
139		shift += 5;
140		if (shift > 24) shift -= 24;
141		s++;
142	}
143	return total;
144}
145
146int
147dict_key_cmp_string(void * key1, void * key2) {
148	assert(key1);
149	assert(key2);
150	return strcmp((const char *)key1, (const char *)key2);
151}
152
153unsigned int
154dict_key2hash_int(void * key) {
155	return (unsigned long)key;
156}
157
158int
159dict_key_cmp_int(void * key1, void * key2) {
160	return key1 - key2;
161}
162
163