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 <[email protected]>

1 files changed, 30 insertions, 0 deletions

diff --git a/include/alist.h b/include/alist.h
index c639e42ab7d..b00d9ea97d6 100644
--- a/include/alist.h
+++ b/include/alist.h
@@ -275,6 +275,36 @@ bool alist_chk_ptr(const struct alist *lst, const void *ptr);
 	     _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
  *
  * This removes all entries from the list, without changing the allocated size