diff options
| -rw-r--r-- | misc/hashtable.c | 175 | ||||
| -rw-r--r-- | misc/hashtable.h | 80 |
2 files changed, 255 insertions, 0 deletions
diff --git a/misc/hashtable.c b/misc/hashtable.c new file mode 100644 index 0000000..22a60ba --- /dev/null +++ b/misc/hashtable.c @@ -0,0 +1,175 @@ +#include <stdlib.h> +#include <stdint.h> + +#include "hashtable.h" + +#define KEYP(tbl, o) ((o) + (tbl)->keyoff) +#define CHAINP(tbl, o) *((void **)((o) + (tbl)->chainoff)) + +struct _htbl { + int (*eq)(const void *, const void *); + uint32_t (*hash)(const void *); + void **buckets; + size_t buckcnt; + size_t size; + size_t keyoff; + size_t chainoff; +}; + +struct _htbl * +_htbl_create(int (*eq)(const void *, const void *), + uint32_t (*hash)(const void *), size_t keyoff, size_t chainoff) +{ + struct _htbl *tbl = calloc(1, sizeof(*tbl)); + if (tbl == NULL) + return NULL; + tbl->size = 0; + tbl->buckcnt = 1; + tbl->keyoff = keyoff; + tbl->chainoff = chainoff; + tbl->hash = hash; + tbl->eq = eq; + tbl->buckets = calloc(tbl->buckcnt, sizeof(*tbl->buckets)); + if (tbl->buckets == NULL) { + free(tbl); + return NULL; + } + return tbl; +} + +void +_htbl_free(struct _htbl *tbl) +{ + free(tbl->buckets); + free(tbl); +} + +static void * +bucket_rev(struct _htbl *tbl, void *p, void *n) +{ + while (n != NULL) { + void *s = CHAINP(tbl, n); + CHAINP(tbl, n) = p; + p = n; + n = s; + } + return p; +} + +static void +bucket_insert(struct _htbl *tbl, void *o) +{ + size_t bi = tbl->hash(KEYP(tbl, o)) % tbl->buckcnt; + CHAINP(tbl, o) = tbl->buckets[bi]; + tbl->buckets[bi] = o; +} + +static void +_htbl_grow(struct _htbl *tbl) +{ + size_t ncnt = 2 * tbl->buckcnt + 1; + size_t ocnt = tbl->buckcnt; + void **obuckets = tbl->buckets; + void **nbuckets = calloc(ncnt, sizeof(*nbuckets)); + if (nbuckets == NULL) + return; + + tbl->buckcnt = ncnt; + tbl->buckets = nbuckets; + + for (size_t i = 0; i < ocnt; i++) { + void *o = bucket_rev(tbl, NULL, obuckets[i]); + while (o != NULL) { + void *s = CHAINP(tbl, o); + bucket_insert(tbl, o); + o = s; + } + } + + free(obuckets); +} + +void +_htbl_insert(struct _htbl *tbl, void *o) +{ + bucket_insert(tbl, o); + tbl->size++; + if (tbl->size > tbl->buckcnt * 4 / 5) + _htbl_grow(tbl); +} + +void * +_htbl_find(struct _htbl *tbl, const void *key) +{ + size_t bi = tbl->hash(key) % tbl->buckcnt; + for (void *ret = tbl->buckets[bi]; ret != NULL; ret = CHAINP(tbl, ret)) + if (tbl->eq(KEYP(tbl, ret), key)) + return ret; + return NULL; +} + +void * +_htbl_remove(struct _htbl *tbl, const void *key) +{ + size_t bi = tbl->hash(key) % tbl->buckcnt; + void *p = NULL, *o = tbl->buckets[bi]; + while (o != NULL && !tbl->eq(KEYP(tbl, o), key)) { + p = o; + o = CHAINP(tbl, o); + } + if (o != NULL) { + if (p == NULL) + tbl->buckets[bi] = CHAINP(tbl, o); + else + CHAINP(tbl, p) = CHAINP(tbl, o); + tbl->size--; + } + return o; +} + +void +_htbl_tov(struct _htbl *tbl, void **v) +{ + size_t vi = 0; + size_t bi = 0; + void *o = tbl->buckets[bi]; + while (vi < tbl->size) { + while (o == NULL) { + bi++; + o = tbl->buckets[bi]; + } + v[vi] = o; + vi++; + o = CHAINP(tbl, o); + } +} + +size_t +_htbl_size(struct _htbl *tbl) +{ + return tbl->size; +} + +void +_htbl_iter_init(struct _htbl *tbl, struct htbl_iter *it) +{ + it->tbl = tbl; + it->bi = 0; + it->cnt = 0; + it->obj = NULL; +} + +void * +_htbl_iter_next(struct htbl_iter *it) +{ + if (it->cnt == it->tbl->size) + return NULL; + it->obj = it->cnt == 0 ? + it->tbl->buckets[it->bi] : CHAINP(it->tbl, it->obj); + while (it->obj == NULL) { + it->bi++; + it->obj = it->tbl->buckets[it->bi]; + } + it->cnt++; + return it->obj; +} diff --git a/misc/hashtable.h b/misc/hashtable.h new file mode 100644 index 0000000..2dd227d --- /dev/null +++ b/misc/hashtable.h @@ -0,0 +1,80 @@ +#ifndef BTPD_HASHTABLE_H +#define BTPD_HASHTABLE_H + +struct htbl_iter { + struct _htbl *tbl; + size_t bi; + size_t cnt; + void *obj; +}; + +struct _htbl *_htbl_create(int (*equal)(const void *, const void *), + uint32_t (*hash)(const void *), size_t keyoff, size_t chainoff); +void _htbl_free(struct _htbl *tbl); +void _htbl_insert(struct _htbl *tbl, void *o); +void *_htbl_remove(struct _htbl *tbl, const void *key); +void *_htbl_find(struct _htbl *tbl, const void *key); +void _htbl_tov(struct _htbl *tb, void **v); +size_t _htbl_size(struct _htbl *tbl); +void _htbl_iter_init(struct _htbl *tbl, struct htbl_iter *it); +void *_htbl_iter_next(struct htbl_iter *it); + +#define HTBLTYPE(name, type, ktype, kname, cname) \ +__attribute__((always_inline)) static inline struct name * \ +name##_create(int (*equal)(const ktype *, const ktype *), \ + uint32_t (*hash)(const ktype *)) \ +{ \ + return (struct name *) \ + _htbl_create((int (*)(const void *, const void *))equal, \ + (uint32_t (*)(const void *))hash, offsetof(struct type, kname), \ + offsetof(struct type, cname)); \ +} \ +\ +__attribute__((always_inline)) static inline struct type * \ +name##_find(struct name *tbl, const ktype *key) \ +{ \ + return (struct type *)_htbl_find((struct _htbl *)tbl, key); \ +} \ +\ +__attribute__((always_inline)) static inline struct type * \ +name##_remove(struct name *tbl, const ktype *key) \ +{ \ + return (struct type *)_htbl_remove((struct _htbl *)tbl, key); \ +} \ +\ +__attribute__((always_inline)) static inline void \ +name##_free(struct name *tbl) \ +{ \ + _htbl_free((struct _htbl *)tbl); \ +} \ +\ +__attribute__((always_inline)) static inline void \ +name##_insert(struct name *tbl, struct type *o) \ +{ \ + _htbl_insert((struct _htbl *)tbl, o); \ +} \ +__attribute__((always_inline)) static inline void \ +name##_tov(struct name *tbl, struct type **v) \ +{ \ + _htbl_tov((struct _htbl *)tbl, (void **)v); \ +} \ +\ +__attribute__((always_inline)) static inline size_t \ +name##_size(struct name *tbl) \ +{ \ + return _htbl_size((struct _htbl *)tbl); \ +} \ +\ +__attribute__((always_inline)) static inline void \ +name##_iter_init(struct name *tbl, struct htbl_iter *it) \ +{ \ + _htbl_iter_init((struct _htbl *)tbl, it); \ +} \ +\ +__attribute__((always_inline)) static inline struct type * \ +name##_iter_next(struct htbl_iter *it) \ +{ \ + return (struct type *)_htbl_iter_next(it); \ +} + +#endif |