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