[MINOR] update ebtree to version 4.1
Ebtree version 4.1 brings lookup by ranges. This will be useful for
the scheduler.
diff --git a/include/common/eb32tree.h b/include/common/eb32tree.h
index b5c88ee..f794131 100644
--- a/include/common/eb32tree.h
+++ b/include/common/eb32tree.h
@@ -100,6 +100,7 @@
*/
REGPRM2 struct eb32_node *eb32_lookup(struct eb_root *root, u32 x);
REGPRM2 struct eb32_node *eb32i_lookup(struct eb_root *root, s32 x);
+REGPRM2 struct eb32_node *eb32_lookup_ge(struct eb_root *root, u32 x);
REGPRM2 struct eb32_node *eb32_insert(struct eb_root *root, struct eb32_node *new);
REGPRM2 struct eb32_node *eb32i_insert(struct eb_root *root, struct eb32_node *new);
@@ -122,6 +123,7 @@
{
struct eb32_node *node;
eb_troot_t *troot;
+ u32 y;
troot = root->b[EB_LEFT];
if (unlikely(troot == NULL))
@@ -139,7 +141,8 @@
node = container_of(eb_untag(troot, EB_NODE),
struct eb32_node, node.branches);
- if (x == node->key) {
+ y = node->key ^ x;
+ if (!y) {
/* Either we found the node which holds the key, or
* we have a dup tree. In the later case, we have to
* walk it down left to get the first entry.
@@ -154,6 +157,9 @@
return node;
}
+ if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
+ return NULL; /* no more common bits */
+
troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
}
}
@@ -167,6 +173,7 @@
struct eb32_node *node;
eb_troot_t *troot;
u32 key = x ^ 0x80000000;
+ u32 y;
troot = root->b[EB_LEFT];
if (unlikely(troot == NULL))
@@ -184,7 +191,8 @@
node = container_of(eb_untag(troot, EB_NODE),
struct eb32_node, node.branches);
- if (x == node->key) {
+ y = node->key ^ x;
+ if (!y) {
/* Either we found the node which holds the key, or
* we have a dup tree. In the later case, we have to
* walk it down left to get the first entry.
@@ -199,6 +207,9 @@
return node;
}
+ if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
+ return NULL; /* no more common bits */
+
troot = node->node.branches.b[(key >> node->node.bit) & EB_NODE_BRANCH_MASK];
}
}
diff --git a/include/common/eb64tree.h b/include/common/eb64tree.h
index 3874ac8..04f57ec 100644
--- a/include/common/eb64tree.h
+++ b/include/common/eb64tree.h
@@ -122,6 +122,7 @@
{
struct eb64_node *node;
eb_troot_t *troot;
+ u64 y;
troot = root->b[EB_LEFT];
if (unlikely(troot == NULL))
@@ -139,7 +140,8 @@
node = container_of(eb_untag(troot, EB_NODE),
struct eb64_node, node.branches);
- if (x == node->key) {
+ y = node->key ^ x;
+ if (!y) {
/* Either we found the node which holds the key, or
* we have a dup tree. In the later case, we have to
* walk it down left to get the first entry.
@@ -154,6 +156,9 @@
return node;
}
+ if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
+ return NULL; /* no more common bits */
+
troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
}
}
@@ -167,6 +172,7 @@
struct eb64_node *node;
eb_troot_t *troot;
u64 key = x ^ (1ULL << 63);
+ u64 y;
troot = root->b[EB_LEFT];
if (unlikely(troot == NULL))
@@ -184,7 +190,8 @@
node = container_of(eb_untag(troot, EB_NODE),
struct eb64_node, node.branches);
- if (x == node->key) {
+ y = node->key ^ x;
+ if (!y) {
/* Either we found the node which holds the key, or
* we have a dup tree. In the later case, we have to
* walk it down left to get the first entry.
@@ -199,6 +206,9 @@
return node;
}
+ if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
+ return NULL; /* no more common bits */
+
troot = node->node.branches.b[(key >> node->node.bit) & EB_NODE_BRANCH_MASK];
}
}
diff --git a/include/common/ebpttree.h b/include/common/ebpttree.h
index d863f3c..d1dbcfd 100644
--- a/include/common/ebpttree.h
+++ b/include/common/ebpttree.h
@@ -123,6 +123,7 @@
{
struct ebpt_node *node;
eb_troot_t *troot;
+ ptr_t y;
troot = root->b[EB_LEFT];
if (unlikely(troot == NULL))
@@ -140,7 +141,8 @@
node = container_of(eb_untag(troot, EB_NODE),
struct ebpt_node, node.branches);
- if (x == node->key) {
+ y = (ptr_t)node->key ^ (ptr_t)x;
+ if (!y) {
/* Either we found the node which holds the key, or
* we have a dup tree. In the later case, we have to
* walk it down left to get the first entry.
@@ -155,6 +157,9 @@
return node;
}
+ if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
+ return NULL; /* no more common bits */
+
troot = node->node.branches.b[((ptr_t)x >> node->node.bit) & EB_NODE_BRANCH_MASK];
}
}