/* 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();
}