From nobody Mon Apr 28 12:23:30 2025 X-Original-To: dev-commits-src-main@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 4ZmN034wQJz5vJM2; Mon, 28 Apr 2025 12:23:31 +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 4ZmN030yTsz3g1r; Mon, 28 Apr 2025 12:23:31 +0000 (UTC) (envelope-from git@FreeBSD.org) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1745843011; 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=17NT04aqee3WOl7+5snsCd76vBJyRq08s1gjWvwti5Y=; b=JpJcm5MyAGkYj4Yrj2Iaty4gkGVVjULmJKEowa0fiWZSCK3xjks4U0+mprX1Jk32QDceBy qwD5KxgRpBo0iQIi6x8oL4Cl003gkHrjn3OY2EQCdk59pYDqBkgbgXi223wFRs7ZxKPZ9z +2vl0nrUSTa6ASkqRtdLeMW+JwHpgtrNdQKu6D2Rtq3/gQsEsqJJwX5vS1h3jF9Vws9fzu sxzDic9tfSIcoOlNyMkjwm9xQZRt+PNg+d9gbeJ14mYKTwPG4nUtI06E1DHQ+YHVDWqZkL SyRnSEp52lExiSnA42eqczrdgd5iI5CA+IWwO/B9u80FyfGtV0XysS1PyX9luQ== ARC-Seal: i=1; s=dkim; d=freebsd.org; t=1745843011; a=rsa-sha256; cv=none; b=v38AJbF2fve7NeScNtkpe+M1QM9vLjbhdamt8R7jqTBXDLa8/WfWjZbr5u2zumKI2CD9VD VyzaWN3OTgJmzWqIB3IoLLCCaiPsfKsMWY/e1+xBra8JBPNsZnT44BZkoi8f+w5nfirIz0 +j/xmxu8h0u78Bo5V3QuiTI6tiUf0UZRwd8tG6Txijxql03r+5C+/TGXrU4AKJTrSM0Wsv r3l2qi3CuhVqiePOdjJ0seT6tcRpE6IOnUBjdJbw5STcAiU2+UcIAqEuvjLY2qk/w6YvQ4 n2uq4J5rWdhx+2GOfgD+GW16ARLnnnENvXHytBtxe4wYl/BaQphxAXSffZ1ovQ== ARC-Authentication-Results: i=1; mx1.freebsd.org; none ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=freebsd.org; s=dkim; t=1745843011; 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=17NT04aqee3WOl7+5snsCd76vBJyRq08s1gjWvwti5Y=; b=XRVlvE0l6y43WQsnhwLC6uP4UWXgjtes2Dv9jLaIGyT6Mp+ENISdEjrzBnqSz0fZ1HWT8P rHIsDBP4XdGVITyrq/cfmEku/5LIHi78DjTz30f4mXE7CDUYZIsdKunmWZiUNTFngXmSVz qFGMHv/lrbxptaW8Vhc/zqBPD+UeJ7HTXbvxcI00uWJnJuzQkIcl4JZt2w/kEP0LKz7dys ZkedQzXxMUon273e2KqUYwdpcYMLqWRW2tAAriML/X5DlDBdgeNk6lzab4cp2+rAHdbfBU LMMk6mrl7XJmc0hDoVbXXUxgmNwLZteQIMBSXID6TyM54o5LTzQPforEFtEWlA== 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 4ZmN030F50zbkZ; Mon, 28 Apr 2025 12:23:31 +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 53SCNUHX025474; Mon, 28 Apr 2025 12:23:30 GMT (envelope-from git@gitrepo.freebsd.org) Received: (from git@localhost) by gitrepo.freebsd.org (8.18.1/8.18.1/Submit) id 53SCNUvO025471; Mon, 28 Apr 2025 12:23:30 GMT (envelope-from git) Date: Mon, 28 Apr 2025 12:23:30 GMT Message-Id: <202504281223.53SCNUvO025471@gitrepo.freebsd.org> To: src-committers@FreeBSD.org, dev-commits-src-all@FreeBSD.org, dev-commits-src-main@FreeBSD.org From: Olivier Certner Subject: git: c02880233949 - main - queue(3): New *_SPLIT_AFTER(), *_ASSERT_EMPTY(), *_ASSERT_NONEMPTY() List-Id: Commit messages for the main branch of the src repository List-Archive: https://lists.freebsd.org/archives/dev-commits-src-main List-Help: List-Post: List-Subscribe: List-Unsubscribe: X-BeenThere: dev-commits-src-main@freebsd.org Sender: owner-dev-commits-src-main@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/main X-Git-Reftype: branch X-Git-Commit: c02880233949b01fcfb2067962596f5c05553471 Auto-Submitted: auto-generated The branch main has been updated by olce: URL: https://cgit.FreeBSD.org/src/commit/?id=c02880233949b01fcfb2067962596f5c05553471 commit c02880233949b01fcfb2067962596f5c05553471 Author: Olivier Certner AuthorDate: 2025-02-28 09:18:48 +0000 Commit: Olivier Certner 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; \