| 420 | } |
| 421 | |
| 422 | static struct radix_node * |
| 423 | rn_insert(void *v_arg, struct radix_head *head, int *dupentry, |
| 424 | struct radix_node nodes[2]) |
| 425 | { |
| 426 | caddr_t v = v_arg; |
| 427 | struct radix_node *top = head->rnh_treetop; |
| 428 | int head_off = top->rn_offset, vlen = LEN(v); |
| 429 | struct radix_node *t = rn_search(v_arg, top); |
| 430 | caddr_t cp = v + head_off; |
| 431 | int b; |
| 432 | struct radix_node *p, *tt, *x; |
| 433 | /* |
| 434 | * Find first bit at which v and t->rn_key differ |
| 435 | */ |
| 436 | caddr_t cp2 = t->rn_key + head_off; |
| 437 | int cmp_res; |
| 438 | caddr_t cplim = v + vlen; |
| 439 | |
| 440 | while (cp < cplim) |
| 441 | if (*cp2++ != *cp++) |
| 442 | goto on1; |
| 443 | *dupentry = 1; |
| 444 | return (t); |
| 445 | on1: |
| 446 | *dupentry = 0; |
| 447 | cmp_res = (cp[-1] ^ cp2[-1]) & 0xff; |
| 448 | for (b = (cp - v) << 3; cmp_res; b--) |
| 449 | cmp_res >>= 1; |
| 450 | |
| 451 | x = top; |
| 452 | cp = v; |
| 453 | do { |
| 454 | p = x; |
| 455 | if (cp[x->rn_offset] & x->rn_bmask) |
| 456 | x = x->rn_right; |
| 457 | else |
| 458 | x = x->rn_left; |
| 459 | } while (b > (unsigned) x->rn_bit); |
| 460 | /* x->rn_bit < b && x->rn_bit >= 0 */ |
| 461 | #ifdef RN_DEBUG |
| 462 | if (rn_debug) |
| 463 | log(LOG_DEBUG, "rn_insert: Going In:\n"), traverse(p); |
| 464 | #endif |
| 465 | t = rn_newpair(v_arg, b, nodes); |
| 466 | tt = t->rn_left; |
| 467 | if ((cp[p->rn_offset] & p->rn_bmask) == 0) |
| 468 | p->rn_left = t; |
| 469 | else |
| 470 | p->rn_right = t; |
| 471 | x->rn_parent = t; |
| 472 | t->rn_parent = p; /* frees x, p as temp vars below */ |
| 473 | if ((cp[t->rn_offset] & t->rn_bmask) == 0) { |
| 474 | t->rn_right = x; |
| 475 | } else { |
| 476 | t->rn_right = tt; |
| 477 | t->rn_left = x; |
| 478 | } |
| 479 | #ifdef RN_DEBUG |
no test coverage detected