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]); } 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
