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/Makefile | 9 ++ hmap/README.md | 8 ++ hmap/hash.h | 61 ++++++++++++ hmap/hmap-test.c | 291 +++++++++++++++++++++++++++++++++++++++++++++++++++++ hmap/hmap.c | 297 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ hmap/hmap.h | 238 ++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 904 insertions(+) create mode 100644 hmap/Makefile create mode 100644 hmap/README.md create mode 100644 hmap/hash.h create mode 100644 hmap/hmap-test.c create mode 100644 hmap/hmap.c create mode 100644 hmap/hmap.h (limited to 'hmap') diff --git a/hmap/Makefile b/hmap/Makefile new file mode 100644 index 0000000..dc52ab3 --- /dev/null +++ b/hmap/Makefile @@ -0,0 +1,9 @@ +CC?=gcc +CFLAGS+=-Wall -Werror -std=gnu11 -Og -g + +ifdef DEBUG +CFLAGS+=-DHMAP_DEBUG +endif + +all: + $(CC) $(CFLAGS) -o hmap-test hmap-test.c hmap.c diff --git a/hmap/README.md b/hmap/README.md new file mode 100644 index 0000000..a39d14a --- /dev/null +++ b/hmap/README.md @@ -0,0 +1,8 @@ +# Hmap + +Simple generic hash map with no macro vodoo magic. Inspired by other data +structures in the Linux Kernel. + +## Example usage + +If you want to see an example on how to use hmap, take a look at `hmap-test.c`. diff --git a/hmap/hash.h b/hmap/hash.h new file mode 100644 index 0000000..9d4d8dd --- /dev/null +++ b/hmap/hash.h @@ -0,0 +1,61 @@ +/* SPDX-License-Identifier: MIT */ +/** + * hash.h - implementations of the FNV1a hashing algorithm. + * + * Copyright (c) 2022-2023 - Yaroslav de la Peña Smirnov + */ +#ifndef HMAP_HASH_H +#define HMAP_HASH_H + +#include +#include + +#if SIZE_MAX == 0xFFFFFFFF +/* size_t is 32bit */ +static const size_t fnv_prime = 16777619u; +static const size_t fnv_offsetb = 2166136261u; +#elif SIZE_MAX == 0xFFFFFFFFFFFFFFFF +/* size_t is 64bit */ +static const size_t fnv_prime = 1099511628211u; +static const size_t fnv_offsetb = 14695981039346656037u; +#endif + +/** + * fnv1a_bytes_hash() - generic fnv1a hash function. + * @data: pointer to data to hash. + * @len: size of @data in bytes. + * + * Return: hash value. + */ +static inline size_t fnv1a_bytes_hash(const void *data, size_t len) +{ + const char *bytes = (const char *)data; + size_t hash = fnv_offsetb; + + for (size_t i = 0; i < len; i++) { + hash ^= bytes[i]; + hash *= fnv_prime; + } + + return hash; +} + +/** + * fnv1a_str_hash() - fnv1a hash function for nul-terminated strings. + * @str: nul-terminated string of characters to hash. + * + * Return: hash value. + */ +static inline size_t fnv1a_str_hash(const char *str) +{ + size_t hash = fnv_offsetb; + + for (size_t i = 0; str[i]; i++) { + hash ^= str[i]; + hash *= fnv_prime; + } + + return hash; +} + +#endif /* HMAP_HASH_H */ diff --git a/hmap/hmap-test.c b/hmap/hmap-test.c new file mode 100644 index 0000000..bf3ebe2 --- /dev/null +++ b/hmap/hmap-test.c @@ -0,0 +1,291 @@ +#include "hash.h" +#include "hmap.h" +#include "../utest/utest.h" + +#include + +struct hmap_test_s { + const char *key; + uint64_t data; + struct hmap_entry entry; +}; + +#define entry_to_test_s(ent) hmap_item(ent, struct hmap_test_s, entry) + +bool hmap_test_cmp(const struct hmap_entry *ent, const struct hmap_entry *key) +{ + struct hmap_test_s *a = entry_to_test_s(ent); + struct hmap_test_s *b = entry_to_test_s(key); + + return !strcmp(a->key, b->key); +} + +void hmap_test_hash(struct hmap_entry *ent) +{ + struct hmap_test_s *e = entry_to_test_s(ent); + ent->hash = fnv1a_str_hash(e->key); +} + +struct hmap *map; + +/* clang-format off */ +struct hmap_test_s inputs[] = { + { .key = "alpha", .data = 10, }, + { .key = "bravo", .data = 24, }, + { .key = "charlie", .data = 30, }, + { .key = "delta", .data = 42, }, + { .key = "echo", .data = 50, }, + { .key = "foxtrot", .data = 69, }, + { .key = "golf", .data = 70, }, + { .key = "hotel", .data = 80, }, + { .key = "india", .data = 99, }, +}; + +struct hmap_test_s inputs2[] = { + { .key = "aa" }, + { .key = "ab" }, + { .key = "ac" }, + { .key = "ad" }, + { .key = "ae" }, + { .key = "af" }, + { .key = "ag" }, + { .key = "ah" }, + { .key = "ai" }, + { .key = "aj" }, + { .key = "ak" }, + { .key = "al" }, + { .key = "am" }, + { .key = "an" }, + { .key = "ao" }, + { .key = "ap" }, + { .key = "aq" }, + { .key = "ar" }, + { .key = "as" }, + { .key = "at" }, + { .key = "au" }, + { .key = "av" }, + { .key = "aw" }, + { .key = "ax" }, + { .key = "ay" }, + { .key = "az" }, + { .key = "ba" }, + { .key = "bb" }, + { .key = "bc" }, + { .key = "bd" }, + { .key = "be" }, + { .key = "bf" }, + { .key = "bg" }, + { .key = "bh" }, + { .key = "bi" }, + { .key = "bj" }, + { .key = "bk" }, + { .key = "bl" }, + { .key = "bm" }, + { .key = "bn" }, + { .key = "bo" }, + { .key = "bp" }, + { .key = "bq" }, + { .key = "br" }, + { .key = "bs" }, + { .key = "bt" }, + { .key = "bu" }, + { .key = "bv" }, + { .key = "bw" }, + { .key = "bx" }, + { .key = "by" }, +}; +/* clang-format on */ + +struct hmap_test_s duplicate = { .key = "foxtrot", .data = 420 }; + +#ifndef HMAP_DEBUG + +TEST_BEGIN(test_hmap_add) +{ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + size_t cnt = hmap_entry_cnt(map); + expect(cnt == ARRAY_SIZE(inputs), + "number of entries in hashmap (%lu) != number of entries added " + "(%lu)", + cnt, ARRAY_SIZE(inputs)); + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_get) +{ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + struct hmap_test_s key = { .key = inputs[i].key }; + struct hmap_test_s *expect = inputs + i; + struct hmap_entry *ent = hmap_get(map, &key.entry); + + assertneq(ent, NULL); + + struct hmap_test_s *got = entry_to_test_s(ent); + asserteq(expect, got); + } + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_get_next_dup) +{ + hmap_add(map, &duplicate.entry); + struct hmap_test_s key = { .key = duplicate.key }; + struct hmap_entry *ent = hmap_get(map, &key.entry); + + assertneq(ent, NULL); + + struct hmap_test_s *got = entry_to_test_s(ent); + + struct hmap_entry *next = hmap_get_next_dup(map, ent); + + assertneq(next, NULL); + + struct hmap_test_s *got_dup = entry_to_test_s(next); + if (got->data != duplicate.data) { + asserteq(got_dup->data, duplicate.data); + } else { + assertneq(got_dup->data, duplicate.data); + } + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_remove) +{ + struct hmap_entry *removed; + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + struct hmap_test_s key = { .key = inputs[i].key }; + removed = hmap_remove(map, &key.entry); + + assertneq(removed, NULL); + } + + expect(hmap_entry_cnt(map) == 1, "expected only duplicate entry left"); + removed = hmap_remove(map, &duplicate.entry); + asserteq(removed, &duplicate.entry); + + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_realloc) +{ + /* This test case assumes default hmap settings */ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + expect(hmap_cur_cap(map) <= 64, "hashmap shouldn't grow so fast"); + + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_add(map, &inputs2[i].entry); + } + asserteq(hmap_entry_cnt(map), ARRAY_SIZE(inputs) + ARRAY_SIZE(inputs2)); + expect(hmap_cur_cap(map) > 64, "expected hashmap to grow"); + + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_remove(map, &inputs2[i].entry); + } + expect(hmap_cur_cap(map) <= 64, "expected hashmap to shrink"); + + TEST_OUT + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_remove(map, &inputs[i].entry); + } +} +TEST_END + +TEST_BEGIN(test_hmap_iter) +{ + struct hmap_iter iter; + struct hmap_entry *ent, *prev = NULL; + size_t cnt = 0; + + hmap_iter_init(&iter, map); + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + + hmap_iter_foreach(&iter, ent) { + cnt++; + expect(ent != prev, "hmap_iter shouldn't return same entry on next"); + } + asserteq(cnt, ARRAY_SIZE(inputs)); + + TEST_OUT +} +TEST_END + +TEST_BEGIN(test_hmap_iter_remove) +{ + struct hmap_iter iter; + struct hmap_entry *ent; + + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_add(map, &inputs2[i].entry); + } + + hmap_dynamic_set(map, false); + expect(!hmap_dynamic_get(map), "expected dynamic setting to be off"); + + hmap_iter_init(&iter, map); + hmap_iter_foreach(&iter, ent) { + expect(hmap_remove(map, ent), "expected entry to be removed"); + } + asserteq(hmap_entry_cnt(map), 0); + + hmap_dynamic_set(map, true); + expect(hmap_dynamic_get(map), "expected dynamic setting to be on"); + + TEST_OUT +} +TEST_END + +#else + +TEST_BEGIN(test_hmap_collisions) +{ + for (size_t i = 0; i < ARRAY_SIZE(inputs); i++) { + hmap_add(map, &inputs[i].entry); + } + for (size_t i = 0; i < ARRAY_SIZE(inputs2); i++) { + hmap_add(map, &inputs2[i].entry); + } + asserteq(hmap_entry_cnt(map), ARRAY_SIZE(inputs) + ARRAY_SIZE(inputs2)); + TEST_OUT +} +TEST_END + +#endif /* HMAP_DEBUG */ + +void hmap_test_init(void) +{ +#ifdef HMAP_DEBUG +#ifndef HMAP_DEBUG_CAP +#define HMAP_DEBUG_CAP 128 +#endif /* HMAP_DEBUG_CAP */ + map = hmap_new_with(hmap_test_cmp, hmap_test_hash, HMAP_DEBUG_CAP, false); +#else + map = hmap_new(hmap_test_cmp, hmap_test_hash); +#endif /* HMAP_DEBUG */ +} + +void hmap_test_destroy(void) +{ + hmap_free(map); +} + +#ifdef HMAP_DEBUG + +RUN_TEST_SUITE(hmap_test_init, hmap_test_destroy, test_hmap_collisions); + +#else + +RUN_TEST_SUITE(hmap_test_init, hmap_test_destroy, test_hmap_add, test_hmap_get, + test_hmap_get_next_dup, test_hmap_remove, test_hmap_realloc, + test_hmap_iter, test_hmap_iter_remove) + +#endif /* HMAP_DEBUG */ 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++]; + } +} diff --git a/hmap/hmap.h b/hmap/hmap.h new file mode 100644 index 0000000..bbd95f3 --- /dev/null +++ b/hmap/hmap.h @@ -0,0 +1,238 @@ +/* SPDX-License-Identifier: LGPL-2.1 */ +/** + * hmap.h - a simple generic hashmap. v2.0.0 + * + * Copyright (c) 2022-2023 - Yaroslav de la Peña Smirnov + * + * Documentation + * ============= + * + * In order to use this hashmap, you need to incapsulate struct hmap_entry + * inside your own structure. For example:: + * + * struct my_struct { + * char *key; + * uint64_t data; + * struct hmap_entry entry; + * }; + * + * Then you can insert any instance of such struct into the hashmap by calling + * the corresponding method and passing it the pointer to @entry. + * + * For search and removal operations you just need to fill your structure with + * your key. The hmap_cmp_fn and hmap_hash_fn functions you provided will be + * called by hmap in order to perform the needed operations. + * + * When you get a hmap_entry pointer from hmap's API, you can get your + * containing structure with the help of the hmap_item macro, for example:: + * + * struct hmap_entry *e = hmap_get(map, key); + * struct my_struct *my = hmap_item(e, struct my_struct, entry); + * + */ +#ifndef HMAP_H +#define HMAP_H +#include "../utils.h" + +#include +#include +#include + +#ifndef HMAP_INIT_CAP +#define HMAP_INIT_CAP 64 +#endif + +/** + * Structures + * ========== + */ + +/** + * struct hmap - opaque structure for generic hashmap. + */ +struct hmap; + +/** + * struct hmap_entry - the base class for a hashmap entry. + * @next: linked list in case of collisions. + * @hash: the hash value of the entry key. + * + * This structure should only be manipulated using the methods below. The @hash + * member should be filled by the hmap_hash_fn function provided to hmap_new(). + */ +struct hmap_entry { + struct hmap_entry *next; + size_t hash; +}; + +/** + * struct hmap_iter - iterator over hmap entries. + * @map: hashmap. + * @next: next item to be returned. + * @cursor: current position in buckets table. + * + * If you want to remove entries while iterating, be sure to change the dynamic + * resizing setting to on = false with hmap_dynamic_get(). + */ +struct hmap_iter { + struct hmap *map; + struct hmap_entry *next; + size_t cursor; +}; + +/** + * Typedefs + * ======== + */ + +typedef bool (*hmap_cmp_fn)(const struct hmap_entry *ent, + const struct hmap_entry *key); +typedef void (*hmap_hash_fn)(struct hmap_entry *ent); + +/** + * Methods + * ======= + */ + +/** + * hmap_new_with() - allocate new hashmap with given parameters. + * @cmp_fn: key comparison function. + * @hash_fn: key hashing function. + * @cap: initial hashmap capacity. + * @dynamic: whether the hashmap should dynamically grow/shrink based on load + * factor. + * + * Return: pointer to hmap object. + */ +struct hmap *hmap_new_with(hmap_cmp_fn cmp_fn, hmap_hash_fn hash_fn, size_t cap, + bool dynamic); + +/** + * hmap_new - allocate new hashmap with default parameters. + * @cmp_fn: key comparison function. + * @hash_fn: key hashing function. + * + * Return: pointer to hmap object. + */ +#define hmap_new(cmp_fn, hash_fn) \ + hmap_new_with(cmp_fn, hash_fn, HMAP_INIT_CAP, true) + +/** + * hmap_free() - free all resources used by @map. + * @map: hashmap. + * + * This function does not release or free any resources associated with any + * entries stored in the hashmap. It is the responsibility of the caller to free + * any such resources. + */ +void hmap_free(struct hmap *map); + +/** + * hmap_item - get the pointer to the containing structure for this entry. + * @entry: struct hmap_entry pointer. + * @type: containing struct. + * @member: the member in the struct that holds hmap_entry. + */ +#define hmap_item(entry, type, member) container_of(entry, type, member) + +/** + * hmap_add() - add entry to @map. + * @map: hashmap. + * @ent: entry to add. + * + * If there's already an entry with the same key, it wil still add it and hold + * both. + */ +void hmap_add(struct hmap *map, struct hmap_entry *ent); + +/** + * hmap_get() - get entry with @key from @map. + * @map: hashmap. + * @key: hmap_entry object that holds the key. + * + * In order to pass the key, you just need to fill what is needed by your + * hashing and comparison functions; you could even use a separate structure + * that just holds the key, if you use the appropriate logic in your functions. + * + * If there are entries with duplicate keys, it will get the first it finds. If + * your want to get the next duplicate-key entry use hmap_get_next_dup(). + * + * Return: pointer to entry; NULL if no entry with such key. + */ +struct hmap_entry *hmap_get(struct hmap *map, struct hmap_entry *key); + +/** + * hmap_get_next_dup() - get the next entry with the same key as @ent. + * @map: hashmap. + * @ent: entry with duplicate key. + * + * Return: pointer to entry; NULL if no more entries with same key. + */ +struct hmap_entry *hmap_get_next_dup(struct hmap *map, struct hmap_entry *ent); + +/** + * hmap_remove() - remove entry with @key from @map. + * @map: hashmap. + * @key: hmap_entry object that holds the key. + * + * If there are entries with duplicates keys, it will remove the first it finds. + * + * Return: pointer to removed entry; NULL if no entry with such key. + */ +struct hmap_entry *hmap_remove(struct hmap *map, struct hmap_entry *key); + +/** + * hmap_entry_cnt() - get the current number of entries in @map. + * @map: hashmap. + * + * Return: number of entries held by @map. + */ +size_t hmap_entry_cnt(struct hmap *map); + +/** + * hmap_dynamic_set() - enable/disable hashmap resizing. + * @map: hashmap. + * @on: whether to turn on/off. + */ +void hmap_dynamic_set(struct hmap *map, bool on); + +/** + * hmap_dynamic_get() - get current hashmap resizing setting. + * @map: hashmap. + * + * Return: current dynamic resizing setting. + */ +bool hmap_dynamic_get(struct hmap *map); + +/** + * hmap_cur_cap() - get the current capacity of @map. + * @map: hashmap. + * + * Return: current @map capacity. + */ +size_t hmap_cur_cap(struct hmap *map); + +/** + * hmap_iter_init() - initialize and reset hmap iterator. + * @iter: pointer to hmap_iter object. + * @map: hashmap to iterate over. + */ +void hmap_iter_init(struct hmap_iter *iter, struct hmap *map); + +/** + * hmap_iter_next() - get the next entry. + * @iter: iterator. + * + * Return: pointer to entry; NULL if no more entries are left. + */ +struct hmap_entry *hmap_iter_next(struct hmap_iter *iter); + +/** + * hmap_iter_foreach - loop to iterate over every entry. + * @iter: pointer to iterator. + * @entry: hmap_entry pointer to hold the next entry. + */ +#define hmap_iter_foreach(iter, entry) \ + for (entry = hmap_iter_next((iter)); entry; entry = hmap_iter_next((iter))) + +#endif /* HMAP_H */ -- cgit v1.2.3