diff --git a/ebtree/eb32tree.c b/ebtree/eb32tree.c
index 84a47e8..f504105 100644
--- a/ebtree/eb32tree.c
+++ b/ebtree/eb32tree.c
@@ -1,6 +1,7 @@
 /*
  * Elastic Binary Trees - exported functions for operations on 32bit nodes.
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -97,7 +98,7 @@
 			 * 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)) {
+			if ((node->key >> node->node.bit) < (x >> node->node.bit)) {
 				troot = node->node.branches.b[EB_RGHT];
 				return eb32_entry(eb_walk_down(troot, EB_RGHT), struct eb32_node, node);
 			}
diff --git a/ebtree/eb32tree.h b/ebtree/eb32tree.h
index 037c458..906ab49 100644
--- a/ebtree/eb32tree.h
+++ b/ebtree/eb32tree.h
@@ -1,7 +1,7 @@
 /*
  * Elastic Binary Trees - macros and structures for operations on 32bit nodes.
- * Version 5.0
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -125,6 +125,7 @@
 	struct eb32_node *node;
 	eb_troot_t *troot;
 	u32 y;
+	int node_bit;
 
 	troot = root->b[EB_LEFT];
 	if (unlikely(troot == NULL))
@@ -141,6 +142,7 @@
 		}
 		node = container_of(eb_untag(troot, EB_NODE),
 				    struct eb32_node, node.branches);
+		node_bit = node->node.bit;
 
 		y = node->key ^ x;
 		if (!y) {
@@ -148,7 +150,7 @@
 			 * we have a dup tree. In the later case, we have to
 			 * walk it down left to get the first entry.
 			 */
-			if (node->node.bit < 0) {
+			if (node_bit < 0) {
 				troot = node->node.branches.b[EB_LEFT];
 				while (eb_gettag(troot) != EB_LEAF)
 					troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
@@ -158,10 +160,10 @@
 			return node;
 		}
 
-		if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
+		if ((y >> node_bit) >= EB_NODE_BRANCHES)
 			return NULL; /* no more common bits */
 
-		troot = node->node.branches.b[(x >> node->node.bit) & EB_NODE_BRANCH_MASK];
+		troot = node->node.branches.b[(x >> node_bit) & EB_NODE_BRANCH_MASK];
 	}
 }
 
@@ -175,6 +177,7 @@
 	eb_troot_t *troot;
 	u32 key = x ^ 0x80000000;
 	u32 y;
+	int node_bit;
 
 	troot = root->b[EB_LEFT];
 	if (unlikely(troot == NULL))
@@ -184,13 +187,14 @@
 		if ((eb_gettag(troot) == EB_LEAF)) {
 			node = container_of(eb_untag(troot, EB_LEAF),
 					    struct eb32_node, node.branches);
-			if (node->key == x)
+			if (node->key == (u32)x)
 				return node;
 			else
 				return NULL;
 		}
 		node = container_of(eb_untag(troot, EB_NODE),
 				    struct eb32_node, node.branches);
+		node_bit = node->node.bit;
 
 		y = node->key ^ x;
 		if (!y) {
@@ -198,7 +202,7 @@
 			 * we have a dup tree. In the later case, we have to
 			 * walk it down left to get the first entry.
 			 */
-			if (node->node.bit < 0) {
+			if (node_bit < 0) {
 				troot = node->node.branches.b[EB_LEFT];
 				while (eb_gettag(troot) != EB_LEAF)
 					troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
@@ -208,10 +212,10 @@
 			return node;
 		}
 
-		if ((y >> node->node.bit) >= EB_NODE_BRANCHES)
+		if ((y >> node_bit) >= EB_NODE_BRANCHES)
 			return NULL; /* no more common bits */
 
-		troot = node->node.branches.b[(key >> node->node.bit) & EB_NODE_BRANCH_MASK];
+		troot = node->node.branches.b[(key >> node_bit) & EB_NODE_BRANCH_MASK];
 	}
 }
 
@@ -223,9 +227,12 @@
 __eb32_insert(struct eb_root *root, struct eb32_node *new) {
 	struct eb32_node *old;
 	unsigned int side;
-	eb_troot_t *troot;
+	eb_troot_t *troot, **up_ptr;
 	u32 newkey; /* caching the key saves approximately one cycle */
 	eb_troot_t *root_right = root;
+	eb_troot_t *new_left, *new_rght;
+	eb_troot_t *new_leaf;
+	int old_node_bit;
 
 	side = EB_LEFT;
 	troot = root->b[EB_LEFT];
@@ -252,119 +259,45 @@
 	newkey = new->key;
 
 	while (1) {
-		if (unlikely(eb_gettag(troot) == EB_LEAF)) {
-			eb_troot_t *new_left, *new_rght;
-			eb_troot_t *new_leaf, *old_leaf;
-
+		if (eb_gettag(troot) == EB_LEAF) {
+			/* insert above a leaf */
 			old = container_of(eb_untag(troot, EB_LEAF),
 					    struct eb32_node, node.branches);
-
-			new_left = eb_dotag(&new->node.branches, EB_LEFT);
-			new_rght = eb_dotag(&new->node.branches, EB_RGHT);
-			new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
-			old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
-
 			new->node.node_p = old->node.leaf_p;
-
-			/* Right here, we have 3 possibilities :
-			   - the tree does not contain the key, and we have
-			     new->key < old->key. We insert new above old, on
-			     the left ;
-
-			   - the tree does not contain the key, and we have
-			     new->key > old->key. We insert new above old, on
-			     the right ;
-
-			   - the tree does contain the key, which implies it
-			     is alone. We add the new key next to it as a
-			     first duplicate.
-
-			   The last two cases can easily be partially merged.
-			*/
-			 
-			if (new->key < old->key) {
-				new->node.leaf_p = new_left;
-				old->node.leaf_p = new_rght;
-				new->node.branches.b[EB_LEFT] = new_leaf;
-				new->node.branches.b[EB_RGHT] = old_leaf;
-			} else {
-				/* we may refuse to duplicate this key if the tree is
-				 * tagged as containing only unique keys.
-				 */
-				if ((new->key == old->key) && eb_gettag(root_right))
-					return old;
-
-				/* new->key >= old->key, new goes the right */
-				old->node.leaf_p = new_left;
-				new->node.leaf_p = new_rght;
-				new->node.branches.b[EB_LEFT] = old_leaf;
-				new->node.branches.b[EB_RGHT] = new_leaf;
-
-				if (new->key == old->key) {
-					new->node.bit = -1;
-					root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
-					return new;
-				}
-			}
+			up_ptr = &old->node.leaf_p;
 			break;
 		}
 
 		/* OK we're walking down this link */
 		old = container_of(eb_untag(troot, EB_NODE),
 				    struct eb32_node, node.branches);
+		old_node_bit = old->node.bit;
 
 		/* Stop going down when we don't have common bits anymore. We
 		 * also stop in front of a duplicates tree because it means we
 		 * have to insert above.
 		 */
 
-		if ((old->node.bit < 0) || /* we're above a duplicate tree, stop here */
-		    (((new->key ^ old->key) >> old->node.bit) >= EB_NODE_BRANCHES)) {
+		if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
+		    (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
 			/* The tree did not contain the key, so we insert <new> before the node
 			 * <old>, and set ->bit to designate the lowest bit position in <new>
 			 * which applies to ->branches.b[].
 			 */
-			eb_troot_t *new_left, *new_rght;
-			eb_troot_t *new_leaf, *old_node;
-
-			new_left = eb_dotag(&new->node.branches, EB_LEFT);
-			new_rght = eb_dotag(&new->node.branches, EB_RGHT);
-			new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
-			old_node = eb_dotag(&old->node.branches, EB_NODE);
-
 			new->node.node_p = old->node.node_p;
-
-			if (new->key < old->key) {
-				new->node.leaf_p = new_left;
-				old->node.node_p = new_rght;
-				new->node.branches.b[EB_LEFT] = new_leaf;
-				new->node.branches.b[EB_RGHT] = old_node;
-			}
-			else if (new->key > old->key) {
-				old->node.node_p = new_left;
-				new->node.leaf_p = new_rght;
-				new->node.branches.b[EB_LEFT] = old_node;
-				new->node.branches.b[EB_RGHT] = new_leaf;
-			}
-			else {
-				struct eb_node *ret;
-				ret = eb_insert_dup(&old->node, &new->node);
-				return container_of(ret, struct eb32_node, node);
-			}
+			up_ptr = &old->node.node_p;
 			break;
 		}
 
 		/* walk down */
 		root = &old->node.branches;
-		side = (newkey >> old->node.bit) & EB_NODE_BRANCH_MASK;
+		side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
 		troot = root->b[side];
 	}
 
-	/* Ok, now we are inserting <new> between <root> and <old>. <old>'s
-	 * parent is already set to <new>, and the <root>'s branch is still in
-	 * <side>. Update the root's leaf till we have it. Note that we can also
-	 * find the side by checking the side of new->node.node_p.
-	 */
+	new_left = eb_dotag(&new->node.branches, EB_LEFT);
+	new_rght = eb_dotag(&new->node.branches, EB_RGHT);
+	new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
 
 	/* We need the common higher bits between new->key and old->key.
 	 * What differences are there between new->key and the node here ?
@@ -372,10 +305,49 @@
 	 * bit of new->key and old->key are identical here (otherwise they
 	 * would sit on different branches).
 	 */
+
 	// note that if EB_NODE_BITS > 1, we should check that it's still >= 0
 	new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
-	root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
+
+	if (new->key == old->key) {
+		new->node.bit = -1; /* mark as new dup tree, just in case */
+
+		if (likely(eb_gettag(root_right))) {
+			/* we refuse to duplicate this key if the tree is
+			 * tagged as containing only unique keys.
+			 */
+			return old;
+		}
+
+		if (eb_gettag(troot) != EB_LEAF) {
+			/* there was already a dup tree below */
+			struct eb_node *ret;
+			ret = eb_insert_dup(&old->node, &new->node);
+			return container_of(ret, struct eb32_node, node);
+		}
+		/* otherwise fall through */
+	}
 
+	if (new->key >= old->key) {
+		new->node.branches.b[EB_LEFT] = troot;
+		new->node.branches.b[EB_RGHT] = new_leaf;
+		new->node.leaf_p = new_rght;
+		*up_ptr = new_left;
+	}
+	else {
+		new->node.branches.b[EB_LEFT] = new_leaf;
+		new->node.branches.b[EB_RGHT] = troot;
+		new->node.leaf_p = new_left;
+		*up_ptr = new_rght;
+	}
+
+	/* Ok, now we are inserting <new> between <root> and <old>. <old>'s
+	 * parent is already set to <new>, and the <root>'s branch is still in
+	 * <side>. Update the root's leaf till we have it. Note that we can also
+	 * find the side by checking the side of new->node.node_p.
+	 */
+
+	root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
 	return new;
 }
 
@@ -387,9 +359,12 @@
 __eb32i_insert(struct eb_root *root, struct eb32_node *new) {
 	struct eb32_node *old;
 	unsigned int side;
-	eb_troot_t *troot;
+	eb_troot_t *troot, **up_ptr;
 	int newkey; /* caching the key saves approximately one cycle */
 	eb_troot_t *root_right = root;
+	eb_troot_t *new_left, *new_rght;
+	eb_troot_t *new_leaf;
+	int old_node_bit;
 
 	side = EB_LEFT;
 	troot = root->b[EB_LEFT];
@@ -418,119 +393,44 @@
 	newkey = new->key + 0x80000000;
 
 	while (1) {
-		if (unlikely(eb_gettag(troot) == EB_LEAF)) {
-			eb_troot_t *new_left, *new_rght;
-			eb_troot_t *new_leaf, *old_leaf;
-
+		if (eb_gettag(troot) == EB_LEAF) {
 			old = container_of(eb_untag(troot, EB_LEAF),
 					    struct eb32_node, node.branches);
-
-			new_left = eb_dotag(&new->node.branches, EB_LEFT);
-			new_rght = eb_dotag(&new->node.branches, EB_RGHT);
-			new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
-			old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
-
 			new->node.node_p = old->node.leaf_p;
-
-			/* Right here, we have 3 possibilities :
-			   - the tree does not contain the key, and we have
-			     new->key < old->key. We insert new above old, on
-			     the left ;
-
-			   - the tree does not contain the key, and we have
-			     new->key > old->key. We insert new above old, on
-			     the right ;
-
-			   - the tree does contain the key, which implies it
-			     is alone. We add the new key next to it as a
-			     first duplicate.
-
-			   The last two cases can easily be partially merged.
-			*/
-			 
-			if ((s32)new->key < (s32)old->key) {
-				new->node.leaf_p = new_left;
-				old->node.leaf_p = new_rght;
-				new->node.branches.b[EB_LEFT] = new_leaf;
-				new->node.branches.b[EB_RGHT] = old_leaf;
-			} else {
-				/* we may refuse to duplicate this key if the tree is
-				 * tagged as containing only unique keys.
-				 */
-				if ((new->key == old->key) && eb_gettag(root_right))
-					return old;
-
-				/* new->key >= old->key, new goes the right */
-				old->node.leaf_p = new_left;
-				new->node.leaf_p = new_rght;
-				new->node.branches.b[EB_LEFT] = old_leaf;
-				new->node.branches.b[EB_RGHT] = new_leaf;
-
-				if (new->key == old->key) {
-					new->node.bit = -1;
-					root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
-					return new;
-				}
-			}
+			up_ptr = &old->node.leaf_p;
 			break;
 		}
 
 		/* OK we're walking down this link */
 		old = container_of(eb_untag(troot, EB_NODE),
 				    struct eb32_node, node.branches);
+		old_node_bit = old->node.bit;
 
 		/* Stop going down when we don't have common bits anymore. We
 		 * also stop in front of a duplicates tree because it means we
 		 * have to insert above.
 		 */
 
-		if ((old->node.bit < 0) || /* we're above a duplicate tree, stop here */
-		    (((new->key ^ old->key) >> old->node.bit) >= EB_NODE_BRANCHES)) {
+		if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
+		    (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
 			/* The tree did not contain the key, so we insert <new> before the node
 			 * <old>, and set ->bit to designate the lowest bit position in <new>
 			 * which applies to ->branches.b[].
 			 */
-			eb_troot_t *new_left, *new_rght;
-			eb_troot_t *new_leaf, *old_node;
-
-			new_left = eb_dotag(&new->node.branches, EB_LEFT);
-			new_rght = eb_dotag(&new->node.branches, EB_RGHT);
-			new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
-			old_node = eb_dotag(&old->node.branches, EB_NODE);
-
 			new->node.node_p = old->node.node_p;
-
-			if ((s32)new->key < (s32)old->key) {
-				new->node.leaf_p = new_left;
-				old->node.node_p = new_rght;
-				new->node.branches.b[EB_LEFT] = new_leaf;
-				new->node.branches.b[EB_RGHT] = old_node;
-			}
-			else if ((s32)new->key > (s32)old->key) {
-				old->node.node_p = new_left;
-				new->node.leaf_p = new_rght;
-				new->node.branches.b[EB_LEFT] = old_node;
-				new->node.branches.b[EB_RGHT] = new_leaf;
-			}
-			else {
-				struct eb_node *ret;
-				ret = eb_insert_dup(&old->node, &new->node);
-				return container_of(ret, struct eb32_node, node);
-			}
+			up_ptr = &old->node.node_p;
 			break;
 		}
 
 		/* walk down */
 		root = &old->node.branches;
-		side = (newkey >> old->node.bit) & EB_NODE_BRANCH_MASK;
+		side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
 		troot = root->b[side];
 	}
 
-	/* Ok, now we are inserting <new> between <root> and <old>. <old>'s
-	 * parent is already set to <new>, and the <root>'s branch is still in
-	 * <side>. Update the root's leaf till we have it. Note that we can also
-	 * find the side by checking the side of new->node.node_p.
-	 */
+	new_left = eb_dotag(&new->node.branches, EB_LEFT);
+	new_rght = eb_dotag(&new->node.branches, EB_RGHT);
+	new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
 
 	/* We need the common higher bits between new->key and old->key.
 	 * What differences are there between new->key and the node here ?
@@ -538,10 +438,49 @@
 	 * bit of new->key and old->key are identical here (otherwise they
 	 * would sit on different branches).
 	 */
+
 	// note that if EB_NODE_BITS > 1, we should check that it's still >= 0
 	new->node.bit = flsnz(new->key ^ old->key) - EB_NODE_BITS;
-	root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
+
+	if (new->key == old->key) {
+		new->node.bit = -1; /* mark as new dup tree, just in case */
+
+		if (likely(eb_gettag(root_right))) {
+			/* we refuse to duplicate this key if the tree is
+			 * tagged as containing only unique keys.
+			 */
+			return old;
+		}
+
+		if (eb_gettag(troot) != EB_LEAF) {
+			/* there was already a dup tree below */
+			struct eb_node *ret;
+			ret = eb_insert_dup(&old->node, &new->node);
+			return container_of(ret, struct eb32_node, node);
+		}
+		/* otherwise fall through */
+	}
 
+	if ((s32)new->key >= (s32)old->key) {
+		new->node.branches.b[EB_LEFT] = troot;
+		new->node.branches.b[EB_RGHT] = new_leaf;
+		new->node.leaf_p = new_rght;
+		*up_ptr = new_left;
+	}
+	else {
+		new->node.branches.b[EB_LEFT] = new_leaf;
+		new->node.branches.b[EB_RGHT] = troot;
+		new->node.leaf_p = new_left;
+		*up_ptr = new_rght;
+	}
+
+	/* Ok, now we are inserting <new> between <root> and <old>. <old>'s
+	 * parent is already set to <new>, and the <root>'s branch is still in
+	 * <side>. Update the root's leaf till we have it. Note that we can also
+	 * find the side by checking the side of new->node.node_p.
+	 */
+
+	root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
 	return new;
 }
 
diff --git a/ebtree/eb64tree.c b/ebtree/eb64tree.c
index 1abb4c8..3d18fb2 100644
--- a/ebtree/eb64tree.c
+++ b/ebtree/eb64tree.c
@@ -1,6 +1,7 @@
 /*
  * Elastic Binary Trees - exported functions for operations on 64bit nodes.
- * (C) 2002-2007 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -97,7 +98,7 @@
 			 * 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)) {
+			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);
 			}
diff --git a/ebtree/eb64tree.h b/ebtree/eb64tree.h
index 6ffa586..d756e7a 100644
--- a/ebtree/eb64tree.h
+++ b/ebtree/eb64tree.h
@@ -1,7 +1,7 @@
 /*
  * Elastic Binary Trees - macros and structures for operations on 64bit nodes.
- * Version 5.0
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -125,6 +125,7 @@
 	struct eb64_node *node;
 	eb_troot_t *troot;
 	u64 y;
+	int node_bit;
 
 	troot = root->b[EB_LEFT];
 	if (unlikely(troot == NULL))
@@ -141,6 +142,7 @@
 		}
 		node = container_of(eb_untag(troot, EB_NODE),
 				    struct eb64_node, node.branches);
+		node_bit = node->node.bit;
 
 		y = node->key ^ x;
 		if (!y) {
@@ -175,6 +177,7 @@
 	eb_troot_t *troot;
 	u64 key = x ^ (1ULL << 63);
 	u64 y;
+	int node_bit;
 
 	troot = root->b[EB_LEFT];
 	if (unlikely(troot == NULL))
@@ -184,13 +187,14 @@
 		if ((eb_gettag(troot) == EB_LEAF)) {
 			node = container_of(eb_untag(troot, EB_LEAF),
 					    struct eb64_node, node.branches);
-			if (node->key == x)
+			if (node->key == (u64)x)
 				return node;
 			else
 				return NULL;
 		}
 		node = container_of(eb_untag(troot, EB_NODE),
 				    struct eb64_node, node.branches);
+		node_bit = node->node.bit;
 
 		y = node->key ^ x;
 		if (!y) {
@@ -226,6 +230,7 @@
 	eb_troot_t *troot;
 	u64 newkey; /* caching the key saves approximately one cycle */
 	eb_troot_t *root_right = root;
+	int old_node_bit;
 
 	side = EB_LEFT;
 	troot = root->b[EB_LEFT];
@@ -312,14 +317,15 @@
 		/* OK we're walking down this link */
 		old = container_of(eb_untag(troot, EB_NODE),
 				    struct eb64_node, node.branches);
+		old_node_bit = old->node.bit;
 
 		/* Stop going down when we don't have common bits anymore. We
 		 * also stop in front of a duplicates tree because it means we
 		 * have to insert above.
 		 */
 
-		if ((old->node.bit < 0) || /* we're above a duplicate tree, stop here */
-		    (((new->key ^ old->key) >> old->node.bit) >= EB_NODE_BRANCHES)) {
+		if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
+		    (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
 			/* The tree did not contain the key, so we insert <new> before the node
 			 * <old>, and set ->bit to designate the lowest bit position in <new>
 			 * which applies to ->branches.b[].
@@ -357,13 +363,13 @@
 		/* walk down */
 		root = &old->node.branches;
 #if BITS_PER_LONG >= 64
-		side = (newkey >> old->node.bit) & EB_NODE_BRANCH_MASK;
+		side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
 #else
 		side = newkey;
-		side >>= old->node.bit;
-		if (old->node.bit >= 32) {
+		side >>= old_node_bit;
+		if (old_node_bit >= 32) {
 			side = newkey >> 32;
-			side >>= old->node.bit & 0x1F;
+			side >>= old_node_bit & 0x1F;
 		}
 		side &= EB_NODE_BRANCH_MASK;
 #endif
@@ -400,6 +406,7 @@
 	eb_troot_t *troot;
 	u64 newkey; /* caching the key saves approximately one cycle */
 	eb_troot_t *root_right = root;
+	int old_node_bit;
 
 	side = EB_LEFT;
 	troot = root->b[EB_LEFT];
@@ -488,14 +495,15 @@
 		/* OK we're walking down this link */
 		old = container_of(eb_untag(troot, EB_NODE),
 				    struct eb64_node, node.branches);
+		old_node_bit = old->node.bit;
 
 		/* Stop going down when we don't have common bits anymore. We
 		 * also stop in front of a duplicates tree because it means we
 		 * have to insert above.
 		 */
 
-		if ((old->node.bit < 0) || /* we're above a duplicate tree, stop here */
-		    (((new->key ^ old->key) >> old->node.bit) >= EB_NODE_BRANCHES)) {
+		if ((old_node_bit < 0) || /* we're above a duplicate tree, stop here */
+		    (((new->key ^ old->key) >> old_node_bit) >= EB_NODE_BRANCHES)) {
 			/* The tree did not contain the key, so we insert <new> before the node
 			 * <old>, and set ->bit to designate the lowest bit position in <new>
 			 * which applies to ->branches.b[].
@@ -533,13 +541,13 @@
 		/* walk down */
 		root = &old->node.branches;
 #if BITS_PER_LONG >= 64
-		side = (newkey >> old->node.bit) & EB_NODE_BRANCH_MASK;
+		side = (newkey >> old_node_bit) & EB_NODE_BRANCH_MASK;
 #else
 		side = newkey;
-		side >>= old->node.bit;
-		if (old->node.bit >= 32) {
+		side >>= old_node_bit;
+		if (old_node_bit >= 32) {
 			side = newkey >> 32;
-			side >>= old->node.bit & 0x1F;
+			side >>= old_node_bit & 0x1F;
 		}
 		side &= EB_NODE_BRANCH_MASK;
 #endif
diff --git a/ebtree/ebimtree.c b/ebtree/ebimtree.c
index 5e63937..eb58b2e 100644
--- a/ebtree/ebimtree.c
+++ b/ebtree/ebimtree.c
@@ -1,7 +1,7 @@
 /*
- * Elastic Binary Trees - exported functinos for Indirect Multi-Byte data nodes.
- * Version 5.0
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Elastic Binary Trees - exported functions for Indirect Multi-Byte data nodes.
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
diff --git a/ebtree/ebimtree.h b/ebtree/ebimtree.h
index f53a26a..4d2eea0 100644
--- a/ebtree/ebimtree.h
+++ b/ebtree/ebimtree.h
@@ -1,7 +1,7 @@
 /*
  * Elastic Binary Trees - macros for Indirect Multi-Byte data nodes.
- * Version 5.0
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -40,7 +40,8 @@
 {
 	struct ebpt_node *node;
 	eb_troot_t *troot;
-	unsigned int bit;
+	int bit;
+	int node_bit;
 
 	troot = root->b[EB_LEFT];
 	if (unlikely(troot == NULL))
@@ -59,7 +60,8 @@
 		node = container_of(eb_untag(troot, EB_NODE),
 				    struct ebpt_node, node.branches);
 
-		if (node->node.bit < 0) {
+		node_bit = node->node.bit;
+		if (node_bit < 0) {
 			/* We have a dup tree now. Either it's for the same
 			 * value, and we walk down left, or it's a different
 			 * one and we don't have our key.
@@ -76,12 +78,12 @@
 		}
 
 		/* OK, normal data node, let's walk down */
-		bit = equal_bits(x, node->key, bit, node->node.bit);
-		if (bit < node->node.bit)
+		bit = equal_bits(x, node->key, bit, node_bit);
+		if (bit < node_bit)
 			return NULL; /* no more common bits */
 
-		troot = node->node.branches.b[(((unsigned char*)x)[node->node.bit >> 3] >>
-					       (~node->node.bit & 7)) & 1];
+		troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>
+					       (~node_bit & 7)) & 1];
 	}
 }
 
@@ -99,6 +101,7 @@
 	eb_troot_t *root_right = root;
 	int diff;
 	int bit;
+	int old_node_bit;
 
 	side = EB_LEFT;
 	troot = root->b[EB_LEFT];
@@ -189,6 +192,7 @@
 		/* OK we're walking down this link */
 		old = container_of(eb_untag(troot, EB_NODE),
 				   struct ebpt_node, node.branches);
+		old_node_bit = old->node.bit;
 
 		/* Stop going down when we don't have common bits anymore. We
 		 * also stop in front of a duplicates tree because it means we
@@ -196,16 +200,16 @@
 		 * the current node's because as long as they are identical, we
 		 * know we descend along the correct side.
 		 */
-		if (old->node.bit < 0) {
+		if (old_node_bit < 0) {
 			/* we're above a duplicate tree, we must compare till the end */
 			bit = equal_bits(new->key, old->key, bit, len);
 			goto dup_tree;
 		}
-		else if (bit < old->node.bit) {
-			bit = equal_bits(new->key, old->key, bit, old->node.bit);
+		else if (bit < old_node_bit) {
+			bit = equal_bits(new->key, old->key, bit, old_node_bit);
 		}
 
-		if (bit < old->node.bit) { /* we don't have all bits in common */
+		if (bit < old_node_bit) { /* we don't have all bits in common */
 			/* The tree did not contain the key, so we insert <new> before the node
 			 * <old>, and set ->bit to designate the lowest bit position in <new>
 			 * which applies to ->branches.b[].
@@ -244,7 +248,7 @@
 
 		/* walk down */
 		root = &old->node.branches;
-		side = (((unsigned char *)new->key)[old->node.bit >> 3] >> (~old->node.bit & 7)) & 1;
+		side = (((unsigned char *)new->key)[old_node_bit >> 3] >> (~old_node_bit & 7)) & 1;
 		troot = root->b[side];
 	}
 
diff --git a/ebtree/ebistree.c b/ebtree/ebistree.c
index 938caf7..1b8c912 100644
--- a/ebtree/ebistree.c
+++ b/ebtree/ebistree.c
@@ -1,7 +1,7 @@
 /*
  * Elastic Binary Trees - exported functions for Indirect String data nodes.
- * Version 5.1
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
diff --git a/ebtree/ebistree.h b/ebtree/ebistree.h
index 62f42c6..b77c748 100644
--- a/ebtree/ebistree.h
+++ b/ebtree/ebistree.h
@@ -1,7 +1,7 @@
 /*
  * Elastic Binary Trees - macros to manipulate Indirect String data nodes.
- * Version 5.1
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -43,7 +43,8 @@
 {
 	struct ebpt_node *node;
 	eb_troot_t *troot;
-	unsigned int bit;
+	int bit;
+	int node_bit;
 
 	troot = root->b[EB_LEFT];
 	if (unlikely(troot == NULL))
@@ -61,8 +62,9 @@
 		}
 		node = container_of(eb_untag(troot, EB_NODE),
 				    struct ebpt_node, node.branches);
+		node_bit = node->node.bit;
 
-		if (node->node.bit < 0) {
+		if (node_bit < 0) {
 			/* We have a dup tree now. Either it's for the same
 			 * value, and we walk down left, or it's a different
 			 * one and we don't have our key.
@@ -80,11 +82,11 @@
 
 		/* OK, normal data node, let's walk down */
 		bit = string_equal_bits(x, node->key, bit);
-		if (bit < node->node.bit)
+		if (bit < node_bit)
 			return NULL; /* no more common bits */
 
-		troot = node->node.branches.b[(((unsigned char*)x)[node->node.bit >> 3] >>
-					       (~node->node.bit & 7)) & 1];
+		troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>
+					       (~node_bit & 7)) & 1];
 	}
 }
 
@@ -102,6 +104,7 @@
 	eb_troot_t *root_right = root;
 	int diff;
 	int bit;
+	int old_node_bit;
 
 	side = EB_LEFT;
 	troot = root->b[EB_LEFT];
@@ -190,6 +193,7 @@
 		/* OK we're walking down this link */
 		old = container_of(eb_untag(troot, EB_NODE),
 				   struct ebpt_node, node.branches);
+		old_node_bit = old->node.bit;
 
 		/* Stop going down when we don't have common bits anymore. We
 		 * also stop in front of a duplicates tree because it means we
@@ -197,16 +201,16 @@
 		 * the current node's because as long as they are identical, we
 		 * know we descend along the correct side.
 		 */
-		if (old->node.bit < 0) {
+		if (old_node_bit < 0) {
 			/* we're above a duplicate tree, we must compare till the end */
 			bit = string_equal_bits(new->key, old->key, bit);
 			goto dup_tree;
 		}
-		else if (bit < old->node.bit) {
+		else if (bit < old_node_bit) {
 			bit = string_equal_bits(new->key, old->key, bit);
 		}
 
-		if (bit < old->node.bit) { /* we don't have all bits in common */
+		if (bit < old_node_bit) { /* we don't have all bits in common */
 			/* The tree did not contain the key, so we insert <new> before the node
 			 * <old>, and set ->bit to designate the lowest bit position in <new>
 			 * which applies to ->branches.b[].
@@ -244,7 +248,7 @@
 
 		/* walk down */
 		root = &old->node.branches;
-		side = (((unsigned char *)new->key)[old->node.bit >> 3] >> (~old->node.bit & 7)) & 1;
+		side = (((unsigned char *)new->key)[old_node_bit >> 3] >> (~old_node_bit & 7)) & 1;
 		troot = root->b[side];
 	}
 
diff --git a/ebtree/ebmbtree.c b/ebtree/ebmbtree.c
index a4a0354..156f0e2 100644
--- a/ebtree/ebmbtree.c
+++ b/ebtree/ebmbtree.c
@@ -1,7 +1,7 @@
 /*
- * Elastic Binary Trees - exported functinos for Multi-Byte data nodes.
- * Version 5.0
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Elastic Binary Trees - exported functions for Multi-Byte data nodes.
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -41,3 +41,37 @@
 {
 	return __ebmb_insert(root, new, len);
 }
+
+/* Find the first occurence of the longest prefix matching a key <x> in the
+ * tree <root>. It's the caller's responsibility to ensure that key <x> is at
+ * least as long as the keys in the tree. If none can be found, return NULL.
+ */
+REGPRM2 struct ebmb_node *
+ebmb_lookup_longest(struct eb_root *root, const void *x)
+{
+	return __ebmb_lookup_longest(root, x);
+}
+
+/* Find the first occurence of a prefix matching a key <x> of <pfx> BITS in the
+ * tree <root>. If none can be found, return NULL.
+ */
+REGPRM3 struct ebmb_node *
+ebmb_lookup_prefix(struct eb_root *root, const void *x, unsigned int pfx)
+{
+	return __ebmb_lookup_prefix(root, x, pfx);
+}
+
+/* Insert ebmb_node <new> into a prefix subtree starting at node root <root>.
+ * Only new->key and new->pfx need be set with the key and its prefix length.
+ * Note that bits between <pfx> and <len> are theorically ignored and should be
+ * zero, as it is not certain yet that they will always be ignored everywhere
+ * (eg in bit compare functions).
+ * The ebmb_node is returned.
+ * If root->b[EB_RGHT]==1, the tree may only contain unique keys. The
+ * len is specified in bytes.
+ */
+REGPRM3 struct ebmb_node *
+ebmb_insert_prefix(struct eb_root *root, struct ebmb_node *new, unsigned int len)
+{
+	return __ebmb_insert_prefix(root, new, len);
+}
diff --git a/ebtree/ebmbtree.h b/ebtree/ebmbtree.h
index 12b534d..78a17c1 100644
--- a/ebtree/ebmbtree.h
+++ b/ebtree/ebmbtree.h
@@ -1,7 +1,7 @@
 /*
  * Elastic Binary Trees - macros and structures for Multi-Byte data nodes.
- * Version 5.0
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -18,6 +18,8 @@
  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  */
 
+#define dprintf(x,...) do { } while(0)
+
 #ifndef _EBMBTREE_H
 #define _EBMBTREE_H
 
@@ -97,6 +99,9 @@
  */
 REGPRM3 struct ebmb_node *ebmb_lookup(struct eb_root *root, const void *x, unsigned int len);
 REGPRM3 struct ebmb_node *ebmb_insert(struct eb_root *root, struct ebmb_node *new, unsigned int len);
+REGPRM2 struct ebmb_node *ebmb_lookup_longest(struct eb_root *root, const void *x);
+REGPRM3 struct ebmb_node *ebmb_lookup_prefix(struct eb_root *root, const void *x, unsigned int pfx);
+REGPRM3 struct ebmb_node *ebmb_insert_prefix(struct eb_root *root, struct ebmb_node *new, unsigned int len);
 
 /* The following functions are less likely to be used directly, because their
  * code is larger. The non-inlined version is preferred.
@@ -115,31 +120,33 @@
 {
 	struct ebmb_node *node;
 	eb_troot_t *troot;
-	unsigned int bit;
+	int pos, side;
+	int node_bit;
 
 	troot = root->b[EB_LEFT];
 	if (unlikely(troot == NULL))
 		return NULL;
 
-	bit = 0;
+	pos = 0;
 	while (1) {
-		if ((eb_gettag(troot) == EB_LEAF)) {
+		if (eb_gettag(troot) == EB_LEAF) {
 			node = container_of(eb_untag(troot, EB_LEAF),
 					    struct ebmb_node, node.branches);
-			if (memcmp(node->key, x, len) == 0)
-				return node;
-			else
+			if (memcmp(node->key + pos, x, len - pos) != 0)
 				return NULL;
+			else
+				return node;
 		}
 		node = container_of(eb_untag(troot, EB_NODE),
 				    struct ebmb_node, node.branches);
 
-		if (node->node.bit < 0) {
+		node_bit = node->node.bit;
+		if (node_bit < 0) {
 			/* We have a dup tree now. Either it's for the same
 			 * value, and we walk down left, or it's a different
 			 * one and we don't have our key.
 			 */
-			if (memcmp(node->key, x, len) != 0)
+			if (memcmp(node->key + pos, x, len - pos) != 0)
 				return NULL;
 
 			troot = node->node.branches.b[EB_LEFT];
@@ -150,13 +157,37 @@
 			return node;
 		}
 
-		/* OK, normal data node, let's walk down */
-		bit = equal_bits(x, node->key, bit, node->node.bit);
-		if (bit < node->node.bit)
-			return NULL; /* no more common bits */
+		/* OK, normal data node, let's walk down. We check if all full
+		 * bytes are equal, and we start from the last one we did not
+		 * completely check. We stop as soon as we reach the last byte,
+		 * because we must decide to go left/right or abort.
+		 */
+		node_bit = ~node_bit + (pos << 3) + 8; // = (pos<<3) + (7 - node_bit)
+		if (node_bit < 0) {
+			/* This surprizing construction gives better performance
+			 * because gcc does not try to reorder the loop. Tested to
+			 * be fine with 2.95 to 4.2.
+			 */
+			while (1) {
+				x++; pos++;
+				if (node->key[pos-1] ^ *(unsigned char*)(x-1))
+					return NULL; /* more than one full byte is different */
+				node_bit += 8;
+				if (node_bit >= 0)
+					break;
+			}
+		}
 
-		troot = node->node.branches.b[(((unsigned char*)x)[node->node.bit >> 3] >>
-					       (~node->node.bit & 7)) & 1];
+		/* here we know that only the last byte differs, so node_bit < 8.
+		 * We have 2 possibilities :
+		 *   - more than the last bit differs => return NULL
+		 *   - walk down on side = (x[pos] >> node_bit) & 1
+		 */
+		side = *(unsigned char *)x >> node_bit;
+		if (((node->key[pos] >> node_bit) ^ side) > 1)
+			return NULL;
+		side &= 1;
+		troot = node->node.branches.b[side];
 	}
 }
 
@@ -170,10 +201,13 @@
 {
 	struct ebmb_node *old;
 	unsigned int side;
-	eb_troot_t *troot;
+	eb_troot_t *troot, **up_ptr;
 	eb_troot_t *root_right = root;
 	int diff;
 	int bit;
+	eb_troot_t *new_left, *new_rght;
+	eb_troot_t *new_leaf;
+	int old_node_bit;
 
 	side = EB_LEFT;
 	troot = root->b[EB_LEFT];
@@ -186,8 +220,6 @@
 		return new;
 	}
 
-	len <<= 3;
-
 	/* The tree descent is fairly easy :
 	 *  - first, check if we have reached a leaf node
 	 *  - second, check if we have gone too far
@@ -203,67 +235,27 @@
 	bit = 0;
 	while (1) {
 		if (unlikely(eb_gettag(troot) == EB_LEAF)) {
-			eb_troot_t *new_left, *new_rght;
-			eb_troot_t *new_leaf, *old_leaf;
-
+			/* insert above a leaf */
 			old = container_of(eb_untag(troot, EB_LEAF),
 					    struct ebmb_node, node.branches);
-
-			new_left = eb_dotag(&new->node.branches, EB_LEFT);
-			new_rght = eb_dotag(&new->node.branches, EB_RGHT);
-			new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
-			old_leaf = eb_dotag(&old->node.branches, EB_LEAF);
-
 			new->node.node_p = old->node.leaf_p;
-
-			/* Right here, we have 3 possibilities :
-			 * - the tree does not contain the key, and we have
-			 *   new->key < old->key. We insert new above old, on
-			 *   the left ;
-			 *
-			 * - the tree does not contain the key, and we have
-			 *   new->key > old->key. We insert new above old, on
-			 *   the right ;
-			 *
-			 * - the tree does contain the key, which implies it
-			 *   is alone. We add the new key next to it as a
-			 *   first duplicate.
-			 *
-			 * The last two cases can easily be partially merged.
-			 */
-			bit = equal_bits(new->key, old->key, bit, len);
-			diff = cmp_bits(new->key, old->key, bit);
-
-			if (diff < 0) {
-				new->node.leaf_p = new_left;
-				old->node.leaf_p = new_rght;
-				new->node.branches.b[EB_LEFT] = new_leaf;
-				new->node.branches.b[EB_RGHT] = old_leaf;
-			} else {
-				/* we may refuse to duplicate this key if the tree is
-				 * tagged as containing only unique keys.
-				 */
-				if (diff == 0 && eb_gettag(root_right))
-					return old;
-
-				/* new->key >= old->key, new goes the right */
-				old->node.leaf_p = new_left;
-				new->node.leaf_p = new_rght;
-				new->node.branches.b[EB_LEFT] = old_leaf;
-				new->node.branches.b[EB_RGHT] = new_leaf;
-
-				if (diff == 0) {
-					new->node.bit = -1;
-					root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
-					return new;
-				}
-			}
-			break;
+			up_ptr = &old->node.leaf_p;
+			goto check_bit_and_break;
 		}
 
 		/* OK we're walking down this link */
 		old = container_of(eb_untag(troot, EB_NODE),
 				   struct ebmb_node, node.branches);
+		old_node_bit = old->node.bit;
+
+		if (unlikely(old->node.bit < 0)) {
+			/* We're above a duplicate tree, so we must compare the whole value */
+			new->node.node_p = old->node.node_p;
+			up_ptr = &old->node.node_p;
+		check_bit_and_break:
+			bit = equal_bits(new->key, old->key, bit, len << 3);
+			break;
+		}
 
 		/* Stop going down when we don't have common bits anymore. We
 		 * also stop in front of a duplicates tree because it means we
@@ -271,71 +263,522 @@
 		 * the current node's because as long as they are identical, we
 		 * know we descend along the correct side.
 		 */
-		if (old->node.bit < 0) {
-			/* we're above a duplicate tree, we must compare till the end */
-			bit = equal_bits(new->key, old->key, bit, len);
-			goto dup_tree;
-		}
-		else if (bit < old->node.bit) {
-			bit = equal_bits(new->key, old->key, bit, old->node.bit);
+
+		bit = equal_bits(new->key, old->key, bit, old_node_bit);
+		if (unlikely(bit < old_node_bit)) {
+			/* The tree did not contain the key, so we insert <new> before the
+			 * node <old>, and set ->bit to designate the lowest bit position in
+			 * <new> which applies to ->branches.b[].
+			 */
+			new->node.node_p = old->node.node_p;
+			up_ptr = &old->node.node_p;
+			break;
 		}
+		/* we don't want to skip bits for further comparisons, so we must limit <bit>.
+		 * However, since we're going down around <old_node_bit>, we know it will be
+		 * properly matched, so we can skip this bit.
+		 */
+		bit = old_node_bit + 1;
+
+		/* walk down */
+		root = &old->node.branches;
+		side = old_node_bit & 7;
+		side ^= 7;
+		side = (new->key[old_node_bit >> 3] >> side) & 1;
+		troot = root->b[side];
+	}
+
+	new_left = eb_dotag(&new->node.branches, EB_LEFT);
+	new_rght = eb_dotag(&new->node.branches, EB_RGHT);
+	new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
+
+	/* Note: we can compare more bits than
+	 * the current node's because as long as they are identical, we
+	 * know we descend along the correct side.
+	 */
+	new->node.bit = bit;
+	diff = cmp_bits(new->key, old->key, bit);
+	if (diff == 0) {
+		new->node.bit = -1; /* mark as new dup tree, just in case */
 
-		if (bit < old->node.bit) { /* we don't have all bits in common */
-			/* The tree did not contain the key, so we insert <new> before the node
-			 * <old>, and set ->bit to designate the lowest bit position in <new>
-			 * which applies to ->branches.b[].
+		if (likely(eb_gettag(root_right))) {
+			/* we refuse to duplicate this key if the tree is
+			 * tagged as containing only unique keys.
 			 */
-			eb_troot_t *new_left, *new_rght;
-			eb_troot_t *new_leaf, *old_node;
+			return old;
+		}
 
-		dup_tree:
-			new_left = eb_dotag(&new->node.branches, EB_LEFT);
-			new_rght = eb_dotag(&new->node.branches, EB_RGHT);
-			new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
-			old_node = eb_dotag(&old->node.branches, EB_NODE);
+		if (eb_gettag(troot) != EB_LEAF) {
+			/* there was already a dup tree below */
+			struct eb_node *ret;
+			ret = eb_insert_dup(&old->node, &new->node);
+			return container_of(ret, struct ebmb_node, node);
+		}
+		/* otherwise fall through */
+	}
 
-			new->node.node_p = old->node.node_p;
+	if (diff >= 0) {
+		new->node.branches.b[EB_LEFT] = troot;
+		new->node.branches.b[EB_RGHT] = new_leaf;
+		new->node.leaf_p = new_rght;
+		*up_ptr = new_left;
+	}
+	else if (diff < 0) {
+		new->node.branches.b[EB_LEFT] = new_leaf;
+		new->node.branches.b[EB_RGHT] = troot;
+		new->node.leaf_p = new_left;
+		*up_ptr = new_rght;
+	}
 
-			diff = cmp_bits(new->key, old->key, bit);
-			if (diff < 0) {
-				new->node.leaf_p = new_left;
-				old->node.node_p = new_rght;
-				new->node.branches.b[EB_LEFT] = new_leaf;
-				new->node.branches.b[EB_RGHT] = old_node;
-			}
-			else if (diff > 0) {
-				old->node.node_p = new_left;
-				new->node.leaf_p = new_rght;
-				new->node.branches.b[EB_LEFT] = old_node;
-				new->node.branches.b[EB_RGHT] = new_leaf;
+	/* Ok, now we are inserting <new> between <root> and <old>. <old>'s
+	 * parent is already set to <new>, and the <root>'s branch is still in
+	 * <side>. Update the root's leaf till we have it. Note that we can also
+	 * find the side by checking the side of new->node.node_p.
+	 */
+
+	root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
+	return new;
+}
+
+
+/* Find the first occurence of the longest prefix matching a key <x> in the
+ * tree <root>. It's the caller's responsibility to ensure that key <x> is at
+ * least as long as the keys in the tree. If none can be found, return NULL.
+ */
+static forceinline struct ebmb_node *__ebmb_lookup_longest(struct eb_root *root, const void *x)
+{
+	struct ebmb_node *node;
+	eb_troot_t *troot, *cover;
+	int pos, side;
+	int node_bit;
+
+	troot = root->b[EB_LEFT];
+	if (unlikely(troot == NULL))
+		return NULL;
+
+	cover = NULL;
+	pos = 0;
+	while (1) {
+		if ((eb_gettag(troot) == EB_LEAF)) {
+			node = container_of(eb_untag(troot, EB_LEAF),
+					    struct ebmb_node, node.branches);
+			if (check_bits(x - pos, node->key, pos, node->node.pfx))
+				goto not_found;
+
+			return node;
+		}
+		node = container_of(eb_untag(troot, EB_NODE),
+				    struct ebmb_node, node.branches);
+
+		node_bit = node->node.bit;
+		if (node_bit < 0) {
+			/* We have a dup tree now. Either it's for the same
+			 * value, and we walk down left, or it's a different
+			 * one and we don't have our key.
+			 */
+			if (check_bits(x - pos, node->key, pos, node->node.pfx))
+				goto not_found;
+
+			troot = node->node.branches.b[EB_LEFT];
+			while (eb_gettag(troot) != EB_LEAF)
+				troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
+			node = container_of(eb_untag(troot, EB_LEAF),
+					    struct ebmb_node, node.branches);
+			return node;
+		}
+
+		node_bit >>= 1; /* strip cover bit */
+		node_bit = ~node_bit + (pos << 3) + 8; // = (pos<<3) + (7 - node_bit)
+		if (node_bit < 0) {
+			/* This uncommon construction gives better performance
+			 * because gcc does not try to reorder the loop. Tested to
+			 * be fine with 2.95 to 4.2.
+			 */
+			while (1) {
+				x++; pos++;
+				if (node->key[pos-1] ^ *(unsigned char*)(x-1))
+					goto not_found; /* more than one full byte is different */
+				node_bit += 8;
+				if (node_bit >= 0)
+					break;
 			}
-			else {
-				struct eb_node *ret;
-				ret = eb_insert_dup(&old->node, &new->node);
-				return container_of(ret, struct ebmb_node, node);
+		}
+
+		/* here we know that only the last byte differs, so 0 <= node_bit <= 7.
+		 * We have 2 possibilities :
+		 *   - more than the last bit differs => data does not match
+		 *   - walk down on side = (x[pos] >> node_bit) & 1
+		 */
+		side = *(unsigned char *)x >> node_bit;
+		if (((node->key[pos] >> node_bit) ^ side) > 1)
+			goto not_found;
+
+		if (!(node->node.bit & 1)) {
+			/* This is a cover node, let's keep a reference to it
+			 * for later. The covering subtree is on the left, and
+			 * the covered subtree is on the right, so we have to
+			 * walk down right.
+			 */
+			cover = node->node.branches.b[EB_LEFT];
+			troot = node->node.branches.b[EB_RGHT];
+			continue;
+		}
+		side &= 1;
+		troot = node->node.branches.b[side];
+	}
+
+ not_found:
+	/* Walk down last cover tre if it exists. It does not matter if cover is NULL */
+	return ebmb_entry(eb_walk_down(cover, EB_LEFT), struct ebmb_node, node);
+}
+
+
+/* Find the first occurence of a prefix matching a key <x> of <pfx> BITS in the
+ * tree <root>. If none can be found, return NULL.
+ */
+static forceinline struct ebmb_node *__ebmb_lookup_prefix(struct eb_root *root, const void *x, unsigned int pfx)
+{
+	struct ebmb_node *node;
+	eb_troot_t *troot;
+	int pos, side;
+	int node_bit;
+
+	troot = root->b[EB_LEFT];
+	if (unlikely(troot == NULL))
+		return NULL;
+
+	pos = 0;
+	while (1) {
+		if ((eb_gettag(troot) == EB_LEAF)) {
+			node = container_of(eb_untag(troot, EB_LEAF),
+					    struct ebmb_node, node.branches);
+			if (node->node.pfx != pfx)
+				return NULL;
+			if (check_bits(x - pos, node->key, pos, node->node.pfx))
+				return NULL;
+			return node;
+		}
+		node = container_of(eb_untag(troot, EB_NODE),
+				    struct ebmb_node, node.branches);
+
+		node_bit = node->node.bit;
+		if (node_bit < 0) {
+			/* We have a dup tree now. Either it's for the same
+			 * value, and we walk down left, or it's a different
+			 * one and we don't have our key.
+			 */
+			if (node->node.pfx != pfx)
+				return NULL;
+			if (check_bits(x - pos, node->key, pos, node->node.pfx))
+				return NULL;
+
+			troot = node->node.branches.b[EB_LEFT];
+			while (eb_gettag(troot) != EB_LEAF)
+				troot = (eb_untag(troot, EB_NODE))->b[EB_LEFT];
+			node = container_of(eb_untag(troot, EB_LEAF),
+					    struct ebmb_node, node.branches);
+			return node;
+		}
+
+		node_bit >>= 1; /* strip cover bit */
+		node_bit = ~node_bit + (pos << 3) + 8; // = (pos<<3) + (7 - node_bit)
+		if (node_bit < 0) {
+			/* This uncommon construction gives better performance
+			 * because gcc does not try to reorder the loop. Tested to
+			 * be fine with 2.95 to 4.2.
+			 */
+			while (1) {
+				x++; pos++;
+				if (node->key[pos-1] ^ *(unsigned char*)(x-1))
+					return NULL; /* more than one full byte is different */
+				node_bit += 8;
+				if (node_bit >= 0)
+					break;
 			}
+		}
+
+		/* here we know that only the last byte differs, so 0 <= node_bit <= 7.
+		 * We have 2 possibilities :
+		 *   - more than the last bit differs => data does not match
+		 *   - walk down on side = (x[pos] >> node_bit) & 1
+		 */
+		side = *(unsigned char *)x >> node_bit;
+		if (((node->key[pos] >> node_bit) ^ side) > 1)
+			return NULL;
+
+		if (!(node->node.bit & 1)) {
+			/* This is a cover node, it may be the entry we're
+			 * looking for. We already know that it matches all the
+			 * bits, let's compare prefixes and descend the cover
+			 * subtree if they match.
+			 */
+			if (node->node.bit >> 1 == pfx)
+				troot = node->node.branches.b[EB_LEFT];
+			else
+				troot = node->node.branches.b[EB_RGHT];
+			continue;
+		}
+		side &= 1;
+		troot = node->node.branches.b[side];
+	}
+}
+
+
+/* Insert ebmb_node <new> into a prefix subtree starting at node root <root>.
+ * Only new->key and new->pfx need be set with the key and its prefix length.
+ * Note that bits between <pfx> and <len> are theorically ignored and should be
+ * zero, as it is not certain yet that they will always be ignored everywhere
+ * (eg in bit compare functions).
+ * The ebmb_node is returned.
+ * If root->b[EB_RGHT]==1, the tree may only contain unique keys. The
+ * len is specified in bytes.
+ */
+static forceinline struct ebmb_node *
+__ebmb_insert_prefix(struct eb_root *root, struct ebmb_node *new, unsigned int len)
+{
+	struct ebmb_node *old;
+	unsigned int side;
+	eb_troot_t *troot, **up_ptr;
+	eb_troot_t *root_right = root;
+	int diff;
+	int bit;
+	eb_troot_t *new_left, *new_rght;
+	eb_troot_t *new_leaf;
+	int old_node_bit;
+
+	side = EB_LEFT;
+	troot = root->b[EB_LEFT];
+	root_right = root->b[EB_RGHT];
+	if (unlikely(troot == NULL)) {
+		/* Tree is empty, insert the leaf part below the left branch */
+		root->b[EB_LEFT] = eb_dotag(&new->node.branches, EB_LEAF);
+		new->node.leaf_p = eb_dotag(root, EB_LEFT);
+		new->node.node_p = NULL; /* node part unused */
+		return new;
+	}
+
+	len <<= 3;
+	if (len > new->node.pfx)
+		len = new->node.pfx;
+
+	/* The tree descent is fairly easy :
+	 *  - first, check if we have reached a leaf node
+	 *  - second, check if we have gone too far
+	 *  - third, reiterate
+	 * Everywhere, we use <new> for the node node we are inserting, <root>
+	 * for the node we attach it to, and <old> for the node we are
+	 * displacing below <new>. <troot> will always point to the future node
+	 * (tagged with its type). <side> carries the side the node <new> is
+	 * attached to below its parent, which is also where previous node
+	 * was attached.
+	 */
+
+	bit = 0;
+	while (1) {
+		if (unlikely(eb_gettag(troot) == EB_LEAF)) {
+			/* Insert above a leaf. Note that this leaf could very
+			 * well be part of a cover node.
+			 */
+			old = container_of(eb_untag(troot, EB_LEAF),
+					    struct ebmb_node, node.branches);
+			new->node.node_p = old->node.leaf_p;
+			up_ptr = &old->node.leaf_p;
+			goto check_bit_and_break;
+		}
+
+		/* OK we're walking down this link */
+		old = container_of(eb_untag(troot, EB_NODE),
+				   struct ebmb_node, node.branches);
+		old_node_bit = old->node.bit;
+		/* Note that old_node_bit can be :
+		 *   < 0    : dup tree
+		 *   = 2N   : cover node for N bits
+		 *   = 2N+1 : normal node at N bits
+		 */
+
+		if (unlikely(old_node_bit < 0)) {
+			/* We're above a duplicate tree, so we must compare the whole value */
+			new->node.node_p = old->node.node_p;
+			up_ptr = &old->node.node_p;
+		check_bit_and_break:
+			/* No need to compare everything if the leaves are shorter than the new one. */
+			if (len > old->node.pfx)
+				len = old->node.pfx;
+			bit = equal_bits(new->key, old->key, bit, len);
+			dprintf(" [new=%p, old=%p] obit=%d, eqbit=%d\n", new, old, old->node.bit, bit);
 			break;
 		}
 
+		/* WARNING: for the two blocks below, <bit> is counted in half-bits */
+
+		bit = equal_bits(new->key, old->key, bit, old_node_bit >> 1);
+		bit = (bit << 1) + 1; // assume comparisons with normal nodes
+		dprintf(" [old=%p, new=%p] bit=%d/2, old_bit=%d/2\n", old, new, bit, old_node_bit);
+
+		/* we must always check that our prefix is larger than the nodes
+		 * we visit, otherwise we have to stop going down. The following
+		 * test is able to stop before both normal and cover nodes.
+		 */
+		if (bit >= (new->node.pfx << 1) && (new->node.pfx << 1) < old_node_bit) {
+			/* insert cover node here on the left */
+			new->node.node_p = old->node.node_p;
+			up_ptr = &old->node.node_p;
+			new->node.bit = new->node.pfx << 1;
+			diff = -1;
+			dprintf(" [new=%p, old=%p] obit=%d, nbit=%d (1)\n", new, old, old->node.bit, new->node.bit);
+			goto insert_above;
+		}
+
+		if (unlikely(bit < old_node_bit)) {
+			/* The tree did not contain the key, so we insert <new> before the
+			 * node <old>, and set ->bit to designate the lowest bit position in
+			 * <new> which applies to ->branches.b[]. We know that the bit is not
+			 * greater than the prefix length thanks to the test above.
+			 */
+			new->node.node_p = old->node.node_p;
+			up_ptr = &old->node.node_p;
+			new->node.bit = bit;
+			diff = cmp_bits(new->key, old->key, bit >> 1);
+			dprintf(" --> diff=%d, node.bit=%d/2\n", diff, new->node.bit);
+			goto insert_above;
+		}
+
+		if (!(old_node_bit & 1)) {
+			/* if we encounter a cover node with our exact prefix length, it's
+			 * necessarily the same value, so we insert there as a duplicate on
+			 * the left. For that, we go down on the left and the leaf detection
+			 * code will finish the job.
+			 */
+			if ((new->node.pfx << 1) == old_node_bit) {
+				root = &old->node.branches;
+				side = EB_LEFT;
+				troot = root->b[side];
+				dprintf(" --> going down cover by left\n");
+				continue;
+			}
+
+			/* cover nodes are always walked through on the right */
+			side = EB_RGHT;
+			bit = old_node_bit >> 1; /* recheck that bit */
+			root = &old->node.branches;
+			troot = root->b[side];
+			dprintf(" --> going down cover by right\n");
+			continue;
+		}
+
+		/* we don't want to skip bits for further comparisons, so we must limit <bit>.
+		 * However, since we're going down around <old_node_bit>, we know it will be
+		 * properly matched, so we can skip this bit.
+		 */
+		old_node_bit >>= 1;
+		bit = old_node_bit + 1;
+
 		/* walk down */
 		root = &old->node.branches;
-		side = (new->key[old->node.bit >> 3] >> (~old->node.bit & 7)) & 1;
+		side = old_node_bit & 7;
+		side ^= 7;
+		side = (new->key[old_node_bit >> 3] >> side) & 1;
 		troot = root->b[side];
 	}
 
-	/* Ok, now we are inserting <new> between <root> and <old>. <old>'s
-	 * parent is already set to <new>, and the <root>'s branch is still in
-	 * <side>. Update the root's leaf till we have it. Note that we can also
-	 * find the side by checking the side of new->node.node_p.
+	/* Right here, we have 4 possibilities :
+	 * - the tree does not contain any leaf matching the
+	 *   key, and we have new->key < old->key. We insert
+	 *   new above old, on the left ;
+	 *
+	 * - the tree does not contain any leaf matching the
+	 *   key, and we have new->key > old->key. We insert
+	 *   new above old, on the right ;
+	 *
+	 * - the tree does contain the key with the same prefix
+	 *   length. We add the new key next to it as a first
+	 *   duplicate (since it was alone).
+	 *
+	 * The last two cases can easily be partially merged.
+	 *
+	 * - the tree contains a leaf matching the key, we have
+	 *   to insert above it as a cover node. The leaf with
+	 *   the shortest prefix becomes the left subtree and
+	 *   the leaf with the longest prefix becomes the right
+	 *   one. The cover node gets the min of both prefixes
+	 *   as its new bit.
 	 */
 
-	/* We need the common higher bits between new->key and old->key.
-	 * This number of bits is already in <bit>.
+	/* first we want to ensure that we compare the correct bit, which means
+	 * the largest common to both nodes.
 	 */
-	new->node.bit = bit;
+	if (bit > new->node.pfx)
+		bit = new->node.pfx;
+	if (bit > old->node.pfx)
+		bit = old->node.pfx;
+
+	dprintf(" [old=%p, new=%p] bit2=%d\n", old, new, bit);
+	new->node.bit = (bit << 1) + 1; /* assume normal node by default */
+
+	/* if one prefix is included in the second one, we don't compare bits
+	 * because they won't necessarily match, we just proceed with a cover
+	 * node insertion.
+	 */
+	diff = 0;
+	if (bit < old->node.pfx && bit < new->node.pfx)
+		diff = cmp_bits(new->key, old->key, bit);
+
+	if (diff == 0) {
+		/* Both keys match. Either it's a duplicate entry or we have to
+		 * put the shortest prefix left and the largest one right below
+		 * a new cover node. By default, diff==0 means we'll be inserted
+		 * on the right.
+		 */
+		new->node.bit--; /* anticipate cover node insertion */
+		if (new->node.pfx == old->node.pfx) {
+			dprintf(" [inserting dup %p->%p]\n", old, new);
+			new->node.bit = -1; /* mark as new dup tree, just in case */
+
+			if (unlikely(eb_gettag(root_right))) {
+				/* we refuse to duplicate this key if the tree is
+				 * tagged as containing only unique keys.
+				 */
+				return old;
+			}
+
+			if (eb_gettag(troot) != EB_LEAF) {
+				/* there was already a dup tree below */
+				struct eb_node *ret;
+				ret = eb_insert_dup(&old->node, &new->node);
+				return container_of(ret, struct ebmb_node, node);
+			}
+			/* otherwise fall through to insert first duplicate */
+		}
+		/* otherwise we just rely on the tests below to select the right side */
+		else if (new->node.pfx < old->node.pfx)
+			diff = -1; /* force insertion to left side */
+	}
+
+ insert_above:
+	new_left = eb_dotag(&new->node.branches, EB_LEFT);
+	new_rght = eb_dotag(&new->node.branches, EB_RGHT);
+	new_leaf = eb_dotag(&new->node.branches, EB_LEAF);
+
+	if (diff >= 0) {
+		dprintf(" [old=%p, new=%p] inserting right, obit=%d/2, nbit=%d/2\n", old, new, old->node.bit, new->node.bit);
+		new->node.branches.b[EB_LEFT] = troot;
+		new->node.branches.b[EB_RGHT] = new_leaf;
+		new->node.leaf_p = new_rght;
+		*up_ptr = new_left;
+	}
+	else {
+		dprintf(" [old=%p, new=%p] inserting left,  obit=%d/2, nbit=%d/2\n", old, new, old->node.bit, new->node.bit);
+		new->node.branches.b[EB_LEFT] = new_leaf;
+		new->node.branches.b[EB_RGHT] = troot;
+		new->node.leaf_p = new_left;
+		*up_ptr = new_rght;
+	}
+
 	root->b[side] = eb_dotag(&new->node.branches, EB_NODE);
 	return new;
 }
 
+
+
 #endif /* _EBMBTREE_H */
 
diff --git a/ebtree/ebpttree.c b/ebtree/ebpttree.c
index 76e6db8..d0ca15f 100644
--- a/ebtree/ebpttree.c
+++ b/ebtree/ebpttree.c
@@ -1,6 +1,7 @@
 /*
  * Elastic Binary Trees - exported functions for operations on pointer nodes.
- * (C) 2002-2007 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -87,7 +88,7 @@
 			 * small and we need to get its highest value, or it is
 			 * too large, and we need to get the prev value.
 			 */
-			if (((ptr_t)node->key >> node->node.bit) > ((ptr_t)x >> node->node.bit)) {
+			if (((ptr_t)node->key >> node->node.bit) < ((ptr_t)x >> node->node.bit)) {
 				troot = node->node.branches.b[EB_RGHT];
 				return ebpt_entry(eb_walk_down(troot, EB_RGHT), struct ebpt_node, node);
 			}
diff --git a/ebtree/ebpttree.h b/ebtree/ebpttree.h
index f6e5219..b040c35 100644
--- a/ebtree/ebpttree.h
+++ b/ebtree/ebpttree.h
@@ -1,7 +1,7 @@
 /*
  * Elastic Binary Trees - macros and structures for operations on pointer nodes.
- * Version 5.0
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
diff --git a/ebtree/ebsttree.c b/ebtree/ebsttree.c
index b00ad69..a98b0f3 100644
--- a/ebtree/ebsttree.c
+++ b/ebtree/ebsttree.c
@@ -1,7 +1,7 @@
 /*
  * Elastic Binary Trees - exported functions for String data nodes.
- * Version 5.1
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
diff --git a/ebtree/ebsttree.h b/ebtree/ebsttree.h
index 6fa6412..f15af38 100644
--- a/ebtree/ebsttree.h
+++ b/ebtree/ebsttree.h
@@ -1,7 +1,7 @@
 /*
  * Elastic Binary Trees - macros to manipulate String data nodes.
- * Version 5.1
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -41,7 +41,8 @@
 {
 	struct ebmb_node *node;
 	eb_troot_t *troot;
-	unsigned int bit;
+	int bit;
+	int node_bit;
 
 	troot = root->b[EB_LEFT];
 	if (unlikely(troot == NULL))
@@ -59,8 +60,9 @@
 		}
 		node = container_of(eb_untag(troot, EB_NODE),
 				    struct ebmb_node, node.branches);
+		node_bit = node->node.bit;
 
-		if (node->node.bit < 0) {
+		if (node_bit < 0) {
 			/* We have a dup tree now. Either it's for the same
 			 * value, and we walk down left, or it's a different
 			 * one and we don't have our key.
@@ -78,11 +80,11 @@
 
 		/* OK, normal data node, let's walk down */
 		bit = string_equal_bits(x, node->key, bit);
-		if (bit < node->node.bit)
+		if (bit < node_bit)
 			return NULL; /* no more common bits */
 
-		troot = node->node.branches.b[(((unsigned char*)x)[node->node.bit >> 3] >>
-					       (~node->node.bit & 7)) & 1];
+		troot = node->node.branches.b[(((unsigned char*)x)[node_bit >> 3] >>
+					       (~node_bit & 7)) & 1];
 	}
 }
 
@@ -100,6 +102,7 @@
 	eb_troot_t *root_right = root;
 	int diff;
 	int bit;
+	int old_node_bit;
 
 	side = EB_LEFT;
 	troot = root->b[EB_LEFT];
@@ -188,6 +191,7 @@
 		/* OK we're walking down this link */
 		old = container_of(eb_untag(troot, EB_NODE),
 				   struct ebmb_node, node.branches);
+		old_node_bit = old->node.bit;
 
 		/* Stop going down when we don't have common bits anymore. We
 		 * also stop in front of a duplicates tree because it means we
@@ -195,16 +199,16 @@
 		 * the current node's because as long as they are identical, we
 		 * know we descend along the correct side.
 		 */
-		if (old->node.bit < 0) {
+		if (old_node_bit < 0) {
 			/* we're above a duplicate tree, we must compare till the end */
 			bit = string_equal_bits(new->key, old->key, bit);
 			goto dup_tree;
 		}
-		else if (bit < old->node.bit) {
+		else if (bit < old_node_bit) {
 			bit = string_equal_bits(new->key, old->key, bit);
 		}
 
-		if (bit < old->node.bit) { /* we don't have all bits in common */
+		if (bit < old_node_bit) { /* we don't have all bits in common */
 			/* The tree did not contain the key, so we insert <new> before the node
 			 * <old>, and set ->bit to designate the lowest bit position in <new>
 			 * which applies to ->branches.b[].
@@ -242,7 +246,7 @@
 
 		/* walk down */
 		root = &old->node.branches;
-		side = (new->key[old->node.bit >> 3] >> (~old->node.bit & 7)) & 1;
+		side = (new->key[old_node_bit >> 3] >> (~old_node_bit & 7)) & 1;
 		troot = root->b[side];
 	}
 
diff --git a/ebtree/ebtree.c b/ebtree/ebtree.c
index 8f45da2..1bcd46b 100644
--- a/ebtree/ebtree.c
+++ b/ebtree/ebtree.c
@@ -1,6 +1,7 @@
 /*
  * Elastic Binary Trees - exported generic functions
- * (C) 2002-2007 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
diff --git a/ebtree/ebtree.h b/ebtree/ebtree.h
index 76ea1e7..60fc197 100644
--- a/ebtree/ebtree.h
+++ b/ebtree/ebtree.h
@@ -1,7 +1,7 @@
 /*
  * Elastic Binary Trees - generic macros and structures.
- * Version 5.0
- * (C) 2002-2009 - Willy Tarreau <w@1wt.eu>
+ * Version 6.0
+ * (C) 2002-2010 - Willy Tarreau <w@1wt.eu>
  *
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -259,10 +259,18 @@
 #include <stdlib.h>
 #include "compiler.h"
 
+static inline int flsnz8_generic(unsigned int x)
+{
+	int ret = 0;
+	if (x >> 4) { x >>= 4; ret += 4; }
+	return ret + ((0xFFFFAA50U >> (x << 1)) & 3) + 1;
+}
+
 /* Note: we never need to run fls on null keys, so we can optimize the fls
  * function by removing a conditional jump.
  */
-#if defined(__i386__)
+#if defined(__i386__) || defined(__x86_64__)
+/* this code is similar on 32 and 64 bit */
 static inline int flsnz(int x)
 {
 	int r;
@@ -270,6 +278,16 @@
 	        : "=r" (r) : "rm" (x));
 	return r+1;
 }
+
+static inline int flsnz8(unsigned char x)
+{
+	int r;
+	__asm__("movzbl %%al, %%eax\n"
+		"bsrl %%eax,%0\n"
+	        : "=r" (r) : "a" (x));
+	return r+1;
+}
+
 #else
 // returns 1 to 32 for 1<<0 to 1<<31. Undefined for 0.
 #define flsnz(___a) ({ \
@@ -282,6 +300,13 @@
 	if (___x & 0xaaaaaaaa) { ___x &= 0xaaaaaaaa; ___bits +=  1;} \
 	___bits + 1; \
 	})
+
+static inline int flsnz8(unsigned int x)
+{
+	return flsnz8_generic(x);
+}
+
+
 #endif
 
 static inline int fls64(unsigned long long x)
@@ -350,7 +375,8 @@
 	struct eb_root branches; /* branches, must be at the beginning */
 	eb_troot_t    *node_p;  /* link node's parent */
 	eb_troot_t    *leaf_p;  /* leaf node's parent */
-	int           bit;     /* link's bit position. */
+	short int      bit;     /* link's bit position. */
+	short int      pfx;     /* data prefix length, always related to leaf */
 };
 
 /* Return the structure of type <type> whose member <member> points to <ptr> */
@@ -698,40 +724,63 @@
  * bytes. Note that parts or all of <ignore> bits may be rechecked. It is only
  * passed here as a hint to speed up the check.
  */
-static forceinline unsigned int equal_bits(const unsigned char *a,
-				      const unsigned char *b,
-				      unsigned int ignore, unsigned int len)
+static forceinline int equal_bits(const unsigned char *a,
+				  const unsigned char *b,
+				  int ignore, int len)
 {
-	unsigned int beg;
-	unsigned int end;
-	unsigned int ret;
-	unsigned char c;
+	for (ignore >>= 3, a += ignore, b += ignore, ignore <<= 3;
+	     ignore < len; ) {
+		unsigned char c;
 
-	beg = ignore >> 3;
-	end = (len + 7) >> 3;
-	ret = end << 3;
-	
-	do {
-		if (beg >= end)
-			goto out;
-		beg++;
-		c = a[beg-1] ^ b[beg-1];
-	} while (!c);
+		a++; b++;
+		ignore += 8;
+		c = b[-1] ^ a[-1];
+
+		if (c) {
+			/* OK now we know that old and new differ at byte <ptr> and that <c> holds
+			 * the bit differences. We have to find what bit is differing and report
+			 * it as the number of identical bits. Note that low bit numbers are
+			 * assigned to high positions in the byte, as we compare them as strings.
+			 */
+			ignore -= flsnz8(c);
+			break;
+		}
+	}
+	return ignore;
+}
 
-	/* OK now we know that a and b differ at byte <beg> and that <c> holds
-	 * the bit differences. We have to find what bit is differing and report
-	 * it as the number of identical bits. Note that low bit numbers are
-	 * assigned to high positions in the byte, as we compare them as strings.
+/* check that the two blocks <a> and <b> are equal on <len> bits. If it is known
+ * they already are on some bytes, this number of equal bytes to be skipped may
+ * be passed in <skip>. It returns 0 if they match, otherwise non-zero.
+ */
+static forceinline int check_bits(const unsigned char *a,
+				  const unsigned char *b,
+				  int skip,
+				  int len)
+{
+	int bit, ret;
+
+	/* This uncommon construction gives the best performance on x86 because
+	 * it makes heavy use multiple-index addressing and parallel instructions,
+	 * and it prevents gcc from reordering the loop since it is already
+	 * properly oriented. Tested to be fine with 2.95 to 4.2.
 	 */
-	ret = beg << 3;
-	if (c & 0xf0) { c >>= 4; ret -= 4; }
-	if (c & 0x0c) { c >>= 2; ret -= 2; }
-	ret -= (c >> 1);
-	ret--;
- out:
-	return ret;
+	bit = ~len + (skip << 3) + 9; // = (skip << 3) + (8 - len)
+	ret = a[skip] ^ b[skip];
+	if (unlikely(bit >= 0))
+		return ret >> bit;
+	while (1) {
+		skip++;
+		if (ret)
+			return ret;
+		ret = a[skip] ^ b[skip];
+		bit += 8;
+		if (bit >= 0)
+			return ret >> bit;
+	}
 }
 
+
 /* Compare strings <a> and <b> byte-to-byte, from bit <ignore> to the last 0.
  * Return the number of equal bits between strings, assuming that the first
  * <ignore> bits are already identical. Note that parts or all of <ignore> bits
@@ -740,11 +789,11 @@
  * of the two strings. However, referencing any bit from the trailing zero is
  * permitted.
  */
-static forceinline unsigned int string_equal_bits(const unsigned char *a,
-						  const unsigned char *b,
-						  unsigned int ignore)
+static forceinline int string_equal_bits(const unsigned char *a,
+					 const unsigned char *b,
+					 int ignore)
 {
-	unsigned int beg;
+	int beg;
 	unsigned char c;
 
 	beg = ignore >> 3;
@@ -771,14 +820,7 @@
 	 * identical bits. Note that low bit numbers are assigned to high positions
 	 * in the byte, as we compare them as strings.
 	 */
-	beg <<= 3;
-	if (c & 0xf0) { c >>= 4; beg -= 4; }
-	if (c & 0x0c) { c >>= 2; beg -= 2; }
-	beg -= (c >> 1);
-	if (c)
-		beg--;
-
-	return beg;
+	return (beg << 3) - flsnz8(c);
 }
 
 static forceinline int cmp_bits(const unsigned char *a, const unsigned char *b, unsigned int pos)