![[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 [Net/2] / Net2 / net|
Return to radix.c CVS log | Up to [Net/2] / Net2 / net |
1.1 ! root 1: /* ! 2: * Copyright (c) 1988, 1989 Regents of the University of California. ! 3: * All rights reserved. ! 4: * ! 5: * Redistribution and use in source and binary forms, with or without ! 6: * modification, are permitted provided that the following conditions ! 7: * are met: ! 8: * 1. Redistributions of source code must retain the above copyright ! 9: * notice, this list of conditions and the following disclaimer. ! 10: * 2. Redistributions in binary form must reproduce the above copyright ! 11: * notice, this list of conditions and the following disclaimer in the ! 12: * documentation and/or other materials provided with the distribution. ! 13: * 3. All advertising materials mentioning features or use of this software ! 14: * must display the following acknowledgement: ! 15: * This product includes software developed by the University of ! 16: * California, Berkeley and its contributors. ! 17: * 4. Neither the name of the University nor the names of its contributors ! 18: * may be used to endorse or promote products derived from this software ! 19: * without specific prior written permission. ! 20: * ! 21: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND ! 22: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE ! 23: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ! 24: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE ! 25: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL ! 26: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS ! 27: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) ! 28: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT ! 29: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY ! 30: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF ! 31: * SUCH DAMAGE. ! 32: * ! 33: * @(#)radix.c 7.9 (Berkeley) 2/4/91 ! 34: */ ! 35: ! 36: /* ! 37: * Routines to build and maintain radix trees for routing lookups. ! 38: */ ! 39: #ifndef RNF_NORMAL ! 40: #include "param.h" ! 41: #include "radix.h" ! 42: #include "malloc.h" ! 43: #define M_DONTWAIT M_NOWAIT ! 44: #endif ! 45: struct radix_node_head *mask_rnhead; ! 46: #define rn_maskhead mask_rnhead->rnh_treetop ! 47: struct radix_mask *rn_mkfreelist; ! 48: struct radix_node_head *radix_node_head; ! 49: #undef Bcmp ! 50: #define Bcmp(a, b, l) (l == 0 ? 0 : bcmp((caddr_t)(a), (caddr_t)(b), (u_long)l)) ! 51: /* ! 52: * The data structure for the keys is a radix tree with one way ! 53: * branching removed. The index rn_b at an internal node n represents a bit ! 54: * position to be tested. The tree is arranged so that all descendants ! 55: * of a node n have keys whose bits all agree up to position rn_b - 1. ! 56: * (We say the index of n is rn_b.) ! 57: * ! 58: * There is at least one descendant which has a one bit at position rn_b, ! 59: * and at least one with a zero there. ! 60: * ! 61: * A route is determined by a pair of key and mask. We require that the ! 62: * bit-wise logical and of the key and mask to be the key. ! 63: * We define the index of a route to associated with the mask to be ! 64: * the first bit number in the mask where 0 occurs (with bit number 0 ! 65: * representing the highest order bit). ! 66: * ! 67: * We say a mask is normal if every bit is 0, past the index of the mask. ! 68: * If a node n has a descendant (k, m) with index(m) == index(n) == rn_b, ! 69: * and m is a normal mask, then the route applies to every descendant of n. ! 70: * If the index(m) < rn_b, this implies the trailing last few bits of k ! 71: * before bit b are all 0, (and hence consequently true of every descendant ! 72: * of n), so the route applies to all descendants of the node as well. ! 73: * ! 74: * The present version of the code makes no use of normal routes, ! 75: * but similar logic shows that a non-normal mask m such that ! 76: * index(m) <= index(n) could potentially apply to many children of n. ! 77: * Thus, for each non-host route, we attach its mask to a list at an internal ! 78: * node as high in the tree as we can go. ! 79: */ ! 80: ! 81: struct radix_node * ! 82: rn_search(v, head) ! 83: struct radix_node *head; ! 84: register caddr_t v; ! 85: { ! 86: register struct radix_node *x; ! 87: ! 88: for (x = head; x->rn_b >= 0;) { ! 89: if (x->rn_bmask & v[x->rn_off]) ! 90: x = x->rn_r; ! 91: else ! 92: x = x->rn_l; ! 93: } ! 94: return x; ! 95: }; ! 96: ! 97: struct radix_node * ! 98: rn_search_m(v, head, m) ! 99: struct radix_node *head; ! 100: register caddr_t v, m; ! 101: { ! 102: register struct radix_node *x; ! 103: ! 104: for (x = head; x->rn_b >= 0;) { ! 105: if ((x->rn_bmask & m[x->rn_off]) && ! 106: (x->rn_bmask & v[x->rn_off])) ! 107: x = x->rn_r; ! 108: else ! 109: x = x->rn_l; ! 110: } ! 111: return x; ! 112: }; ! 113: ! 114: ! 115: static int gotOddMasks; ! 116: static char maskedKey[MAXKEYLEN]; ! 117: ! 118: struct radix_node * ! 119: rn_match(v, head) ! 120: struct radix_node *head; ! 121: caddr_t v; ! 122: { ! 123: register struct radix_node *t = head, *x; ! 124: register caddr_t cp = v, cp2, cp3; ! 125: caddr_t cplim, mstart; ! 126: struct radix_node *saved_t; ! 127: int off = t->rn_off, vlen = *(u_char *)cp, matched_off; ! 128: ! 129: /* ! 130: * Open code rn_search(v, head) to avoid overhead of extra ! 131: * subroutine call. ! 132: */ ! 133: for (; t->rn_b >= 0; ) { ! 134: if (t->rn_bmask & cp[t->rn_off]) ! 135: t = t->rn_r; ! 136: else ! 137: t = t->rn_l; ! 138: } ! 139: /* ! 140: * See if we match exactly as a host destination ! 141: */ ! 142: cp += off; cp2 = t->rn_key + off; cplim = v + vlen; ! 143: for (; cp < cplim; cp++, cp2++) ! 144: if (*cp != *cp2) ! 145: goto on1; ! 146: /* ! 147: * This extra grot is in case we are explicitly asked ! 148: * to look up the default. Ugh! ! 149: */ ! 150: if ((t->rn_flags & RNF_ROOT) && t->rn_dupedkey) ! 151: t = t->rn_dupedkey; ! 152: return t; ! 153: on1: ! 154: matched_off = cp - v; ! 155: saved_t = t; ! 156: do { ! 157: if (t->rn_mask) { ! 158: /* ! 159: * Even if we don't match exactly as a hosts; ! 160: * we may match if the leaf we wound up at is ! 161: * a route to a net. ! 162: */ ! 163: cp3 = matched_off + t->rn_mask; ! 164: cp2 = matched_off + t->rn_key; ! 165: for (; cp < cplim; cp++) ! 166: if ((*cp2++ ^ *cp) & *cp3++) ! 167: break; ! 168: if (cp == cplim) ! 169: return t; ! 170: cp = matched_off + v; ! 171: } ! 172: } while (t = t->rn_dupedkey); ! 173: t = saved_t; ! 174: /* start searching up the tree */ ! 175: do { ! 176: register struct radix_mask *m; ! 177: t = t->rn_p; ! 178: if (m = t->rn_mklist) { ! 179: /* ! 180: * After doing measurements here, it may ! 181: * turn out to be faster to open code ! 182: * rn_search_m here instead of always ! 183: * copying and masking. ! 184: */ ! 185: off = min(t->rn_off, matched_off); ! 186: mstart = maskedKey + off; ! 187: do { ! 188: cp2 = mstart; ! 189: cp3 = m->rm_mask + off; ! 190: for (cp = v + off; cp < cplim;) ! 191: *cp2++ = *cp++ & *cp3++; ! 192: x = rn_search(maskedKey, t); ! 193: while (x && x->rn_mask != m->rm_mask) ! 194: x = x->rn_dupedkey; ! 195: if (x && ! 196: (Bcmp(mstart, x->rn_key + off, ! 197: vlen - off) == 0)) ! 198: return x; ! 199: } while (m = m->rm_mklist); ! 200: } ! 201: } while (t != head); ! 202: return 0; ! 203: }; ! 204: ! 205: #ifdef RN_DEBUG ! 206: int rn_nodenum; ! 207: struct radix_node *rn_clist; ! 208: int rn_saveinfo; ! 209: #endif ! 210: ! 211: struct radix_node * ! 212: rn_newpair(v, b, nodes) ! 213: caddr_t v; ! 214: struct radix_node nodes[2]; ! 215: { ! 216: register struct radix_node *tt = nodes, *t = tt + 1; ! 217: t->rn_b = b; t->rn_bmask = 0x80 >> (b & 7); ! 218: t->rn_l = tt; t->rn_off = b >> 3; ! 219: tt->rn_b = -1; tt->rn_key = v; tt->rn_p = t; ! 220: tt->rn_flags = t->rn_flags = RNF_ACTIVE; ! 221: #ifdef RN_DEBUG ! 222: tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; ! 223: tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; ! 224: #endif ! 225: return t; ! 226: } ! 227: ! 228: int rn_debug = 1; ! 229: struct radix_node * ! 230: rn_insert(v, head, dupentry, nodes) ! 231: caddr_t v; ! 232: struct radix_node *head; ! 233: int *dupentry; ! 234: struct radix_node nodes[2]; ! 235: { ! 236: int head_off = head->rn_off, vlen = (int)*((u_char *)v); ! 237: register struct radix_node *t = rn_search(v, head); ! 238: register caddr_t cp = v + head_off; ! 239: register int b; ! 240: struct radix_node *tt; ! 241: /* ! 242: *find first bit at which v and t->rn_key differ ! 243: */ ! 244: { ! 245: register caddr_t cp2 = t->rn_key + head_off; ! 246: register int cmp_res; ! 247: caddr_t cplim = v + vlen; ! 248: ! 249: while (cp < cplim) ! 250: if (*cp2++ != *cp++) ! 251: goto on1; ! 252: *dupentry = 1; ! 253: return t; ! 254: on1: ! 255: *dupentry = 0; ! 256: cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; ! 257: for (b = (cp - v) << 3; cmp_res; b--) ! 258: cmp_res >>= 1; ! 259: } ! 260: { ! 261: register struct radix_node *p, *x = head; ! 262: cp = v; ! 263: do { ! 264: p = x; ! 265: if (cp[x->rn_off] & x->rn_bmask) ! 266: x = x->rn_r; ! 267: else x = x->rn_l; ! 268: } while (b > (unsigned) x->rn_b); /* x->rn_b < b && x->rn_b >= 0 */ ! 269: #ifdef RN_DEBUG ! 270: if (rn_debug) ! 271: printf("Going In:\n"), traverse(p); ! 272: #endif ! 273: t = rn_newpair(v, b, nodes); tt = t->rn_l; ! 274: if ((cp[p->rn_off] & p->rn_bmask) == 0) ! 275: p->rn_l = t; ! 276: else ! 277: p->rn_r = t; ! 278: x->rn_p = t; t->rn_p = p; /* frees x, p as temp vars below */ ! 279: if ((cp[t->rn_off] & t->rn_bmask) == 0) { ! 280: t->rn_r = x; ! 281: } else { ! 282: t->rn_r = tt; t->rn_l = x; ! 283: } ! 284: #ifdef RN_DEBUG ! 285: if (rn_debug) ! 286: printf("Coming out:\n"), traverse(p); ! 287: #endif ! 288: } ! 289: return (tt); ! 290: } ! 291: ! 292: struct radix_node * ! 293: rn_addmask(netmask, search, skip) ! 294: caddr_t netmask; ! 295: { ! 296: register struct radix_node *x; ! 297: register caddr_t cp, cplim; ! 298: register int b, mlen, j; ! 299: int maskduplicated; ! 300: ! 301: mlen = *(u_char *)netmask; ! 302: if (search) { ! 303: x = rn_search(netmask, rn_maskhead); ! 304: mlen = *(u_char *)netmask; ! 305: if (Bcmp(netmask, x->rn_key, mlen) == 0) ! 306: return (x); ! 307: } ! 308: R_Malloc(x, struct radix_node *, MAXKEYLEN + 2 * sizeof (*x)); ! 309: if (x == 0) ! 310: return (0); ! 311: Bzero(x, MAXKEYLEN + 2 * sizeof (*x)); ! 312: cp = (caddr_t)(x + 2); ! 313: Bcopy(netmask, cp, mlen); ! 314: netmask = cp; ! 315: x = rn_insert(netmask, rn_maskhead, &maskduplicated, x); ! 316: /* ! 317: * Calculate index of mask. ! 318: */ ! 319: cplim = netmask + mlen; ! 320: for (cp = netmask + skip; cp < cplim; cp++) ! 321: if (*(u_char *)cp != 0xff) ! 322: break; ! 323: b = (cp - netmask) << 3; ! 324: if (cp != cplim) { ! 325: if (*cp != 0) { ! 326: gotOddMasks = 1; ! 327: for (j = 0x80; j; b++, j >>= 1) ! 328: if ((j & *cp) == 0) ! 329: break; ! 330: } ! 331: } ! 332: x->rn_b = -1 - b; ! 333: return (x); ! 334: } ! 335: ! 336: struct radix_node * ! 337: rn_addroute(v, netmask, head, treenodes) ! 338: struct radix_node *head; ! 339: caddr_t netmask, v; ! 340: struct radix_node treenodes[2]; ! 341: { ! 342: register int j; ! 343: register caddr_t cp; ! 344: register struct radix_node *t, *x, *tt; ! 345: short b = 0, b_leaf; ! 346: int vlen = *(u_char *)v, mlen, keyduplicated; ! 347: caddr_t cplim; unsigned char *maskp; ! 348: struct radix_mask *m, **mp; ! 349: struct radix_node *saved_tt; ! 350: ! 351: /* ! 352: * In dealing with non-contiguous masks, there may be ! 353: * many different routes which have the same mask. ! 354: * We will find it useful to have a unique pointer to ! 355: * the mask to speed avoiding duplicate references at ! 356: * nodes and possibly save time in calculating indices. ! 357: */ ! 358: if (netmask) { ! 359: x = rn_search(netmask, rn_maskhead); ! 360: mlen = *(u_char *)netmask; ! 361: if (Bcmp(netmask, x->rn_key, mlen) != 0) { ! 362: x = rn_addmask(netmask, 0, head->rn_off); ! 363: if (x == 0) ! 364: return (0); ! 365: } ! 366: netmask = x->rn_key; ! 367: b = -1 - x->rn_b; ! 368: } ! 369: /* ! 370: * Deal with duplicated keys: attach node to previous instance ! 371: */ ! 372: saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); ! 373: if (keyduplicated) { ! 374: do { ! 375: if (tt->rn_mask == netmask) ! 376: return (0); ! 377: t = tt; ! 378: } while (tt = tt->rn_dupedkey); ! 379: /* ! 380: * If the mask is not duplicated, we wouldn't ! 381: * find it among possible duplicate key entries ! 382: * anyway, so the above test doesn't hurt. ! 383: * ! 384: * XXX: we really ought to sort the masks ! 385: * for a duplicated key the same way as in a masklist. ! 386: * It is an unfortunate pain having to relocate ! 387: * the head of the list. ! 388: */ ! 389: t->rn_dupedkey = tt = treenodes; ! 390: #ifdef RN_DEBUG ! 391: t=tt+1; tt->rn_info = rn_nodenum++; t->rn_info = rn_nodenum++; ! 392: tt->rn_twin = t; tt->rn_ybro = rn_clist; rn_clist = tt; ! 393: #endif ! 394: t = saved_tt; ! 395: tt->rn_key = (caddr_t) v; ! 396: tt->rn_b = -1; ! 397: tt->rn_flags = t->rn_flags & ~RNF_ROOT; ! 398: } ! 399: /* ! 400: * Put mask in tree. ! 401: */ ! 402: if (netmask) { ! 403: tt->rn_mask = netmask; ! 404: tt->rn_b = x->rn_b; ! 405: } ! 406: t = saved_tt->rn_p; ! 407: b_leaf = -1 - t->rn_b; ! 408: if (t->rn_r == saved_tt) x = t->rn_l; else x = t->rn_r; ! 409: /* Promote general routes from below */ ! 410: if (x->rn_b < 0) { ! 411: if (x->rn_mask && (x->rn_b >= b_leaf) && x->rn_mklist == 0) { ! 412: MKGet(m); ! 413: if (m) { ! 414: Bzero(m, sizeof *m); ! 415: m->rm_b = x->rn_b; ! 416: m->rm_mask = x->rn_mask; ! 417: x->rn_mklist = t->rn_mklist = m; ! 418: } ! 419: } ! 420: } else if (x->rn_mklist) { ! 421: /* ! 422: * Skip over masks whose index is > that of new node ! 423: */ ! 424: for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) ! 425: if (m->rm_b >= b_leaf) ! 426: break; ! 427: t->rn_mklist = m; *mp = 0; ! 428: } ! 429: /* Add new route to highest possible ancestor's list */ ! 430: if ((netmask == 0) || (b > t->rn_b )) ! 431: return tt; /* can't lift at all */ ! 432: b_leaf = tt->rn_b; ! 433: do { ! 434: x = t; ! 435: t = t->rn_p; ! 436: } while (b <= t->rn_b && x != head); ! 437: /* ! 438: * Search through routes associated with node to ! 439: * insert new route according to index. ! 440: * For nodes of equal index, place more specific ! 441: * masks first. ! 442: */ ! 443: cplim = netmask + mlen; ! 444: for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) { ! 445: if (m->rm_b < b_leaf) ! 446: continue; ! 447: if (m->rm_b > b_leaf) ! 448: break; ! 449: if (m->rm_mask == netmask) { ! 450: m->rm_refs++; ! 451: tt->rn_mklist = m; ! 452: return tt; ! 453: } ! 454: maskp = (u_char *)m->rm_mask; ! 455: for (cp = netmask; cp < cplim; cp++) ! 456: if (*(u_char *)cp > *maskp++) ! 457: goto on2; ! 458: } ! 459: on2: ! 460: MKGet(m); ! 461: if (m == 0) { ! 462: printf("Mask for route not entered\n"); ! 463: return (tt); ! 464: } ! 465: Bzero(m, sizeof *m); ! 466: m->rm_b = b_leaf; ! 467: m->rm_mask = netmask; ! 468: m->rm_mklist = *mp; ! 469: *mp = m; ! 470: tt->rn_mklist = m; ! 471: return tt; ! 472: } ! 473: ! 474: struct radix_node * ! 475: rn_delete(v, netmask, head) ! 476: caddr_t v, netmask; ! 477: struct radix_node *head; ! 478: { ! 479: register struct radix_node *t, *p, *x = head; ! 480: register struct radix_node *tt = rn_search(v, x); ! 481: int b, head_off = x->rn_off, vlen = * (u_char *) v; ! 482: struct radix_mask *m, *saved_m, **mp; ! 483: struct radix_node *dupedkey, *saved_tt = tt; ! 484: ! 485: if (tt == 0 || ! 486: Bcmp(v + head_off, tt->rn_key + head_off, vlen - head_off)) ! 487: return (0); ! 488: /* ! 489: * Delete our route from mask lists. ! 490: */ ! 491: if (dupedkey = tt->rn_dupedkey) { ! 492: if (netmask) ! 493: netmask = rn_search(netmask, rn_maskhead)->rn_key; ! 494: while (tt->rn_mask != netmask) ! 495: if ((tt = tt->rn_dupedkey) == 0) ! 496: return (0); ! 497: } ! 498: if (tt->rn_mask == 0 || (saved_m = m = tt->rn_mklist) == 0) ! 499: goto on1; ! 500: if (m->rm_mask != tt->rn_mask) { ! 501: printf("rn_delete: inconsistent annotation\n"); ! 502: goto on1; ! 503: } ! 504: if (--m->rm_refs >= 0) ! 505: goto on1; ! 506: b = -1 - tt->rn_b; ! 507: t = saved_tt->rn_p; ! 508: if (b > t->rn_b) ! 509: goto on1; /* Wasn't lifted at all */ ! 510: do { ! 511: x = t; ! 512: t = t->rn_p; ! 513: } while (b <= t->rn_b && x != head); ! 514: for (mp = &x->rn_mklist; m = *mp; mp = &m->rm_mklist) ! 515: if (m == saved_m) { ! 516: *mp = m->rm_mklist; ! 517: MKFree(m); ! 518: break; ! 519: } ! 520: if (m == 0) ! 521: printf("rn_delete: couldn't find our annotation\n"); ! 522: on1: ! 523: /* ! 524: * Eliminate us from tree ! 525: */ ! 526: if (tt->rn_flags & RNF_ROOT) ! 527: return (0); ! 528: #ifdef RN_DEBUG ! 529: /* Get us out of the creation list */ ! 530: for (t = rn_clist; t && t->rn_ybro != tt; t = t->rn_ybro) {} ! 531: if (t) t->rn_ybro = tt->rn_ybro; ! 532: #endif RN_DEBUG ! 533: t = tt->rn_p; ! 534: if (dupedkey) { ! 535: if (tt == saved_tt) { ! 536: x = dupedkey; x->rn_p = t; ! 537: if (t->rn_l == tt) t->rn_l = x; else t->rn_r = x; ! 538: #ifndef RN_DEBUG ! 539: x++; t = tt + 1; *x = *t; p = t->rn_p; ! 540: #else ! 541: x++; b = x->rn_info; t = tt + 1; *x = *t; p = t->rn_p; ! 542: x->rn_info = b; ! 543: #endif ! 544: if (p->rn_l == t) p->rn_l = x; else p->rn_r = x; ! 545: x->rn_l->rn_p = x; x->rn_r->rn_p = x; ! 546: } else { ! 547: for (p = saved_tt; p && p->rn_dupedkey != tt;) ! 548: p = p->rn_dupedkey; ! 549: if (p) p->rn_dupedkey = tt->rn_dupedkey; ! 550: else printf("rn_delete: couldn't find us\n"); ! 551: } ! 552: goto out; ! 553: } ! 554: if (t->rn_l == tt) x = t->rn_r; else x = t->rn_l; ! 555: p = t->rn_p; ! 556: if (p->rn_r == t) p->rn_r = x; else p->rn_l = x; ! 557: x->rn_p = p; ! 558: /* ! 559: * Demote routes attached to us. ! 560: */ ! 561: if (t->rn_mklist) { ! 562: if (x->rn_b >= 0) { ! 563: for (mp = &x->rn_mklist; m = *mp;) ! 564: mp = &m->rm_mklist; ! 565: *mp = t->rn_mklist; ! 566: } else { ! 567: for (m = t->rn_mklist; m;) { ! 568: struct radix_mask *mm = m->rm_mklist; ! 569: if (m == x->rn_mklist && (--(m->rm_refs) < 0)) { ! 570: x->rn_mklist = 0; ! 571: MKFree(m); ! 572: } else ! 573: printf("%s %x at %x\n", ! 574: "rn_delete: Orphaned Mask", m, x); ! 575: m = mm; ! 576: } ! 577: } ! 578: } ! 579: /* ! 580: * We may be holding an active internal node in the tree. ! 581: */ ! 582: x = tt + 1; ! 583: if (t != x) { ! 584: #ifndef RN_DEBUG ! 585: *t = *x; ! 586: #else ! 587: b = t->rn_info; *t = *x; t->rn_info = b; ! 588: #endif ! 589: t->rn_l->rn_p = t; t->rn_r->rn_p = t; ! 590: p = x->rn_p; ! 591: if (p->rn_l == x) p->rn_l = t; else p->rn_r = t; ! 592: } ! 593: out: ! 594: tt->rn_flags &= ~RNF_ACTIVE; ! 595: tt[1].rn_flags &= ~RNF_ACTIVE; ! 596: return (tt); ! 597: } ! 598: char rn_zeros[MAXKEYLEN], rn_ones[MAXKEYLEN]; ! 599: ! 600: rn_inithead(head, off, af) ! 601: struct radix_node_head **head; ! 602: int off; ! 603: { ! 604: register struct radix_node_head *rnh; ! 605: register struct radix_node *t, *tt, *ttt; ! 606: if (*head) ! 607: return (1); ! 608: R_Malloc(rnh, struct radix_node_head *, sizeof (*rnh)); ! 609: if (rnh == 0) ! 610: return (0); ! 611: Bzero(rnh, sizeof (*rnh)); ! 612: *head = rnh; ! 613: t = rn_newpair(rn_zeros, off, rnh->rnh_nodes); ! 614: ttt = rnh->rnh_nodes + 2; ! 615: t->rn_r = ttt; ! 616: t->rn_p = t; ! 617: tt = t->rn_l; ! 618: tt->rn_flags = t->rn_flags = RNF_ROOT | RNF_ACTIVE; ! 619: tt->rn_b = -1 - off; ! 620: *ttt = *tt; ! 621: ttt->rn_key = rn_ones; ! 622: rnh->rnh_af = af; ! 623: rnh->rnh_treetop = t; ! 624: if (radix_node_head == 0) { ! 625: caddr_t cp = rn_ones, cplim = rn_ones + MAXKEYLEN; ! 626: while (cp < cplim) ! 627: *cp++ = -1; ! 628: if (rn_inithead(&radix_node_head, 0, 0) == 0) { ! 629: Free(rnh); ! 630: *head = 0; ! 631: return (0); ! 632: } ! 633: mask_rnhead = radix_node_head; ! 634: } ! 635: rnh->rnh_next = radix_node_head->rnh_next; ! 636: if (radix_node_head != rnh) ! 637: radix_node_head->rnh_next = rnh; ! 638: return (1); ! 639: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.