diff options
author | ZhengLingyun <konghuarukhr@163.com> | 2013-07-15 08:21:04 +0800 |
---|---|---|
committer | Ben Pfaff <blp@nicira.com> | 2013-07-16 09:58:50 -0700 |
commit | 30cc7d2969aa5397328a49a7d85196a4afdc7f8b (patch) | |
tree | d1787f2aba1c7f147a9e77570b62235b9cc0ccf0 /lib/hindex.c | |
parent | fb93e9aa6ce38fcf85aa997a430115b5b3247af4 (diff) | |
download | openvswitch-30cc7d2969aa5397328a49a7d85196a4afdc7f8b.tar.gz |
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 <konghuarukhr@163.com>
[blp@nicira.com changed how hindex_head_node() is implemented and
other code details]
Signed-off-by: Ben Pfaff <blp@nicira.com>
Diffstat (limited to 'lib/hindex.c')
-rw-r--r-- | lib/hindex.c | 35 |
1 files changed, 29 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); } |