diff options
91 files changed, 4508 insertions, 23 deletions
@@ -1,5 +1,7 @@ .cache .gdb_history compile_commands.json -build.jst +build.rmk tabular +.subgit +/.subgit diff --git a/.gitmodules b/.gitmodules index ee1b0f1..e69de29 100644 --- a/.gitmodules +++ b/.gitmodules @@ -1,12 +0,0 @@ -[submodule "lib/libtabular"] - path = lib/libtabular - url = git@sinitax.com:sinitax/libtabular-c -[submodule "lib/libdvec"] - path = lib/libdvec - url = git@sinitax.com:sinitax/libdvec-c -[submodule "lib/libhmap"] - path = lib/libhmap - url = git@sinitax.com:sinitax/libhmap-c -[submodule "lib/liballoc"] - path = lib/liballoc - url = git@sinitax.com:sinitax/liballoc-c diff --git a/.subgitrc b/.subgitrc new file mode 100644 index 0000000..2b162b1 --- /dev/null +++ b/.subgitrc @@ -0,0 +1,24 @@ +#!/bin/bash + +declare -A subgit subgitinfo + +subgit[lib/libdvec]=1 +subgitinfo[lib/libdvec/remote]='git@sinitax.com:sinitax/libdvec-c' +subgitinfo[lib/libdvec/branch]='master' +subgitinfo[lib/libdvec/commit]='83827177907caedf60f8c1c8d1692d976dcef3ee' + +subgit[lib/liballoc]=1 +subgitinfo[lib/liballoc/remote]='git@sinitax.com:sinitax/liballoc-c' +subgitinfo[lib/liballoc/branch]='master' +subgitinfo[lib/liballoc/commit]='fd51196ac2d1bf1c34c8578146ef1bc66c1c8ec4' + +subgit[lib/libtabular]=1 +subgitinfo[lib/libtabular/remote]='git@sinitax.com:sinitax/libtabular-c' +subgitinfo[lib/libtabular/branch]='master' +subgitinfo[lib/libtabular/commit]='897ff51fdb9bccb90415d1bcd54541640dba4465' + +subgit[lib/libhmap]=1 +subgitinfo[lib/libhmap/remote]='git@sinitax.com:sinitax/libhmap-c' +subgitinfo[lib/libhmap/branch]='master' +subgitinfo[lib/libhmap/commit]='eff6ad090ed53cf97b11393fc3ab45abe8f67214' + diff --git a/build.rmk b/build.rmk new file mode 100644 index 0000000..f794a51 --- /dev/null +++ b/build.rmk @@ -0,0 +1,43 @@ + + +cflags = -I lib/libdvec/include -I lib/libhmap/include + -I lib/libtabular/include -I lib/liballoc/include + -Wunused-variable -Wunused-function -Wconversion + -O2 + +rule cc + gcc -o $out $in $cflags + +target lib/libdvec/build/libdvec.a + rmk lib/libdvec + +target lib/libhmap/build/libhmap.a + rmk lib/libhmap + +target lib/libtabular/build/libtabular.a + rmk lib/libtabular + +target lib/liballoc/build/liballoc.a + rmk lib/liballoc + +target tabular + cc tabular.c lib/libdvec/build/libdvec.a lib/libhmap/build/libhmap.a + lib/libtabular/build/libtabular.a lib/liballoc/build/liballoc.a + +command clean + rm -f tabular + +command cleanall + rmk clean + rmk -C lib/libtabular clean + rmk -C lib/libhmap clean + rmk -C lib/libdvec clean + +command install + install -m755 tabular -t "/usr/local/bin" + +command uninstall + rm -f "/usr/local/bin/tabular" + +command all + rmk tabular diff --git a/build.jst.tmpl b/build.rmk.tmpl index 45eb28a..c51085e 100644 --- a/build.jst.tmpl +++ b/build.rmk.tmpl @@ -17,16 +17,16 @@ rule cc #{CC} -o $out $in $cflags target lib/libdvec/build/libdvec.a - just lib/libdvec + rmk lib/libdvec target lib/libhmap/build/libhmap.a - just lib/libhmap + rmk lib/libhmap target lib/libtabular/build/libtabular.a - just lib/libtabular + rmk lib/libtabular target lib/liballoc/build/liballoc.a - just lib/liballoc + rmk lib/liballoc target tabular cc tabular.c lib/libdvec/build/libdvec.a lib/libhmap/build/libhmap.a @@ -36,10 +36,10 @@ command clean rm -f tabular command cleanall - just clean - just -C lib/libtabular clean - just -C lib/libhmap clean - just -C lib/libdvec clean + rmk clean + rmk -C lib/libtabular clean + rmk -C lib/libhmap clean + rmk -C lib/libdvec clean command install install -m755 tabular -t "#{DESTDIR}#{PREFIX}#{BINDIR}" @@ -48,4 +48,4 @@ command uninstall rm -f "#{DESTDIR}#{PREFIX}#{BINDIR}/tabular" command all - just tabular + rmk tabular @@ -1,6 +1,9 @@ #!/bin/sh -tmpl "$@" build.jst.tmpl > build.jst +set -ex + +tmpl "$@" build.rmk.tmpl > build.rmk + for lib in ./lib/*; do pushd $lib ./configure "$@" diff --git a/lib/liballoc b/lib/liballoc deleted file mode 160000 -Subproject 3f388a2659ae2d121322101930d33412815d84e diff --git a/lib/liballoc/.gitignore b/lib/liballoc/.gitignore new file mode 100644 index 0000000..b6a670a --- /dev/null +++ b/lib/liballoc/.gitignore @@ -0,0 +1,7 @@ +compile_commands.json +build +build.rmk +.cache +vgcore* +.gdb_history +test diff --git a/lib/liballoc/LICENSE b/lib/liballoc/LICENSE new file mode 100644 index 0000000..361f116 --- /dev/null +++ b/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/liballoc/Makefile b/lib/liballoc/Makefile new file mode 100644 index 0000000..dab8818 --- /dev/null +++ b/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/liballoc/build.rmk.tmpl b/lib/liballoc/build.rmk.tmpl new file mode 100644 index 0000000..410749d --- /dev/null +++ b/lib/liballoc/build.rmk.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/liballoc/common.mk b/lib/liballoc/common.mk new file mode 100644 index 0000000..fe00d79 --- /dev/null +++ b/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/liballoc/configure b/lib/liballoc/configure new file mode 100755 index 0000000..16d5220 --- /dev/null +++ b/lib/liballoc/configure @@ -0,0 +1,5 @@ +#!/bin/sh + +set -ex + +tmpl "$@" build.rmk.tmpl > build.rmk diff --git a/lib/liballoc/include/allocator.h b/lib/liballoc/include/allocator.h new file mode 100644 index 0000000..fc9a13d --- /dev/null +++ b/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/liballoc/liballoc.api b/lib/liballoc/liballoc.api new file mode 100644 index 0000000..e875b2b --- /dev/null +++ b/lib/liballoc/liballoc.api @@ -0,0 +1,4 @@ +strict_allocator_init + +stdlib_heap_allocator +stdlib_strict_heap_allocator diff --git a/lib/liballoc/liballoc.lds b/lib/liballoc/liballoc.lds new file mode 100644 index 0000000..07e5fca --- /dev/null +++ b/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/liballoc/src/allocator.c b/lib/liballoc/src/allocator.c new file mode 100644 index 0000000..eb6bc6d --- /dev/null +++ b/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/liballoc/src/test.c b/lib/liballoc/src/test.c new file mode 100644 index 0000000..7b3ee44 --- /dev/null +++ b/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/libdvec b/lib/libdvec deleted file mode 160000 -Subproject d9bc4e34e3a880e31118af3b7f623d644af7025 diff --git a/lib/libdvec/.gitignore b/lib/libdvec/.gitignore new file mode 100644 index 0000000..374a2c2 --- /dev/null +++ b/lib/libdvec/.gitignore @@ -0,0 +1,9 @@ +compile_commands.json +build +build.rmk +.cache +vgcore* +test +.gdb_history +/.subgit +/.subrepo diff --git a/lib/libdvec/.gitmodules b/lib/libdvec/.gitmodules new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/lib/libdvec/.gitmodules diff --git a/lib/libdvec/.subgitrc b/lib/libdvec/.subgitrc new file mode 100644 index 0000000..5f1b14f --- /dev/null +++ b/lib/libdvec/.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/libdvec/LICENSE b/lib/libdvec/LICENSE new file mode 100644 index 0000000..361f116 --- /dev/null +++ b/lib/libdvec/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/libdvec/Makefile b/lib/libdvec/Makefile new file mode 100644 index 0000000..0361af4 --- /dev/null +++ b/lib/libdvec/Makefile @@ -0,0 +1,59 @@ +PREFIX ?= /usr/local +LIBDIR ?= /lib +INCLDIR ?= /include + +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 += -DLIBDVEC_ASSERT_ARGS=1 +endif + +ifeq "$(ASSERT_ALLOC)" "1" +CFLAGS += -DLIBDVEC_ASSERT_ALLOC=1 +endif + +all: build/libdvec.so build/libdvec.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/libdvec.a: src/dvec.c include/dvec.h libdvec.api | build + $(CC) -o build/tmp.o src/dvec.c $(CFLAGS) -r + objcopy --keep-global-symbols=libdvec.api build/tmp.o build/fixed.o + ar rcs $@ build/fixed.o + +build/libdvec.so: src/dvec.c include/dvec.h libdvec.lds | build + $(CC) -o $@ src/dvec.c -fPIC $(CFLAGS) \ + -shared -Wl,-version-script libdvec.lds + +build/test: src/test.c build/libdvec.a lib/liballoc/build/liballoc.a + $(CC) -o $@ $^ $(CFLAGS) + +install: + install -m644 include/dvec.h -t "$(DESTDIR)$(PREFIX)$(INCLDIR)" + install -m755 build/libdvec.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)" + install -m755 build/libdvec.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)" + +uninstall: + rm -f "$(DESTDIR)$(PREFIX)$(INCLDIR)/dvec.h" + rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libdvec.so" + rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libdvec.a" + +.PHONY: all clean cleanall install uninstall diff --git a/lib/libdvec/build.rmk.tmpl b/lib/libdvec/build.rmk.tmpl new file mode 100644 index 0000000..873a83d --- /dev/null +++ b/lib/libdvec/build.rmk.tmpl @@ -0,0 +1,69 @@ +#default PREFIX /usr/local +#default INCLDIR /include +#default LIBDIR /lib +#default CC gcc + +#ifdef LIBDVEC_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 + -Wpedantic -I include -I lib/liballoc/include + #{OPT_CFLAGS} #{LIBDVEC_EXTRA_CFLAGS} #{EXTRA_CFLAGS} + +rule liba + #{CC} -o $out.tmp.o $in $cflags -r + objcopy --keep-global-symbols=libdvec.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 libdvec.lds + +rule cc + #{CC} -o $out $in $cflags + +rule mkdir + mkdir $out + +target build + mkdir + +target lib/liballoc/build/liballoc.a + rmk lib/liballoc + +target build/libdvec.a + liba src/dvec.c | include/dvec.h build + +target build/libdvec.so + libso src/dvec.c | include/dvec.h build + +target build/test + cc src/test.c build/libdvec.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/libdvec.a -t "#{DESTDIR}#{PREFIX}#{LIBDIR}" + install -m755 build/libdvec.so -t "#{DESTDIR}#{PREFIX}#{LIBDIR}" + install -m644 include/dvec.h -t "#{DESTDIR}#{PREFIX}#{INCLDIR}" + +command uninstall + rm -f "#{DESTDIR}#{PREFIX}#{LIBDIR}/libdvec.a" + rm -f "#{DESTDIR}#{PREFIX}#{LIBDIR}/libdvec.so" + rm -f "#{DESTDIR}#{PREFIX}#{INCLDIR}/dvec.h" + +command all + rmk build/libdvec.a build/libdvec.so build/test + diff --git a/lib/libdvec/configure b/lib/libdvec/configure new file mode 100755 index 0000000..b4dd05d --- /dev/null +++ b/lib/libdvec/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/libdvec/include/dvec.h b/lib/libdvec/include/dvec.h new file mode 100644 index 0000000..45888a6 --- /dev/null +++ b/lib/libdvec/include/dvec.h @@ -0,0 +1,182 @@ +#pragma once + +#include "allocator.h" + +#include <sys/types.h> +#include <limits.h> +#include <stdbool.h> +#include <stdint.h> +#include <stddef.h> + +#define DVEC_ERRNO(rc) ((rc) > 0 && (rc) & (1 << 30) ? (rc) & ~(1 << 30) : 0) +#define DVEC_ERR(lut, rc) errx(1, "libdvec: %s", \ + (rc) == DVEC_BAD ? lut[0] : (DVEC_ERRNO(rc) ? strerror(DVEC_ERRNO(rc)) : lut[rc+1])) + +#define DVEC_ITER(dvec, p) (p) = NULL; ((p) = dvec_iter_fwd((dvec), (p))); +#define DVEC_ITER_BWD(dvec, p) (p) = NULL; ((p) = dvec_iter_bwd((dvec), (p))); + +#define DVEC_STRERR_INIT \ + [0] = "Failure", \ + [1+DVEC_OK] = "Success", \ + [1+DVEC_LOCKED] = "Locked", \ + [1+DVEC_MODIFIED] = "Modified" + +#ifdef LIBDVEC_ASSERT_ARGS +#include "stdlib.h" +#define LIBDVEC_ABORT_ON_ARGS(cond) do { if (cond) abort(); } while (0) +#else +#define LIBDVEC_ABORT_ON_ARGS(cond) +#endif + +#ifdef LIBDVEC_ASSERT_ALLOC +#include "stdlib.h" +#define LIBDVEC_ABORT_ON_ALLOC(cond) do { if (cond) abort(); } while (0) +#else +#define LIBDVEC_ABORT_ON_ALLOC(cond) +#endif + +enum { + DVEC_BAD = -1 & INT_MAX, + DVEC_OK = 0, + DVEC_LOCKED = 1 << 0, + DVEC_MODIFIED = 1 << 1 +}; + +struct dvec { + size_t dsize; + size_t len, cap; + uint8_t *data; + uint8_t locked : 1; /* prevents resizes */ + uint8_t fused : 1; /* single allocation w/ data */ + const struct allocator *allocator; +}; + +typedef bool (*dvec_sort_order_fn)(const void *left, const void *right, const void *user); +typedef int (*dvec_search_cmp_fn)(const void *other, const void *user); + +int dvec_init(struct dvec *dvec, size_t dsize, size_t cap, + const struct allocator *allocator); +int dvec_deinit(struct dvec *dvec); + +struct dvec *dvec_alloc(size_t dsize, size_t cap, + const struct allocator *allocator, int *rc); +struct dvec *dvec_alloc_fused(size_t dsize, size_t cap, + const struct allocator *allocator, int *rc); +int dvec_free(struct dvec *dvec); + +int dvec_copy(struct dvec *dst, struct dvec *src); +void dvec_move(struct dvec *dst, struct dvec *src); +void dvec_swap(struct dvec *dst, struct dvec *src); + +void dvec_clear(struct dvec *dvec); +int dvec_reserve(struct dvec *dvec, size_t cap); +int dvec_shrink(struct dvec *dvec); + +int dvec_add(struct dvec *dvec, size_t index, size_t count); +void dvec_rm(struct dvec *dvec, size_t index, size_t count); +void dvec_replace(struct dvec *dvec, size_t index, + const void *data, size_t count); + +void *dvec_iter_fwd(const struct dvec *dvec, const void *p); +void *dvec_iter_bwd(const struct dvec *dvec, const void *p); + +int dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator, + void *tmp, bool reverse, dvec_sort_order_fn in_order, const void *user); +int dvec_quick_sort_ex(struct dvec *dvec, const struct allocator *allocator, + void *tmp, bool reverse, dvec_sort_order_fn in_order, const void *user); + +ssize_t dvec_binary_search(struct dvec *dvec, dvec_search_cmp_fn search_cmp, + void *user, ssize_t *lower, ssize_t *higher); + +static inline void * +dvec_at(const struct dvec *dvec, size_t index) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec || index >= dvec->len); + + return dvec->data + index * dvec->dsize; +} + +static inline void * +dvec_at_back(const struct dvec *dvec, size_t index) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec || !index || index >= dvec->len); + + return dvec->data + (dvec->len - 1 - index) * dvec->dsize; +} + +static inline void * +dvec_front(const struct dvec *dvec) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec); + + return dvec->data; +} + +static inline void * +dvec_back(const struct dvec *dvec) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec); + + return dvec->data + (dvec->len - 1) * dvec->dsize; +} + +static inline bool +dvec_empty(const struct dvec *dvec) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec); + + return !dvec->len; +} + +static inline size_t +dvec_len(const struct dvec *dvec) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec); + + return dvec->len; +} + +static inline int +dvec_add_back(struct dvec *dvec, size_t count) +{ + return dvec_add(dvec, dvec->len, count); +} + +static inline void +dvec_rm_back(struct dvec *dvec, size_t count) +{ + dvec_rm(dvec, dvec->len - count, count); +} + +static inline void +dvec_lock(struct dvec *dvec, bool lock) +{ + dvec->locked = lock; +} + +static inline void * +dvec_push(struct dvec *dvec) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec); + + dvec_reserve(dvec, dvec->len + 1); + + return dvec->data + dvec->len++ * dvec->dsize; +} + +static inline void * +dvec_pop(struct dvec *dvec) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec || !dvec->len); + + return dvec->data + --dvec->len * dvec->dsize; +} + +static inline size_t +dvec_idx(struct dvec *dvec, const void *p) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec || p < dvec->data + || p >= dvec->data + dvec->dsize * dvec->len); + + return (size_t) ((uint8_t *)p - dvec->data) / dvec->dsize; +} diff --git a/lib/libdvec/lib/liballoc/.gitignore b/lib/libdvec/lib/liballoc/.gitignore new file mode 100644 index 0000000..ac80ccf --- /dev/null +++ b/lib/libdvec/lib/liballoc/.gitignore @@ -0,0 +1,7 @@ +compile_commands.json +build +build.jst +.cache +vgcore* +.gdb_history +test diff --git a/lib/libdvec/lib/liballoc/LICENSE b/lib/libdvec/lib/liballoc/LICENSE new file mode 100644 index 0000000..361f116 --- /dev/null +++ b/lib/libdvec/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/libdvec/lib/liballoc/Makefile b/lib/libdvec/lib/liballoc/Makefile new file mode 100644 index 0000000..dab8818 --- /dev/null +++ b/lib/libdvec/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/libdvec/lib/liballoc/build.jst.tmpl b/lib/libdvec/lib/liballoc/build.jst.tmpl new file mode 100644 index 0000000..410749d --- /dev/null +++ b/lib/libdvec/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/libdvec/lib/liballoc/common.mk b/lib/libdvec/lib/liballoc/common.mk new file mode 100644 index 0000000..fe00d79 --- /dev/null +++ b/lib/libdvec/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/libdvec/lib/liballoc/configure b/lib/libdvec/lib/liballoc/configure new file mode 100755 index 0000000..9b3f0eb --- /dev/null +++ b/lib/libdvec/lib/liballoc/configure @@ -0,0 +1,3 @@ +#!/bin/sh + +tmpl "$@" build.jst.tmpl > build.jst diff --git a/lib/libdvec/lib/liballoc/include/allocator.h b/lib/libdvec/lib/liballoc/include/allocator.h new file mode 100644 index 0000000..fc9a13d --- /dev/null +++ b/lib/libdvec/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/libdvec/lib/liballoc/liballoc.api b/lib/libdvec/lib/liballoc/liballoc.api new file mode 100644 index 0000000..e875b2b --- /dev/null +++ b/lib/libdvec/lib/liballoc/liballoc.api @@ -0,0 +1,4 @@ +strict_allocator_init + +stdlib_heap_allocator +stdlib_strict_heap_allocator diff --git a/lib/libdvec/lib/liballoc/liballoc.lds b/lib/libdvec/lib/liballoc/liballoc.lds new file mode 100644 index 0000000..07e5fca --- /dev/null +++ b/lib/libdvec/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/libdvec/lib/liballoc/src/allocator.c b/lib/libdvec/lib/liballoc/src/allocator.c new file mode 100644 index 0000000..eb6bc6d --- /dev/null +++ b/lib/libdvec/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/libdvec/lib/liballoc/src/test.c b/lib/libdvec/lib/liballoc/src/test.c new file mode 100644 index 0000000..7b3ee44 --- /dev/null +++ b/lib/libdvec/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/libdvec/libdvec.api b/lib/libdvec/libdvec.api new file mode 100644 index 0000000..a421bc3 --- /dev/null +++ b/lib/libdvec/libdvec.api @@ -0,0 +1,25 @@ +dvec_init +dvec_deinit + +dvec_alloc +dvec_alloc_fused +dvec_free + +dvec_copy +dvec_swap + +dvec_clear +dvec_reserve +dvec_shrink + +dvec_add +dvec_rm +dvec_replace + +dvec_iter_fwd +dvec_iter_bwd + +dvec_quick_sort +dvec_quick_sort_ex + +dvec_binary_search diff --git a/lib/libdvec/libdvec.lds b/lib/libdvec/libdvec.lds new file mode 100644 index 0000000..4f0fc40 --- /dev/null +++ b/lib/libdvec/libdvec.lds @@ -0,0 +1,29 @@ +LIBDVEC_1.1.4 { + global: + dvec_init; + dvec_deinit; + + dvec_alloc; + dvec_alloc_fused; + dvec_free; + + dvec_copy; + dvec_swap; + + dvec_clear; + dvec_reserve; + dvec_shrink; + + dvec_add; + dvec_rm; + dvec_replace; + + dvec_iter_fwd; + dvec_iter_bwd; + + dvec_quick_sort; + dvec_quick_sort_ex; + + dvec_binary_search; + local: *; +}; diff --git a/lib/libdvec/src/dvec.c b/lib/libdvec/src/dvec.c new file mode 100644 index 0000000..bc71f3f --- /dev/null +++ b/lib/libdvec/src/dvec.c @@ -0,0 +1,510 @@ +#include "dvec.h" + +#include <stddef.h> +#include <string.h> + +#define ERR(x) ((x) >= 0 ? DVEC_BAD : (x)) + +struct sort_order_user_proxy { + dvec_sort_order_fn order_fn; + const void *user; +}; + +int +dvec_init(struct dvec *dvec, size_t dsize, size_t cap, + const struct allocator *allocator) +{ + int rc = 0; + + LIBDVEC_ABORT_ON_ARGS(!dvec || !dsize || !allocator); + + dvec->allocator = allocator; + dvec->dsize = dsize; + dvec->cap = cap; + dvec->len = 0; + dvec->data = NULL; + dvec->locked = false; + dvec->fused = false; + if (dvec->cap) { + dvec->data = allocator->alloc(allocator, cap * dsize, &rc); + LIBDVEC_ABORT_ON_ALLOC(!dvec->data); + if (!dvec->data) return ERR(rc); + } + + return DVEC_OK; +} + +int +dvec_deinit(struct dvec *dvec) +{ + int rc; + + LIBDVEC_ABORT_ON_ARGS(!dvec); + + rc = dvec->allocator->free(dvec->allocator, dvec->data); + LIBDVEC_ABORT_ON_ALLOC(rc); + + return rc >= 0 ? DVEC_OK : ERR(rc); +} + +struct dvec * +dvec_alloc(size_t dsize, size_t cap, + const struct allocator *allocator, int *rc) +{ + struct dvec *dvec; + int _rc; + + LIBDVEC_ABORT_ON_ARGS(!allocator); + + dvec = allocator->alloc(allocator, sizeof(struct dvec), &_rc); + LIBDVEC_ABORT_ON_ALLOC(!dvec); + if (!dvec) { + if (rc) *rc = ERR(_rc); + return NULL; + } + + _rc = dvec_init(dvec, dsize, cap, allocator); + if (_rc < 0) { + if (rc) *rc = _rc; + allocator->free(allocator, dvec); + return NULL; + } + + return dvec; +} + +static size_t +aligned_size(size_t size, size_t dsize) +{ + return size + (size % dsize ? dsize - size % dsize : 0); +} + +struct dvec * +dvec_alloc_fused(size_t dsize, size_t cap, + const struct allocator *allocator, int *rc) +{ + struct dvec *dvec; + size_t off; + int _rc = 0; + + LIBDVEC_ABORT_ON_ARGS(!allocator); + + off = aligned_size(sizeof(struct dvec), dsize); + dvec = allocator->alloc(allocator, off + cap * dsize, &_rc); + if (!dvec) { + if (_rc) *rc = ERR(_rc); + return NULL; + } + + dvec->allocator = allocator; + dvec->dsize = dsize; + dvec->cap = cap; + dvec->len = 0; + dvec->data = (uint8_t *) dvec + off; + dvec->locked = false; + dvec->fused = true; + + return dvec; +} + +int +dvec_free(struct dvec *dvec) +{ + const struct allocator *allocator; + int rc; + + if (!dvec) return DVEC_OK; + + allocator = dvec->allocator; + + if (dvec->fused) { + rc = allocator->free(allocator, dvec); + if (rc < 0) return rc; + } else { + rc = dvec_deinit(dvec); + if (rc) return rc; + + rc = allocator->free(allocator, dvec); + LIBDVEC_ABORT_ON_ALLOC(rc); + if (rc < 0) return rc; + } + + return DVEC_OK; +} + +int +dvec_copy(struct dvec *dst, struct dvec *src) +{ + int rc; + + LIBDVEC_ABORT_ON_ARGS(!dst || !src || dst->dsize != src->dsize); + + rc = dvec_reserve(dst, src->len); + if (rc) return rc; + + dst->len = src->len; + memcpy(dst->data, src->data, src->len * src->dsize); + + return DVEC_OK; +} + +void +dvec_move(struct dvec *dst, struct dvec *src) +{ + LIBDVEC_ABORT_ON_ARGS(!dst || !src); + + memcpy(dst, src, sizeof(struct dvec)); +} + +void +dvec_swap(struct dvec *dst, struct dvec *src) +{ + struct dvec tmp; + + LIBDVEC_ABORT_ON_ARGS(!dst || !src); + + memcpy(&tmp, dst, sizeof(struct dvec)); + memcpy(dst, src, sizeof(struct dvec)); + memcpy(src, &tmp, sizeof(struct dvec)); +} + +void +dvec_clear(struct dvec *dvec) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec); + + dvec->len = 0; +} + +int +dvec_reserve(struct dvec *dvec, size_t len) +{ + void *data; + size_t cap, off; + int rc = 1; + + LIBDVEC_ABORT_ON_ARGS(!dvec); + + if (len <= dvec->cap) return DVEC_OK; + + if (dvec->locked) return DVEC_LOCKED; + + cap = 2 * dvec->cap; + if (len > cap) cap = len; + + if (dvec->fused) { + off = aligned_size(sizeof(struct dvec), dvec->dsize); + data = dvec->allocator->realloc(dvec->allocator, dvec, + off + dvec->cap * dvec->dsize, &rc); + LIBDVEC_ABORT_ON_ALLOC(!data); + if (!data) return ERR(rc); + dvec = data; + dvec->data = (uint8_t *) dvec + off; + } else { + data = dvec->allocator->realloc(dvec->allocator, + dvec->data, cap * dvec->dsize, &rc); + LIBDVEC_ABORT_ON_ALLOC(!data); + if (!data) return ERR(rc); + dvec->data = data; + } + + dvec->cap = cap; + + return DVEC_OK; +} + +int +dvec_shrink(struct dvec *dvec) +{ + void *data; + size_t cap, off; + int rc = 0; + + LIBDVEC_ABORT_ON_ARGS(!dvec); + + if (dvec->locked) return DVEC_LOCKED; + + cap = dvec->len; + + if (dvec->fused) { + off = aligned_size(sizeof(struct dvec), dvec->dsize); + data = dvec->allocator->realloc(dvec->allocator, dvec, + off + cap * dvec->dsize, &rc); + LIBDVEC_ABORT_ON_ALLOC(!data); + if (!data) return ERR(rc); + dvec = data; + dvec->data = (uint8_t *) dvec + off; + } else if (!dvec->len) { + rc = dvec->allocator->free(dvec->allocator, dvec->data); + LIBDVEC_ABORT_ON_ALLOC(rc); + if (rc < 0) return rc; + } else { + data = dvec->allocator->realloc(dvec->allocator, + &dvec->data, cap * dvec->dsize, &rc); + LIBDVEC_ABORT_ON_ALLOC(!data); + if (!data) return ERR(rc); + dvec->data = data; + } + + dvec->cap = cap; + + return DVEC_OK; +} + +int +dvec_add(struct dvec *dvec, size_t index, size_t len) +{ + int rc; + + LIBDVEC_ABORT_ON_ARGS(!dvec || index > dvec->len); + + rc = dvec_reserve(dvec, dvec->len + len); + if (rc) return rc; + + if (index < dvec->len) { + memmove(dvec->data + (index + len) * dvec->dsize, + dvec->data + index * dvec->dsize, + (dvec->len - index) * dvec->dsize); + } + + dvec->len += len; + + return DVEC_OK; +} + +void +dvec_rm(struct dvec *dvec, size_t index, size_t count) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec || index + count > dvec->len); + + if (index + count < dvec->len) { + memmove(dvec->data + index * dvec->dsize, + dvec->data + (index + count) * dvec->dsize, + (dvec->len - (index + count)) * dvec->dsize); + } + + dvec->len -= count; +} + +void +dvec_replace(struct dvec *dvec, size_t index, const void *data, size_t count) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec || !data || index + count > dvec->len); + + memcpy(dvec->data + index * dvec->dsize, data, count * dvec->dsize); +} + +void * +dvec_iter_fwd(const struct dvec *dvec, const void *p) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec); + LIBDVEC_ABORT_ON_ARGS(p && (p < dvec->data)); + LIBDVEC_ABORT_ON_ARGS(p && (p >= dvec->data + dvec->len * dvec->dsize)); + LIBDVEC_ABORT_ON_ARGS(p && ((size_t) (p - dvec->data) % dvec->dsize)); + + if (p == NULL) { + if (dvec->len > 0) + return dvec->data; + else + return NULL; + } else if ((uint8_t *) p < dvec->data + dvec->dsize * (dvec->len - 1)) { + return (uint8_t *) p + dvec->dsize; + } else { + return NULL; + } +} + +void * +dvec_iter_bwd(const struct dvec *dvec, const void *p) +{ + LIBDVEC_ABORT_ON_ARGS(!dvec); + LIBDVEC_ABORT_ON_ARGS(p && (p < dvec->data)); + LIBDVEC_ABORT_ON_ARGS(p && (p >= dvec->data + dvec->len * dvec->dsize)); + LIBDVEC_ABORT_ON_ARGS(p && ((size_t) (p - dvec->data) % dvec->dsize)); + + if (p == NULL) { + if (dvec->len > 0) + return dvec->data + (dvec->len - 1) * dvec->dsize; + else + return NULL; + } else if ((uint8_t *) p > dvec->data) { + return (uint8_t *) p - dvec->dsize; + } else { + return NULL; + } +} + +static void +dvec_quick_sort_swap(void *a, void *b, void *tmp, size_t dsize) +{ + memcpy(tmp, a, dsize); + memcpy(a, b, dsize); + memcpy(b, tmp, dsize); +} + +int +dvec_quick_sort(struct dvec *dvec, const struct allocator *allocator, + void *tmp, bool reverse, dvec_sort_order_fn in_order, const void *user) +{ + const size_t dsize = dvec->dsize; + struct dvec stack; + uint8_t *start, *end; + uint8_t *lo, *hi, *pivot; + bool lo_order, hi_order; + bool modified = false; + int rc; + + if (!dvec->len) return DVEC_OK; + + rc = dvec_init(&stack, sizeof(uint8_t *), 32, allocator); + if (rc) return rc; + + *(uint8_t **)dvec_push(&stack) = dvec_front(dvec); + *(uint8_t **)dvec_push(&stack) = dvec_back(dvec); + + while (!dvec_empty(&stack)) { + end = *(uint8_t **)dvec_pop(&stack); + start = *(uint8_t **)dvec_pop(&stack); + + if (start == end) continue; + + if (start + dsize >= end) { + if (!in_order(start, end, user)) { + dvec_quick_sort_swap(start, end, tmp, dsize); + modified = true; + } + continue; + } + + lo = start; + hi = end; + pivot = start + (size_t) (end - start) / dsize / 2 * dsize; + + while (lo < hi) { + lo_order = lo != pivot && in_order(lo, pivot, user); + hi_order = hi != pivot && in_order(pivot, hi, user); + if (!lo_order && !hi_order) { + if (lo == pivot) pivot = hi; + else if (hi == pivot) pivot = lo; + dvec_quick_sort_swap(lo, hi, tmp, dsize); + modified = true; + } + if (lo_order) lo += dsize; + if (hi_order) hi -= dsize; + } + + if (start != pivot) { + *(uint8_t **)dvec_push(&stack) = start; + *(uint8_t **)dvec_push(&stack) = pivot - dsize; + } + + if (end != pivot) { + *(uint8_t **)dvec_push(&stack) = pivot + dsize; + *(uint8_t **)dvec_push(&stack) = end; + } + } + + dvec_deinit(&stack); + + return modified ? DVEC_MODIFIED : DVEC_OK; +} + +static bool +dvec_quick_sort_ex_order(const void *p1, const void *p2, const void *user) +{ + const struct sort_order_user_proxy *user_proxy = user; + const void *d1 = *(void **)p1, *d2 = *(void **)p2; + + return user_proxy->order_fn(d1, d2, user_proxy->user); +} + +int +dvec_quick_sort_ex(struct dvec *dvec, const struct allocator *allocator, + void *tmp, bool reverse, dvec_sort_order_fn in_order, const void *user) +{ + const struct sort_order_user_proxy user_proxy = { + .order_fn = in_order, + .user = user + }; + struct dvec ptrmap; + void *p, **pp, **dst, **src; + size_t dsize; + int rc; + + if (!dvec->len) return DVEC_OK; + + dsize = dvec->dsize; + + rc = dvec_init(&ptrmap, sizeof(void *), dvec->len, allocator); + if (rc) return rc; + + for (DVEC_ITER(dvec, p)) + *(void **)dvec_push(&ptrmap) = p; + + rc = dvec_quick_sort(&ptrmap, allocator, tmp, reverse, + dvec_quick_sort_ex_order, &user_proxy); + if (rc) return rc; + + for (DVEC_ITER(&ptrmap, pp)) { + if (!*pp || dvec_idx(&ptrmap, pp) == dvec_idx(dvec, *pp)) + continue; + dst = pp; + memcpy(tmp, *dst, dsize); + while (1) { + src = dvec_at(&ptrmap, dvec_idx(dvec, *dst)); + if (!*src) break; + memcpy(*dst, *src, dsize); + *dst = NULL; + dst = src; + } + memcpy(*dst, tmp, dsize); + } + + rc = dvec_deinit(&ptrmap); + if (rc) return rc; + + return DVEC_OK; +} + +ssize_t +dvec_binary_search(struct dvec *dvec, dvec_search_cmp_fn search_cmp, + void *user, ssize_t *lower, ssize_t *higher) +{ + size_t min, max, pos; + int rc; + + min = 0; + max = dvec->len; + if (lower) *lower = -1; + if (higher) *higher = -1; + + while (min < max) { + pos = min + (max - min) / 2; + rc = search_cmp(dvec_at(dvec, pos), user); + if (!rc) { + if (lower && pos > 0) + *lower = (ssize_t) pos - 1; + if (higher && pos < dvec->len - 1) + *higher = (ssize_t) pos + 1; + return (ssize_t) pos; + } else if (rc > 0) { + if (pos + 1 == max) { + if (lower) *lower = (ssize_t) min; + if (higher && min < dvec->len - 1) + *higher = (ssize_t) min + 1; + break; + } + min = pos + 1; + } else { + if (min == pos) { + if (higher) *higher = (ssize_t) min; + if (lower && min > 0) + *lower = (ssize_t) min - 1; + break; + } + max = pos; + } + } + + return -1; +} diff --git a/lib/libdvec/src/test.c b/lib/libdvec/src/test.c new file mode 100644 index 0000000..af0ee24 --- /dev/null +++ b/lib/libdvec/src/test.c @@ -0,0 +1,77 @@ +#include "allocator.h" +#include "dvec.h" + +#include <err.h> +#include <stdbool.h> +#include <stdio.h> +#include <string.h> +#include <stdlib.h> + +static const char *dvec_err[] = { + DVEC_STRERR_INIT +}; + +bool +str_sort_order(const void *p1, const void *p2, const void *user) +{ + const char *s1 = *(const char **)p1; + const char *s2 = *(const char **)p2; + + return strcmp(s1, s2) <= 0; +} + +int +str_search(const void *p, const void *user) +{ + const char *str = *(const char **)p, *cmp = user; + + return strcmp(cmp, str); +} + +int +main(int argc, const char **argv) +{ + struct dvec dvec, *fused; + ssize_t below, above, on; + const char **val, *tmp; + int i, rc; + + rc = dvec_init(&dvec, sizeof(const char *), 16, &stdlib_heap_allocator); + if (rc) DVEC_ERR(dvec_err, rc); + + for (i = 1; i < argc; i++) { + rc = dvec_add_back(&dvec, 1); + if (rc) DVEC_ERR(dvec_err, rc); + val = dvec_back(&dvec); + *val = argv[i]; + } + + rc = dvec_quick_sort_ex(&dvec, &stdlib_heap_allocator, &tmp, + false, str_sort_order, NULL); + if (rc < 0) DVEC_ERR(dvec_err, rc); + + on = dvec_binary_search(&dvec, str_search, "abc", &below, &above); + + for (DVEC_ITER(&dvec, val)) + printf("%s\n", *val); + + printf("dvec len: %lu\n", dvec.len); + + printf("\n"); + printf("below: %li\n", below); + printf("on: %li\n", on); + printf("above: %li\n", above); + printf("\n"); + + fused = dvec_alloc_fused(sizeof(const char *), 0, + &stdlib_heap_allocator, &rc); + if (!fused) DVEC_ERR(dvec_err, rc); + + printf("fused: %p %p (+%li)\n", (void *) fused, + fused->data, fused->data - (uint8_t *) fused); + + rc = dvec_free(fused); + if (rc) DVEC_ERR(dvec_err, rc); + + dvec_deinit(&dvec); +} 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); +} diff --git a/lib/libtabular b/lib/libtabular deleted file mode 160000 -Subproject f518cb2853fa164b4c4d3871da464c8f54fc600 diff --git a/lib/libtabular/.gitignore b/lib/libtabular/.gitignore new file mode 100644 index 0000000..65056fc --- /dev/null +++ b/lib/libtabular/.gitignore @@ -0,0 +1,8 @@ +compile_commands.json +build +build.rmk +.cache +.gdb_history +vgcore* +/.subgit +/.subrepo diff --git a/lib/libtabular/.gitmodules b/lib/libtabular/.gitmodules new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/lib/libtabular/.gitmodules diff --git a/lib/libtabular/.subgitrc b/lib/libtabular/.subgitrc new file mode 100644 index 0000000..0ec8d87 --- /dev/null +++ b/lib/libtabular/.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]='fd51196ac2d1bf1c34c8578146ef1bc66c1c8ec4' + diff --git a/lib/libtabular/build.jst b/lib/libtabular/build.jst new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/lib/libtabular/build.jst diff --git a/lib/libtabular/build.rmk.tmpl b/lib/libtabular/build.rmk.tmpl new file mode 100644 index 0000000..5f874ed --- /dev/null +++ b/lib/libtabular/build.rmk.tmpl @@ -0,0 +1,70 @@ +#default PREFIX /usr/local +#default INCLDIR /include +#default LIBDIR /lib +#default CC gcc + +#ifdef LIBTABULAR_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} #{LIBTABULAR_EXTRA_CFLAGS} + +rule liba + #{CC} -o $out.tmp.o $in $cflags -r + objcopy --keep-global-symbols=libtabular.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 libtabular.lds + +rule cc + #{CC} -o $out $in $cflags + +rule mkdir + mkdir $out + +target build + mkdir + +target lib/liballoc/build/liballoc.a + rmk lib/liballoc + +target build/libtabular.a + liba src/tabular.c src/util.c lib/liballoc/build/liballoc.a + | build include/tabular.h libtabular.api + +target build/libtabular.so + libso src/tabular.c src/util.c + | build include/tabular.h libtabular.lds + +target build/test + cc src/test.c build/libtabular.a lib/liballoc/build/liballoc.a | build + +command clean + rm -rf build + +command cleanall + rmk clean + rmk -C lib/liballoc cleanall + +command install + install -m644 include/tabular.h -t "#{DESTDIR}#{PREFIX}#{INCLDIR}" + install -m755 build/libtabular.a -t "#{DESTDIR}#{PREFIX}#{LIBDIR}" + install -m755 build/libtabular.so -t "#{DESTDIR}#{PREFIX}#{LIBDIR}" + +command uninstall + rm -f "#{DESTDIR}#{PREFIX}#{INCLDIR}/tabular.h" + rm -f "#{DESTDIR}#{PREFIX}#{LIBDIR}/libtabular.a" + rm -f "#{DESTDIR}#{PREFIX}#{LIBDIR}/libtabular.so" + +command all + rmk build/libtabular.a build/libtabular.so build/test diff --git a/lib/libtabular/configure b/lib/libtabular/configure new file mode 100755 index 0000000..b4dd05d --- /dev/null +++ b/lib/libtabular/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/libtabular/include/tabular.h b/lib/libtabular/include/tabular.h new file mode 100644 index 0000000..b3d1c54 --- /dev/null +++ b/lib/libtabular/include/tabular.h @@ -0,0 +1,133 @@ +#pragma once + +#include "allocator.h" + +#include <wchar.h> +#include <stdio.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> +#include <wctype.h> + +enum { + TABULAR_ALIGN_LEFT, + TABULAR_ALIGN_CENTER, + TABULAR_ALIGN_RIGHT +}; + +enum { + TABULAR_TRUNC, + TABULAR_WRAP, + TABULAR_WRAP_WORDAWARE +}; + +enum { + TABULAR_ENTRY_HIDDEN, + TABULAR_ENTRY_STR_SET, + TABULAR_ENTRY_HIDDEN_SET, +}; + +struct tabular_user { + union { + void *ptr; + size_t id; + }; +}; + +struct tabular_entry { + char *str; + uint32_t flags; + uint32_t ulen; +}; + +struct tabular_row { + struct tabular_user user; + struct tabular_entry *entries; + struct tabular_row *next; +}; + +struct tabular_col { + struct tabular_user user; + + /* column name displayed in header */ + const char *name; + + /* create str entry to display from user objects */ + char *(*to_str)(const struct tabular_user *user_row, + const struct tabular_user *user_col); + + /* only show content if atleast one row is not 'hidden' */ + bool (*is_hidden)(const struct tabular_user *user_row, + const struct tabular_user *user_col); + + /* size restrictions */ + size_t minwidth, maxwidth; + + /* whitespace padding */ + size_t lpad, rpad; + + /* text alignment */ + int align; + + /* content packing strategy */ + int strategy; + + /* omiting column due to col contraints disallowed */ + bool essential; + + /* reducing length due to col contraints allowed */ + bool squashable; +}; + +struct tabular_cfg { + struct tabular_user user; + + const struct tabular_col *columns; + size_t column_count; + + /* color mode: 1, 16, 256 */ + int colors; + + /* fit rows to output size */ + bool fit_rows; + + /* amount of available lines to skip */ + size_t skip_lines; + + /* output dimensions */ + size_t outw, outh; + + /* entry separators */ + const char *hsep, *vsep, *xsep; + + /* total lpad, rpad */ + size_t lpad, rpad; + + /* lazy load rows */ + struct tabular_row *(*row_gen)(const struct tabular_user *user); + + /* style printing hook for header, separators and content */ + bool (*print_style)(FILE *file, const struct tabular_cfg *cfg, + const struct tabular_row *row, const struct tabular_col *col); + + const struct allocator *allocator; +}; + +struct tabular_stats { + bool rows_truncated; + bool cols_truncated; + size_t rows_displayed; + size_t lines_used; +}; + +int tabular_format(FILE *file, const struct tabular_cfg *cfg, + struct tabular_stats *stat, struct tabular_row **rows); + +void tabular_load_row_entry_hidden(const struct tabular_cfg *cfg, + struct tabular_row *row, size_t col); +void tabular_load_row_entry_str(const struct tabular_cfg *cfg, + struct tabular_row *row, size_t col); + +struct tabular_row *tabular_alloc_row(const struct tabular_cfg *cfg, + int *error, struct tabular_user user); +int tabular_free_rows(const struct tabular_cfg *cfg, struct tabular_row *rows); diff --git a/lib/libtabular/lib/liballoc/.gitignore b/lib/libtabular/lib/liballoc/.gitignore new file mode 100644 index 0000000..b6a670a --- /dev/null +++ b/lib/libtabular/lib/liballoc/.gitignore @@ -0,0 +1,7 @@ +compile_commands.json +build +build.rmk +.cache +vgcore* +.gdb_history +test diff --git a/lib/libtabular/lib/liballoc/LICENSE b/lib/libtabular/lib/liballoc/LICENSE new file mode 100644 index 0000000..361f116 --- /dev/null +++ b/lib/libtabular/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/libtabular/lib/liballoc/Makefile b/lib/libtabular/lib/liballoc/Makefile new file mode 100644 index 0000000..dab8818 --- /dev/null +++ b/lib/libtabular/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/libtabular/lib/liballoc/build.jst b/lib/libtabular/lib/liballoc/build.jst new file mode 100644 index 0000000..f590d49 --- /dev/null +++ b/lib/libtabular/lib/liballoc/build.jst @@ -0,0 +1,51 @@ + + +cflags = -Wunused-function -Wunused-variable -Wconversion -Wformat + -I include -O2 + +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 "/usr/local/lib" + install -m755 build/liballoc.so -t "/usr/local/lib" + install -m644 include/allocator.h -t "/usr/local/include" + +command uninstall + rm -f "/usr/local/lib/liballoc.a" + rm -f "/usr/local/lib/liballoc.so" + rm -f "/usr/local/include/allocator.h" + +command all + just build/liballoc.a build/liballoc.so build/test + diff --git a/lib/libtabular/lib/liballoc/build.rmk.tmpl b/lib/libtabular/lib/liballoc/build.rmk.tmpl new file mode 100644 index 0000000..410749d --- /dev/null +++ b/lib/libtabular/lib/liballoc/build.rmk.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/libtabular/lib/liballoc/common.mk b/lib/libtabular/lib/liballoc/common.mk new file mode 100644 index 0000000..fe00d79 --- /dev/null +++ b/lib/libtabular/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/libtabular/lib/liballoc/configure b/lib/libtabular/lib/liballoc/configure new file mode 100755 index 0000000..16d5220 --- /dev/null +++ b/lib/libtabular/lib/liballoc/configure @@ -0,0 +1,5 @@ +#!/bin/sh + +set -ex + +tmpl "$@" build.rmk.tmpl > build.rmk diff --git a/lib/libtabular/lib/liballoc/include/allocator.h b/lib/libtabular/lib/liballoc/include/allocator.h new file mode 100644 index 0000000..fc9a13d --- /dev/null +++ b/lib/libtabular/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/libtabular/lib/liballoc/liballoc.api b/lib/libtabular/lib/liballoc/liballoc.api new file mode 100644 index 0000000..e875b2b --- /dev/null +++ b/lib/libtabular/lib/liballoc/liballoc.api @@ -0,0 +1,4 @@ +strict_allocator_init + +stdlib_heap_allocator +stdlib_strict_heap_allocator diff --git a/lib/libtabular/lib/liballoc/liballoc.lds b/lib/libtabular/lib/liballoc/liballoc.lds new file mode 100644 index 0000000..07e5fca --- /dev/null +++ b/lib/libtabular/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/libtabular/lib/liballoc/src/allocator.c b/lib/libtabular/lib/liballoc/src/allocator.c new file mode 100644 index 0000000..eb6bc6d --- /dev/null +++ b/lib/libtabular/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/libtabular/lib/liballoc/src/test.c b/lib/libtabular/lib/liballoc/src/test.c new file mode 100644 index 0000000..7b3ee44 --- /dev/null +++ b/lib/libtabular/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/libtabular/libtabular.api b/lib/libtabular/libtabular.api new file mode 100644 index 0000000..79ca84a --- /dev/null +++ b/lib/libtabular/libtabular.api @@ -0,0 +1,7 @@ +tabular_format + +tabular_load_row_entry_str +tabular_load_row_entry_hidden + +tabular_alloc_row +tabular_free_rows diff --git a/lib/libtabular/libtabular.lds b/lib/libtabular/libtabular.lds new file mode 100644 index 0000000..5b1a674 --- /dev/null +++ b/lib/libtabular/libtabular.lds @@ -0,0 +1,7 @@ +LIBTABULAR_1.0 { + global: + tabular_format; + tabular_alloc_row; + tabular_free_rows; + local: *; +}; diff --git a/lib/libtabular/src/tabular.c b/lib/libtabular/src/tabular.c new file mode 100644 index 0000000..88fab17 --- /dev/null +++ b/lib/libtabular/src/tabular.c @@ -0,0 +1,695 @@ +#define _XOPEN_SOURCE + +#include "tabular.h" +#include "util.h" + +#include <sys/ioctl.h> +#include <wchar.h> +#include <errno.h> +#include <unistd.h> +#include <stdio.h> +#include <string.h> +#include <stdint.h> +#include <stddef.h> + +#define BIT(i) (1U << (i)) + +struct col_state { + size_t width; + size_t written; + size_t maxlen; + size_t lpad, rpad; + bool hidden; +}; + +struct fmt_state { + struct col_state *columns; + size_t column_count; + + size_t hseplen; + size_t vseplen; + size_t xseplen; + size_t mseplen; + + size_t line_limit; + size_t row_limit; + + bool header_line; +}; + +static void calc_word_aware(struct tabular_entry *entry, size_t maxwidth, + size_t *offset, size_t *width, size_t *lines); +static size_t recalc_col_word_aware(const struct tabular_cfg *cfg, + struct tabular_row *rows, size_t limit, + size_t col, size_t maxwidth); +static size_t calc_row_width(struct fmt_state *fmt); +static size_t calc_output_lines(const struct tabular_cfg *cfg, + struct fmt_state *fmt, struct tabular_row *rows, size_t limit); +static bool recalc_cols(const struct tabular_cfg *cfg, + struct tabular_stats *stats, struct fmt_state *fmt, + struct tabular_row *rows, size_t limit); + +static int calc_params_row(const struct tabular_cfg *cfg, + struct tabular_stats *stats, struct tabular_row *rows, + struct tabular_row *row, struct fmt_state *fmt, size_t limit); +static int calc_params(const struct tabular_cfg *cfg, + struct tabular_stats *stat, struct tabular_row **rows, + struct fmt_state *fmt); + +static void output_header(FILE *file, const struct tabular_cfg *cfg, + struct tabular_stats *stat, const struct fmt_state *fmt); +static void output_row(FILE *file, const struct tabular_cfg *cfg, + struct tabular_stats *stat, const struct tabular_row *row, + struct fmt_state *fmt); +static int output_rows(FILE *file, const struct tabular_cfg *cfg, + struct tabular_stats *stats, struct tabular_row *rows, + struct fmt_state *fmt); + +const char * +calc_word_aware_line(const char *str, size_t maxwidth, + size_t *out_offset, size_t *out_width) +{ + const char *sep, *nstr; + size_t width, nwidth; + size_t offset, wlen; + + if (!str) { + if (out_offset) *out_offset = 0; + if (out_width) *out_width = 0; + return NULL; + } + + offset = strspn(str, " \v\t\r\n"); + str += offset; + + nstr = str; + nwidth = width = 0; + while (nwidth <= maxwidth) { + width = nwidth; + str = nstr; + if (!str) break; + sep = strchr(str, ' '); + if (!sep) { + wlen = u8strlen(str); + nstr = NULL; + } else { + wlen = u8strnlen(str, (size_t) (sep - str)); + nstr = sep + 1; + } + nwidth = width + (width > 0) + wlen; + } + + if (out_offset) *out_offset = offset; + if (out_width) { + /* single word > maxwidth */ + if (!width && nwidth) { + *out_width = maxwidth; + str = nstr; /* skip single word */ + } else { + *out_width = width; + } + } + + return str; +} + +void +calc_word_aware(struct tabular_entry *entry, size_t maxwidth, + size_t *out_offset, size_t *out_width, size_t *out_lines) +{ + const char *str; + size_t width, mwidth; + size_t lines; + + if (out_offset) *out_offset = 0; + + lines = 0; + mwidth = 0; + str = entry->str; + while (str) { + str = calc_word_aware_line(str, maxwidth, + str == entry->str ? out_offset : NULL, &width); + lines++; + mwidth = MAX(mwidth, width); + } + + if (out_width) *out_width = mwidth; + if (out_lines) *out_lines = lines; +} + +size_t +recalc_col_word_aware(const struct tabular_cfg *cfg, + struct tabular_row *rows, size_t limit, size_t col, + size_t maxwidth) +{ + size_t off, wwidth, max_wwidth, rowcnt; + struct tabular_row *row; + + max_wwidth = cfg->columns[col].minwidth; + + rowcnt = 0; + for (row = rows; row && rowcnt < limit; row = row->next) { + calc_word_aware(&row->entries[col], + maxwidth, &off, &wwidth, NULL); + max_wwidth = MAX(max_wwidth, wwidth); + rowcnt += 1; + } + + return max_wwidth; +} + +size_t +calc_row_width(struct fmt_state *fmt) +{ + size_t sum, i; + + sum = 0; + for (i = 0; i < fmt->column_count; i++) { + if (fmt->columns[i].hidden) continue; + sum += fmt->columns[i].width + (sum ? fmt->hseplen : 0); + } + + return sum; +} + +size_t +calc_output_lines(const struct tabular_cfg *cfg, struct fmt_state *fmt, + struct tabular_row *rows, size_t limit) +{ + struct tabular_row *row; + size_t row_index, row_lines; + size_t entry_lines; + size_t lines, i; + size_t width; + + lines = 0; + row_index = 0; + for (row = rows; row; row = row->next) { + if (row_index == limit) break; + + row_lines = 0; + for (i = 0; i < cfg->column_count; i++) { + if (fmt->columns[i].hidden) continue; + width = fmt->columns[i].width + - fmt->columns[i].lpad - fmt->columns[i].rpad; + switch (cfg->columns[i].strategy) { + case TABULAR_TRUNC: + entry_lines = 1; + break; + case TABULAR_WRAP: + entry_lines = CEILDIV(row->entries[i].ulen, width); + break; + case TABULAR_WRAP_WORDAWARE: + calc_word_aware(&row->entries[i], + width, NULL, NULL, &entry_lines); + break; + } + row_lines = MAX(row_lines, entry_lines); + } + lines += row_lines; + + row_index += 1; + } + + return lines; +} + +bool +recalc_cols(const struct tabular_cfg *cfg, struct tabular_stats *stats, + struct fmt_state *fmt, struct tabular_row *rows, size_t limit) +{ + size_t width, fullwidth, remaining; + ssize_t i; + + fullwidth = cfg->outw - cfg->lpad - cfg->rpad; + + /* reset widths to minimum requirement */ + for (i = 0; i < cfg->column_count; i++) { + if (fmt->columns[i].hidden) continue; + if (cfg->columns[i].squashable) { + fmt->columns[i].width = cfg->columns[i].minwidth; + } else { + width = MIN(fmt->columns[i].maxlen, + cfg->columns[i].maxwidth - cfg->columns[i].lpad + - cfg->columns[i].rpad); + if (cfg->columns[i].strategy == TABULAR_WRAP_WORDAWARE) + width = recalc_col_word_aware(cfg, rows, + limit, (size_t) i, width); + fmt->columns[i].width = width + cfg->columns[i].lpad + + cfg->columns[i].rpad; + } + } + + /* could not fit all necessary columns at minimum width */ + width = calc_row_width(fmt); + while (width > fullwidth) { + /* remove non-essential columns */ + for (i = ((ssize_t) cfg->column_count) - 1; i >= 0; i--) { + if (!cfg->columns[i].essential + && !fmt->columns[i].hidden) { + fmt->columns[i].hidden = true; + break; + } + } + + /* failed to remove any more */ + if (i < 0) return false; + + stats->cols_truncated = true; + width = calc_row_width(fmt); + } + + /* redistribute excess width to columns, left to right */ + remaining = fullwidth - width; + for (i = 0; remaining > 0 && i < cfg->column_count; i++) { + if (fmt->columns[i].hidden) continue; + if (!cfg->columns[i].squashable) continue; + width = MIN(fmt->columns[i].maxlen, cfg->columns[i].maxwidth + - fmt->columns[i].lpad - fmt->columns[i].rpad); + width = MIN(width, fmt->columns[i].width + remaining + - fmt->columns[i].lpad - fmt->columns[i].rpad); + if (cfg->columns[i].strategy == TABULAR_WRAP_WORDAWARE) + width = recalc_col_word_aware(cfg, rows, + limit, (size_t) i, width); + width = MAX(width + fmt->columns[i].lpad + fmt->columns[i].rpad, + fmt->columns[i].width); + remaining -= width - fmt->columns[i].width; + fmt->columns[i].width = width; + } + + return true; +} + +int +calc_params_row(const struct tabular_cfg *cfg, struct tabular_stats *stats, + struct tabular_row *rows, struct tabular_row *row, + struct fmt_state *fmt, size_t limit) +{ + struct colinfo *copy; + size_t i, height; + int rc; + + /* make copy of current width in case the next row does not fit */ + copy = cfg->allocator->alloc(cfg->allocator, + sizeof(struct col_state) * cfg->column_count, &rc); + if (!copy) return -rc; + memcpy(copy, fmt->columns, sizeof(struct col_state) * cfg->column_count); + + /* unhide cols */ + for (i = 0; i < cfg->column_count; i++) { + tabular_load_row_entry_hidden(cfg, row, i); + if (fmt->columns[i].hidden) { + fmt->columns[i].hidden = + (row->entries[i].flags & BIT(TABULAR_ENTRY_HIDDEN)); + } + if (fmt->columns[i].hidden) continue; + } + + /* update maxlen for visible cols */ + for (i = 0; i < cfg->column_count; i++) { + tabular_load_row_entry_str(cfg, row, i); + fmt->columns[i].maxlen = MAX(fmt->columns[i].maxlen, + row->entries[i].ulen); + } + + /* recalc column sizes to fit new column */ + if (!recalc_cols(cfg, stats, fmt, rows, limit)) + goto undo; + + height = calc_output_lines(cfg, fmt, rows, limit); + + /* check the line limit if applicable */ + if (fmt->line_limit > 0 && height > fmt->line_limit) + goto undo; + + cfg->allocator->free(cfg->allocator, copy); + + return 0; + +undo: + memcpy(fmt->columns, copy, sizeof(struct col_state) * fmt->column_count); + cfg->allocator->free(cfg->allocator, copy); + + return 1; +} + +int +calc_params(const struct tabular_cfg *cfg, struct tabular_stats *stats, + struct tabular_row **rows, struct fmt_state *fmt) +{ + struct tabular_row **row; + ssize_t first, last; + size_t i; + int rc; + + fmt->header_line = ((cfg->vsep != NULL && *cfg->vsep) + && (cfg->xsep != NULL && *cfg->xsep)); + + fmt->line_limit = 0; + if (cfg->fit_rows) { + fmt->line_limit = MAX(0, cfg->outh + - cfg->skip_lines - 1 - fmt->header_line); + } + + fmt->hseplen = u8strlen(cfg->hsep); + fmt->vseplen = u8strlen(cfg->vsep); + fmt->xseplen = u8strlen(cfg->xsep); + fmt->mseplen = MAX(fmt->hseplen, fmt->xseplen); + + fmt->column_count = cfg->column_count; + fmt->columns = cfg->allocator->alloc(cfg->allocator, + fmt->column_count * sizeof(struct col_state), &rc); + if (!fmt->columns) return -rc; + + for (i = 0; i < cfg->column_count; i++) { + fmt->columns[i].lpad = cfg->columns[i].lpad; + fmt->columns[i].rpad = cfg->columns[i].rpad; + fmt->columns[i].hidden = true; + fmt->columns[i].width = cfg->columns[i].minwidth; + fmt->columns[i].maxlen = u8strlen(cfg->columns[i].name) + + fmt->columns[i].lpad + fmt->columns[i].rpad; + if (fmt->columns[i].maxlen > cfg->columns[i].minwidth) + return 1; + fmt->columns[i].written = 0; + } + + fmt->row_limit = 0; + + if (!*rows && cfg->row_gen) *rows = cfg->row_gen(&cfg->user); + if (!*rows) return 0; + + if (!recalc_cols(cfg, stats, fmt, *rows, 0)) { + stats->cols_truncated = true; + stats->rows_truncated = true; + return 0; + } + + for (row = rows; ; row = &(*row)->next) { + if (!*row && cfg->row_gen) *row = cfg->row_gen(&cfg->user); + if (!*row) break; + rc = calc_params_row(cfg, stats, *rows, + *row, fmt, fmt->row_limit + 1); + if (rc < 0) return rc; + if (rc > 0) { + stats->rows_truncated = true; + break; + } + fmt->row_limit++; + } + + first = last = -1; + for (i = 0; i < cfg->column_count; i++) { + if (fmt->columns[i].hidden) continue; + if (first < 0) first = (ssize_t) i; + last = (ssize_t) i; + } + + if (first >= 0 && last >= 0) { + fmt->columns[first].lpad += cfg->lpad; + fmt->columns[first].width += cfg->lpad; + fmt->columns[last].rpad += cfg->rpad; + fmt->columns[last].width += cfg->rpad; + } + + return 0; +} + +void +output_header(FILE *file, const struct tabular_cfg *cfg, + struct tabular_stats *stats, const struct fmt_state *fmt) +{ + size_t i, k, width; + bool dirty, first; + + first = true; + for (i = 0; i < cfg->column_count; i++) { + if (fmt->columns[i].hidden) continue; + if (!first) { + dirty = cfg->print_style(file, cfg, NULL, NULL); + fprintf(file, "%s%*.s", cfg->hsep, + (int) (fmt->mseplen - fmt->hseplen), ""); + if (dirty) fprintf(file, "\x1b[0m"); + } + first = false; + + width = fmt->columns[i].width + - fmt->columns[i].lpad - fmt->columns[i].rpad; + + dirty = cfg->print_style(file, cfg, + NULL, &cfg->columns[i]); + print_pad(file, fmt->columns[i].lpad); + print_left(file, cfg->columns[i].name, width, width); + print_pad(file, fmt->columns[i].rpad); + if (dirty) fprintf(file, "\x1b[0m"); + } + + fprintf(file, "\n"); + stats->lines_used += 1; + + if (fmt->header_line) { + first = true; + dirty = cfg->print_style(file, cfg, NULL, NULL); + for (i = 0; i < cfg->column_count; i++) { + if (fmt->columns[i].hidden) continue; + if (!first) { + fprintf(file, "%s%*.s", cfg->xsep, + (int) (fmt->mseplen - fmt->xseplen), ""); + } + for (k = 0; k < fmt->columns[i].width; k++) + fprintf(file, "%s", cfg->vsep); + first = false; + } + if (dirty) fprintf(file, "\x1b[0m"); + fprintf(file, "\n"); + stats->lines_used += 1; + } +} + +void +output_row(FILE *file, const struct tabular_cfg *cfg, + struct tabular_stats *stat, const struct tabular_row *row, + struct fmt_state *fmt) +{ + size_t wwidth, padwidth, outlen; + size_t i, off, width; + bool first, done, dirty; + char *entry; + + for (i = 0; i < cfg->column_count; i++) { + fmt->columns[i].written = 0; + + if (cfg->columns[i].strategy == TABULAR_TRUNC) { + width = fmt->columns[i].width + - fmt->columns[i].lpad - fmt->columns[i].rpad; + if (row->entries[i].ulen > width) { + width = u8rawlen(row->entries[i].str, width - 2); + row->entries[i].str[width] = '.'; + row->entries[i].str[width+1] = '.'; + row->entries[i].str[width+2] = '\0'; + } + } + } + + do { + done = true; + first = true; + for (i = 0; i < cfg->column_count; i++) { + if (fmt->columns[i].hidden) continue; + + if (!first) { + dirty = cfg->print_style(file, cfg, NULL, NULL); + fprintf(file, "%s", cfg->hsep); + if (dirty) fprintf(file, "\x1b[0m"); + } + first = false; + + if (!row->entries[i].str) { + print_pad(file, fmt->columns[i].width); + continue; + } + + entry = row->entries[i].str + fmt->columns[i].written; + + dirty = cfg->print_style(file, cfg, row, &cfg->columns[i]); + + off = 0; + width = fmt->columns[i].width + - fmt->columns[i].lpad - fmt->columns[i].rpad; + padwidth = width; + if (cfg->columns[i].strategy == TABULAR_WRAP_WORDAWARE) { + calc_word_aware_line(entry, width, &off, &wwidth); + entry += off; + width = wwidth; + } + + print_pad(file, fmt->columns[i].lpad); + if (cfg->columns[i].align == TABULAR_ALIGN_LEFT) { + print_left(file, entry, width, padwidth); + } else if (cfg->columns[i].align == TABULAR_ALIGN_RIGHT) { + print_right(file, entry, width, padwidth); + } else { + print_center(file, entry, width, padwidth); + } + print_pad(file, fmt->columns[i].rpad); + + if (dirty) fprintf(file, "\x1b[0m"); + + outlen = MIN(u8strlen(entry), width + off); + fmt->columns[i].written += u8rawlen(entry, outlen); + + /* check if anything other than whitespace left */ + entry += u8rawlen(entry, outlen); + if (strspn(entry, " \t\v\r\n") != u8strlen(entry)) + done = false; + } + fprintf(file, "\n"); + stat->lines_used += 1; + } while (!done); + + stat->rows_displayed += 1; +} + +int +output_rows(FILE *file, const struct tabular_cfg *cfg, + struct tabular_stats *stats, struct tabular_row *rows, + struct fmt_state *fmt) +{ + struct tabular_row *row; + size_t count; + + if (fmt->row_limit == 0) return 0; + + output_header(file, cfg, stats, fmt); + + count = 0; + for (row = rows; row; row = row->next) { + if (count == fmt->row_limit) + break; + output_row(file, cfg, stats, row, fmt); + count += 1; + } + + return 0; +} + +int +tabular_format(FILE *file, const struct tabular_cfg *cfg, + struct tabular_stats *stats, struct tabular_row **rows) +{ + struct fmt_state fmt; + size_t i; + int rc; + + stats->lines_used = 0; + stats->rows_displayed = 0; + stats->rows_truncated = false; + stats->cols_truncated = false; + + if (!rows) return 1; + + if (!cfg->column_count) return 0; + + for (i = 0; i < cfg->column_count; i++) { + if (cfg->columns[i].minwidth > cfg->columns[i].maxwidth) + return 1; + if (cfg->columns[i].lpad + cfg->columns[i].rpad + >= cfg->columns[i].minwidth) + return 1; + if (cfg->columns[i].strategy != TABULAR_TRUNC + && cfg->columns[i].strategy != TABULAR_WRAP + && cfg->columns[i].strategy != TABULAR_WRAP_WORDAWARE) + return 1; + } + + rc = calc_params(cfg, stats, rows, &fmt); + if (rc) return rc; + + rc = output_rows(file, cfg, stats, *rows, &fmt); + if (rc) return rc; + + rc = cfg->allocator->free(cfg->allocator, fmt.columns); + if (rc) return -rc; + + return 0; +} + +struct tabular_row * +tabular_alloc_row(const struct tabular_cfg *cfg, + int *rc, struct tabular_user user) +{ + struct tabular_row *row; + + row = cfg->allocator->alloc(cfg->allocator, + sizeof(struct tabular_row), rc); + if (!row && rc) *rc = -*rc; + if (!row) return NULL; + + row->next = NULL; + row->user = user; + row->entries = cfg->allocator->alloc(cfg->allocator, + sizeof(struct tabular_entry) * cfg->column_count, rc); + if (!row->entries && rc) *rc = -*rc; + if (!row->entries) return NULL; + memset(row->entries, 0, sizeof(struct tabular_entry) * cfg->column_count); + + return row; +} + +int +tabular_free_rows(const struct tabular_cfg *cfg, struct tabular_row *rows) +{ + struct tabular_row *iter, *next; + size_t i; + int rc; + + for (iter = rows; iter; iter = next) { + next = iter->next; + for (i = 0; i < cfg->column_count; i++) { + rc = cfg->allocator->free(cfg->allocator, + iter->entries[i].str); + if (rc) return -rc; + } + rc = cfg->allocator->free(cfg->allocator, iter->entries); + if (rc) return -rc; + rc = cfg->allocator->free(cfg->allocator, iter); + if (rc) return -rc; + } + + return 0; +} + +void +tabular_load_row_entry_hidden(const struct tabular_cfg *cfg, + struct tabular_row *row, size_t col) +{ + bool hidden; + + if (row->entries[col].flags & BIT(TABULAR_ENTRY_HIDDEN_SET)) return; + + if (cfg->columns[col].is_hidden) { + hidden = cfg->columns[col].is_hidden( + &row->user, &cfg->columns[col].user); + } else { + hidden = false; + } + + if (hidden) { + row->entries[col].flags |= BIT(TABULAR_ENTRY_HIDDEN); + } else { + row->entries[col].flags &= ~BIT(TABULAR_ENTRY_HIDDEN); + } + + row->entries[col].flags |= BIT(TABULAR_ENTRY_HIDDEN_SET); +} + +void +tabular_load_row_entry_str(const struct tabular_cfg *cfg, + struct tabular_row *row, size_t col) +{ + if (row->entries[col].flags & BIT(TABULAR_ENTRY_STR_SET)) return; + + row->entries[col].str = cfg->columns[col].to_str( + &row->user, &cfg->columns[col].user); + row->entries[col].ulen = (uint32_t) u8strlen(row->entries[col].str); + row->entries[col].flags |= BIT(TABULAR_ENTRY_STR_SET); +} diff --git a/lib/libtabular/src/test.c b/lib/libtabular/src/test.c new file mode 100644 index 0000000..f33fab1 --- /dev/null +++ b/lib/libtabular/src/test.c @@ -0,0 +1,154 @@ +#include "tabular.h" +#include "allocator.h" + +#include <sys/ioctl.h> +#include <err.h> +#include <string.h> +#include <stdbool.h> +#include <stdio.h> + +#define ARRLEN(x) (sizeof(x)/sizeof(*(x))) + +bool print_style(FILE *file, const struct tabular_cfg *cfg, + const struct tabular_row *row, const struct tabular_col *col); + +char *col_pos_str(const struct tabular_user *row, const struct tabular_user *col); +bool col_pos_hidden(const struct tabular_user *user); + +char *col_name_str(const struct tabular_user *row, const struct tabular_user *col); +bool col_name_hidden(const struct tabular_user *user); + +static const char **argv = NULL; + +static struct tabular_col columns[] = { + { + .name = "Pos", + + .to_str = col_pos_str, + .is_hidden = NULL, + + .minwidth = 3, + .maxwidth = 3, + .lpad = 0, + .rpad = 0, + + .align = TABULAR_ALIGN_CENTER, + + .strategy = TABULAR_TRUNC, + .essential = true, + }, + { + .name = "Value", + + .to_str = col_name_str, + .is_hidden = NULL, + + .minwidth = 5, + .maxwidth = 80, + .lpad = 0, + .rpad = 0, + + .align = TABULAR_ALIGN_LEFT, + + .strategy = TABULAR_WRAP_WORDAWARE, + .essential = true, + }, +}; + +static struct tabular_cfg cfg = { + .colors = 256, + + .columns = columns, + .column_count = ARRLEN(columns), + + .fit_rows = true, + + .hsep = "│ ", + .vsep = "─", + .xsep = "┼─", + + .outw = 0, + .outh = 0, + + .lpad = 1, + .rpad = 1, + + .print_style = print_style, + + .skip_lines = 3, + + .allocator = &stdlib_heap_allocator +}; + +bool +print_style(FILE *file, const struct tabular_cfg *cfg, + const struct tabular_row *row, const struct tabular_col *col) +{ + if (cfg->colors == 256) { + if (!col) { /* separators */ + fprintf(file, "\x1b[90m"); + return true; + } else if (!row) { /* header */ + fprintf(file, "\x1b[1m"); + return true; + } else if (!strcmp(col->name, "Name")) { + fprintf(file, "\x1b[35m"); + return true; + } + } + + return false; +} + +char * +col_pos_str(const struct tabular_user *row, const struct tabular_user *col) +{ + char buf[16]; + + snprintf(buf, sizeof(buf), "%li", row->id); + + return strdup(buf); +} + +char * +col_name_str(const struct tabular_user *row, const struct tabular_user *col) +{ + return strdup(argv[row->id]); +} + +int +main(int argc, const char **_argv) +{ + struct tabular_row *rows, **end; + struct tabular_stats stats; + struct winsize ws; + int i, rc; + + argv = _argv; + + rc = ioctl(1, TIOCGWINSZ, &ws); + if (!rc) { + cfg.outw = ws.ws_col; + cfg.outh = ws.ws_row; + } else { + cfg.outw = 80; + cfg.outh = 26; + } + + rows = NULL; + end = &rows; + for (i = 0; i < argc; i++) { + *end = tabular_alloc_row(&cfg, &rc, + (struct tabular_user) { .id = (size_t) i }); + if (!*end) errx(1, "tabular_append_row %i", rc); + end = &(*end)->next; + } + + rc = tabular_format(stdout, &cfg, &stats, &rows); + if (rc) errx(1, "tabular_format %i", rc); + + printf("\n%lu lines, %lu rows\n", + stats.lines_used, stats.rows_displayed); + + tabular_free_rows(&cfg, rows); +} diff --git a/lib/libtabular/src/util.c b/lib/libtabular/src/util.c new file mode 100644 index 0000000..c2baa24 --- /dev/null +++ b/lib/libtabular/src/util.c @@ -0,0 +1,146 @@ +#include "util.h" + +#include <stddef.h> +#include <stdio.h> +#include <stdint.h> +#include <stdlib.h> + +size_t +u8strlen(const char *str) +{ + size_t i, len; + + if (!str) return 0; + + len = 0; + for (i = 0; str[i]; i++) { + if ((str[i] & 0xC0) != 0x80) + len += 1; + } + + return len; +} + +size_t +u8strnlen(const char *str, size_t max) +{ + size_t i, len; + + if (!str) return 0; + + len = 0; + for (i = 0; str[i] && i < max; i++) { + if ((str[i] & 0xC0) != 0x80) + len += 1; + } + + return len; +} + +size_t +u8rawlen(const char *str, size_t max) +{ + size_t i, len; + + if (!str) return 0; + + len = 0; + for (i = 0; str[i] && len < max; i++) + if ((str[i] & 0xC0) != 0x80) { + len += 1; + } + + return i; +} + +size_t +print_pad(FILE *file, size_t len) +{ + fprintf(file, "%*.s", (int) len, ""); + + return len; +} + +size_t +print_hex(FILE *file, const void *bytes, size_t len) +{ + size_t i; + + for (i = 0; i < len; i++) + fprintf(file, "%02X", *(uint8_t *)(bytes + i)); + + return len * 2; +} + +size_t +print_trunc(FILE *file, const char *str, size_t width) +{ + size_t len; + + len = u8strlen(str); + if (len > width && width >= 2) { + fprintf(file, "%*.*s..", (int) width - 2, (int) width - 2, str); + } else if (len > width&& width < 2) { + fprintf(file, "%*.*s", (int) width, (int) width, ".."); + } else { + fprintf(file, "%s", str); + } + + return MIN(len, width); +} + +size_t +print_left(FILE *file, const char *str, size_t width, size_t padwidth) +{ + size_t rawlen, u8len; + ssize_t ret; + + u8len = MIN(u8strlen(str), width); + rawlen = u8rawlen(str, u8len); + + /* make up for invisible bytes */ + padwidth += rawlen - u8len; + + ret = fprintf(file, "%-*.*s", (int) padwidth, (int) rawlen, str); + + return (size_t) MAX(0, ret); +} + +size_t +print_center(FILE *file, const char *str, size_t width, size_t padwidth) +{ + size_t u8len, rawlen; + size_t lpad, rpad; + ssize_t ret; + + u8len = MIN(width, u8strlen(str)); + rawlen = u8rawlen(str, u8len); + lpad = MAX(padwidth - u8len, 0) / 2; + rpad = MAX(padwidth - u8len - lpad, 0); + + /* make up for invisible bytes */ + rpad += rawlen - u8len; + + ret = fprintf(file, "%*s%*.*s%*s", (int) lpad, "", + (int) rawlen, (int) rawlen, str, (int) rpad, ""); + + return (size_t) MAX(0, ret); +} + +size_t +print_right(FILE *file, const char *str, size_t width, size_t padwidth) +{ + size_t rawlen, u8len; + ssize_t ret; + + u8len = MIN(width, u8strlen(str)); + rawlen = u8rawlen(str, u8len); + + /* make up for invisible bytes */ + padwidth += rawlen - u8len; + + ret = fprintf(file, "%*.*s", (int) padwidth, (int) rawlen, str); + + return (size_t) MAX(0, ret); +} + diff --git a/lib/libtabular/src/util.h b/lib/libtabular/src/util.h new file mode 100644 index 0000000..a325b18 --- /dev/null +++ b/lib/libtabular/src/util.h @@ -0,0 +1,25 @@ +#pragma once + +#include <stdio.h> +#include <stdlib.h> + +#define MIN(a, b) ((a) < (b) ? (a) : (b)) +#define MAX(a, b) ((a) < (b) ? (b) : (a)) +#define CEILDIV(a, b) (((a) / (b)) + !!((a) % (b))) + +size_t u8strlen(const char *str); +size_t u8strnlen(const char *str, size_t max); +size_t u8rawlen(const char *str, size_t max); + +size_t print_pad(FILE *file, size_t len); +size_t print_hex(FILE *file, const void *in, size_t len); + +size_t print_trunc(FILE *file, const char *str, size_t width); +size_t print_left(FILE *file, const char *str, + size_t width, size_t padwidth); +size_t print_center(FILE *file, const char *str, + size_t width, size_t padwidth); +size_t print_right(FILE *file, const char *str, + size_t width, size_t padwidth); + + |