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