From 23fe71639ecdc20a472130de6a2b8d71d8e5d2b0 Mon Sep 17 00:00:00 2001 From: Josh Rahm Date: Sat, 5 Dec 2020 16:03:09 -0700 Subject: Add array_list.h --- tests/test_array_list.c | 65 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) create mode 100644 tests/test_array_list.c (limited to 'tests') diff --git a/tests/test_array_list.c b/tests/test_array_list.c new file mode 100644 index 0000000..71ffa55 --- /dev/null +++ b/tests/test_array_list.c @@ -0,0 +1,65 @@ +#include "kern/mem.h" +#include "shared/array_list.h" +#include "test_harness.h" + +ARRAY_LIST_DECL(int); +ARRAY_LIST_IMPL(int); + +TEST(array_list, smell) +{ + array_list_t(int)* list = array_list_new(int)(); + + array_list_add(int)(list, 1); + array_list_add(int)(list, 2); + array_list_add(int)(list, 3); + array_list_add(int)(list, 4); + array_list_add(int)(list, 5); + + int expected[5] = {1, 2, 3, 4, 5}; + + for (size_t i = 0; i < 5; ++i) { + ASSERT_EQ(*array_list_ref(int)(list, i), expected[i]); + } + + ASSERT_EQ(array_list_length(int)(list), 5); + *array_list_ref(int)(list, 3) = 8; + expected[3] = 8; + + for (size_t i = 0; i < 5; ++i) { + ASSERT_EQ(*array_list_ref(int)(list, i), expected[i]); + } + + int out; + array_list_remove(int)(list, 2, &out); + ASSERT_EQ(out, 3); + ASSERT_EQ(array_list_length(int)(list), 4); + + int expected2[4] = {1, 2, 8, 5}; + for (size_t i = 0; i < 4; ++i) { + ASSERT_EQ(*array_list_ref(int)(list, i), expected2[i]); + } + + return 0; +} + +TEST(array_list, foreach) +{ + array_list_t(int)* arl = array_list_new(int)(); + array_list_add(int)(arl, 3); + array_list_add(int)(arl, 2); + array_list_add(int)(arl, 1); + + int i = 0; + int values[3]; + array_list_foreach(arl, val) { + values[i] = val; + ++ i; + } + + ASSERT_EQ(values[0], 3); + ASSERT_EQ(values[1], 2); + ASSERT_EQ(values[2], 1); + + return 0; + +} -- cgit From d29ea8d7fb8cc6f7c3dda1cbca6266908acd4291 Mon Sep 17 00:00:00 2001 From: Josh Rahm Date: Sat, 5 Dec 2020 16:25:27 -0700 Subject: Add remove ability to linked list. --- tests/test_linked_list.c | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) (limited to 'tests') diff --git a/tests/test_linked_list.c b/tests/test_linked_list.c index 7ec96b5..2c51625 100644 --- a/tests/test_linked_list.c +++ b/tests/test_linked_list.c @@ -60,3 +60,25 @@ TEST(linked_list, foreach) return 0; } + +TEST(linked_list, remove) +{ + linked_list_t(int) ll = LINKED_LIST_INIT; + linked_list_push_front(int)(&ll, 1); + linked_list_push_front(int)(&ll, 2); + linked_list_push_front(int)(&ll, 3); + linked_list_push_front(int)(&ll, 4); + linked_list_push_front(int)(&ll, 4); + + int ec = linked_list_remove(int)(&ll, 4); + ASSERT_EQ(!!ec, 1); + ec = linked_list_remove(int)(&ll, 2); + ASSERT_EQ(!!ec, 1); + ec = linked_list_remove(int)(&ll, 1); + ASSERT_EQ(!!ec, 1); + + ASSERT_EQ(linked_list_length(int)(&ll), 1); + ASSERT_EQ(*linked_list_front(int)(&ll), 3); + + return 0; +} -- cgit From 1710871aa1958c2cac38e4b372964ef22032ed4a Mon Sep 17 00:00:00 2001 From: Josh Rahm Date: Sun, 6 Dec 2020 02:00:43 -0700 Subject: 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. --- tests/test_avl_tree.c | 149 ++++++++++++++++++++++++++++++++++++++++++++++++++ tests/test_map.c | 113 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 262 insertions(+) create mode 100644 tests/test_avl_tree.c create mode 100644 tests/test_map.c (limited to 'tests') 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 + +#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; +} -- cgit From 90eb3a0b79bfef67c70dc545b49c48928eea05f4 Mon Sep 17 00:00:00 2001 From: Josh Rahm Date: Mon, 27 Sep 2021 22:56:46 -0600 Subject: Completed ws2812b 2020 Christmas Lights. --- tests/test_mpu.c | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) create mode 100644 tests/test_mpu.c (limited to 'tests') diff --git a/tests/test_mpu.c b/tests/test_mpu.c new file mode 100644 index 0000000..551e079 --- /dev/null +++ b/tests/test_mpu.c @@ -0,0 +1,27 @@ +#include "test_harness.c" + +#include "arch/arm/cortex-m4/mpu.h" +#include "kern/mpu/mpu_manager.h" + +TEST(mpu, smell) +{ + memory_region_opts_t memopts = { 0 }; + memopts.region = (void*) 0; + memopts.bufferable = 0; + memopts.cacheable = 1; + memopts.sharable = 1; + memopts.tex = 0; + memopts.size = REGION_SIZE_4Gb; + memopts.perms = ACCESS_PERMS_FULL; + memopts.subregion_disable = 0; + memopts.executable = 1; + memopts.enable = 1; + + mpu_configure_region(0, &memopts); + mpu_set_enabled(1); + + ASSERT_EQ(MPU.rba_r, 1 << 4); + ASSERT_EQ(MPU.ras_r, 0x0306003F); + + return 0; +} -- cgit