2 * Copyright (C) 2007-2009 Internet Systems Consortium, Inc. ("ISC")
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.
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.
17 /* $Id: radix.c,v 1.20.36.3 2009/01/18 23:47:41 tbox Exp $ */
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
28 #include <isc/types.h>
30 #include <isc/radix.h>
33 _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family,
34 void *dest, int bitlen);
37 _deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix);
40 _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix);
43 _comp_with_mask(void *addr, void *dest, u_int mask);
46 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
49 _new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
54 REQUIRE(target != NULL);
56 if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC)
57 return (ISC_R_NOTIMPLEMENTED);
59 prefix = isc_mem_get(mctx, sizeof(isc_prefix_t));
61 return (ISC_R_NOMEMORY);
63 if (family == AF_INET6) {
64 prefix->bitlen = (bitlen >= 0) ? bitlen : 128;
65 memcpy(&prefix->add.sin6, dest, 16);
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);
72 prefix->family = family;
74 isc_refcount_init(&prefix->refcount, 1);
77 return (ISC_R_SUCCESS);
81 _deref_prefix(isc_mem_t *mctx, isc_prefix_t *prefix) {
87 isc_refcount_decrement(&prefix->refcount, &refs);
90 isc_refcount_destroy(&prefix->refcount);
91 isc_mem_put(mctx, prefix, sizeof(isc_prefix_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);
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
108 if (isc_refcount_current(&prefix->refcount) == 0) {
110 ret = _new_prefix(mctx, target, prefix->family,
111 &prefix->add, prefix->bitlen);
115 isc_refcount_increment(&prefix->refcount, NULL);
118 return (ISC_R_SUCCESS);
122 _comp_with_mask(void *addr, void *dest, u_int mask) {
124 /* Mask length of zero matches everything */
128 if (memcmp(addr, dest, mask / 8) == 0) {
130 int m = ((~0) << (8 - (mask % 8)));
132 if ((mask % 8) == 0 ||
133 (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
140 isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
141 isc_radix_tree_t *radix;
143 REQUIRE(target != NULL && *target == NULL);
145 radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
147 return (ISC_R_NOMEMORY);
150 radix->maxbits = maxbits;
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;
157 return (ISC_R_SUCCESS);
161 * if func is supplied, it will be called as func(node->data)
162 * before deleting the node
166 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
168 REQUIRE(radix != NULL);
170 if (radix->head != NULL) {
172 isc_radix_node_t *Xstack[RADIX_MAXBITS+1];
173 isc_radix_node_t **Xsp = Xstack;
174 isc_radix_node_t *Xrn = radix->head;
176 while (Xrn != NULL) {
177 isc_radix_node_t *l = Xrn->l;
178 isc_radix_node_t *r = Xrn->r;
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))
186 INSIST(Xrn->data[0] == NULL &&
187 Xrn->data[1] == NULL);
190 isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
191 radix->num_active_node--;
198 } else if (r != NULL) {
200 } else if (Xsp != Xstack) {
207 RUNTIME_CHECK(radix->num_active_node == 0);
212 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func)
214 REQUIRE(radix != NULL);
215 _clear_radix(radix, func);
216 isc_mem_put(radix->mctx, radix, sizeof(*radix));
221 * func will be called as func(node->prefix, node->data)
224 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func)
226 isc_radix_node_t *node;
228 REQUIRE(func != NULL);
230 RADIX_WALK(radix->head, node) {
231 func(node->prefix, node->data);
237 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
238 isc_prefix_t *prefix)
240 isc_radix_node_t *node;
241 isc_radix_node_t *stack[RADIX_MAXBITS + 1];
247 REQUIRE(radix != NULL);
248 REQUIRE(prefix != NULL);
249 REQUIRE(target != NULL && *target == NULL);
250 RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);
254 if (radix->head == NULL) {
255 return (ISC_R_NOTFOUND);
259 addr = isc_prefix_touchar(prefix);
260 bitlen = prefix->bitlen;
262 while (node->bit < bitlen) {
266 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
275 if (node && node->prefix)
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)])) {
289 tfamily = prefix->family;
294 if (*target == NULL) {
295 return (ISC_R_NOTFOUND);
297 return (ISC_R_SUCCESS);
302 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
303 isc_radix_node_t *source, isc_prefix_t *prefix)
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;
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);
317 prefix = source->prefix;
319 INSIST(prefix != NULL);
321 bitlen = prefix->bitlen;
322 fam = prefix->family;
324 if (radix->head == NULL) {
325 node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
327 return (ISC_R_NOMEMORY);
329 node->node_num[0] = node->node_num[1] = -1;
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));
338 node->l = node->r = NULL;
339 if (source != NULL) {
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.
348 if (source->node_num[0] != -1)
349 node->node_num[0] = radix->num_added_node +
351 if (source->node_num[1] != -1)
352 node->node_num[1] = radix->num_added_node +
354 node->data[0] = source->data[0];
355 node->data[1] = source->data[1];
357 if (fam == AF_UNSPEC) {
358 /* "any" or "none" */
359 node->node_num[0] = node->node_num[1] =
360 ++radix->num_added_node;
362 node->node_num[ISC_IS6(fam)] =
363 ++radix->num_added_node;
365 node->data[0] = NULL;
366 node->data[1] = NULL;
369 radix->num_active_node++;
371 return (ISC_R_SUCCESS);
374 addr = isc_prefix_touchar(prefix);
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)))
390 INSIST(node != NULL);
393 INSIST(node->prefix != NULL);
395 test_addr = isc_prefix_touchar(node->prefix);
396 /* Find the first bit different. */
397 check_bit = (node->bit < bitlen) ? node->bit : bitlen;
399 for (i = 0; i*8 < check_bit; i++) {
400 if ((r = (addr[i] ^ test_addr[i])) == 0) {
401 differ_bit = (i + 1) * 8;
404 /* I know the better way, but for now. */
405 for (j = 0; j < 8; j++) {
406 if (BIT_TEST (r, (0x80 >> j)))
411 differ_bit = i * 8 + j;
415 if (differ_bit > check_bit)
416 differ_bit = check_bit;
418 parent = node->parent;
419 while (parent != NULL && parent->bit >= differ_bit) {
421 parent = node->parent;
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) {
429 if (node->node_num[0] == -1 &&
430 source->node_num[0] != -1) {
432 radix->num_added_node +
434 node->data[0] = source->data[0];
436 if (node->node_num[1] == -1 &&
437 source->node_num[0] != -1) {
439 radix->num_added_node +
441 node->data[1] = source->data[1];
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;
451 if (node->node_num[1] == -1) {
452 node->node_num[1] = next;
453 radix->num_added_node = next;
456 if (node->node_num[ISC_IS6(fam)] == -1)
457 node->node_num[ISC_IS6(fam)]
458 = ++radix->num_added_node;
462 return (ISC_R_SUCCESS);
465 _ref_prefix(radix->mctx, &node->prefix, prefix);
466 if (result != ISC_R_SUCCESS)
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) {
473 if (source->node_num[0] != -1) {
474 node->node_num[0] = radix->num_added_node +
476 node->data[0] = source->data[0];
478 if (source->node_num[1] != -1) {
479 node->node_num[1] = radix->num_added_node +
481 node->data[1] = source->data[1];
484 if (fam == AF_UNSPEC) {
485 /* "any" or "none" */
486 node->node_num[0] = node->node_num[1] =
487 ++radix->num_added_node;
489 node->node_num[ISC_IS6(fam)] =
490 ++radix->num_added_node;
494 return (ISC_R_SUCCESS);
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));
503 isc_mem_put(radix->mctx, new_node,
504 sizeof(isc_radix_node_t));
505 return (ISC_R_NOMEMORY);
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));
514 isc_mem_put(radix->mctx, glue,
515 sizeof(isc_radix_node_t));
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++;
523 if (source != NULL) {
525 if (source->node_num[0] != -1)
526 new_node->node_num[0] = radix->num_added_node +
528 if (source->node_num[1] != -1)
529 new_node->node_num[1] = radix->num_added_node +
531 new_node->data[0] = source->data[0];
532 new_node->data[1] = source->data[1];
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;
539 new_node->node_num[ISC_IS6(fam)] =
540 ++radix->num_added_node;
542 new_node->data[0] = NULL;
543 new_node->data[1] = NULL;
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)))
552 INSIST(node->r == NULL);
555 INSIST(node->l == NULL);
559 return (ISC_R_SUCCESS);
562 if (bitlen == differ_bit) {
563 INSIST(glue == NULL);
564 if (bitlen < radix->maxbits &&
565 BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
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;
577 node->parent->l = new_node;
579 node->parent = new_node;
581 INSIST(glue != NULL);
582 glue->bit = differ_bit;
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))) {
596 new_node->parent = glue;
598 if (node->parent == NULL) {
599 INSIST(radix->head == node);
601 } else if (node->parent->r == node) {
602 node->parent->r = glue;
604 node->parent->l = glue;
610 return (ISC_R_SUCCESS);
614 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
615 isc_radix_node_t *parent, *child;
617 REQUIRE(radix != NULL);
618 REQUIRE(node != NULL);
620 if (node->r && node->l) {
622 * This might be a placeholder node -- have to check and
623 * make sure there is a prefix associated with it!
625 if (node->prefix != NULL)
626 _deref_prefix(radix->mctx, node->prefix);
629 node->data[0] = node->data[1] = NULL;
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--;
639 if (parent == NULL) {
640 INSIST(radix->head == node);
645 if (parent->r == node) {
649 INSIST(parent->l == node);
657 /* We need to remove parent too. */
659 if (parent->parent == NULL) {
660 INSIST(radix->head == parent);
662 } else if (parent->parent->r == parent) {
663 parent->parent->r = child;
665 INSIST(parent->parent->l == parent);
666 parent->parent->l = child;
668 child->parent = parent->parent;
669 isc_mem_put(radix->mctx, parent, sizeof(*parent));
670 radix->num_active_node--;
677 INSIST(node->l != NULL);
680 parent = node->parent;
681 child->parent = parent;
683 _deref_prefix(radix->mctx, node->prefix);
684 isc_mem_put(radix->mctx, node, sizeof(*node));
685 radix->num_active_node--;
687 if (parent == NULL) {
688 INSIST(radix->head == node);
693 if (parent->r == node) {
696 INSIST(parent->l == node);