commit 6431e7434c0b935c5825322d286d5721f1782d32
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 17 Feb 2023 19:41:59 +0100
Migration out of libvec
Diffstat:
7 files changed, 347 insertions(+), 0 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -0,0 +1,5 @@
+compile_commands.json
+build
+.cache
+vgcore*
+test
diff --git a/Makefile b/Makefile
@@ -0,0 +1,48 @@
+PREFIX ?= /usr/local
+INCLUDEDIR ?= /include
+LIBDIR ?= /lib
+
+CFLAGS = -I include -Wno-prototype -Wunused-function -Wunused-variable
+
+ifeq "$(LIBBITVEC_DEBUG)" "1"
+CFLAGS += -g
+endif
+
+ifeq "$(LIBBITVEC_ASSERT)" "1"
+CFLAGS += -DLIBBITVEC_ASSERT_ENABLE=1
+endif
+
+ifeq "$(LIBBITVEC_HANDLE_ERR)" "1"
+CFLAGS += -DLIBBITVEC_HANDLE_ERRS=1
+endif
+
+all: build/libbitvec.so build/libbitvec.a build/test
+
+clean:
+ rm -rf build
+
+build:
+ mkdir build
+
+build/libbitvec.a: src/bitvec.c include/bitvec.h | build
+ $(CC) -o build/tmp.o src/bitvec.c $(CFLAGS) -r
+ objcopy --keep-global-symbols=libbitvec.abi build/tmp.o build/fixed.o
+ ar rcs $@ build/fixed.o
+
+build/libbitvec.so: src/bitvec.c include/bitvec.h | build
+ $(CC) -o $@ src/bitvec.c -fPIC $(CFLAGS) -shared -Wl,-version-script libbitvec.lds
+
+build/test: src/test.c build/libbitvec.a
+ $(CC) -o $@ $^ $(CFLAGS)
+
+install:
+ install -m644 include/bitvec.h -t "$(DESTDIR)$(PREFIX)$(INCLUDEDIR)"
+ install -m755 build/libbitvec.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+ install -m755 build/libbitvec.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+
+uninstall:
+ rm -f "$(DESTDIR)$(PREFIX)$(INCLUDEDIR)/bitvec.h"
+ rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libbitvec.so"
+ rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libbitvec.a"
+
+.PHONY: all clean install uninstall
diff --git a/include/bitvec.h b/include/bitvec.h
@@ -0,0 +1,68 @@
+#pragma once
+
+#include <stdint.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+#ifdef LIBBITVEC_ASSERT_ENABLE
+
+#include <stdio.h>
+
+#define LIBBITVEC_ASSERT(x) libbitvec_assert((x), __FILE__, __LINE__, #x)
+
+static inline void libbitvec_assert(int cond,
+ const char *file, int line, const char *condstr)
+{
+ if (cond) return;
+
+ fprintf(stderr, "libvec: Assertion failed at %s:%i (%s)\n",
+ file, line, condstr);
+ abort();
+}
+
+#else
+#define LIBBITVEC_ASSERT(x)
+#endif
+
+#ifdef LIBBITVEC_HANDLE_ERRS
+
+#include <errno.h>
+#include <stdio.h>
+
+#define LIBBITVEC_HANDLE_ERR(x) libbitvec_err(__FILE__, __LINE__, x)
+
+static inline void libbitvec_err(const char *file, int line, const char *info)
+{
+ fprintf(stderr, "libvec: %s at %s:%i: %s\n",
+ info, file, line, strerror(errno));
+ exit(1);
+}
+
+#else
+#define LIBBITVEC_HANDLE_ERR(x)
+#endif
+
+#ifdef UINT64_MAX
+typedef uint64_t libbitvec_slot_t;
+#else
+typedef uint32_t libbitvec_slot_t;
+#endif
+
+struct bitvec {
+ size_t cap;
+ libbitvec_slot_t *data;
+};
+
+bool bitvec_init(struct bitvec *vec, size_t cap);
+void bitvec_deinit(struct bitvec *vec);
+
+struct bitvec *bitvec_alloc(size_t cap);
+void bitvec_free(struct bitvec *vec);
+
+bool bitvec_reserve(struct bitvec *vec, size_t cnt);
+bool bitvec_shrink(struct bitvec *vec, size_t cnt);
+
+bool bitvec_get(struct bitvec *vec, size_t pos);
+void bitvec_set(struct bitvec *vec, size_t pos);
+void bitvec_clear(struct bitvec *vec, size_t pos);
+void bitvec_setn(struct bitvec *vec, size_t start, size_t end, bool set);
diff --git a/libbitvec.abi b/libbitvec.abi
@@ -0,0 +1,13 @@
+bitvec_init
+bitvec_deinit
+
+bitvec_alloc
+bitvec_free
+
+bitvec_reserve
+bitvec_shrink
+
+bitvec_get
+bitvec_set
+bitvec_clear
+bitvec_setn
diff --git a/libbitvec.lds b/libbitvec.lds
@@ -0,0 +1,17 @@
+LIBBITVEC_1.0 {
+ global:
+ bitvec_init;
+ bitvec_deinit;
+
+ bitvec_alloc;
+ bitvec_free;
+
+ bitvec_reserve;
+ bitvec_shrink;
+
+ bitvec_get;
+ bitvec_set;
+ bitvec_clear;
+ bitvec_setn;
+ local: *;
+};
diff --git a/src/bitvec.c b/src/bitvec.c
@@ -0,0 +1,166 @@
+#include "bitvec.h"
+
+#include <string.h>
+
+#define SLOT_BYTES sizeof(libbitvec_slot_t)
+#define SLOT_BITS (SLOT_BYTES * 8)
+#define SLOT_MAX (~(libbitvec_slot_t)0)
+
+#define CEILDIV(n, d) ((n) / (d) + ((n) % (d) == 0 ? 0 : 1))
+#define BITCEIL(n) ((n) + SLOT_BITS - 1 - (SLOT_BITS - 1 + n) % SLOT_BITS)
+
+#define SLOT(n) ((n) / SLOT_BITS)
+#define SLOTCNT(n) CEILDIV(n, SLOT_BITS)
+#define SLOT_BIT(n) (((libbitvec_slot_t)1) << n)
+
+#define APPLY_MASK(x,s,m) ((s) ? ((x) | (m)) : ((x) & ~(m)))
+
+bool
+bitvec_init(struct bitvec *vec, size_t cap)
+{
+ LIBBITVEC_ASSERT(vec != NULL);
+
+ if (cap) {
+ vec->data = calloc(SLOTCNT(cap), SLOT_BYTES);
+ if (!vec->data) {
+ LIBBITVEC_HANDLE_ERR("calloc");
+ return false;
+ }
+ } else {
+ vec->data = NULL;
+ }
+
+ vec->cap = BITCEIL(cap);
+
+ return true;
+}
+
+void
+bitvec_deinit(struct bitvec *vec)
+{
+ LIBBITVEC_ASSERT(vec != NULL);
+
+ vec->cap = 0;
+ free(vec->data);
+}
+
+struct bitvec *
+bitvec_alloc(size_t cap)
+{
+ struct bitvec *bitvec;
+
+ bitvec = malloc(sizeof(struct bitvec));
+ if (!bitvec) {
+ LIBBITVEC_HANDLE_ERR("malloc");
+ return NULL;
+ }
+
+ if (!bitvec_init(bitvec, cap)) {
+ free(bitvec);
+ return NULL;
+ }
+
+ return bitvec;
+}
+
+void
+bitvec_free(struct bitvec *vec)
+{
+ bitvec_deinit(vec);
+ free(vec);
+}
+
+bool
+bitvec_reserve(struct bitvec *vec, size_t cnt)
+{
+ LIBBITVEC_ASSERT(vec != NULL);
+
+ cnt = BITCEIL(cnt);
+ if (vec->cap >= cnt) return true;
+
+ vec->data = realloc(vec->data, SLOTCNT(cnt) * SLOT_BYTES);
+ if (!vec->data) {
+ LIBBITVEC_HANDLE_ERR("realloc");
+ return false;
+ }
+
+ memset(vec->data + SLOT(vec->cap), 0, SLOT(cnt) - SLOT(vec->cap));
+ vec->cap = cnt;
+
+ return true;
+}
+
+bool
+bitvec_shrink(struct bitvec *vec, size_t cnt)
+{
+ LIBBITVEC_ASSERT(vec != NULL);
+
+ cnt = BITCEIL(cnt);
+ if (vec->cap <= cnt) return true;
+
+ vec->data = realloc(vec->data, SLOTCNT(cnt));
+ if (!vec->data) {
+ LIBBITVEC_HANDLE_ERR("realloc");
+ return false;
+ }
+
+ vec->cap = cnt;
+
+ return true;
+}
+
+bool
+bitvec_get(struct bitvec *vec, size_t pos)
+{
+ LIBBITVEC_ASSERT(vec != NULL);
+
+ if (pos >= vec->cap) return false;
+ return !!(vec->data[pos / SLOT_BITS] & SLOT_BIT(pos % SLOT_BITS));
+}
+
+void
+bitvec_set(struct bitvec *vec, size_t pos)
+{
+ LIBBITVEC_ASSERT(vec != NULL && pos < vec->cap);
+
+ vec->data[pos / SLOT_BITS] |= SLOT_BIT(pos % SLOT_BITS);
+}
+
+void
+bitvec_clear(struct bitvec *vec, size_t pos)
+{
+ LIBBITVEC_ASSERT(vec != NULL && pos < vec->cap);
+
+ vec->data[pos / SLOT_BITS] &= ~SLOT_BIT(pos % SLOT_BITS);
+}
+
+void
+bitvec_setn(struct bitvec *vec, size_t start, size_t end, bool set)
+{
+ libbitvec_slot_t mask;
+ size_t starti, endi, i;
+
+ LIBBITVEC_ASSERT(vec != NULL && end >= start && end <= vec->cap);
+
+ if (start == end) return;
+
+ starti = SLOT(start);
+ end = SLOT(end - 1);
+
+ if (starti == endi) {
+ if (end % SLOT_BITS == 0)
+ mask = SLOT_MAX - SLOT_BIT(start % SLOT_BITS);
+ else
+ mask = SLOT_BIT(end % SLOT_BITS) - SLOT_BIT(start % SLOT_BITS);
+ vec->data[starti] = APPLY_MASK(vec->data[starti], set, mask);
+ } else {
+ mask = SLOT_MAX - SLOT_BIT(start % SLOT_BITS);
+ vec->data[starti] = APPLY_MASK(vec->data[starti], set, mask);
+
+ for (i = starti + 1; i <= endi - 1; i++)
+ vec->data[i] = APPLY_MASK(vec->data[i], set, SLOT_MAX);
+
+ mask = SLOT_BIT(end % SLOT_BITS) - SLOT_BIT(0);
+ vec->data[endi] = APPLY_MASK(vec->data[endi], set, mask);
+ }
+}
diff --git a/src/test.c b/src/test.c
@@ -0,0 +1,30 @@
+#include "bitvec.h"
+
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+int
+main(int argc, const char **argv)
+{
+ struct bitvec bitvec;
+ int i, *val;
+
+ bitvec_init(&bitvec, 10);
+
+ for (i = 1; i < argc; i++) {
+ *val = atoi(argv[i]);
+ if (bitvec_get(&bitvec, *val))
+ printf("%i -> dup!\n", *val);
+ bitvec_reserve(&bitvec, *val);
+ bitvec_set(&bitvec, *val);
+ }
+
+ for (i = 0; i < 10; i++)
+ printf("%i", bitvec_get(&bitvec, i));
+ printf("\n");
+
+ printf("bitvec len: %lu\n", bitvec.cap / (8 * sizeof(libbitvec_slot_t)));
+
+ bitvec_deinit(&bitvec);
+}
