git: c02880233949 - main - queue(3): New *_SPLIT_AFTER(), *_ASSERT_EMPTY(), *_ASSERT_NONEMPTY()

From: Olivier Certner <olce_at_FreeBSD.org>
Date: Mon, 28 Apr 2025 12:23:30 UTC
The branch main has been updated by olce:

URL: https://cgit.FreeBSD.org/src/commit/?id=c02880233949b01fcfb2067962596f5c05553471

commit c02880233949b01fcfb2067962596f5c05553471
Author:     Olivier Certner <olce@FreeBSD.org>
AuthorDate: 2025-02-28 09:18:48 +0000
Commit:     Olivier Certner <olce@FreeBSD.org>
CommitDate: 2025-04-28 11:58:37 +0000

    queue(3): New *_SPLIT_AFTER(), *_ASSERT_EMPTY(), *_ASSERT_NONEMPTY()
    
    *_SPLIT_AFTER() allows to split an existing queue in two.  It is the
    missing block that enables arbitrary splitting and recombinations of
    lists/queues together with *_CONCAT() and *_SWAP().
    
    Add *_ASSERT_NONEMPTY(), used by *_SPLIT_AFTER().
    
    Reviewed by:    markj
    MFC after:      3 days
    Sponsored by:   The FreeBSD Foundation
    Differential Revision:  https://reviews.freebsd.org/D49608 (stailq)
    Differential Revision:  https://reviews.freebsd.org/D49969 (rest)
---
 share/man/man3/queue.3 |  54 +++++++++++++++++++++++++
 sys/sys/queue.h        | 108 +++++++++++++++++++++++++++++++++++++++++++++----
 2 files changed, 155 insertions(+), 7 deletions(-)

diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3
index e55c7cfb7513..e0684fa7c70f 100644
--- a/share/man/man3/queue.3
+++ b/share/man/man3/queue.3
@@ -49,6 +49,7 @@
 .Nm SLIST_REMOVE ,
 .Nm SLIST_REMOVE_AFTER ,
 .Nm SLIST_REMOVE_HEAD ,
+.Nm SLIST_SPLIT_AFTER ,
 .Nm SLIST_SWAP ,
 .Nm STAILQ_CLASS_ENTRY ,
 .Nm STAILQ_CLASS_HEAD ,
@@ -72,6 +73,7 @@
 .Nm STAILQ_REMOVE ,
 .Nm STAILQ_REMOVE_AFTER ,
 .Nm STAILQ_REMOVE_HEAD ,
+.Nm STAILQ_SPLIT_AFTER ,
 .Nm STAILQ_SWAP ,
 .Nm LIST_CLASS_ENTRY ,
 .Nm LIST_CLASS_HEAD ,
@@ -94,6 +96,7 @@
 .Nm LIST_PREV ,
 .Nm LIST_REMOVE ,
 .Nm LIST_REPLACE ,
+.Nm LIST_SPLIT_AFTER ,
 .Nm LIST_SWAP ,
 .Nm TAILQ_CLASS_ENTRY ,
 .Nm TAILQ_CLASS_HEAD ,
@@ -122,6 +125,7 @@
 .Nm TAILQ_PREV ,
 .Nm TAILQ_REMOVE ,
 .Nm TAILQ_REPLACE ,
+.Nm TAILQ_SPLIT_AFTER ,
 .Nm TAILQ_SWAP
 .Nd implementations of singly-linked lists, singly-linked tail queues,
 lists and tail queues
@@ -148,6 +152,7 @@ lists and tail queues
 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
 .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
+.Fn SLIST_SPLIT_AFTER "SLIST_HEAD *head" "TYPE *elm" "SLIST_HEAD *rest" "SLIST_ENTRY NAME"
 .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE"
 .\"
 .Fn STAILQ_CLASS_ENTRY "CLASSTYPE"
@@ -172,6 +177,7 @@ lists and tail queues
 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
 .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
+.Fn STAILQ_SPLIT_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_HEAD *rest" "STAILQ_ENTRY NAME"
 .Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "TYPE"
 .\"
 .Fn LIST_CLASS_ENTRY "CLASSTYPE"
@@ -195,6 +201,7 @@ lists and tail queues
 .Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME"
 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
 .Fn LIST_REPLACE "TYPE *elm" "TYPE *new" "LIST_ENTRY NAME"
+.Fn LIST_SPLIT_AFTER "LIST_HEAD *head" "TYPE *elm" "LIST_HEAD *rest" "LIST_ENTRY NAME"
 .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
 .\"
 .Fn TAILQ_CLASS_ENTRY "CLASSTYPE"
@@ -224,6 +231,7 @@ lists and tail queues
 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
 .Fn TAILQ_REPLACE "TAILQ_HEAD *head" "TYPE *elm" "TYPE *new" "TAILQ_ENTRY NAME"
+.Fn TAILQ_SPLIT_AFTER "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_HEAD *rest" "TAILQ_ENTRY NAME"
 .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME"
 .\"
 .Sh DESCRIPTION
@@ -250,6 +258,8 @@ O(1) removal of an entry from the head of the list.
 .It
 Forward traversal through the list.
 .It
+Splitting a list in two after any element in the list.
+.It
 Swapping the contents of two lists.
 .El
 .Pp
@@ -547,6 +557,17 @@ A doubly-linked list should be used if this macro is needed in
 high-usage code paths or to operate on long lists.
 .Pp
 The macro
+.Nm SLIST_SPLIT_AFTER
+splits the list referenced by
+.Fa head ,
+making
+.Fa rest
+reference the list formed by elements after
+.Fa elm
+in
+.Fa head .
+.Pp
+The macro
 .Nm SLIST_SWAP
 swaps the contents of
 .Fa head1
@@ -770,6 +791,17 @@ A doubly-linked tail queue should be used if this macro is needed in
 high-usage code paths or to operate on long tail queues.
 .Pp
 The macro
+.Nm STAILQ_SPLIT_AFTER
+splits the tail queue referenced by
+.Fa head ,
+making
+.Fa rest
+reference the tail queue formed by elements after
+.Fa elm
+in
+.Fa head .
+.Pp
+The macro
 .Nm STAILQ_SWAP
 swaps the contents of
 .Fa head1
@@ -998,6 +1030,17 @@ The element
 must not already be on a list.
 .Pp
 The macro
+.Nm LIST_SPLIT_AFTER
+splits the list referenced by
+.Fa head ,
+making
+.Fa rest
+reference the list formed by elements after
+.Fa elm
+in
+.Fa head .
+.Pp
+The macro
 .Nm LIST_SWAP
 swaps the contents of
 .Fa head1
@@ -1271,6 +1314,17 @@ The element
 must not already be on a list.
 .Pp
 The macro
+.Nm TAILQ_SPLIT_AFTER
+splits the tail queue referenced by
+.Fa head ,
+making
+.Fa rest
+reference the tail queue formed by elements after
+.Fa elm
+in
+.Fa head .
+.Pp
+The macro
 .Nm TAILQ_SWAP
 swaps the contents of
 .Fa head1
diff --git a/sys/sys/queue.h b/sys/sys/queue.h
index 70d13ee92617..91da1ec08640 100644
--- a/sys/sys/queue.h
+++ b/sys/sys/queue.h
@@ -111,6 +111,7 @@
  * _REMOVE_HEAD			+	+	+	+
  * _REMOVE			s	+	s	+
  * _REPLACE			-	+	-	+
+ * _SPLIT_AFTER			+	+	+	+
  * _SWAP			+	+	+	+
  *
  */
@@ -207,8 +208,20 @@ struct {								\
 		panic("Bad prevptr *(%p) == %p != %p",			\
 		    (prevp), *(prevp), (elm));				\
 } while (0)
+
+#define	SLIST_ASSERT_EMPTY(head) do {					\
+	if (!SLIST_EMPTY((head)))					\
+		panic("%s: slist %p is not empty", __func__, (head));	\
+} while (0)
+
+#define	SLIST_ASSERT_NONEMPTY(head) do {				\
+	if (SLIST_EMPTY((head)))					\
+		panic("%s: slist %p is empty", __func__, (head));	\
+} while (0)
 #else
 #define	QMD_SLIST_CHECK_PREVPTR(prevp, elm)
+#define	SLIST_ASSERT_EMPTY(head)
+#define	SLIST_ASSERT_NONEMPTY(head)
 #endif
 
 #define SLIST_CONCAT(head1, head2, type, field) do {			\
@@ -303,6 +316,12 @@ struct {								\
 	TRASHIT((elm)->field.sle_next);					\
 } while (0)
 
+#define	SLIST_SPLIT_AFTER(head, elm, rest, field) do {			\
+	SLIST_ASSERT_NONEMPTY((head));					\
+	SLIST_FIRST((rest)) = SLIST_NEXT((elm), field);			\
+	SLIST_NEXT((elm), field) = NULL;				\
+} while (0)
+
 #define SLIST_SWAP(head1, head2, type) do {				\
 	QUEUE_TYPEOF(type) *swap_first = SLIST_FIRST(head1);		\
 	SLIST_FIRST(head1) = SLIST_FIRST(head2);			\
@@ -355,11 +374,6 @@ struct {								\
 		    "first field address", (head), (head)->stqh_last);	\
 } while (0)
 
-#define	STAILQ_ASSERT_EMPTY(head) do {					\
-	if (!STAILQ_EMPTY((head)))					\
-		panic("stailq %p is not empty", (head));		\
-} while (0)
-
 /*
  * QMD_STAILQ_CHECK_TAIL(STAILQ_HEAD *head)
  *
@@ -370,11 +384,23 @@ struct {								\
 		panic("Stailq %p last element's next pointer is %p, "	\
 		    "not NULL", (head), *(head)->stqh_last);		\
 } while (0)
+
+#define	STAILQ_ASSERT_EMPTY(head) do {					\
+	if (!STAILQ_EMPTY((head)))					\
+		panic("%s: stailq %p is not empty", __func__, (head));	\
+} while (0)
+
+#define	STAILQ_ASSERT_NONEMPTY(head) do {				\
+	if (STAILQ_EMPTY((head)))					\
+		panic("%s: stailq %p is empty", __func__, (head));	\
+} while (0)
+
 #else
 #define	QMD_STAILQ_CHECK_EMPTY(head)
-#define	STAILQ_ASSERT_EMPTY(head)
 #define	QMD_STAILQ_CHECK_TAIL(head)
-#endif /* (_KERNEL && INVARIANTS) */
+#define	STAILQ_ASSERT_EMPTY(head)
+#define	STAILQ_ASSERT_NONEMPTY(head)
+#endif /* _KERNEL && INVARIANTS */
 
 #define	STAILQ_CONCAT(head1, head2) do {				\
 	if (!STAILQ_EMPTY((head2))) {					\
@@ -472,6 +498,20 @@ struct {								\
 		(head)->stqh_last = &STAILQ_FIRST((head));		\
 } while (0)
 
+#define	STAILQ_SPLIT_AFTER(head, elm, rest, field) do {			\
+	STAILQ_ASSERT_NONEMPTY((head));					\
+	QMD_STAILQ_CHECK_TAIL((head));					\
+	if (STAILQ_NEXT((elm), field) == NULL)				\
+		/* 'elm' is the last element in 'head'. */		\
+		STAILQ_INIT((rest));					\
+	else {								\
+		STAILQ_FIRST((rest)) = STAILQ_NEXT((elm), field);	\
+		(rest)->stqh_last = (head)->stqh_last;			\
+		STAILQ_NEXT((elm), field) = NULL;			\
+		(head)->stqh_last = &STAILQ_NEXT((elm), field);		\
+	}								\
+} while (0)
+
 #define STAILQ_SWAP(head1, head2, type) do {				\
 	QUEUE_TYPEOF(type) *swap_first = STAILQ_FIRST(head1);		\
 	QUEUE_TYPEOF(type) **swap_last = (head1)->stqh_last;		\
@@ -556,10 +596,22 @@ struct {								\
 	if (*(elm)->field.le_prev != (elm))				\
 		panic("Bad link elm %p prev->next != elm", (elm));	\
 } while (0)
+
+#define	LIST_ASSERT_EMPTY(head) do {					\
+	if (!LIST_EMPTY((head)))					\
+		panic("%s: list %p is not empty", __func__, (head));	\
+} while (0)
+
+#define	LIST_ASSERT_NONEMPTY(head) do {					\
+	if (LIST_EMPTY((head)))						\
+		panic("%s: list %p is empty", __func__, (head));	\
+} while (0)
 #else
 #define	QMD_LIST_CHECK_HEAD(head, field)
 #define	QMD_LIST_CHECK_NEXT(elm, field)
 #define	QMD_LIST_CHECK_PREV(elm, field)
+#define	LIST_ASSERT_EMPTY(head)
+#define	LIST_ASSERT_NONEMPTY(head)
 #endif /* (_KERNEL && INVARIANTS) */
 
 #define LIST_CONCAT(head1, head2, type, field) do {			\
@@ -673,6 +725,19 @@ struct {								\
 	TRASHIT(*oldprev);						\
 } while (0)
 
+#define	LIST_SPLIT_AFTER(head, elm, rest, field) do {			\
+	LIST_ASSERT_NONEMPTY((head));					\
+	if (LIST_NEXT((elm), field) == NULL)				\
+		/* 'elm' is the last element in 'head'. */		\
+		LIST_INIT((rest));					\
+	else {								\
+		LIST_FIRST((rest)) = LIST_NEXT((elm), field);		\
+		LIST_NEXT((elm), field)->field.le_prev =		\
+		    &LIST_FIRST((rest));				\
+		LIST_NEXT((elm), field) = NULL;				\
+	}								\
+} while (0)
+
 #define LIST_SWAP(head1, head2, type, field) do {			\
 	QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1);		\
 	LIST_FIRST((head1)) = LIST_FIRST((head2));			\
@@ -768,11 +833,23 @@ struct {								\
 	if (*(elm)->field.tqe_prev != (elm))				\
 		panic("Bad link elm %p prev->next != elm", (elm));	\
 } while (0)
+
+#define	TAILQ_ASSERT_EMPTY(head) do {					\
+	if (!TAILQ_EMPTY((head)))					\
+		panic("%s: tailq %p is not empty", __func__, (head));	\
+} while (0)
+
+#define	TAILQ_ASSERT_NONEMPTY(head) do {				\
+	if (TAILQ_EMPTY((head)))					\
+		panic("%s: tailq %p is empty", __func__, (head));	\
+} while (0)
 #else
 #define	QMD_TAILQ_CHECK_HEAD(head, field)
 #define	QMD_TAILQ_CHECK_TAIL(head, headname)
 #define	QMD_TAILQ_CHECK_NEXT(elm, field)
 #define	QMD_TAILQ_CHECK_PREV(elm, field)
+#define	TAILQ_ASSERT_EMPTY(head)
+#define	TAILQ_ASSERT_NONEMPTY(head)
 #endif /* (_KERNEL && INVARIANTS) */
 
 #define	TAILQ_CONCAT(head1, head2, field) do {				\
@@ -948,6 +1025,23 @@ struct {								\
 	QMD_TRACE_ELEM(&(elm)->field);					\
 } while (0)
 
+#define	TAILQ_SPLIT_AFTER(head, elm, rest, field) do {			\
+	TAILQ_ASSERT_NONEMPTY((head));					\
+	QMD_TAILQ_CHECK_TAIL((head), field);				\
+	if (TAILQ_NEXT((elm), field) == NULL)				\
+		/* 'elm' is the last element in 'head'. */		\
+		TAILQ_INIT((rest));					\
+	else {								\
+		TAILQ_FIRST((rest)) = TAILQ_NEXT((elm), field);		\
+		(rest)->tqh_last = (head)->tqh_last;			\
+		TAILQ_NEXT((elm), field)->field.tqe_prev =		\
+		    &TAILQ_FIRST((rest));				\
+									\
+		TAILQ_NEXT((elm), field) = NULL;			\
+		(head)->tqh_last = &TAILQ_NEXT((elm), field);		\
+	}								\
+} while (0)
+
 #define TAILQ_SWAP(head1, head2, type, field) do {			\
 	QUEUE_TYPEOF(type) *swap_first = (head1)->tqh_first;		\
 	QUEUE_TYPEOF(type) **swap_last = (head1)->tqh_last;		\