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