On Thu, Jan 8, 2026 at 9:47 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]> > --- > lib/automake.mk | 2 + > lib/ovn-util.h | 15 +++ > lib/sparse-array.c | 102 +++++++++++++++++++ > lib/sparse-array.h | 54 ++++++++++ > tests/automake.mk | 1 + > tests/ovn.at | 5 + > tests/test-sparse-array.c | 206 ++++++++++++++++++++++++++++++++++++++ > 7 files changed, 385 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/ovn-util.h b/lib/ovn-util.h > index daff01995..3b206e6f6 100644 > --- a/lib/ovn-util.h > +++ b/lib/ovn-util.h > @@ -529,6 +529,21 @@ 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]) > + + (BITMAP_ULONG_BITS * 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 > new file mode 100644 > index 000000000..cab30158a > --- /dev/null > +++ b/lib/sparse-array.c > @@ -0,0 +1,102 @@ > +/* 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), > + .capacity = capacity, > + }; > + 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); > + array->buffer[idx] = CONST_CAST(void *, obj); > + dynamic_bitmap_set1(&array->bitmap, idx); > + 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->capacity || > + !dynamic_bitmap_is_set(&array->bitmap, idx)) { > + return NULL; > + } > + > + void *ret = sparse_array_get(array, idx); > + dynamic_bitmap_set0(&array->bitmap, idx); > + > + 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->capacity || > + !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..047b2f304 > --- /dev/null > +++ b/lib/sparse-array.h > @@ -0,0 +1,54 @@ > +/* 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 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); > + > +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 > + */ > +#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..3948ba884 > --- /dev/null > +++ b/tests/test-sparse-array.c > @@ -0,0 +1,206 @@ > +/* 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.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.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)); > + } > + > + /* 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.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.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); > + > + /* 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.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); > + ovs_assert(under_test == item_three); > + 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); > + > + /* 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.bitmap.n_elems == n_elems); > + ovs_assert(sparse_array_len(&test_array) == (n_elems ? 3 : 0)); > + test_index++; > + } > + ovs_assert(test_array.bitmap.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 > > Looks good to me, thanks. Acked-by: Ales Musil <[email protected]> _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
