Added header files implementing a basic AVL tree and Map based off it.

These headers take inspiration from the linked list and array list
headers as a way to provide primitive templates in C. This time
they implement an AVL tree and Map template (which uses the AVL tree).

Included are relatively robust tests, though they could be improved.

2 files changed, 262 insertions, 0 deletions

diff --git a/tests/test_avl_tree.c b/tests/test_avl_tree.c
new file mode 100644
index 0000000..2a7260f
--- /dev/null
+++ b/tests/test_avl_tree.c
@@ -0,0 +1,149 @@
+#include "shared/avl_tree.h"
+#include "test_harness.h"
+
+#define integer_cmp_(a, b) (a - b)
+AVL_TREE_DECL(int);
+AVL_TREE_IMPL(int, integer_cmp_, null_dtor);
+
+static inline void avl_tree_debug_print(avl_tree_node_t(int) * node, int tab)
+{
+  if (node) {
+    avl_tree_debug_print(node->right, tab + 1);
+  }
+  for (int i = 0; i < tab; ++i) {
+    printf(" ");
+  }
+  if (!node) {
+    printf("(nil)\n");
+    return;
+  }
+  printf("%d\n", node->value);
+  avl_tree_debug_print(node->left, tab + 1);
+}
+
+TEST(avl_tree, insert)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+  avl_tree_insert(int)(tree, 5);
+
+  ASSERT_EQ(avl_tree_size(int)(tree), 1);
+
+  avl_tree_insert(int)(tree, 4);
+  avl_tree_insert(int)(tree, 6);
+
+  ASSERT_EQ(avl_tree_size(int)(tree), 3);
+  ASSERT_EQ(avl_tree_height(int)(tree), 2);
+
+  return 0;
+}
+
+TEST(avl_tree, insert_rotate_asc)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+
+  avl_tree_insert(int)(tree, 1);
+  avl_tree_insert(int)(tree, 2);
+  avl_tree_insert(int)(tree, 3);
+  avl_tree_insert(int)(tree, 4);
+
+  ASSERT_EQ(avl_tree_size(int)(tree), 4);
+  ASSERT_EQ(avl_tree_height(int)(tree), 3);
+
+  return 0;
+}
+
+TEST(avl_tree, insert_rotate_desc)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+
+  avl_tree_insert(int)(tree, 4);
+  avl_tree_insert(int)(tree, 3);
+  avl_tree_insert(int)(tree, 2);
+  avl_tree_insert(int)(tree, 1);
+
+  ASSERT_EQ(avl_tree_size(int)(tree), 4);
+  ASSERT_EQ(avl_tree_height(int)(tree), 3);
+
+  return 0;
+}
+
+TEST(avl_tree_erase, erase)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+
+  avl_tree_insert(int)(tree, 4);
+  avl_tree_insert(int)(tree, 3);
+  avl_tree_insert(int)(tree, 2);
+  avl_tree_insert(int)(tree, 1);
+
+  ASSERT_EQ(avl_tree_size(int)(tree), 4);
+  ASSERT_EQ(avl_tree_height(int)(tree), 3);
+
+  int out;
+  bool b = avl_tree_erase(int)(tree, 3, &out);
+
+  ASSERT_EQ(b, 1);
+  ASSERT_EQ(out, 3);
+  ASSERT_EQ(avl_tree_size(int)(tree), 3);
+  ASSERT_EQ(avl_tree_height(int)(tree), 2);
+
+  b = avl_tree_erase(int)(tree, 1, &out);
+
+  ASSERT_EQ(b, 1);
+  ASSERT_EQ(out, 1);
+  ASSERT_EQ(avl_tree_size(int)(tree), 2);
+  ASSERT_EQ(avl_tree_height(int)(tree), 2);
+
+  return 0;
+}
+
+TEST(avl_tree, erase_onesided)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+  for (int i = 0; i < 16; ++i) {
+    avl_tree_insert(int)(tree, i);
+  }
+
+  ASSERT_EQ(avl_tree_erase(int)(tree, 0, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 1, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 2, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 3, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 4, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 5, NULL), 1);
+  ASSERT_EQ(avl_tree_erase(int)(tree, 6, NULL), 1);
+
+  ASSERT_EQ(avl_tree_height(int)(tree), 4);
+  ASSERT_EQ(avl_tree_size(int)(tree), 9);
+
+  avl_tree_free(int)(tree);
+  ASSERT_TRUE(debug_is_heap_empty());
+
+  return 0;
+}
+
+TEST(avl_tree, find)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+
+  for (int i = 0; i < 16; ++ i) {
+    avl_tree_insert(int)(tree, i);
+  }
+
+  ASSERT_EQ(*avl_tree_find(int)(tree, 4), 4);
+  ASSERT_EQ(*avl_tree_find(int)(tree, 3), 3);
+  ASSERT_EQ(*avl_tree_find(int)(tree, 15), 15);
+
+  ASSERT_EQ(avl_tree_find(int)(tree, 100), NULL);
+
+  return 0;
+}
+
+TEST (avl_tree, stress)
+{
+  avl_tree_t(int)* tree = avl_tree_new(int)();
+  for (int i = 0; i < 512; ++ i) {
+    avl_tree_insert(int)(tree, i);
+  }
+
+  return 0;
+}
diff --git a/tests/test_map.c b/tests/test_map.c
new file mode 100644
index 0000000..29704f0
--- /dev/null
+++ b/tests/test_map.c
@@ -0,0 +1,113 @@
+#include <stdlib.h>
+
+#include "shared/map.h"
+#include "test_harness.h"
+
+typedef const char* const_char_ptr;
+
+#define integer_cmp_(a, b) (a - b)
+MAP_DECL(int, const_char_ptr);
+MAP_IMPL(int, const_char_ptr, integer_cmp_, null_dtor);
+
+TEST(map, smoke)
+{
+  map_t(int, const_char_ptr)* map = map_new(int, const_char_ptr)();
+
+  map_put(int, const_char_ptr)(map, 6, "string1");
+  map_put(int, const_char_ptr)(map, 8, "string2");
+  map_put(int, const_char_ptr)(map, 9, "string3");
+
+  const char* str = *map_get(int, const_char_ptr)(map, 8);
+  ASSERT_EQ_STR(str, "string2");
+
+  str = *map_get(int, const_char_ptr)(map, 9);
+  ASSERT_EQ_STR(str, "string3");
+  ASSERT_EQ(map_get(int, const_char_ptr)(map, 20), NULL);
+
+  map_free(int, const_char_ptr)(map);
+  ASSERT_TRUE(debug_is_heap_empty());
+  return 0;
+}
+
+typedef uint32_t* int_ptr;
+MAP_DECL(int, int_ptr);
+MAP_IMPL(int, int_ptr, integer_cmp_, kfree);
+
+static inline void loose_map_print(
+    avl_tree_node_t(map_entry_t(int, int_ptr))* node,
+    int tab) {
+  if (node) {
+    loose_map_print(node->right, tab + 1);
+  }
+  for (int i = 0; i < tab; ++i) {
+    printf(" ");
+  }
+  if (!node) {
+    printf("(nil)\n");
+    return;
+  }
+  printf("(%d => %d)\n", node->value.key, *node->value.value);
+  loose_map_print(node->left, tab + 1);
+}
+static inline void map_debug_print(
+    map_t(int, int_ptr) * map)
+{
+  printf("------\n");
+  if (map->tree) {
+    loose_map_print(map->tree->root, 0);
+  }
+  printf("------\n");
+}
+TEST(map, stress)
+{
+#define N 256
+  uint32_t* arr[N];
+  memset(arr, 0, sizeof(arr));
+  map_t(int, int_ptr)* map = map_new(int, int_ptr)();
+
+  for (int i = 0; i < N; ++i) {
+    uint32_t* a = kalloc(sizeof(uint32_t));
+    *a = rand();
+    arr[i] = a;
+  }
+
+  for (int i = 0; i < N; ++i) {
+    map_put(int, int_ptr)(map, i, arr[i]);
+  }
+
+  for (int i = 0; i < N; ++i) {
+    uint32_t** ptr = map_get(int, int_ptr)(map, i);
+    ASSERT_TRUE(ptr != NULL);
+    ASSERT_TRUE(*ptr != NULL);
+    ASSERT_EQ(**ptr, *arr[i]);
+  }
+
+  int erased[N];
+  memset(erased, 0, sizeof(erased));
+
+  for (int i = 0; i < (N / 2); ++i) {
+    int_ptr out;
+    int e = rand() % N;
+    if (map_erase(int, int_ptr)(map, e, &out)) {
+      ASSERT_EQ(*out, *arr[e]);
+      arr[e] = NULL;
+      kfree(out);
+    }
+    erased[e] = 1;
+  }
+
+  for (int i = 0; i < N; ++ i) {
+    if (erased[i]) {
+      continue;
+    }
+    uint32_t** ptr = map_get(int, int_ptr)(map, i);
+    ASSERT_TRUE(ptr != NULL);
+    ASSERT_TRUE(*ptr != NULL);
+    ASSERT_EQ(**ptr, *arr[i]);
+  }
+
+  map_free(int, int_ptr)(map);
+  ASSERT_TRUE(debug_is_heap_empty());
+
+  return 0;
+}