/* -*- Mode: c; c-basic-offset: 2 -*- * * raptor_avltree.c - Balanced Binary Tree / AVL Tree * * This file is in the public domain. * * Based on public domain sources posted to comp.sources.misc in 1993 * * From: p...@vix.com (Paul Vixie) * Newsgroups: comp.sources.unix * Subject: v27i034: REPOST AVL Tree subroutines (replaces v11i020 from 1987), Part01/01 * Date: 6 Sep 1993 13:51:22 -0700 * Message-ID: <1.747348668.4037@gw.home.vix.com> * * ---------------------------------------------------------------------- * Original headers below */ /* as_tree - tree library for as * vix 14dec85 [written] * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221] * vix 06feb86 [added tree_mung()] * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224] * vix 23jun86 [added delete uar to add for replaced nodes] * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes] */ /* This program text was created by Paul Vixie using examples from the book: * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN * 0-13-022005-1. This code and associated documentation is hereby placed * in the public domain. */ #ifdef HAVE_CONFIG_H #include #endif #ifdef HAVE_STDLIB_H #include #endif /* Raptor includes */ #include "raptor2.h" #include "raptor_internal.h" #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 #define RAPTOR_AVLTREE_DEBUG1(msg) RAPTOR_DEBUG1(msg) #else #define RAPTOR_AVLTREE_DEBUG1(msg) #endif #define RAPTOR_AVLTREE_ENOMEM -1 #define RAPTOR_AVLTREE_EXISTS 1 #ifndef STANDALONE /* raptor_avltree.c */ typedef struct raptor_avltree_node_s raptor_avltree_node; /* AVL-tree */ struct raptor_avltree_s { /* root node of tree */ raptor_avltree_node* root; /* node comparison function (optional) */ raptor_data_compare_handler compare_handler; /* node deletion function (optional) */ raptor_data_free_handler free_handler; /* node print function (optional) */ raptor_data_print_handler print_handler; /* tree bitflags - bitmask of #raptor_avltree_bitflags flags */ unsigned int flags; /* number of nodes in tree */ unsigned int size; }; /* AVL-tree node */ struct raptor_avltree_node_s { /* parent tree */ struct raptor_avltree_node_s *parent; /* left child tree */ struct raptor_avltree_node_s *left; /* right child tree */ struct raptor_avltree_node_s *right; /* balance factor = * height of the right tree minus the height of the left tree * i.e. equal: 0 left larger: -1 right larger: 1 */ signed char balance; /* actual data */ void* data; }; #ifndef TRUE #define TRUE 1 #define FALSE 0 #endif /* local prototypes */ static int raptor_avltree_sprout(raptor_avltree* tree, raptor_avltree_node* parent, raptor_avltree_node** node_pp, void* p_data, int *rebalancing_p); static void* raptor_avltree_delete_internal(raptor_avltree* tree, raptor_avltree_node** node_pp, void* p_data, int *rebalancing_p); static void* raptor_avltree_delete_internal2(raptor_avltree* tree, raptor_avltree_node** ppr_r, int *rebalancing_p, raptor_avltree_node** ppr_q); static void raptor_avltree_balance_left(raptor_avltree* tree, raptor_avltree_node** node_pp, int *rebalancing_p); static void raptor_avltree_balance_right(raptor_avltree* tree, raptor_avltree_node** node_pp, int *rebalancing_p); static raptor_avltree_node* raptor_avltree_search_internal(raptor_avltree* tree, raptor_avltree_node* node, const void* p_data); static int raptor_avltree_visit_internal(raptor_avltree* tree, raptor_avltree_node* node, int depth, raptor_avltree_visit_handler visit_fn, void* user_data); static void raptor_free_avltree_internal(raptor_avltree* tree, raptor_avltree_node* node); #ifdef RAPTOR_DEBUG static void raptor_avltree_check_internal(raptor_avltree* tree, raptor_avltree_node* node, unsigned int* count_p); #endif /** * raptor_new_avltree: * @compare_handler: item comparison handler for ordering * @free_handler: item free handler (or NULL) * @flags: AVLTree flags - bitmask of #raptor_avltree_bitflags flags. * * AVL Tree Constructor * * Return value: new AVL Tree or NULL on failure */ raptor_avltree* raptor_new_avltree(raptor_data_compare_handler compare_handler, raptor_data_free_handler free_handler, unsigned int flags) { raptor_avltree* tree; tree = RAPTOR_MALLOC(raptor_avltree*, sizeof(*tree)); if(!tree) return NULL; tree->root = NULL; tree->compare_handler = compare_handler; tree->free_handler = free_handler; tree->print_handler = NULL; tree->flags = flags; tree->size = 0; return tree; } /** * raptor_free_avltree: * @tree: AVLTree object * * AVL Tree destructor */ void raptor_free_avltree(raptor_avltree* tree) { if(!tree) return; raptor_free_avltree_internal(tree, tree->root); RAPTOR_FREE(raptor_avltree, tree); } static void raptor_free_avltree_internal(raptor_avltree* tree, raptor_avltree_node* node) { if(node) { raptor_free_avltree_internal(tree, node->left); raptor_free_avltree_internal(tree, node->right); if(tree->free_handler) tree->free_handler(node->data); tree->size--; RAPTOR_FREE(raptor_avltree_node, node); } } /* methods */ static raptor_avltree_node* raptor_avltree_search_internal(raptor_avltree* tree, raptor_avltree_node* node, const void* p_data) { if(node) { int cmp= tree->compare_handler(p_data, node->data); if(cmp > 0) return raptor_avltree_search_internal(tree, node->right, p_data); else if(cmp < 0) return raptor_avltree_search_internal(tree, node->left, p_data); /* found */ return node; } /* otherwise not found */ return NULL; } /** * raptor_avltree_search: * @tree: AVL Tree object * @p_data: pointer to data item * * Find an item in an AVL Tree * * Return value: shared pointer to item (still owned by AVL Tree) or NULL on failure or if not found */ void* raptor_avltree_search(raptor_avltree* tree, const void* p_data) { raptor_avltree_node* node; node = raptor_avltree_search_internal(tree, tree->root, p_data); return node ? node->data : NULL; } /** * raptor_avltree_add: * @tree: AVL Tree object * @p_data: pointer to data item * * add an item to an AVL Tree * * The item added becomes owned by the AVL Tree, and will be freed by * the free_handler argument given to raptor_new_avltree(). * * Return value: 0 on success, >0 if equivalent item exists (and the old element remains in the tree), <0 on failure */ int raptor_avltree_add(raptor_avltree* tree, void* p_data) { int rebalancing = FALSE; int rv; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 RAPTOR_AVLTREE_DEBUG1("Checking tree before adding\n"); raptor_avltree_check(tree); #endif rv = raptor_avltree_sprout(tree, NULL, &tree->root, p_data, &rebalancing); #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 RAPTOR_AVLTREE_DEBUG1("Checking tree after adding\n"); raptor_avltree_check(tree); #endif return rv; } /** * raptor_avltree_remove: * @tree: AVL Tree object * @p_data: pointer to data item * * Remove an item from an AVL Tree and return it * * The item removed is no longer owned by the AVL Tree and is * owned by the caller. * * Return value: object or NULL on failure or if not found */ void* raptor_avltree_remove(raptor_avltree* tree, void* p_data) { int rebalancing = FALSE; void* rdata; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 RAPTOR_AVLTREE_DEBUG1("Checking tree before removing\n"); raptor_avltree_dump(tree,stderr); raptor_avltree_check(tree); #endif rdata = raptor_avltree_delete_internal(tree, &tree->root, p_data, &rebalancing); if(rdata) tree->size--; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 RAPTOR_AVLTREE_DEBUG1("Checking tree after removing\n"); raptor_avltree_dump(tree,stderr); raptor_avltree_check(tree); #endif return rdata; } /** * raptor_avltree_delete: * @tree: AVL Tree object * @p_data: pointer to data item * * Remove an item from an AVL Tree and free it * * Return value: non-0 on failure */ int raptor_avltree_delete(raptor_avltree* tree, void* p_data) { void* rdata; rdata = raptor_avltree_remove(tree, p_data); if(rdata) { if(tree->free_handler) tree->free_handler(rdata); } return (rdata != NULL); } /** * raptor_avltree_trim: * @tree: AVLTree object * * Delete all nodes from an AVL tree but keep the shell. */ void raptor_avltree_trim(raptor_avltree* tree) { if(!tree) return; raptor_free_avltree_internal(tree, tree->root); tree->root = NULL; } static int raptor_avltree_visit_internal(raptor_avltree* tree, raptor_avltree_node* node, int depth, raptor_avltree_visit_handler visit_handler, void* user_data) { if(!node) return TRUE; if(!raptor_avltree_visit_internal(tree, node->left, depth+1, visit_handler, user_data)) return FALSE; if(!visit_handler(depth, node->data, user_data)) return FALSE; if(!raptor_avltree_visit_internal(tree, node->right, depth+1, visit_handler, user_data)) return FALSE; return TRUE; } /** * raptor_avltree_visit: * @tree: AVL Tree object * @visit_handler: visit function to call at each item * @user_data: user data pointer fo visit function * * Perform an in-order visit of the items in the AVL Tree * * Return value: non-0 if traversal was terminated early by @visit_handler */ int raptor_avltree_visit(raptor_avltree* tree, raptor_avltree_visit_handler visit_handler, void* user_data) { return raptor_avltree_visit_internal(tree, tree->root, 0, visit_handler, user_data); } #ifdef RAPTOR_DEBUG static void raptor_avltree_print_node(raptor_avltree_node* node) { fprintf(stderr, "%p: parent %p left %p right %p data %p", RAPTOR_VOIDP(node), RAPTOR_VOIDP(node->parent), RAPTOR_VOIDP(node->left), RAPTOR_VOIDP(node->right), RAPTOR_VOIDP(node->data)); } static void raptor_avltree_check_node(raptor_avltree* tree, raptor_avltree_node* node, const char* fn, const char* where) { if(node->parent) { if((node->parent == node->left) || (node->parent == node->right)) { if(fn && where) fprintf(stderr, "%s (%s): ", fn, where); fputs("ERROR bad node ", stderr); raptor_avltree_print_node(node); fputc('\n', stderr); fflush(stderr); abort(); } if(node->parent->left != node && node->parent->right != node) { if(fn && where) fprintf(stderr, "%s (%s): ", fn, where); fputs("ERROR parent node ", stderr); raptor_avltree_print_node(node->parent); fputs(" has no reference to child node ", stderr); raptor_avltree_print_node(node); fputc('\n', stderr); fflush(stderr); abort(); } } if(node->left) { if(node->left->parent != node) { if(fn && where) fprintf(stderr, "%s (%s): ", fn, where); fputs("ERROR left child node ", stderr); raptor_avltree_print_node(node->left); fputs(" has no reference to this[parent] node ", stderr); raptor_avltree_print_node(node); fputc('\n', stderr); fflush(stderr); abort(); } } if(node->right) { if(node->right->parent != node) { if(fn && where) fprintf(stderr, "%s (%s): ", fn, where); fputs("ERROR right child node ", stderr); raptor_avltree_print_node(node->right); fputs(" has no reference to this[parent] node ", stderr); raptor_avltree_print_node(node); fputc('\n', stderr); fflush(stderr); abort(); } } } #endif static int raptor_avltree_sprout_left(raptor_avltree* tree, raptor_avltree_node** node_pp, void* p_data, int *rebalancing_p) { raptor_avltree_node *p1, *p2, *p_parent; int rc; RAPTOR_AVLTREE_DEBUG1("LESS. raptor_avltree_sprouting left.\n"); p_parent = (*node_pp)->parent; rc = raptor_avltree_sprout(tree, *node_pp, &(*node_pp)->left, p_data, rebalancing_p); if(rc) return rc; if(!*rebalancing_p) return FALSE; /* left branch has grown longer */ RAPTOR_AVLTREE_DEBUG1("LESS: left branch has grown\n"); switch((*node_pp)->balance) { case 1: /* right branch WAS longer; balance is ok now */ RAPTOR_AVLTREE_DEBUG1("LESS: case 1.. balance restored implicitly\n"); (*node_pp)->balance = 0; *rebalancing_p = FALSE; break; case 0: /* balance WAS okay; now left branch longer */ RAPTOR_AVLTREE_DEBUG1("LESS: case 0.. balance bad but still ok\n"); (*node_pp)->balance = -1; break; case -1: /* left branch was already too long. rebalance */ RAPTOR_AVLTREE_DEBUG1("LESS: case -1: rebalancing\n"); #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 RAPTOR_AVLTREE_DEBUG1("Tree before rebalancing\n"); raptor_avltree_dump(tree, stderr); #endif p1 = (*node_pp)->left; if(p1->balance == -1) { /* LL */ RAPTOR_AVLTREE_DEBUG1("LESS: single LL\n"); (*node_pp)->left = p1->right; if((*node_pp)->left) (*node_pp)->left->parent = (*node_pp); p1->right = *node_pp; if(p1->right) p1->right->parent = p1; (*node_pp)->balance = 0; *node_pp = p1; (*node_pp)->parent = p_parent; } else { /* double LR */ RAPTOR_AVLTREE_DEBUG1("LESS: double LR\n"); p2 = p1->right; p1->right= p2->left; if(p1->right) p1->right->parent = p1; p2->left = p1; if(p2->left) p2->left->parent = p2; (*node_pp)->left = p2->right; if((*node_pp)->left) (*node_pp)->left->parent = (*node_pp); p2->right = *node_pp; if(p2->right) p2->right->parent = p2; if(p2->balance == -1) (*node_pp)->balance = 1; else (*node_pp)->balance = 0; if(p2->balance == 1) p1->balance = -1; else p1->balance = 0; *node_pp = p2; (*node_pp)->parent = p_parent; } /* end else */ #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 RAPTOR_AVLTREE_DEBUG1("Tree after rebalancing\n"); raptor_avltree_dump(tree, stderr); #endif (*node_pp)->balance = 0; *rebalancing_p = FALSE; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 if(1) { unsigned int discard = 0; raptor_avltree_check_internal(tree, *node_pp, &discard); } #endif } /* end switch */ return FALSE; } static int raptor_avltree_sprout_right(raptor_avltree* tree, raptor_avltree_node** node_pp, void* p_data, int *rebalancing_p) { raptor_avltree_node *p1, *p2, *p_parent; int rc; RAPTOR_AVLTREE_DEBUG1("MORE: raptor_avltree_sprouting to the right\n"); p_parent = (*node_pp)->parent; rc = raptor_avltree_sprout(tree, *node_pp, &(*node_pp)->right, p_data, rebalancing_p); if(rc) return rc; if(!*rebalancing_p) return FALSE; /* right branch has grown longer */ RAPTOR_AVLTREE_DEBUG1("MORE: right branch has grown\n"); switch((*node_pp)->balance) { case -1: RAPTOR_AVLTREE_DEBUG1("MORE: balance was off, fixed implicitly\n"); (*node_pp)->balance = 0; *rebalancing_p = FALSE; break; case 0: RAPTOR_AVLTREE_DEBUG1("MORE: balance was okay, now off but ok\n"); (*node_pp)->balance = 1; break; case 1: RAPTOR_AVLTREE_DEBUG1("MORE: balance was off, need to rebalance\n"); p1 = (*node_pp)->right; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 RAPTOR_AVLTREE_DEBUG1("Tree before rebalancing\n"); raptor_avltree_dump(tree, stderr); #endif if(p1->balance == 1) { /* RR */ RAPTOR_AVLTREE_DEBUG1("MORE: single RR\n"); (*node_pp)->right = p1->left; if((*node_pp)->right) (*node_pp)->right->parent = (*node_pp); p1->left = *node_pp; if(p1->left) p1->left->parent = p1; (*node_pp)->balance = 0; *node_pp = p1; (*node_pp)->parent = p_parent; } else { /* double RL */ RAPTOR_AVLTREE_DEBUG1("MORE: double RL\n"); p2 = p1->left; p1->left = p2->right; if(p1->left) p1->left->parent = p1; p2->right = p1; if(p2->right) p2->right->parent = p2; (*node_pp)->right = p2->left; if((*node_pp)->right) (*node_pp)->right->parent = (*node_pp); p2->left = *node_pp; if(p2->left) p2->left->parent = p2; if(p2->balance == 1) (*node_pp)->balance = -1; else (*node_pp)->balance = 0; if(p2->balance == -1) p1->balance = 1; else p1->balance = 0; *node_pp = p2; (*node_pp)->parent = p_parent; } /* end else */ #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 RAPTOR_AVLTREE_DEBUG1("Tree after rebalancing\n"); raptor_avltree_dump(tree, stderr); #endif (*node_pp)->balance = 0; *rebalancing_p = FALSE; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 if(1) { unsigned int discard = 0; raptor_avltree_check_internal(tree, *node_pp, &discard); } #endif } /* end switch */ return FALSE; } /* grow a tree by sprouting with a new node * * Return values: * 0 on success * >0 if equivalent item exists (and the old element remains in the tree) * <0 if memory is exhausted. */ static int raptor_avltree_sprout(raptor_avltree* tree, raptor_avltree_node* parent, raptor_avltree_node** node_pp, void* p_data, int *rebalancing_p) { int cmp; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 RAPTOR_AVLTREE_DEBUG1("Enter\n"); if ( *node_pp) { raptor_avltree_print_node(*node_pp); RAPTOR_AVLTREE_DEBUG1("\n"); } else { RAPTOR_AVLTREE_DEBUG1("Nil node\n"); } #endif /* If grounded, add the node here, set the rebalance flag and return */ if(!*node_pp) { RAPTOR_AVLTREE_DEBUG1("grounded. adding new node, setting rebalancing flag true\n"); *node_pp = RAPTOR_MALLOC(raptor_avltree_node*, sizeof(**node_pp)); if(!*node_pp) { if(tree->free_handler) tree->free_handler(p_data); return RAPTOR_AVLTREE_ENOMEM; } #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 RAPTOR_DEBUG2("Creating new node %p\n", RAPTOR_VOIDP(*node_pp)); #endif (*node_pp)->parent = parent; (*node_pp)->left = NULL; (*node_pp)->right = NULL; (*node_pp)->balance = 0; (*node_pp)->data= p_data; *rebalancing_p = TRUE; tree->size++; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 raptor_avltree_check_node(tree, *node_pp, 0, 0); RAPTOR_AVLTREE_DEBUG1("Tree now looks this way\n"); raptor_avltree_dump(tree,stderr); #endif return FALSE; } /* check node */ #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 raptor_avltree_check_node(tree, *node_pp, 0, 0); #endif /* compare the data */ cmp = tree->compare_handler(p_data, (*node_pp)->data); if(cmp < 0) /* if LESS, prepare to move to the left. */ return raptor_avltree_sprout_left(tree, node_pp, p_data, rebalancing_p); else if(cmp > 0) /* if MORE, prepare to move to the right. */ return raptor_avltree_sprout_right(tree, node_pp, p_data, rebalancing_p); /* otherwise equivalent key */ *rebalancing_p = FALSE; if(tree->flags & RAPTOR_AVLTREE_FLAG_REPLACE_DUPLICATES) { /* replace item with equivalent key */ if(tree->free_handler) tree->free_handler((*node_pp)->data); (*node_pp)->data= p_data; return FALSE; } else { /* ignore item with equivalent key */ if(tree->free_handler) tree->free_handler(p_data); return RAPTOR_AVLTREE_EXISTS; } } static void* raptor_avltree_delete_internal(raptor_avltree* tree, raptor_avltree_node** node_pp, void* p_data, int *rebalancing_p) { int cmp; void* rdata = NULL; RAPTOR_AVLTREE_DEBUG1("Enter\n"); if(*node_pp == NULL) { RAPTOR_AVLTREE_DEBUG1("key not in tree\n"); return rdata; } if(p_data) cmp = tree->compare_handler((*node_pp)->data, p_data); else cmp = 0; if(cmp > 0) { RAPTOR_AVLTREE_DEBUG1("too high - scan left\n"); rdata = raptor_avltree_delete_internal(tree, &(*node_pp)->left, p_data, rebalancing_p); if(*rebalancing_p) raptor_avltree_balance_left(tree, node_pp, rebalancing_p); } else if(cmp < 0) { RAPTOR_AVLTREE_DEBUG1("too low - scan right\n"); rdata = raptor_avltree_delete_internal(tree, &(*node_pp)->right, p_data, rebalancing_p); if(*rebalancing_p) raptor_avltree_balance_right(tree, node_pp, rebalancing_p); } else { raptor_avltree_node *pr_q; RAPTOR_AVLTREE_DEBUG1("equal\n"); pr_q = *node_pp; rdata = pr_q->data; if(pr_q->right == NULL) { RAPTOR_AVLTREE_DEBUG1("right subtree null\n"); *node_pp = pr_q->left; if(*node_pp) (*node_pp)->parent = pr_q->parent; *rebalancing_p = TRUE; } else if(pr_q->left == NULL) { RAPTOR_AVLTREE_DEBUG1("right subtree non-null, left subtree null\n"); *node_pp = pr_q->right; if(*node_pp) (*node_pp)->parent = pr_q->parent; *rebalancing_p = TRUE; } else { RAPTOR_AVLTREE_DEBUG1("neither subtree null\n"); rdata = raptor_avltree_delete_internal2(tree, &pr_q->left, rebalancing_p, &pr_q); if(*rebalancing_p) raptor_avltree_balance_left(tree, node_pp, rebalancing_p); } RAPTOR_FREE(raptor_avltree_node, pr_q); } return rdata; } static void* raptor_avltree_delete_internal2(raptor_avltree* tree, raptor_avltree_node** ppr_r, int *rebalancing_p, raptor_avltree_node** ppr_q) { void* rdata = NULL; RAPTOR_AVLTREE_DEBUG1("Enter\n"); if((*ppr_r)->right != NULL) { rdata = raptor_avltree_delete_internal2(tree, &(*ppr_r)->right, rebalancing_p, ppr_q); if(*rebalancing_p) raptor_avltree_balance_right(tree, ppr_r, rebalancing_p); } else { raptor_avltree_node* ppr_r_left_new_parent; rdata = (*ppr_q)->data; (*ppr_q)->data = (*ppr_r)->data; *ppr_q = *ppr_r; ppr_r_left_new_parent = (*ppr_r)->parent; *ppr_r = (*ppr_r)->left; if(*ppr_r) (*ppr_r)->parent = ppr_r_left_new_parent; *rebalancing_p = TRUE; } return rdata; } static void raptor_avltree_balance_left(raptor_avltree* tree, raptor_avltree_node** node_pp, int *rebalancing_p) { raptor_avltree_node *p1, *p2, *p_parent; int b1, b2; RAPTOR_AVLTREE_DEBUG1("left branch has shrunk\n"); p_parent = (*node_pp)->parent; switch((*node_pp)->balance) { case -1: RAPTOR_AVLTREE_DEBUG1("was imbalanced, fixed implicitly\n"); (*node_pp)->balance = 0; break; case 0: RAPTOR_AVLTREE_DEBUG1("was okay, is now one off\n"); (*node_pp)->balance = 1; *rebalancing_p = FALSE; break; case 1: RAPTOR_AVLTREE_DEBUG1("was already off, this is too much\n"); p1 = (*node_pp)->right; b1 = p1->balance; if(b1 >= 0) { RAPTOR_AVLTREE_DEBUG1("single RR\n"); (*node_pp)->right = p1->left; if((*node_pp)->right) (*node_pp)->right->parent = (*node_pp); p1->left = *node_pp; if(p1->left) p1->left->parent = p1; if(b1 == 0) { RAPTOR_AVLTREE_DEBUG1("b1 == 0\n"); (*node_pp)->balance = 1; p1->balance = -1; *rebalancing_p = FALSE; } else { RAPTOR_AVLTREE_DEBUG1("b1 != 0\n"); (*node_pp)->balance = 0; p1->balance = 0; } *node_pp = p1; (*node_pp)->parent = p_parent; } else { RAPTOR_AVLTREE_DEBUG1("double RL\n"); p2 = p1->left; b2 = p2->balance; p1->left = p2->right; if(p1->left) p1->left->parent = p1; p2->right = p1; if(p2->right) p2->right->parent = p2; (*node_pp)->right = p2->left; if((*node_pp)->right) (*node_pp)->right->parent = (*node_pp); p2->left = *node_pp; if(p2->left) p2->left->parent = p2; if(b2 == 1) (*node_pp)->balance = -1; else (*node_pp)->balance = 0; if(b2 == -1) p1->balance = 1; else p1->balance = 0; *node_pp = p2; (*node_pp)->parent = p_parent; p2->balance = 0; } break; } /* end switch */ } static void raptor_avltree_balance_right(raptor_avltree* tree, raptor_avltree_node** node_pp, int *rebalancing_p) { raptor_avltree_node *p1, *p2, *p_parent; int b1, b2; RAPTOR_AVLTREE_DEBUG1("right branch has shrunk\n"); p_parent = (*node_pp)->parent; switch((*node_pp)->balance) { case 1: RAPTOR_AVLTREE_DEBUG1("was imbalanced, fixed implicitly\n"); (*node_pp)->balance = 0; break; case 0: RAPTOR_AVLTREE_DEBUG1("was okay, is now one off\n"); (*node_pp)->balance = -1; *rebalancing_p = FALSE; break; case -1: RAPTOR_AVLTREE_DEBUG1("was already off, this is too much\n"); p1 = (*node_pp)->left; b1 = p1->balance; if(b1 <= 0) { RAPTOR_AVLTREE_DEBUG1("single LL\n"); (*node_pp)->left = p1->right; if((*node_pp)->left) (*node_pp)->left->parent = (*node_pp); p1->right = *node_pp; if(p1->right) p1->right->parent = p1; if(b1 == 0) { RAPTOR_AVLTREE_DEBUG1("b1 == 0\n"); (*node_pp)->balance = -1; p1->balance = 1; *rebalancing_p = FALSE; } else { RAPTOR_AVLTREE_DEBUG1("b1 != 0\n"); (*node_pp)->balance = 0; p1->balance = 0; } *node_pp = p1; (*node_pp)->parent = p_parent; } else { RAPTOR_AVLTREE_DEBUG1("double LR\n"); p2 = p1->right; b2 = p2->balance; p1->right = p2->left; if(p1->right) p1->right->parent = p1; p2->left = p1; if(p2->left) p2->left->parent = p2; (*node_pp)->left = p2->right; if((*node_pp)->left) (*node_pp)->left->parent = (*node_pp); p2->right = *node_pp; if(p2->right) p2->right->parent = p2; if(b2 == -1) (*node_pp)->balance = 1; else (*node_pp)->balance = 0; if(b2 == 1) p1->balance = -1; else p1->balance = 0; *node_pp = p2; (*node_pp)->parent = p_parent; p2->balance = 0; } } /* end switch */ } /** * raptor_avltree_size: * @tree: AVL Tree object * * Get the number of items in the AVL Tree * * Return value: number of items in tree */ int raptor_avltree_size(raptor_avltree* tree) { return tree->size; } /** * raptor_avltree_set_print_handler: * @tree: AVL Tree object * @print_handler: print function * * Set the handler for printing an item in a tree * */ void raptor_avltree_set_print_handler(raptor_avltree* tree, raptor_data_print_handler print_handler) { tree->print_handler = print_handler; } /* Follow left children until a match for range is found (if range not NULL) */ static raptor_avltree_node* raptor_avltree_node_leftmost(raptor_avltree* tree, raptor_avltree_node* node, void* range) { /*assert(node); assert(!range || tree->compare_handler(range, node->data) == 0);*/ if(range) while(node && node->left && tree->compare_handler(range, node->left->data) == 0) node = node->left; else while(node && node->left) node = node->left; return node; } static raptor_avltree_node* raptor_avltree_node_rightmost(raptor_avltree* tree, raptor_avltree_node* node, void* range) { /*assert(node); assert(!range || tree->compare_handler(range, node->data) == 0);*/ if(range) while(node && node->right && tree->compare_handler(range, node->right->data) == 0) node = node->right; else while(node && node->right) node = node->right; return node; } /* Follow right children until a match for range is found (range required) */ static raptor_avltree_node* raptor_avltree_node_search_right(raptor_avltree* tree, raptor_avltree_node* node, void* range) { raptor_avltree_node* result; if(!node) return NULL; result = node->right; while(result) { if(tree->compare_handler(range, result->data) == 0) { return result; } else { result = result->right; } } return node; } /* Follow left children until a match for range is found (range required) */ static raptor_avltree_node* raptor_avltree_node_search_left(raptor_avltree* tree, raptor_avltree_node* node, void* range) { raptor_avltree_node* result; if(!node) return NULL; result = node->left; while(result) { if(tree->compare_handler(range, result->data) == 0) { return result; } else { result = result->left; } } return node; } static raptor_avltree_node* raptor_avltree_node_prev(raptor_avltree* tree, raptor_avltree_node* node, void* range) { int up = 0; /*assert(!range || tree->compare_handler(range, node->data) == 0);*/ if(node->left) { /* Should never go left if the current node is already < range */ raptor_avltree_node* prev; prev = raptor_avltree_node_rightmost(tree, node->left, NULL); /*assert(!range ||tree->compare_handler(range, node->data) <= 0);*/ if(range) { if(tree->compare_handler(range, prev->data) == 0) { up = 0; node = prev; } else { up = 1; } } else { node = prev; up = 0; } } else { up = 1; } if(up) { raptor_avltree_node* last = node; /* Need to go up */ node = node->parent; while(node) { /* moving from right subtree to this node */ if(node->right && last == node->right) { break; } /* moved up to find an unvisited left subtree */ if(node->left && last != node->left) { /* Should never go left if the current node is already > range */ /*assert(!range ||tree->compare_handler(range, node->data) <= 0);*/ node = raptor_avltree_node_rightmost(tree, node->left, range); break; } last = node; node = node->parent; } } if(node && range) { if(tree->compare_handler(range, node->data) == 0) return node; else return NULL; } else { return node; } } /* Follow right children until a match for range is found (if range not NULL) */ static raptor_avltree_node* raptor_avltree_node_next(raptor_avltree* tree, raptor_avltree_node* node, void* range) { int up = 0; /*assert(!range || tree->compare_handler(range, node->data) == 0);*/ if(node->right) { /* Should never go right if the current node is already > range */ raptor_avltree_node* next; next = raptor_avltree_node_leftmost(tree, node->right, NULL); /*assert(!range ||tree->compare_handler(range, node->data) <= 0);*/ if(range) { if(tree->compare_handler(range, next->data) == 0) { up = 0; node = next; } else { up = 1; } } else { node = next; up = 0; } } else { up = 1; } if(up) { raptor_avltree_node* last = node; /* Need to go up */ node = node->parent; while(node) { /* moving from left subtree to this node */ if(node->left && last == node->left) { break; } /* moved up to find an unvisited right subtree */ if(node->right && last != node->right) { /* Should never go right if the current node is already > range */ /*assert(!range ||tree->compare_handler(range, node->data) <= 0);*/ node = raptor_avltree_node_leftmost(tree, node->right, range); break; } last = node; node = node->parent; } } if(node && range) { if(tree->compare_handler(range, node->data) == 0) return node; else return NULL; } else { return node; } } struct raptor_avltree_iterator_s { raptor_avltree* tree; raptor_avltree_node* root; raptor_avltree_node* current; void* range; raptor_data_free_handler range_free_handler; int direction; int is_finished; }; /** * raptor_new_avltree_iterator: * @tree: #raptor_avltree object * @range: range * @range_free_handler: function to free @range object * @direction: <0 to go 'backwards' otherwise 'forwards' * * Get an in-order iterator for the start of a range, or the entire contents * * If range is NULL, the entire tree is walked in order. If range * specifies a range (i.e. the tree comparison function will 'match' * (return 0 for) range and /several/ nodes), the iterator will be * placed at the leftmost child matching range, and * raptor_avltree_iterator_next will iterate over all nodes (and only * nodes) that match range. * * Return value: a new #raptor_avltree_iterator object or NULL on failure **/ raptor_avltree_iterator* raptor_new_avltree_iterator(raptor_avltree* tree, void* range, raptor_data_free_handler range_free_handler, int direction) { raptor_avltree_iterator* iterator; iterator = RAPTOR_CALLOC(raptor_avltree_iterator*, 1, sizeof(*iterator)); if(!iterator) return NULL; iterator->is_finished = 0; iterator->current = NULL; iterator->tree = tree; iterator->range = range; iterator->range_free_handler = range_free_handler; iterator->direction = direction; if(range) { /* find the topmost match (range is contained entirely in tree * rooted here) */ iterator->current = raptor_avltree_search_internal(tree, tree->root, range); } else { iterator->current = tree->root; } iterator->root = iterator->current; if(iterator->current) { if(iterator->direction < 0) { /* go down to find END of range (or tree) */ while(1) { raptor_avltree_node* pred; iterator->current = raptor_avltree_node_rightmost(tree, iterator->current, range); /* move left until a match is found */ pred = raptor_avltree_node_search_left(tree, iterator->current->right, range); if(pred && tree->compare_handler(range, pred->data) == 0) iterator->current = pred; else break; } } else { /* go down to find START of range (or tree) */ while(1) { raptor_avltree_node* pred; iterator->current = raptor_avltree_node_leftmost(tree, iterator->current, range); /* move right until a match is found */ pred = raptor_avltree_node_search_right(tree, iterator->current->left, range); if(pred && tree->compare_handler(range, pred->data) == 0) iterator->current = pred; else break; } } } return iterator; } /** * raptor_free_avltree_iterator: * @iterator: AVL Tree iterator object * * AVL Tree Iterator destructor */ void raptor_free_avltree_iterator(raptor_avltree_iterator* iterator) { if(!iterator) return; if(iterator->range && iterator->range_free_handler) iterator->range_free_handler(iterator->range); RAPTOR_FREE(raptor_avltree_iterator, iterator); } /** * raptor_avltree_iterator_is_end: * @iterator: AVL Tree iterator object * * Test if an iteration is finished * * Return value: non-0 if iteration is finished */ int raptor_avltree_iterator_is_end(raptor_avltree_iterator* iterator) { raptor_avltree_node *node = iterator->current; if(iterator->is_finished) return 1; iterator->is_finished = (node == NULL); return iterator->is_finished; } /** * raptor_avltree_iterator_next: * @iterator: AVL Tree iterator object * * Move iteration to next/prev object * * Return value: non-0 if iteration is finished */ int raptor_avltree_iterator_next(raptor_avltree_iterator* iterator) { raptor_avltree_node *node = iterator->current; if(!node || iterator->is_finished) return 1; if(iterator->direction < 0) iterator->current = raptor_avltree_node_prev(iterator->tree, node, iterator->range); else iterator->current = raptor_avltree_node_next(iterator->tree, node, iterator->range); /* Stay within rooted subtree */ if(iterator->root->parent == iterator->current) iterator->current = NULL; iterator->is_finished = (iterator->current == NULL); return iterator->is_finished; } /** * raptor_avltree_iterator_get: * @iterator: AVL Tree iterator object * * Get current iteration object * * Return value: object or NULL if iteration is finished */ void* raptor_avltree_iterator_get(raptor_avltree_iterator* iterator) { raptor_avltree_node *node = iterator->current; if(iterator->is_finished) return NULL; iterator->is_finished = (node == NULL); if(iterator->is_finished) return NULL; return node->data; } /** * raptor_avltree_print: * @tree: AVL Tree * @stream: stream to print to * * Print the items in the tree in order to a stream (for debugging) * * Return value: non-0 on failure */ int raptor_avltree_print(raptor_avltree* tree, FILE* stream) { int i; int rv = 0; raptor_avltree_iterator* iter = NULL; fprintf(stream, "AVL Tree size %u\n", tree->size); for(i = 0, (iter = raptor_new_avltree_iterator(tree, NULL, NULL, 1)); iter && !rv; i++, (rv = raptor_avltree_iterator_next(iter))) { void* data = raptor_avltree_iterator_get(iter); if(!data) continue; fprintf(stream, "%d) ", i); if(tree->print_handler) tree->print_handler(data, stream); else fprintf(stream, "Data Node %p\n", RAPTOR_VOIDP(data)); } /*assert(i == tree->size);*/ if(iter) raptor_free_avltree_iterator(iter); return 0; } #ifdef RAPTOR_DEBUG static int raptor_avltree_dump_internal(raptor_avltree* tree, raptor_avltree_node* node, int depth, FILE* stream) { int i; if(!node) return TRUE; for(i = 0; i < depth; i++) fputs(" ", stream); fprintf(stream, "Node %p: parent %p left %p right %p data %p\n", RAPTOR_VOIDP(node), RAPTOR_VOIDP(node->parent), RAPTOR_VOIDP(node->left), RAPTOR_VOIDP(node->right), RAPTOR_VOIDP(node->data)); if(tree->print_handler) { for(i= 0; i < depth; i++) fputs(" ", stream); tree->print_handler(node->data, stream); } if(!raptor_avltree_dump_internal(tree, node->left, depth+1, stream)) return FALSE; if(!raptor_avltree_dump_internal(tree, node->right, depth+1, stream)) return FALSE; return TRUE; } /* debugging tree dump with pointers and depth indenting */ int raptor_avltree_dump(raptor_avltree* tree, FILE* stream) { fprintf(stream, "Dumping avltree %p size %u\n", RAPTOR_VOIDP(tree), tree->size); return raptor_avltree_dump_internal(tree, tree->root, 0, stream); } static void raptor_avltree_check_internal(raptor_avltree* tree, raptor_avltree_node* node, unsigned int* count_p) { if(!node) return; (*count_p)++; raptor_avltree_check_node(tree, node, NULL, NULL); raptor_avltree_check_internal(tree, node->left, count_p); raptor_avltree_check_internal(tree, node->right, count_p); } /* debugging tree check - parent/child pointers and counts */ void raptor_avltree_check(raptor_avltree* tree) { unsigned int count = 0; raptor_avltree_check_internal(tree, tree->root, &count); if(count != tree->size) { fprintf(stderr, "Tree %p nodes count is %u. actual count %u\n", RAPTOR_VOIDP(tree), tree->size, count); abort(); } } #endif #endif #ifdef STANDALONE #include typedef struct { FILE *fh; int count; const char** results; int failed; } visit_state; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 static int print_string(int depth, void* data, void *user_data) { visit_state* vs = (visit_state*)user_data; fprintf(vs->fh, "%3d: %s\n", vs->count, (char*) data); vs->count++; return 1; } #endif static int check_string(int depth, void* data, void *user_data) { visit_state* vs = (visit_state*)user_data; const char* result = vs->results[vs->count]; if(strcmp((const char*)data, result)) { fprintf(vs->fh, "%3d: Expected '%s' but found '%s'\n", vs->count, result, (char*)data); vs->failed = 1; } vs->count++; return 1; } static int compare_strings(const void *l, const void *r) { return strcmp((const char*)l, (const char*)r); } /* one more prototype */ int main(int argc, char *argv[]); int main(int argc, char *argv[]) { raptor_world *world; const char *program = raptor_basename(argv[0]); #define ITEM_COUNT 8 const char *items[ITEM_COUNT+1] = { "ron", "amy", "jen", "bij", "jib", "daj", "jim", "def", NULL }; #define DELETE_COUNT 2 const char *delete_items[DELETE_COUNT+1] = { "jen", "jim", NULL }; #define RESULT_COUNT (ITEM_COUNT-DELETE_COUNT) const char *results[RESULT_COUNT+1] = { "amy", "bij", "daj", "def", "jib", "ron", NULL}; raptor_avltree* tree; raptor_avltree_iterator* iter; visit_state vs; int i; world = raptor_new_world(); if(!world || raptor_world_open(world)) exit(1); tree = raptor_new_avltree(compare_strings, NULL, /* no free as they are static pointers above */ 0); if(!tree) { fprintf(stderr, "%s: Failed to create tree\n", program); exit(1); } for(i = 0; items[i]; i++) { int rc; void* node; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 fprintf(stderr, "%s: Adding tree item '%s'\n", program, items[i]); #endif rc = raptor_avltree_add(tree, (void*)items[i]); if(rc) { fprintf(stderr, "%s: Adding tree item %d '%s' failed, returning error %d\n", program, i, items[i], rc); exit(1); } #ifdef RAPTOR_DEBUG raptor_avltree_check(tree); #endif node = raptor_avltree_search(tree, (void*)items[i]); if(!node) { fprintf(stderr, "%s: Tree did NOT contain item %d '%s' as expected\n", program, i, items[i]); exit(1); } } #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 fprintf(stderr, "%s: Printing tree\n", program); vs.fh = stderr; vs.count = 0; raptor_avltree_visit(tree, print_string, &vs); fprintf(stderr, "%s: Dumping tree\n", program); raptor_avltree_dump(tree, stderr); #endif for(i = 0; delete_items[i]; i++) { int rc; #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 fprintf(stderr, "%s: Deleting tree item '%s'\n", program, delete_items[i]); #endif rc = raptor_avltree_delete(tree, (void*)delete_items[i]); if(!rc) { fprintf(stderr, "%s: Deleting tree item %d '%s' failed, returning error %d\n", program, i, delete_items[i], rc); exit(1); } #ifdef RAPTOR_DEBUG raptor_avltree_check(tree); #endif } #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 fprintf(stderr, "%s: Walking tree forwards via iterator\n", program); #endif iter = raptor_new_avltree_iterator(tree, NULL, NULL, 1); for(i = 0; 1; i++) { const char* data = (const char*)raptor_avltree_iterator_get(iter); const char* result = results[i]; if((!data && data != result) || (data && strcmp(data, result))) { fprintf(stderr, "%3d: Forwards iterator expected '%s' but found '%s'\n", i, result, data); exit(1); } #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 fprintf(stderr, "%3d: Got '%s'\n", i, data); #endif if(raptor_avltree_iterator_next(iter)) break; if(i > RESULT_COUNT) { fprintf(stderr, "Forward iterator did not end on result %i as expected\n", i); exit(1); } } raptor_free_avltree_iterator(iter); #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 fprintf(stderr, "%s: Checking tree\n", program); #endif vs.count = 0; vs.results = results; vs.failed = 0; raptor_avltree_visit(tree, check_string, &vs); if(vs.failed) { fprintf(stderr, "%s: Checking tree failed\n", program); exit(1); } for(i = 0; results[i]; i++) { const char* result = results[i]; char* data = (char*)raptor_avltree_remove(tree, (void*)result); if(!data) { fprintf(stderr, "%s: remove %i failed at item '%s'\n", program, i, result); exit(1); } if(strcmp(data, result)) { fprintf(stderr, "%s: remove %i returned %s not %s as expected\n", program, i, data, result); exit(1); } } #if defined(RAPTOR_DEBUG) && RAPTOR_DEBUG > 1 fprintf(stderr, "%s: Freeing tree\n", program); #endif raptor_free_avltree(tree); raptor_free_world(world); /* keep gcc -Wall happy */ return(0); } #endif