/*
* splay tree routines
* By Matthew Luckie
* U of Waikato 0657.317b 1999
*
* Copyright (C) 1999-2007 Matthew Luckie. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY Matthew Luckie ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
* ARE DISCLAIMED. IN NO EVENT SHALL Matthew Luckie BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*
* $Id: mjl_splaytree.c,v 1.14 2007/05/09 03:15:58 mjl Exp $
*
*/
#include <stdlib.h>
#include <assert.h>
#if defined(DMALLOC)
#include <dmalloc.h>
#endif
#include "mjl_splaytree.h"
/*
* the splay tree algorithm needs a simple stack to do the work.
* the implementations of these functions is found at the bottom of this
* file.
*/
typedef struct splaytree_stack
{
splaytree_node_t **nodes;
int i;
int c;
} splaytree_stack_t;
/*
* splay tree node data structure
* conveniently hidden from users of the splay tree.
*/
struct splaytree_node
{
void *item;
splaytree_node_t *left;
splaytree_node_t *right;
};
struct splaytree
{
splaytree_node_t *head;
int size;
splaytree_cmp_t cmp;
splaytree_stack_t *stack;
};
static splaytree_stack_t *stack_create(void);
static splaytree_node_t *stack_pop(splaytree_stack_t *stack);
static void stack_destroy(splaytree_stack_t *stack);
static int stack_push(splaytree_stack_t *stack, splaytree_node_t *node);
static void stack_clean(splaytree_stack_t *stack);
#if !defined(NDEBUG) && defined(MJLSPLAYTREE_DEBUG)
static void splaytree_assert2(splaytree_t *tree, splaytree_node_t *node)
{
int i;
if(node != NULL)
{
if(node->left != NULL)
{
i = tree->cmp(node->left->item, node->item);
assert(i < 0);
splaytree_assert2(tree, node->left);
}
if(node->right != NULL)
{
i = tree->cmp(node->right->item, node->item);
assert(i > 0);
splaytree_assert2(tree, node->right);
}
}
return;
}
static void splaytree_assert(splaytree_t *tree)
{
splaytree_assert2(tree, tree->head);
return;
}
#else
#define splaytree_assert(tree)((void)0)
#endif
/*
* splaytree_rotate
*
* perform the generic treenode-rotate algorithm.
*/
static void splaytree_rotate(splaytree_node_t *above, splaytree_node_t *below)
{
splaytree_node_t *temp;
/*
* above and below must be valid treenode pointers.
* above must point to the below node
*/
assert(above != NULL);
assert(below != NULL);
assert(above->left == below || above->right == below);
/*
* check to see if the below node is to the left of the above or to
* the right
*/
if(above->left == below)
{
temp = below->right;
below->right = above;
above->left = temp;
}
else
{
temp = below->left;
below->left = above;
above->right = temp;
}
return;
}
/*
* splaytree_splay2
*
* appropriately splay the treenodes passed in so that the child is moved
* higher than the other nodes passed in
*/
static void splaytree_splay2(splaytree_node_t *child,
splaytree_node_t *parent,
splaytree_node_t *grandparent)
{
/* pre-condition: grandparent points to parent, parent points to child */
assert(child != NULL);
assert(parent == NULL || (parent->left == child || parent->right == child));
assert(grandparent == NULL ||
(grandparent->left == parent || grandparent->right == parent));
/* case 0: access node is root */
if(parent == NULL)
{
return;
}
/* case 1: parent is root */
else if(grandparent == NULL)
{
splaytree_rotate(parent, child);
}
/*
* case 2: zig zig - p is not the root and the child and the parent are both
* left (right) children
*/
else if((parent->left == child && grandparent->left == parent) ||
(parent->right == child && grandparent->right == parent))
{
splaytree_rotate(grandparent, parent);
splaytree_rotate(parent, child);
}
/*
* case 3: zig zag - p is not the root and the child is a left(right) child
* and parent is a right(left) child
*/
else if((parent->left == child && grandparent->right == parent) ||
(parent->right == child && grandparent->left == parent))
{
if(grandparent->left == parent)
{
splaytree_rotate(parent, child);
grandparent->left = child;
splaytree_rotate(grandparent, child);
}
else
{
splaytree_rotate(parent, child);
grandparent->right = child;
splaytree_rotate(grandparent, child);
}
}
return;
}
/*
* splaytree_splay
*
* coordinate the calls to splaytree_splay2.
* the stack contains, in order, the path to the child so that the nodes can
* be splayed.
*/
static void splaytree_splay(splaytree_t *tree)
{
splaytree_node_t *child, *parent, *grandparent, *keep;
child = stack_pop(tree->stack);
parent = stack_pop(tree->stack);
grandparent = stack_pop(tree->stack);
/* there has to be at least one entry in the stack */
assert(child != NULL);
/* is there only one node in the tree */
if(parent == NULL)
{
tree->head = child;
return;
}
/* splay the node */
splaytree_splay2(child, parent, grandparent);
/* it was a simple swap at the root */
if(grandparent == NULL)
{
tree->head = child;
return;
}
/*
* remember the grandparent so that we can figure out where to relink the
* splayed child to
*/
keep = grandparent;
/* just loop and we will break out when we need to */
for(;;)
{
/* get the parent nodes to the child */
parent = stack_pop(tree->stack);
grandparent = stack_pop(tree->stack);
/*
* if the child node is now at the root, break out as the splay is
* complete
*/
if(parent == NULL)
{
break;
}
assert(parent->left == keep || parent->right == keep);
/*
* figure out where to relink the child to
* (as the grandparent in keep is now down the tree)
*/
if(parent->left == keep)
{
parent->left = child;
}
else
{
parent->right = child;
}
/* splay now */
splaytree_splay2(child, parent, grandparent);
if(grandparent == NULL)
{
break;
}
keep = grandparent;
}
/* return the new root of the tree */
tree->head = child;
return;
}
/*
* splaytree_node_alloc
*
* creates/mallocs a node and initialises the contents of the node ready to
* insert to the tree
*/
static splaytree_node_t *splaytree_node_alloc(const void *item)
{
splaytree_node_t *node;
if((node = (splaytree_node_t *)malloc(sizeof(splaytree_node_t))) != NULL)
{
node->left = NULL;
node->right = NULL;
node->item = (void *)item;
}
return node;
}
/*
* splaytree_insert2
*
* insert the item into the tree.
* returns 0 if inserted, -1 on error.
*/
static int splaytree_insert2(splaytree_t *tree, const void *item,
splaytree_node_t *parent)
{
splaytree_node_t *node;
int i;
/* put the node into the insert path and try the next level */
if(stack_push(tree->stack, parent) != 0)
{
return -1;
}
/* see whether the data belongs to the left, right, or is a duplicate */
i = tree->cmp(item, parent->item);
if(i < 0)
{
if(parent->left != NULL)
{
return splaytree_insert2(tree, item, parent->left);
}
/* insert the item into the tree here */
if((node = splaytree_node_alloc(item)) == NULL ||
stack_push(tree->stack, node) != 0)
{
return -1;
}
parent->left = node;
}
else if(i > 0)
{
if(parent->right != NULL)
{
return splaytree_insert2(tree, item, parent->right);
}
if((node = splaytree_node_alloc(item)) == NULL ||
stack_push(tree->stack, node) != 0)
{
return -1;
}
parent->right = node;
}
else
{
/* the data already exists in the tree: do not add it */
return -1;
}
return 0;
}
/*
* splaytree_insert
*
* insert a value into the splay tree, and return with the tree splayed on
* that value. return the node of the item.
*
*/
splaytree_node_t *splaytree_insert(splaytree_t *tree, const void *item)
{
assert(tree != NULL);
splaytree_assert(tree);
/*
* if the tree actually has something in it, then we need to
* find the place to insert the node and splay on that.
*/
if(tree->head != NULL)
{
stack_clean(tree->stack);
/*
* try and insert the item. can't insert it if an item matching this
* one is already there
*/
if(splaytree_insert2(tree, item, tree->head) != 0)
{
return NULL;
}
splaytree_splay(tree);
}
else
{
if((tree->head = splaytree_node_alloc(item)) == NULL)
{
return NULL;
}
}
tree->size++;
splaytree_assert(tree);
return tree->head;
}
/*
* splaytree_find2
*
* find the node with the data item matching. returns the node, if found.
*/
static splaytree_node_t *splaytree_find2(splaytree_t *tree, const void *item,
splaytree_node_t *tn)
{
int i;
/* item is not in the tree */
if(tn == NULL)
{
return NULL;
}
/*
* try and push the node onto the stack.
* if we don't then we can't splay the node to the top of the tree, so
* we fail.
*/
if(stack_push(tree->stack, tn) != 0)
{
return NULL;
}
if((i = tree->cmp(item, tn->item)) < 0)
{
/* look left */
return splaytree_find2(tree, item, tn->left);
}
else if(i > 0)
{
/* look right */
return splaytree_find2(tree, item, tn->right);
}
/* we found it ! */
return tn;
}
/*
* splaytree_find
*
* finds an item in the tree, and then splays the tree on that value
*/
void *splaytree_find(splaytree_t *tree, const void *item)
{
if(tree == NULL || tree->head == NULL)
{
return NULL;
}
splaytree_assert(tree);
stack_clean(tree->stack);
if(splaytree_find2(tree, item, tree->head) == NULL)
{
return NULL;
}
splaytree_splay(tree);
splaytree_assert(tree);
return tree->head->item;
}
/*
* splaytree_remove
*
* remove the first item in the splaytree
*/
static int splaytree_remove(splaytree_t *tree)
{
splaytree_node_t *node;
splaytree_node_t *l, *r;
splaytree_node_t *temp;
node = tree->head;
l = node->left;
r = node->right;
/*
* search for the right most node in the left tree
* if there are no nodes on the left hand side of the tree, then we just
* need to shift the head of the tree to whatever is there on the right
* of it.
*/
if(l != NULL)
{
stack_clean(tree->stack);
if(stack_push(tree->stack, l) != 0)
{
return -1;
}
temp = l;
while(temp->right != NULL)
{
if(stack_push(tree->stack, temp->right) != 0)
{
return -1;
}
temp = temp->right;
}
/* bring this node to the top of the tree with a splay operation */
splaytree_splay(tree);
/*
* as the right most node on the left branch has no nodes on the right
* branch, we connect the right hand branch to it
*/
tree->head->right = r;
}
else
{
tree->head = r;
}
tree->size--;
free(node);
return 0;
}
/*
* splaytree_remove_item
*
* remove an item from the tree that matches the particular key
*/
int splaytree_remove_item(splaytree_t *tree, const void *item)
{
/*
* find the node that we are supposed to delete.
* if we can't find it, then the remove operation has failed.
*/
stack_clean(tree->stack);
if(splaytree_find2(tree, item, tree->head) == NULL)
{
return -1;
}
/*
* now that we've found it, splay the tree to bring the node we are to
* delete to the top of the tree and then delete it.
*/
splaytree_splay(tree);
return splaytree_remove(tree);
}
/*
* splaytree_remove_node
*
* remove a specific node from the splay tree
*/
int splaytree_remove_node(splaytree_t *tree, splaytree_node_t *node)
{
/*
* find the path to the node that we are supposed to delete. the node
* that we find has to match what was passed in
*/
stack_clean(tree->stack);
if(splaytree_find2(tree, node->item, tree->head) != node)
{
return -1;
}
/*
* now that we've found it, splay the tree to bring the node we are to
* delete to the top of the tree and then delete it.
*/
splaytree_splay(tree);
return splaytree_remove(tree);
}
/*
* splaytree_findclosest
*
* find a value in the tree as close to the specified one as possible
*/
void *splaytree_findclosest(splaytree_t *tree, const void *item,
splaytree_diff_t diff)
{
splaytree_node_t *ret;
splaytree_node_t *first, *second;
int first_diff, second_diff;
if(tree == NULL || tree->head == NULL) return NULL;
stack_clean(tree->stack);
/* wow, the value we are looking for is actually in the tree! */
if((ret = splaytree_find2(tree, item, tree->head)) != NULL)
{
splaytree_splay(tree);
return tree->head->item;
}
/*
* we need to get the last two items off the stack and figure out which
* one of the two is the closest to the one we are looking for
*/
first = stack_pop(tree->stack);
second = stack_pop(tree->stack);
/* need at least one item in the stack if tree->head != NULL */
assert(first != NULL);
/* if there is only one item in the stack, splay? on it and return it */
if(second == NULL)
{
if(stack_push(tree->stack, first) != 0)
{
return NULL;
}
splaytree_splay(tree);
return tree->head->item;
}
/* work out which one is closer to the value we are looking for */
first_diff = abs(diff(first->item, item));
second_diff = abs(diff(second->item, item));
/*
* if the first item is closer than the second, put the first back on the
* stack and the splay on that
* else put them both back on and splay on that
*/
if(second_diff > first_diff)
{
if(stack_push(tree->stack, second) != 0)
{
return NULL;
}
}
else
{
if(stack_push(tree->stack, second) != 0 ||
stack_push(tree->stack, first) != 0)
{
return NULL;
}
}
splaytree_splay(tree);
return tree->head->item;
}
/*
* splaytree_depth2
*
* recursive function to return the depth of the splay tree.
*/
static int splaytree_depth2(splaytree_node_t *tn)
{
int left = 0;
int right = 0;
if(tn == NULL) return 0;
if(tn->left != NULL)
{
left = splaytree_depth2(tn->left) + 1;
}
if(tn->right != NULL)
{
right = splaytree_depth2(tn->right) + 1;
}
return (left > right) ? left : right;
}
/*
* splaytree_depth
*
* returns the longest path (the depth) of the splay tree
*/
int splaytree_depth(splaytree_t *tree)
{
if(tree == NULL) return -1;
if(tree->head == NULL) return 0;
return splaytree_depth2(tree->head) + 1;
}
/*
* splaytree_free2
*
* recursive function used to free a splaytree's nodes.
*/
static void splaytree_free2(splaytree_node_t *tn, splaytree_free_t free_ptr)
{
if(tn == NULL) return;
splaytree_free2(tn->left, free_ptr);
splaytree_free2(tn->right, free_ptr);
if(free_ptr != NULL) free_ptr(tn->item);
free(tn);
return;
}
/*
* splaytree_free
*
* dellocate the splaytree
*/
void splaytree_free(splaytree_t *tree, splaytree_free_t free_ptr)
{
if(tree == NULL) return;
splaytree_free2(tree->head, free_ptr);
stack_destroy(tree->stack);
free(tree);
return;
}
/*
* splaytree_getrmlb
*
* return the right-most item on the left branch of the tree
*/
void *splaytree_getrmlb(splaytree_t *tree)
{
splaytree_node_t *tn;
if(tree == NULL || tree->head == NULL || tree->head->left == NULL)
{
return NULL;
}
tn = tree->head->left;
while(tn->right != NULL)
{
tn = tn->right;
}
return tn->item;
}
/*
* splaytree_getlmrb
*
* return the left-most item on the right branch of the tree
*/
void *splaytree_getlmrb(splaytree_t *tree)
{
splaytree_node_t *tn;
if(tree == NULL || tree->head == NULL || tree->head->right == NULL)
{
return NULL;
}
tn = tree->head->right;
while(tn->left != NULL)
{
tn = tn->left;
}
return tn->item;
}
/*
* splaytree_display2
*
* recursive function to print the contents of the splaytree, ascii-like.
*/
static void splaytree_display2(splaytree_node_t *tn, splaytree_display_t disp,
int pad)
{
if(tn != NULL)
{
splaytree_display2(tn->left, disp, pad+1);
disp(tn->item, pad);
splaytree_display2(tn->right, disp, pad+1);
}
return;
}
/*
* splaytree_display
*
* print the contents of the splaytree.
*/
void splaytree_display(splaytree_t *tree, splaytree_display_t disp)
{
if(tree != NULL && disp != NULL)
{
splaytree_display2(tree->head, disp, 1);
}
return;
}
/*
* splaytree_inorder2
*
* recursive function to call a user-provided function on all items in
* the splay tree in order.
*/
static void splaytree_inorder2(splaytree_node_t *node,
splaytree_inorder_t func, void *in)
{
if(node != NULL)
{
splaytree_inorder2(node->left, func, in);
func(in, node->item);
splaytree_inorder2(node->right, func, in);
}
return;
}
/*
* splaytree_inorder
*
* call a user-provided function on all items in the splay tree in order
*/
void splaytree_inorder(splaytree_t *tree, splaytree_inorder_t func, void *in)
{
if(tree != NULL && func != NULL)
{
splaytree_inorder2(tree->head, func, in);
}
return;
}
/*
* splaytree_alloc
*
* allocate a splaytree
*/
splaytree_t *splaytree_alloc(splaytree_cmp_t cmp)
{
splaytree_t *tree;
if((tree = (splaytree_t *)malloc(sizeof(splaytree_t))) == NULL)
{
return NULL;
}
tree->head = NULL;
tree->size = 0;
tree->cmp = cmp;
if((tree->stack = stack_create()) == NULL)
{
goto err;
}
return tree;
err:
splaytree_free(tree, NULL);
return NULL;
}
/*
* splaytree_count
*
* return the number of items in the splaytree.
*/
int splaytree_count(splaytree_t *tree)
{
if(tree == NULL) return -1;
return tree->size;
}
/*
* stack_create
*
* create a stack that is optimised for dealing with splaytree processing
*/
static splaytree_stack_t *stack_create(void)
{
splaytree_stack_t *s;
if((s = (splaytree_stack_t *)malloc(sizeof(splaytree_stack_t))) == NULL)
{
return NULL;
}
s->i = -1;
s->c = 128;
if((s->nodes = malloc(sizeof(splaytree_node_t *) * s->c)) == NULL)
{
free(s);
return NULL;
}
return s;
}
/*
* stack_clean
*
* reset the splaytree stack so it is emptied.
*/
static void stack_clean(splaytree_stack_t *s)
{
s->i = -1;
return;
}
/*
* stack_destroy
*
* free the memory allocated to the splaytree stack.
*/
static void stack_destroy(splaytree_stack_t *s)
{
free(s->nodes);
free(s);
return;
}
/*
* stack_push
*
* put the node on the splaytree stack, growing the array if necessary.
*/
static int stack_push(splaytree_stack_t *s, splaytree_node_t *node)
{
splaytree_node_t **nodes;
size_t size;
if(s->i+1 == s->c)
{
size = sizeof(splaytree_node_t *) * (s->c + 128);
if((nodes = (splaytree_node_t **)realloc(s->nodes, size)) == NULL)
{
return -1;
}
s->c += 128;
s->nodes = nodes;
}
s->nodes[++s->i] = node;
return 0;
}
/*
* stack_pop
*
* remove the splaytree node at the top of the stack.
*/
static splaytree_node_t *stack_pop(splaytree_stack_t *s)
{
if(s->i == -1) return NULL;
return s->nodes[s->i--];
}
syntax highlighted by Code2HTML, v. 0.9.1