radix.c 17 KB
Newer Older
1
/*
Automatic Updater's avatar
Automatic Updater committed
2
 * Copyright (C) 2007, 2008  Internet Systems Consortium, Inc. ("ISC")
Automatic Updater's avatar
Automatic Updater committed
3 4 5 6 7 8 9 10 11 12 13 14
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
15 16
 */

17
/* $Id: radix.c,v 1.16 2008/09/12 06:02:31 each Exp $ */
Automatic Updater's avatar
Automatic Updater committed
18

19 20 21 22 23 24
/*
 * This source was adapted from MRT's RCS Ids:
 * Id: radix.c,v 1.10.2.1 1999/11/29 05:16:24 masaki Exp
 * Id: prefix.c,v 1.37.2.9 2000/03/10 02:53:19 labovit Exp
 */

25 26
#include <config.h>

27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
#include <isc/mem.h>
#include <isc/types.h>
#include <isc/util.h>
#include <isc/radix.h>

static isc_result_t
_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family,
	    void *dest, int bitlen);

static void
_deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix);

static isc_result_t
_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix);

static int
_comp_with_mask(void *addr, void *dest, u_int mask);

static void
Mark Andrews's avatar
Mark Andrews committed
46
_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
47 48 49 50 51 52 53

static isc_result_t
_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
	    int bitlen)
{
	isc_prefix_t *prefix;

Mark Andrews's avatar
Mark Andrews committed
54 55
	REQUIRE(target != NULL);

56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
	if (family != AF_INET6 && family != AF_INET)
		return (ISC_R_NOTIMPLEMENTED);

	prefix = isc_mem_get(mctx, sizeof(isc_prefix_t));
	if (prefix == NULL)
		return (ISC_R_NOMEMORY);

	if (family == AF_INET6) {
		prefix->bitlen = (bitlen >= 0) ? bitlen : 128;
		memcpy(&prefix->add.sin6, dest, 16);
	} else {
		prefix->bitlen = (bitlen >= 0) ? bitlen : 32;
		memcpy(&prefix->add.sin, dest, 4);
	}

	prefix->family = family;

	isc_refcount_init(&prefix->refcount, 1);

	*target = prefix;
	return (ISC_R_SUCCESS);
}

Automatic Updater's avatar
Automatic Updater committed
79
static void
80 81 82 83 84 85 86 87 88 89
_deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix) {
	int refs;

	if (prefix == NULL)
		return;

	isc_refcount_decrement(&prefix->refcount, &refs);

	if (refs <= 0) {
		isc_refcount_destroy(&prefix->refcount);
Mark Andrews's avatar
Mark Andrews committed
90
		isc_mem_put(mctx, prefix, sizeof(isc_prefix_t));
91 92 93 94 95
	}
}

static isc_result_t
_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
Mark Andrews's avatar
Mark Andrews committed
96 97 98 99 100 101 102 103 104 105 106 107 108
	INSIST(prefix != NULL);
	INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
	       (prefix->family == AF_INET6 && prefix->bitlen <= 128));
	REQUIRE(target != NULL);

	/* If this prefix is a static allocation, copy it into new memory */
	if (isc_refcount_current(&prefix->refcount) == 0) {
		isc_result_t ret;
		ret = _new_prefix(mctx, target, prefix->family,
				  &prefix->add, prefix->bitlen);
		if (ret == ISC_R_SUCCESS)
			isc_refcount_destroy(&prefix->refcount);
		return ret;
109 110
	}

Mark Andrews's avatar
Mark Andrews committed
111 112
	isc_refcount_increment(&prefix->refcount, NULL);

113 114 115 116
	*target = prefix;
	return (ISC_R_SUCCESS);
}

Automatic Updater's avatar
Automatic Updater committed
117
static int
118 119
_comp_with_mask(void *addr, void *dest, u_int mask) {

120 121 122
	/* Mask length of zero matches everything */
	if (mask == 0)
		return (1);
123

124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
	if (memcmp(addr, dest, mask / 8) == 0) {
		int n = mask / 8;
		int m = ((~0) << (8 - (mask % 8)));

		if ((mask % 8) == 0 ||
		    (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
			return (1);
	}
	return (0);
}

isc_result_t
isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
	isc_radix_tree_t *radix;

Mark Andrews's avatar
Mark Andrews committed
139 140
	REQUIRE(target != NULL);

141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
	radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
	if (radix == NULL)
		return (ISC_R_NOMEMORY);

	radix->mctx = mctx;
	radix->maxbits = maxbits;
	radix->head = NULL;
	radix->num_active_node = 0;
	radix->num_added_node = 0;
	RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */
	radix->magic = RADIX_TREE_MAGIC;
	*target = radix;
	return (ISC_R_SUCCESS);
}

/*
 * if func is supplied, it will be called as func(node->data)
 * before deleting the node
 */

static void
Mark Andrews's avatar
Mark Andrews committed
162
_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
163

Mark Andrews's avatar
Mark Andrews committed
164
	REQUIRE(radix != NULL);
165

Mark Andrews's avatar
Mark Andrews committed
166
	if (radix->head != NULL) {
167 168 169 170 171 172 173 174 175

		isc_radix_node_t *Xstack[RADIX_MAXBITS+1];
		isc_radix_node_t **Xsp = Xstack;
		isc_radix_node_t *Xrn = radix->head;

		while (Xrn != NULL) {
			isc_radix_node_t *l = Xrn->l;
			isc_radix_node_t *r = Xrn->r;

Mark Andrews's avatar
Mark Andrews committed
176
			if (Xrn->prefix != NULL) {
177
				_deref_prefix(radix->mctx, Xrn->prefix);
178
				if (func != NULL && (Xrn->data[0] != NULL ||
Automatic Updater's avatar
Automatic Updater committed
179
						     Xrn->data[1] != NULL))
180 181
					func(Xrn->data);
			} else {
182
				INSIST(Xrn->data[0] == NULL &&
Automatic Updater's avatar
Automatic Updater committed
183
				       Xrn->data[1] == NULL);
184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207
			}

			isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
			radix->num_active_node--;

			if (l != NULL) {
				if (r != NULL) {
					*Xsp++ = r;
				}
				Xrn = l;
			} else if (r != NULL) {
				Xrn = r;
			} else if (Xsp != Xstack) {
				Xrn = *(--Xsp);
			} else {
				Xrn = NULL;
			}
		}
	}
	RUNTIME_CHECK(radix->num_active_node == 0);
}


void
208
isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func)
209
{
Mark Andrews's avatar
Mark Andrews committed
210
	REQUIRE(radix != NULL);
211 212 213 214 215 216 217 218 219
	_clear_radix(radix, func);
	isc_mem_put(radix->mctx, radix, sizeof(*radix));
}


/*
 * func will be called as func(node->prefix, node->data)
 */
void
Mark Andrews's avatar
Mark Andrews committed
220
isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func)
221 222 223
{
	isc_radix_node_t *node;

Mark Andrews's avatar
Mark Andrews committed
224
	REQUIRE(func != NULL);
225 226 227 228 229 230 231 232 233 234 235 236 237

	RADIX_WALK(radix->head, node) {
		func(node->prefix, node->data);
	} RADIX_WALK_END;
}


isc_result_t
isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
		 isc_prefix_t *prefix) {
	isc_radix_node_t *node;
	isc_radix_node_t *stack[RADIX_MAXBITS + 1];
	u_char *addr;
238 239
	isc_uint32_t bitlen;
	int family, tfamily = -1;
240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
	int cnt = 0;

	REQUIRE(radix != NULL);
	REQUIRE(prefix != NULL);
	RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);

	*target = NULL;

	if (radix->head == NULL) {
		return (ISC_R_NOTFOUND);
	}

	node = radix->head;
	addr = isc_prefix_touchar(prefix);
	bitlen = prefix->bitlen;

256

257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
	while (node->bit < bitlen) {
		if (node->prefix)
			stack[cnt++] = node;

		if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
			node = node->r;
		else
			node = node->l;

		if (node == NULL)
			break;
	}

	if (node && node->prefix)
		stack[cnt++] = node;

	while (--cnt >= 0) {
		node = stack[cnt];

Automatic Updater's avatar
Automatic Updater committed
276
		if (_comp_with_mask(isc_prefix_tochar(node->prefix),
277 278
				    isc_prefix_tochar(prefix),
				    node->prefix->bitlen)) {
279 280 281 282
			/* Bitlen 0 means "any" or "none",
			   which is always treated as IPv4 */
			family = node->prefix->bitlen ?
				 prefix->family : AF_INET;
283
			if (node->node_num[ISC_IS6(family)] != -1 &&
Automatic Updater's avatar
Automatic Updater committed
284 285
				 ((*target == NULL) ||
				  (*target)->node_num[ISC_IS6(tfamily)] >
286
				   node->node_num[ISC_IS6(family)])) {
Mark Andrews's avatar
Mark Andrews committed
287
				*target = node;
288 289
				tfamily = family;
			}
290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305
		}
	}

	if (*target == NULL) {
		return (ISC_R_NOTFOUND);
	} else {
		return (ISC_R_SUCCESS);
	}
}

isc_result_t
isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
		 isc_radix_node_t *source, isc_prefix_t *prefix)
{
	isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
	u_char *addr, *test_addr;
306
	isc_uint32_t bitlen, family, check_bit, differ_bit;
307 308 309
	isc_uint32_t i, j, r;
	isc_result_t result;

310 311 312
	REQUIRE(radix != NULL);
	REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
	RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
313

314
	if (prefix == NULL)
Mark Andrews's avatar
Mark Andrews committed
315
		prefix = source->prefix;
316

317
	INSIST(prefix != NULL);
318 319 320

	bitlen = prefix->bitlen;

Automatic Updater's avatar
Automatic Updater committed
321
	/* Bitlen 0 means "any" or "none", which is always treated as IPv4 */
322 323
	family = bitlen ? prefix->family : AF_INET;

324 325 326 327
	if (radix->head == NULL) {
		node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
		if (node == NULL)
			return (ISC_R_NOMEMORY);
328
		node->bit = bitlen;
329
		node->node_num[0] = node->node_num[1] = -1;
330 331 332 333 334 335 336 337
		result = _ref_prefix(radix->mctx, &node->prefix, prefix);
		if (result != ISC_R_SUCCESS) {
			isc_mem_put(radix->mctx, node,
				    sizeof(isc_radix_node_t));
			return (result);
		}
		node->parent = NULL;
		node->l = node->r = NULL;
338 339 340 341 342 343 344 345 346
		if (source != NULL) {
			/*
			 * If source is non-NULL, then we're merging in a
			 * node from an existing radix tree.  To keep
			 * the node_num values consistent, the calling
			 * function will add the total number of nodes
			 * added to num_added_node at the end of
			 * the merge operation--we don't do it here.
			 */
347 348 349 350 351 352 353 354
			if (source->node_num[0] != -1)
				node->node_num[0] = radix->num_added_node +
						    source->node_num[0];
			if (source->node_num[1] != -1)
				node->node_num[1] = radix->num_added_node +
						    source->node_num[1];
			node->data[0] = source->data[0];
			node->data[1] = source->data[1];
355
		} else {
356 357 358 359
			node->node_num[ISC_IS6(family)] =
				++radix->num_added_node;
			node->data[0] = NULL;
			node->data[1] = NULL;
360
		}
361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385
		radix->head = node;
		radix->num_active_node++;
		*target = node;
		return (ISC_R_SUCCESS);
	}

	addr = isc_prefix_touchar(prefix);
	node = radix->head;

	while (node->bit < bitlen || node->prefix == NULL) {
		if (node->bit < radix->maxbits &&
		    BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
		{
			if (node->r == NULL)
				break;
			node = node->r;
		} else {
			if (node->l == NULL)
				break;
			node = node->l;
		}

		INSIST(node != NULL);
	}

386
	INSIST(node->prefix != NULL);
387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411

	test_addr = isc_prefix_touchar(node->prefix);
	/* Find the first bit different. */
	check_bit = (node->bit < bitlen) ? node->bit : bitlen;
	differ_bit = 0;
	for (i = 0; i*8 < check_bit; i++) {
		if ((r = (addr[i] ^ test_addr[i])) == 0) {
			differ_bit = (i + 1) * 8;
			continue;
		}
		/* I know the better way, but for now. */
		for (j = 0; j < 8; j++) {
			if (BIT_TEST (r, (0x80 >> j)))
				break;
		}
		/* Must be found. */
		INSIST(j < 8);
		differ_bit = i * 8 + j;
		break;
	}

	if (differ_bit > check_bit)
		differ_bit = check_bit;

	parent = node->parent;
412
	while (parent != NULL && parent->bit >= differ_bit) {
413 414 415 416 417
		node = parent;
		parent = node->parent;
	}

	if (differ_bit == bitlen && node->bit == bitlen) {
418
		if (node->prefix != NULL) {
419
			/* Set node_num only if it hasn't been set before */
420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440
                        if (source != NULL) {
                                /* Merging node */
                                if (node->node_num[0] == -1 &&
                                    source->node_num[0] != -1) {
                                        node->node_num[0] =
                                                radix->num_added_node +
                                                source->node_num[0];
                                        node->data[0] = source->data[0];
                                }
                                if (node->node_num[1] == -1 &&
                                    source->node_num[0] != -1) {
                                        node->node_num[1] =
                                                radix->num_added_node +
                                                source->node_num[1];
                                        node->data[1] = source->data[1];
                                }
                        } else {
                                if (node->node_num[ISC_IS6(family)] == -1)
                                        node->node_num[ISC_IS6(family)] =
                                                 ++radix->num_added_node;
                        }
441 442
			*target = node;
			return (ISC_R_SUCCESS);
443 444 445 446 447 448
                } else {
                        result =
                                _ref_prefix(radix->mctx, &node->prefix, prefix);
                        if (result != ISC_R_SUCCESS)
                                return (result);
                }
449 450
		INSIST(node->data[0] == NULL && node->node_num[0] == -1 &&
		       node->data[1] == NULL && node->node_num[1] == -1);
451 452
		if (source != NULL) {
			/* Merging node */
453 454 455 456 457 458 459 460 461 462
                        if (source->node_num[0] != -1) {
                                node->node_num[0] = radix->num_added_node +
                                                    source->node_num[0];
                                node->data[0] = source->data[0];
                        }
                        if (source->node_num[1] != -1) {
                                node->node_num[1] = radix->num_added_node +
                                                    source->node_num[1];
                                node->data[1] = source->data[1];
                        }
463
		} else {
464 465
			node->node_num[ISC_IS6(family)] =
				++radix->num_added_node;
466
		}
467 468 469 470 471 472 473 474 475 476 477 478 479 480 481
		*target = node;
		return (ISC_R_SUCCESS);
	}

	new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
	if (new_node == NULL)
		return (ISC_R_NOMEMORY);
	if (node->bit != differ_bit && bitlen != differ_bit) {
		glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
		if (glue == NULL) {
			isc_mem_put(radix->mctx, new_node,
				    sizeof(isc_radix_node_t));
			return (ISC_R_NOMEMORY);
		}
	}
482
	new_node->bit = bitlen;
483 484 485 486 487 488 489 490 491 492
	result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
	if (result != ISC_R_SUCCESS) {
		isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
		if (glue != NULL)
			isc_mem_put(radix->mctx, glue,
				    sizeof(isc_radix_node_t));
		return (result);
	}
	new_node->parent = NULL;
	new_node->l = new_node->r = NULL;
493
	new_node->node_num[0] = new_node->node_num[1] = -1;
494 495
	radix->num_active_node++;

496
	if (source != NULL) {
497
		/* Merging node */
498 499 500 501 502 503 504 505
		if (source->node_num[0] != -1)
			new_node->node_num[0] = radix->num_added_node +
						source->node_num[0];
		if (source->node_num[1] != -1)
			new_node->node_num[1] = radix->num_added_node +
						source->node_num[1];
		new_node->data[0] = source->data[0];
		new_node->data[1] = source->data[1];
Mark Andrews's avatar
Mark Andrews committed
506
	} else {
507 508 509
		new_node->node_num[ISC_IS6(family)] = ++radix->num_added_node;
		new_node->data[0] = NULL;
		new_node->data[1] = NULL;
Mark Andrews's avatar
Mark Andrews committed
510
	}
511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550

	if (node->bit == differ_bit) {
		INSIST(glue == NULL);
		new_node->parent = node;
		if (node->bit < radix->maxbits &&
		    BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
		{
			INSIST(node->r == NULL);
			node->r = new_node;
		} else {
			INSIST(node->l == NULL);
			node->l = new_node;
		}
		*target = new_node;
		return (ISC_R_SUCCESS);
	}

	if (bitlen == differ_bit) {
		INSIST(glue == NULL);
		if (bitlen < radix->maxbits &&
		    BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
			new_node->r = node;
		} else {
			new_node->l = node;
		}
		new_node->parent = node->parent;
		if (node->parent == NULL) {
			INSIST(radix->head == node);
			radix->head = new_node;
		} else if (node->parent->r == node) {
			node->parent->r = new_node;
		} else {
			node->parent->l = new_node;
		}
		node->parent = new_node;
	} else {
		INSIST(glue != NULL);
		glue->bit = differ_bit;
		glue->prefix = NULL;
		glue->parent = node->parent;
551 552
		glue->data[0] = glue->data[1] = NULL;
		glue->node_num[0] = glue->node_num[1] = -1;
553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590
		radix->num_active_node++;
		if (differ_bit < radix->maxbits &&
		    BIT_TEST(addr[differ_bit >> 3], 0x80 >> (differ_bit & 0x07))) {
			glue->r = new_node;
			glue->l = node;
		} else {
			glue->r = node;
			glue->l = new_node;
		}
		new_node->parent = glue;

		if (node->parent == NULL) {
			INSIST(radix->head == node);
			radix->head = glue;
		} else if (node->parent->r == node) {
			node->parent->r = glue;
		} else {
			node->parent->l = glue;
		}
		node->parent = glue;
	}

	*target = new_node;
	return (ISC_R_SUCCESS);
}

void
isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
	isc_radix_node_t *parent, *child;

	REQUIRE(radix != NULL);
	REQUIRE(node != NULL);

	if (node->r && node->l) {
		/*
		 * This might be a placeholder node -- have to check and
		 * make sure there is a prefix aossciated with it!
		 */
Automatic Updater's avatar
Automatic Updater committed
591
		if (node->prefix != NULL)
592 593 594
			_deref_prefix(radix->mctx, node->prefix);

		node->prefix = NULL;
595
		node->data[0] = node->data[1] = NULL;
596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672
		return;
	}

	if (node->r == NULL && node->l == NULL) {
		parent = node->parent;
		_deref_prefix(radix->mctx, node->prefix);
		isc_mem_put(radix->mctx, node, sizeof(*node));
		radix->num_active_node--;

		if (parent == NULL) {
			INSIST(radix->head == node);
			radix->head = NULL;
			return;
		}

		if (parent->r == node) {
			parent->r = NULL;
			child = parent->l;
		} else {
			INSIST(parent->l == node);
			parent->l = NULL;
			child = parent->r;
		}

		if (parent->prefix)
			return;

		/* We need to remove parent too. */

		if (parent->parent == NULL) {
			INSIST(radix->head == parent);
			radix->head = child;
		} else if (parent->parent->r == parent) {
			parent->parent->r = child;
		} else {
			INSIST(parent->parent->l == parent);
			parent->parent->l = child;
		}
		child->parent = parent->parent;
		isc_mem_put(radix->mctx, parent, sizeof(*parent));
		radix->num_active_node--;
		return;
	}

	if (node->r) {
		child = node->r;
	} else {
		INSIST(node->l != NULL);
		child = node->l;
	}
	parent = node->parent;
	child->parent = parent;

	_deref_prefix(radix->mctx, node->prefix);
	isc_mem_put(radix->mctx, node, sizeof(*node));
	radix->num_active_node--;

	if (parent == NULL) {
		INSIST(radix->head == node);
		radix->head = child;
		return;
	}

	if (parent->r == node) {
		parent->r = child;
	} else {
		INSIST(parent->l == node);
		parent->l = child;
	}
}

/*
Local Variables:
c-basic-offset: 4
indent-tabs-mode: t
End:
*/