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/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 *)); + 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); + array->n_elems--; + + 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; + /* The length of buffer space currently used by the sparse array. */ + size_t len; + /* 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
