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; \