dict.c revision a11cbede4711e1efe2d6fb0a8a5b2050b2fe941c 
1/*
2 * This file is part of ltrace.
3 * Copyright (C) 2011,2012 Petr Machata
4 * Copyright (C) 2003,2004,2008,2009 Juan Cespedes
5 * Copyright (C) 2006 Ian Wienand
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License as
9 * published by the Free Software Foundation; either version 2 of the
10 * License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful, but
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15 * General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
20 * 02110-1301 USA
21 */
22
23#include <stdio.h>
24#include <stdlib.h>
25#include <string.h>
26#include <assert.h>
27
28#include "common.h"
29
30/*
31 * Dictionary based on code by Morten Eriksen <mortene@sim.no>.
32 */
33
34struct dict_entry {
35	unsigned int hash;
36	void *key;
37	void *value;
38	struct dict_entry *next;
39};
40
41/* #define DICTTABLESIZE 97 */
42#define DICTTABLESIZE 997	/* Semi-randomly selected prime number. */
43/* #define DICTTABLESIZE 9973 */
44/* #define DICTTABLESIZE 99991 */
45/* #define DICTTABLESIZE 999983 */
46
47struct dict {
48	struct dict_entry *buckets[DICTTABLESIZE];
49	unsigned int (*key2hash) (const void *);
50	int (*key_cmp) (const void *, const void *);
51};
52
53Dict *
54dict_init(unsigned int (*key2hash) (const void *),
55	  int (*key_cmp) (const void *, const void *))
56{
57	Dict *d;
58	int i;
59
60	debug(DEBUG_FUNCTION, "dict_init()");
61
62	d = malloc(sizeof(Dict));
63	if (!d) {
64		perror("malloc()");
65		exit(1);
66	}
67	for (i = 0; i < DICTTABLESIZE; i++) {	/* better use memset()? */
68		d->buckets[i] = NULL;
69	}
70	d->key2hash = key2hash;
71	d->key_cmp = key_cmp;
72	return d;
73}
74
75void
76dict_clear(Dict *d) {
77	int i;
78	struct dict_entry *entry, *nextentry;
79
80	debug(DEBUG_FUNCTION, "dict_clear()");
81	assert(d);
82	for (i = 0; i < DICTTABLESIZE; i++) {
83		for (entry = d->buckets[i]; entry != NULL; entry = nextentry) {
84			nextentry = entry->next;
85			free(entry);
86		}
87		d->buckets[i] = NULL;
88	}
89	free(d);
90}
91
92int
93dict_enter(Dict *d, void *key, void *value) {
94	struct dict_entry *entry, *newentry;
95	unsigned int hash;
96	unsigned int bucketpos;
97
98	debug(DEBUG_FUNCTION, "dict_enter()");
99
100	hash = d->key2hash(key);
101	bucketpos = hash % DICTTABLESIZE;
102
103	assert(d);
104	newentry = malloc(sizeof(struct dict_entry));
105	if (!newentry) {
106		perror("malloc");
107		exit(1);
108	}
109
110	newentry->hash = hash;
111	newentry->key = key;
112	newentry->value = value;
113	newentry->next = NULL;
114
115	entry = d->buckets[bucketpos];
116	while (entry && entry->next)
117		entry = entry->next;
118
119	if (entry)
120		entry->next = newentry;
121	else
122		d->buckets[bucketpos] = newentry;
123
124	debug(3, "new dict entry at %p[%d]: (%p,%p)", d, bucketpos, key, value);
125	return 0;
126}
127
128void *
129dict_remove(Dict *d, void *key)
130{
131	assert(d != NULL);
132	debug(DEBUG_FUNCTION, "dict_remove(%p)", key);
133
134	unsigned int hash = d->key2hash(key);
135	unsigned int bucketpos = hash % DICTTABLESIZE;
136
137	struct dict_entry **entryp;
138	for (entryp = &d->buckets[bucketpos]; (*entryp) != NULL;
139	     entryp = &(*entryp)->next) {
140		struct dict_entry *entry = *entryp;
141		if (hash != entry->hash)
142			continue;
143		if (d->key_cmp(key, entry->key) == 0) {
144			*entryp = entry->next;
145			return entry->value;
146		}
147	}
148	return NULL;
149}
150
151void *
152dict_find_entry(Dict *d, const void *key)
153{
154	unsigned int hash;
155	unsigned int bucketpos;
156	struct dict_entry *entry;
157
158	debug(DEBUG_FUNCTION, "dict_find_entry()");
159
160	hash = d->key2hash(key);
161	bucketpos = hash % DICTTABLESIZE;
162
163	assert(d);
164	for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
165		if (hash != entry->hash) {
166			continue;
167		}
168		if (!d->key_cmp(key, entry->key)) {
169			break;
170		}
171	}
172	return entry ? entry->value : NULL;
173}
174
175void
176dict_apply_to_all(Dict *d,
177		  void (*func) (void *key, void *value, void *data), void *data) {
178	int i;
179
180	debug(DEBUG_FUNCTION, "dict_apply_to_all()");
181
182	if (!d) {
183		return;
184	}
185	for (i = 0; i < DICTTABLESIZE; i++) {
186		struct dict_entry *entry = d->buckets[i];
187		while (entry) {
188			func(entry->key, entry->value, data);
189			entry = entry->next;
190		}
191	}
192}
193
194/*****************************************************************************/
195
196unsigned int
197dict_key2hash_string(const void *key)
198{
199	const char *s = (const char *)key;
200	unsigned int total = 0, shift = 0;
201
202	assert(key);
203	while (*s) {
204		total = total ^ ((*s) << shift);
205		shift += 5;
206		if (shift > 24)
207			shift -= 24;
208		s++;
209	}
210	return total;
211}
212
213int
214dict_key_cmp_string(const void *key1, const void *key2)
215{
216	assert(key1);
217	assert(key2);
218	return strcmp((const char *)key1, (const char *)key2);
219}
220
221unsigned int
222dict_key2hash_int(const void *key)
223{
224	return (unsigned long)key;
225}
226
227int
228dict_key_cmp_int(const void *key1, const void *key2)
229{
230	return key1 - key2;
231}
232
233Dict *
234dict_clone2(Dict * old, void * (*key_clone)(void *, void *),
235	    void * (*value_clone)(void *, void *), void * data)
236{
237	Dict *d;
238	int i;
239
240	debug(DEBUG_FUNCTION, "dict_clone()");
241
242	d = malloc(sizeof(Dict));
243	if (!d) {
244		perror("malloc()");
245		exit(1);
246	}
247	memcpy(d, old, sizeof(Dict));
248	for (i = 0; i < DICTTABLESIZE; i++) {	/* better use memset()? */
249		struct dict_entry *de_old;
250		struct dict_entry **de_new;
251
252		de_old = old->buckets[i];
253		de_new = &d->buckets[i];
254		while (de_old) {
255			void * nkey, * nval;
256			*de_new = malloc(sizeof(struct dict_entry));
257			if (!*de_new) {
258				perror("malloc()");
259				exit(1);
260			}
261			memcpy(*de_new, de_old, sizeof(struct dict_entry));
262
263			/* The error detection is rather weak :-/ */
264			nkey = key_clone(de_old->key, data);
265			if (nkey == NULL && de_old->key != NULL) {
266				perror("key_clone");
267			err:
268				/* XXX Will this actually work?  We
269				 * simply memcpy the old dictionary
270				 * over up there.  */
271				dict_clear(d);
272				free(de_new);
273				return NULL;
274			}
275
276			nval = value_clone(de_old->value, data);
277			if (nval == NULL && de_old->value != NULL) {
278				perror("value_clone");
279				goto err;
280			}
281
282			(*de_new)->key = nkey;
283			(*de_new)->value = nval;
284			de_new = &(*de_new)->next;
285			de_old = de_old->next;
286		}
287	}
288	return d;
289}
290
291struct wrap_clone_cb
292{
293	void * (*key_clone)(void *);
294	void * (*value_clone)(void *);
295};
296
297static void *
298value_clone_1(void * arg, void * data)
299{
300	return ((struct wrap_clone_cb *)data)->value_clone(arg);
301}
302
303static void *
304key_clone_1(void * arg, void * data)
305{
306	return ((struct wrap_clone_cb *)data)->key_clone(arg);
307}
308
309Dict *
310dict_clone(Dict * old, void * (*key_clone)(void *),
311	   void * (*value_clone)(void *))
312{
313	struct wrap_clone_cb cb = { key_clone, value_clone };
314	return dict_clone2(old, &key_clone_1, &value_clone_1, &cb);
315}
316