[ovs-dev] [PATCH] Fix hindex iteration incomplete bug
ZhengLingyun
konghuarukhr at 163.com
Mon Jul 15 00:21:04 UTC 2013
hindex_next() shouldn't jump over different hashs in the same bucket.
tests/test-hindex did not detect it, add a multipart_hash() method to detect it.
Signed-off-by: ZhengLingyun <konghuarukhr at 163.com>
---
lib/hindex.c | 21 ++++++++++++++++++---
tests/test-hindex.c | 7 +++++++
2 files changed, 25 insertions(+), 3 deletions(-)
diff --git a/lib/hindex.c b/lib/hindex.c
index dc0f1b7..37b1d0b 100644
--- a/lib/hindex.c
+++ b/lib/hindex.c
@@ -287,6 +287,17 @@ hindex_node_with_hash(const struct hindex *hindex, size_t hash)
return node;
}
+/* Returns the head node of 'node', 'node' can be head node or body node. */
+static struct hindex_node *
+hindex_head_node(const struct hindex *hindex OVS_UNUSED,
+ const struct hindex_node *node)
+{
+ while (hindex_node_is_body(node)) {
+ node = node->d;
+ }
+ return node;
+}
+
static struct hindex_node *
hindex_next__(const struct hindex *hindex, size_t start)
{
@@ -318,7 +329,11 @@ hindex_first(const struct hindex *hindex)
struct hindex_node *
hindex_next(const struct hindex *hindex, const struct hindex_node *node)
{
- return (node->s ? node->s
- : node->d && node->d->hash != node->hash ? node->d
- : hindex_next__(hindex, (node->hash & hindex->mask) + 1));
+ if (node->s) {
+ return node->s;
+ }
+
+ node = hindex_head_node(hindex, node);
+ return node->d ? node->d
+ : hindex_next__(hindex, (node->hash & hindex->mask) + 1);
}
diff --git a/tests/test-hindex.c b/tests/test-hindex.c
index 7a3ef72..f0a8b93 100644
--- a/tests/test-hindex.c
+++ b/tests/test-hindex.c
@@ -178,6 +178,12 @@ mod2_hash(int value)
return value % 2;
}
+static size_t
+multipart_hash(int value)
+{
+ return (mod4_hash(value) << 16) | (constant_hash(value) & 0xFFFF);
+}
+
/* Tests basic hindex insertion and deletion. */
static void
test_hindex_insert_delete(hash_func *hash)
@@ -298,6 +304,7 @@ run_test(void (*function)(hash_func *))
mod4_hash,
mod3_hash,
mod2_hash,
+ multipart_hash,
};
size_t i;
--
1.7.9.5
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openvswitch.org/pipermail/ovs-dev/attachments/20130715/c07e48b4/attachment-0003.html>
More information about the dev
mailing list