![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to radix.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple Darwin 0.x] / kernel / bsd / net|
Return to radix.c CVS log | Up to [Apple Darwin 0.x] / kernel / bsd / net |
1.1 ! root 1: /* ! 2: * Copyright (c) 1999 Apple Computer, Inc. All rights reserved. ! 3: * ! 4: * @APPLE_LICENSE_HEADER_START@ ! 5: * ! 6: * Portions Copyright (c) 1999 Apple Computer, Inc. All Rights ! 7: * Reserved. This file contains Original Code and/or Modifications of ! 8: * Original Code as defined in and that are subject to the Apple Public ! 9: * Source License Version 1.1 (the "License"). You may not use this file ! 10: * except in compliance with the License. Please obtain a copy of the ! 11: * License at http://www.apple.com/publicsource and read it before using ! 12: * this file. ! 13: * ! 14: * The Original Code and all software distributed under the License are ! 15: * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER ! 16: * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, ! 17: * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, ! 18: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the ! 19: * License for the specific language governing rights and limitations ! 20: * under the License. ! 21: * ! 22: * @APPLE_LICENSE_HEADER_END@ ! 23: */ ! 24: ! 25: /* Copyright (c) 1995 NeXT Computer, Inc. All Rights Reserved */ ! 26: /* ! 27: * Copyright (c) 1988, 1989, 1993 ! 28: * The Regents of the University of California. All rights reserved. ! 29: * ! 30: * Redistribution and use in source and binary forms, with or without ! 31: * modification, are permitted provided that the following conditions ! 32: * are met: ! 33: * 1. Redistributions of source code must retain the above copyright ! 34: * notice, this list of conditions and the following disclaimer. ! 35: * 2. Redistributions in binary form must reproduce the above copyright ! 36: * notice, this list of conditions and the following disclaimer in the ! 37: * documentation and/or other materials provided with the distribution. ! 38: * 3. All advertising materials mentioning features or use of this software ! 39: * must display the following acknowledgement: ! 40: * This product includes software developed by the University of ! 41: * California, Berkeley and its contributors. ! 42: * 4. Neither the name of the University nor the names of its contributors ! 43: * may be used to endorse or promote products derived from this software ! 44: * without specific prior written permission. ! 45: * ! 46: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ! 47: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE ! 48: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ! 49: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE ! 50: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL ! 51: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS ! 52: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) ! 53: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT ! 54: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY ! 55: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF ! 56: * SUCH DAMAGE. ! 57: * ! 58: * @(#)radix.c 8.5 (Berkeley) 5/19/95 ! 59: */ ! 60: ! 61: /* ! 62: * Routines to build and maintain radix trees for routing lookups. ! 63: */ ! 64: #ifndef _RADIX_H_ ! 65: #include <sys/param.h> ! 66: #ifdef KERNEL ! 67: #include <sys/systm.h> ! 68: #include <sys/malloc.h> ! 69: #define M_DONTWAIT M_NOWAIT ! 70: #include <sys/domain.h> ! 71: #else ! 72: #include <stdlib.h> ! 73: #endif ! 74: #include <sys/syslog.h> ! 75: #include <net/radix.h> ! 76: #endif ! 77: ! 78: int max_keylen; ! 79: struct radix_mask *rn_mkfreelist; ! 80: struct radix_node_head *mask_rnhead; ! 81: static char *addmask_key; ! 82: static char normal_chars[] = {0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, -1}; ! 83: static char *rn_zeros, *rn_ones; ! 84: ! 85: #define rn_masktop (mask_rnhead->rnh_treetop) ! 86: #undef Bcmp ! 87: #define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l)) ! 88: /* ! 89: * The data structure for the keys is a radix tree with one way ! 90: * branching removed. The index rn_b at an internal node n represents a bit ! 91: * position to be tested. The tree is arranged so that all descendants ! 92: * of a node n have keys whose bits all agree up to position rn_b - 1. ! 93: * (We say the index of n is rn_b.) ! 94: * ! 95: * There is at least one descendant which has a one bit at position rn_b, ! 96: * and at least one with a zero there. ! 97: * ! 98: * A route is determined by a pair of key and mask. We require that the ! 99: * bit-wise logical and of the key and mask to be the key. ! 100: * We define the index of a route to associated with the mask to be ! 101: * the first bit number in the mask where 0 occurs (with bit number 0 ! 102: * representing the highest order bit). ! 103: * ! 104: * We say a mask is normal if every bit is 0, past the index of the mask. ! 105: * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b, ! 106: * and m is a normal mask, then the route applies to every descendant of n. ! 107: * If the index(m) < rn_b, this implies the trailing last few bits of k ! 108: * before bit b are all 0, (and hence consequently true of every descendant ! 109: * of n), so the route applies to all descendants of the node as well. ! 110: * ! 111: * Similar logic shows that a non-normal mask m such that ! 112: * index(m) <= index(n) could potentially apply to many children of n. ! 113: * Thus, for each non-host route, we attach its mask to a list at an internal ! 114: * node as high in the tree as we can go. ! 115: * ! 116: * The present version of the code makes use of normal routes in short- ! 117: * circuiting an explict mask and compare operation when testing whether ! 118: * a key satisfies a normal route, and also in remembering the unique leaf ! 119: * that governs a subtree. ! 120: */ ! 121: ! 122: struct radix_node * ! 123: rn_search(v_arg, head) ! 124: void *v_arg; ! 125: struct radix_node *head; ! 126: { ! 127: register struct radix_node *x; ! 128: register caddr_t v; ! 129: ! 130: for (x = head, v = v_arg; x->rn_b >= 0;) { ! 131: if (x->rn_bmask & v[x->rn_off]) ! 132: x = x->rn_r; ! 133: else ! 134: x = x->rn_l; ! 135: } ! 136: return (x); ! 137: }; ! 138: ! 139: struct radix_node * ! 140: rn_search_m(v_arg, head, m_arg) ! 141: struct radix_node *head; ! 142: void *v_arg, *m_arg; ! 143: { ! 144: register struct radix_node *x; ! 145: register caddr_t v = v_arg, m = m_arg; ! 146: ! 147: for (x = head; x->rn_b >= 0;) { ! 148: if ((x->rn_bmask & m[x->rn_off]) && ! 149: (x->rn_bmask & v[x->rn_off])) ! 150: x = x->rn_r; ! 151: else ! 152: x = x->rn_l; ! 153: } ! 154: return x; ! 155: }; ! 156: ! 157: int ! 158: rn_refines(m_arg, n_arg) ! 159: void *m_arg, *n_arg; ! 160: { ! 161: register caddr_t m = m_arg, n = n_arg; ! 162: register caddr_t lim, lim2 = lim = n + *(u_char *)n; ! 163: int longer = (*(u_char *)n++) - (int)(*(u_char *)m++); ! 164: int masks_are_equal = 1; ! 165: ! 166: if (longer > 0) ! 167: lim -= longer; ! 168: while (n < lim) { ! 169: if (*n & ~(*m)) ! 170: return 0; ! 171: if (*n++ != *m++) ! 172: masks_are_equal = 0; ! 173: } ! 174: while (n < lim2) ! 175: if (*n++) ! 176: return 0; ! 177: if (masks_are_equal && (longer < 0)) ! 178: for (lim2 = m - longer; m < lim2; ) ! 179: if (*m++) ! 180: return 1; ! 181: return (!masks_are_equal); ! 182: } ! 183: ! 184: struct radix_node * ! 185: rn_lookup(v_arg, m_arg, head) ! 186: void *v_arg, *m_arg; ! 187: struct radix_node_head *head; ! 188: { ! 189: register struct radix_node *x; ! 190: caddr_t netmask = 0; ! 191: ! 192: if (m_arg) { ! 193: if ((x = rn_addmask(m_arg, 1, head->rnh_treetop->rn_off)) == 0) ! 194: return (0); ! 195: netmask = x->rn_key; ! 196: } ! 197: x = rn_match(v_arg, head); ! 198: if (x && netmask) { ! 199: while (x && x->rn_mask != netmask) ! 200: x = x->rn_dupedkey; ! 201: } ! 202: return x; ! 203: } ! 204: ! 205: static int ! 206: rn_satsifies_leaf(trial, leaf, skip) ! 207: char *trial; ! 208: register struct radix_node *leaf; ! 209: int skip; ! 210: { ! 211: register char *cp = trial, *cp2 = leaf->rn_key, *cp3 = leaf->rn_mask; ! 212: char *cplim; ! 213: int length = min(*(u_char *)cp, *(u_char *)cp2); ! 214: ! 215: if (cp3 == 0) ! 216: cp3 = rn_ones; ! 217: else ! 218: length = min(length, *(u_char *)cp3); ! 219: cplim = cp + length; cp3 += skip; cp2 += skip; ! 220: for (cp += skip; cp < cplim; cp++, cp2++, cp3++) ! 221: if ((*cp ^ *cp2) & *cp3) ! 222: return 0; ! 223: return 1; ! 224: } ! 225: ! 226: struct radix_node * ! 227: rn_match(v_arg, head) ! 228: void *v_arg; ! 229: struct radix_node_head *head; ! 230: { ! 231: caddr_t v = v_arg; ! 232: register struct radix_node *t = head->rnh_treetop, *x; ! 233: register caddr_t cp = v, cp2; ! 234: caddr_t cplim; ! 235: struct radix_node *saved_t, *top = t; ! 236: int off = t->rn_off, vlen = *(u_char *)cp, matched_off; ! 237: register int test, b, rn_b; ! 238: ! 239: /* ! 240: * Open code rn_search(v, top) to avoid overhead of extra ! 241: * subroutine call. ! 242: */ ! 243: for (; t->rn_b >= 0; ) { ! 244: if (t->rn_bmask & cp[t->rn_off]) ! 245: t = t->rn_r; ! 246: else ! 247: t = t->rn_l; ! 248: } ! 249: /* ! 250: * See if we match exactly as a host destination ! 251: * or at least learn how many bits match, for normal mask finesse. ! 252: * ! 253: * It doesn't hurt us to limit how many bytes to check ! 254: * to the length of the mask, since if it matches we had a genuine ! 255: * match and the leaf we have is the most specific one anyway; ! 256: * if it didn't match with a shorter length it would fail ! 257: * with a long one. This wins big for class B&C netmasks which ! 258: * are probably the most common case... ! 259: */ ! 260: if (t->rn_mask) ! 261: vlen = *(u_char *)t->rn_mask; ! 262: cp += off; cp2 = t->rn_key + off; cplim = v + vlen; ! 263: for (; cp < cplim; cp++, cp2++) ! 264: if (*cp != *cp2) ! 265: goto on1; ! 266: /* ! 267: * This extra grot is in case we are explicitly asked ! 268: * to look up the default. Ugh! ! 269: */ ! 270: if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey) ! 271: t = t->rn_dupedkey; ! 272: return t; ! 273: on1: ! 274: test = (*cp ^ *cp2) & 0xff; /* find first bit that differs */ ! 275: for (b = 7; (test >>= 1) > 0;) ! 276: b--; ! 277: matched_off = cp - v; ! 278: b += matched_off << 3; ! 279: rn_b = -1 - b; ! 280: /* ! 281: * If there is a host route in a duped-key chain, it will be first. ! 282: */ ! 283: if ((saved_t = t)->rn_mask == 0) ! 284: t = t->rn_dupedkey; ! 285: for (; t; t = t->rn_dupedkey) ! 286: /* ! 287: * Even if we don't match exactly as a host, ! 288: * we may match if the leaf we wound up at is ! 289: * a route to a net. ! 290: */ ! 291: if (t->rn_flags & RNF_NORMAL) { ! 292: if (rn_b <= t->rn_b) ! 293: return t; ! 294: } else if (rn_satsifies_leaf(v, t, matched_off)) ! 295: return t; ! 296: t = saved_t; ! 297: /* start searching up the tree */ ! 298: do { ! 299: register struct radix_mask *m; ! 300: t = t->rn_p; ! 301: m = t->rn_mklist; ! 302: if (m) { ! 303: /* ! 304: * If non-contiguous masks ever become important ! 305: * we can restore the masking and open coding of ! 306: * the search and satisfaction test and put the ! 307: * calculation of "off" back before the "do". ! 308: */ ! 309: do { ! 310: if (m->rm_flags & RNF_NORMAL) { ! 311: if (rn_b <= m->rm_b) ! 312: return (m->rm_leaf); ! 313: } else { ! 314: off = min(t->rn_off, matched_off); ! 315: x = rn_search_m(v, t, m->rm_mask); ! 316: while (x && x->rn_mask != m->rm_mask) ! 317: x = x->rn_dupedkey; ! 318: if (x && rn_satsifies_leaf(v, x, off)) ! 319: return x; ! 320: } ! 321: m = m->rm_mklist; ! 322: } while (m); ! 323: } ! 324: } while (t != top); ! 325: return 0; ! 326: }; ! 327: ! 328: #ifdef RN_DEBUG ! 329: int rn_nodenum; ! 330: struct radix_node *rn_clist; ! 331: int rn_saveinfo; ! 332: int rn_debug = 1; ! 333: #endif ! 334: ! 335: struct radix_node * ! 336: rn_newpair(v, b, nodes) ! 337: void *v; ! 338: int b; ! 339: struct radix_node nodes[2]; ! 340: { ! 341: register struct radix_node *tt = nodes, *t = tt + 1; ! 342: t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7); ! 343: t->rn_l = tt; t->rn_off = b >> 3; ! 344: tt->rn_b = -1; tt->rn_key = (caddr_t)v; tt->rn_p = t; ! 345: tt->rn_flags = t->rn_flags = RNF_ACTIVE; ! 346: #ifdef RN_DEBUG ! 347: tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; ! 348: tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; ! 349: #endif ! 350: return t; ! 351: } ! 352: ! 353: struct radix_node * ! 354: rn_insert(v_arg, head, dupentry, nodes) ! 355: void *v_arg; ! 356: struct radix_node_head *head; ! 357: int *dupentry; ! 358: struct radix_node nodes[2]; ! 359: { ! 360: caddr_t v = v_arg; ! 361: struct radix_node *top = head->rnh_treetop; ! 362: int head_off = top->rn_off, vlen = (int)*((u_char *)v); ! 363: register struct radix_node *t = rn_search(v_arg, top); ! 364: register caddr_t cp = v + head_off; ! 365: register int b; ! 366: struct radix_node *tt; ! 367: /* ! 368: * Find first bit at which v and t->rn_key differ ! 369: */ ! 370: { ! 371: register caddr_t cp2 = t->rn_key + head_off; ! 372: register int cmp_res; ! 373: caddr_t cplim = v + vlen; ! 374: ! 375: while (cp < cplim) ! 376: if (*cp2++ != *cp++) ! 377: goto on1; ! 378: *dupentry = 1; ! 379: return t; ! 380: on1: ! 381: *dupentry = 0; ! 382: cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; ! 383: for (b = (cp - v) << 3; cmp_res; b--) ! 384: cmp_res >>= 1; ! 385: } ! 386: { ! 387: register struct radix_node *p, *x = top; ! 388: cp = v; ! 389: do { ! 390: p = x; ! 391: if (cp[x->rn_off] & x->rn_bmask) ! 392: x = x->rn_r; ! 393: else x = x->rn_l; ! 394: } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */ ! 395: #ifdef RN_DEBUG ! 396: if (rn_debug) ! 397: log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); ! 398: #endif ! 399: t = rn_newpair(v_arg, b, nodes); tt = t->rn_l; ! 400: if ((cp[p->rn_off] & p->rn_bmask) == 0) ! 401: p->rn_l = t; ! 402: else ! 403: p->rn_r = t; ! 404: x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */ ! 405: if ((cp[t->rn_off] & t->rn_bmask) == 0) { ! 406: t->rn_r = x; ! 407: } else { ! 408: t->rn_r = tt; t->rn_l = x; ! 409: } ! 410: #ifdef RN_DEBUG ! 411: if (rn_debug) ! 412: log(LOG_DEBUG, "rn_insert: Coming Out:\n"), traverse(p); ! 413: #endif ! 414: } ! 415: return (tt); ! 416: } ! 417: ! 418: struct radix_node * ! 419: rn_addmask(n_arg, search, skip) ! 420: int search, skip; ! 421: void *n_arg; ! 422: { ! 423: caddr_t netmask = (caddr_t)n_arg; ! 424: register struct radix_node *x; ! 425: register caddr_t cp, cplim; ! 426: register int b = 0, mlen, j; ! 427: int maskduplicated, m0, isnormal; ! 428: struct radix_node *saved_x; ! 429: static int last_zeroed = 0; ! 430: ! 431: if ((mlen = *(u_char *)netmask) > max_keylen) ! 432: mlen = max_keylen; ! 433: if (skip == 0) ! 434: skip = 1; ! 435: if (mlen <= skip) ! 436: return (mask_rnhead->rnh_nodes); ! 437: if (skip > 1) ! 438: Bcopy(rn_ones + 1, addmask_key + 1, skip - 1); ! 439: if ((m0 = mlen) > skip) ! 440: Bcopy(netmask + skip, addmask_key + skip, mlen - skip); ! 441: /* ! 442: * Trim trailing zeroes. ! 443: */ ! 444: for (cp = addmask_key + mlen; (cp > addmask_key) && cp[-1] == 0;) ! 445: cp--; ! 446: mlen = cp - addmask_key; ! 447: if (mlen <= skip) { ! 448: if (m0 >= last_zeroed) ! 449: last_zeroed = mlen; ! 450: return (mask_rnhead->rnh_nodes); ! 451: } ! 452: if (m0 < last_zeroed) ! 453: Bzero(addmask_key + m0, last_zeroed - m0); ! 454: *addmask_key = last_zeroed = mlen; ! 455: x = rn_search(addmask_key, rn_masktop); ! 456: if (Bcmp(addmask_key, x->rn_key, mlen) != 0) ! 457: x = 0; ! 458: if (x || search) ! 459: return (x); ! 460: R_Malloc(x, struct radix_node *, max_keylen + 2 * sizeof (*x)); ! 461: if ((saved_x = x) == 0) ! 462: return (0); ! 463: Bzero(x, max_keylen + 2 * sizeof (*x)); ! 464: netmask = cp = (caddr_t)(x + 2); ! 465: Bcopy(addmask_key, cp, mlen); ! 466: x = rn_insert(cp, mask_rnhead, &maskduplicated, x); ! 467: if (maskduplicated) { ! 468: log(LOG_ERR, "rn_addmask: mask impossibly already in tree"); ! 469: Free(saved_x); ! 470: return (x); ! 471: } ! 472: /* ! 473: * Calculate index of mask, and check for normalcy. ! 474: */ ! 475: cplim = netmask + mlen; isnormal = 1; ! 476: for (cp = netmask + skip; (cp < cplim) && *(u_char *)cp == 0xff;) ! 477: cp++; ! 478: if (cp != cplim) { ! 479: for (j = 0x80; (j & *cp) != 0; j >>= 1) ! 480: b++; ! 481: if (*cp != normal_chars[b] || cp != (cplim - 1)) ! 482: isnormal = 0; ! 483: } ! 484: b += (cp - netmask) << 3; ! 485: x->rn_b = -1 - b; ! 486: if (isnormal) ! 487: x->rn_flags |= RNF_NORMAL; ! 488: return (x); ! 489: } ! 490: ! 491: static int /* XXX: arbitrary ordering for non-contiguous masks */ ! 492: rn_lexobetter(m_arg, n_arg) ! 493: void *m_arg, *n_arg; ! 494: { ! 495: register u_char *mp = m_arg, *np = n_arg, *lim; ! 496: ! 497: if (*mp > *np) ! 498: return 1; /* not really, but need to check longer one first */ ! 499: if (*mp == *np) ! 500: for (lim = mp + *mp; mp < lim;) ! 501: if (*mp++ > *np++) ! 502: return 1; ! 503: return 0; ! 504: } ! 505: ! 506: static struct radix_mask * ! 507: rn_new_radix_mask(tt, next) ! 508: register struct radix_node *tt; ! 509: register struct radix_mask *next; ! 510: { ! 511: register struct radix_mask *m; ! 512: ! 513: MKGet(m); ! 514: if (m == 0) { ! 515: log(LOG_ERR, "Mask for route not entered\n"); ! 516: return (0); ! 517: } ! 518: Bzero(m, sizeof *m); ! 519: m->rm_b = tt->rn_b; ! 520: m->rm_flags = tt->rn_flags; ! 521: if (tt->rn_flags & RNF_NORMAL) ! 522: m->rm_leaf = tt; ! 523: else ! 524: m->rm_mask = tt->rn_mask; ! 525: m->rm_mklist = next; ! 526: tt->rn_mklist = m; ! 527: return m; ! 528: } ! 529: ! 530: struct radix_node * ! 531: rn_addroute(v_arg, n_arg, head, treenodes) ! 532: void *v_arg, *n_arg; ! 533: struct radix_node_head *head; ! 534: struct radix_node treenodes[2]; ! 535: { ! 536: caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; ! 537: register struct radix_node *t, *x = 0, *tt; ! 538: struct radix_node *saved_tt, *top = head->rnh_treetop; ! 539: short b = 0, b_leaf = 0; ! 540: int keyduplicated; ! 541: caddr_t mmask; ! 542: struct radix_mask *m, **mp; ! 543: ! 544: /* ! 545: * In dealing with non-contiguous masks, there may be ! 546: * many different routes which have the same mask. ! 547: * We will find it useful to have a unique pointer to ! 548: * the mask to speed avoiding duplicate references at ! 549: * nodes and possibly save time in calculating indices. ! 550: */ ! 551: if (netmask) { ! 552: if ((x = rn_addmask(netmask, 0, top->rn_off)) == 0) ! 553: return (0); ! 554: b_leaf = x->rn_b; ! 555: b = -1 - x->rn_b; ! 556: netmask = x->rn_key; ! 557: } ! 558: /* ! 559: * Deal with duplicated keys: attach node to previous instance ! 560: */ ! 561: saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); ! 562: if (keyduplicated) { ! 563: for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { ! 564: if (tt->rn_mask == netmask) ! 565: return (0); ! 566: if (netmask == 0 || ! 567: (tt->rn_mask && ! 568: ((b_leaf < tt->rn_b) || /* index(netmask) > node */ ! 569: rn_refines(netmask, tt->rn_mask) || ! 570: rn_lexobetter(netmask, tt->rn_mask)))) ! 571: break; ! 572: } ! 573: /* ! 574: * If the mask is not duplicated, we wouldn't ! 575: * find it among possible duplicate key entries ! 576: * anyway, so the above test doesn't hurt. ! 577: * ! 578: * We sort the masks for a duplicated key the same way as ! 579: * in a masklist -- most specific to least specific. ! 580: * This may require the unfortunate nuisance of relocating ! 581: * the head of the list. ! 582: * ! 583: * We also reverse, or doubly link the list through the ! 584: * parent pointer. ! 585: */ ! 586: if (tt == saved_tt) { ! 587: struct radix_node *xx = x; ! 588: /* link in at head of list */ ! 589: (tt = treenodes)->rn_dupedkey = t; ! 590: tt->rn_flags = t->rn_flags; ! 591: tt->rn_p = x = t->rn_p; ! 592: t->rn_p = tt; ! 593: if (x->rn_l == t) x->rn_l = tt; else x->rn_r = tt; ! 594: saved_tt = tt; x = xx; ! 595: } else { ! 596: (tt = treenodes)->rn_dupedkey = t->rn_dupedkey; ! 597: t->rn_dupedkey = tt; ! 598: tt->rn_p = t; ! 599: if (tt->rn_dupedkey) ! 600: tt->rn_dupedkey->rn_p = tt; ! 601: } ! 602: #ifdef RN_DEBUG ! 603: t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; ! 604: tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; ! 605: #endif ! 606: tt->rn_key = (caddr_t) v; ! 607: tt->rn_b = -1; ! 608: tt->rn_flags = RNF_ACTIVE; ! 609: } ! 610: /* ! 611: * Put mask in tree. ! 612: */ ! 613: if (netmask) { ! 614: tt->rn_mask = netmask; ! 615: tt->rn_b = x->rn_b; ! 616: tt->rn_flags |= x->rn_flags & RNF_NORMAL; ! 617: } ! 618: t = saved_tt->rn_p; ! 619: if (keyduplicated) ! 620: goto on2; ! 621: b_leaf = -1 - t->rn_b; ! 622: if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r; ! 623: /* Promote general routes from below */ ! 624: if (x->rn_b < 0) { ! 625: for (mp = &t->rn_mklist; x; x = x->rn_dupedkey) ! 626: if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) { ! 627: *mp = m = rn_new_radix_mask(x, 0); ! 628: if (m) ! 629: mp = &m->rm_mklist; ! 630: } ! 631: } else if (x->rn_mklist) { ! 632: /* ! 633: * Skip over masks whose index is > that of new node ! 634: */ ! 635: for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) ! 636: if (m->rm_b >= b_leaf) ! 637: break; ! 638: t->rn_mklist = m; *mp = 0; ! 639: } ! 640: on2: ! 641: /* Add new route to highest possible ancestor's list */ ! 642: if ((netmask == 0) || (b > t->rn_b )) ! 643: return tt; /* can't lift at all */ ! 644: b_leaf = tt->rn_b; ! 645: do { ! 646: x = t; ! 647: t = t->rn_p; ! 648: } while (b <= t->rn_b && x != top); ! 649: /* ! 650: * Search through routes associated with node to ! 651: * insert new route according to index. ! 652: * Need same criteria as when sorting dupedkeys to avoid ! 653: * double loop on deletion. ! 654: */ ! 655: for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) { ! 656: if (m->rm_b < b_leaf) ! 657: continue; ! 658: if (m->rm_b > b_leaf) ! 659: break; ! 660: if (m->rm_flags & RNF_NORMAL) { ! 661: mmask = m->rm_leaf->rn_mask; ! 662: if (tt->rn_flags & RNF_NORMAL) { ! 663: log(LOG_ERR, ! 664: "Non-unique normal route, mask not entered"); ! 665: return tt; ! 666: } ! 667: } else ! 668: mmask = m->rm_mask; ! 669: if (mmask == netmask) { ! 670: m->rm_refs++; ! 671: tt->rn_mklist = m; ! 672: return tt; ! 673: } ! 674: if (rn_refines(netmask, mmask) || rn_lexobetter(netmask, mmask)) ! 675: break; ! 676: } ! 677: *mp = rn_new_radix_mask(tt, *mp); ! 678: return tt; ! 679: } ! 680: ! 681: struct radix_node * ! 682: rn_delete(v_arg, netmask_arg, head) ! 683: void *v_arg, *netmask_arg; ! 684: struct radix_node_head *head; ! 685: { ! 686: register struct radix_node *t, *p, *x, *tt; ! 687: struct radix_mask *m, *saved_m, **mp; ! 688: struct radix_node *dupedkey, *saved_tt, *top; ! 689: caddr_t v, netmask; ! 690: int b, head_off, vlen; ! 691: ! 692: v = v_arg; ! 693: netmask = netmask_arg; ! 694: x = head->rnh_treetop; ! 695: tt = rn_search(v, x); ! 696: head_off = x->rn_off; ! 697: vlen = *(u_char *)v; ! 698: saved_tt = tt; ! 699: top = x; ! 700: if (tt == 0 || ! 701: Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) ! 702: return (0); ! 703: /* ! 704: * Delete our route from mask lists. ! 705: */ ! 706: if (netmask) { ! 707: if ((x = rn_addmask(netmask, 1, head_off)) == 0) ! 708: return (0); ! 709: netmask = x->rn_key; ! 710: while (tt->rn_mask != netmask) ! 711: if ((tt = tt->rn_dupedkey) == 0) ! 712: return (0); ! 713: } ! 714: if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) ! 715: goto on1; ! 716: if (tt->rn_flags & RNF_NORMAL) { ! 717: if (m->rm_leaf != tt || m->rm_refs > 0) { ! 718: log(LOG_ERR, "rn_delete: inconsistent annotation\n"); ! 719: return 0; /* dangling ref could cause disaster */ ! 720: } ! 721: } else { ! 722: if (m->rm_mask != tt->rn_mask) { ! 723: log(LOG_ERR, "rn_delete: inconsistent annotation\n"); ! 724: goto on1; ! 725: } ! 726: if (--m->rm_refs >= 0) ! 727: goto on1; ! 728: } ! 729: b = -1 - tt->rn_b; ! 730: t = saved_tt->rn_p; ! 731: if (b > t->rn_b) ! 732: goto on1; /* Wasn't lifted at all */ ! 733: do { ! 734: x = t; ! 735: t = t->rn_p; ! 736: } while (b <= t->rn_b && x != top); ! 737: for (mp = &x->rn_mklist; (m = *mp); mp = &m->rm_mklist) ! 738: if (m == saved_m) { ! 739: *mp = m->rm_mklist; ! 740: MKFree(m); ! 741: break; ! 742: } ! 743: if (m == 0) { ! 744: log(LOG_ERR, "rn_delete: couldn't find our annotation\n"); ! 745: if (tt->rn_flags & RNF_NORMAL) ! 746: return (0); /* Dangling ref to us */ ! 747: } ! 748: on1: ! 749: /* ! 750: * Eliminate us from tree ! 751: */ ! 752: if (tt->rn_flags & RNF_ROOT) ! 753: return (0); ! 754: #ifdef RN_DEBUG ! 755: /* Get us out of the creation list */ ! 756: for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} ! 757: if (t) t->rn_ybro = tt->rn_ybro; ! 758: #endif ! 759: t = tt->rn_p; ! 760: dupedkey = saved_tt->rn_dupedkey; ! 761: if (dupedkey) { ! 762: /* ! 763: * Here, tt is the deletion target, and ! 764: * saved_tt is the head of the dupedkey chain. ! 765: */ ! 766: if (tt == saved_tt) { ! 767: x = dupedkey; x->rn_p = t; ! 768: if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x; ! 769: } else { ! 770: /* find node in front of tt on the chain */ ! 771: for (x = p = saved_tt; p && p->rn_dupedkey != tt;) ! 772: p = p->rn_dupedkey; ! 773: if (p) { ! 774: p->rn_dupedkey = tt->rn_dupedkey; ! 775: if (tt->rn_dupedkey) ! 776: tt->rn_dupedkey->rn_p = p; ! 777: } else log(LOG_ERR, "rn_delete: couldn't find us\n"); ! 778: } ! 779: t = tt + 1; ! 780: if (t->rn_flags & RNF_ACTIVE) { ! 781: #ifndef RN_DEBUG ! 782: *++x = *t; p = t->rn_p; ! 783: #else ! 784: b = t->rn_info; *++x = *t; t->rn_info = b; p = t->rn_p; ! 785: #endif ! 786: if (p->rn_l == t) p->rn_l = x; else p->rn_r = x; ! 787: x->rn_l->rn_p = x; x->rn_r->rn_p = x; ! 788: } ! 789: goto out; ! 790: } ! 791: if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l; ! 792: p = t->rn_p; ! 793: if (p->rn_r == t) p->rn_r = x; else p->rn_l = x; ! 794: x->rn_p = p; ! 795: /* ! 796: * Demote routes attached to us. ! 797: */ ! 798: if (t->rn_mklist) { ! 799: if (x->rn_b >= 0) { ! 800: for (mp = &x->rn_mklist; (m = *mp);) ! 801: mp = &m->rm_mklist; ! 802: *mp = t->rn_mklist; ! 803: } else { ! 804: /* If there are any key,mask pairs in a sibling ! 805: duped-key chain, some subset will appear sorted ! 806: in the same order attached to our mklist */ ! 807: for (m = t->rn_mklist; m && x; x = x->rn_dupedkey) ! 808: if (m == x->rn_mklist) { ! 809: struct radix_mask *mm = m->rm_mklist; ! 810: x->rn_mklist = 0; ! 811: if (--(m->rm_refs) < 0) ! 812: MKFree(m); ! 813: m = mm; ! 814: } ! 815: if (m) ! 816: log(LOG_ERR, "%s %x at %x\n", ! 817: "rn_delete: Orphaned Mask", m, x); ! 818: } ! 819: } ! 820: /* ! 821: * We may be holding an active internal node in the tree. ! 822: */ ! 823: x = tt + 1; ! 824: if (t != x) { ! 825: #ifndef RN_DEBUG ! 826: *t = *x; ! 827: #else ! 828: b = t->rn_info; *t = *x; t->rn_info = b; ! 829: #endif ! 830: t->rn_l->rn_p = t; t->rn_r->rn_p = t; ! 831: p = x->rn_p; ! 832: if (p->rn_l == x) p->rn_l = t; else p->rn_r = t; ! 833: } ! 834: out: ! 835: tt->rn_flags &= ~RNF_ACTIVE; ! 836: tt[1].rn_flags &= ~RNF_ACTIVE; ! 837: return (tt); ! 838: } ! 839: ! 840: int ! 841: rn_walktree(h, f, w) ! 842: struct radix_node_head *h; ! 843: register int (*f)(); ! 844: void *w; ! 845: { ! 846: int error; ! 847: struct radix_node *base, *next; ! 848: register struct radix_node *rn = h->rnh_treetop; ! 849: /* ! 850: * This gets complicated because we may delete the node ! 851: * while applying the function f to it, so we need to calculate ! 852: * the successor node in advance. ! 853: */ ! 854: /* First time through node, go left */ ! 855: while (rn->rn_b >= 0) ! 856: rn = rn->rn_l; ! 857: for (;;) { ! 858: base = rn; ! 859: /* If at right child go back up, otherwise, go right */ ! 860: while (rn->rn_p->rn_r == rn && (rn->rn_flags & RNF_ROOT) == 0) ! 861: rn = rn->rn_p; ! 862: /* Find the next *leaf* since next node might vanish, too */ ! 863: for (rn = rn->rn_p->rn_r; rn->rn_b >= 0;) ! 864: rn = rn->rn_l; ! 865: next = rn; ! 866: /* Process leaves */ ! 867: while ((rn = base)) { ! 868: base = rn->rn_dupedkey; ! 869: if (!(rn->rn_flags & RNF_ROOT) && (error = (*f)(rn, w))) ! 870: return (error); ! 871: } ! 872: rn = next; ! 873: if (rn->rn_flags & RNF_ROOT) ! 874: return (0); ! 875: } ! 876: /* NOTREACHED */ ! 877: } ! 878: ! 879: int ! 880: rn_inithead(head, off) ! 881: void **head; ! 882: int off; ! 883: { ! 884: register struct radix_node_head *rnh; ! 885: register struct radix_node *t, *tt, *ttt; ! 886: if (*head) ! 887: return (1); ! 888: R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh)); ! 889: if (rnh == 0) ! 890: return (0); ! 891: Bzero(rnh, sizeof (*rnh)); ! 892: *head = rnh; ! 893: t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); ! 894: ttt = rnh->rnh_nodes + 2; ! 895: t->rn_r = ttt; ! 896: t->rn_p = t; ! 897: tt = t->rn_l; ! 898: tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; ! 899: tt->rn_b = -1 - off; ! 900: *ttt = *tt; ! 901: ttt->rn_key = rn_ones; ! 902: rnh->rnh_addaddr = rn_addroute; ! 903: rnh->rnh_deladdr = rn_delete; ! 904: rnh->rnh_matchaddr = rn_match; ! 905: rnh->rnh_lookup = rn_lookup; ! 906: rnh->rnh_walktree = rn_walktree; ! 907: rnh->rnh_treetop = t; ! 908: return (1); ! 909: } ! 910: ! 911: void ! 912: rn_init() ! 913: { ! 914: char *cp, *cplim; ! 915: #ifdef _KERNEL ! 916: struct domain *dom; ! 917: ! 918: for (dom = domains; dom; dom = dom->dom_next) ! 919: if (dom->dom_maxrtkey > max_keylen) ! 920: max_keylen = dom->dom_maxrtkey; ! 921: #endif ! 922: if (max_keylen == 0) { ! 923: log(LOG_ERR, ! 924: "rn_init: radix functions require max_keylen be set\n"); ! 925: return; ! 926: } ! 927: R_Malloc(rn_zeros, char *, 3 * max_keylen); ! 928: if (rn_zeros == NULL) ! 929: panic("rn_init"); ! 930: Bzero(rn_zeros, 3 * max_keylen); ! 931: rn_ones = cp = rn_zeros + max_keylen; ! 932: addmask_key = cplim = rn_ones + max_keylen; ! 933: while (cp < cplim) ! 934: *cp++ = -1; ! 935: if (rn_inithead((void **)&mask_rnhead, 0) == 0) ! 936: panic("rn_init 2"); ! 937: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.