[PATCH 07/34] alist: Add a way to efficiently filter an alist

[Simon Glass]

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 at 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);
-- 
2.34.1