From 008b4ff92f785cf3808df26ac5b23f25a691b23c Mon Sep 17 00:00:00 2001 From: Pauli Date: Thu, 14 Feb 2019 08:13:58 +1000 Subject: [PATCH] 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 (Merged from https://github.com/openssl/openssl/pull/8229) --- crypto/include/internal/sparse_array.h | 15 ++-- crypto/sparse_array.c | 22 +++-- doc/internal/man3/DEFINE_SPARSE_ARRAY_OF.pod | 20 +++-- test/sparse_array_test.c | 95 ++++++++++++++++++++ 4 files changed, 129 insertions(+), 23 deletions(-) diff --git a/crypto/include/internal/sparse_array.h b/crypto/include/internal/sparse_array.h index bf0a9966af..839fcedde4 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 8c9efed0eb..796d35e349 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 146f02dd2f..099f7a69e6 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. After this call B is no longer valid. ossl_sa_TYPE_free_leaves() frees up the B structure and all of its elements. After this call B is no longer valid. -ossl_sa_TYPE_doall() calls the function B for each element in B in -ascending index order. +ossl_sa_TYPE_doall() calls the function B for each element in B +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 for each element in +B 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. -ossl_sa_TYPE_doall_arg() calls the function B for each element in B -in ascending index order. The argument B is passed to each call of -B. =head1 NOTES diff --git a/test/sparse_array_test.c b/test/sparse_array_test.c index 295ccb0782..fa57f3fc0e 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; } -- 2.34.1