git: c4ee6d4acb90 - stable/14 - queue(3): New *_SPLIT_AFTER(), *_ASSERT_EMPTY(), *_ASSERT_NONEMPTY()
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Thu, 01 May 2025 19:51:39 UTC
The branch stable/14 has been updated by olce:
URL: https://cgit.FreeBSD.org/src/commit/?id=c4ee6d4acb90a45367227655673476cbbb5e962b
commit c4ee6d4acb90a45367227655673476cbbb5e962b
Author: Olivier Certner <olce@FreeBSD.org>
AuthorDate: 2025-02-28 09:18:48 +0000
Commit: Olivier Certner <olce@FreeBSD.org>
CommitDate: 2025-05-01 19:37:04 +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)
(cherry picked from commit c02880233949b01fcfb2067962596f5c05553471)
---
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 9fc57a59cf11..6fd3d7f2e0f9 100644
--- a/share/man/man3/queue.3
+++ b/share/man/man3/queue.3
@@ -51,6 +51,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 ,
@@ -74,6 +75,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 ,
@@ -96,6 +98,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 ,
@@ -124,6 +127,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
@@ -150,6 +154,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"
@@ -174,6 +179,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"
@@ -197,6 +203,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"
@@ -226,6 +233,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
@@ -252,6 +260,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
@@ -549,6 +559,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
@@ -772,6 +793,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
@@ -1000,6 +1032,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
@@ -1273,6 +1316,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 dd3956d7c111..97af11876232 100644
--- a/sys/sys/queue.h
+++ b/sys/sys/queue.h
@@ -113,6 +113,7 @@
* _REMOVE_HEAD + + + +
* _REMOVE s + s +
* _REPLACE - + - +
+ * _SPLIT_AFTER + + + +
* _SWAP + + + +
*
*/
@@ -209,8 +210,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 { \
@@ -305,6 +318,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); \
@@ -357,11 +376,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)
*
@@ -372,11 +386,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))) { \
@@ -474,6 +500,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; \
@@ -558,10 +598,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 { \
@@ -675,6 +727,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)); \
@@ -770,11 +835,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 { \
@@ -950,6 +1027,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; \