[ovs-dev] [PATCH] cmap: Fix cmap_next_position()
Daniele Di Proietto
ddiproietto at vmware.com
Wed Jul 16 04:57:55 UTC 2014
cmap_next_position() didn't update the node pointer while iterating through a
list of nodes with the same hash.
This commit fixes the bug and improve test-cmap to detect it.
Signed-off-by: Daniele Di Proietto <ddiproietto at vmware.com>
---
lib/cmap.c | 2 +-
tests/test-cmap.c | 31 +++++++++++++++++++++++--------
2 files changed, 24 insertions(+), 9 deletions(-)
diff --git a/lib/cmap.c b/lib/cmap.c
index 0a79132..5d6dbcf 100644
--- a/lib/cmap.c
+++ b/lib/cmap.c
@@ -854,7 +854,7 @@ cmap_next_position(const struct cmap *cmap,
const struct cmap_node *node = cmap_node_next(&b->nodes[entry]);
unsigned int i;
- for (i = 0; node; i++) {
+ for (i = 0; node; i++, node = cmap_node_next(node)) {
if (i == offset) {
if (cmap_node_next(node)) {
offset++;
diff --git a/tests/test-cmap.c b/tests/test-cmap.c
index 46c00e1..3dfe998 100644
--- a/tests/test-cmap.c
+++ b/tests/test-cmap.c
@@ -50,10 +50,12 @@ compare_ints(const void *a_, const void *b_)
return *a < *b ? -1 : *a > *b;
}
-/* Verifies that 'cmap' contains exactly the 'n' values in 'values'. */
+/* Verifies that 'cmap' contains exactly the 'n' values in 'values'. If
+ * 'uses_next_position' is true, it uses cmap_next_position() instead of a
+ * cursor to perform the iteration. */
static void
check_cmap(struct cmap *cmap, const int values[], size_t n,
- hash_func *hash)
+ hash_func *hash, bool use_next_position)
{
int *sort_values, *cmap_values;
const struct element *e;
@@ -64,9 +66,21 @@ check_cmap(struct cmap *cmap, const int values[], size_t n,
cmap_values = xmalloc(sizeof *sort_values * n);
i = 0;
- CMAP_FOR_EACH (e, node, cmap) {
- assert(i < n);
- cmap_values[i++] = e->value;
+ if (use_next_position) {
+ struct cmap_position pos = { 0, 0, 0 };
+ struct cmap_node * cn;
+
+ while ((cn = cmap_next_position(cmap, &pos))) {
+ struct element *e = OBJECT_CONTAINING(cn, e, node);
+
+ assert(i < n);
+ cmap_values[i++] = e->value;
+ }
+ } else {
+ CMAP_FOR_EACH (e, node, cmap) {
+ assert(i < n);
+ cmap_values[i++] = e->value;
+ }
}
assert(i == n);
@@ -172,19 +186,20 @@ test_cmap_insert_replace_delete(hash_func *hash)
elements[i].value = i;
cmap_insert(&cmap, &elements[i].node, hash(i));
values[i] = i;
- check_cmap(&cmap, values, i + 1, hash);
+ check_cmap(&cmap, values, i + 1, hash, false);
}
+ check_cmap(&cmap, values, N_ELEMS, hash, true);
shuffle(values, N_ELEMS);
for (i = 0; i < N_ELEMS; i++) {
copies[values[i]].value = values[i];
cmap_replace(&cmap, &elements[values[i]].node,
&copies[values[i]].node, hash(values[i]));
- check_cmap(&cmap, values, N_ELEMS, hash);
+ check_cmap(&cmap, values, N_ELEMS, hash, false);
}
shuffle(values, N_ELEMS);
for (i = 0; i < N_ELEMS; i++) {
cmap_remove(&cmap, &copies[values[i]].node, hash(values[i]));
- check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash);
+ check_cmap(&cmap, values + (i + 1), N_ELEMS - (i + 1), hash, false);
}
cmap_destroy(&cmap);
}
--
2.0.0
More information about the dev
mailing list