path: root/tests/t_vector.c

/* This software was written by Dirk Engling <erdgeist@erdgeist.org>
   It is considered beerware. Prost. Skol. Cheers or whatever.

   $id$ */

/* System */
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

/* Opentracker */
#include "ot_vector.h"
#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);
}

/* ------------------------------------------------- bucket redistribution */

/* A flat peer list of count distinct v4 peers. The low byte of the index goes
   into the first address byte, so the peers are distinct but arrive in no
   particular order: a list generated in ascending order would come back
   sorted whether or not vector_redistribute_buckets sorted it. */
static void build_flat_peerlist(ot_peerlist *peer_list, size_t count) {
  size_t i;

  memset(peer_list, 0, sizeof(*peer_list));
  peer_list->peers.data  = malloc(count * OT_PEER_SIZE4);
  peer_list->peers.size  = count;
  peer_list->peers.space = count;
  peer_list->peer_count  = count;

  for (i = 0; i < count; ++i) {
    uint8_t *peer = (uint8_t *)peer_list->peers.data + i * OT_PEER_SIZE4;

    memset(peer, 0, OT_PEER_SIZE4);
    peer[0] = (uint8_t)i;
    peer[1] = (uint8_t)(i >> 8);
    peer[2] = (uint8_t)(i >> 16);
    peer[3] = 1;
  }
}

static void case_redistribute_holds_every_peer(void) {
  const size_t count = 513;
  ot_peerlist  peer_list;
  size_t       bucket, total_size = 0, empty = 0, largest = 0;
  ot_vector   *buckets;

  test_case("a peer list past the threshold is split into buckets");
  build_flat_peerlist(&peer_list, count);
  CHECK(peer_list.peers.data != NULL);
  vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4);
  CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 1);
  CHECK_INT(peer_list.peers.size, 16);

  buckets = peer_list.peers.data;
  for (bucket = 0; bucket < peer_list.peers.size; ++bucket) {
    total_size += buckets[bucket].size;
    if (!buckets[bucket].size)
      ++empty;
    if (buckets[bucket].size > largest)
      largest = buckets[bucket].size;
  }

  test_case("no peer is lost on the way");
  CHECK_INT(total_size, count);

  /* The point of the exercise is that a lookup only searches one bucket, so
     a hash that piled everything into one would defeat it. The input and the
     hash are both fixed, so this is not a matter of luck. */
  test_case("and they are spread over the buckets rather than piled up");
  CHECK_INT(empty, 0);
  CHECK(largest < count / 2);

  vector_clean_list(peer_list.peers.data, peer_list.peers.size);
}

static void case_redistribute_sorts_each_bucket(void) {
  const size_t count = 1000;
  ot_peerlist  peer_list;
  size_t       bucket, i, out_of_order = 0;
  ot_vector   *buckets;

  test_case("every bucket comes back sorted, so bsearch can be used on it");
  build_flat_peerlist(&peer_list, count);
  CHECK(peer_list.peers.data != NULL);
  vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4);
  CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 1);

  buckets = peer_list.peers.data;
  for (bucket = 0; bucket < peer_list.peers.size; ++bucket)
    for (i = 1; i < buckets[bucket].size; ++i) {
      const uint8_t *prev = (uint8_t *)buckets[bucket].data + (i - 1) * OT_PEER_SIZE4;
      const uint8_t *next = (uint8_t *)buckets[bucket].data + i * OT_PEER_SIZE4;

      if (memcmp(prev, next, OT_PEER_COMPARE_SIZE4) >= 0)
        ++out_of_order;
    }
  CHECK_INT(out_of_order, 0);

  vector_clean_list(peer_list.peers.data, peer_list.peers.size);
}

static void case_redistribute_below_threshold(void) {
  ot_peerlist peer_list;

  test_case("a small peer list is left flat");
  build_flat_peerlist(&peer_list, 100);
  CHECK(peer_list.peers.data != NULL);
  vector_redistribute_buckets(&peer_list, OT_PEER_SIZE4);
  CHECK_INT(OT_PEERLIST_HASBUCKETS(&peer_list), 0);
  CHECK_INT(peer_list.peers.size, 100);
  free(peer_list.peers.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();
  case_redistribute_holds_every_peer();
  case_redistribute_sorts_each_bucket();
  case_redistribute_below_threshold();
}