23 files changed, 1060 insertions, 0 deletions

diff --git a/lib/libhmap b/lib/libhmap
deleted file mode 160000
-Subproject 274addaba036c4dafda702f4dd449ab3157565d
diff --git a/lib/libhmap/.gitignore b/lib/libhmap/.gitignore
new file mode 100644
index 0000000..a64dd56
--- /dev/null
+++ b/lib/libhmap/.gitignore
@@ -0,0 +1,7 @@
+compile_commands.json
+build
+build.rmk
+.cache
+vgcore*
+test
+/.subgit
diff --git a/lib/libhmap/.subgitrc b/lib/libhmap/.subgitrc
new file mode 100644
index 0000000..5f1b14f
--- /dev/null
+++ b/lib/libhmap/.subgitrc
@@ -0,0 +1,9 @@
+#!/bin/bash
+
+declare -A subgit subgitinfo
+
+subgit[lib/liballoc]=1
+subgitinfo[lib/liballoc/remote]='git@sinitax.com:sinitax/liballoc-c'
+subgitinfo[lib/liballoc/branch]='master'
+subgitinfo[lib/liballoc/commit]='24d37e4298575df36399f32a6fa5ef10b005c964'
+
diff --git a/lib/libhmap/LICENSE b/lib/libhmap/LICENSE
new file mode 100644
index 0000000..361f116
--- /dev/null
+++ b/lib/libhmap/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2023 Louis Burda
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/lib/libhmap/Makefile b/lib/libhmap/Makefile
new file mode 100644
index 0000000..3adad36
--- /dev/null
+++ b/lib/libhmap/Makefile
@@ -0,0 +1,59 @@
+PREFIX ?= /usr/local
+INCLDIR ?= /include
+LIBDIR ?= /lib
+
+CFLAGS += -I include -I lib/liballoc/include
+CFLAGS += -Wunused-function -Wunused-variable -Wno-prototype 
+CFLAGS += -Wconversion -Wsign-compare -Werror
+
+ifeq "$(DEBUG)" "1"
+CFLAGS += -Og -g
+else
+CFLAGS += -O2
+endif
+
+ifeq "$(ASSERT_ARGS)" "1"
+CFLAGS += -DLIBHMAP_ASSERT_ARGS=1
+endif
+
+ifeq "$(ASSERT_ALLOC)" "1"
+CFLAGS += -DLIBHMAP_ASSERT_ALLLOC=1
+endif
+
+all: build/libhmap.so build/libhmap.a build/test
+
+clean:
+	rm -rf build
+
+cleanall: clean
+	make -C lib/liballoc cleanall
+
+build:
+	mkdir build
+
+lib/liballoc/build/liballoc.a:
+	make -C lib/liballoc build/liballoc.a
+
+build/libhmap.a: src/hmap.c include/hmap.h libhmap.api | build
+	$(CC) -o build/tmp.o src/hmap.c $(CFLAGS) -r
+	objcopy --keep-global-symbols=libhmap.api build/tmp.o build/fixed.o
+	$(AR) rcs $@ build/fixed.o
+
+build/libhmap.so: src/hmap.c include/hmap.h libhmap.lds | build
+	$(CC) -o $@ src/hmap.c -fPIC $(CFLAGS) -shared \
+		-Wl,-version-script libhmap.lds
+
+build/test: src/test.c build/libhmap.a lib/liballoc/build/liballoc.a  | build
+	$(CC) -o $@ $^ -I include -I lib/liballoc/include -g
+
+install:
+	install -m 644 include/hmap.h -t "$(DESTDIR)$(PREFIX)$(INCLDIR)"
+	install -m 755 build/libhmap.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+	install -m 755 build/libhmap.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+
+uninstall:
+	rm -f "$(DESTDIR)$(PREFIX)$(INCLDIR)/hmap.h"
+	rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libhmap.a"
+	rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libhmap.so"
+
+.PHONY: all clean cleanall install uninstall
diff --git a/lib/libhmap/build.rmk.tmpl b/lib/libhmap/build.rmk.tmpl
new file mode 100644
index 0000000..b123dcf
--- /dev/null
+++ b/lib/libhmap/build.rmk.tmpl
@@ -0,0 +1,69 @@
+#default PREFIX /usr/local
+#default INCLDIR /include
+#default LIBDIR /lib
+#default CC gcc
+
+#ifdef LIBHMAP_DEBUG
+#define DEBUG 1
+#endif
+
+#ifdef DEBUG
+#define OPT_CFLAGS -Og -g
+#else
+#define OPT_CFLAGS -O2
+#endif
+
+cflags = -Wunused-function -Wunused-variable -Wconversion -Wformat
+		-I include -I lib/liballoc/include #{OPT_CFLAGS}
+		 #{EXTRA_CFLAGS} #{LIBHMAP_EXTRA_CFLAGS}
+
+rule mkdir
+	mkdir $out
+
+rule liba
+	#{CC} -o $out.tmp.o $in $cflags -r
+	objcopy --keep-global-symbols=libhmap.api $out.tmp.o $out.fixed.o
+	ar rcs $out $out.fixed.o
+	rm $out.tmp.o $out.fixed.o
+
+rule libso
+	#{CC} -o $out $in $cflags -shared -Wl,-version-script libhmap.lds
+
+rule cc
+	#{CC} -o $out $in $cflags
+
+target build
+	mkdir
+
+target lib/liballoc/build/liballoc.a
+	rmk lib/liballoc
+
+target build/libhmap.a
+	liba src/hmap.c | include/hmap.h build
+
+target build/libhmap.so
+	libso src/hmap.c | include/hmap.h build
+
+target build/test
+	cc src/test.c build/libhmap.a lib/liballoc/build/liballoc.a | build
+
+command clean
+	rm -rf build
+
+command cleanall
+	rmk clean
+	rmk -C lib/liballoc cleanall
+
+command install
+	install -m755 build/libhmap.a -t "#{DESTDIR}#{PREFIX}#{LIBDIR}"
+	install -m755 build/libhmap.so -t "#{DESTDIR}#{PREFIX}#{LIBDIR}"
+	install -m644 include/hmap.h -t "#{DESTDIR}#{PREFIX}#{INCLDIR}"
+
+command uninstall
+	rm -f "#{DESTDIR}#{PREFIX}#{LIBDIR}/libhmap.a"
+	rm -f "#{DESTDIR}#{PREFIX}#{LIBDIR}/libhmap.so"
+	rm -f "#{DESTDIR}#{PREFIX}#{INCLDIR}/hmap.h"
+
+command all
+	rmk build/libhmap.a build/libhmap.so build/test
+
diff --git a/lib/libhmap/configure b/lib/libhmap/configure
new file mode 100755
index 0000000..b4dd05d
--- /dev/null
+++ b/lib/libhmap/configure
@@ -0,0 +1,8 @@
+#!/bin/sh
+
+tmpl "$@" build.rmk.tmpl > build.rmk
+for lib in ./lib/*; do
+	pushd $lib
+	./configure "$@"
+	popd
+done
diff --git a/lib/libhmap/include/hmap.h b/lib/libhmap/include/hmap.h
new file mode 100644
index 0000000..3700c6e
--- /dev/null
+++ b/lib/libhmap/include/hmap.h
@@ -0,0 +1,123 @@
+#pragma once
+
+#include "allocator.h"
+
+#include <stdint.h>
+#include <stdbool.h>
+#include <sys/types.h>
+
+#define HMAP_ITER(map, iter) \
+	hmap_iter_init(&(iter)); hmap_iter_next(map, &(iter));
+
+#define HMAP_STRERR_INIT \
+	[HMAP_OK] = "Success", \
+	[HMAP_KEY_EXISTS] = "Key exists", \
+	[HMAP_KEY_MISSING] = "Key missing"
+
+#ifdef LIBHMAP_ASSERT_ARGS
+#define LIBHMAP_ABORT_ON_ARGS(cond) do { if (cond) abort(); } while (0)
+#else
+#define LIBHMAP_ABORT_ON_ARGS(cond)
+#endif
+
+#ifdef LIBHMAP_ASSERT_ALLOC
+#define LIBHMAP_ABORT_ON_ALLOC(cond) do { if (cond) abort(); } while (0)
+#else
+#define LIBHMAP_ABORT_ON_ALLOC(cond)
+#endif
+
+struct hmap_key;
+
+typedef uint32_t (*hmap_hash_func)(struct hmap_key key);
+typedef bool (*hmap_keycmp_func)(struct hmap_key k1, struct hmap_key k2);
+
+enum {
+	HMAP_OK = 0,
+	HMAP_KEY_EXISTS,
+	HMAP_KEY_MISSING,
+};
+
+struct hmap_key {
+	union {
+		bool b;
+		char c;
+		float f;
+		double d;
+		int i;
+		unsigned int u;
+		size_t s;
+		ssize_t ss;
+		const void *p;
+		void *_p;
+	};
+};
+
+struct hmap_val {
+	union {
+		bool b;
+		char c;
+		float f;
+		double d;
+		int i;
+		unsigned int u;
+		size_t s;
+		ssize_t ss;
+		const void *p;
+		void *_p;
+	};
+};
+
+struct hmap_link {
+	struct hmap_key key;
+	struct hmap_val value;
+	struct hmap_link *next;
+};
+
+struct hmap_iter {
+	struct hmap_link *link;
+	size_t bucket;
+};
+
+struct hmap {
+	hmap_hash_func hash;
+	hmap_keycmp_func keycmp;
+	struct hmap_link **buckets;
+	size_t bucketcnt;
+	const struct allocator *allocator;
+};
+
+int hmap_init(struct hmap *map, size_t buckets, hmap_hash_func hasher,
+	hmap_keycmp_func keycmp, const struct allocator *allocator);
+int hmap_deinit(struct hmap *map);
+
+struct hmap *hmap_alloc(size_t buckets, hmap_hash_func hasher,
+	hmap_keycmp_func keycmp, const struct allocator *allocator, int *rc);
+int hmap_free(struct hmap *map);
+
+int hmap_copy(const struct hmap *dst, const struct hmap *src);
+void hmap_swap(struct hmap *m1, struct hmap *m2);
+void hmap_clear(const struct hmap *map);
+
+struct hmap_link **hmap_link_get(const struct hmap *map, struct hmap_key key);
+struct hmap_link **hmap_link_pos(const struct hmap *map, struct hmap_key key);
+struct hmap_link *hmap_link_pop(const struct hmap *map, struct hmap_link **linkp);
+struct hmap_link *hmap_link_alloc(const struct hmap *map,
+	struct hmap_key key, struct hmap_val value, int *rc);
+
+struct hmap_link *hmap_get(const struct hmap *map, struct hmap_key key);
+int hmap_set(const struct hmap *map, struct hmap_key key, struct hmap_val value);
+int hmap_rm(const struct hmap *map, struct hmap_key key);
+int hmap_add(const struct hmap *map, struct hmap_key key, struct hmap_val value);
+
+void hmap_iter_init(struct hmap_iter *iter);
+bool hmap_iter_next(const struct hmap *map, struct hmap_iter *iter);
+static inline bool hmap_iter_done(const struct hmap_iter *iter);
+
+uint32_t hmap_str_hash(struct hmap_key key);
+bool hmap_str_keycmp(struct hmap_key k1, struct hmap_key k2);
+
+static inline bool
+hmap_iter_done(const struct hmap_iter *iter)
+{
+	return !iter->link;
+}
diff --git a/lib/libhmap/lib/liballoc/.gitignore b/lib/libhmap/lib/liballoc/.gitignore
new file mode 100644
index 0000000..ac80ccf
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/.gitignore
@@ -0,0 +1,7 @@
+compile_commands.json
+build
+build.jst
+.cache
+vgcore*
+.gdb_history
+test
diff --git a/lib/libhmap/lib/liballoc/LICENSE b/lib/libhmap/lib/liballoc/LICENSE
new file mode 100644
index 0000000..361f116
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/LICENSE
@@ -0,0 +1,21 @@
+MIT License
+
+Copyright (c) 2023 Louis Burda
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
diff --git a/lib/libhmap/lib/liballoc/Makefile b/lib/libhmap/lib/liballoc/Makefile
new file mode 100644
index 0000000..dab8818
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/Makefile
@@ -0,0 +1,45 @@
+PREFIX ?= /usr/local
+LIBDIR ?= /lib
+INCLDIR ?= /include
+
+CFLAGS = -I include
+
+ifeq "$(DEBUG)" "1"
+CFLAGS += -Og -g
+else
+CFLAGS += -O2
+endif
+
+all: build/liballoc.so build/liballoc.a build/test
+
+clean:
+	rm -rf build
+
+cleanall: clean
+
+build:
+	mkdir build
+
+build/liballoc.a: src/allocator.c | build
+	$(CC) -o build/tmp.o src/allocator.c $(CFLAGS) -r
+	objcopy --keep-global-symbols=liballoc.api build/tmp.o build/fixed.o
+	ar rcs $@ build/fixed.o
+
+build/liballoc.so: src/allocator.c include/allocator.h | build
+	$(CC) -o $@ src/allocator.c $(CFLAGS) \
+		-shared -Wl,-version-script liballoc.lds
+
+build/test: src/test.c build/liballoc.a | build
+	$(CC) -o $@ $^ -I include
+
+install:
+	install -m755 include/allocator.h -t "$(DESTDIR)$(PREFIX)$(INCLDIR)"
+	install -m755 build/liballoc.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+	install -m755 build/liballoc.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+
+uninstall:
+	rm -f "$(DESTDIR)$(PREFIX)$(INCLDIR)/allocator.h"
+	rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/liballoc.a"
+	rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/liballoc.so"
+
+.PHONY: all clean cleanall install uninstall
diff --git a/lib/libhmap/lib/liballoc/build.jst.tmpl b/lib/libhmap/lib/liballoc/build.jst.tmpl
new file mode 100644
index 0000000..410749d
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/build.jst.tmpl
@@ -0,0 +1,60 @@
+#default PREFIX /usr/local
+#default INCLDIR /include
+#default LIBDIR /lib
+#default CC gcc
+
+#ifdef DEBUG
+#define OPT_CFLAGS -Og -g
+#else
+#define OPT_CFLAGS -O2
+#endif
+
+cflags = -Wunused-function -Wunused-variable -Wconversion -Wformat
+		-I include #{OPT_CFLAGS} #{EXTRA_CFLAGS}
+
+rule liba
+	gcc -o $out.tmp.o $in $cflags -r
+	objcopy --keep-global-symbols=liballoc.api $out.tmp.o $out.fixed.o
+	ar rcs $out $out.fixed.o
+	rm $out.tmp.o $out.fixed.o
+
+rule libso
+	gcc -o $out $in $cflags -shared -Wl,-version-script liballoc.lds
+
+rule cc
+	gcc -o $out $in $cflags
+
+rule mkdir
+	mkdir $out
+
+target build
+	mkdir
+
+target build/liballoc.a
+	liba src/allocator.c | include/allocator.h build
+
+target build/liballoc.so
+	libso src/allocator.c | include/allocator.h build
+
+target build/test
+	cc src/test.c build/liballoc.a | build
+
+command clean
+	rm -rf build
+
+command cleanall
+	just clean
+
+command install
+	install -m755 build/liballoc.a -t "#{DESTDIR}#{PREFIX}#{LIBDIR}"
+	install -m755 build/liballoc.so -t "#{DESTDIR}#{PREFIX}#{LIBDIR}"
+	install -m644 include/allocator.h -t "#{DESTDIR}#{PREFIX}#{INCLDIR}"
+
+command uninstall
+	rm -f "#{DESTDIR}#{PREFIX}#{LIBDIR}/liballoc.a"
+	rm -f "#{DESTDIR}#{PREFIX}#{LIBDIR}/liballoc.so"
+	rm -f "#{DESTDIR}#{PREFIX}#{INCLDIR}/allocator.h"
+
+command all
+	just build/liballoc.a build/liballoc.so build/test
+
diff --git a/lib/libhmap/lib/liballoc/common.mk b/lib/libhmap/lib/liballoc/common.mk
new file mode 100644
index 0000000..fe00d79
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/common.mk
@@ -0,0 +1,9 @@
+LIBALLOC_A = build/liballoc.a
+LIBALLOC_A_SRC = src/allocator.c
+LIBALLOC_A_DEP = $(LIBALLOC_A_SRC) include/allocator.h
+LIBALLOC_A_SRCDEP = $(LIBALLOC_A_DEP)
+
+LIBALLOC_SO = build/liballoc.so
+LIBALLOC_SO_SRC = src/allocator.c
+LIBALLOC_SO_DEP = $(LIBALLOC_SO_SRC) include/allocator.h
+LIBALLOC_SO_SRCDEP = $(LIBALLOC_SO_DEP)
diff --git a/lib/libhmap/lib/liballoc/configure b/lib/libhmap/lib/liballoc/configure
new file mode 100755
index 0000000..9b3f0eb
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/configure
@@ -0,0 +1,3 @@
+#!/bin/sh
+
+tmpl "$@" build.jst.tmpl > build.jst
diff --git a/lib/libhmap/lib/liballoc/include/allocator.h b/lib/libhmap/lib/liballoc/include/allocator.h
new file mode 100644
index 0000000..fc9a13d
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/include/allocator.h
@@ -0,0 +1,22 @@
+#pragma once
+
+#include <stddef.h>
+
+struct allocator {
+	void *(*alloc)(const struct allocator *allocator,
+		size_t size, int *rc);
+	void *(*realloc)(const struct allocator *allocator,
+		void *p, size_t size, int *rc);
+	int (*free)(const struct allocator *allocator, void *p);
+};
+
+struct strict_allocator {
+	const struct allocator *allocator_ul;
+	struct allocator allocator;
+};
+
+void strict_allocator_init(struct strict_allocator *strict_allocator_init,
+	const struct allocator *allocator_ul);
+
+extern const struct allocator stdlib_heap_allocator;
+extern const struct allocator stdlib_strict_heap_allocator;
diff --git a/lib/libhmap/lib/liballoc/liballoc.api b/lib/libhmap/lib/liballoc/liballoc.api
new file mode 100644
index 0000000..e875b2b
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/liballoc.api
@@ -0,0 +1,4 @@
+strict_allocator_init
+
+stdlib_heap_allocator
+stdlib_strict_heap_allocator
diff --git a/lib/libhmap/lib/liballoc/liballoc.lds b/lib/libhmap/lib/liballoc/liballoc.lds
new file mode 100644
index 0000000..07e5fca
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/liballoc.lds
@@ -0,0 +1,7 @@
+LIBALLOC_2.1 {
+	global:
+		strict_allocator_init;
+		stdlib_heap_allocator;
+		stdlib_strict_heap_allocator;
+	local: *;
+};
diff --git a/lib/libhmap/lib/liballoc/src/allocator.c b/lib/libhmap/lib/liballoc/src/allocator.c
new file mode 100644
index 0000000..eb6bc6d
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/src/allocator.c
@@ -0,0 +1,150 @@
+#include "allocator.h"
+
+#include <errno.h>
+#include <stdlib.h>
+
+static void *stdlib_heap_alloc(const struct allocator *allocator,
+	size_t size, int *rc);
+static void *stdlib_heap_realloc(const struct allocator *allocator,
+	void *p, size_t size, int *rc);
+static int stdlib_heap_free(const struct allocator *allocator, void *p);
+
+static void *stdlib_strict_heap_alloc(const struct allocator *allocator,
+	size_t size, int *rc);
+static void *stdlib_strict_heap_realloc(const struct allocator *allocator,
+	void *p, size_t size, int *rc);
+static int stdlib_strict_heap_free(const struct allocator *allocator, void *p);
+
+const struct allocator stdlib_heap_allocator = {
+	.alloc = stdlib_heap_alloc,
+	.realloc = stdlib_heap_realloc,
+	.free = stdlib_heap_free
+};
+
+const struct allocator stdlib_strict_heap_allocator = {
+	.alloc = stdlib_strict_heap_alloc,
+	.realloc = stdlib_strict_heap_realloc,
+	.free = stdlib_strict_heap_free
+};
+
+void *
+stdlib_heap_alloc(const struct allocator *allocator, size_t size, int *rc)
+{
+	void *p;
+
+	p = malloc(size);
+	if (rc && !p) *rc = errno;
+
+	return p;
+}
+
+void *
+stdlib_heap_realloc(const struct allocator *allocator,
+	void *p, size_t size, int *rc)
+{
+	void *np;
+
+	np = realloc(p, size);
+	if (rc && !np) *rc = errno;
+
+	return np;
+}
+
+int
+stdlib_heap_free(const struct allocator *allocator, void *p)
+{
+	free(p);
+
+	return 0;
+}
+
+void *
+stdlib_strict_heap_alloc(const struct allocator *allocator,
+	size_t size, int *rc)
+{
+	void *p;
+
+	p = malloc(size);
+	if (!p) abort();
+
+	return p;
+}
+
+void *
+stdlib_strict_heap_realloc(const struct allocator *allocator,
+	void *p, size_t size, int *rc)
+{
+	void *np;
+
+	np = realloc(p, size);
+	if (!np) abort();
+
+	return np;
+}
+
+int
+stdlib_strict_heap_free(const struct allocator *allocator, void *p)
+{
+	free(p);
+
+	return 0;
+}
+
+void *
+strict_allocator_alloc(const struct allocator *allocator, size_t size, int *rc)
+{
+	const struct strict_allocator *strict_allocator;
+	void *p;
+
+	strict_allocator = ((void *) allocator)
+		- offsetof(struct strict_allocator, allocator);
+
+	p = strict_allocator->allocator_ul->alloc(
+		strict_allocator->allocator_ul, size, rc);
+	if (!p) abort();
+
+	return p;
+}
+
+void *
+strict_allocator_realloc(const struct allocator *allocator,
+	void *p, size_t size, int *rc)
+{
+	const struct strict_allocator *strict_allocator;
+	void *np;
+
+	strict_allocator = ((void *) allocator)
+		- offsetof(struct strict_allocator, allocator);
+
+	np = strict_allocator->allocator_ul->realloc(
+		strict_allocator->allocator_ul, p, size, rc);
+	if (!np) abort();
+
+	return np;
+}
+
+int
+strict_allocator_free(const struct allocator *allocator, void *p)
+{
+	const struct strict_allocator *strict_allocator;
+	int rc;
+
+	strict_allocator = ((void *) allocator)
+		- offsetof(struct strict_allocator, allocator);
+
+	rc = strict_allocator->allocator_ul->free(
+		strict_allocator->allocator_ul, p);
+	if (rc) abort();
+
+	return 0;
+}
+
+void
+strict_allocator_init(struct strict_allocator *strict_allocator,
+	const struct allocator *allocator_ul)
+{
+	strict_allocator->allocator_ul = allocator_ul;
+	strict_allocator->allocator.alloc = strict_allocator_alloc;
+	strict_allocator->allocator.realloc = strict_allocator_realloc;
+	strict_allocator->allocator.free = strict_allocator_free;
+}
diff --git a/lib/libhmap/lib/liballoc/src/test.c b/lib/libhmap/lib/liballoc/src/test.c
new file mode 100644
index 0000000..7b3ee44
--- /dev/null
+++ b/lib/libhmap/lib/liballoc/src/test.c
@@ -0,0 +1,22 @@
+#include "allocator.h"
+
+#include <err.h>
+#include <string.h>
+#include <stdlib.h>
+
+const struct allocator *ga = &stdlib_heap_allocator;
+
+int
+main(int argc, const char **argv)
+{
+	struct test *test;
+	int rc;
+
+	if (argc <= 1) exit(1);
+
+	test = ga->alloc(ga, strtoull(argv[1], NULL, 10), &rc);
+	if (!test) errx(1, "alloc: %s", strerror(rc));
+
+	rc = ga->free(ga, test);
+	if (rc) errx(1, "free: %s", strerror(rc));
+}
diff --git a/lib/libhmap/libhmap.api b/lib/libhmap/libhmap.api
new file mode 100644
index 0000000..768193b
--- /dev/null
+++ b/lib/libhmap/libhmap.api
@@ -0,0 +1,25 @@
+hmap_init
+hmap_deinit
+hmap_alloc
+hmap_free
+
+hmap_copy
+hmap_swap
+hmap_clear
+
+hmap_link_get
+hmap_link_pos
+hmap_link_pop
+hmap_link_set
+hmap_link_alloc
+
+hmap_get
+hmap_rm
+hmap_set
+hmap_add
+
+hmap_iter_init
+hmap_iter_next
+
+hmap_str_hash
+hmap_str_keycmp
diff --git a/lib/libhmap/libhmap.lds b/lib/libhmap/libhmap.lds
new file mode 100644
index 0000000..e3ac91f
--- /dev/null
+++ b/lib/libhmap/libhmap.lds
@@ -0,0 +1,27 @@
+LIBHMAP_1.0.0 {
+	hmap_init;
+	hmap_deinit;
+	hmap_alloc;
+	hmap_free;
+
+	hmap_copy;
+	hmap_swap;
+	hmap_clear;
+
+	hmap_link_get;
+	hmap_link_pos;
+	hmap_link_pop;
+	hmap_link_set;
+	hmap_link_add;
+	hmap_link_alloc;
+
+	hmap_get;
+	hmap_rm;
+	hmap_set;
+
+	hmap_iter_init;
+	hmap_iter_next;
+
+	hmap_str_hash;
+	hmap_str_keycmp;
+};
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);
+}
diff --git a/lib/libhmap/src/test.c b/lib/libhmap/src/test.c
new file mode 100644
index 0000000..b248702
--- /dev/null
+++ b/lib/libhmap/src/test.c
@@ -0,0 +1,42 @@
+#include "hmap.h"
+
+#include <err.h>
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#define LIBHMAP_ERR(rc) errx(1, "libhmap: %s", \
+	rc < 0 ? strerror(-rc) : hmap_err[rc])
+
+static const char *hmap_err[] = {
+	HMAP_STRERR_INIT
+};
+
+int
+main(int argc, const char **argv)
+{
+	struct hmap hmap;
+	struct hmap_iter iter;
+	char *arg;
+	int i, rc;
+
+	rc = hmap_init(&hmap, 10, hmap_str_hash,
+		hmap_str_keycmp, &stdlib_heap_allocator);
+	if (rc) LIBHMAP_ERR(rc);
+
+	for (i = 1; i < argc; i++) {
+		arg = strdup(argv[i]);
+		rc = hmap_add(&hmap, (struct hmap_key) {.p = arg},
+			(struct hmap_val) {.i = i});
+		if (rc) LIBHMAP_ERR(rc);
+	}
+
+	for (HMAP_ITER(&hmap, iter)) {
+		printf("%s: %i\n", (char *)iter.link->key.p,
+			iter.link->value.i);
+	}
+
+	for (HMAP_ITER(&hmap, iter))
+		free(iter.link->key._p);
+	hmap_deinit(&hmap);
+}