aboutsummaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/hash.c99
-rw-r--r--lib/hash.h44
-rw-r--r--lib/hostip.c5
-rw-r--r--lib/multi.c27
4 files changed, 126 insertions, 49 deletions
diff --git a/lib/hash.c b/lib/hash.c
index e00462778..ec4a759f8 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -5,7 +5,7 @@
* | (__| |_| | _ <| |___
* \___|\___/|_| \_\_____|
*
- * Copyright (C) 1998 - 2006, Daniel Stenberg, <daniel@haxx.se>, et al.
+ * Copyright (C) 1998 - 2007, 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
@@ -33,20 +33,6 @@
/* this must be the last include file */
#include "memdebug.h"
-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 *user, void *element)
{
@@ -63,10 +49,20 @@ hash_element_dtor(void *user, void *element)
/* return 1 on error, 0 is fine */
int
-Curl_hash_init(struct curl_hash *h, int slots, curl_hash_dtor dtor)
+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;
@@ -89,13 +85,20 @@ Curl_hash_init(struct curl_hash *h, int slots, curl_hash_dtor dtor)
}
struct curl_hash *
-Curl_hash_alloc(int slots, curl_hash_dtor dtor)
+Curl_hash_alloc(int slots,
+ hash_function hfunc,
+ comp_function comparator,
+ curl_hash_dtor dtor)
{
struct curl_hash *h;
+ if (!slots || !hfunc || !comparator ||!dtor) {
+ return NULL; /* failure */
+ }
+
h = (struct curl_hash *) malloc(sizeof(struct curl_hash));
if (h) {
- if(Curl_hash_init(h, slots, dtor)) {
+ if(Curl_hash_init(h, slots, hfunc, comparator, dtor)) {
/* failure */
free(h);
h = NULL;
@@ -105,26 +108,16 @@ Curl_hash_alloc(int slots, curl_hash_dtor dtor)
return h;
}
-static int
-hash_key_compare(char *key1, size_t key1_len, char *key2, size_t key2_len)
-{
- if (key1_len == key2_len &&
- *key1 == *key2 &&
- memcmp(key1, key2, key1_len) == 0) {
- return 1;
- }
- return 0;
-}
static struct curl_hash_element *
-mk_hash_element(char *key, size_t key_len, const void *p)
+mk_hash_element(void *key, size_t key_len, const void *p)
{
struct curl_hash_element *he =
(struct curl_hash_element *) malloc(sizeof(struct curl_hash_element));
if(he) {
- char *dup = malloc(key_len);
+ void *dup = malloc(key_len);
if(dup) {
/* copy the key */
memcpy(dup, key, key_len);
@@ -142,22 +135,20 @@ mk_hash_element(char *key, size_t key_len, const void *p)
return he;
}
-#define find_slot(__h, __k, __k_len) (hash_str(__k, __k_len) % (__h)->slots)
-
-#define FETCH_LIST(x,y,z) x->table[find_slot(x, y, z)]
+#define FETCH_LIST(x,y,z) x->table[x->hash_func(y, z, x->slots)]
/* Return the data in the hash. If there already was a match in the hash,
that data is returned. */
void *
-Curl_hash_add(struct curl_hash *h, char *key, size_t key_len, void *p)
+Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p)
{
struct curl_hash_element *he;
struct curl_llist_element *le;
- struct curl_llist *l = FETCH_LIST(h, key, key_len);
+ 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 (hash_key_compare(he->key, he->key_len, key, key_len)) {
+ if (h->comp_func(he->key, he->key_len, key, key_len)) {
h->dtor(p); /* remove the NEW entry */
return he->ptr; /* return the EXISTING entry */
}
@@ -183,7 +174,7 @@ Curl_hash_add(struct curl_hash *h, char *key, size_t key_len, void *p)
}
/* remove the identified hash entry, returns non-zero on failure */
-int Curl_hash_delete(struct curl_hash *h, char *key, size_t key_len)
+int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len)
{
struct curl_llist_element *le;
struct curl_hash_element *he;
@@ -191,7 +182,7 @@ int Curl_hash_delete(struct curl_hash *h, char *key, size_t key_len)
for (le = l->head; le; le = le->next) {
he = le->ptr;
- if (hash_key_compare(he->key, he->key_len, key, key_len)) {
+ if (h->comp_func(he->key, he->key_len, key, key_len)) {
Curl_llist_remove(l, le, (void *) h);
return 0;
}
@@ -200,7 +191,7 @@ int Curl_hash_delete(struct curl_hash *h, char *key, size_t key_len)
}
void *
-Curl_hash_pick(struct curl_hash *h, char *key, size_t key_len)
+Curl_hash_pick(struct curl_hash *h, void *key, size_t key_len)
{
struct curl_llist_element *le;
struct curl_hash_element *he;
@@ -208,7 +199,7 @@ Curl_hash_pick(struct curl_hash *h, char *key, size_t key_len)
for (le = l->head; le; le = le->next) {
he = le->ptr;
- if (hash_key_compare(he->key, he->key_len, key, key_len)) {
+ if (h->comp_func(he->key, he->key_len, key, key_len)) {
return he->ptr;
}
}
@@ -282,6 +273,34 @@ Curl_hash_destroy(struct curl_hash *h)
free(h);
}
+size_t Curl_hash_str(void* key, size_t key_length, size_t slots_num)
+{
+ char* key_str = (char *) key;
+ char *end = (char *) key_str + key_length;
+ unsigned long h = 5381;
+
+ while (key_str < end) {
+ h += h << 5;
+ h ^= (unsigned long) *key_str++;
+ }
+
+ return (h % slots_num);
+}
+
+size_t Curl_str_key_compare(void*k1, size_t key1_len, void*k2, size_t key2_len)
+{
+ char *key1 = (char *)k1;
+ char *key2 = (char *)k2;
+
+ if (key1_len == key2_len &&
+ *key1 == *key2 &&
+ memcmp(key1, key2, key1_len) == 0) {
+ return 1;
+ }
+
+ return 0;
+}
+
#if 0 /* useful function for debugging hashes and their contents */
void Curl_hash_print(struct curl_hash *h,
void (*func)(void *))
diff --git a/lib/hash.h b/lib/hash.h
index ceebb5234..1e2e5dfb4 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -7,7 +7,7 @@
* | (__| |_| | _ <| |___
* \___|\___/|_| \_\_____|
*
- * Copyright (C) 1998 - 2005, Daniel Stenberg, <daniel@haxx.se>, et al.
+ * Copyright (C) 1998 - 2007, 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
@@ -29,10 +29,29 @@
#include "llist.h"
+/* Hash function prototype */
+typedef size_t (*hash_function) (void* key,
+ size_t key_length,
+ size_t slots_num);
+
+/*
+ Comparator function prototype. Compares two keys.
+*/
+typedef size_t (*comp_function) (void* key1,
+ size_t key1_len,
+ void*key2,
+ size_t key2_len);
+
typedef void (*curl_hash_dtor)(void *);
struct curl_hash {
struct curl_llist **table;
+
+ /* Hash function to be used for this hash table */
+ hash_function hash_func;
+
+ /* Comparator function to compare keys */
+ comp_function comp_func;
curl_hash_dtor dtor;
int slots;
size_t size;
@@ -45,11 +64,20 @@ struct curl_hash_element {
};
-int Curl_hash_init(struct curl_hash *, int, curl_hash_dtor);
-struct curl_hash *Curl_hash_alloc(int, curl_hash_dtor);
-void *Curl_hash_add(struct curl_hash *, char *, size_t, void *);
-int Curl_hash_delete(struct curl_hash *h, char *key, size_t key_len);
-void *Curl_hash_pick(struct curl_hash *, char *, size_t);
+int Curl_hash_init(struct curl_hash *h,
+ int slots,
+ hash_function hfunc,
+ comp_function comparator,
+ curl_hash_dtor dtor);
+
+struct curl_hash *Curl_hash_alloc(int slots,
+ hash_function hfunc,
+ comp_function comparator,
+ curl_hash_dtor dtor);
+
+void *Curl_hash_add(struct curl_hash *h, void *key, size_t key_len, void *p);
+int Curl_hash_delete(struct curl_hash *h, void *key, size_t key_len);
+void *Curl_hash_pick(struct curl_hash *, void * key, size_t key_len);
void Curl_hash_apply(struct curl_hash *h, void *user,
void (*cb)(void *user, void *ptr));
int Curl_hash_count(struct curl_hash *h);
@@ -58,4 +86,8 @@ void Curl_hash_clean_with_criterium(struct curl_hash *h, void *user,
int (*comp)(void *, void *));
void Curl_hash_destroy(struct curl_hash *h);
+size_t Curl_hash_str(void* key, size_t key_length, size_t slots_num);
+size_t Curl_str_key_compare(void*k1, size_t key1_len, void*k2,
+ size_t key2_len);
+
#endif
diff --git a/lib/hostip.c b/lib/hostip.c
index 9fb157fd3..5a7da5016 100644
--- a/lib/hostip.c
+++ b/lib/hostip.c
@@ -131,7 +131,8 @@ static void freednsentry(void *freethis);
void Curl_global_host_cache_init(void)
{
if (!host_cache_initialized) {
- Curl_hash_init(&hostname_cache, 7, freednsentry);
+ Curl_hash_init(&hostname_cache, 7, Curl_hash_str, Curl_str_key_compare,
+ freednsentry);
host_cache_initialized = 1;
}
}
@@ -537,7 +538,7 @@ static void freednsentry(void *freethis)
*/
struct curl_hash *Curl_mk_dnscache(void)
{
- return Curl_hash_alloc(7, freednsentry);
+ return Curl_hash_alloc(7, Curl_hash_str, Curl_str_key_compare, freednsentry);
}
#ifdef CURLRES_ADDRINFO_COPY
diff --git a/lib/multi.c b/lib/multi.c
index 5e91a5e7c..0bdfd6170 100644
--- a/lib/multi.c
+++ b/lib/multi.c
@@ -50,6 +50,15 @@
/* The last #include file should be: */
#include "memdebug.h"
+/*
+ CURL_SOCKET_HASH_TABLE_SIZE should be a prime number. Increasing it from 97
+ to 911 takes on a 32-bit machine 4 x 804 = 3211 more bytes. Still, every
+ CURL handle takes 45-50 K memory, therefore this 3K are not significant.
+*/
+#ifndef CURL_SOCKET_HASH_TABLE_SIZE
+#define CURL_SOCKET_HASH_TABLE_SIZE 911
+#endif
+
struct Curl_message {
/* the 'CURLMsg' is the part that is visible to the external user */
struct CURLMsg extmsg;
@@ -305,6 +314,21 @@ static void sh_freeentry(void *freethis)
free(p);
}
+static size_t fd_key_compare(void*k1, size_t k1_len, void*k2, size_t k2_len)
+{
+ (void) k1_len; (void) k2_len;
+
+ return ((*((int* ) k1)) == (*((int* ) k2))) ? 1 : 0;
+}
+
+static size_t hash_fd(void* key, size_t key_length, size_t slots_num)
+{
+ int fd = * ((int* ) key);
+ (void) key_length;
+
+ return (fd % (int)slots_num);
+}
+
/*
* sh_init() creates a new socket hash and returns the handle for it.
*
@@ -325,7 +349,8 @@ static void sh_freeentry(void *freethis)
*/
static struct curl_hash *sh_init(void)
{
- return Curl_hash_alloc(97, sh_freeentry);
+ return Curl_hash_alloc(CURL_SOCKET_HASH_TABLE_SIZE, hash_fd, fd_key_compare,
+ sh_freeentry);
}
CURLM *curl_multi_init(void)