contrib/bind9/lib/isc/radix.c

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