/***************************************************************************
- * _ _ ____ _
- * Project ___| | | | _ \| |
- * / __| | | | |_) | |
- * | (__| |_| | _ <| |___
+ * _ _ ____ _
+ * Project ___| | | | _ \| |
+ * / __| | | | |_) | |
+ * | (__| |_| | _ <| |___
* \___|\___/|_| \_\_____|
*
- * Copyright (C) 1998 - 2003, Daniel Stenberg, <daniel@haxx.se>, et al.
+ * Copyright (C) 1998 - 2017, Daniel Stenberg, <daniel@haxx.se>, et al.
*
* This software is licensed as described in the file COPYING, which
* you should have received as part of this distribution. The terms
- * are also available at http://curl.haxx.se/docs/copyright.html.
- *
+ * are also available at https://curl.haxx.se/docs/copyright.html.
+ *
* 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 COPYING file.
* This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
* KIND, either express or implied.
*
- * $Id$
***************************************************************************/
-#include "setup.h"
+#include "curl_setup.h"
-#include <string.h>
-#include <stdlib.h>
+#include <curl/curl.h>
#include "hash.h"
#include "llist.h"
+#include "curl_memory.h"
-#ifdef MALLOCDEBUG
-/* this must be the last include file */
+/* The last #include file should be: */
#include "memdebug.h"
-#endif
-
-
-/* {{{ static unsigned long _hash_str (const char *, size_t)
- */
-static unsigned long
-_hash_str (const char *key, size_t key_length)
-{
- char *end = (char *) key + key_length;
- unsigned long h = 5381;
-
- while (key < end) {
- h += h << 5;
- h ^= (unsigned long) *key++;
- }
-
- return h;
-}
-/* }}} */
-/* {{{ static void _hash_element_dtor (void *, void *)
- */
-static void
-_hash_element_dtor (void *user, void *element)
+static void
+hash_element_dtor(void *user, void *element)
{
- curl_hash *h = (curl_hash *) user;
- curl_hash_element *e = (curl_hash_element *) element;
+ struct curl_hash *h = (struct curl_hash *) user;
+ struct curl_hash_element *e = (struct curl_hash_element *) element;
- if (e->key) {
- free(e->key);
+ if(e->ptr) {
+ h->dtor(e->ptr);
+ e->ptr = NULL;
}
- h->dtor(e->ptr);
+ e->key_len = 0;
free(e);
}
-/* }}} */
-/* {{{ void curl_hash_init (curl_hash *, int, curl_hash_dtor)
+/* Initializes a hash structure.
+ * Return 1 on error, 0 is fine.
+ *
+ * @unittest: 1602
+ * @unittest: 1603
*/
-void
-Curl_hash_init (curl_hash *h, int slots, curl_hash_dtor dtor)
+int
+Curl_hash_init(struct curl_hash *h,
+ int slots,
+ hash_function hfunc,
+ comp_function comparator,
+ curl_hash_dtor dtor)
{
int i;
+ if(!slots || !hfunc || !comparator ||!dtor) {
+ return 1; /* failure */
+ }
+
+ h->hash_func = hfunc;
+ h->comp_func = comparator;
h->dtor = dtor;
h->size = 0;
- h->slots = slots;
+ h->slots = slots;
- h->table = (curl_llist **) malloc(slots * sizeof(curl_llist *));
- for (i = 0; i < slots; ++i) {
- h->table[i] = Curl_llist_alloc((curl_llist_dtor) _hash_element_dtor);
+ h->table = malloc(slots * sizeof(struct curl_llist));
+ if(h->table) {
+ for(i = 0; i < slots; ++i)
+ Curl_llist_init(&h->table[i], (curl_llist_dtor) hash_element_dtor);
+ return 0; /* fine */
}
+ h->slots = 0;
+ return 1; /* failure */
}
-/* }}} */
-
-/* {{{ curl_hash *curl_hash_alloc (int, curl_hash_dtor)
- */
-curl_hash *
-Curl_hash_alloc (int slots, curl_hash_dtor dtor)
-{
- curl_hash *h;
-
- h = (curl_hash *) malloc(sizeof(curl_hash));
- if (NULL == h)
- return NULL;
-
- Curl_hash_init(h, slots, dtor);
-
- return h;
-}
-/* }}} */
-/* {{{ static int _hash_key_compare (char *, size_t, char *, size_t)
- */
-static int
-_hash_key_compare (char *key1, size_t key1_len, char *key2, size_t key2_len)
+static struct curl_hash_element *
+mk_hash_element(const void *key, size_t key_len, const void *p)
{
- if (key1_len == key2_len &&
- *key1 == *key2 &&
- memcmp(key1, key2, key1_len) == 0) {
- return 1;
+ /* allocate the struct plus memory after it to store the key */
+ struct curl_hash_element *he = malloc(sizeof(struct curl_hash_element) +
+ key_len);
+ if(he) {
+ /* copy the key */
+ memcpy(he->key, key, key_len);
+ he->key_len = key_len;
+ he->ptr = (void *) p;
}
-
- return 0;
-}
-/* }}} */
-
-/* {{{ 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;
+ return he;
}
-/* }}} */
-
-#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)]
+#define FETCH_LIST(x,y,z) &x->table[x->hash_func(y, z, x->slots)]
-
-/* {{{ int curl_hash_add (curl_hash *, char *, size_t, const void *)
+/* Insert the data in the hash. If there already was a match in the hash,
+ * that data is replaced.
+ *
+ * @unittest: 1305
+ * @unittest: 1602
+ * @unittest: 1603
*/
-int
-Curl_hash_add (curl_hash *h, char *key, size_t key_len, const void *p)
+void *
+Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p)
{
- curl_hash_element *he;
- curl_llist_element *le;
- 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;
+ struct curl_hash_element *he;
+ struct curl_llist_element *le;
+ struct curl_llist *l = FETCH_LIST(h, key, key_len);
+
+ for(le = l->head; le; le = le->next) {
+ he = (struct curl_hash_element *) le->ptr;
+ if(h->comp_func(he->key, he->key_len, key, key_len)) {
+ Curl_llist_remove(l, le, (void *)h);
+ --h->size;
+ break;
}
}
- if (_mk_hash_element(&he, key, key_len, p) != 0)
- return 0;
-
- if (Curl_llist_insert_next(l, CURL_LLIST_TAIL(l), he)) {
+ he = mk_hash_element(key, key_len, p);
+ if(he) {
+ Curl_llist_insert_next(l, l->tail, he, &he->list);
++h->size;
- return 1;
+ return p; /* return the new entry */
}
- return 0;
+ return NULL; /* failure */
}
-/* }}} */
-/* {{{ int curl_hash_delete (curl_hash *, char *, size_t)
+/* Remove the identified hash entry.
+ * Returns non-zero on failure.
+ *
+ * @unittest: 1603
*/
-int
-Curl_hash_delete(curl_hash *h, char *key, size_t key_len)
+int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len)
{
- curl_hash_element *he;
- curl_llist_element *le;
- 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)) {
+ struct curl_llist_element *le;
+ struct curl_hash_element *he;
+ struct curl_llist *l = FETCH_LIST(h, key, key_len);
+
+ for(le = l->head; le; le = le->next) {
+ he = le->ptr;
+ if(h->comp_func(he->key, he->key_len, key, key_len)) {
Curl_llist_remove(l, le, (void *) h);
--h->size;
- return 1;
+ return 0;
}
}
-
- return 0;
+ return 1;
}
-/* }}} */
-/* {{{ int curl_hash_pick (curl_hash *, char *, size_t, void **)
+/* Retrieves a hash element.
+ *
+ * @unittest: 1603
*/
void *
-Curl_hash_pick(curl_hash *h, char *key, size_t key_len)
+Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len)
{
- curl_llist_element *le;
- 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)) {
- return he->ptr;
+ struct curl_llist_element *le;
+ struct curl_hash_element *he;
+ struct curl_llist *l;
+
+ if(h) {
+ l = FETCH_LIST(h, key, key_len);
+ for(le = l->head; le; le = le->next) {
+ he = le->ptr;
+ if(h->comp_func(he->key, he->key_len, key, key_len)) {
+ return he->ptr;
+ }
}
}
return NULL;
}
-/* }}} */
-/* {{{ void curl_hash_apply (curl_hash *, void *, void (*)(void *, curl_hash_element *))
- */
-void
+#if defined(DEBUGBUILD) && defined(AGGRESIVE_TEST)
+void
Curl_hash_apply(curl_hash *h, void *user,
void (*cb)(void *user, void *ptr))
{
- curl_llist_element *le;
+ struct 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)) {
- curl_hash_element *el = CURL_LLIST_VALP(le);
+ for(i = 0; i < h->slots; ++i) {
+ for(le = (h->table[i])->head;
+ le;
+ le = le->next) {
+ curl_hash_element *el = le->ptr;
cb(user, el->ptr);
}
}
}
-/* }}} */
+#endif
-/* {{{ void curl_hash_clean (curl_hash *)
+/* Destroys all the entries in the given hash and resets its attributes,
+ * prepping the given hash for [static|dynamic] deallocation.
+ *
+ * @unittest: 1305
+ * @unittest: 1602
+ * @unittest: 1603
*/
void
-Curl_hash_clean(curl_hash *h)
+Curl_hash_destroy(struct curl_hash *h)
{
int i;
- for (i = 0; i < h->slots; ++i) {
- Curl_llist_destroy(h->table[i], (void *) h);
+ for(i = 0; i < h->slots; ++i) {
+ Curl_llist_destroy(&h->table[i], (void *) h);
}
- free(h->table);
+ Curl_safefree(h->table);
+ h->size = 0;
+ h->slots = 0;
}
-/* }}} */
-/* {{{ void curl_hash_clean_with_criterium (curl_hash *, void *,
- int (*)(void *, void *))
+/* Removes all the entries in the given hash.
+ *
+ * @unittest: 1602
*/
void
-Curl_hash_clean_with_criterium(curl_hash *h, void *user,
+Curl_hash_clean(struct curl_hash *h)
+{
+ Curl_hash_clean_with_criterium(h, NULL, NULL);
+}
+
+/* Cleans all entries that pass the comp function criteria. */
+void
+Curl_hash_clean_with_criterium(struct curl_hash *h, void *user,
int (*comp)(void *, void *))
{
- curl_llist_element *le;
- curl_llist_element *lnext;
+ struct curl_llist_element *le;
+ struct curl_llist_element *lnext;
+ struct curl_llist *list;
int i;
- for (i = 0; i < h->slots; ++i) {
- le = CURL_LLIST_HEAD(h->table[i]);
- while(le != NULL)
- if (comp(user, ((curl_hash_element *) CURL_LLIST_VALP(le))->ptr)) {
- lnext = CURL_LLIST_NEXT(le);
- Curl_llist_remove(h->table[i], le, (void *) h);
- --h->size;
- le = lnext;
+ if(!h)
+ return;
+
+ for(i = 0; i < h->slots; ++i) {
+ list = &h->table[i];
+ le = list->head; /* get first list entry */
+ while(le) {
+ struct curl_hash_element *he = le->ptr;
+ lnext = le->next;
+ /* ask the callback function if we shall remove this entry or not */
+ if(comp == NULL || comp(user, he->ptr)) {
+ Curl_llist_remove(list, le, (void *) h);
+ --h->size; /* one less entry in the hash now */
}
- else
- le = CURL_LLIST_NEXT(le);
+ le = lnext;
+ }
}
}
-/* {{{ int curl_hash_count (curl_hash *)
- */
-int
-Curl_hash_count(curl_hash *h)
+size_t Curl_hash_str(void *key, size_t key_length, size_t slots_num)
{
- return h->size;
+ const char *key_str = (const char *) key;
+ const char *end = key_str + key_length;
+ unsigned long h = 5381;
+
+ while(key_str < end) {
+ h += h << 5;
+ h ^= (unsigned long) *key_str++;
+ }
+
+ return (h % slots_num);
}
-/* }}} */
-/* {{{ void curl_hash_destroy (curl_hash *)
- */
-void
-Curl_hash_destroy(curl_hash *h)
+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)
{
- if (!h)
+ iter->hash = hash;
+ iter->slot_index = 0;
+ iter->current_element = NULL;
+}
+
+struct curl_hash_element *
+Curl_hash_next_element(struct curl_hash_iterator *iter)
+{
+ int i;
+ struct curl_hash *h = iter->hash;
+
+ /* Get the next element in the current list, if any */
+ if(iter->current_element)
+ iter->current_element = iter->current_element->next;
+
+ /* If we have reached the end of the list, find the next one */
+ if(!iter->current_element) {
+ for(i = iter->slot_index; i < h->slots; i++) {
+ if(h->table[i].head) {
+ iter->current_element = h->table[i].head;
+ iter->slot_index = i + 1;
+ break;
+ }
+ }
+ }
+
+ if(iter->current_element) {
+ struct curl_hash_element *he = iter->current_element->ptr;
+ return he;
+ }
+ iter->current_element = NULL;
+ return NULL;
+}
+
+#if 0 /* useful function for debugging hashes and their contents */
+void Curl_hash_print(struct curl_hash *h,
+ void (*func)(void *))
+{
+ struct curl_hash_iterator iter;
+ struct curl_hash_element *he;
+ int last_index = -1;
+
+ if(!h)
return;
- Curl_hash_clean(h);
- free(h);
+ 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");
}
-/* }}} */
-
-/*
- * local variables:
- * eval: (load-file "../curl-mode.el")
- * end:
- * vim600: fdm=marker
- * vim: et sw=2 ts=2 sts=2 tw=78
- */
+#endif
projects / platform / upstream / curl.git / blobdiff