"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.11.23/lib/isc/radix.c" (7 Sep 2020, 17186 Bytes) of package /linux/misc/dns/bind9/9.11.23/bind-9.11.23.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "radix.c" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 9.17.2_vs_9.17.3.

    1 /*
    2  * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
    3  *
    4  * This Source Code Form is subject to the terms of the Mozilla Public
    5  * License, v. 2.0. If a copy of the MPL was not distributed with this
    6  * file, You can obtain one at http://mozilla.org/MPL/2.0/.
    7  *
    8  * See the COPYRIGHT file distributed with this work for additional
    9  * information regarding copyright ownership.
   10  */
   11 
   12 
   13 /*
   14  * This source was adapted from MRT's RCS Ids:
   15  * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp
   16  * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp
   17  */
   18 
   19 #include <config.h>
   20 
   21 #include <inttypes.h>
   22 
   23 #include <isc/mem.h>
   24 #include <isc/types.h>
   25 #include <isc/util.h>
   26 #include <isc/radix.h>
   27 
   28 #define BIT_TEST(f, b)  (((f) & (b)) != 0)
   29 
   30 static isc_result_t
   31 _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family,
   32         void *dest, int bitlen);
   33 
   34 static void
   35 _deref_prefix(isc_prefix_t *prefix);
   36 
   37 static isc_result_t
   38 _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix);
   39 
   40 static int
   41 _comp_with_mask(void *addr, void *dest, u_int mask);
   42 
   43 static void
   44 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
   45 
   46 static isc_result_t
   47 _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
   48         int bitlen)
   49 {
   50     isc_prefix_t *prefix;
   51 
   52     REQUIRE(target != NULL);
   53 
   54     if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC)
   55         return (ISC_R_NOTIMPLEMENTED);
   56 
   57     prefix = isc_mem_get(mctx, sizeof(isc_prefix_t));
   58     if (prefix == NULL)
   59         return (ISC_R_NOMEMORY);
   60 
   61     if (family == AF_INET6) {
   62         prefix->bitlen = (bitlen >= 0) ? bitlen : 128;
   63         memmove(&prefix->add.sin6, dest, 16);
   64     } else {
   65         /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */
   66         prefix->bitlen = (bitlen >= 0) ? bitlen : 32;
   67         memmove(&prefix->add.sin, dest, 4);
   68     }
   69 
   70     prefix->family = family;
   71     prefix->ecs = false;
   72     prefix->mctx = NULL;
   73     isc_mem_attach(mctx, &prefix->mctx);
   74 
   75     isc_refcount_init(&prefix->refcount, 1);
   76 
   77     *target = prefix;
   78     return (ISC_R_SUCCESS);
   79 }
   80 
   81 static void
   82 _deref_prefix(isc_prefix_t *prefix) {
   83     int refs;
   84 
   85     if (prefix == NULL)
   86         return;
   87 
   88     isc_refcount_decrement(&prefix->refcount, &refs);
   89 
   90     if (refs <= 0) {
   91         isc_refcount_destroy(&prefix->refcount);
   92         isc_mem_putanddetach(&prefix->mctx, prefix,
   93                      sizeof(isc_prefix_t));
   94     }
   95 }
   96 
   97 static isc_result_t
   98 _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
   99     INSIST(prefix != NULL);
  100     INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
  101            (prefix->family == AF_INET6 && prefix->bitlen <= 128) ||
  102            (prefix->family == AF_UNSPEC && prefix->bitlen == 0));
  103     REQUIRE(target != NULL && *target == NULL);
  104 
  105     /*
  106      * If this prefix is a static allocation, copy it into new memory.
  107      * (Note, the refcount still has to be destroyed by the calling
  108      * routine.)
  109      */
  110     if (isc_refcount_current(&prefix->refcount) == 0) {
  111         isc_result_t ret;
  112         ret = _new_prefix(mctx, target, prefix->family,
  113                   &prefix->add, prefix->bitlen);
  114         return (ret);
  115     }
  116 
  117     isc_refcount_increment(&prefix->refcount, NULL);
  118 
  119     *target = prefix;
  120     return (ISC_R_SUCCESS);
  121 }
  122 
  123 static int
  124 _comp_with_mask(void *addr, void *dest, u_int mask) {
  125 
  126     /* Mask length of zero matches everything */
  127     if (mask == 0)
  128         return (1);
  129 
  130     if (memcmp(addr, dest, mask / 8) == 0) {
  131         u_int n = mask / 8;
  132         u_int m = ((~0U) << (8 - (mask % 8)));
  133 
  134         if ((mask % 8) == 0 ||
  135             (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
  136             return (1);
  137     }
  138     return (0);
  139 }
  140 
  141 isc_result_t
  142 isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
  143     isc_radix_tree_t *radix;
  144 
  145     REQUIRE(target != NULL && *target == NULL);
  146 
  147     radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
  148     if (radix == NULL)
  149         return (ISC_R_NOMEMORY);
  150 
  151     radix->mctx = NULL;
  152     isc_mem_attach(mctx, &radix->mctx);
  153     radix->maxbits = maxbits;
  154     radix->head = NULL;
  155     radix->num_active_node = 0;
  156     radix->num_added_node = 0;
  157     RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */
  158     radix->magic = RADIX_TREE_MAGIC;
  159     *target = radix;
  160     return (ISC_R_SUCCESS);
  161 }
  162 
  163 /*
  164  * if func is supplied, it will be called as func(node->data)
  165  * before deleting the node
  166  */
  167 
  168 static void
  169 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
  170     REQUIRE(radix != NULL);
  171 
  172     if (radix->head != NULL) {
  173         isc_radix_node_t *Xstack[RADIX_MAXBITS+1];
  174         isc_radix_node_t **Xsp = Xstack;
  175         isc_radix_node_t *Xrn = radix->head;
  176 
  177         while (Xrn != NULL) {
  178             isc_radix_node_t *l = Xrn->l;
  179             isc_radix_node_t *r = Xrn->r;
  180 
  181             if (Xrn->prefix != NULL) {
  182                 _deref_prefix(Xrn->prefix);
  183                 if (func != NULL)
  184                     func(Xrn->data);
  185             } else {
  186                 INSIST(Xrn->data[RADIX_V4] == NULL &&
  187                        Xrn->data[RADIX_V6] == NULL &&
  188                        Xrn->data[RADIX_V4_ECS] == NULL &&
  189                        Xrn->data[RADIX_V6_ECS] == NULL);
  190             }
  191 
  192             isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
  193             radix->num_active_node--;
  194 
  195             if (l != NULL) {
  196                 if (r != NULL) {
  197                     *Xsp++ = r;
  198                 }
  199                 Xrn = l;
  200             } else if (r != NULL) {
  201                 Xrn = r;
  202             } else if (Xsp != Xstack) {
  203                 Xrn = *(--Xsp);
  204             } else {
  205                 Xrn = NULL;
  206             }
  207         }
  208     }
  209     RUNTIME_CHECK(radix->num_active_node == 0);
  210 }
  211 
  212 
  213 void
  214 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
  215     REQUIRE(radix != NULL);
  216     _clear_radix(radix, func);
  217     isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix));
  218 }
  219 
  220 
  221 /*
  222  * func will be called as func(node->prefix, node->data)
  223  */
  224 void
  225 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) {
  226     isc_radix_node_t *node;
  227 
  228     REQUIRE(func != NULL);
  229 
  230     RADIX_WALK(radix->head, node) {
  231         func(node->prefix, node->data);
  232     } RADIX_WALK_END;
  233 }
  234 
  235 
  236 isc_result_t
  237 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
  238          isc_prefix_t *prefix)
  239 {
  240     isc_radix_node_t *node;
  241     isc_radix_node_t *stack[RADIX_MAXBITS + 1];
  242     u_char *addr;
  243     uint32_t bitlen;
  244     int tfam = -1, cnt = 0;
  245 
  246     REQUIRE(radix != NULL);
  247     REQUIRE(prefix != NULL);
  248     REQUIRE(target != NULL && *target == NULL);
  249     RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);
  250 
  251     *target = NULL;
  252 
  253     node = radix->head;
  254 
  255     if (node == NULL) {
  256         return (ISC_R_NOTFOUND);
  257     }
  258 
  259     addr = isc_prefix_touchar(prefix);
  260     bitlen = prefix->bitlen;
  261 
  262     while (node != NULL && node->bit < bitlen) {
  263         if (node->prefix) {
  264             stack[cnt++] = node;
  265         }
  266 
  267         if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
  268         {
  269             node = node->r;
  270         } else {
  271             node = node->l;
  272         }
  273     }
  274 
  275     if (node != NULL && node->prefix) {
  276         stack[cnt++] = node;
  277     }
  278 
  279     while (cnt-- > 0) {
  280         node = stack[cnt];
  281 
  282         if (prefix->bitlen < node->bit) {
  283             continue;
  284         }
  285 
  286         if (_comp_with_mask(isc_prefix_tochar(node->prefix),
  287                     isc_prefix_tochar(prefix),
  288                     node->prefix->bitlen))
  289         {
  290             int fam = ISC_RADIX_FAMILY(prefix);
  291             if (node->node_num[fam] != -1 &&
  292                 ((*target == NULL) ||
  293                  (*target)->node_num[tfam] > node->node_num[fam]))
  294             {
  295                 *target = node;
  296                 tfam = fam;
  297             }
  298         }
  299     }
  300 
  301     if (*target == NULL) {
  302         return (ISC_R_NOTFOUND);
  303     } else {
  304         return (ISC_R_SUCCESS);
  305     }
  306 }
  307 
  308 isc_result_t
  309 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
  310          isc_radix_node_t *source, isc_prefix_t *prefix)
  311 {
  312     isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
  313     u_char *addr, *test_addr;
  314     uint32_t bitlen, fam, check_bit, differ_bit;
  315     uint32_t i, j, r;
  316     isc_result_t result;
  317 
  318     REQUIRE(radix != NULL);
  319     REQUIRE(target != NULL && *target == NULL);
  320     REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
  321     RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
  322 
  323     if (prefix == NULL)
  324         prefix = source->prefix;
  325 
  326     INSIST(prefix != NULL);
  327 
  328     bitlen = prefix->bitlen;
  329     fam = prefix->family;
  330 
  331     if (radix->head == NULL) {
  332         node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
  333         if (node == NULL)
  334             return (ISC_R_NOMEMORY);
  335         node->bit = bitlen;
  336         for (i = 0; i < RADIX_FAMILIES; i++) {
  337             node->node_num[i] = -1;
  338         }
  339         node->prefix = NULL;
  340         result = _ref_prefix(radix->mctx, &node->prefix, prefix);
  341         if (result != ISC_R_SUCCESS) {
  342             isc_mem_put(radix->mctx, node,
  343                     sizeof(isc_radix_node_t));
  344             return (result);
  345         }
  346         node->parent = NULL;
  347         node->l = node->r = NULL;
  348         if (source != NULL) {
  349             /*
  350              * If source is non-NULL, then we're merging in a
  351              * node from an existing radix tree.  To keep
  352              * the node_num values consistent, the calling
  353              * function will add the total number of nodes
  354              * added to num_added_node at the end of
  355              * the merge operation--we don't do it here.
  356              */
  357             for (i = 0; i < RADIX_FAMILIES; i++) {
  358                 if (source->node_num[i] != -1) {
  359                     node->node_num[i] =
  360                         radix->num_added_node +
  361                         source->node_num[i];
  362                 }
  363                 node->data[i] = source->data[i];
  364             }
  365         } else {
  366             int next = ++radix->num_added_node;
  367             if (fam == AF_UNSPEC) {
  368                 /* "any" or "none" */
  369                 for (i = 0; i < RADIX_FAMILIES; i++) {
  370                     node->node_num[i] = next;
  371                 }
  372             } else {
  373                 node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
  374             }
  375 
  376             memset(node->data, 0, sizeof(node->data));
  377         }
  378         radix->head = node;
  379         radix->num_active_node++;
  380         *target = node;
  381         return (ISC_R_SUCCESS);
  382     }
  383 
  384     addr = isc_prefix_touchar(prefix);
  385     node = radix->head;
  386 
  387     while (node->bit < bitlen || node->prefix == NULL) {
  388         if (node->bit < radix->maxbits &&
  389             BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
  390         {
  391             if (node->r == NULL)
  392                 break;
  393             node = node->r;
  394         } else {
  395             if (node->l == NULL)
  396                 break;
  397             node = node->l;
  398         }
  399 
  400         INSIST(node != NULL);
  401     }
  402 
  403     INSIST(node->prefix != NULL);
  404 
  405     test_addr = isc_prefix_touchar(node->prefix);
  406     /* Find the first bit different. */
  407     check_bit = (node->bit < bitlen) ? node->bit : bitlen;
  408     differ_bit = 0;
  409     for (i = 0; i * 8 < check_bit; i++) {
  410         if ((r = (addr[i] ^ test_addr[i])) == 0) {
  411             differ_bit = (i + 1) * 8;
  412             continue;
  413         }
  414         /* I know the better way, but for now. */
  415         for (j = 0; j < 8; j++) {
  416             if (BIT_TEST(r, (0x80 >> j)))
  417                 break;
  418         }
  419         /* Must be found. */
  420         INSIST(j < 8);
  421         differ_bit = i * 8 + j;
  422         break;
  423     }
  424 
  425     if (differ_bit > check_bit)
  426         differ_bit = check_bit;
  427 
  428     parent = node->parent;
  429     while (parent != NULL && parent->bit >= differ_bit) {
  430         node = parent;
  431         parent = node->parent;
  432     }
  433 
  434     if (differ_bit == bitlen && node->bit == bitlen) {
  435         if (node->prefix != NULL) {
  436             /* Set node_num only if it hasn't been set before */
  437             if (source != NULL) {
  438                 /* Merging nodes */
  439                 for (i = 0; i < RADIX_FAMILIES; i++) {
  440                     if (node->node_num[i] == -1 &&
  441                         source->node_num[i] != -1) {
  442                         node->node_num[i] =
  443                             radix->num_added_node +
  444                             source->node_num[i];
  445                         node->data[i] = source->data[i];
  446                     }
  447                 }
  448             } else {
  449                 if (fam == AF_UNSPEC) {
  450                     /* "any" or "none" */
  451                     int next = radix->num_added_node + 1;
  452                     for (i = 0; i < RADIX_FAMILIES; i++) {
  453                         if (node->node_num[i] == -1) {
  454                             node->node_num[i] =
  455                                 next;
  456                             radix->num_added_node =
  457                                 next;
  458                         }
  459                     }
  460                 } else {
  461                     int foff = ISC_RADIX_FAMILY(prefix);
  462                     if (node->node_num[foff] == -1) {
  463                         node->node_num[foff] =
  464                             ++radix->num_added_node;
  465                     }
  466                 }
  467             }
  468             *target = node;
  469             return (ISC_R_SUCCESS);
  470         } else {
  471             result = _ref_prefix(radix->mctx,
  472                          &node->prefix, prefix);
  473             if (result != ISC_R_SUCCESS)
  474                 return (result);
  475         }
  476 
  477         /* Check everything is null and empty before we proceed */
  478         INSIST(node->data[RADIX_V4] == NULL &&
  479                node->node_num[RADIX_V4] == -1 &&
  480                node->data[RADIX_V6] == NULL &&
  481                node->node_num[RADIX_V6] == -1 &&
  482                node->data[RADIX_V4_ECS] == NULL &&
  483                node->node_num[RADIX_V4_ECS] == -1 &&
  484                node->data[RADIX_V6_ECS] == NULL &&
  485                node->node_num[RADIX_V6_ECS] == -1);
  486 
  487         if (source != NULL) {
  488             /* Merging node */
  489             for (i = 0; i < RADIX_FAMILIES; i++) {
  490                 int cur = radix->num_added_node;
  491                 if (source->node_num[i] != -1) {
  492                     node->node_num[i] =
  493                         source->node_num[i] + cur;
  494                     node->data[i] = source->data[i];
  495                 }
  496             }
  497         } else {
  498             int next = ++radix->num_added_node;
  499             if (fam == AF_UNSPEC) {
  500                 /* "any" or "none" */
  501                 for (i = 0; i < RADIX_FAMILIES; i++) {
  502                     node->node_num[i] = next;
  503                 }
  504             } else {
  505                 node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
  506             }
  507         }
  508         *target = node;
  509         return (ISC_R_SUCCESS);
  510     }
  511 
  512     new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
  513     if (new_node == NULL)
  514         return (ISC_R_NOMEMORY);
  515     if (node->bit != differ_bit && bitlen != differ_bit) {
  516         glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
  517         if (glue == NULL) {
  518             isc_mem_put(radix->mctx, new_node,
  519                     sizeof(isc_radix_node_t));
  520             return (ISC_R_NOMEMORY);
  521         }
  522     }
  523     new_node->bit = bitlen;
  524     new_node->prefix = NULL;
  525     result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
  526     if (result != ISC_R_SUCCESS) {
  527         isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
  528         if (glue != NULL)
  529             isc_mem_put(radix->mctx, glue,
  530                     sizeof(isc_radix_node_t));
  531         return (result);
  532     }
  533     new_node->parent = NULL;
  534     new_node->l = new_node->r = NULL;
  535     for (i = 0; i < RADIX_FAMILIES; i++) {
  536         new_node->node_num[i] = -1;
  537         new_node->data[i] = NULL;
  538     }
  539     radix->num_active_node++;
  540 
  541     if (source != NULL) {
  542         /* Merging node */
  543         for (i = 0; i < RADIX_FAMILIES; i++) {
  544             int cur = radix->num_added_node;
  545             if (source->node_num[i] != -1) {
  546                 new_node->node_num[i] =
  547                     source->node_num[i] + cur;
  548                 new_node->data[i] = source->data[i];
  549             }
  550         }
  551     } else {
  552         int next = ++radix->num_added_node;
  553         if (fam == AF_UNSPEC) {
  554             /* "any" or "none" */
  555             for (i = 0; i < RADIX_FAMILIES; i++) {
  556                 new_node->node_num[i] = next;
  557             }
  558         } else {
  559             new_node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
  560         }
  561         memset(new_node->data, 0, sizeof(new_node->data));
  562     }
  563 
  564     if (node->bit == differ_bit) {
  565         INSIST(glue == NULL);
  566         new_node->parent = node;
  567         if (node->bit < radix->maxbits &&
  568             BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
  569         {
  570             INSIST(node->r == NULL);
  571             node->r = new_node;
  572         } else {
  573             INSIST(node->l == NULL);
  574             node->l = new_node;
  575         }
  576         *target = new_node;
  577         return (ISC_R_SUCCESS);
  578     }
  579 
  580     if (bitlen == differ_bit) {
  581         INSIST(glue == NULL);
  582         if (bitlen < radix->maxbits &&
  583             BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
  584             new_node->r = node;
  585         } else {
  586             new_node->l = node;
  587         }
  588         new_node->parent = node->parent;
  589         if (node->parent == NULL) {
  590             INSIST(radix->head == node);
  591             radix->head = new_node;
  592         } else if (node->parent->r == node) {
  593             node->parent->r = new_node;
  594         } else {
  595             node->parent->l = new_node;
  596         }
  597         node->parent = new_node;
  598     } else {
  599         INSIST(glue != NULL);
  600         glue->bit = differ_bit;
  601         glue->prefix = NULL;
  602         glue->parent = node->parent;
  603         for (i = 0; i < RADIX_FAMILIES; i++) {
  604             glue->data[i] = NULL;
  605             glue->node_num[i] = -1;
  606         }
  607         radix->num_active_node++;
  608         if (differ_bit < radix->maxbits &&
  609             BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) {
  610             glue->r = new_node;
  611             glue->l = node;
  612         } else {
  613             glue->r = node;
  614             glue->l = new_node;
  615         }
  616         new_node->parent = glue;
  617 
  618         if (node->parent == NULL) {
  619             INSIST(radix->head == node);
  620             radix->head = glue;
  621         } else if (node->parent->r == node) {
  622             node->parent->r = glue;
  623         } else {
  624             node->parent->l = glue;
  625         }
  626         node->parent = glue;
  627     }
  628 
  629     *target = new_node;
  630     return (ISC_R_SUCCESS);
  631 }
  632 
  633 void
  634 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
  635     isc_radix_node_t *parent, *child;
  636 
  637     REQUIRE(radix != NULL);
  638     REQUIRE(node != NULL);
  639 
  640     if (node->r && node->l) {
  641         /*
  642          * This might be a placeholder node -- have to check and
  643          * make sure there is a prefix associated with it!
  644          */
  645         if (node->prefix != NULL)
  646             _deref_prefix(node->prefix);
  647 
  648         node->prefix = NULL;
  649         memset(node->data, 0, sizeof(node->data));
  650         return;
  651     }
  652 
  653     if (node->r == NULL && node->l == NULL) {
  654         parent = node->parent;
  655         _deref_prefix(node->prefix);
  656 
  657         if (parent == NULL) {
  658             INSIST(radix->head == node);
  659             radix->head = NULL;
  660             isc_mem_put(radix->mctx, node, sizeof(*node));
  661             radix->num_active_node--;
  662             return;
  663         }
  664 
  665         if (parent->r == node) {
  666             parent->r = NULL;
  667             child = parent->l;
  668         } else {
  669             INSIST(parent->l == node);
  670             parent->l = NULL;
  671             child = parent->r;
  672         }
  673 
  674         isc_mem_put(radix->mctx, node, sizeof(*node));
  675         radix->num_active_node--;
  676 
  677         if (parent->prefix)
  678             return;
  679 
  680         /* We need to remove parent too. */
  681         if (parent->parent == NULL) {
  682             INSIST(radix->head == parent);
  683             radix->head = child;
  684         } else if (parent->parent->r == parent) {
  685             parent->parent->r = child;
  686         } else {
  687             INSIST(parent->parent->l == parent);
  688             parent->parent->l = child;
  689         }
  690 
  691         child->parent = parent->parent;
  692         isc_mem_put(radix->mctx, parent, sizeof(*parent));
  693         radix->num_active_node--;
  694         return;
  695     }
  696 
  697     if (node->r) {
  698         child = node->r;
  699     } else {
  700         INSIST(node->l != NULL);
  701         child = node->l;
  702     }
  703 
  704     parent = node->parent;
  705     child->parent = parent;
  706 
  707     _deref_prefix(node->prefix);
  708 
  709     if (parent == NULL) {
  710         INSIST(radix->head == node);
  711         radix->head = child;
  712         isc_mem_put(radix->mctx, node, sizeof(*node));
  713         radix->num_active_node--;
  714         return;
  715     }
  716 
  717     isc_mem_put(radix->mctx, node, sizeof(*node));
  718     radix->num_active_node--;
  719 
  720     if (parent->r == node) {
  721         parent->r = child;
  722     } else {
  723         INSIST(parent->l == node);
  724         parent->l = child;
  725     }
  726 }
  727 
  728 /*
  729 Local Variables:
  730 c-basic-offset: 4
  731 indent-tabs-mode: t
  732 End:
  733 */