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