| 592 | } |
| 593 | |
| 594 | struct radix_node * |
| 595 | rn_addroute(void *v_arg, void *n_arg, struct radix_head *head, |
| 596 | struct radix_node treenodes[2]) |
| 597 | { |
| 598 | caddr_t v = (caddr_t)v_arg, netmask = (caddr_t)n_arg; |
| 599 | struct radix_node *t, *x = NULL, *tt; |
| 600 | struct radix_node *saved_tt, *top = head->rnh_treetop; |
| 601 | short b = 0, b_leaf = 0; |
| 602 | int keyduplicated; |
| 603 | caddr_t mmask; |
| 604 | struct radix_mask *m, **mp; |
| 605 | |
| 606 | /* |
| 607 | * In dealing with non-contiguous masks, there may be |
| 608 | * many different routes which have the same mask. |
| 609 | * We will find it useful to have a unique pointer to |
| 610 | * the mask to speed avoiding duplicate references at |
| 611 | * nodes and possibly save time in calculating indices. |
| 612 | */ |
| 613 | if (netmask) { |
| 614 | x = rn_addmask(netmask, head->rnh_masks, 0, top->rn_offset); |
| 615 | if (x == NULL) |
| 616 | return (0); |
| 617 | b_leaf = x->rn_bit; |
| 618 | b = -1 - x->rn_bit; |
| 619 | netmask = x->rn_key; |
| 620 | } |
| 621 | /* |
| 622 | * Deal with duplicated keys: attach node to previous instance |
| 623 | */ |
| 624 | saved_tt = tt = rn_insert(v, head, &keyduplicated, treenodes); |
| 625 | if (keyduplicated) { |
| 626 | for (t = tt; tt; t = tt, tt = tt->rn_dupedkey) { |
| 627 | if (tt->rn_mask == netmask) |
| 628 | return (0); |
| 629 | if (netmask == 0 || |
| 630 | (tt->rn_mask && |
| 631 | ((b_leaf < tt->rn_bit) /* index(netmask) > node */ |
| 632 | || rn_refines(netmask, tt->rn_mask) |
| 633 | || rn_lexobetter(netmask, tt->rn_mask)))) |
| 634 | break; |
| 635 | } |
| 636 | /* |
| 637 | * If the mask is not duplicated, we wouldn't |
| 638 | * find it among possible duplicate key entries |
| 639 | * anyway, so the above test doesn't hurt. |
| 640 | * |
| 641 | * We sort the masks for a duplicated key the same way as |
| 642 | * in a masklist -- most specific to least specific. |
| 643 | * This may require the unfortunate nuisance of relocating |
| 644 | * the head of the list. |
| 645 | * |
| 646 | * We also reverse, or doubly link the list through the |
| 647 | * parent pointer. |
| 648 | */ |
| 649 | if (tt == saved_tt) { |
| 650 | struct radix_node *xx = x; |
| 651 | /* link in at head of list */ |
no test coverage detected