[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/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];
}
}