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 <s...@chromium.org>
---
(no changes since v1)
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);
--
2.34.1
