From 30cc7d2969aa5397328a49a7d85196a4afdc7f8b Mon Sep 17 00:00:00 2001 From: ZhengLingyun Date: Mon, 15 Jul 2013 08:21:04 +0800 Subject: [PATCH] hindex: Fix incomplete iteration bug. hindex_next() make the completely wrong assumption that head nodes within a bucket were sorted in ascending order by hash. This commit removes that assumption. Also add a test that would have found the problem. Signed-off-by: ZhengLingyun [blp@nicira.com changed how hindex_head_node() is implemented and other code details] Signed-off-by: Ben Pfaff --- lib/hindex.c | 35 +++++++++++++++++++++++++++++------ tests/test-hindex.c | 7 +++++++ 2 files changed, 36 insertions(+), 6 deletions(-) diff --git a/lib/hindex.c b/lib/hindex.c index dc0f1b73a..fd4199ae1 100644 --- a/lib/hindex.c +++ b/lib/hindex.c @@ -287,6 +287,19 @@ hindex_node_with_hash(const struct hindex *hindex, size_t hash) return node; } +/* Returns the head node in 'hindex' with the given 'hash'. 'hindex' must + * contain a head node with the given hash. */ +static struct hindex_node * +hindex_head_node(const struct hindex *hindex, size_t hash) +{ + struct hindex_node *node = hindex->buckets[hash & hindex->mask]; + + while (node->hash != hash) { + node = node->d; + } + return node; +} + static struct hindex_node * hindex_next__(const struct hindex *hindex, size_t start) { @@ -312,13 +325,23 @@ hindex_first(const struct hindex *hindex) * null pointer if 'node' is the last node in 'hindex'. * * If the hash index has been reallocated since 'node' was visited, some nodes - * may be skipped or visited twice. (Removing 'node' from the hash index does - * not prevent calling this function, since node->next is preserved, although - * freeing 'node' of course does.) */ + * may be skipped or visited twice. */ 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)); + struct hindex_node *head; + + /* If there's a node with the same hash, return it. */ + if (node->s) { + return node->s; + } + + /* If there's another node in the same bucket, return it. */ + head = hindex_head_node(hindex, node->hash); + if (head->d) { + return head->d; + } + + /* Return the first node in the next (or later) bucket. */ + return hindex_next__(hindex, (node->hash & hindex->mask) + 1); } diff --git a/tests/test-hindex.c b/tests/test-hindex.c index 7a3ef7212..f0a8b9335 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; -- 2.43.0