contrib/bind9/lib/isc/radix.c

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