summaryrefslogtreecommitdiff
path: root/lib/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/hash.c')
-rw-r--r--lib/hash.c271
1 files changed, 271 insertions, 0 deletions
diff --git a/lib/hash.c b/lib/hash.c
new file mode 100644
index 000000000..c0680e488
--- /dev/null
+++ b/lib/hash.c
@@ -0,0 +1,271 @@
+/*****************************************************************************
+ * _ _ ____ _
+ * Project ___| | | | _ \| |
+ * / __| | | | |_) | |
+ * | (__| |_| | _ <| |___
+ * \___|\___/|_| \_\_____|
+ *
+ * Copyright (C) 2001, Daniel Stenberg, <daniel@haxx.se>, et al
+ *
+ * In order to be useful for every potential user, curl and libcurl are
+ * dual-licensed under the MPL and the MIT/X-derivate licenses.
+ *
+ * You may opt to use, copy, modify, merge, publish, distribute and/or sell
+ * copies of the Software, and permit persons to whom the Software is
+ * furnished to do so, under the terms of the MPL or the MIT/X-derivate
+ * licenses. You may pick one of these licenses.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ * $Id$
+ *****************************************************************************/
+
+#include "setup.h"
+
+#include <string.h>
+
+#include "hash.h"
+#include "llist.h"
+
+#ifdef MALLOCDEBUG
+/* this must be the last include file */
+#include "memdebug.h"
+#endif
+
+
+static unsigned long
+curl_hash_str(const char *key, unsigned int key_length)
+{
+ register unsigned long h = 0;
+ register unsigned long g;
+ register char *p = (char *) key;
+ register char *end = (char *) key + key_length;
+
+ while (p < end) {
+ h = (h << 4) + *p++;
+ if ((g = (h & 0xF0000000))) {
+ h = h ^ (g >> 24);
+ h = h ^ g;
+ }
+ }
+
+ return h;
+}
+
+static unsigned long
+curl_hash_num(unsigned long key)
+{
+ key += ~(key << 15);
+ key ^= (key >> 10);
+ key += (key << 3);
+ key ^= (key >> 6);
+ key += (key << 11);
+ key ^= (key >> 16);
+
+ return key;
+}
+
+static void
+hash_element_dtor(void *u, void *ele)
+{
+ curl_hash_element *e = (curl_hash_element *) ele;
+ curl_hash *h = (curl_hash *) u;
+
+ if (e->key.type == CURL_HASH_KEY_IS_STRING) {
+ free(e->key.value.str.val);
+ }
+ h->dtor(e->ptr);
+
+ free(e);
+ e = NULL;
+}
+
+void
+curl_hash_init(curl_hash *h, int slots, curl_hash_dtor dtor)
+{
+ int i;
+
+ h->dtor = dtor;
+ h->size = 0;
+ h->slots = slots;
+
+ h->table = (curl_llist **) malloc(slots * sizeof(curl_llist *));
+ for (i = 0; i < h->slots; ++i) {
+ h->table[i] = curl_llist_alloc((curl_llist_dtor) hash_element_dtor);
+ }
+}
+
+curl_hash *
+curl_hash_alloc(int slots, curl_hash_dtor dtor)
+{
+ curl_hash *h;
+
+ h = malloc(sizeof(curl_hash));
+ curl_hash_init(h, slots, dtor);
+
+ return h;
+}
+
+#define FIND_SLOT(__h, __s_key, __s_key_len, __n_key) \
+ ((__s_key ? curl_hash_str(__s_key, __s_key_len) : curl_hash_num(__n_key)) % (__h)->slots)
+
+#define KEY_CREATE(__k, __s_key, __s_key_len, __n_key, __dup) \
+ if (__s_key) { \
+ if (__dup) { \
+ (__k)->value.str.val = (char *) malloc(__s_key_len); \
+ memcpy((__k)->value.str.val, __s_key, __s_key_len); \
+ } else { \
+ (__k)->value.str.val = __s_key; \
+ } \
+ (__k)->value.str.len = __s_key_len; \
+ (__k)->type = CURL_HASH_KEY_IS_STRING; \
+ } else { \
+ (__k)->value.num = __n_key; \
+ (__k)->type = CURL_HASH_KEY_IS_NUM; \
+ }
+
+#define MIN(a, b) (a > b ? b : a)
+
+static int
+curl_hash_key_compare(curl_hash_key *key1, curl_hash_key *key2)
+{
+ if (key1->type == CURL_HASH_KEY_IS_NUM) {
+ if (key2->type == CURL_HASH_KEY_IS_STRING)
+ return 0;
+
+ if (key1->value.num == key2->value.num)
+ return 1;
+ } else {
+ if (key2->type == CURL_HASH_KEY_IS_NUM)
+ return 0;
+
+ if (memcmp(key1->value.str.val, key2->value.str.val,
+ MIN(key1->value.str.len, key2->value.str.len)) == 0)
+ return 1;
+ }
+
+ return 0;
+}
+
+int
+curl_hash_add_or_update(curl_hash *h, char *str_key, unsigned int str_key_len,
+ unsigned long num_key, const void *p)
+{
+ curl_hash_element *e;
+ curl_hash_key tmp;
+ curl_llist *l;
+ curl_llist_element *le;
+ int slot;
+
+ slot = FIND_SLOT(h, str_key, str_key_len, num_key);
+ l = h->table[slot];
+ KEY_CREATE(&tmp, str_key, str_key_len, num_key, 0);
+ for (le = CURL_LLIST_HEAD(l); le != NULL; le = CURL_LLIST_NEXT(le)) {
+ if (curl_hash_key_compare(&tmp, &((curl_hash_element *) CURL_LLIST_VALP(le))->key)) {
+ curl_hash_element *to_update = CURL_LLIST_VALP(le);
+ h->dtor(to_update->ptr);
+ to_update->ptr = (void *) p;
+ return 1;
+ }
+ }
+
+ e = (curl_hash_element *) malloc(sizeof(curl_hash_element));
+ KEY_CREATE(&e->key, str_key, str_key_len, num_key, 1);
+ e->ptr = (void *) p;
+
+ if (curl_llist_insert_next(l, CURL_LLIST_TAIL(l), e)) {
+ ++h->size;
+ return 1;
+ } else {
+ return 0;
+ }
+}
+
+int
+curl_hash_extended_delete(curl_hash *h, char *str_key, unsigned int str_key_len,
+ unsigned long num_key)
+{
+ curl_llist *l;
+ curl_llist_element *le;
+ curl_hash_key tmp;
+ int slot;
+
+ slot = FIND_SLOT(h, str_key, str_key_len, num_key);
+ l = h->table[slot];
+
+ KEY_CREATE(&tmp, str_key, str_key_len, num_key, 0);
+ for (le = CURL_LLIST_HEAD(l); le != NULL; le = CURL_LLIST_NEXT(le)) {
+ if (curl_hash_key_compare(&tmp, &((curl_hash_element *) CURL_LLIST_VALP(le))->key)) {
+ curl_llist_remove(l, le, (void *) h);
+ --h->size;
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+int
+curl_hash_extended_find(curl_hash *h, char *str_key, unsigned int str_key_len,
+ unsigned long num_key, void **p)
+{
+ curl_llist *l;
+ curl_llist_element *le;
+ curl_hash_key tmp;
+ int slot;
+
+ slot = FIND_SLOT(h, str_key, str_key_len, num_key);
+ l = h->table[slot];
+
+ KEY_CREATE(&tmp, str_key, str_key_len, num_key, 0);
+ for (le = CURL_LLIST_HEAD(l); le != NULL; le = CURL_LLIST_NEXT(le)) {
+ if (curl_hash_key_compare(&tmp, &((curl_hash_element *) CURL_LLIST_VALP(le))->key)) {
+ *p = ((curl_hash_element *) CURL_LLIST_VALP(le))->ptr;
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+void
+curl_hash_apply(curl_hash *h, void *user, void (*cb)(void *, curl_hash_element *))
+{
+ curl_llist_element *le;
+ int i;
+
+ for (i = 0; i < h->slots; ++i) {
+ for (le = CURL_LLIST_HEAD(h->table[i]); le != NULL; le = CURL_LLIST_NEXT(le)) {
+ cb(user, (curl_hash_element *) CURL_LLIST_VALP(le));
+ }
+ }
+}
+
+void
+curl_hash_clean(curl_hash *h)
+{
+ int i;
+
+ for (i = 0; i < h->slots; ++i) {
+ curl_llist_destroy(h->table[i], (void *) h);
+ }
+
+ free(h->table);
+ h->table = NULL;
+}
+
+void
+curl_hash_destroy(curl_hash *h)
+{
+ curl_hash_clean(h);
+ free(h);
+}
+
+/*
+ * local variables:
+ * eval: (load-file "../curl-mode.el")
+ * end:
+ * vim600: fdm=marker
+ * vim: et sw=2 ts=2 sts=2 tw=78
+ */