commit 8892e68e27576b4601da16173e2b82665a7fcdeb
parent 53ccd2847a9b0cac412b18bf778dffb42d395b97
Author: Louis Burda <quent.burda@gmail.com>
Date: Fri, 17 Feb 2023 19:47:53 +0100
Migrate out bitvec into separate library
Diffstat:
8 files changed, 62 insertions(+), 291 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,7 +1,12 @@
-CFLAGS = -g -I include -Wno-prototype -Wunused-function -Wunused-variable
+PREFIX ?= /usr/local
+LIBDIR ?= /lib
+INCLUDEDIR ?= /include
-SRC = src/vec.c src/bitvec.c
-HDR = include/vec.h include/bitvec.h
+CFLAGS = -I include -Wno-prototype -Wunused-function -Wunused-variable
+
+ifeq "$(LIBVEC_DEBUG)" "1"
+CFLAGS += -g
+endif
ifeq "$(LIBVEC_ASSERT)" "1"
CFLAGS += -DLIBVEC_ASSERT_ENABLE=1
@@ -19,15 +24,25 @@ clean:
build:
mkdir build
-build/libvec.a: $(SRC) $(HDR) | build
- $(CC) -o build/tmp.o $(SRC) $(CFLAGS) -r
+build/libvec.a: src/vec.c include/vec.h | build
+ $(CC) -o build/tmp.o src/vec.c $(CFLAGS) -r
objcopy --keep-global-symbols=libvec.abi build/tmp.o build/fixed.o
ar rcs $@ build/fixed.o
-build/libvec.so: $(SRC) $(HDR) | build
- $(CC) -o $@ $(SRC) -fPIC $(CFLAGS) -shared -Wl,-version-script libvec.lds
+build/libvec.so: src/vec.c include/vec.h | build
+ $(CC) -o $@ src/vec.c -fPIC $(CFLAGS) -shared -Wl,-version-script libvec.lds
build/test: src/test.c build/libvec.a
$(CC) -o $@ $^ $(CFLAGS)
-.PHONY: all clean
+install:
+ install -m644 include/vec.h -t "$(DESTDIR)$(PREFIX)$(INCLUDEDIR)"
+ install -m755 build/libvec.so -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+ install -m755 build/libvec.a -t "$(DESTDIR)$(PREFIX)$(LIBDIR)"
+
+uninstall:
+ rm -f "$(DESTDIR)$(PREFIX)$(INCLUDEDIR)/vec.h"
+ rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libvec.so"
+ rm -f "$(DESTDIR)$(PREFIX)$(LIBDIR)/libvec.a"
+
+.PHONY: all clean install uninstall
diff --git a/include/assert.h b/include/assert.h
@@ -1,43 +0,0 @@
-#pragma once
-
-#ifdef LIBVEC_ASSERT_ENABLE
-
-#include <stdio.h>
-#include <stdlib.h>
-
-#define LIBVEC_ASSERT(x) libvec_assert((x), __FILE__, __LINE__, #x)
-
-static inline void libvec_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 LIBVEC_ASSERT(x)
-#endif
-
-
-#ifdef LIBVEC_HANDLE_ERRS
-
-#include <errno.h>
-#include <string.h>
-#include <stdio.h>
-#include <stdlib.h>
-
-#define LIBVEC_HANDLE_ERR(x) libvec_err(__FILE__, __LINE__, x)
-
-static inline void libvec_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 LIBVEC_HANDLE_ERR(x)
-#endif
diff --git a/include/bitvec.h b/include/bitvec.h
@@ -1,32 +0,0 @@
-#pragma once
-
-#include "assert.h"
-
-#include <stdint.h>
-#include <stdbool.h>
-#include <stdlib.h>
-
-#ifdef UINT64_MAX
-typedef uint64_t libvec_bitslot_t;
-#else
-typedef uint32_t libvec_bitslot_t;
-#endif
-
-struct bitvec {
- size_t cap;
- libvec_bitslot_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/include/vec.h b/include/vec.h
@@ -1,11 +1,47 @@
#pragma once
-#include "assert.h"
-
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
+#ifdef LIBVEC_ASSERT_ENABLE
+
+#include <stdio.h>
+
+#define LIBVEC_ASSERT(x) libvec_assert((x), __FILE__, __LINE__, #x)
+
+static inline void libvec_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 LIBVEC_ASSERT(x)
+#endif
+
+#ifdef LIBVEC_HANDLE_ERRS
+
+#include <errno.h>
+#include <stdio.h>
+
+#define LIBVEC_HANDLE_ERR(x) libvec_err(__FILE__, __LINE__, x)
+
+static inline void libvec_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 LIBVEC_HANDLE_ERR(x)
+#endif
+
struct vec {
size_t dsize;
size_t len, cap;
@@ -62,6 +98,7 @@ static inline void *
vec_alloc_slots(struct vec *vec, size_t count)
{
vec_reserve(vec, vec->len, count);
+
return vec->data + (vec->len - count) * vec->dsize;
}
diff --git a/libvec.abi b/libvec.abi
@@ -14,17 +14,3 @@ vec_replace
vec_iter_fwd
vec_iter_bwd
-
-bitvec_init
-bitvec_deinit
-
-bitvec_alloc
-bitvec_free
-
-bitvec_reserve
-bitvec_shrink
-
-bitvec_get
-bitvec_set
-bitvec_clear
-bitvec_setn
diff --git a/libvec.lds b/libvec.lds
@@ -16,19 +16,5 @@ LIBVEC_1.1 {
vec_iter_fwd;
vec_iter_bwd;
-
- 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
@@ -1,166 +0,0 @@
-#include "bitvec.h"
-
-#include <string.h>
-
-#define SLOT_BYTES sizeof(libvec_bitslot_t)
-#define SLOT_BITS (SLOT_BYTES * 8)
-#define SLOT_MAX (~(libvec_bitslot_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) (((libvec_bitslot_t)1) << n)
-
-#define APPLY_MASK(x,s,m) ((s) ? ((x) | (m)) : ((x) & ~(m)))
-
-bool
-bitvec_init(struct bitvec *vec, size_t cap)
-{
- LIBVEC_ASSERT(vec != NULL);
-
- if (cap) {
- vec->data = calloc(SLOTCNT(cap), SLOT_BYTES);
- if (!vec->data) {
- LIBVEC_HANDLE_ERR("calloc");
- return false;
- }
- } else {
- vec->data = NULL;
- }
-
- vec->cap = BITCEIL(cap);
-
- return true;
-}
-
-void
-bitvec_deinit(struct bitvec *vec)
-{
- LIBVEC_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) {
- LIBVEC_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)
-{
- LIBVEC_ASSERT(vec != NULL);
-
- cnt = BITCEIL(cnt);
- if (vec->cap >= cnt) return true;
-
- vec->data = realloc(vec->data, SLOTCNT(cnt) * SLOT_BYTES);
- if (!vec->data) {
- LIBVEC_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)
-{
- LIBVEC_ASSERT(vec != NULL);
-
- cnt = BITCEIL(cnt);
- if (vec->cap <= cnt) return true;
-
- vec->data = realloc(vec->data, SLOTCNT(cnt));
- if (!vec->data) {
- LIBVEC_HANDLE_ERR("realloc");
- return false;
- }
-
- vec->cap = cnt;
-
- return true;
-}
-
-bool
-bitvec_get(struct bitvec *vec, size_t pos)
-{
- LIBVEC_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)
-{
- LIBVEC_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)
-{
- LIBVEC_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)
-{
- libvec_bitslot_t mask;
- size_t starti, endi, i;
-
- LIBVEC_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
@@ -1,5 +1,4 @@
#include "vec.h"
-#include "bitvec.h"
#include <stdlib.h>
#include <stdio.h>
@@ -8,31 +7,20 @@
int
main(int argc, const char **argv)
{
- struct bitvec bitvec;
struct vec vec;
int i, *val;
vec_init(&vec, sizeof(int), 10);
- bitvec_init(&bitvec, 10);
for (i = 1; i < argc; i++) {
val = vec_alloc_slot(&vec);
*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");
-
for (i = 0; i < vec.len; i++)
printf("%i\n", *(int *)vec_at(&vec, i));
printf("vec len: %lu\n", vec.len);
- printf("bitvec len: %lu\n", bitvec.cap / (8 * sizeof(libvec_bitslot_t)));
vec_deinit(&vec);
}
