lander/lsm/test/bt/bt.c

#include "test.h"
#include "lsm/bt_internal.h"

#define BT_INIT() \
  lsm_bt *bt; \
  TEST_CHECK(lsm_bt_init(&bt) == lsm_error_ok); \
  TEST_CHECK(bt != NULL)

void test_init() {
  BT_INIT();
  lsm_bt_free(bt);
}

void test_insert_first() {
  BT_INIT();

  TEST_CHECK(lsm_bt_insert(bt, 'a', (void *)1) == lsm_error_ok);
  TEST_CHECK(lsm_bt_insert(bt, 'a', (void *)1) == lsm_error_already_present);

  void *data;
  TEST_CHECK(lsm_bt_search(&data, bt, 'a') == lsm_error_ok);
  TEST_CHECK(data == (void *)1);

  TEST_CHECK(lsm_bt_search(&data, bt, 'b') == lsm_error_not_found);

  lsm_bt_free(bt);
}

void test_insert_two() {
  BT_INIT();

  TEST_CHECK(lsm_bt_insert(bt, 'a', (void *)1) == lsm_error_ok);
  TEST_CHECK(lsm_bt_insert(bt, 'a', (void *)1) == lsm_error_already_present);
  TEST_CHECK(lsm_bt_insert(bt, 'b', (void *)2) == lsm_error_ok);
  TEST_CHECK(lsm_bt_insert(bt, 'b', (void *)2) == lsm_error_already_present);

  void *data;
  TEST_CHECK(lsm_bt_search(&data, bt, 'a') == lsm_error_ok);
  TEST_CHECK(data == (void *)1);
  TEST_CHECK(lsm_bt_search(&data, bt, 'b') == lsm_error_ok);
  TEST_CHECK(data == (void *)2);
  TEST_CHECK(lsm_bt_search(&data, bt, 'c') == lsm_error_not_found);

  lsm_bt_free(bt);
}

void test_insert_multiple() {
  char chars[] = "falcoep";
  size_t char_count = sizeof(chars) / sizeof(char);

  BT_INIT();

  for (size_t i = 0; i < char_count; i++) {
    TEST_CHECK(lsm_bt_insert(bt, chars[i], (void *)(i + 1)) == lsm_error_ok);
  }

  TEST_CHECK(lsm_bt_size(bt) == char_count);

  void *data;
  for (size_t i = 0; i < char_count; i++) {
    TEST_CHECK(lsm_bt_insert(bt, chars[i], (void *)(i + 1)) == lsm_error_already_present);
    TEST_CHECK(lsm_bt_search(&data, bt, chars[i]) == lsm_error_ok);
    TEST_CHECK(data == (void *)(i + 1));
  }

  lsm_bt_free(bt);
}

void test_remove_root() {
  BT_INIT();

  TEST_CHECK(lsm_bt_insert(bt, 'a', (void *)1) == lsm_error_ok);
  TEST_CHECK(lsm_bt_size(bt) == 1);

  void *data;
  TEST_CHECK(lsm_bt_remove(&data, bt, 'a') == lsm_error_ok);
  TEST_CHECK(data == (void *)1);
  TEST_CHECK(bt->root == NULL);
  TEST_CHECK(lsm_bt_size(bt) == 0);

  lsm_bt_free(bt);
}

void test_remove_multiple() {
  char chars[] = "falcoep";
  size_t char_count = sizeof(chars) / sizeof(char);

  BT_INIT();

  for (size_t i = 0; i < char_count; i++) {
    TEST_CHECK(lsm_bt_insert(bt, chars[i], (void *)(i + 1)) == lsm_error_ok);
  }

  void *data;
  TEST_CHECK(lsm_bt_remove(&data, bt, 'l') == lsm_error_ok);
  TEST_CHECK(data == (void *)3);
  TEST_CHECK(lsm_bt_remove(&data, bt, 'l') == lsm_error_not_found);
  TEST_CHECK(lsm_bt_remove(&data, bt, 'e') == lsm_error_ok);
  TEST_CHECK(data == (void *)6);
  TEST_CHECK(lsm_bt_remove(&data, bt, 'e') == lsm_error_not_found);

  TEST_CHECK(lsm_bt_size(bt) == char_count - 2);

  lsm_bt_free(bt);
}

void test_iter() {
  char chars[] = "falcoep";
  size_t char_count = sizeof(chars) / sizeof(char) - 1;

  char sorted_chars[] = "aceflop";

  BT_INIT();

  for (size_t i = 0; i < char_count; i++) {
    TEST_CHECK(lsm_bt_insert(bt, chars[i], (void *)(i + 1)) == lsm_error_ok);
  }

  lsm_bt_iterator iter;
  lsm_bt_iter(&iter, bt);

  char key;
  void *data;
  size_t i = 0;

  while (lsm_bt_iter_next(&data, &key, &iter)) {
    TEST_CHECK_(key == sorted_chars[i], "%c == %c", key, sorted_chars[i]);
    i++;
  }

  TEST_CHECK(i == char_count);
}

TEST_LIST = {
  { "bt init", test_init },
  { "bt insert first", test_insert_first },
  { "bt insert two", test_insert_two },
  { "bt insert multiple", test_insert_multiple },
  { "bt remove root", test_remove_root },
  { "bt remove multiple", test_remove_multiple },
  { "bt iter", test_iter },
  { NULL, NULL }
};