util: Implement dynamic vector array for storing AST children

Previously, we lacked a dynamic array for storing children elements in
our abstract syntax tree (AST). This commit introduces a new
implementation that dynamically adjusts its capacity as elements are
added, using a doubling strategy.

I considered two approaches for managing the vector's memory
allocation: allocating it on the heap, or providing a vector_init
function that allocates only the items array. Ultimately, I decided to
provide a vector_new function for instantiating the vector, as this
aligns with the expected usage pattern when there is a destroy function.

With this new implementation, we can efficiently store and manage AST
children, enabling more flexible and expressive tree structures.

Signed-off-by: Johnny Richard <johnny@johnnyrichard.com>

2 files changed, 118 insertions, 0 deletions

diff --git a/test/Makefile b/test/Makefile
index 1858166..09adcfb 100644
--- a/test/Makefile
+++ b/test/Makefile
@@ -17,6 +17,9 @@ clean:
 string_view_test: munit.o ../build/string_view.o string_view_test.o
 	$(CC) $? $(CFLAGS) -o $@
 
+vector_test: munit.o ../build/vector.o vector_test.o
+	$(CC) $? $(CFLAGS) -o $@
+
 lexer_test: munit.o ../build/string_view.o ../build/lexer.o lexer_test.o
 	$(CC) $? $(CFLAGS) -o $@
 
diff --git a/test/vector_test.c b/test/vector_test.c
new file mode 100644
index 0000000..e327735
--- /dev/null
+++ b/test/vector_test.c
@@ -0,0 +1,115 @@
+/*
+* Copyright (C) 2023 Johnny Richard
+*
+* This program is free software: you can redistribute it and/or modify
+* it under the terms of the GNU General Public License as published by
+* the Free Software Foundation, either version 3 of the License, or
+* (at your option) any later version.
+*
+* This program is distributed in the hope that it will be useful,
+* but WITHOUT ANY WARRANTY; without even the implied warranty of
+* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+* GNU General Public License for more details.
+*
+* You should have received a copy of the GNU General Public License
+* along with this program.  If not, see <https://www.gnu.org/licenses/>.
+*/
+#define MUNIT_ENABLE_ASSERT_ALIASES
+#include "munit.h"
+#include "vector.h"
+
+static MunitResult
+test_create_new(const  MunitParameter params[],
+                void  *user_data_or_fixture)
+{
+  vector_t *vec = vector_new();
+
+  assert_not_null(vec);
+  assert_int(vec->capacity, ==, VECTOR_INITIAL_CAPACITY);
+  assert_int(vec->size, ==, 0);
+
+  // assert we have allocated memory for full capacity
+
+  int items[VECTOR_INITIAL_CAPACITY];
+
+  for (int i = 0; i < VECTOR_INITIAL_CAPACITY; ++i) {
+    items[i] = 1;
+    vec->items[i] = &items[i];
+  }
+
+  for (int i = 0; i < VECTOR_INITIAL_CAPACITY; ++i) {
+    assert_int(*((int *)vec->items[i]), ==, 1);
+  }
+
+  vector_destroy(vec);
+
+  return MUNIT_OK;
+}
+
+static MunitResult
+test_push_back(const  MunitParameter params[],
+               void  *user_data_or_fixture)
+{
+  vector_t *vec = vector_new();
+
+  int number1 = 1;
+  int number2 = 2;
+
+  vector_push_back(vec, (void *) &number1);
+  vector_push_back(vec, (void *) &number2);
+
+  assert_int(vec->size, ==, 2);
+  assert_int(*((int *) vector_at(vec, 0)), ==, number1);
+  assert_int(*((int *) vector_at(vec, 1)), ==, number2);
+
+  vector_destroy(vec);
+
+  return MUNIT_OK;
+}
+
+static MunitResult
+test_vector_push_back_until_resize(const  MunitParameter params[],
+                                   void  *user_data_or_fixture)
+{
+  vector_t *vec = vector_new();
+
+  int items[VECTOR_INITIAL_CAPACITY + 1];
+
+  for (int i = 0; i < VECTOR_INITIAL_CAPACITY; ++i) {
+    items[i] = 1;
+    vector_push_back(vec, (void *) &items[i]);
+  }
+
+  items[VECTOR_INITIAL_CAPACITY] = 1;
+  vector_push_back(vec, (void *) &items[VECTOR_INITIAL_CAPACITY]);
+
+  assert_int(vec->size, ==, VECTOR_INITIAL_CAPACITY + 1);
+  assert_int(vec->capacity, ==, VECTOR_INITIAL_CAPACITY * 2);
+
+  for (int i = 0; i < vec->size; ++i) {
+    assert_int(*((int *) vec->items[i]), ==, 1);
+  }
+
+  vector_destroy(vec);
+
+  return MUNIT_OK;
+}
+
+static MunitTest tests[] = {
+  { "/test_create_new", test_create_new, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+  { "/test_push_back", test_push_back, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+  { "/test_vector_push_back_until_resize", test_vector_push_back_until_resize, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL },
+
+  { NULL, NULL, NULL, NULL, MUNIT_TEST_OPTION_NONE, NULL }
+};
+
+static const MunitSuite suite = {
+  "/vector", tests, NULL, 1, MUNIT_SUITE_OPTION_NONE
+};
+
+int
+main(int argc, char *argv[])
+{
+  return munit_suite_main(&suite, NULL, argc, argv);
+  return EXIT_SUCCESS;
+}