Adding upstream version 2.9.5.upstream/2.9.5

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

1 files changed, 218 insertions, 0 deletions

diff --git a/src/eb64tree.c b/src/eb64tree.c
new file mode 100644
index 0000000..b908d4d
--- /dev/null
+++ b/src/eb64tree.c
@@ -0,0 +1,218 @@
+/*
+ * Elastic Binary Trees - exported functions for operations on 64bit nodes.
+ * Version 6.0.6
+ * (C) 2002-2011 - Willy Tarreau <w@1wt.eu>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation, version 2.1
+ * exclusively.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+/* Consult eb64tree.h for more details about those functions */
+
+#include <import/eb64tree.h>
+
+struct eb64_node *eb64_insert(struct eb_root *root, struct eb64_node *new)
+{
+	return __eb64_insert(root, new);
+}
+
+struct eb64_node *eb64i_insert(struct eb_root *root, struct eb64_node *new)
+{
+	return __eb64i_insert(root, new);
+}
+
+struct eb64_node *eb64_lookup(struct eb_root *root, u64 x)
+{
+	return __eb64_lookup(root, x);
+}
+
+struct eb64_node *eb64i_lookup(struct eb_root *root, s64 x)
+{
+	return __eb64i_lookup(root, x);
+}
+
+/*
+ * Find the last occurrence of the highest key in the tree <root>, which is
+ * equal to or less than <x>. NULL is returned is no key matches.
+ */
+struct eb64_node *eb64_lookup_le(struct eb_root *root, u64 x)
+{
+	struct eb64_node *node;
+	eb_troot_t *troot;
+
+	troot = root->b[EB_LEFT];
+	if (unlikely(troot == NULL))
+		return NULL;
+
+	while (1) {
+		if ((eb_gettag(troot) == EB_LEAF)) {
+			/* We reached a leaf, which means that the whole upper
+			 * parts were common. We will return either the current
+			 * node or its next one if the former is too small.
+			 */
+			node = container_of(eb_untag(troot, EB_LEAF),
+					    struct eb64_node, node.branches);
+			if (node->key <= x)
+				return node;
+			/* return prev */
+			troot = node->node.leaf_p;
+			break;
+		}
+		node = container_of(eb_untag(troot, EB_NODE),
+				    struct eb64_node, node.branches);
+
+		if (node->node.bit < 0) {
+			/* We're at the top of a dup tree. Either we got a
+			 * matching value and we return the rightmost node, or
+			 * we don't and we skip the whole subtree to return the
+			 * prev node before the subtree. Note that since we're
+			 * at the top of the dup tree, we can simply return the
+			 * prev node without first trying to escape from the
+			 * tree.
+			 */
+			if (node->key <= x) {
+				troot = node->node.branches.b[EB_RGHT];
+				while (eb_gettag(troot) != EB_LEAF)
+					troot = (eb_untag(troot, EB_NODE))->b[EB_RGHT];
+				return container_of(eb_untag(troot, EB_LEAF),
+						    struct eb64_node, node.branches);
+			}
+			/* return prev */
+			troot = node->node.node_p;
+			break;
+		}
+
+		if (((x ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
+			/* No more common bits at all. Either this node is too
+			 * small and we need to get its highest value, or it is
+			 * too large, and we need to get the prev value.
+			 */
+			if ((node->key >> node->node.bit) < (x >> node->node.bit)) {
+				troot = node->node.branches.b[EB_RGHT];
+				return eb64_entry(eb_walk_down(troot, EB_RGHT), struct eb64_node, node);
+			}
+
+			/* Further values will be too high here, so return the prev
+			 * unique node (if it exists).
+			 */
+			troot = node->node.node_p;
+			break;
+		}
+		troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
+	}
+
+	/* If we get here, it means we want to report previous node before the
+	 * current one which is not above. <troot> is already initialised to
+	 * the parent's branches.
+	 */
+	while (eb_gettag(troot) == EB_LEFT) {
+		/* Walking up from left branch. We must ensure that we never
+		 * walk beyond root.
+		 */
+		if (unlikely(eb_clrtag((eb_untag(troot, EB_LEFT))->b[EB_RGHT]) == NULL))
+			return NULL;
+		troot = (eb_root_to_node(eb_untag(troot, EB_LEFT)))->node_p;
+	}
+	/* Note that <troot> cannot be NULL at this stage */
+	troot = (eb_untag(troot, EB_RGHT))->b[EB_LEFT];
+	node = eb64_entry(eb_walk_down(troot, EB_RGHT), struct eb64_node, node);
+	return node;
+}
+
+/*
+ * Find the first occurrence of the lowest key in the tree <root>, which is
+ * equal to or greater than <x>. NULL is returned is no key matches.
+ */
+struct eb64_node *eb64_lookup_ge(struct eb_root *root, u64 x)
+{
+	struct eb64_node *node;
+	eb_troot_t *troot;
+
+	troot = root->b[EB_LEFT];
+	if (unlikely(troot == NULL))
+		return NULL;
+
+	while (1) {
+		if ((eb_gettag(troot) == EB_LEAF)) {
+			/* We reached a leaf, which means that the whole upper
+			 * parts were common. We will return either the current
+			 * node or its next one if the former is too small.
+			 */
+			node = container_of(eb_untag(troot, EB_LEAF),
+					    struct eb64_node, node.branches);
+			if (node->key >= x)
+				return node;
+			/* return next */
+			troot = node->node.leaf_p;
+			break;
+		}
+		node = container_of(eb_untag(troot, EB_NODE),
+				    struct eb64_node, node.branches);
+
+		if (node->node.bit < 0) {
+			/* We're at the top of a dup tree. Either we got a
+			 * matching value and we return the leftmost node, or
+			 * we don't and we skip the whole subtree to return the
+			 * next node after the subtree. Note that since we're
+			 * at the top of the dup tree, we can simply return the
+			 * next node without first trying to escape from the
+			 * tree.
+			 */
+			if (node->key >= x) {
+				troot = node->node.branches.b[EB_LEFT];
+				while (eb_gettag(troot) != EB_LEAF)
+					troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
+				return container_of(eb_untag(troot, EB_LEAF),
+						    struct eb64_node, node.branches);
+			}
+			/* return next */
+			troot = node->node.node_p;
+			break;
+		}
+
+		if (((x ^ node->key) >> node->node.bit) >= EB_NODE_BRANCHES) {
+			/* No more common bits at all. Either this node is too
+			 * large and we need to get its lowest value, or it is too
+			 * small, and we need to get the next value.
+			 */
+			if ((node->key >> node->node.bit) > (x >> node->node.bit)) {
+				troot = node->node.branches.b[EB_LEFT];
+				return eb64_entry(eb_walk_down(troot, EB_LEFT), struct eb64_node, node);
+			}
+
+			/* Further values will be too low here, so return the next
+			 * unique node (if it exists).
+			 */
+			troot = node->node.node_p;
+			break;
+		}
+		troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
+	}
+
+	/* If we get here, it means we want to report next node after the
+	 * current one which is not below. <troot> is already initialised
+	 * to the parent's branches.
+	 */
+	while (eb_gettag(troot) != EB_LEFT)
+		/* Walking up from right branch, so we cannot be below root */
+		troot = (eb_root_to_node(eb_untag(troot, EB_RGHT)))->node_p;
+
+	/* Note that <troot> cannot be NULL at this stage */
+	troot = (eb_untag(troot, EB_LEFT))->b[EB_RGHT];
+	if (eb_clrtag(troot) == NULL)
+		return NULL;
+
+	node = eb64_entry(eb_walk_down(troot, EB_LEFT), struct eb64_node, node);
+	return node;
+}