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