diff options
Diffstat (limited to 'common/hash.c')
| -rw-r--r-- | common/hash.c | 200 |
1 files changed, 100 insertions, 100 deletions
diff --git a/common/hash.c b/common/hash.c index 9bbe8ac..5f3308c 100644 --- a/common/hash.c +++ b/common/hash.c @@ -22,11 +22,11 @@ #include <stdlib.h> #include "hash.h" -#ifdef HASH_TIMESTAMP +#ifdef HSH_TIMESTAMP #include <time.h> #endif -#ifdef HASH_COPYKEYS +#ifdef HSH_COPYKEYS #define KEY_DATA(he) (void*)(((unsigned char*)(he)) + sizeof(*(he))) #else #define KEY_DATA(he) ((he)->key) @@ -41,18 +41,18 @@ * isn't too bad given that pools have a low allocation overhead. */ -typedef struct hash_entry_t hash_entry_t; +typedef struct hsh_entry_t hsh_entry_t; -struct hash_entry_t +struct hsh_entry_t { - hash_entry_t* next; + hsh_entry_t* next; unsigned int hash; -#ifndef HASH_COPYKEYS +#ifndef HSH_COPYKEYS const void* key; size_t klen; #endif const void* val; -#ifdef HASH_TIMESTAMP +#ifdef HSH_TIMESTAMP time_t stamp; #endif }; @@ -62,13 +62,13 @@ struct hash_entry_t * * We keep a pointer to the next hash entry here to allow the current * hash entry to be freed or otherwise mangled between calls to - * hash_next(). + * hsh_next(). */ -struct hash_index_t +struct hsh_index_t { - hash_t* ht; - hash_entry_t* ths; - hash_entry_t* next; + hsh_t* ht; + hsh_entry_t* ths; + hsh_entry_t* next; unsigned int index; }; @@ -79,30 +79,30 @@ struct hash_index_t * The count of hash entries may be greater depending on the chosen * collision rate. */ -struct hash_t +struct hsh_t { - hash_entry_t** array; - hash_index_t iterator; /* For hash_first(...) */ + hsh_entry_t** array; + hsh_index_t iterator; /* For hsh_first(...) */ unsigned int count; unsigned int max; -#ifdef HASH_COPYKEYS +#ifdef HSH_COPYKEYS unsigned int klen; #endif -#ifdef HASH_CALLBACKS - hash_table_calls_t calls; +#ifdef HSH_CALLBACKS + hsh_table_calls_t calls; #endif }; #define INITIAL_MAX 15 /* tunable == 2^n - 1 */ -#ifdef HASH_CALLBACKS +#ifdef HSH_CALLBACKS /* A copy of the memory call table we've been set to */ -static hash_memory_calls_t g_memory_calls_cpy; +static hsh_memory_calls_t g_memory_calls_cpy; /* Pointer to above. This indicates when we actually are set */ -static hash_memory_calls_t* g_memory_calls = NULL; +static hsh_memory_calls_t* g_memory_calls = NULL; static void* int_malloc(size_t len) { @@ -131,7 +131,7 @@ static void int_free(void* ptr) free(ptr); } -void hash_set_memory_calls(hash_memory_calls_t* hmc) +void hsh_set_memory_calls(hsh_memory_calls_t* hmc) { if(hmc == NULL) { @@ -144,7 +144,7 @@ void hash_set_memory_calls(hash_memory_calls_t* hmc) } } -void hash_set_table_calls(hash_t* ht, hash_table_calls_t* htc) +void hsh_set_table_calls(hsh_t* ht, hsh_table_calls_t* htc) { memcpy(&(ht->calls), htc, sizeof(ht->calls)); } @@ -161,24 +161,24 @@ void hash_set_table_calls(hash_t* ht, hash_table_calls_t* htc) * Hash creation functions. */ -static hash_entry_t** alloc_array(hash_t* ht, unsigned int max) +static hsh_entry_t** alloc_array(hsh_t* ht, unsigned int max) { - return int_malloc(sizeof(*(ht->array)) * (max + 1)); + return int_calloc(sizeof(*(ht->array)) * (max + 1)); } -#ifdef HASH_COPYKEYS -hash_t* hash_create(size_t klen) +#ifdef HSH_COPYKEYS +hsh_t* hsh_create(size_t klen) #else -hash_t* hash_create() +hsh_t* hsh_create() #endif { - hash_t* ht = int_malloc(sizeof(hash_t)); + 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 HASH_COPYKEYS +#ifdef HSH_COPYKEYS ht->klen = klen; #endif if(!ht->array) @@ -190,13 +190,13 @@ hash_t* hash_create() return ht; } -void hash_free(hash_t* ht) +void hsh_free(hsh_t* ht) { - hash_index_t* hi; + hsh_index_t* hi; - for(hi = hash_first(ht); hi; hi = hash_next(hi)) + for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) { -#ifdef HASH_CALLBACKS +#ifdef HSH_CALLBACKS if(hi->ths->val && ht->calls.f_freeval) (ht->calls.f_freeval)(ht->calls.arg, (void*)hi->ths->val); #endif @@ -213,7 +213,7 @@ void hash_free(hash_t* ht) * Hash iteration functions. */ -hash_index_t* hash_next(hash_index_t* hi) +hsh_index_t* hsh_next(hsh_index_t* hi) { hi->ths = hi->next; while(!hi->ths) @@ -227,27 +227,27 @@ hash_index_t* hash_next(hash_index_t* hi) return hi; } -hash_index_t* hash_first(hash_t* ht) +hsh_index_t* hsh_first(hsh_t* ht) { - hash_index_t* hi = &ht->iterator; + hsh_index_t* hi = &ht->iterator; hi->ht = ht; hi->index = 0; hi->ths = NULL; hi->next = NULL; - return hash_next(hi); + return hsh_next(hi); } -#ifdef HASH_COPYKEYS -void* hash_this(hash_index_t* hi, const void** key) +#ifdef HSH_COPYKEYS +void* hsh_this(hsh_index_t* hi, const void** key) #else -void* hash_this(hash_index_t* hi, const void** key, size_t* klen) +void* hsh_this(hsh_index_t* hi, const void** key, size_t* klen) #endif { if(key) *key = KEY_DATA(hi->ths); -#ifndef HASH_COPYKEYS +#ifndef HSH_COPYKEYS if(klen) *klen = hi->ths->klen; #endif @@ -260,10 +260,10 @@ void* hash_this(hash_index_t* hi, const void** key, size_t* klen) * Expanding a hash table */ -static int expand_array(hash_t* ht) +static int expand_array(hsh_t* ht) { - hash_index_t* hi; - hash_entry_t** new_array; + hsh_index_t* hi; + hsh_entry_t** new_array; unsigned int new_max; new_max = ht->max * 2 + 1; @@ -272,7 +272,7 @@ static int expand_array(hash_t* ht) if(!new_array) return 0; - for(hi = hash_first(ht); hi; hi = hash_next(hi)) + for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) { unsigned int i = hi->ths->hash & new_max; hi->ths->next = new_array[i]; @@ -296,19 +296,19 @@ static int expand_array(hash_t* ht) * that hash entries can be removed. */ -#ifdef HASH_COPYKEYS -static hash_entry_t** find_entry(hash_t* ht, const void* key, const void* val) +#ifdef HSH_COPYKEYS +static hsh_entry_t** find_entry(hsh_t* ht, const void* key, const void* val) #else -static hash_entry_t** find_entry(hash_t* ht, const void* key, size_t klen, const void* val) +static hsh_entry_t** find_entry(hsh_t* ht, const void* key, size_t klen, const void* val) #endif { - hash_entry_t** hep; - hash_entry_t* he; + hsh_entry_t** hep; + hsh_entry_t* he; const unsigned char* p; unsigned int hash; size_t i; -#ifdef HASH_COPYKEYS +#ifdef HSH_COPYKEYS size_t klen = ht->klen; #endif @@ -351,8 +351,8 @@ static hash_entry_t** find_entry(hash_t* ht, const void* key, size_t klen, const */ hash = 0; -#ifndef HASH_COPYKEYS - if(klen == HASH_KEY_STRING) +#ifndef HSH_COPYKEYS + if(klen == HSH_KEY_STRING) { for(p = key; *p; p++) hash = hash * 33 + *p; @@ -371,7 +371,7 @@ static hash_entry_t** find_entry(hash_t* ht, const void* key, size_t klen, const he; hep = &he->next, he = *hep) { if(he->hash == hash && -#ifndef HASH_COPYKEYS +#ifndef HSH_COPYKEYS he->klen == klen && #endif memcmp(KEY_DATA(he), key, klen) == 0) @@ -382,7 +382,7 @@ static hash_entry_t** find_entry(hash_t* ht, const void* key, size_t klen, const return hep; /* add a new entry for non-NULL val */ -#ifdef HASH_COPYKEYS +#ifdef HSH_COPYKEYS he = int_malloc(sizeof(*he) + klen); #else he = int_malloc(sizeof(*he)); @@ -390,7 +390,7 @@ static hash_entry_t** find_entry(hash_t* ht, const void* key, size_t klen, const if(he) { -#ifdef HASH_COPYKEYS +#ifdef HSH_COPYKEYS /* Key data points past end of entry */ memcpy(KEY_DATA(he), key, klen); #else @@ -403,7 +403,7 @@ static hash_entry_t** find_entry(hash_t* ht, const void* key, size_t klen, const he->hash = hash; he->val = val; -#ifdef HASH_TIMESTAMP +#ifdef HSH_TIMESTAMP he->stamp = 0; #endif @@ -414,14 +414,14 @@ static hash_entry_t** find_entry(hash_t* ht, const void* key, size_t klen, const return hep; } -#ifdef HASH_COPYKEYS -void* hash_get(hash_t* ht, const void *key) +#ifdef HSH_COPYKEYS +void* hsh_get(hsh_t* ht, const void *key) { - hash_entry_t** he = find_entry(ht, key, NULL); + hsh_entry_t** he = find_entry(ht, key, NULL); #else -void* hash_get(hash_t* ht, const void *key, size_t klen) +void* hsh_get(hsh_t* ht, const void *key, size_t klen) { - hash_entry_t** he = find_entry(ht, key, klen, NULL); + hsh_entry_t** he = find_entry(ht, key, klen, NULL); #endif if(he && *he) @@ -430,19 +430,19 @@ void* hash_get(hash_t* ht, const void *key, size_t klen) return NULL; } -#ifdef HASH_COPYKEYS -int hash_set(hash_t* ht, const void* key, void* val) +#ifdef HSH_COPYKEYS +int hsh_set(hsh_t* ht, const void* key, void* val) { - hash_entry_t** hep = find_entry(ht, key, val); + hsh_entry_t** hep = find_entry(ht, key, val); #else -int hash_set(hash_t* ht, const void* key, size_t klen, void* val) +int hsh_set(hsh_t* ht, const void* key, size_t klen, void* val) { - hash_entry_t** hep = find_entry(ht, key, klen, val); + hsh_entry_t** hep = find_entry(ht, key, klen, val); #endif if(hep && *hep) { -#ifdef HASH_CALLBACKS +#ifdef HSH_CALLBACKS if((*hep)->val && (*hep)->val != val && ht->calls.f_freeval) (ht->calls.f_freeval)(ht->calls.arg, (void*)((*hep)->val)); #endif @@ -450,7 +450,7 @@ int hash_set(hash_t* ht, const void* key, size_t klen, void* val) /* replace entry */ (*hep)->val = val; -#ifdef HASH_TIMESTAMP +#ifdef HSH_TIMESTAMP /* Update or set the timestamp */ (*hep)->stamp = time(NULL); #endif @@ -468,20 +468,20 @@ int hash_set(hash_t* ht, const void* key, size_t klen, void* val) return 0; } -#ifdef HASH_COPYKEYS -void* hash_rem(hash_t* ht, const void* key) +#ifdef HSH_COPYKEYS +void* hsh_rem(hsh_t* ht, const void* key) { - hash_entry_t** hep = find_entry(ht, key, NULL); + hsh_entry_t** hep = find_entry(ht, key, NULL); #else -void* hash_rem(hash_t* ht, const void* key, size_t klen) +void* hsh_rem(hsh_t* ht, const void* key, size_t klen) { - hash_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) { - hash_entry_t* old = *hep; + hsh_entry_t* old = *hep; *hep = (*hep)->next; --ht->count; val = (void*)old->val; @@ -491,30 +491,30 @@ void* hash_rem(hash_t* ht, const void* key, size_t klen) return val; } -unsigned int hash_count(hash_t* ht) +unsigned int hsh_count(hsh_t* ht) { return ht->count; } -#ifdef HASH_TIMESTAMP -int hash_purge(hash_t* ht, time_t stamp) +#ifdef HSH_TIMESTAMP +int hsh_purge(hsh_t* ht, time_t stamp) { - hash_index_t* hi; + hsh_index_t* hi; int r = 0; void* val; - for(hi = hash_first(ht); hi; hi = hash_next(hi)) + for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) { if(hi->ths->stamp < stamp) { /* No need to check for errors as we're deleting */ -#ifdef HASH_COPYKEYS - val = hash_rem(ht, KEY_DATA(hi->ths)); +#ifdef HSH_COPYKEYS + val = hsh_rem(ht, KEY_DATA(hi->ths)); #else - val = hash_rem(ht, hi->ths->key, hi->ths->klen); + val = hsh_rem(ht, hi->ths->key, hi->ths->klen); #endif -#ifdef HASH_CALLBACKS +#ifdef HSH_CALLBACKS if(val && ht->calls.f_freeval) (ht->calls.f_freeval)(ht->calls.arg, val); #endif @@ -526,37 +526,37 @@ int hash_purge(hash_t* ht, time_t stamp) return r; } -#ifdef HASH_COPYKEYS -void hash_touch(hash_t* ht, const void* key) +#ifdef HSH_COPYKEYS +void hsh_touch(hsh_t* ht, const void* key) { - hash_entry_t** hep = find_entry(ht, key, NULL); + hsh_entry_t** hep = find_entry(ht, key, NULL); #else -void hash_touch(hash_t* ht, const void* key, size_t* klen) +void hsh_touch(hsh_t* ht, const void* key, size_t* klen) { - hash_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); } -int hash_bump(hash_t* ht) +int hsh_bump(hsh_t* ht) { - hash_index_t* hi; + hsh_index_t* hi; void* key = NULL; void* val = NULL; time_t least = 0; -#ifndef HASH_COPYKEYS +#ifndef HSH_COPYKEYS size_t klen = 0; #endif - for(hi = hash_first(ht); hi; hi = hash_next(hi)) + for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) { if(least == 0 || hi->ths->stamp < least) { least = hi->ths->stamp; key = KEY_DATA(hi->ths); -#ifndef HASH_COPYKEYS +#ifndef HSH_COPYKEYS klen = hi->this->klen; #endif } @@ -564,13 +564,13 @@ int hash_bump(hash_t* ht) if(key) { -#ifdef HASH_COPYKEYS - val = hash_rem(ht, key); +#ifdef HSH_COPYKEYS + val = hsh_rem(ht, key); #else - val = hash_rem(ht, key, klen); + val = hsh_rem(ht, key, klen); #endif -#ifdef HASH_CALLBACKS +#ifdef HSH_CALLBACKS if(val && ht->calls.f_freeval) (ht->calls.f_freeval)(ht->calls.arg, (void*)val); #endif @@ -581,4 +581,4 @@ int hash_bump(hash_t* ht) return 0; } -#endif /* HASH_TIMESTAMP */ +#endif /* HSH_TIMESTAMP */ |