commit 53ccd2847a9b0cac412b18bf778dffb42d395b97
parent 75a9d022cfa82ecbd91e0a37d5cb677e36cae860
Author: Louis Burda <quent.burda@gmail.com>
Date: Sun, 15 Jan 2023 15:33:34 +0100
Added bit vector implementation and optional error handling
Diffstat:
9 files changed, 342 insertions(+), 39 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,7 +1,14 @@
CFLAGS = -g -I include -Wno-prototype -Wunused-function -Wunused-variable
+SRC = src/vec.c src/bitvec.c
+HDR = include/vec.h include/bitvec.h
+
ifeq "$(LIBVEC_ASSERT)" "1"
-CFLAGS += -DLIBVEC_ASSERT=1
+CFLAGS += -DLIBVEC_ASSERT_ENABLE=1
+endif
+
+ifeq "$(LIBVEC_HANDLE_ERR)" "1"
+CFLAGS += -DLIBVEC_HANDLE_ERRS=1
endif
all: build/libvec.so build/libvec.a build/test
@@ -12,13 +19,13 @@ clean:
build:
mkdir build
-build/libvec.a: src/vec.c | build
- $(CC) -o build/tmp.o $^ $(CFLAGS) -r
+build/libvec.a: $(SRC) $(HDR) | build
+ $(CC) -o build/tmp.o $(SRC) $(CFLAGS) -r
objcopy --keep-global-symbols=libvec.abi build/tmp.o build/fixed.o
ar rcs $@ build/fixed.o
-build/libvec.so: src/vec.c | build
- $(CC) -o $@ $* -fPIC $(CFLAGS) -shared -Wl,-version-script libvec.lds
+build/libvec.so: $(SRC) $(HDR) | build
+ $(CC) -o $@ $(SRC) -fPIC $(CFLAGS) -shared -Wl,-version-script libvec.lds
build/test: src/test.c build/libvec.a
$(CC) -o $@ $^ $(CFLAGS)
diff --git a/include/assert.h b/include/assert.h
@@ -0,0 +1,43 @@
+#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
@@ -0,0 +1,32 @@
+#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,13 +1,11 @@
+#pragma once
+
+#include "assert.h"
+
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
-#ifdef LIBVEC_ASSERT_ENABLE
-#define LIBVEC_ASSERT(x) libvec_assert((x), __FILE__, __LINE__, #x)
-#else
-#define LIBVEC_ASSERT(x)
-#endif
-
struct vec {
size_t dsize;
size_t len, cap;
@@ -15,33 +13,23 @@ struct vec {
void *data;
};
-void vec_init(struct vec *vec, size_t dsize, size_t cap);
+bool vec_init(struct vec *vec, size_t dsize, size_t cap);
void vec_deinit(struct vec *vec);
struct vec *vec_alloc(size_t dsize, size_t cap);
void vec_free(struct vec *vec);
void vec_clear(struct vec *vec);
-void vec_resize(struct vec *vec, size_t cap);
-void vec_shrink(struct vec *vec);
+bool vec_resize(struct vec *vec, size_t cap);
+bool vec_shrink(struct vec *vec);
-void vec_reserve(struct vec *vec, size_t index, size_t count);
+bool vec_reserve(struct vec *vec, size_t index, size_t count);
void vec_remove(struct vec *vec, size_t index, size_t count);
void vec_replace(struct vec *vec, size_t index, const void *data, size_t count);
bool vec_iter_fwd(struct vec *vec, void **p);
bool vec_iter_bwd(struct vec *vec, void **p);
-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();
-}
-
static inline void *vec_at(struct vec *vec, size_t index)
{
LIBVEC_ASSERT(vec != NULL && index < vec->len);
@@ -93,8 +81,8 @@ vec_free_slots(struct vec *vec, void *slot, size_t count)
vec_remove(vec, (slot - vec->data) / vec->dsize, count);
}
-static inline void *
+static inline void
vec_free_slot(struct vec *vec, void *slot)
{
- return vec_free_slot(vec, slot);
+ vec_free_slots(vec, slot, 1);
}
diff --git a/libvec.abi b/libvec.abi
@@ -14,3 +14,17 @@ 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,5 +16,19 @@ 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
@@ -0,0 +1,166 @@
+#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,4 +1,5 @@
#include "vec.h"
+#include "bitvec.h"
#include <stdlib.h>
#include <stdio.h>
@@ -7,18 +8,31 @@
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);
}
diff --git a/src/vec.c b/src/vec.c
@@ -1,13 +1,12 @@
#include "vec.h"
-#include <err.h>
#include <errno.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <string.h>
-void
+bool
vec_init(struct vec *vec, size_t dsize, size_t cap)
{
LIBVEC_ASSERT(vec != NULL && dsize > 0 && cap >= 0);
@@ -18,9 +17,14 @@ vec_init(struct vec *vec, size_t dsize, size_t cap)
vec->len = 0;
vec->data = NULL;
if (vec->cap) {
- vec->data = malloc(dsize * cap);
- if (!vec->data) err(1, "malloc");
+ vec->data = calloc(cap, dsize);
+ if (!vec->data) {
+ LIBVEC_HANDLE_ERR("calloc");
+ return false;
+ }
}
+
+ return true;
}
void
@@ -39,9 +43,15 @@ vec_alloc(size_t dsize, size_t cap)
LIBVEC_ASSERT(dsize > 0 && cap > 0);
vec = malloc(sizeof(struct vec));
- if (!vec) err(1, "malloc");
+ if (!vec) {
+ LIBVEC_HANDLE_ERR("malloc");
+ return NULL;
+ }
- vec_init(vec, dsize, cap);
+ if (!vec_init(vec, dsize, cap)) {
+ free(vec);
+ return NULL;
+ }
return vec;
}
@@ -63,17 +73,22 @@ vec_clear(struct vec *vec)
vec->len = 0;
}
-void
+bool
vec_resize(struct vec *vec, size_t cap)
{
LIBVEC_ASSERT(vec != NULL && cap != 0 && vec->len <= cap);
vec->cap = cap;
vec->data = realloc(vec->data, vec->cap * vec->dsize);
- if (!vec->data) err(1, "realloc");
+ if (!vec->data) {
+ LIBVEC_HANDLE_ERR("realloc");
+ return false;
+ }
+
+ return true;
}
-void
+bool
vec_shrink(struct vec *vec)
{
LIBVEC_ASSERT(vec != NULL);
@@ -85,10 +100,15 @@ vec_shrink(struct vec *vec)
}
vec->data = realloc(vec->data, vec->cap * vec->dsize);
- if (!vec->data) err(1, "realloc");
+ if (!vec->data) {
+ LIBVEC_HANDLE_ERR("realloc");
+ return false;
+ }
+
+ return true;
}
-void
+bool
vec_reserve(struct vec *vec, size_t index, size_t len)
{
LIBVEC_ASSERT(vec != NULL && index <= vec->len);
@@ -98,7 +118,10 @@ vec_reserve(struct vec *vec, size_t index, size_t len)
if (vec->len + len > vec->cap)
vec->cap = vec->len + len;
vec->data = realloc(vec->data, vec->cap * vec->dsize);
- if (!vec->data) err(1, "realloc");
+ if (!vec->data) {
+ LIBVEC_HANDLE_ERR("realloc");
+ return false;
+ }
}
if (index < vec->len) {
@@ -108,6 +131,8 @@ vec_reserve(struct vec *vec, size_t index, size_t len)
}
vec->len += len;
+
+ return true;
}
void
