diff options
| -rw-r--r-- | CHANGES | 6 | ||||
| -rw-r--r-- | RELEASE-NOTES | 2 | ||||
| -rw-r--r-- | lib/hash.c | 99 | ||||
| -rw-r--r-- | lib/hash.h | 44 | ||||
| -rw-r--r-- | lib/hostip.c | 5 | ||||
| -rw-r--r-- | lib/multi.c | 27 |
6 files changed, 133 insertions, 50 deletions
@@ -6,6 +6,12 @@ Changelog +Daniel S (26 June 2007) +- Robert Iakobashvili re-arranged the internal hash code to work with a custom + hash function for different hashes, and also expanded the default size for + the socket hash table used in multi handles to greatly enhance speed when + very many connections are added and the socket API is used. + Daniel S (25 June 2007) - Adjusted how libcurl treats HTTP 1.1 responses without content-lenth or chunked encoding (that also lacks "Connection: close"). It now simply diff --git a/RELEASE-NOTES b/RELEASE-NOTES index 19ab978d3..808fcbde0 100644 --- a/RELEASE-NOTES +++ b/RELEASE-NOTES @@ -33,6 +33,6 @@ New curl mirrors: This release would not have looked like this without help, code, reports and advice from friends like these: - + Robert Iakobashvili Thanks! (and sorry if I forgot to mention someone) 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) |