diff options
Diffstat (limited to 'common')
| -rw-r--r-- | common/hash.c | 112 | ||||
| -rw-r--r-- | common/hash.h | 293 |
2 files changed, 268 insertions, 137 deletions
diff --git a/common/hash.c b/common/hash.c index 6471803..9bbe8ac 100644 --- a/common/hash.c +++ b/common/hash.c @@ -89,38 +89,90 @@ struct hash_t unsigned int klen; #endif #ifdef HASH_CALLBACKS - hash_free_val_t f_free; - void* arg; + hash_table_calls_t calls; #endif }; #define INITIAL_MAX 15 /* tunable == 2^n - 1 */ +#ifdef HASH_CALLBACKS + +/* A copy of the memory call table we've been set to */ +static hash_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 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); +} + +static void* int_calloc(size_t len) +{ + 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); +} + +void hash_set_memory_calls(hash_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; + } +} + +void hash_set_table_calls(hash_t* ht, hash_table_calls_t* htc) +{ + memcpy(&(ht->calls), htc, sizeof(ht->calls)); +} + +#else + +#define int_malloc malloc +#define int_free free + +#endif + + /* * Hash creation functions. */ static hash_entry_t** alloc_array(hash_t* ht, unsigned int max) { - return malloc(sizeof(*(ht->array)) * (max + 1)); + return int_malloc(sizeof(*(ht->array)) * (max + 1)); } -#ifdef HASH_CALLBACKS - #ifdef HASH_COPYKEYS -hash_t* hash_create(size_t klen, hash_free_val_t f_free, void* arg) - #else -hash_t* hash_create(hash_free_val_t f_free, void* arg) - #endif -#else - #ifdef HASH_COPYKEYS +#ifdef HASH_COPYKEYS hash_t* hash_create(size_t klen) - #else +#else hash_t* hash_create() - #endif #endif { - hash_t* ht = malloc(sizeof(hash_t)); + hash_t* ht = int_malloc(sizeof(hash_t)); if(ht) { ht->count = 0; @@ -129,13 +181,9 @@ hash_t* hash_create() #ifdef HASH_COPYKEYS ht->klen = klen; #endif -#ifdef HASH_CALLBACKS - ht->f_free = f_free; - ht->arg = arg; -#endif if(!ht->array) { - free(ht); + int_free(ht); return NULL; } } @@ -149,16 +197,16 @@ void hash_free(hash_t* ht) for(hi = hash_first(ht); hi; hi = hash_next(hi)) { #ifdef HASH_CALLBACKS - if(hi->ths->val && ht->f_free) - ht->f_free(ht->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 - free(hi->ths); + int_free(hi->ths); } if(ht->array) - free(ht->array); + int_free(ht->array); - free(ht); + int_free(ht); } /* @@ -335,9 +383,9 @@ static hash_entry_t** find_entry(hash_t* ht, const void* key, size_t klen, const /* add a new entry for non-NULL val */ #ifdef HASH_COPYKEYS - he = malloc(sizeof(*he) + klen); + he = int_malloc(sizeof(*he) + klen); #else - he = malloc(sizeof(*he)); + he = int_malloc(sizeof(*he)); #endif if(he) @@ -395,8 +443,8 @@ int hash_set(hash_t* ht, const void* key, size_t klen, void* val) if(hep && *hep) { #ifdef HASH_CALLBACKS - if((*hep)->val && (*hep)->val != val && ht->f_free) - ht->f_free(ht->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 */ @@ -467,8 +515,8 @@ int hash_purge(hash_t* ht, time_t stamp) #endif #ifdef HASH_CALLBACKS - if(val && ht->f_free) - (ht->f_free)(ht->arg, val); + if(val && ht->calls.f_freeval) + (ht->calls.f_freeval)(ht->calls.arg, val); #endif r++; @@ -523,8 +571,8 @@ int hash_bump(hash_t* ht) #endif #ifdef HASH_CALLBACKS - if(val && ht->f_free) - (ht->f_free)(ht->arg, (void*)val); + if(val && ht->calls.f_freeval) + (ht->calls.f_freeval)(ht->calls.arg, (void*)val); #endif return 1; diff --git a/common/hash.h b/common/hash.h index 2b22b64..174c209 100644 --- a/common/hash.h +++ b/common/hash.h @@ -21,30 +21,43 @@ #ifndef __HASH_H__ #define __HASH_H__ +#ifdef __cplusplus +extern "C" { +#endif + /* + * OPTIONAL FEATURES + * * Features to define. You need to build both this file and - * the corresponding hash.c file with whatever options you set here + * the corresponding hash.c file with whatever options you set here. + * These affect the method signatures, so see the sections below + * for the actual options */ /* Keep timestamps for the entries */ -#define HASH_TIMESTAMP 1 +#define HASH_TIMESTAMP /* Keep key values internally */ -#define HASH_COPYKEYS 1 +#define HASH_COPYKEYS /* Hash callback functionality */ -#define HASH_CALLBACKS 1 +#define HASH_CALLBACKS +/* + * ARGUMENT DOCUMENTATION + * + * ht: The hashtable + * key: Pointer to the key value + * klen: The length of the key + * val: Pointer to the value + * hi: A hashtable iterator + * stamp: A unix timestamp + */ -#ifdef __cplusplus -extern "C" { -#endif -/** - * When passing a key to hash_set or hash_get, this value can be passed to - * indicate a string-valued key, and have hash compute the length automatically. +/* ---------------------------------------------------------------------------------- + * TYPES */ -#define HASH_KEY_STRING (-1) /* Abstract type for hash tables. */ typedef struct hash_t hash_t; @@ -52,146 +65,216 @@ typedef struct hash_t hash_t; /* Abstract type for scanning hash tables. */ typedef struct hash_index_t hash_index_t; -/* A callback during remove operations */ -#ifdef HASH_CALLBACKS - typedef void (*hash_free_val_t)(void* arg, void* val); -#endif -/* Create a hash table */ -#ifdef HASH_CALLBACKS - #ifdef HASH_COPYKEYS - hash_t* hash_create(size_t klen, hash_free_val_t f_free, void* arg); - #else - hash_t* hash_create(hash_free_val_t f_free, void* arg); - #endif -#else - #ifdef HASH_COPYKEYS - hash_t* hash_create(size_t klen); - #else - hash_t* hash_create(); - #endif -#endif /* HASH_CALLBACKS */ +/* ---------------------------------------------------------------------------------- + * COPY KEYS MODE + * + * Use these functions when you want specific length keys, with those + * keys stored in the hashtable itself. + */ + +#ifdef HASH_COPYKEYS +/* + * hash_create : Create a hash table + * - returns an allocated hashtable + */ +hash_t* hash_create(size_t klen); -/* To release all resources for a hash table */ +/* + * hash_free : Free a hash table + */ void hash_free(hash_t* ht); +/* + * hash_count: Number of values in hash table + * - returns the number of entries in hash table + */ +unsigned int hash_count(hash_t* ht); -/** - * Associate a value with a key in a hash table. - * - * ht The hash table - * key Pointer to the key - * klen Length of the key. Can be HASH_KEY_STRING to use the string length. - * val Value to associate with the key - * - * val must not be null +/* + * hash_get: Retrieves a value from the hash table + * - returns the value of the entry */ -#ifdef HASH_COPYKEYS - int hash_set(hash_t* ht, const void* key, void* val); -#else - int hash_set(hash_t* ht, const void* key, size_t klen, void* val); -#endif +void* hash_get(hash_t* ht, const void* key); +/* + * hash_set: Set a value in the hash table + * - returns 1 if the entry was added properly + */ +int hash_set(hash_t* ht, const void* key, void* val); -/** - * Remove a value and key form the hash table - * - * ht The hash table - * key Pointer to the key - * klen Length of the key. Can be HASH_KEY_STRING to use the string length +/* + * hash_rem: Remove a value from the hash table + * - returns the value of the removed entry */ -#ifdef HASH_COPYKEYS - void* hash_rem(hash_t* ht, const void* key); -#else - void* hash_rem(hash_t* ht, const void* key, size_t klen); -#endif +void* hash_rem(hash_t* ht, const void* key); +/* + * hash_first: Start enumerating through the hash table + * - returns a hash iterator + */ +hash_index_t* hash_first(hash_t* ht); -/** - * Look up the value associated with a key in a hash table. - * - * ht The hash table - * key Pointer to the key - * klen Length of the key. Can be APR_HASH_KEY_STRING to use the string length. +/* + * hash_next: Enumerate through hash table + * - returns the hash iterator or null when no more entries + */ +hash_index_t* hash_next(hash_index_t* hi); + +/* + * hash_this: While enumerating get current value + * - returns the value that the iterator currently points to + */ +void* hash_this(hash_index_t* hi, const void** key); + + + +/* ---------------------------------------------------------------------------------- + * VARIABLE KEYS MODE * - * Returns NULL if the key is not present. + * Use these functions if you want to use variable length keys or for some + * other reason don't want the keys stored in the hash table. */ -#ifdef HASH_COPYKEYS - void* hash_get(hash_t* ht, const void* key); + #else - void* hash_get(hash_t* ht, const void* key, size_t klen); -#endif +/* + * hash_create : Create a hash table + * - returns an allocated hashtable + */ +hash_t* hash_create(); -/** - * Start iterating over the entries in a hash table. - * - * ht The hash table - * - * There is no restriction on adding or deleting hash entries during - * an iteration (although the results may be unpredictable unless all you do - * is delete the current entry). Only one iteration can be in progress at once. +/* + * hash_free : Free a hash table */ -hash_index_t* hash_first(hash_t* ht); +void hash_free(hash_t* ht); +/* + * hash_count: Number of values in hash table + * - returns the number of entries in hash table + */ +unsigned int hash_count(hash_t* ht); -/** - * Continue iterating over the entries in a hash table. - * - * hi The iteration state - * - * Returns a pointer to the updated iteration state. - * NULL if there are no more entries. +/* + * hash_get: Retrieves a value from the hash table + * - returns the value of the entry + */ +void* hash_get(hash_t* ht, const void* key, size_t klen); + +/* + * hash_set: Set a value in the hash table + * - returns 1 if the entry was added properly + */ +int hash_set(hash_t* ht, const void* key, size_t klen, void* val); + +/* + * hash_rem: Remove a value from the hash table + * - returns the value of the removed entry + */ +void* hash_rem(hash_t* ht, const void* key, size_t klen); + +/* + * hash_first: Start enumerating through the hash table + * - returns a hash iterator + */ +hash_index_t* hash_first(hash_t* ht); + +/* + * hash_next: Enumerate through hash table + * - returns the hash iterator or null when no more entries */ hash_index_t* hash_next(hash_index_t* hi); +/* + * hash_this: While enumerating get current value + * - returns the value that the iterator currently points to + */ +void* hash_this(hash_index_t* hi, const void** key, size_t* klen); -/** - * Get the current entry's details from the iteration state. - * - * hi The iteration state - * key Return pointer for the pointer to the key. - * klen Return pointer for the key length. - * val Return pointer for the associated value. - * - * The return pointers should point to a variable that will be set to the - * corresponding data, or they may be NULL if the data isn't interesting. +/* + * This can be passed as 'klen' in any of the above functions to indicate + * a string-valued key, and have hash compute the length automatically. */ -#ifdef HASH_COPYKEYS - void* hash_this(hash_index_t* hi, const void** key); -#else - void* hash_this(hash_index_t* hi, const void** key, size_t* klen); +#define HASH_KEY_STRING (-1) + #endif -/** - * Purge entries before a certain timestamp + +/* ---------------------------------------------------------------------------------- + * TIMESTAMP FUNCTIONALITY + * + * Use these functions to include functionality which tracks the time + * each key was added or changed. This is useful for caches. Use these + * functions in addition to one of the above 'key' modes. */ + #ifdef HASH_TIMESTAMP +/* + * hash_purge: Purge entries before a certain timestamp + * - returns the number of entries purged + */ int hash_purge(hash_t* ht, time_t stamp); +/* + * hash_touch: Touch an entry to make it's timestamp current + */ #ifdef HASH_COPYKEYS void hash_touch(hash_t* ht, const void* key); #else void hash_touch(hash_t* ht, const void* key, size_t* klen); #endif -/* Bumps the oldest out */ +/* + * hash_bump: Bumps the oldest entry out + */ int hash_bump(hash_t* ht); #endif -/** - * Get the number of key/value pairs in the hash table. - * - * ht The hash table + +/* ---------------------------------------------------------------------------------- + * CALLBACK FUNCTIONALITY * - * The number of key/value pairs in the hash table. + * Use these functions to replace certain calls (malloc, free etc...) as + * well as to get callbacks when an item is discarded. */ -unsigned int hash_count(hash_t* ht); + +#ifdef HASH_CALLBACKS + +typedef void* (*hash_falloc)(void* arg, size_t len); +typedef void (*hash_ffree)(void* arg, void* ptr); + +typedef struct hash_memory_calls +{ + hash_falloc f_alloc; + hash_ffree f_free; + void* arg; +} +hash_memory_calls_t; + +/* Set the global memory calls */ +void hash_set_memory_calls(hash_memory_calls_t* hmc); + + +typedef void (*hash_ffreeval)(void* arg, void* val); + +typedef struct hash_table_calls +{ + hash_ffreeval f_freeval; + void* arg; +} +hash_table_calls_t; + +/* Set the per table free value call */ +void hash_set_table_calls(hash_t* ht, hash_table_calls_t* htc); + +#endif + + #ifdef __cplusplus |