From cb1a40859029f33184355475e51fec95afb79a73 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Yaroslav=20de=20la=20Pe=C3=B1a=20Smirnov?=
<yps@yaroslavps.com>
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 <inttypes.h>
+#include <stdlib.h>
+
+#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 <string.h>
+
+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 <string.h>
+#include <stdlib.h>
+#include <limits.h>
+#ifdef HMAP_DEBUG
+#include <stdio.h>
+#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 <inttypes.h>
+#include <stdbool.h>
+#include <sys/types.h>
+
+#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