radix.c revision 128433
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 * 4. Neither the name of the University nor the names of its contributors 141541Srgrimes * may be used to endorse or promote products derived from this software 151541Srgrimes * without specific prior written permission. 161541Srgrimes * 171541Srgrimes * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 181541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 191541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 201541Srgrimes * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 211541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 221541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 231541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 241541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 251541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 261541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 271541Srgrimes * SUCH DAMAGE. 281541Srgrimes * 29108268Sru * @(#)radix.c 8.5 (Berkeley) 5/19/95 3050477Speter * $FreeBSD: head/sys/net/radix.c 128433 2004-04-19 17:28:39Z luigi $ 311541Srgrimes */ 321541Srgrimes 331541Srgrimes/* 341541Srgrimes * Routines to build and maintain radix trees for routing lookups. 351541Srgrimes */ 368152Spst#ifndef _RADIX_H_ 371541Srgrimes#include <sys/param.h> 3855205Speter#ifdef _KERNEL 39110527Shsu#include <sys/lock.h> 40110527Shsu#include <sys/mutex.h> 411541Srgrimes#include <sys/systm.h> 421541Srgrimes#include <sys/malloc.h> 431541Srgrimes#include <sys/domain.h> 448152Spst#else 458152Spst#include <stdlib.h> 461541Srgrimes#endif 478152Spst#include <sys/syslog.h> 488152Spst#include <net/radix.h> 491541Srgrimes#endif 501541Srgrimes 5193084Sbdestatic int rn_walktree_from(struct radix_node_head *h, void *a, void *m, 5293084Sbde walktree_f_t *f, void *w); 5392725Salfredstatic int rn_walktree(struct radix_node_head *, walktree_f_t *, void *); 5412820Sphkstatic struct radix_node 5592725Salfred *rn_insert(void *, struct radix_node_head *, int *, 5693084Sbde struct radix_node [2]), 5792725Salfred *rn_newpair(void *, int, struct radix_node[2]), 5892725Salfred *rn_search(void *, struct radix_node *), 5992725Salfred *rn_search_m(void *, struct radix_node *, void *); 6012579Sbde 6112820Sphkstatic int max_keylen; 6212820Sphkstatic struct radix_mask *rn_mkfreelist; 6312820Sphkstatic struct radix_node_head *mask_rnhead; 64128433Sluigi/* 65128433Sluigi * Work area -- the following point to 3 buffers of size max_keylen, 66128433Sluigi * allocated in this order in a block of memory malloc'ed by rn_init. 67128433Sluigi */ 68128433Sluigistatic char *rn_zeros, *rn_ones, *addmask_key; 691541Srgrimes 70128401Sluigi#define MKGet(m) { \ 71128401Sluigi if (rn_mkfreelist) { \ 72128401Sluigi m = rn_mkfreelist; \ 73128401Sluigi rn_mkfreelist = (m)->rm_mklist; \ 74128401Sluigi } else \ 75128401Sluigi R_Malloc(m, struct radix_mask *, sizeof (struct radix_mask)); } 76128401Sluigi 77128401Sluigi#define MKFree(m) { (m)->rm_mklist = rn_mkfreelist; rn_mkfreelist = (m);} 78128401Sluigi 791541Srgrimes#define rn_masktop (mask_rnhead->rnh_treetop) 8012579Sbde 8192725Salfredstatic int rn_lexobetter(void *m_arg, void *n_arg); 8212579Sbdestatic struct radix_mask * 8392725Salfred rn_new_radix_mask(struct radix_node *tt, 8493084Sbde struct radix_mask *next); 85108273Srustatic int rn_satisfies_leaf(char *trial, struct radix_node *leaf, 8693084Sbde int skip); 8712579Sbde 881541Srgrimes/* 891541Srgrimes * The data structure for the keys is a radix tree with one way 9059529Swollman * branching removed. The index rn_bit at an internal node n represents a bit 911541Srgrimes * position to be tested. The tree is arranged so that all descendants 9259529Swollman * of a node n have keys whose bits all agree up to position rn_bit - 1. 9359529Swollman * (We say the index of n is rn_bit.) 941541Srgrimes * 9559529Swollman * There is at least one descendant which has a one bit at position rn_bit, 961541Srgrimes * and at least one with a zero there. 971541Srgrimes * 981541Srgrimes * A route is determined by a pair of key and mask. We require that the 991541Srgrimes * bit-wise logical and of the key and mask to be the key. 1001541Srgrimes * We define the index of a route to associated with the mask to be 1011541Srgrimes * the first bit number in the mask where 0 occurs (with bit number 0 1021541Srgrimes * representing the highest order bit). 1038876Srgrimes * 1041541Srgrimes * We say a mask is normal if every bit is 0, past the index of the mask. 10559529Swollman * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit, 1061541Srgrimes * and m is a normal mask, then the route applies to every descendant of n. 10759529Swollman * If the index(m) < rn_bit, this implies the trailing last few bits of k 1081541Srgrimes * before bit b are all 0, (and hence consequently true of every descendant 1091541Srgrimes * of n), so the route applies to all descendants of the node as well. 1108876Srgrimes * 1118152Spst * Similar logic shows that a non-normal mask m such that 1121541Srgrimes * index(m) <= index(n) could potentially apply to many children of n. 1131541Srgrimes * Thus, for each non-host route, we attach its mask to a list at an internal 1148876Srgrimes * node as high in the tree as we can go. 1158152Spst * 1168152Spst * The present version of the code makes use of normal routes in short- 1178152Spst * circuiting an explict mask and compare operation when testing whether 1188152Spst * a key satisfies a normal route, and also in remembering the unique leaf 1198152Spst * that governs a subtree. 1201541Srgrimes */ 1211541Srgrimes 12212820Sphkstatic struct radix_node * 1231541Srgrimesrn_search(v_arg, head) 1241541Srgrimes void *v_arg; 1251541Srgrimes struct radix_node *head; 1261541Srgrimes{ 1271541Srgrimes register struct radix_node *x; 1281541Srgrimes register caddr_t v; 1291541Srgrimes 13059529Swollman for (x = head, v = v_arg; x->rn_bit >= 0;) { 13159529Swollman if (x->rn_bmask & v[x->rn_offset]) 13259529Swollman x = x->rn_right; 1331541Srgrimes else 13459529Swollman x = x->rn_left; 1351541Srgrimes } 1361541Srgrimes return (x); 13731390Sbde} 1381541Srgrimes 13912820Sphkstatic struct radix_node * 1401541Srgrimesrn_search_m(v_arg, head, m_arg) 1411541Srgrimes struct radix_node *head; 1421541Srgrimes void *v_arg, *m_arg; 1431541Srgrimes{ 1441541Srgrimes register struct radix_node *x; 1451541Srgrimes register caddr_t v = v_arg, m = m_arg; 1461541Srgrimes 14759529Swollman for (x = head; x->rn_bit >= 0;) { 14859529Swollman if ((x->rn_bmask & m[x->rn_offset]) && 14959529Swollman (x->rn_bmask & v[x->rn_offset])) 15059529Swollman x = x->rn_right; 1511541Srgrimes else 15259529Swollman x = x->rn_left; 1531541Srgrimes } 1541541Srgrimes return x; 15531390Sbde} 1561541Srgrimes 1571541Srgrimesint 1581541Srgrimesrn_refines(m_arg, n_arg) 1591541Srgrimes void *m_arg, *n_arg; 1601541Srgrimes{ 1611541Srgrimes register caddr_t m = m_arg, n = n_arg; 1621541Srgrimes register caddr_t lim, lim2 = lim = n + *(u_char *)n; 1631541Srgrimes int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); 1641541Srgrimes int masks_are_equal = 1; 1651541Srgrimes 1661541Srgrimes if (longer > 0) 1671541Srgrimes lim -= longer; 1681541Srgrimes while (n < lim) { 1691541Srgrimes if (*n & ~(*m)) 1701541Srgrimes return 0; 1711541Srgrimes if (*n++ != *m++) 1721541Srgrimes masks_are_equal = 0; 1731541Srgrimes } 1741541Srgrimes while (n < lim2) 1751541Srgrimes if (*n++) 1761541Srgrimes return 0; 1771541Srgrimes if (masks_are_equal && (longer < 0)) 1781541Srgrimes for (lim2 = m - longer; m < lim2; ) 1791541Srgrimes if (*m++) 1801541Srgrimes return 1; 1811541Srgrimes return (!masks_are_equal); 1821541Srgrimes} 1831541Srgrimes 1848152Spststruct radix_node * 1858152Spstrn_lookup(v_arg, m_arg, head) 1868152Spst void *v_arg, *m_arg; 1878152Spst struct radix_node_head *head; 1888152Spst{ 1898152Spst register struct radix_node *x; 1908152Spst caddr_t netmask = 0; 1911541Srgrimes 1928152Spst if (m_arg) { 19359529Swollman x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset); 19459529Swollman if (x == 0) 1958152Spst return (0); 1968152Spst netmask = x->rn_key; 1978152Spst } 1988152Spst x = rn_match(v_arg, head); 1998152Spst if (x && netmask) { 2008152Spst while (x && x->rn_mask != netmask) 2018152Spst x = x->rn_dupedkey; 2028152Spst } 2038152Spst return x; 2048152Spst} 2058152Spst 2068152Spststatic int 207108273Srurn_satisfies_leaf(trial, leaf, skip) 2088152Spst char *trial; 2098152Spst register struct radix_node *leaf; 2108152Spst int skip; 2118152Spst{ 2128152Spst register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 2138152Spst char *cplim; 2148152Spst int length = min(*(u_char *)cp, *(u_char *)cp2); 2158152Spst 2168152Spst if (cp3 == 0) 2178152Spst cp3 = rn_ones; 2188152Spst else 2198152Spst length = min(length, *(u_char *)cp3); 2208152Spst cplim = cp + length; cp3 += skip; cp2 += skip; 2218152Spst for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 2228152Spst if ((*cp ^ *cp2) & *cp3) 2238152Spst return 0; 2248152Spst return 1; 2258152Spst} 2268152Spst 2271541Srgrimesstruct radix_node * 2281541Srgrimesrn_match(v_arg, head) 2291541Srgrimes void *v_arg; 2301541Srgrimes struct radix_node_head *head; 2311541Srgrimes{ 2321541Srgrimes caddr_t v = v_arg; 2331541Srgrimes register struct radix_node *t = head->rnh_treetop, *x; 2348152Spst register caddr_t cp = v, cp2; 2358152Spst caddr_t cplim; 2361541Srgrimes struct radix_node *saved_t, *top = t; 23759529Swollman int off = t->rn_offset, vlen = *(u_char *)cp, matched_off; 23859529Swollman register int test, b, rn_bit; 2391541Srgrimes 2401541Srgrimes /* 2411541Srgrimes * Open code rn_search(v, top) to avoid overhead of extra 2421541Srgrimes * subroutine call. 2431541Srgrimes */ 24459529Swollman for (; t->rn_bit >= 0; ) { 24559529Swollman if (t->rn_bmask & cp[t->rn_offset]) 24659529Swollman t = t->rn_right; 2471541Srgrimes else 24859529Swollman t = t->rn_left; 2491541Srgrimes } 2501541Srgrimes /* 2511541Srgrimes * See if we match exactly as a host destination 2528152Spst * or at least learn how many bits match, for normal mask finesse. 2538152Spst * 2548152Spst * It doesn't hurt us to limit how many bytes to check 2558152Spst * to the length of the mask, since if it matches we had a genuine 2568152Spst * match and the leaf we have is the most specific one anyway; 2578152Spst * if it didn't match with a shorter length it would fail 2588152Spst * with a long one. This wins big for class B&C netmasks which 2598152Spst * are probably the most common case... 2601541Srgrimes */ 2618152Spst if (t->rn_mask) 2628152Spst vlen = *(u_char *)t->rn_mask; 2631541Srgrimes cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 2641541Srgrimes for (; cp < cplim; cp++, cp2++) 2651541Srgrimes if (*cp != *cp2) 2661541Srgrimes goto on1; 2671541Srgrimes /* 2681541Srgrimes * This extra grot is in case we are explicitly asked 2691541Srgrimes * to look up the default. Ugh! 27048215Spb * 27148215Spb * Never return the root node itself, it seems to cause a 27248215Spb * lot of confusion. 2731541Srgrimes */ 27448215Spb if (t->rn_flags & RNF_ROOT) 2751541Srgrimes t = t->rn_dupedkey; 2761541Srgrimes return t; 2771541Srgrimeson1: 2788152Spst test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 2798152Spst for (b = 7; (test >>= 1) > 0;) 2808152Spst b--; 2811541Srgrimes matched_off = cp - v; 2828152Spst b += matched_off << 3; 28359529Swollman rn_bit = -1 - b; 2848152Spst /* 2858152Spst * If there is a host route in a duped-key chain, it will be first. 2868152Spst */ 2878152Spst if ((saved_t = t)->rn_mask == 0) 2888152Spst t = t->rn_dupedkey; 2898152Spst for (; t; t = t->rn_dupedkey) 2901541Srgrimes /* 2918152Spst * Even if we don't match exactly as a host, 2921541Srgrimes * we may match if the leaf we wound up at is 2931541Srgrimes * a route to a net. 2941541Srgrimes */ 2958152Spst if (t->rn_flags & RNF_NORMAL) { 29659529Swollman if (rn_bit <= t->rn_bit) 2978152Spst return t; 298108273Sru } else if (rn_satisfies_leaf(v, t, matched_off)) 2998152Spst return t; 3001541Srgrimes t = saved_t; 3011541Srgrimes /* start searching up the tree */ 3021541Srgrimes do { 3031541Srgrimes register struct radix_mask *m; 30459529Swollman t = t->rn_parent; 3053443Sphk m = t->rn_mklist; 30659529Swollman /* 30759529Swollman * If non-contiguous masks ever become important 30859529Swollman * we can restore the masking and open coding of 30959529Swollman * the search and satisfaction test and put the 31059529Swollman * calculation of "off" back before the "do". 31159529Swollman */ 31259529Swollman while (m) { 31359529Swollman if (m->rm_flags & RNF_NORMAL) { 31459529Swollman if (rn_bit <= m->rm_bit) 31559529Swollman return (m->rm_leaf); 31659529Swollman } else { 31759529Swollman off = min(t->rn_offset, matched_off); 31859529Swollman x = rn_search_m(v, t, m->rm_mask); 31959529Swollman while (x && x->rn_mask != m->rm_mask) 32059529Swollman x = x->rn_dupedkey; 321108273Sru if (x && rn_satisfies_leaf(v, x, off)) 32259529Swollman return x; 32359529Swollman } 32459529Swollman m = m->rm_mklist; 3251541Srgrimes } 3261541Srgrimes } while (t != top); 3271541Srgrimes return 0; 32831390Sbde} 3298876Srgrimes 3301541Srgrimes#ifdef RN_DEBUG 3311541Srgrimesint rn_nodenum; 3321541Srgrimesstruct radix_node *rn_clist; 3331541Srgrimesint rn_saveinfo; 3341541Srgrimesint rn_debug = 1; 3351541Srgrimes#endif 3361541Srgrimes 33712820Sphkstatic struct radix_node * 3381541Srgrimesrn_newpair(v, b, nodes) 3391541Srgrimes void *v; 3401541Srgrimes int b; 3411541Srgrimes struct radix_node nodes[2]; 3421541Srgrimes{ 3431541Srgrimes register struct radix_node *tt = nodes, *t = tt + 1; 34459529Swollman t->rn_bit = b; 34559529Swollman t->rn_bmask = 0x80 >> (b & 7); 34659529Swollman t->rn_left = tt; 34759529Swollman t->rn_offset = b >> 3; 34859529Swollman tt->rn_bit = -1; 34959529Swollman tt->rn_key = (caddr_t)v; 35059529Swollman tt->rn_parent = t; 3511541Srgrimes tt->rn_flags = t->rn_flags = RNF_ACTIVE; 35267727Swollman tt->rn_mklist = t->rn_mklist = 0; 3531541Srgrimes#ifdef RN_DEBUG 3541541Srgrimes tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 35559529Swollman tt->rn_twin = t; 35659529Swollman tt->rn_ybro = rn_clist; 35759529Swollman rn_clist = tt; 3581541Srgrimes#endif 3591541Srgrimes return t; 3601541Srgrimes} 3611541Srgrimes 36212820Sphkstatic struct radix_node * 3631541Srgrimesrn_insert(v_arg, head, dupentry, nodes) 3641541Srgrimes void *v_arg; 3651541Srgrimes struct radix_node_head *head; 3661541Srgrimes int *dupentry; 3671541Srgrimes struct radix_node nodes[2]; 3681541Srgrimes{ 3691541Srgrimes caddr_t v = v_arg; 3701541Srgrimes struct radix_node *top = head->rnh_treetop; 37159529Swollman int head_off = top->rn_offset, vlen = (int)*((u_char *)v); 3721541Srgrimes register struct radix_node *t = rn_search(v_arg, top); 3731541Srgrimes register caddr_t cp = v + head_off; 3741541Srgrimes register int b; 3751541Srgrimes struct radix_node *tt; 3761541Srgrimes /* 3778152Spst * Find first bit at which v and t->rn_key differ 3781541Srgrimes */ 3791541Srgrimes { 3801541Srgrimes register caddr_t cp2 = t->rn_key + head_off; 3811541Srgrimes register int cmp_res; 3821541Srgrimes caddr_t cplim = v + vlen; 3831541Srgrimes 3841541Srgrimes while (cp < cplim) 3851541Srgrimes if (*cp2++ != *cp++) 3861541Srgrimes goto on1; 3871541Srgrimes *dupentry = 1; 3881541Srgrimes return t; 3891541Srgrimeson1: 3901541Srgrimes *dupentry = 0; 3911541Srgrimes cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 3921541Srgrimes for (b = (cp - v) << 3; cmp_res; b--) 3931541Srgrimes cmp_res >>= 1; 3941541Srgrimes } 3951541Srgrimes { 3961541Srgrimes register struct radix_node *p, *x = top; 3971541Srgrimes cp = v; 3981541Srgrimes do { 3991541Srgrimes p = x; 40059529Swollman if (cp[x->rn_offset] & x->rn_bmask) 40159529Swollman x = x->rn_right; 40259529Swollman else 40359529Swollman x = x->rn_left; 40459529Swollman } while (b > (unsigned) x->rn_bit); 40559529Swollman /* x->rn_bit < b && x->rn_bit >= 0 */ 4061541Srgrimes#ifdef RN_DEBUG 4071541Srgrimes if (rn_debug) 4088152Spst log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); 4091541Srgrimes#endif 41059529Swollman t = rn_newpair(v_arg, b, nodes); 41159529Swollman tt = t->rn_left; 41259529Swollman if ((cp[p->rn_offset] & p->rn_bmask) == 0) 41359529Swollman p->rn_left = t; 4141541Srgrimes else 41559529Swollman p->rn_right = t; 41659529Swollman x->rn_parent = t; 41759529Swollman t->rn_parent = p; /* frees x, p as temp vars below */ 41859529Swollman if ((cp[t->rn_offset] & t->rn_bmask) == 0) { 41959529Swollman t->rn_right = x; 4201541Srgrimes } else { 42159529Swollman t->rn_right = tt; 42259529Swollman t->rn_left = x; 4231541Srgrimes } 4241541Srgrimes#ifdef RN_DEBUG 4251541Srgrimes if (rn_debug) 4268152Spst log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); 4271541Srgrimes#endif 4281541Srgrimes } 4291541Srgrimes return (tt); 4301541Srgrimes} 4311541Srgrimes 4321541Srgrimesstruct radix_node * 4331541Srgrimesrn_addmask(n_arg, search, skip) 4341541Srgrimes int search, skip; 4351541Srgrimes void *n_arg; 4361541Srgrimes{ 4371541Srgrimes caddr_t netmask = (caddr_t)n_arg; 4381541Srgrimes register struct radix_node *x; 4391541Srgrimes register caddr_t cp, cplim; 4408152Spst register int b = 0, mlen, j; 4418152Spst int maskduplicated, m0, isnormal; 4428152Spst struct radix_node *saved_x; 4438152Spst static int last_zeroed = 0; 4441541Srgrimes 4458152Spst if ((mlen = *(u_char *)netmask) > max_keylen) 4468152Spst mlen = max_keylen; 4478152Spst if (skip == 0) 4488152Spst skip = 1; 4498152Spst if (mlen <= skip) 4508152Spst return (mask_rnhead->rnh_nodes); 4518152Spst if (skip > 1) 452128401Sluigi bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 4538152Spst if ((m0 = mlen) > skip) 454128401Sluigi bcopy(netmask + skip, addmask_key + skip, mlen - skip); 4558152Spst /* 4568152Spst * Trim trailing zeroes. 4578152Spst */ 4588152Spst for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) 4598152Spst cp--; 4608152Spst mlen = cp - addmask_key; 4618152Spst if (mlen <= skip) { 4628152Spst if (m0 >= last_zeroed) 4638152Spst last_zeroed = mlen; 4648152Spst return (mask_rnhead->rnh_nodes); 4651541Srgrimes } 4668152Spst if (m0 < last_zeroed) 467128401Sluigi bzero(addmask_key + m0, last_zeroed - m0); 4688152Spst *addmask_key = last_zeroed = mlen; 4698152Spst x = rn_search(addmask_key, rn_masktop); 470128401Sluigi if (bcmp(addmask_key, x->rn_key, mlen) != 0) 4718152Spst x = 0; 4728152Spst if (x || search) 4738152Spst return (x); 474128433Sluigi R_Zalloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); 4758152Spst if ((saved_x = x) == 0) 4761541Srgrimes return (0); 4778152Spst netmask = cp = (caddr_t)(x + 2); 478128401Sluigi bcopy(addmask_key, cp, mlen); 4798152Spst x = rn_insert(cp, mask_rnhead, &maskduplicated, x); 4808152Spst if (maskduplicated) { 4818152Spst log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 4828152Spst Free(saved_x); 4838152Spst return (x); 4848152Spst } 4851541Srgrimes /* 4868152Spst * Calculate index of mask, and check for normalcy. 487128433Sluigi * First find the first byte with a 0 bit, then if there are 488128433Sluigi * more bits left (remember we already trimmed the trailing 0's), 489128433Sluigi * the pattern must be one of those in normal_chars[], or we have 490128433Sluigi * a non-contiguous mask. 4911541Srgrimes */ 492128433Sluigi cplim = netmask + mlen; 493128433Sluigi isnormal = 1; 4948152Spst for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) 4958152Spst cp++; 4961541Srgrimes if (cp != cplim) { 497128433Sluigi static char normal_chars[] = { 498128433Sluigi 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff}; 499128433Sluigi 5008876Srgrimes for (j = 0x80; (j & *cp) != 0; j >>= 1) 5018152Spst b++; 5028152Spst if (*cp != normal_chars[b] || cp != (cplim - 1)) 5038152Spst isnormal = 0; 5041541Srgrimes } 5058152Spst b += (cp - netmask) << 3; 50659529Swollman x->rn_bit = -1 - b; 5078152Spst if (isnormal) 5088152Spst x->rn_flags |= RNF_NORMAL; 5091541Srgrimes return (x); 5101541Srgrimes} 5111541Srgrimes 5128152Spststatic int /* XXX: arbitrary ordering for non-contiguous masks */ 5138152Spstrn_lexobetter(m_arg, n_arg) 5148152Spst void *m_arg, *n_arg; 5158152Spst{ 5168152Spst register u_char *mp = m_arg, *np = n_arg, *lim; 5178152Spst 5188152Spst if (*mp > *np) 5198152Spst return 1; /* not really, but need to check longer one first */ 5208876Srgrimes if (*mp == *np) 5218152Spst for (lim = mp + *mp; mp < lim;) 5228152Spst if (*mp++ > *np++) 5238152Spst return 1; 5248152Spst return 0; 5258152Spst} 5268152Spst 5278152Spststatic struct radix_mask * 5288152Spstrn_new_radix_mask(tt, next) 5298152Spst register struct radix_node *tt; 5308152Spst register struct radix_mask *next; 5318152Spst{ 5328152Spst register struct radix_mask *m; 5338152Spst 5348152Spst MKGet(m); 5358152Spst if (m == 0) { 5368152Spst log(LOG_ERR, "Mask for route not entered\n"); 5378152Spst return (0); 5388152Spst } 539128401Sluigi bzero(m, sizeof *m); 54059529Swollman m->rm_bit = tt->rn_bit; 5418152Spst m->rm_flags = tt->rn_flags; 5428152Spst if (tt->rn_flags & RNF_NORMAL) 5438152Spst m->rm_leaf = tt; 5448152Spst else 5458152Spst m->rm_mask = tt->rn_mask; 5468152Spst m->rm_mklist = next; 5478152Spst tt->rn_mklist = m; 5488152Spst return m; 5498152Spst} 5508152Spst 5511541Srgrimesstruct radix_node * 5521541Srgrimesrn_addroute(v_arg, n_arg, head, treenodes) 5531541Srgrimes void *v_arg, *n_arg; 5541541Srgrimes struct radix_node_head *head; 5551541Srgrimes struct radix_node treenodes[2]; 5561541Srgrimes{ 5571541Srgrimes caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 5581549Srgrimes register struct radix_node *t, *x = 0, *tt; 5591541Srgrimes struct radix_node *saved_tt, *top = head->rnh_treetop; 5608152Spst short b = 0, b_leaf = 0; 5618152Spst int keyduplicated; 5628152Spst caddr_t mmask; 5631541Srgrimes struct radix_mask *m, **mp; 5641541Srgrimes 5651541Srgrimes /* 5661541Srgrimes * In dealing with non-contiguous masks, there may be 5671541Srgrimes * many different routes which have the same mask. 5681541Srgrimes * We will find it useful to have a unique pointer to 5691541Srgrimes * the mask to speed avoiding duplicate references at 5701541Srgrimes * nodes and possibly save time in calculating indices. 5711541Srgrimes */ 5721541Srgrimes if (netmask) { 57359529Swollman if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0) 5748152Spst return (0); 57559529Swollman b_leaf = x->rn_bit; 57659529Swollman b = -1 - x->rn_bit; 5771541Srgrimes netmask = x->rn_key; 5781541Srgrimes } 5791541Srgrimes /* 5801541Srgrimes * Deal with duplicated keys: attach node to previous instance 5811541Srgrimes */ 5821541Srgrimes saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 5831541Srgrimes if (keyduplicated) { 5848152Spst for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 5851541Srgrimes if (tt->rn_mask == netmask) 5861541Srgrimes return (0); 5871541Srgrimes if (netmask == 0 || 5888152Spst (tt->rn_mask && 58959529Swollman ((b_leaf < tt->rn_bit) /* index(netmask) > node */ 59059529Swollman || rn_refines(netmask, tt->rn_mask) 59159529Swollman || rn_lexobetter(netmask, tt->rn_mask)))) 5921541Srgrimes break; 5938152Spst } 5941541Srgrimes /* 5951541Srgrimes * If the mask is not duplicated, we wouldn't 5961541Srgrimes * find it among possible duplicate key entries 5971541Srgrimes * anyway, so the above test doesn't hurt. 5981541Srgrimes * 5991541Srgrimes * We sort the masks for a duplicated key the same way as 6001541Srgrimes * in a masklist -- most specific to least specific. 6011541Srgrimes * This may require the unfortunate nuisance of relocating 6021541Srgrimes * the head of the list. 603108268Sru * 604108268Sru * We also reverse, or doubly link the list through the 605108268Sru * parent pointer. 6061541Srgrimes */ 6078152Spst if (tt == saved_tt) { 6081541Srgrimes struct radix_node *xx = x; 6091541Srgrimes /* link in at head of list */ 6101541Srgrimes (tt = treenodes)->rn_dupedkey = t; 6111541Srgrimes tt->rn_flags = t->rn_flags; 61259529Swollman tt->rn_parent = x = t->rn_parent; 61359529Swollman t->rn_parent = tt; /* parent */ 61459529Swollman if (x->rn_left == t) 61559529Swollman x->rn_left = tt; 61659529Swollman else 61759529Swollman x->rn_right = tt; 6181541Srgrimes saved_tt = tt; x = xx; 6191541Srgrimes } else { 6201541Srgrimes (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 6211541Srgrimes t->rn_dupedkey = tt; 62259529Swollman tt->rn_parent = t; /* parent */ 6238152Spst if (tt->rn_dupedkey) /* parent */ 62459529Swollman tt->rn_dupedkey->rn_parent = tt; /* parent */ 6251541Srgrimes } 6261541Srgrimes#ifdef RN_DEBUG 6271541Srgrimes t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 6281541Srgrimes tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 6291541Srgrimes#endif 6301541Srgrimes tt->rn_key = (caddr_t) v; 63159529Swollman tt->rn_bit = -1; 6328152Spst tt->rn_flags = RNF_ACTIVE; 6331541Srgrimes } 6341541Srgrimes /* 6351541Srgrimes * Put mask in tree. 6361541Srgrimes */ 6371541Srgrimes if (netmask) { 6381541Srgrimes tt->rn_mask = netmask; 63959529Swollman tt->rn_bit = x->rn_bit; 6408152Spst tt->rn_flags |= x->rn_flags & RNF_NORMAL; 6411541Srgrimes } 64259529Swollman t = saved_tt->rn_parent; 6438152Spst if (keyduplicated) 6448152Spst goto on2; 64559529Swollman b_leaf = -1 - t->rn_bit; 64659529Swollman if (t->rn_right == saved_tt) 64759529Swollman x = t->rn_left; 64859529Swollman else 64959529Swollman x = t->rn_right; 6501541Srgrimes /* Promote general routes from below */ 65159529Swollman if (x->rn_bit < 0) { 6528152Spst for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 65359529Swollman if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) { 6548152Spst *mp = m = rn_new_radix_mask(x, 0); 6558152Spst if (m) 6568152Spst mp = &m->rm_mklist; 6571541Srgrimes } 6581541Srgrimes } else if (x->rn_mklist) { 6591541Srgrimes /* 6601541Srgrimes * Skip over masks whose index is > that of new node 6611541Srgrimes */ 6628152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 66359529Swollman if (m->rm_bit >= b_leaf) 6641541Srgrimes break; 6651541Srgrimes t->rn_mklist = m; *mp = 0; 6661541Srgrimes } 6678152Spston2: 6681541Srgrimes /* Add new route to highest possible ancestor's list */ 66959529Swollman if ((netmask == 0) || (b > t->rn_bit )) 6701541Srgrimes return tt; /* can't lift at all */ 67159529Swollman b_leaf = tt->rn_bit; 6721541Srgrimes do { 6731541Srgrimes x = t; 67459529Swollman t = t->rn_parent; 67559529Swollman } while (b <= t->rn_bit && x != top); 6761541Srgrimes /* 6771541Srgrimes * Search through routes associated with node to 6781541Srgrimes * insert new route according to index. 6798152Spst * Need same criteria as when sorting dupedkeys to avoid 6808152Spst * double loop on deletion. 6811541Srgrimes */ 6828152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { 68359529Swollman if (m->rm_bit < b_leaf) 6841541Srgrimes continue; 68559529Swollman if (m->rm_bit > b_leaf) 6861541Srgrimes break; 6878152Spst if (m->rm_flags & RNF_NORMAL) { 6888152Spst mmask = m->rm_leaf->rn_mask; 6898152Spst if (tt->rn_flags & RNF_NORMAL) { 69059529Swollman log(LOG_ERR, 69195023Ssuz "Non-unique normal route, mask not entered\n"); 6928152Spst return tt; 6938152Spst } 6948152Spst } else 6958152Spst mmask = m->rm_mask; 6968152Spst if (mmask == netmask) { 6971541Srgrimes m->rm_refs++; 6981541Srgrimes tt->rn_mklist = m; 6991541Srgrimes return tt; 7001541Srgrimes } 70159529Swollman if (rn_refines(netmask, mmask) 70259529Swollman || rn_lexobetter(netmask, mmask)) 7031541Srgrimes break; 7041541Srgrimes } 7058152Spst *mp = rn_new_radix_mask(tt, *mp); 7061541Srgrimes return tt; 7071541Srgrimes} 7081541Srgrimes 70931390Sbdestruct radix_node * 7101541Srgrimesrn_delete(v_arg, netmask_arg, head) 7111541Srgrimes void *v_arg, *netmask_arg; 7121541Srgrimes struct radix_node_head *head; 7131541Srgrimes{ 7141541Srgrimes register struct radix_node *t, *p, *x, *tt; 7151541Srgrimes struct radix_mask *m, *saved_m, **mp; 7161541Srgrimes struct radix_node *dupedkey, *saved_tt, *top; 7171541Srgrimes caddr_t v, netmask; 7181541Srgrimes int b, head_off, vlen; 7191541Srgrimes 7201541Srgrimes v = v_arg; 7211541Srgrimes netmask = netmask_arg; 7221541Srgrimes x = head->rnh_treetop; 7231541Srgrimes tt = rn_search(v, x); 72459529Swollman head_off = x->rn_offset; 7251541Srgrimes vlen = *(u_char *)v; 7261541Srgrimes saved_tt = tt; 7271541Srgrimes top = x; 7281541Srgrimes if (tt == 0 || 729128401Sluigi bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 7301541Srgrimes return (0); 7311541Srgrimes /* 7321541Srgrimes * Delete our route from mask lists. 7331541Srgrimes */ 7348152Spst if (netmask) { 7358152Spst if ((x = rn_addmask(netmask, 1, head_off)) == 0) 7368152Spst return (0); 7378152Spst netmask = x->rn_key; 7381541Srgrimes while (tt->rn_mask != netmask) 7391541Srgrimes if ((tt = tt->rn_dupedkey) == 0) 7401541Srgrimes return (0); 7411541Srgrimes } 7421541Srgrimes if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 7431541Srgrimes goto on1; 7448152Spst if (tt->rn_flags & RNF_NORMAL) { 7458152Spst if (m->rm_leaf != tt || m->rm_refs > 0) { 7468152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 7478152Spst return 0; /* dangling ref could cause disaster */ 7488152Spst } 7498876Srgrimes } else { 7508152Spst if (m->rm_mask != tt->rn_mask) { 7518152Spst log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 7528152Spst goto on1; 7538152Spst } 7548152Spst if (--m->rm_refs >= 0) 7558152Spst goto on1; 7561541Srgrimes } 75759529Swollman b = -1 - tt->rn_bit; 75859529Swollman t = saved_tt->rn_parent; 75959529Swollman if (b > t->rn_bit) 7601541Srgrimes goto on1; /* Wasn't lifted at all */ 7611541Srgrimes do { 7621541Srgrimes x = t; 76359529Swollman t = t->rn_parent; 76459529Swollman } while (b <= t->rn_bit && x != top); 7658152Spst for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 7661541Srgrimes if (m == saved_m) { 7671541Srgrimes *mp = m->rm_mklist; 7681541Srgrimes MKFree(m); 7691541Srgrimes break; 7701541Srgrimes } 7718152Spst if (m == 0) { 7728152Spst log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 7738152Spst if (tt->rn_flags & RNF_NORMAL) 7748152Spst return (0); /* Dangling ref to us */ 7758152Spst } 7761541Srgrimeson1: 7771541Srgrimes /* 7781541Srgrimes * Eliminate us from tree 7791541Srgrimes */ 7801541Srgrimes if (tt->rn_flags & RNF_ROOT) 7811541Srgrimes return (0); 7821541Srgrimes#ifdef RN_DEBUG 7831541Srgrimes /* Get us out of the creation list */ 7841541Srgrimes for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 7851541Srgrimes if (t) t->rn_ybro = tt->rn_ybro; 7861541Srgrimes#endif 78759529Swollman t = tt->rn_parent; 7888152Spst dupedkey = saved_tt->rn_dupedkey; 7891541Srgrimes if (dupedkey) { 7908152Spst /* 791108268Sru * Here, tt is the deletion target and 792108268Sru * saved_tt is the head of the dupekey chain. 7938152Spst */ 7941541Srgrimes if (tt == saved_tt) { 7958152Spst /* remove from head of chain */ 79659529Swollman x = dupedkey; x->rn_parent = t; 79759529Swollman if (t->rn_left == tt) 79859529Swollman t->rn_left = x; 79959529Swollman else 80059529Swollman t->rn_right = x; 8011541Srgrimes } else { 8028152Spst /* find node in front of tt on the chain */ 8031541Srgrimes for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 8041541Srgrimes p = p->rn_dupedkey; 8058152Spst if (p) { 8068152Spst p->rn_dupedkey = tt->rn_dupedkey; 80759529Swollman if (tt->rn_dupedkey) /* parent */ 80859529Swollman tt->rn_dupedkey->rn_parent = p; 80959529Swollman /* parent */ 8108152Spst } else log(LOG_ERR, "rn_delete: couldn't find us\n"); 8111541Srgrimes } 8121541Srgrimes t = tt + 1; 8131541Srgrimes if (t->rn_flags & RNF_ACTIVE) { 8141541Srgrimes#ifndef RN_DEBUG 81559529Swollman *++x = *t; 81659529Swollman p = t->rn_parent; 8171541Srgrimes#else 81859529Swollman b = t->rn_info; 81959529Swollman *++x = *t; 82059529Swollman t->rn_info = b; 82159529Swollman p = t->rn_parent; 8221541Srgrimes#endif 82359529Swollman if (p->rn_left == t) 82459529Swollman p->rn_left = x; 82559529Swollman else 82659529Swollman p->rn_right = x; 82759529Swollman x->rn_left->rn_parent = x; 82859529Swollman x->rn_right->rn_parent = x; 8291541Srgrimes } 8301541Srgrimes goto out; 8311541Srgrimes } 83259529Swollman if (t->rn_left == tt) 83359529Swollman x = t->rn_right; 83459529Swollman else 83559529Swollman x = t->rn_left; 83659529Swollman p = t->rn_parent; 83759529Swollman if (p->rn_right == t) 83859529Swollman p->rn_right = x; 83959529Swollman else 84059529Swollman p->rn_left = x; 84159529Swollman x->rn_parent = p; 8421541Srgrimes /* 8431541Srgrimes * Demote routes attached to us. 8441541Srgrimes */ 8451541Srgrimes if (t->rn_mklist) { 84659529Swollman if (x->rn_bit >= 0) { 8478152Spst for (mp = &x->rn_mklist; (m = *mp);) 8481541Srgrimes mp = &m->rm_mklist; 8491541Srgrimes *mp = t->rn_mklist; 8501541Srgrimes } else { 8518152Spst /* If there are any key,mask pairs in a sibling 8528152Spst duped-key chain, some subset will appear sorted 8538152Spst in the same order attached to our mklist */ 8548152Spst for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 8558152Spst if (m == x->rn_mklist) { 8568152Spst struct radix_mask *mm = m->rm_mklist; 8571541Srgrimes x->rn_mklist = 0; 8588152Spst if (--(m->rm_refs) < 0) 8598152Spst MKFree(m); 8608152Spst m = mm; 8618152Spst } 8628152Spst if (m) 86337560Sbde log(LOG_ERR, 86437560Sbde "rn_delete: Orphaned Mask %p at %p\n", 86537560Sbde (void *)m, (void *)x); 8661541Srgrimes } 8671541Srgrimes } 8681541Srgrimes /* 8691541Srgrimes * We may be holding an active internal node in the tree. 8701541Srgrimes */ 8711541Srgrimes x = tt + 1; 8721541Srgrimes if (t != x) { 8731541Srgrimes#ifndef RN_DEBUG 8741541Srgrimes *t = *x; 8751541Srgrimes#else 87659529Swollman b = t->rn_info; 87759529Swollman *t = *x; 87859529Swollman t->rn_info = b; 8791541Srgrimes#endif 88059529Swollman t->rn_left->rn_parent = t; 88159529Swollman t->rn_right->rn_parent = t; 88259529Swollman p = x->rn_parent; 88359529Swollman if (p->rn_left == x) 88459529Swollman p->rn_left = t; 88559529Swollman else 88659529Swollman p->rn_right = t; 8871541Srgrimes } 8881541Srgrimesout: 8891541Srgrimes tt->rn_flags &= ~RNF_ACTIVE; 8901541Srgrimes tt[1].rn_flags &= ~RNF_ACTIVE; 8911541Srgrimes return (tt); 8921541Srgrimes} 8931541Srgrimes 8947197Swollman/* 8957197Swollman * This is the same as rn_walktree() except for the parameters and the 8967197Swollman * exit. 8977197Swollman */ 89812820Sphkstatic int 8997197Swollmanrn_walktree_from(h, a, m, f, w) 9007197Swollman struct radix_node_head *h; 9017197Swollman void *a, *m; 90212579Sbde walktree_f_t *f; 9037197Swollman void *w; 9047197Swollman{ 9057197Swollman int error; 9067197Swollman struct radix_node *base, *next; 9077197Swollman u_char *xa = (u_char *)a; 9087197Swollman u_char *xm = (u_char *)m; 9097197Swollman register struct radix_node *rn, *last = 0 /* shut up gcc */; 9107197Swollman int stopping = 0; 9117197Swollman int lastb; 9127197Swollman 9137197Swollman /* 9147197Swollman * rn_search_m is sort-of-open-coded here. 9157197Swollman */ 9167279Swollman /* printf("about to search\n"); */ 91759529Swollman for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) { 9187197Swollman last = rn; 91959529Swollman /* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n", 92059529Swollman rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */ 92159529Swollman if (!(rn->rn_bmask & xm[rn->rn_offset])) { 9227197Swollman break; 9237279Swollman } 92459529Swollman if (rn->rn_bmask & xa[rn->rn_offset]) { 92559529Swollman rn = rn->rn_right; 9267197Swollman } else { 92759529Swollman rn = rn->rn_left; 9287197Swollman } 9297197Swollman } 9307279Swollman /* printf("done searching\n"); */ 9317197Swollman 9327197Swollman /* 9337197Swollman * Two cases: either we stepped off the end of our mask, 9347197Swollman * in which case last == rn, or we reached a leaf, in which 9357197Swollman * case we want to start from the last node we looked at. 9367197Swollman * Either way, last is the node we want to start from. 9377197Swollman */ 9387197Swollman rn = last; 93959529Swollman lastb = rn->rn_bit; 9407197Swollman 9417279Swollman /* printf("rn %p, lastb %d\n", rn, lastb);*/ 9427279Swollman 9437197Swollman /* 9447197Swollman * This gets complicated because we may delete the node 9457197Swollman * while applying the function f to it, so we need to calculate 9467197Swollman * the successor node in advance. 9477197Swollman */ 94859529Swollman while (rn->rn_bit >= 0) 94959529Swollman rn = rn->rn_left; 9507197Swollman 9517197Swollman while (!stopping) { 95259529Swollman /* printf("node %p (%d)\n", rn, rn->rn_bit); */ 9537197Swollman base = rn; 9547197Swollman /* If at right child go back up, otherwise, go right */ 95559529Swollman while (rn->rn_parent->rn_right == rn 95659529Swollman && !(rn->rn_flags & RNF_ROOT)) { 95759529Swollman rn = rn->rn_parent; 9587197Swollman 9598876Srgrimes /* if went up beyond last, stop */ 96059529Swollman if (rn->rn_bit < lastb) { 9617197Swollman stopping = 1; 9627279Swollman /* printf("up too far\n"); */ 9637197Swollman } 9647197Swollman } 9657197Swollman 9667197Swollman /* Find the next *leaf* since next node might vanish, too */ 96759529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 96859529Swollman rn = rn->rn_left; 9697197Swollman next = rn; 9707197Swollman /* Process leaves */ 9717197Swollman while ((rn = base) != 0) { 9727197Swollman base = rn->rn_dupedkey; 9737279Swollman /* printf("leaf %p\n", rn); */ 9748876Srgrimes if (!(rn->rn_flags & RNF_ROOT) 9757197Swollman && (error = (*f)(rn, w))) 9767197Swollman return (error); 9777197Swollman } 9787197Swollman rn = next; 9797279Swollman 9807279Swollman if (rn->rn_flags & RNF_ROOT) { 9817279Swollman /* printf("root, stopping"); */ 9827279Swollman stopping = 1; 9837279Swollman } 9847279Swollman 9857197Swollman } 9867197Swollman return 0; 9877197Swollman} 9887197Swollman 98912820Sphkstatic int 9901541Srgrimesrn_walktree(h, f, w) 9911541Srgrimes struct radix_node_head *h; 99212579Sbde walktree_f_t *f; 9931541Srgrimes void *w; 9941541Srgrimes{ 9951541Srgrimes int error; 9961541Srgrimes struct radix_node *base, *next; 9971541Srgrimes register struct radix_node *rn = h->rnh_treetop; 9981541Srgrimes /* 9991541Srgrimes * This gets complicated because we may delete the node 10001541Srgrimes * while applying the function f to it, so we need to calculate 10011541Srgrimes * the successor node in advance. 10021541Srgrimes */ 10031541Srgrimes /* First time through node, go left */ 100459529Swollman while (rn->rn_bit >= 0) 100559529Swollman rn = rn->rn_left; 10061541Srgrimes for (;;) { 10071541Srgrimes base = rn; 10081541Srgrimes /* If at right child go back up, otherwise, go right */ 100959529Swollman while (rn->rn_parent->rn_right == rn 101059529Swollman && (rn->rn_flags & RNF_ROOT) == 0) 101159529Swollman rn = rn->rn_parent; 10121541Srgrimes /* Find the next *leaf* since next node might vanish, too */ 101359529Swollman for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 101459529Swollman rn = rn->rn_left; 10151541Srgrimes next = rn; 10161541Srgrimes /* Process leaves */ 10178152Spst while ((rn = base)) { 10181541Srgrimes base = rn->rn_dupedkey; 101959529Swollman if (!(rn->rn_flags & RNF_ROOT) 102059529Swollman && (error = (*f)(rn, w))) 10211541Srgrimes return (error); 10221541Srgrimes } 10231541Srgrimes rn = next; 10241541Srgrimes if (rn->rn_flags & RNF_ROOT) 10251541Srgrimes return (0); 10261541Srgrimes } 10271541Srgrimes /* NOTREACHED */ 10281541Srgrimes} 10291541Srgrimes 10301541Srgrimesint 10311541Srgrimesrn_inithead(head, off) 10321541Srgrimes void **head; 10331541Srgrimes int off; 10341541Srgrimes{ 10351541Srgrimes register struct radix_node_head *rnh; 10361541Srgrimes register struct radix_node *t, *tt, *ttt; 10371541Srgrimes if (*head) 10381541Srgrimes return (1); 1039128433Sluigi R_Zalloc(rnh, struct radix_node_head *, sizeof (*rnh)); 10401541Srgrimes if (rnh == 0) 10411541Srgrimes return (0); 1042110527Shsu#ifdef _KERNEL 1043108250Shsu RADIX_NODE_HEAD_LOCK_INIT(rnh); 1044110527Shsu#endif 10451541Srgrimes *head = rnh; 10461541Srgrimes t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 10471541Srgrimes ttt = rnh->rnh_nodes + 2; 104859529Swollman t->rn_right = ttt; 104959529Swollman t->rn_parent = t; 105059529Swollman tt = t->rn_left; 10511541Srgrimes tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 105259529Swollman tt->rn_bit = -1 - off; 10531541Srgrimes *ttt = *tt; 10541541Srgrimes ttt->rn_key = rn_ones; 10551541Srgrimes rnh->rnh_addaddr = rn_addroute; 10561541Srgrimes rnh->rnh_deladdr = rn_delete; 10571541Srgrimes rnh->rnh_matchaddr = rn_match; 10588152Spst rnh->rnh_lookup = rn_lookup; 10591541Srgrimes rnh->rnh_walktree = rn_walktree; 10607197Swollman rnh->rnh_walktree_from = rn_walktree_from; 10611541Srgrimes rnh->rnh_treetop = t; 10621541Srgrimes return (1); 10631541Srgrimes} 10641541Srgrimes 10651541Srgrimesvoid 10661541Srgrimesrn_init() 10671541Srgrimes{ 10681541Srgrimes char *cp, *cplim; 106955205Speter#ifdef _KERNEL 10701541Srgrimes struct domain *dom; 10711541Srgrimes 10721541Srgrimes for (dom = domains; dom; dom = dom->dom_next) 10731541Srgrimes if (dom->dom_maxrtkey > max_keylen) 10741541Srgrimes max_keylen = dom->dom_maxrtkey; 10751541Srgrimes#endif 10761541Srgrimes if (max_keylen == 0) { 10778152Spst log(LOG_ERR, 10788152Spst "rn_init: radix functions require max_keylen be set\n"); 10791541Srgrimes return; 10801541Srgrimes } 10811541Srgrimes R_Malloc(rn_zeros, char *, 3 * max_keylen); 10821541Srgrimes if (rn_zeros == NULL) 10831541Srgrimes panic("rn_init"); 1084128401Sluigi bzero(rn_zeros, 3 * max_keylen); 10851541Srgrimes rn_ones = cp = rn_zeros + max_keylen; 10868152Spst addmask_key = cplim = rn_ones + max_keylen; 10871541Srgrimes while (cp < cplim) 10881541Srgrimes *cp++ = -1; 1089120359Speter if (rn_inithead((void **)(void *)&mask_rnhead, 0) == 0) 10901541Srgrimes panic("rn_init 2"); 10911541Srgrimes} 1092