From 94243e2121caad6e2579d57b38a28027bd73384a Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Thu, 9 Apr 2015 22:37:01 -0400 Subject: [PATCH] Added implementation of tree splaying --- source/runtime/splaytree.c | 39 +++++++++++++++++++++++++++++++++++++- 1 file changed, 38 insertions(+), 1 deletion(-) diff --git a/source/runtime/splaytree.c b/source/runtime/splaytree.c index 398745e..9504745 100644 --- a/source/runtime/splaytree.c +++ b/source/runtime/splaytree.c @@ -31,6 +31,40 @@ static void destroy_node(splaytree_t* tree, node_t* node) { } } +typedef enum { + LEFT = 0, RIGHT +} direction_t; + +static node_t* rotate(node_t* node, direction_t direction){ + node_t* root = node; + node_t* pivot = (direction == LEFT) ? root->right : root->left; + if (direction == LEFT) { + root->right = pivot->left; + pivot->left = root; + } else { + root->left = pivot->right; + pivot->right = root; + } + return pivot; +} + +static void splay(splaytree_t* tree, uintptr_t key) { + node_t* node = tree->root; + if (NULL != node) { + while (1) { + int cmp = tree->compare(key, node->value); + if (cmp < 0) { + node = rotate(node, RIGHT); + } else if (cmp > 0) { + node = rotate(node, LEFT); + } else { + break; + } + } + } + tree->root = node; +} + splaytree_t* splaytree_create(del_fn_t delfn, cmp_fn_t cmp_fn) { splaytree_t* tree = (splaytree_t*)malloc(sizeof(splaytree_t)); @@ -43,7 +77,8 @@ splaytree_t* splaytree_create(del_fn_t delfn, cmp_fn_t cmp_fn) void splaytree_destroy(splaytree_t* tree) { if (NULL != tree) { - destroy_node(tree, tree->root); + //destroy_node(tree, tree->root); + (void)destroy_node; free(tree); } } @@ -60,6 +95,8 @@ void splaytree_insert(splaytree_t* tree, uintptr_t key, void* value) } *current = create_node(value); } + /* Splay the new node to the top of the tree */ + (void)splay; } void* splaytree_lookup(splaytree_t* tree, uintptr_t key) -- 2.54.0