tree/tree.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include "vixie.h"
#include "tree.h"
#include "debug.h"

Include dependency graph for tree.c:

Go to the source code of this file.

Defines
#define	__P(x)   ()
Functions
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 *))
void	tree_init (tree **ppr_tree)
tree_t	tree_srch (tree **ppr_tree, int(*pfi_compare)(), tree_t p_user)
void	tree_add (tree **ppr_tree, int(*pfi_compare)(), tree_t p_user, void(*pfv_uar)())
int	tree_delete (tree **ppr_p, int(*pfi_compare)(), tree_t p_user, void(*pfv_uar)())
int	tree_trav (tree **ppr_tree, int(*pfi_uar)())
void	tree_mung (tree **ppr_tree, void(*pfv_uar)())
static void	sprout (tree **ppr, tree_t p_data, int *pi_balance, int(*pfi_compare)(), void(*pfv_delete)())
static int	delete (tree **ppr_p, int(*pfi_compare)(), tree_t p_user, void(*pfv_uar)(), int *pi_balance, int *pi_uar_called)
static void	del (tree **ppr_r, int *pi_balance, tree **ppr_q, void(*pfv_uar)(), int *pi_uar_called)
static void	bal_L (tree **ppr_p, int *pi_balance)
static void	bal_R (tree **ppr_p, int *pi_balance)

---

Define Documentation

#define __P

(

x

)

()

Definition at line 33 of file tree.c.

---

Function Documentation

static void bal_R __P

(

(tree **, int *)

)

[static]

static void del __P

(

(tree **, int *, tree **, void(*)(), int *)

)

[static]

static int delete __P

(

(tree **, int(*)(), tree_t, void(*)(), int *, int *)

)

[static]

static void sprout __P

(

(tree **, tree_t, int *, int(*)(), void(*)())

)

[static]

static void bal_L	(	tree **	ppr_p,
		int *	pi_balance
	)			[static]

Definition at line 360 of file tree.c.

References dprintk, ENTER, EXITV, FALSE, tree_s::tree_b, tree_s::tree_l, and tree_s::tree_r.

Referenced by delete().

{
    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
	)			[static]

Definition at line 421 of file tree.c.

References dprintk, ENTER, EXITV, FALSE, tree_s::tree_b, tree_s::tree_l, and tree_s::tree_r.

Referenced by del(), and delete().

{
    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;
}

static void del	(	tree **	ppr_r,
		int *	pi_balance,
		tree **	ppr_q,
		void(*)()	pfv_uar,
		int *	pi_uar_called
	)			[static]

Definition at line 337 of file tree.c.

References bal_R(), ENTER, EXITV, tree_s::tree_l, and TRUE.

Referenced by delete().

{
    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 int delete	(	tree **	ppr_p,
		int(*)()	pfi_compare,
		tree_t	p_user,
		void(*)()	pfv_uar,
		int *	pi_balance,
		int *	pi_uar_called
	)			[static]

Definition at line 281 of file tree.c.

References bal_L(), bal_R(), del(), dprintk, ENTER, EXIT, FALSE, i_comp(), tree_s::tree_l, tree_s::tree_p, tree_s::tree_r, and TRUE.

{
    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 sprout	(	tree **	ppr,
		tree_t	p_data,
		int *	pi_balance,
		int(*)()	pfi_compare,
		void(*)()	pfv_delete
	)			[static]

Definition at line 129 of file tree.c.

References dprintk, ENTER, EXITV, FALSE, tree_s::tree_b, tree_s::tree_l, tree_s::tree_r, and TRUE.

Referenced by tree_add().

{
    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;
}

void tree_add	(	tree **	ppr_tree,
		int(*)()	pfi_compare,
		tree_t	p_user,
		void(*)()	pfv_uar
	)

Definition at line 80 of file tree.c.

References ENTER, EXITV, FALSE, and sprout().

{
    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
	)

Definition at line 91 of file tree.c.

References ENTER, EXIT, and FALSE.

{
    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) ( /* ??? */ ))

void tree_init

(

tree **

ppr_tree

)

Definition at line 47 of file tree.c.

References ENTER, and EXITV.

{
    ENTER("tree_init");
    *ppr_tree = NULL;
    EXITV;
}

void tree_mung	(	tree **	ppr_tree,
		void(*)()	pfv_uar
	)

Definition at line 114 of file tree.c.

References ENTER, EXITV, and tree_mung().

{
    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;
}

tree_t tree_srch	(	tree **	ppr_tree,
		int(*)()	pfi_compare,
		tree_t	p_user
	)

Definition at line 55 of file tree.c.

References ENTER, EXIT, i_comp(), and tree_srch().

{
    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);
}

int tree_trav	(	tree **	ppr_tree,
		int(*)()	pfi_uar
	)

Definition at line 99 of file tree.c.

{
    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);
}

---