Add some version of vector.c

7 files changed, 768 insertions, 0 deletions

diff --git a/deps.mk b/deps.mk
index d52cce6..7849036 100644
--- a/deps.mk
+++ b/deps.mk
@@ -11,6 +11,7 @@ sources.c = \
 	src/string.c \
 	src/testing.c \
 	src/util.c \
+	src/vector.c \
 
 tests.c = \
 	tests/catalog.c \
@@ -21,6 +22,7 @@ tests.c = \
 	tests/string.c \
 	tests/testing.c \
 	tests/util.c \
+	tests/vector.c \
 
 src/catalog.o:	src/catalog.h
 src/i18n.o:	src/i18n.h
@@ -30,6 +32,7 @@ src/random.o:	src/random.h
 src/string.o:	src/string.h
 src/testing.o:	src/testing.h
 src/util.o:	src/util.h
+src/vector.o:	src/vector.h
 
 tests/catalog.o:	src/catalog.c	src/catalog.h
 tests/i18n.o:	src/i18n.c	src/i18n.h
@@ -39,6 +42,7 @@ tests/random.o:	src/random.c	src/random.h
 tests/string.o:	src/string.c	src/string.h
 tests/testing.o:	src/testing.c	src/testing.h
 tests/util.o:	src/util.c	src/util.h
+tests/vector.o:	src/vector.c	src/vector.h
 
 tests/catalog.a:	tests/catalog.o
 tests/i18n.a:	tests/i18n.o
@@ -48,6 +52,7 @@ tests/random.a:	tests/random.o
 tests/string.a:	tests/string.o
 tests/testing.a:	tests/testing.o
 tests/util.a:	tests/util.o
+tests/vector.a:	tests/vector.o
 
 tests/catalog.bin-check:	tests/catalog.bin
 tests/i18n.bin-check:	tests/i18n.bin
@@ -57,6 +62,7 @@ tests/random.bin-check:	tests/random.bin
 tests/string.bin-check:	tests/string.bin
 tests/testing.bin-check:	tests/testing.bin
 tests/util.bin-check:	tests/util.bin
+tests/vector.bin-check:	tests/vector.bin
 
 
 src/catalog.o: src/logerr.h
@@ -67,6 +73,7 @@ src/random.o: src/logerr.h
 src/string.o:
 src/testing.o:
 src/util.o: src/logerr.h
+src/vector.o: src/logerr.h src/catalog.h src/i18n.h
 
 tests/catalog.o: src/logerr.h src/testing.h tests/slurp.h
 tests/i18n.o: src/catalog.h src/logerr.h
@@ -76,6 +83,7 @@ tests/random.o: src/logerr.h src/testing.h
 tests/string.o:
 tests/testing.o:
 tests/util.o: src/logerr.h src/testing.h tests/slurp.h
+tests/vector.o: src/logerr.h src/catalog.h src/i18n.h src/testing.h
 
 tests/catalog.a: src/logerr.o src/testing.o tests/slurp.o
 tests/i18n.a: src/catalog.o src/logerr.o
@@ -85,3 +93,4 @@ tests/random.a: src/logerr.o src/testing.o
 tests/string.a:
 tests/testing.a:
 tests/util.a: src/logerr.o src/testing.o tests/slurp.o
+tests/vector.a: src/logerr.o src/catalog.o src/i18n.o src/testing.o
diff --git a/src/i18n.c b/src/i18n.c
index 5d5c33a..81d1e36 100644
--- a/src/i18n.c
+++ b/src/i18n.c
@@ -47,6 +47,7 @@ MSGS[] = {
 	[MSG_VERSION]= NAME " " VERSION " " DATE "\n",
 	[MSG_ERR_VECTOR_MAX_CAPACITY]= "Already at max capacity (%ld): %s\n",
 	[MSG_ERR_VECTOR_OUT_OF_BOUNDS]=  "idx (%ld) is beyond bounds (%ld)\n",
+	[MSG_ERR_VECTOR_UNDERFLOW]=  "pop on an empty vector\n",
 	NULL
 };
 
diff --git a/src/i18n.h b/src/i18n.h
index 0472079..3d3f98a 100644
--- a/src/i18n.h
+++ b/src/i18n.h
@@ -36,6 +36,7 @@ enum MSGCATALOG_ID {
 	MSG_VERSION,
 	MSG_ERR_VECTOR_MAX_CAPACITY,
 	MSG_ERR_VECTOR_OUT_OF_BOUNDS,
+	MSG_ERR_VECTOR_UNDERFLOW,
 };
 
 
diff --git a/src/pindaibabs.en.msg b/src/pindaibabs.en.msg
index a0f6726..24eccbd 100644
--- a/src/pindaibabs.en.msg
+++ b/src/pindaibabs.en.msg
@@ -72,3 +72,5 @@
 
 37 idx (%ld) is beyond bounds (%ld)\n
 
+38 pop on an empty vector\n
+
diff --git a/src/vector.c b/src/vector.c
new file mode 100644
index 0000000..65f004f
--- /dev/null
+++ b/src/vector.c
@@ -0,0 +1,268 @@
+#include "config.h"
+
+#include <assert.h>
+#include <errno.h>
+#include <locale.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "logerr.h"
+#include "catalog.h"
+#include "i18n.h"
+
+#include "vector.h"
+
+
+struct Vector {
+	void **values;
+	size_t capacity;
+	size_t back_count;
+	size_t front_count;
+	const size_t max_capacity;
+	const size_t multiplier;
+	const size_t value_size;
+};
+
+static const size_t
+VECTOR_MAX_CAPACITY = SIZE_MAX;
+
+static const size_t
+VECTOR_DEFAULT_CAPACITY = 8;
+
+static const size_t
+GROWTH_MULTIPLIER = 2;
+
+
+int
+vector_new_with(
+	const size_t capacity,
+	const size_t max_capacity,
+	const size_t multiplier,
+	const size_t value_size,
+	struct Vector **const out
+) {
+	int rc = -1;
+
+	struct Vector v = {
+		.values       = NULL,
+		.capacity     = capacity,
+		.back_count   = 0U,
+		.front_count  = 0U,
+		.max_capacity = max_capacity,
+		.multiplier   = multiplier,
+		.value_size   = value_size,
+	};
+	struct Vector *restrict vref = NULL;
+
+	assert(capacity > 0);
+	if (capacity > max_capacity) {
+		logerr(
+			_(MSG_ERR_VECTOR_MAX_CAPACITY),
+			max_capacity,
+			strerror(EOVERFLOW)
+		);
+		rc = EOVERFLOW;
+		goto out;
+	}
+
+	const size_t array_bytes_size = capacity * value_size;
+	v.values = malloc(array_bytes_size);
+	if (v.values == NULL) {
+		logerr("malloc(%ld): %s\n", array_bytes_size, strerror(errno));
+		goto out;
+	}
+
+	vref = malloc(sizeof(*vref));
+	if (vref == NULL) {
+		logerr("malloc(%ld): %s\n", sizeof(vref), strerror(errno));
+		goto out;
+	}
+	memcpy(vref, &v, sizeof(v));
+
+	*out = vref;
+	rc = 0;
+out:
+	if (rc) {
+		if (vref != NULL) {
+			free(vref);
+		}
+		if (v.values != NULL) {
+			free(v.values);
+		}
+	}
+	return rc;
+}
+
+int
+vector_new(const size_t value_size, struct Vector **const out) {
+	return vector_new_with(
+		VECTOR_DEFAULT_CAPACITY,
+		VECTOR_MAX_CAPACITY,
+		GROWTH_MULTIPLIER,
+		value_size,
+		out
+	);
+}
+
+void
+vector_free(const struct Vector *const v) {
+	assert(v != NULL);
+	free(v->values);
+	free((void *)v);
+}
+
+size_t
+vector_count(const struct Vector *const v) {
+	const size_t count = v->back_count + v->front_count;
+	assert(count <= v->capacity);
+	return count;
+}
+
+int
+vector_nth(const struct Vector *const v, const size_t idx, const void **const out) {
+	int rc = -1;
+
+	const size_t count = vector_count(v);
+	if (idx >= count) {
+		logerr(_(MSG_ERR_VECTOR_OUT_OF_BOUNDS), idx, count);
+		goto out;
+	}
+
+	*out = v->values[idx]; // FIXME
+	rc = 0;
+out:
+	return rc;
+}
+
+static size_t
+next_capacity(const struct Vector *const v) {
+	if (v->capacity > v->max_capacity / v->multiplier) {
+		return v->max_capacity;
+	} else {
+		return v->capacity * v->multiplier;
+	}
+}
+
+int
+vector_push_back(struct Vector *const v, void *const value) {
+	int rc = -1;
+
+	void *new_values = NULL;
+
+	const size_t count = vector_count(v);
+	if (count == v->capacity) {
+		if (count == v->max_capacity) {
+			logerr(
+				_(MSG_ERR_VECTOR_MAX_CAPACITY),
+				v->max_capacity,
+				strerror(EOVERFLOW)
+			);
+			rc = EOVERFLOW;
+			goto out;
+		}
+
+		const size_t new_capacity = next_capacity(v);
+		const size_t new_size = new_capacity * v->value_size;
+		new_values = realloc(v->values, new_size);
+		if (new_values == NULL) {
+			logerr(
+				"realloc(v->values, %ld): %s\n",
+				new_size,
+				strerror(errno)
+			);
+			goto out;
+		}
+		v->capacity = new_capacity;
+		v->values   = new_values;
+	}
+
+	v->values[v->back_count] = value;
+	v->back_count++;
+	rc = 0;
+out:
+	if (rc) {
+		if (new_values != NULL) {
+			free(new_values);
+		}
+	}
+	return rc;
+}
+
+int
+vector_push_front(struct Vector *const v, void *const value) {
+	int rc = -1;
+
+	void *new_values = NULL;
+
+	const size_t count = vector_count(v);
+	if (count == v->capacity) {
+		if (count == v->max_capacity) {
+			logerr(
+				_(MSG_ERR_VECTOR_MAX_CAPACITY),
+				v->max_capacity,
+				strerror(EOVERFLOW)
+			);
+		}
+
+		const size_t new_capacity = next_capacity(v);
+		const size_t new_size = new_capacity * v->value_size;
+		new_values = realloc(v->values, new_size);
+		if (new_values == NULL) {
+			logerr(
+				"realloc(v->values, %ld): %s\n",
+				new_size,
+				strerror(errno)
+			);
+			goto out;
+		}
+		v->capacity = new_capacity;
+		// FIXME: copy, but leaving things at the beginning
+	}
+
+	v->values[v->front_count] = value;
+	v->front_count++;
+	rc = 0;
+out:
+	if (rc) {
+		if (new_values != NULL) {
+			free(new_values);
+		}
+	}
+	return rc;
+}
+
+int
+vector_pop_back(struct Vector *const v, const void **const out) {
+	int rc = -1;
+
+	const size_t count = vector_count(v);
+	if (count == 0) {
+		logerr(_(MSG_ERR_VECTOR_UNDERFLOW));
+		goto out;
+	}
+
+	*out = v->values[v->back_count - 1]; // FIXME: can become negative!
+	v->back_count--;
+	rc = 0;
+out:
+	return rc;
+}
+
+int
+vector_pop_front(struct Vector *const v, const void **const out) {
+	int rc = -1;
+
+	const size_t count = vector_count(v);
+	if (count == 0) {
+		logerr(_(MSG_ERR_VECTOR_UNDERFLOW));
+		goto out;
+	}
+
+	*out = v->values[v->front_count - 1]; // FIXME: can become negative!
+	v->front_count--;
+	rc = 0;
+out:
+	return rc;
+}
diff --git a/src/vector.h b/src/vector.h
new file mode 100644
index 0000000..cc3c96a
--- /dev/null
+++ b/src/vector.h
@@ -0,0 +1,29 @@
+struct Vector;
+
+
+int
+vector_new(const size_t value_size, struct Vector **out);
+
+int
+vector_new_with(
+	const size_t capacity,
+	const size_t max_capacity,
+	const size_t multiplier,
+	const size_t value_size,
+	struct Vector **out
+);
+
+void
+vector_free(const struct Vector *const v);
+
+size_t
+vector_count(const struct Vector *v);
+
+int
+vector_nth(const struct Vector *const v, const size_t idx, const void **const out);
+
+int
+vector_push_back(struct Vector *const v, void *const value);
+
+int
+vector_pop_back(struct Vector *const v, const void **const out);
diff --git a/tests/vector.c b/tests/vector.c
new file mode 100644
index 0000000..74bffc7
--- /dev/null
+++ b/tests/vector.c
@@ -0,0 +1,458 @@
+#include "../src/vector.c"
+
+#include <assert.h>
+#include <errno.h>
+#include <locale.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+
+#include "../src/testing.h"
+
+
+static int
+test_vector_new_with(void) {
+	int rc = -1;
+
+	struct Vector *v = NULL;
+
+	test_start("vector_new_with()");
+	{
+		testing("allocating struct Vector with small capacity");
+
+		const size_t capacity     = 1U;
+		const size_t max_capacity = 2U;
+		const size_t multiplier   = 3U;
+		const size_t size         = 4U;
+
+		if (vector_new_with(
+			capacity,
+			max_capacity,
+			multiplier,
+			size,
+			&v
+		)) {
+			logerr("vector_new_with()");
+			goto out;
+		}
+
+		assert(v->capacity     == capacity);
+		assert(v->back_count   == 0U);
+		assert(v->front_count  == 0U);
+		assert(v->max_capacity == max_capacity);
+		assert(v->multiplier   == multiplier);
+		assert(v->value_size   == size);
+
+		vector_free(v);
+		v = NULL;
+
+		test_ok();
+	}
+	{
+		testing("we can't ask for a capacity beyond max_capacity");
+
+		const size_t max_capacity = 2U;
+
+		assert(v == NULL);
+		assert(vector_new_with(
+			max_capacity + 1,
+			max_capacity,
+			1U,
+			1U,
+			&v
+		) == EOVERFLOW);
+		assert(v == NULL);
+
+		test_ok();
+	}
+
+	rc = 0;
+out:
+	if (v != NULL) {
+		vector_free(v);
+		v = NULL;
+	}
+	return rc;
+}
+
+
+static int
+test_vector_new(void) {
+	int rc = -1;
+
+	struct Vector *v = NULL;
+
+	test_start("vector_new()");
+	{
+		testing("simple allocation of int[]");
+
+		const size_t size = sizeof(int);
+		if (vector_new(size, &v)) {
+			logerr("vector_new()");
+			goto out;
+		}
+
+		assert(v->capacity     == VECTOR_DEFAULT_CAPACITY);
+		assert(v->back_count   == 0);
+		assert(v->front_count  == 0);
+		assert(v->max_capacity == VECTOR_MAX_CAPACITY);
+		assert(v->multiplier   == GROWTH_MULTIPLIER);
+		assert(v->value_size   == size);
+
+		vector_free(v);
+		v = NULL;
+
+		test_ok();
+	}
+	{
+		testing("simple allocation of custom struct");
+
+		struct Custom {
+			int a;
+			char b;
+			void *c;
+		} custom;
+
+		const size_t size = sizeof(custom);
+		if (vector_new(size, &v)) {
+			logerr("vector_new()");
+			goto out;
+		}
+
+		assert(v->capacity     == VECTOR_DEFAULT_CAPACITY);
+		assert(v->back_count   == 0);
+		assert(v->front_count  == 0);
+		assert(v->max_capacity == VECTOR_MAX_CAPACITY);
+		assert(v->multiplier   == GROWTH_MULTIPLIER);
+		assert(v->value_size   == size);
+
+		vector_free(v);
+		v = NULL;
+
+		test_ok();
+	}
+
+	rc = 0;
+out:
+	if (v != NULL) {
+		vector_free(v);
+		v = NULL;
+	}
+	return rc;
+}
+
+static int
+test_vector_free(void) {
+	int rc = -1;
+
+	struct Vector *v = NULL;
+
+	test_start("vector_free()");
+	{
+		testing("*v becomes NULL again after vector_free(&v)");
+		assert(v == NULL);
+		if (vector_new(sizeof(char), &v)) {
+			logerr("vector_new()");
+			goto out;
+		}
+
+		assert(v != NULL);
+		vector_free(v);
+		v = NULL;
+
+		test_ok();
+	}
+
+	rc = 0;
+out:
+	return rc;
+}
+
+static int
+test_vector_count(void) {
+	int rc = -1;
+
+	struct Vector *v = NULL;
+
+	test_start("vector_count()");
+	{
+		testing("we get whatever the count is");
+
+		if (vector_new(sizeof(unsigned long), &v)) {
+			logerr("vector_new()");
+			goto out;
+		}
+
+		assert(vector_count(v) == 0);
+		assert(v->back_count   == 0);
+		assert(v->front_count  == 0);
+
+		if (vector_push_back(v, (void *)123)) {
+			logerr("vector_push_back()");
+			goto out;
+		}
+
+		assert(vector_count(v) == 1);
+		assert(v->back_count   == 1);
+		assert(v->front_count  == 0);
+
+		vector_free(v);
+		v = NULL;
+
+		test_ok();
+	}
+
+	rc = 0;
+out:
+	if (v != NULL) {
+		vector_free(v);
+		v = NULL;
+	}
+	return rc;
+}
+
+static int
+test_vector_nth(void) {
+	int rc = -1;
+
+	struct Vector *v = NULL;
+	int first  = 123;
+	int second = 321;
+	int third  = 555;
+	// const int values[] = { first, second, third };
+	int values[] = { first, second, third };
+	const size_t values_len = sizeof(values) / sizeof(values[0]);
+
+	return 0;
+	test_start("vector_nth()");
+	{
+		testing("nth with growth");
+
+		if (vector_new(sizeof(int), &v)) {
+			logerr("vector_new_with()");
+			goto out;
+		}
+
+		for (unsigned int i = 0; i < values_len; i++) {
+			if (vector_push_back(v, &values[i])) {
+				logerr("vector_push_back(v, values[%d])", i);
+				goto out;
+			}
+		}
+
+		int ret;
+
+		assert(vector_nth(v, 0U, (void *)&ret) == 0);
+		assert(ret == 123);
+		assert(vector_nth(v, 1U, (void *)&ret) == 0);
+		assert(ret == 321);
+		assert(vector_nth(v, 2U, (void *)&ret) == 0);
+		assert(ret == 555);
+
+		vector_free(v);
+		v = NULL;
+
+		test_ok();
+	}
+	{
+		testing("nth out of bounds errors");
+
+		if (vector_new(sizeof(int), &v)) {
+			logerr("vector_new_with()");
+			goto out;
+		}
+
+		for (unsigned int i = 0; i < values_len; i++) {
+			if (vector_push_back(v, &values[i])) {
+				logerr("vector_push_back(v, values[%d])", i);
+				goto out;
+			}
+		}
+
+		int ret = 222;
+		assert(vector_nth(v, 4U, (void *)&ret) == -1);
+		assert(ret == 222);
+
+		vector_free(v);
+		v = NULL;
+
+		test_ok();
+	}
+
+	rc = 0;
+out:
+	if (v != NULL) {
+		vector_free(v);
+		v = NULL;
+	}
+	return rc;
+}
+
+static void
+test_next_capacity(void) {
+	test_start("next_capacity()");
+}
+
+static int
+test_vector_push_back(void) {
+	int rc = -1;
+
+	struct Vector *v = NULL;
+
+	test_start("vector_push_back()");
+	{
+		testing("a single push back overwrites existing garbage");
+
+		if (vector_new(sizeof(long long), &v)) {
+			logerr("vector_new()");
+			goto out;
+		}
+
+		long long before = 123;
+		long long after  = 321;
+		v->values[0] = &before;
+		if (vector_push_back(v, &after)) {
+			logerr("vector_push_back()");
+			goto out;
+		}
+		assert(v->values[0] == &after);
+
+		vector_free(v);
+		v = NULL;
+
+		test_ok();
+	}
+	{
+		testing("push back beyond capacity causes reallocation");
+
+		unsigned long data = 2222U;
+
+		if (vector_new(sizeof(unsigned long), &v)) {
+			logerr("vector_new()");
+			goto out;
+		}
+		assert(v->capacity     == VECTOR_DEFAULT_CAPACITY);
+		assert(vector_count(v) == 0);
+
+		for (unsigned int i = 0; i < v->capacity; i++) {
+			if (vector_push_back(v, &data)) {
+				logerr("vector_push_back(): i = %d", i);
+				goto out;
+			}
+		}
+
+		assert(v->capacity  == vector_count(v));
+		assert(v->values[0] == (void *)data);
+
+		if (vector_push_back(v, &data)) {
+			logerr("vector_push_vack()");
+			goto out;
+		}
+		assert(v->capacity     == (v->capacity * v->multiplier));
+		assert(vector_count(v) == v->capacity);
+		assert(v->values[1]    == &data);
+
+		if (vector_push_back(v, &data)) {
+			logerr("vector_push_back()");
+			goto out;
+		}
+		assert(v->capacity  == 4);
+		// assert(v->count     == 3);
+		assert(v->values[2] == &data);
+
+		assert(vector_push_back(v, &data) == 0);
+		assert(v->capacity  == 4);
+		// assert(v->count     == 4);
+		assert(v->values[3] == &data);
+
+		vector_free(v);
+		v = NULL;
+
+		test_ok();
+	}
+
+	rc = 0;
+out:
+	if (v != NULL) {
+		vector_free(v);
+		v = NULL;
+	}
+	return rc;
+}
+
+static int
+test_vector_push_front(void) {
+	test_start("vector_push_front()");
+	return 0;
+}
+
+static int
+test_vector_pop_back(void) {
+	test_start("vector_pop_back()");
+	return 0;
+}
+
+static int
+test_vector_pop_front(void) {
+	test_start("vector_pop_front()");
+	return 0;
+}
+
+
+int
+main(void) {
+	int rc = -1;
+
+	if (test_vector_new_with()) {
+		logerr("test_vector_new_with()");
+		goto out;
+	}
+
+	if (test_vector_new()) {
+		logerr("test_vector_new()");
+		goto out;
+	}
+
+	if (test_vector_free()) {
+		logerr("test_vector_free()");
+		goto out;
+	}
+
+	if (test_vector_count()) {
+		logerr("test_vector_count()");
+		goto out;
+	}
+
+	if (test_vector_nth()) {
+		logerr("test_vector_nth()");
+		goto out;
+	}
+
+	return 0;
+	test_next_capacity();
+
+	if (test_vector_push_back()) {
+		logerr("test_vector_push_back()");
+		goto out;
+	}
+
+	if (test_vector_push_front()) {
+		logerr("test_vector_push_front()");
+		goto out;
+	}
+
+	if (test_vector_pop_back()) {
+		logerr("test_vector_pop_back()");
+		goto out;
+	}
+
+	if (test_vector_pop_front()) {
+		logerr("test_vector_pop_front()");
+		goto out;
+	}
+
+	rc = 0;
+out:
+	return !!rc;
+}