Diffstat (limited to 'libetpan/src/data-types/chash.c') (more/less context) (show whitespace changes)
-rw-r--r-- | libetpan/src/data-types/chash.c | 394 |
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 | |||
49 | static 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 | |||
73 | static 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 | |||
84 | chash * 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 | |||
105 | int 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 | |||
128 | int 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 | |||
227 | int 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 | |||
273 | void 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 | |||
294 | void 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 | |||
315 | chashiter * 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 | |||
329 | chashiter * 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 | |||
347 | int 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 | ||
379 | int chash_count(chash * hash) { | ||
380 | return hash->count; | ||
381 | } | ||
382 | |||
383 | int chash_size(chash * hash) { | ||
384 | return hash->size; | ||
385 | } | ||
386 | |||
387 | void chash_value(chashiter * iter, chashdatum * result) { | ||
388 | * result = iter->value; | ||
389 | } | ||
390 | |||
391 | void chash_key(chashiter * iter, chashdatum * result) { | ||
392 | * result = iter->key; | ||
393 | } | ||
394 | #endif | ||