123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403 |
- #include "curl_setup.h"
- #include <curl/curl.h>
- #include "hash.h"
- #include "llist.h"
- #include "curl_memory.h"
- #include "memdebug.h"
- #define HASHINIT 0x7017e781
- #define ITERINIT 0x5FEDCBA9
- static void
- hash_element_dtor(void *user, void *element)
- {
- struct Curl_hash *h = (struct Curl_hash *) user;
- struct Curl_hash_element *e = (struct Curl_hash_element *) element;
- if(e->ptr) {
- if(e->dtor)
- e->dtor(e->key, e->key_len, e->ptr);
- else
- h->dtor(e->ptr);
- e->ptr = NULL;
- }
- e->key_len = 0;
- free(e);
- }
- void
- Curl_hash_init(struct Curl_hash *h,
- size_t slots,
- hash_function hfunc,
- comp_function comparator,
- Curl_hash_dtor dtor)
- {
- DEBUGASSERT(h);
- DEBUGASSERT(slots);
- DEBUGASSERT(hfunc);
- DEBUGASSERT(comparator);
- DEBUGASSERT(dtor);
- h->table = NULL;
- h->hash_func = hfunc;
- h->comp_func = comparator;
- h->dtor = dtor;
- h->size = 0;
- h->slots = slots;
- #ifdef DEBUGBUILD
- h->init = HASHINIT;
- #endif
- }
- static struct Curl_hash_element *
- mk_hash_element(const void *key, size_t key_len, const void *p,
- Curl_hash_elem_dtor dtor)
- {
-
- struct Curl_hash_element *he = malloc(sizeof(struct Curl_hash_element) +
- key_len);
- if(he) {
-
- memcpy(he->key, key, key_len);
- he->key_len = key_len;
- he->ptr = (void *) p;
- he->dtor = dtor;
- }
- return he;
- }
- #define FETCH_LIST(x,y,z) &x->table[x->hash_func(y, z, x->slots)]
- void *Curl_hash_add2(struct Curl_hash *h, void *key, size_t key_len, void *p,
- Curl_hash_elem_dtor dtor)
- {
- struct Curl_hash_element *he;
- struct Curl_llist_node *le;
- struct Curl_llist *l;
- DEBUGASSERT(h);
- DEBUGASSERT(h->slots);
- DEBUGASSERT(h->init == HASHINIT);
- if(!h->table) {
- size_t i;
- h->table = malloc(h->slots * sizeof(struct Curl_llist));
- if(!h->table)
- return NULL;
- for(i = 0; i < h->slots; ++i)
- Curl_llist_init(&h->table[i], hash_element_dtor);
- }
- l = FETCH_LIST(h, key, key_len);
- for(le = Curl_llist_head(l); le; le = Curl_node_next(le)) {
- he = (struct Curl_hash_element *) Curl_node_elem(le);
- if(h->comp_func(he->key, he->key_len, key, key_len)) {
- Curl_node_uremove(le, (void *)h);
- --h->size;
- break;
- }
- }
- he = mk_hash_element(key, key_len, p, dtor);
- if(he) {
- Curl_llist_append(l, he, &he->list);
- ++h->size;
- return p;
- }
- return NULL;
- }
- void *
- Curl_hash_add(struct Curl_hash *h, void *key, size_t key_len, void *p)
- {
- return Curl_hash_add2(h, key, key_len, p, NULL);
- }
- int Curl_hash_delete(struct Curl_hash *h, void *key, size_t key_len)
- {
- DEBUGASSERT(h);
- DEBUGASSERT(h->slots);
- DEBUGASSERT(h->init == HASHINIT);
- if(h->table) {
- struct Curl_llist_node *le;
- struct Curl_llist *l = FETCH_LIST(h, key, key_len);
- for(le = Curl_llist_head(l); le; le = Curl_node_next(le)) {
- struct Curl_hash_element *he = Curl_node_elem(le);
- if(h->comp_func(he->key, he->key_len, key, key_len)) {
- Curl_node_uremove(le, (void *) h);
- --h->size;
- return 0;
- }
- }
- }
- return 1;
- }
- void *
- Curl_hash_pick(struct Curl_hash *h, void *key, size_t key_len)
- {
- DEBUGASSERT(h);
- DEBUGASSERT(h->init == HASHINIT);
- if(h->table) {
- struct Curl_llist_node *le;
- struct Curl_llist *l;
- DEBUGASSERT(h->slots);
- l = FETCH_LIST(h, key, key_len);
- for(le = Curl_llist_head(l); le; le = Curl_node_next(le)) {
- struct Curl_hash_element *he = Curl_node_elem(le);
- if(h->comp_func(he->key, he->key_len, key, key_len)) {
- return he->ptr;
- }
- }
- }
- return NULL;
- }
- void
- Curl_hash_destroy(struct Curl_hash *h)
- {
- DEBUGASSERT(h->init == HASHINIT);
- if(h->table) {
- size_t i;
- for(i = 0; i < h->slots; ++i) {
- Curl_llist_destroy(&h->table[i], (void *) h);
- }
- Curl_safefree(h->table);
- }
- h->size = 0;
- h->slots = 0;
- }
- void
- Curl_hash_clean(struct Curl_hash *h)
- {
- Curl_hash_clean_with_criterium(h, NULL, NULL);
- }
- size_t Curl_hash_count(struct Curl_hash *h)
- {
- DEBUGASSERT(h->init == HASHINIT);
- return h->size;
- }
- void
- Curl_hash_clean_with_criterium(struct Curl_hash *h, void *user,
- int (*comp)(void *, void *))
- {
- size_t i;
- if(!h || !h->table)
- return;
- DEBUGASSERT(h->init == HASHINIT);
- for(i = 0; i < h->slots; ++i) {
- struct Curl_llist *list = &h->table[i];
- struct Curl_llist_node *le =
- Curl_llist_head(list);
- while(le) {
- struct Curl_hash_element *he = Curl_node_elem(le);
- struct Curl_llist_node *lnext = Curl_node_next(le);
-
- if(!comp || comp(user, he->ptr)) {
- Curl_node_uremove(le, (void *) h);
- --h->size;
- }
- le = lnext;
- }
- }
- }
- size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num)
- {
- const char *key_str = (const char *) key;
- const char *end = key_str + key_length;
- size_t h = 5381;
- while(key_str < end) {
- size_t j = (size_t)*key_str++;
- h += h << 5;
- h ^= j;
- }
- return (h % slots_num);
- }
- size_t Curl_str_key_compare(void *k1, size_t key1_len,
- void *k2, size_t key2_len)
- {
- if((key1_len == key2_len) && !memcmp(k1, k2, key1_len))
- return 1;
- return 0;
- }
- void Curl_hash_start_iterate(struct Curl_hash *hash,
- struct Curl_hash_iterator *iter)
- {
- DEBUGASSERT(hash->init == HASHINIT);
- iter->hash = hash;
- iter->slot_index = 0;
- iter->current_element = NULL;
- #ifdef DEBUGBUILD
- iter->init = ITERINIT;
- #endif
- }
- struct Curl_hash_element *
- Curl_hash_next_element(struct Curl_hash_iterator *iter)
- {
- struct Curl_hash *h;
- DEBUGASSERT(iter->init == ITERINIT);
- h = iter->hash;
- if(!h->table)
- return NULL;
-
- if(iter->current_element)
- iter->current_element = Curl_node_next(iter->current_element);
-
- if(!iter->current_element) {
- size_t i;
- for(i = iter->slot_index; i < h->slots; i++) {
- if(Curl_llist_head(&h->table[i])) {
- iter->current_element = Curl_llist_head(&h->table[i]);
- iter->slot_index = i + 1;
- break;
- }
- }
- }
- if(iter->current_element) {
- struct Curl_hash_element *he = Curl_node_elem(iter->current_element);
- return he;
- }
- return NULL;
- }
- #if 0
- void Curl_hash_print(struct Curl_hash *h,
- void (*func)(void *))
- {
- struct Curl_hash_iterator iter;
- struct Curl_hash_element *he;
- size_t last_index = ~0;
- if(!h)
- return;
- fprintf(stderr, "=Hash dump=\n");
- Curl_hash_start_iterate(h, &iter);
- he = Curl_hash_next_element(&iter);
- while(he) {
- if(iter.slot_index != last_index) {
- fprintf(stderr, "index %d:", iter.slot_index);
- if(last_index != ~0) {
- fprintf(stderr, "\n");
- }
- last_index = iter.slot_index;
- }
- if(func)
- func(he->ptr);
- else
- fprintf(stderr, " [%p]", (void *)he->ptr);
- he = Curl_hash_next_element(&iter);
- }
- fprintf(stderr, "\n");
- }
- #endif
- void Curl_hash_offt_init(struct Curl_hash *h,
- size_t slots,
- Curl_hash_dtor dtor)
- {
- Curl_hash_init(h, slots, Curl_hash_str, Curl_str_key_compare, dtor);
- }
- void *Curl_hash_offt_set(struct Curl_hash *h, curl_off_t id, void *elem)
- {
- return Curl_hash_add(h, &id, sizeof(id), elem);
- }
- int Curl_hash_offt_remove(struct Curl_hash *h, curl_off_t id)
- {
- return Curl_hash_delete(h, &id, sizeof(id));
- }
- void *Curl_hash_offt_get(struct Curl_hash *h, curl_off_t id)
- {
- return Curl_hash_pick(h, &id, sizeof(id));
- }
|