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

   1 /*      $NetBSD$        */
   2
   3 /*
   4  * Copyright (C) 2007-2009  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: radix.c,v 1.23 2009/01/18 23:48:14 tbox Exp */
  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_mem_t *mctx, 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                 memcpy(&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                 memcpy(&prefix->add.sin, dest, 4);
  72         }
  73
  74         prefix->family = family;
  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_mem_t *mctx, 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_put(mctx, prefix, 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                 int n = mask / 8;
 132                 int m = ((~0) << (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 = mctx;
 152         radix->maxbits = maxbits;
 153         radix->head = NULL;
 154         radix->num_active_node = 0;
 155         radix->num_added_node = 0;
 156         RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */
 157         radix->magic = RADIX_TREE_MAGIC;
 158         *target = radix;
 159         return (ISC_R_SUCCESS);
 160 }
 161
 162 /*
 163  * if func is supplied, it will be called as func(node->data)
 164  * before deleting the node
 165  */
 166
 167 static void
 168 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
 169
 170         REQUIRE(radix != NULL);
 171
 172         if (radix->head != NULL) {
 173
 174                 isc_radix_node_t *Xstack[RADIX_MAXBITS+1];
 175                 isc_radix_node_t **Xsp = Xstack;
 176                 isc_radix_node_t *Xrn = radix->head;
 177
 178                 while (Xrn != NULL) {
 179                         isc_radix_node_t *l = Xrn->l;
 180                         isc_radix_node_t *r = Xrn->r;
 181
 182                         if (Xrn->prefix != NULL) {
 183                                 _deref_prefix(radix->mctx, Xrn->prefix);
 184                                 if (func != NULL && (Xrn->data[0] != NULL ||
 185                                                      Xrn->data[1] != NULL))
 186                                         func(Xrn->data);
 187                         } else {
 188                                 INSIST(Xrn->data[0] == NULL &&
 189                                        Xrn->data[1] == 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 {
 216         REQUIRE(radix != NULL);
 217         _clear_radix(radix, func);
 218         isc_mem_put(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 {
 228         isc_radix_node_t *node;
 229
 230         REQUIRE(func != NULL);
 231
 232         RADIX_WALK(radix->head, node) {
 233                 func(node->prefix, node->data);
 234         } RADIX_WALK_END;
 235 }
 236
 237
 238 isc_result_t
 239 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
 240                  isc_prefix_t *prefix)
 241 {
 242         isc_radix_node_t *node;
 243         isc_radix_node_t *stack[RADIX_MAXBITS + 1];
 244         u_char *addr;
 245         isc_uint32_t bitlen;
 246         int tfamily = -1;
 247         int cnt = 0;
 248
 249         REQUIRE(radix != NULL);
 250         REQUIRE(prefix != NULL);
 251         REQUIRE(target != NULL && *target == NULL);
 252         RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);
 253
 254         *target = NULL;
 255
 256         if (radix->head == NULL) {
 257                 return (ISC_R_NOTFOUND);
 258         }
 259
 260         node = radix->head;
 261         addr = isc_prefix_touchar(prefix);
 262         bitlen = prefix->bitlen;
 263
 264         while (node->bit < bitlen) {
 265                 if (node->prefix)
 266                         stack[cnt++] = node;
 267
 268                 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
 269                         node = node->r;
 270                 else
 271                         node = node->l;
 272
 273                 if (node == NULL)
 274                         break;
 275         }
 276
 277         if (node && node->prefix)
 278                 stack[cnt++] = node;
 279
 280         while (--cnt >= 0) {
 281                 node = stack[cnt];
 282
 283                 if (_comp_with_mask(isc_prefix_tochar(node->prefix),
 284                                     isc_prefix_tochar(prefix),
 285                                     node->prefix->bitlen)) {
 286                         if (node->node_num[ISC_IS6(prefix->family)] != -1 &&
 287                                  ((*target == NULL) ||
 288                                   (*target)->node_num[ISC_IS6(tfamily)] >
 289                                    node->node_num[ISC_IS6(prefix->family)])) {
 290                                 *target = node;
 291                                 tfamily = prefix->family;
 292                         }
 293                 }
 294         }
 295
 296         if (*target == NULL) {
 297                 return (ISC_R_NOTFOUND);
 298         } else {
 299                 return (ISC_R_SUCCESS);
 300         }
 301 }
 302
 303 isc_result_t
 304 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
 305                  isc_radix_node_t *source, isc_prefix_t *prefix)
 306 {
 307         isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
 308         u_char *addr, *test_addr;
 309         isc_uint32_t bitlen, fam, check_bit, differ_bit;
 310         isc_uint32_t i, j, r;
 311         isc_result_t result;
 312
 313         REQUIRE(radix != NULL);
 314         REQUIRE(target != NULL && *target == NULL);
 315         REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
 316         RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
 317
 318         if (prefix == NULL)
 319                 prefix = source->prefix;
 320
 321         INSIST(prefix != NULL);
 322
 323         bitlen = prefix->bitlen;
 324         fam = prefix->family;
 325
 326         if (radix->head == NULL) {
 327                 node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
 328                 if (node == NULL)
 329                         return (ISC_R_NOMEMORY);
 330                 node->bit = bitlen;
 331                 node->node_num[0] = node->node_num[1] = -1;
 332                 node->prefix = NULL;
 333                 result = _ref_prefix(radix->mctx, &node->prefix, prefix);
 334                 if (result != ISC_R_SUCCESS) {
 335                         isc_mem_put(radix->mctx, node,
 336                                     sizeof(isc_radix_node_t));
 337                         return (result);
 338                 }
 339                 node->parent = NULL;
 340                 node->l = node->r = NULL;
 341                 if (source != NULL) {
 342                         /*
 343                          * If source is non-NULL, then we're merging in a
 344                          * node from an existing radix tree.  To keep
 345                          * the node_num values consistent, the calling
 346                          * function will add the total number of nodes
 347                          * added to num_added_node at the end of
 348                          * the merge operation--we don't do it here.
 349                          */
 350                         if (source->node_num[0] != -1)
 351                                 node->node_num[0] = radix->num_added_node +
 352                                                     source->node_num[0];
 353                         if (source->node_num[1] != -1)
 354                                 node->node_num[1] = radix->num_added_node +
 355                                                     source->node_num[1];
 356                         node->data[0] = source->data[0];
 357                         node->data[1] = source->data[1];
 358                 } else {
 359                         if (fam == AF_UNSPEC) {
 360                                 /* "any" or "none" */
 361                                 node->node_num[0] = node->node_num[1] =
 362                                         ++radix->num_added_node;
 363                         } else {
 364                                 node->node_num[ISC_IS6(fam)] =
 365                                         ++radix->num_added_node;
 366                         }
 367                         node->data[0] = NULL;
 368                         node->data[1] = NULL;
 369                 }
 370                 radix->head = node;
 371                 radix->num_active_node++;
 372                 *target = node;
 373                 return (ISC_R_SUCCESS);
 374         }
 375
 376         addr = isc_prefix_touchar(prefix);
 377         node = radix->head;
 378
 379         while (node->bit < bitlen || node->prefix == NULL) {
 380                 if (node->bit < radix->maxbits &&
 381                     BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
 382                 {
 383                         if (node->r == NULL)
 384                                 break;
 385                         node = node->r;
 386                 } else {
 387                         if (node->l == NULL)
 388                                 break;
 389                         node = node->l;
 390                 }
 391
 392                 INSIST(node != NULL);
 393         }
 394
 395         INSIST(node->prefix != NULL);
 396
 397         test_addr = isc_prefix_touchar(node->prefix);
 398         /* Find the first bit different. */
 399         check_bit = (node->bit < bitlen) ? node->bit : bitlen;
 400         differ_bit = 0;
 401         for (i = 0; i*8 < check_bit; i++) {
 402                 if ((r = (addr[i] ^ test_addr[i])) == 0) {
 403                         differ_bit = (i + 1) * 8;
 404                         continue;
 405                 }
 406                 /* I know the better way, but for now. */
 407                 for (j = 0; j < 8; j++) {
 408                         if (BIT_TEST (r, (0x80 >> j)))
 409                                 break;
 410                 }
 411                 /* Must be found. */
 412                 INSIST(j < 8);
 413                 differ_bit = i * 8 + j;
 414                 break;
 415         }
 416
 417         if (differ_bit > check_bit)
 418                 differ_bit = check_bit;
 419
 420         parent = node->parent;
 421         while (parent != NULL && parent->bit >= differ_bit) {
 422                 node = parent;
 423                 parent = node->parent;
 424         }
 425
 426         if (differ_bit == bitlen && node->bit == bitlen) {
 427                 if (node->prefix != NULL) {
 428                         /* Set node_num only if it hasn't been set before */
 429                         if (source != NULL) {
 430                                 /* Merging node */
 431                                 if (node->node_num[0] == -1 &&
 432                                     source->node_num[0] != -1) {
 433                                         node->node_num[0] =
 434                                                 radix->num_added_node +
 435                                                 source->node_num[0];
 436                                         node->data[0] = source->data[0];
 437                                 }
 438                                 if (node->node_num[1] == -1 &&
 439                                     source->node_num[0] != -1) {
 440                                         node->node_num[1] =
 441                                                 radix->num_added_node +
 442                                                 source->node_num[1];
 443                                         node->data[1] = source->data[1];
 444                                 }
 445                         } else {
 446                                 if (fam == AF_UNSPEC) {
 447                                         /* "any" or "none" */
 448                                         int next = radix->num_added_node + 1;
 449                                         if (node->node_num[0] == -1) {
 450                                                 node->node_num[0] = next;
 451                                                 radix->num_added_node = next;
 452                                         }
 453                                         if (node->node_num[1] == -1) {
 454                                                 node->node_num[1] = next;
 455                                                 radix->num_added_node = next;
 456                                         }
 457                                 } else {
 458                                         if (node->node_num[ISC_IS6(fam)] == -1)
 459                                                 node->node_num[ISC_IS6(fam)]
 460                                                    = ++radix->num_added_node;
 461                                 }
 462                         }
 463                         *target = node;
 464                         return (ISC_R_SUCCESS);
 465                 } else {
 466                         result =
 467                                 _ref_prefix(radix->mctx, &node->prefix, prefix);
 468                         if (result != ISC_R_SUCCESS)
 469                                 return (result);
 470                 }
 471                 INSIST(node->data[0] == NULL && node->node_num[0] == -1 &&
 472                        node->data[1] == NULL && node->node_num[1] == -1);
 473                 if (source != NULL) {
 474                         /* Merging node */
 475                         if (source->node_num[0] != -1) {
 476                                 node->node_num[0] = radix->num_added_node +
 477                                                     source->node_num[0];
 478                                 node->data[0] = source->data[0];
 479                         }
 480                         if (source->node_num[1] != -1) {
 481                                 node->node_num[1] = radix->num_added_node +
 482                                                     source->node_num[1];
 483                                 node->data[1] = source->data[1];
 484                         }
 485                 } else {
 486                         if (fam == AF_UNSPEC) {
 487                                 /* "any" or "none" */
 488                                 node->node_num[0] = node->node_num[1] =
 489                                         ++radix->num_added_node;
 490                         } else {
 491                                 node->node_num[ISC_IS6(fam)] =
 492                                         ++radix->num_added_node;
 493                         }
 494                 }
 495                 *target = node;
 496                 return (ISC_R_SUCCESS);
 497         }
 498
 499         new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
 500         if (new_node == NULL)
 501                 return (ISC_R_NOMEMORY);
 502         if (node->bit != differ_bit && bitlen != differ_bit) {
 503                 glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
 504                 if (glue == NULL) {
 505                         isc_mem_put(radix->mctx, new_node,
 506                                     sizeof(isc_radix_node_t));
 507                         return (ISC_R_NOMEMORY);
 508                 }
 509         }
 510         new_node->bit = bitlen;
 511         new_node->prefix = NULL;
 512         result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
 513         if (result != ISC_R_SUCCESS) {
 514                 isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
 515                 if (glue != NULL)
 516                         isc_mem_put(radix->mctx, glue,
 517                                     sizeof(isc_radix_node_t));
 518                 return (result);
 519         }
 520         new_node->parent = NULL;
 521         new_node->l = new_node->r = NULL;
 522         new_node->node_num[0] = new_node->node_num[1] = -1;
 523         radix->num_active_node++;
 524
 525         if (source != NULL) {
 526                 /* Merging node */
 527                 if (source->node_num[0] != -1)
 528                         new_node->node_num[0] = radix->num_added_node +
 529                                                 source->node_num[0];
 530                 if (source->node_num[1] != -1)
 531                         new_node->node_num[1] = radix->num_added_node +
 532                                                 source->node_num[1];
 533                 new_node->data[0] = source->data[0];
 534                 new_node->data[1] = source->data[1];
 535         } else {
 536                 if (fam == AF_UNSPEC) {
 537                         /* "any" or "none" */
 538                         new_node->node_num[0] = new_node->node_num[1] =
 539                                 ++radix->num_added_node;
 540                 } else {
 541                         new_node->node_num[ISC_IS6(fam)] =
 542                                 ++radix->num_added_node;
 543                 }
 544                 new_node->data[0] = NULL;
 545                 new_node->data[1] = NULL;
 546         }
 547
 548         if (node->bit == differ_bit) {
 549                 INSIST(glue == NULL);
 550                 new_node->parent = node;
 551                 if (node->bit < radix->maxbits &&
 552                     BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
 553                 {
 554                         INSIST(node->r == NULL);
 555                         node->r = new_node;
 556                 } else {
 557                         INSIST(node->l == NULL);
 558                         node->l = new_node;
 559                 }
 560                 *target = new_node;
 561                 return (ISC_R_SUCCESS);
 562         }
 563
 564         if (bitlen == differ_bit) {
 565                 INSIST(glue == NULL);
 566                 if (bitlen < radix->maxbits &&
 567                     BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
 568                         new_node->r = node;
 569                 } else {
 570                         new_node->l = node;
 571                 }
 572                 new_node->parent = node->parent;
 573                 if (node->parent == NULL) {
 574                         INSIST(radix->head == node);
 575                         radix->head = new_node;
 576                 } else if (node->parent->r == node) {
 577                         node->parent->r = new_node;
 578                 } else {
 579                         node->parent->l = new_node;
 580                 }
 581                 node->parent = new_node;
 582         } else {
 583                 INSIST(glue != NULL);
 584                 glue->bit = differ_bit;
 585                 glue->prefix = NULL;
 586                 glue->parent = node->parent;
 587                 glue->data[0] = glue->data[1] = NULL;
 588                 glue->node_num[0] = glue->node_num[1] = -1;
 589                 radix->num_active_node++;
 590                 if (differ_bit < radix->maxbits &&
 591                     BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) {
 592                         glue->r = new_node;
 593                         glue->l = node;
 594                 } else {
 595                         glue->r = node;
 596                         glue->l = new_node;
 597                 }
 598                 new_node->parent = glue;
 599
 600                 if (node->parent == NULL) {
 601                         INSIST(radix->head == node);
 602                         radix->head = glue;
 603                 } else if (node->parent->r == node) {
 604                         node->parent->r = glue;
 605                 } else {
 606                         node->parent->l = glue;
 607                 }
 608                 node->parent = glue;
 609         }
 610
 611         *target = new_node;
 612         return (ISC_R_SUCCESS);
 613 }
 614
 615 void
 616 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
 617         isc_radix_node_t *parent, *child;
 618
 619         REQUIRE(radix != NULL);
 620         REQUIRE(node != NULL);
 621
 622         if (node->r && node->l) {
 623                 /*
 624                  * This might be a placeholder node -- have to check and
 625                  * make sure there is a prefix associated with it!
 626                  */
 627                 if (node->prefix != NULL)
 628                         _deref_prefix(radix->mctx, node->prefix);
 629
 630                 node->prefix = NULL;
 631                 node->data[0] = node->data[1] = NULL;
 632                 return;
 633         }
 634
 635         if (node->r == NULL && node->l == NULL) {
 636                 parent = node->parent;
 637                 _deref_prefix(radix->mctx, node->prefix);
 638                 isc_mem_put(radix->mctx, node, sizeof(*node));
 639                 radix->num_active_node--;
 640
 641                 if (parent == NULL) {
 642                         INSIST(radix->head == node);
 643                         radix->head = NULL;
 644                         return;
 645                 }
 646
 647                 if (parent->r == node) {
 648                         parent->r = NULL;
 649                         child = parent->l;
 650                 } else {
 651                         INSIST(parent->l == node);
 652                         parent->l = NULL;
 653                         child = parent->r;
 654                 }
 655
 656                 if (parent->prefix)
 657                         return;
 658
 659                 /* We need to remove parent too. */
 660
 661                 if (parent->parent == NULL) {
 662                         INSIST(radix->head == parent);
 663                         radix->head = child;
 664                 } else if (parent->parent->r == parent) {
 665                         parent->parent->r = child;
 666                 } else {
 667                         INSIST(parent->parent->l == parent);
 668                         parent->parent->l = child;
 669                 }
 670                 child->parent = parent->parent;
 671                 isc_mem_put(radix->mctx, parent, sizeof(*parent));
 672                 radix->num_active_node--;
 673                 return;
 674         }
 675
 676         if (node->r) {
 677                 child = node->r;
 678         } else {
 679                 INSIST(node->l != NULL);
 680                 child = node->l;
 681         }
 682         parent = node->parent;
 683         child->parent = parent;
 684
 685         _deref_prefix(radix->mctx, node->prefix);
 686         isc_mem_put(radix->mctx, node, sizeof(*node));
 687         radix->num_active_node--;
 688
 689         if (parent == NULL) {
 690                 INSIST(radix->head == node);
 691                 radix->head = child;
 692                 return;
 693         }
 694
 695         if (parent->r == node) {
 696                 parent->r = child;
 697         } else {
 698                 INSIST(parent->l == node);
 699                 parent->l = child;
 700         }
 701 }
 702
 703 /*
 704 Local Variables:
 705 c-basic-offset: 4
 706 indent-tabs-mode: t
 707 End:
 708 */