dict.c revision cac15c3f170b5ec2cc6304c8c0763a78103e1778 
1#include <stdio.h>
2#include <stdlib.h>
3
4#include "debug.h"
5
6/*
7  Dictionary based on code by Morten Eriksen <mortene@sim.no>.
8*/
9
10#include "dict.h"
11
12struct dict_entry {
13	unsigned int hash;
14	void * key;
15	void * value;
16	struct dict_entry * next;
17};
18
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 */
24
25struct dict {
26	struct dict_entry * buckets[DICTTABLESIZE];
27	unsigned int (*key2hash)(void *);
28	int (*key_cmp)(void *, void *);
29};
30
31struct dict *
32dict_init(unsigned int (*key2hash)(void *), int (*key_cmp)(void *, void *)) {
33	struct dict * d;
34	int i;
35
36	d = malloc(sizeof(struct dict));
37	if (!d) {
38		perror("malloc()");
39		exit(1);
40	}
41	for (i = 0; i < DICTTABLESIZE; i++) { /* better use memset()? */
42		d->buckets[i] = NULL;
43	}
44	d->key2hash = key2hash;
45	d->key_cmp = key_cmp;
46	return d;
47}
48
49void
50dict_clear(struct dict * d) {
51	int i;
52	struct dict_entry * entry, * nextentry;
53
54	for (i = 0; i < DICTTABLESIZE; i++) {
55		for (entry = d->buckets[i]; entry != NULL; entry = nextentry) {
56			nextentry = entry->next;
57			free(entry);
58		}
59		d->buckets[i] = NULL;
60	}
61	free(d);
62}
63
64int
65dict_enter(struct dict * d, void * key, void * value) {
66	struct dict_entry * entry, * newentry;
67	unsigned int hash = d->key2hash(key);
68	unsigned int bucketpos = hash % DICTTABLESIZE;
69
70	newentry = malloc(sizeof(struct dict_entry));
71	if (!newentry) {
72		perror("malloc");
73		exit(1);
74	}
75
76	newentry->hash  = hash;
77	newentry->key   = key;
78	newentry->value = value;
79	newentry->next  = NULL;
80
81	entry = d->buckets[bucketpos];
82	while (entry && entry->next) entry = entry->next;
83
84	if (entry) entry->next = newentry;
85	else d->buckets[bucketpos] = newentry;
86
87	debug(3, "new dict entry at %p[%d]: (%p,%p)\n", d, bucketpos, key, value);
88	return 0;
89}
90
91void *
92dict_find_entry(struct dict * d, void * key) {
93	unsigned int hash = d->key2hash(key);
94	unsigned int bucketpos = hash % DICTTABLESIZE;
95	struct dict_entry * entry;
96
97	for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
98		if (hash != entry->hash) {
99			continue;
100		}
101		if (!d->key_cmp(key, entry->key)) {
102			break;
103		}
104	}
105	return entry ? entry->value : NULL;
106}
107
108void
109dict_apply_to_all(struct dict * d, void (*func)(void *key, void *value, void *data), void *data) {
110	int i;
111
112	for (i = 0; i < DICTTABLESIZE; i++) {
113		struct dict_entry * entry = d->buckets[i];
114		while (entry) {
115			func(entry->key, entry->value, data);
116			entry = entry->next;
117		}
118	}
119}
120
121/*****************************************************************************/
122
123unsigned int
124dict_key2hash_string(void * key) {
125	const char * s = (const char *)key;
126	unsigned int total = 0, shift = 0;
127
128	while (*s) {
129		total = total ^ ((*s) << shift);
130		shift += 5;
131		if (shift > 24) shift -= 24;
132		s++;
133	}
134	return total;
135}
136
137int
138dict_key_cmp_string(void * key1, void * key2) {
139	return strcmp((const char *)key1, (const char *)key2);
140}
141
142unsigned int
143dict_key2hash_int(void * key) {
144	return (unsigned int)key;
145}
146
147int
148dict_key_cmp_int(void * key1, void * key2) {
149	return key1 - key2;
150}
151
152