From nobody Thu May 1 19:51:39 2025 X-Original-To: dev-commits-src-branches@mlmmj.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mlmmj.nyi.freebsd.org (Postfix) with ESMTP id 4ZpPnm1GYMz5vf37; Thu, 01 May 2025 19:51:40 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from mxrelay.nyi.freebsd.org (mxrelay.nyi.freebsd.org [IPv6:2610:1c1:1:606c::19:3]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256 client-signature RSA-PSS (4096 bits) client-digest SHA256) (Client CN "mxrelay.nyi.freebsd.org", Issuer "R11" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 4ZpPnl3tFRz46xv; Thu, 01 May 2025 19:51:39 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1746129099; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=QW4I3dAwUYr6A0ePF5yHiBWtsDXZ+8z4pF1KSC9SMIE=; b=xcQ0VPFNcFtnxGXOpQkdWvBybGmSC7SK6MoJfa+FJ9Gb0RVPSzbmpPsF3ihgIcwTRSnVHZ /DONKx4wbYjvJmE9UPbOcMXWwDfu4yYMafGiNBDn8d0/hE6Bzfe+s2QoX9MoQSJozQbG9Z I0DabxQzHJoUvlLccN+/IKHOM/u2/rdstrezQZkMuvVfn+6OA+7XveNZ6fE9nEtdxafdj8 elwoGwSx7swmrL8bupT3lvJRgXw1Ro/vatanKcLLndu1t7sLEspQ7SYx8+r618aAU+qeGx DGLwjR3gwp+Qcx/Su94JmbWdZMFu8P9JWO34mfEi3yevnDTVpvXS4ezyiEkMaw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1746129099; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=QW4I3dAwUYr6A0ePF5yHiBWtsDXZ+8z4pF1KSC9SMIE=; b=wzS0bxr4UNYo/wKFPSGyd5gDhupAoL4AFjJheSKHj2pRKgdVnEiquHkwq/AmGPwVyl4WLi DP73NR33mPrLGqQq4TeEbEOAZlbwCJln0gBiupy2Y3wABM+mABaQCT2VVFGQZYiTo+hTx+ FZTVH8XFkKROEqyWSC5IKcb+UE/87Urm5BL6etb8TImihihM9y8F1ZBS1XhX6lcvdNJ3/0 uJRA7t6rBDnDVqCmtr1RnNmdLHsdQUu5IJXGwMuPjOCUa/QsWZc+gscpcdh7lsJEtA2zyf gA/lifvaEpOij2ea/Veu/Q9J4FX1g+pwPTP3pwfly3OPE/3Gkp4FYIi7IWHxDA== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1746129099; a=rsa-sha256; cv=none; b=DWSmlk7N7lqayDro25wntO4TfzTsgaUXjOEHbgz0iTxQaHKEk/lHD2dFd1kFsR9Wkl2yie l/yibbdr1BdXXGVJZdrLoX42IEoB7omOeK+owq7dX9shNNrRj5y9CsZdCYgwxLrnJAM3Ea S+XNwjB6uPo6Y0RONWqP8E1K1zbKVbp7RcEQWfePF7qL/QxEJNoNg/xff5Do1ERturNwHJ Dhg7YChYEmsDKeGO4K8wQYvi3utU1+d/yloSQAtxmR7+D7NZrV6ge02jvLyoXVZDHlrCU1 0MDxPjgqvXI5QzjGca2upvR93y/nIwYhdzjAX9+JFVU/ZDdNFfpUcdrHL8vu1A== ARC-Authentication-Results: i=1; mx1.freebsd.org; none Received: from gitrepo.freebsd.org (gitrepo.freebsd.org [IPv6:2610:1c1:1:6068::e6a:5]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (Client did not present a certificate) by mxrelay.nyi.freebsd.org (Postfix) with ESMTPS id 4ZpPnl3GKvzhwC; Thu, 01 May 2025 19:51:39 +0000 (UTC) (envelope-from git@FreeBSD.org) Received: from gitrepo.freebsd.org ([127.0.1.44]) by gitrepo.freebsd.org (8.18.1/8.18.1) with ESMTP id 541JpddK068577; Thu, 1 May 2025 19:51:39 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 541JpdY8068574; Thu, 1 May 2025 19:51:39 GMT (envelope-from git) Date: Thu, 1 May 2025 19:51:39 GMT Message-Id: <202505011951.541JpdY8068574@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-branches@FreeBSD.org From: Olivier Certner Subject: git: c4ee6d4acb90 - stable/14 - queue(3): New *_SPLIT_AFTER(), *_ASSERT_EMPTY(), *_ASSERT_NONEMPTY() List-Id: Commits to the stable branches of the FreeBSD src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-branches List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-branches@freebsd.org Sender: owner-dev-commits-src-branches@FreeBSD.org MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit X-Git-Committer: olce X-Git-Repository: src X-Git-Refname: refs/heads/stable/14 X-Git-Reftype: branch X-Git-Commit: c4ee6d4acb90a45367227655673476cbbb5e962b Auto-Submitted: auto-generated The branch stable/14 has been updated by olce: URL: https://cgit.FreeBSD.org/src/commit/?id=c4ee6d4acb90a45367227655673476cbbb5e962b commit c4ee6d4acb90a45367227655673476cbbb5e962b Author: Olivier Certner AuthorDate: 2025-02-28 09:18:48 +0000 Commit: Olivier Certner 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; \