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