From 03ee129cb9de10e4429ad9990d8d5746907ab355 Mon Sep 17 00:00:00 2001 From: Christian Hopps Date: Fri, 23 Jun 2023 14:34:47 -0400 Subject: [PATCH] lib: add dynamic array type Signed-off-by: Christian Hopps (cherry picked from commit e6e0c5bd25599c76bd05db3c2e3f32f6d3fe47bb) # Conflicts: # .clang-format --- .clang-format | 2 + lib/darr.c | 114 +++++++++++++ lib/darr.h | 363 ++++++++++++++++++++++++++++++++++++++++++ lib/subdir.am | 2 + tests/lib/subdir.am | 7 + tests/lib/test_darr.c | 279 ++++++++++++++++++++++++++++++++ 6 files changed, 767 insertions(+) create mode 100644 lib/darr.c create mode 100644 lib/darr.h create mode 100644 tests/lib/test_darr.c diff --git a/.clang-format b/.clang-format index 1b18323348..3ba262994b 100644 --- a/.clang-format +++ b/.clang-format @@ -25,6 +25,8 @@ CommentPragmas: '\$(FRR|clippy)' ContinuationIndentWidth: 8 ForEachMacros: # lib + - darr_foreach_p + - darr_foreach_i - frr_each - frr_each_safe - frr_each_from diff --git a/lib/darr.c b/lib/darr.c new file mode 100644 index 0000000000..2c8b7b8778 --- /dev/null +++ b/lib/darr.c @@ -0,0 +1,114 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * June 23 2023, Christian Hopps + * + * Copyright (c) 2023, LabN Consulting, L.L.C. + * + */ +#include +#include "darr.h" + +void __dar_resize(void **a, uint count, size_t esize); + +static uint _msb(uint count) +{ + uint bit = 0; + int msb = 0; + + while (count) { + if (count & 1) + msb = bit; + count >>= 1; + bit += 1; + } + return msb; +} + +static uint darr_next_count(uint count, size_t esize) +{ + uint ncount; + + if (esize > sizeof(long long) && count == 1) + /* treat like a pointer */ + ncount = 1; + else { + uint msb = _msb(count); + + ncount = 1ull << msb; + /* if the users count wasn't a pow2 make it the next pow2. */ + if (ncount != count) { + assert(ncount < count); + ncount <<= 1; + if (esize < sizeof(long long) && ncount < 8) + ncount = 8; + } + } + return ncount; +} + +static size_t darr_size(uint count, size_t esize) +{ + return count * esize + sizeof(struct darr_metadata); +} + +void *__darr_resize(void *a, uint count, size_t esize) +{ + uint ncount = darr_next_count(count, esize); + size_t osz = (a == NULL) ? 0 : darr_size(darr_cap(a), esize); + size_t sz = darr_size(ncount, esize); + struct darr_metadata *dm = realloc(a ? _darr_meta(a) : NULL, sz); + /* do *not* use a */ + + assert(dm); + if (sz > osz) + memset((char *)dm + osz, 0, sz - osz); + + dm->cap = ncount; + + return (void *)(dm + 1); +} + + +void *__darr_insert_n(void *a, uint at, uint count, size_t esize, bool zero) +{ + + struct darr_metadata *dm; + uint olen, nlen; + + if (!a) + a = __darr_resize(NULL, at + count, esize); + dm = (struct darr_metadata *)a - 1; + olen = dm->len; + + // at == 1 + // count == 100 + // olen == 2 + + /* see if the user is expanding first using `at` */ + if (at >= olen) + nlen = at + count; + else + nlen = olen + count; + + if (nlen > dm->cap) { + a = __darr_resize(a, nlen, esize); + dm = (struct darr_metadata *)a - 1; + } + +#define _a_at(i) ((char *)a + ((i)*esize)) + if (at < olen) + memmove(_a_at(at + count), _a_at(at), esize * (olen - at)); + + dm->len = nlen; + + if (zero) { + if (at >= olen) { + at -= olen; + count += olen; + } + memset(_a_at(at), 0, esize * count); + } + + return (void *)a; +#undef _a_at +} diff --git a/lib/darr.h b/lib/darr.h new file mode 100644 index 0000000000..ca46fb3054 --- /dev/null +++ b/lib/darr.h @@ -0,0 +1,363 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * June 23 2023, Christian Hopps + * + * Copyright (c) 2023, LabN Consulting, L.L.C. + * + * API functions: + * ============== + * - darr_append + * - darr_append_n + * - darr_append_nz + * - darr_cap + * - darr_ensure_cap + * - darr_ensure_i + * - darr_foreach_i + * - darr_foreach_p + * - darr_free + * - darr_insert + * - darr_insertz + * - darr_insert_n + * - darr_insert_nz + * - darr_len + * - darr_maxi + * - darr_pop + * - darr_push + * - darr_pushz + * - darr_remove + * - darr_remove_n + * - darr_reset + * - darr_setlen + */ +/* + * A few assured items + * + * - DAs will never have capacity 0 unless they are NULL pointers. + */ +#include + +struct darr_metadata { + uint len; + uint cap; +}; +void *__darr_insert_n(void *a, uint at, uint count, size_t esize, bool zero); +void *__darr_resize(void *a, uint count, size_t esize); + +#define _darr_esize(A) sizeof((A)[0]) +#define darr_esize(A) sizeof((A)[0]) +#define _darr_len(A) _darr_meta(A)->len +#define _darr_meta(A) (((struct darr_metadata *)(A)) - 1) +#define _darr_resize(A, C) ({ (A) = __darr_resize((A), C, _darr_esize(A)); }) + +/* Get the current capacity of the array */ +#define darr_cap(A) (((A) == NULL) ? 0 : _darr_meta(A)->cap) + +/* Get the largest possible index one can `darr_ensure_i` w/o resizing */ +#define darr_maxi(A) ((int)darr_cap(A) - 1) + +/** + * Get the current length of the array. + * + * As long as `A` is non-NULL, this macro may be used as an L-value to modify + * the length of the array. + * + * Args: + * A: The dynamic array, can be NULL. + * + * Return: + * The current length of the array. + */ +#define darr_len(A) (((A) == NULL) ? 0 : _darr_meta(A)->len) + +/** + * Set the current length of the array `A` to 0. + * + * Args: + * A: The dynamic array, can be NULL. + */ +#define darr_reset(A) \ + do { \ + if ((A)) \ + _darr_len(A) = 0; \ + } while (0) + +/** + * Set the current length of the array `A` to `L`. + * + * This function does *not* guarantee the memory is valid to L, + * use `darr_ensure` or `darr_ensure_cap` for that. + * + * Args: + * A: The dynamic array, can only be NULL if (L) == 0. + * L: The new length of the array. + */ +#define darr_setlen(A, L) \ + do { \ + assert((A) || !(L)); \ + if ((A)) { \ + /* have to cast to avoid compiler warning for "0" */ \ + assert((long long)darr_cap(A) >= (L)); \ + _darr_len(A) = (L); \ + } \ + } while (0) + +/** + * Free memory allocated for the dynamic array `A` + * + * Args: + * A: The dynamic array, can be NULL. + */ + +#define darr_free(A) \ + do { \ + if ((A)) { \ + free(_darr_meta(A)); \ + (A) = NULL; \ + } \ + } while (0) + +/** + * Make sure that there is room in the dynamic array `A` for `C` elements. + * + * The value `A` may be changed as a result of this call in which case any + * pointers into the previous memory block are no longer valid. The `A` value + * is guaranteed not to change if there is sufficient capacity in the array. + * + * Args: + * A: (IN/OUT) the dynamic array, can be NULL. + * I: the index to guarantee memory exists for + * + * Return: + * A pointer to the (possibly moved) array. + */ +#define darr_ensure_cap(A, C) \ + ({ \ + if (darr_cap(A) < (C)) \ + _darr_resize((A), (C)); \ + (A); \ + }) + +/** + * Return a pointer to the (I)th element of array `A`, making sure there is + * room for the element. + * + * If the array length is less than `I + 1` then the length is set to `I + 1`. + * + * The value `A` may be changed as a result of this call in which case any + * pointers into the previous memory block are no longer valid. The `A` value + * is guaranteed not to change if there is sufficient capacity in the array. + * + * Args: + * + * A: (IN/OUT) the dynamic array, can be NULL. + * I: the index to guarantee memory exists for + * + * Return: + * A pointer to the (I)th element in `A` + */ +#define darr_ensure_i(A, I) \ + ({ \ + if ((int)(I) > darr_maxi(A)) \ + _darr_resize((A), (I) + 1); \ + if ((I) + 1 > _darr_len(A)) \ + _darr_len(A) = (I) + 1; \ + &(A)[I]; \ + }) + +#define _darr_insert_n(A, I, N, Z) \ + ({ \ + (A) = __darr_insert_n(A, I, N, _darr_esize(A), Z); \ + &(A)[I]; \ + }) +/** + * Insert N uninitialized elements in the array at index `I`. + * + * Previous elements from `I` are shifted right by `N`. Array length is + * increased by `N`. + * + * The value `A` may be changed as a result of this call in which case any + * pointers into the previous memory block are no longer valid. The `A` value + * is guaranteed not to change if there is sufficient capacity in the array. + * + * The `z` variant zeros new elements. + * + * Args: + * A: The dynamic array, can be NULL. + * + * Return: + * A pointer to the first inserted element in the array. + */ +#define darr_insert_n(A, I, N) _darr_insert_n(A, I, N, false) +#define darr_insert_nz(A, I, N) _darr_insert_n(A, I, N, true) + +/** + * Insert an uninitialized element in the array at index `I`. + * + * Previous elements from `I` are shifted right by 1. Array length is + * increased by 1. + * + * The value `A` may be changed as a result of this call in which case any + * pointers into the previous memory block are no longer valid. The `A` value + * is guaranteed not to change if there is sufficient capacity in the array. + * + * The `z` variant zeros the new element. + * + * Args: + * A: The dynamic array, can be NULL. + * + * Return: + * A pointer to the element in the array. + */ +#define darr_insert(A, I) _darr_insert_n(A, I, 1, false) +#define darr_insertz(A, I) _darr_insert_n(A, I, 1, true) + +/** + * Remove `N` elements from the array starting at index `I`. + * + * Elements from `I` + `N` are shifted left by `N`. Array length is reduced by + * `N`. + * + * Args: + * A: The dynamic array, can be NULL. + */ +#define darr_remove_n(A, I, N) \ + do { \ + uint __i = (I); \ + uint __n = (N); \ + uint __len = darr_len(A); \ + if (!__len) \ + break; \ + else if (__i + __n < __len) { \ + memmove(&(A)[__i], &(A)[__i + __n], \ + _darr_esize(A) * (__len - (__i + __n))); \ + _darr_len(A) = __len - __n; \ + } else \ + _darr_len(A) = __i; \ + } while (0) + +/** + * Remove the `I`th element from the array. + * + * Previous elements from `I` + 1 are shifted left by 1, Array length is reduced + * by 1. + * + * Args: + * A: The dynamic array, can be NULL. + */ +#define darr_remove(A, I) darr_remove_n(A, I, 1) + + +#define _darr_append_n(A, N, Z) \ + ({ \ + uint __len = darr_len(A); \ + darr_ensure_cap(A, __len + (N)); \ + _darr_len(A) = __len + (N); \ + if (Z) \ + memset(&(A)[__len], 0, (N)*_darr_esize(A)); \ + &(A)[__len]; \ + }) +/** + * Extending the array's length by N. + * + * Args: + * A: The dynamic array, can be NULL. + * + * The `z` variant zeros new elements. + * + * Return: + * A pointer to the first of the added elements at the end of the array. + */ +#define darr_append_n(A, N) _darr_append_n(A, N, false) +#define darr_append_nz(A, N) _darr_append_n(A, N, true) + +/** + * Extending the array's length by 1. + * + * Args: + * A: The dynamic array, can be NULL. + * + * The `z` variant zeros the new element. + * + * Return: + * A pointer to the new element at the end of the array. + */ +#define darr_append(A) _darr_append_n(A, 1, false) +#define darr_appendz(A) _darr_append_n(A, 1, true) + +/** + * Append an element `E` onto the array `A`, extending it's length by 1. + * + * The `z` variant zeros the new element. + * + * Args: + * A: The dynamic array, can be NULL. + * + * Return: + * A pointer to the element in the array. + */ +#define darr_push(A, E) (*darr_append(A) = (E)) +#define darr_pushz(A) (darr_appendz(A)) + + +/** + * Pop the last `N` elements from the array decrementing the length by `N`. + * + * Args: + * A: The dynamic array, can be NULL. + */ +#define darr_pop_n(A, N) \ + do { \ + if ((A) && (N) >= _darr_len(A)) \ + darr_reset(A); \ + else \ + _darr_len(A) -= (N); \ + } while (0) + + +/** + * Pop the last element from the array decrementing the length by 1. + * + * Args: + * A: The dynamic array, can be NULL. + * + * Return: + * The element just popped. + */ +#define darr_pop(A) \ + ({ \ + uint __len = _darr_len(A); \ + assert(__len); \ + darr_remove(A, __len - 1); \ + /* count on fact that we don't resize */ \ + (A)[__len - 1]; \ + }) + +/** + * Return the address at the end of the array -- useful for iterating + * + * Args: + * A: The dynamic array, can be NULL. + * + * Return: + * The address of the end of the array (past the last elment) or NULL + * if `A` is NULL. + */ +#define darr_end(A) ((A) + darr_len(A)) + +/** + * Iterate over array `A` using a pointer to each element in `P`. + * + * Args: + * A: The dynamic array, can be NULL. + * P: A variable with the same type as A used as the iterator. + */ +#define darr_foreach_p(A, P) for ((P) = (A); (P) < darr_end(A); (P)++) + +/** + * Iterate over array `A`s indices. + * + * Args: + * A: The dynamic array, can be NULL. + * I: A uint variable to store the current element index in. + */ +#define darr_foreach_i(A, I) for ((I) = 0; (I) < darr_len(A); (I)++) diff --git a/lib/subdir.am b/lib/subdir.am index c046c3c43c..d7b28ffbd5 100644 --- a/lib/subdir.am +++ b/lib/subdir.am @@ -25,6 +25,7 @@ lib_libfrr_la_SOURCES = \ lib/command_parse.y \ lib/cspf.c \ lib/csv.c \ + lib/darr.c \ lib/debug.c \ lib/defaults.c \ lib/distribute.c \ @@ -209,6 +210,7 @@ pkginclude_HEADERS += \ lib/compiler.h \ lib/cspf.h \ lib/csv.h \ + lib/darr.h \ lib/db.h \ lib/debug.h \ lib/defaults.h \ diff --git a/tests/lib/subdir.am b/tests/lib/subdir.am index c3a1a3e2c0..6c1be50201 100644 --- a/tests/lib/subdir.am +++ b/tests/lib/subdir.am @@ -157,6 +157,13 @@ tests_lib_test_checksum_LDADD = $(ALL_TESTS_LDADD) tests_lib_test_checksum_SOURCES = tests/lib/test_checksum.c tests/helpers/c/prng.c +check_PROGRAMS += tests/lib/test_darr +tests_lib_test_darr_CFLAGS = $(TESTS_CFLAGS) +tests_lib_test_darr_CPPFLAGS = $(TESTS_CPPFLAGS) +tests_lib_test_darr_LDADD = $(ALL_TESTS_LDADD) +tests_lib_test_darr_SOURCES = tests/lib/test_darr.c + + check_PROGRAMS += tests/lib/test_graph tests_lib_test_graph_CFLAGS = $(TESTS_CFLAGS) tests_lib_test_graph_CPPFLAGS = $(TESTS_CPPFLAGS) diff --git a/tests/lib/test_darr.c b/tests/lib/test_darr.c new file mode 100644 index 0000000000..9150aed09d --- /dev/null +++ b/tests/lib/test_darr.c @@ -0,0 +1,279 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * June 23 2023, Christian Hopps + * + * Copyright (c) 2023, LabN Consulting, L.L.C. + * + */ +#include +#include "darr.h" + +/* + * Public functions to test: + * [x] - darr_append + * [x] - darr_append_n + * [x] - darr_append_nz + * [x] - darr_cap + * [-] - darr_ensure_cap + * [x] - darr_ensure_i + * [x] - darr_foreach_i + * [x] - darr_foreach_p + * [x] - darr_free + * [x] - darr_insert + * [ ] - darr_insertz + * [x] - darr_insert_n + * [x] - darr_insert_nz + * [x] - darr_maxi + * [x] - darr_pop + * [x] - darr_push + * [ ] - darr_pushz + * [x] - darr_remove + * [x] - darr_remove_n + * [x] - darr_reset + * [x] - darr_setlen + */ + +static void test_int(void) +{ + int z105[105] = {0}; + int a1[] = {0, 1, 2, 3, 4}; + int a2[] = {4, 3, 2, 1, 0}; + int *da1 = NULL; + int *da2 = NULL; + int *dap; + uint i; + + darr_ensure_i(da1, 0); + da1[0] = 0; + assert(darr_len(da1) == 1); + assert(darr_cap(da1) == 1); + + *darr_ensure_i(da1, 1) = 1; + assert(darr_len(da1) == 2); + assert(darr_cap(da1) == 2); + + darr_ensure_i(da1, 4); + darr_foreach_i (da1, i) + da1[i] = i; + + assert(darr_len(da1) == 5); + /* minimum non-pow2 array size for long long and smaller */ + assert(darr_cap(da1) == 8); + assert(!memcmp(da1, a1, sizeof(a1))); + + /* reverse the numbers */ + darr_foreach_p (da1, dap) + *dap = darr_end(da1) - dap - 1; + assert(!memcmp(da1, a2, sizeof(a2))); + + darr_append_n(da1, 100); + darr_foreach_p (da1, dap) + *dap = darr_end(da1) - dap - 1; + + darr_pop_n(da1, 100); + darr_append_nz(da1, 100); + assert(!memcmp(&da1[5], z105, _darr_esize(da1) * 100)); + + assert(darr_len(da1) == 105); + assert(darr_maxi(da1) == 127); + assert(darr_cap(da1) == 128); + + darr_setlen(da1, 102); + assert(darr_len(da1) == 102); + assert(darr_maxi(da1) == 127); + + int a3[] = { 0xdeadbeaf, 0x12345678 }; + + da1[0] = a3[0]; + da1[101] = a3[1]; + darr_remove_n(da1, 1, 100); + assert(darr_len(da1) == array_size(a3)); + assert(!memcmp(da1, a3, sizeof(a3))); + + da1[0] = a3[1]; + da1[1] = a3[0]; + + darr_insert_n(da1, 1, 100); + assert(darr_len(da1) == 102); + assert(da1[0] == a3[1]); + assert(da1[101] == a3[0]); + + darr_reset(da1); + assert(darr_len(da1) == 0); + assert(darr_maxi(da1) == 127); + assert(darr_cap(da1) == 128); + + /* we touch the length field of the freed block here somehow */ + darr_insert_n(da1, 100, 300); + assert(darr_len(da1) == 400); + assert(darr_cap(da1) == 512); + + da1[400 - 1] = 0x0BAD; + *darr_insert(da1, 0) = 0xF00D; + assert(da1[0] == 0xF00D); + assert(da1[400] == 0x0BAD); + assert(darr_len(da1) == 401); + assert(darr_cap(da1) == 512); + + darr_free(da1); + assert(da1 == NULL); + assert(darr_len(da1) == 0); + darr_setlen(da1, 0); + darr_reset(da1); + darr_free(da1); + + *darr_append(da2) = 0; + *darr_append(da2) = 1; + darr_push(da2, 2); + darr_push(da2, 3); + darr_push(da2, 4); + + assert(!memcmp(da2, a1, sizeof(a1))); + + assert(darr_pop(da2) == 4); + assert(darr_pop(da2) == 3); + assert(darr_pop(da2) == 2); + assert(darr_len(da2) == 2); + assert(darr_pop(da2) == 1); + assert(darr_pop(da2) == 0); + assert(darr_len(da2) == 0); + + darr_free(da2); +} + +static void test_struct(void) +{ + /* + *uwould like to use different sizes with padding but memcmp can't be + *used then. + */ + struct st { + long long a; + long long b; + }; + struct st z102[102] = {{0, 0}}; + struct st *da1 = NULL; + struct st *da2 = NULL; + struct st a1[] = { + {0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, + }; + uint i; + + darr_ensure_i(da1, 0); + da1[0].a = 0; + da1[0].b = 0; + assert(darr_len(da1) == 1); + assert(darr_cap(da1) == 1); + + darr_ensure_i(da1, 1)->a = 1; + darr_ensure_i(da1, 1)->b = 1; + assert(darr_len(da1) == 2); + assert(darr_cap(da1) == 2); + + darr_ensure_i(da1, 4); + da1[2].a = 2; + da1[2].b = 2; + + da1[3].a = 3; + da1[3].b = 3; + + da1[4].a = 4; + da1[4].b = 4; + + assert(darr_len(da1) == 5); + /* minimum non-pow2 array size for long long and smaller */ + assert(darr_cap(da1) == 8); + assert(!memcmp(da1, a1, sizeof(a1))); + + darr_append_n(da1, 100); + + assert(darr_len(da1) == 105); + assert(darr_maxi(da1) == 127); + assert(darr_cap(da1) == 128); + + darr_setlen(da1, 102); + assert(darr_len(da1) == 102); + assert(darr_maxi(da1) == 127); + + struct st a2[] = { + {0xdeadbeaf, 0xdeadbeaf}, + {0x12345678, 0x12345678}, + }; + da1[0] = a2[0]; + da1[101] = a2[1]; + darr_remove_n(da1, 1, 100); + assert(darr_len(da1) == array_size(a2)); + assert(!memcmp(da1, a2, sizeof(a2))); + + da1[0] = a2[1]; + da1[1] = a2[0]; + + darr_insert_n(da1, 1, 100); + assert(darr_len(da1) == 102); + darr_foreach_i (da1, i) { + da1[i].a = i; + da1[i].b = i; + } + darr_remove_n(da1, 1, 100); + assert(darr_len(da1) == 2); + darr_insert_nz(da1, 1, 100); + assert(!memcmp(&da1[1], z102, 100 * sizeof(da1[0]))); + /* assert(da1[0] == a2[1]); */ + /* assert(da1[101] == a2[0]); */ + + darr_reset(da1); + assert(darr_len(da1) == 0); + assert(darr_maxi(da1) == 127); + assert(darr_cap(da1) == 128); + + /* we touch the length field of the freed block here somehow */ + darr_insert_n(da1, 100, 300); + + assert(darr_len(da1) == 400); + assert(darr_cap(da1) == 512); + + darr_free(da1); + assert(da1 == NULL); + + assert(darr_len(da1) == 0); + darr_setlen(da1, 0); + darr_reset(da1); + + darr_free(da1); + + struct st i0 = {0, 0}; + struct st i1 = {1, 1}; + struct st i2 = {2, 2}; + struct st i3 = {3, 3}; + struct st i4 = {4, 4}; + + *darr_append(da2) = i0; + *darr_append(da2) = i1; + darr_push(da2, i2); + darr_push(da2, i3); + darr_push(da2, i4); + + assert(!memcmp(da2, a1, sizeof(a1))); + + struct st p0, p1, p2, p3, p4; + + p4 = darr_pop(da2); + p3 = darr_pop(da2); + p2 = darr_pop(da2); + p1 = darr_pop(da2); + p0 = darr_pop(da2); + assert(darr_len(da2) == 0); + assert(p4.a == i4.a && p4.b == i4.b); + assert(p3.a == i3.a && p3.b == i3.b); + assert(p2.a == i2.a && p2.b == i2.b); + assert(p1.a == i1.a && p1.b == i1.b); + assert(p0.a == i0.a && p0.b == i0.b); + + darr_free(da2); +} + +int main(int argc, char **argv) +{ + test_int(); + test_struct(); +} -- 2.39.5