From e3b89230f065c48c84b48c88edb6eb088374c487 Mon Sep 17 00:00:00 2001 From: zautrix Date: Sat, 03 Jul 2004 16:33:12 +0000 Subject: Initial revision --- (limited to 'kmicromail/libetpan/tools/chash.c') diff --git a/kmicromail/libetpan/tools/chash.c b/kmicromail/libetpan/tools/chash.c new file mode 100644 index 0000000..2055221 --- a/dev/null +++ b/kmicromail/libetpan/tools/chash.c @@ -0,0 +1,395 @@ + +/* + * libEtPan! -- a mail stuff library + * + * chash - Implements generic hash tables. + * + * Copyright (c) 1999-2000, Gaël Roualland + * interface changes - 2002 - DINH Viet Hoa + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. Neither the name of the libEtPan! project nor the names of its + * contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +/* + * $Id$ + */ + +#include +#include + +#include "chash.h" + +/* This defines the maximum (average) number of entries per bucket. + The hash is resized everytime inserting an entry makes the + average go over that value. */ +#define CHASH_MAXDEPTH 3 + +static inline unsigned int chash_func(const char * key, unsigned int len) { +#if 0 + register unsigned int c = 0, t; + register const char * k = key; + + while (len--) { + c += (c << 4) + *k++; + if ((t = c & 0xF0000000)) { + c ^= t >> 24; + c ^= t; + } + } + return c; +#endif + register unsigned int c = 5381; + register const char * k = key; + + while (len--) { + c = ((c << 5) + c) + *k++; + } + + return c; +} + +static inline char * chash_dup(const void * data, unsigned int len) +{ + void * r; + + r = (char *) malloc(len); + if (!r) + return NULL; + memcpy(r, data, len); + return r; +} + +chash * chash_new(unsigned int size, int flags) +{ + chash * h; + + h = (chash *) malloc(sizeof(chash)); + if (h == NULL) + return NULL; + + h->count = 0; + h->cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *)); + if (h->cells == NULL) { + free(h); + return NULL; + } + h->size = size; + h->copykey = flags & CHASH_COPYKEY; + h->copyvalue = flags & CHASH_COPYVALUE; + + return h; +} + +int chash_get(chash * hash, + chashdatum * key, chashdatum * result) +{ + unsigned int func; + chashiter * iter; + + func = chash_func(key->data, key->len); + + /* look for the key in existing cells */ + iter = hash->cells[func % hash->size]; + while (iter) { + if (iter->key.len == key->len && iter->func == func + && !memcmp(iter->key.data, key->data, key->len)) { + * result = iter->value; /* found */ + + return 0; + } + iter = iter->next; + } + + return -1; +} + +int chash_set(chash * hash, + chashdatum * key, + chashdatum * value, + chashdatum * oldvalue) +{ + unsigned int func, indx; + chashiter * iter, * cell; + int r; + + if (hash->count > hash->size * CHASH_MAXDEPTH) { + r = chash_resize(hash, (hash->count / CHASH_MAXDEPTH) * 2 + 1); + if (r < 0) + goto err; + } + + func = chash_func(key->data, key->len); + indx = func % hash->size; + + /* look for the key in existing cells */ + iter = hash->cells[indx]; + while (iter) { + if (iter->key.len == key->len && iter->func == func + && !memcmp(iter->key.data, key->data, key->len)) { + /* found, replacing entry */ + if (hash->copyvalue) { + char * data; + + data = chash_dup(value->data, value->len); + if (data == NULL) + goto err; + + free(iter->value.data); + iter->value.data = data; + iter->value.len = value->len; + } else { + if (oldvalue != NULL) { + oldvalue->data = iter->value.data; + oldvalue->len = iter->value.len; + } + iter->value.data = value->data; + iter->value.len = value->len; + } + if (!hash->copykey) + iter->key.data = key->data; + + if (oldvalue != NULL) { + oldvalue->data = value->data; + oldvalue->len = value->len; + } + + return 0; + } + iter = iter->next; + } + + if (oldvalue != NULL) { + oldvalue->data = NULL; + oldvalue->len = 0; + } + + /* not found, adding entry */ + cell = (struct chashcell *) malloc(sizeof(struct chashcell)); + if (cell == NULL) + goto err; + + if (hash->copykey) { + cell->key.data = chash_dup(key->data, key->len); + if (cell->key.data == NULL) + goto free; + } + else + cell->key.data = key->data; + + cell->key.len = key->len; + if (hash->copyvalue) { + cell->value.data = chash_dup(value->data, value->len); + if (cell->value.data == NULL) + goto free_key_data; + } + else + cell->value.data = value->data; + + cell->value.len = value->len; + cell->func = func; + cell->next = hash->cells[indx]; + hash->cells[indx] = cell; + hash->count++; + + return 0; + + free_key_data: + if (hash->copykey) + free(cell->key.data); + free: + free(cell); + err: + return -1; +} + +int chash_delete(chash * hash, chashdatum * key, chashdatum * oldvalue) +{ + /* chashdatum result = { NULL, TRUE }; */ + unsigned int func, indx; + chashiter * iter, * old; + + /* + if (!keylen) + keylen = strlen(key) + 1; + */ + + func = chash_func(key->data, key->len); + indx = func % hash->size; + + /* look for the key in existing cells */ + old = NULL; + iter = hash->cells[indx]; + while (iter) { + if (iter->key.len == key->len && iter->func == func + && !memcmp(iter->key.data, key->data, key->len)) { + /* found, deleting */ + if (old) + old->next = iter->next; + else + hash->cells[indx] = iter->next; + if (hash->copykey) + free(iter->key.data); + if (hash->copyvalue) + free(iter->value.data); + else { + if (oldvalue != NULL) { + oldvalue->data = iter->value.data; + oldvalue->len = iter->value.len; + } + } + free(iter); + hash->count--; + return 0; + } + old = iter; + iter = iter->next; + } + + return -1; /* not found */ +} + +void chash_free(chash * hash) { + unsigned int indx; + chashiter * iter, * next; + + /* browse the hash table */ + for(indx = 0; indx < hash->size; indx++) { + iter = hash->cells[indx]; + while (iter) { + next = iter->next; + if (hash->copykey) + free(iter->key.data); + if (hash->copyvalue) + free(iter->value.data); + free(iter); + iter = next; + } + } + free(hash->cells); + free(hash); +} + +void chash_clear(chash * hash) { + unsigned int indx; + chashiter * iter, * next; + + /* browse the hash table */ + for(indx = 0; indx < hash->size; indx++) { + iter = hash->cells[indx]; + while (iter) { + next = iter->next; + if (hash->copykey) + free(iter->key.data); + if (hash->copyvalue) + free(iter->value.data); + free(iter); + iter = next; + } + } + memset(hash->cells, 0, hash->size * sizeof(* hash->cells)); + hash->count = 0; +} + +chashiter * chash_begin(chash * hash) { + chashiter * iter; + unsigned int indx = 0; + + iter = hash->cells[0]; + while(!iter) { + indx++; + if (indx >= hash->size) + return NULL; + iter = hash->cells[indx]; + } + return iter; +} + +chashiter * chash_next(chash * hash, chashiter * iter) { + unsigned int indx; + + if (!iter) + return NULL; + + indx = iter->func % hash->size; + iter = iter->next; + + while(!iter) { + indx++; + if (indx >= hash->size) + return NULL; + iter = hash->cells[indx]; + } + return iter; +} + +int chash_resize(chash * hash, unsigned int size) +{ + struct chashcell ** cells; + unsigned int indx, nindx; + chashiter * iter, * next; + + if (hash->size == size) + return 0; + + cells = (struct chashcell **) calloc(size, sizeof(struct chashcell *)); + if (!cells) + return -1; + + /* browse initial hash and copy items in second hash */ + for(indx = 0; indx < hash->size; indx++) { + iter = hash->cells[indx]; + while (iter) { + next = iter->next; + nindx = iter->func % size; + iter->next = cells[nindx]; + cells[nindx] = iter; + iter = next; + } + } + free(hash->cells); + hash->size = size; + hash->cells = cells; + + return 0; +} + +#ifdef NO_MACROS +int chash_count(chash * hash) { + return hash->count; +} + +int chash_size(chash * hash) { + return hash->size; +} + +void chash_value(chashiter * iter, chashdatum * result) { + * result = iter->value; +} + +void chash_key(chashiter * iter, chashdatum * result) { + * result = iter->key; +} +#endif -- cgit v0.9.0.2