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 sjg@chromium.org ---
include/alist.h | 30 +++++++++++++++++ lib/alist.c | 8 +++++ test/lib/alist.c | 85 ++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 123 insertions(+)
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);