From 670eba73c474230e31d688e9568fcd540b4e3b39 Mon Sep 17 00:00:00 2001 From: Stef Walter Date: Mon, 9 Aug 2004 18:35:56 +0000 Subject: - added request parameter to ha_message... - combined ha_request and ha_response --- common/hash.c | 544 +++++++++++++++++++++++++++++----------------------------- 1 file changed, 272 insertions(+), 272 deletions(-) (limited to 'common/hash.c') diff --git a/common/hash.c b/common/hash.c index 5f3308c..3ff3982 100644 --- a/common/hash.c +++ b/common/hash.c @@ -9,7 +9,7 @@ * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * - * http://www.apache.org/licenses/LICENSE-2.0 + * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, @@ -27,9 +27,9 @@ #endif #ifdef HSH_COPYKEYS - #define KEY_DATA(he) (void*)(((unsigned char*)(he)) + sizeof(*(he))) + #define KEY_DATA(he) (void*)(((unsigned char*)(he)) + sizeof(*(he))) #else - #define KEY_DATA(he) ((he)->key) + #define KEY_DATA(he) ((he)->key) #endif /* @@ -45,15 +45,15 @@ typedef struct hsh_entry_t hsh_entry_t; struct hsh_entry_t { - hsh_entry_t* next; - unsigned int hash; + hsh_entry_t* next; + unsigned int hash; #ifndef HSH_COPYKEYS - const void* key; - size_t klen; + const void* key; + size_t klen; #endif - const void* val; + const void* val; #ifdef HSH_TIMESTAMP - time_t stamp; + time_t stamp; #endif }; @@ -66,10 +66,10 @@ struct hsh_entry_t */ struct hsh_index_t { - hsh_t* ht; - hsh_entry_t* ths; - hsh_entry_t* next; - unsigned int index; + hsh_t* ht; + hsh_entry_t* ths; + hsh_entry_t* next; + unsigned int index; }; /* @@ -81,15 +81,15 @@ struct hsh_index_t */ struct hsh_t { - hsh_entry_t** array; - hsh_index_t iterator; /* For hsh_first(...) */ - unsigned int count; - unsigned int max; + hsh_entry_t** array; + hsh_index_t iterator; /* For hsh_first(...) */ + unsigned int count; + unsigned int max; #ifdef HSH_COPYKEYS - unsigned int klen; + unsigned int klen; #endif #ifdef HSH_CALLBACKS - hsh_table_calls_t calls; + hsh_table_calls_t calls; #endif }; @@ -106,47 +106,47 @@ static hsh_memory_calls_t* g_memory_calls = NULL; static void* int_malloc(size_t len) { - if(g_memory_calls) - return (g_memory_calls->f_alloc)(g_memory_calls->arg, len); - else - return malloc(len); + if(g_memory_calls) + return (g_memory_calls->f_alloc)(g_memory_calls->arg, len); + else + return malloc(len); } static void* int_calloc(size_t len) { - void* p = int_malloc(len); - memset(p, 0, len); - return p; + void* p = int_malloc(len); + memset(p, 0, len); + return p; } static void int_free(void* ptr) { - if(g_memory_calls) - { - /* We allow for gc type memory allocation with a null free */ - if(g_memory_calls->f_free) - (g_memory_calls->f_free)(g_memory_calls->arg, ptr); - } - else - free(ptr); + if(g_memory_calls) + { + /* We allow for gc type memory allocation with a null free */ + if(g_memory_calls->f_free) + (g_memory_calls->f_free)(g_memory_calls->arg, ptr); + } + else + free(ptr); } void hsh_set_memory_calls(hsh_memory_calls_t* hmc) { - if(hmc == NULL) - { - g_memory_calls = NULL; - } - else - { - memcpy(&g_memory_calls_cpy, hmc, sizeof(g_memory_calls_cpy)); - g_memory_calls = &g_memory_calls_cpy; - } + if(hmc == NULL) + { + g_memory_calls = NULL; + } + else + { + memcpy(&g_memory_calls_cpy, hmc, sizeof(g_memory_calls_cpy)); + g_memory_calls = &g_memory_calls_cpy; + } } void hsh_set_table_calls(hsh_t* ht, hsh_table_calls_t* htc) { - memcpy(&(ht->calls), htc, sizeof(ht->calls)); + memcpy(&(ht->calls), htc, sizeof(ht->calls)); } #else @@ -163,7 +163,7 @@ void hsh_set_table_calls(hsh_t* ht, hsh_table_calls_t* htc) static hsh_entry_t** alloc_array(hsh_t* ht, unsigned int max) { - return int_calloc(sizeof(*(ht->array)) * (max + 1)); + return int_calloc(sizeof(*(ht->array)) * (max + 1)); } #ifdef HSH_COPYKEYS @@ -172,41 +172,41 @@ hsh_t* hsh_create(size_t klen) hsh_t* hsh_create() #endif { - hsh_t* ht = int_malloc(sizeof(hsh_t)); - if(ht) - { - ht->count = 0; - ht->max = INITIAL_MAX; - ht->array = alloc_array(ht, ht->max); + hsh_t* ht = int_malloc(sizeof(hsh_t)); + if(ht) + { + ht->count = 0; + ht->max = INITIAL_MAX; + ht->array = alloc_array(ht, ht->max); #ifdef HSH_COPYKEYS - ht->klen = klen; + ht->klen = klen; #endif - if(!ht->array) - { - int_free(ht); - return NULL; + if(!ht->array) + { + int_free(ht); + return NULL; + } } - } - return ht; + return ht; } void hsh_free(hsh_t* ht) { - hsh_index_t* hi; + hsh_index_t* hi; - for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) - { + for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) + { #ifdef HSH_CALLBACKS - if(hi->ths->val && ht->calls.f_freeval) - (ht->calls.f_freeval)(ht->calls.arg, (void*)hi->ths->val); + if(hi->ths->val && ht->calls.f_freeval) + (ht->calls.f_freeval)(ht->calls.arg, (void*)hi->ths->val); #endif - int_free(hi->ths); - } + int_free(hi->ths); + } - if(ht->array) - int_free(ht->array); + if(ht->array) + int_free(ht->array); - int_free(ht); + int_free(ht); } /* @@ -215,27 +215,27 @@ void hsh_free(hsh_t* ht) hsh_index_t* hsh_next(hsh_index_t* hi) { - hi->ths = hi->next; - while(!hi->ths) - { - if(hi->index > hi->ht->max) - return NULL; - - hi->ths = hi->ht->array[hi->index++]; - } - hi->next = hi->ths->next; - return hi; + hi->ths = hi->next; + while(!hi->ths) + { + if(hi->index > hi->ht->max) + return NULL; + + hi->ths = hi->ht->array[hi->index++]; + } + hi->next = hi->ths->next; + return hi; } hsh_index_t* hsh_first(hsh_t* ht) { - hsh_index_t* hi = &ht->iterator; + hsh_index_t* hi = &ht->iterator; - hi->ht = ht; - hi->index = 0; - hi->ths = NULL; - hi->next = NULL; - return hsh_next(hi); + hi->ht = ht; + hi->index = 0; + hi->ths = NULL; + hi->next = NULL; + return hsh_next(hi); } #ifdef HSH_COPYKEYS @@ -244,15 +244,15 @@ void* hsh_this(hsh_index_t* hi, const void** key) void* hsh_this(hsh_index_t* hi, const void** key, size_t* klen) #endif { - if(key) - *key = KEY_DATA(hi->ths); + if(key) + *key = KEY_DATA(hi->ths); #ifndef HSH_COPYKEYS - if(klen) - *klen = hi->ths->klen; + if(klen) + *klen = hi->ths->klen; #endif - return (void*)hi->ths->val; + return (void*)hi->ths->val; } @@ -262,29 +262,29 @@ void* hsh_this(hsh_index_t* hi, const void** key, size_t* klen) static int expand_array(hsh_t* ht) { - hsh_index_t* hi; - hsh_entry_t** new_array; - unsigned int new_max; + hsh_index_t* hi; + hsh_entry_t** new_array; + unsigned int new_max; - new_max = ht->max * 2 + 1; - new_array = alloc_array(ht, new_max); + new_max = ht->max * 2 + 1; + new_array = alloc_array(ht, new_max); - if(!new_array) - return 0; + if(!new_array) + return 0; - for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) - { - unsigned int i = hi->ths->hash & new_max; - hi->ths->next = new_array[i]; - new_array[i] = hi->ths; - } + for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) + { + unsigned int i = hi->ths->hash & new_max; + hi->ths->next = new_array[i]; + new_array[i] = hi->ths; + } - if(ht->array) - free(ht->array); + if(ht->array) + free(ht->array); - ht->array = new_array; - ht->max = new_max; - return 1; + ht->array = new_array; + ht->max = new_max; + return 1; } /* @@ -302,283 +302,283 @@ static hsh_entry_t** find_entry(hsh_t* ht, const void* key, const void* val) static hsh_entry_t** find_entry(hsh_t* ht, const void* key, size_t klen, const void* val) #endif { - hsh_entry_t** hep; - hsh_entry_t* he; - const unsigned char* p; - unsigned int hash; - size_t i; + hsh_entry_t** hep; + hsh_entry_t* he; + const unsigned char* p; + unsigned int hash; + size_t i; #ifdef HSH_COPYKEYS - size_t klen = ht->klen; + size_t klen = ht->klen; #endif - /* - * This is the popular `times 33' hash algorithm which is used by - * perl and also appears in Berkeley DB. This is one of the best - * known hash functions for strings because it is both computed - * very fast and distributes very well. - * - * The originator may be Dan Bernstein but the code in Berkeley DB - * cites Chris Torek as the source. The best citation I have found - * is "Chris Torek, Hash function for text in C, Usenet message - * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich - * Salz's USENIX 1992 paper about INN which can be found at - * . - * - * The magic of number 33, i.e. why it works better than many other - * constants, prime or not, has never been adequately explained by - * anyone. So I try an explanation: if one experimentally tests all - * multipliers between 1 and 256 (as I did while writing a low-level - * data structure library some time ago) one detects that even - * numbers are not useable at all. The remaining 128 odd numbers - * (except for the number 1) work more or less all equally well. - * They all distribute in an acceptable way and this way fill a hash - * table with an average percent of approx. 86%. - * - * If one compares the chi^2 values of the variants (see - * Bob Jenkins ``Hashing Frequently Asked Questions'' at - * http://burtleburtle.net/bob/hash/hashfaq.html for a description - * of chi^2), the number 33 not even has the best value. But the - * number 33 and a few other equally good numbers like 17, 31, 63, - * 127 and 129 have nevertheless a great advantage to the remaining - * numbers in the large set of possible multipliers: their multiply - * operation can be replaced by a faster operation based on just one - * shift plus either a single addition or subtraction operation. And - * because a hash function has to both distribute good _and_ has to - * be very fast to compute, those few numbers should be preferred. - * - * -- Ralf S. Engelschall - */ - hash = 0; + /* + * This is the popular `times 33' hash algorithm which is used by + * perl and also appears in Berkeley DB. This is one of the best + * known hash functions for strings because it is both computed + * very fast and distributes very well. + * + * The originator may be Dan Bernstein but the code in Berkeley DB + * cites Chris Torek as the source. The best citation I have found + * is "Chris Torek, Hash function for text in C, Usenet message + * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich + * Salz's USENIX 1992 paper about INN which can be found at + * . + * + * The magic of number 33, i.e. why it works better than many other + * constants, prime or not, has never been adequately explained by + * anyone. So I try an explanation: if one experimentally tests all + * multipliers between 1 and 256 (as I did while writing a low-level + * data structure library some time ago) one detects that even + * numbers are not useable at all. The remaining 128 odd numbers + * (except for the number 1) work more or less all equally well. + * They all distribute in an acceptable way and this way fill a hash + * table with an average percent of approx. 86%. + * + * If one compares the chi^2 values of the variants (see + * Bob Jenkins ``Hashing Frequently Asked Questions'' at + * http://burtleburtle.net/bob/hash/hashfaq.html for a description + * of chi^2), the number 33 not even has the best value. But the + * number 33 and a few other equally good numbers like 17, 31, 63, + * 127 and 129 have nevertheless a great advantage to the remaining + * numbers in the large set of possible multipliers: their multiply + * operation can be replaced by a faster operation based on just one + * shift plus either a single addition or subtraction operation. And + * because a hash function has to both distribute good _and_ has to + * be very fast to compute, those few numbers should be preferred. + * + * -- Ralf S. Engelschall + */ + hash = 0; #ifndef HSH_COPYKEYS - if(klen == HSH_KEY_STRING) - { - for(p = key; *p; p++) - hash = hash * 33 + *p; - - klen = p - (const unsigned char *)key; - } - else + if(klen == HSH_KEY_STRING) + { + for(p = key; *p; p++) + hash = hash * 33 + *p; + + klen = p - (const unsigned char *)key; + } + else #endif - { - for(p = key, i = klen; i; i--, p++) - hash = hash * 33 + *p; - } - - /* scan linked list */ - for(hep = &ht->array[hash & ht->max], he = *hep; - he; hep = &he->next, he = *hep) - { - if(he->hash == hash && + { + for(p = key, i = klen; i; i--, p++) + hash = hash * 33 + *p; + } + + /* scan linked list */ + for(hep = &ht->array[hash & ht->max], he = *hep; + he; hep = &he->next, he = *hep) + { + if(he->hash == hash && #ifndef HSH_COPYKEYS - he->klen == klen && + he->klen == klen && #endif - memcmp(KEY_DATA(he), key, klen) == 0) - break; - } + memcmp(KEY_DATA(he), key, klen) == 0) + break; + } - if(he || !val) - return hep; + if(he || !val) + return hep; - /* add a new entry for non-NULL val */ + /* add a new entry for non-NULL val */ #ifdef HSH_COPYKEYS - he = int_malloc(sizeof(*he) + klen); + he = int_malloc(sizeof(*he) + klen); #else - he = int_malloc(sizeof(*he)); + he = int_malloc(sizeof(*he)); #endif - if(he) - { + if(he) + { #ifdef HSH_COPYKEYS - /* Key data points past end of entry */ - memcpy(KEY_DATA(he), key, klen); + /* Key data points past end of entry */ + memcpy(KEY_DATA(he), key, klen); #else - /* Key points to external data */ - he->key = key; - he->klen = klen; + /* Key points to external data */ + he->key = key; + he->klen = klen; #endif - he->next = NULL; - he->hash = hash; - he->val = val; + he->next = NULL; + he->hash = hash; + he->val = val; #ifdef HSH_TIMESTAMP - he->stamp = 0; + he->stamp = 0; #endif - *hep = he; - ht->count++; - } + *hep = he; + ht->count++; + } - return hep; + return hep; } #ifdef HSH_COPYKEYS void* hsh_get(hsh_t* ht, const void *key) { - hsh_entry_t** he = find_entry(ht, key, NULL); + hsh_entry_t** he = find_entry(ht, key, NULL); #else void* hsh_get(hsh_t* ht, const void *key, size_t klen) { - hsh_entry_t** he = find_entry(ht, key, klen, NULL); + hsh_entry_t** he = find_entry(ht, key, klen, NULL); #endif - if(he && *he) - return (void*)((*he)->val); - else - return NULL; + if(he && *he) + return (void*)((*he)->val); + else + return NULL; } #ifdef HSH_COPYKEYS int hsh_set(hsh_t* ht, const void* key, void* val) { - hsh_entry_t** hep = find_entry(ht, key, val); + hsh_entry_t** hep = find_entry(ht, key, val); #else int hsh_set(hsh_t* ht, const void* key, size_t klen, void* val) { - hsh_entry_t** hep = find_entry(ht, key, klen, val); + hsh_entry_t** hep = find_entry(ht, key, klen, val); #endif - if(hep && *hep) - { + if(hep && *hep) + { #ifdef HSH_CALLBACKS - if((*hep)->val && (*hep)->val != val && ht->calls.f_freeval) - (ht->calls.f_freeval)(ht->calls.arg, (void*)((*hep)->val)); + if((*hep)->val && (*hep)->val != val && ht->calls.f_freeval) + (ht->calls.f_freeval)(ht->calls.arg, (void*)((*hep)->val)); #endif - /* replace entry */ - (*hep)->val = val; + /* replace entry */ + (*hep)->val = val; #ifdef HSH_TIMESTAMP - /* Update or set the timestamp */ - (*hep)->stamp = time(NULL); + /* Update or set the timestamp */ + (*hep)->stamp = time(NULL); #endif - /* check that the collision rate isn't too high */ - if(ht->count > ht->max) - { - if(!expand_array(ht)) - return 0; - } + /* check that the collision rate isn't too high */ + if(ht->count > ht->max) + { + if(!expand_array(ht)) + return 0; + } - return 1; - } + return 1; + } - return 0; + return 0; } #ifdef HSH_COPYKEYS void* hsh_rem(hsh_t* ht, const void* key) { - hsh_entry_t** hep = find_entry(ht, key, NULL); + hsh_entry_t** hep = find_entry(ht, key, NULL); #else void* hsh_rem(hsh_t* ht, const void* key, size_t klen) { - hsh_entry_t** hep = find_entry(ht, key, klen, NULL); + hsh_entry_t** hep = find_entry(ht, key, klen, NULL); #endif - void* val = NULL; - - if(hep && *hep) - { - hsh_entry_t* old = *hep; - *hep = (*hep)->next; - --ht->count; - val = (void*)old->val; - free(old); - } - - return val; + void* val = NULL; + + if(hep && *hep) + { + hsh_entry_t* old = *hep; + *hep = (*hep)->next; + --ht->count; + val = (void*)old->val; + free(old); + } + + return val; } unsigned int hsh_count(hsh_t* ht) { - return ht->count; + return ht->count; } #ifdef HSH_TIMESTAMP int hsh_purge(hsh_t* ht, time_t stamp) { - hsh_index_t* hi; - int r = 0; - void* val; + hsh_index_t* hi; + int r = 0; + void* val; - for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) - { - if(hi->ths->stamp < stamp) + for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) { - /* No need to check for errors as we're deleting */ + if(hi->ths->stamp < stamp) + { + /* No need to check for errors as we're deleting */ #ifdef HSH_COPYKEYS - val = hsh_rem(ht, KEY_DATA(hi->ths)); + val = hsh_rem(ht, KEY_DATA(hi->ths)); #else - val = hsh_rem(ht, hi->ths->key, hi->ths->klen); + val = hsh_rem(ht, hi->ths->key, hi->ths->klen); #endif #ifdef HSH_CALLBACKS - if(val && ht->calls.f_freeval) - (ht->calls.f_freeval)(ht->calls.arg, val); + if(val && ht->calls.f_freeval) + (ht->calls.f_freeval)(ht->calls.arg, val); #endif - r++; + r++; + } } - } - return r; + return r; } #ifdef HSH_COPYKEYS void hsh_touch(hsh_t* ht, const void* key) { - hsh_entry_t** hep = find_entry(ht, key, NULL); + hsh_entry_t** hep = find_entry(ht, key, NULL); #else void hsh_touch(hsh_t* ht, const void* key, size_t* klen) { - hsh_entry_t** hep = find_entry(ht, key, klen, NULL); + hsh_entry_t** hep = find_entry(ht, key, klen, NULL); #endif - if(hep && *hep) - ((*hep)->stamp) = time(NULL); + if(hep && *hep) + ((*hep)->stamp) = time(NULL); } int hsh_bump(hsh_t* ht) { - hsh_index_t* hi; - void* key = NULL; - void* val = NULL; - time_t least = 0; + hsh_index_t* hi; + void* key = NULL; + void* val = NULL; + time_t least = 0; #ifndef HSH_COPYKEYS - size_t klen = 0; + size_t klen = 0; #endif - for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) - { - if(least == 0 || hi->ths->stamp < least) + for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) { - least = hi->ths->stamp; - key = KEY_DATA(hi->ths); + if(least == 0 || hi->ths->stamp < least) + { + least = hi->ths->stamp; + key = KEY_DATA(hi->ths); #ifndef HSH_COPYKEYS - klen = hi->this->klen; + klen = hi->this->klen; #endif + } } - } - if(key) - { + if(key) + { #ifdef HSH_COPYKEYS - val = hsh_rem(ht, key); + val = hsh_rem(ht, key); #else - val = hsh_rem(ht, key, klen); + val = hsh_rem(ht, key, klen); #endif #ifdef HSH_CALLBACKS - if(val && ht->calls.f_freeval) - (ht->calls.f_freeval)(ht->calls.arg, (void*)val); + if(val && ht->calls.f_freeval) + (ht->calls.f_freeval)(ht->calls.arg, (void*)val); #endif - return 1; - } + return 1; + } - return 0; + return 0; } #endif /* HSH_TIMESTAMP */ -- cgit v1.2.3