"Fossies" - the Fresh Open Source Software Archive

Member "bind-9.16.7/lib/isc/radix.c" (4 Sep 2020, 16465 Bytes) of package /linux/misc/dns/bind9/9.16.7/bind-9.16.7.tar.xz:


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