1c22d69bfSAxel Dörfler/*
2c22d69bfSAxel Dörfler * Copyright 2006, Haiku, Inc. All Rights Reserved.
3c22d69bfSAxel Dörfler * Distributed under the terms of the MIT License.
4c22d69bfSAxel Dörfler */
5c22d69bfSAxel Dörfler
6c22d69bfSAxel Dörfler/*
7c22d69bfSAxel Dörfler * Copyright (c) 1988, 1989, 1993
8c22d69bfSAxel Dörfler *	The Regents of the University of California.  All rights reserved.
9c22d69bfSAxel Dörfler *
10c22d69bfSAxel Dörfler * Redistribution and use in source and binary forms, with or without
11c22d69bfSAxel Dörfler * modification, are permitted provided that the following conditions
12c22d69bfSAxel Dörfler * are met:
13c22d69bfSAxel Dörfler * 1. Redistributions of source code must retain the above copyright
14c22d69bfSAxel Dörfler *    notice, this list of conditions and the following disclaimer.
15c22d69bfSAxel Dörfler * 2. Redistributions in binary form must reproduce the above copyright
16c22d69bfSAxel Dörfler *    notice, this list of conditions and the following disclaimer in the
17c22d69bfSAxel Dörfler *    documentation and/or other materials provided with the distribution.
18c22d69bfSAxel Dörfler * 4. Neither the name of the University nor the names of its contributors
19c22d69bfSAxel Dörfler *    may be used to endorse or promote products derived from this software
20c22d69bfSAxel Dörfler *    without specific prior written permission.
21c22d69bfSAxel Dörfler *
22c22d69bfSAxel Dörfler * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23c22d69bfSAxel Dörfler * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24c22d69bfSAxel Dörfler * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25c22d69bfSAxel Dörfler * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26c22d69bfSAxel Dörfler * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27c22d69bfSAxel Dörfler * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28c22d69bfSAxel Dörfler * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29c22d69bfSAxel Dörfler * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30c22d69bfSAxel Dörfler * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31c22d69bfSAxel Dörfler * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32c22d69bfSAxel Dörfler * SUCH DAMAGE.
33c22d69bfSAxel Dörfler */
34c22d69bfSAxel Dörfler
35c22d69bfSAxel Dörfler/*
36c22d69bfSAxel Dörfler * Routines to build and maintain radix trees for routing lookups.
37c22d69bfSAxel Dörfler */
38c22d69bfSAxel Dörfler
39c22d69bfSAxel Dörfler#include "radix.h"
40c22d69bfSAxel Dörfler
41c22d69bfSAxel Dörfler#include <KernelExport.h>
42c22d69bfSAxel Dörfler
43c22d69bfSAxel Dörfler#include <stdlib.h>
44c22d69bfSAxel Dörfler#include <string.h>
45c22d69bfSAxel Dörfler
46c22d69bfSAxel Dörfler
47c22d69bfSAxel Dörflerstatic int	rn_walktree_from(struct radix_node_head *h, void *a, void *m,
48c22d69bfSAxel Dörfler				walktree_f_t *f, void *w);
49c22d69bfSAxel Dörflerstatic int rn_walktree(struct radix_node_head *, walktree_f_t *, void *);
50c22d69bfSAxel Dörflerstatic struct radix_node *rn_insert(void *, struct radix_node_head *, int *,
51c22d69bfSAxel Dörfler	     		struct radix_node [2]);
52c22d69bfSAxel Dörflerstatic struct radix_node *rn_newpair(void *, int, struct radix_node[2]);
53c22d69bfSAxel Dörflerstatic struct radix_node *rn_search(void *, struct radix_node *);
54c22d69bfSAxel Dörflerstatic struct radix_node *rn_search_m(void *, struct radix_node *, void *);
55c22d69bfSAxel Dörfler
56c22d69bfSAxel Dörflerstatic int	max_keylen;
57c22d69bfSAxel Dörflerstatic struct radix_mask *rn_mkfreelist;
58c22d69bfSAxel Dörflerstatic struct radix_node_head *mask_rnhead;
59c22d69bfSAxel Dörfler/*
60c22d69bfSAxel Dörfler * Work area -- the following point to 3 buffers of size max_keylen,
61c22d69bfSAxel Dörfler * allocated in this order in a block of memory malloc'ed by rn_init.
62c22d69bfSAxel Dörfler */
63c22d69bfSAxel Dörflerstatic uint8 *rn_zeros, *rn_ones, *addmask_key;
64c22d69bfSAxel Dörfler
65c22d69bfSAxel Dörfler#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);}
66c22d69bfSAxel Dörfler
67c22d69bfSAxel Dörfler#define rn_masktop (mask_rnhead->rnh_treetop)
68c22d69bfSAxel Dörfler
69c22d69bfSAxel Dörflerstatic int	rn_lexobetter(void *m_arg, void *n_arg);
70c22d69bfSAxel Dörflerstatic struct radix_mask *rn_new_radix_mask(struct radix_node *tt,
71c22d69bfSAxel Dörfler					struct radix_mask *next);
72c22d69bfSAxel Dörflerstatic int	rn_satisfies_leaf(char *trial, struct radix_node *leaf,
73c22d69bfSAxel Dörfler					int skip);
74c22d69bfSAxel Dörfler
75c22d69bfSAxel Dörfler/*
76c22d69bfSAxel Dörfler * The data structure for the keys is a radix tree with one way
77c22d69bfSAxel Dörfler * branching removed.  The index rn_bit at an internal node n represents a bit
78c22d69bfSAxel Dörfler * position to be tested.  The tree is arranged so that all descendants
79c22d69bfSAxel Dörfler * of a node n have keys whose bits all agree up to position rn_bit - 1.
80c22d69bfSAxel Dörfler * (We say the index of n is rn_bit.)
81c22d69bfSAxel Dörfler *
82c22d69bfSAxel Dörfler * There is at least one descendant which has a one bit at position rn_bit,
83c22d69bfSAxel Dörfler * and at least one with a zero there.
84c22d69bfSAxel Dörfler *
85c22d69bfSAxel Dörfler * A route is determined by a pair of key and mask.  We require that the
86c22d69bfSAxel Dörfler * bit-wise logical and of the key and mask to be the key.
87c22d69bfSAxel Dörfler * We define the index of a route to associated with the mask to be
88c22d69bfSAxel Dörfler * the first bit number in the mask where 0 occurs (with bit number 0
89c22d69bfSAxel Dörfler * representing the highest order bit).
90c22d69bfSAxel Dörfler *
91c22d69bfSAxel Dörfler * We say a mask is normal if every bit is 0, past the index of the mask.
92c22d69bfSAxel Dörfler * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit,
93c22d69bfSAxel Dörfler * and m is a normal mask, then the route applies to every descendant of n.
94c22d69bfSAxel Dörfler * If the index(m) < rn_bit, this implies the trailing last few bits of k
95c22d69bfSAxel Dörfler * before bit b are all 0, (and hence consequently true of every descendant
96c22d69bfSAxel Dörfler * of n), so the route applies to all descendants of the node as well.
97c22d69bfSAxel Dörfler *
98c22d69bfSAxel Dörfler * Similar logic shows that a non-normal mask m such that
99c22d69bfSAxel Dörfler * index(m) <= index(n) could potentially apply to many children of n.
100c22d69bfSAxel Dörfler * Thus, for each non-host route, we attach its mask to a list at an internal
101c22d69bfSAxel Dörfler * node as high in the tree as we can go.
102c22d69bfSAxel Dörfler *
103c22d69bfSAxel Dörfler * The present version of the code makes use of normal routes in short-
104c22d69bfSAxel Dörfler * circuiting an explict mask and compare operation when testing whether
105c22d69bfSAxel Dörfler * a key satisfies a normal route, and also in remembering the unique leaf
106c22d69bfSAxel Dörfler * that governs a subtree.
107c22d69bfSAxel Dörfler */
108c22d69bfSAxel Dörfler
109c22d69bfSAxel Dörfler/*
110c22d69bfSAxel Dörfler * Most of the functions in this code assume that the key/mask arguments
111c22d69bfSAxel Dörfler * are sockaddr-like structures, where the first byte is an u_char
112c22d69bfSAxel Dörfler * indicating the size of the entire structure.
113c22d69bfSAxel Dörfler *
114c22d69bfSAxel Dörfler * To make the assumption more explicit, we use the LEN() macro to access
115c22d69bfSAxel Dörfler * this field. It is safe to pass an expression with side effects
116c22d69bfSAxel Dörfler * to LEN() as the argument is evaluated only once.
117c22d69bfSAxel Dörfler */
118c22d69bfSAxel Dörfler#define LEN(x) (*(const u_char *)(x))
119c22d69bfSAxel Dörfler
120c22d69bfSAxel Dörfler/*
121c22d69bfSAxel Dörfler * XXX THIS NEEDS TO BE FIXED
122c22d69bfSAxel Dörfler * In the code, pointers to keys and masks are passed as either
123c22d69bfSAxel Dörfler * 'void *' (because callers use to pass pointers of various kinds), or
124c22d69bfSAxel Dörfler * 'caddr_t' (which is fine for pointer arithmetics, but not very
125c22d69bfSAxel Dörfler * clean when you dereference it to access data). Furthermore, caddr_t
126c22d69bfSAxel Dörfler * is really 'char *', while the natural type to operate on keys and
127c22d69bfSAxel Dörfler * masks would be 'u_char'. This mismatch require a lot of casts and
128c22d69bfSAxel Dörfler * intermediate variables to adapt types that clutter the code.
129c22d69bfSAxel Dörfler */
130c22d69bfSAxel Dörfler
131c22d69bfSAxel Dörfler
132c22d69bfSAxel Dörflerstatic int	/* XXX: arbitrary ordering for non-contiguous masks */
133c22d69bfSAxel Dörflerrn_lexobetter(void *m_arg, void *n_arg)
134c22d69bfSAxel Dörfler{
135c22d69bfSAxel Dörfler	register uint8 *mp = m_arg, *np = n_arg, *lim;
136c22d69bfSAxel Dörfler
137c22d69bfSAxel Dörfler	if (LEN(mp) > LEN(np))
138c22d69bfSAxel Dörfler		return 1;  /* not really, but need to check longer one first */
139c22d69bfSAxel Dörfler	if (LEN(mp) == LEN(np)) {
140c22d69bfSAxel Dörfler		for (lim = mp + LEN(mp); mp < lim;) {
141c22d69bfSAxel Dörfler			if (*mp++ > *np++)
142c22d69bfSAxel Dörfler				return 1;
143c22d69bfSAxel Dörfler		}
144c22d69bfSAxel Dörfler	}
145c22d69bfSAxel Dörfler	return 0;
146c22d69bfSAxel Dörfler}
147c22d69bfSAxel Dörfler
148c22d69bfSAxel Dörfler
149c22d69bfSAxel Dörflerstatic struct radix_mask *
150c22d69bfSAxel Dörflerrn_new_radix_mask(register struct radix_node *tt, register struct radix_mask *next)
151c22d69bfSAxel Dörfler{
152c22d69bfSAxel Dörfler	register struct radix_mask *m;
153c22d69bfSAxel Dörfler
154c22d69bfSAxel Dörfler	if (rn_mkfreelist) {
155c22d69bfSAxel Dörfler		m = rn_mkfreelist;
156c22d69bfSAxel Dörfler		rn_mkfreelist = m->rm_mklist;
157c22d69bfSAxel Dörfler	} else
158c22d69bfSAxel Dörfler		m = (struct radix_mask *)malloc(sizeof(struct radix_mask));
159c22d69bfSAxel Dörfler	if (m == 0) {
160c22d69bfSAxel Dörfler		dprintf("Mask for route not entered\n");
161c22d69bfSAxel Dörfler		return 0;
162c22d69bfSAxel Dörfler	}
163c22d69bfSAxel Dörfler	memset(m, 0, sizeof *m);
164c22d69bfSAxel Dörfler	m->rm_bit = tt->rn_bit;
165c22d69bfSAxel Dörfler	m->rm_flags = tt->rn_flags;
166c22d69bfSAxel Dörfler	if (tt->rn_flags & RNF_NORMAL)
167c22d69bfSAxel Dörfler		m->rm_leaf = tt;
168c22d69bfSAxel Dörfler	else
169c22d69bfSAxel Dörfler		m->rm_mask = tt->rn_mask;
170c22d69bfSAxel Dörfler	m->rm_mklist = next;
171c22d69bfSAxel Dörfler	tt->rn_mklist = m;
172c22d69bfSAxel Dörfler	return m;
173c22d69bfSAxel Dörfler}
174c22d69bfSAxel Dörfler
175c22d69bfSAxel Dörfler
176c22d69bfSAxel Dörfler/*!
177c22d69bfSAxel Dörfler	Search a node in the tree matching the key.
178c22d69bfSAxel Dörfler*/
179c22d69bfSAxel Dörflerstatic struct radix_node *
180c22d69bfSAxel Dörflerrn_search(void *v_arg, struct radix_node *head)
181c22d69bfSAxel Dörfler{
182c22d69bfSAxel Dörfler	register struct radix_node *x;
183c22d69bfSAxel Dörfler	register caddr_t v;
184c22d69bfSAxel Dörfler
185c22d69bfSAxel Dörfler	for (x = head, v = v_arg; x->rn_bit >= 0;) {
186c22d69bfSAxel Dörfler		if (x->rn_bmask & v[x->rn_offset])
187c22d69bfSAxel Dörfler			x = x->rn_right;
188c22d69bfSAxel Dörfler		else
189c22d69bfSAxel Dörfler			x = x->rn_left;
190c22d69bfSAxel Dörfler	}
191c22d69bfSAxel Dörfler	return x;
192c22d69bfSAxel Dörfler}
193c22d69bfSAxel Dörfler
194c22d69bfSAxel Dörfler
195c22d69bfSAxel Dörfler/*!
196c22d69bfSAxel Dörfler	Same as above, but with an additional mask.
197c22d69bfSAxel Dörfler	XXX note this function is used only once.
198c22d69bfSAxel Dörfler*/
199c22d69bfSAxel Dörflerstatic struct radix_node *
200c22d69bfSAxel Dörflerrn_search_m(void *v_arg, struct radix_node *head, void *m_arg)
201c22d69bfSAxel Dörfler{
202c22d69bfSAxel Dörfler	register struct radix_node *x;
203c22d69bfSAxel Dörfler	register caddr_t v = v_arg, m = m_arg;
204c22d69bfSAxel Dörfler
205c22d69bfSAxel Dörfler	for (x = head; x->rn_bit >= 0;) {
206c22d69bfSAxel Dörfler		if ((x->rn_bmask & m[x->rn_offset])
207c22d69bfSAxel Dörfler			&& (x->rn_bmask & v[x->rn_offset]))
208c22d69bfSAxel Dörfler			x = x->rn_right;
209c22d69bfSAxel Dörfler		else
210c22d69bfSAxel Dörfler			x = x->rn_left;
211c22d69bfSAxel Dörfler	}
212c22d69bfSAxel Dörfler	return x;
213c22d69bfSAxel Dörfler}
214c22d69bfSAxel Dörfler
215c22d69bfSAxel Dörfler
216c22d69bfSAxel Dörflerstatic int
217c22d69bfSAxel Dörflerrn_satisfies_leaf(char *trial, register struct radix_node *leaf, int skip)
218c22d69bfSAxel Dörfler{
219c22d69bfSAxel Dörfler	register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask;
220c22d69bfSAxel Dörfler	char *cplim;
221c22d69bfSAxel Dörfler	int length = min(LEN(cp), LEN(cp2));
222c22d69bfSAxel Dörfler
223c22d69bfSAxel Dörfler	if (cp3 == 0)
224c22d69bfSAxel Dörfler		cp3 = rn_ones;
225c22d69bfSAxel Dörfler	else
226c22d69bfSAxel Dörfler		length = min(length, *(u_char *)cp3);
227c22d69bfSAxel Dörfler	cplim = cp + length; cp3 += skip; cp2 += skip;
228c22d69bfSAxel Dörfler	for (cp += skip; cp < cplim; cp++, cp2++, cp3++)
229c22d69bfSAxel Dörfler		if ((*cp ^ *cp2) & *cp3)
230c22d69bfSAxel Dörfler			return 0;
231c22d69bfSAxel Dörfler	return 1;
232c22d69bfSAxel Dörfler}
233c22d69bfSAxel Dörfler
234c22d69bfSAxel Dörfler
235c22d69bfSAxel Dörfler/*
236c22d69bfSAxel Dörfler * Whenever we add a new leaf to the tree, we also add a parent node,
237c22d69bfSAxel Dörfler * so we allocate them as an array of two elements: the first one must be
238c22d69bfSAxel Dörfler * the leaf (see RNTORT() in route.c), the second one is the parent.
239c22d69bfSAxel Dörfler * This routine initializes the relevant fields of the nodes, so that
240c22d69bfSAxel Dörfler * the leaf is the left child of the parent node, and both nodes have
241c22d69bfSAxel Dörfler * (almost) all all fields filled as appropriate.
242c22d69bfSAxel Dörfler * (XXX some fields are left unset, see the '#if 0' section).
243c22d69bfSAxel Dörfler * The function returns a pointer to the parent node.
244c22d69bfSAxel Dörfler */
245c22d69bfSAxel Dörfler
246c22d69bfSAxel Dörflerstatic struct radix_node *
247c22d69bfSAxel Dörflerrn_newpair(void *v, int b, struct radix_node nodes[2])
248c22d69bfSAxel Dörfler{
249c22d69bfSAxel Dörfler	register struct radix_node *tt = nodes, *t = tt + 1;
250c22d69bfSAxel Dörfler	t->rn_bit = b;
251c22d69bfSAxel Dörfler	t->rn_bmask = 0x80 >> (b & 7);
252c22d69bfSAxel Dörfler	t->rn_left = tt;
253c22d69bfSAxel Dörfler	t->rn_offset = b >> 3;
254c22d69bfSAxel Dörfler
255c22d69bfSAxel Dörfler#if 0  /* XXX perhaps we should fill these fields as well. */
256c22d69bfSAxel Dörfler	t->rn_parent = t->rn_right = NULL;
257c22d69bfSAxel Dörfler
258c22d69bfSAxel Dörfler	tt->rn_mask = NULL;
259c22d69bfSAxel Dörfler	tt->rn_dupedkey = NULL;
260c22d69bfSAxel Dörfler	tt->rn_bmask = 0;
261c22d69bfSAxel Dörfler#endif
262c22d69bfSAxel Dörfler	tt->rn_bit = -1;
263c22d69bfSAxel Dörfler	tt->rn_key = (caddr_t)v;
264c22d69bfSAxel Dörfler	tt->rn_parent = t;
265c22d69bfSAxel Dörfler	tt->rn_flags = t->rn_flags = RNF_ACTIVE;
266c22d69bfSAxel Dörfler	tt->rn_mklist = t->rn_mklist = 0;
267c22d69bfSAxel Dörfler	return t;
268c22d69bfSAxel Dörfler}
269c22d69bfSAxel Dörfler
270c22d69bfSAxel Dörfler
271c22d69bfSAxel Dörflerstatic struct radix_node *
272c22d69bfSAxel Dörflerrn_insert(void *v_arg, struct radix_node_head *head, int *dupentry,
273c22d69bfSAxel Dörfler	struct radix_node nodes[2])
274c22d69bfSAxel Dörfler{
275c22d69bfSAxel Dörfler	uint8 *v = v_arg;
276c22d69bfSAxel Dörfler	struct radix_node *top = head->rnh_treetop;
277c22d69bfSAxel Dörfler	int head_off = top->rn_offset, vlen = (int)LEN(v);
278c22d69bfSAxel Dörfler	register struct radix_node *t = rn_search(v_arg, top);
279c22d69bfSAxel Dörfler	register uint8 *cp = v + head_off;
280c22d69bfSAxel Dörfler	register int b;
281c22d69bfSAxel Dörfler	struct radix_node *tt;
282c22d69bfSAxel Dörfler	/*
283c22d69bfSAxel Dörfler	 * Find first bit at which v and t->rn_key differ
284c22d69bfSAxel Dörfler	 */
285c22d69bfSAxel Dörfler    {
286c22d69bfSAxel Dörfler		register uint8 *cp2 = t->rn_key + head_off;
287c22d69bfSAxel Dörfler		register int cmp_res;
288c22d69bfSAxel Dörfler		uint8 *cplim = v + vlen;
289c22d69bfSAxel Dörfler
290c22d69bfSAxel Dörfler		while (cp < cplim) {
291c22d69bfSAxel Dörfler			if (*cp2++ != *cp++)
292c22d69bfSAxel Dörfler				goto on1;
293c22d69bfSAxel Dörfler		}
294c22d69bfSAxel Dörfler		*dupentry = 1;
295c22d69bfSAxel Dörfler		return t;
296c22d69bfSAxel Dörfler	on1:
297c22d69bfSAxel Dörfler		*dupentry = 0;
298c22d69bfSAxel Dörfler		cmp_res = (cp[-1] ^ cp2[-1]) & 0xff;
299c22d69bfSAxel Dörfler		for (b = (cp - v) << 3; cmp_res; b--) {
300c22d69bfSAxel Dörfler			cmp_res >>= 1;
301c22d69bfSAxel Dörfler		}
302c22d69bfSAxel Dörfler    }
303c22d69bfSAxel Dörfler    {
304c22d69bfSAxel Dörfler		register struct radix_node *p, *x = top;
305c22d69bfSAxel Dörfler		cp = v;
306c22d69bfSAxel Dörfler		do {
307c22d69bfSAxel Dörfler			p = x;
308c22d69bfSAxel Dörfler			if (cp[x->rn_offset] & x->rn_bmask)
309c22d69bfSAxel Dörfler				x = x->rn_right;
310c22d69bfSAxel Dörfler			else
311c22d69bfSAxel Dörfler				x = x->rn_left;
312c22d69bfSAxel Dörfler		} while (b > (unsigned) x->rn_bit);
313c22d69bfSAxel Dörfler					/* x->rn_bit < b && x->rn_bit >= 0 */
314c22d69bfSAxel Dörfler		t = rn_newpair(v_arg, b, nodes);
315c22d69bfSAxel Dörfler		tt = t->rn_left;
316c22d69bfSAxel Dörfler		if ((cp[p->rn_offset] & p->rn_bmask) == 0)
317c22d69bfSAxel Dörfler			p->rn_left = t;
318c22d69bfSAxel Dörfler		else
319c22d69bfSAxel Dörfler			p->rn_right = t;
320c22d69bfSAxel Dörfler		x->rn_parent = t;
321c22d69bfSAxel Dörfler		t->rn_parent = p; /* frees x, p as temp vars below */
322c22d69bfSAxel Dörfler		if ((cp[t->rn_offset] & t->rn_bmask) == 0) {
323c22d69bfSAxel Dörfler			t->rn_right = x;
324c22d69bfSAxel Dörfler		} else {
325c22d69bfSAxel Dörfler			t->rn_right = tt;
326c22d69bfSAxel Dörfler			t->rn_left = x;
327c22d69bfSAxel Dörfler		}
328c22d69bfSAxel Dörfler    }
329c22d69bfSAxel Dörfler	return tt;
330c22d69bfSAxel Dörfler}
331c22d69bfSAxel Dörfler
332c22d69bfSAxel Dörfler
333c22d69bfSAxel Dörfler/*!
334c22d69bfSAxel Dörfler	This is the same as rn_walktree() except for the parameters and the
335c22d69bfSAxel Dörfler	exit.
336c22d69bfSAxel Dörfler*/
337c22d69bfSAxel Dörflerstatic int
338c22d69bfSAxel Dörflerrn_walktree_from(struct radix_node_head *h, void *a, void *m, walktree_f_t *f, void *w)
339c22d69bfSAxel Dörfler{
340c22d69bfSAxel Dörfler	int error;
341c22d69bfSAxel Dörfler	struct radix_node *base, *next;
342c22d69bfSAxel Dörfler	u_char *xa = (u_char *)a;
343c22d69bfSAxel Dörfler	u_char *xm = (u_char *)m;
344c22d69bfSAxel Dörfler	register struct radix_node *rn, *last = 0 /* shut up gcc */;
345c22d69bfSAxel Dörfler	int stopping = 0;
346c22d69bfSAxel Dörfler	int lastb;
347c22d69bfSAxel Dörfler
348c22d69bfSAxel Dörfler	/*
349c22d69bfSAxel Dörfler	 * rn_search_m is sort-of-open-coded here. We cannot use the
350c22d69bfSAxel Dörfler	 * function because we need to keep track of the last node seen.
351c22d69bfSAxel Dörfler	 */
352c22d69bfSAxel Dörfler	/* printf("about to search\n"); */
353c22d69bfSAxel Dörfler	for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) {
354c22d69bfSAxel Dörfler		last = rn;
355c22d69bfSAxel Dörfler		/* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n",
356c22d69bfSAxel Dörfler		       rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */
357c22d69bfSAxel Dörfler		if (!(rn->rn_bmask & xm[rn->rn_offset])) {
358c22d69bfSAxel Dörfler			break;
359c22d69bfSAxel Dörfler		}
360c22d69bfSAxel Dörfler		if (rn->rn_bmask & xa[rn->rn_offset]) {
361c22d69bfSAxel Dörfler			rn = rn->rn_right;
362c22d69bfSAxel Dörfler		} else {
363c22d69bfSAxel Dörfler			rn = rn->rn_left;
364c22d69bfSAxel Dörfler		}
365c22d69bfSAxel Dörfler	}
366c22d69bfSAxel Dörfler	/* printf("done searching\n"); */
367c22d69bfSAxel Dörfler
368c22d69bfSAxel Dörfler	/*
369c22d69bfSAxel Dörfler	 * Two cases: either we stepped off the end of our mask,
370c22d69bfSAxel Dörfler	 * in which case last == rn, or we reached a leaf, in which
371c22d69bfSAxel Dörfler	 * case we want to start from the last node we looked at.
372c22d69bfSAxel Dörfler	 * Either way, last is the node we want to start from.
373c22d69bfSAxel Dörfler	 */
374c22d69bfSAxel Dörfler	rn = last;
375c22d69bfSAxel Dörfler	lastb = rn->rn_bit;
376c22d69bfSAxel Dörfler
377c22d69bfSAxel Dörfler	/* printf("rn %p, lastb %d\n", rn, lastb);*/
378c22d69bfSAxel Dörfler
379c22d69bfSAxel Dörfler	/*
380c22d69bfSAxel Dörfler	 * This gets complicated because we may delete the node
381c22d69bfSAxel Dörfler	 * while applying the function f to it, so we need to calculate
382c22d69bfSAxel Dörfler	 * the successor node in advance.
383c22d69bfSAxel Dörfler	 */
384c22d69bfSAxel Dörfler	while (rn->rn_bit >= 0) {
385c22d69bfSAxel Dörfler		rn = rn->rn_left;
386c22d69bfSAxel Dörfler	}
387c22d69bfSAxel Dörfler
388c22d69bfSAxel Dörfler	while (!stopping) {
389c22d69bfSAxel Dörfler		/* printf("node %p (%d)\n", rn, rn->rn_bit); */
390c22d69bfSAxel Dörfler		base = rn;
391c22d69bfSAxel Dörfler		/* If at right child go back up, otherwise, go right */
392c22d69bfSAxel Dörfler		while (rn->rn_parent->rn_right == rn
393c22d69bfSAxel Dörfler			&& !(rn->rn_flags & RNF_ROOT)) {
394c22d69bfSAxel Dörfler			rn = rn->rn_parent;
395c22d69bfSAxel Dörfler
396c22d69bfSAxel Dörfler			/* if went up beyond last, stop */
397c22d69bfSAxel Dörfler			if (rn->rn_bit <= lastb) {
398c22d69bfSAxel Dörfler				stopping = 1;
399c22d69bfSAxel Dörfler				/* printf("up too far\n"); */
400c22d69bfSAxel Dörfler				/*
401c22d69bfSAxel Dörfler				 * XXX we should jump to the 'Process leaves'
402c22d69bfSAxel Dörfler				 * part, because the values of 'rn' and 'next'
403c22d69bfSAxel Dörfler				 * we compute will not be used. Not a big deal
404c22d69bfSAxel Dörfler				 * because this loop will terminate, but it is
405c22d69bfSAxel Dörfler				 * inefficient and hard to understand!
406c22d69bfSAxel Dörfler				 */
407c22d69bfSAxel Dörfler			}
408c22d69bfSAxel Dörfler		}
409c22d69bfSAxel Dörfler
410c22d69bfSAxel Dörfler		/*
411c22d69bfSAxel Dörfler		 * At the top of the tree, no need to traverse the right
412c22d69bfSAxel Dörfler		 * half, prevent the traversal of the entire tree in the
413c22d69bfSAxel Dörfler		 * case of default route.
414c22d69bfSAxel Dörfler		 */
415c22d69bfSAxel Dörfler		if (rn->rn_parent->rn_flags & RNF_ROOT)
416c22d69bfSAxel Dörfler			stopping = 1;
417c22d69bfSAxel Dörfler
418c22d69bfSAxel Dörfler		/* Find the next *leaf* since next node might vanish, too */
419c22d69bfSAxel Dörfler		for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;)
420c22d69bfSAxel Dörfler			rn = rn->rn_left;
421c22d69bfSAxel Dörfler		next = rn;
422c22d69bfSAxel Dörfler		/* Process leaves */
423c22d69bfSAxel Dörfler		while ((rn = base) != 0) {
424c22d69bfSAxel Dörfler			base = rn->rn_dupedkey;
425c22d69bfSAxel Dörfler			/* printf("leaf %p\n", rn); */
426c22d69bfSAxel Dörfler			if (!(rn->rn_flags & RNF_ROOT)
427c22d69bfSAxel Dörfler			    && (error = (*f)(rn, w)))
428c22d69bfSAxel Dörfler				return (error);
429c22d69bfSAxel Dörfler		}
430c22d69bfSAxel Dörfler		rn = next;
431c22d69bfSAxel Dörfler
432c22d69bfSAxel Dörfler		if (rn->rn_flags & RNF_ROOT) {
433c22d69bfSAxel Dörfler			/* printf("root, stopping"); */
434c22d69bfSAxel Dörfler			stopping = 1;
435c22d69bfSAxel Dörfler		}
436c22d69bfSAxel Dörfler	}
437c22d69bfSAxel Dörfler	return 0;
438c22d69bfSAxel Dörfler}
439c22d69bfSAxel Dörfler
440c22d69bfSAxel Dörfler
441c22d69bfSAxel Dörflerstatic int
442c22d69bfSAxel Dörflerrn_walktree(struct radix_node_head *h, walktree_f_t *f, void *w)
443c22d69bfSAxel Dörfler{
444c22d69bfSAxel Dörfler	int error;
445c22d69bfSAxel Dörfler	struct radix_node *base, *next;
446c22d69bfSAxel Dörfler	register struct radix_node *rn = h->rnh_treetop;
447c22d69bfSAxel Dörfler	/*
448c22d69bfSAxel Dörfler	 * This gets complicated because we may delete the node
449c22d69bfSAxel Dörfler	 * while applying the function f to it, so we need to calculate
450c22d69bfSAxel Dörfler	 * the successor node in advance.
451c22d69bfSAxel Dörfler	 */
452c22d69bfSAxel Dörfler	/* First time through node, go left */
453c22d69bfSAxel Dörfler	while (rn->rn_bit >= 0) {
454c22d69bfSAxel Dörfler		rn = rn->rn_left;
455c22d69bfSAxel Dörfler	}
456c22d69bfSAxel Dörfler	for (;;) {
457c22d69bfSAxel Dörfler		base = rn;
458c22d69bfSAxel Dörfler		/* If at right child go back up, otherwise, go right */
459c22d69bfSAxel Dörfler		while (rn->rn_parent->rn_right == rn
460c22d69bfSAxel Dörfler			&& (rn->rn_flags & RNF_ROOT) == 0) {
461c22d69bfSAxel Dörfler			rn = rn->rn_parent;
462c22d69bfSAxel Dörfler		}
463c22d69bfSAxel Dörfler		/* Find the next *leaf* since next node might vanish, too */
464c22d69bfSAxel Dörfler		for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) {
465c22d69bfSAxel Dörfler			rn = rn->rn_left;
466c22d69bfSAxel Dörfler		}
467c22d69bfSAxel Dörfler		next = rn;
468c22d69bfSAxel Dörfler		/* Process leaves */
469c22d69bfSAxel Dörfler		while ((rn = base)) {
470c22d69bfSAxel Dörfler			base = rn->rn_dupedkey;
471c22d69bfSAxel Dörfler			if (!(rn->rn_flags & RNF_ROOT)
472c22d69bfSAxel Dörfler			    && (error = (*f)(rn, w)))
473c22d69bfSAxel Dörfler				return error;
474c22d69bfSAxel Dörfler		}
475c22d69bfSAxel Dörfler		rn = next;
476c22d69bfSAxel Dörfler		if (rn->rn_flags & RNF_ROOT)
477c22d69bfSAxel Dörfler			return 0;
478c22d69bfSAxel Dörfler	}
479c22d69bfSAxel Dörfler	/* NOTREACHED */
480c22d69bfSAxel Dörfler}
481c22d69bfSAxel Dörfler
482c22d69bfSAxel Dörfler
483c22d69bfSAxel Dörfler//	#pragma mark - public API
484c22d69bfSAxel Dörfler
485c22d69bfSAxel Dörfler
486c22d69bfSAxel Dörflerstruct radix_node *
487c22d69bfSAxel Dörflerrn_lookup(void *v_arg, void *m_arg, struct radix_node_head *head)
488c22d69bfSAxel Dörfler{
489c22d69bfSAxel Dörfler	register struct radix_node *x;
490c22d69bfSAxel Dörfler	uint8 *netmask = NULL;
491c22d69bfSAxel Dörfler
492c22d69bfSAxel Dörfler	if (m_arg) {
493c22d69bfSAxel Dörfler		x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset);
494c22d69bfSAxel Dörfler		if (x == 0)
495c22d69bfSAxel Dörfler			return 0;
496c22d69bfSAxel Dörfler		netmask = x->rn_key;
497c22d69bfSAxel Dörfler	}
498c22d69bfSAxel Dörfler	x = rn_match(v_arg, head);
499c22d69bfSAxel Dörfler	if (x && netmask) {
500c22d69bfSAxel Dörfler		while (x && x->rn_mask != netmask)
501c22d69bfSAxel Dörfler			x = x->rn_dupedkey;
502c22d69bfSAxel Dörfler	}
503c22d69bfSAxel Dörfler	return x;
504c22d69bfSAxel Dörfler}
505c22d69bfSAxel Dörfler
506c22d69bfSAxel Dörfler
507c22d69bfSAxel Dörflerstruct radix_node *
508c22d69bfSAxel Dörflerrn_match(void *v_arg, struct radix_node_head *head)
509c22d69bfSAxel Dörfler{
510c22d69bfSAxel Dörfler	caddr_t v = v_arg;
511c22d69bfSAxel Dörfler	register struct radix_node *t = head->rnh_treetop, *x;
512c22d69bfSAxel Dörfler	register caddr_t cp = v, cp2;
513c22d69bfSAxel Dörfler	caddr_t cplim;
514c22d69bfSAxel Dörfler	struct radix_node *saved_t, *top = t;
515c22d69bfSAxel Dörfler	int off = t->rn_offset, vlen = LEN(cp), matched_off;
516c22d69bfSAxel Dörfler	register int test, b, rn_bit;
517c22d69bfSAxel Dörfler
518c22d69bfSAxel Dörfler	/*
519c22d69bfSAxel Dörfler	 * Open code rn_search(v, top) to avoid overhead of extra
520c22d69bfSAxel Dörfler	 * subroutine call.
521c22d69bfSAxel Dörfler	 */
522c22d69bfSAxel Dörfler	for (; t->rn_bit >= 0; ) {
523c22d69bfSAxel Dörfler		if (t->rn_bmask & cp[t->rn_offset])
524c22d69bfSAxel Dörfler			t = t->rn_right;
525c22d69bfSAxel Dörfler		else
526c22d69bfSAxel Dörfler			t = t->rn_left;
527c22d69bfSAxel Dörfler	}
528c22d69bfSAxel Dörfler	/*
529c22d69bfSAxel Dörfler	 * See if we match exactly as a host destination
530c22d69bfSAxel Dörfler	 * or at least learn how many bits match, for normal mask finesse.
531c22d69bfSAxel Dörfler	 *
532c22d69bfSAxel Dörfler	 * It doesn't hurt us to limit how many bytes to check
533c22d69bfSAxel Dörfler	 * to the length of the mask, since if it matches we had a genuine
534c22d69bfSAxel Dörfler	 * match and the leaf we have is the most specific one anyway;
535c22d69bfSAxel Dörfler	 * if it didn't match with a shorter length it would fail
536c22d69bfSAxel Dörfler	 * with a long one.  This wins big for class B&C netmasks which
537c22d69bfSAxel Dörfler	 * are probably the most common case...
538c22d69bfSAxel Dörfler	 */
539c22d69bfSAxel Dörfler	if (t->rn_mask)
540c22d69bfSAxel Dörfler		vlen = *(u_char *)t->rn_mask;
541c22d69bfSAxel Dörfler	cp += off; cp2 = t->rn_key + off; cplim = v + vlen;
542c22d69bfSAxel Dörfler	for (; cp < cplim; cp++, cp2++) {
543c22d69bfSAxel Dörfler		if (*cp != *cp2)
544c22d69bfSAxel Dörfler			goto on1;
545c22d69bfSAxel Dörfler	}
546c22d69bfSAxel Dörfler	/*
547c22d69bfSAxel Dörfler	 * This extra grot is in case we are explicitly asked
548c22d69bfSAxel Dörfler	 * to look up the default.  Ugh!
549c22d69bfSAxel Dörfler	 *
550c22d69bfSAxel Dörfler	 * Never return the root node itself, it seems to cause a
551c22d69bfSAxel Dörfler	 * lot of confusion.
552c22d69bfSAxel Dörfler	 */
553c22d69bfSAxel Dörfler	if (t->rn_flags & RNF_ROOT)
554c22d69bfSAxel Dörfler		t = t->rn_dupedkey;
555c22d69bfSAxel Dörfler	return t;
556c22d69bfSAxel Dörfleron1:
557c22d69bfSAxel Dörfler	test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */
558c22d69bfSAxel Dörfler	for (b = 7; (test >>= 1) > 0;)
559c22d69bfSAxel Dörfler		b--;
560c22d69bfSAxel Dörfler	matched_off = cp - v;
561c22d69bfSAxel Dörfler	b += matched_off << 3;
562c22d69bfSAxel Dörfler	rn_bit = -1 - b;
563c22d69bfSAxel Dörfler	/*
564c22d69bfSAxel Dörfler	 * If there is a host route in a duped-key chain, it will be first.
565c22d69bfSAxel Dörfler	 */
566c22d69bfSAxel Dörfler	if ((saved_t = t)->rn_mask == 0)
567c22d69bfSAxel Dörfler		t = t->rn_dupedkey;
568c22d69bfSAxel Dörfler	for (; t; t = t->rn_dupedkey) {
569c22d69bfSAxel Dörfler		/*
570c22d69bfSAxel Dörfler		 * Even if we don't match exactly as a host,
571c22d69bfSAxel Dörfler		 * we may match if the leaf we wound up at is
572c22d69bfSAxel Dörfler		 * a route to a net.
573c22d69bfSAxel Dörfler		 */
574c22d69bfSAxel Dörfler		if (t->rn_flags & RNF_NORMAL) {
575c22d69bfSAxel Dörfler			if (rn_bit <= t->rn_bit)
576c22d69bfSAxel Dörfler				return t;
577c22d69bfSAxel Dörfler		} else if (rn_satisfies_leaf(v, t, matched_off))
578c22d69bfSAxel Dörfler				return t;
579c22d69bfSAxel Dörfler	}
580c22d69bfSAxel Dörfler
581c22d69bfSAxel Dörfler	t = saved_t;
582c22d69bfSAxel Dörfler	/* start searching up the tree */
583c22d69bfSAxel Dörfler	do {
584c22d69bfSAxel Dörfler		register struct radix_mask *m;
585c22d69bfSAxel Dörfler		t = t->rn_parent;
586c22d69bfSAxel Dörfler		m = t->rn_mklist;
587c22d69bfSAxel Dörfler		/*
588c22d69bfSAxel Dörfler		 * If non-contiguous masks ever become important
589c22d69bfSAxel Dörfler		 * we can restore the masking and open coding of
590c22d69bfSAxel Dörfler		 * the search and satisfaction test and put the
591c22d69bfSAxel Dörfler		 * calculation of "off" back before the "do".
592c22d69bfSAxel Dörfler		 */
593c22d69bfSAxel Dörfler		while (m) {
594c22d69bfSAxel Dörfler			if (m->rm_flags & RNF_NORMAL) {
595c22d69bfSAxel Dörfler				if (rn_bit <= m->rm_bit)
596c22d69bfSAxel Dörfler					return (m->rm_leaf);
597c22d69bfSAxel Dörfler			} else {
598c22d69bfSAxel Dörfler				off = min(t->rn_offset, matched_off);
599c22d69bfSAxel Dörfler				x = rn_search_m(v, t, m->rm_mask);
600c22d69bfSAxel Dörfler				while (x && x->rn_mask != m->rm_mask)
601c22d69bfSAxel Dörfler					x = x->rn_dupedkey;
602c22d69bfSAxel Dörfler				if (x && rn_satisfies_leaf(v, x, off))
603c22d69bfSAxel Dörfler					return x;
604c22d69bfSAxel Dörfler			}
605c22d69bfSAxel Dörfler			m = m->rm_mklist;
606c22d69bfSAxel Dörfler		}
607c22d69bfSAxel Dörfler	} while (t != top);
608c22d69bfSAxel Dörfler
609c22d69bfSAxel Dörfler	return 0;
610c22d69bfSAxel Dörfler}
611c22d69bfSAxel Dörfler
612c22d69bfSAxel Dörfler
613c22d69bfSAxel Dörflerstruct radix_node *
614c22d69bfSAxel Dörflerrn_addmask(void *n_arg, int search, int skip)
615c22d69bfSAxel Dörfler{
616c22d69bfSAxel Dörfler	uint8 *netmask = (uint8 *)n_arg;
617c22d69bfSAxel Dörfler	register struct radix_node *x;
618c22d69bfSAxel Dörfler	register uint8 *cp, *cplim;
619c22d69bfSAxel Dörfler	register int b = 0, mlen, j;
620c22d69bfSAxel Dörfler	int maskduplicated, m0, isnormal;
621c22d69bfSAxel Dörfler	struct radix_node *saved_x;
622c22d69bfSAxel Dörfler	static int last_zeroed = 0;
623c22d69bfSAxel Dörfler
624c22d69bfSAxel Dörfler	if ((mlen = LEN(netmask)) > max_keylen)
625c22d69bfSAxel Dörfler		mlen = max_keylen;
626c22d69bfSAxel Dörfler	if (skip == 0)
627c22d69bfSAxel Dörfler		skip = 1;
628c22d69bfSAxel Dörfler	if (mlen <= skip)
629c22d69bfSAxel Dörfler		return mask_rnhead->rnh_nodes;
630c22d69bfSAxel Dörfler	if (skip > 1)
631c22d69bfSAxel Dörfler		memcpy(addmask_key + 1, rn_ones + 1, skip - 1);
632c22d69bfSAxel Dörfler	if ((m0 = mlen) > skip)
633c22d69bfSAxel Dörfler		memcpy(addmask_key + skip, netmask + skip, mlen - skip);
634c22d69bfSAxel Dörfler	/*
635c22d69bfSAxel Dörfler	 * Trim trailing zeroes.
636c22d69bfSAxel Dörfler	 */
637c22d69bfSAxel Dörfler	for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;)
638c22d69bfSAxel Dörfler		cp--;
639c22d69bfSAxel Dörfler	mlen = cp - addmask_key;
640c22d69bfSAxel Dörfler	if (mlen <= skip) {
641c22d69bfSAxel Dörfler		if (m0 >= last_zeroed)
642c22d69bfSAxel Dörfler			last_zeroed = mlen;
643c22d69bfSAxel Dörfler		return (mask_rnhead->rnh_nodes);
644c22d69bfSAxel Dörfler	}
645c22d69bfSAxel Dörfler	if (m0 < last_zeroed)
646c22d69bfSAxel Dörfler		memset(addmask_key + m0, 0, last_zeroed - m0);
647c22d69bfSAxel Dörfler	*addmask_key = last_zeroed = mlen;
648c22d69bfSAxel Dörfler	x = rn_search(addmask_key, rn_masktop);
649c22d69bfSAxel Dörfler	if (memcmp(addmask_key, x->rn_key, mlen) != 0)
650c22d69bfSAxel Dörfler		x = 0;
651c22d69bfSAxel Dörfler	if (x || search)
652c22d69bfSAxel Dörfler		return x;
653c22d69bfSAxel Dörfler	x = (struct radix_node *)calloc(1, max_keylen + 2 * sizeof(*x));
654c22d69bfSAxel Dörfler	if ((saved_x = x) == 0)
655c22d69bfSAxel Dörfler		return 0;
656c22d69bfSAxel Dörfler	netmask = cp = (caddr_t)(x + 2);
657c22d69bfSAxel Dörfler	memcpy(cp, addmask_key, mlen);
658c22d69bfSAxel Dörfler	x = rn_insert(cp, mask_rnhead, &maskduplicated, x);
659c22d69bfSAxel Dörfler	if (maskduplicated) {
660c22d69bfSAxel Dörfler		dprintf("rn_addmask: mask impossibly already in tree\n");
661c22d69bfSAxel Dörfler		free(saved_x);
662c22d69bfSAxel Dörfler		return x;
663c22d69bfSAxel Dörfler	}
664c22d69bfSAxel Dörfler	/*
665c22d69bfSAxel Dörfler	 * Calculate index of mask, and check for normalcy.
666c22d69bfSAxel Dörfler	 * First find the first byte with a 0 bit, then if there are
667c22d69bfSAxel Dörfler	 * more bits left (remember we already trimmed the trailing 0's),
668c22d69bfSAxel Dörfler	 * the pattern must be one of those in normal_chars[], or we have
669c22d69bfSAxel Dörfler	 * a non-contiguous mask.
670c22d69bfSAxel Dörfler	 */
671c22d69bfSAxel Dörfler	cplim = netmask + mlen;
672c22d69bfSAxel Dörfler	isnormal = 1;
673c22d69bfSAxel Dörfler	for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) {
674c22d69bfSAxel Dörfler		cp++;
675c22d69bfSAxel Dörfler	}
676c22d69bfSAxel Dörfler	if (cp != cplim) {
677c22d69bfSAxel Dörfler		static char normal_chars[] = {
678c22d69bfSAxel Dörfler			0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff};
679c22d69bfSAxel Dörfler
680c22d69bfSAxel Dörfler		for (j = 0x80; (j & *cp) != 0; j >>= 1)
681c22d69bfSAxel Dörfler			b++;
682c22d69bfSAxel Dörfler		if (*cp != normal_chars[b] || cp != (cplim - 1))
683c22d69bfSAxel Dörfler			isnormal = 0;
684c22d69bfSAxel Dörfler	}
685c22d69bfSAxel Dörfler	b += (cp - netmask) << 3;
686c22d69bfSAxel Dörfler	x->rn_bit = -1 - b;
687c22d69bfSAxel Dörfler	if (isnormal)
688c22d69bfSAxel Dörfler		x->rn_flags |= RNF_NORMAL;
689c22d69bfSAxel Dörfler	return x;
690c22d69bfSAxel Dörfler}
691c22d69bfSAxel Dörfler
692c22d69bfSAxel Dörfler
693c22d69bfSAxel Dörflerstruct radix_node *
694c22d69bfSAxel Dörflerrn_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
695c22d69bfSAxel Dörfler	struct radix_node treenodes[2])
696c22d69bfSAxel Dörfler{
697c22d69bfSAxel Dörfler	uint8 *v = (uint8 *)v_arg, *netmask = (uint8 *)n_arg;
698c22d69bfSAxel Dörfler	register struct radix_node *t, *x = 0, *tt;
699c22d69bfSAxel Dörfler	struct radix_node *saved_tt, *top = head->rnh_treetop;
700c22d69bfSAxel Dörfler	short b = 0, b_leaf = 0;
701c22d69bfSAxel Dörfler	int keyduplicated;
702c22d69bfSAxel Dörfler	uint8 *mmask;
703c22d69bfSAxel Dörfler	struct radix_mask *m, **mp;
704c22d69bfSAxel Dörfler
705c22d69bfSAxel Dörfler	/*
706c22d69bfSAxel Dörfler	 * In dealing with non-contiguous masks, there may be
707c22d69bfSAxel Dörfler	 * many different routes which have the same mask.
708c22d69bfSAxel Dörfler	 * We will find it useful to have a unique pointer to
709c22d69bfSAxel Dörfler	 * the mask to speed avoiding duplicate references at
710c22d69bfSAxel Dörfler	 * nodes and possibly save time in calculating indices.
711c22d69bfSAxel Dörfler	 */
712c22d69bfSAxel Dörfler	if (netmask)  {
713c22d69bfSAxel Dörfler		if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0)
714c22d69bfSAxel Dörfler			return (0);
715c22d69bfSAxel Dörfler		b_leaf = x->rn_bit;
716c22d69bfSAxel Dörfler		b = -1 - x->rn_bit;
717c22d69bfSAxel Dörfler		netmask = x->rn_key;
718c22d69bfSAxel Dörfler	}
719c22d69bfSAxel Dörfler	/*
720c22d69bfSAxel Dörfler	 * Deal with duplicated keys: attach node to previous instance
721c22d69bfSAxel Dörfler	 */
722c22d69bfSAxel Dörfler	saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes);
723c22d69bfSAxel Dörfler	if (keyduplicated) {
724c22d69bfSAxel Dörfler		for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) {
725c22d69bfSAxel Dörfler			if (tt->rn_mask == netmask)
726c22d69bfSAxel Dörfler				return (0);
727c22d69bfSAxel Dörfler			if (netmask == 0 ||
728c22d69bfSAxel Dörfler			    (tt->rn_mask &&
729c22d69bfSAxel Dörfler			     ((b_leaf < tt->rn_bit) /* index(netmask) > node */
730c22d69bfSAxel Dörfler			      || rn_refines(netmask, tt->rn_mask)
731c22d69bfSAxel Dörfler			      || rn_lexobetter(netmask, tt->rn_mask))))
732c22d69bfSAxel Dörfler				break;
733c22d69bfSAxel Dörfler		}
734c22d69bfSAxel Dörfler		/*
735c22d69bfSAxel Dörfler		 * If the mask is not duplicated, we wouldn't
736c22d69bfSAxel Dörfler		 * find it among possible duplicate key entries
737c22d69bfSAxel Dörfler		 * anyway, so the above test doesn't hurt.
738c22d69bfSAxel Dörfler		 *
739c22d69bfSAxel Dörfler		 * We sort the masks for a duplicated key the same way as
740c22d69bfSAxel Dörfler		 * in a masklist -- most specific to least specific.
741c22d69bfSAxel Dörfler		 * This may require the unfortunate nuisance of relocating
742c22d69bfSAxel Dörfler		 * the head of the list.
743c22d69bfSAxel Dörfler		 *
744c22d69bfSAxel Dörfler		 * We also reverse, or doubly link the list through the
745c22d69bfSAxel Dörfler		 * parent pointer.
746c22d69bfSAxel Dörfler		 */
747c22d69bfSAxel Dörfler		if (tt == saved_tt) {
748c22d69bfSAxel Dörfler			struct	radix_node *xx = x;
749c22d69bfSAxel Dörfler			/* link in at head of list */
750c22d69bfSAxel Dörfler			(tt = treenodes)->rn_dupedkey = t;
751c22d69bfSAxel Dörfler			tt->rn_flags = t->rn_flags;
752c22d69bfSAxel Dörfler			tt->rn_parent = x = t->rn_parent;
753c22d69bfSAxel Dörfler			t->rn_parent = tt;	 		/* parent */
754c22d69bfSAxel Dörfler			if (x->rn_left == t)
755c22d69bfSAxel Dörfler				x->rn_left = tt;
756c22d69bfSAxel Dörfler			else
757c22d69bfSAxel Dörfler				x->rn_right = tt;
758c22d69bfSAxel Dörfler			saved_tt = tt; x = xx;
759c22d69bfSAxel Dörfler		} else {
760c22d69bfSAxel Dörfler			(tt = treenodes)->rn_dupedkey = t->rn_dupedkey;
761c22d69bfSAxel Dörfler			t->rn_dupedkey = tt;
762c22d69bfSAxel Dörfler			tt->rn_parent = t;			/* parent */
763c22d69bfSAxel Dörfler			if (tt->rn_dupedkey)			/* parent */
764c22d69bfSAxel Dörfler				tt->rn_dupedkey->rn_parent = tt; /* parent */
765c22d69bfSAxel Dörfler		}
766c22d69bfSAxel Dörfler		tt->rn_key = (caddr_t) v;
767c22d69bfSAxel Dörfler		tt->rn_bit = -1;
768c22d69bfSAxel Dörfler		tt->rn_flags = RNF_ACTIVE;
769c22d69bfSAxel Dörfler	}
770c22d69bfSAxel Dörfler	/*
771c22d69bfSAxel Dörfler	 * Put mask in tree.
772c22d69bfSAxel Dörfler	 */
773c22d69bfSAxel Dörfler	if (netmask) {
774c22d69bfSAxel Dörfler		tt->rn_mask = netmask;
775c22d69bfSAxel Dörfler		tt->rn_bit = x->rn_bit;
776c22d69bfSAxel Dörfler		tt->rn_flags |= x->rn_flags & RNF_NORMAL;
777c22d69bfSAxel Dörfler	}
778c22d69bfSAxel Dörfler	t = saved_tt->rn_parent;
779c22d69bfSAxel Dörfler	if (keyduplicated)
780c22d69bfSAxel Dörfler		goto on2;
781c22d69bfSAxel Dörfler	b_leaf = -1 - t->rn_bit;
782c22d69bfSAxel Dörfler	if (t->rn_right == saved_tt)
783c22d69bfSAxel Dörfler		x = t->rn_left;
784c22d69bfSAxel Dörfler	else
785c22d69bfSAxel Dörfler		x = t->rn_right;
786c22d69bfSAxel Dörfler	/* Promote general routes from below */
787c22d69bfSAxel Dörfler	if (x->rn_bit < 0) {
788c22d69bfSAxel Dörfler	    for (mp = &t->rn_mklist; x; x = x->rn_dupedkey)
789c22d69bfSAxel Dörfler		if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) {
790c22d69bfSAxel Dörfler			*mp = m = rn_new_radix_mask(x, 0);
791c22d69bfSAxel Dörfler			if (m)
792c22d69bfSAxel Dörfler				mp = &m->rm_mklist;
793c22d69bfSAxel Dörfler		}
794c22d69bfSAxel Dörfler	} else if (x->rn_mklist) {
795c22d69bfSAxel Dörfler		/*
796c22d69bfSAxel Dörfler		 * Skip over masks whose index is > that of new node
797c22d69bfSAxel Dörfler		 */
798c22d69bfSAxel Dörfler		for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
799c22d69bfSAxel Dörfler			if (m->rm_bit >= b_leaf)
800c22d69bfSAxel Dörfler				break;
801c22d69bfSAxel Dörfler		t->rn_mklist = m; *mp = 0;
802c22d69bfSAxel Dörfler	}
803c22d69bfSAxel Dörfleron2:
804c22d69bfSAxel Dörfler	/* Add new route to highest possible ancestor's list */
805c22d69bfSAxel Dörfler	if ((netmask == 0) || (b > t->rn_bit ))
806c22d69bfSAxel Dörfler		return tt; /* can't lift at all */
807c22d69bfSAxel Dörfler	b_leaf = tt->rn_bit;
808c22d69bfSAxel Dörfler	do {
809c22d69bfSAxel Dörfler		x = t;
810c22d69bfSAxel Dörfler		t = t->rn_parent;
811c22d69bfSAxel Dörfler	} while (b <= t->rn_bit && x != top);
812c22d69bfSAxel Dörfler	/*
813c22d69bfSAxel Dörfler	 * Search through routes associated with node to
814c22d69bfSAxel Dörfler	 * insert new route according to index.
815c22d69bfSAxel Dörfler	 * Need same criteria as when sorting dupedkeys to avoid
816c22d69bfSAxel Dörfler	 * double loop on deletion.
817c22d69bfSAxel Dörfler	 */
818c22d69bfSAxel Dörfler	for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) {
819c22d69bfSAxel Dörfler		if (m->rm_bit < b_leaf)
820c22d69bfSAxel Dörfler			continue;
821c22d69bfSAxel Dörfler		if (m->rm_bit > b_leaf)
822c22d69bfSAxel Dörfler			break;
823c22d69bfSAxel Dörfler		if (m->rm_flags & RNF_NORMAL) {
824c22d69bfSAxel Dörfler			mmask = m->rm_leaf->rn_mask;
825c22d69bfSAxel Dörfler			if (tt->rn_flags & RNF_NORMAL) {
826c22d69bfSAxel Dörfler			    dprintf("Non-unique normal route, mask not entered\n");
827c22d69bfSAxel Dörfler				return tt;
828c22d69bfSAxel Dörfler			}
829c22d69bfSAxel Dörfler		} else
830c22d69bfSAxel Dörfler			mmask = m->rm_mask;
831c22d69bfSAxel Dörfler		if (mmask == netmask) {
832c22d69bfSAxel Dörfler			m->rm_refs++;
833c22d69bfSAxel Dörfler			tt->rn_mklist = m;
834c22d69bfSAxel Dörfler			return tt;
835c22d69bfSAxel Dörfler		}
836c22d69bfSAxel Dörfler		if (rn_refines(netmask, mmask)
837c22d69bfSAxel Dörfler		    || rn_lexobetter(netmask, mmask))
838c22d69bfSAxel Dörfler			break;
839c22d69bfSAxel Dörfler	}
840c22d69bfSAxel Dörfler	*mp = rn_new_radix_mask(tt, *mp);
841c22d69bfSAxel Dörfler	return tt;
842c22d69bfSAxel Dörfler}
843c22d69bfSAxel Dörfler
844c22d69bfSAxel Dörfler
845c22d69bfSAxel Dörflerstruct radix_node *
846c22d69bfSAxel Dörflerrn_delete(void *v_arg, void *netmask_arg, struct radix_node_head *head)
847c22d69bfSAxel Dörfler{
848c22d69bfSAxel Dörfler	register struct radix_node *t, *p, *x, *tt;
849c22d69bfSAxel Dörfler	struct radix_mask *m, *saved_m, **mp;
850c22d69bfSAxel Dörfler	struct radix_node *dupedkey, *saved_tt, *top;
851c22d69bfSAxel Dörfler	uint8 *v, *netmask;
852c22d69bfSAxel Dörfler	int b, head_off, vlen;
853c22d69bfSAxel Dörfler
854c22d69bfSAxel Dörfler	v = v_arg;
855c22d69bfSAxel Dörfler	netmask = netmask_arg;
856c22d69bfSAxel Dörfler	x = head->rnh_treetop;
857c22d69bfSAxel Dörfler	tt = rn_search(v, x);
858c22d69bfSAxel Dörfler	head_off = x->rn_offset;
859c22d69bfSAxel Dörfler	vlen =  LEN(v);
860c22d69bfSAxel Dörfler	saved_tt = tt;
861c22d69bfSAxel Dörfler	top = x;
862c22d69bfSAxel Dörfler	if (tt == 0
863c22d69bfSAxel Dörfler		|| memcmp(v + head_off, tt->rn_key + head_off, vlen - head_off))
864c22d69bfSAxel Dörfler		return 0;
865c22d69bfSAxel Dörfler	/*
866c22d69bfSAxel Dörfler	 * Delete our route from mask lists.
867c22d69bfSAxel Dörfler	 */
868c22d69bfSAxel Dörfler	if (netmask) {
869c22d69bfSAxel Dörfler		if ((x = rn_addmask(netmask, 1, head_off)) == 0)
870c22d69bfSAxel Dörfler			return 0;
871c22d69bfSAxel Dörfler		netmask = x->rn_key;
872c22d69bfSAxel Dörfler		while (tt->rn_mask != netmask)
873c22d69bfSAxel Dörfler			if ((tt = tt->rn_dupedkey) == 0)
874c22d69bfSAxel Dörfler				return 0;
875c22d69bfSAxel Dörfler	}
876c22d69bfSAxel Dörfler	if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0)
877c22d69bfSAxel Dörfler		goto on1;
878c22d69bfSAxel Dörfler	if (tt->rn_flags & RNF_NORMAL) {
879c22d69bfSAxel Dörfler		if (m->rm_leaf != tt || m->rm_refs > 0) {
880c22d69bfSAxel Dörfler			dprintf("rn_delete: inconsistent annotation\n");
881c22d69bfSAxel Dörfler			return 0;  /* dangling ref could cause disaster */
882c22d69bfSAxel Dörfler		}
883c22d69bfSAxel Dörfler	} else {
884c22d69bfSAxel Dörfler		if (m->rm_mask != tt->rn_mask) {
885c22d69bfSAxel Dörfler			dprintf("rn_delete: inconsistent annotation\n");
886c22d69bfSAxel Dörfler			goto on1;
887c22d69bfSAxel Dörfler		}
888c22d69bfSAxel Dörfler		if (--m->rm_refs >= 0)
889c22d69bfSAxel Dörfler			goto on1;
890c22d69bfSAxel Dörfler	}
891c22d69bfSAxel Dörfler	b = -1 - tt->rn_bit;
892c22d69bfSAxel Dörfler	t = saved_tt->rn_parent;
893c22d69bfSAxel Dörfler	if (b > t->rn_bit)
894c22d69bfSAxel Dörfler		goto on1; /* Wasn't lifted at all */
895c22d69bfSAxel Dörfler	do {
896c22d69bfSAxel Dörfler		x = t;
897c22d69bfSAxel Dörfler		t = t->rn_parent;
898c22d69bfSAxel Dörfler	} while (b <= t->rn_bit && x != top);
899c22d69bfSAxel Dörfler	for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist)
900c22d69bfSAxel Dörfler		if (m == saved_m) {
901c22d69bfSAxel Dörfler			*mp = m->rm_mklist;
902c22d69bfSAxel Dörfler			MKFree(m);
903c22d69bfSAxel Dörfler			break;
904c22d69bfSAxel Dörfler		}
905c22d69bfSAxel Dörfler	if (m == 0) {
906c22d69bfSAxel Dörfler		dprintf("rn_delete: couldn't find our annotation\n");
907c22d69bfSAxel Dörfler		if (tt->rn_flags & RNF_NORMAL)