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