2 * Copyright (C) 2007-2009, 2011-2013 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.
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_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_mem_attach(mctx, &prefix->mctx);
76 isc_refcount_init(&prefix->refcount, 1);
79 return (ISC_R_SUCCESS);
83 _deref_prefix(isc_prefix_t *prefix) {
89 isc_refcount_decrement(&prefix->refcount, &refs);
92 isc_refcount_destroy(&prefix->refcount);
93 isc_mem_putanddetach(&prefix->mctx, prefix,
94 sizeof(isc_prefix_t));
99 _ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
100 INSIST(prefix != NULL);
101 INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
102 (prefix->family == AF_INET6 && prefix->bitlen <= 128) ||
103 (prefix->family == AF_UNSPEC && prefix->bitlen == 0));
104 REQUIRE(target != NULL && *target == NULL);
107 * If this prefix is a static allocation, copy it into new memory.
108 * (Note, the refcount still has to be destroyed by the calling
111 if (isc_refcount_current(&prefix->refcount) == 0) {
113 ret = _new_prefix(mctx, target, prefix->family,
114 &prefix->add, prefix->bitlen);
118 isc_refcount_increment(&prefix->refcount, NULL);
121 return (ISC_R_SUCCESS);
125 _comp_with_mask(void *addr, void *dest, u_int mask) {
127 /* Mask length of zero matches everything */
131 if (memcmp(addr, dest, mask / 8) == 0) {
133 int m = ((~0) << (8 - (mask % 8)));
135 if ((mask % 8) == 0 ||
136 (((u_char *)addr)[n] & m) == (((u_char *)dest)[n] & m))
143 isc_radix_create(isc_mem_t *mctx, isc_radix_tree_t **target, int maxbits) {
144 isc_radix_tree_t *radix;
146 REQUIRE(target != NULL && *target == NULL);
148 radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
150 return (ISC_R_NOMEMORY);
153 isc_mem_attach(mctx, &radix->mctx);
154 radix->maxbits = maxbits;
156 radix->num_active_node = 0;
157 radix->num_added_node = 0;
158 RUNTIME_CHECK(maxbits <= RADIX_MAXBITS); /* XXX */
159 radix->magic = RADIX_TREE_MAGIC;
161 return (ISC_R_SUCCESS);
165 * if func is supplied, it will be called as func(node->data)
166 * before deleting the node
170 _clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
172 REQUIRE(radix != NULL);
174 if (radix->head != NULL) {
175 isc_radix_node_t *Xstack[RADIX_MAXBITS+1];
176 isc_radix_node_t **Xsp = Xstack;
177 isc_radix_node_t *Xrn = radix->head;
179 while (Xrn != NULL) {
180 isc_radix_node_t *l = Xrn->l;
181 isc_radix_node_t *r = Xrn->r;
183 if (Xrn->prefix != NULL) {
184 _deref_prefix(Xrn->prefix);
185 if (func != NULL && (Xrn->data[0] != NULL ||
186 Xrn->data[1] != NULL))
189 INSIST(Xrn->data[0] == NULL &&
190 Xrn->data[1] == NULL);
193 isc_mem_put(radix->mctx, Xrn, sizeof(*Xrn));
194 radix->num_active_node--;
201 } else if (r != NULL) {
203 } else if (Xsp != Xstack) {
210 RUNTIME_CHECK(radix->num_active_node == 0);
215 isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
216 REQUIRE(radix != NULL);
217 _clear_radix(radix, func);
218 isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix));
223 * func will be called as func(node->prefix, node->data)
226 isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) {
227 isc_radix_node_t *node;
229 REQUIRE(func != NULL);
231 RADIX_WALK(radix->head, node) {
232 func(node->prefix, node->data);
238 isc_radix_search(isc_radix_tree_t *radix, isc_radix_node_t **target,
239 isc_prefix_t *prefix)
241 isc_radix_node_t *node;
242 isc_radix_node_t *stack[RADIX_MAXBITS + 1];
248 REQUIRE(radix != NULL);
249 REQUIRE(prefix != NULL);
250 REQUIRE(target != NULL && *target == NULL);
251 RUNTIME_CHECK(prefix->bitlen <= radix->maxbits);
255 if (radix->head == NULL) {
256 return (ISC_R_NOTFOUND);
260 addr = isc_prefix_touchar(prefix);
261 bitlen = prefix->bitlen;
263 while (node->bit < bitlen) {
267 if (BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
276 if (node && node->prefix)
282 if (_comp_with_mask(isc_prefix_tochar(node->prefix),
283 isc_prefix_tochar(prefix),
284 node->prefix->bitlen)) {
285 if (node->node_num[ISC_IS6(prefix->family)] != -1 &&
286 ((*target == NULL) ||
287 (*target)->node_num[ISC_IS6(tfamily)] >
288 node->node_num[ISC_IS6(prefix->family)])) {
290 tfamily = prefix->family;
295 if (*target == NULL) {
296 return (ISC_R_NOTFOUND);
298 return (ISC_R_SUCCESS);
303 isc_radix_insert(isc_radix_tree_t *radix, isc_radix_node_t **target,
304 isc_radix_node_t *source, isc_prefix_t *prefix)
306 isc_radix_node_t *node, *new_node, *parent, *glue = NULL;
307 u_char *addr, *test_addr;
308 isc_uint32_t bitlen, fam, check_bit, differ_bit;
309 isc_uint32_t i, j, r;
312 REQUIRE(radix != NULL);
313 REQUIRE(target != NULL && *target == NULL);
314 REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
315 RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
318 prefix = source->prefix;
320 INSIST(prefix != NULL);
322 bitlen = prefix->bitlen;
323 fam = prefix->family;
325 if (radix->head == NULL) {
326 node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
328 return (ISC_R_NOMEMORY);
330 node->node_num[0] = node->node_num[1] = -1;
332 result = _ref_prefix(radix->mctx, &node->prefix, prefix);
333 if (result != ISC_R_SUCCESS) {
334 isc_mem_put(radix->mctx, node,
335 sizeof(isc_radix_node_t));
339 node->l = node->r = NULL;
340 if (source != NULL) {
342 * If source is non-NULL, then we're merging in a
343 * node from an existing radix tree. To keep
344 * the node_num values consistent, the calling
345 * function will add the total number of nodes
346 * added to num_added_node at the end of
347 * the merge operation--we don't do it here.
349 if (source->node_num[0] != -1)
350 node->node_num[0] = radix->num_added_node +
352 if (source->node_num[1] != -1)
353 node->node_num[1] = radix->num_added_node +
355 node->data[0] = source->data[0];
356 node->data[1] = source->data[1];
358 if (fam == AF_UNSPEC) {
359 /* "any" or "none" */
360 node->node_num[0] = node->node_num[1] =
361 ++radix->num_added_node;
363 node->node_num[ISC_IS6(fam)] =
364 ++radix->num_added_node;
366 node->data[0] = NULL;
367 node->data[1] = NULL;
370 radix->num_active_node++;
372 return (ISC_R_SUCCESS);
375 addr = isc_prefix_touchar(prefix);
378 while (node->bit < bitlen || node->prefix == NULL) {
379 if (node->bit < radix->maxbits &&
380 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
391 INSIST(node != NULL);
394 INSIST(node->prefix != NULL);
396 test_addr = isc_prefix_touchar(node->prefix);
397 /* Find the first bit different. */
398 check_bit = (node->bit < bitlen) ? node->bit : bitlen;
400 for (i = 0; i*8 < check_bit; i++) {
401 if ((r = (addr[i] ^ test_addr[i])) == 0) {
402 differ_bit = (i + 1) * 8;
405 /* I know the better way, but for now. */
406 for (j = 0; j < 8; j++) {
407 if (BIT_TEST (r, (0x80 >> j)))
412 differ_bit = i * 8 + j;
416 if (differ_bit > check_bit)
417 differ_bit = check_bit;
419 parent = node->parent;
420 while (parent != NULL && parent->bit >= differ_bit) {
422 parent = node->parent;
425 if (differ_bit == bitlen && node->bit == bitlen) {
426 if (node->prefix != NULL) {
427 /* Set node_num only if it hasn't been set before */
428 if (source != NULL) {
430 if (node->node_num[0] == -1 &&
431 source->node_num[0] != -1) {
433 radix->num_added_node +
435 node->data[0] = source->data[0];
437 if (node->node_num[1] == -1 &&
438 source->node_num[0] != -1) {
440 radix->num_added_node +
442 node->data[1] = source->data[1];
445 if (fam == AF_UNSPEC) {
446 /* "any" or "none" */
447 int next = radix->num_added_node + 1;
448 if (node->node_num[0] == -1) {
449 node->node_num[0] = next;
450 radix->num_added_node = next;
452 if (node->node_num[1] == -1) {
453 node->node_num[1] = next;
454 radix->num_added_node = next;
457 if (node->node_num[ISC_IS6(fam)] == -1)
458 node->node_num[ISC_IS6(fam)]
459 = ++radix->num_added_node;
463 return (ISC_R_SUCCESS);
465 result = _ref_prefix(radix->mctx,
466 &node->prefix, prefix);
467 if (result != ISC_R_SUCCESS)
470 INSIST(node->data[0] == NULL && node->node_num[0] == -1 &&
471 node->data[1] == NULL && node->node_num[1] == -1);
472 if (source != NULL) {
474 if (source->node_num[0] != -1) {
475 node->node_num[0] = radix->num_added_node +
477 node->data[0] = source->data[0];
479 if (source->node_num[1] != -1) {
480 node->node_num[1] = radix->num_added_node +
482 node->data[1] = source->data[1];
485 if (fam == AF_UNSPEC) {
486 /* "any" or "none" */
487 node->node_num[0] = node->node_num[1] =
488 ++radix->num_added_node;
490 node->node_num[ISC_IS6(fam)] =
491 ++radix->num_added_node;
495 return (ISC_R_SUCCESS);
498 new_node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
499 if (new_node == NULL)
500 return (ISC_R_NOMEMORY);
501 if (node->bit != differ_bit && bitlen != differ_bit) {
502 glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
504 isc_mem_put(radix->mctx, new_node,
505 sizeof(isc_radix_node_t));
506 return (ISC_R_NOMEMORY);
509 new_node->bit = bitlen;
510 new_node->prefix = NULL;
511 result = _ref_prefix(radix->mctx, &new_node->prefix, prefix);
512 if (result != ISC_R_SUCCESS) {
513 isc_mem_put(radix->mctx, new_node, sizeof(isc_radix_node_t));
515 isc_mem_put(radix->mctx, glue,
516 sizeof(isc_radix_node_t));
519 new_node->parent = NULL;
520 new_node->l = new_node->r = NULL;
521 new_node->node_num[0] = new_node->node_num[1] = -1;
522 radix->num_active_node++;
524 if (source != NULL) {
526 if (source->node_num[0] != -1)
527 new_node->node_num[0] = radix->num_added_node +
529 if (source->node_num[1] != -1)
530 new_node->node_num[1] = radix->num_added_node +
532 new_node->data[0] = source->data[0];
533 new_node->data[1] = source->data[1];
535 if (fam == AF_UNSPEC) {
536 /* "any" or "none" */
537 new_node->node_num[0] = new_node->node_num[1] =
538 ++radix->num_added_node;
540 new_node->node_num[ISC_IS6(fam)] =
541 ++radix->num_added_node;
543 new_node->data[0] = NULL;
544 new_node->data[1] = NULL;
547 if (node->bit == differ_bit) {
548 INSIST(glue == NULL);
549 new_node->parent = node;
550 if (node->bit < radix->maxbits &&
551 BIT_TEST(addr[node->bit >> 3], 0x80 >> (node->bit & 0x07)))
553 INSIST(node->r == NULL);
556 INSIST(node->l == NULL);
560 return (ISC_R_SUCCESS);
563 if (bitlen == differ_bit) {
564 INSIST(glue == NULL);
565 if (bitlen < radix->maxbits &&
566 BIT_TEST(test_addr[bitlen >> 3], 0x80 >> (bitlen & 0x07))) {
571 new_node->parent = node->parent;
572 if (node->parent == NULL) {
573 INSIST(radix->head == node);
574 radix->head = new_node;
575 } else if (node->parent->r == node) {
576 node->parent->r = new_node;
578 node->parent->l = new_node;
580 node->parent = new_node;
582 INSIST(glue != NULL);
583 glue->bit = differ_bit;
585 glue->parent = node->parent;
586 glue->data[0] = glue->data[1] = NULL;
587 glue->node_num[0] = glue->node_num[1] = -1;
588 radix->num_active_node++;
589 if (differ_bit < radix->maxbits &&
590 BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) {
597 new_node->parent = glue;
599 if (node->parent == NULL) {
600 INSIST(radix->head == node);
602 } else if (node->parent->r == node) {
603 node->parent->r = glue;
605 node->parent->l = glue;
611 return (ISC_R_SUCCESS);
615 isc_radix_remove(isc_radix_tree_t *radix, isc_radix_node_t *node) {
616 isc_radix_node_t *parent, *child;
618 REQUIRE(radix != NULL);
619 REQUIRE(node != NULL);
621 if (node->r && node->l) {
623 * This might be a placeholder node -- have to check and
624 * make sure there is a prefix associated with it!
626 if (node->prefix != NULL)
627 _deref_prefix(node->prefix);
630 node->data[0] = node->data[1] = NULL;
634 if (node->r == NULL && node->l == NULL) {
635 parent = node->parent;
636 _deref_prefix(node->prefix);
637 isc_mem_put(radix->mctx, node, sizeof(*node));
638 radix->num_active_node--;
640 if (parent == NULL) {
641 INSIST(radix->head == node);
646 if (parent->r == node) {
650 INSIST(parent->l == node);
658 /* We need to remove parent too. */
660 if (parent->parent == NULL) {
661 INSIST(radix->head == parent);
663 } else if (parent->parent->r == parent) {
664 parent->parent->r = child;
666 INSIST(parent->parent->l == parent);
667 parent->parent->l = child;
669 child->parent = parent->parent;
670 isc_mem_put(radix->mctx, parent, sizeof(*parent));
671 radix->num_active_node--;
678 INSIST(node->l != NULL);
681 parent = node->parent;
682 child->parent = parent;
684 _deref_prefix(node->prefix);
685 isc_mem_put(radix->mctx, node, sizeof(*node));
686 radix->num_active_node--;
688 if (parent == NULL) {
689 INSIST(radix->head == node);
694 if (parent->r == node) {
697 INSIST(parent->l == node);