aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSterling Hughes <sterling@bumblebury.com>2002-04-12 23:40:19 +0000
committerSterling Hughes <sterling@bumblebury.com>2002-04-12 23:40:19 +0000
commit9ebcfe9dff762ee1f294b851fd2872fab032455a (patch)
tree0d1787f406132ea2faeb4cb8ad1a72de47b0c71f
parentf339bf613cfc16bab12e0c3bd582553f627df546 (diff)
Speed up the hash code considerably, removing a bunch of legacy crud
-rw-r--r--lib/hash.c219
-rw-r--r--lib/hash.h50
2 files changed, 115 insertions, 154 deletions
diff --git a/lib/hash.c b/lib/hash.c
index e2d577c28..13311e205 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -34,55 +34,45 @@
#endif
-static unsigned long
-curl_hash_str(const char *key, unsigned int key_length)
+/* {{{ static unsigned long _hash_str (const char *, size_t)
+ */
+static unsigned long
+_hash_str (const char *key, size_t 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;
- }
+ char *end = (char *) key + key_length;
+ unsigned long h = 5381;
+
+ while (key < end) {
+ h += h << 5;
+ h ^= (unsigned long) *key++;
}
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 *, void *)
+ */
static void
-hash_element_dtor(void *u, void *ele)
+_hash_element_dtor (void *user, void *element)
{
- 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);
+ curl_hash *h = (curl_hash *) user;
+ curl_hash_element *e = (curl_hash_element *) element;
+
+ if (e->key) {
+ free(e->key);
}
+
h->dtor(e->ptr);
free(e);
- e = NULL;
}
+/* }}} */
+/* {{{ void curl_hash_init (curl_hash *, int, curl_hash_dtor)
+ */
void
-curl_hash_init(curl_hash *h, int slots, curl_hash_dtor dtor)
+curl_hash_init (curl_hash *h, int slots, curl_hash_dtor dtor)
{
int i;
@@ -91,115 +81,108 @@ curl_hash_init(curl_hash *h, int slots, curl_hash_dtor dtor)
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);
+ for (i = 0; i < slots; ++i) {
+ h->table[i] = curl_llist_alloc((curl_llist_dtor) _hash_element_dtor);
}
}
+/* }}} */
+/* {{{ curl_hash *curl_hash_alloc (int, curl_hash_dtor)
+ */
curl_hash *
-curl_hash_alloc(int slots, curl_hash_dtor dtor)
+curl_hash_alloc (int slots, curl_hash_dtor dtor)
{
curl_hash *h;
- h = (curl_hash *)malloc(sizeof(curl_hash));
- if(NULL == h)
+ h = (curl_hash *) malloc(sizeof(curl_hash));
+ if (NULL == h)
return NULL;
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 _hash_key_compare (char *, size_t, char *, size_t)
+ */
static int
-curl_hash_key_compare(curl_hash_key *key1, curl_hash_key *key2)
+_hash_key_compare (char *key1, size_t key1_len, char *key2, size_t key2_len)
{
- if (key1->type == CURL_HASH_KEY_IS_NUM) {
- if (key2->type == CURL_HASH_KEY_IS_STRING)
- return 0;
+ if (key1_len == key2_len &&
+ *key1 == *key2 &&
+ memcmp(key1, key2, key1_len) == 0) {
+ return 1;
+ }
- if (key1->value.num == key2->value.num)
- return 1;
- } else {
- if (key2->type == CURL_HASH_KEY_IS_NUM)
- return 0;
+ return 0;
+}
+/* }}} */
- if (memcmp(key1->value.str.val, key2->value.str.val,
- MIN(key1->value.str.len, key2->value.str.len)) == 0)
- return 1;
- }
+/* {{{ static int _mk_hash_element (curl_hash_element **, char *, size_t, const void *)
+ */
+static int
+_mk_hash_element (curl_hash_element **e, char *key, size_t key_len, const void *p)
+{
+ *e = (curl_hash_element *) malloc(sizeof(curl_hash_element));
+ (*e)->key = strdup(key);
+ (*e)->key_len = key_len;
+ (*e)->ptr = (void *) p;
return 0;
}
+/* }}} */
+
+#define find_slot(__h, __k, __k_len) (_hash_str(__k, __k_len) % (__h)->slots)
+
+#define FETCH_LIST \
+ curl_llist *l = h->table[find_slot(h, key, key_len)]
+
+/* {{{ int curl_hash_add (curl_hash *, char *, size_t, const void *)
+ */
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_add (curl_hash *h, char *key, size_t key_len, const void *p)
{
- curl_hash_element *e;
- curl_hash_key tmp;
- curl_llist *l;
+ curl_hash_element *he;
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;
+ FETCH_LIST;
+
+ for (le = CURL_LLIST_HEAD(l);
+ le != NULL;
+ le = CURL_LLIST_NEXT(le)) {
+ he = (curl_hash_element *) CURL_LLIST_VALP(le);
+ if (_hash_key_compare(he->key, he->key_len, key, key_len)) {
+ h->dtor(he->ptr);
+ he->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 (_mk_hash_element(&he, key, key_len, p) != 0)
+ return 0;
- if (curl_llist_insert_next(l, CURL_LLIST_TAIL(l), e)) {
+ if (curl_llist_insert_next(l, CURL_LLIST_TAIL(l), he)) {
++h->size;
return 1;
- } else {
- return 0;
}
+
+ return 0;
}
+/* }}} */
int
-curl_hash_extended_delete(curl_hash *h, char *str_key, unsigned int str_key_len,
- unsigned long num_key)
+curl_hash_delete(curl_hash *h, char *key, size_t key_len)
{
- curl_llist *l;
+ curl_hash_element *he;
curl_llist_element *le;
- curl_hash_key tmp;
- int slot;
+ FETCH_LIST;
- 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)) {
+ for (le = CURL_LLIST_HEAD(l);
+ le != NULL;
+ le = CURL_LLIST_NEXT(le)) {
+ he = CURL_LLIST_VALP(le);
+ if (_hash_key_compare(he->key, he->key_len, key, key_len)) {
curl_llist_remove(l, le, (void *) h);
--h->size;
return 1;
@@ -210,21 +193,18 @@ curl_hash_extended_delete(curl_hash *h, char *str_key, unsigned int str_key_len,
}
int
-curl_hash_extended_find(curl_hash *h, char *str_key, unsigned int str_key_len,
- unsigned long num_key, void **p)
+curl_hash_find(curl_hash *h, char *key, size_t key_len, 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;
+ curl_hash_element *he;
+ FETCH_LIST;
+
+ for (le = CURL_LLIST_HEAD(l);
+ le != NULL;
+ le = CURL_LLIST_NEXT(le)) {
+ he = CURL_LLIST_VALP(le);
+ if (_hash_key_compare(he->key, he->key_len, key, key_len)) {
+ *p = he->ptr;
return 1;
}
}
@@ -255,7 +235,6 @@ curl_hash_clean(curl_hash *h)
}
free(h->table);
- h->table = NULL;
}
size_t
@@ -267,13 +246,11 @@ curl_hash_count(curl_hash *h)
void
curl_hash_destroy(curl_hash *h)
{
- if (!h) {
+ if (!h)
return;
- }
curl_hash_clean(h);
free(h);
- h = NULL;
}
/*
diff --git a/lib/hash.h b/lib/hash.h
index ecbcab3bb..6aa71b318 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -29,9 +29,6 @@
#include "llist.h"
-#define CURL_HASH_KEY_IS_STRING 0
-#define CURL_HASH_KEY_IS_NUM 1
-
typedef void (*curl_hash_dtor)(void *);
typedef struct _curl_hash {
@@ -41,45 +38,32 @@ typedef struct _curl_hash {
size_t size;
} curl_hash;
-typedef struct _curl_hash_key {
- union {
- struct {
- char *val;
- unsigned int len;
- } str;
-
- unsigned long num;
- } value;
-
- int type;
-} curl_hash_key;
-
typedef struct _curl_hash_element {
- curl_hash_key key;
- void *ptr;
+ void *ptr;
+ char *key;
+ size_t key_len;
} curl_hash_element;
-void curl_hash_init(curl_hash *h, int slots, curl_hash_dtor dtor);
-curl_hash *curl_hash_alloc(int slots, curl_hash_dtor dtor);
-int curl_hash_add_or_update(curl_hash *h, char *str_key, unsigned int str_key_len,
- unsigned long num_key, const void *p);
-int curl_hash_extended_delete(curl_hash *h, char *str_key, unsigned int str_key_len,
- unsigned long num_key);
-int curl_hash_extended_find(curl_hash *h, char *str_key, unsigned int str_key_len,
- unsigned long num_key, void **p);
+void curl_hash_init(curl_hash *, int, curl_hash_dtor);
+curl_hash *curl_hash_alloc(int, curl_hash_dtor);
+int curl_hash_add(curl_hash *, char *, size_t, const void *);
+int curl_hash_delete(curl_hash *h, char *key, size_t key_len);
+int curl_hash_find(curl_hash *, char *, size_t, void **p);
void curl_hash_apply(curl_hash *h, void *user, void (*cb)(void *, curl_hash_element *));
size_t curl_hash_count(curl_hash *h);
void curl_hash_clean(curl_hash *h);
void curl_hash_destroy(curl_hash *h);
-#define curl_hash_find(h, key, key_len, p) curl_hash_extended_find(h, key, key_len, 0, p)
-#define curl_hash_delete(h, key, key_len) curl_hash_extended_delete(h, key, key_len, 0)
-#define curl_hash_add(h, key, key_len, p) curl_hash_add_or_update(h, key, key_len, 0, p)
#define curl_hash_update curl_hash_add
-#define curl_hash_index_find(h, key, p) curl_hash_extended_find(h, NULL, 0, key, p)
-#define curl_hash_index_delete(h, key) curl_hash_extended_delete(h, NULL, 0, key)
-#define curl_hash_index_add(h, key, p) curl_hash_add_or_update(h, NULL, 0, key, p)
-#define curl_hash_index_update curl_hash_index_add
+
#endif
+
+/*
+ * local variables:
+ * eval: (load-file "../curl-mode.el")
+ * end:
+ * vim600: fdm=marker
+ * vim: et sw=2 ts=2 sts=2 tw=78
+ */