[MEDIUM] ebtree: upgrade to version 6.0
This version adds support for prefix-based matching of memory blocks,
as well as some code-size and performance improvements on the generic
code. It provides a prefix insertion and longest match which are
compatible with the rest of the common features (walk, duplicates,
delete, ...). This is typically used for network address matching. The
longest-match code is a bit slower than the original memory block
handling code, so they have not been merged together into generic
code. Still it's possible to perform about 10 million networks lookups
per second in a set of 50000, so this should be enough for most usages.
This version also fixes some bugs in parts that were not used, so there
is no need to backport them.
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)