/* $NetBSD: tree.c,v 1.1.1.2 2012/09/09 16:08:00 christos Exp $ */ #ifndef LINT static const char rcsid[] = "Id: tree.c,v 1.4 2005/04/27 04:56:39 sra Exp "; #endif /*% * tree - balanced binary tree library * * vix 05apr94 [removed vixie.h dependencies; cleaned up formatting, names] * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes] * vix 23jun86 [added delete uar to add for replaced nodes] * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224] * vix 06feb86 [added tree_mung()] * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221] * vix 14dec85 [written] */ /*% * 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. Any errors in the conversion from Modula-2 to C are Paul * Vixie's. */ /* * Copyright (c) 2004 by Internet Systems Consortium, Inc. ("ISC") * Portions Copyright (c) 1996-1999 by Internet Software Consortium. * * Permission to use, copy, modify, and distribute this software for any * purpose with or without fee is hereby granted, provided that the above * copyright notice and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ /*#define DEBUG "tree"*/ #include "port_before.h" #include #include #include "port_after.h" #include #include #ifdef DEBUG static int debugDepth = 0; static char *debugFuncs[256]; # define ENTER(proc) { \ debugFuncs[debugDepth] = proc; \ fprintf(stderr, "ENTER(%d:%s.%s)\n", \ debugDepth, DEBUG, \ debugFuncs[debugDepth]); \ debugDepth++; \ } # define RET(value) { \ debugDepth--; \ fprintf(stderr, "RET(%d:%s.%s)\n", \ debugDepth, DEBUG, \ debugFuncs[debugDepth]); \ return (value); \ } # define RETV { \ debugDepth--; \ fprintf(stderr, "RETV(%d:%s.%s)\n", \ debugDepth, DEBUG, \ debugFuncs[debugDepth]); \ return; \ } # define MSG(msg) fprintf(stderr, "MSG(%s)\n", msg); #else # define ENTER(proc) ; # define RET(value) return (value); # define RETV return; # define MSG(msg) ; #endif #ifndef TRUE # define TRUE 1 # define FALSE 0 #endif static tree * sprout(tree **, tree_t, int *, int (*)(), void (*)()); static int delete(tree **, int (*)(), tree_t, void (*)(), int *, int *); static void del(tree **, int *, tree **, void (*)(), int *); static void bal_L(tree **, int *); static void bal_R(tree **, int *); void tree_init(tree **ppr_tree) { ENTER("tree_init") *ppr_tree = NULL; RETV } tree_t tree_srch(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t), tree_t p_user) { ENTER("tree_srch") if (*ppr_tree) { int i_comp = (*pfi_compare)(p_user, (**ppr_tree).data); if (i_comp > 0) RET(tree_srch(&(**ppr_tree).right, pfi_compare, p_user)) if (i_comp < 0) RET(tree_srch(&(**ppr_tree).left, pfi_compare, p_user)) /* not higher, not lower... this must be the one. */ RET((**ppr_tree).data) } /* grounded. NOT found. */ RET(NULL) } tree_t tree_add(tree **ppr_tree, int (*pfi_compare)(tree_t, tree_t), tree_t p_user, void (*pfv_uar)()) { int i_balance = FALSE; ENTER("tree_add") if (!sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar)) RET(NULL) RET(p_user) } int tree_delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t), tree_t p_user, void (*pfv_uar)()) { int i_balance = FALSE, i_uar_called = FALSE; ENTER("tree_delete"); RET(delete(ppr_p, pfi_compare, p_user, pfv_uar, &i_balance, &i_uar_called)) } int tree_trav(tree **ppr_tree, int (*pfi_uar)(tree_t)) { ENTER("tree_trav") if (!*ppr_tree) RET(TRUE) if (!tree_trav(&(**ppr_tree).left, pfi_uar)) RET(FALSE) if (!(*pfi_uar)((**ppr_tree).data)) RET(FALSE) if (!tree_trav(&(**ppr_tree).right, pfi_uar)) RET(FALSE) RET(TRUE) } void tree_mung(tree **ppr_tree, void (*pfv_uar)(tree_t)) { ENTER("tree_mung") if (*ppr_tree) { tree_mung(&(**ppr_tree).left, pfv_uar); tree_mung(&(**ppr_tree).right, pfv_uar); if (pfv_uar) (*pfv_uar)((**ppr_tree).data); memput(*ppr_tree, sizeof(tree)); *ppr_tree = NULL; } RETV } static tree * sprout(tree **ppr, tree_t p_data, int *pi_balance, int (*pfi_compare)(tree_t, tree_t), void (*pfv_delete)(tree_t)) { tree *p1, *p2, *sub; int cmp; ENTER("sprout") /* are we grounded? if so, add the node "here" and set the rebalance * flag, then exit. */ if (!*ppr) { MSG("grounded. adding new node, setting h=true") *ppr = (tree *) memget(sizeof(tree)); if (*ppr) { (*ppr)->left = NULL; (*ppr)->right = NULL; (*ppr)->bal = 0; (*ppr)->data = p_data; *pi_balance = TRUE; } RET(*ppr); } /* compare the data using routine passed by caller. */ cmp = (*pfi_compare)(p_data, (*ppr)->data); /* if LESS, prepare to move to the left. */ if (cmp < 0) { MSG("LESS. sprouting left.") sub = sprout(&(*ppr)->left, p_data, pi_balance, pfi_compare, pfv_delete); if (sub && *pi_balance) { /*%< left branch has grown */ MSG("LESS: left branch has grown") switch ((*ppr)->bal) { case 1: /* right branch WAS longer; bal is ok now */ MSG("LESS: case 1.. bal restored implicitly") (*ppr)->bal = 0; *pi_balance = FALSE; break; case 0: /* balance WAS okay; now left branch longer */ MSG("LESS: case 0.. balnce bad but still ok") (*ppr)->bal = -1; break; case -1: /* left branch was already too long. rebal */ MSG("LESS: case -1: rebalancing") p1 = (*ppr)->left; if (p1->bal == -1) { /*%< LL */ MSG("LESS: single LL") (*ppr)->left = p1->right; p1->right = *ppr; (*ppr)->bal = 0; *ppr = p1; } else { /*%< double LR */ MSG("LESS: double LR") p2 = p1->right; p1->right = p2->left; p2->left = p1; (*ppr)->left = p2->right; p2->right = *ppr; if (p2->bal == -1) (*ppr)->bal = 1; else (*ppr)->bal = 0; if (p2->bal == 1) p1->bal = -1; else p1->bal = 0; *ppr = p2; } /*else*/ (*ppr)->bal = 0; *pi_balance = FALSE; } /*switch*/ } /*if*/ RET(sub) } /*if*/ /* if MORE, prepare to move to the right. */ if (cmp > 0) { MSG("MORE: sprouting to the right") sub = sprout(&(*ppr)->right, p_data, pi_balance, pfi_compare, pfv_delete); if (sub && *pi_balance) { MSG("MORE: right branch has grown") switch ((*ppr)->bal) { case -1: MSG("MORE: balance was off, fixed implicitly") (*ppr)->bal = 0; *pi_balance = FALSE; break; case 0: MSG("MORE: balance was okay, now off but ok") (*ppr)->bal = 1; break; case 1: MSG("MORE: balance was off, need to rebalance") p1 = (*ppr)->right; if (p1->bal == 1) { /*%< RR */ MSG("MORE: single RR") (*ppr)->right = p1->left; p1->left = *ppr; (*ppr)->bal = 0; *ppr = p1; } else { /*%< double RL */ MSG("MORE: double RL") p2 = p1->left; p1->left = p2->right; p2->right = p1; (*ppr)->right = p2->left; p2->left = *ppr; if (p2->bal == 1) (*ppr)->bal = -1; else (*ppr)->bal = 0; if (p2->bal == -1) p1->bal = 1; else p1->bal = 0; *ppr = p2; } /*else*/ (*ppr)->bal = 0; *pi_balance = FALSE; } /*switch*/ } /*if*/ RET(sub) } /*if*/ /* not less, not more: this is the same key! replace... */ MSG("FOUND: Replacing data value") *pi_balance = FALSE; if (pfv_delete) (*pfv_delete)((*ppr)->data); (*ppr)->data = p_data; RET(*ppr) } static int delete(tree **ppr_p, int (*pfi_compare)(tree_t, tree_t), tree_t p_user, void (*pfv_uar)(tree_t), int *pi_balance, int *pi_uar_called) { tree *pr_q; int i_comp, i_ret; ENTER("delete") if (*ppr_p == NULL) { MSG("key not in tree") RET(FALSE) } i_comp = (*pfi_compare)((*ppr_p)->data, p_user); if (i_comp > 0) { MSG("too high - scan left") i_ret = delete(&(*ppr_p)->left, pfi_compare, p_user, pfv_uar, pi_balance, pi_uar_called); if (*pi_balance) bal_L(ppr_p, pi_balance); } else if (i_comp < 0) { MSG("too low - scan right") i_ret = delete(&(*ppr_p)->right, pfi_compare, p_user, pfv_uar, pi_balance, pi_uar_called); if (*pi_balance) bal_R(ppr_p, pi_balance); } else { MSG("equal") pr_q = *ppr_p; if (pr_q->right == NULL) { MSG("right subtree null") *ppr_p = pr_q->left; *pi_balance = TRUE; } else if (pr_q->left == NULL) { MSG("right subtree non-null, left subtree null") *ppr_p = pr_q->right; *pi_balance = TRUE; } else { MSG("neither subtree null") del(&pr_q->left, pi_balance, &pr_q, pfv_uar, pi_uar_called); if (*pi_balance) bal_L(ppr_p, pi_balance); } if (!*pi_uar_called && pfv_uar) (*pfv_uar)(pr_q->data); /* Thanks to wuth@castrov.cuc.ab.ca for the following stmt. */ memput(pr_q, sizeof(tree)); i_ret = TRUE; } RET(i_ret) } static void del(tree **ppr_r, int *pi_balance, tree **ppr_q, void (*pfv_uar)(tree_t), int *pi_uar_called) { ENTER("del") if ((*ppr_r)->right != NULL) { del(&(*ppr_r)->right, pi_balance, ppr_q, pfv_uar, pi_uar_called); if (*pi_balance) bal_R(ppr_r, pi_balance); } else { if (pfv_uar) (*pfv_uar)((*ppr_q)->data); *pi_uar_called = TRUE; (*ppr_q)->data = (*ppr_r)->data; *ppr_q = *ppr_r; *ppr_r = (*ppr_r)->left; *pi_balance = TRUE; } RETV } static void bal_L(tree **ppr_p, int *pi_balance) { tree *p1, *p2; int b1, b2; ENTER("bal_L") MSG("left branch has shrunk") switch ((*ppr_p)->bal) { case -1: MSG("was imbalanced, fixed implicitly") (*ppr_p)->bal = 0; break; case 0: MSG("was okay, is now one off") (*ppr_p)->bal = 1; *pi_balance = FALSE; break; case 1: MSG("was already off, this is too much") p1 = (*ppr_p)->right; b1 = p1->bal; if (b1 >= 0) { MSG("single RR") (*ppr_p)->right = p1->left; p1->left = *ppr_p; if (b1 == 0) { MSG("b1 == 0") (*ppr_p)->bal = 1; p1->bal = -1; *pi_balance = FALSE; } else { MSG("b1 != 0") (*ppr_p)->bal = 0; p1->bal = 0; } *ppr_p = p1; } else { MSG("double RL") p2 = p1->left; b2 = p2->bal; p1->left = p2->right; p2->right = p1; (*ppr_p)->right = p2->left; p2->left = *ppr_p; if (b2 == 1) (*ppr_p)->bal = -1; else (*ppr_p)->bal = 0; if (b2 == -1) p1->bal = 1; else p1->bal = 0; *ppr_p = p2; p2->bal = 0; } } RETV } static void bal_R(tree **ppr_p, int *pi_balance) { tree *p1, *p2; int b1, b2; ENTER("bal_R") MSG("right branch has shrunk") switch ((*ppr_p)->bal) { case 1: MSG("was imbalanced, fixed implicitly") (*ppr_p)->bal = 0; break; case 0: MSG("was okay, is now one off") (*ppr_p)->bal = -1; *pi_balance = FALSE; break; case -1: MSG("was already off, this is too much") p1 = (*ppr_p)->left; b1 = p1->bal; if (b1 <= 0) { MSG("single LL") (*ppr_p)->left = p1->right; p1->right = *ppr_p; if (b1 == 0) { MSG("b1 == 0") (*ppr_p)->bal = -1; p1->bal = 1; *pi_balance = FALSE; } else { MSG("b1 != 0") (*ppr_p)->bal = 0; p1->bal = 0; } *ppr_p = p1; } else { MSG("double LR") p2 = p1->right; b2 = p2->bal; p1->right = p2->left; p2->left = p1; (*ppr_p)->left = p2->right; p2->right = *ppr_p; if (b2 == -1) (*ppr_p)->bal = 1; else (*ppr_p)->bal = 0; if (b2 == 1) p1->bal = -1; else p1->bal = 0; *ppr_p = p2; p2->bal = 0; } } RETV } /*! \file */