git: 7f479dee4897 - main - sys/queue.h: Add {LIST,TAILQ}_REPLACE().

From: Dag-Erling Smørgrav <des_at_FreeBSD.org>
Date: Mon, 08 Apr 2024 18:21:17 UTC
The branch main has been updated by des:

URL: https://cgit.FreeBSD.org/src/commit/?id=7f479dee48973541da8c869b888b953161301c3b

commit 7f479dee48973541da8c869b888b953161301c3b
Author:     Dag-Erling Smørgrav <des@FreeBSD.org>
AuthorDate: 2024-04-08 18:16:40 +0000
Commit:     Dag-Erling Smørgrav <des@FreeBSD.org>
CommitDate: 2024-04-08 18:16:46 +0000

    sys/queue.h: Add {LIST,TAILQ}_REPLACE().
    
    MFC after:      1 week
    Obtained from:  NetBSD
    Sponsored by:   Klara, Inc.
    Reviewed by:    cperciva, imp
    Differential Revision:  https://reviews.freebsd.org/D44679
---
 share/man/man3/Makefile |  2 ++
 share/man/man3/queue.3  | 34 ++++++++++++++++++++++++++++++++--
 sys/sys/queue.h         | 34 ++++++++++++++++++++++++++++++++++
 3 files changed, 68 insertions(+), 2 deletions(-)

diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile
index b1f9cc087837..d82ff2bccd51 100644
--- a/share/man/man3/Makefile
+++ b/share/man/man3/Makefile
@@ -215,6 +215,7 @@ MLINKS+=	queue.3 LIST_CLASS_ENTRY.3 \
 		queue.3 LIST_NEXT.3 \
 		queue.3 LIST_PREV.3 \
 		queue.3 LIST_REMOVE.3 \
+		queue.3 LIST_REPLACE.3 \
 		queue.3 LIST_SWAP.3 \
 		queue.3 SLIST_CLASS_ENTRY.3 \
 		queue.3 SLIST_CLASS_HEAD.3 \
@@ -283,6 +284,7 @@ MLINKS+=	queue.3 LIST_CLASS_ENTRY.3 \
 		queue.3 TAILQ_NEXT.3 \
 		queue.3 TAILQ_PREV.3 \
 		queue.3 TAILQ_REMOVE.3 \
+		queue.3 TAILQ_REPLACE.3 \
 		queue.3 TAILQ_SWAP.3
 MLINKS+=	stats.3 stats_tpl_alloc.3 \
 		stats.3 stats_tpl_fetch_allocid.3 \
diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3
index 41d88cb6ffce..be890fd2cc88 100644
--- a/share/man/man3/queue.3
+++ b/share/man/man3/queue.3
@@ -25,7 +25,7 @@
 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 .\" SUCH DAMAGE.
 .\"
-.Dd September 8, 2016
+.Dd April 8, 2024
 .Dt QUEUE 3
 .Os
 .Sh NAME
@@ -90,6 +90,7 @@
 .Nm LIST_NEXT ,
 .Nm LIST_PREV ,
 .Nm LIST_REMOVE ,
+.Nm LIST_REPLACE ,
 .Nm LIST_SWAP ,
 .Nm TAILQ_CLASS_ENTRY ,
 .Nm TAILQ_CLASS_HEAD ,
@@ -116,6 +117,7 @@
 .Nm TAILQ_NEXT ,
 .Nm TAILQ_PREV ,
 .Nm TAILQ_REMOVE ,
+.Nm TAILQ_REPLACE ,
 .Nm TAILQ_SWAP
 .Nd implementations of singly-linked lists, singly-linked tail queues,
 lists and tail queues
@@ -185,6 +187,7 @@ lists and tail queues
 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
 .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_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
 .\"
 .Fn TAILQ_CLASS_ENTRY "CLASSTYPE"
@@ -212,6 +215,7 @@ lists and tail queues
 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
 .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_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME"
 .\"
 .Sh DESCRIPTION
@@ -963,6 +967,17 @@ removes the element
 from the list.
 .Pp
 The macro
+.Fn LIST_REPLACE
+replaces the element
+.Fa elm
+with
+.Fa new
+in the list.
+The element
+.Fa new
+must not already be on a list.
+.Pp
+The macro
 .Nm LIST_SWAP
 swaps the contents of
 .Fa head1
@@ -1221,6 +1236,17 @@ removes the element
 from the tail queue.
 .Pp
 The macro
+.Fn TAILQ_REPLACE
+replaces the element
+.Fa elm
+with
+.Fa new
+in the tail queue.
+The element
+.Fa new
+must not already be on a list.
+.Pp
+The macro
 .Nm TAILQ_SWAP
 swaps the contents of
 .Fa head1
@@ -1235,7 +1261,7 @@ struct entry {
 	...
 	TAILQ_ENTRY(entry) entries;	/* Tail queue. */
 	...
-} *n1, *n2, *n3, *np;
+} *n1, *n2, *n3, *n4, *np;
 
 TAILQ_INIT(&head);			/* Initialize the queue. */
 
@@ -1253,6 +1279,10 @@ TAILQ_INSERT_BEFORE(n2, n3, entries);
 
 TAILQ_REMOVE(&head, n2, entries);	/* Deletion. */
 free(n2);
+
+n4 = malloc(sizeof(struct entry));	/* Replacement. */
+TAILQ_REPLACE(&head, n3, n4, entries);
+free(n3);
 					/* Forward traversal. */
 TAILQ_FOREACH(np, &head, entries)
 	np-> ...
diff --git a/sys/sys/queue.h b/sys/sys/queue.h
index 2b11d54cdd45..0479d780fd85 100644
--- a/sys/sys/queue.h
+++ b/sys/sys/queue.h
@@ -110,6 +110,7 @@
  * _REMOVE_AFTER		+	-	+	-
  * _REMOVE_HEAD			+	+	+	+
  * _REMOVE			s	+	s	+
+ * _REPLACE			-	+	-	+
  * _SWAP			+	+	+	+
  *
  */
@@ -609,6 +610,21 @@ struct {								\
 	TRASHIT(*oldprev);						\
 } while (0)
 
+#define LIST_REPLACE(elm, elm2, field) do {				\
+	QMD_SAVELINK(oldnext, (elm)->field.le_next);			\
+	QMD_SAVELINK(oldprev, (elm)->field.le_prev);			\
+	QMD_LIST_CHECK_NEXT(elm, field);				\
+	QMD_LIST_CHECK_PREV(elm, field);				\
+	LIST_NEXT((elm2), field) = LIST_NEXT((elm), field);		\
+	if (LIST_NEXT((elm2), field) != NULL)				\
+		LIST_NEXT((elm2), field)->field.le_prev =		\
+		    &(elm2)->field.le_next;				\
+	(elm2)->field.le_prev = (elm)->field.le_prev;			\
+	*(elm2)->field.le_prev = (elm2);				\
+	TRASHIT(*oldnext);						\
+	TRASHIT(*oldprev);						\
+} while (0)
+
 #define LIST_SWAP(head1, head2, type, field) do {			\
 	QUEUE_TYPEOF(type) *swap_tmp = LIST_FIRST(head1);		\
 	LIST_FIRST((head1)) = LIST_FIRST((head2));			\
@@ -863,6 +879,24 @@ struct {								\
 	QMD_TRACE_ELEM(&(elm)->field);					\
 } while (0)
 
+#define TAILQ_REPLACE(head, elm, elm2, field) do {			\
+	QMD_SAVELINK(oldnext, (elm)->field.tqe_next);			\
+	QMD_SAVELINK(oldprev, (elm)->field.tqe_prev);			\
+	QMD_TAILQ_CHECK_NEXT(elm, field);				\
+	QMD_TAILQ_CHECK_PREV(elm, field);				\
+	TAILQ_NEXT((elm2), field) = TAILQ_NEXT((elm), field);		\
+	if (TAILQ_NEXT((elm2), field) != TAILQ_END(head))		\
+                TAILQ_NEXT((elm2), field)->field.tqe_prev =		\
+                    &(elm2)->field.tqe_next;				\
+        else								\
+                (head)->tqh_last = &(elm2)->field.tqe_next;		\
+        (elm2)->field.tqe_prev = (elm)->field.tqe_prev;			\
+        *(elm2)->field.tqe_prev = (elm2);				\
+	TRASHIT(*oldnext);						\
+	TRASHIT(*oldprev);						\
+	QMD_TRACE_ELEM(&(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;		\