commit 3bedae2458a1fc293e5a580bff663816537363a8
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 15 Mar 2024 22:53:25 +0100
Squashed 'src/lib/libhmap/' content from commit e86177e
git-subtree-dir: src/lib/libhmap
git-subtree-split: e86177eb3072c0c755986ff4c8d4c5d0cce72139
Diffstat:
12 files changed, 704 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,6 @@
+compile_commands.json
+build
+build.jst
+.cache
+vgcore*
+test
diff --git a/.gitmodules b/.gitmodules
@@ -0,0 +1,3 @@
+[submodule "lib/liballoc"]
+ path = lib/liballoc
+ url = git@sinitax.com:sinitax/liballoc
diff --git a/LICENSE b/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/Makefile b/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/build.jst.tmpl b/build.jst.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
+ just 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
+ just clean
+ just -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
+ just build/libhmap.a build/libhmap.so build/test
+
diff --git a/configure b/configure
@@ -0,0 +1,8 @@
+#!/bin/sh
+
+tmpl "$@" build.jst.tmpl > build.jst
+for lib in ./lib/*; do
+ pushd $lib
+ ./configure "$@"
+ popd
+done
diff --git a/include/hmap.h b/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/liballoc b/lib/liballoc
@@ -0,0 +1 @@
+Subproject commit 3f388a2659ae2d121322101930d33412815d84e6
diff --git a/libhmap.api b/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/libhmap.lds b/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/src/hmap.c b/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/src/test.c b/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);
+}
