radix.c revision 67727
1148330Snetchild/* 2148330Snetchild * Copyright (c) 1988, 1989, 1993 3148330Snetchild * The Regents of the University of California. All rights reserved. 4148330Snetchild * 5148330Snetchild * Redistribution and use in source and binary forms, with or without 6148330Snetchild * modification, are permitted provided that the following conditions 7148330Snetchild * are met: 8148330Snetchild * 1. Redistributions of source code must retain the above copyright 9148330Snetchild * notice, this list of conditions and the following disclaimer. 10148330Snetchild * 2. Redistributions in binary form must reproduce the above copyright 11148330Snetchild * notice, this list of conditions and the following disclaimer in the 12148330Snetchild * documentation and/or other materials provided with the distribution. 13148330Snetchild * 3. All advertising materials mentioning features or use of this software 14148543Snetchild * must display the following acknowledgement: 15148543Snetchild * This product includes software developed by the University of 16148330Snetchild * California, Berkeley and its contributors. 17197081Sdelphij * 4. Neither the name of the University nor the names of its contributors 18197081Sdelphij * may be used to endorse or promote products derived from this software 19197081Sdelphij * without specific prior written permission. 20196787Sremko * 21196787Sremko * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22196787Sremko * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23196787Sremko * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24196787Sremko * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25196768Sflz * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26196768Sflz * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27196768Sflz * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28196768Sflz * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29196019Srwatson * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30196019Srwatson * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31195767Skensmith * SUCH DAMAGE. 32195767Skensmith * 33195767Skensmith * @(#)radix.c 8.4 (Berkeley) 11/2/94 34195767Skensmith * $FreeBSD: head/sys/net/radix.c 67727 2000-10-27 20:50:14Z wollman $ 35195767Skensmith */ 36195767Skensmith 37195767Skensmith/* 38195767Skensmith * Routines to build and maintain radix trees for routing lookups. 39195767Skensmith */ 40195767Skensmith#ifndef _RADIX_H_ 41195767Skensmith#include <sys/param.h> 42195767Skensmith#ifdef _KERNEL 43195767Skensmith#include <sys/systm.h> 44195767Skensmith#include <sys/malloc.h> 45195767Skensmith#define M_DONTWAIT M_NOWAIT 46195767Skensmith#include <sys/domain.h> 47195767Skensmith#else 48195767Skensmith#include <stdlib.h> 49195767Skensmith#endif 50195767Skensmith#include <sys/syslog.h> 51195767Skensmith#include <net/radix.h> 52195767Skensmith#endif 53195767Skensmith 54195767Skensmithstatic int rn_walktree_from __P((struct radix_node_head *h, void *a, 55195767Skensmith void *m, walktree_f_t *f, void *w)); 56195767Skensmithstatic int rn_walktree __P((struct radix_node_head *, walktree_f_t *, void *)); 57195767Skensmithstatic struct radix_node 58195767Skensmith *rn_insert __P((void *, struct radix_node_head *, int *, 59195767Skensmith struct radix_node [2])), 60195767Skensmith *rn_newpair __P((void *, int, struct radix_node[2])), 61195767Skensmith *rn_search __P((void *, struct radix_node *)), 62195767Skensmith *rn_search_m __P((void *, struct radix_node *, void *)); 63195767Skensmith 64195767Skensmithstatic int max_keylen; 65195767Skensmithstatic struct radix_mask *rn_mkfreelist; 66195767Skensmithstatic struct radix_node_head *mask_rnhead; 67195767Skensmithstatic char *addmask_key; 68195767Skensmithstatic char normal_chars[] = {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1}; 69195767Skensmithstatic char *rn_zeros, *rn_ones; 70195767Skensmith 71195767Skensmith#define rn_masktop (mask_rnhead->rnh_treetop) 72195767Skensmith#undef Bcmp 73195767Skensmith#define Bcmp(a, b, l) \ 74195767Skensmith (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l)) 75195767Skensmith 76195767Skensmithstatic int rn_lexobetter __P((void *m_arg, void *n_arg)); 77195767Skensmithstatic struct radix_mask * 78195767Skensmith rn_new_radix_mask __P((struct radix_node *tt, 79195767Skensmith struct radix_mask *next)); 80195767Skensmithstatic int rn_satsifies_leaf __P((char *trial, struct radix_node *leaf, 81195767Skensmith int skip)); 82195767Skensmith 83195767Skensmith/* 84195767Skensmith * The data structure for the keys is a radix tree with one way 85195767Skensmith * branching removed. The index rn_bit at an internal node n represents a bit 86195767Skensmith * position to be tested. The tree is arranged so that all descendants 87195767Skensmith * of a node n have keys whose bits all agree up to position rn_bit - 1. 88195767Skensmith * (We say the index of n is rn_bit.) 89195767Skensmith * 90195767Skensmith * There is at least one descendant which has a one bit at position rn_bit, 91195767Skensmith * and at least one with a zero there. 92195767Skensmith * 93195767Skensmith * A route is determined by a pair of key and mask. We require that the 94195767Skensmith * bit-wise logical and of the key and mask to be the key. 95195767Skensmith * We define the index of a route to associated with the mask to be 96195767Skensmith * the first bit number in the mask where 0 occurs (with bit number 0 97195767Skensmith * representing the highest order bit). 98195767Skensmith * 99195767Skensmith * We say a mask is normal if every bit is 0, past the index of the mask. 100195767Skensmith * If a node n has a descendant (k, m) with index(m) == index(n) == rn_bit, 101195767Skensmith * and m is a normal mask, then the route applies to every descendant of n. 102195767Skensmith * If the index(m) < rn_bit, this implies the trailing last few bits of k 103195767Skensmith * before bit b are all 0, (and hence consequently true of every descendant 104195767Skensmith * of n), so the route applies to all descendants of the node as well. 105195789Santoine * 106195767Skensmith * Similar logic shows that a non-normal mask m such that 107195767Skensmith * index(m) <= index(n) could potentially apply to many children of n. 108195767Skensmith * Thus, for each non-host route, we attach its mask to a list at an internal 109195767Skensmith * node as high in the tree as we can go. 110195767Skensmith * 111195767Skensmith * The present version of the code makes use of normal routes in short- 112195767Skensmith * circuiting an explict mask and compare operation when testing whether 113195767Skensmith * a key satisfies a normal route, and also in remembering the unique leaf 114195767Skensmith * that governs a subtree. 115195767Skensmith */ 116195767Skensmith 117195767Skensmithstatic struct radix_node * 118195767Skensmithrn_search(v_arg, head) 119195767Skensmith void *v_arg; 120195767Skensmith struct radix_node *head; 121195767Skensmith{ 122195767Skensmith register struct radix_node *x; 123195767Skensmith register caddr_t v; 124195767Skensmith 125195767Skensmith for (x = head, v = v_arg; x->rn_bit >= 0;) { 126195767Skensmith if (x->rn_bmask & v[x->rn_offset]) 127195767Skensmith x = x->rn_right; 128195767Skensmith else 129195767Skensmith x = x->rn_left; 130195767Skensmith } 131195767Skensmith return (x); 132195767Skensmith} 133195767Skensmith 134195767Skensmithstatic struct radix_node * 135195767Skensmithrn_search_m(v_arg, head, m_arg) 136195767Skensmith struct radix_node *head; 137195767Skensmith void *v_arg, *m_arg; 138195767Skensmith{ 139195767Skensmith register struct radix_node *x; 140195767Skensmith register caddr_t v = v_arg, m = m_arg; 141195767Skensmith 142195767Skensmith for (x = head; x->rn_bit >= 0;) { 143195767Skensmith if ((x->rn_bmask & m[x->rn_offset]) && 144195767Skensmith (x->rn_bmask & v[x->rn_offset])) 145195767Skensmith x = x->rn_right; 146195767Skensmith else 147195767Skensmith x = x->rn_left; 148195767Skensmith } 149195767Skensmith return x; 150195767Skensmith} 151195767Skensmith 152195767Skensmithint 153195767Skensmithrn_refines(m_arg, n_arg) 154195767Skensmith void *m_arg, *n_arg; 155195767Skensmith{ 156195767Skensmith register caddr_t m = m_arg, n = n_arg; 157195767Skensmith register caddr_t lim, lim2 = lim = n + *(u_char *)n; 158195767Skensmith int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); 159195767Skensmith int masks_are_equal = 1; 160195767Skensmith 161195767Skensmith if (longer > 0) 162195767Skensmith lim -= longer; 163195767Skensmith while (n < lim) { 164195767Skensmith if (*n & ~(*m)) 165195767Skensmith return 0; 166195767Skensmith if (*n++ != *m++) 167195767Skensmith masks_are_equal = 0; 168195767Skensmith } 169195767Skensmith while (n < lim2) 170195767Skensmith if (*n++) 171195767Skensmith return 0; 172195767Skensmith if (masks_are_equal && (longer < 0)) 173195767Skensmith for (lim2 = m - longer; m < lim2; ) 174195767Skensmith if (*m++) 175195767Skensmith return 1; 176195767Skensmith return (!masks_are_equal); 177195767Skensmith} 178195767Skensmith 179195767Skensmithstruct radix_node * 180195767Skensmithrn_lookup(v_arg, m_arg, head) 181195767Skensmith void *v_arg, *m_arg; 182195767Skensmith struct radix_node_head *head; 183195767Skensmith{ 184195767Skensmith register struct radix_node *x; 185195767Skensmith caddr_t netmask = 0; 186195767Skensmith 187195767Skensmith if (m_arg) { 188195767Skensmith x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_offset); 189195767Skensmith if (x == 0) 190195767Skensmith return (0); 191195767Skensmith netmask = x->rn_key; 192195767Skensmith } 193195767Skensmith x = rn_match(v_arg, head); 194195767Skensmith if (x && netmask) { 195195767Skensmith while (x && x->rn_mask != netmask) 196195767Skensmith x = x->rn_dupedkey; 197195767Skensmith } 198195767Skensmith return x; 199195767Skensmith} 200195767Skensmith 201195767Skensmithstatic int 202195767Skensmithrn_satsifies_leaf(trial, leaf, skip) 203195767Skensmith char *trial; 204195767Skensmith register struct radix_node *leaf; 205195767Skensmith int skip; 206195767Skensmith{ 207195767Skensmith register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; 208195767Skensmith char *cplim; 209195767Skensmith int length = min(*(u_char *)cp, *(u_char *)cp2); 210195767Skensmith 211195767Skensmith if (cp3 == 0) 212195767Skensmith cp3 = rn_ones; 213195767Skensmith else 214195767Skensmith length = min(length, *(u_char *)cp3); 215195767Skensmith cplim = cp + length; cp3 += skip; cp2 += skip; 216195767Skensmith for (cp += skip; cp < cplim; cp++, cp2++, cp3++) 217195767Skensmith if ((*cp ^ *cp2) & *cp3) 218195767Skensmith return 0; 219195767Skensmith return 1; 220195767Skensmith} 221195767Skensmith 222195767Skensmithstruct radix_node * 223195767Skensmithrn_match(v_arg, head) 224195767Skensmith void *v_arg; 225195767Skensmith struct radix_node_head *head; 226195767Skensmith{ 227195767Skensmith caddr_t v = v_arg; 228195767Skensmith register struct radix_node *t = head->rnh_treetop, *x; 229195767Skensmith register caddr_t cp = v, cp2; 230195767Skensmith caddr_t cplim; 231195767Skensmith struct radix_node *saved_t, *top = t; 232195767Skensmith int off = t->rn_offset, vlen = *(u_char *)cp, matched_off; 233195767Skensmith register int test, b, rn_bit; 234195767Skensmith 235195767Skensmith /* 236195767Skensmith * Open code rn_search(v, top) to avoid overhead of extra 237195767Skensmith * subroutine call. 238195767Skensmith */ 239195767Skensmith for (; t->rn_bit >= 0; ) { 240195754Smarcus if (t->rn_bmask & cp[t->rn_offset]) 241195754Smarcus t = t->rn_right; 242195699Srwatson else 243195699Srwatson t = t->rn_left; 244195699Srwatson } 245195699Srwatson /* 246195789Santoine * See if we match exactly as a host destination 247195789Santoine * or at least learn how many bits match, for normal mask finesse. 248195789Santoine * 249195789Santoine * It doesn't hurt us to limit how many bytes to check 250195656Strasz * to the length of the mask, since if it matches we had a genuine 251195656Strasz * match and the leaf we have is the most specific one anyway; 252195656Strasz * if it didn't match with a shorter length it would fail 253195656Strasz * with a long one. This wins big for class B&C netmasks which 254195656Strasz * are probably the most common case... 255195230Sdfr */ 256195230Sdfr if (t->rn_mask) 257194860Sthompsa vlen = *(u_char *)t->rn_mask; 258195096Santoine cp += off; cp2 = t->rn_key + off; cplim = v + vlen; 259195096Santoine for (; cp < cplim; cp++, cp2++) 260195096Santoine if (*cp != *cp2) 261195096Santoine goto on1; 262195096Santoine /* 263195096Santoine * This extra grot is in case we are explicitly asked 264195096Santoine * to look up the default. Ugh! 265195096Santoine * 266195096Santoine * Never return the root node itself, it seems to cause a 267195096Santoine * lot of confusion. 268195096Santoine */ 269195096Santoine if (t->rn_flags & RNF_ROOT) 270195096Santoine t = t->rn_dupedkey; 271195096Santoine return t; 272195096Santoineon1: 273195096Santoine test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ 274195096Santoine for (b = 7; (test >>= 1) > 0;) 275195096Santoine b--; 276195096Santoine matched_off = cp - v; 277195096Santoine b += matched_off << 3; 278195096Santoine rn_bit = -1 - b; 279195096Santoine /* 280195096Santoine * If there is a host route in a duped-key chain, it will be first. 281195096Santoine */ 282195096Santoine if ((saved_t = t)->rn_mask == 0) 283195096Santoine t = t->rn_dupedkey; 284195096Santoine for (; t; t = t->rn_dupedkey) 285195096Santoine /* 286195096Santoine * Even if we don't match exactly as a host, 287195096Santoine * we may match if the leaf we wound up at is 288195096Santoine * a route to a net. 289195096Santoine */ 290195096Santoine if (t->rn_flags & RNF_NORMAL) { 291195096Santoine if (rn_bit <= t->rn_bit) 292195096Santoine return t; 293195096Santoine } else if (rn_satsifies_leaf(v, t, matched_off)) 294195096Santoine return t; 295195096Santoine t = saved_t; 296195096Santoine /* start searching up the tree */ 297195096Santoine do { 298195096Santoine register struct radix_mask *m; 299195096Santoine t = t->rn_parent; 300195096Santoine m = t->rn_mklist; 301195096Santoine /* 302195096Santoine * If non-contiguous masks ever become important 303195096Santoine * we can restore the masking and open coding of 304195096Santoine * the search and satisfaction test and put the 305195096Santoine * calculation of "off" back before the "do". 306195096Santoine */ 307195096Santoine while (m) { 308195096Santoine if (m->rm_flags & RNF_NORMAL) { 309195096Santoine if (rn_bit <= m->rm_bit) 310195096Santoine return (m->rm_leaf); 311195096Santoine } else { 312195096Santoine off = min(t->rn_offset, matched_off); 313195096Santoine x = rn_search_m(v, t, m->rm_mask); 314195096Santoine while (x && x->rn_mask != m->rm_mask) 315195096Santoine x = x->rn_dupedkey; 316195096Santoine if (x && rn_satsifies_leaf(v, x, off)) 317193513Sed return x; 318193513Sed } 319193308Sed m = m->rm_mklist; 320193308Sed } 321193308Sed } while (t != top); 322195096Santoine return 0; 323195096Santoine} 324193113Sdougb 325193113Sdougb#ifdef RN_DEBUG 326192926Sedint rn_nodenum; 327192926Sedstruct radix_node *rn_clist; 328192926Sedint rn_saveinfo; 329192901Sthompsaint rn_debug = 1; 330192901Sthompsa#endif 331192901Sthompsa 332192901Sthompsastatic struct radix_node * 333192901Sthompsarn_newpair(v, b, nodes) 334192901Sthompsa void *v; 335192901Sthompsa int b; 336192901Sthompsa struct radix_node nodes[2]; 337192901Sthompsa{ 338192901Sthompsa register struct radix_node *tt = nodes, *t = tt + 1; 339192901Sthompsa t->rn_bit = b; 340192901Sthompsa t->rn_bmask = 0x80 >> (b & 7); 341192901Sthompsa t->rn_left = tt; 342192901Sthompsa t->rn_offset = b >> 3; 343192901Sthompsa tt->rn_bit = -1; 344192901Sthompsa tt->rn_key = (caddr_t)v; 345192901Sthompsa tt->rn_parent = t; 346192901Sthompsa tt->rn_flags = t->rn_flags = RNF_ACTIVE; 347192901Sthompsa tt->rn_mklist = t->rn_mklist = 0; 348192901Sthompsa#ifdef RN_DEBUG 349192901Sthompsa tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 350192901Sthompsa tt->rn_twin = t; 351192901Sthompsa tt->rn_ybro = rn_clist; 352192901Sthompsa rn_clist = tt; 353192901Sthompsa#endif 354192901Sthompsa return t; 355192901Sthompsa} 356192901Sthompsa 357192901Sthompsastatic struct radix_node * 358192901Sthompsarn_insert(v_arg, head, dupentry, nodes) 359192901Sthompsa void *v_arg; 360192901Sthompsa struct radix_node_head *head; 361192901Sthompsa int *dupentry; 362192916Sdougb struct radix_node nodes[2]; 363195096Santoine{ 364192916Sdougb caddr_t v = v_arg; 365192580Srwatson struct radix_node *top = head->rnh_treetop; 366192580Srwatson int head_off = top->rn_offset, vlen = (int)*((u_char *)v); 367192580Srwatson register struct radix_node *t = rn_search(v_arg, top); 368192580Srwatson register caddr_t cp = v + head_off; 369192650Santoine register int b; 370192580Srwatson struct radix_node *tt; 371192650Santoine /* 372192650Santoine * Find first bit at which v and t->rn_key differ 373192650Santoine */ 374191250Santoine { 375191250Santoine register caddr_t cp2 = t->rn_key + head_off; 376191250Santoine register int cmp_res; 377191250Santoine caddr_t cplim = v + vlen; 378191250Santoine 379191250Santoine while (cp < cplim) 380191250Santoine if (*cp2++ != *cp++) 381191250Santoine goto on1; 382191250Santoine *dupentry = 1; 383191250Santoine return t; 384191250Santoineon1: 385191250Santoine *dupentry = 0; 386191250Santoine cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; 387191250Santoine for (b = (cp - v) << 3; cmp_res; b--) 388191250Santoine cmp_res >>= 1; 389191146Smaxim } 390191146Smaxim { 391191146Smaxim register struct radix_node *p, *x = top; 392191146Smaxim cp = v; 393191146Smaxim do { 394191146Smaxim p = x; 395190894Sdanger if (cp[x->rn_offset] & x->rn_bmask) 396190905Sdanger x = x->rn_right; 397191250Santoine else 398191250Santoine x = x->rn_left; 399190751Sed } while (b > (unsigned) x->rn_bit); 400190864Sru /* x->rn_bit < b && x->rn_bit >= 0 */ 401190864Sru#ifdef RN_DEBUG 402190751Sed if (rn_debug) 403190751Sed log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); 404190751Sed#endif 405190751Sed t = rn_newpair(v_arg, b, nodes); 406190751Sed tt = t->rn_left; 407190751Sed if ((cp[p->rn_offset] & p->rn_bmask) == 0) 408190864Sru p->rn_left = t; 409190751Sed else 410190751Sed p->rn_right = t; 411190751Sed x->rn_parent = t; 412190751Sed t->rn_parent = p; /* frees x, p as temp vars below */ 413190751Sed if ((cp[t->rn_offset] & t->rn_bmask) == 0) { 414190751Sed t->rn_right = x; 415190751Sed } else { 416190751Sed t->rn_right = tt; 417190751Sed t->rn_left = x; 418190751Sed } 419190864Sru#ifdef RN_DEBUG 420190751Sed if (rn_debug) 421190864Sru log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); 422190772Sru#endif 423190772Sru } 424190772Sru return (tt); 425190772Sru} 426190772Sru 427190100Sthompsastruct radix_node * 428190100Sthompsarn_addmask(n_arg, search, skip) 429189977Sbrueffer int search, skip; 430189977Sbrueffer void *n_arg; 431189585Sthompsa{ 432189585Sthompsa caddr_t netmask = (caddr_t)n_arg; 433189607Sthompsa register struct radix_node *x; 434189607Sthompsa register caddr_t cp, cplim; 435189607Sthompsa register int b = 0, mlen, j; 436189585Sthompsa int maskduplicated, m0, isnormal; 437191250Santoine struct radix_node *saved_x; 438190772Sru static int last_zeroed = 0; 439190772Sru 440190772Sru if ((mlen = *(u_char *)netmask) > max_keylen) 441190772Sru mlen = max_keylen; 442190772Sru if (skip == 0) 443190772Sru skip = 1; 444189092Sed if (mlen <= skip) 445189092Sed return (mask_rnhead->rnh_nodes); 446190772Sru if (skip > 1) 447190772Sru Bcopy(rn_ones + 1, addmask_key + 1, skip - 1); 448190772Sru if ((m0 = mlen) > skip) 449188948Sthompsa Bcopy(netmask + skip, addmask_key + skip, mlen - skip); 450189000Sthompsa /* 451189000Sthompsa * Trim trailing zeroes. 452189000Sthompsa */ 453189000Sthompsa for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) 454189000Sthompsa cp--; 455189000Sthompsa mlen = cp - addmask_key; 456189000Sthompsa if (mlen <= skip) { 457189000Sthompsa if (m0 >= last_zeroed) 458189000Sthompsa last_zeroed = mlen; 459189000Sthompsa return (mask_rnhead->rnh_nodes); 460189000Sthompsa } 461189000Sthompsa if (m0 < last_zeroed) 462189000Sthompsa Bzero(addmask_key + m0, last_zeroed - m0); 463189000Sthompsa *addmask_key = last_zeroed = mlen; 464188948Sthompsa x = rn_search(addmask_key, rn_masktop); 465188948Sthompsa if (Bcmp(addmask_key, x->rn_key, mlen) != 0) 466188948Sthompsa x = 0; 467188948Sthompsa if (x || search) 468188948Sthompsa return (x); 469188948Sthompsa R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); 470188948Sthompsa if ((saved_x = x) == 0) 471188948Sthompsa return (0); 472188948Sthompsa Bzero(x, max_keylen + 2 * sizeof (*x)); 473188948Sthompsa netmask = cp = (caddr_t)(x + 2); 474188948Sthompsa Bcopy(addmask_key, cp, mlen); 475188948Sthompsa x = rn_insert(cp, mask_rnhead, &maskduplicated, x); 476188948Sthompsa if (maskduplicated) { 477188948Sthompsa log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); 478188948Sthompsa Free(saved_x); 479188948Sthompsa return (x); 480188948Sthompsa } 481191250Santoine /* 482191250Santoine * Calculate index of mask, and check for normalcy. 483188948Sthompsa */ 484188948Sthompsa cplim = netmask + mlen; isnormal = 1; 485188948Sthompsa for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) 486188948Sthompsa cp++; 487188948Sthompsa if (cp != cplim) { 488188948Sthompsa for (j = 0x80; (j & *cp) != 0; j >>= 1) 489188948Sthompsa b++; 490188948Sthompsa if (*cp != normal_chars[b] || cp != (cplim - 1)) 491188948Sthompsa isnormal = 0; 492188948Sthompsa } 493188948Sthompsa b += (cp - netmask) << 3; 494188948Sthompsa x->rn_bit = -1 - b; 495188948Sthompsa if (isnormal) 496188948Sthompsa x->rn_flags |= RNF_NORMAL; 497188948Sthompsa return (x); 498188948Sthompsa} 499188948Sthompsa 500188948Sthompsastatic int /* XXX: arbitrary ordering for non-contiguous masks */ 501188948Sthompsarn_lexobetter(m_arg, n_arg) 502188948Sthompsa void *m_arg, *n_arg; 503188948Sthompsa{ 504188948Sthompsa register u_char *mp = m_arg, *np = n_arg, *lim; 505188948Sthompsa 506188652Sed if (*mp > *np) 507188652Sed return 1; /* not really, but need to check longer one first */ 508188652Sed if (*mp == *np) 509188652Sed for (lim = mp + *mp; mp < lim;) 510188102Sgabor if (*mp++ > *np++) 511188102Sgabor return 1; 512187694Santoine return 0; 513187694Santoine} 514187694Santoine 515187694Santoinestatic struct radix_mask * 516187694Santoinern_new_radix_mask(tt, next) 517186716Santoine register struct radix_node *tt; 518186716Santoine register struct radix_mask *next; 519186437Sbz{ 520186437Sbz register struct radix_mask *m; 521185472Santoine 522185472Santoine MKGet(m); 523185472Santoine if (m == 0) { 524185472Santoine log(LOG_ERR, "Mask for route not entered\n"); 525185472Santoine return (0); 526183442Sed } 527183442Sed Bzero(m, sizeof *m); 528183442Sed m->rm_bit = tt->rn_bit; 529183442Sed m->rm_flags = tt->rn_flags; 530183442Sed if (tt->rn_flags & RNF_NORMAL) 531183442Sed m->rm_leaf = tt; 532183113Sattilio else 533183235Santoine m->rm_mask = tt->rn_mask; 534183235Santoine m->rm_mklist = next; 535183026Santoine tt->rn_mklist = m; 536183026Santoine return m; 537182105Sed} 538182105Sed 539182518Santoinestruct radix_node * 540182518Santoinern_addroute(v_arg, n_arg, head, treenodes) 541182518Santoine void *v_arg, *n_arg; 542182518Santoine struct radix_node_head *head; 543182518Santoine struct radix_node treenodes[2]; 544182518Santoine{ 545182518Santoine caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; 546182518Santoine register struct radix_node *t, *x = 0, *tt; 547182518Santoine struct radix_node *saved_tt, *top = head->rnh_treetop; 548182518Santoine short b = 0, b_leaf = 0; 549182518Santoine int keyduplicated; 550182518Santoine caddr_t mmask; 551182518Santoine struct radix_mask *m, **mp; 552182518Santoine 553182518Santoine /* 554182518Santoine * In dealing with non-contiguous masks, there may be 555182518Santoine * many different routes which have the same mask. 556182518Santoine * We will find it useful to have a unique pointer to 557181905Sed * the mask to speed avoiding duplicate references at 558181905Sed * nodes and possibly save time in calculating indices. 559181905Sed */ 560180800Sed if (netmask) { 561180800Sed if ((x = rn_addmask(netmask, 0, top->rn_offset)) == 0) 562180614Smarcel return (0); 563180614Smarcel b_leaf = x->rn_bit; 564180614Smarcel b = -1 - x->rn_bit; 565180614Smarcel netmask = x->rn_key; 566180614Smarcel } 567180614Smarcel /* 568180331Smarcel * Deal with duplicated keys: attach node to previous instance 569180331Smarcel */ 570180331Smarcel saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); 571180331Smarcel if (keyduplicated) { 572180331Smarcel for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { 573180267Sjhb if (tt->rn_mask == netmask) 574180267Sjhb return (0); 575180267Sjhb if (netmask == 0 || 576180265Sjhb (tt->rn_mask && 577180265Sjhb ((b_leaf < tt->rn_bit) /* index(netmask) > node */ 578180265Sjhb || rn_refines(netmask, tt->rn_mask) 579180259Sjhb || rn_lexobetter(netmask, tt->rn_mask)))) 580180259Sjhb break; 581180259Sjhb } 582180259Sjhb /* 583180259Sjhb * If the mask is not duplicated, we wouldn't 584180257Sjhb * find it among possible duplicate key entries 585180257Sjhb * anyway, so the above test doesn't hurt. 586180257Sjhb * 587180259Sjhb * We sort the masks for a duplicated key the same way as 588180257Sjhb * in a masklist -- most specific to least specific. 589180257Sjhb * This may require the unfortunate nuisance of relocating 590180248Smarcel * the head of the list. 591180248Smarcel */ 592180248Smarcel if (tt == saved_tt) { 593180248Smarcel struct radix_node *xx = x; 594180248Smarcel /* link in at head of list */ 595180230Smarcel (tt = treenodes)->rn_dupedkey = t; 596180230Smarcel tt->rn_flags = t->rn_flags; 597180230Smarcel tt->rn_parent = x = t->rn_parent; 598180230Smarcel t->rn_parent = tt; /* parent */ 599180230Smarcel if (x->rn_left == t) 600180230Smarcel x->rn_left = tt; 601180230Smarcel else 602180230Smarcel x->rn_right = tt; 603180159Sdanger saved_tt = tt; x = xx; 604180159Sdanger } else { 605180159Sdanger (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; 606180496Santoine t->rn_dupedkey = tt; 607180496Santoine tt->rn_parent = t; /* parent */ 608180496Santoine if (tt->rn_dupedkey) /* parent */ 609180496Santoine tt->rn_dupedkey->rn_parent = tt; /* parent */ 610179784Sed } 611179784Sed#ifdef RN_DEBUG 612179784Sed t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; 613179784Sed tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; 614179784Sed#endif 615179692Smarcel tt->rn_key = (caddr_t) v; 616179692Smarcel tt->rn_bit = -1; 617179692Smarcel tt->rn_flags = RNF_ACTIVE; 618179315Sbz } 619179315Sbz /* 620179315Sbz * Put mask in tree. 621179315Sbz */ 622179315Sbz if (netmask) { 623179315Sbz tt->rn_mask = netmask; 624179315Sbz tt->rn_bit = x->rn_bit; 625179315Sbz tt->rn_flags |= x->rn_flags & RNF_NORMAL; 626179315Sbz } 627179315Sbz t = saved_tt->rn_parent; 628179315Sbz if (keyduplicated) 629179315Sbz goto on2; 630179315Sbz b_leaf = -1 - t->rn_bit; 631179315Sbz if (t->rn_right == saved_tt) 632179315Sbz x = t->rn_left; 633179315Sbz else 634179315Sbz x = t->rn_right; 635179315Sbz /* Promote general routes from below */ 636179315Sbz if (x->rn_bit < 0) { 637179315Sbz for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) 638179315Sbz if (x->rn_mask && (x->rn_bit >= b_leaf) && x->rn_mklist == 0) { 639179315Sbz *mp = m = rn_new_radix_mask(x, 0); 640179315Sbz if (m) 641179315Sbz mp = &m->rm_mklist; 642179315Sbz } 643179315Sbz } else if (x->rn_mklist) { 644179315Sbz /* 645179315Sbz * Skip over masks whose index is > that of new node 646179315Sbz */ 647179315Sbz for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 648179315Sbz if (m->rm_bit >= b_leaf) 649179315Sbz break; 650179315Sbz t->rn_mklist = m; *mp = 0; 651179315Sbz } 652179315Sbzon2: 653179315Sbz /* Add new route to highest possible ancestor's list */ 654179315Sbz if ((netmask == 0) || (b > t->rn_bit )) 655179315Sbz return tt; /* can't lift at all */ 656179315Sbz b_leaf = tt->rn_bit; 657179315Sbz do { 658179315Sbz x = t; 659179315Sbz t = t->rn_parent; 660179315Sbz } while (b <= t->rn_bit && x != top); 661179315Sbz /* 662179315Sbz * Search through routes associated with node to 663179315Sbz * insert new route according to index. 664179315Sbz * Need same criteria as when sorting dupedkeys to avoid 665179315Sbz * double loop on deletion. 666179315Sbz */ 667179315Sbz for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { 668179315Sbz if (m->rm_bit < b_leaf) 669179315Sbz continue; 670179315Sbz if (m->rm_bit > b_leaf) 671179315Sbz break; 672179315Sbz if (m->rm_flags & RNF_NORMAL) { 673179315Sbz mmask = m->rm_leaf->rn_mask; 674179315Sbz if (tt->rn_flags & RNF_NORMAL) { 675179315Sbz log(LOG_ERR, 676179315Sbz "Non-unique normal route, mask not entered"); 677179315Sbz return tt; 678179315Sbz } 679179315Sbz } else 680179315Sbz mmask = m->rm_mask; 681179315Sbz if (mmask == netmask) { 682179315Sbz m->rm_refs++; 683179315Sbz tt->rn_mklist = m; 684179315Sbz return tt; 685179315Sbz } 686179315Sbz if (rn_refines(netmask, mmask) 687179315Sbz || rn_lexobetter(netmask, mmask)) 688179315Sbz break; 689179315Sbz } 690179315Sbz *mp = rn_new_radix_mask(tt, *mp); 691179315Sbz return tt; 692179315Sbz} 693179315Sbz 694179315Sbzstruct radix_node * 695179315Sbzrn_delete(v_arg, netmask_arg, head) 696179315Sbz void *v_arg, *netmask_arg; 697179315Sbz struct radix_node_head *head; 698179315Sbz{ 699179315Sbz register struct radix_node *t, *p, *x, *tt; 700179315Sbz struct radix_mask *m, *saved_m, **mp; 701179315Sbz struct radix_node *dupedkey, *saved_tt, *top; 702179315Sbz caddr_t v, netmask; 703179315Sbz int b, head_off, vlen; 704179315Sbz 705179315Sbz v = v_arg; 706179315Sbz netmask = netmask_arg; 707179315Sbz x = head->rnh_treetop; 708179315Sbz tt = rn_search(v, x); 709179315Sbz head_off = x->rn_offset; 710179315Sbz vlen = *(u_char *)v; 711179315Sbz saved_tt = tt; 712179315Sbz top = x; 713179315Sbz if (tt == 0 || 714179315Sbz Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) 715179315Sbz return (0); 716179315Sbz /* 717179315Sbz * Delete our route from mask lists. 718179315Sbz */ 719179315Sbz if (netmask) { 720179315Sbz if ((x = rn_addmask(netmask, 1, head_off)) == 0) 721179315Sbz return (0); 722179315Sbz netmask = x->rn_key; 723179315Sbz while (tt->rn_mask != netmask) 724179315Sbz if ((tt = tt->rn_dupedkey) == 0) 725179315Sbz return (0); 726179315Sbz } 727179315Sbz if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) 728179315Sbz goto on1; 729179315Sbz if (tt->rn_flags & RNF_NORMAL) { 730179315Sbz if (m->rm_leaf != tt || m->rm_refs > 0) { 731179315Sbz log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 732179361Santoine return 0; /* dangling ref could cause disaster */ 733179361Santoine } 734179361Santoine } else { 735179361Santoine if (m->rm_mask != tt->rn_mask) { 736179361Santoine log(LOG_ERR, "rn_delete: inconsistent annotation\n"); 737179361Santoine goto on1; 738179361Santoine } 739179361Santoine if (--m->rm_refs >= 0) 740179361Santoine goto on1; 741179361Santoine } 742179361Santoine b = -1 - tt->rn_bit; 743179361Santoine t = saved_tt->rn_parent; 744179361Santoine if (b > t->rn_bit) 745179361Santoine goto on1; /* Wasn't lifted at all */ 746179361Santoine do { 747179361Santoine x = t; 748179361Santoine t = t->rn_parent; 749179361Santoine } while (b <= t->rn_bit && x != top); 750179361Santoine for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) 751179361Santoine if (m == saved_m) { 752178924Santoine *mp = m->rm_mklist; 753178924Santoine MKFree(m); 754178924Santoine break; 755178924Santoine } 756178924Santoine if (m == 0) { 757177831Sflz log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); 758177831Sflz if (tt->rn_flags & RNF_NORMAL) 759177831Sflz return (0); /* Dangling ref to us */ 760177831Sflz } 761177831Sflzon1: 762178331Santoine /* 763178331Santoine * Eliminate us from tree 764178331Santoine */ 765178331Santoine if (tt->rn_flags & RNF_ROOT) 766178331Santoine return (0); 767178331Santoine#ifdef RN_DEBUG 768178331Santoine /* Get us out of the creation list */ 769178331Santoine for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} 770178331Santoine if (t) t->rn_ybro = tt->rn_ybro; 771178331Santoine#endif 772178331Santoine t = tt->rn_parent; 773178331Santoine dupedkey = saved_tt->rn_dupedkey; 774178331Santoine if (dupedkey) { 775178331Santoine /* 776178331Santoine * at this point, tt is the deletion target and saved_tt 777178331Santoine * is the head of the dupekey chain 778178924Santoine */ 779178924Santoine if (tt == saved_tt) { 780178924Santoine /* remove from head of chain */ 781178924Santoine x = dupedkey; x->rn_parent = t; 782176422Sthompsa if (t->rn_left == tt) 783176422Sthompsa t->rn_left = x; 784175690Sbrueffer else 785175690Sbrueffer t->rn_right = x; 786175690Sbrueffer } else { 787175576Sattilio /* find node in front of tt on the chain */ 788175576Sattilio for (x = p = saved_tt; p && p->rn_dupedkey != tt;) 789175227Sjhb p = p->rn_dupedkey; 790175227Sjhb if (p) { 791175227Sjhb p->rn_dupedkey = tt->rn_dupedkey; 792174426Sdougb if (tt->rn_dupedkey) /* parent */ 793174426Sdougb tt->rn_dupedkey->rn_parent = p; 794174426Sdougb /* parent */ 795177153Sbrueffer } else log(LOG_ERR, "rn_delete: couldn't find us\n"); 796177153Sbrueffer } 797174092Sbrooks t = tt + 1; 798174092Sbrooks if (t->rn_flags & RNF_ACTIVE) { 799174092Sbrooks#ifndef RN_DEBUG 800174092Sbrooks *++x = *t; 801176956Santoine p = t->rn_parent; 802176956Santoine#else 803176956Santoine b = t->rn_info; 804176956Santoine *++x = *t; 805174092Sbrooks t->rn_info = b; 806174061Sjb p = t->rn_parent; 807174061Sjb#endif 808175227Sjhb if (p->rn_left == t) 809175227Sjhb p->rn_left = x; 810173466Simp else 811173466Simp p->rn_right = x; 812173662Smarcel x->rn_left->rn_parent = x; 813173662Smarcel x->rn_right->rn_parent = x; 814173662Smarcel } 815173662Smarcel goto out; 816173662Smarcel } 817173662Smarcel if (t->rn_left == tt) 818172983Smtm x = t->rn_right; 819172983Smtm else 820172390Sbushman x = t->rn_left; 821173176Sbushman p = t->rn_parent; 822172390Sbushman if (p->rn_right == t) 823172390Sbushman p->rn_right = x; 824172570Sru else 825172570Sru p->rn_left = x; 826171786Smarcel x->rn_parent = p; 827171786Smarcel /* 828171786Smarcel * Demote routes attached to us. 829171786Smarcel */ 830171696Sbz if (t->rn_mklist) { 831171696Sbz if (x->rn_bit >= 0) { 832179368Sbz for (mp = &x->rn_mklist; (m = *mp);) 833171461Srwatson mp = &m->rm_mklist; 834171461Srwatson *mp = t->rn_mklist; 835171461Srwatson } else { 836171461Srwatson /* If there are any key,mask pairs in a sibling 837171461Srwatson duped-key chain, some subset will appear sorted 838171461Srwatson in the same order attached to our mklist */ 839171461Srwatson for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) 840171461Srwatson if (m == x->rn_mklist) { 841171461Srwatson struct radix_mask *mm = m->rm_mklist; 842171461Srwatson x->rn_mklist = 0; 843171461Srwatson if (--(m->rm_refs) < 0) 844171461Srwatson MKFree(m); 845171461Srwatson m = mm; 846171461Srwatson } 847171461Srwatson if (m) 848171461Srwatson log(LOG_ERR, 849171461Srwatson "rn_delete: Orphaned Mask %p at %p\n", 850171461Srwatson (void *)m, (void *)x); 851171461Srwatson } 852171461Srwatson } 853171461Srwatson /* 854171461Srwatson * We may be holding an active internal node in the tree. 855171461Srwatson */ 856171461Srwatson x = tt + 1; 857171461Srwatson if (t != x) { 858171461Srwatson#ifndef RN_DEBUG 859171461Srwatson *t = *x; 860171461Srwatson#else 861171461Srwatson b = t->rn_info; 862171461Srwatson *t = *x; 863171461Srwatson t->rn_info = b; 864171461Srwatson#endif 865171461Srwatson t->rn_left->rn_parent = t; 866171461Srwatson t->rn_right->rn_parent = t; 867171461Srwatson p = x->rn_parent; 868171461Srwatson if (p->rn_left == x) 869171461Srwatson p->rn_left = t; 870171461Srwatson else 871171461Srwatson p->rn_right = t; 872171461Srwatson } 873171461Srwatsonout: 874171461Srwatson tt->rn_flags &= ~RNF_ACTIVE; 875171461Srwatson tt[1].rn_flags &= ~RNF_ACTIVE; 876171461Srwatson return (tt); 877171461Srwatson} 878171461Srwatson 879171461Srwatson/* 880171461Srwatson * This is the same as rn_walktree() except for the parameters and the 881171461Srwatson * exit. 882171461Srwatson */ 883171461Srwatsonstatic int 884171461Srwatsonrn_walktree_from(h, a, m, f, w) 885171461Srwatson struct radix_node_head *h; 886171461Srwatson void *a, *m; 887171461Srwatson walktree_f_t *f; 888171461Srwatson void *w; 889171461Srwatson{ 890171461Srwatson int error; 891171461Srwatson struct radix_node *base, *next; 892171461Srwatson u_char *xa = (u_char *)a; 893171461Srwatson u_char *xm = (u_char *)m; 894171461Srwatson register struct radix_node *rn, *last = 0 /* shut up gcc */; 895171461Srwatson int stopping = 0; 896171461Srwatson int lastb; 897171461Srwatson 898171461Srwatson /* 899171461Srwatson * rn_search_m is sort-of-open-coded here. 900171461Srwatson */ 901171461Srwatson /* printf("about to search\n"); */ 902171461Srwatson for (rn = h->rnh_treetop; rn->rn_bit >= 0; ) { 903171461Srwatson last = rn; 904171461Srwatson /* printf("rn_bit %d, rn_bmask %x, xm[rn_offset] %x\n", 905176956Santoine rn->rn_bit, rn->rn_bmask, xm[rn->rn_offset]); */ 906176956Santoine if (!(rn->rn_bmask & xm[rn->rn_offset])) { 907176956Santoine break; 908176956Santoine } 909176956Santoine if (rn->rn_bmask & xa[rn->rn_offset]) { 910176956Santoine rn = rn->rn_right; 911171274Sbz } else { 912171274Sbz rn = rn->rn_left; 913171274Sbz } 914171274Sbz } 915171274Sbz /* printf("done searching\n"); */ 916171274Sbz 917171274Sbz /* 918171274Sbz * Two cases: either we stepped off the end of our mask, 919171274Sbz * in which case last == rn, or we reached a leaf, in which 920179368Sbz * case we want to start from the last node we looked at. 921171205Sbz * Either way, last is the node we want to start from. 922171205Sbz */ 923171205Sbz rn = last; 924171205Sbz lastb = rn->rn_bit; 925171205Sbz 926171175Smlaier /* printf("rn %p, lastb %d\n", rn, lastb);*/ 927171175Smlaier 928171137Sbz /* 929171137Sbz * This gets complicated because we may delete the node 930171137Sbz * while applying the function f to it, so we need to calculate 931171137Sbz * the successor node in advance. 932171137Sbz */ 933171137Sbz while (rn->rn_bit >= 0) 934171137Sbz rn = rn->rn_left; 935171137Sbz 936171137Sbz while (!stopping) { 937171137Sbz /* printf("node %p (%d)\n", rn, rn->rn_bit); */ 938171137Sbz base = rn; 939171137Sbz /* If at right child go back up, otherwise, go right */ 940171137Sbz while (rn->rn_parent->rn_right == rn 941171137Sbz && !(rn->rn_flags & RNF_ROOT)) { 942171137Sbz rn = rn->rn_parent; 943171137Sbz 944171137Sbz /* if went up beyond last, stop */ 945171137Sbz if (rn->rn_bit < lastb) { 946171137Sbz stopping = 1; 947171131Sthompsa /* printf("up too far\n"); */ 948171131Sthompsa } 949171143Sthompsa } 950171023Srafan 951171023Srafan /* Find the next *leaf* since next node might vanish, too */ 952171023Srafan for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 953171023Srafan rn = rn->rn_left; 954171023Srafan next = rn; 955171023Srafan /* Process leaves */ 956171388Sdougb while ((rn = base) != 0) { 957171388Sdougb base = rn->rn_dupedkey; 958171388Sdougb /* printf("leaf %p\n", rn); */ 959171388Sdougb if (!(rn->rn_flags & RNF_ROOT) 960170926Srafan && (error = (*f)(rn, w))) 961170926Srafan return (error); 962170926Srafan } 963170926Srafan rn = next; 964170926Srafan 965170926Srafan if (rn->rn_flags & RNF_ROOT) { 966170926Srafan /* printf("root, stopping"); */ 967170926Srafan stopping = 1; 968170926Srafan } 969170926Srafan 970170926Srafan } 971170926Srafan return 0; 972170926Srafan} 973170926Srafan 974170926Srafanstatic int 975170926Srafanrn_walktree(h, f, w) 976170926Srafan struct radix_node_head *h; 977170926Srafan walktree_f_t *f; 978170926Srafan void *w; 979170926Srafan{ 980170926Srafan int error; 981170926Srafan struct radix_node *base, *next; 982170926Srafan register struct radix_node *rn = h->rnh_treetop; 983170926Srafan /* 984170926Srafan * This gets complicated because we may delete the node 985170926Srafan * while applying the function f to it, so we need to calculate 986170926Srafan * the successor node in advance. 987170926Srafan */ 988170926Srafan /* First time through node, go left */ 989170926Srafan while (rn->rn_bit >= 0) 990170926Srafan rn = rn->rn_left; 991170926Srafan for (;;) { 992170926Srafan base = rn; 993170926Srafan /* If at right child go back up, otherwise, go right */ 994170926Srafan while (rn->rn_parent->rn_right == rn 995170926Srafan && (rn->rn_flags & RNF_ROOT) == 0) 996170926Srafan rn = rn->rn_parent; 997170926Srafan /* Find the next *leaf* since next node might vanish, too */ 998170926Srafan for (rn = rn->rn_parent->rn_right; rn->rn_bit >= 0;) 999170926Srafan rn = rn->rn_left; 1000170926Srafan next = rn; 1001176956Santoine /* Process leaves */ 1002176956Santoine while ((rn = base)) { 1003176956Santoine base = rn->rn_dupedkey; 1004176956Santoine if (!(rn->rn_flags & RNF_ROOT) 1005176956Santoine && (error = (*f)(rn, w))) 1006176956Santoine return (error); 1007176956Santoine } 1008176956Santoine rn = next; 1009176956Santoine if (rn->rn_flags & RNF_ROOT) 1010176956Santoine return (0); 1011176956Santoine } 1012176956Santoine /* NOTREACHED */ 1013176956Santoine} 1014176956Santoine 1015176956Santoineint 1016176956Santoinern_inithead(head, off) 1017176956Santoine void **head; 1018176956Santoine int off; 1019176956Santoine{ 1020176956Santoine register struct radix_node_head *rnh; 1021176956Santoine register struct radix_node *t, *tt, *ttt; 1022176956Santoine if (*head) 1023176956Santoine return (1); 1024176956Santoine R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh)); 1025176956Santoine if (rnh == 0) 1026176956Santoine return (0); 1027176956Santoine Bzero(rnh, sizeof (*rnh)); 1028176956Santoine *head = rnh; 1029176956Santoine t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); 1030176956Santoine ttt = rnh->rnh_nodes + 2; 1031176956Santoine t->rn_right = ttt; 1032176956Santoine t->rn_parent = t; 1033176956Santoine tt = t->rn_left; 1034176956Santoine tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; 1035176956Santoine tt->rn_bit = -1 - off; 1036176956Santoine *ttt = *tt; 1037171476Sdelphij ttt->rn_key = rn_ones; 1038171476Sdelphij rnh->rnh_addaddr = rn_addroute; 1039170312Sdelphij rnh->rnh_deladdr = rn_delete; 1040170312Sdelphij rnh->rnh_matchaddr = rn_match; 1041170926Srafan rnh->rnh_lookup = rn_lookup; 1042173816Sru rnh->rnh_walktree = rn_walktree; 1043169815Sdelphij rnh->rnh_walktree_from = rn_walktree_from; 1044169815Sdelphij rnh->rnh_treetop = t; 1045169815Sdelphij return (1); 1046169815Sdelphij} 1047169815Sdelphij 1048169815Sdelphijvoid 1049169815Sdelphijrn_init() 1050169815Sdelphij{ 1051169815Sdelphij char *cp, *cplim; 1052169815Sdelphij#ifdef _KERNEL 1053169815Sdelphij struct domain *dom; 1054169815Sdelphij 1055170204Sru for (dom = domains; dom; dom = dom->dom_next) 1056169815Sdelphij if (dom->dom_maxrtkey > max_keylen) 1057169815Sdelphij max_keylen = dom->dom_maxrtkey; 1058169815Sdelphij#endif 1059169815Sdelphij if (max_keylen == 0) { 1060170204Sru log(LOG_ERR, 1061169815Sdelphij "rn_init: radix functions require max_keylen be set\n"); 1062169815Sdelphij return; 1063169815Sdelphij } 1064169815Sdelphij R_Malloc(rn_zeros, char *, 3 * max_keylen); 1065169815Sdelphij if (rn_zeros == NULL) 1066169815Sdelphij panic("rn_init"); 1067169815Sdelphij Bzero(rn_zeros, 3 * max_keylen); 1068169815Sdelphij rn_ones = cp = rn_zeros + max_keylen; 1069169815Sdelphij addmask_key = cplim = rn_ones + max_keylen; 1070169815Sdelphij while (cp < cplim) 1071169815Sdelphij *cp++ = -1; 1072169815Sdelphij if (rn_inithead((void **)&mask_rnhead, 0) == 0) 1073169815Sdelphij panic("rn_init 2"); 1074169815Sdelphij} 1075169815Sdelphij