1 #ifndef lint
2 static char *rcsid = "$Id: strhash.c,v 1.12 2002/11/29 09:08:05 ishisone 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
70 typedef struct strhash_entry {
71 struct strhash_entry *next;
72 unsigned long hash_value;
73 char *key;
74 void *value;
75 } strhash_entry_t;
76
77 struct idn__strhash {
78 int nbins;
79 int nelements;
80 strhash_entry_t **bins;
81 };
82
83 static unsigned long hash_value(const char *key);
84 static strhash_entry_t *find_entry(strhash_entry_t *entry, const char *key,
85 unsigned long hash);
86 static strhash_entry_t *new_entry(const char *key, void *value);
87 static idn_result_t expand_bins(idn__strhash_t hash, int new_size);
88
89 idn_result_t
idn__strhash_create(idn__strhash_t * hashp)90 idn__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
118 void
idn__strhash_destroy(idn__strhash_t hash,idn__strhash_freeproc_t proc)119 idn__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
140 idn_result_t
idn__strhash_put(idn__strhash_t hash,const char * key,void * value)141 idn__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
176 idn_result_t
idn__strhash_get(idn__strhash_t hash,const char * key,void ** valuep)177 idn__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
192 int
idn__strhash_exists(idn__strhash_t hash,const char * key)193 idn__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
202 static unsigned long
hash_value(const char * key)203 hash_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
214 static strhash_entry_t *
find_entry(strhash_entry_t * entry,const char * key,unsigned long hash)215 find_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
226 static strhash_entry_t *
new_entry(const char * key,void * value)227 new_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
246 static idn_result_t
expand_bins(idn__strhash_t hash,int new_size)247 expand_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