radix.c revision 55205
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 * 338152Spst * @(#)radix.c 8.4 (Berkeley) 11/2/94 3450477Speter * $FreeBSD: head/sys/net/radix.c 55205 1999-12-29 04:46:21Z peter $ 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#define M_DONTWAIT M_NOWAIT 461541Srgrimes#include <sys/domain.h> 478152Spst#else 488152Spst#include <stdlib.h> 491541Srgrimes#endif 508152Spst#include <sys/syslog.h> 518152Spst#include <net/radix.h> 521541Srgrimes#endif 531541Srgrimes 5412820Sphkstatic int rn_walktree_from __P((struct radix_node_head *h, void *a, 5512579Sbde void *m, walktree_f_t *f, void *w)); 5612820Sphkstatic int rn_walktree __P((struct radix_node_head *, walktree_f_t *, void *)); 5712820Sphkstatic struct radix_node 5812820Sphk *rn_insert __P((void *, struct radix_node_head *, int *, 5912820Sphk struct radix_node [2])), 6012820Sphk *rn_newpair __P((void *, int, struct radix_node[2])), 6112820Sphk *rn_search __P((void *, struct radix_node *)), 6212820Sphk *rn_search_m __P((void *, struct radix_node *, void *)); 6312579Sbde 6412820Sphkstatic int max_keylen; 6512820Sphkstatic struct radix_mask *rn_mkfreelist; 6612820Sphkstatic struct radix_node_head *mask_rnhead; 678152Spststatic char *addmask_key; 688152Spststatic char normal_chars[] = {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1}; 691541Srgrimesstatic char *rn_zeros, *rn_ones; 701541Srgrimes 711541Srgrimes#define rn_masktop (mask_rnhead->rnh_treetop) 721541Srgrimes#undef Bcmp 731541Srgrimes#define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l)) 7412579Sbde 7512579Sbdestatic int rn_lexobetter __P((void *m_arg, void *n_arg)); 7612579Sbdestatic struct radix_mask * 7712579Sbde rn_new_radix_mask __P((struct radix_node *tt, 7812579Sbde struct radix_mask *next)); 7912579Sbdestatic int rn_satsifies_leaf __P((char *trial, struct radix_node *leaf, 8012579Sbde int skip)); 8112579Sbde 821541Srgrimes/* 831541Srgrimes * The data structure for the keys is a radix tree with one way 841541Srgrimes * branching removed. The index rn_b at an internal node n represents a bit 851541Srgrimes * position to be tested. The tree is arranged so that all descendants 861541Srgrimes * of a node n have keys whose bits all agree up to position rn_b - 1. 871541Srgrimes * (We say the index of n is rn_b.) 881541Srgrimes * 891541Srgrimes * There is at least one descendant which has a one bit at position rn_b, 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. 991541Srgrimes * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b, 1001541Srgrimes * and m is a normal mask, then the route applies to every descendant of n. 1011541Srgrimes * If the index(m) < rn_b, 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 1241541Srgrimes for (x = head, v = v_arg; x->rn_b >= 0;) { 1251541Srgrimes if (x->rn_bmask & v[x->rn_off]) 1261541Srgrimes x = x->rn_r; 1271541Srgrimes else 1281541Srgrimes x = x->rn_l; 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 1411541Srgrimes for (x = head; x->rn_b >= 0;) { 1421541Srgrimes if ((x->rn_bmask & m[x->rn_off]) && 1431541Srgrimes (x->rn_bmask & v[x->rn_off])) 1441541Srgrimes x = x->rn_r; 1451541Srgrimes else 1461541Srgrimes x = x->rn_l; 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) { 1878152Spst if ((x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 0) 1888152Spst return (0); 1898152Spst netmask = x->rn_key; 1908152Spst } 1918152Spst x = rn_match(v_arg, head); 1928152Spst if (x && netmask) { 1938152Spst while (x && x->rn_mask != netmask) 1948152Spst x = x->rn_dupedkey; 1958152Spst } 1968152Spst return x; 1978152Spst} 1988152Spst 1998152Spststatic int 2008152Spstrn_satsifies_leaf(trial, leaf, skip) 2018152Spst char *trial; 2028152Spst register struct radix_node *leaf; 2038152Spst int skip; 2048152Spst{ 2058152Spst register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 2068152Spst char *cplim; 2078152Spst int length = min(*(u_char *)cp, *(u_char *)cp2); 2088152Spst 2098152Spst if (cp3 == 0) 2108152Spst cp3 = rn_ones; 2118152Spst else 2128152Spst length = min(length, *(u_char *)cp3); 2138152Spst cplim = cp + length; cp3 += skip; cp2 += skip; 2148152Spst for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 2158152Spst if ((*cp ^ *cp2) & *cp3) 2168152Spst return 0; 2178152Spst return 1; 2188152Spst} 2198152Spst 2201541Srgrimesstruct radix_node * 2211541Srgrimesrn_match(v_arg, head) 2221541Srgrimes void *v_arg; 2231541Srgrimes struct radix_node_head *head; 2241541Srgrimes{ 2251541Srgrimes caddr_t v = v_arg; 2261541Srgrimes register struct radix_node *t = head->rnh_treetop, *x; 2278152Spst register caddr_t cp = v, cp2; 2288152Spst caddr_t cplim; 2291541Srgrimes struct radix_node *saved_t, *top = t; 2301541Srgrimes int off = t->rn_off, vlen = *(u_char *)cp, matched_off; 2318152Spst register int test, b, rn_b; 2321541Srgrimes 2331541Srgrimes /* 2341541Srgrimes * Open code rn_search(v, top) to avoid overhead of extra 2351541Srgrimes * subroutine call. 2361541Srgrimes */ 2371541Srgrimes for (; t->rn_b >= 0; ) { 2381541Srgrimes if (t->rn_bmask & cp[t->rn_off]) 2391541Srgrimes t = t->rn_r; 2401541Srgrimes else 2411541Srgrimes t = t->rn_l; 2421541Srgrimes } 2431541Srgrimes /* 2441541Srgrimes * See if we match exactly as a host destination 2458152Spst * or at least learn how many bits match, for normal mask finesse. 2468152Spst * 2478152Spst * It doesn't hurt us to limit how many bytes to check 2488152Spst * to the length of the mask, since if it matches we had a genuine 2498152Spst * match and the leaf we have is the most specific one anyway; 2508152Spst * if it didn't match with a shorter length it would fail 2518152Spst * with a long one. This wins big for class B&C netmasks which 2528152Spst * are probably the most common case... 2531541Srgrimes */ 2548152Spst if (t->rn_mask) 2558152Spst vlen = *(u_char *)t->rn_mask; 2561541Srgrimes cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 2571541Srgrimes for (; cp < cplim; cp++, cp2++) 2581541Srgrimes if (*cp != *cp2) 2591541Srgrimes goto on1; 2601541Srgrimes /* 2611541Srgrimes * This extra grot is in case we are explicitly asked 2621541Srgrimes * to look up the default. Ugh! 26348215Spb * 26448215Spb * Never return the root node itself, it seems to cause a 26548215Spb * lot of confusion. 2661541Srgrimes */ 26748215Spb if (t->rn_flags & RNF_ROOT) 2681541Srgrimes t = t->rn_dupedkey; 2691541Srgrimes return t; 2701541Srgrimeson1: 2718152Spst test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 2728152Spst for (b = 7; (test >>= 1) > 0;) 2738152Spst b--; 2741541Srgrimes matched_off = cp - v; 2758152Spst b += matched_off << 3; 2768152Spst rn_b = -1 - b; 2778152Spst /* 2788152Spst * If there is a host route in a duped-key chain, it will be first. 2798152Spst */ 2808152Spst if ((saved_t = t)->rn_mask == 0) 2818152Spst t = t->rn_dupedkey; 2828152Spst for (; t; t = t->rn_dupedkey) 2831541Srgrimes /* 2848152Spst * Even if we don't match exactly as a host, 2851541Srgrimes * we may match if the leaf we wound up at is 2861541Srgrimes * a route to a net. 2871541Srgrimes */ 2888152Spst if (t->rn_flags & RNF_NORMAL) { 2898152Spst if (rn_b <= t->rn_b) 2908152Spst return t; 2918152Spst } else if (rn_satsifies_leaf(v, t, matched_off)) 2928152Spst return t; 2931541Srgrimes t = saved_t; 2941541Srgrimes /* start searching up the tree */ 2951541Srgrimes do { 2961541Srgrimes register struct radix_mask *m; 2971541Srgrimes t = t->rn_p; 2983443Sphk m = t->rn_mklist; 2993443Sphk if (m) { 3001541Srgrimes /* 3018152Spst * If non-contiguous masks ever become important 3028152Spst * we can restore the masking and open coding of 3038152Spst * the search and satisfaction test and put the 3048152Spst * calculation of "off" back before the "do". 3051541Srgrimes */ 3061541Srgrimes do { 3078152Spst if (m->rm_flags & RNF_NORMAL) { 3088152Spst if (rn_b <= m->rm_b) 3098152Spst return (m->rm_leaf); 3108152Spst } else { 3118152Spst off = min(t->rn_off, matched_off); 3128152Spst x = rn_search_m(v, t, m->rm_mask); 3138152Spst while (x && x->rn_mask != m->rm_mask) 3148152Spst x = x->rn_dupedkey; 3158152Spst if (x && rn_satsifies_leaf(v, x, off)) 3168152Spst return x; 3178152Spst } 3188152Spst m = m->rm_mklist; 3198152Spst } while (m); 3201541Srgrimes } 3211541Srgrimes } while (t != top); 3221541Srgrimes return 0; 32331390Sbde} 3248876Srgrimes 3251541Srgrimes#ifdef RN_DEBUG 3261541Srgrimesint rn_nodenum; 3271541Srgrimesstruct radix_node *rn_clist; 3281541Srgrimesint rn_saveinfo; 3291541Srgrimesint rn_debug = 1; 3301541Srgrimes#endif 3311541Srgrimes 33212820Sphkstatic struct radix_node * 3331541Srgrimesrn_newpair(v, b, nodes) 3341541Srgrimes void *v; 3351541Srgrimes int b; 3361541Srgrimes struct radix_node nodes[2]; 3371541Srgrimes{ 3381541Srgrimes register struct radix_node *tt = nodes, *t = tt + 1; 3391541Srgrimes t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7); 3401541Srgrimes t->rn_l = tt; t->rn_off = b >> 3; 3411541Srgrimes tt->rn_b = -1; tt->rn_key = (caddr_t)v; tt->rn_p = t; 3421541Srgrimes tt->rn_flags = t->rn_flags = RNF_ACTIVE; 3431541Srgrimes#ifdef RN_DEBUG 3441541Srgrimes tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 3451541Srgrimes tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 3461541Srgrimes#endif 3471541Srgrimes return t; 3481541Srgrimes} 3491541Srgrimes 35012820Sphkstatic struct radix_node * 3511541Srgrimesrn_insert(v_arg, head, dupentry, nodes) 3521541Srgrimes void *v_arg; 3531541Srgrimes struct radix_node_head *head; 3541541Srgrimes int *dupentry; 3551541Srgrimes struct radix_node nodes[2]; 3561541Srgrimes{ 3571541Srgrimes caddr_t v = v_arg; 3581541Srgrimes struct radix_node *top = head->rnh_treetop; 3591541Srgrimes int head_off = top->rn_off, vlen = (int)*((u_char *)v); 3601541Srgrimes register struct radix_node *t = rn_search(v_arg, top); 3611541Srgrimes register caddr_t cp = v + head_off; 3621541Srgrimes register int b; 3631541Srgrimes struct radix_node *tt; 3641541Srgrimes /* 3658152Spst * Find first bit at which v and t->rn_key differ 3661541Srgrimes */ 3671541Srgrimes { 3681541Srgrimes register caddr_t cp2 = t->rn_key + head_off; 3691541Srgrimes register int cmp_res; 3701541Srgrimes caddr_t cplim = v + vlen; 3711541Srgrimes 3721541Srgrimes while (cp < cplim) 3731541Srgrimes if (*cp2++ != *cp++) 3741541Srgrimes goto on1; 3751541Srgrimes *dupentry = 1; 3761541Srgrimes return t; 3771541Srgrimeson1: 3781541Srgrimes *dupentry = 0; 3791541Srgrimes cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 3801541Srgrimes for (b = (cp - v) << 3; cmp_res; b--) 3811541Srgrimes cmp_res >>= 1; 3821541Srgrimes } 3831541Srgrimes { 3841541Srgrimes register struct radix_node *p, *x = top; 3851541Srgrimes cp = v; 3861541Srgrimes do { 3871541Srgrimes p = x; 3888876Srgrimes if (cp[x->rn_off] & x->rn_bmask) 3891541Srgrimes x = x->rn_r; 3901541Srgrimes else x = x->rn_l; 3911541Srgrimes } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */ 3921541Srgrimes#ifdef RN_DEBUG 3931541Srgrimes if (rn_debug) 3948152Spst log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); 3951541Srgrimes#endif 3961541Srgrimes t = rn_newpair(v_arg, b, nodes); tt = t->rn_l; 3971541Srgrimes if ((cp[p->rn_off] & p->rn_bmask) == 0) 3981541Srgrimes p->rn_l = t; 3991541Srgrimes else 4001541Srgrimes p->rn_r = t; 4011541Srgrimes x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */ 4021541Srgrimes if ((cp[t->rn_off] & t->rn_bmask) == 0) { 4031541Srgrimes t->rn_r = x; 4041541Srgrimes } else { 4051541Srgrimes t->rn_r = tt; t->rn_l = x; 4061541Srgrimes } 4071541Srgrimes#ifdef RN_DEBUG 4081541Srgrimes if (rn_debug) 4098152Spst log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); 4101541Srgrimes#endif 4111541Srgrimes } 4121541Srgrimes return (tt); 4131541Srgrimes} 4141541Srgrimes 4151541Srgrimesstruct radix_node * 4161541Srgrimesrn_addmask(n_arg, search, skip) 4171541Srgrimes int search, skip; 4181541Srgrimes void *n_arg; 4191541Srgrimes{ 4201541Srgrimes caddr_t netmask = (caddr_t)n_arg; 4211541Srgrimes register struct radix_node *x; 4221541Srgrimes register caddr_t cp, cplim; 4238152Spst register int b = 0, mlen, j; 4248152Spst int maskduplicated, m0, isnormal; 4258152Spst struct radix_node *saved_x; 4268152Spst static int last_zeroed = 0; 4271541Srgrimes 4288152Spst if ((mlen = *(u_char *)netmask) > max_keylen) 4298152Spst mlen = max_keylen; 4308152Spst if (skip == 0) 4318152Spst skip = 1; 4328152Spst if (mlen <= skip) 4338152Spst return (mask_rnhead->rnh_nodes); 4348152Spst if (skip > 1) 4358152Spst Bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 4368152Spst if ((m0 = mlen) > skip) 4378152Spst Bcopy(netmask + skip, addmask_key + skip, mlen - skip); 4388152Spst /* 4398152Spst * Trim trailing zeroes. 4408152Spst */ 4418152Spst for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) 4428152Spst cp--; 4438152Spst mlen = cp - addmask_key; 4448152Spst if (mlen <= skip) { 4458152Spst if (m0 >= last_zeroed) 4468152Spst last_zeroed = mlen; 4478152Spst return (mask_rnhead->rnh_nodes); 4481541Srgrimes } 4498152Spst if (m0 < last_zeroed) 4508152Spst Bzero(addmask_key + m0, last_zeroed - m0); 4518152Spst *addmask_key = last_zeroed = mlen; 4528152Spst x = rn_search(addmask_key, rn_masktop); 4538152Spst if (Bcmp(addmask_key, x->rn_key, mlen) != 0) 4548152Spst x = 0; 4558152Spst if (x || search) 4568152Spst return (x); 4571541Srgrimes R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); 4588152Spst if ((saved_x = x) == 0) 4591541Srgrimes return (0); 4601541Srgrimes Bzero(x, max_keylen + 2 * sizeof (*x)); 4618152Spst netmask = cp = (caddr_t)(x + 2); 4628152Spst Bcopy(addmask_key, cp, mlen); 4638152Spst x = rn_insert(cp, mask_rnhead, &maskduplicated, x); 4648152Spst if (maskduplicated) { 4658152Spst log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 4668152Spst Free(saved_x); 4678152Spst return (x); 4688152Spst } 4691541Srgrimes /* 4708152Spst * Calculate index of mask, and check for normalcy. 4711541Srgrimes */ 4728152Spst cplim = netmask + mlen; isnormal = 1; 4738152Spst for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) 4748152Spst cp++; 4751541Srgrimes if (cp != cplim) { 4768876Srgrimes for (j = 0x80; (j & *cp) != 0; j >>= 1) 4778152Spst b++; 4788152Spst if (*cp != normal_chars[b] || cp != (cplim - 1)) 4798152Spst isnormal = 0; 4801541Srgrimes } 4818152Spst b += (cp - netmask) << 3; 4821541Srgrimes x->rn_b = -1 - b; 4838152Spst if (isnormal) 4848152Spst x->rn_flags |= RNF_NORMAL; 4851541Srgrimes return (x); 4861541Srgrimes} 4871541Srgrimes 4888152Spststatic int /* XXX: arbitrary ordering for non-contiguous masks */ 4898152Spstrn_lexobetter(m_arg, n_arg) 4908152Spst void *m_arg, *n_arg; 4918152Spst{ 4928152Spst register u_char *mp = m_arg, *np = n_arg, *lim; 4938152Spst 4948152Spst if (*mp > *np) 4958152Spst return 1; /* not really, but need to check longer one first */ 4968876Srgrimes if (*mp == *np) 4978152Spst for (lim = mp + *mp; mp < lim;) 4988152Spst if (*mp++ > *np++) 4998152Spst return 1; 5008152Spst return 0; 5018152Spst} 5028152Spst 5038152Spststatic struct radix_mask * 5048152Spstrn_new_radix_mask(tt, next) 5058152Spst register struct radix_node *tt; 5068152Spst register struct radix_mask *next; 5078152Spst{ 5088152Spst register struct radix_mask *m; 5098152Spst 5108152Spst MKGet(m); 5118152Spst if (m == 0) { 5128152Spst log(LOG_ERR, "Mask for route not entered\n"); 5138152Spst return (0); 5148152Spst } 5158152Spst Bzero(m, sizeof *m); 5168152Spst m->rm_b = tt->rn_b; 5178152Spst m->rm_flags = tt->rn_flags; 5188152Spst if (tt->rn_flags & RNF_NORMAL) 5198152Spst m->rm_leaf = tt; 5208152Spst else 5218152Spst m->rm_mask = tt->rn_mask; 5228152Spst m->rm_mklist = next; 5238152Spst tt->rn_mklist = m; 5248152Spst return m; 5258152Spst} 5268152Spst 5271541Srgrimesstruct radix_node * 5281541Srgrimesrn_addroute(v_arg, n_arg, head, treenodes) 5291541Srgrimes void *v_arg, *n_arg; 5301541Srgrimes struct radix_node_head *head; 5311541Srgrimes struct radix_node treenodes[2]; 5321541Srgrimes{ 5331541Srgrimes caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 5341549Srgrimes register struct radix_node *t, *x = 0, *tt; 5351541Srgrimes struct radix_node *saved_tt, *top = head->rnh_treetop; 5368152Spst short b = 0, b_leaf = 0; 5378152Spst int keyduplicated; 5388152Spst caddr_t mmask; 5391541Srgrimes struct radix_mask *m, **mp; 5401541Srgrimes 5411541Srgrimes /* 5421541Srgrimes * In dealing with non-contiguous masks, there may be 5431541Srgrimes * many different routes which have the same mask. 5441541Srgrimes * We will find it useful to have a unique pointer to 5451541Srgrimes * the mask to speed avoiding duplicate references at 5461541Srgrimes * nodes and possibly save time in calculating indices. 5471541Srgrimes */ 5481541Srgrimes if (netmask) { 5498152Spst if ((x = rn_addmask(netmask, 0, top->rn_off)) == 0) 5508152Spst return (0); 5518152Spst b_leaf = x->rn_b; 5528152Spst b = -1 - x->rn_b; 5531541Srgrimes netmask = x->rn_key; 5541541Srgrimes } 5551541Srgrimes /* 5561541Srgrimes * Deal with duplicated keys: attach node to previous instance 5571541Srgrimes */ 5581541Srgrimes saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 5591541Srgrimes if (keyduplicated) { 5608152Spst for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 5611541Srgrimes if (tt->rn_mask == netmask) 5621541Srgrimes return (0); 5631541Srgrimes if (netmask == 0 || 5648152Spst (tt->rn_mask && 5658152Spst ((b_leaf < tt->rn_b) || /* index(netmask) > node */ 5668152Spst rn_refines(netmask, tt->rn_mask) || 5678152Spst rn_lexobetter(netmask, tt->rn_mask)))) 5681541Srgrimes break; 5698152Spst } 5701541Srgrimes /* 5711541Srgrimes * If the mask is not duplicated, we wouldn't 5721541Srgrimes * find it among possible duplicate key entries 5731541Srgrimes * anyway, so the above test doesn't hurt. 5741541Srgrimes * 5751541Srgrimes * We sort the masks for a duplicated key the same way as 5761541Srgrimes * in a masklist -- most specific to least specific. 5771541Srgrimes * This may require the unfortunate nuisance of relocating 5781541Srgrimes * the head of the list. 5791541Srgrimes */ 5808152Spst if (tt == saved_tt) { 5811541Srgrimes struct radix_node *xx = x; 5821541Srgrimes /* link in at head of list */ 5831541Srgrimes (tt = treenodes)->rn_dupedkey = t; 5841541Srgrimes tt->rn_flags = t->rn_flags; 5851541Srgrimes tt->rn_p = x = t->rn_p; 5868152Spst t->rn_p = tt; /* parent */ 5871541Srgrimes if (x->rn_l == t) x->rn_l = tt; else x->rn_r = tt; 5881541Srgrimes saved_tt = tt; x = xx; 5891541Srgrimes } else { 5901541Srgrimes (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 5911541Srgrimes t->rn_dupedkey = tt; 5928152Spst tt->rn_p = t; /* parent */ 5938152Spst if (tt->rn_dupedkey) /* parent */ 5948152Spst tt->rn_dupedkey->rn_p = tt; /* parent */ 5951541Srgrimes } 5961541Srgrimes#ifdef RN_DEBUG 5971541Srgrimes t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 5981541Srgrimes tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 5991541Srgrimes#endif 6001541Srgrimes tt->rn_key = (caddr_t) v; 6011541Srgrimes tt->rn_b = -1; 6028152Spst tt->rn_flags = RNF_ACTIVE; 6031541Srgrimes } 6041541Srgrimes /* 6051541Srgrimes * Put mask in tree. 6061541Srgrimes */ 6071541Srgrimes if (netmask) { 6081541Srgrimes tt->rn_mask = netmask; 6091541Srgrimes tt->rn_b = x->rn_b; 6108152Spst tt->rn_flags |= x->rn_flags & RNF_NORMAL; 6111541Srgrimes } 6121541Srgrimes t = saved_tt->rn_p; 6138152Spst if (keyduplicated) 6148152Spst goto on2; 6151541Srgrimes b_leaf = -1 - t->rn_b; 6161541Srgrimes if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r; 6171541Srgrimes /* Promote general routes from below */ 6188876Srgrimes if (x->rn_b < 0) { 6198152Spst for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 6201541Srgrimes if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) { 6218152Spst *mp = m = rn_new_radix_mask(x, 0); 6228152Spst if (m) 6238152Spst mp = &m->rm_mklist; 6241541Srgrimes } 6251541Srgrimes } else if (x->rn_mklist) { 6261541Srgrimes /* 6271541Srgrimes * Skip over masks whose index is > that of new node 6281541Srgrimes */ 6298152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 6301541Srgrimes if (m->rm_b >= b_leaf) 6311541Srgrimes break; 6321541Srgrimes t->rn_mklist = m; *mp = 0; 6331541Srgrimes } 6348152Spston2: 6351541Srgrimes /* Add new route to highest possible ancestor's list */ 6361541Srgrimes if ((netmask == 0) || (b > t->rn_b )) 6371541Srgrimes return tt; /* can't lift at all */ 6381541Srgrimes b_leaf = tt->rn_b; 6391541Srgrimes do { 6401541Srgrimes x = t; 6411541Srgrimes t = t->rn_p; 6421541Srgrimes } while (b <= t->rn_b && x != top); 6431541Srgrimes /* 6441541Srgrimes * Search through routes associated with node to 6451541Srgrimes * insert new route according to index. 6468152Spst * Need same criteria as when sorting dupedkeys to avoid 6478152Spst * double loop on deletion. 6481541Srgrimes */ 6498152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { 6501541Srgrimes if (m->rm_b < b_leaf) 6511541Srgrimes continue; 6521541Srgrimes if (m->rm_b > b_leaf) 6531541Srgrimes break; 6548152Spst if (m->rm_flags & RNF_NORMAL) { 6558152Spst mmask = m->rm_leaf->rn_mask; 6568152Spst if (tt->rn_flags & RNF_NORMAL) { 6578152Spst log(LOG_ERR, 6588152Spst "Non-unique normal route, mask not entered"); 6598152Spst return tt; 6608152Spst } 6618152Spst } else 6628152Spst mmask = m->rm_mask; 6638152Spst if (mmask == netmask) { 6641541Srgrimes m->rm_refs++; 6651541Srgrimes tt->rn_mklist = m; 6661541Srgrimes return tt; 6671541Srgrimes } 6688152Spst if (rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask)) 6691541Srgrimes break; 6701541Srgrimes } 6718152Spst *mp = rn_new_radix_mask(tt, *mp); 6721541Srgrimes return tt; 6731541Srgrimes} 6741541Srgrimes 67531390Sbdestruct radix_node * 6761541Srgrimesrn_delete(v_arg, netmask_arg, head) 6771541Srgrimes void *v_arg, *netmask_arg; 6781541Srgrimes struct radix_node_head *head; 6791541Srgrimes{ 6801541Srgrimes register struct radix_node *t, *p, *x, *tt; 6811541Srgrimes struct radix_mask *m, *saved_m, **mp; 6821541Srgrimes struct radix_node *dupedkey, *saved_tt, *top; 6831541Srgrimes caddr_t v, netmask; 6841541Srgrimes int b, head_off, vlen; 6851541Srgrimes 6861541Srgrimes v = v_arg; 6871541Srgrimes netmask = netmask_arg; 6881541Srgrimes x = head->rnh_treetop; 6891541Srgrimes tt = rn_search(v, x); 6901541Srgrimes head_off = x->rn_off; 6911541Srgrimes vlen = *(u_char *)v; 6921541Srgrimes saved_tt = tt; 6931541Srgrimes top = x; 6941541Srgrimes if (tt == 0 || 6951541Srgrimes Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 6961541Srgrimes return (0); 6971541Srgrimes /* 6981541Srgrimes * Delete our route from mask lists. 6991541Srgrimes */ 7008152Spst if (netmask) { 7018152Spst if ((x = rn_addmask(netmask, 1, head_off)) == 0) 7028152Spst return (0); 7038152Spst netmask = x->rn_key; 7041541Srgrimes while (tt->rn_mask != netmask) 7051541Srgrimes if ((tt = tt->rn_dupedkey) == 0) 7061541Srgrimes return (0); 7071541Srgrimes } 7081541Srgrimes if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 7091541Srgrimes goto on1; 7108152Spst if (tt->rn_flags & RNF_NORMAL) { 7118152Spst if (m->rm_leaf != tt || m->rm_refs > 0) { 7128152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 7138152Spst return 0; /* dangling ref could cause disaster */ 7148152Spst } 7158876Srgrimes } else { 7168152Spst if (m->rm_mask != tt->rn_mask) { 7178152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 7188152Spst goto on1; 7198152Spst } 7208152Spst if (--m->rm_refs >= 0) 7218152Spst goto on1; 7221541Srgrimes } 7231541Srgrimes b = -1 - tt->rn_b; 7241541Srgrimes t = saved_tt->rn_p; 7251541Srgrimes if (b > t->rn_b) 7261541Srgrimes goto on1; /* Wasn't lifted at all */ 7271541Srgrimes do { 7281541Srgrimes x = t; 7291541Srgrimes t = t->rn_p; 7301541Srgrimes } while (b <= t->rn_b && x != top); 7318152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 7321541Srgrimes if (m == saved_m) { 7331541Srgrimes *mp = m->rm_mklist; 7341541Srgrimes MKFree(m); 7351541Srgrimes break; 7361541Srgrimes } 7378152Spst if (m == 0) { 7388152Spst log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 7398152Spst if (tt->rn_flags & RNF_NORMAL) 7408152Spst return (0); /* Dangling ref to us */ 7418152Spst } 7421541Srgrimeson1: 7431541Srgrimes /* 7441541Srgrimes * Eliminate us from tree 7451541Srgrimes */ 7461541Srgrimes if (tt->rn_flags & RNF_ROOT) 7471541Srgrimes return (0); 7481541Srgrimes#ifdef RN_DEBUG 7491541Srgrimes /* Get us out of the creation list */ 7501541Srgrimes for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 7511541Srgrimes if (t) t->rn_ybro = tt->rn_ybro; 7521541Srgrimes#endif 7531541Srgrimes t = tt->rn_p; 7548152Spst dupedkey = saved_tt->rn_dupedkey; 7551541Srgrimes if (dupedkey) { 7568152Spst /* 7578152Spst * at this point, tt is the deletion target and saved_tt 7588152Spst * is the head of the dupekey chain 7598152Spst */ 7601541Srgrimes if (tt == saved_tt) { 7618152Spst /* remove from head of chain */ 7621541Srgrimes x = dupedkey; x->rn_p = t; 7631541Srgrimes if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x; 7641541Srgrimes } else { 7658152Spst /* find node in front of tt on the chain */ 7661541Srgrimes for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 7671541Srgrimes p = p->rn_dupedkey; 7688152Spst if (p) { 7698152Spst p->rn_dupedkey = tt->rn_dupedkey; 7708152Spst if (tt->rn_dupedkey) /* parent */ 7718152Spst tt->rn_dupedkey->rn_p = p; /* parent */ 7728152Spst } else log(LOG_ERR, "rn_delete: couldn't find us\n"); 7731541Srgrimes } 7741541Srgrimes t = tt + 1; 7751541Srgrimes if (t->rn_flags & RNF_ACTIVE) { 7761541Srgrimes#ifndef RN_DEBUG 7771541Srgrimes *++x = *t; p = t->rn_p; 7781541Srgrimes#else 7791541Srgrimes b = t->rn_info; *++x = *t; t->rn_info = b; p = t->rn_p; 7801541Srgrimes#endif 7811541Srgrimes if (p->rn_l == t) p->rn_l = x; else p->rn_r = x; 7821541Srgrimes x->rn_l->rn_p = x; x->rn_r->rn_p = x; 7831541Srgrimes } 7841541Srgrimes goto out; 7851541Srgrimes } 7861541Srgrimes if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l; 7871541Srgrimes p = t->rn_p; 7881541Srgrimes if (p->rn_r == t) p->rn_r = x; else p->rn_l = x; 7891541Srgrimes x->rn_p = p; 7901541Srgrimes /* 7911541Srgrimes * Demote routes attached to us. 7921541Srgrimes */ 7931541Srgrimes if (t->rn_mklist) { 7941541Srgrimes if (x->rn_b >= 0) { 7958152Spst for (mp = &x->rn_mklist; (m = *mp);) 7961541Srgrimes mp = &m->rm_mklist; 7971541Srgrimes *mp = t->rn_mklist; 7981541Srgrimes } else { 7998152Spst /* If there are any key,mask pairs in a sibling 8008152Spst duped-key chain, some subset will appear sorted 8018152Spst in the same order attached to our mklist */ 8028152Spst for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 8038152Spst if (m == x->rn_mklist) { 8048152Spst struct radix_mask *mm = m->rm_mklist; 8051541Srgrimes x->rn_mklist = 0; 8068152Spst if (--(m->rm_refs) < 0) 8078152Spst MKFree(m); 8088152Spst m = mm; 8098152Spst } 8108152Spst if (m) 81137560Sbde log(LOG_ERR, 81237560Sbde "rn_delete: Orphaned Mask %p at %p\n", 81337560Sbde (void *)m, (void *)x); 8141541Srgrimes } 8151541Srgrimes } 8161541Srgrimes /* 8171541Srgrimes * We may be holding an active internal node in the tree. 8181541Srgrimes */ 8191541Srgrimes x = tt + 1; 8201541Srgrimes if (t != x) { 8211541Srgrimes#ifndef RN_DEBUG 8221541Srgrimes *t = *x; 8231541Srgrimes#else 8241541Srgrimes b = t->rn_info; *t = *x; t->rn_info = b; 8251541Srgrimes#endif 8261541Srgrimes t->rn_l->rn_p = t; t->rn_r->rn_p = t; 8271541Srgrimes p = x->rn_p; 8281541Srgrimes if (p->rn_l == x) p->rn_l = t; else p->rn_r = t; 8291541Srgrimes } 8301541Srgrimesout: 8311541Srgrimes tt->rn_flags &= ~RNF_ACTIVE; 8321541Srgrimes tt[1].rn_flags &= ~RNF_ACTIVE; 8331541Srgrimes return (tt); 8341541Srgrimes} 8351541Srgrimes 8367197Swollman/* 8377197Swollman * This is the same as rn_walktree() except for the parameters and the 8387197Swollman * exit. 8397197Swollman */ 84012820Sphkstatic int 8417197Swollmanrn_walktree_from(h, a, m, f, w) 8427197Swollman struct radix_node_head *h; 8437197Swollman void *a, *m; 84412579Sbde walktree_f_t *f; 8457197Swollman void *w; 8467197Swollman{ 8477197Swollman int error; 8487197Swollman struct radix_node *base, *next; 8497197Swollman u_char *xa = (u_char *)a; 8507197Swollman u_char *xm = (u_char *)m; 8517197Swollman register struct radix_node *rn, *last = 0 /* shut up gcc */; 8527197Swollman int stopping = 0; 8537197Swollman int lastb; 8547197Swollman 8557197Swollman /* 8567197Swollman * rn_search_m is sort-of-open-coded here. 8577197Swollman */ 8587279Swollman /* printf("about to search\n"); */ 8597197Swollman for (rn = h->rnh_treetop; rn->rn_b >= 0; ) { 8607197Swollman last = rn; 8617279Swollman /* printf("rn_b %d, rn_bmask %x, xm[rn_off] %x\n", 8627279Swollman rn->rn_b, rn->rn_bmask, xm[rn->rn_off]); */ 8637279Swollman if (!(rn->rn_bmask & xm[rn->rn_off])) { 8647197Swollman break; 8657279Swollman } 8667197Swollman if (rn->rn_bmask & xa[rn->rn_off]) { 8677197Swollman rn = rn->rn_r; 8687197Swollman } else { 8697197Swollman rn = rn->rn_l; 8707197Swollman } 8717197Swollman } 8727279Swollman /* printf("done searching\n"); */ 8737197Swollman 8747197Swollman /* 8757197Swollman * Two cases: either we stepped off the end of our mask, 8767197Swollman * in which case last == rn, or we reached a leaf, in which 8777197Swollman * case we want to start from the last node we looked at. 8787197Swollman * Either way, last is the node we want to start from. 8797197Swollman */ 8807197Swollman rn = last; 8817197Swollman lastb = rn->rn_b; 8827197Swollman 8837279Swollman /* printf("rn %p, lastb %d\n", rn, lastb);*/ 8847279Swollman 8857197Swollman /* 8867197Swollman * This gets complicated because we may delete the node 8877197Swollman * while applying the function f to it, so we need to calculate 8887197Swollman * the successor node in advance. 8897197Swollman */ 8908876Srgrimes while (rn->rn_b >= 0) 8917197Swollman rn = rn->rn_l; 8927197Swollman 8937197Swollman while (!stopping) { 8947279Swollman /* printf("node %p (%d)\n", rn, rn->rn_b); */ 8957197Swollman base = rn; 8967197Swollman /* If at right child go back up, otherwise, go right */ 8977197Swollman while (rn->rn_p->rn_r == rn && !(rn->rn_flags & RNF_ROOT)) { 8987197Swollman rn = rn->rn_p; 8997197Swollman 9008876Srgrimes /* if went up beyond last, stop */ 9017197Swollman if (rn->rn_b < lastb) { 9027197Swollman stopping = 1; 9037279Swollman /* printf("up too far\n"); */ 9047197Swollman } 9057197Swollman } 9067197Swollman 9077197Swollman /* Find the next *leaf* since next node might vanish, too */ 9087197Swollman for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) 9097197Swollman rn = rn->rn_l; 9107197Swollman next = rn; 9117197Swollman /* Process leaves */ 9127197Swollman while ((rn = base) != 0) { 9137197Swollman base = rn->rn_dupedkey; 9147279Swollman /* printf("leaf %p\n", rn); */ 9158876Srgrimes if (!(rn->rn_flags & RNF_ROOT) 9167197Swollman && (error = (*f)(rn, w))) 9177197Swollman return (error); 9187197Swollman } 9197197Swollman rn = next; 9207279Swollman 9217279Swollman if (rn->rn_flags & RNF_ROOT) { 9227279Swollman /* printf("root, stopping"); */ 9237279Swollman stopping = 1; 9247279Swollman } 9257279Swollman 9267197Swollman } 9277197Swollman return 0; 9287197Swollman} 9297197Swollman 93012820Sphkstatic int 9311541Srgrimesrn_walktree(h, f, w) 9321541Srgrimes struct radix_node_head *h; 93312579Sbde walktree_f_t *f; 9341541Srgrimes void *w; 9351541Srgrimes{ 9361541Srgrimes int error; 9371541Srgrimes struct radix_node *base, *next; 9381541Srgrimes register struct radix_node *rn = h->rnh_treetop; 9391541Srgrimes /* 9401541Srgrimes * This gets complicated because we may delete the node 9411541Srgrimes * while applying the function f to it, so we need to calculate 9421541Srgrimes * the successor node in advance. 9431541Srgrimes */ 9441541Srgrimes /* First time through node, go left */ 9451541Srgrimes while (rn->rn_b >= 0) 9461541Srgrimes rn = rn->rn_l; 9471541Srgrimes for (;;) { 9481541Srgrimes base = rn; 9491541Srgrimes /* If at right child go back up, otherwise, go right */ 9501541Srgrimes while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0) 9511541Srgrimes rn = rn->rn_p; 9521541Srgrimes /* Find the next *leaf* since next node might vanish, too */ 9531541Srgrimes for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) 9541541Srgrimes rn = rn->rn_l; 9551541Srgrimes next = rn; 9561541Srgrimes /* Process leaves */ 9578152Spst while ((rn = base)) { 9581541Srgrimes base = rn->rn_dupedkey; 9591541Srgrimes if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w))) 9601541Srgrimes return (error); 9611541Srgrimes } 9621541Srgrimes rn = next; 9631541Srgrimes if (rn->rn_flags & RNF_ROOT) 9641541Srgrimes return (0); 9651541Srgrimes } 9661541Srgrimes /* NOTREACHED */ 9671541Srgrimes} 9681541Srgrimes 9691541Srgrimesint 9701541Srgrimesrn_inithead(head, off) 9711541Srgrimes void **head; 9721541Srgrimes int off; 9731541Srgrimes{ 9741541Srgrimes register struct radix_node_head *rnh; 9751541Srgrimes register struct radix_node *t, *tt, *ttt; 9761541Srgrimes if (*head) 9771541Srgrimes return (1); 9781541Srgrimes R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh)); 9791541Srgrimes if (rnh == 0) 9801541Srgrimes return (0); 9811541Srgrimes Bzero(rnh, sizeof (*rnh)); 9821541Srgrimes *head = rnh; 9831541Srgrimes t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 9841541Srgrimes ttt = rnh->rnh_nodes + 2; 9851541Srgrimes t->rn_r = ttt; 9861541Srgrimes t->rn_p = t; 9871541Srgrimes tt = t->rn_l; 9881541Srgrimes tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 9891541Srgrimes tt->rn_b = -1 - off; 9901541Srgrimes *ttt = *tt; 9911541Srgrimes ttt->rn_key = rn_ones; 9921541Srgrimes rnh->rnh_addaddr = rn_addroute; 9931541Srgrimes rnh->rnh_deladdr = rn_delete; 9941541Srgrimes rnh->rnh_matchaddr = rn_match; 9958152Spst rnh->rnh_lookup = rn_lookup; 9961541Srgrimes rnh->rnh_walktree = rn_walktree; 9977197Swollman rnh->rnh_walktree_from = rn_walktree_from; 9981541Srgrimes rnh->rnh_treetop = t; 9991541Srgrimes return (1); 10001541Srgrimes} 10011541Srgrimes 10021541Srgrimesvoid 10031541Srgrimesrn_init() 10041541Srgrimes{ 10051541Srgrimes char *cp, *cplim; 100655205Speter#ifdef _KERNEL 10071541Srgrimes struct domain *dom; 10081541Srgrimes 10091541Srgrimes for (dom = domains; dom; dom = dom->dom_next) 10101541Srgrimes if (dom->dom_maxrtkey > max_keylen) 10111541Srgrimes max_keylen = dom->dom_maxrtkey; 10121541Srgrimes#endif 10131541Srgrimes if (max_keylen == 0) { 10148152Spst log(LOG_ERR, 10158152Spst "rn_init: radix functions require max_keylen be set\n"); 10161541Srgrimes return; 10171541Srgrimes } 10181541Srgrimes R_Malloc(rn_zeros, char *, 3 * max_keylen); 10191541Srgrimes if (rn_zeros == NULL) 10201541Srgrimes panic("rn_init"); 10211541Srgrimes Bzero(rn_zeros, 3 * max_keylen); 10221541Srgrimes rn_ones = cp = rn_zeros + max_keylen; 10238152Spst addmask_key = cplim = rn_ones + max_keylen; 10241541Srgrimes while (cp < cplim) 10251541Srgrimes *cp++ = -1; 10261541Srgrimes if (rn_inithead((void **)&mask_rnhead, 0) == 0) 10271541Srgrimes panic("rn_init 2"); 10281541Srgrimes} 1029