libdvec-c

commit 75a9d022cfa82ecbd91e0a37d5cb677e36cae860
parent 13578a3547d66b6cd6788ae2dfed744e20a00e74
Author: Louis Burda <quent.burda@gmail.com>
Date:   Thu, 12 Jan 2023 02:12:07 +0100

Refactor abi for common use-cases and perf

Diffstat:
M
Makefile
 | 
33
+++++++++------------------------
M
include/vec.h
 | 
106
++++++++++++++++++++++++++++++++++++++++++++++++++++++++-----------------------
M
libvec.abi
 | 
16
++++++----------
M
libvec.lds
 | 
18
+++++++-----------
M
src/test.c
 | 
12
+++++++-----
M
src/vec.c
 | 
177
+++++++++++++++++++++++++++-----------------------------------------------------

6 files changed, 164 insertions(+), 198 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,14 +1,8 @@
-CFLAGS = -I include -g
-LDLIBS =
-DEPFLAGS = -MT $@ -MMD -MP -MF build/$*.d
+CFLAGS = -g -I include -Wno-prototype -Wunused-function -Wunused-variable
 
-_SRCS = vec.c
-SRCS = $(_SRCS:%.c=src/%.c)
-OBJS = $(_SRCS:%.c=build/%.o)
-DEPS = $(_SRCS:%.c=build/%.d)
-PI_OBJS = $(_SRCS:%.c=build/%.pi.o)
-
-.PHONY: all clean
+ifeq "$(LIBVEC_ASSERT)" "1"
+CFLAGS += -DLIBVEC_ASSERT=1
+endif
 
 all: build/libvec.so build/libvec.a build/test
 
@@ -18,24 +12,15 @@ clean:
 build:
 	mkdir build
 
-build/%.o: src/%.c build/%.d | build
-	$(CC) -c -o $@ $< $(DEPFLAGS) $(CFLAGS)
-
-build/%.pi.o: src/%.c build/%.d | build
-	$(CC) -c -o $@ $< $(DEPFLAGS) $(CFLAGS) -fPIC
-
-build/%.d: | build;
-
-include $(DEPS)
-
-build/libvec.a: $(OBJS) | build
+build/libvec.a: src/vec.c | build
 	$(CC) -o build/tmp.o $^ $(CFLAGS) -r
 	objcopy --keep-global-symbols=libvec.abi build/tmp.o build/fixed.o
 	ar rcs $@ build/fixed.o
 
-build/libvec.so: $(PI_OBJS) | build
-	$(CC) -o $@ $(PI_OBJS) $(CFLAGS) -shared -Wl,-version-script libvec.lds
+build/libvec.so: src/vec.c | build
+	$(CC) -o $@ $* -fPIC $(CFLAGS) -shared -Wl,-version-script libvec.lds
 
-build/test: src/test.c build/libvec.a | build
+build/test: src/test.c build/libvec.a
 	$(CC) -o $@ $^ $(CFLAGS)
 
+.PHONY: all clean
diff --git a/include/vec.h b/include/vec.h
@@ -1,29 +1,18 @@
 #include <stdbool.h>
+#include <stdio.h>
 #include <stdlib.h>
 
-#define VEC_ITER(vec, type, var) \
-	var = (type*) NULL; vec_iter(vec, &var); 
-
-#define VEC_PUSH(vec, type, val) \
-	do { \
-		type tmp = (val); \
-		vec_push(vec, &tmp); \
-	} while (0)
-
-#define VEC_POP(vec, type, var) \
-	do { \
-		type *tmp = vec_pop(vec); \
-		memcpy(&var, tmp, sizeof(type); \
-	} while (0)
-
-#define VEC_AT(vec, type, idx) \
-		(*(type *)vec_at(vec, idx))
+#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;
 
-	char *data;
+	void *data;
 };
 
 void vec_init(struct vec *vec, size_t dsize, size_t cap);
@@ -34,21 +23,78 @@ 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);
+
+void 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);
+
+	return vec->data + index * vec->dsize;
+}
+
+static inline void *vec_front(struct vec *vec)
+{
+	LIBVEC_ASSERT(vec != NULL);
+
+	return vec->data;
+}
+
+static inline void *vec_back(struct vec *vec)
+{
+	LIBVEC_ASSERT(vec != NULL && vec->len > 0);
+
+	return vec->data + (vec->len - 1) * vec->dsize;
+}
+
+static inline bool vec_empty(struct vec *vec)
+{
+	LIBVEC_ASSERT(vec != NULL);
 
-void vec_add(struct vec *vec, const void *data, size_t count);
-void vec_rm(struct vec *vec, size_t count);
-void vec_rm_at(struct vec *vec, size_t index, size_t count);
+	return !vec->len;
+}
 
-void vec_push(struct vec *vec, const void *data);
-void *vec_pop(struct vec *vec);
+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;
+}
 
-void *vec_at(struct vec *vec, size_t index);
-bool vec_iter(struct vec *vec, void *p);
+static inline void *
+vec_alloc_slot(struct vec *vec)
+{
+	return vec_alloc_slots(vec, 1);
+}
 
-void vec_set(struct vec *vec, size_t index, const void *data);
+static inline void
+vec_free_slots(struct vec *vec, void *slot, size_t count)
+{
+	LIBVEC_ASSERT(vec != NULL && slot >= vec->data
+		&& slot < vec->data + vec->len * vec->dsize
+		&& (slot - vec->data) % vec->dsize == 0);
 
-void vec_setbuf(struct vec *vec, void *buf);
-void *vec_popbuf(struct vec *vec);
+	vec_remove(vec, (slot - vec->data) / vec->dsize, count);
+}
 
-bool vec_empty(struct vec *vec);
-int vec_len(struct vec *vec);
+static inline void *
+vec_free_slot(struct vec *vec, void *slot)
+{
+	return vec_free_slot(vec, slot);
+}
diff --git a/libvec.abi b/libvec.abi
@@ -6,15 +6,11 @@ vec_free
 
 vec_clear
 vec_resize
+vec_shrink
 
-vec_push
-vec_pop
+vec_reserve
+vec_remove
+vec_replace
 
-vec_at
-vec_iter
-
-vec_set
-vec_rm
-
-vec_empty
-vec_len
+vec_iter_fwd
+vec_iter_bwd
diff --git a/libvec.lds b/libvec.lds
@@ -1,4 +1,4 @@
-LIBVEC_1.0 {
+LIBVEC_1.1 {
 	global:
 		vec_init;
 		vec_deinit;
@@ -8,17 +8,13 @@ LIBVEC_1.0 {
 
 		vec_clear;
 		vec_resize;
+		vec_shrink;
 
-		vec_push;
-		vec_pop;
+		vec_reserve;
+		vec_remove;
+		vec_replace;
 
-		vec_at;
-		vec_iter;
-
-		vec_set;
-		vec_rm;
-
-		vec_empty;
-		vec_len;
+		vec_iter_fwd;
+		vec_iter_bwd;
 	local: *;
 };
diff --git a/src/test.c b/src/test.c
@@ -8,15 +8,17 @@ int
 main(int argc, const char **argv)
 {
 	struct vec vec;
-	int *num, i;
+	int i, *val;
 
 	vec_init(&vec, sizeof(int), 10);
 
-	for (i = 1; i < argc; i++)
-		VEC_PUSH(&vec, int, atoi(argv[i]));
+	for (i = 1; i < argc; i++) {
+		val = vec_alloc_slot(&vec);
+		*val = atoi(argv[i]);
+	}
 
-	for (i = 0; i < vec_len(&vec); i++)
-		printf("%i\n", VEC_AT(&vec, int, i));
+	for (i = 0; i < vec.len; i++)
+		printf("%i\n", *(int *)vec_at(&vec, i));
 
 	vec_deinit(&vec);
 }
diff --git a/src/vec.c b/src/vec.c
@@ -1,35 +1,16 @@
 #include "vec.h"
 
+#include <err.h>
 #include <errno.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <stdarg.h>
 #include <string.h>
 
-#ifdef LIBVEC_UNSAFE
-#define ASSERT(x)
-#define OOM_CHECK(x)
-#else
-#define ASSERT(x) assert((x), __FILE__, __LINE__, #x)
-#define OOM_CHECK(x) assert((x) != NULL, __FILE__, __LINE__, "Out of Memory")
-#endif
-
-static void assert(int cond, const char *file, int line, const char *condstr);
-
-void
-assert(int cond, const char *file, int line, const char *condstr)
-{
-	if (cond) return;
-
-	fprintf(stderr, "CVEC: Assertion failed at %s:%i (%s)\n",
-		file, line, condstr);
-	exit(1);
-}
-
 void
 vec_init(struct vec *vec, size_t dsize, size_t cap)
 {
-	ASSERT(vec != NULL && dsize > 0 && cap >= 0);
+	LIBVEC_ASSERT(vec != NULL && dsize > 0 && cap >= 0);
 
 	vec->dsize = dsize;
 	vec->cap = cap;
@@ -38,14 +19,14 @@ vec_init(struct vec *vec, size_t dsize, size_t cap)
 	vec->data = NULL;
 	if (vec->cap) {
 		vec->data = malloc(dsize * cap);
-		OOM_CHECK(vec->data);
+		if (!vec->data) err(1, "malloc");
 	}
 }
 
 void
 vec_deinit(struct vec *vec)
 {
-	ASSERT(vec != NULL);
+	LIBVEC_ASSERT(vec != NULL);
 
 	free(vec->data);
 }
@@ -55,10 +36,10 @@ vec_alloc(size_t dsize, size_t cap)
 {
 	struct vec *vec;
 
-	ASSERT(dsize > 0 && cap > 0);
+	LIBVEC_ASSERT(dsize > 0 && cap > 0);
 
 	vec = malloc(sizeof(struct vec));
-	OOM_CHECK(vec);
+	if (!vec) err(1, "malloc");
 
 	vec_init(vec, dsize, cap);
 
@@ -68,7 +49,7 @@ vec_alloc(size_t dsize, size_t cap)
 void
 vec_free(struct vec *vec)
 {
-	ASSERT(vec != NULL);
+	LIBVEC_ASSERT(vec != NULL);
 
 	vec_deinit(vec);
 	free(vec);
@@ -77,7 +58,7 @@ vec_free(struct vec *vec)
 void
 vec_clear(struct vec *vec)
 {
-	ASSERT(vec != NULL);
+	LIBVEC_ASSERT(vec != NULL);
 
 	vec->len = 0;
 }
@@ -85,92 +66,78 @@ vec_clear(struct vec *vec)
 void
 vec_resize(struct vec *vec, size_t cap)
 {
-	ASSERT(vec != NULL && cap != 0 && vec->len <= cap);
+	LIBVEC_ASSERT(vec != NULL && cap != 0 && vec->len <= cap);
 
 	vec->cap = cap;
 	vec->data = realloc(vec->data, vec->cap * vec->dsize);
-	OOM_CHECK(vec->data);
+	if (!vec->data) err(1, "realloc");
 }
 
 void
-vec_add(struct vec *vec, const void *data, size_t len)
+vec_shrink(struct vec *vec)
 {
-	ASSERT(vec != NULL && data != NULL);
+	LIBVEC_ASSERT(vec != NULL);
 
-	if (vec->len + len > vec->cap) {
-		vec->cap *= 2;
-		if (vec->len + len > vec->cap)
-			vec->cap = vec->len + len;
-		vec->data = realloc(vec->data, vec->cap * vec->dsize);
-		OOM_CHECK(vec->data);
+	if (!vec->len) {
+		vec->cap = 1;
+	} else {
+		vec->cap = vec->len;
 	}
 
-	memcpy(vec->data + vec->len * vec->dsize, data, len * vec->dsize);
-	vec->len += len;
+	vec->data = realloc(vec->data, vec->cap * vec->dsize);
+	if (!vec->data) err(1, "realloc");
 }
 
 void
-vec_rm(struct vec *vec, size_t count)
+vec_reserve(struct vec *vec, size_t index, size_t len)
 {
-	ASSERT(vec != NULL && count >= vec->len);
+	LIBVEC_ASSERT(vec != NULL && index <= vec->len);
 
-	vec->len -= count;
-	if (vec->len < vec->cap / 2) {
-		vec->cap /= 2;
+	if (vec->len + len > vec->cap) {
+		vec->cap *= 2;
+		if (vec->len + len > vec->cap)
+			vec->cap = vec->len + len;
 		vec->data = realloc(vec->data, vec->cap * vec->dsize);
-		OOM_CHECK(vec->data);
+		if (!vec->data) err(1, "realloc");
 	}
-}
-
-void
-vec_rm_at(struct vec *vec, size_t index, size_t count)
-{
-	void *start, *end;
 
-	ASSERT(vec != NULL && index < vec->len
-		&& count > 0 && index + count < vec->len);
-
-	if (index + count < vec->len) {
-		start = vec->data + index * vec->dsize;
-		end = vec->data + vec->len * vec->dsize;
-		memcpy(start, start + count * vec->dsize,
-			(vec->len - index - count) * vec->dsize);
+	if (index < vec->len) {
+		memmove(vec->data + (index + len) * vec->dsize,
+			vec->data + index * vec->dsize,
+			(vec->len - index) * vec->dsize);
 	}
 
-	vec_rm(vec, count);
+	vec->len += len;
 }
 
-
 void
-vec_push(struct vec *vec, const void *data)
-{
-	vec_add(vec, data, 1);
-}
-
-void *
-vec_pop(struct vec *vec)
+vec_remove(struct vec *vec, size_t index, size_t count)
 {
-	ASSERT(vec != NULL);
+	LIBVEC_ASSERT(vec != NULL && count >= vec->len && index + count <= vec->len);
 
-	vec_rm(vec, 1);
+	if (index + count < vec->len) {
+		memmove(vec->data + index * vec->dsize,
+			vec->data + (index + count) * vec->dsize,
+			(vec->len - (index + count)) * vec->dsize);
+	}
 
-	return vec->data + vec->dsize * vec->len;
+	vec->len -= count;
 }
 
-void *
-vec_at(struct vec *vec, size_t index)
+void
+vec_replace(struct vec *vec, size_t index, const void *data, size_t count)
 {
-	ASSERT(vec != NULL && index < vec->len);
+	LIBVEC_ASSERT(vec != NULL && data != NULL && index + count < vec->len);
 
-	return vec->data + vec->dsize * index;
+	memcpy(vec->data + index * vec->dsize, data, count * vec->dsize);
 }
 
 bool
-vec_iter(struct vec *vec, void *p)
+vec_iter_fwd(struct vec *vec, void **p)
 {
-	char **iter;
+	void **iter;
 
-	ASSERT(vec != NULL && p != NULL);
+	LIBVEC_ASSERT(vec != NULL && p != NULL);
 
 	if (!vec->len) return false;
 
@@ -184,49 +151,23 @@ vec_iter(struct vec *vec, void *p)
 	return *iter < vec->data + vec->dsize * vec->len;
 }
 
-void
-vec_set(struct vec *vec, size_t index, const void *data)
-{
-	ASSERT(vec != NULL && data != NULL && index < vec->len);
-
-	memcpy(vec->data + index * vec->dsize, data, vec->dsize);
-}
-
-void
-vec_setbuf(struct vec *vec, void *data)
-{
-	ASSERT(vec != NULL && data != NULL);
-
-	free(vec->data);
-	vec->data = data;
-}
-
-void *
-vec_popbuf(struct vec *vec)
-{
-	void *data;
-
-	ASSERT(vec != NULL);
-
-	data = vec->data;
-	vec->data = NULL;
-	vec->len = 0;
-
-	return data;
-}
-
 bool
-vec_empty(struct vec *vec)
+vec_iter_bwd(struct vec *vec, void **p)
 {
-	ASSERT(vec != NULL);
+	void **iter;
 
-	return vec->len == 0;
-}
+	LIBVEC_ASSERT(vec != NULL && p != NULL);
 
-int
-vec_len(struct vec *vec)
-{
-	ASSERT(vec != NULL);
+	if (!vec->len) return false;
+
+	iter = p;
+	if (*iter == NULL) {
+		*iter = vec->data + (vec->len - 1) * vec->dsize;
+	} else if (*iter > vec->data) {
+		*iter -= vec->dsize;
+	} else {
+		return false;
+	}
 
-	return vec->len;
+	return true;
 }