1 files changed, 297 insertions, 0 deletions
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++];
+	}
+}