1 files changed, 320 insertions, 0 deletions

diff --git a/lib/libhmap/src/hmap.c b/lib/libhmap/src/hmap.c
new file mode 100644
index 0000000..d527516
--- /dev/null
+++ b/lib/libhmap/src/hmap.c
@@ -0,0 +1,320 @@
+#include "hmap.h"
+
+#include <errno.h>
+#include <stdbool.h>
+#include <string.h>
+
+static inline size_t
+hmap_key_bucket(const struct hmap *map, struct hmap_key key)
+{
+	return map->hash(key) % map->bucketcnt;
+}
+
+int
+hmap_init(struct hmap *map, size_t size, hmap_hash_func hasher,
+	hmap_keycmp_func keycmp, const struct allocator *allocator)
+{
+	int rc;
+
+	LIBHMAP_ABORT_ON_ARGS(!size || !hasher || !keycmp || !allocator);
+
+	map->allocator = allocator;
+	map->keycmp = keycmp;
+	map->bucketcnt = size;
+	map->hash = hasher;
+	map->buckets = map->allocator->alloc(map->allocator,
+		sizeof(void *) * size, &rc);
+	if (!map->buckets) return -rc;
+	memset(map->buckets, 0, size * sizeof(void *));
+
+	return 0;
+}
+
+int
+hmap_deinit(struct hmap *map)
+{
+	LIBHMAP_ABORT_ON_ARGS(!map);
+
+	hmap_clear(map);
+
+	return map->allocator->free(map->allocator, map->buckets);
+}
+
+struct hmap *
+hmap_alloc(size_t size, hmap_hash_func hasher,
+	hmap_keycmp_func keycmp, const struct allocator *allocator, int *_rc)
+{
+	struct hmap *map;
+	int *rc, stub;
+
+	LIBHMAP_ABORT_ON_ARGS(!allocator);
+
+	rc = _rc ? _rc : &stub;
+
+	map = allocator->alloc(allocator, sizeof(struct hmap), rc);
+	if (!map && _rc) *rc = -*rc;
+	if (!map) return NULL;
+
+	*rc = hmap_init(map, size, hasher, keycmp, allocator);
+	if (*rc) {
+		allocator->free(allocator, map);
+		return NULL;
+	}
+
+	return map;
+}
+
+int
+hmap_free(struct hmap *map)
+{
+	const struct allocator *allocator;
+	int rc;
+
+	LIBHMAP_ABORT_ON_ARGS(!map);
+
+	allocator = map->allocator;
+	rc = hmap_deinit(map);
+	if (rc) return rc;
+
+	rc = allocator->free(allocator, map);
+	if (rc) return -rc;
+
+	return 0;
+}
+
+int
+hmap_copy(const struct hmap *dst, const struct hmap *src)
+{
+	struct hmap_iter iter;
+	int rc;
+
+	LIBHMAP_ABORT_ON_ARGS(!dst || !src);
+
+	for (HMAP_ITER(src, iter)) {
+		rc = hmap_set(dst, iter.link->key, iter.link->value);
+		if (rc) return rc;
+	}
+
+	return 0;
+}
+
+void
+hmap_swap(struct hmap *m1, struct hmap *m2)
+{
+	struct hmap tmp;
+
+	LIBHMAP_ABORT_ON_ARGS(!m1 || !m2);
+
+	memcpy(&tmp, m1, sizeof(struct hmap));
+	memcpy(m1, m2, sizeof(struct hmap));
+	memcpy(m2, &tmp, sizeof(struct hmap));
+}
+
+void
+hmap_clear(const struct hmap *map)
+{
+	struct hmap_iter iter;
+	struct hmap_link *prev;
+	size_t i;
+
+	LIBHMAP_ABORT_ON_ARGS(!map);
+
+	prev = NULL;
+	for (HMAP_ITER(map, iter)) {
+		map->allocator->free(map->allocator, prev);
+		prev = iter.link;
+	}
+	map->allocator->free(map->allocator, prev);
+
+	for (i = 0; i < map->bucketcnt; i++)
+		map->buckets[i] = NULL;
+}
+
+struct hmap_link **
+hmap_link_get(const struct hmap *map, struct hmap_key key)
+{
+	struct hmap_link **iter, *link;
+
+	LIBHMAP_ABORT_ON_ARGS(!map);
+
+	iter = &map->buckets[hmap_key_bucket(map, key)];
+	while (*iter != NULL) {
+		link = *iter;
+		if (map->keycmp(link->key, key))
+			return iter;
+		iter = &(*iter)->next;
+	}
+
+	return NULL;
+}
+
+struct hmap_link **
+hmap_link_pos(const struct hmap *map, struct hmap_key key)
+{
+	struct hmap_link **iter, *link;
+
+	LIBHMAP_ABORT_ON_ARGS(!map);
+
+	iter = &map->buckets[hmap_key_bucket(map, key)];
+	while (*iter != NULL) {
+		link = *iter;
+		if (map->keycmp(link->key, key))
+			return iter;
+		iter = &(*iter)->next;
+	}
+
+	return iter;
+}
+
+struct hmap_link *
+hmap_link_pop(const struct hmap *map, struct hmap_link **link)
+{
+	struct hmap_link *tmp;
+
+	LIBHMAP_ABORT_ON_ARGS(!map || !link);
+
+	tmp = *link;
+	*link = (*link)->next;
+
+	return tmp;
+}
+
+struct hmap_link *
+hmap_link_alloc(const struct hmap *map,
+	struct hmap_key key, struct hmap_val value, int *rc)
+{
+	struct hmap_link *link;
+
+	LIBHMAP_ABORT_ON_ARGS(!map);
+
+	link = map->allocator->alloc(map->allocator,
+		sizeof(struct hmap_link), rc);
+	if (!link && rc) *rc = -*rc;
+	if (!link) return NULL;
+
+	link->key = key;
+	link->value = value;
+	link->next = NULL;
+
+	return link;
+}
+
+struct hmap_link *
+hmap_get(const struct hmap *map, struct hmap_key key)
+{
+	struct hmap_link **iter;
+
+	LIBHMAP_ABORT_ON_ARGS(!map);
+
+	iter = hmap_link_get(map, key);
+
+	return iter ? *iter : NULL;
+}
+
+int
+hmap_set(const struct hmap *map, struct hmap_key key, struct hmap_val value)
+{
+	struct hmap_link **iter;
+
+	LIBHMAP_ABORT_ON_ARGS(!map);
+
+	iter = hmap_link_pos(map, key);
+	if (!*iter) return HMAP_KEY_MISSING;
+
+	(*iter)->value = value;
+
+	return 0;
+}
+
+int
+hmap_rm(const struct hmap *map, struct hmap_key key)
+{
+	struct hmap_link *link, **linkp;
+	int rc;
+
+	LIBHMAP_ABORT_ON_ARGS(!map);
+
+	linkp = hmap_link_get(map, key);
+	if (!linkp) return HMAP_KEY_MISSING;
+	link = hmap_link_pop(map, linkp);
+
+	rc = map->allocator->free(map->allocator, link);
+	if (rc) return -rc;
+
+	return 0;
+}
+
+int
+hmap_add(const struct hmap *map, struct hmap_key key, struct hmap_val value)
+{
+	struct hmap_link **iter;
+	int rc;
+
+	LIBHMAP_ABORT_ON_ARGS(!map);
+
+	iter = hmap_link_pos(map, key);
+	if (*iter) return HMAP_KEY_EXISTS;
+
+	*iter = hmap_link_alloc(map, key, value, &rc);
+	if (!*iter) return rc;
+
+	return 0;
+}
+
+void
+hmap_iter_init(struct hmap_iter *iter)
+{
+	LIBHMAP_ABORT_ON_ARGS(!iter);
+
+	iter->bucket = 0;
+	iter->link = NULL;
+}
+
+bool
+hmap_iter_next(const struct hmap *map, struct hmap_iter *iter)
+{
+	size_t i;
+
+	LIBHMAP_ABORT_ON_ARGS(!map || !iter);
+
+	if (iter->link && iter->link->next) {
+		iter->link = iter->link->next;
+		return true;
+	}
+
+	i = iter->bucket + (iter->link ? 1 : 0);
+	for (; i < map->bucketcnt; i++) {
+		if (map->buckets[i]) {
+			iter->bucket = i;
+			iter->link = map->buckets[i];
+			return true;
+		}
+	}
+
+	iter->link = NULL;
+
+	return false;
+}
+
+uint32_t
+hmap_str_hash(struct hmap_key key)
+{
+	const char *c;
+	uint32_t hash;
+
+	LIBHMAP_ABORT_ON_ARGS(!key.p);
+
+	hash = 5381;
+	for (c = key.p; *c; c++)
+		hash = 33 * hash + (uint8_t) *c;
+
+	return hash;
+}
+
+bool
+hmap_str_keycmp(struct hmap_key k1, struct hmap_key k2)
+{
+	LIBHMAP_ABORT_ON_ARGS(!k1.p || !k2.p);
+
+	return !strcmp(k1.p, k2.p);
+}