Sparse array iterators include index position.

Iterators over the sparse array structures have gained an initial argument
which indicates the index into the array of the element.  This can be used,
e.g., to delete or modify the associated value.

Reviewed-by: Richard Levitte <levitte@openssl.org>
(Merged from https://github.com/openssl/openssl/pull/8229)

4 files changed, 129 insertions, 23 deletions

diff --git a/crypto/include/internal/sparse_array.h b/crypto/include/internal/sparse_array.h
index bf0a996..839fced 100644
--- a/crypto/include/internal/sparse_array.h
+++ b/crypto/include/internal/sparse_array.h
@@ -37,16 +37,17 @@ extern "C" {
         return OPENSSL_SA_num((OPENSSL_SA *)sa); \
     } \
     static ossl_inline void ossl_sa_##type##_doall(const SPARSE_ARRAY_OF(type) *sa, \
-                                                   void (*leaf)(type *)) \
+                                                   void (*leaf)(size_t, type *)) \
     { \
-        OPENSSL_SA_doall((OPENSSL_SA *)sa, (void (*)(void *))leaf); \
+        OPENSSL_SA_doall((OPENSSL_SA *)sa, (void (*)(size_t, void *))leaf); \
     } \
     static ossl_inline void ossl_sa_##type##_doall_arg(const SPARSE_ARRAY_OF(type) *sa, \
-                                                       void (*leaf)(type *, \
+                                                       void (*leaf)(size_t, \
+                                                                    type *, \
 						                    void *),\
                                                        void *arg) \
     { \
-        OPENSSL_SA_doall_arg((OPENSSL_SA *)sa, (void (*)(void *, void *))leaf, \
+        OPENSSL_SA_doall_arg((OPENSSL_SA *)sa, (void (*)(size_t, void *, void *))leaf, \
                              arg); \
     } \
     static ossl_inline type *ossl_sa_##type##_get(const SPARSE_ARRAY_OF(type) *sa, \
@@ -66,9 +67,9 @@ OPENSSL_SA *OPENSSL_SA_new(void);
 void OPENSSL_SA_free(OPENSSL_SA *sa);
 void OPENSSL_SA_free_leaves(OPENSSL_SA *sa);
 size_t OPENSSL_SA_num(const OPENSSL_SA *sa);
-void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(void *));
-void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa, void (*leaf)(void *, void *),
-                          void *);
+void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(size_t, void *));
+void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa,
+                          void (*leaf)(size_t, void *, void *), void *);
 void *OPENSSL_SA_get(const OPENSSL_SA *sa, size_t n);
 int OPENSSL_SA_set(OPENSSL_SA *sa, size_t n, void *val);
 
diff --git a/crypto/sparse_array.c b/crypto/sparse_array.c
index 8c9efed..796d35e 100644
--- a/crypto/sparse_array.c
+++ b/crypto/sparse_array.c
@@ -68,10 +68,11 @@ OPENSSL_SA *OPENSSL_SA_new(void)
 }
 
 static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **),
-                     void (*leaf)(void *, void *), void *arg)
+                     void (*leaf)(size_t, void *, void *), void *arg)
 {
     int i[SA_BLOCK_MAX_LEVELS];
     void *nodes[SA_BLOCK_MAX_LEVELS];
+    size_t idx = 0;
     int l = 0;
 
     i[0] = 0;
@@ -84,14 +85,17 @@ static void sa_doall(const OPENSSL_SA *sa, void (*node)(void **),
             if (p != NULL && node != NULL)
                 (*node)(p);
             l--;
+            idx >>= OPENSSL_SA_BLOCK_BITS;
         } else {
             i[l] = n + 1;
             if (p != NULL && p[n] != NULL) {
+                idx = (idx & ~SA_BLOCK_MASK) | n;
                 if (l < sa->levels - 1) {
                     i[++l] = 0;
                     nodes[l] = p[n];
+                    idx <<= OPENSSL_SA_BLOCK_BITS;
                 } else if (leaf != NULL) {
-                    (*leaf)(p[n], arg);
+                    (*leaf)(idx, p[n], arg);
                 }
             }
         }
@@ -103,7 +107,7 @@ static void sa_free_node(void **p)
     OPENSSL_free(p);
 }
 
-static void sa_free_leaf(void *p, void *arg)
+static void sa_free_leaf(size_t n, void *p, void *arg)
 {
     OPENSSL_free(p);
 }
@@ -122,15 +126,15 @@ void OPENSSL_SA_free_leaves(OPENSSL_SA *sa)
 
 /* Wrap this in a structure to avoid compiler warnings */
 struct trampoline_st {
-    void (*func)(void *);
+    void (*func)(size_t, void *);
 };
 
-static void trampoline(void *l, void *arg)
+static void trampoline(size_t n, void *l, void *arg)
 {
-    ((const struct trampoline_st *)arg)->func(l);
+    ((const struct trampoline_st *)arg)->func(n, l);
 }
 
-void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(void *))
+void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(size_t, void *))
 {
     struct trampoline_st tramp;
 
@@ -139,8 +143,8 @@ void OPENSSL_SA_doall(const OPENSSL_SA *sa, void (*leaf)(void *))
         sa_doall(sa, NULL, &trampoline, &tramp);
 }
 
-void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa, void (*leaf)(void *, void *),
-                          void *arg)
+void OPENSSL_SA_doall_arg(const OPENSSL_SA *sa,
+                          void (*leaf)(size_t, void *, void *), void *arg)
 {
     if (sa != NULL)
         sa_doall(sa, NULL, leaf, arg);
diff --git a/doc/internal/man3/DEFINE_SPARSE_ARRAY_OF.pod b/doc/internal/man3/DEFINE_SPARSE_ARRAY_OF.pod
index 146f02d..099f7a6 100644
--- a/doc/internal/man3/DEFINE_SPARSE_ARRAY_OF.pod
+++ b/doc/internal/man3/DEFINE_SPARSE_ARRAY_OF.pod
@@ -20,8 +20,9 @@ ossl_sa_TYPE_doall_arg, ossl_sa_TYPE_get, ossl_sa_TYPE_set
  void ossl_sa_TYPE_free(const SPARSE_ARRAY_OF(TYPE) *sa);
  void ossl_sa_TYPE_free_leaves(const SPARSE_ARRAY_OF(TYPE) *sa);
  int ossl_sa_TYPE_num(const SPARSE_ARRAY_OF(TYPE) *sa);
- void ossl_sa_TYPE_doall(const OPENSSL_SA *sa, void (*leaf)(void *));
- void ossl_sa_TYPE_doall_arg(const OPENSSL_SA *sa, void (*leaf)(void *), void *arg);
+ void ossl_sa_TYPE_doall(const OPENSSL_SA *sa, void (*leaf)(size_t, void *));
+ void ossl_sa_TYPE_doall_arg(const OPENSSL_SA *sa,
+                             void (*leaf)(size_t, void *, void *), void *arg);
  TYPE *ossl_sa_TYPE_get(const SPARSE_ARRAY_OF(TYPE) *sa, size_t idx);
  int ossl_sa_TYPE_set(SPARSE_ARRAY_OF(TYPE) *sa, size_t idx, TYPE *value);
 
@@ -53,12 +54,17 @@ elements of B<sa>. After this call B<sa> is no longer valid.
 ossl_sa_TYPE_free_leaves() frees up the B<sa> structure and all of its
 elements.  After this call B<sa> is no longer valid.
 
-ossl_sa_TYPE_doall() calls the function B<leaf> for each element in B<sa> in
-ascending index order.
+ossl_sa_TYPE_doall() calls the function B<leaf> for each element in B<sa>
+in ascending index order. The index position, within the sparse array,
+of each item is passed as the first argument to the leaf function and a
+pointer to the associated value is is passed as the second argument.
+
+ossl_sa_TYPE_doall_arg() calls the function B<leaf> for each element in
+B<sa> in ascending index order. The index position, within the sparse
+array, of each item is passed as the first argument to the leaf function,
+a pointer to the associated value is passed as the second argument and
+the third argument is the user supplied B<arg>.
 
-ossl_sa_TYPE_doall_arg() calls the function B<leaf> for each element in B<sa>
-in ascending index order. The argument B<arg> is passed to each call of
-B<leaf>.
 
 =head1 NOTES
 
diff --git a/test/sparse_array_test.c b/test/sparse_array_test.c
index 295ccb0..fa57f3f 100644
--- a/test/sparse_array_test.c
+++ b/test/sparse_array_test.c
@@ -95,9 +95,104 @@ err:
     return res;
 }
 
+struct index_cases_st {
+    size_t n;
+    char *v;
+    int del;
+};
+
+struct doall_st {
+    SPARSE_ARRAY_OF(char) *sa;
+    size_t num_cases;
+    const struct index_cases_st *cases;
+    int res;
+    int all;
+};
+
+static void leaf_check_all(size_t n, char *value, void *arg)
+{
+    struct doall_st *doall_data = (struct doall_st *)arg;
+    const struct index_cases_st *cases = doall_data->cases;
+    size_t i;
+
+    doall_data->res = 0;
+    for (i = 0; i < doall_data->num_cases; i++)
+        if ((doall_data->all || !cases[i].del)
+            && n == cases[i].n && strcmp(value, cases[i].v) == 0) {
+            doall_data->res = 1;
+            return;
+        }
+    TEST_error("Index %zu with value %s not found", n, value);
+}
+
+static void leaf_delete(size_t n, char *value, void *arg)
+{
+    struct doall_st *doall_data = (struct doall_st *)arg;
+    const struct index_cases_st *cases = doall_data->cases;
+    size_t i;
+
+    doall_data->res = 0;
+    for (i = 0; i < doall_data->num_cases; i++)
+        if (n == cases[i].n && strcmp(value, cases[i].v) == 0) {
+            doall_data->res = 1;
+            ossl_sa_char_set(doall_data->sa, n, NULL);
+            return;
+        }
+    TEST_error("Index %zu with value %s not found", n, value);
+}
+
+static int test_sparse_array_doall(void)
+{
+    static const struct index_cases_st cases[] = {
+        { 22, "A", 1 }, { 1021, "b", 0 }, { 3, "c", 0 }, { INT_MAX, "d", 1 },
+        { (size_t)-1, "H", 0 }, { (size_t)-2, "i", 1 }, { 666666666, "s", 1 },
+        { 1234567890, "t", 0 },
+    };
+    struct doall_st doall_data;
+    size_t i;
+    SPARSE_ARRAY_OF(char) *sa = NULL;
+    int res = 0;
+
+    if (!TEST_ptr(sa = ossl_sa_char_new()))
+        goto err;
+    doall_data.num_cases = OSSL_NELEM(cases);
+    doall_data.cases = cases;
+    doall_data.all = 1;
+    doall_data.sa = NULL;
+    for (i = 0; i <  OSSL_NELEM(cases); i++)
+        if (!TEST_true(ossl_sa_char_set(sa, cases[i].n, cases[i].v))) {
+            TEST_note("failed at iteration %zu", i + 1);
+            goto err;
+    }
+    
+    ossl_sa_char_doall_arg(sa, &leaf_check_all, &doall_data);
+    if (doall_data.res == 0) {
+        TEST_info("while checking all elements");
+        goto err;
+    }
+    doall_data.all = 0;
+    doall_data.sa = sa;
+    ossl_sa_char_doall_arg(sa, &leaf_delete, &doall_data);
+    if (doall_data.res == 0) {
+        TEST_info("while deleting selected elements");
+        goto err;
+    }
+    ossl_sa_char_doall_arg(sa, &leaf_check_all, &doall_data);
+    if (doall_data.res == 0) {
+        TEST_info("while checking for deleted elements");
+        goto err;
+    }
+    res = 1;
+
+err:
+    ossl_sa_char_free(sa);
+    return res;
+}
+
 int setup_tests(void)
 {
     ADD_TEST(test_sparse_array);
     ADD_TEST(test_sparse_array_num);
+    ADD_TEST(test_sparse_array_doall);
     return 1;
 }