init

Just some C wares; hmap, list, optional, unit tests.

6 files changed, 904 insertions, 0 deletions

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 */