dict.c revision d3202de1176057520f49b5e6231b8774f6b6b31f 
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			void *value = entry->value;
146			free(entry);
147			return value;
148		}
149	}
150	return NULL;
151}
152
153void *
154dict_find_entry(Dict *d, const void *key)
155{
156	unsigned int hash;
157	unsigned int bucketpos;
158	struct dict_entry *entry;
159
160	debug(DEBUG_FUNCTION, "dict_find_entry()");
161
162	hash = d->key2hash(key);
163	bucketpos = hash % DICTTABLESIZE;
164
165	assert(d);
166	for (entry = d->buckets[bucketpos]; entry; entry = entry->next) {
167		if (hash != entry->hash) {
168			continue;
169		}
170		if (!d->key_cmp(key, entry->key)) {
171			break;
172		}
173	}
174	return entry ? entry->value : NULL;
175}
176
177void
178dict_apply_to_all(Dict *d,
179		  void (*func) (void *key, void *value, void *data), void *data) {
180	int i;
181
182	debug(DEBUG_FUNCTION, "dict_apply_to_all()");
183
184	if (!d) {
185		return;
186	}
187	for (i = 0; i < DICTTABLESIZE; i++) {
188		struct dict_entry *entry = d->buckets[i];
189		while (entry) {
190			func(entry->key, entry->value, data);
191			entry = entry->next;
192		}
193	}
194}
195
196/*****************************************************************************/
197
198unsigned int
199dict_key2hash_string(const void *key)
200{
201	const char *s = (const char *)key;
202	unsigned int total = 0, shift = 0;
203
204	assert(key);
205	while (*s) {
206		total = total ^ ((*s) << shift);
207		shift += 5;
208		if (shift > 24)
209			shift -= 24;
210		s++;
211	}
212	return total;
213}
214
215int
216dict_key_cmp_string(const void *key1, const void *key2)
217{
218	assert(key1);
219	assert(key2);
220	return strcmp((const char *)key1, (const char *)key2);
221}
222
223unsigned int
224dict_key2hash_int(const void *key)
225{
226	return (unsigned long)key;
227}
228
229int
230dict_key_cmp_int(const void *key1, const void *key2)
231{
232	return key1 - key2;
233}
234
235Dict *
236dict_clone2(Dict * old, void * (*key_clone)(void *, void *),
237	    void * (*value_clone)(void *, void *), void * data)
238{
239	Dict *d;
240	int i;
241
242	debug(DEBUG_FUNCTION, "dict_clone()");
243
244	d = malloc(sizeof(Dict));
245	if (!d) {
246		perror("malloc()");
247		exit(1);
248	}
249	memcpy(d, old, sizeof(Dict));
250	for (i = 0; i < DICTTABLESIZE; i++) {	/* better use memset()? */
251		struct dict_entry *de_old;
252		struct dict_entry **de_new;
253
254		de_old = old->buckets[i];
255		de_new = &d->buckets[i];
256		while (de_old) {
257			void * nkey, * nval;
258			*de_new = malloc(sizeof(struct dict_entry));
259			if (!*de_new) {
260				perror("malloc()");
261				exit(1);
262			}
263			memcpy(*de_new, de_old, sizeof(struct dict_entry));
264
265			/* The error detection is rather weak :-/ */
266			nkey = key_clone(de_old->key, data);
267			if (nkey == NULL && de_old->key != NULL) {
268				perror("key_clone");
269			err:
270				/* XXX Will this actually work?  We
271				 * simply memcpy the old dictionary
272				 * over up there.  */
273				dict_clear(d);
274				free(de_new);
275				return NULL;
276			}
277
278			nval = value_clone(de_old->value, data);
279			if (nval == NULL && de_old->value != NULL) {
280				perror("value_clone");
281				goto err;
282			}
283
284			(*de_new)->key = nkey;
285			(*de_new)->value = nval;
286			de_new = &(*de_new)->next;
287			de_old = de_old->next;
288		}
289	}
290	return d;
291}
292
293struct wrap_clone_cb
294{
295	void * (*key_clone)(void *);
296	void * (*value_clone)(void *);
297};
298
299static void *
300value_clone_1(void * arg, void * data)
301{
302	return ((struct wrap_clone_cb *)data)->value_clone(arg);
303}
304
305static void *
306key_clone_1(void * arg, void * data)
307{
308	return ((struct wrap_clone_cb *)data)->key_clone(arg);
309}
310
311Dict *
312dict_clone(Dict * old, void * (*key_clone)(void *),
313	   void * (*value_clone)(void *))
314{
315	struct wrap_clone_cb cb = { key_clone, value_clone };
316	return dict_clone2(old, &key_clone_1, &value_clone_1, &cb);
317}
318