external/bsd/bind/dist/lib/isc/radix.c

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