From 722fd71eb753663566bbd2d2886112456a283596 Mon Sep 17 00:00:00 2001 From: "Mike D. Lowis" Date: Thu, 9 Apr 2015 14:54:44 -0400 Subject: [PATCH] Added tests for splay tree insert and lookup functions --- source/runtime/heap.c | 31 ++++++++++++- source/runtime/segment.c | 4 ++ source/runtime/segment.h | 2 + source/runtime/splaytree.c | 16 ++++++- tests/test_splaytree.c | 94 +++++++++++++++++++++++++++++++++++--- 5 files changed, 137 insertions(+), 10 deletions(-) diff --git a/source/runtime/heap.c b/source/runtime/heap.c index 6331669..0ebd15d 100644 --- a/source/runtime/heap.c +++ b/source/runtime/heap.c @@ -40,13 +40,12 @@ heap_t* heap_create(void) void heap_destroy(heap_t* heap) { - unsigned int i; /* Free all the large blocks */ splaytree_destroy(heap->segments); splaytree_destroy(heap->blocks); splaytree_destroy(heap->greylist); /* Free all of the small block segments */ - for (i = 0; i < NUM_HEAP_STACKS; i++) { + for (unsigned int i = 0; i < NUM_HEAP_STACKS; i++) { segment_destroy(heap->heaps[i].available); } /* Free the heap itself */ @@ -102,7 +101,35 @@ void heap_start_collection(heap_t* heap) void heap_finish_collection(heap_t* heap) { + /* All blocks remaining in the greylist now are unreachable so free them */ splaytree_destroy(heap->greylist); + /* Now iterate over the sub heaps and make sure the full/available lists are in order */ + for (unsigned int i = 0; i < NUM_HEAP_STACKS; i++) { + segment_t* prev = NULL; + segment_t* curr = heap->heaps[i].full; + while(curr != NULL) { + if (segment_empty(curr)) { + segment_t* deadite = curr; + if (NULL != prev) { + prev->next = curr->next; + curr = curr->next; + } + deadite->next = NULL; + segment_destroy(deadite); + } else if (!segment_full(curr)) { + if (NULL != prev) { + prev->next = curr->next; + curr = curr->next; + } + curr->next = heap->heaps[i].available; + heap->heaps[i].available = curr; + } else { + prev = curr; + curr = curr->next; + } + } + segment_destroy(heap->heaps[i].available); + } } void* heap_find_and_mark(heap_t* heap, uintptr_t addr) diff --git a/source/runtime/segment.c b/source/runtime/segment.c index fa69bc6..92e09f0 100644 --- a/source/runtime/segment.c +++ b/source/runtime/segment.c @@ -39,6 +39,10 @@ bool segment_full(segment_t* seg) { return (0u == seg->blockmap[0]); } +bool segment_empty(segment_t* seg) { + return (UINT16_MAX == seg->blockmap[0]); +} + static void* alloc_block(segment_t* seg, uintptr_t root_idx, uintptr_t submap_idx) { void* object = NULL; uintptr_t submap_mask = (1u << submap_idx); diff --git a/source/runtime/segment.h b/source/runtime/segment.h index 318d625..955c2a0 100644 --- a/source/runtime/segment.h +++ b/source/runtime/segment.h @@ -26,6 +26,8 @@ void segment_destroy(segment_t* seg); bool segment_full(segment_t* seg); +bool segment_empty(segment_t* seg); + void* segment_alloc(segment_t* seg); void segment_clear_map(segment_t* seg); diff --git a/source/runtime/splaytree.c b/source/runtime/splaytree.c index 0f761cf..398745e 100644 --- a/source/runtime/splaytree.c +++ b/source/runtime/splaytree.c @@ -22,6 +22,15 @@ static node_t** next_node(splaytree_t* tree, node_t* curr, uintptr_t address) return &(curr->right); } +static void destroy_node(splaytree_t* tree, node_t* node) { + if (NULL != node) { + destroy_node(tree, node->left); + destroy_node(tree, node->right); + //tree->destroy(node->value); + free(node); + } +} + splaytree_t* splaytree_create(del_fn_t delfn, cmp_fn_t cmp_fn) { splaytree_t* tree = (splaytree_t*)malloc(sizeof(splaytree_t)); @@ -33,7 +42,10 @@ splaytree_t* splaytree_create(del_fn_t delfn, cmp_fn_t cmp_fn) void splaytree_destroy(splaytree_t* tree) { - (void)tree; + if (NULL != tree) { + destroy_node(tree, tree->root); + free(tree); + } } void splaytree_insert(splaytree_t* tree, uintptr_t key, void* value) @@ -54,7 +66,7 @@ void* splaytree_lookup(splaytree_t* tree, uintptr_t key) { node_t* current = tree->root; while (current != NULL) { - int cmp_val = tree->compare(key, current); + int cmp_val = tree->compare(key, current->value); if (cmp_val == 0) return current->value; else if (cmp_val < 0) diff --git a/tests/test_splaytree.c b/tests/test_splaytree.c index 6223e20..e44e309 100644 --- a/tests/test_splaytree.c +++ b/tests/test_splaytree.c @@ -1,15 +1,97 @@ #include "atf.h" #include "splaytree.h" +static int cmp_int(uintptr_t key, uintptr_t val) { + return (key == val) ? 0 : (key < val) ? -1 : 1; +} + +static void del_int(uintptr_t val) { + (void)val; +} + TEST_SUITE(SplayTree) { /* Verify: splaytree_create *************************************************************************/ - //TEST(Verify_Create_allocates_and_initializes_an_empty_tree) { - // splaytree_t* tree = splaytree_create(); - // CHECK(tree->root == NULL); - // splaytree_destroy(tree); - //} + TEST(Verify_Create_allocates_and_initializes_an_empty_tree) { + splaytree_t* tree = splaytree_create((del_fn_t)del_int, (cmp_fn_t)cmp_int); + CHECK(tree->destroy == (del_fn_t)del_int); + CHECK(tree->compare == (cmp_fn_t)cmp_int); + CHECK(tree->root == NULL); + splaytree_destroy(tree); + } - /* Verify: splaytree_create + /* Verify: splaytree_insert *************************************************************************/ + TEST(Verify_Insert_will_insert_into_an_empty_tree) + { + splaytree_t* tree = splaytree_create((del_fn_t)del_int, (cmp_fn_t)cmp_int); + splaytree_insert(tree, 42, (void*)42); + CHECK((void*)42 == tree->root->value); + splaytree_destroy(tree); + } + + TEST(Verify_Insert_will_insert_to_the_left_of_root_when_less_than) + { + splaytree_t* tree = splaytree_create((del_fn_t)del_int, (cmp_fn_t)cmp_int); + splaytree_insert(tree, 42, (void*)42); + splaytree_insert(tree, 41, (void*)41); + CHECK((void*)42 == tree->root->value); + CHECK((void*)41 == tree->root->left->value); + splaytree_destroy(tree); + } + + TEST(Verify_Insert_will_insert_to_the_right_of_root_when_greater_than) + { + splaytree_t* tree = splaytree_create((del_fn_t)del_int, (cmp_fn_t)cmp_int); + splaytree_insert(tree, 42, (void*)42); + splaytree_insert(tree, 43, (void*)43); + CHECK((void*)42 == tree->root->value); + CHECK((void*)43 == tree->root->right->value); + splaytree_destroy(tree); + } + + /* Verify: splaytree_lookup + *************************************************************************/ + TEST(Verify_Lookup_will_find_the_item_at_the_root) + { + splaytree_t* tree = splaytree_create((del_fn_t)del_int, (cmp_fn_t)cmp_int); + splaytree_insert(tree, 42, (void*)42); + CHECK((void*)42 == splaytree_lookup(tree, 42)); + splaytree_destroy(tree); + } + + TEST(Verify_Lookup_will_find_the_item_left_of_root_when_less_than) + { + splaytree_t* tree = splaytree_create((del_fn_t)del_int, (cmp_fn_t)cmp_int); + splaytree_insert(tree, 42, (void*)42); + splaytree_insert(tree, 41, (void*)41); + CHECK((void*)41 == splaytree_lookup(tree, 41)); + splaytree_destroy(tree); + } + + TEST(Verify_Lookup_will_find_the_item_right_of_root_when_greater_than) + { + splaytree_t* tree = splaytree_create((del_fn_t)del_int, (cmp_fn_t)cmp_int); + splaytree_insert(tree, 42, (void*)42); + splaytree_insert(tree, 43, (void*)43); + CHECK((void*)43 == splaytree_lookup(tree, 43)); + splaytree_destroy(tree); + } + + /* Verify: splaytree_delete + *************************************************************************/ + TEST(Verify_Delete_will_delete_the_item_at_the_root) + { + CHECK(false); + } + + TEST(Verify_Delete_will_delete_the_item_left_of_root_when_less_than) + { + CHECK(false); + } + + TEST(Verify_Delete_will_delete_the_item_right_of_root_when_greater_than) + { + CHECK(false); + } } -- 2.52.0