rrbtree.c

用于嵌入式系统的TCP/IP协议栈及若干服务

/*
*            Copyright (c) 1998-2001 by NETsilicon Inc.
*
*  This software is copyrighted by and is the sole property of
*  NETsilicon.  All rights, title, ownership, or other interests
*  in the software remain the property of NETsilicon.  This
*  software may only be used in accordance with the corresponding
*  license agreement.  Any unauthorized use, duplication, transmission,
*  distribution, or disclosure of this software is expressly forbidden.
*
*  This Copyright notice may not be removed or modified without prior
*  written consent of NETsilicon.
*
*  NETsilicon, reserves the right to modify this software
*  without notice.
*
*  NETsilicon
*  411 Waverley Oaks Road                  USA 781.647.1234
*  Suite 227                               http://www.netsilicon.com
*  Waltham, MA 02452                       [e-mail]
*
*************************************************************************
*  $Name: Fusion 6.52 Fusion 6.51 $
*  $Date: 2002/01/15 11:50:39 $
*  $Source: M:/psisrc/routing/rrfdb/rcs/rrbtree.c $
*  $Revision: 1.6 $
*************************************************************************
*  File Description: IP forwarding database. 

Overall architecture used:

1 hash table for all routing tables of a given metric.
The contents of hash table are pointers to a routing
entry (iproute_entry). 
***************************************************************************
*  File Description: binary tree functions shared across protocols 
**************************************************************************/
#include <riproute.h>

#include "rrport.h"
#include "rrbtree.h"

/* look at the back link from XN1 and set its left or
   right fwd link to XN2
*/
#define ADJ_BLINK(XN1,XN2) {\
if(XN1->b_bwd->b_left == XN1)            \
        XN1->b_bwd->b_left = XN2;           \
else                                           \
        XN1->b_bwd->b_right = XN2;          \
}

fnc_prot(static rrbtree *, findNode,(rrbtree *,rrbtree *,rrbtcmp))

static rrbtree *findNode(rrbtree * newt, rrbtree * head,rrbtcmp fcmp)
{
    rrbtree *nd = head;
    int     rc;

    while (nd) {
	rc = fcmp(newt, nd);
	if (!rc)
	    return (nd);
	else if (rc > 0)
	    nd = nd->b_right;
	else
	    nd = nd->b_left;
    }
    return ((rrbtree *) 0);
}

static int getTreeHeight(rrbtree * nd)
{
    int     cnt = 0;
    while (nd) {
	cnt++;
	if (nd->b_bal < 0)
	    nd = nd->b_left;
	else
	    nd = nd->b_right;
    }
    return (cnt);
}

int     rrBtreeInsert(rrbtree * node, rrbtree ** headp, rrbtcmp fcmp)
{
    rrbtree *tmp, *adjnd, *r, *head;
    int     a, rc;

    head = *headp;
    /* verify does not exist */
    if (findNode(node, head, fcmp))
	return (-1);

    node->b_left = 0;
    node->b_right = 0;
    node->b_bwd = 0;
    node->b_bal = 0;

    if (!head) {
	*headp = node;
	return (0);
    }

    /* find a home, will add at end of a chain */
    tmp = head;
    adjnd = head;
    while (tmp) {

	/* potential starting point for adjustment */
	if (tmp->b_bal)
	    adjnd = tmp;

	rc = fcmp(node, tmp);
	if (rc > 0) {
	    if (!tmp->b_right) {
		tmp->b_right = node;
		node->b_bwd = tmp;
		break;
	    }
	    tmp = tmp->b_right;
	}
	else if (rc < 0) {
	    if (!tmp->b_left) {
		tmp->b_left = node;
		node->b_bwd = tmp;
		break;
	    }
	    tmp = tmp->b_left;
	}
	else
	    return (0);
    }

    /* adjust balance factors, starting from next after adjnd. (adjnd
       adjusted later) */
    rc = fcmp(node, adjnd);
    if (rc < 0) {
	tmp = adjnd->b_left;
	a = -1;
    }
    else {
	tmp = adjnd->b_right;
	a = 1;
    }
    r = tmp;
    while (tmp != node) {
	rc = fcmp(node, tmp);
	if (rc < 0) {
	    tmp->b_bal = -1;
	    tmp = tmp->b_left;
	}
	else {
	    tmp->b_bal = 1;
	    tmp = tmp->b_right;
	}
    }
    /* do we need to rebalance? */
    if (!adjnd->b_bal) {
	/* tree 1 deeper, still balanced. only happens when adjnd is head */
	adjnd->b_bal = a;
    }
    else if (adjnd->b_bal != a) {
	/* tree is more balanced */
	adjnd->b_bal = 0;
    }
    else {
	/* whoops, out of balance, rebalance */
	if (r->b_bal == a) {
	    /* right single rotate */
	    if (a == 1) {
		/* fwd ptrs */
		adjnd->b_right = r->b_left;
		r->b_left = adjnd;
		adjnd->b_bal = r->b_bal = 0;
		if (adjnd != head) {
		    ADJ_BLINK(adjnd, r);
		}
		else {
		    /* tree head has changed, must adjust head ptr */
		    *headp = r;
		}
		/* b_bwd ptrs */
		r->b_bwd = adjnd->b_bwd;
		adjnd->b_bwd = r;
		if (adjnd->b_right)
		    adjnd->b_right->b_bwd = adjnd;
	    }
	    /* left single rotate */
	    else {
		/* fwd ptrs */
		adjnd->b_left = r->b_right;
		r->b_right = adjnd;
		adjnd->b_bal = r->b_bal = 0;
		if (adjnd != head) {
		    ADJ_BLINK(adjnd, r);
		}
		else {
		    /* tree head has changed, must adjust head ptr */
		    *headp = r;
		}
		/* back ptrs */
		r->b_bwd = adjnd->b_bwd;
		adjnd->b_bwd = r;
		if (adjnd->b_left)
		    adjnd->b_left->b_bwd = adjnd;
	    }
	}
	else {
	    /* right double rotate */
	    if (a == 1) {
		/* fwd links */
		tmp = r->b_left;
		r->b_left = tmp->b_right;
		tmp->b_right = r;
		adjnd->b_right = tmp->b_left;
		tmp->b_left = adjnd;
		if (tmp->b_bal == a) {
		    adjnd->b_bal = -a;
		    r->b_bal = 0;
		}
		else if (!tmp->b_bal) {
		    adjnd->b_bal = 0;
		    r->b_bal = 0;
		}
		else {
		    adjnd->b_bal = 0;
		    r->b_bal = a;
		}
		tmp->b_bal = 0;
		if (adjnd != head) {
		    ADJ_BLINK(adjnd, tmp);
		}
		else {
		    /* tree head has changed, must adjust head ptr */
		    *headp = tmp;

		}
		/* back links */
		tmp->b_bwd = adjnd->b_bwd;
		r->b_bwd = tmp;
		adjnd->b_bwd = tmp;
		if (adjnd->b_right)
		    adjnd->b_right->b_bwd = adjnd;
		if (r->b_left)
		    r->b_left->b_bwd = r;
	    }
	    else {
		/* fwd links */
		tmp = r->b_right;
		r->b_right = tmp->b_left;
		tmp->b_left = r;
		adjnd->b_left = tmp->b_right;
		tmp->b_right = adjnd;
		if (tmp->b_bal == a) {
		    adjnd->b_bal = -a;
		    r->b_bal = 0;
		}
		else if (!tmp->b_bal) {
		    adjnd->b_bal = 0;
		    r->b_bal = 0;
		}
		else {
		    adjnd->b_bal = 0;
		    r->b_bal = a;
		}
		tmp->b_bal = 0;
		if (adjnd != head) {
		    ADJ_BLINK(adjnd, tmp);
		}
		else {
		    /* tree head has changed, must adjust head ptr */
		    *headp = tmp;
		}
		/* back links */
		tmp->b_bwd = adjnd->b_bwd;
		r->b_bwd = tmp;
		adjnd->b_bwd = tmp;
		if (adjnd->b_left)
		    adjnd->b_left->b_bwd = adjnd;
		if (r->b_right)
		    r->b_right->b_bwd = r;
	    }
	}
    }
    return (0);
}
void    rrBtreeDelete(rrbtree * nd, rrbtree ** headp)
{
    rrbtree *tmp, *fwd, *x;
    rrbtree troute;
    int     lr, arht, alht, blht, brht;
    rrbtree *head = *headp;

    if (!head)
	return;

    /* we can only remove from end of tree, so.. */
    /* if have both left and right link, shuffle by finding the leftmost
       entry in the right path and exchanging. the resulting tree is out of
       order, but we dont care since the offending member (nd), which is now
       at the end, will be deleted. */
    if (nd->b_left && nd->b_right) {
	tmp = nd->b_right;
	while (tmp->b_left) {
	    tmp = tmp->b_left;
	}
	/* do swap places */
	troute.b_right = tmp->b_right;
	troute.b_bwd = tmp->b_bwd;
	troute.b_bal = tmp->b_bal;
	tmp->b_bwd = nd->b_bwd;
	if (nd->b_right == tmp) {
	    tmp->b_right = nd;
	    nd->b_bwd = tmp;
	}
	else {
	    tmp->b_right = nd->b_right;
	    nd->b_bwd = troute.b_bwd;
	}
	tmp->b_left = nd->b_left;
	tmp->b_bal = nd->b_bal;
	nd->b_left = 0;
	nd->b_right = troute.b_right;
	nd->b_bal = troute.b_bal;

	/* now adjust all links pointing to these nodes. */
	if (head == nd) {
	    head = tmp;
	    *headp = head;
	    head->b_bwd = 0;
	}
	else {
	    if (tmp->b_bwd->b_left == nd)
		tmp->b_bwd->b_left = tmp;
	    else
		tmp->b_bwd->b_right = tmp;
	}
	tmp->b_left->b_bwd = tmp;
	tmp->b_right->b_bwd = tmp;
	if (nd->b_right)
	    nd->b_right->b_bwd = nd;
	/* if nodes were not adjacent */
	if (tmp->b_right != nd) {
	    nd->b_bwd->b_left = nd;
	}
    }

    /* now delete a node which has at least one null link */
    if (!nd->b_left) {
	/* previous will now point to our right */
	if (nd != head) {
	    tmp = nd->b_bwd;
	    if (nd->b_bwd->b_left == nd) {
		nd->b_bwd->b_left = nd->b_right;
		lr = 1;
	    }
	    else {
		nd->b_bwd->b_right = nd->b_right;
		lr = -1;
	    }
	    if (nd->b_right)
		nd->b_right->b_bwd = nd->b_bwd;
	}
	else {
	    /* is head may have right link */
	    head = nd->b_right;
	    *headp = head;
	    if (head)
		head->b_bwd = 0;
	    return;
	}
    }
    else {
	/* does have left link, doesnt have right */
	/* previous will now point to our b_left */
	if (nd != head) {
	    tmp = nd->b_bwd;
	    if (nd->b_bwd->b_right == nd) {
		nd->b_bwd->b_right = nd->b_left;
		lr = -1;
	    }
	    else {
		nd->b_bwd->b_left = nd->b_left;
		lr = 1;
	    }
	    if (nd->b_left)
		nd->b_left->b_bwd = nd->b_bwd;
	}
	else {
	    /* is head does have left link */
	    head = nd->b_left;
	    *headp = head;
	    if (head)
		head->b_bwd = 0;
	    return;
	}
    }
    /* work our way back up the tree, rebalancing as we go. start with the
       parent of the node we just deleted. here is the pertinent info we
       need: - we know that parent's tree has shrunk by one on the side nd
       was on, whether or not nd had a child. - we know nd's child tree, if
       it had one consisted of only a single child on one side, otherwise the
       tree was out of balance to begin with. */
    while (tmp) {
	tmp->b_bal += lr;
	if (tmp->b_bal > 1) {
	    /* need to rebalance, 3 cases (and their mirror. all delete from
	       a left. (see knuth pg 454) 1: a->right = b, alht = h, blht =
	       h, brht = h+1 2: a->right = b, alht = h, blht = h+1, brht = h
	       3: a->right = b, alht = h, blht = h+1, brht = h+1 dgenerates
	       to case 1, except new bal */
	    alht = getTreeHeight(tmp->b_left);
	    blht = getTreeHeight(tmp->b_right->b_left);
	    brht = getTreeHeight(tmp->b_right->b_right);
	    if (alht != brht) {
		/* case 1/3 single rotate */
		/* fwd ptrs */
		fwd = tmp->b_right;
		tmp->b_right = fwd->b_left;
		fwd->b_left = tmp;
		if (tmp != head) {
		    ADJ_BLINK(tmp, fwd);
		}
		else {
		    head = fwd;
		    *headp = head;
		}
		/* back ptrs */
		fwd->b_bwd = tmp->b_bwd;
		tmp->b_bwd = fwd;
		if (tmp->b_right)
		    tmp->b_right->b_bwd = tmp;
		/* adjust balance */
		if (blht != brht)
		    fwd->b_bal = tmp->b_bal = 0;
		else {
		    tmp->b_bal = 1;
		    fwd->b_bal = -1;
		}
		tmp = fwd;
	    }
	    else {
		/* case 2 double rotate */
		/* fwd links */
		fwd = tmp->b_right;
		x = fwd->b_left;
		fwd->b_left = x->b_right;
		x->b_right = fwd;
		tmp->b_right = x->b_left;
		x->b_left = tmp;
		if (tmp != head) {
		    ADJ_BLINK(tmp, x);
		}
		else {
		    head = x;
		    *headp = head;
		}
		/* back links */
		x->b_bwd = tmp->b_bwd;
		fwd->b_bwd = x;
		tmp->b_bwd = x;
		if (tmp->b_right)
		    tmp->b_right->b_bwd = tmp;
		if (fwd->b_left)
		    fwd->b_left->b_bwd = fwd;

		/* adjust balance count */
		if (x->b_bal == 1) {
		    tmp->b_bal = -1;
		    fwd->b_bal = 0;
		}
		else if (!x->b_bal) {
		    tmp->b_bal = 0;
		    fwd->b_bal = 0;
		}
		else {
		    tmp->b_bal = 0;
		    fwd->b_bal = 1;
		}
		x->b_bal = 0;
		tmp = x;
	    }
	}
	else if (tmp->b_bal < -1) {
	    /* mirror above */
	    arht = getTreeHeight(tmp->b_right);
	    blht = getTreeHeight(tmp->b_left->b_left);
	    brht = getTreeHeight(tmp->b_left->b_right);
	    if (arht != blht) {
		/* case 1/3 single rotate */
		/* fwd ptrs */
		fwd = tmp->b_left;
		tmp->b_left = fwd->b_right;
		fwd->b_right = tmp;
		if (tmp != head) {
		    ADJ_BLINK(tmp, fwd);
		}
		else {
		    head = fwd;
		    *headp = head;
		}
		/* back ptrs */
		fwd->b_bwd = tmp->b_bwd;
		tmp->b_bwd = fwd;
		if (tmp->b_left)
		    tmp->b_left->b_bwd = tmp;
		/* adjust balance */
		if (blht != brht)
		    fwd->b_bal = tmp->b_bal = 0;
		else {
		    tmp->b_bal = -1;
		    fwd->b_bal = 1;
		}
		tmp = fwd;
	    }
	    else {
		/* case 2 double rotate */
		/* fwd links */
		fwd = tmp->b_left;
		x = fwd->b_right;
		fwd->b_right = x->b_left;
		x->b_left = fwd;
		tmp->b_left = x->b_right;
		x->b_right = tmp;
		if (tmp != head) {
		    ADJ_BLINK(tmp, x);
		}
		else {
		    head = x;
		    *headp = head;
		}
		/* back links */
		x->b_bwd = tmp->b_bwd;
		fwd->b_bwd = x;
		tmp->b_bwd = x;
		if (tmp->b_left)
		    tmp->b_left->b_bwd = tmp;
		if (fwd->b_right)
		    fwd->b_right->b_bwd = fwd;

		/* adjust balance count */
		if (x->b_bal == -1) {
		    tmp->b_bal = 1;
		    fwd->b_bal = 0;
		}
		else if (!x->b_bal) {
		    tmp->b_bal = 0;
		    fwd->b_bal = 0;
		}
		else {
		    tmp->b_bal = 0;
		    fwd->b_bal = -1;
		}
		x->b_bal = 0;
		tmp = x;
	    }
	}
	else {
	    /* balanced at this level */
	}
	/* if bal != 0, nothing above here has changed */
	if (tmp->b_bal)
	    break;

	/* go up one node, try again */
	if (tmp == head)
	    break;

	if (tmp->b_bwd->b_left == tmp)
	    lr = 1;
	else
	    lr = -1;
	tmp = tmp->b_bwd;
    }
}
/******************************************
tree traversal functions
********************************************/
rrbtree *rrBtreeNext(rrbtree * nd)
{

    /* if there is right link, follow it then all left links. */
    if (nd->b_right) {
	nd = nd->b_right;
	for (; nd; nd = nd->b_left) {
	    if (!nd->b_left)
		return (nd);
	}
    }
    /* go up tree till we find a link that is left (ie. up is greater) */
    while (1) {
	    if (nd->b_bwd == 0)
	        return (0);
	    if (nd->b_bwd->b_left == nd)
	        return (nd->b_bwd);
	    nd = nd->b_bwd;
    }

}
/******************************************
find route with next lowest val, given
head and current route
********************************************/
rrbtree *rrBtreeFirst(rrbtree ** head)
{
    rrbtree *nd = *head;

    if (!nd)
	return (0);

    /* find first */
    /* follow left links */
    for (;; nd = nd->b_left) {
	if (!nd->b_left)
	    break;
    }
    return (nd);
}

/******************************************
tree traversal functions
********************************************/
rrbtree *rrBtreePrev(rrbtree * nd)
{

    /* if there is left link, follow it then all right links. */
    if (nd->b_left) {
	nd = nd->b_left;
	for (; nd; nd = nd->b_right) {
	    if (!nd->b_right)
		return (nd);
	}
    }
    /* go up tree till we find a link that is right (ie. up is less) */
    while (1) {
	    if (nd->b_bwd == 0)
	        return (0);
	    if (nd->b_bwd->b_right == nd)
	        return (nd->b_bwd);
	    nd = nd->b_bwd;
    }

}
/******************************************
find route with next highest val, given
head and current route
********************************************/
rrbtree *rrBtreeLast(rrbtree ** head)
{
    rrbtree *nd = *head;

    if (!nd)
	return (0);

    /* follow rightlinks */
    for (;; nd = nd->b_right) {
	if (!nd->b_right)
	    break;
    }
    return (nd);
}