git: 43e0ae562921 - stable/14 - sys/queue.h: Add {LIST,TAILQ}_REPLACE().
- Go to: [ bottom of page ] [ top of archives ] [ this month ]
Date: Mon, 15 Apr 2024 10:57:02 UTC
The branch stable/14 has been updated by des:
URL: https://cgit.FreeBSD.org/src/commit/?id=43e0ae5629213db428a017d5d57afca652d4c53c
commit 43e0ae5629213db428a017d5d57afca652d4c53c
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-15 10:54:59 +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
(cherry picked from commit 7f479dee48973541da8c869b888b953161301c3b)
sys/queue.h: Whitespace cleanup.
MFC after: 1 week
Sponsored by: Klara, Inc.
Differential Revision: https://reviews.freebsd.org/D44678
(cherry picked from commit 69fd60f1ead5a86eeb0b18847dd71f7ae3fce4a0)
---
share/man/man3/Makefile | 2 ++
share/man/man3/queue.3 | 34 ++++++++++++++++--
sys/sys/queue.h | 94 +++++++++++++++++++++++++++++++++----------------
3 files changed, 98 insertions(+), 32 deletions(-)
diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile
index 7fff5eedd5fb..2b2d7516c11f 100644
--- a/share/man/man3/Makefile
+++ b/share/man/man3/Makefile
@@ -216,6 +216,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 \
@@ -284,6 +285,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 3dc21be032ea..ea395d7ffe7f 100644
--- a/share/man/man3/queue.3
+++ b/share/man/man3/queue.3
@@ -27,7 +27,7 @@
.\"
.\" @(#)queue.3 8.2 (Berkeley) 1/24/94
.\"
-.Dd September 8, 2016
+.Dd April 8, 2024
.Dt QUEUE 3
.Os
.Sh NAME
@@ -92,6 +92,7 @@
.Nm LIST_NEXT ,
.Nm LIST_PREV ,
.Nm LIST_REMOVE ,
+.Nm LIST_REPLACE ,
.Nm LIST_SWAP ,
.Nm TAILQ_CLASS_ENTRY ,
.Nm TAILQ_CLASS_HEAD ,
@@ -118,6 +119,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
@@ -187,6 +189,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"
@@ -214,6 +217,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
@@ -965,6 +969,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
@@ -1223,6 +1238,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
@@ -1237,7 +1263,7 @@ struct entry {
...
TAILQ_ENTRY(entry) entries; /* Tail queue. */
...
-} *n1, *n2, *n3, *np;
+} *n1, *n2, *n3, *n4, *np;
TAILQ_INIT(&head); /* Initialize the queue. */
@@ -1255,6 +1281,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 47d85121e317..9bdfd497b165 100644
--- a/sys/sys/queue.h
+++ b/sys/sys/queue.h
@@ -112,6 +112,7 @@
* _REMOVE_AFTER + - + -
* _REMOVE_HEAD + + + +
* _REMOVE s + s +
+ * _REPLACE - + - +
* _SWAP + + + +
*
*/
@@ -395,9 +396,9 @@ struct { \
(head)->stqh_last = &STAILQ_NEXT((elm), field); \
} while (0)
-#define STAILQ_LAST(head, type, field) \
- (STAILQ_EMPTY((head)) ? NULL : \
- __containerof((head)->stqh_last, \
+#define STAILQ_LAST(head, type, field) \
+ (STAILQ_EMPTY((head)) ? NULL : \
+ __containerof((head)->stqh_last, \
QUEUE_TYPEOF(type), field.stqe_next))
#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
@@ -500,7 +501,7 @@ struct { \
if (LIST_NEXT((elm), field) != NULL && \
LIST_NEXT((elm), field)->field.le_prev != \
&((elm)->field.le_next)) \
- panic("Bad link elm %p next->prev != elm", (elm)); \
+ panic("Bad link elm %p next->prev != elm", (elm)); \
} while (0)
/*
@@ -518,21 +519,21 @@ struct { \
#define QMD_LIST_CHECK_PREV(elm, field)
#endif /* (_KERNEL && INVARIANTS) */
-#define LIST_CONCAT(head1, head2, type, field) do { \
- QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \
- if (curelm == NULL) { \
- if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \
- LIST_FIRST(head2)->field.le_prev = \
- &LIST_FIRST((head1)); \
- LIST_INIT(head2); \
- } \
- } else if (LIST_FIRST(head2) != NULL) { \
- while (LIST_NEXT(curelm, field) != NULL) \
- curelm = LIST_NEXT(curelm, field); \
- LIST_NEXT(curelm, field) = LIST_FIRST(head2); \
- LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field); \
- LIST_INIT(head2); \
- } \
+#define LIST_CONCAT(head1, head2, type, field) do { \
+ QUEUE_TYPEOF(type) *curelm = LIST_FIRST(head1); \
+ if (curelm == NULL) { \
+ if ((LIST_FIRST(head1) = LIST_FIRST(head2)) != NULL) { \
+ LIST_FIRST(head2)->field.le_prev = \
+ &LIST_FIRST((head1)); \
+ LIST_INIT(head2); \
+ } \
+ } else if (LIST_FIRST(head2) != NULL) { \
+ while (LIST_NEXT(curelm, field) != NULL) \
+ curelm = LIST_NEXT(curelm, field); \
+ LIST_NEXT(curelm, field) = LIST_FIRST(head2); \
+ LIST_FIRST(head2)->field.le_prev = &LIST_NEXT(curelm, field);\
+ LIST_INIT(head2); \
+ } \
} while (0)
#define LIST_EMPTY(head) ((head)->lh_first == NULL)
@@ -590,12 +591,12 @@ struct { \
#define LIST_NEXT(elm, field) ((elm)->field.le_next)
-#define LIST_PREV(elm, head, type, field) \
- ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \
- __containerof((elm)->field.le_prev, \
+#define LIST_PREV(elm, head, type, field) \
+ ((elm)->field.le_prev == &LIST_FIRST((head)) ? NULL : \
+ __containerof((elm)->field.le_prev, \
QUEUE_TYPEOF(type), field.le_next))
-#define LIST_REMOVE_HEAD(head, field) \
+#define LIST_REMOVE_HEAD(head, field) \
LIST_REMOVE(LIST_FIRST(head), field)
#define LIST_REMOVE(elm, field) do { \
@@ -604,13 +605,28 @@ struct { \
QMD_LIST_CHECK_NEXT(elm, field); \
QMD_LIST_CHECK_PREV(elm, field); \
if (LIST_NEXT((elm), field) != NULL) \
- LIST_NEXT((elm), field)->field.le_prev = \
+ LIST_NEXT((elm), field)->field.le_prev = \
(elm)->field.le_prev; \
*(elm)->field.le_prev = LIST_NEXT((elm), field); \
TRASHIT(*oldnext); \
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)); \
@@ -681,7 +697,7 @@ struct { \
*/
#define QMD_TAILQ_CHECK_TAIL(head, field) do { \
if (*(head)->tqh_last != NULL) \
- panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
+ panic("Bad tailq NEXT(%p->tqh_last) != NULL", (head)); \
} while (0)
/*
@@ -763,7 +779,7 @@ struct { \
(var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
(var) = (tvar))
-#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar) \
+#define TAILQ_FOREACH_REVERSE_FROM_SAFE(var, head, headname, field, tvar)\
for ((var) = ((var) ? (var) : TAILQ_LAST((head), headname)); \
(var) && ((tvar) = TAILQ_PREV((var), headname, field), 1); \
(var) = (tvar))
@@ -777,7 +793,7 @@ struct { \
#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
QMD_TAILQ_CHECK_NEXT(listelm, field); \
if ((TAILQ_NEXT((elm), field) = TAILQ_NEXT((listelm), field)) != NULL)\
- TAILQ_NEXT((elm), field)->field.tqe_prev = \
+ TAILQ_NEXT((elm), field)->field.tqe_prev = \
&TAILQ_NEXT((elm), field); \
else { \
(head)->tqh_last = &TAILQ_NEXT((elm), field); \
@@ -832,7 +848,7 @@ struct { \
* the previous element. FAST is very useful for instances when
* you may want to prefetch the last data element.
*/
-#define TAILQ_LAST_FAST(head, type, field) \
+#define TAILQ_LAST_FAST(head, type, field) \
(TAILQ_EMPTY(head) ? NULL : __containerof((head)->tqh_last, QUEUE_TYPEOF(type), field.tqe_next))
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
@@ -844,7 +860,7 @@ struct { \
((elm)->field.tqe_prev == &(head)->tqh_first ? NULL : \
__containerof((elm)->field.tqe_prev, QUEUE_TYPEOF(type), field.tqe_next))
-#define TAILQ_REMOVE_HEAD(head, field) \
+#define TAILQ_REMOVE_HEAD(head, field) \
TAILQ_REMOVE(head, TAILQ_FIRST(head), field)
#define TAILQ_REMOVE(head, elm, field) do { \
@@ -853,7 +869,7 @@ struct { \
QMD_TAILQ_CHECK_NEXT(elm, field); \
QMD_TAILQ_CHECK_PREV(elm, field); \
if ((TAILQ_NEXT((elm), field)) != NULL) \
- TAILQ_NEXT((elm), field)->field.tqe_prev = \
+ TAILQ_NEXT((elm), field)->field.tqe_prev = \
(elm)->field.tqe_prev; \
else { \
(head)->tqh_last = (elm)->field.tqe_prev; \
@@ -865,6 +881,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; \