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