diff options
Diffstat (limited to 'usr.sbin/named/tree.c')
| -rw-r--r-- | usr.sbin/named/tree.c | 570 |
1 files changed, 0 insertions, 570 deletions
diff --git a/usr.sbin/named/tree.c b/usr.sbin/named/tree.c deleted file mode 100644 index 58607ea0bd48..000000000000 --- a/usr.sbin/named/tree.c +++ /dev/null @@ -1,570 +0,0 @@ -/* 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. - * - * This code and associated documentation is hereby placed in the public - * domain, with the wish that my name and Prof. Wirth's not be removed - * from the source or documentation. - */ - - -#ifndef LINT -static char RCSid[] = "$Id:"; -#endif - - -/*#define DEBUG "tree"*/ - - -#include <stdio.h> -#ifndef _PATH_XFER -# include <stdlib.h> -#else -# include "../conf/portability.h" -#endif -#include "tree.h" - - -#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 __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 *) ); - - -void -tree_init(ppr_tree) - tree **ppr_tree; -{ - ENTER("tree_init") - *ppr_tree = NULL; - RETV -} - - -tree_t -tree_srch(ppr_tree, pfi_compare, p_user) - 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).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(ppr_tree, pfi_compare, p_user, pfv_uar) - tree **ppr_tree; - int (*pfi_compare)(); - 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(ppr_p, pfi_compare, p_user, pfv_uar) - tree **ppr_p; - int (*pfi_compare)(); - 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(ppr_tree, pfi_uar) - tree **ppr_tree; - int (*pfi_uar)(); -{ - 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(ppr_tree, pfv_uar) - tree **ppr_tree; - void (*pfv_uar)(); -{ - 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); - free(*ppr_tree); - *ppr_tree = NULL; - } - RETV -} - - -static tree * -sprout(ppr, p_data, pi_balance, pfi_compare, pfv_delete) - tree **ppr; - tree_t p_data; - int *pi_balance; - int (*pfi_compare)(); - void (*pfv_delete)(); -{ - 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 *) malloc(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(ppr_p, pfi_compare, p_user, pfv_uar, pi_balance, pi_uar_called) - 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) { - 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); - free(pr_q); /* thanks to wuth@castrov.cuc.ab.ca */ - i_ret = TRUE; - } - RET(i_ret) -} - - -static void -del(ppr_r, pi_balance, ppr_q, pfv_uar, pi_uar_called) - tree **ppr_r; - int *pi_balance; - tree **ppr_q; - void (*pfv_uar)(); - 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(ppr_p, pi_balance) - 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(ppr_p, pi_balance) - 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 -} |