/* 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. */ /*#define DEBUG "tree"*/ #include <stdio.h> #include <stdlib.h> #include "vixie.h" #include "tree.h" #ifdef DEBUG #undef DEBUG #endif #include "debug.h" #ifdef __STDC__ #define __P(x) x #else #define __P(x) () #endif static void sprout __P((tree **, tree_t, int *, int (*)(), void (*)())); static int delete __P((tree **, int (*)(), tree_t, void (*)(), int *, int *)); static void del __P((tree **, int *, tree **, void (*)(), int *)); static void bal_L __P((tree **, int *)); static void bal_R __P((tree **, int *)); #undef __P void tree_init(tree ** ppr_tree) { ENTER("tree_init"); *ppr_tree = NULL; EXITV; } tree_t tree_srch(tree ** ppr_tree, int (*pfi_compare) ( /* ??? */ ), tree_t p_user) { register int i_comp; ENTER("tree_srch"); if (*ppr_tree) { i_comp = (*pfi_compare) (p_user, (**ppr_tree).tree_p); if (i_comp > 0) EXIT(tree_srch(&(**ppr_tree).tree_r, pfi_compare, p_user)); if (i_comp < 0) EXIT(tree_srch(&(**ppr_tree).tree_l, pfi_compare, p_user)); /* not higher, not lower... this must be the one. */ EXIT((**ppr_tree).tree_p); } /* grounded. NOT found. */ EXIT(NULL); } void tree_add(tree ** ppr_tree, int (*pfi_compare) ( /* ??? */ ), tree_t p_user, void (*pfv_uar) ( /* ??? */ )) { int i_balance = FALSE; ENTER("tree_add"); sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar); EXITV; } int tree_delete(tree ** ppr_p, int (*pfi_compare) ( /* ??? */ ), tree_t p_user, void (*pfv_uar) ( /* ??? */ )) { int i_balance = FALSE, i_uar_called = FALSE; ENTER("tree_delete"); EXIT(delete(ppr_p, pfi_compare, p_user, pfv_uar, &i_balance, &i_uar_called)); } int tree_trav(tree ** ppr_tree, int (*pfi_uar) ( /* ??? */ )) { ENTER("tree_trav"); if (!*ppr_tree) EXIT(TRUE); if (!tree_trav(&(**ppr_tree).tree_l, pfi_uar)) EXIT(FALSE); if (!(*pfi_uar) ((**ppr_tree).tree_p)) EXIT(FALSE); if (!tree_trav(&(**ppr_tree).tree_r, pfi_uar)) EXIT(FALSE); EXIT(TRUE); } void tree_mung(tree ** ppr_tree, void (*pfv_uar) ( /* ??? */ )) { ENTER("tree_mung"); if (*ppr_tree) { tree_mung(&(**ppr_tree).tree_l, pfv_uar); tree_mung(&(**ppr_tree).tree_r, pfv_uar); if (pfv_uar) (*pfv_uar) ((**ppr_tree).tree_p); free(*ppr_tree); *ppr_tree = NULL; } EXITV; } static void sprout(tree ** ppr, tree_t p_data, int *pi_balance, int (*pfi_compare) ( /* ??? */ ), void (*pfv_delete) ( /* ??? */ )) { tree *p1, *p2; int cmp; ENTER("sprout"); /* are we grounded? if so, add the node "here" and set the rebalance * flag, then exit. */ if (!*ppr) { dprintk("grounded. adding new node, setting h=true"); *ppr = (tree *) malloc(sizeof(tree)); (*ppr)->tree_l = NULL; (*ppr)->tree_r = NULL; (*ppr)->tree_b = 0; (*ppr)->tree_p = p_data; *pi_balance = TRUE; EXITV; } /* compare the data using routine passed by caller. */ cmp = (*pfi_compare) (p_data, (*ppr)->tree_p); /* if LESS, prepare to move to the left. */ if (cmp < 0) { dprintk("LESS. sprouting left."); sprout(&(*ppr)->tree_l, p_data, pi_balance, pfi_compare, pfv_delete); if (*pi_balance) { /* left branch has grown longer */ dprintk("LESS: left branch has grown"); switch ((*ppr)->tree_b) { case 1: /* right branch WAS longer; balance is ok now */ dprintk("LESS: case 1.. balnce restored implicitly"); (*ppr)->tree_b = 0; *pi_balance = FALSE; break; case 0: /* balance WAS okay; now left branch longer */ dprintk("LESS: case 0.. balnce bad but still ok"); (*ppr)->tree_b = -1; break; case -1: /* left branch was already too long. rebalnce */ dprintk("LESS: case -1: rebalancing"); p1 = (*ppr)->tree_l; if (p1->tree_b == -1) { /* LL */ dprintk("LESS: single LL"); (*ppr)->tree_l = p1->tree_r; p1->tree_r = *ppr; (*ppr)->tree_b = 0; *ppr = p1; } else { /* double LR */ dprintk("LESS: double LR"); p2 = p1->tree_r; p1->tree_r = p2->tree_l; p2->tree_l = p1; (*ppr)->tree_l = p2->tree_r; p2->tree_r = *ppr; if (p2->tree_b == -1) (*ppr)->tree_b = 1; else (*ppr)->tree_b = 0; if (p2->tree_b == 1) p1->tree_b = -1; else p1->tree_b = 0; *ppr = p2; } /*else */ (*ppr)->tree_b = 0; *pi_balance = FALSE; } /*switch */ } /*if */ EXITV; } /*if */ /* if MORE, prepare to move to the right. */ if (cmp > 0) { dprintk("MORE: sprouting to the right"); sprout(&(*ppr)->tree_r, p_data, pi_balance, pfi_compare, pfv_delete); if (*pi_balance) { /* right branch has grown longer */ dprintk("MORE: right branch has grown"); switch ((*ppr)->tree_b) { case -1: dprintk("MORE: balance was off, fixed implicitly"); (*ppr)->tree_b = 0; *pi_balance = FALSE; break; case 0: dprintk("MORE: balance was okay, now off but ok"); (*ppr)->tree_b = 1; break; case 1: dprintk("MORE: balance was off, need to rebalance"); p1 = (*ppr)->tree_r; if (p1->tree_b == 1) { /* RR */ dprintk("MORE: single RR"); (*ppr)->tree_r = p1->tree_l; p1->tree_l = *ppr; (*ppr)->tree_b = 0; *ppr = p1; } else { /* double RL */ dprintk("MORE: double RL"); p2 = p1->tree_l; p1->tree_l = p2->tree_r; p2->tree_r = p1; (*ppr)->tree_r = p2->tree_l; p2->tree_l = *ppr; if (p2->tree_b == 1) (*ppr)->tree_b = -1; else (*ppr)->tree_b = 0; if (p2->tree_b == -1) p1->tree_b = 1; else p1->tree_b = 0; *ppr = p2; } /*else */ (*ppr)->tree_b = 0; *pi_balance = FALSE; } /*switch */ } /*if */ EXITV; } /*if */ /* not less, not more: this is the same key! replace... */ dprintk("I found it! Replacing data value"); *pi_balance = FALSE; if (pfv_delete) (*pfv_delete) ((*ppr)->tree_p); (*ppr)->tree_p = p_data; EXITV; } static int delete(tree ** ppr_p, int (*pfi_compare) ( /* ??? */ ), tree_t p_user, void (*pfv_uar) ( /* ??? */ ), int *pi_balance, int *pi_uar_called) { tree *pr_q; int i_comp, i_ret; ENTER("delete"); if (*ppr_p == NULL) { dprintk("key not in tree"); EXIT(FALSE); } i_comp = (*pfi_compare) ((*ppr_p)->tree_p, p_user); if (i_comp > 0) { dprintk("too high - scan left"); i_ret = delete(&(*ppr_p)->tree_l, 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) { dprintk("too low - scan right"); i_ret = delete(&(*ppr_p)->tree_r, pfi_compare, p_user, pfv_uar, pi_balance, pi_uar_called); if (*pi_balance) bal_R(ppr_p, pi_balance); } else { dprintk("equal"); pr_q = *ppr_p; if (pr_q->tree_r == NULL) { dprintk("right subtree null"); *ppr_p = pr_q->tree_l; *pi_balance = TRUE; } else if (pr_q->tree_l == NULL) { dprintk("right subtree non-null, left subtree null"); *ppr_p = pr_q->tree_r; *pi_balance = TRUE; } else { dprintk("neither subtree null"); del(&pr_q->tree_l, 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->tree_p); free(pr_q); /* thanks to wuth@castrov.cuc.ab.ca */ i_ret = TRUE; } EXIT(i_ret); } static void del(tree ** ppr_r, int *pi_balance, tree ** ppr_q, void (*pfv_uar) ( /* ??? */ ), int *pi_uar_called) { ENTER("del"); if ((*ppr_r)->tree_r != NULL) { del(&(*ppr_r)->tree_r, 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)->tree_p); *pi_uar_called = TRUE; (*ppr_q)->tree_p = (*ppr_r)->tree_p; *ppr_q = *ppr_r; *ppr_r = (*ppr_r)->tree_l; *pi_balance = TRUE; } EXITV; } static void bal_L(tree ** ppr_p, int *pi_balance) { tree *p1, *p2; int b1, b2; ENTER("bal_L"); dprintk("left branch has shrunk"); switch ((*ppr_p)->tree_b) { case -1: dprintk("was imbalanced, fixed implicitly"); (*ppr_p)->tree_b = 0; break; case 0: dprintk("was okay, is now one off"); (*ppr_p)->tree_b = 1; *pi_balance = FALSE; break; case 1: dprintk("was already off, this is too much"); p1 = (*ppr_p)->tree_r; b1 = p1->tree_b; if (b1 >= 0) { dprintk("single RR"); (*ppr_p)->tree_r = p1->tree_l; p1->tree_l = *ppr_p; if (b1 == 0) { dprintk("b1 == 0"); (*ppr_p)->tree_b = 1; p1->tree_b = -1; *pi_balance = FALSE; } else { dprintk("b1 != 0"); (*ppr_p)->tree_b = 0; p1->tree_b = 0; } *ppr_p = p1; } else { dprintk("double RL"); p2 = p1->tree_l; b2 = p2->tree_b; p1->tree_l = p2->tree_r; p2->tree_r = p1; (*ppr_p)->tree_r = p2->tree_l; p2->tree_l = *ppr_p; if (b2 == 1) (*ppr_p)->tree_b = -1; else (*ppr_p)->tree_b = 0; if (b2 == -1) p1->tree_b = 1; else p1->tree_b = 0; *ppr_p = p2; p2->tree_b = 0; } } EXITV; } static void bal_R(tree ** ppr_p, int *pi_balance) { tree *p1, *p2; int b1, b2; ENTER("bal_R"); dprintk("right branch has shrunk"); switch ((*ppr_p)->tree_b) { case 1: dprintk("was imbalanced, fixed implicitly"); (*ppr_p)->tree_b = 0; break; case 0: dprintk("was okay, is now one off"); (*ppr_p)->tree_b = -1; *pi_balance = FALSE; break; case -1: dprintk("was already off, this is too much"); p1 = (*ppr_p)->tree_l; b1 = p1->tree_b; if (b1 <= 0) { dprintk("single LL"); (*ppr_p)->tree_l = p1->tree_r; p1->tree_r = *ppr_p; if (b1 == 0) { dprintk("b1 == 0"); (*ppr_p)->tree_b = -1; p1->tree_b = 1; *pi_balance = FALSE; } else { dprintk("b1 != 0"); (*ppr_p)->tree_b = 0; p1->tree_b = 0; } *ppr_p = p1; } else { dprintk("double LR"); p2 = p1->tree_r; b2 = p2->tree_b; p1->tree_r = p2->tree_l; p2->tree_l = p1; (*ppr_p)->tree_l = p2->tree_r; p2->tree_r = *ppr_p; if (b2 == -1) (*ppr_p)->tree_b = 1; else (*ppr_p)->tree_b = 0; if (b2 == 1) p1->tree_b = -1; else p1->tree_b = 0; *ppr_p = p2; p2->tree_b = 0; } } EXITV; }