From 9cf1d1ea51af44c1d2733dac7a337c0c6997ab49 Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Sun, 12 Apr 2015 11:42:47 -0400 Subject: [PATCH] implemented splay operation and started debugging confusing insert behavior --- source/runtime/splaytree.c | 92 ++++++++++++++++++++++----- tests/test_splaytree.c | 124 +++++++++++++++++++------------------ 2 files changed, 141 insertions(+), 75 deletions(-) diff --git a/source/runtime/splaytree.c b/source/runtime/splaytree.c index 9504745..65d658a 100644 --- a/source/runtime/splaytree.c +++ b/source/runtime/splaytree.c @@ -4,6 +4,7 @@ */ #include "splaytree.h" #include +#include static node_t* create_node(void* value) { @@ -48,21 +49,62 @@ static node_t* rotate(node_t* node, direction_t direction){ return pivot; } +void print_tree(node_t* tree) { + if (tree) { + printf("(%lu ", (uintptr_t)tree->value); + if (tree->left) { + print_tree(tree->left); + printf(" "); + } else + printf("nil "); + if (tree->right) + print_tree(tree->right); + else + printf("nil"); + printf(")"); + } +} + static void splay(splaytree_t* tree, uintptr_t key) { - node_t* node = tree->root; - if (NULL != node) { + node_t subroots = {0, 0, 0}; + node_t* subleft = &subroots; + node_t* subright = &subroots; + node_t* root = tree->root; + if (NULL != root) { while (1) { - int cmp = tree->compare(key, node->value); + int cmp = tree->compare(key, root->value); if (cmp < 0) { - node = rotate(node, RIGHT); + if (NULL == root->left) break; + if (tree->compare(key, root->left->value) < 0) { + root = rotate(root, RIGHT); + if (NULL == root->left) break; + } + subright->left = root; + subright = root; + root = root->left; } else if (cmp > 0) { - node = rotate(node, LEFT); + if (NULL == root->right) break; + if (tree->compare(key, root->right->value) < 0) { + root = rotate(root, LEFT); + if (NULL == root->right) break; + } + subleft->right = root; + subleft = root; + root = root->right; } else { break; } } } - tree->root = node; + + /* assemble */ + subleft->right = root->left; + subright->left = root->right; + root->left = subroots.right; + root->right = subroots.left; + + /* Set the root */ + tree->root = root; } splaytree_t* splaytree_create(del_fn_t delfn, cmp_fn_t cmp_fn) @@ -85,18 +127,40 @@ void splaytree_destroy(splaytree_t* tree) void splaytree_insert(splaytree_t* tree, uintptr_t key, void* value) { - /* Insert the item into the tree */ + (void)next_node; if (tree->root == NULL) { tree->root = create_node(value); } else { - node_t** current = &(tree->root); - while(*current != NULL) { - current = next_node(tree, *current, key); - } - *current = create_node(value); + /* Splay the closest node in value to the root */ + puts("before splay: "); + print_tree(tree->root); + puts(""); + /* Splay the new node to the top of the tree */ + splay(tree, key); + puts("after splay: "); + print_tree(tree->root); + puts(""); + + /* Compare the key to the new root */ + int cmp = tree->compare(key, tree->root->value); + if (cmp < 0) { + node_t* newroot = create_node(value); + printf("newroot1: %lu\n", (uintptr_t)newroot->value); + newroot->left = tree->root->left; + newroot->right = tree->root; + tree->root->left = NULL; + tree->root = newroot; + } else if (cmp > 0) { + node_t* newroot = create_node(value); + newroot->right = tree->root->right; + newroot->left = tree->root; + printf("newroot2: %lu\n", (uintptr_t)newroot->value); + tree->root->right = NULL; + printf("newroot2: %lu\n", (uintptr_t)newroot->value); + tree->root = newroot; + } else { /* do nothing, item already present */ } + printf("values: %lu %lu\n", (uintptr_t)value, (uintptr_t)(tree->root->value)); } - /* Splay the new node to the top of the tree */ - (void)splay; } void* splaytree_lookup(splaytree_t* tree, uintptr_t key) diff --git a/tests/test_splaytree.c b/tests/test_splaytree.c index e44e309..ca2b5df 100644 --- a/tests/test_splaytree.c +++ b/tests/test_splaytree.c @@ -1,5 +1,6 @@ #include "atf.h" #include "splaytree.h" +#include static int cmp_int(uintptr_t key, uintptr_t val) { return (key == val) ? 0 : (key < val) ? -1 : 1; @@ -22,76 +23,77 @@ TEST_SUITE(SplayTree) { /* 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_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*)41 == tree->root->value); +// CHECK((void*)42 == tree->root->right->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); + printf("root->value: %p\n", tree->root->value); + CHECK((void*)43 == tree->root->value); + CHECK((void*)42 == tree->root->left->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); - } +// 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