9 Dictionary based on code by Morten Eriksen <mortene@sim.no>.
16 struct dict_entry *next;
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 */
26 struct dict_entry *buckets[DICTTABLESIZE];
27 unsigned int (*key2hash) (void *);
28 int (*key_cmp) (void *, void *);
32 dict_init(unsigned int (*key2hash) (void *),
33 int (*key_cmp) (void *, void *)) {
37 debug(DEBUG_FUNCTION, "dict_init()");
39 d = malloc(sizeof(Dict));
44 for (i = 0; i < DICTTABLESIZE; i++) { /* better use memset()? */
47 d->key2hash = key2hash;
55 struct dict_entry *entry, *nextentry;
57 debug(DEBUG_FUNCTION, "dict_clear()");
59 for (i = 0; i < DICTTABLESIZE; i++) {
60 for (entry = d->buckets[i]; entry != NULL; entry = nextentry) {
61 nextentry = entry->next;
70 dict_enter(Dict *d, void *key, void *value) {
71 struct dict_entry *entry, *newentry;
73 unsigned int bucketpos;
75 debug(DEBUG_FUNCTION, "dict_enter()");
77 hash = d->key2hash(key);
78 bucketpos = hash % DICTTABLESIZE;
81 newentry = malloc(sizeof(struct dict_entry));
87 newentry->hash = hash;
89 newentry->value = value;
90 newentry->next = NULL;
92 entry = d->buckets[bucketpos];
93 while (entry && entry->next)
97 entry->next = newentry;
99 d->buckets[bucketpos] = newentry;
101 debug(3, "new dict entry at %p[%d]: (%p,%p)", d, bucketpos, key, value);
106 dict_find_entry(Dict *d, void *key) {
108 unsigned int bucketpos;
109 struct dict_entry *entry;
111 debug(DEBUG_FUNCTION, "dict_find_entry()");
113 hash = d->key2hash(key);
114 bucketpos = hash % DICTTABLESIZE;
117 for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
118 if (hash != entry->hash) {
121 if (!d->key_cmp(key, entry->key)) {
125 return entry ? entry->value : NULL;
129 dict_apply_to_all(Dict *d,
130 void (*func) (void *key, void *value, void *data), void *data) {
133 debug(DEBUG_FUNCTION, "dict_apply_to_all()");
138 for (i = 0; i < DICTTABLESIZE; i++) {
139 struct dict_entry *entry = d->buckets[i];
141 func(entry->key, entry->value, data);
147 /*****************************************************************************/
150 dict_key2hash_string(void *key) {
151 const char *s = (const char *)key;
152 unsigned int total = 0, shift = 0;
156 total = total ^ ((*s) << shift);
166 dict_key_cmp_string(void *key1, void *key2) {
169 return strcmp((const char *)key1, (const char *)key2);
173 dict_key2hash_int(void *key) {
174 return (unsigned long)key;
178 dict_key_cmp_int(void *key1, void *key2) {
183 dict_clone(Dict *old, void * (*key_clone)(void*), void * (*value_clone)(void*)) {
187 debug(DEBUG_FUNCTION, "dict_clone()");
189 d = malloc(sizeof(Dict));
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;
199 de_old = old->buckets[i];
200 de_new = &d->buckets[i];
202 *de_new = malloc(sizeof(struct dict_entry));
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;