radix.c

This is a source code of VxWorks

			break;
		}
	if (m == 0) {
#ifdef WV_INSTRUMENTATION
#ifdef INCLUDE_WVNET    /* WV_NET_ALERT event */
        WV_NET_MARKER_0 (NET_AUX_EVENT, WV_NET_ALERT, 5, 7,
                         WV_NETEVENT_RNDEL_SEARCHFAIL)
#endif  /* INCLUDE_WVNET */ 
#endif

		logMsg("rn_delete: couldn't find our annotation\n", 
		       0,0,0,0,0,0);
		if (tt->rn_flags & RNF_NORMAL)
			return (0); /* Dangling ref to us */
	}
on1:
	/*
	 * Eliminate us from tree
	 */
	if (tt->rn_flags & RNF_ROOT)
		return (0);
#ifdef RN_DEBUG
	/* Get us out of the creation list */
	for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {}
	if (t) t->rn_ybro = tt->rn_ybro;
#endif
	t = tt->rn_p;
	dupedkey = saved_tt->rn_dupedkey;
	if (dupedkey) {
		/*
		 * Here, tt is the deletion target, and
		 * saved_tt is the head of the dupedkey chain.
		 */
		if (tt == saved_tt) {
			x = dupedkey; x->rn_p = t;
			if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x;
		} else {
			/* find node in front of tt on the chain */
			for (x = p = saved_tt; p && p->rn_dupedkey != tt;)
				p = p->rn_dupedkey;
			if (p) {
				p->rn_dupedkey = tt->rn_dupedkey;
				if (tt->rn_dupedkey)
					tt->rn_dupedkey->rn_p = p;
			} else
                                { 
#ifdef WV_INSTRUMENTATION
#ifdef INCLUDE_WVNET    /* WV_NET_ALERT event */
                WV_NET_MARKER_0 (NET_AUX_EVENT, WV_NET_ALERT, 6, 8,
                                 WV_NETEVENT_RNDEL_KEYSEARCHFAIL)
#endif  /* INCLUDE_WVNET */
#endif

                                logMsg ("rn_delete: couldn't find us\n",
                                         0, 0, 0, 0, 0, 0);
                                }
		}
		t = tt + 1;
		if  (t->rn_flags & RNF_ACTIVE) {
#ifndef RN_DEBUG
			*++x = *t; p = t->rn_p;
#else
			b = t->rn_info; *++x = *t; t->rn_info = b; p = t->rn_p;
#endif
			if (p->rn_l == t) p->rn_l = x; else p->rn_r = x;
			x->rn_l->rn_p = x; x->rn_r->rn_p = x;
		}
		goto out;
	}
	if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l;
	p = t->rn_p;
	if (p->rn_r == t) p->rn_r = x; else p->rn_l = x;
	x->rn_p = p;
	/*
	 * Demote routes attached to us.
	 */
	if (t->rn_mklist) {
		if (x->rn_b >= 0) {
			for (mp = &x->rn_mklist; (m = *mp);)
				mp = &m->rm_mklist;
			*mp = t->rn_mklist;
		} else {
			/* If there are any key,mask pairs in a sibling
			   duped-key chain, some subset will appear sorted
			   in the same order attached to our mklist */
			for (m = t->rn_mklist; m && x; x = x->rn_dupedkey)
				if (m == x->rn_mklist) {
					struct radix_mask *mm = m->rm_mklist;
					x->rn_mklist = 0;
					if (--(m->rm_refs) < 0)
						MKFree(m);
					m = mm;
				}
			if (m)
                            {
#ifdef WV_INSTRUMENTATION
#ifdef INCLUDE_WVNET    /* WV_NET_ALERT event */
            WV_NET_MARKER_0 (NET_AUX_EVENT, WV_NET_ALERT, 7, 9,
                             WV_NETEVENT_RNDEL_EXTRAMASK)
#endif  /* INCLUDE_WVNET */
#endif

                            logMsg("%s %x at %x\n", 
                                   (int)"rn_delete: Orphaned Mask", (int)m, 
                                   (int)x, 0, 0, 0);
                            }
		}
	}
	/*
	 * We may be holding an active internal node in the tree.
	 */
	x = tt + 1;
	if (t != x) {
#ifndef RN_DEBUG
		*t = *x;
#else
		b = t->rn_info; *t = *x; t->rn_info = b;
#endif
		t->rn_l->rn_p = t; t->rn_r->rn_p = t;
		p = x->rn_p;
		if (p->rn_l == x) p->rn_l = t; else p->rn_r = t;
	}
out:
	tt->rn_flags &= ~RNF_ACTIVE;
	tt[1].rn_flags &= ~RNF_ACTIVE;
	return (tt);
}

/*
 * The rn_walksubtree routine is similar to rn_walktree() but only 
 * traverses a portion of the Patricia tree.
 */

int
rn_walksubtree(h, a, m, f, w)
        struct radix_node_head *h;
        void *a, *m;
	register int (*f)();
        void *w;
{
        int error;
        struct radix_node *base, *next;
        u_char *xa = (u_char *)a;
        u_char *xm = (u_char *)m;
        register struct radix_node *rn, *last = 0;
        int stopping = 0;
        int lastb;

    /*
     * Search for the root node of the subtree.
     */

        for (rn = h->rnh_treetop; rn->rn_b >= 0; ) {
                last = rn;

                /* Skip remaining (rightmost) bits if netmask doesn't apply. */

                if (!(rn->rn_bmask & xm[rn->rn_off])) {
                        break;
                }

                /*
                 * Descend tree like rn_search() routine for bits which are
                 * part of the network number.
                 */
 
                if (rn->rn_bmask & xa[rn->rn_off]) {
                        rn = rn->rn_r;
                } else {
                        rn = rn->rn_l;
                }
        }

    /*
     * Any (cloned) children of the target route reside in the subtree
     * starting at the "last" node. The remainder of this routine basically
     * mimics rn_walktree() except it uses an arbitrary node as the root.
     */

        rn = last;
        lastb = rn->rn_b;

        /*
         * This gets complicated because we may delete the node
         * while applying the function f to it, so we need to calculate
         * the successor node in advance.
         */
        while (rn->rn_b >= 0)
                rn = rn->rn_l;

        while (!stopping) {
                base = rn;
                /* If at right child go back up, otherwise, go right */
                while (rn->rn_p->rn_r == rn && !(rn->rn_flags & RNF_ROOT)) {
                        rn = rn->rn_p;

                        /* if went up beyond last, stop */
                        if (rn->rn_b < lastb) {
                                stopping = 1;
                        }
                }

                /* Find the next *leaf* since next node might vanish, too */

                for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;)
                        rn = rn->rn_l;
                next = rn;
                /* Process leaves */
                while ((rn = base) != 0) {
                        base = rn->rn_dupedkey;
                        if (!(rn->rn_flags & RNF_ROOT)
                            && (error = (*f)(rn, w)))
                                return (error);
                }
                rn = next;

                if (rn->rn_flags & RNF_ROOT) {
                        stopping = 1;
                }

        }
        return 0;
}

int
rn_walktree(h, f, w)
	struct radix_node_head *h;
	register int (*f)();
	void *w;
{
	int error;
	struct radix_node *base, *next;
	register struct radix_node *rn = h->rnh_treetop;
	/*
	 * This gets complicated because we may delete the node
	 * while applying the function f to it, so we need to calculate
	 * the successor node in advance.
	 */
	/* First time through node, go left */
	while (rn->rn_b >= 0)
		rn = rn->rn_l;
	for (;;) {
		base = rn;
		/* If at right child go back up, otherwise, go right */
		while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0)
			rn = rn->rn_p;
		/* Find the next *leaf* since next node might vanish, too */
		for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;)
			rn = rn->rn_l;
		next = rn;
		/* Process leaves */
		while ((rn = base)) {
			base = rn->rn_dupedkey;
			if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w)))
				return (error);
		}
		rn = next;
		if (rn->rn_flags & RNF_ROOT)
			return (0);
	}
	/* NOTREACHED */
}

int
rn_inithead(head, off)
        struct radix_node_head **head;
	int off;
{
	register struct radix_node_head *rnh;
	register struct radix_node *t, *tt, *ttt;
	if (*head)
		return (1);
	R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh));
	if (rnh == 0)
		return (0);
	Bzero(rnh, sizeof (*rnh));
	*head = rnh;
	t = rn_newpair(rn_zeros, off, rnh->rnh_nodes);
	ttt = rnh->rnh_nodes + 2;
	t->rn_r = ttt;
	t->rn_p = t;
	tt = t->rn_l;
	tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE;
	tt->rn_b = -1 - off;
	*ttt = *tt;
	ttt->rn_key = rn_ones;
	rnh->rnh_addaddr = rn_addroute;
	rnh->rnh_deladdr = rn_delete;
	rnh->rnh_matchaddr = rn_match;
	rnh->rnh_lookup = rn_lookup;
	rnh->rnh_walktree = rn_walktree;
	rnh->rnh_treetop = t;
	return (1);
}

int
rn_destroyhead(head)
        struct radix_node_head *head;
{
        if (head == 0)
                return (0);
        Free(head);
        return (1);
}


#ifdef VIRTUAL_STACK
/*
 * This routine mimics rn_init, but doesn't bother searching the domains list
 * since the only entry available involves AF_INET with a key length of 16.
 * The original version can be used if support for other domains is necessary.
 */

STATUS radixInit (void)
    {
    char *cp, *cplim;

    max_keylen = sizeof (struct sockaddr_in);

    R_Malloc(rn_zeros, char *, 3 * max_keylen);
    if (rn_zeros == NULL)
        {
        return (ERROR);
        }

    Bzero(rn_zeros, 3 * max_keylen);
    rn_ones = cp = rn_zeros + max_keylen;
    addmask_key = cplim = rn_ones + max_keylen;
    while (cp < cplim)
        *cp++ = -1;
    if (rn_inithead (&mask_rnhead, 0) == 0)
        {
        Free (rn_zeros);

        return (ERROR);
        }
    return (OK);
    }
#else
/*
 * The radixInit routine replaces this version with an implementation
 * to initialize radix trees for a virtual stack.
 */

void
rn_init()
{
	char *cp, *cplim;
	struct domain *dom;

	for (dom = domains; dom; dom = dom->dom_next)
		if (dom->dom_maxrtkey > max_keylen)
			max_keylen = dom->dom_maxrtkey;

	if (max_keylen == 0) {
		logMsg(
		"rn_init: radix functions require max_keylen be set\n",
		0,0,0,0,0,0);
		return;
	}
	R_Malloc(rn_zeros, char *, 3 * max_keylen);
	if (rn_zeros == NULL)
            {
#ifdef WV_INSTRUMENTATION
#ifdef INCLUDE_WVNET    /* WV_NET_EMERGENCY event */
            WV_NET_MARKER_0 (NET_AUX_EVENT, WV_NET_EMERGENCY, 18, 1,
                             WV_NETEVENT_RNINIT_PANIC)
#endif  /* INCLUDE_WVNET */
#endif

		panic("rn_init");
            }
	Bzero(rn_zeros, 3 * max_keylen);
	rn_ones = cp = rn_zeros + max_keylen;
	addmask_key = cplim = rn_ones + max_keylen;
	while (cp < cplim)
		*cp++ = -1;
	if (rn_inithead(&mask_rnhead, 0) == 0)
            {
#ifdef WV_INSTRUMENTATION
#ifdef INCLUDE_WVNET    /* WV_NET_EMERGENCY event */
            WV_NET_MARKER_0 (NET_AUX_EVENT, WV_NET_EMERGENCY, 18, 1,
                             WV_NETEVENT_RNINIT_PANIC)
#endif  /* INCLUDE_WVNET */
#endif

		panic("rn_init 2");
            }
}
#endif