1#ifndef lint
2static char *rcsid = "$Id: strhash.c,v 1.1 2003/06/04 00:26:13 marka Exp $";
3#endif
4
5/*
6 * Copyright (c) 2000 Japan Network Information Center.  All rights reserved.
7 *
8 * By using this file, you agree to the terms and conditions set forth bellow.
9 *
10 * 			LICENSE TERMS AND CONDITIONS
11 *
12 * The following License Terms and Conditions apply, unless a different
13 * license is obtained from Japan Network Information Center ("JPNIC"),
14 * a Japanese association, Kokusai-Kougyou-Kanda Bldg 6F, 2-3-4 Uchi-Kanda,
15 * Chiyoda-ku, Tokyo 101-0047, Japan.
16 *
17 * 1. Use, Modification and Redistribution (including distribution of any
18 *    modified or derived work) in source and/or binary forms is permitted
19 *    under this License Terms and Conditions.
20 *
21 * 2. Redistribution of source code must retain the copyright notices as they
22 *    appear in each source code file, this License Terms and Conditions.
23 *
24 * 3. Redistribution in binary form must reproduce the Copyright Notice,
25 *    this License Terms and Conditions, in the documentation and/or other
26 *    materials provided with the distribution.  For the purposes of binary
27 *    distribution the "Copyright Notice" refers to the following language:
28 *    "Copyright (c) 2000-2002 Japan Network Information Center.  All rights reserved."
29 *
30 * 4. The name of JPNIC may not be used to endorse or promote products
31 *    derived from this Software without specific prior written approval of
32 *    JPNIC.
33 *
34 * 5. Disclaimer/Limitation of Liability: THIS SOFTWARE IS PROVIDED BY JPNIC
35 *    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
36 *    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
37 *    PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL JPNIC BE LIABLE
38 *    FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
39 *    CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
40 *    SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
41 *    BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
42 *    WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
43 *    OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
44 *    ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
45 */
46
47#include <config.h>
48
49#include <stddef.h>
50#include <stdlib.h>
51#include <string.h>
52
53#include <idn/assert.h>
54#include <idn/logmacro.h>
55#include <idn/result.h>
56#include <idn/strhash.h>
57
58/*
59 * Initially, the number of hash buckets is INITIAL_HASH_SIZE.
60 * As the more elements are put in the hash, the number of elements
61 * per bucket will exceed THRESHOLD eventually.  When it happens,
62 * the number of buckets will be multiplied by FACTOR.
63 */
64#define INITIAL_HASH_SIZE	67
65#define FACTOR			7
66#define THRESHOLD		5
67
68#define HASH_MULT		31
69
70typedef struct strhash_entry {
71	struct strhash_entry *next;
72	unsigned long hash_value;
73	char *key;
74	void *value;
75} strhash_entry_t;
76
77struct idn__strhash {
78	int nbins;
79	int nelements;
80	strhash_entry_t **bins;
81};
82
83static unsigned long	hash_value(const char *key);
84static strhash_entry_t	*find_entry(strhash_entry_t *entry, const char *key,
85				    unsigned long hash);
86static strhash_entry_t	*new_entry(const char *key, void *value);
87static idn_result_t	expand_bins(idn__strhash_t hash, int new_size);
88
89idn_result_t
90idn__strhash_create(idn__strhash_t *hashp) {
91	idn__strhash_t hash;
92	idn_result_t r;
93
94	TRACE(("idn__strhash_create()\n"));
95
96	assert(hashp != NULL);
97
98	*hashp = NULL;
99
100	if ((hash = malloc(sizeof(struct idn__strhash))) == NULL) {
101		WARNING(("idn__strhash_create: malloc failed (hash)\n"));
102		return (idn_nomemory);
103	}
104	hash->nbins = 0;
105	hash->nelements = 0;
106	hash->bins = NULL;
107	if ((r = expand_bins(hash, INITIAL_HASH_SIZE)) != idn_success) {
108		WARNING(("idn__strhash_create: malloc failed (bins)\n"));
109		free(hash);
110		return (r);
111	}
112
113	*hashp = hash;
114
115	return (idn_success);
116}
117
118void
119idn__strhash_destroy(idn__strhash_t hash, idn__strhash_freeproc_t proc) {
120	int i;
121
122	assert(hash != NULL && hash->bins != NULL);
123
124	for (i = 0; i < hash->nbins; i++) {
125		strhash_entry_t *bin = hash->bins[i];
126		strhash_entry_t *next;
127
128		while (bin != NULL) {
129			next = bin->next;
130			if (proc != NULL)
131				(*proc)(bin->value);
132			free(bin);
133			bin = next;
134		}
135	}
136	free(hash->bins);
137	free(hash);
138}
139
140idn_result_t
141idn__strhash_put(idn__strhash_t hash, const char *key, void *value) {
142	unsigned long h, h_index;
143	strhash_entry_t *entry;
144
145	assert(hash != NULL && key != NULL);
146
147	h = hash_value(key);
148	h_index = h % hash->nbins;
149
150	if ((entry = find_entry(hash->bins[h_index], key, h)) != NULL) {
151		/* Entry exists.  Replace the value. */
152		entry->value = value;
153	} else {
154		/* Create new entry. */
155		if ((entry = new_entry(key, value)) == NULL) {
156			return (idn_nomemory);
157		}
158		/* Insert it to the list. */
159		entry->next = hash->bins[h_index];
160		hash->bins[h_index] = entry;
161		hash->nelements++;
162
163		if (hash->nelements > hash->nbins * THRESHOLD) {
164			idn_result_t r;
165			r = expand_bins(hash, hash->nbins * FACTOR);
166			if (r != idn_success) {
167				TRACE(("idn__strhash_put: hash table "
168					"expansion failed\n"));
169			}
170		}
171	}
172
173	return (idn_success);
174}
175
176idn_result_t
177idn__strhash_get(idn__strhash_t hash, const char *key, void **valuep) {
178	unsigned long h;
179	strhash_entry_t *entry;
180
181	assert(hash != NULL && key != NULL && valuep != NULL);
182
183	h = hash_value(key);
184	entry = find_entry(hash->bins[h % hash->nbins], key, h);
185	if (entry == NULL)
186		return (idn_noentry);
187
188	*valuep = entry->value;
189	return (idn_success);
190}
191
192int
193idn__strhash_exists(idn__strhash_t hash, const char *key) {
194	unsigned long h;
195
196	assert(hash != NULL && key != NULL);
197
198	h = hash_value(key);
199	return (find_entry(hash->bins[h % hash->nbins], key, h) != NULL);
200}
201
202static unsigned long
203hash_value(const char *key) {
204	unsigned long h = 0;
205	unsigned char *p = (unsigned char *)key;
206	int c;
207
208	while ((c = *p++) != '\0') {
209		h = h * HASH_MULT + c;
210	}
211	return (h);
212}
213
214static strhash_entry_t *
215find_entry(strhash_entry_t *entry, const char *key, unsigned long hash) {
216	assert(key != NULL);
217
218	while (entry != NULL) {
219		if (entry->hash_value == hash && strcmp(key, entry->key) == 0)
220			return (entry);
221		entry = entry->next;
222	}
223	return (NULL);
224}
225
226static strhash_entry_t *
227new_entry(const char *key, void *value) {
228	strhash_entry_t *entry;
229	int len;
230
231	assert(key != NULL);
232
233	len = strlen(key) + 1;
234	if ((entry = malloc(sizeof(strhash_entry_t) + len)) == NULL) {
235		return (NULL);
236	}
237	entry->next = NULL;
238	entry->hash_value = hash_value(key);
239	entry->key = (char *)(entry + 1);
240	(void)strcpy(entry->key, key);
241	entry->value = value;
242
243	return (entry);
244}
245
246static idn_result_t
247expand_bins(idn__strhash_t hash, int new_size) {
248	strhash_entry_t **old_bins, **new_bins;
249	int old_size;
250	int old_index, new_index;
251
252	new_bins = malloc(sizeof(strhash_entry_t *) * new_size);
253	if (new_bins == NULL)
254		return (idn_nomemory);
255
256	memset(new_bins, 0, sizeof(strhash_entry_t *) * new_size);
257
258	old_bins = hash->bins;
259	old_size = hash->nbins;
260	for (old_index = 0; old_index < old_size; old_index++) {
261		strhash_entry_t *entries = old_bins[old_index];
262
263		while (entries != NULL) {
264			strhash_entry_t *e = entries;
265
266			/* Remove the top element from the linked list. */
267			entries = entries->next;
268
269			/* ..and move to the new hash. */
270			new_index = e->hash_value % new_size;
271			e->next = new_bins[new_index];
272			new_bins[new_index] = e;
273		}
274	}
275
276	hash->nbins = new_size;
277	hash->bins = new_bins;
278
279	if (old_bins != NULL)
280		free(old_bins);
281
282	return (idn_success);
283}
284