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