summaryrefslogtreecommitdiffstats
path: root/lib/isc/radix.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/isc/radix.c')
-rw-r--r--lib/isc/radix.c728
1 files changed, 728 insertions, 0 deletions
diff --git a/lib/isc/radix.c b/lib/isc/radix.c
new file mode 100644
index 0000000..6299dfe
--- /dev/null
+++ b/lib/isc/radix.c
@@ -0,0 +1,728 @@
+/*
+ * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * See the COPYRIGHT file distributed with this work for additional
+ * information regarding copyright ownership.
+ */
+
+
+/*
+ * 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
+ */
+
+#include <config.h>
+
+#include <inttypes.h>
+
+#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_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
+_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func);
+
+static isc_result_t
+_new_prefix(isc_mem_t *mctx, isc_prefix_t **target, int family, void *dest,
+ int bitlen)
+{
+ isc_prefix_t *prefix;
+
+ REQUIRE(target != NULL);
+
+ if (family != AF_INET6 && family != AF_INET && family != AF_UNSPEC)
+ 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;
+ memmove(&prefix->add.sin6, dest, 16);
+ } else {
+ /* AF_UNSPEC is "any" or "none"--treat it as AF_INET */
+ prefix->bitlen = (bitlen >= 0) ? bitlen : 32;
+ memmove(&prefix->add.sin, dest, 4);
+ }
+
+ prefix->family = family;
+ prefix->ecs = false;
+ prefix->mctx = NULL;
+ isc_mem_attach(mctx, &prefix->mctx);
+
+ isc_refcount_init(&prefix->refcount, 1);
+
+ *target = prefix;
+ return (ISC_R_SUCCESS);
+}
+
+static void
+_deref_prefix(isc_prefix_t *prefix) {
+ int refs;
+
+ if (prefix == NULL)
+ return;
+
+ isc_refcount_decrement(&prefix->refcount, &refs);
+
+ if (refs <= 0) {
+ isc_refcount_destroy(&prefix->refcount);
+ isc_mem_putanddetach(&prefix->mctx, prefix,
+ sizeof(isc_prefix_t));
+ }
+}
+
+static isc_result_t
+_ref_prefix(isc_mem_t *mctx, isc_prefix_t **target, isc_prefix_t *prefix) {
+ INSIST(prefix != NULL);
+ INSIST((prefix->family == AF_INET && prefix->bitlen <= 32) ||
+ (prefix->family == AF_INET6 && prefix->bitlen <= 128) ||
+ (prefix->family == AF_UNSPEC && prefix->bitlen == 0));
+ REQUIRE(target != NULL && *target == NULL);
+
+ /*
+ * If this prefix is a static allocation, copy it into new memory.
+ * (Note, the refcount still has to be destroyed by the calling
+ * routine.)
+ */
+ if (isc_refcount_current(&prefix->refcount) == 0) {
+ isc_result_t ret;
+ ret = _new_prefix(mctx, target, prefix->family,
+ &prefix->add, prefix->bitlen);
+ return (ret);
+ }
+
+ isc_refcount_increment(&prefix->refcount, NULL);
+
+ *target = prefix;
+ return (ISC_R_SUCCESS);
+}
+
+static int
+_comp_with_mask(void *addr, void *dest, u_int mask) {
+
+ /* Mask length of zero matches everything */
+ if (mask == 0)
+ return (1);
+
+ if (memcmp(addr, dest, mask / 8) == 0) {
+ u_int n = mask / 8;
+ u_int m = ((~0U) << (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;
+
+ REQUIRE(target != NULL && *target == NULL);
+
+ radix = isc_mem_get(mctx, sizeof(isc_radix_tree_t));
+ if (radix == NULL)
+ return (ISC_R_NOMEMORY);
+
+ radix->mctx = NULL;
+ isc_mem_attach(mctx, &radix->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
+_clear_radix(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
+ REQUIRE(radix != NULL);
+
+ if (radix->head != NULL) {
+ 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;
+
+ if (Xrn->prefix != NULL) {
+ _deref_prefix(Xrn->prefix);
+ if (func != NULL)
+ func(Xrn->data);
+ } else {
+ INSIST(Xrn->data[RADIX_V4] == NULL &&
+ Xrn->data[RADIX_V6] == NULL &&
+ Xrn->data[RADIX_V4_ECS] == NULL &&
+ Xrn->data[RADIX_V6_ECS] == NULL);
+ }
+
+ 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
+isc_radix_destroy(isc_radix_tree_t *radix, isc_radix_destroyfunc_t func) {
+ REQUIRE(radix != NULL);
+ _clear_radix(radix, func);
+ isc_mem_putanddetach(&radix->mctx, radix, sizeof(*radix));
+}
+
+
+/*
+ * func will be called as func(node->prefix, node->data)
+ */
+void
+isc_radix_process(isc_radix_tree_t *radix, isc_radix_processfunc_t func) {
+ isc_radix_node_t *node;
+
+ REQUIRE(func != NULL);
+
+ 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;
+ uint32_t bitlen;
+ int tfam = -1, cnt = 0;
+
+ REQUIRE(radix != NULL);
+ REQUIRE(prefix != NULL);
+ REQUIRE(target != NULL && *target == 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;
+
+ 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];
+
+ if (prefix->bitlen < node->bit)
+ continue;
+
+ if (_comp_with_mask(isc_prefix_tochar(node->prefix),
+ isc_prefix_tochar(prefix),
+ node->prefix->bitlen))
+ {
+ int fam = ISC_RADIX_FAMILY(prefix);
+ if (node->node_num[fam] != -1 &&
+ ((*target == NULL) ||
+ (*target)->node_num[tfam] > node->node_num[fam]))
+ {
+ *target = node;
+ tfam = fam;
+ }
+ }
+ }
+
+ 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;
+ uint32_t bitlen, fam, check_bit, differ_bit;
+ uint32_t i, j, r;
+ isc_result_t result;
+
+ REQUIRE(radix != NULL);
+ REQUIRE(target != NULL && *target == NULL);
+ REQUIRE(prefix != NULL || (source != NULL && source->prefix != NULL));
+ RUNTIME_CHECK(prefix == NULL || prefix->bitlen <= radix->maxbits);
+
+ if (prefix == NULL)
+ prefix = source->prefix;
+
+ INSIST(prefix != NULL);
+
+ bitlen = prefix->bitlen;
+ fam = prefix->family;
+
+ if (radix->head == NULL) {
+ node = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
+ if (node == NULL)
+ return (ISC_R_NOMEMORY);
+ node->bit = bitlen;
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ node->node_num[i] = -1;
+ }
+ node->prefix = NULL;
+ 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;
+ 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.
+ */
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ if (source->node_num[i] != -1) {
+ node->node_num[i] =
+ radix->num_added_node +
+ source->node_num[i];
+ }
+ node->data[i] = source->data[i];
+ }
+ } else {
+ int next = ++radix->num_added_node;
+ if (fam == AF_UNSPEC) {
+ /* "any" or "none" */
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ node->node_num[i] = next;
+ }
+ } else {
+ node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
+ }
+
+ memset(node->data, 0, sizeof(node->data));
+ }
+ 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);
+ }
+
+ INSIST(node->prefix != NULL);
+
+ 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;
+ while (parent != NULL && parent->bit >= differ_bit) {
+ node = parent;
+ parent = node->parent;
+ }
+
+ if (differ_bit == bitlen && node->bit == bitlen) {
+ if (node->prefix != NULL) {
+ /* Set node_num only if it hasn't been set before */
+ if (source != NULL) {
+ /* Merging nodes */
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ if (node->node_num[i] == -1 &&
+ source->node_num[i] != -1) {
+ node->node_num[i] =
+ radix->num_added_node +
+ source->node_num[i];
+ node->data[i] = source->data[i];
+ }
+ }
+ } else {
+ if (fam == AF_UNSPEC) {
+ /* "any" or "none" */
+ int next = radix->num_added_node + 1;
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ if (node->node_num[i] == -1) {
+ node->node_num[i] =
+ next;
+ radix->num_added_node =
+ next;
+ }
+ }
+ } else {
+ int foff = ISC_RADIX_FAMILY(prefix);
+ if (node->node_num[foff] == -1) {
+ node->node_num[foff] =
+ ++radix->num_added_node;
+ }
+ }
+ }
+ *target = node;
+ return (ISC_R_SUCCESS);
+ } else {
+ result = _ref_prefix(radix->mctx,
+ &node->prefix, prefix);
+ if (result != ISC_R_SUCCESS)
+ return (result);
+ }
+
+ /* Check everything is null and empty before we proceed */
+ INSIST(node->data[RADIX_V4] == NULL &&
+ node->node_num[RADIX_V4] == -1 &&
+ node->data[RADIX_V6] == NULL &&
+ node->node_num[RADIX_V6] == -1 &&
+ node->data[RADIX_V4_ECS] == NULL &&
+ node->node_num[RADIX_V4_ECS] == -1 &&
+ node->data[RADIX_V6_ECS] == NULL &&
+ node->node_num[RADIX_V6_ECS] == -1);
+
+ if (source != NULL) {
+ /* Merging node */
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ int cur = radix->num_added_node;
+ if (source->node_num[i] != -1) {
+ node->node_num[i] =
+ source->node_num[i] + cur;
+ node->data[i] = source->data[i];
+ }
+ }
+ } else {
+ int next = ++radix->num_added_node;
+ if (fam == AF_UNSPEC) {
+ /* "any" or "none" */
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ node->node_num[i] = next;
+ }
+ } else {
+ node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
+ }
+ }
+ *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);
+ }
+ }
+ new_node->bit = bitlen;
+ new_node->prefix = NULL;
+ 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;
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ new_node->node_num[i] = -1;
+ new_node->data[i] = NULL;
+ }
+ radix->num_active_node++;
+
+ if (source != NULL) {
+ /* Merging node */
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ int cur = radix->num_added_node;
+ if (source->node_num[i] != -1) {
+ new_node->node_num[i] =
+ source->node_num[i] + cur;
+ new_node->data[i] = source->data[i];
+ }
+ }
+ } else {
+ int next = ++radix->num_added_node;
+ if (fam == AF_UNSPEC) {
+ /* "any" or "none" */
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ new_node->node_num[i] = next;
+ }
+ } else {
+ new_node->node_num[ISC_RADIX_FAMILY(prefix)] = next;
+ }
+ memset(new_node->data, 0, sizeof(new_node->data));
+ }
+
+ 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;
+ for (i = 0; i < RADIX_FAMILIES; i++) {
+ glue->data[i] = NULL;
+ glue->node_num[i] = -1;
+ }
+ radix->num_active_node++;
+ if (differ_bit < radix->maxbits &&
+ BIT_TEST(addr[differ_bit>>3], 0x80 >> (differ_bit & 07))) {
+ 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 associated with it!
+ */
+ if (node->prefix != NULL)
+ _deref_prefix(node->prefix);
+
+ node->prefix = NULL;
+ memset(node->data, 0, sizeof(node->data));
+ return;
+ }
+
+ if (node->r == NULL && node->l == NULL) {
+ parent = node->parent;
+ _deref_prefix(node->prefix);
+
+ if (parent == NULL) {
+ INSIST(radix->head == node);
+ radix->head = NULL;
+ isc_mem_put(radix->mctx, node, sizeof(*node));
+ radix->num_active_node--;
+ return;
+ }
+
+ if (parent->r == node) {
+ parent->r = NULL;
+ child = parent->l;
+ } else {
+ INSIST(parent->l == node);
+ parent->l = NULL;
+ child = parent->r;
+ }
+
+ isc_mem_put(radix->mctx, node, sizeof(*node));
+ radix->num_active_node--;
+
+ 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(node->prefix);
+
+ if (parent == NULL) {
+ INSIST(radix->head == node);
+ radix->head = child;
+ isc_mem_put(radix->mctx, node, sizeof(*node));
+ radix->num_active_node--;
+ return;
+ }
+
+ isc_mem_put(radix->mctx, node, sizeof(*node));
+ radix->num_active_node--;
+
+ 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:
+*/