contrib/bind/lib/isc/radix.c

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