1
2 /*
3 * libEtPan! -- a mail stuff library
4 *
5 * chash - Implements generic hash tables.
6 *
7 * Copyright (c) 1999-2000, Ga�l Roualland <gael.roualland@iname.com>
8 * interface changes - 2002 - DINH Viet Hoa
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. Neither the name of the libEtPan! project nor the names of its
20 * contributors may be used to endorse or promote products derived
21 * from this software without specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 * SUCH DAMAGE.
34 */
35
36 /*
37 * $Id$
38 */
39
40 #include <stdlib.h>
41 #include <string.h>
42
43 #include "chash.h"
44
45 /* This defines the maximum (average) number of entries per bucket.
46 The hash is resized everytime inserting an entry makes the
47 average go over that value. */
48 #define CHASH_MAXDEPTH 3
49
chash_func(const char * key,unsigned int len)50 static inline unsigned int chash_func(const char * key, unsigned int len) {
51 #if 0
52 register unsigned int c = 0, t;
53 register const char * k = key;
54
55 while (len--) {
56 c += (c << 4) + *k++;
57 if ((t = c & 0xF0000000)) {
58 c ^= t >> 24;
59 c ^= t;
60 }
61 }
62 return c;
63 #endif
64 register unsigned int c = 5381;
65 register const char * k = key;
66
67 while (len--) {
68 c = ((c << 5) + c) + *k++;
69 }
70
71 return c;
72 }
73
chash_dup(const void * data,unsigned int len)74 static inline char * chash_dup(const void * data, unsigned int len)
75 {
76 void * r;
77
78 r = (char *) malloc(len);
79 if (!r)
80 return NULL;
81 memcpy(r, data, len);
82 return r;
83 }
84
chash_new(unsigned int size,int flags)85 chash * chash_new(unsigned int size, int flags)
86 {
87 chash * h;
88
89 h = (chash *) malloc(sizeof(chash));
90 if (h == NULL)
91 return NULL;
92
93 h->count = 0;
94 h->cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *));
95 if (h->cells == NULL) {
96 free(h);
97 return NULL;
98 }
99 h->size = size;
100 h->copykey = flags & CHASH_COPYKEY;
101 h->copyvalue = flags & CHASH_COPYVALUE;
102
103 return h;
104 }
105
chash_get(chash * hash,chashdatum * key,chashdatum * result)106 int chash_get(chash * hash,
107 chashdatum * key, chashdatum * result)
108 {
109 unsigned int func;
110 chashiter * iter;
111
112 func = chash_func(key->data, key->len);
113
114 /* look for the key in existing cells */
115 iter = hash->cells[func % hash->size];
116 while (iter) {
117 if (iter->key.len == key->len && iter->func == func
118 && !memcmp(iter->key.data, key->data, key->len)) {
119 * result = iter->value; /* found */
120
121 return 0;
122 }
123 iter = iter->next;
124 }
125
126 return -1;
127 }
128
chash_set(chash * hash,chashdatum * key,chashdatum * value,chashdatum * oldvalue)129 int chash_set(chash * hash,
130 chashdatum * key,
131 chashdatum * value,
132 chashdatum * oldvalue)
133 {
134 unsigned int func, indx;
135 chashiter * iter, * cell;
136 int r;
137
138 if (hash->count > hash->size * CHASH_MAXDEPTH) {
139 r = chash_resize(hash, (hash->count / CHASH_MAXDEPTH) * 2 + 1);
140 if (r < 0)
141 goto err;
142 }
143
144 func = chash_func(key->data, key->len);
145 indx = func % hash->size;
146
147 /* look for the key in existing cells */
148 iter = hash->cells[indx];
149 while (iter) {
150 if (iter->key.len == key->len && iter->func == func
151 && !memcmp(iter->key.data, key->data, key->len)) {
152 /* found, replacing entry */
153 if (hash->copyvalue) {
154 char * data;
155
156 data = chash_dup(value->data, value->len);
157 if (data == NULL)
158 goto err;
159
160 free(iter->value.data);
161 iter->value.data = data;
162 iter->value.len = value->len;
163 } else {
164 if (oldvalue != NULL) {
165 oldvalue->data = iter->value.data;
166 oldvalue->len = iter->value.len;
167 }
168 iter->value.data = value->data;
169 iter->value.len = value->len;
170 }
171 if (!hash->copykey)
172 iter->key.data = key->data;
173
174 if (oldvalue != NULL) {
175 oldvalue->data = value->data;
176 oldvalue->len = value->len;
177 }
178
179 return 0;
180 }
181 iter = iter->next;
182 }
183
184 if (oldvalue != NULL) {
185 oldvalue->data = NULL;
186 oldvalue->len = 0;
187 }
188
189 /* not found, adding entry */
190 cell = (struct chashcell *) malloc(sizeof(struct chashcell));
191 if (cell == NULL)
192 goto err;
193
194 if (hash->copykey) {
195 cell->key.data = chash_dup(key->data, key->len);
196 if (cell->key.data == NULL)
197 goto free;
198 }
199 else
200 cell->key.data = key->data;
201
202 cell->key.len = key->len;
203 if (hash->copyvalue) {
204 cell->value.data = chash_dup(value->data, value->len);
205 if (cell->value.data == NULL)
206 goto free_key_data;
207 }
208 else
209 cell->value.data = value->data;
210
211 cell->value.len = value->len;
212 cell->func = func;
213 cell->next = hash->cells[indx];
214 hash->cells[indx] = cell;
215 hash->count++;
216
217 return 0;
218
219 free_key_data:
220 if (hash->copykey)
221 free(cell->key.data);
222 free:
223 free(cell);
224 err:
225 return -1;
226 }
227
chash_delete(chash * hash,chashdatum * key,chashdatum * oldvalue)228 int chash_delete(chash * hash, chashdatum * key, chashdatum * oldvalue)
229 {
230 /* chashdatum result = { NULL, TRUE }; */
231 unsigned int func, indx;
232 chashiter * iter, * old;
233
234 /*
235 if (!keylen)
236 keylen = strlen(key) + 1;
237 */
238
239 func = chash_func(key->data, key->len);
240 indx = func % hash->size;
241
242 /* look for the key in existing cells */
243 old = NULL;
244 iter = hash->cells[indx];
245 while (iter) {
246 if (iter->key.len == key->len && iter->func == func
247 && !memcmp(iter->key.data, key->data, key->len)) {
248 /* found, deleting */
249 if (old)
250 old->next = iter->next;
251 else
252 hash->cells[indx] = iter->next;
253 if (hash->copykey)
254 free(iter->key.data);
255 if (hash->copyvalue)
256 free(iter->value.data);
257 else {
258 if (oldvalue != NULL) {
259 oldvalue->data = iter->value.data;
260 oldvalue->len = iter->value.len;
261 }
262 }
263 free(iter);
264 hash->count--;
265 return 0;
266 }
267 old = iter;
268 iter = iter->next;
269 }
270
271 return -1; /* not found */
272 }
273
chash_free(chash * hash)274 void chash_free(chash * hash) {
275 unsigned int indx;
276 chashiter * iter, * next;
277
278 /* browse the hash table */
279 for(indx = 0; indx < hash->size; indx++) {
280 iter = hash->cells[indx];
281 while (iter) {
282 next = iter->next;
283 if (hash->copykey)
284 free(iter->key.data);
285 if (hash->copyvalue)
286 free(iter->value.data);
287 free(iter);
288 iter = next;
289 }
290 }
291 free(hash->cells);
292 free(hash);
293 }
294
chash_clear(chash * hash)295 void chash_clear(chash * hash) {
296 unsigned int indx;
297 chashiter * iter, * next;
298
299 /* browse the hash table */
300 for(indx = 0; indx < hash->size; indx++) {
301 iter = hash->cells[indx];
302 while (iter) {
303 next = iter->next;
304 if (hash->copykey)
305 free(iter->key.data);
306 if (hash->copyvalue)
307 free(iter->value.data);
308 free(iter);
309 iter = next;
310 }
311 }
312 memset(hash->cells, 0, hash->size * sizeof(* hash->cells));
313 hash->count = 0;
314 }
315
chash_begin(chash * hash)316 chashiter * chash_begin(chash * hash) {
317 chashiter * iter;
318 unsigned int indx = 0;
319
320 iter = hash->cells[0];
321 while(!iter) {
322 indx++;
323 if (indx >= hash->size)
324 return NULL;
325 iter = hash->cells[indx];
326 }
327 return iter;
328 }
329
chash_next(chash * hash,chashiter * iter)330 chashiter * chash_next(chash * hash, chashiter * iter) {
331 unsigned int indx;
332
333 if (!iter)
334 return NULL;
335
336 indx = iter->func % hash->size;
337 iter = iter->next;
338
339 while(!iter) {
340 indx++;
341 if (indx >= hash->size)
342 return NULL;
343 iter = hash->cells[indx];
344 }
345 return iter;
346 }
347
chash_resize(chash * hash,unsigned int size)348 int chash_resize(chash * hash, unsigned int size)
349 {
350 struct chashcell ** cells;
351 unsigned int indx, nindx;
352 chashiter * iter, * next;
353
354 if (hash->size == size)
355 return 0;
356
357 cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *));
358 if (!cells)
359 return -1;
360
361 /* browse initial hash and copy items in second hash */
362 for(indx = 0; indx < hash->size; indx++) {
363 iter = hash->cells[indx];
364 while (iter) {
365 next = iter->next;
366 nindx = iter->func % size;
367 iter->next = cells[nindx];
368 cells[nindx] = iter;
369 iter = next;
370 }
371 }
372 free(hash->cells);
373 hash->size = size;
374 hash->cells = cells;
375
376 return 0;
377 }
378
379 #ifdef NO_MACROS
chash_count(chash * hash)380 int chash_count(chash * hash) {
381 return hash->count;
382 }
383
chash_size(chash * hash)384 int chash_size(chash * hash) {
385 return hash->size;
386 }
387
chash_value(chashiter * iter,chashdatum * result)388 void chash_value(chashiter * iter, chashdatum * result) {
389 * result = iter->value;
390 }
391
chash_key(chashiter * iter,chashdatum * result)392 void chash_key(chashiter * iter, chashdatum * result) {
393 * result = iter->key;
394 }
395 #endif
396