radix.c revision 108268
11541Srgrimes/* 21541Srgrimes * Copyright (c) 1988, 1989, 1993 31541Srgrimes * The Regents of the University of California. All rights reserved. 41541Srgrimes * 51541Srgrimes * Redistribution and use in source and binary forms, with or without 61541Srgrimes * modification, are permitted provided that the following conditions 71541Srgrimes * are met: 81541Srgrimes * 1. Redistributions of source code must retain the above copyright 91541Srgrimes * notice, this list of conditions and the following disclaimer. 101541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111541Srgrimes * notice, this list of conditions and the following disclaimer in the 121541Srgrimes * documentation and/or other materials provided with the distribution. 131541Srgrimes * 3. All advertising materials mentioning features or use of this software 141541Srgrimes * must display the following acknowledgement: 151541Srgrimes * This product includes software developed by the University of 161541Srgrimes * California, Berkeley and its contributors. 171541Srgrimes * 4. Neither the name of the University nor the names of its contributors 181541Srgrimes * may be used to endorse or promote products derived from this software 191541Srgrimes * without specific prior written permission. 201541Srgrimes * 211541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 221541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 231541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 241541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 251541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 261541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 271541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 281541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 291541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 301541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 311541Srgrimes * SUCH DAMAGE. 321541Srgrimes * 33108268Sru * @(#)radix.c 8.5 (Berkeley) 5/19/95 3450477Speter * $FreeBSD: head/sys/net/radix.c 108268 2002-12-25 09:16:58Z ru $ 351541Srgrimes */ 361541Srgrimes 371541Srgrimes/* 381541Srgrimes * Routines to build and maintain radix trees for routing lookups. 391541Srgrimes */ 408152Spst#ifndef _RADIX_H_ 411541Srgrimes#include <sys/param.h> 4255205Speter#ifdef _KERNEL 431541Srgrimes#include <sys/systm.h> 441541Srgrimes#include <sys/malloc.h> 451541Srgrimes#include <sys/domain.h> 468152Spst#else 478152Spst#include <stdlib.h> 481541Srgrimes#endif 498152Spst#include <sys/syslog.h> 508152Spst#include <net/radix.h> 511541Srgrimes#endif 521541Srgrimes 5393084Sbdestatic int rn_walktree_from(struct radix_node_head *h, void *a, void *m, 5493084Sbde walktree_f_t *f, void *w); 5592725Salfredstatic int rn_walktree(struct radix_node_head *, walktree_f_t *, void *); 5612820Sphkstatic struct radix_node 5792725Salfred *rn_insert(void *, struct radix_node_head *, int *, 5893084Sbde struct radix_node [2]), 5992725Salfred *rn_newpair(void *, int, struct radix_node[2]), 6092725Salfred *rn_search(void *, struct radix_node *), 6192725Salfred *rn_search_m(void *, struct radix_node *, void *); 6212579Sbde 6312820Sphkstatic int max_keylen; 6412820Sphkstatic struct radix_mask *rn_mkfreelist; 6512820Sphkstatic struct radix_node_head *mask_rnhead; 668152Spststatic char *addmask_key; 678152Spststatic char normal_chars[] = {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1}; 681541Srgrimesstatic char *rn_zeros, *rn_ones; 691541Srgrimes 701541Srgrimes#define rn_masktop (mask_rnhead->rnh_treetop) 711541Srgrimes#undef Bcmp 7259529Swollman#define Bcmp(a, b, l) \ 73106696Salfred ((l) == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)(l))) 7412579Sbde 7592725Salfredstatic int rn_lexobetter(void *m_arg, void *n_arg); 7612579Sbdestatic struct radix_mask * 7792725Salfred rn_new_radix_mask(struct radix_node *tt, 7893084Sbde struct radix_mask *next); 7992725Salfredstatic int rn_satsifies_leaf(char *trial, struct radix_node *leaf, 8093084Sbde int skip); 8112579Sbde 821541Srgrimes/* 831541Srgrimes * The data structure for the keys is a radix tree with one way 8459529Swollman * branching removed. The index rn_bit at an internal node n represents a bit 851541Srgrimes * position to be tested. The tree is arranged so that all descendants 8659529Swollman * of a node n have keys whose bits all agree up to position rn_bit - 1. 8759529Swollman * (We say the index of n is rn_bit.) 881541Srgrimes * 8959529Swollman * There is at least one descendant which has a one bit at position rn_bit, 901541Srgrimes * and at least one with a zero there. 911541Srgrimes * 921541Srgrimes * A route is determined by a pair of key and mask. We require that the 931541Srgrimes * bit-wise logical and of the key and mask to be the key. 941541Srgrimes * We define the index of a route to associated with the mask to be 951541Srgrimes * the first bit number in the mask where 0 occurs (with bit number 0 961541Srgrimes * representing the highest order bit). 978876Srgrimes * 981541Srgrimes * We say a mask is normal if every bit is 0, past the index of the mask. 9959529Swollman * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit, 1001541Srgrimes * and m is a normal mask, then the route applies to every descendant of n. 10159529Swollman * If the index(m) < rn_bit, this implies the trailing last few bits of k 1021541Srgrimes * before bit b are all 0, (and hence consequently true of every descendant 1031541Srgrimes * of n), so the route applies to all descendants of the node as well. 1048876Srgrimes * 1058152Spst * Similar logic shows that a non-normal mask m such that 1061541Srgrimes * index(m) <= index(n) could potentially apply to many children of n. 1071541Srgrimes * Thus, for each non-host route, we attach its mask to a list at an internal 1088876Srgrimes * node as high in the tree as we can go. 1098152Spst * 1108152Spst * The present version of the code makes use of normal routes in short- 1118152Spst * circuiting an explict mask and compare operation when testing whether 1128152Spst * a key satisfies a normal route, and also in remembering the unique leaf 1138152Spst * that governs a subtree. 1141541Srgrimes */ 1151541Srgrimes 11612820Sphkstatic struct radix_node * 1171541Srgrimesrn_search(v_arg, head) 1181541Srgrimes void *v_arg; 1191541Srgrimes struct radix_node *head; 1201541Srgrimes{ 1211541Srgrimes register struct radix_node *x; 1221541Srgrimes register caddr_t v; 1231541Srgrimes 12459529Swollman for (x = head, v = v_arg; x->rn_bit >= 0;) { 12559529Swollman if (x->rn_bmask & v[x->rn_offset]) 12659529Swollman x = x->rn_right; 1271541Srgrimes else 12859529Swollman x = x->rn_left; 1291541Srgrimes } 1301541Srgrimes return (x); 13131390Sbde} 1321541Srgrimes 13312820Sphkstatic struct radix_node * 1341541Srgrimesrn_search_m(v_arg, head, m_arg) 1351541Srgrimes struct radix_node *head; 1361541Srgrimes void *v_arg, *m_arg; 1371541Srgrimes{ 1381541Srgrimes register struct radix_node *x; 1391541Srgrimes register caddr_t v = v_arg, m = m_arg; 1401541Srgrimes 14159529Swollman for (x = head; x->rn_bit >= 0;) { 14259529Swollman if ((x->rn_bmask & m[x->rn_offset]) && 14359529Swollman (x->rn_bmask & v[x->rn_offset])) 14459529Swollman x = x->rn_right; 1451541Srgrimes else 14659529Swollman x = x->rn_left; 1471541Srgrimes } 1481541Srgrimes return x; 14931390Sbde} 1501541Srgrimes 1511541Srgrimesint 1521541Srgrimesrn_refines(m_arg, n_arg) 1531541Srgrimes void *m_arg, *n_arg; 1541541Srgrimes{ 1551541Srgrimes register caddr_t m = m_arg, n = n_arg; 1561541Srgrimes register caddr_t lim, lim2 = lim = n + *(u_char *)n; 1571541Srgrimes int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); 1581541Srgrimes int masks_are_equal = 1; 1591541Srgrimes 1601541Srgrimes if (longer > 0) 1611541Srgrimes lim -= longer; 1621541Srgrimes while (n < lim) { 1631541Srgrimes if (*n & ~(*m)) 1641541Srgrimes return 0; 1651541Srgrimes if (*n++ != *m++) 1661541Srgrimes masks_are_equal = 0; 1671541Srgrimes } 1681541Srgrimes while (n < lim2) 1691541Srgrimes if (*n++) 1701541Srgrimes return 0; 1711541Srgrimes if (masks_are_equal && (longer < 0)) 1721541Srgrimes for (lim2 = m - longer; m < lim2; ) 1731541Srgrimes if (*m++) 1741541Srgrimes return 1; 1751541Srgrimes return (!masks_are_equal); 1761541Srgrimes} 1771541Srgrimes 1788152Spststruct radix_node * 1798152Spstrn_lookup(v_arg, m_arg, head) 1808152Spst void *v_arg, *m_arg; 1818152Spst struct radix_node_head *head; 1828152Spst{ 1838152Spst register struct radix_node *x; 1848152Spst caddr_t netmask = 0; 1851541Srgrimes 1868152Spst if (m_arg) { 18759529Swollman x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset); 18859529Swollman if (x == 0) 1898152Spst return (0); 1908152Spst netmask = x->rn_key; 1918152Spst } 1928152Spst x = rn_match(v_arg, head); 1938152Spst if (x && netmask) { 1948152Spst while (x && x->rn_mask != netmask) 1958152Spst x = x->rn_dupedkey; 1968152Spst } 1978152Spst return x; 1988152Spst} 1998152Spst 2008152Spststatic int 2018152Spstrn_satsifies_leaf(trial, leaf, skip) 2028152Spst char *trial; 2038152Spst register struct radix_node *leaf; 2048152Spst int skip; 2058152Spst{ 2068152Spst register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 2078152Spst char *cplim; 2088152Spst int length = min(*(u_char *)cp, *(u_char *)cp2); 2098152Spst 2108152Spst if (cp3 == 0) 2118152Spst cp3 = rn_ones; 2128152Spst else 2138152Spst length = min(length, *(u_char *)cp3); 2148152Spst cplim = cp + length; cp3 += skip; cp2 += skip; 2158152Spst for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 2168152Spst if ((*cp ^ *cp2) & *cp3) 2178152Spst return 0; 2188152Spst return 1; 2198152Spst} 2208152Spst 2211541Srgrimesstruct radix_node * 2221541Srgrimesrn_match(v_arg, head) 2231541Srgrimes void *v_arg; 2241541Srgrimes struct radix_node_head *head; 2251541Srgrimes{ 2261541Srgrimes caddr_t v = v_arg; 2271541Srgrimes register struct radix_node *t = head->rnh_treetop, *x; 2288152Spst register caddr_t cp = v, cp2; 2298152Spst caddr_t cplim; 2301541Srgrimes struct radix_node *saved_t, *top = t; 23159529Swollman int off = t->rn_offset, vlen = *(u_char *)cp, matched_off; 23259529Swollman register int test, b, rn_bit; 2331541Srgrimes 2341541Srgrimes /* 2351541Srgrimes * Open code rn_search(v, top) to avoid overhead of extra 2361541Srgrimes * subroutine call. 2371541Srgrimes */ 23859529Swollman for (; t->rn_bit >= 0; ) { 23959529Swollman if (t->rn_bmask & cp[t->rn_offset]) 24059529Swollman t = t->rn_right; 2411541Srgrimes else 24259529Swollman t = t->rn_left; 2431541Srgrimes } 2441541Srgrimes /* 2451541Srgrimes * See if we match exactly as a host destination 2468152Spst * or at least learn how many bits match, for normal mask finesse. 2478152Spst * 2488152Spst * It doesn't hurt us to limit how many bytes to check 2498152Spst * to the length of the mask, since if it matches we had a genuine 2508152Spst * match and the leaf we have is the most specific one anyway; 2518152Spst * if it didn't match with a shorter length it would fail 2528152Spst * with a long one. This wins big for class B&C netmasks which 2538152Spst * are probably the most common case... 2541541Srgrimes */ 2558152Spst if (t->rn_mask) 2568152Spst vlen = *(u_char *)t->rn_mask; 2571541Srgrimes cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 2581541Srgrimes for (; cp < cplim; cp++, cp2++) 2591541Srgrimes if (*cp != *cp2) 2601541Srgrimes goto on1; 2611541Srgrimes /* 2621541Srgrimes * This extra grot is in case we are explicitly asked 2631541Srgrimes * to look up the default. Ugh! 26448215Spb * 26548215Spb * Never return the root node itself, it seems to cause a 26648215Spb * lot of confusion. 2671541Srgrimes */ 26848215Spb if (t->rn_flags & RNF_ROOT) 2691541Srgrimes t = t->rn_dupedkey; 2701541Srgrimes return t; 2711541Srgrimeson1: 2728152Spst test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 2738152Spst for (b = 7; (test >>= 1) > 0;) 2748152Spst b--; 2751541Srgrimes matched_off = cp - v; 2768152Spst b += matched_off << 3; 27759529Swollman rn_bit = -1 - b; 2788152Spst /* 2798152Spst * If there is a host route in a duped-key chain, it will be first. 2808152Spst */ 2818152Spst if ((saved_t = t)->rn_mask == 0) 2828152Spst t = t->rn_dupedkey; 2838152Spst for (; t; t = t->rn_dupedkey) 2841541Srgrimes /* 2858152Spst * Even if we don't match exactly as a host, 2861541Srgrimes * we may match if the leaf we wound up at is 2871541Srgrimes * a route to a net. 2881541Srgrimes */ 2898152Spst if (t->rn_flags & RNF_NORMAL) { 29059529Swollman if (rn_bit <= t->rn_bit) 2918152Spst return t; 2928152Spst } else if (rn_satsifies_leaf(v, t, matched_off)) 2938152Spst return t; 2941541Srgrimes t = saved_t; 2951541Srgrimes /* start searching up the tree */ 2961541Srgrimes do { 2971541Srgrimes register struct radix_mask *m; 29859529Swollman t = t->rn_parent; 2993443Sphk m = t->rn_mklist; 30059529Swollman /* 30159529Swollman * If non-contiguous masks ever become important 30259529Swollman * we can restore the masking and open coding of 30359529Swollman * the search and satisfaction test and put the 30459529Swollman * calculation of "off" back before the "do". 30559529Swollman */ 30659529Swollman while (m) { 30759529Swollman if (m->rm_flags & RNF_NORMAL) { 30859529Swollman if (rn_bit <= m->rm_bit) 30959529Swollman return (m->rm_leaf); 31059529Swollman } else { 31159529Swollman off = min(t->rn_offset, matched_off); 31259529Swollman x = rn_search_m(v, t, m->rm_mask); 31359529Swollman while (x && x->rn_mask != m->rm_mask) 31459529Swollman x = x->rn_dupedkey; 31559529Swollman if (x && rn_satsifies_leaf(v, x, off)) 31659529Swollman return x; 31759529Swollman } 31859529Swollman m = m->rm_mklist; 3191541Srgrimes } 3201541Srgrimes } while (t != top); 3211541Srgrimes return 0; 32231390Sbde} 3238876Srgrimes 3241541Srgrimes#ifdef RN_DEBUG 3251541Srgrimesint rn_nodenum; 3261541Srgrimesstruct radix_node *rn_clist; 3271541Srgrimesint rn_saveinfo; 3281541Srgrimesint rn_debug = 1; 3291541Srgrimes#endif 3301541Srgrimes 33112820Sphkstatic struct radix_node * 3321541Srgrimesrn_newpair(v, b, nodes) 3331541Srgrimes void *v; 3341541Srgrimes int b; 3351541Srgrimes struct radix_node nodes[2]; 3361541Srgrimes{ 3371541Srgrimes register struct radix_node *tt = nodes, *t = tt + 1; 33859529Swollman t->rn_bit = b; 33959529Swollman t->rn_bmask = 0x80 >> (b & 7); 34059529Swollman t->rn_left = tt; 34159529Swollman t->rn_offset = b >> 3; 34259529Swollman tt->rn_bit = -1; 34359529Swollman tt->rn_key = (caddr_t)v; 34459529Swollman tt->rn_parent = t; 3451541Srgrimes tt->rn_flags = t->rn_flags = RNF_ACTIVE; 34667727Swollman tt->rn_mklist = t->rn_mklist = 0; 3471541Srgrimes#ifdef RN_DEBUG 3481541Srgrimes tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 34959529Swollman tt->rn_twin = t; 35059529Swollman tt->rn_ybro = rn_clist; 35159529Swollman rn_clist = tt; 3521541Srgrimes#endif 3531541Srgrimes return t; 3541541Srgrimes} 3551541Srgrimes 35612820Sphkstatic struct radix_node * 3571541Srgrimesrn_insert(v_arg, head, dupentry, nodes) 3581541Srgrimes void *v_arg; 3591541Srgrimes struct radix_node_head *head; 3601541Srgrimes int *dupentry; 3611541Srgrimes struct radix_node nodes[2]; 3621541Srgrimes{ 3631541Srgrimes caddr_t v = v_arg; 3641541Srgrimes struct radix_node *top = head->rnh_treetop; 36559529Swollman int head_off = top->rn_offset, vlen = (int)*((u_char *)v); 3661541Srgrimes register struct radix_node *t = rn_search(v_arg, top); 3671541Srgrimes register caddr_t cp = v + head_off; 3681541Srgrimes register int b; 3691541Srgrimes struct radix_node *tt; 3701541Srgrimes /* 3718152Spst * Find first bit at which v and t->rn_key differ 3721541Srgrimes */ 3731541Srgrimes { 3741541Srgrimes register caddr_t cp2 = t->rn_key + head_off; 3751541Srgrimes register int cmp_res; 3761541Srgrimes caddr_t cplim = v + vlen; 3771541Srgrimes 3781541Srgrimes while (cp < cplim) 3791541Srgrimes if (*cp2++ != *cp++) 3801541Srgrimes goto on1; 3811541Srgrimes *dupentry = 1; 3821541Srgrimes return t; 3831541Srgrimeson1: 3841541Srgrimes *dupentry = 0; 3851541Srgrimes cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 3861541Srgrimes for (b = (cp - v) << 3; cmp_res; b--) 3871541Srgrimes cmp_res >>= 1; 3881541Srgrimes } 3891541Srgrimes { 3901541Srgrimes register struct radix_node *p, *x = top; 3911541Srgrimes cp = v; 3921541Srgrimes do { 3931541Srgrimes p = x; 39459529Swollman if (cp[x->rn_offset] & x->rn_bmask) 39559529Swollman x = x->rn_right; 39659529Swollman else 39759529Swollman x = x->rn_left; 39859529Swollman } while (b > (unsigned) x->rn_bit); 39959529Swollman /* x->rn_bit < b && x->rn_bit >= 0 */ 4001541Srgrimes#ifdef RN_DEBUG 4011541Srgrimes if (rn_debug) 4028152Spst log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); 4031541Srgrimes#endif 40459529Swollman t = rn_newpair(v_arg, b, nodes); 40559529Swollman tt = t->rn_left; 40659529Swollman if ((cp[p->rn_offset] & p->rn_bmask) == 0) 40759529Swollman p->rn_left = t; 4081541Srgrimes else 40959529Swollman p->rn_right = t; 41059529Swollman x->rn_parent = t; 41159529Swollman t->rn_parent = p; /* frees x, p as temp vars below */ 41259529Swollman if ((cp[t->rn_offset] & t->rn_bmask) == 0) { 41359529Swollman t->rn_right = x; 4141541Srgrimes } else { 41559529Swollman t->rn_right = tt; 41659529Swollman t->rn_left = x; 4171541Srgrimes } 4181541Srgrimes#ifdef RN_DEBUG 4191541Srgrimes if (rn_debug) 4208152Spst log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); 4211541Srgrimes#endif 4221541Srgrimes } 4231541Srgrimes return (tt); 4241541Srgrimes} 4251541Srgrimes 4261541Srgrimesstruct radix_node * 4271541Srgrimesrn_addmask(n_arg, search, skip) 4281541Srgrimes int search, skip; 4291541Srgrimes void *n_arg; 4301541Srgrimes{ 4311541Srgrimes caddr_t netmask = (caddr_t)n_arg; 4321541Srgrimes register struct radix_node *x; 4331541Srgrimes register caddr_t cp, cplim; 4348152Spst register int b = 0, mlen, j; 4358152Spst int maskduplicated, m0, isnormal; 4368152Spst struct radix_node *saved_x; 4378152Spst static int last_zeroed = 0; 4381541Srgrimes 4398152Spst if ((mlen = *(u_char *)netmask) > max_keylen) 4408152Spst mlen = max_keylen; 4418152Spst if (skip == 0) 4428152Spst skip = 1; 4438152Spst if (mlen <= skip) 4448152Spst return (mask_rnhead->rnh_nodes); 4458152Spst if (skip > 1) 4468152Spst Bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 4478152Spst if ((m0 = mlen) > skip) 4488152Spst Bcopy(netmask + skip, addmask_key + skip, mlen - skip); 4498152Spst /* 4508152Spst * Trim trailing zeroes. 4518152Spst */ 4528152Spst for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) 4538152Spst cp--; 4548152Spst mlen = cp - addmask_key; 4558152Spst if (mlen <= skip) { 4568152Spst if (m0 >= last_zeroed) 4578152Spst last_zeroed = mlen; 4588152Spst return (mask_rnhead->rnh_nodes); 4591541Srgrimes } 4608152Spst if (m0 < last_zeroed) 4618152Spst Bzero(addmask_key + m0, last_zeroed - m0); 4628152Spst *addmask_key = last_zeroed = mlen; 4638152Spst x = rn_search(addmask_key, rn_masktop); 4648152Spst if (Bcmp(addmask_key, x->rn_key, mlen) != 0) 4658152Spst x = 0; 4668152Spst if (x || search) 4678152Spst return (x); 4681541Srgrimes R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); 4698152Spst if ((saved_x = x) == 0) 4701541Srgrimes return (0); 4711541Srgrimes Bzero(x, max_keylen + 2 * sizeof (*x)); 4728152Spst netmask = cp = (caddr_t)(x + 2); 4738152Spst Bcopy(addmask_key, cp, mlen); 4748152Spst x = rn_insert(cp, mask_rnhead, &maskduplicated, x); 4758152Spst if (maskduplicated) { 4768152Spst log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 4778152Spst Free(saved_x); 4788152Spst return (x); 4798152Spst } 4801541Srgrimes /* 4818152Spst * Calculate index of mask, and check for normalcy. 4821541Srgrimes */ 4838152Spst cplim = netmask + mlen; isnormal = 1; 4848152Spst for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) 4858152Spst cp++; 4861541Srgrimes if (cp != cplim) { 4878876Srgrimes for (j = 0x80; (j & *cp) != 0; j >>= 1) 4888152Spst b++; 4898152Spst if (*cp != normal_chars[b] || cp != (cplim - 1)) 4908152Spst isnormal = 0; 4911541Srgrimes } 4928152Spst b += (cp - netmask) << 3; 49359529Swollman x->rn_bit = -1 - b; 4948152Spst if (isnormal) 4958152Spst x->rn_flags |= RNF_NORMAL; 4961541Srgrimes return (x); 4971541Srgrimes} 4981541Srgrimes 4998152Spststatic int /* XXX: arbitrary ordering for non-contiguous masks */ 5008152Spstrn_lexobetter(m_arg, n_arg) 5018152Spst void *m_arg, *n_arg; 5028152Spst{ 5038152Spst register u_char *mp = m_arg, *np = n_arg, *lim; 5048152Spst 5058152Spst if (*mp > *np) 5068152Spst return 1; /* not really, but need to check longer one first */ 5078876Srgrimes if (*mp == *np) 5088152Spst for (lim = mp + *mp; mp < lim;) 5098152Spst if (*mp++ > *np++) 5108152Spst return 1; 5118152Spst return 0; 5128152Spst} 5138152Spst 5148152Spststatic struct radix_mask * 5158152Spstrn_new_radix_mask(tt, next) 5168152Spst register struct radix_node *tt; 5178152Spst register struct radix_mask *next; 5188152Spst{ 5198152Spst register struct radix_mask *m; 5208152Spst 5218152Spst MKGet(m); 5228152Spst if (m == 0) { 5238152Spst log(LOG_ERR, "Mask for route not entered\n"); 5248152Spst return (0); 5258152Spst } 5268152Spst Bzero(m, sizeof *m); 52759529Swollman m->rm_bit = tt->rn_bit; 5288152Spst m->rm_flags = tt->rn_flags; 5298152Spst if (tt->rn_flags & RNF_NORMAL) 5308152Spst m->rm_leaf = tt; 5318152Spst else 5328152Spst m->rm_mask = tt->rn_mask; 5338152Spst m->rm_mklist = next; 5348152Spst tt->rn_mklist = m; 5358152Spst return m; 5368152Spst} 5378152Spst 5381541Srgrimesstruct radix_node * 5391541Srgrimesrn_addroute(v_arg, n_arg, head, treenodes) 5401541Srgrimes void *v_arg, *n_arg; 5411541Srgrimes struct radix_node_head *head; 5421541Srgrimes struct radix_node treenodes[2]; 5431541Srgrimes{ 5441541Srgrimes caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 5451549Srgrimes register struct radix_node *t, *x = 0, *tt; 5461541Srgrimes struct radix_node *saved_tt, *top = head->rnh_treetop; 5478152Spst short b = 0, b_leaf = 0; 5488152Spst int keyduplicated; 5498152Spst caddr_t mmask; 5501541Srgrimes struct radix_mask *m, **mp; 5511541Srgrimes 5521541Srgrimes /* 5531541Srgrimes * In dealing with non-contiguous masks, there may be 5541541Srgrimes * many different routes which have the same mask. 5551541Srgrimes * We will find it useful to have a unique pointer to 5561541Srgrimes * the mask to speed avoiding duplicate references at 5571541Srgrimes * nodes and possibly save time in calculating indices. 5581541Srgrimes */ 5591541Srgrimes if (netmask) { 56059529Swollman if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0) 5618152Spst return (0); 56259529Swollman b_leaf = x->rn_bit; 56359529Swollman b = -1 - x->rn_bit; 5641541Srgrimes netmask = x->rn_key; 5651541Srgrimes } 5661541Srgrimes /* 5671541Srgrimes * Deal with duplicated keys: attach node to previous instance 5681541Srgrimes */ 5691541Srgrimes saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 5701541Srgrimes if (keyduplicated) { 5718152Spst for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 5721541Srgrimes if (tt->rn_mask == netmask) 5731541Srgrimes return (0); 5741541Srgrimes if (netmask == 0 || 5758152Spst (tt->rn_mask && 57659529Swollman ((b_leaf < tt->rn_bit) /* index(netmask) > node */ 57759529Swollman || rn_refines(netmask, tt->rn_mask) 57859529Swollman || rn_lexobetter(netmask, tt->rn_mask)))) 5791541Srgrimes break; 5808152Spst } 5811541Srgrimes /* 5821541Srgrimes * If the mask is not duplicated, we wouldn't 5831541Srgrimes * find it among possible duplicate key entries 5841541Srgrimes * anyway, so the above test doesn't hurt. 5851541Srgrimes * 5861541Srgrimes * We sort the masks for a duplicated key the same way as 5871541Srgrimes * in a masklist -- most specific to least specific. 5881541Srgrimes * This may require the unfortunate nuisance of relocating 5891541Srgrimes * the head of the list. 590108268Sru * 591108268Sru * We also reverse, or doubly link the list through the 592108268Sru * parent pointer. 5931541Srgrimes */ 5948152Spst if (tt == saved_tt) { 5951541Srgrimes struct radix_node *xx = x; 5961541Srgrimes /* link in at head of list */ 5971541Srgrimes (tt = treenodes)->rn_dupedkey = t; 5981541Srgrimes tt->rn_flags = t->rn_flags; 59959529Swollman tt->rn_parent = x = t->rn_parent; 60059529Swollman t->rn_parent = tt; /* parent */ 60159529Swollman if (x->rn_left == t) 60259529Swollman x->rn_left = tt; 60359529Swollman else 60459529Swollman x->rn_right = tt; 6051541Srgrimes saved_tt = tt; x = xx; 6061541Srgrimes } else { 6071541Srgrimes (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 6081541Srgrimes t->rn_dupedkey = tt; 60959529Swollman tt->rn_parent = t; /* parent */ 6108152Spst if (tt->rn_dupedkey) /* parent */ 61159529Swollman tt->rn_dupedkey->rn_parent = tt; /* parent */ 6121541Srgrimes } 6131541Srgrimes#ifdef RN_DEBUG 6141541Srgrimes t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 6151541Srgrimes tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 6161541Srgrimes#endif 6171541Srgrimes tt->rn_key = (caddr_t) v; 61859529Swollman tt->rn_bit = -1; 6198152Spst tt->rn_flags = RNF_ACTIVE; 6201541Srgrimes } 6211541Srgrimes /* 6221541Srgrimes * Put mask in tree. 6231541Srgrimes */ 6241541Srgrimes if (netmask) { 6251541Srgrimes tt->rn_mask = netmask; 62659529Swollman tt->rn_bit = x->rn_bit; 6278152Spst tt->rn_flags |= x->rn_flags & RNF_NORMAL; 6281541Srgrimes } 62959529Swollman t = saved_tt->rn_parent; 6308152Spst if (keyduplicated) 6318152Spst goto on2; 63259529Swollman b_leaf = -1 - t->rn_bit; 63359529Swollman if (t->rn_right == saved_tt) 63459529Swollman x = t->rn_left; 63559529Swollman else 63659529Swollman x = t->rn_right; 6371541Srgrimes /* Promote general routes from below */ 63859529Swollman if (x->rn_bit < 0) { 6398152Spst for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 64059529Swollman if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) { 6418152Spst *mp = m = rn_new_radix_mask(x, 0); 6428152Spst if (m) 6438152Spst mp = &m->rm_mklist; 6441541Srgrimes } 6451541Srgrimes } else if (x->rn_mklist) { 6461541Srgrimes /* 6471541Srgrimes * Skip over masks whose index is > that of new node 6481541Srgrimes */ 6498152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 65059529Swollman if (m->rm_bit >= b_leaf) 6511541Srgrimes break; 6521541Srgrimes t->rn_mklist = m; *mp = 0; 6531541Srgrimes } 6548152Spston2: 6551541Srgrimes /* Add new route to highest possible ancestor's list */ 65659529Swollman if ((netmask == 0) || (b > t->rn_bit )) 6571541Srgrimes return tt; /* can't lift at all */ 65859529Swollman b_leaf = tt->rn_bit; 6591541Srgrimes do { 6601541Srgrimes x = t; 66159529Swollman t = t->rn_parent; 66259529Swollman } while (b <= t->rn_bit && x != top); 6631541Srgrimes /* 6641541Srgrimes * Search through routes associated with node to 6651541Srgrimes * insert new route according to index. 6668152Spst * Need same criteria as when sorting dupedkeys to avoid 6678152Spst * double loop on deletion. 6681541Srgrimes */ 6698152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { 67059529Swollman if (m->rm_bit < b_leaf) 6711541Srgrimes continue; 67259529Swollman if (m->rm_bit > b_leaf) 6731541Srgrimes break; 6748152Spst if (m->rm_flags & RNF_NORMAL) { 6758152Spst mmask = m->rm_leaf->rn_mask; 6768152Spst if (tt->rn_flags & RNF_NORMAL) { 67759529Swollman log(LOG_ERR, 67895023Ssuz "Non-unique normal route, mask not entered\n"); 6798152Spst return tt; 6808152Spst } 6818152Spst } else 6828152Spst mmask = m->rm_mask; 6838152Spst if (mmask == netmask) { 6841541Srgrimes m->rm_refs++; 6851541Srgrimes tt->rn_mklist = m; 6861541Srgrimes return tt; 6871541Srgrimes } 68859529Swollman if (rn_refines(netmask, mmask) 68959529Swollman || rn_lexobetter(netmask, mmask)) 6901541Srgrimes break; 6911541Srgrimes } 6928152Spst *mp = rn_new_radix_mask(tt, *mp); 6931541Srgrimes return tt; 6941541Srgrimes} 6951541Srgrimes 69631390Sbdestruct radix_node * 6971541Srgrimesrn_delete(v_arg, netmask_arg, head) 6981541Srgrimes void *v_arg, *netmask_arg; 6991541Srgrimes struct radix_node_head *head; 7001541Srgrimes{ 7011541Srgrimes register struct radix_node *t, *p, *x, *tt; 7021541Srgrimes struct radix_mask *m, *saved_m, **mp; 7031541Srgrimes struct radix_node *dupedkey, *saved_tt, *top; 7041541Srgrimes caddr_t v, netmask; 7051541Srgrimes int b, head_off, vlen; 7061541Srgrimes 7071541Srgrimes v = v_arg; 7081541Srgrimes netmask = netmask_arg; 7091541Srgrimes x = head->rnh_treetop; 7101541Srgrimes tt = rn_search(v, x); 71159529Swollman head_off = x->rn_offset; 7121541Srgrimes vlen = *(u_char *)v; 7131541Srgrimes saved_tt = tt; 7141541Srgrimes top = x; 7151541Srgrimes if (tt == 0 || 7161541Srgrimes Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 7171541Srgrimes return (0); 7181541Srgrimes /* 7191541Srgrimes * Delete our route from mask lists. 7201541Srgrimes */ 7218152Spst if (netmask) { 7228152Spst if ((x = rn_addmask(netmask, 1, head_off)) == 0) 7238152Spst return (0); 7248152Spst netmask = x->rn_key; 7251541Srgrimes while (tt->rn_mask != netmask) 7261541Srgrimes if ((tt = tt->rn_dupedkey) == 0) 7271541Srgrimes return (0); 7281541Srgrimes } 7291541Srgrimes if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 7301541Srgrimes goto on1; 7318152Spst if (tt->rn_flags & RNF_NORMAL) { 7328152Spst if (m->rm_leaf != tt || m->rm_refs > 0) { 7338152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 7348152Spst return 0; /* dangling ref could cause disaster */ 7358152Spst } 7368876Srgrimes } else { 7378152Spst if (m->rm_mask != tt->rn_mask) { 7388152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 7398152Spst goto on1; 7408152Spst } 7418152Spst if (--m->rm_refs >= 0) 7428152Spst goto on1; 7431541Srgrimes } 74459529Swollman b = -1 - tt->rn_bit; 74559529Swollman t = saved_tt->rn_parent; 74659529Swollman if (b > t->rn_bit) 7471541Srgrimes goto on1; /* Wasn't lifted at all */ 7481541Srgrimes do { 7491541Srgrimes x = t; 75059529Swollman t = t->rn_parent; 75159529Swollman } while (b <= t->rn_bit && x != top); 7528152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 7531541Srgrimes if (m == saved_m) { 7541541Srgrimes *mp = m->rm_mklist; 7551541Srgrimes MKFree(m); 7561541Srgrimes break; 7571541Srgrimes } 7588152Spst if (m == 0) { 7598152Spst log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 7608152Spst if (tt->rn_flags & RNF_NORMAL) 7618152Spst return (0); /* Dangling ref to us */ 7628152Spst } 7631541Srgrimeson1: 7641541Srgrimes /* 7651541Srgrimes * Eliminate us from tree 7661541Srgrimes */ 7671541Srgrimes if (tt->rn_flags & RNF_ROOT) 7681541Srgrimes return (0); 7691541Srgrimes#ifdef RN_DEBUG 7701541Srgrimes /* Get us out of the creation list */ 7711541Srgrimes for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 7721541Srgrimes if (t) t->rn_ybro = tt->rn_ybro; 7731541Srgrimes#endif 77459529Swollman t = tt->rn_parent; 7758152Spst dupedkey = saved_tt->rn_dupedkey; 7761541Srgrimes if (dupedkey) { 7778152Spst /* 778108268Sru * Here, tt is the deletion target and 779108268Sru * saved_tt is the head of the dupekey chain. 7808152Spst */ 7811541Srgrimes if (tt == saved_tt) { 7828152Spst /* remove from head of chain */ 78359529Swollman x = dupedkey; x->rn_parent = t; 78459529Swollman if (t->rn_left == tt) 78559529Swollman t->rn_left = x; 78659529Swollman else 78759529Swollman t->rn_right = x; 7881541Srgrimes } else { 7898152Spst /* find node in front of tt on the chain */ 7901541Srgrimes for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 7911541Srgrimes p = p->rn_dupedkey; 7928152Spst if (p) { 7938152Spst p->rn_dupedkey = tt->rn_dupedkey; 79459529Swollman if (tt->rn_dupedkey) /* parent */ 79559529Swollman tt->rn_dupedkey->rn_parent = p; 79659529Swollman /* parent */ 7978152Spst } else log(LOG_ERR, "rn_delete: couldn't find us\n"); 7981541Srgrimes } 7991541Srgrimes t = tt + 1; 8001541Srgrimes if (t->rn_flags & RNF_ACTIVE) { 8011541Srgrimes#ifndef RN_DEBUG 80259529Swollman *++x = *t; 80359529Swollman p = t->rn_parent; 8041541Srgrimes#else 80559529Swollman b = t->rn_info; 80659529Swollman *++x = *t; 80759529Swollman t->rn_info = b; 80859529Swollman p = t->rn_parent; 8091541Srgrimes#endif 81059529Swollman if (p->rn_left == t) 81159529Swollman p->rn_left = x; 81259529Swollman else 81359529Swollman p->rn_right = x; 81459529Swollman x->rn_left->rn_parent = x; 81559529Swollman x->rn_right->rn_parent = x; 8161541Srgrimes } 8171541Srgrimes goto out; 8181541Srgrimes } 81959529Swollman if (t->rn_left == tt) 82059529Swollman x = t->rn_right; 82159529Swollman else 82259529Swollman x = t->rn_left; 82359529Swollman p = t->rn_parent; 82459529Swollman if (p->rn_right == t) 82559529Swollman p->rn_right = x; 82659529Swollman else 82759529Swollman p->rn_left = x; 82859529Swollman x->rn_parent = p; 8291541Srgrimes /* 8301541Srgrimes * Demote routes attached to us. 8311541Srgrimes */ 8321541Srgrimes if (t->rn_mklist) { 83359529Swollman if (x->rn_bit >= 0) { 8348152Spst for (mp = &x->rn_mklist; (m = *mp);) 8351541Srgrimes mp = &m->rm_mklist; 8361541Srgrimes *mp = t->rn_mklist; 8371541Srgrimes } else { 8388152Spst /* If there are any key,mask pairs in a sibling 8398152Spst duped-key chain, some subset will appear sorted 8408152Spst in the same order attached to our mklist */ 8418152Spst for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 8428152Spst if (m == x->rn_mklist) { 8438152Spst struct radix_mask *mm = m->rm_mklist; 8441541Srgrimes x->rn_mklist = 0; 8458152Spst if (--(m->rm_refs) < 0) 8468152Spst MKFree(m); 8478152Spst m = mm; 8488152Spst } 8498152Spst if (m) 85037560Sbde log(LOG_ERR, 85137560Sbde "rn_delete: Orphaned Mask %p at %p\n", 85237560Sbde (void *)m, (void *)x); 8531541Srgrimes } 8541541Srgrimes } 8551541Srgrimes /* 8561541Srgrimes * We may be holding an active internal node in the tree. 8571541Srgrimes */ 8581541Srgrimes x = tt + 1; 8591541Srgrimes if (t != x) { 8601541Srgrimes#ifndef RN_DEBUG 8611541Srgrimes *t = *x; 8621541Srgrimes#else 86359529Swollman b = t->rn_info; 86459529Swollman *t = *x; 86559529Swollman t->rn_info = b; 8661541Srgrimes#endif 86759529Swollman t->rn_left->rn_parent = t; 86859529Swollman t->rn_right->rn_parent = t; 86959529Swollman p = x->rn_parent; 87059529Swollman if (p->rn_left == x) 87159529Swollman p->rn_left = t; 87259529Swollman else 87359529Swollman p->rn_right = t; 8741541Srgrimes } 8751541Srgrimesout: 8761541Srgrimes tt->rn_flags &= ~RNF_ACTIVE; 8771541Srgrimes tt[1].rn_flags &= ~RNF_ACTIVE; 8781541Srgrimes return (tt); 8791541Srgrimes} 8801541Srgrimes 8817197Swollman/* 8827197Swollman * This is the same as rn_walktree() except for the parameters and the 8837197Swollman * exit. 8847197Swollman */ 88512820Sphkstatic int 8867197Swollmanrn_walktree_from(h, a, m, f, w) 8877197Swollman struct radix_node_head *h; 8887197Swollman void *a, *m; 88912579Sbde walktree_f_t *f; 8907197Swollman void *w; 8917197Swollman{ 8927197Swollman int error; 8937197Swollman struct radix_node *base, *next; 8947197Swollman u_char *xa = (u_char *)a; 8957197Swollman u_char *xm = (u_char *)m; 8967197Swollman register struct radix_node *rn, *last = 0 /* shut up gcc */; 8977197Swollman int stopping = 0; 8987197Swollman int lastb; 8997197Swollman 9007197Swollman /* 9017197Swollman * rn_search_m is sort-of-open-coded here. 9027197Swollman */ 9037279Swollman /* printf("about to search\n"); */ 90459529Swollman for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) { 9057197Swollman last = rn; 90659529Swollman /* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n", 90759529Swollman rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */ 90859529Swollman if (!(rn->rn_bmask & xm[rn->rn_offset])) { 9097197Swollman break; 9107279Swollman } 91159529Swollman if (rn->rn_bmask & xa[rn->rn_offset]) { 91259529Swollman rn = rn->rn_right; 9137197Swollman } else { 91459529Swollman rn = rn->rn_left; 9157197Swollman } 9167197Swollman } 9177279Swollman /* printf("done searching\n"); */ 9187197Swollman 9197197Swollman /* 9207197Swollman * Two cases: either we stepped off the end of our mask, 9217197Swollman * in which case last == rn, or we reached a leaf, in which 9227197Swollman * case we want to start from the last node we looked at. 9237197Swollman * Either way, last is the node we want to start from. 9247197Swollman */ 9257197Swollman rn = last; 92659529Swollman lastb = rn->rn_bit; 9277197Swollman 9287279Swollman /* printf("rn %p, lastb %d\n", rn, lastb);*/ 9297279Swollman 9307197Swollman /* 9317197Swollman * This gets complicated because we may delete the node 9327197Swollman * while applying the function f to it, so we need to calculate 9337197Swollman * the successor node in advance. 9347197Swollman */ 93559529Swollman while (rn->rn_bit >= 0) 93659529Swollman rn = rn->rn_left; 9377197Swollman 9387197Swollman while (!stopping) { 93959529Swollman /* printf("node %p (%d)\n", rn, rn->rn_bit); */ 9407197Swollman base = rn; 9417197Swollman /* If at right child go back up, otherwise, go right */ 94259529Swollman while (rn->rn_parent->rn_right == rn 94359529Swollman && !(rn->rn_flags & RNF_ROOT)) { 94459529Swollman rn = rn->rn_parent; 9457197Swollman 9468876Srgrimes /* if went up beyond last, stop */ 94759529Swollman if (rn->rn_bit < lastb) { 9487197Swollman stopping = 1; 9497279Swollman /* printf("up too far\n"); */ 9507197Swollman } 9517197Swollman } 9527197Swollman 9537197Swollman /* Find the next *leaf* since next node might vanish, too */ 95459529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 95559529Swollman rn = rn->rn_left; 9567197Swollman next = rn; 9577197Swollman /* Process leaves */ 9587197Swollman while ((rn = base) != 0) { 9597197Swollman base = rn->rn_dupedkey; 9607279Swollman /* printf("leaf %p\n", rn); */ 9618876Srgrimes if (!(rn->rn_flags & RNF_ROOT) 9627197Swollman && (error = (*f)(rn, w))) 9637197Swollman return (error); 9647197Swollman } 9657197Swollman rn = next; 9667279Swollman 9677279Swollman if (rn->rn_flags & RNF_ROOT) { 9687279Swollman /* printf("root, stopping"); */ 9697279Swollman stopping = 1; 9707279Swollman } 9717279Swollman 9727197Swollman } 9737197Swollman return 0; 9747197Swollman} 9757197Swollman 97612820Sphkstatic int 9771541Srgrimesrn_walktree(h, f, w) 9781541Srgrimes struct radix_node_head *h; 97912579Sbde walktree_f_t *f; 9801541Srgrimes void *w; 9811541Srgrimes{ 9821541Srgrimes int error; 9831541Srgrimes struct radix_node *base, *next; 9841541Srgrimes register struct radix_node *rn = h->rnh_treetop; 9851541Srgrimes /* 9861541Srgrimes * This gets complicated because we may delete the node 9871541Srgrimes * while applying the function f to it, so we need to calculate 9881541Srgrimes * the successor node in advance. 9891541Srgrimes */ 9901541Srgrimes /* First time through node, go left */ 99159529Swollman while (rn->rn_bit >= 0) 99259529Swollman rn = rn->rn_left; 9931541Srgrimes for (;;) { 9941541Srgrimes base = rn; 9951541Srgrimes /* If at right child go back up, otherwise, go right */ 99659529Swollman while (rn->rn_parent->rn_right == rn 99759529Swollman && (rn->rn_flags & RNF_ROOT) == 0) 99859529Swollman rn = rn->rn_parent; 9991541Srgrimes /* Find the next *leaf* since next node might vanish, too */ 100059529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 100159529Swollman rn = rn->rn_left; 10021541Srgrimes next = rn; 10031541Srgrimes /* Process leaves */ 10048152Spst while ((rn = base)) { 10051541Srgrimes base = rn->rn_dupedkey; 100659529Swollman if (!(rn->rn_flags & RNF_ROOT) 100759529Swollman && (error = (*f)(rn, w))) 10081541Srgrimes return (error); 10091541Srgrimes } 10101541Srgrimes rn = next; 10111541Srgrimes if (rn->rn_flags & RNF_ROOT) 10121541Srgrimes return (0); 10131541Srgrimes } 10141541Srgrimes /* NOTREACHED */ 10151541Srgrimes} 10161541Srgrimes 10171541Srgrimesint 10181541Srgrimesrn_inithead(head, off) 10191541Srgrimes void **head; 10201541Srgrimes int off; 10211541Srgrimes{ 10221541Srgrimes register struct radix_node_head *rnh; 10231541Srgrimes register struct radix_node *t, *tt, *ttt; 10241541Srgrimes if (*head) 10251541Srgrimes return (1); 10261541Srgrimes R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh)); 10271541Srgrimes if (rnh == 0) 10281541Srgrimes return (0); 10291541Srgrimes Bzero(rnh, sizeof (*rnh)); 1030108250Shsu RADIX_NODE_HEAD_LOCK_INIT(rnh); 10311541Srgrimes *head = rnh; 10321541Srgrimes t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 10331541Srgrimes ttt = rnh->rnh_nodes + 2; 103459529Swollman t->rn_right = ttt; 103559529Swollman t->rn_parent = t; 103659529Swollman tt = t->rn_left; 10371541Srgrimes tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 103859529Swollman tt->rn_bit = -1 - off; 10391541Srgrimes *ttt = *tt; 10401541Srgrimes ttt->rn_key = rn_ones; 10411541Srgrimes rnh->rnh_addaddr = rn_addroute; 10421541Srgrimes rnh->rnh_deladdr = rn_delete; 10431541Srgrimes rnh->rnh_matchaddr = rn_match; 10448152Spst rnh->rnh_lookup = rn_lookup; 10451541Srgrimes rnh->rnh_walktree = rn_walktree; 10467197Swollman rnh->rnh_walktree_from = rn_walktree_from; 10471541Srgrimes rnh->rnh_treetop = t; 10481541Srgrimes return (1); 10491541Srgrimes} 10501541Srgrimes 10511541Srgrimesvoid 10521541Srgrimesrn_init() 10531541Srgrimes{ 10541541Srgrimes char *cp, *cplim; 105555205Speter#ifdef _KERNEL 10561541Srgrimes struct domain *dom; 10571541Srgrimes 10581541Srgrimes for (dom = domains; dom; dom = dom->dom_next) 10591541Srgrimes if (dom->dom_maxrtkey > max_keylen) 10601541Srgrimes max_keylen = dom->dom_maxrtkey; 10611541Srgrimes#endif 10621541Srgrimes if (max_keylen == 0) { 10638152Spst log(LOG_ERR, 10648152Spst "rn_init: radix functions require max_keylen be set\n"); 10651541Srgrimes return; 10661541Srgrimes } 10671541Srgrimes R_Malloc(rn_zeros, char *, 3 * max_keylen); 10681541Srgrimes if (rn_zeros == NULL) 10691541Srgrimes panic("rn_init"); 10701541Srgrimes Bzero(rn_zeros, 3 * max_keylen); 10711541Srgrimes rn_ones = cp = rn_zeros + max_keylen; 10728152Spst addmask_key = cplim = rn_ones + max_keylen; 10731541Srgrimes while (cp < cplim) 10741541Srgrimes *cp++ = -1; 10751541Srgrimes if (rn_inithead((void **)&mask_rnhead, 0) == 0) 10761541Srgrimes panic("rn_init 2"); 10771541Srgrimes} 1078