diff options
| -rw-r--r-- | lib/hash.c | 219 | ||||
| -rw-r--r-- | lib/hash.h | 50 |
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 + */ |