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.

1 files changed, 15 insertions, 2 deletions

diff --git a/src/kern/mem.c b/src/kern/mem.c
index aa221ff..d7f7dc3 100644
--- a/src/kern/mem.c
+++ b/src/kern/mem.c
@@ -50,7 +50,7 @@ typedef uint64_t ptrint_t;
 typedef uint32_t ptrint_t;
 #endif
 
-#define CANARY ((uint32_t) 0xdeadbeee)
+#define CANARY ((uint32_t)0xdeadbeee)
 #define kalloc_node_in_use(node) ((node)->used_and_canary & 1)
 #define kalloc_node_get_canary(node) ((node)->used_and_canary & (~1))
 #define WORD_SIZE (sizeof(uint32_t))
@@ -153,7 +153,7 @@ static void coalesce(kalloc_node_t* cur)
 
   /* Find the next used block. */
   cur = orig;
-  while (!kalloc_node_in_use(cur) && !kalloc_node_out_of_range(cur)) {
+  while (!kalloc_node_out_of_range(cur) && !kalloc_node_in_use(cur)) {
     cur = kalloc_node_next(cur);
   }
 
@@ -212,6 +212,8 @@ void debug_print_blocks()
   printf("---------------------------\n");
   kalloc_node_t* cur = kalloc_node_at_off(0);
 
+  int total_words = 0;
+  int total_blocks = 0;
   while (!kalloc_node_out_of_range(cur)) {
     printf(
         "header (%04x)@%p {used=%d, size=%5d, prev=%04x, canary=%04x}\n",
@@ -221,8 +223,13 @@ void debug_print_blocks()
         cur->size_words,
         cur->prev,
         kalloc_node_get_canary(cur));
+    total_words += cur->size_words;
+    total_blocks ++;
     cur = kalloc_node_next(cur);
   }
+
+  printf("Total words allocated: %d\n", total_words);
+  printf("Total blocks allocated: %d\n", total_blocks);
 }
 
 /* Tests that we can walk up and down the allocated blocks and that they
@@ -305,4 +312,10 @@ int debug_kalloc_assert_consistency(char* error, size_t len)
   return 1;
 }
 
+int debug_is_heap_empty()
+{
+  return (void*)((uint8_t*)kalloc_start + kalloc_start->size_words * sizeof(uint32_t) + sizeof(kalloc_node_t)) ==
+         (void*)&HEAP_STOP;
+}
+
 #endif