Add a new list iteration macro that always takes the first element of the
list and removes it, until the list is empty.

Add a list_for_each_entry_del_init() variant too.

This is a common pattern.

Signed-off-by: Miklos Szeredi <mszeredi@redhat.com>
---
 include/linux/list.h | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)

diff --git a/include/linux/list.h b/include/linux/list.h
index 164b4d0e9d2a..db23a9ee98f0 100644
--- a/include/linux/list.h
+++ b/include/linux/list.h
@@ -921,6 +921,35 @@ static inline size_t list_count_nodes(struct list_head *head)
 #define list_safe_reset_next(pos, n, member)				\
 	n = list_next_entry(pos, member)
 
+/**
+ * list_for_each_entry_del - iterate list and remove elements
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Delete first element from list before the iteration.  Iterate until
+ * the list is empty.
+ */
+#define list_for_each_entry_del(pos, head, member)			\
+	while (!list_empty(head) &&					\
+		({ pos = list_first_entry(head, typeof(*(pos)), member);\
+		   list_del(&(pos)->member); 1; }))
+
+/**
+ * list_for_each_entry_del_init - iterate list, remove and reinitialize elements
+ * @pos:	the type * to use as a loop cursor.
+ * @head:	the head for your list.
+ * @member:	the name of the list_head within the struct.
+ *
+ * Delete first element from list before the iteration using list_del_init().
+ * Iterate until the list is empty.
+ */
+#define list_for_each_entry_del_init(pos, head, member)			\
+	while (!list_empty(head) &&					\
+		({ pos = list_first_entry(head, typeof(*(pos)), member);\
+		   list_del_init(&(pos)->member); 1; }))
+
+
 /*
  * Double linked lists with a single pointer list head.
  * Mostly useful for hash tables where the two pointer list head is
-- 
2.41.0

From: Miklos Szeredi
> Sent: 20 October 2023 11:29
> 
> Add a new list iteration macro that always takes the first element of the
> list and removes it, until the list is empty.
...
> +/**
> + * list_for_each_entry_del - iterate list and remove elements
> + * @pos:	the type * to use as a loop cursor.
> + * @head:	the head for your list.
> + * @member:	the name of the list_head within the struct.
> + *
> + * Delete first element from list before the iteration.  Iterate until
> + * the list is empty.
> + */
> +#define list_for_each_entry_del(pos, head, member)			\
> +	while (!list_empty(head) &&					\
> +		({ pos = list_first_entry(head, typeof(*(pos)), member);\
> +		   list_del(&(pos)->member); 1; }))

That pattern is actually pretty obvious.
Add another wrapper and people end up having to read the
header to find out what it does.

I can't help feeling that if you look inside list_empty(),
list_first_entry() and list_del() there is a lot of
replicated code and tests.

Adding a list_del_first() function that returns the deleted
item or NULL to optimise it might make more sense.

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)

On Sat, Oct 21, 2023 at 12:00 PM David Laight <David.Laight@aculab.com> wrote:

> Adding a list_del_first() function that returns the deleted
> item or NULL to optimise it might make more sense.

Something like this?

- list_for_each_entry_del(entry, head, member))
+ while (list_del_first(entry, head, member))

This allows the compact loop condition, and I always hated having to
pass the type to list_*entry()...  Disadvantage being that the
assignment is now implicit (just as with all the list iterators).

Thanks,
Miklos

On Wed, 25 Oct 2023 at 23:52, Miklos Szeredi <mszeredi@redhat.com> wrote:
>
> Something like this?
>
> - list_for_each_entry_del(entry, head, member))
> + while (list_del_first(entry, head, member))
>
> This allows the compact loop condition, and I always hated having to
> pass the type to list_*entry()...  Disadvantage being that the
> assignment is now implicit (just as with all the list iterators).

So I have two issues with this.

One is purely syntactical: I would be personally happier if any new
list iterators kept the declaration of the iterator internally to
itself.

IOW, instead of

        struct request *rq;

        list_for_each_entry_del(rq, list, queuelist) {
                ...

we'd move on to modern C which allows declaring variables in for loops
(so they aren't visible outside the loop), and turn it into

        list_for_each_entry_del(struct request, rq, list, queuelist) {
                ...

which would then behind the scenes turn into

        for (struct request *rq; rq = list_del_first(list, queuelist); ) {
                ...

or something. None of these "we have stale 'rq' variables outside the
list" things.

(Of course, I realize that people then sometimes intentionally use
those stale variables outside the list by breaking out of the loop in
the middle, but it's ugly)

That said, the *second* issue I have with this whole
list_for_each_entry_del() is that it seems a bit mis-designed. You
have two cases:

 - you want to unconditionally delete everything

 - you might want to have a condition on it and break out early

and the first one is often better dealt with by first moving the list
to a private list head (presumably using list_splice_init()), and then
iterating the private list head instead. That can avoid having to hold
a lock over the whole loop (or dropping it and re-taking it), for
example.

And that *second* case would presumably want to use
list_for_each_entry_safe(), and then do the "list_del()" at the _end_
of the loop, not at the beginning?

Hmm?

I guess the "delete the whole list" is the simple case you want to
deal with, and people who can use a private list to avoid locking
already do the list_splice_init() thing separately (or create the
private list as a separate phase, to also deal with the "I'm not going
to delete everything" issue).

                 Linus