From 1beb6f63170fef1c26502e0f27925765067c7762 Mon Sep 17 00:00:00 2001 From: Krisztian Litkey Date: Fri, 6 Apr 2012 14:13:36 +0300 Subject: [PATCH] common: added a simple hash table implementation. --- src/common/hashtbl.c | 348 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/common/hashtbl.h | 70 +++++++++++ 2 files changed, 418 insertions(+) create mode 100644 src/common/hashtbl.c create mode 100644 src/common/hashtbl.h diff --git a/src/common/hashtbl.c b/src/common/hashtbl.c new file mode 100644 index 0000000..d56aa61 --- /dev/null +++ b/src/common/hashtbl.c @@ -0,0 +1,348 @@ +#include + +#include "murphy/common/mm.h" +#include "murphy/common/list.h" +#include "murphy/common/hashtbl.h" + +#define MIN_NBUCKET 8 +#define MAX_NBUCKET 128 + +typedef struct { /* a hash bucket */ + mrp_list_hook_t entries; /* hook to hash table entries */ + mrp_list_hook_t used; /* hook to list of buckets in use */ +} bucket_t; + +typedef struct { /* a hash table entry */ + mrp_list_hook_t hook; /* hook to bucket chain */ + void *key; /* key for this entry */ + void *obj; /* object for this entry */ +} entry_t; + +typedef struct { /* iterator state */ + mrp_list_hook_t *bp, *bn; /* current bucket hook pointers */ + mrp_list_hook_t *ep, *en; /* current entry hook pointers */ + entry_t *entry; /* current entry */ + int verdict; /* remove-from-cb verdict */ +} iter_t; + +struct mrp_htbl_s { + bucket_t *buckets; /* hash table buckets */ + size_t nbucket; /* this many of them */ + mrp_list_hook_t used; /* buckets in use */ + mrp_htbl_comp_fn_t comp; /* key comparison function */ + mrp_htbl_hash_fn_t hash; /* key hash function */ + mrp_htbl_free_fn_t free; /* function to free an entry */ + iter_t *iter; /* active iterator state */ +}; + + +static size_t calc_buckets(size_t nbucket) +{ + size_t n; + + if (nbucket < MIN_NBUCKET) + nbucket = MIN_NBUCKET; + if (nbucket > MAX_NBUCKET) + nbucket = MAX_NBUCKET; + + for (n = MIN_NBUCKET; n < nbucket; n <<= 1) + ; + + return n; +} + + +mrp_htbl_t *mrp_htbl_create(mrp_htbl_config_t *cfg) +{ + mrp_htbl_t *ht; + size_t i, nbucket; + + + if (cfg->comp && cfg->hash) { + if ((ht = mrp_allocz(sizeof(*ht))) != NULL) { + if (cfg->nbucket != 0) + nbucket = cfg->nbucket; + else { + if (cfg->nentry != 0) + nbucket = cfg->nentry / 4; + else + nbucket = 4 * MIN_NBUCKET; + } + + ht->nbucket = calc_buckets(nbucket); + ht->comp = cfg->comp; + ht->hash = cfg->hash; + ht->free = cfg->free; + + mrp_list_init(&ht->used); + + ht->buckets = mrp_allocz(sizeof(*ht->buckets) * ht->nbucket); + if (ht->buckets != NULL) { + for (i = 0; i < ht->nbucket; i++) { + mrp_list_init(&ht->buckets[i].entries); + mrp_list_init(&ht->buckets[i].used); + } + + return ht; + } + else { + mrp_free(ht); + ht = NULL; + } + } + } + + return NULL; +} + + +void mrp_htbl_destroy(mrp_htbl_t *ht, int free) +{ + if (ht != NULL) { + if (free) + mrp_htbl_reset(ht, free); + + mrp_free(ht->buckets); + mrp_free(ht); + } +} + + +static inline void free_entry(mrp_htbl_t *ht, entry_t *entry, int free) +{ + if (free && ht->free) + ht->free(entry->key, entry->obj); + mrp_free(entry); +} + + +void mrp_htbl_reset(mrp_htbl_t *ht, int free) +{ + mrp_list_hook_t *bp, *bn, *ep, *en; + bucket_t *bucket; + entry_t *entry; + + mrp_list_foreach(&ht->used, bp, bn) { + bucket = mrp_list_entry(bp, bucket_t, used); + + mrp_list_foreach(&bucket->entries, ep, en) { + entry = mrp_list_entry(ep, entry_t, hook); + mrp_list_delete(ep); + free_entry(ht, entry, free); + } + + mrp_list_delete(&bucket->used); + } +} + + +int mrp_htbl_insert(mrp_htbl_t *ht, void *key, void *object) +{ + uint32_t idx = ht->hash(key) & (ht->nbucket - 1); + bucket_t *bucket = ht->buckets + idx; + int first = mrp_list_empty(&bucket->entries); + entry_t *entry; + + if ((entry = mrp_allocz(sizeof(*entry))) != NULL) { + entry->key = key; + entry->obj = object; + mrp_list_append(&bucket->entries, &entry->hook); + if (first) + mrp_list_append(&ht->used, &bucket->used); + + return TRUE; + } + else + return FALSE; +} + + +static inline entry_t *lookup(mrp_htbl_t *ht, void *key, bucket_t **bucketp) +{ + uint32_t idx = ht->hash(key) & (ht->nbucket - 1); + bucket_t *bucket = ht->buckets + idx; + mrp_list_hook_t *p, *n; + entry_t *entry; + + mrp_list_foreach(&bucket->entries, p, n) { + entry = mrp_list_entry(p, entry_t, hook); + + if (!ht->comp(entry->key, key)) { + if (bucketp != NULL) + *bucketp = bucket; + return entry; + } + } + + return NULL; +} + + +void *mrp_htbl_lookup(mrp_htbl_t *ht, void *key) +{ + entry_t *entry; + + entry = lookup(ht, key, NULL); + if (entry != NULL) + return entry->obj; + else + return NULL; +} + + +static void delete_from_bucket(mrp_htbl_t *ht, bucket_t *bucket, entry_t *entry) +{ + mrp_list_hook_t *eh = &entry->hook; + + + /* + * If there is an iterator active and this entry would + * have been the next one to iterate over, we need to + * update the iterator to skip to the next entry instead + * as this one will be removed. Failing to update the + * iterator could crash mrp_htbl_foreach or drive it into + * an infinite loop. + */ + + if (ht->iter != NULL && ht->iter->en == eh) + ht->iter->en = eh->next; + + mrp_list_delete(eh); + + + /* + * If there is an iterator active and this bucket would + * have been the next one to iterate over, we need to + * update the iterator to skip to the next bucket instead + * as this one just became empty and will be removed from + * the used bucket list. Failing to update the iterator + * could drive mrp_htbl_foreach into an infinite loop + * because of the unexpected hop from the used bucket list + * (to a single empty bucket). + */ + + if (ht->iter != NULL && mrp_list_empty(&bucket->entries)) { + if (ht->iter->bn == &bucket->used) + ht->iter->bn = bucket->used.next; + + mrp_list_delete(&bucket->used); + } +} + + +void *mrp_htbl_remove(mrp_htbl_t *ht, void *key, int free) +{ + bucket_t *bucket; + entry_t *entry; + void *object; + + /* + * We need to check the found entry and its hash-bucket + * against any potentially active iterator. Special care + * needs to be taken if the entry is being iterated over + * or if the bucket becomes empty and it would be the next + * bucket to iterate over. The former is taken care of + * here while the latter is handled in delete_from_bucket. + */ + if ((entry = lookup(ht, key, &bucket)) != NULL) { + delete_from_bucket(ht, bucket, entry); + object = entry->obj; + + if (ht->iter != NULL && entry == ht->iter->entry) /* being iterated */ + ht->iter->verdict = free ? MRP_HTBL_ITER_DELETE : 0; + else { + free_entry(ht, entry, free); + } + } + else + object = NULL; + + return object; +} + + +int mrp_htbl_foreach(mrp_htbl_t *ht, mrp_htbl_iter_cb_t cb, void *user_data) +{ + iter_t iter; + bucket_t *bucket; + entry_t *entry; + int cb_verdict, ht_verdict; + + /* + * Now we can only handle a single callback-based iterator. + * If there is already one we're busy so just bail out. + */ + if (ht->iter != NULL) + return FALSE; + + mrp_clear(&iter); + ht->iter = &iter; + + mrp_list_foreach(&ht->used, iter.bp, iter.bn) { + bucket = mrp_list_entry(iter.bp, bucket_t, used); + + mrp_list_foreach(&bucket->entries, iter.ep, iter.en) { + iter.entry = entry = mrp_list_entry(iter.ep, entry_t, hook); + cb_verdict = cb(entry->key, entry->obj, user_data); + ht_verdict = iter.verdict; + + /* delete was called from cb (unhashed entry and marked it) */ + if (ht_verdict & MRP_HTBL_ITER_DELETE) { + free_entry(ht, entry, TRUE); + } + else { + /* cb wants us to unhash (safe even if unhashed in remove) */ + if (cb_verdict & MRP_HTBL_ITER_UNHASH) + mrp_list_delete(iter.ep); + /* cb want us to free entry (and remove was not called) */ + if (cb_verdict & MRP_HTBL_ITER_DELETE) + free_entry(ht, entry, TRUE); + + /* cb wants to stop iterating */ + if (cb_verdict & MRP_HTBL_ITER_STOP) + goto out; + } + } + } + + out: + ht->iter = NULL; + + return TRUE; +} + + +void *mrp_htbl_find(mrp_htbl_t *ht, mrp_htbl_find_cb_t cb, void *user_data) +{ + iter_t iter; + bucket_t *bucket; + entry_t *entry, *found; + + /* + * Bail out if there is also an iterator active... + */ + if (ht->iter != NULL) + return FALSE; + + mrp_clear(&iter); + ht->iter = &iter; + found = NULL; + + mrp_list_foreach(&ht->used, iter.bp, iter.bn) { + bucket = mrp_list_entry(iter.bp, bucket_t, used); + + mrp_list_foreach(&bucket->entries, iter.ep, iter.en) { + entry = mrp_list_entry(iter.ep, entry_t, hook); + + if (cb(entry->key, entry->obj, user_data)) { + found = entry->obj; + goto out; + } + } + } + + out: + ht->iter = NULL; + + return found; +} diff --git a/src/common/hashtbl.h b/src/common/hashtbl.h new file mode 100644 index 0000000..cf46109 --- /dev/null +++ b/src/common/hashtbl.h @@ -0,0 +1,70 @@ +#ifndef __MURPHY_HASHTBL_H__ +#define __MURPHY_HASHTBL_H__ + + +MRP_CDECL_BEGIN + +typedef struct mrp_htbl_s mrp_htbl_t; + +/** Prototype for key comparison functions. */ +typedef int (*mrp_htbl_comp_fn_t)(const void *key1, const void *key2); + +/** Prototoype for key hash functions. */ +typedef uint32_t (*mrp_htbl_hash_fn_t)(const void *key); + +/** Prototype for functions used to free entries. */ +typedef void (*mrp_htbl_free_fn_t)(void *key, void *object); + + +/* + * hash table configuration + */ +typedef struct { + size_t nentry; /* estimated entries */ + mrp_htbl_comp_fn_t comp; /* comparison function */ + mrp_htbl_hash_fn_t hash; /* hash function */ + mrp_htbl_free_fn_t free; /* freeing function */ + size_t nbucket; /* number of buckets, or 0 */ +} mrp_htbl_config_t; + + +/** Create a new hash table with the given configuration. */ +mrp_htbl_t *mrp_htbl_create(mrp_htbl_config_t *cfg); + +/** Destroy a hash table, free all entries unless @free is FALSE. */ +void mrp_htbl_destroy(mrp_htbl_t *ht, int free); + +/** Reset a hash table, also free all entries unless @free is FALSE. */ +void mrp_htbl_reset(mrp_htbl_t *ht, int free); + +/** Insert the given @key/@object pair to the hash table. */ +int mrp_htbl_insert(mrp_htbl_t *ht, void *key, void *object); + +/** Remove and return the object for @key, also free unless @free is FALSE. */ +void *mrp_htbl_remove(mrp_htbl_t *ht, void *key, int free); + +/** Look up the object corresponding to @key. */ +void *mrp_htbl_lookup(mrp_htbl_t *ht, void *key); + +/** Find the first matching entry in a hash table. */ +typedef int (*mrp_htbl_find_cb_t)(void *key, void *object, void *user_data); +void *mrp_htbl_find(mrp_htbl_t *ht, mrp_htbl_find_cb_t cb, void *user_data); + + +/* + * hash table iterators + */ + +enum { + MRP_HTBL_ITER_STOP = 0x0, /* stop iterating */ + MRP_HTBL_ITER_MORE = 0x1, /* keep iterating */ + MRP_HTBL_ITER_UNHASH = 0x2, /* unhash without freeing */ + MRP_HTBL_ITER_DELETE = 0x6, /* unhash and free */ +}; + +typedef int (*mrp_htbl_iter_cb_t)(void *key, void *object, void *user_data); +int mrp_htbl_foreach(mrp_htbl_t *ht, mrp_htbl_iter_cb_t cb, void *user_data); + +MRP_CDECL_END + +#endif /* __MURPHY_HASHTBL_H__ */ -- 2.7.4