diff options
Diffstat (limited to 'src/shared/shl-htable.h')
| -rw-r--r-- | src/shared/shl-htable.h | 222 |
1 files changed, 222 insertions, 0 deletions
diff --git a/src/shared/shl-htable.h b/src/shared/shl-htable.h new file mode 100644 index 0000000..9591180 --- /dev/null +++ b/src/shared/shl-htable.h @@ -0,0 +1,222 @@ +/* + * SHL - Dynamic hash-table + * + * Copyright (c) 2010-2013 David Herrmann <dh.herrmann@gmail.com> + * Licensed under LGPLv2+ - see LICENSE_htable file for details + */ + +/* + * Dynamic hash-table + * Implementation of a self-resizing hashtable to store arbitrary objects. + * Entries are not allocated by the table itself but are user-allocated. A + * single entry can be stored multiple times in the hashtable. No + * maintenance-members need to be embedded in user-allocated objects. However, + * the key (and optionally the hash) must be stored in the objects. + * + * Uses internally the htable from CCAN. See LICENSE_htable. + */ + +#ifndef SHL_HTABLE_H +#define SHL_HTABLE_H + +#include <limits.h> +#include <stdbool.h> +#include <stddef.h> +#include <stdint.h> +#include <stdlib.h> + +/* miscellaneous */ + +#define shl_htable_offsetof(pointer, type, member) ({ \ + const typeof(((type*)0)->member) *__ptr = (pointer); \ + (type*)(((char*)__ptr) - offsetof(type, member)); \ + }) + +/* htable */ + +struct shl_htable_int { + size_t (*rehash)(const void *elem, void *priv); + void *priv; + unsigned int bits; + size_t elems, deleted, max, max_with_deleted; + /* These are the bits which are the same in all pointers. */ + uintptr_t common_mask, common_bits; + uintptr_t perfect_bit; + uintptr_t *table; +}; + +struct shl_htable { + bool (*compare) (const void *a, const void *b); + struct shl_htable_int htable; +}; + +#define SHL_HTABLE_INIT(_obj, _compare, _rehash, _priv) \ + { \ + .compare = (_compare), \ + .htable = { \ + .rehash = (_rehash), \ + .priv = (_priv), \ + .bits = 0, \ + .elems = 0, \ + .deleted = 0, \ + .max = 0, \ + .max_with_deleted = 0, \ + .common_mask = -1, \ + .common_bits = 0, \ + .perfect_bit = 0, \ + .table = &(_obj).htable.perfect_bit \ + } \ + } + +void shl_htable_init(struct shl_htable *htable, + bool (*compare) (const void *a, const void *b), + size_t (*rehash)(const void *elem, void *priv), + void *priv); +void shl_htable_clear(struct shl_htable *htable, + void (*free_cb) (void *elem, void *ctx), + void *ctx); +void shl_htable_visit(struct shl_htable *htable, + void (*visit_cb) (void *elem, void *ctx), + void *ctx); +bool shl_htable_lookup(struct shl_htable *htable, const void *obj, size_t hash, + void **out); +int shl_htable_insert(struct shl_htable *htable, const void *obj, size_t hash); +bool shl_htable_remove(struct shl_htable *htable, const void *obj, size_t hash, + void **out); + +/* ulong htables */ + +#if SIZE_MAX < ULONG_MAX +# error "'size_t' is smaller than 'unsigned long'" +#endif + +bool shl_htable_compare_ulong(const void *a, const void *b); +size_t shl_htable_rehash_ulong(const void *elem, void *priv); + +#define SHL_HTABLE_INIT_ULONG(_obj) \ + SHL_HTABLE_INIT((_obj), shl_htable_compare_ulong, \ + shl_htable_rehash_ulong, \ + NULL) + +static inline void shl_htable_init_ulong(struct shl_htable *htable) +{ + shl_htable_init(htable, shl_htable_compare_ulong, + shl_htable_rehash_ulong, NULL); +} + +static inline void shl_htable_clear_ulong(struct shl_htable *htable, + void (*cb) (unsigned long *elem, + void *ctx), + void *ctx) +{ + shl_htable_clear(htable, (void (*) (void*, void*))cb, ctx); +} + +static inline void shl_htable_visit_ulong(struct shl_htable *htable, + void (*cb) (unsigned long *elem, + void *ctx), + void *ctx) +{ + shl_htable_visit(htable, (void (*) (void*, void*))cb, ctx); +} + +static inline bool shl_htable_lookup_ulong(struct shl_htable *htable, + unsigned long key, + unsigned long **out) +{ + return shl_htable_lookup(htable, (const void*)&key, (size_t)key, + (void**)out); +} + +static inline int shl_htable_insert_ulong(struct shl_htable *htable, + const unsigned long *key) +{ + return shl_htable_insert(htable, (const void*)key, (size_t)*key); +} + +static inline bool shl_htable_remove_ulong(struct shl_htable *htable, + unsigned long key, + unsigned long **out) +{ + return shl_htable_remove(htable, (const void*)&key, (size_t)key, + (void**)out); +} + +/* string htables */ + +bool shl_htable_compare_str(const void *a, const void *b); +size_t shl_htable_rehash_str(const void *elem, void *priv); + +#define SHL_HTABLE_INIT_STR(_obj) \ + SHL_HTABLE_INIT((_obj), shl_htable_compare_str, \ + shl_htable_rehash_str, \ + NULL) + +static inline void shl_htable_init_str(struct shl_htable *htable) +{ + shl_htable_init(htable, shl_htable_compare_str, + shl_htable_rehash_str, NULL); +} + +static inline void shl_htable_clear_str(struct shl_htable *htable, + void (*cb) (char **elem, + void *ctx), + void *ctx) +{ + shl_htable_clear(htable, (void (*) (void*, void*))cb, ctx); +} + +static inline void shl_htable_visit_str(struct shl_htable *htable, + void (*cb) (char **elem, + void *ctx), + void *ctx) +{ + shl_htable_visit(htable, (void (*) (void*, void*))cb, ctx); +} + +static inline size_t shl_htable_hash_str(struct shl_htable *htable, + const char *str, size_t *hash) +{ + size_t h; + + if (hash && *hash) { + h = *hash; + } else { + h = htable->htable.rehash((const void*)&str, NULL); + if (hash) + *hash = h; + } + + return h; +} + +static inline bool shl_htable_lookup_str(struct shl_htable *htable, + const char *str, size_t *hash, + char ***out) +{ + size_t h; + + h = shl_htable_hash_str(htable, str, hash); + return shl_htable_lookup(htable, (const void*)&str, h, (void**)out); +} + +static inline int shl_htable_insert_str(struct shl_htable *htable, + char **str, size_t *hash) +{ + size_t h; + + h = shl_htable_hash_str(htable, *str, hash); + return shl_htable_insert(htable, (const void*)str, h); +} + +static inline bool shl_htable_remove_str(struct shl_htable *htable, + const char *str, size_t *hash, + char ***out) +{ + size_t h; + + h = shl_htable_hash_str(htable, str, hash); + return shl_htable_remove(htable, (const void*)&str, h, (void **)out); +} + +#endif /* SHL_HTABLE_H */ |