118316Swollman/*
218316Swollman * Copyright (c) 1988, 1989, 1993
318316Swollman *	The Regents of the University of California.  All rights reserved.
418316Swollman *
518316Swollman * Redistribution and use in source and binary forms, with or without
618316Swollman * modification, are permitted provided that the following conditions
718316Swollman * are met:
818316Swollman * 1. Redistributions of source code must retain the above copyright
918316Swollman *    notice, this list of conditions and the following disclaimer.
1018316Swollman * 2. Redistributions in binary form must reproduce the above copyright
1118316Swollman *    notice, this list of conditions and the following disclaimer in the
1218316Swollman *    documentation and/or other materials provided with the distribution.
1318316Swollman * 4. Neither the name of the University nor the names of its contributors
1418316Swollman *    may be used to endorse or promote products derived from this software
1518316Swollman *    without specific prior written permission.
1618316Swollman *
1718316Swollman * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
1818316Swollman * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
1918316Swollman * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
2018316Swollman * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
2118316Swollman * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
2218316Swollman * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
2318316Swollman * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
2418316Swollman * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
2518316Swollman * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
2618316Swollman * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
2718316Swollman * SUCH DAMAGE.
2818316Swollman *
2946303Smarkm *	@(#)radix.c	8.4 (Berkeley) 11/2/94
3046303Smarkm *
3150476Speter * $FreeBSD$
3218316Swollman */
3318316Swollman
3418316Swollman/*
3518316Swollman * Routines to build and maintain radix trees for routing lookups.
3618316Swollman */
3718316Swollman
3818316Swollman#include "defs.h"
3918316Swollman
40126250Sbms#ifdef __NetBSD__
4146303Smarkm__RCSID("$NetBSD$");
42126250Sbms#elif defined(__FreeBSD__)
43126250Sbms__RCSID("$FreeBSD$");
44126250Sbms#else
45126250Sbms__RCSID("$Revision: 2.23 $");
46126250Sbms#ident "$Revision: 2.23 $"
4746303Smarkm#endif
4846303Smarkm
4918316Swollman#define log(x, msg) syslog(x, msg)
5018316Swollman#define panic(s) {log(LOG_ERR,s); exit(1);}
5118316Swollman#define min(a,b) (((a)<(b))?(a):(b))
5218316Swollman
5318316Swollmanint	max_keylen;
54190715Sphkstatic struct radix_mask *rn_mkfreelist;
55190715Sphkstatic struct radix_node_head *mask_rnhead;
5618316Swollmanstatic char *addmask_key;
57190718Sphkstatic const uint8_t normal_chars[] =
58190715Sphk    { 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff};
5918316Swollmanstatic char *rn_zeros, *rn_ones;
6018316Swollman
6118316Swollman#define rn_masktop (mask_rnhead->rnh_treetop)
6246303Smarkm#define Bcmp(a, b, l) (l == 0 ? 0 \
6346303Smarkm		       : memcmp((caddr_t)(a), (caddr_t)(b), (size_t)l))
6418316Swollman
6546303Smarkmstatic int rn_satisfies_leaf(char *, struct radix_node *, int);
66190715Sphkstatic struct radix_node *rn_addmask(void *n_arg, int search, int skip);
67190715Sphkstatic struct radix_node *rn_addroute(void *v_arg, void *n_arg,
68190715Sphk	    struct radix_node_head *head, struct radix_node treenodes[2]);
69190715Sphkstatic struct radix_node *rn_match(void *v_arg, struct radix_node_head *head);
7018316Swollman
7118316Swollman/*
7218316Swollman * The data structure for the keys is a radix tree with one way
7318316Swollman * branching removed.  The index rn_b at an internal node n represents a bit
7418316Swollman * position to be tested.  The tree is arranged so that all descendants
7518316Swollman * of a node n have keys whose bits all agree up to position rn_b - 1.
7618316Swollman * (We say the index of n is rn_b.)
7718316Swollman *
7818316Swollman * There is at least one descendant which has a one bit at position rn_b,
7918316Swollman * and at least one with a zero there.
8018316Swollman *
8118316Swollman * A route is determined by a pair of key and mask.  We require that the
8218316Swollman * bit-wise logical and of the key and mask to be the key.
8318316Swollman * We define the index of a route to associated with the mask to be
8418316Swollman * the first bit number in the mask where 0 occurs (with bit number 0
8518316Swollman * representing the highest order bit).
8618316Swollman *
8718316Swollman * We say a mask is normal if every bit is 0, past the index of the mask.
8818316Swollman * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b,
8918316Swollman * and m is a normal mask, then the route applies to every descendant of n.
9018316Swollman * If the index(m) < rn_b, this implies the trailing last few bits of k
9118316Swollman * before bit b are all 0, (and hence consequently true of every descendant
9218316Swollman * of n), so the route applies to all descendants of the node as well.
9318316Swollman *
9418316Swollman * Similar logic shows that a non-normal mask m such that
9518316Swollman * index(m) <= index(n) could potentially apply to many children of n.
9618316Swollman * Thus, for each non-host route, we attach its mask to a list at an internal
9718316Swollman * node as high in the tree as we can go.
9818316Swollman *
9918316Swollman * The present version of the code makes use of normal routes in short-
100229778Suqs * circuiting an explicit mask and compare operation when testing whether
10118316Swollman * a key satisfies a normal route, and also in remembering the unique leaf
10218316Swollman * that governs a subtree.
10318316Swollman */
10418316Swollman
105190715Sphkstatic struct radix_node *
10618316Swollmanrn_search(void *v_arg,
10718316Swollman	  struct radix_node *head)
10818316Swollman{
10946303Smarkm	struct radix_node *x;
11046303Smarkm	caddr_t v;
11118316Swollman
11218316Swollman	for (x = head, v = v_arg; x->rn_b >= 0;) {
11318316Swollman		if (x->rn_bmask & v[x->rn_off])
11418316Swollman			x = x->rn_r;
11518316Swollman		else
11618316Swollman			x = x->rn_l;
11718316Swollman	}
11818316Swollman	return (x);
11918316Swollman}
12018316Swollman
121190715Sphkstatic struct radix_node *
12218316Swollmanrn_search_m(void *v_arg,
12318316Swollman	    struct radix_node *head,
12418316Swollman	    void *m_arg)
12518316Swollman{
12646303Smarkm	struct radix_node *x;
12746303Smarkm	caddr_t v = v_arg, m = m_arg;
12818316Swollman
12918316Swollman	for (x = head; x->rn_b >= 0;) {
13018316Swollman		if ((x->rn_bmask & m[x->rn_off]) &&
13118316Swollman		    (x->rn_bmask & v[x->rn_off]))
13218316Swollman			x = x->rn_r;
13318316Swollman		else
13418316Swollman			x = x->rn_l;
13518316Swollman	}
13618316Swollman	return x;
13718316Swollman}
13818316Swollman
139190715Sphkstatic int
14018316Swollmanrn_refines(void* m_arg, void *n_arg)
14118316Swollman{
14246303Smarkm	caddr_t m = m_arg, n = n_arg;
14346303Smarkm	caddr_t lim, lim2 = lim = n + *(u_char *)n;
14418316Swollman	int longer = (*(u_char *)n++) - (int)(*(u_char *)m++);
14518316Swollman	int masks_are_equal = 1;
14618316Swollman
14718316Swollman	if (longer > 0)
14818316Swollman		lim -= longer;
14918316Swollman	while (n < lim) {
15018316Swollman		if (*n & ~(*m))
15118316Swollman			return 0;
15218316Swollman		if (*n++ != *m++)
15318316Swollman			masks_are_equal = 0;
15418316Swollman	}
15518316Swollman	while (n < lim2)
15618316Swollman		if (*n++)
15718316Swollman			return 0;
15818316Swollman	if (masks_are_equal && (longer < 0))
15918316Swollman		for (lim2 = m - longer; m < lim2; )
16018316Swollman			if (*m++)
16118316Swollman				return 1;
16218316Swollman	return (!masks_are_equal);
16318316Swollman}
16418316Swollman
165190715Sphkstatic struct radix_node *
16646303Smarkmrn_lookup(void *v_arg, void *m_arg, struct radix_node_head *head)
16718316Swollman{
16846303Smarkm	struct radix_node *x;
16918316Swollman	caddr_t netmask = 0;
17018316Swollman
17118316Swollman	if (m_arg) {
17218316Swollman		if ((x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 0)
17318316Swollman			return (0);
17418316Swollman		netmask = x->rn_key;
17518316Swollman	}
17618316Swollman	x = rn_match(v_arg, head);
17718316Swollman	if (x && netmask) {
17818316Swollman		while (x && x->rn_mask != netmask)
17918316Swollman			x = x->rn_dupedkey;
18018316Swollman	}
18118316Swollman	return x;
18218316Swollman}
18318316Swollman
18418316Swollmanstatic int
18546303Smarkmrn_satisfies_leaf(char *trial,
18646303Smarkm		  struct radix_node *leaf,
18718316Swollman		  int skip)
18818316Swollman{
18946303Smarkm	char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask;
19018316Swollman	char *cplim;
19118316Swollman	int length = min(*(u_char *)cp, *(u_char *)cp2);
19218316Swollman
19318316Swollman	if (cp3 == 0)
19418316Swollman		cp3 = rn_ones;
19518316Swollman	else
19618316Swollman		length = min(length, *(u_char *)cp3);
19718316Swollman	cplim = cp + length; cp3 += skip; cp2 += skip;
19818316Swollman	for (cp += skip; cp < cplim; cp++, cp2++, cp3++)
19918316Swollman		if ((*cp ^ *cp2) & *cp3)
20018316Swollman			return 0;
20118316Swollman	return 1;
20218316Swollman}
20318316Swollman
204190715Sphkstatic struct radix_node *
20518316Swollmanrn_match(void *v_arg,
20618316Swollman	 struct radix_node_head *head)
20718316Swollman{
20818316Swollman	caddr_t v = v_arg;
20946303Smarkm	struct radix_node *t = head->rnh_treetop, *x;
21046303Smarkm	caddr_t cp = v, cp2;
21118316Swollman	caddr_t cplim;
21218316Swollman	struct radix_node *saved_t, *top = t;
21318316Swollman	int off = t->rn_off, vlen = *(u_char *)cp, matched_off;
21446303Smarkm	int test, b, rn_b;
21518316Swollman
21618316Swollman	/*
21718316Swollman	 * Open code rn_search(v, top) to avoid overhead of extra
21818316Swollman	 * subroutine call.
21918316Swollman	 */
22018316Swollman	for (; t->rn_b >= 0; ) {
22118316Swollman		if (t->rn_bmask & cp[t->rn_off])
22218316Swollman			t = t->rn_r;
22318316Swollman		else
22418316Swollman			t = t->rn_l;
22518316Swollman	}
22618316Swollman	/*
22718316Swollman	 * See if we match exactly as a host destination
22818316Swollman	 * or at least learn how many bits match, for normal mask finesse.
22918316Swollman	 *
23018316Swollman	 * It doesn't hurt us to limit how many bytes to check
23118316Swollman	 * to the length of the mask, since if it matches we had a genuine
23218316Swollman	 * match and the leaf we have is the most specific one anyway;
23318316Swollman	 * if it didn't match with a shorter length it would fail
23418316Swollman	 * with a long one.  This wins big for class B&C netmasks which
23518316Swollman	 * are probably the most common case...
23618316Swollman	 */
23718316Swollman	if (t->rn_mask)
23818316Swollman		vlen = *(u_char *)t->rn_mask;
23918316Swollman	cp += off; cp2 = t->rn_key + off; cplim = v + vlen;
24018316Swollman	for (; cp < cplim; cp++, cp2++)
24118316Swollman		if (*cp != *cp2)
24218316Swollman			goto on1;
24318316Swollman	/*
24418316Swollman	 * This extra grot is in case we are explicitly asked
24518316Swollman	 * to look up the default.  Ugh!
24618316Swollman	 * Or 255.255.255.255
24718316Swollman	 *
24818316Swollman	 * In this case, we have a complete match of the key.  Unless
24918316Swollman	 * the node is one of the roots, we are finished.
250229778Suqs	 * If it is the zeros root, then take what we have, preferring
25118316Swollman	 * any real data.
25218316Swollman	 * If it is the ones root, then pretend the target key was followed
25318316Swollman	 * by a byte of zeros.
25418316Swollman	 */
25518316Swollman	if (!(t->rn_flags & RNF_ROOT))
25618316Swollman		return t;		/* not a root */
25718316Swollman	if (t->rn_dupedkey) {
25818316Swollman		t = t->rn_dupedkey;
25918316Swollman		return t;		/* have some real data */
26018316Swollman	}
26118316Swollman	if (*(cp-1) == 0)
26218316Swollman		return t;		/* not the ones root */
26318316Swollman	b = 0;				/* fake a zero after 255.255.255.255 */
26418316Swollman	goto on2;
26518316Swollmanon1:
26618316Swollman	test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */
26718316Swollman	for (b = 7; (test >>= 1) > 0;)
26818316Swollman		b--;
26918316Swollmanon2:
27018316Swollman	matched_off = cp - v;
27118316Swollman	b += matched_off << 3;
27218316Swollman	rn_b = -1 - b;
27318316Swollman	/*
27418316Swollman	 * If there is a host route in a duped-key chain, it will be first.
27518316Swollman	 */
27618316Swollman	if ((saved_t = t)->rn_mask == 0)
27718316Swollman		t = t->rn_dupedkey;
27846303Smarkm	for (; t; t = t->rn_dupedkey) {
27918316Swollman		/*
28018316Swollman		 * Even if we don't match exactly as a host,
28118316Swollman		 * we may match if the leaf we wound up at is
28218316Swollman		 * a route to a net.
28318316Swollman		 */
28418316Swollman		if (t->rn_flags & RNF_NORMAL) {
28518316Swollman			if (rn_b <= t->rn_b)
28618316Swollman				return t;
28746303Smarkm		} else if (rn_satisfies_leaf(v, t, matched_off)) {
28846303Smarkm			return t;
28946303Smarkm		}
29046303Smarkm	}
29118316Swollman	t = saved_t;
29218316Swollman	/* start searching up the tree */
29318316Swollman	do {
29446303Smarkm		struct radix_mask *m;
29518316Swollman		t = t->rn_p;
29618316Swollman		if ((m = t->rn_mklist)) {
29718316Swollman			/*
29818316Swollman			 * If non-contiguous masks ever become important
29918316Swollman			 * we can restore the masking and open coding of
30018316Swollman			 * the search and satisfaction test and put the
30118316Swollman			 * calculation of "off" back before the "do".
30218316Swollman			 */
30318316Swollman			do {
30418316Swollman				if (m->rm_flags & RNF_NORMAL) {
30518316Swollman					if (rn_b <= m->rm_b)
30618316Swollman						return (m->rm_leaf);
30718316Swollman				} else {
30818316Swollman					off = min(t->rn_off, matched_off);
30918316Swollman					x = rn_search_m(v, t, m->rm_mask);
31018316Swollman					while (x && x->rn_mask != m->rm_mask)
31118316Swollman						x = x->rn_dupedkey;
31246303Smarkm					if (x && rn_satisfies_leaf(v, x, off))
31318316Swollman						    return x;
31418316Swollman				}
31518316Swollman			} while ((m = m->rm_mklist));
31618316Swollman		}
31718316Swollman	} while (t != top);
31818316Swollman	return 0;
31918316Swollman}
32018316Swollman
32118316Swollman#ifdef RN_DEBUG
32218316Swollmanint	rn_nodenum;
32318316Swollmanstruct	radix_node *rn_clist;
32418316Swollmanint	rn_saveinfo;
32518316Swollmanint	rn_debug =  1;
32618316Swollman#endif
32718316Swollman
328190715Sphkstatic struct radix_node *
32918316Swollmanrn_newpair(void *v, int b, struct radix_node nodes[2])
33018316Swollman{
33146303Smarkm	struct radix_node *tt = nodes, *t = tt + 1;
33218316Swollman	t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7);
33318316Swollman	t->rn_l = tt; t->rn_off = b >> 3;
33418316Swollman	tt->rn_b = -1; tt->rn_key = (caddr_t)v; tt->rn_p = t;
33518316Swollman	tt->rn_flags = t->rn_flags = RNF_ACTIVE;
33618316Swollman#ifdef RN_DEBUG
33718316Swollman	tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
33818316Swollman	tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt;
33918316Swollman#endif
34018316Swollman	return t;
34118316Swollman}
34218316Swollman
343190715Sphkstatic struct radix_node *
34418316Swollmanrn_insert(void* v_arg,
34518316Swollman	  struct radix_node_head *head,
34618316Swollman	  int *dupentry,
34718316Swollman	  struct radix_node nodes[2])
34818316Swollman{
34918316Swollman	caddr_t v = v_arg;
35018316Swollman	struct radix_node *top = head->rnh_treetop;
35118316Swollman	int head_off = top->rn_off, vlen = (int)*((u_char *)v);
35246303Smarkm	struct radix_node *t = rn_search(v_arg, top);
35346303Smarkm	caddr_t cp = v + head_off;
35446303Smarkm	int b;
35518316Swollman	struct radix_node *tt;
35618316Swollman
35718316Swollman	/*
35818316Swollman	 * Find first bit at which v and t->rn_key differ
35918316Swollman	 */
36018316Swollman    {
36146303Smarkm		caddr_t cp2 = t->rn_key + head_off;
36246303Smarkm		int cmp_res;
36318316Swollman	caddr_t cplim = v + vlen;
36418316Swollman
36518316Swollman	while (cp < cplim)
36618316Swollman		if (*cp2++ != *cp++)
36718316Swollman			goto on1;
36818316Swollman	/* handle adding 255.255.255.255 */
36918316Swollman	if (!(t->rn_flags & RNF_ROOT) || *(cp2-1) == 0) {
37018316Swollman		*dupentry = 1;
37118316Swollman		return t;
37218316Swollman	}
37318316Swollmanon1:
37418316Swollman	*dupentry = 0;
37518316Swollman	cmp_res = (cp[-1] ^ cp2[-1]) & 0xff;
37618316Swollman	for (b = (cp - v) << 3; cmp_res; b--)
37718316Swollman		cmp_res >>= 1;
37818316Swollman    }
37918316Swollman    {
38046303Smarkm	    struct radix_node *p, *x = top;
38118316Swollman	cp = v;
38218316Swollman	do {
38318316Swollman		p = x;
38418316Swollman		if (cp[x->rn_off] & x->rn_bmask)
38518316Swollman			x = x->rn_r;
38618316Swollman		else x = x->rn_l;
38746303Smarkm	} while ((unsigned)b > (unsigned)x->rn_b);
38818316Swollman#ifdef RN_DEBUG
38918316Swollman	if (rn_debug)
39018316Swollman		log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p);
39118316Swollman#endif
39218316Swollman	t = rn_newpair(v_arg, b, nodes); tt = t->rn_l;
39318316Swollman	if ((cp[p->rn_off] & p->rn_bmask) == 0)
39418316Swollman		p->rn_l = t;
39518316Swollman	else
39618316Swollman		p->rn_r = t;
39718316Swollman	x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */
39818316Swollman	if ((cp[t->rn_off] & t->rn_bmask) == 0) {
39918316Swollman		t->rn_r = x;
40018316Swollman	} else {
40118316Swollman		t->rn_r = tt; t->rn_l = x;
40218316Swollman	}
40318316Swollman#ifdef RN_DEBUG
40418316Swollman	if (rn_debug)
40518316Swollman		log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p);
40618316Swollman#endif
40718316Swollman    }
40818316Swollman	return (tt);
40918316Swollman}
41018316Swollman
411190715Sphkstatic struct radix_node *
41218316Swollmanrn_addmask(void *n_arg, int search, int skip)
41318316Swollman{
41418316Swollman	caddr_t netmask = (caddr_t)n_arg;
41546303Smarkm	struct radix_node *x;
41646303Smarkm	caddr_t cp, cplim;
41746303Smarkm	int b = 0, mlen, j;
41818316Swollman	int maskduplicated, m0, isnormal;
41918316Swollman	struct radix_node *saved_x;
42018316Swollman	static int last_zeroed = 0;
42118316Swollman
42218316Swollman	if ((mlen = *(u_char *)netmask) > max_keylen)
42318316Swollman		mlen = max_keylen;
42418316Swollman	if (skip == 0)
42518316Swollman		skip = 1;
42618316Swollman	if (mlen <= skip)
42718316Swollman		return (mask_rnhead->rnh_nodes);
42818316Swollman	if (skip > 1)
42918316Swollman		Bcopy(rn_ones + 1, addmask_key + 1, skip - 1);
43018316Swollman	if ((m0 = mlen) > skip)
43118316Swollman		Bcopy(netmask + skip, addmask_key + skip, mlen - skip);
43218316Swollman	/*
43318316Swollman	 * Trim trailing zeroes.
43418316Swollman	 */
43518316Swollman	for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;)
43618316Swollman		cp--;
43718316Swollman	mlen = cp - addmask_key;
43818316Swollman	if (mlen <= skip) {
43918316Swollman		if (m0 >= last_zeroed)
44018316Swollman			last_zeroed = mlen;
44118316Swollman		return (mask_rnhead->rnh_nodes);
44218316Swollman	}
44318316Swollman	if (m0 < last_zeroed)
44418316Swollman		Bzero(addmask_key + m0, last_zeroed - m0);
44518316Swollman	*addmask_key = last_zeroed = mlen;
44618316Swollman	x = rn_search(addmask_key, rn_masktop);
44718316Swollman	if (Bcmp(addmask_key, x->rn_key, mlen) != 0)
44818316Swollman		x = 0;
44918316Swollman	if (x || search)
45018316Swollman		return (x);
45146303Smarkm	x = (struct radix_node *)rtmalloc(max_keylen + 2*sizeof(*x),
45246303Smarkm					  "rn_addmask");
45346303Smarkm	saved_x = x;
45418316Swollman	Bzero(x, max_keylen + 2 * sizeof (*x));
45518316Swollman	netmask = cp = (caddr_t)(x + 2);
45618316Swollman	Bcopy(addmask_key, cp, mlen);
45718316Swollman	x = rn_insert(cp, mask_rnhead, &maskduplicated, x);
45818316Swollman	if (maskduplicated) {
45918316Swollman		log(LOG_ERR, "rn_addmask: mask impossibly already in tree");
46018316Swollman		Free(saved_x);
46118316Swollman		return (x);
46218316Swollman	}
46318316Swollman	/*
46418316Swollman	 * Calculate index of mask, and check for normalcy.
46518316Swollman	 */
46618316Swollman	cplim = netmask + mlen; isnormal = 1;
46718316Swollman	for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;)
46818316Swollman		cp++;
46918316Swollman	if (cp != cplim) {
47018316Swollman		for (j = 0x80; (j & *cp) != 0; j >>= 1)
47118316Swollman			b++;
47218316Swollman		if (*cp != normal_chars[b] || cp != (cplim - 1))
47318316Swollman			isnormal = 0;
47418316Swollman	}
47518316Swollman	b += (cp - netmask) << 3;
47618316Swollman	x->rn_b = -1 - b;
47718316Swollman	if (isnormal)
47818316Swollman		x->rn_flags |= RNF_NORMAL;
47918316Swollman	return (x);
48018316Swollman}
48118316Swollman
48218316Swollmanstatic int	/* XXX: arbitrary ordering for non-contiguous masks */
48318316Swollmanrn_lexobetter(void *m_arg, void *n_arg)
48418316Swollman{
48546303Smarkm	u_char *mp = m_arg, *np = n_arg, *lim;
48618316Swollman
48718316Swollman	if (*mp > *np)
48818316Swollman		return 1;  /* not really, but need to check longer one first */
48918316Swollman	if (*mp == *np)
49018316Swollman		for (lim = mp + *mp; mp < lim;)
49118316Swollman			if (*mp++ > *np++)
49218316Swollman				return 1;
49318316Swollman	return 0;
49418316Swollman}
49518316Swollman
49618316Swollmanstatic struct radix_mask *
49746303Smarkmrn_new_radix_mask(struct radix_node *tt,
49846303Smarkm		  struct radix_mask *next)
49918316Swollman{
50046303Smarkm	struct radix_mask *m;
50118316Swollman
50218316Swollman	MKGet(m);
50318316Swollman	if (m == 0) {
50418316Swollman		log(LOG_ERR, "Mask for route not entered\n");
50518316Swollman		return (0);
50618316Swollman	}
50718316Swollman	Bzero(m, sizeof *m);
50818316Swollman	m->rm_b = tt->rn_b;
50918316Swollman	m->rm_flags = tt->rn_flags;
51018316Swollman	if (tt->rn_flags & RNF_NORMAL)
51118316Swollman		m->rm_leaf = tt;
51218316Swollman	else
51318316Swollman		m->rm_mask = tt->rn_mask;
51418316Swollman	m->rm_mklist = next;
51518316Swollman	tt->rn_mklist = m;
51618316Swollman	return m;
51718316Swollman}
51818316Swollman
519190715Sphkstatic struct radix_node *
52018316Swollmanrn_addroute(void *v_arg,
52118316Swollman	    void *n_arg,
52218316Swollman	    struct radix_node_head *head,
52318316Swollman	    struct radix_node treenodes[2])
52418316Swollman{
52518316Swollman	caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg;
52646303Smarkm	struct radix_node *t, *x = 0, *tt;
52718316Swollman	struct radix_node *saved_tt, *top = head->rnh_treetop;
52818316Swollman	short b = 0, b_leaf = 0;
52918316Swollman	int keyduplicated;
53018316Swollman	caddr_t mmask;
53118316Swollman	struct radix_mask *m, **mp;
53218316Swollman
53318316Swollman	/*
53418316Swollman	 * In dealing with non-contiguous masks, there may be
53518316Swollman	 * many different routes which have the same mask.
53618316Swollman	 * We will find it useful to have a unique pointer to
53718316Swollman	 * the mask to speed avoiding duplicate references at
53818316Swollman	 * nodes and possibly save time in calculating indices.
53918316Swollman	 */
54018316Swollman	if (netmask)  {
54118316Swollman		if ((x = rn_addmask(netmask, 0, top->rn_off)) == 0)
54218316Swollman			return (0);
54318316Swollman		b_leaf = x->rn_b;
54418316Swollman		b = -1 - x->rn_b;
54518316Swollman		netmask = x->rn_key;
54618316Swollman	}
54718316Swollman	/*
54818316Swollman	 * Deal with duplicated keys: attach node to previous instance
54918316Swollman	 */
55018316Swollman	saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
55118316Swollman	if (keyduplicated) {
55218316Swollman		for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) {
55318316Swollman			if (tt->rn_mask == netmask)
55418316Swollman				return (0);
55518316Swollman			if (netmask == 0 ||
55618316Swollman			    (tt->rn_mask &&
55718316Swollman			     ((b_leaf < tt->rn_b) || /* index(netmask) > node */
55818316Swollman			       rn_refines(netmask, tt->rn_mask) ||
55918316Swollman			       rn_lexobetter(netmask, tt->rn_mask))))
56018316Swollman				break;
56118316Swollman		}
56218316Swollman		/*
56318316Swollman		 * If the mask is not duplicated, we wouldn't
56418316Swollman		 * find it among possible duplicate key entries
56518316Swollman		 * anyway, so the above test doesn't hurt.
56618316Swollman		 *
56718316Swollman		 * We sort the masks for a duplicated key the same way as
56818316Swollman		 * in a masklist -- most specific to least specific.
56918316Swollman		 * This may require the unfortunate nuisance of relocating
57018316Swollman		 * the head of the list.
57118316Swollman		 */
57218316Swollman		if (tt == saved_tt) {
57318316Swollman			struct	radix_node *xx = x;
57418316Swollman			/* link in at head of list */
57518316Swollman			(tt = treenodes)->rn_dupedkey = t;
57618316Swollman			tt->rn_flags = t->rn_flags;
57718316Swollman			tt->rn_p = x = t->rn_p;
57818316Swollman			if (x->rn_l == t) x->rn_l = tt; else x->rn_r = tt;
57918316Swollman			saved_tt = tt; x = xx;
58018316Swollman		} else {
58118316Swollman			(tt = treenodes)->rn_dupedkey = t->rn_dupedkey;
58218316Swollman			t->rn_dupedkey = tt;
58318316Swollman		}
58418316Swollman#ifdef RN_DEBUG
58518316Swollman		t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++;
58618316Swollman		tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt;
58718316Swollman#endif
58818316Swollman		tt->rn_key = (caddr_t) v;
58918316Swollman		tt->rn_b = -1;
59018316Swollman		tt->rn_flags = RNF_ACTIVE;
59118316Swollman	}
59218316Swollman	/*
59318316Swollman	 * Put mask in tree.
59418316Swollman	 */
59518316Swollman	if (netmask) {
59618316Swollman		tt->rn_mask = netmask;
59718316Swollman		tt->rn_b = x->rn_b;
59818316Swollman		tt->rn_flags |= x->rn_flags & RNF_NORMAL;
59918316Swollman	}
60018316Swollman	t = saved_tt->rn_p;
60118316Swollman	if (keyduplicated)
60218316Swollman		goto on2;
60318316Swollman	b_leaf = -1 - t->rn_b;
60418316Swollman	if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r;
60518316Swollman	/* Promote general routes from below */
60618316Swollman	if (x->rn_b < 0) {
60718316Swollman	    for (mp = &t->rn_mklist; x; x = x->rn_dupedkey)
60818316Swollman		if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) {
60918316Swollman			if ((*mp = m = rn_new_radix_mask(x, 0)))
61018316Swollman				mp = &m->rm_mklist;
61118316Swollman		}
61218316Swollman	} else if (x->rn_mklist) {
61318316Swollman		/*
61418316Swollman		 * Skip over masks whose index is > that of new node
61518316Swollman		 */
61618316Swollman		for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
61718316Swollman			if (m->rm_b >= b_leaf)
61818316Swollman				break;
61918316Swollman		t->rn_mklist = m; *mp = 0;
62018316Swollman	}
62118316Swollmanon2:
62218316Swollman	/* Add new route to highest possible ancestor's list */
62318316Swollman	if ((netmask == 0) || (b > t->rn_b ))
62418316Swollman		return tt; /* can't lift at all */
62518316Swollman	b_leaf = tt->rn_b;
62618316Swollman	do {
62718316Swollman		x = t;
62818316Swollman		t = t->rn_p;
62918316Swollman	} while (b <= t->rn_b && x != top);
63018316Swollman	/*
63118316Swollman	 * Search through routes associated with node to
63218316Swollman	 * insert new route according to index.
63318316Swollman	 * Need same criteria as when sorting dupedkeys to avoid
63418316Swollman	 * double loop on deletion.
63518316Swollman	 */
63618316Swollman	for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) {
63718316Swollman		if (m->rm_b < b_leaf)
63818316Swollman			continue;
63918316Swollman		if (m->rm_b > b_leaf)
64018316Swollman			break;
64118316Swollman		if (m->rm_flags & RNF_NORMAL) {
64218316Swollman			mmask = m->rm_leaf->rn_mask;
64318316Swollman			if (tt->rn_flags & RNF_NORMAL) {
64418316Swollman				log(LOG_ERR,
64518316Swollman				   "Non-unique normal route, mask not entered");
64618316Swollman				return tt;
64718316Swollman			}
64818316Swollman		} else
64918316Swollman			mmask = m->rm_mask;
65018316Swollman		if (mmask == netmask) {
65118316Swollman			m->rm_refs++;
65218316Swollman			tt->rn_mklist = m;
65318316Swollman			return tt;
65418316Swollman		}
65518316Swollman		if (rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask))
65618316Swollman			break;
65718316Swollman	}
65818316Swollman	*mp = rn_new_radix_mask(tt, *mp);
65918316Swollman	return tt;
66018316Swollman}
66118316Swollman
662190715Sphkstatic struct radix_node *
66318316Swollmanrn_delete(void *v_arg,
66418316Swollman	  void *netmask_arg,
66518316Swollman	  struct radix_node_head *head)
66618316Swollman{
66746303Smarkm	struct radix_node *t, *p, *x, *tt;
66818316Swollman	struct radix_mask *m, *saved_m, **mp;
66918316Swollman	struct radix_node *dupedkey, *saved_tt, *top;
67018316Swollman	caddr_t v, netmask;
67118316Swollman	int b, head_off, vlen;
67218316Swollman
67318316Swollman	v = v_arg;
67418316Swollman	netmask = netmask_arg;
67518316Swollman	x = head->rnh_treetop;
67618316Swollman	tt = rn_search(v, x);
67718316Swollman	head_off = x->rn_off;
67818316Swollman	vlen =  *(u_char *)v;
67918316Swollman	saved_tt = tt;
68018316Swollman	top = x;
68118316Swollman	if (tt == 0 ||
68218316Swollman	    Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off))
68318316Swollman		return (0);
68418316Swollman	/*
68518316Swollman	 * Delete our route from mask lists.
68618316Swollman	 */
68718316Swollman	if (netmask) {
68818316Swollman		if ((x = rn_addmask(netmask, 1, head_off)) == 0)
68918316Swollman			return (0);
69018316Swollman		netmask = x->rn_key;
69118316Swollman		while (tt->rn_mask != netmask)
69218316Swollman			if ((tt = tt->rn_dupedkey) == 0)
69318316Swollman				return (0);
69418316Swollman	}
69518316Swollman	if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
69618316Swollman		goto on1;
69718316Swollman	if (tt->rn_flags & RNF_NORMAL) {
69818316Swollman		if (m->rm_leaf != tt || m->rm_refs > 0) {
69918316Swollman			log(LOG_ERR, "rn_delete: inconsistent annotation\n");
70018316Swollman			return 0;  /* dangling ref could cause disaster */
70118316Swollman		}
70218316Swollman	} else {
70318316Swollman		if (m->rm_mask != tt->rn_mask) {
70418316Swollman			log(LOG_ERR, "rn_delete: inconsistent annotation\n");
70518316Swollman			goto on1;
70618316Swollman		}
70718316Swollman		if (--m->rm_refs >= 0)
70818316Swollman			goto on1;
70918316Swollman	}
71018316Swollman	b = -1 - tt->rn_b;
71118316Swollman	t = saved_tt->rn_p;
71218316Swollman	if (b > t->rn_b)
71318316Swollman		goto on1; /* Wasn't lifted at all */
71418316Swollman	do {
71518316Swollman		x = t;
71618316Swollman		t = t->rn_p;
71718316Swollman	} while (b <= t->rn_b && x != top);
71818316Swollman	for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
71918316Swollman		if (m == saved_m) {
72018316Swollman			*mp = m->rm_mklist;
72118316Swollman			MKFree(m);
72218316Swollman			break;
72318316Swollman		}
72418316Swollman	if (m == 0) {
72518316Swollman		log(LOG_ERR, "rn_delete: couldn't find our annotation\n");
72618316Swollman		if (tt->rn_flags & RNF_NORMAL)
72718316Swollman			return (0); /* Dangling ref to us */
72818316Swollman	}
72918316Swollmanon1:
73018316Swollman	/*
73118316Swollman	 * Eliminate us from tree
73218316Swollman	 */
73318316Swollman	if (tt->rn_flags & RNF_ROOT)
73418316Swollman		return (0);
73518316Swollman#ifdef RN_DEBUG
73618316Swollman	/* Get us out of the creation list */
73718316Swollman	for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {}
73818316Swollman	if (t) t->rn_ybro = tt->rn_ybro;
73918316Swollman#endif
74018316Swollman	t = tt->rn_p;
74118316Swollman	if ((dupedkey = saved_tt->rn_dupedkey)) {
74218316Swollman		if (tt == saved_tt) {
74318316Swollman			x = dupedkey; x->rn_p = t;
74418316Swollman			if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x;
74518316Swollman		} else {
74618316Swollman			for (x = p = saved_tt; p && p->rn_dupedkey != tt;)
74718316Swollman				p = p->rn_dupedkey;
74818316Swollman			if (p) p->rn_dupedkey = tt->rn_dupedkey;
74918316Swollman			else log(LOG_ERR, "rn_delete: couldn't find us\n");
75018316Swollman		}
75118316Swollman		t = tt + 1;
75218316Swollman		if  (t->rn_flags & RNF_ACTIVE) {
75318316Swollman#ifndef RN_DEBUG
75418316Swollman			*++x = *t; p = t->rn_p;
75518316Swollman#else
75618316Swollman			b = t->rn_info; *++x = *t; t->rn_info = b; p = t->rn_p;
75718316Swollman#endif
75818316Swollman			if (p->rn_l == t) p->rn_l = x; else p->rn_r = x;
75918316Swollman			x->rn_l->rn_p = x; x->rn_r->rn_p = x;
76018316Swollman		}
76118316Swollman		goto out;
76218316Swollman	}
76318316Swollman	if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l;
76418316Swollman	p = t->rn_p;
76518316Swollman	if (p->rn_r == t) p->rn_r = x; else p->rn_l = x;
76618316Swollman	x->rn_p = p;
76718316Swollman	/*
76818316Swollman	 * Demote routes attached to us.
76918316Swollman	 */
77018316Swollman	if (t->rn_mklist) {
77118316Swollman		if (x->rn_b >= 0) {
77218316Swollman			for (mp = &x->rn_mklist; (m = *mp);)
77318316Swollman				mp = &m->rm_mklist;
77418316Swollman			*mp = t->rn_mklist;
77518316Swollman		} else {
77618316Swollman			/* If there are any key,mask pairs in a sibling
77718316Swollman			   duped-key chain, some subset will appear sorted
77818316Swollman			   in the same order attached to our mklist */
77918316Swollman			for (m = t->rn_mklist; m && x; x = x->rn_dupedkey)
78018316Swollman				if (m == x->rn_mklist) {
78118316Swollman					struct radix_mask *mm = m->rm_mklist;
78218316Swollman					x->rn_mklist = 0;
78318316Swollman					if (--(m->rm_refs) < 0)
78418316Swollman						MKFree(m);
78518316Swollman					m = mm;
78618316Swollman				}
78718316Swollman			if (m)
78846303Smarkm				syslog(LOG_ERR, "%s 0x%lx at 0x%lx\n",
78918316Swollman				       "rn_delete: Orphaned Mask",
79018316Swollman				       (unsigned long)m,
79118316Swollman				       (unsigned long)x);
79218316Swollman		}
79318316Swollman	}
79418316Swollman	/*
79518316Swollman	 * We may be holding an active internal node in the tree.
79618316Swollman	 */
79718316Swollman	x = tt + 1;
79818316Swollman	if (t != x) {
79918316Swollman#ifndef RN_DEBUG
80018316Swollman		*t = *x;
80118316Swollman#else
80218316Swollman		b = t->rn_info; *t = *x; t->rn_info = b;
80318316Swollman#endif
80418316Swollman		t->rn_l->rn_p = t; t->rn_r->rn_p = t;
80518316Swollman		p = x->rn_p;
80618316Swollman		if (p->rn_l == x) p->rn_l = t; else p->rn_r = t;
80718316Swollman	}
80818316Swollmanout:
80918316Swollman	tt->rn_flags &= ~RNF_ACTIVE;
81018316Swollman	tt[1].rn_flags &= ~RNF_ACTIVE;
81118316Swollman	return (tt);
81218316Swollman}
81318316Swollman
81418316Swollmanint
81518316Swollmanrn_walktree(struct radix_node_head *h,
81646303Smarkm	    int (*f)(struct radix_node *, struct walkarg *),
81718316Swollman	    struct walkarg *w)
81818316Swollman{
81918316Swollman	int error;
82018316Swollman	struct radix_node *base, *next;
82146303Smarkm	struct radix_node *rn = h->rnh_treetop;
82218316Swollman	/*
82318316Swollman	 * This gets complicated because we may delete the node
82418316Swollman	 * while applying the function f to it, so we need to calculate
82518316Swollman	 * the successor node in advance.
82618316Swollman	 */
82718316Swollman	/* First time through node, go left */
82818316Swollman	while (rn->rn_b >= 0)
82918316Swollman		rn = rn->rn_l;
83018316Swollman	for (;;) {
83118316Swollman		base = rn;
83218316Swollman		/* If at right child go back up, otherwise, go right */
83318316Swollman		while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0)
83418316Swollman			rn = rn->rn_p;
83518316Swollman		/* Find the next *leaf* since next node might vanish, too */
83618316Swollman		for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;)
83718316Swollman			rn = rn->rn_l;
83818316Swollman		next = rn;
83918316Swollman		/* Process leaves */
84018316Swollman		while ((rn = base)) {
84118316Swollman			base = rn->rn_dupedkey;
84218316Swollman			if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w)))
84318316Swollman				return (error);
84418316Swollman		}
84518316Swollman		rn = next;
84618316Swollman		if (rn->rn_flags & RNF_ROOT)
84718316Swollman			return (0);
84818316Swollman	}
84918316Swollman	/* NOTREACHED */
85018316Swollman}
85118316Swollman
85218316Swollmanint
853190712Sphkrn_inithead(struct radix_node_head **head, int off)
85418316Swollman{
85546303Smarkm	struct radix_node_head *rnh;
85646303Smarkm	struct radix_node *t, *tt, *ttt;
85718316Swollman	if (*head)
85818316Swollman		return (1);
85946303Smarkm	rnh = (struct radix_node_head *)rtmalloc(sizeof(*rnh), "rn_inithead");
86018316Swollman	Bzero(rnh, sizeof (*rnh));
86118316Swollman	*head = rnh;
86218316Swollman	t = rn_newpair(rn_zeros, off, rnh->rnh_nodes);
86318316Swollman	ttt = rnh->rnh_nodes + 2;
86418316Swollman	t->rn_r = ttt;
86518316Swollman	t->rn_p = t;
86618316Swollman	tt = t->rn_l;
86718316Swollman	tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE;
86818316Swollman	tt->rn_b = -1 - off;
86918316Swollman	*ttt = *tt;
87018316Swollman	ttt->rn_key = rn_ones;
87118316Swollman	rnh->rnh_addaddr = rn_addroute;
87218316Swollman	rnh->rnh_deladdr = rn_delete;
87318316Swollman	rnh->rnh_matchaddr = rn_match;
87418316Swollman	rnh->rnh_lookup = rn_lookup;
87518316Swollman	rnh->rnh_walktree = rn_walktree;
87618316Swollman	rnh->rnh_treetop = t;
87718316Swollman	return (1);
87818316Swollman}
87918316Swollman
88018316Swollmanvoid
88118316Swollmanrn_init(void)
88218316Swollman{
88318316Swollman	char *cp, *cplim;
88418316Swollman	if (max_keylen == 0) {
88518316Swollman		printf("rn_init: radix functions require max_keylen be set\n");
88618316Swollman		return;
88718316Swollman	}
88837908Scharnier	rn_zeros = (char *)rtmalloc(3 * max_keylen, "rn_init");
88918316Swollman	Bzero(rn_zeros, 3 * max_keylen);
89018316Swollman	rn_ones = cp = rn_zeros + max_keylen;
89118316Swollman	addmask_key = cplim = rn_ones + max_keylen;
89218316Swollman	while (cp < cplim)
89318316Swollman		*cp++ = -1;
894190712Sphk	if (rn_inithead(&mask_rnhead, 0) == 0)
89518316Swollman		panic("rn_init 2");
89618316Swollman}
89718316Swollman
898