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