On Thu, Jan 8, 2026 at 9:51 PM Mark Michelson <[email protected]> wrote:
> 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. > Ah whoops, yeah that makes more sense :) > > 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. > Thanks, I will take a look at v2 later today. > > > } > > > > 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
