1 files changed, 161 insertions, 0 deletions

diff --git a/tests/t_vector.c b/tests/t_vector.c
new file mode 100644
index 0000000..fee336b
--- /dev/null
+++ b/tests/t_vector.c
@@ -0,0 +1,161 @@
+/* This software was written by Dirk Engling <erdgeist@erdgeist.org>
+   It is considered beerware. Prost. Skol. Cheers or whatever.
+
+   $id$ */
+
+/* System */
+#include <stdlib.h>
+#include <string.h>
+
+/* Opentracker */
+#include "trackerlogic.h"
+#include "test.h"
+
+/* binary_search returns the matching member when there is one, and otherwise
+   the position at which the key would have to be inserted to keep the vector
+   sorted. exactmatch distinguishes the two. */
+
+static const unsigned char sorted[5][4] = {{0, 0, 0, 1}, {0, 0, 0, 3}, {0, 0, 0, 5}, {0, 0, 0, 7}, {0, 0, 0, 9}};
+
+static void                case_search_finds_member(void) {
+  const unsigned char key[4] = {0, 0, 0, 5};
+  int                 exactmatch;
+  void               *found;
+
+  test_case("an existing key is found");
+  found = binary_search(key, sorted, 5, 4, 4, &exactmatch);
+  CHECK(exactmatch != 0);
+  CHECK_PTR(found, sorted[2]);
+}
+
+static void case_search_finds_first_and_last(void) {
+  const unsigned char first[4] = {0, 0, 0, 1};
+  const unsigned char last[4]  = {0, 0, 0, 9};
+  int                 exactmatch;
+
+  test_case("the first and last members are found");
+  CHECK_PTR(binary_search(first, sorted, 5, 4, 4, &exactmatch), sorted[0]);
+  CHECK(exactmatch != 0);
+  CHECK_PTR(binary_search(last, sorted, 5, 4, 4, &exactmatch), sorted[4]);
+  CHECK(exactmatch != 0);
+}
+
+static void case_search_insert_position(void) {
+  const unsigned char middle[4] = {0, 0, 0, 4};
+  const unsigned char before[4] = {0, 0, 0, 0};
+  int                 exactmatch;
+  void               *slot;
+
+  test_case("a missing key yields its insert position");
+  slot = binary_search(middle, sorted, 5, 4, 4, &exactmatch);
+  CHECK_INT(exactmatch, 0);
+  CHECK_PTR(slot, sorted[2]);
+
+  slot = binary_search(before, sorted, 5, 4, 4, &exactmatch);
+  CHECK_INT(exactmatch, 0);
+  CHECK_PTR(slot, sorted[0]);
+}
+
+static void case_search_past_the_end(void) {
+  const unsigned char beyond[4] = {0, 0, 0, 0xff};
+  int                 exactmatch;
+  void               *slot;
+
+  test_case("a key above every member yields the position past the end");
+  slot = binary_search(beyond, sorted, 5, 4, 4, &exactmatch);
+  CHECK_INT(exactmatch, 0);
+  CHECK_PTR(slot, sorted[5]);
+}
+
+static void case_search_empty(void) {
+  int   exactmatch;
+  void *base = (void *)sorted;
+
+  test_case("searching an empty vector reports no match at the base");
+  CHECK_PTR(binary_search(sorted[0], base, 0, 4, 4, &exactmatch), base);
+  CHECK_INT(exactmatch, 0);
+}
+
+static void case_insert_keeps_order(void) {
+  ot_vector           vector = {NULL, 0, 0};
+  const unsigned char five[4] = {0, 0, 0, 5};
+  const unsigned char one[4]  = {0, 0, 0, 1};
+  const unsigned char nine[4] = {0, 0, 0, 9};
+  int                 exactmatch;
+  void               *slot;
+
+  test_case("inserts land in sorted order and grow the vector");
+  slot = vector_find_or_insert(&vector, (void *)five, 4, 4, &exactmatch);
+  CHECK(slot != NULL);
+  CHECK_INT(exactmatch, 0);
+  memcpy(slot, five, 4);
+  CHECK_INT(vector.size, 1);
+  CHECK_INT(vector.space, OT_VECTOR_MIN_MEMBERS);
+
+  slot = vector_find_or_insert(&vector, (void *)one, 4, 4, &exactmatch);
+  CHECK(slot != NULL);
+  CHECK_INT(exactmatch, 0);
+  memcpy(slot, one, 4);
+  CHECK_INT(vector.size, 2);
+
+  slot = vector_find_or_insert(&vector, (void *)nine, 4, 4, &exactmatch);
+  CHECK(slot != NULL);
+  CHECK_INT(exactmatch, 0);
+  memcpy(slot, nine, 4);
+  CHECK_INT(vector.size, 3);
+  CHECK_INT(vector.space, OT_VECTOR_MIN_MEMBERS * OT_VECTOR_GROW_RATIO);
+
+  CHECK_MEM(vector.data, "\0\0\0\1\0\0\0\5\0\0\0\11", 12);
+
+  free(vector.data);
+}
+
+static void case_insert_finds_existing(void) {
+  ot_vector           vector = {NULL, 0, 0};
+  const unsigned char five[4] = {0, 0, 0, 5};
+  int                 exactmatch;
+  void               *slot, *again;
+
+  test_case("a second insert of the same key returns the existing member");
+  slot = vector_find_or_insert(&vector, (void *)five, 4, 4, &exactmatch);
+  CHECK(slot != NULL);
+  memcpy(slot, five, 4);
+
+  again = vector_find_or_insert(&vector, (void *)five, 4, 4, &exactmatch);
+  CHECK(exactmatch != 0);
+  CHECK_PTR(again, vector.data);
+  CHECK_INT(vector.size, 1);
+
+  free(vector.data);
+}
+
+static void case_insert_compare_prefix(void) {
+  ot_vector     vector = {NULL, 0, 0};
+  unsigned char first[6]  = {1, 2, 3, 0xaa, 0xaa, 0xaa};
+  unsigned char second[6] = {1, 2, 3, 0xbb, 0xbb, 0xbb};
+  int           exactmatch;
+  void         *slot;
+
+  test_case("only the compare prefix decides identity");
+  slot = vector_find_or_insert(&vector, first, 6, 3, &exactmatch);
+  CHECK(slot != NULL);
+  memcpy(slot, first, 6);
+
+  slot = vector_find_or_insert(&vector, second, 6, 3, &exactmatch);
+  CHECK(exactmatch != 0);
+  CHECK_INT(vector.size, 1);
+  CHECK_MEM(slot, first, 6);
+
+  free(vector.data);
+}
+
+void test_vector(void) {
+  case_search_finds_member();
+  case_search_finds_first_and_last();
+  case_search_insert_position();
+  case_search_past_the_end();
+  case_search_empty();
+  case_insert_keeps_order();
+  case_insert_finds_existing();
+  case_insert_compare_prefix();
+}