From cb1a40859029f33184355475e51fec95afb79a73 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Yaroslav=20de=20la=20Pe=C3=B1a=20Smirnov?= Date: Sat, 22 Jul 2023 03:03:09 +0300 Subject: init Just some C wares; hmap, list, optional, unit tests. --- hmap/hmap.c | 297 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 297 insertions(+) create mode 100644 hmap/hmap.c (limited to 'hmap/hmap.c') diff --git a/hmap/hmap.c b/hmap/hmap.c new file mode 100644 index 0000000..8bc5760 --- /dev/null +++ b/hmap/hmap.c @@ -0,0 +1,297 @@ +/* SPDX-License-Identifier: MIT */ +#include "hmap.h" + +#include +#include +#include +#ifdef HMAP_DEBUG +#include +#endif + +#ifndef HMAP_LOAD_FACTOR +#define HMAP_LOAD_FACTOR 80 +#endif +#ifndef HMAP_GROWTH_RATE +#define HMAP_GROWTH_RATE 2 +#endif + +/** + * Structures + * ========== + */ + +/** + * struct hmap - generic hash map. + * @buckets: table where we store our buckets. + * @cap: current capacity. + * @cnt: how many entries we currently hold. + * @grow_at: load factor at which we grow. > 100 if hmap is not dynamic. + * @shrink_at: load factor at which we shrink. + * @cmp: key compare function. + */ +struct hmap { + struct hmap_entry **buckets; + + size_t cap; + size_t cnt; + + size_t grow_at; + size_t shrink_at; + + hmap_cmp_fn cmp; + hmap_hash_fn hash_key; + + uint8_t dynamic : 1; +}; + +/** + * Internal methods + * ================ + */ + +/** + * find_hmap_bucket() - find the bucket for @key. + * @map: hashmap. + * @key: key with hash. + * + * Return: pointer to bucket in buckets table. + */ +static inline struct hmap_entry **find_hmap_bucket(struct hmap *map, + struct hmap_entry *key) +{ + size_t i = key->hash % map->cap; + + return map->buckets + i; +} + +/** + * find_hmap_entry() - find entry that has @key. + * @map: hashmap. + * @key: key with hash. + * + * Return: pointer where the entry is stored. + */ +static struct hmap_entry **find_hmap_entry(struct hmap *map, + struct hmap_entry *key) +{ + map->hash_key(key); + + struct hmap_entry **ptr = find_hmap_bucket(map, key); + while (*ptr) { + if (map->cmp(*ptr, key)) { + return ptr; + } + ptr = &(*ptr)->next; + } + + return ptr; +} + +/** + * __hmap_add() -- low level add function. + * @map: hashmap. + * @ent: entry to add. + */ +static void __hmap_add(struct hmap *map, struct hmap_entry *ent) +{ + struct hmap_entry **bucket = find_hmap_bucket(map, ent); + if (*bucket) { + struct hmap_entry *coll = *bucket; + struct hmap_entry *next = coll->next; +#ifdef HMAP_DEBUG + fprintf(stderr, "\nCOLLISION!\n"); +#endif + while (next) { +#ifdef HMAP_DEBUG + fprintf(stderr, "\nCOLLISION!\n"); +#endif + coll = next; + next = coll->next; + } + coll->next = ent; + } else { + *bucket = ent; + } +} + +/** + * set_thresholds() - set growth and shrink thresholds. + * @map: hashmap. + */ +static inline void set_thresholds(struct hmap *map) +{ + map->grow_at = map->cap * HMAP_LOAD_FACTOR / 100; + if (map->cap <= HMAP_INIT_CAP) { + map->shrink_at = 0; + } else { + map->shrink_at = map->grow_at / HMAP_GROWTH_RATE - 2; + } +} + +/** + * alloc_buckets() - allocate buckets table. + * @map: hashmap. + */ +static inline void alloc_buckets(struct hmap *map) +{ + map->buckets = calloc(map->cap, sizeof(struct hmap_entry *)); +} + +/** + * maybe_realloc() - grow/shrink buckets table if needed. + * @map: hashmap. + */ +static void maybe_realloc(struct hmap *map) +{ + if (!map->dynamic) { + return; + } + + size_t oldcap = map->cap; + + if (map->cnt >= map->grow_at) { + map->cap = map->cap * HMAP_GROWTH_RATE; + } else if (map->cnt < map->shrink_at) { + map->cap = map->cap / HMAP_GROWTH_RATE; + } else { + return; + } + + struct hmap_entry **oldbucks = map->buckets; + + alloc_buckets(map); + set_thresholds(map); + + for (size_t i = 0; i < oldcap; i++) { + struct hmap_entry *next = oldbucks[i], *cur; + while (next) { + cur = next; + next = cur->next; + cur->next = NULL; + __hmap_add(map, cur); + } + } + + free(oldbucks); +} + +/** + * Public methods + * ============== + */ + +struct hmap *hmap_new_with(hmap_cmp_fn cmp_fn, hmap_hash_fn hash_fn, size_t cap, + bool dynamic) +{ + struct hmap *map = malloc(sizeof(*map)); + + map->cap = cap; + map->cnt = 0; + map->cmp = cmp_fn; + map->hash_key = hash_fn; + map->dynamic = dynamic; + alloc_buckets(map); + if (dynamic) { + set_thresholds(map); + } + + return map; +} + +void hmap_add(struct hmap *map, struct hmap_entry *ent) +{ + ent->next = NULL; + map->hash_key(ent); + + map->cnt++; + maybe_realloc(map); + + __hmap_add(map, ent); +} + +struct hmap_entry *hmap_get(struct hmap *map, struct hmap_entry *key) +{ + return *find_hmap_entry(map, key); +} + +struct hmap_entry *hmap_get_next_dup(struct hmap *map, struct hmap_entry *ent) +{ + struct hmap_entry *next = ent->next; + while (next) { + if (map->cmp(next, ent)) { + return next; + } + } + + return next; +} + +struct hmap_entry *hmap_remove(struct hmap *map, struct hmap_entry *key) +{ + struct hmap_entry **ptr = find_hmap_entry(map, key), *old; + + if (*ptr) { + if (map->cmp(*ptr, key)) { + old = *ptr; + *ptr = old->next; + + map->cnt--; + maybe_realloc(map); + + return old; + } + } + + return NULL; +} + +size_t hmap_entry_cnt(struct hmap *map) +{ + return map->cnt; +} + +size_t hmap_cur_cap(struct hmap *map) +{ + return map->cap; +} + +void hmap_dynamic_set(struct hmap *map, bool on) +{ + map->dynamic = on; +} + +bool hmap_dynamic_get(struct hmap *map) +{ + return map->dynamic; +} + +void hmap_free(struct hmap *map) +{ + free(map->buckets); + free(map); +} + +void hmap_iter_init(struct hmap_iter *iter, struct hmap *map) +{ + iter->map = map; + iter->cursor = 0; + iter->next = NULL; +} + +struct hmap_entry *hmap_iter_next(struct hmap_iter *iter) +{ + struct hmap_entry *cur = iter->next; + + for (;;) { + if (cur) { + iter->next = cur->next; + return cur; + } + + if (iter->cursor >= iter->map->cap) { + return NULL; + } + + cur = iter->map->buckets[iter->cursor++]; + } +} -- cgit v1.2.3