aboutsummaryrefslogtreecommitdiff
path: root/share/man/man3/queue.3
diff options
context:
space:
mode:
Diffstat (limited to 'share/man/man3/queue.3')
-rw-r--r--share/man/man3/queue.3180
1 files changed, 151 insertions, 29 deletions
diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3
index be890fd2cc88..79c8d92decbe 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 April 8, 2024
+.Dd April 28, 2025
.Dt QUEUE 3
.Os
.Sh NAME
@@ -33,6 +33,7 @@
.Nm SLIST_CLASS_HEAD ,
.Nm SLIST_CONCAT ,
.Nm SLIST_EMPTY ,
+.Nm SLIST_EMPTY_ATOMIC ,
.Nm SLIST_ENTRY ,
.Nm SLIST_FIRST ,
.Nm SLIST_FOREACH ,
@@ -48,11 +49,13 @@
.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 ,
.Nm STAILQ_CONCAT ,
.Nm STAILQ_EMPTY ,
+.Nm STAILQ_EMPTY_ATOMIC ,
.Nm STAILQ_ENTRY ,
.Nm STAILQ_FIRST ,
.Nm STAILQ_FOREACH ,
@@ -70,11 +73,14 @@
.Nm STAILQ_REMOVE ,
.Nm STAILQ_REMOVE_AFTER ,
.Nm STAILQ_REMOVE_HEAD ,
+.Nm STAILQ_REVERSE ,
+.Nm STAILQ_SPLIT_AFTER ,
.Nm STAILQ_SWAP ,
.Nm LIST_CLASS_ENTRY ,
.Nm LIST_CLASS_HEAD ,
.Nm LIST_CONCAT ,
.Nm LIST_EMPTY ,
+.Nm LIST_EMPTY_ATOMIC ,
.Nm LIST_ENTRY ,
.Nm LIST_FIRST ,
.Nm LIST_FOREACH ,
@@ -91,11 +97,13 @@
.Nm LIST_PREV ,
.Nm LIST_REMOVE ,
.Nm LIST_REPLACE ,
+.Nm LIST_SPLIT_AFTER ,
.Nm LIST_SWAP ,
.Nm TAILQ_CLASS_ENTRY ,
.Nm TAILQ_CLASS_HEAD ,
.Nm TAILQ_CONCAT ,
.Nm TAILQ_EMPTY ,
+.Nm TAILQ_EMPTY_ATOMIC ,
.Nm TAILQ_ENTRY ,
.Nm TAILQ_FIRST ,
.Nm TAILQ_FOREACH ,
@@ -118,6 +126,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
@@ -128,6 +137,7 @@ lists and tail queues
.Fn SLIST_CLASS_HEAD "HEADNAME" "CLASSTYPE"
.Fn SLIST_CONCAT "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" "SLIST_ENTRY NAME"
.Fn SLIST_EMPTY "SLIST_HEAD *head"
+.Fn SLIST_EMPTY_ATOMIC "SLIST_HEAD *head"
.Fn SLIST_ENTRY "TYPE"
.Fn SLIST_FIRST "SLIST_HEAD *head"
.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
@@ -143,12 +153,14 @@ 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"
.Fn STAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE"
.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
.Fn STAILQ_EMPTY "STAILQ_HEAD *head"
+.Fn STAILQ_EMPTY_ATOMIC "STAILQ_HEAD *head"
.Fn STAILQ_ENTRY "TYPE"
.Fn STAILQ_FIRST "STAILQ_HEAD *head"
.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
@@ -166,12 +178,15 @@ 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_REVERSE "STAILQ_HEAD *head" "TYPE" "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"
.Fn LIST_CLASS_HEAD "HEADNAME" "CLASSTYPE"
.Fn LIST_CONCAT "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
.Fn LIST_EMPTY "LIST_HEAD *head"
+.Fn LIST_EMPTY_ATOMIC "LIST_HEAD *head"
.Fn LIST_ENTRY "TYPE"
.Fn LIST_FIRST "LIST_HEAD *head"
.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
@@ -188,12 +203,14 @@ 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"
.Fn TAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE"
.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
.Fn TAILQ_EMPTY "TAILQ_HEAD *head"
+.Fn TAILQ_EMPTY_ATOMIC "TAILQ_HEAD *head"
.Fn TAILQ_ENTRY "TYPE"
.Fn TAILQ_FIRST "TAILQ_HEAD *head"
.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
@@ -216,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
@@ -242,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
@@ -425,6 +445,10 @@ high-usage code paths or to operate on long lists.
The macro
.Nm SLIST_EMPTY
evaluates to true if there are no elements in the list.
+The
+.Nm SLIST_EMPTY_ATOMIC
+variant has the same behavior, but can be safely used in contexts where it is
+possible that a different thread is concurrently updating the list.
.Pp
The macro
.Nm SLIST_ENTRY
@@ -535,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
@@ -633,6 +668,10 @@ removing all entries from the former.
The macro
.Nm STAILQ_EMPTY
evaluates to true if there are no items on the tail queue.
+The
+.Nm STAILQ_EMPTY_ATOMIC
+variant has the same behavior, but can be safely used in contexts where it is
+possible that a different thread is concurrently updating the queue.
.Pp
The macro
.Nm STAILQ_ENTRY
@@ -754,6 +793,21 @@ 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_REVERSE
+reverses the queue in place.
+.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
@@ -866,6 +920,10 @@ high-usage code paths or to operate on long lists.
The macro
.Nm LIST_EMPTY
evaluates to true if there are no elements in the list.
+The
+.Nm LIST_EMPTY_ATOMIC
+variant has the same behavior, but can be safely used in contexts where it is
+possible that a different thread is concurrently updating the list.
.Pp
The macro
.Nm LIST_ENTRY
@@ -978,6 +1036,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
@@ -1084,6 +1153,10 @@ removing all entries from the former.
The macro
.Nm TAILQ_EMPTY
evaluates to true if there are no items on the tail queue.
+The
+.Nm TAILQ_EMPTY_ATOMIC
+variant has the same behavior, but can be safely used in contexts where it is
+possible that a different thread is concurrently updating the queue.
.Pp
The macro
.Nm TAILQ_ENTRY
@@ -1247,6 +1320,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
@@ -1312,49 +1396,87 @@ while (n1 != NULL) {
TAILQ_INIT(&head);
.Ed
.Sh DIAGNOSTICS
-When debugging
-.Nm queue(3) ,
-it can be useful to trace queue changes.
-To enable tracing, define the macro
-.Va QUEUE_MACRO_DEBUG_TRACE
-at compile time.
+.Nm queue(3)
+provides several diagnostic and debugging facilities.
.Pp
-It can also be useful to trash pointers that have been unlinked from a queue,
-to detect use after removal.
-To enable pointer trashing, define the macro
-.Va QUEUE_MACRO_DEBUG_TRASH
-at compile time.
-The macro
-.Fn QMD_IS_TRASHED "void *ptr"
-returns true if
-.Fa ptr
-has been trashed by the
-.Va QUEUE_MACRO_DEBUG_TRASH
-option.
+Check code that performs basic integrity and API conformance checks is
+automatically inserted when using queue macros in the kernel if compiling it
+with
+.Va INVARIANTS .
+One can request insertion or elision of check code by respectively defining one
+of the macros
+.Va QUEUE_MACRO_DEBUG_ASSERTIONS
+or
+.Va QUEUE_MACRO_NO_DEBUG_ASSERTIONS
+before first inclusion of
+.In sys/queue.h .
+When check code encounters an anomaly, it panics the kernel or aborts the
+program.
+To this end, in the kernel or in
+.Va _STANDALONE
+builds, it by default calls
+.Fn panic ,
+while in userland builds it prints the diagnostic message on
+.Dv stderr
+and then calls
+.Fn abort .
+These behaviors can be overriden by defining a custom
+.Fn QMD_PANIC
+macro before first inclusion of
+.In sys/queue.h .
+The diagnostic messages automatically include the source file, line and function
+where the failing check occured.
+This behavior can be overriden by defining a custom
+.Fn QMD_ASSERT
+macro before first inclusion of
+.In sys/queue.h .
.Pp
-In the kernel (with
-.Va INVARIANTS
-enabled), the
+The
.Fn SLIST_REMOVE_PREVPTR
macro is available to aid debugging:
.Bl -hang -offset indent
.It Fn SLIST_REMOVE_PREVPTR "TYPE **prev" "TYPE *elm" "SLIST_ENTRY NAME"
.Pp
-Removes
+Removes element
.Fa elm ,
which must directly follow the element whose
.Va &SLIST_NEXT()
is
.Fa prev ,
-from the SLIST.
-This macro validates that
+from the list.
+This macro may insert, under conditions detailed above, check code that
+validates that
.Fa elm
-follows
+indeed follows
.Fa prev
-in
-.Va INVARIANTS
-mode.
+in the list
+.Po
+through the
+.Fn QMD_SLIST_CHECK_PREVPTR
+macro
+.Pc .
.El
+.Pp
+When debugging, it can be useful to trace queue changes.
+To enable tracing, define the macro
+.Va QUEUE_MACRO_DEBUG_TRACE .
+Note that, at the moment, only macros for regular tail queues have been
+instrumented.
+.Pp
+It can also be useful to trash pointers that have been unlinked from a queue,
+to detect use after removal.
+To enable pointer trashing, define the macro
+.Va QUEUE_MACRO_DEBUG_TRASH
+at compile time.
+Note that, at the moment, only a limited number of macros have been
+instrumented.
+The macro
+.Fn QMD_IS_TRASHED "void *ptr"
+returns true if
+.Fa ptr
+has been trashed by the
+.Va QUEUE_MACRO_DEBUG_TRASH
+option.
.Sh SEE ALSO
.Xr arb 3 ,
.Xr tree 3