[ovs-dev] [PATCH] cmap: Fix cmap_next_position()

[Daniele Di Proietto]

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 <ddiproie...@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

_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev