1 files changed, 114 insertions, 0 deletions
diff --git a/src/vector.c b/src/vector.c
new file mode 100644
index 0000000..41cd0cc
--- /dev/null
+++ b/src/vector.c
@@ -0,0 +1,114 @@
+/**
+   \file
+
+   Typesafe dynamically sized arrays
+*/
+
+
+#include "vector.h"
+
+#include <errno.h>
+#include <stdint.h>
+#include <string.h>
+
+/** The minimum number of elements to allocate even when fewer elements are used */
+#define MIN_VECTOR_ALLOC 4
+
+/**
+   Multiplies two size_t values, checking for overflows
+
+   Both arguments are limited to the size of a uint32_t (to keep the check simple)
+
+   Returns SIZE_MAX and sets errno on failure.
+*/
+static inline size_t mul_check(size_t members, size_t size) {
+	uint64_t v = (uint64_t)members * size;
+
+	if (members > UINT32_MAX || size > UINT32_MAX || v > SIZE_MAX) {
+		errno = EOVERFLOW;
+		return SIZE_MAX;
+	}
+
+	return v;
+}
+
+/**
+   Reallocates a block of memory for an array on the heap
+
+   May fail with EOVERFLOW (when members or size does not fit into a uint32_t,
+   or their product does not fit into a size_t) or ENOMEM.
+*/
+static inline void * realloc_array(void *ptr, size_t members, size_t size) {
+	errno = 0;
+	size_t array_size = mul_check(members, size);
+	if (errno)
+		return NULL;
+
+	return realloc(ptr, array_size);
+}
+
+/**
+   Resizes a vector
+
+   Vector allocations are always powers of 2.
+
+   Internal function, use VECTOR_RESIZE() instead.
+*/
+bool _vector_resize(vector_desc_t *desc, void **data, size_t n, size_t elemsize) {
+	desc->length = n;
+
+	size_t alloc = desc->allocated;
+
+	if (!alloc) {
+		alloc = MIN_VECTOR_ALLOC;
+		n = n*3/2;
+	}
+
+	while (alloc < n) {
+		alloc <<= 1;
+		if (!alloc) {
+			errno = ENOMEM;
+			return false;
+		}
+	}
+
+	if (alloc != desc->allocated) {
+		desc->allocated = alloc;
+		void *tmp = realloc_array(*data, alloc, elemsize);
+		if (!tmp)
+			return false;
+
+		*data = tmp;
+	}
+
+	return true;
+}
+
+/**
+   Inserts an element into a vector
+
+   Internal function, use VECTOR_INSERT() and VECTOR_ADD() instead.
+*/
+bool _vector_insert(vector_desc_t *desc, void **data, void *element, size_t pos, size_t elemsize) {
+	if (!_vector_resize(desc, data, desc->length+1, elemsize))
+		return false;
+
+	void *p = *data + pos*elemsize;
+
+	memmove(p+elemsize, p, (desc->length-pos-1)*elemsize);
+	memcpy(p, element, elemsize);
+
+	return true;
+}
+
+/**
+   Deletes an element from a vector
+
+   Internal function, use VECTOR_DELETE() instead.
+*/
+void _vector_delete(vector_desc_t *desc, void **data, size_t pos, size_t elemsize) {
+	void *p = *data + pos*elemsize;
+	memmove(p, p+elemsize, (desc->length-pos-1)*elemsize);
+
+	desc->length--;
+}