Hi Ales.
On Wed, Jan 7, 2026 at 6:02 AM Ales Musil <[email protected]> wrote:
>
>
>
> On Tue, Dec 16, 2025 at 7:44 PM Mark Michelson via dev
> <[email protected]> wrote:
>>
>> This operates as an alternate dynamic array type from vector.
>>
>> Vectors are useful for allocating a contiguous block of elements.
>> Inserting an element will cause other elements to shift, resulting in a
>> still-contiguous block of elements. Removing an element causes elements
>> above it to be shifted down to fill in the gap. Attempting to insert an
>> element past the bounds of the array will not work.
>>
>> Sparse arrays serve a different purpose. Their goal is to ensure that
>> elements maintain their index as long as they are in the array.
>> Inserting an element causes it to take the lowest free slot in the
>> array. If an element is inserted at a specific index, then it replaces
>> the element that was there previously. If an element is removed, it
>> results in a hole in the array. If you attempt to add an element past
>> the bounds of the array, then the array expands to allow it.
>>
>> This is all technically possible with vectors, too. There is code in
>> northd.c that uses vector_get() cleverly to avoid outright removal of
>> elements. However, that completely breaks any attempted traversal of the
>> vector, and the length reported by the vector is no longer correct. In
>> my personal opinion, this is a by-the-book definition of a "code smell".
>>
>> Commits following this one will start making use of sparse array.
>>
>> Signed-off-by: Mark Michelson <[email protected]>
>> ---
>
>
>
> Hi Mark,
>
> thank you for the patch, I have a couple of comment down below.
>
>>
>> lib/automake.mk | 2 +
>> lib/sparse-array.c | 110 ++++++++++++++++++++
>> lib/sparse-array.h | 51 ++++++++++
>> tests/automake.mk | 1 +
>> tests/ovn.at | 5 +
>> tests/test-sparse-array.c | 207 ++++++++++++++++++++++++++++++++++++++
>> 6 files changed, 376 insertions(+)
>> create mode 100644 lib/sparse-array.c
>> create mode 100644 lib/sparse-array.h
>> create mode 100644 tests/test-sparse-array.c
>>
>> diff --git a/lib/automake.mk b/lib/automake.mk
>> index 3924c631c..25741cbdf 100644
>> --- a/lib/automake.mk
>> +++ b/lib/automake.mk
>> @@ -48,6 +48,8 @@ lib_libovn_la_SOURCES = \
>> lib/inc-proc-eng.h \
>> lib/lb.c \
>> lib/lb.h \
>> + lib/sparse-array.c \
>> + lib/sparse-array.h \
>> lib/stopwatch-names.h \
>> lib/vec.c \
>> lib/vec.h \
>> diff --git a/lib/sparse-array.c b/lib/sparse-array.c
>> new file mode 100644
>> index 000000000..bbf7a11b5
>> --- /dev/null
>> +++ b/lib/sparse-array.c
>> @@ -0,0 +1,110 @@
>> +/* Copyright (c) 2025, Red Hat, Inc.
>> + *
>> + * Licensed under the Apache License, Version 2.0 (the "License");
>> + * you may not use this file except in compliance with the License.
>> + * You may obtain a copy of the License at:
>> + *
>> + * http://www.apache.org/licenses/LICENSE-2.0
>> + *
>> + * Unless required by applicable law or agreed to in writing, software
>> + * distributed under the License is distributed on an "AS IS" BASIS,
>> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
>> + * See the License for the specific language governing permissions and
>> + * limitations under the License.
>> + */
>> +
>> +#include <config.h>
>> +
>> +#include "sparse-array.h"
>> +
>> +void
>> +sparse_array_init(struct sparse_array *array, size_t capacity)
>> +{
>> + *array = (struct sparse_array) {
>> + .buffer = xmalloc(sizeof (void *) * capacity),
>>
>> + .n_elems = 0,
>> + .capacity = capacity,
>> + .len = 0,
>> + };
>> + dynamic_bitmap_alloc(&array->bitmap, capacity);
>> +}
>> +
>> +void
>> +sparse_array_destroy(struct sparse_array *array)
>> +{
>> + free(array->buffer);
>> + dynamic_bitmap_free(&array->bitmap);
>> +}
>> +
>> +static void
>> +sparse_array_expand(struct sparse_array *array, size_t target)
>> +{
>> + if (target <= array->capacity) {
>> + return;
>> + }
>> +
>> + size_t new_capacity =
>> + target <= array->capacity * 2 ?
>> + array->capacity * 2 :
>> + target;
>> + array->buffer = xrealloc(array->buffer, new_capacity * sizeof (void *));
>> + array->capacity = new_capacity;
>> + dynamic_bitmap_realloc(&array->bitmap, new_capacity);
>> + ovs_assert(array->capacity == array->bitmap.capacity);
>> +}
>> +
>> +static size_t
>> +sparse_array_add__(struct sparse_array *array, const void *obj, size_t idx)
>> +{
>> + sparse_array_expand(array, idx + 1);
>> + uint8_t *dst = (uint8_t *) array->buffer + idx * sizeof(void *);
>> + memcpy(dst, obj, sizeof (void *));
>
>
> Since we are dealing with array of void pointer we could just do
> array->buffer[idx] = obj;
>
>>
>> + dynamic_bitmap_set1(&array->bitmap, idx);
>> + array->n_elems++;
>> + if (idx >= array->len) {
>> + array->len = idx + 1;
>> + }
>> + return idx;
>> +}
>> +
>> +size_t
>> +sparse_array_add(struct sparse_array *array, const void *obj)
>> +{
>> + size_t idx = dynamic_bitmap_scan(&array->bitmap, false, 0);
>>
>> + return sparse_array_add__(array, obj, idx);
>> +}
>> +
>> +void *
>> +sparse_array_remove(struct sparse_array *array, size_t idx)
>> +{
>> + if (idx >= array->len ||
>> + !dynamic_bitmap_is_set(&array->bitmap, idx)) {
>> + return NULL;
>> + }
>> +
>> + void *ret = sparse_array_get(array, idx);
>> + dynamic_bitmap_set0(&array->bitmap, idx);
>
>
> nit: We should also set the element to NULL.
>
>> + array->n_elems--;
>
>
> The array->len is never re-assigned here, which is not right IMO.
> See below for a potential solution.
>
>> +
>> + return ret;
>> +}
>> +
>> +void *
>> +sparse_array_add_at(struct sparse_array *array, const void *obj, size_t idx)
>> +{
>> + void *ret;
>> + ret = sparse_array_remove(array, idx);
>> + sparse_array_add__(array, obj, idx);
>> + return ret;
>> +}
>> +
>> +void *
>> +sparse_array_get(const struct sparse_array *array, size_t idx)
>> +{
>> + if (idx >= array->len ||
>> + !dynamic_bitmap_is_set(&array->bitmap, idx)) {
>> + return NULL;
>> + }
>> +
>> + return array->buffer[idx];
>> +}
>> diff --git a/lib/sparse-array.h b/lib/sparse-array.h
>> new file mode 100644
>> index 000000000..931c0d609
>> --- /dev/null
>> +++ b/lib/sparse-array.h
>> @@ -0,0 +1,51 @@
>> +/* Copyright (c) 2025, Red Hat, Inc.
>> + *
>> + * Licensed under the Apache License, Version 2.0 (the "License");
>> + * you may not use this file except in compliance with the License.
>> + * You may obtain a copy of the License at:
>> + *
>> + * http://www.apache.org/licenses/LICENSE-2.0
>> + *
>> + * Unless required by applicable law or agreed to in writing, software
>> + * distributed under the License is distributed on an "AS IS" BASIS,
>> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
>> + * See the License for the specific language governing permissions and
>> + * limitations under the License.
>> + */
>> +
>> +#ifndef SPARSE_ARRAY_H
>> +#define SPARSE_ARRAY_H
>> +
>> +#include <stddef.h>
>> +#include "ovn-util.h"
>> +
>> +struct sparse_array {
>> + struct dynamic_bitmap bitmap;
>> + void **buffer;
>> + /* The number of non-NULL elements in the buffer. */
>> + size_t n_elems;
>
>
> Seems like n_elems is used only internally, but it is also tracked in
> the dynamic_bitmap, IMO it would be better to use the dynamic_bitmap
> n_elems if we ever need them.
>
>>
>> + /* The length of buffer space currently used by the sparse array. */
>> + size_t len;
>
>
> As I have stated above the len is not properly reflected all the time,
> I was thinking a little bit and I think I came up with a solution.
>
> We add new helper for dynamic_bitmap:
> static inline ssize_t
> dynamic_bitmap_last_set(const struct dynamic_bitmap *db)
> {
> for(ssize_t i = bitmap_n_longs(db->capacity) - 1; i >= 0; i--) {
> if (!db->map[i]) {
> continue;
> }
>
> return (BITMAP_ULONG_BITS - 1) - raw_clz64(db->map[i]);
This unfortunately has an error in that it tops out at 63. So if the
bitmap has more than one unsigned long, the reported index is off by
64. Tests that add more than 64 logical datapaths were crashing. I
fixed this by changing the above line to:
return (BITMAP_ULONG_BITS - 1) - raw_clz64(db->map[i]) +
(BITMAP_ULONG_BITS * i);
This results in the accurate length being reported.
Aside from this, I integrated all suggestions from you in this patch
(plus the other smaller suggestions in later patches) and posted v2 of
the series. I did not add your ACK to the later patches since they
hinge on the sparse array changes being approved.
> }
>
> return -1;
> }
>
> And then helper for sparse_array as follows:
>
> static inline size_t
> sparse_array_len(const struct sparse_array *array)
> {
> ssize_t idx = dynamic_bitmap_last_set(&array->bitmap);
> return idx > -1 ? idx + 1 : 0;
> }
>
>>
>> + /* The memory allocated for the buffer. */
>> + size_t capacity;
>> +};
>> +
>> +void sparse_array_init(struct sparse_array *, size_t capacity);
>> +void sparse_array_destroy(struct sparse_array *);
>> +size_t sparse_array_add(struct sparse_array *, const void *obj);
>> +void *sparse_array_remove(struct sparse_array *, size_t index);
>> +void *sparse_array_add_at(struct sparse_array *, const void *obj,
>> + size_t index);
>> +void *sparse_array_get(const struct sparse_array *, size_t index);
>> +
>> +/* It is safe to destroy array members during traversal, so there
>> + * is no need for a _SAFE variant
>> + */
>> +#define SPARSE_ARRAY_FOR_EACH(ARRAY, MEMBER) \
>> + for (size_t ITER_VAR(IDX) = \
>> + dynamic_bitmap_scan(&(ARRAY)->bitmap, true, 0); \
>> + (MEMBER = sparse_array_get((ARRAY), ITER_VAR(IDX))) != NULL; \
>> + ITER_VAR(IDX) = \
>> + dynamic_bitmap_scan(&(ARRAY)->bitmap, true, ITER_VAR(IDX) +
>> 1)) \
>> +
>> +#endif /* SPARSE_ARRAY_H */
>> diff --git a/tests/automake.mk b/tests/automake.mk
>> index b037a3634..c8047371b 100644
>> --- a/tests/automake.mk
>> +++ b/tests/automake.mk
>> @@ -288,6 +288,7 @@ tests_ovstest_SOURCES = \
>> tests/test-utils.c \
>> tests/test-utils.h \
>> tests/test-ovn.c \
>> + tests/test-sparse-array.c \
>> tests/test-vector.c \
>> controller/test-lflow-cache.c \
>> controller/test-vif-plug.c \
>> diff --git a/tests/ovn.at b/tests/ovn.at
>> index 58127f0d3..697c97fe2 100644
>> --- a/tests/ovn.at
>> +++ b/tests/ovn.at
>> @@ -2406,6 +2406,11 @@ check ovstest test-vector clone
>> check ovstest test-vector pointers
>> AT_CLEANUP
>>
>> +AT_SETUP([Sparse array operations])
>> +check ovstest test-sparse-array add
>> +check ovstest test-sparse-array remove-replace
>> +AT_CLEANUP
>> +
>> AT_BANNER([OVN end-to-end tests])
>>
>> OVN_FOR_EACH_NORTHD([
>> diff --git a/tests/test-sparse-array.c b/tests/test-sparse-array.c
>> new file mode 100644
>> index 000000000..1f9196c60
>> --- /dev/null
>> +++ b/tests/test-sparse-array.c
>> @@ -0,0 +1,207 @@
>> +/* Copyright (c) 2025, Red Hat, Inc.
>> + *
>> + * Licensed under the Apache License, Version 2.0 (the "License");
>> + * you may not use this file except in compliance with the License.
>> + * You may obtain a copy of the License at:
>> + *
>> + * http://www.apache.org/licenses/LICENSE-2.0
>> + *
>> + * Unless required by applicable law or agreed to in writing, software
>> + * distributed under the License is distributed on an "AS IS" BASIS,
>> + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
>> + * See the License for the specific language governing permissions and
>> + * limitations under the License.
>> + */
>> +
>> +#include <config.h>
>> +
>> +#include "lib/sparse-array.h"
>> +#include "tests/ovstest.h"
>> +
>> +struct array_elem {
>> + int int_member;
>> + const char * str;
>> +};
>> +
>> +static void
>> +test_add(struct ovs_cmdl_context *ctx OVS_UNUSED)
>> +{
>> + const struct tester {
>> + struct array_elem elem;
>> + size_t index;
>> + bool add_with_index;
>> + size_t expected_capacity;
>> + } test_vals[] = {
>> + /* The first 5 elements are added to the first available index. */
>> + {{0, "zero" }, 0, false, 1},
>> + {{1, "one" }, 1, false, 2},
>> + {{2, "two" }, 2, false, 4},
>> + {{3, "three"}, 3, false, 4},
>> + {{4, "four" }, 4, false, 8},
>> + /* The final two elements are added with custom indexes. */
>> + {{5, "five" }, 15, true, 16},
>> + {{6, "six" }, 40, true, 41},
>> + };
>> + const struct tester *iter;
>> + const struct array_elem *under_test;
>> +
>> + struct sparse_array test_array;
>> + sparse_array_init(&test_array, 0);
>> + ovs_assert(test_array.n_elems == 0);
>> + ovs_assert(test_array.capacity == 0);
>> +
>> + for (size_t i = 0; i < ARRAY_SIZE(test_vals); i++) {
>> + size_t index;
>> + iter = &test_vals[i];
>> + under_test = &iter->elem;
>> + if (iter->add_with_index) {
>> + index = iter->index;
>> + sparse_array_add_at(&test_array, &under_test, index);
>> + } else {
>> + index = sparse_array_add(&test_array, &under_test);
>> + }
>> +
>> + ovs_assert(index == iter->index);
>> + ovs_assert(test_array.capacity == iter->expected_capacity);
>> + ovs_assert(test_array.n_elems == (i + 1));
>> + ovs_assert(test_array.len == (test_vals[i].index + 1));
>> + under_test = sparse_array_get(&test_array, index);
>> + ovs_assert(under_test->int_member == iter->elem.int_member);
>> + ovs_assert(!strcmp(under_test->str, iter->elem.str));
>> + }
>> +
>> + /* Ensure iteration with a gap succeeds */
>> + size_t tester_index = 0;
>> + SPARSE_ARRAY_FOR_EACH (&test_array, under_test) {
>> + const struct array_elem *expected = &test_vals[tester_index].elem;
>> + ovs_assert(under_test->int_member == expected->int_member);
>> + ovs_assert(!strcmp(under_test->str, expected->str));
>> + tester_index++;
>> + }
>> + sparse_array_destroy(&test_array);
>> +}
>> +
>> +static struct array_elem *
>> +allocate_array_elem(int int_member, const char * str)
>> +{
>> + struct array_elem *elem = xmalloc(sizeof *elem);
>> + *elem = (struct array_elem) {
>> + .int_member = int_member,
>> + .str = str,
>> + };
>> + return elem;
>> +}
>> +
>> +static void
>> +test_remove_replace(struct ovs_cmdl_context *ctx OVS_UNUSED)
>> +{
>> + struct sparse_array test_array;
>> +
>> + struct array_elem *item_one = allocate_array_elem(1, "one");
>> + struct array_elem *item_two = allocate_array_elem(2, "two");
>> + struct array_elem *item_three = allocate_array_elem(3, "three");
>> + struct array_elem *item_four = allocate_array_elem(4, "four");
>> + struct array_elem *item_five = allocate_array_elem(5, "five");
>> + struct array_elem *under_test;
>> +
>> + sparse_array_init(&test_array, 0);
>> +
>> + /* The add() test already ensured basic initialization and addition
>> + * works, so we will only test values after removal or replacement.
>> + */
>> + sparse_array_add(&test_array, &item_one);
>> + sparse_array_add(&test_array, &item_two);
>> + sparse_array_add(&test_array, &item_three);
>> +
>> + ovs_assert(test_array.n_elems == 3);
>> + ovs_assert(test_array.len == 3);
>> + ovs_assert(sparse_array_get(&test_array, 0) == item_one);
>> + ovs_assert(sparse_array_get(&test_array, 1) == item_two);
>> + ovs_assert(sparse_array_get(&test_array, 2) == item_three);
>> +
>> + under_test = sparse_array_remove(&test_array, 1);
>> + ovs_assert(under_test == item_two);
>> + ovs_assert(test_array.n_elems == 2);
>> + ovs_assert(test_array.len == 3);
>> + ovs_assert(sparse_array_get(&test_array, 0) == item_one);
>> + ovs_assert(sparse_array_get(&test_array, 1) == NULL);
>> + ovs_assert(sparse_array_get(&test_array, 2) == item_three);
>> +
>> + /* The sparse array has a hole in it. The next item we add should
>> + * fill in the hole.
>> + */
>> + sparse_array_add(&test_array, &item_four);
>> + ovs_assert(test_array.n_elems == 3);
>> + ovs_assert(test_array.len == 3);
>> + ovs_assert(sparse_array_get(&test_array, 0) == item_one);
>> + ovs_assert(sparse_array_get(&test_array, 1) == item_four);
>> + ovs_assert(sparse_array_get(&test_array, 2) == item_three);
>> +
>> + /* Replace the item at index 2. */
>> + under_test = sparse_array_add_at(&test_array, &item_five, 2);
>> + ovs_assert(under_test == item_three);
>> + ovs_assert(test_array.n_elems == 3);
>> + ovs_assert(test_array.len == 3);
>> + ovs_assert(sparse_array_get(&test_array, 0) == item_one);
>> + ovs_assert(sparse_array_get(&test_array, 1) == item_four);
>> + ovs_assert(sparse_array_get(&test_array, 2) == item_five);
>> +
>> + /* Test out of bounds retrieval/removal. */
>> +
>> + /* Ensure we don't have off-by-one errors. */
>> + under_test = sparse_array_get(&test_array, 3);
>> + ovs_assert(under_test == NULL);
>> + /* And test something that is beyond the array capacity. */
>> + under_test = sparse_array_get(&test_array, 100);
>> + ovs_assert(under_test == NULL);
>> +
>> + /* Test off-by-one again. */
>> + under_test = sparse_array_get(&test_array, 3);
>> + ovs_assert(under_test == NULL);
>> + /* Test a big value again. */
>> + under_test = sparse_array_get(&test_array, 100);
>> + ovs_assert(under_test == NULL);
>> +
>> + struct array_elem *elems[] = {
>> + item_one,
>> + item_four,
>> + item_five,
>> + };
>> + size_t test_index = 0;
>> + size_t n_elems = 3;
>> + SPARSE_ARRAY_FOR_EACH (&test_array, under_test) {
>> + struct array_elem *removed = sparse_array_remove(&test_array,
>> + test_index);
>> + n_elems--;
>> + ovs_assert(removed == under_test);
>> + ovs_assert(under_test == elems[test_index]);
>> + ovs_assert(test_array.n_elems == n_elems);
>> + ovs_assert(test_array.len == 3);
>> + test_index++;
>> + }
>> + ovs_assert(test_array.n_elems == 0);
>> +
>> + sparse_array_destroy(&test_array);
>> + free(item_one);
>> + free(item_two);
>> + free(item_three);
>> + free(item_four);
>> + free(item_five);
>> +}
>> +
>> +static void
>> +test_sparse_array_main(int argc OVS_UNUSED, char *argv[] OVS_UNUSED)
>> +{
>> + ovn_set_program_name(argv[0]);
>> + static const struct ovs_cmdl_command commands[] = {
>> + {"add", NULL, 0, 0, test_add, OVS_RO},
>> + {"remove-replace", NULL, 0, 0, test_remove_replace, OVS_RO},
>> + {NULL, NULL, 0, 0, NULL, OVS_RO},
>> + };
>> + struct ovs_cmdl_context ctx;
>> + ctx.argc = argc - 1;
>> + ctx.argv = argv + 1;
>> + ovs_cmdl_run_command(&ctx, commands);
>> +}
>> +
>> +OVSTEST_REGISTER("test-sparse-array", test_sparse_array_main);
>> --
>> 2.51.1
>>
>> _______________________________________________
>> dev mailing list
>> [email protected]
>> https://mail.openvswitch.org/mailman/listinfo/ovs-dev
>>
>
> If I may suggest the following diff:
>
> diff --git a/lib/ovn-util.h b/lib/ovn-util.h
> index daff01995..0165b43ed 100644
> --- a/lib/ovn-util.h
> +++ b/lib/ovn-util.h
> @@ -529,6 +529,20 @@ ovn_bitmap_realloc(unsigned long *bitmap, size_t
> n_bits_old,
> return bitmap;
> }
>
> +static inline ssize_t
> +dynamic_bitmap_last_set(const struct dynamic_bitmap *db)
> +{
> + for(ssize_t i = bitmap_n_longs(db->capacity) - 1; i >= 0; i--) {
> + if (!db->map[i]) {
> + continue;
> + }
> +
> + return (BITMAP_ULONG_BITS - 1) - raw_clz64(db->map[i]);
> + }
> +
> + return -1;
> +}
> +
> static inline void
> dynamic_bitmap_alloc(struct dynamic_bitmap *db, size_t n_elems)
> {
> diff --git a/lib/sparse-array.c b/lib/sparse-array.c
> index 95f82fbc8..1ac8547fe 100644
> --- a/lib/sparse-array.c
> +++ b/lib/sparse-array.c
> @@ -17,8 +17,6 @@
>
> #include "sparse-array.h"
>
> -#include <stdlib.h>
> -
> void
> sparse_array_init(struct sparse_array *array, size_t capacity)
> {
> @@ -57,11 +55,9 @@ static size_t
> sparse_array_add__(struct sparse_array *array, const void *obj, size_t idx)
> {
> sparse_array_expand(array, idx + 1);
> - array->buffer[idx] = obj;
> + array->buffer[idx] = CONST_CAST(void *, obj);
> dynamic_bitmap_set1(&array->bitmap, idx);
> - if (idx >= array->len) {
> - array->len = idx + 1;
> - }
> +
> return idx;
> }
>
> @@ -75,7 +71,7 @@ sparse_array_add(struct sparse_array *array, const void
> *obj)
> void *
> sparse_array_remove(struct sparse_array *array, size_t idx)
> {
> - if (idx >= array->len ||
> + if (idx >= array->capacity ||
> !dynamic_bitmap_is_set(&array->bitmap, idx)) {
> return NULL;
> }
> @@ -99,7 +95,7 @@ sparse_array_add_at(struct sparse_array *array, const void
> *obj, size_t idx)
> void *
> sparse_array_get(const struct sparse_array *array, size_t idx)
> {
> - if (idx >= array->len ||
> + if (idx >= array->capacity ||
> !dynamic_bitmap_is_set(&array->bitmap, idx)) {
> return NULL;
> }
> diff --git a/lib/sparse-array.h b/lib/sparse-array.h
> index 931c0d609..047b2f304 100644
> --- a/lib/sparse-array.h
> +++ b/lib/sparse-array.h
> @@ -22,10 +22,6 @@
> struct sparse_array {
> struct dynamic_bitmap bitmap;
> void **buffer;
> - /* The number of non-NULL elements in the buffer. */
> - size_t n_elems;
> - /* The length of buffer space currently used by the sparse array. */
> - size_t len;
> /* The memory allocated for the buffer. */
> size_t capacity;
> };
> @@ -38,6 +34,13 @@ void *sparse_array_add_at(struct sparse_array *, const
> void *obj,
> size_t index);
> void *sparse_array_get(const struct sparse_array *, size_t index);
>
> +static inline size_t
> +sparse_array_len(const struct sparse_array *array)
> +{
> + ssize_t idx = dynamic_bitmap_last_set(&array->bitmap);
> + return idx > -1 ? idx + 1 : 0;
> +}
> +
> /* It is safe to destroy array members during traversal, so there
> * is no need for a _SAFE variant
> */
> diff --git a/tests/test-sparse-array.c b/tests/test-sparse-array.c
> index 1f9196c60..3948ba884 100644
> --- a/tests/test-sparse-array.c
> +++ b/tests/test-sparse-array.c
> @@ -47,7 +47,6 @@ test_add(struct ovs_cmdl_context *ctx OVS_UNUSED)
>
> struct sparse_array test_array;
> sparse_array_init(&test_array, 0);
> - ovs_assert(test_array.n_elems == 0);
> ovs_assert(test_array.capacity == 0);
>
> for (size_t i = 0; i < ARRAY_SIZE(test_vals); i++) {
> @@ -56,15 +55,15 @@ test_add(struct ovs_cmdl_context *ctx OVS_UNUSED)
> under_test = &iter->elem;
> if (iter->add_with_index) {
> index = iter->index;
> - sparse_array_add_at(&test_array, &under_test, index);
> + sparse_array_add_at(&test_array, under_test, index);
> } else {
> - index = sparse_array_add(&test_array, &under_test);
> + index = sparse_array_add(&test_array, under_test);
> }
>
> ovs_assert(index == iter->index);
> ovs_assert(test_array.capacity == iter->expected_capacity);
> - ovs_assert(test_array.n_elems == (i + 1));
> - ovs_assert(test_array.len == (test_vals[i].index + 1));
> + ovs_assert(test_array.bitmap.n_elems == (i + 1));
> + ovs_assert(sparse_array_len(&test_array) == (test_vals[i].index +
> 1));
> under_test = sparse_array_get(&test_array, index);
> ovs_assert(under_test->int_member == iter->elem.int_member);
> ovs_assert(!strcmp(under_test->str, iter->elem.str));
> @@ -109,20 +108,20 @@ test_remove_replace(struct ovs_cmdl_context *ctx
> OVS_UNUSED)
> /* The add() test already ensured basic initialization and addition
> * works, so we will only test values after removal or replacement.
> */
> - sparse_array_add(&test_array, &item_one);
> - sparse_array_add(&test_array, &item_two);
> - sparse_array_add(&test_array, &item_three);
> + sparse_array_add(&test_array, item_one);
> + sparse_array_add(&test_array, item_two);
> + sparse_array_add(&test_array, item_three);
>
> - ovs_assert(test_array.n_elems == 3);
> - ovs_assert(test_array.len == 3);
> + ovs_assert(test_array.bitmap.n_elems == 3);
> + ovs_assert(sparse_array_len(&test_array) == 3);
> ovs_assert(sparse_array_get(&test_array, 0) == item_one);
> ovs_assert(sparse_array_get(&test_array, 1) == item_two);
> ovs_assert(sparse_array_get(&test_array, 2) == item_three);
>
> under_test = sparse_array_remove(&test_array, 1);
> ovs_assert(under_test == item_two);
> - ovs_assert(test_array.n_elems == 2);
> - ovs_assert(test_array.len == 3);
> + ovs_assert(test_array.bitmap.n_elems == 2);
> + ovs_assert(sparse_array_len(&test_array) == 3);
> ovs_assert(sparse_array_get(&test_array, 0) == item_one);
> ovs_assert(sparse_array_get(&test_array, 1) == NULL);
> ovs_assert(sparse_array_get(&test_array, 2) == item_three);
> @@ -130,18 +129,18 @@ test_remove_replace(struct ovs_cmdl_context *ctx
> OVS_UNUSED)
> /* The sparse array has a hole in it. The next item we add should
> * fill in the hole.
> */
> - sparse_array_add(&test_array, &item_four);
> - ovs_assert(test_array.n_elems == 3);
> - ovs_assert(test_array.len == 3);
> + sparse_array_add(&test_array, item_four);
> + ovs_assert(test_array.bitmap.n_elems == 3);
> + ovs_assert(sparse_array_len(&test_array) == 3);
> ovs_assert(sparse_array_get(&test_array, 0) == item_one);
> ovs_assert(sparse_array_get(&test_array, 1) == item_four);
> ovs_assert(sparse_array_get(&test_array, 2) == item_three);
>
> /* Replace the item at index 2. */
> - under_test = sparse_array_add_at(&test_array, &item_five, 2);
> + under_test = sparse_array_add_at(&test_array, item_five, 2);
> ovs_assert(under_test == item_three);
> - ovs_assert(test_array.n_elems == 3);
> - ovs_assert(test_array.len == 3);
> + ovs_assert(test_array.bitmap.n_elems == 3);
> + ovs_assert(sparse_array_len(&test_array) == 3);
> ovs_assert(sparse_array_get(&test_array, 0) == item_one);
> ovs_assert(sparse_array_get(&test_array, 1) == item_four);
> ovs_assert(sparse_array_get(&test_array, 2) == item_five);
> @@ -175,11 +174,11 @@ test_remove_replace(struct ovs_cmdl_context *ctx
> OVS_UNUSED)
> n_elems--;
> ovs_assert(removed == under_test);
> ovs_assert(under_test == elems[test_index]);
> - ovs_assert(test_array.n_elems == n_elems);
> - ovs_assert(test_array.len == 3);
> + ovs_assert(test_array.bitmap.n_elems == n_elems);
> + ovs_assert(sparse_array_len(&test_array) == (n_elems ? 3 : 0));
> test_index++;
> }
> - ovs_assert(test_array.n_elems == 0);
> + ovs_assert(test_array.bitmap.n_elems == 0);
>
> sparse_array_destroy(&test_array);
> free(item_one);
>
> Regards,
> Ales
>
_______________________________________________
dev mailing list
[email protected]
https://mail.openvswitch.org/mailman/listinfo/ovs-dev
