/* * 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.2.1 2007/12/03 07:13:54 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--]; }

Generated by Doxygen 1.6.0 Back to index