aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/arch/x86_64/arch.h2
-rw-r--r--include/kern/common.h1
-rw-r--r--include/kern/mem.h2
-rw-r--r--include/shared/avl_tree.h271
-rw-r--r--include/shared/map.h90
-rw-r--r--include/shared/stdmacro.h7
-rw-r--r--src/kern/mem.c17
-rw-r--r--tests/test_avl_tree.c149
-rw-r--r--tests/test_map.c113
9 files changed, 649 insertions, 3 deletions
diff --git a/include/arch/x86_64/arch.h b/include/arch/x86_64/arch.h
index 1848b58..15ebd6d 100644
--- a/include/arch/x86_64/arch.h
+++ b/include/arch/x86_64/arch.h
@@ -41,6 +41,6 @@
// testing.
#define GHOST_DATA_SEGMENT_SIZE 1200
#define HEAP_START (*(((unsigned char*)SRAM1_BASE) + GHOST_DATA_SEGMENT_SIZE))
-#define HEAP_STOP (*(&HEAP_START + 16384 - GHOST_DATA_SEGMENT_SIZE))
+#define HEAP_STOP (*(&HEAP_START + 49152 - GHOST_DATA_SEGMENT_SIZE))
#endif /* ARCH_H_ */
diff --git a/include/kern/common.h b/include/kern/common.h
index 021229b..0acc9d3 100644
--- a/include/kern/common.h
+++ b/include/kern/common.h
@@ -39,6 +39,7 @@ typedef enum { ENDIANNESS_LITTLE, ENDIANNESS_BIG } endianness_t;
#define ptr2reg(ptr) ((uint32_t)(ptrdiff_t)(ptr))
typedef __IO uint32_t bits_t;
+typedef uint16_t msize_t;
#define regset(reg, mask, val) ((reg) = ((reg) & ~mask) | (val << CTZ(mask)))
diff --git a/include/kern/mem.h b/include/kern/mem.h
index 20b09bb..bc6c4e2 100644
--- a/include/kern/mem.h
+++ b/include/kern/mem.h
@@ -22,6 +22,8 @@ int debug_kalloc_assert_consistency(char* error, size_t len);
void debug_print_blocks();
+int debug_is_heap_empty();
+
#endif
diff --git a/include/shared/avl_tree.h b/include/shared/avl_tree.h
new file mode 100644
index 0000000..98151f2
--- /dev/null
+++ b/include/shared/avl_tree.h
@@ -0,0 +1,271 @@
+#ifndef _SHARED_AVL_TREE_H_
+#define _SHARED_AVL_TREE_H_
+
+#define ALLOC kalloc
+#define FREE kfree
+
+#include <assert.h>
+#include <stdio.h>
+
+#include "kern/mem.h"
+#include "shared/stdmacro.h"
+
+#define get_height(n) ((n) == NULL ? 0 : (n)->height)
+#define max(a, b) ((a) < (b) ? (b) : (a))
+#define reset_height(node) \
+ (node)->height = \
+ (max(get_height((node)->right), get_height((node)->left)) + 1)
+
+#define avl_tree_t(T) CONCAT(avl_tree__, T)
+#define avl_tree_node_t(T) CONCAT(avl_tree_node__, T)
+
+#define avl_tree_new(T) CONCAT(avl_tree_new__, T)
+#define avl_tree_free(T) CONCAT(avl_tree_free__, T)
+#define avl_tree_size(T) CONCAT(avl_tree_size__, T)
+#define avl_tree_insert(T) CONCAT(avl_tree_insert__, T)
+#define avl_tree_find(T) CONCAT(avl_tree_find__, T)
+#define avl_tree_erase(T) CONCAT(avl_tree_erase__, T)
+#define avl_tree_height(T) CONCAT(avl_tree_height__, T)
+
+#define null_dtor(a)
+
+typedef unsigned int bool;
+
+#define AVL_TREE_DECL(T) \
+ typedef struct CONCAT(AVL_TREE_NODE_, T) { \
+ T value; \
+ size_t height; \
+ struct CONCAT(AVL_TREE_NODE_, T) * left; \
+ struct CONCAT(AVL_TREE_NODE_, T) * right; \
+ } avl_tree_node_t(T); \
+ \
+ typedef struct { \
+ avl_tree_node_t(T) * root; \
+ } avl_tree_t(T); \
+ \
+ size_t avl_tree_height(T)(avl_tree_t(T) * tree); \
+ avl_tree_t(T) * avl_tree_new(T)(); \
+ void avl_tree_free(T)(avl_tree_t(T) * tree); \
+ size_t avl_tree_size(T)(const avl_tree_t(T) * avl_tree); \
+ T* avl_tree_insert(T)(avl_tree_t(T) * avl_tree, T value); \
+ T* avl_tree_find(T)(const avl_tree_t(T)*, T val); \
+ bool avl_tree_erase(T)(avl_tree_t(T) * tree, T val, T * out);
+
+#define AVL_TREE_IMPL(T, CMP, DTOR) \
+ avl_tree_t(T) * avl_tree_new(T)() \
+ { \
+ avl_tree_t(T)* ret = ALLOC(sizeof(avl_tree_t(T))); \
+ ret->root = NULL; \
+ return ret; \
+ } \
+ static void CONCAT(avl_loose_free__, T)(avl_tree_node_t(T) * node) \
+ { \
+ if (!node) return; \
+ CONCAT(avl_loose_free__, T)(node->right); \
+ CONCAT(avl_loose_free__, T)(node->left); \
+ DTOR(node->value); \
+ FREE(node); \
+ } \
+ void avl_tree_free(T)(avl_tree_t(T) * tree) \
+ { \
+ CONCAT(avl_loose_free__, T)(tree->root); \
+ FREE(tree); \
+ } \
+ static inline size_t CONCAT( \
+ loose_size__, T)(const avl_tree_node_t(T) * node) \
+ { \
+ if (!node) return 0; \
+ return 1 + CONCAT(loose_size__, T)(node->left) + \
+ CONCAT(loose_size__, T)(node->right); \
+ } \
+ size_t avl_tree_size(T)(const avl_tree_t(T) * tree) \
+ { \
+ return CONCAT(loose_size__, T)(tree->root); \
+ } \
+ static int CONCAT(balance_factor, T)(avl_tree_node_t(T) * node) \
+ { \
+ return get_height(node->left) - get_height(node->right); \
+ } \
+ static avl_tree_node_t(T) * CONCAT(ll_rotate, T)(avl_tree_node_t(T) * node) \
+ { \
+ avl_tree_node_t(T)* child = node->left; \
+ node->left = child->right; \
+ reset_height(node); \
+ child->right = node; \
+ reset_height(child); \
+ return child; \
+ } \
+ static avl_tree_node_t(T) * CONCAT(rr_rotate, T)(avl_tree_node_t(T) * node) \
+ { \
+ avl_tree_node_t(T)* child = node->right; \
+ node->right = child->left; \
+ reset_height(node); \
+ child->left = node; \
+ reset_height(child); \
+ return child; \
+ } \
+ static avl_tree_node_t(T) * CONCAT(rl_rotate, T)(avl_tree_node_t(T) * node) \
+ { \
+ avl_tree_node_t(T)* child = node->right; \
+ node->right = CONCAT(ll_rotate, T)(child); \
+ reset_height(node); \
+ return CONCAT(rr_rotate, T)(node); \
+ } \
+ static avl_tree_node_t(T) * CONCAT(lr_rotate, T)(avl_tree_node_t(T) * node) \
+ { \
+ avl_tree_node_t(T)* child = node->left; \
+ node->left = CONCAT(rr_rotate, T)(child); \
+ reset_height(node); \
+ return CONCAT(ll_rotate, T)(node); \
+ } \
+ static avl_tree_node_t(T) * \
+ CONCAT(avl_tree_balance_, T)(avl_tree_node_t(T) * node) \
+ { \
+ int d = CONCAT(balance_factor, T)(node); \
+ if (d > 1) { \
+ if (CONCAT(balance_factor, T)(node->left) > 0) { \
+ return CONCAT(ll_rotate, T)(node); \
+ } else { \
+ return CONCAT(lr_rotate, T)(node); \
+ } \
+ } else if (d < -1) { \
+ if (CONCAT(balance_factor, T)(node->right) > 0) { \
+ return CONCAT(rl_rotate, T)(node); \
+ } else { \
+ return CONCAT(rr_rotate, T)(node); \
+ } \
+ } \
+ \
+ return node; \
+ } \
+ static avl_tree_node_t(T) * \
+ CONCAT(avl_tree_loose_insert_, T)( \
+ avl_tree_node_t(T) * node, T value, T * *ptr_out) \
+ { \
+ if (!node) { \
+ node = ALLOC(sizeof(avl_tree_node_t(T))); \
+ assert(node); \
+ node->left = NULL; \
+ node->right = NULL; \
+ node->value = value; \
+ node->height = 1; \
+ *ptr_out = &node->value; \
+ } else { \
+ typeof(CMP(node->value, value)) cmp = CMP(node->value, value); \
+ if (cmp < 0) { \
+ node->left = \
+ CONCAT(avl_tree_loose_insert_, T)(node->left, value, ptr_out); \
+ reset_height(node); \
+ node = CONCAT(avl_tree_balance_, T)(node); \
+ } else if (cmp > 0) { \
+ node->right = \
+ CONCAT(avl_tree_loose_insert_, T)(node->right, value, ptr_out); \
+ reset_height(node); \
+ node = CONCAT(avl_tree_balance_, T)(node); \
+ } \
+ } \
+ return node; \
+ } \
+ T* avl_tree_insert(T)(avl_tree_t(T) * tree, T value) \
+ { \
+ T* ret; \
+ tree->root = CONCAT(avl_tree_loose_insert_, T)(tree->root, value, &ret); \
+ return ret; \
+ } \
+ size_t avl_tree_height(T)(avl_tree_t(T) * tree) \
+ { \
+ if (!tree) return 0; \
+ return get_height(tree->root); \
+ } \
+ static T* CONCAT(loose_avl_tree_find, T)(avl_tree_node_t(T) * node, T value) \
+ { \
+ if (!node) return NULL; \
+ \
+ typeof(CMP(node->value, value)) cmp = CMP(node->value, value); \
+ if (cmp > 0) { \
+ return CONCAT(loose_avl_tree_find, T)(node->right, value); \
+ } else if (cmp < 0) { \
+ return CONCAT(loose_avl_tree_find, T)(node->left, value); \
+ } \
+ return &node->value; \
+ } \
+ T* avl_tree_find(T)(const avl_tree_t(T) * tree, T val) \
+ { \
+ if (!tree) return NULL; \
+ return CONCAT(loose_avl_tree_find, T)(tree->root, val); \
+ } \
+ static avl_tree_node_t(T) * \
+ CONCAT(pluck_left, T)(avl_tree_node_t(T) * node, T * into) \
+ { \
+ if (node->left) { \
+ node->left = CONCAT(pluck_left, T)(node->left, into); \
+ reset_height(node); \
+ return CONCAT(avl_tree_balance_, T)(node); \
+ } else { \
+ *into = node->value; \
+ FREE(node); \
+ return node->right; \
+ } \
+ } \
+ static avl_tree_node_t(T) * \
+ CONCAT(pluck_right, T)(avl_tree_node_t(T) * node, T * into) \
+ { \
+ if (node->right) { \
+ node->right = CONCAT(pluck_right, T)(node->right, into); \
+ reset_height(node); \
+ return CONCAT(avl_tree_balance_, T)(node); \
+ } else { \
+ *into = node->value; \
+ FREE(node); \
+ return node->left; \
+ } \
+ } \
+ avl_tree_node_t(T) * \
+ CONCAT(loose_avl_tree_erase, T)( \
+ avl_tree_node_t(T) * node, T value, bool* out, T* erased) \
+ { \
+ if (!node) { \
+ *out = 0; \
+ return NULL; \
+ } \
+ typeof(CMP(node->value, value)) cmp = CMP(node->value, value); \
+ if (cmp == 0) { \
+ if (erased) *erased = node->value; \
+ *out = 1; \
+ if (!node->right && !node->left) { \
+ FREE(node); \
+ return NULL; \
+ } \
+ if (get_height(node->right) > get_height(node->left)) { \
+ node->right = CONCAT(pluck_left, T)(node->right, &node->value); \
+ reset_height(node); \
+ node = CONCAT(avl_tree_balance_, T)(node); \
+ return node; \
+ } \
+ node->left = CONCAT(pluck_right, T)(node->left, &node->value); \
+ reset_height(node); \
+ node = CONCAT(avl_tree_balance_, T)(node); \
+ return node; \
+ } else if (cmp < 0) { \
+ node->left = \
+ CONCAT(loose_avl_tree_erase, T)(node->left, value, out, erased); \
+ reset_height(node); \
+ node = CONCAT(avl_tree_balance_, T)(node); \
+ } else { \
+ node->right = \
+ CONCAT(loose_avl_tree_erase, T)(node->right, value, out, erased); \
+ reset_height(node); \
+ node = CONCAT(avl_tree_balance_, T)(node); \
+ } \
+ return node; \
+ } \
+ bool avl_tree_erase(T)(avl_tree_t(T) * tree, T val, T * erased) \
+ { \
+ if (!tree) return 0; \
+ bool out; \
+ tree->root = \
+ CONCAT(loose_avl_tree_erase, T)(tree->root, val, &out, erased); \
+ return out; \
+ }
+
+#endif /* _SHARED_AVL_TREE_H_ */
diff --git a/include/shared/map.h b/include/shared/map.h
new file mode 100644
index 0000000..c9ee6b9
--- /dev/null
+++ b/include/shared/map.h
@@ -0,0 +1,90 @@
+#ifndef _SHARED_MAP_H_
+#define _SHARED_MAP_H_
+
+#include "shared/avl_tree.h"
+#include "shared/stdmacro.h"
+
+#define MAP_PASTE_KV(K, V) CONCAT(CONCAT(K, ___), V)
+#define map_entry_t(K, V) CONCAT(map_entry_t__, MAP_PASTE_KV(K, V))
+#define map_t(K, V) CONCAT(map_t__, MAP_PASTE_KV(K, V))
+
+#define map_new(K, V) CONCAT(map_new__, MAP_PASTE_KV(K, V))
+#define map_free(K, V) CONCAT(map_free__, MAP_PASTE_KV(K, V))
+#define map_put(K, V) CONCAT(map_put__, MAP_PASTE_KV(K, V))
+#define map_get(K, V) CONCAT(map_get__, MAP_PASTE_KV(K, V))
+#define map_erase(K, V) CONCAT(map_erase__, MAP_PASTE_KV(K, V))
+#define _map_compare_(K, V) CONCAT(_map_compare__, MAP_PASTE_KV(K, V))
+#define _map_dtor_(K, V) CONCAT(_map_dtor__, MAP_PASTE_KV(K, V))
+
+#define MAP_DECL(K, V) \
+ typedef struct { \
+ K key; \
+ V value; \
+ } map_entry_t(K, V); \
+ AVL_TREE_DECL(map_entry_t(K, V)); \
+ typedef struct { \
+ avl_tree_t(map_entry_t(K, V)) * tree; \
+ } map_t(K, V); \
+ map_t(K, V) * map_new(K, V)(); \
+ void map_free(K, V)(map_t(K, V) * map); \
+ V* map_get(K, V)(map_t(K, V) * map, K key); \
+ V* map_put(K, V)(map_t(K, V) * map, K key, V value); \
+ bool map_erase(K, V)(map_t(K, V) * map, K key, V * out);
+
+#define MAP_IMPL(K, V, CMP, DTOR) \
+ static inline int _map_compare_(K, V)( \
+ map_entry_t(K, V) e1, map_entry_t(K, V) e2) \
+ { \
+ return CMP(e1.key, e2.key); \
+ } \
+ static inline void _map_dtor_(K, V)(map_entry_t(K, V) e1) \
+ { \
+ DTOR(e1.value); \
+ } \
+ AVL_TREE_IMPL(map_entry_t(K, V), _map_compare_(K, V), _map_dtor_(K, V)) \
+ map_t(K, V) * map_new(K, V)() \
+ { \
+ map_t(K, V)* ret = ALLOC(sizeof(map_t(K, V))); \
+ ret->tree = avl_tree_new(map_entry_t(K, V))(); \
+ return ret; \
+ } \
+ void map_free(K, V)(map_t(K, V) * map) { \
+ avl_tree_free(map_entry_t(K, V))(map->tree); \
+ FREE(map); \
+ }\
+ V* map_get(K, V)(map_t(K, V) * map, K key) \
+ { \
+ map_entry_t(K, V) key_; \
+ key_.key = key; \
+ map_entry_t(K, V)* entry = \
+ avl_tree_find(map_entry_t(K, V))(map->tree, key_); \
+ \
+ if (!entry) { \
+ return NULL; \
+ } \
+ \
+ return &entry->value; \
+ } \
+ V* map_put(K, V)(map_t(K, V) * map, K key, V val) \
+ { \
+ map_entry_t(K, V) entry; \
+ entry.key = key; \
+ entry.value = val; \
+ map_entry_t(K, V)* ref = \
+ avl_tree_insert(map_entry_t(K, V))(map->tree, entry); \
+ return &ref->value; \
+ } \
+ bool map_erase(K, V)(map_t(K, V) * map, K key, V * out) \
+ { \
+ map_entry_t(K, V) key_; \
+ key_.key = key; \
+ \
+ map_entry_t(K, V) entry_out; \
+ bool ret = avl_tree_erase(map_entry_t(K, V))(map->tree, key_, &entry_out); \
+ if (ret) { \
+ *out = entry_out.value; \
+ } \
+ return ret; \
+ }
+
+#endif /* _SHARED_MAP_H_ */
diff --git a/include/shared/stdmacro.h b/include/shared/stdmacro.h
new file mode 100644
index 0000000..6010982
--- /dev/null
+++ b/include/shared/stdmacro.h
@@ -0,0 +1,7 @@
+#ifndef _SHARED_STDMACRO_H_
+#define _SHARED_STDMACRO_H_
+
+#define CONCAT_(a, b) a ## b
+#define CONCAT(a, b) CONCAT_(a, b)
+
+#endif /* _SHARED_STDMACRO_H_ */
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
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;
+}
generated by cgit (git 2.34.1) at 2025-04-28 20:06:03 +0000