git: c02880233949 - main - queue(3): New *_SPLIT_AFTER(), *_ASSERT_EMPTY(), *_ASSERT_NONEMPTY()
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
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; \