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