From 1d49f78c362981435a88d887c777ccc445f5a4e7 Mon Sep 17 00:00:00 2001 From: Simon Glass Date: Sat, 19 Oct 2024 09:21:44 -0600 Subject: alist: Add a way to get the next element Add a new function which returns the next element after the one provided, if it exists in the list. Signed-off-by: Simon Glass --- lib/alist.c | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'lib') diff --git a/lib/alist.c b/lib/alist.c index b7928cad520..7730fe0d473 100644 --- a/lib/alist.c +++ b/lib/alist.c @@ -106,6 +106,27 @@ const void *alist_get_ptr(const struct alist *lst, uint index) return lst->data + index * lst->obj_size; } +int alist_calc_index(const struct alist *lst, const void *ptr) +{ + uint index; + + if (!lst->count || ptr < lst->data) + return -1; + + index = (ptr - lst->data) / lst->obj_size; + + return index; +} + +const void *alist_next_ptrd(const struct alist *lst, const void *ptr) +{ + int index = alist_calc_index(lst, ptr); + + assert(index != -1); + + return alist_get_ptr(lst, index + 1); +} + void *alist_ensure_ptr(struct alist *lst, uint index) { uint minsize = index + 1; -- cgit v1.3.1 From d785a77d18acdf6714f4570c14e622caadf4d5e3 Mon Sep 17 00:00:00 2001 From: Simon Glass Date: Sat, 19 Oct 2024 09:21:45 -0600 Subject: alist: Add for-loop helpers Add some macros which permit easy iteration through an alist, similar to those provided by the 'list' implementation. Signed-off-by: Simon Glass --- include/alist.h | 50 ++++++++++++++++++++++++++++++++++++++ lib/alist.c | 7 ++++++ test/lib/alist.c | 74 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 131 insertions(+) (limited to 'lib') diff --git a/include/alist.h b/include/alist.h index 97523af37a6..0090b9c0eb1 100644 --- a/include/alist.h +++ b/include/alist.h @@ -224,6 +224,56 @@ bool alist_expand_by(struct alist *lst, uint inc_by); */ const void *alist_next_ptrd(const struct alist *lst, const void *ptr); +/** + * alist_chk_ptr() - Check whether a pointer is within a list + * + * Checks if the pointer points to an existing element of the list. The pointer + * must point to the start of an element, either in the list, or just outside of + * it. This function is only useful for handling for() loops + * + * Return: true if @ptr is within the list (0..count-1), else false + */ +bool alist_chk_ptr(const struct alist *lst, const void *ptr); + +/** + * alist_start() - Get the start of the list (first element) + * + * Note that this will always return ->data even if it is not NULL + * + * Usage: + * const struct my_struct *obj; # 'const' is optional + * + * alist_start(&lst, struct my_struct) + */ +#define alist_start(_lst, _struct) \ + ((_struct *)(_lst)->data) + +/** + * alist_end() - Get the end of the list (just after last element) + * + * Usage: + * const struct my_struct *obj; # 'const' is optional + * + * alist_end(&lst, struct my_struct) + */ +#define alist_end(_lst, _struct) \ + ((_struct *)(_lst)->data + (_lst)->count) + +/** + * alist_for_each() - Iterate over an alist (with constant pointer) + * + * Use as: + * const struct my_struct *obj; # 'const' is optional + * + * alist_for_each(obj, &lst) { + * obj->... + * } + */ +#define alist_for_each(_pos, _lst) \ + for (_pos = alist_start(_lst, typeof(*(_pos))); \ + _pos < alist_end(_lst, typeof(*(_pos))); \ + _pos++) + /** * alist_init() - Set up a new object list * diff --git a/lib/alist.c b/lib/alist.c index 7730fe0d473..1a4b4fb9c40 100644 --- a/lib/alist.c +++ b/lib/alist.c @@ -118,6 +118,13 @@ int alist_calc_index(const struct alist *lst, const void *ptr) return index; } +bool alist_chk_ptr(const struct alist *lst, const void *ptr) +{ + int index = alist_calc_index(lst, ptr); + + return index >= 0 && index < lst->count; +} + const void *alist_next_ptrd(const struct alist *lst, const void *ptr) { int index = alist_calc_index(lst, ptr); diff --git a/test/lib/alist.c b/test/lib/alist.c index 96092affec9..1715a22584c 100644 --- a/test/lib/alist.c +++ b/test/lib/alist.c @@ -292,3 +292,77 @@ static int lib_test_alist_next(struct unit_test_state *uts) return 0; } LIB_TEST(lib_test_alist_next, 0); + +/* Test alist_for_each() */ +static int lib_test_alist_for_each(struct unit_test_state *uts) +{ + const struct my_struct *ptr; + struct my_struct data, *ptr2; + struct alist lst; + ulong start; + int sum; + + start = ut_check_free(); + + ut_assert(alist_init_struct(&lst, struct my_struct)); + ut_asserteq_ptr(NULL, alist_end(&lst, struct my_struct)); + + sum = 0; + alist_for_each(ptr, &lst) + sum++; + ut_asserteq(0, sum); + + alist_for_each(ptr, &lst) + sum++; + ut_asserteq(0, sum); + + /* add three items */ + data.val = 1; + data.other_val = 0; + alist_add(&lst, data); + + ptr = lst.data; + ut_asserteq_ptr(ptr + 1, alist_end(&lst, struct my_struct)); + + data.val = 2; + alist_add(&lst, data); + ut_asserteq_ptr(ptr + 2, alist_end(&lst, struct my_struct)); + + data.val = 3; + alist_add(&lst, data); + ut_asserteq_ptr(ptr + 3, alist_end(&lst, struct my_struct)); + + /* check alist_chk_ptr() */ + ut_asserteq(true, alist_chk_ptr(&lst, ptr + 2)); + ut_asserteq(false, alist_chk_ptr(&lst, ptr + 3)); + ut_asserteq(false, alist_chk_ptr(&lst, ptr + 4)); + ut_asserteq(true, alist_chk_ptr(&lst, ptr)); + ut_asserteq(false, alist_chk_ptr(&lst, ptr - 1)); + + /* sum all items */ + sum = 0; + alist_for_each(ptr, &lst) + sum += ptr->val; + ut_asserteq(6, sum); + + /* increment all items */ + alist_for_each(ptr2, &lst) + ptr2->val += 1; + + /* sum all items again */ + sum = 0; + alist_for_each(ptr, &lst) + sum += ptr->val; + ut_asserteq(9, sum); + + ptr = lst.data; + ut_asserteq_ptr(ptr + 3, alist_end(&lst, struct my_struct)); + + alist_uninit(&lst); + + /* Check for memory leaks */ + ut_assertok(ut_check_delta(start)); + + return 0; +} +LIB_TEST(lib_test_alist_for_each, 0); -- cgit v1.3.1 From 5bd4ead8bd76c85aa599c44e8bfb12f512d8ed09 Mon Sep 17 00:00:00 2001 From: Simon Glass Date: Sat, 19 Oct 2024 09:21:46 -0600 Subject: alist: Add a function to empty the list Sometimes it is useful to empty the list without de-allocating any of the memory used, e.g. when the list will be re-populated immediately afterwards. Add a new function for this. Signed-off-by: Simon Glass --- include/alist.h | 7 +++++++ lib/alist.c | 5 +++++ test/lib/alist.c | 42 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 54 insertions(+) (limited to 'lib') diff --git a/include/alist.h b/include/alist.h index 0090b9c0eb1..c639e42ab7d 100644 --- a/include/alist.h +++ b/include/alist.h @@ -274,6 +274,13 @@ bool alist_chk_ptr(const struct alist *lst, const void *ptr); _pos < alist_end(_lst, typeof(*(_pos))); \ _pos++) +/** + * alist_empty() - Empty an alist + * + * This removes all entries from the list, without changing the allocated size + */ +void alist_empty(struct alist *lst); + /** * alist_init() - Set up a new object list * diff --git a/lib/alist.c b/lib/alist.c index 1a4b4fb9c40..32cd45b0b01 100644 --- a/lib/alist.c +++ b/lib/alist.c @@ -41,6 +41,11 @@ void alist_uninit(struct alist *lst) memset(lst, '\0', sizeof(struct alist)); } +void alist_empty(struct alist *lst) +{ + lst->count = 0; +} + /** * alist_expand_to() - Expand a list to the given size * diff --git a/test/lib/alist.c b/test/lib/alist.c index 1715a22584c..87135bb3a51 100644 --- a/test/lib/alist.c +++ b/test/lib/alist.c @@ -358,6 +358,16 @@ static int lib_test_alist_for_each(struct unit_test_state *uts) ptr = lst.data; ut_asserteq_ptr(ptr + 3, alist_end(&lst, struct my_struct)); + /* empty the list and try again */ + alist_empty(&lst); + ut_asserteq_ptr(ptr, alist_end(&lst, struct my_struct)); + ut_assertnull(alist_get(&lst, 0, struct my_struct)); + + sum = 0; + alist_for_each(ptr, &lst) + sum += ptr->val; + ut_asserteq(0, sum); + alist_uninit(&lst); /* Check for memory leaks */ @@ -366,3 +376,35 @@ static int lib_test_alist_for_each(struct unit_test_state *uts) return 0; } LIB_TEST(lib_test_alist_for_each, 0); + +/* Test alist_empty() */ +static int lib_test_alist_empty(struct unit_test_state *uts) +{ + struct my_struct data; + struct alist lst; + ulong start; + + start = ut_check_free(); + + ut_assert(alist_init_struct(&lst, struct my_struct)); + ut_asserteq(0, lst.count); + data.val = 1; + data.other_val = 0; + alist_add(&lst, data); + ut_asserteq(1, lst.count); + ut_asserteq(4, lst.alloc); + + alist_empty(&lst); + ut_asserteq(0, lst.count); + ut_asserteq(4, lst.alloc); + ut_assertnonnull(lst.data); + ut_asserteq(sizeof(data), lst.obj_size); + + alist_uninit(&lst); + + /* Check for memory leaks */ + ut_assertok(ut_check_delta(start)); + + return 0; +} +LIB_TEST(lib_test_alist_empty, 0); -- cgit v1.3.1 From 5dfc1c8078572436fc68817d22d9e046eaa01398 Mon Sep 17 00:00:00 2001 From: Simon Glass Date: Sat, 19 Oct 2024 09:21:47 -0600 Subject: alist: Add a way to efficiently filter an alist Unlike linked lists, it is inefficient to remove items from an alist, particularly if it is large. If most items need to be removed, then the time-complexity approaches O(n2). Provide a way to do this efficiently, by working through the alist once and copying elements down. Signed-off-by: Simon Glass --- include/alist.h | 30 ++++++++++++++++++++ lib/alist.c | 8 ++++++ test/lib/alist.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 123 insertions(+) (limited to 'lib') diff --git a/include/alist.h b/include/alist.h index c639e42ab7d..b00d9ea97d6 100644 --- a/include/alist.h +++ b/include/alist.h @@ -274,6 +274,36 @@ bool alist_chk_ptr(const struct alist *lst, const void *ptr); _pos < alist_end(_lst, typeof(*(_pos))); \ _pos++) +/** + * alist_for_each_filter() - version which sets up a 'from' pointer too + * + * This is used for filtering out information in the list. It works by iterating + * through the list, copying elements down over the top of elements to be + * deleted. + * + * In this example, 'from' iterates through the list from start to end,, 'to' + * also begins at the start, but only increments if the element at 'from' should + * be kept. This provides an O(n) filtering operation. Note that + * alist_update_end() must be called after the loop, to update the count. + * + * alist_for_each_filter(from, to, &lst) { + * if (from->val != 2) + * *to++ = *from; + * } + * alist_update_end(&lst, to); + */ +#define alist_for_each_filter(_pos, _from, _lst) \ + for (_pos = _from = alist_start(_lst, typeof(*(_pos))); \ + _pos < alist_end(_lst, typeof(*(_pos))); \ + _pos++) + +/** + * alist_update_end() - Set the element count based on a given pointer + * + * Set the given element as the final one + */ +void alist_update_end(struct alist *lst, const void *end); + /** * alist_empty() - Empty an alist * diff --git a/lib/alist.c b/lib/alist.c index 32cd45b0b01..4ce651f5c45 100644 --- a/lib/alist.c +++ b/lib/alist.c @@ -123,6 +123,14 @@ int alist_calc_index(const struct alist *lst, const void *ptr) return index; } +void alist_update_end(struct alist *lst, const void *ptr) +{ + int index; + + index = alist_calc_index(lst, ptr); + lst->count = index == -1 ? 0 : index; +} + bool alist_chk_ptr(const struct alist *lst, const void *ptr) { int index = alist_calc_index(lst, ptr); diff --git a/test/lib/alist.c b/test/lib/alist.c index 87135bb3a51..0bf24578d2e 100644 --- a/test/lib/alist.c +++ b/test/lib/alist.c @@ -408,3 +408,88 @@ static int lib_test_alist_empty(struct unit_test_state *uts) return 0; } LIB_TEST(lib_test_alist_empty, 0); + +static int lib_test_alist_filter(struct unit_test_state *uts) +{ + struct my_struct *from, *to, *ptr; + struct my_struct data; + struct alist lst; + ulong start; + int count; + + start = ut_check_free(); + + ut_assert(alist_init_struct(&lst, struct my_struct)); + data.val = 1; + data.other_val = 0; + alist_add(&lst, data); + + data.val = 2; + alist_add(&lst, data); + + data.val = 3; + alist_add(&lst, data); + ptr = lst.data; + + /* filter out all values except 2 */ + alist_for_each_filter(from, to, &lst) { + if (from->val != 2) + *to++ = *from; + } + alist_update_end(&lst, to); + + ut_asserteq(2, lst.count); + ut_assertnonnull(lst.data); + + ut_asserteq(1, alist_get(&lst, 0, struct my_struct)->val); + ut_asserteq(3, alist_get(&lst, 1, struct my_struct)->val); + ut_asserteq_ptr(ptr + 3, from); + ut_asserteq_ptr(ptr + 2, to); + + /* filter out nothing */ + alist_for_each_filter(from, to, &lst) { + if (from->val != 2) + *to++ = *from; + } + alist_update_end(&lst, to); + ut_asserteq_ptr(ptr + 2, from); + ut_asserteq_ptr(ptr + 2, to); + + ut_asserteq(2, lst.count); + ut_assertnonnull(lst.data); + + ut_asserteq(1, alist_get(&lst, 0, struct my_struct)->val); + ut_asserteq(3, alist_get(&lst, 1, struct my_struct)->val); + + /* filter out everything */ + alist_for_each_filter(from, to, &lst) { + if (from->val == 2) + *to++ = *from; + } + alist_update_end(&lst, to); + ut_asserteq_ptr(ptr + 2, from); + ut_asserteq_ptr(ptr, to); + + /* filter out everything (nop) */ + count = 0; + alist_for_each_filter(from, to, &lst) { + if (from->val == 2) + *to++ = *from; + count++; + } + alist_update_end(&lst, to); + ut_asserteq_ptr(ptr, from); + ut_asserteq_ptr(ptr, to); + ut_asserteq(0, count); + + ut_asserteq(0, lst.count); + ut_assertnonnull(lst.data); + + alist_uninit(&lst); + + /* Check for memory leaks */ + ut_assertok(ut_check_delta(start)); + + return 0; +} +LIB_TEST(lib_test_alist_filter, 0); -- cgit v1.3.1