summaryrefslogtreecommitdiffabout
path: root/kmicromail/libetpan/tools/chash.c
Side-by-side diff
Diffstat (limited to 'kmicromail/libetpan/tools/chash.c') (more/less context) (ignore whitespace changes)
-rw-r--r--kmicromail/libetpan/tools/chash.c395
1 files changed, 395 insertions, 0 deletions
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 <gael.roualland@iname.com>
+ * 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 <stdlib.h>
+#include <string.h>
+
+#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