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/alist.c') 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.2.3 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 --- lib/alist.c | 7 +++++++ 1 file changed, 7 insertions(+) (limited to 'lib/alist.c') 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); -- cgit v1.2.3 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 --- lib/alist.c | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'lib/alist.c') 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 * -- cgit v1.2.3 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 --- lib/alist.c | 8 ++++++++ 1 file changed, 8 insertions(+) (limited to 'lib/alist.c') 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); -- cgit v1.2.3