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