tree/tree.c

Go to the documentation of this file.

/* 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;
}

---