Adding upstream version 1:9.16.44.upstream/1%9.16.44upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 706 insertions, 0 deletions

diff --git a/lib/isc/radix.c b/lib/isc/radix.c
new file mode 100644
index 0000000..d84e5d0
--- /dev/null
+++ b/lib/isc/radix.c
@@ -0,0 +1,706 @@
+/*
+ * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
+ *
+ * SPDX-License-Identifier: MPL-2.0
+ *
+ * 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 https://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 <inttypes.h>
+
+#include <isc/mem.h>
+#include <isc/radix.h>
+#include <isc/types.h>
+#include <isc/util.h>
+
+#define BIT_TEST(f, b) (((f) & (b)) != 0)
+
+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 (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->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) {
+	if (prefix != NULL) {
+		if (isc_refcount_decrement(&prefix->refcount) == 1) {
+			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);
+
+	*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));
+
+	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);
+			}
+
+			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;
+
+	node = radix->head;
+
+	if (node == NULL) {
+		return (ISC_R_NOTFOUND);
+	}
+
+	addr = isc_prefix_touchar(prefix);
+	bitlen = prefix->bitlen;
+
+	while (node != NULL && 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 && 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));
+		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);
+			}
+		}
+		INSIST(node->data[RADIX_V4] == NULL &&
+		       node->node_num[RADIX_V4] == -1 &&
+		       node->data[RADIX_V4] == NULL &&
+		       node->node_num[RADIX_V4] == -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 (node->bit != differ_bit && bitlen != differ_bit) {
+		glue = isc_mem_get(radix->mctx, sizeof(isc_radix_node_t));
+	}
+	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;
+	}
+}