3 * libEtPan! -- a mail stuff library
5 * chash - Implements generic hash tables.
7 * Copyright (c) 1999-2000, Gaƫl Roualland <gael.roualland@iname.com>
8 * interface changes - 2002 - DINH Viet Hoa
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
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.
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
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
50 static inline unsigned int chash_func(const char * key, unsigned int len) {
52 register unsigned int c = 0, t;
53 register const char * k = key;
57 if ((t = c & 0xF0000000)) {
64 register unsigned int c = 5381;
65 register const char * k = key;
68 c = ((c << 5) + c) + *k++;
74 static inline char * chash_dup(const void * data, unsigned int len)
78 r = (char *) malloc(len);
85 chash * chash_new(unsigned int size, int flags)
89 h = (chash *) malloc(sizeof(chash));
94 h->cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *));
95 if (h->cells == NULL) {
100 h->copykey = flags & CHASH_COPYKEY;
101 h->copyvalue = flags & CHASH_COPYVALUE;
106 int chash_get(chash * hash,
107 chashdatum * key, chashdatum * result)
112 func = chash_func(key->data, key->len);
114 /* look for the key in existing cells */
115 iter = hash->cells[func % hash->size];
117 if (iter->key.len == key->len && iter->func == func
118 && !memcmp(iter->key.data, key->data, key->len)) {
119 * result = iter->value; /* found */
129 int chash_set(chash * hash,
132 chashdatum * oldvalue)
134 unsigned int func, indx;
135 chashiter * iter, * cell;
138 if (hash->count > hash->size * CHASH_MAXDEPTH) {
139 r = chash_resize(hash, (hash->count / CHASH_MAXDEPTH) * 2 + 1);
144 func = chash_func(key->data, key->len);
145 indx = func % hash->size;
147 /* look for the key in existing cells */
148 iter = hash->cells[indx];
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) {
156 data = chash_dup(value->data, value->len);
160 free(iter->value.data);
161 iter->value.data = data;
162 iter->value.len = value->len;
164 if (oldvalue != NULL) {
165 oldvalue->data = iter->value.data;
166 oldvalue->len = iter->value.len;
168 iter->value.data = value->data;
169 iter->value.len = value->len;
172 iter->key.data = key->data;
174 if (oldvalue != NULL) {
175 oldvalue->data = value->data;
176 oldvalue->len = value->len;
184 if (oldvalue != NULL) {
185 oldvalue->data = NULL;
189 /* not found, adding entry */
190 cell = (struct chashcell *) malloc(sizeof(struct chashcell));
195 cell->key.data = chash_dup(key->data, key->len);
196 if (cell->key.data == NULL)
200 cell->key.data = key->data;
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)
209 cell->value.data = value->data;
211 cell->value.len = value->len;
213 cell->next = hash->cells[indx];
214 hash->cells[indx] = cell;
221 free(cell->key.data);
228 int chash_delete(chash * hash, chashdatum * key, chashdatum * oldvalue)
230 /* chashdatum result = { NULL, TRUE }; */
231 unsigned int func, indx;
232 chashiter * iter, * old;
236 keylen = strlen(key) + 1;
239 func = chash_func(key->data, key->len);
240 indx = func % hash->size;
242 /* look for the key in existing cells */
244 iter = hash->cells[indx];
246 if (iter->key.len == key->len && iter->func == func
247 && !memcmp(iter->key.data, key->data, key->len)) {
248 /* found, deleting */
250 old->next = iter->next;
252 hash->cells[indx] = iter->next;
254 free(iter->key.data);
256 free(iter->value.data);
258 if (oldvalue != NULL) {
259 oldvalue->data = iter->value.data;
260 oldvalue->len = iter->value.len;
271 return -1; /* not found */
274 void chash_free(chash * hash) {
276 chashiter * iter, * next;
278 /* browse the hash table */
279 for(indx = 0; indx < hash->size; indx++) {
280 iter = hash->cells[indx];
284 free(iter->key.data);
286 free(iter->value.data);
295 void chash_clear(chash * hash) {
297 chashiter * iter, * next;
299 /* browse the hash table */
300 for(indx = 0; indx < hash->size; indx++) {
301 iter = hash->cells[indx];
305 free(iter->key.data);
307 free(iter->value.data);
312 memset(hash->cells, 0, hash->size * sizeof(* hash->cells));
316 chashiter * chash_begin(chash * hash) {
318 unsigned int indx = 0;
320 iter = hash->cells[0];
323 if (indx >= hash->size)
325 iter = hash->cells[indx];
330 chashiter * chash_next(chash * hash, chashiter * iter) {
336 indx = iter->func % hash->size;
341 if (indx >= hash->size)
343 iter = hash->cells[indx];
348 int chash_resize(chash * hash, unsigned int size)
350 struct chashcell ** cells;
351 unsigned int indx, nindx;
352 chashiter * iter, * next;
354 if (hash->size == size)
357 cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *));
361 /* browse initial hash and copy items in second hash */
362 for(indx = 0; indx < hash->size; indx++) {
363 iter = hash->cells[indx];
366 nindx = iter->func % size;
367 iter->next = cells[nindx];
380 int chash_count(chash * hash) {
384 int chash_size(chash * hash) {
388 void chash_value(chashiter * iter, chashdatum * result) {
389 * result = iter->value;
392 void chash_key(chashiter * iter, chashdatum * result) {
393 * result = iter->key;