diff --git a/share/man/man3/Makefile b/share/man/man3/Makefile --- a/share/man/man3/Makefile +++ b/share/man/man3/Makefile @@ -25,15 +25,18 @@ Q_SIGNED.3 \ Q_SIGNSHFT.3 \ qmath.3 \ - queue.3 \ + list.3 \ sigevent.3 \ siginfo.3 \ + slist.3 \ snl.3 \ + stailq.3 \ stats.3 \ stdarg.3 \ stdbit.3 \ stdckdint.3 \ sysexits.3 \ + tailq.3 \ tgmath.3 \ timeradd.3 \ tree.3 @@ -201,104 +204,120 @@ Q_SIGNSHFT.3 Q_GCRAW.3 \ Q_SIGNSHFT.3 Q_GCVAL.3 \ Q_SIGNSHFT.3 Q_SCVAL.3 -MLINKS+= queue.3 LIST_CLASS_ENTRY.3 \ - queue.3 LIST_CLASS_HEAD.3 \ - queue.3 LIST_EMPTY.3 \ - queue.3 LIST_EMPTY_ATOMIC.3 \ - queue.3 LIST_ENTRY.3 \ - queue.3 LIST_FIRST.3 \ - queue.3 LIST_FOREACH.3 \ - queue.3 LIST_FOREACH_FROM.3 \ - queue.3 LIST_FOREACH_FROM_SAFE.3 \ - queue.3 LIST_FOREACH_SAFE.3 \ - queue.3 LIST_HEAD.3 \ - queue.3 LIST_HEAD_INITIALIZER.3 \ - queue.3 LIST_INIT.3 \ - queue.3 LIST_INSERT_AFTER.3 \ - queue.3 LIST_INSERT_BEFORE.3 \ - queue.3 LIST_INSERT_HEAD.3 \ - queue.3 LIST_NEXT.3 \ - queue.3 LIST_PREV.3 \ - queue.3 LIST_REMOVE.3 \ - queue.3 LIST_REPLACE.3 \ - queue.3 LIST_SPLIT_AFTER.3 \ - queue.3 LIST_SWAP.3 \ - queue.3 SLIST_CLASS_ENTRY.3 \ - queue.3 SLIST_CLASS_HEAD.3 \ - queue.3 SLIST_EMPTY.3 \ - queue.3 SLIST_EMPTY_ATOMIC.3 \ - queue.3 SLIST_ENTRY.3 \ - queue.3 SLIST_FIRST.3 \ - queue.3 SLIST_FOREACH.3 \ - queue.3 SLIST_FOREACH_FROM.3 \ - queue.3 SLIST_FOREACH_FROM_SAFE.3 \ - queue.3 SLIST_FOREACH_SAFE.3 \ - queue.3 SLIST_HEAD.3 \ - queue.3 SLIST_HEAD_INITIALIZER.3 \ - queue.3 SLIST_INIT.3 \ - queue.3 SLIST_INSERT_AFTER.3 \ - queue.3 SLIST_INSERT_HEAD.3 \ - queue.3 SLIST_NEXT.3 \ - queue.3 SLIST_REMOVE.3 \ - queue.3 SLIST_REMOVE_AFTER.3 \ - queue.3 SLIST_REMOVE_HEAD.3 \ - queue.3 SLIST_REMOVE_PREVPTR.3 \ - queue.3 SLIST_SPLIT_AFTER.3 \ - queue.3 SLIST_SWAP.3 \ - queue.3 STAILQ_CLASS_ENTRY.3 \ - queue.3 STAILQ_CLASS_HEAD.3 \ - queue.3 STAILQ_CONCAT.3 \ - queue.3 STAILQ_EMPTY.3 \ - queue.3 STAILQ_EMPTY_ATOMIC.3 \ - queue.3 STAILQ_ENTRY.3 \ - queue.3 STAILQ_FIRST.3 \ - queue.3 STAILQ_FOREACH.3 \ - queue.3 STAILQ_FOREACH_FROM.3 \ - queue.3 STAILQ_FOREACH_FROM_SAFE.3 \ - queue.3 STAILQ_FOREACH_SAFE.3 \ - queue.3 STAILQ_HEAD.3 \ - queue.3 STAILQ_HEAD_INITIALIZER.3 \ - queue.3 STAILQ_INIT.3 \ - queue.3 STAILQ_INSERT_AFTER.3 \ - queue.3 STAILQ_INSERT_HEAD.3 \ - queue.3 STAILQ_INSERT_TAIL.3 \ - queue.3 STAILQ_LAST.3 \ - queue.3 STAILQ_NEXT.3 \ - queue.3 STAILQ_REMOVE.3 \ - queue.3 STAILQ_REMOVE_AFTER.3 \ - queue.3 STAILQ_REMOVE_HEAD.3 \ - queue.3 STAILQ_REVERSE.3 \ - queue.3 STAILQ_SPLIT_AFTER.3 \ - queue.3 STAILQ_SWAP.3 \ - queue.3 TAILQ_CLASS_ENTRY.3 \ - queue.3 TAILQ_CLASS_HEAD.3 \ - queue.3 TAILQ_CONCAT.3 \ - queue.3 TAILQ_EMPTY.3 \ - queue.3 TAILQ_EMPTY_ATOMIC.3 \ - queue.3 TAILQ_ENTRY.3 \ - queue.3 TAILQ_FIRST.3 \ - queue.3 TAILQ_FOREACH.3 \ - queue.3 TAILQ_FOREACH_FROM.3 \ - queue.3 TAILQ_FOREACH_FROM_SAFE.3 \ - queue.3 TAILQ_FOREACH_REVERSE.3 \ - queue.3 TAILQ_FOREACH_REVERSE_FROM.3 \ - queue.3 TAILQ_FOREACH_REVERSE_FROM_SAFE.3 \ - queue.3 TAILQ_FOREACH_REVERSE_SAFE.3 \ - queue.3 TAILQ_FOREACH_SAFE.3 \ - queue.3 TAILQ_HEAD.3 \ - queue.3 TAILQ_HEAD_INITIALIZER.3 \ - queue.3 TAILQ_INIT.3 \ - queue.3 TAILQ_INSERT_AFTER.3 \ - queue.3 TAILQ_INSERT_BEFORE.3 \ - queue.3 TAILQ_INSERT_HEAD.3 \ - queue.3 TAILQ_INSERT_TAIL.3 \ - queue.3 TAILQ_LAST.3 \ - queue.3 TAILQ_NEXT.3 \ - queue.3 TAILQ_PREV.3 \ - queue.3 TAILQ_REMOVE.3 \ - queue.3 TAILQ_REPLACE.3 \ - queue.3 TAILQ_SPLIT_AFTER.3 \ - queue.3 TAILQ_SWAP.3 +MLINKS+= list.3 list_concat \ + list.3 list_empty \ + list.3 list_empty_atomic \ + list.3 list_first \ + list.3 list_init \ + list.3 list_insert_after \ + list.3 list_insert_before \ + list.3 list_insert_head \ + list.3 list_next \ + list.3 list_prev \ + list.3 list_remove \ + list.3 list_remove_head \ + list.3 list_replace \ + list.3 list_split_after \ + list.3 list_swap \ + list.3 LIST_CLASS_ENTRY.3 \ + list.3 LIST_CLASS_HEAD.3 \ + list.3 LIST_EMPTY.3 \ + list.3 LIST_EMPTY_ATOMIC.3 \ + list.3 LIST_ENTRY.3 \ + list.3 LIST_FIRST.3 \ + list.3 LIST_FOREACH.3 \ + list.3 LIST_FOREACH_FROM.3 \ + list.3 LIST_FOREACH_FROM_SAFE.3 \ + list.3 LIST_FOREACH_SAFE.3 \ + list.3 LIST_HEAD.3 \ + list.3 LIST_HEAD_INITIALIZER.3 \ + list.3 LIST_INIT.3 \ + list.3 LIST_INSERT_AFTER.3 \ + list.3 LIST_INSERT_BEFORE.3 \ + list.3 LIST_INSERT_HEAD.3 \ + list.3 LIST_NEXT.3 \ + list.3 LIST_PREV.3 \ + list.3 LIST_REMOVE.3 \ + list.3 LIST_REPLACE.3 \ + list.3 LIST_SPLIT_AFTER.3 \ + list.3 LIST_SWAP.3 +MLINKS+= slist.3 slist_concat \ + slist.3 slist_empty \ + slist.3 slist_empty_atomic \ + slist.3 slist_first \ + slist.3 slist_init \ + slist.3 slist_insert_after \ + slist.3 slist_insert_head \ + slist.3 slist_next \ + slist.3 slist_remove \ + slist.3 slist_remove_after \ + slist.3 slist_remove_head \ + slist.3 slist_remove_prevptr \ + slist.3 slist_split_after \ + slist.3 slist_swap \ + slist.3 SLIST_CLASS_ENTRY.3 \ + slist.3 SLIST_CLASS_HEAD.3 \ + slist.3 SLIST_EMPTY.3 \ + slist.3 SLIST_EMPTY_ATOMIC.3 \ + slist.3 SLIST_ENTRY.3 \ + slist.3 SLIST_FIRST.3 \ + slist.3 SLIST_FOREACH.3 \ + slist.3 SLIST_FOREACH_FROM.3 \ + slist.3 SLIST_FOREACH_FROM_SAFE.3 \ + slist.3 SLIST_FOREACH_SAFE.3 \ + slist.3 SLIST_HEAD.3 \ + slist.3 SLIST_HEAD_INITIALIZER.3 \ + slist.3 SLIST_INIT.3 \ + slist.3 SLIST_INSERT_AFTER.3 \ + slist.3 SLIST_INSERT_HEAD.3 \ + slist.3 SLIST_NEXT.3 \ + slist.3 SLIST_REMOVE.3 \ + slist.3 SLIST_REMOVE_AFTER.3 \ + slist.3 SLIST_REMOVE_HEAD.3 \ + slist.3 SLIST_REMOVE_PREVPTR.3 \ + slist.3 SLIST_SPLIT_AFTER.3 \ + slist.3 SLIST_SWAP.3 +MLINKS+= stailq.3 stailq_concat \ + stailq.3 stailq_empty \ + stailq.3 stailq_empty_atomic \ + stailq.3 stailq_first \ + stailq.3 stailq_init \ + stailq.3 stailq_insert_after \ + stailq.3 stailq_insert_head \ + stailq.3 stailq_insert_tail \ + stailq.3 stailq_last \ + stailq.3 stailq_next \ + stailq.3 stailq_remove \ + stailq.3 stailq_remove_after \ + stailq.3 stailq_remove_head \ + stailq.3 stailq_reverse \ + stailq.3 stailq_split_after \ + stailq.3 stailq_swap \ + stailq.3 STAILQ_CLASS_ENTRY.3 \ + stailq.3 STAILQ_CLASS_HEAD.3 \ + stailq.3 STAILQ_CONCAT.3 \ + stailq.3 STAILQ_EMPTY.3 \ + stailq.3 STAILQ_EMPTY_ATOMIC.3 \ + stailq.3 STAILQ_ENTRY.3 \ + stailq.3 STAILQ_FIRST.3 \ + stailq.3 STAILQ_FOREACH.3 \ + stailq.3 STAILQ_FOREACH_FROM.3 \ + stailq.3 STAILQ_FOREACH_FROM_SAFE.3 \ + stailq.3 STAILQ_FOREACH_SAFE.3 \ + stailq.3 STAILQ_HEAD.3 \ + stailq.3 STAILQ_HEAD_INITIALIZER.3 \ + stailq.3 STAILQ_INIT.3 \ + stailq.3 STAILQ_INSERT_AFTER.3 \ + stailq.3 STAILQ_INSERT_HEAD.3 \ + stailq.3 STAILQ_INSERT_TAIL.3 \ + stailq.3 STAILQ_LAST.3 \ + stailq.3 STAILQ_NEXT.3 \ + stailq.3 STAILQ_REMOVE.3 \ + stailq.3 STAILQ_REMOVE_AFTER.3 \ + stailq.3 STAILQ_REMOVE_HEAD.3 \ + stailq.3 STAILQ_REVERSE.3 \ + stailq.3 STAILQ_SPLIT_AFTER.3 \ + stailq.3 STAILQ_SWAP.3 MLINKS+= stats.3 stats_tpl_alloc.3 \ stats.3 stats_tpl_fetch_allocid.3 \ stats.3 stats_tpl_fetch.3 \ @@ -328,6 +347,52 @@ MLINKS+= stdckdint.3 ckd_add.3 \ stdckdint.3 ckd_sub.3 \ stdckdint.3 ckd_mul.3 +MLINKS+= tailq.3 tailq_concat \ + tailq.3 tailq_empty \ + tailq.3 tailq_empty_atomic \ + tailq.3 tailq_first \ + tailq.3 tailq_init \ + tailq.3 tailq_insert_after \ + tailq.3 tailq_insert_before \ + tailq.3 tailq_insert_head \ + tailq.3 tailq_insert_tail \ + tailq.3 tailq_last \ + tailq.3 tailq_next \ + tailq.3 tailq_prev \ + tailq.3 tailq_remove \ + tailq.3 tailq_remove_head \ + tailq.3 tailq_replace \ + tailq.3 tailq_split_after \ + tailq.3 tailq_swap \ + tailq.3 TAILQ_CLASS_ENTRY.3 \ + tailq.3 TAILQ_CLASS_HEAD.3 \ + tailq.3 TAILQ_CONCAT.3 \ + tailq.3 TAILQ_EMPTY.3 \ + tailq.3 TAILQ_EMPTY_ATOMIC.3 \ + tailq.3 TAILQ_ENTRY.3 \ + tailq.3 TAILQ_FIRST.3 \ + tailq.3 TAILQ_FOREACH.3 \ + tailq.3 TAILQ_FOREACH_FROM.3 \ + tailq.3 TAILQ_FOREACH_FROM_SAFE.3 \ + tailq.3 TAILQ_FOREACH_REVERSE.3 \ + tailq.3 TAILQ_FOREACH_REVERSE_FROM.3 \ + tailq.3 TAILQ_FOREACH_REVERSE_FROM_SAFE.3 \ + tailq.3 TAILQ_FOREACH_REVERSE_SAFE.3 \ + tailq.3 TAILQ_FOREACH_SAFE.3 \ + tailq.3 TAILQ_HEAD.3 \ + tailq.3 TAILQ_HEAD_INITIALIZER.3 \ + tailq.3 TAILQ_INIT.3 \ + tailq.3 TAILQ_INSERT_AFTER.3 \ + tailq.3 TAILQ_INSERT_BEFORE.3 \ + tailq.3 TAILQ_INSERT_HEAD.3 \ + tailq.3 TAILQ_INSERT_TAIL.3 \ + tailq.3 TAILQ_LAST.3 \ + tailq.3 TAILQ_NEXT.3 \ + tailq.3 TAILQ_PREV.3 \ + tailq.3 TAILQ_REMOVE.3 \ + tailq.3 TAILQ_REPLACE.3 \ + tailq.3 TAILQ_SPLIT_AFTER.3 \ + tailq.3 TAILQ_SWAP.3 MLINKS+= timeradd.3 timerclear.3 \ timeradd.3 timercmp.3 \ timeradd.3 timerisset.3 \ diff --git a/share/man/man3/arb.3 b/share/man/man3/arb.3 --- a/share/man/man3/arb.3 +++ b/share/man/man3/arb.3 @@ -29,7 +29,7 @@ .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. .\" -.Dd October 14, 2019 +.Dd January 17, 2026 .Dt ARB 3 .Os .Sh NAME @@ -493,7 +493,10 @@ macro discards the tree topology. It does not modify embedded object values or the free list. .Sh SEE ALSO -.Xr queue 3 , +.Xr list 3 , +.Xr slist 3 , +.Xr stailq 3 , +.Xr tailq 3 , .Xr tree 3 .Sh HISTORY The diff --git a/share/man/man3/list.3 b/share/man/man3/list.3 new file mode 100644 --- /dev/null +++ b/share/man/man3/list.3 @@ -0,0 +1,737 @@ +.\" Copyright (c) 1993 +.\" The Regents of the University of California. All rights reserved. +.\" Copyright (c) 2026 The FreeBSD Foundation. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.Dd January 18, 2026 +.Dt LIST 3 +.Os +.Sh NAME +.Nm list_concat , +.Nm list_empty , +.Nm list_empty_atomic , +.Nm list_first , +.Nm list_foreach , +.Nm list_foreach_from , +.Nm list_foreach_from_safe , +.Nm list_foreach_safe , +.Nm list_init , +.Nm list_insert_after , +.Nm list_insert_before , +.Nm list_insert_head , +.Nm list_next , +.Nm list_prev , +.Nm list_remove , +.Nm list_replace , +.Nm list_split_after , +.Nm list_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 , +.Nm LIST_FOREACH_FROM , +.Nm LIST_FOREACH_FROM_SAFE , +.Nm LIST_FOREACH_SAFE , +.Nm LIST_HEAD , +.Nm LIST_HEAD_INITIALIZER , +.Nm LIST_INIT , +.Nm LIST_INSERT_AFTER , +.Nm LIST_INSERT_BEFORE , +.Nm LIST_INSERT_HEAD , +.Nm LIST_NEXT , +.Nm LIST_PREV , +.Nm LIST_REMOVE , +.Nm LIST_REPLACE , +.Nm LIST_SPLIT_AFTER , +.Nm LIST_SWAP +.Nd doubly-linked list implementation +.Sh SYNOPSIS +.In sys/list.h +.\" +.Ft void +.Fn list_concat "struct list *list1" "struct list *list2" +.Ft bool +.Fn list_empty "const struct list *list" +.Ft bool +.Fn list_empty_atomic "const struct list *list" +.Ft "struct list_node *" +.Fn list_first "const struct list *list" +.Fn list_foreach "struct list_node *var" "const struct list *list" +.Fn list_foreach_from "struct list_node *var" "const struct list *list" +.Fn list_foreach_from_safe "struct list_node *var" "const struct list *list" "struct list_node *tvar" +.Fn list_foreach_safe "struct list_node *var" "const struct list *list" "struct list_node *tvar" +.Ft void +.Fn list_init "struct list *list" +.Ft void +.Fn list_insert_after "struct list_node *listnode" "struct list_node *node" +.Ft void +.Fn list_insert_before "struct list_node *listnode" "struct list_node *node" +.Ft void +.Fn list_insert_head "struct list *list" "struct list_node *node" +.Ft "struct list_node *" +.Fn list_next "const struct list_node *node" +.Ft "struct list_node *" +.Fn list_prev "const struct list_node *node" "const struct list *list" +.Ft void +.Fn list_remove "struct list_node *node" +.Ft void +.Fn list_replace "struct list_node *node" "struct list_node *node2" +.Ft void +.Fn list_split_after "struct list *list" "struct list_node *node" "struct list *rest" +.Ft void +.Fn list_swap "struct list *list1" "struct list *list2" +.\" +.In sys/queue.h +.\" +.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" +.Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" +.Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" +.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" +.Fn LIST_HEAD "HEADNAME" "TYPE" +.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" +.Fn LIST_INIT "LIST_HEAD *head" +.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" +.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" +.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" +.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_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" +.\" +.Sh DESCRIPTION +Doubly-linked lists are the simplest of the doubly linked data structures. +The elements are doubly linked so that an arbitrary element can be +removed without traversing the list, and bidirectional traversal is possible. +Doubly-linked lists support the following operations: +.Bl -enum -compact -offset indent +.It +Insertion of a new entry at the head of the list. +.It +Insertion of a new entry after any element in the list. +.It +Insertion of a new entry before any element in the list. +.It +O(1) removal of any entry in the list. +.It +Forward and backward traversal through the list. +.It +O(n) concatenation of two lists. +.It +Splitting a list in two after any element in the list. +.It +Swapping the contents of two lists. +.El +However: +.Bl -enum -compact -offset indent +.It +Each element requires two pointers rather than one. +.It +Code size and execution time of operations (except for removal) is about +twice that of the singly-linked data-structures. +.It +To traverse backwards, an entry to begin the traversal and the list in +which it is contained must be specified. +.El +.Pp +The +.Nm list +implementation provides both a modern function-based API (recommended) +and a traditional macro-based API for compatibility. +The function-based API is recommended for new code as it provides: +.Bl -bullet -offset indent +.It +Type safety without requiring type parameters +.It +Better debugger support +.It +Simpler function signatures +.It +Compatible with both C and C++ +.El +.Ss Function-Based API +The function-based API uses standard structure types +.Vt struct list +and +.Vt struct list_node +defined in +.In sys/list.h . +User-defined structures should embed +.Vt struct list_node +and use +.Fa containerof +macro to convert node pointers to structure pointers. +.Pp +.Fn list_concat +concatenates the list headed by +.Fa list2 +onto the end of the one headed by +.Fa list1 +removing all entries from the former. +Use of this function should be avoided as it traverses the entirety of the +.Fa list1 +list. +A tail queue should be used if this operation is needed in +high-usage code paths or to operate on long lists. +.Pp +.Fn list_empty +evaluates to true if there are no elements in the list. +.Fn list_empty_atomic +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 +.Fn list_first +returns the first element in the list or NULL if the list +is empty. +.Pp +.Fn list_foreach +traverses the list referenced by +.Fa list +in the forward direction, assigning each node in turn to +.Fa var . +.Pp +.Fn list_foreach_from +behaves identically to +.Fn list_foreach +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found node and begins the loop at +.Fa var +instead of the first node in the list referenced by +.Fa list . +.Pp +.Fn list_foreach_safe +traverses the list referenced by +.Fa list +in the forward direction, assigning each node in turn to +.Fa var . +However, unlike +.Fn list_foreach +here it is permitted to both remove +.Fa var +as well as free it from within the loop safely without interfering with the +traversal. +.Pp +.Fn list_foreach_from_safe +behaves identically to +.Fn list_foreach_safe +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found node and begins the loop at +.Fa var +instead of the first node in the list referenced by +.Fa list . +.Pp +.Fn list_init +initializes the list referenced by +.Fa list . +.Pp +.Fn list_insert_head +inserts the new element +.Fa node +at the head of the list. +.Pp +.Fn list_insert_after +inserts the new element +.Fa node +after the element +.Fa listnode . +.Pp +.Fn list_insert_before +inserts the new element +.Fa node +before the element +.Fa listnode . +.Pp +.Fn list_next +returns the next element in the list, or NULL if this is the last. +.Pp +.Fn list_prev +returns the previous element in the list, or NULL if this is the first. +List +.Fa list +must contain element +.Fa node . +.Pp +.Fn list_remove +removes the element +.Fa node +from the list. +.Pp +.Fn list_replace +replaces the element +.Fa node +with +.Fa node2 +in the list. +The element +.Fa node2 +must not already be on a list. +.Pp +.Fn list_split_after +splits the list referenced by +.Fa list , +making +.Fa rest +reference the list formed by elements after +.Fa node +in +.Fa list . +.Pp +.Fn list_swap +swaps the contents of +.Fa list1 +and +.Fa list2 . +.Ss Converting Between Node and Structure Pointers +Since the function-based API operates on node pointers +.Pf ( Vt struct list_node ) , +user code needs to convert between node pointers and pointers to the +containing structure. +This is typically done using a +.Fn containerof +macro: +.Bd -literal -offset indent +containerof(ptr, type, member) +.Ed +.Pp +This macro takes a pointer to a structure member +.Fa ptr , +the type of the containing structure +.Fa type , +and the name of the member field +.Fa member , +and returns a pointer to the containing structure. +.Ss Macro-Based API +The macro-based API is provided for compatibility with existing code. +In the macro definitions, +.Fa TYPE +is the name of a user defined structure. +The structure must contain a field called +.Fa NAME +which is of type +.Li LIST_ENTRY . +In the macro definitions, +.Fa CLASSTYPE +is the name of a user defined class. +The class must contain a field called +.Fa NAME +which is of type +.Li LIST_CLASS_ENTRY . +The argument +.Fa HEADNAME +is the name of a user defined structure that must be declared +using the macros +.Li LIST_HEAD +or +.Li LIST_CLASS_HEAD . +See the examples below for further explanation of how these +macros are used. +.Pp +A list is headed by a structure defined by the +.Nm LIST_HEAD +macro. +This structure contains a single pointer to the first element +on the list. +The elements are doubly linked so that an arbitrary element can be +removed without traversing the list. +New elements can be added to the list after an existing element, +before an existing element, or at the head of the list. +A +.Fa LIST_HEAD +structure is declared as follows: +.Bd -literal -offset indent +LIST_HEAD(HEADNAME, TYPE) head; +.Ed +.Pp +where +.Fa HEADNAME +is the name of the structure to be defined, and +.Fa TYPE +is the type of the elements to be linked into the list. +A pointer to the head of the list can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The macro +.Nm LIST_HEAD_INITIALIZER +evaluates to an initializer for the list +.Fa head . +.Pp +The macro +.Nm LIST_CONCAT +concatenates the list headed by +.Fa head2 +onto the end of the one headed by +.Fa head1 +removing all entries from the former. +Use of this macro should be avoided as it traverses the entirety of the +.Fa head1 +list. +A tail queue should be used if this macro is needed in +high-usage code paths or to operate on long lists. +.Pp +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 +declares a structure that connects the elements in +the list. +.Pp +The macro +.Nm LIST_FIRST +returns the first element in the list or NULL if the list +is empty. +.Pp +The macro +.Nm LIST_FOREACH +traverses the list referenced by +.Fa head +in the forward direction, assigning each element in turn to +.Fa var . +.Pp +The macro +.Nm LIST_FOREACH_FROM +behaves identically to +.Nm LIST_FOREACH +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found LIST element and begins the loop at +.Fa var +instead of the first element in the LIST referenced by +.Fa head . +.Pp +The macro +.Nm LIST_FOREACH_SAFE +traverses the list referenced by +.Fa head +in the forward direction, assigning each element in turn to +.Fa var . +However, unlike +.Fn LIST_FOREACH +here it is permitted to both remove +.Fa var +as well as free it from within the loop safely without interfering with the +traversal. +.Pp +The macro +.Nm LIST_FOREACH_FROM_SAFE +behaves identically to +.Nm LIST_FOREACH_SAFE +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found LIST element and begins the loop at +.Fa var +instead of the first element in the LIST referenced by +.Fa head . +.Pp +The macro +.Nm LIST_INIT +initializes the list referenced by +.Fa head . +.Pp +The macro +.Nm LIST_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the list. +.Pp +The macro +.Nm LIST_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Nm LIST_INSERT_BEFORE +inserts the new element +.Fa elm +before the element +.Fa listelm . +.Pp +The macro +.Nm LIST_NEXT +returns the next element in the list, or NULL if this is the last. +.Pp +The macro +.Nm LIST_PREV +returns the previous element in the list, or NULL if this is the first. +List +.Fa head +must contain element +.Fa elm . +.Pp +The macro +.Nm LIST_REMOVE +removes the element +.Fa elm +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_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 +and +.Fa head2 . +.Sh EXAMPLES +.Ss Function-Based API Example +.Bd -literal +#include +#include + +struct entry { + ... + struct list_node node; /* List. */ + ... +} *n1, *n2, *n3; +struct list list; +struct list_node *np, *np_temp; + +list_init(&list); /* Initialize the list. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +list_insert_head(&list, &n1->node); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +list_insert_after(&n1->node, &n2->node); + +n3 = malloc(sizeof(struct entry)); /* Insert before. */ +list_insert_before(&n2->node, &n3->node); + +list_remove(&n2->node); /* Deletion. */ +free(n2); + /* Forward traversal. */ +list_foreach(np, &list) { + n1 = containerof(np, struct entry, node); + n1-> ... +} + /* Safe forward traversal. */ +list_foreach_safe(np, &list, np_temp) { + n1 = containerof(np, struct entry, node); + n1->do_stuff(); + ... + list_remove(np); + free(n1); +} + /* List Deletion. */ +while (!list_empty(&list)) { + np = list_first(&list); + list_remove(np); + n1 = containerof(np, struct entry, node); + free(n1); +} + /* Faster List Deletion. */ +np = list_first(&list); +while (np != NULL) { + np_temp = list_next(np); + n1 = containerof(np, struct entry, node); + free(n1); + np = np_temp; +} +list_init(&list); +.Ed +.Ss Macro-Based API Example +.Bd -literal +#include +#include + +LIST_HEAD(listhead, entry) head = + LIST_HEAD_INITIALIZER(head); +struct listhead *headp; /* List head. */ +struct entry { + ... + LIST_ENTRY(entry) entries; /* List. */ + ... +} *n1, *n2, *n3, *np, *np_temp; + +LIST_INIT(&head); /* Initialize the list. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +LIST_INSERT_HEAD(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +LIST_INSERT_AFTER(n1, n2, entries); + +n3 = malloc(sizeof(struct entry)); /* Insert before. */ +LIST_INSERT_BEFORE(n2, n3, entries); + +LIST_REMOVE(n2, entries); /* Deletion. */ +free(n2); + /* Forward traversal. */ +LIST_FOREACH(np, &head, entries) + np-> ... + + /* Safe forward traversal. */ +LIST_FOREACH_SAFE(np, &head, entries, np_temp) { + np->do_stuff(); + ... + LIST_REMOVE(np, entries); + free(np); +} + +while (!LIST_EMPTY(&head)) { /* List Deletion. */ + n1 = LIST_FIRST(&head); + LIST_REMOVE(n1, entries); + free(n1); +} + +n1 = LIST_FIRST(&head); /* Faster List Deletion. */ +while (n1 != NULL) { + n2 = LIST_NEXT(n1, entries); + free(n1); + n1 = n2; +} +LIST_INIT(&head); +.Ed +.Sh DIAGNOSTICS +.In sys/queue.h +provides several diagnostic and debugging facilities. +.Pp +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 overridden 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 occurred. +This behavior can be overridden by defining a custom +.Fn QMD_ASSERT +macro before first inclusion of +.In sys/queue.h . +.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 slist 3 , +.Xr stailq 3 , +.Xr tailq 3 , +.Xr tree 3 +.Sh HISTORY +The +.Nm LIST +macros first appeared in +.Bx 4.4 . +.Pp +The function-based API was introduced in +.Fx 15.1 . +.Sh AUTHORS +The function-based API was written by +.An Minsoo Choo Aq Mt minsoochoo0122@proton.me . diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3 deleted file mode 100644 --- a/share/man/man3/queue.3 +++ /dev/null @@ -1,1487 +0,0 @@ -.\" Copyright (c) 1993 -.\" The Regents of the University of California. All rights reserved. -.\" -.\" Redistribution and use in source and binary forms, with or without -.\" modification, are permitted provided that the following conditions -.\" are met: -.\" 1. Redistributions of source code must retain the above copyright -.\" notice, this list of conditions and the following disclaimer. -.\" 2. Redistributions in binary form must reproduce the above copyright -.\" notice, this list of conditions and the following disclaimer in the -.\" documentation and/or other materials provided with the distribution. -.\" 3. Neither the name of the University nor the names of its contributors -.\" may be used to endorse or promote products derived from this software -.\" without specific prior written permission. -.\" -.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND -.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE -.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE -.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE -.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL -.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS -.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) -.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT -.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY -.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF -.\" SUCH DAMAGE. -.\" -.Dd April 28, 2025 -.Dt QUEUE 3 -.Os -.Sh NAME -.Nm SLIST_CLASS_ENTRY , -.Nm SLIST_CLASS_HEAD , -.Nm SLIST_CONCAT , -.Nm SLIST_EMPTY , -.Nm SLIST_EMPTY_ATOMIC , -.Nm SLIST_ENTRY , -.Nm SLIST_FIRST , -.Nm SLIST_FOREACH , -.Nm SLIST_FOREACH_FROM , -.Nm SLIST_FOREACH_FROM_SAFE , -.Nm SLIST_FOREACH_SAFE , -.Nm SLIST_HEAD , -.Nm SLIST_HEAD_INITIALIZER , -.Nm SLIST_INIT , -.Nm SLIST_INSERT_AFTER , -.Nm SLIST_INSERT_HEAD , -.Nm SLIST_NEXT , -.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 , -.Nm STAILQ_FOREACH_FROM , -.Nm STAILQ_FOREACH_FROM_SAFE , -.Nm STAILQ_FOREACH_SAFE , -.Nm STAILQ_HEAD , -.Nm STAILQ_HEAD_INITIALIZER , -.Nm STAILQ_INIT , -.Nm STAILQ_INSERT_AFTER , -.Nm STAILQ_INSERT_HEAD , -.Nm STAILQ_INSERT_TAIL , -.Nm STAILQ_LAST , -.Nm STAILQ_NEXT , -.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 , -.Nm LIST_FOREACH_FROM , -.Nm LIST_FOREACH_FROM_SAFE , -.Nm LIST_FOREACH_SAFE , -.Nm LIST_HEAD , -.Nm LIST_HEAD_INITIALIZER , -.Nm LIST_INIT , -.Nm LIST_INSERT_AFTER , -.Nm LIST_INSERT_BEFORE , -.Nm LIST_INSERT_HEAD , -.Nm LIST_NEXT , -.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 , -.Nm TAILQ_FOREACH_FROM , -.Nm TAILQ_FOREACH_FROM_SAFE , -.Nm TAILQ_FOREACH_REVERSE , -.Nm TAILQ_FOREACH_REVERSE_FROM , -.Nm TAILQ_FOREACH_REVERSE_FROM_SAFE , -.Nm TAILQ_FOREACH_REVERSE_SAFE , -.Nm TAILQ_FOREACH_SAFE , -.Nm TAILQ_HEAD , -.Nm TAILQ_HEAD_INITIALIZER , -.Nm TAILQ_INIT , -.Nm TAILQ_INSERT_AFTER , -.Nm TAILQ_INSERT_BEFORE , -.Nm TAILQ_INSERT_HEAD , -.Nm TAILQ_INSERT_TAIL , -.Nm TAILQ_LAST , -.Nm TAILQ_NEXT , -.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 -.Sh SYNOPSIS -.In sys/queue.h -.\" -.Fn SLIST_CLASS_ENTRY "CLASSTYPE" -.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" -.Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" -.Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" -.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" -.Fn SLIST_HEAD "HEADNAME" "TYPE" -.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" -.Fn SLIST_INIT "SLIST_HEAD *head" -.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" -.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" -.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" -.Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" -.Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" -.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" -.Fn STAILQ_HEAD "HEADNAME" "TYPE" -.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" -.Fn STAILQ_INIT "STAILQ_HEAD *head" -.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" -.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" -.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" -.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" -.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" -.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" -.Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" -.Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" -.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" -.Fn LIST_HEAD "HEADNAME" "TYPE" -.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" -.Fn LIST_INIT "LIST_HEAD *head" -.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" -.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" -.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" -.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_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" -.Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" -.Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" -.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" -.Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" -.Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" -.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" -.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" -.Fn TAILQ_HEAD "HEADNAME" "TYPE" -.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" -.Fn TAILQ_INIT "TAILQ_HEAD *head" -.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" -.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" -.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" -.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" -.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" -.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_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 -These macros define and operate on four types of data structures which -can be used in both C and C++ source code: -.Bl -enum -compact -offset indent -.It -Lists -.It -Singly-linked lists -.It -Singly-linked tail queues -.It -Tail queues -.El -All four structures support the following functionality: -.Bl -enum -compact -offset indent -.It -Insertion of a new entry at the head of the list. -.It -Insertion of a new entry after any element in the list. -.It -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 -Singly-linked lists are the simplest of the four data structures -and support only the above functionality. -Singly-linked lists are ideal for applications with large datasets -and few or no removals, -or for implementing a LIFO queue. -Singly-linked lists add the following functionality: -.Bl -enum -compact -offset indent -.It -O(n) removal of any entry in the list. -.It -O(n) concatenation of two lists. -.El -.Pp -Singly-linked tail queues add the following functionality: -.Bl -enum -compact -offset indent -.It -Entries can be added at the end of a list. -.It -O(n) removal of any entry in the list. -.It -They may be concatenated. -.El -However: -.Bl -enum -compact -offset indent -.It -All list insertions must specify the head of the list. -.It -Each head entry requires two pointers rather than one. -.It -Code size is about 15% greater and operations run about 20% slower -than singly-linked lists. -.El -.Pp -Singly-linked tail queues are ideal for applications with large datasets and -few or no removals, -or for implementing a FIFO queue. -.Pp -All doubly linked types of data structures (lists and tail queues) -additionally allow: -.Bl -enum -compact -offset indent -.It -Insertion of a new entry before any element in the list. -.It -O(1) removal of any entry in the list. -.El -However: -.Bl -enum -compact -offset indent -.It -Each element requires two pointers rather than one. -.It -Code size and execution time of operations (except for removal) is about -twice that of the singly-linked data-structures. -.El -.Pp -Linked lists are the simplest of the doubly linked data structures. -They add the following functionality over the above: -.Bl -enum -compact -offset indent -.It -O(n) concatenation of two lists. -.It -They may be traversed backwards. -.El -However: -.Bl -enum -compact -offset indent -.It -To traverse backwards, an entry to begin the traversal and the list in -which it is contained must be specified. -.El -.Pp -Tail queues add the following functionality: -.Bl -enum -compact -offset indent -.It -Entries can be added at the end of a list. -.It -They may be traversed backwards, from tail to head. -.It -They may be concatenated. -.El -However: -.Bl -enum -compact -offset indent -.It -All list insertions and removals must specify the head of the list. -.It -Each head entry requires two pointers rather than one. -.It -Code size is about 15% greater and operations run about 20% slower -than singly-linked lists. -.El -.Pp -In the macro definitions, -.Fa TYPE -is the name of a user defined structure. -The structure must contain a field called -.Fa NAME -which is of type -.Li SLIST_ENTRY , -.Li STAILQ_ENTRY , -.Li LIST_ENTRY , -or -.Li TAILQ_ENTRY . -In the macro definitions, -.Fa CLASSTYPE -is the name of a user defined class. -The class must contain a field called -.Fa NAME -which is of type -.Li SLIST_CLASS_ENTRY , -.Li STAILQ_CLASS_ENTRY , -.Li LIST_CLASS_ENTRY , -or -.Li TAILQ_CLASS_ENTRY . -The argument -.Fa HEADNAME -is the name of a user defined structure that must be declared -using the macros -.Li SLIST_HEAD , -.Li SLIST_CLASS_HEAD , -.Li STAILQ_HEAD , -.Li STAILQ_CLASS_HEAD , -.Li LIST_HEAD , -.Li LIST_CLASS_HEAD , -.Li TAILQ_HEAD , -or -.Li TAILQ_CLASS_HEAD . -See the examples below for further explanation of how these -macros are used. -.Sh SINGLY-LINKED LISTS -A singly-linked list is headed by a structure defined by the -.Nm SLIST_HEAD -macro. -This structure contains a single pointer to the first element -on the list. -The elements are singly linked for minimum space and pointer manipulation -overhead at the expense of O(n) removal for arbitrary elements. -New elements can be added to the list after an existing element or -at the head of the list. -An -.Fa SLIST_HEAD -structure is declared as follows: -.Bd -literal -offset indent -SLIST_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp -where -.Fa HEADNAME -is the name of the structure to be defined, and -.Fa TYPE -is the type of the elements to be linked into the list. -A pointer to the head of the list can later be declared as: -.Bd -literal -offset indent -struct HEADNAME *headp; -.Ed -.Pp -(The names -.Li head -and -.Li headp -are user selectable.) -.Pp -The macro -.Nm SLIST_HEAD_INITIALIZER -evaluates to an initializer for the list -.Fa head . -.Pp -The macro -.Nm SLIST_CONCAT -concatenates the list headed by -.Fa head2 -onto the end of the one headed by -.Fa head1 -removing all entries from the former. -Use of this macro should be avoided as it traverses the entirety of the -.Fa head1 -list. -A singly-linked tail queue should be used if this macro is needed in -high-usage code paths or to operate on long lists. -.Pp -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 -declares a structure that connects the elements in -the list. -.Pp -The macro -.Nm SLIST_FIRST -returns the first element in the list or NULL if the list is empty. -.Pp -The macro -.Nm SLIST_FOREACH -traverses the list referenced by -.Fa head -in the forward direction, assigning each element in -turn to -.Fa var . -.Pp -The macro -.Nm SLIST_FOREACH_FROM -behaves identically to -.Nm SLIST_FOREACH -when -.Fa var -is NULL, else it treats -.Fa var -as a previously found SLIST element and begins the loop at -.Fa var -instead of the first element in the SLIST referenced by -.Fa head . -.Pp -The macro -.Nm SLIST_FOREACH_SAFE -traverses the list referenced by -.Fa head -in the forward direction, assigning each element in -turn to -.Fa var . -However, unlike -.Fn SLIST_FOREACH -here it is permitted to both remove -.Fa var -as well as free it from within the loop safely without interfering with the -traversal. -.Pp -The macro -.Nm SLIST_FOREACH_FROM_SAFE -behaves identically to -.Nm SLIST_FOREACH_SAFE -when -.Fa var -is NULL, else it treats -.Fa var -as a previously found SLIST element and begins the loop at -.Fa var -instead of the first element in the SLIST referenced by -.Fa head . -.Pp -The macro -.Nm SLIST_INIT -initializes the list referenced by -.Fa head . -.Pp -The macro -.Nm SLIST_INSERT_HEAD -inserts the new element -.Fa elm -at the head of the list. -.Pp -The macro -.Nm SLIST_INSERT_AFTER -inserts the new element -.Fa elm -after the element -.Fa listelm . -.Pp -The macro -.Nm SLIST_NEXT -returns the next element in the list. -.Pp -The macro -.Nm SLIST_REMOVE_AFTER -removes the element after -.Fa elm -from the list. -Unlike -.Fa SLIST_REMOVE , -this macro does not traverse the entire list. -.Pp -The macro -.Nm SLIST_REMOVE_HEAD -removes the element -.Fa elm -from the head of the list. -For optimum efficiency, -elements being removed from the head of the list should explicitly use -this macro instead of the generic -.Fa SLIST_REMOVE -macro. -.Pp -The macro -.Nm SLIST_REMOVE -removes the element -.Fa elm -from the list. -Use of this macro should be avoided as it traverses the entire list. -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 -and -.Fa head2 . -.Sh SINGLY-LINKED LIST EXAMPLE -.Bd -literal -SLIST_HEAD(slisthead, entry) head = - SLIST_HEAD_INITIALIZER(head); -struct slisthead *headp; /* Singly-linked List head. */ -struct entry { - ... - SLIST_ENTRY(entry) entries; /* Singly-linked List. */ - ... -} *n1, *n2, *n3, *np; - -SLIST_INIT(&head); /* Initialize the list. */ - -n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ -SLIST_INSERT_HEAD(&head, n1, entries); - -n2 = malloc(sizeof(struct entry)); /* Insert after. */ -SLIST_INSERT_AFTER(n1, n2, entries); - -SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */ -free(n2); - -n3 = SLIST_FIRST(&head); -SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */ -free(n3); - /* Forward traversal. */ -SLIST_FOREACH(np, &head, entries) - np-> ... - /* Safe forward traversal. */ -SLIST_FOREACH_SAFE(np, &head, entries, np_temp) { - np->do_stuff(); - ... - SLIST_REMOVE(&head, np, entry, entries); - free(np); -} - -while (!SLIST_EMPTY(&head)) { /* List Deletion. */ - n1 = SLIST_FIRST(&head); - SLIST_REMOVE_HEAD(&head, entries); - free(n1); -} -.Ed -.Sh SINGLY-LINKED TAIL QUEUES -A singly-linked tail queue is headed by a structure defined by the -.Nm STAILQ_HEAD -macro. -This structure contains a pair of pointers, -one to the first element in the tail queue and the other to -the last element in the tail queue. -The elements are singly linked for minimum space and pointer -manipulation overhead at the expense of O(n) removal for arbitrary -elements. -New elements can be added to the tail queue after an existing element, -at the head of the tail queue, or at the end of the tail queue. -A -.Fa STAILQ_HEAD -structure is declared as follows: -.Bd -literal -offset indent -STAILQ_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp -where -.Li HEADNAME -is the name of the structure to be defined, and -.Li TYPE -is the type of the elements to be linked into the tail queue. -A pointer to the head of the tail queue can later be declared as: -.Bd -literal -offset indent -struct HEADNAME *headp; -.Ed -.Pp -(The names -.Li head -and -.Li headp -are user selectable.) -.Pp -The macro -.Nm STAILQ_HEAD_INITIALIZER -evaluates to an initializer for the tail queue -.Fa head . -.Pp -The macro -.Nm STAILQ_CONCAT -concatenates the tail queue headed by -.Fa head2 -onto the end of the one headed by -.Fa head1 -removing all entries from the former. -.Pp -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 -declares a structure that connects the elements in -the tail queue. -.Pp -The macro -.Nm STAILQ_FIRST -returns the first item on the tail queue or NULL if the tail queue -is empty. -.Pp -The macro -.Nm STAILQ_FOREACH -traverses the tail queue referenced by -.Fa head -in the forward direction, assigning each element -in turn to -.Fa var . -.Pp -The macro -.Nm STAILQ_FOREACH_FROM -behaves identically to -.Nm STAILQ_FOREACH -when -.Fa var -is NULL, else it treats -.Fa var -as a previously found STAILQ element and begins the loop at -.Fa var -instead of the first element in the STAILQ referenced by -.Fa head . -.Pp -The macro -.Nm STAILQ_FOREACH_SAFE -traverses the tail queue referenced by -.Fa head -in the forward direction, assigning each element -in turn to -.Fa var . -However, unlike -.Fn STAILQ_FOREACH -here it is permitted to both remove -.Fa var -as well as free it from within the loop safely without interfering with the -traversal. -.Pp -The macro -.Nm STAILQ_FOREACH_FROM_SAFE -behaves identically to -.Nm STAILQ_FOREACH_SAFE -when -.Fa var -is NULL, else it treats -.Fa var -as a previously found STAILQ element and begins the loop at -.Fa var -instead of the first element in the STAILQ referenced by -.Fa head . -.Pp -The macro -.Nm STAILQ_INIT -initializes the tail queue referenced by -.Fa head . -.Pp -The macro -.Nm STAILQ_INSERT_HEAD -inserts the new element -.Fa elm -at the head of the tail queue. -.Pp -The macro -.Nm STAILQ_INSERT_TAIL -inserts the new element -.Fa elm -at the end of the tail queue. -.Pp -The macro -.Nm STAILQ_INSERT_AFTER -inserts the new element -.Fa elm -after the element -.Fa listelm . -.Pp -The macro -.Nm STAILQ_LAST -returns the last item on the tail queue. -If the tail queue is empty the return value is -.Dv NULL . -.Pp -The macro -.Nm STAILQ_NEXT -returns the next item on the tail queue, or NULL this item is the last. -.Pp -The macro -.Nm STAILQ_REMOVE_AFTER -removes the element after -.Fa elm -from the tail queue. -Unlike -.Fa STAILQ_REMOVE , -this macro does not traverse the entire tail queue. -.Pp -The macro -.Nm STAILQ_REMOVE_HEAD -removes the element at the head of the tail queue. -For optimum efficiency, -elements being removed from the head of the tail queue should -use this macro explicitly rather than the generic -.Fa STAILQ_REMOVE -macro. -.Pp -The macro -.Nm STAILQ_REMOVE -removes the element -.Fa elm -from the tail queue. -Use of this macro should be avoided as it traverses the entire list. -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 -and -.Fa head2 . -.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE -.Bd -literal -STAILQ_HEAD(stailhead, entry) head = - STAILQ_HEAD_INITIALIZER(head); -struct stailhead *headp; /* Singly-linked tail queue head. */ -struct entry { - ... - STAILQ_ENTRY(entry) entries; /* Tail queue. */ - ... -} *n1, *n2, *n3, *np; - -STAILQ_INIT(&head); /* Initialize the queue. */ - -n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ -STAILQ_INSERT_HEAD(&head, n1, entries); - -n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ -STAILQ_INSERT_TAIL(&head, n1, entries); - -n2 = malloc(sizeof(struct entry)); /* Insert after. */ -STAILQ_INSERT_AFTER(&head, n1, n2, entries); - /* Deletion. */ -STAILQ_REMOVE(&head, n2, entry, entries); -free(n2); - /* Deletion from the head. */ -n3 = STAILQ_FIRST(&head); -STAILQ_REMOVE_HEAD(&head, entries); -free(n3); - /* Forward traversal. */ -STAILQ_FOREACH(np, &head, entries) - np-> ... - /* Safe forward traversal. */ -STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { - np->do_stuff(); - ... - STAILQ_REMOVE(&head, np, entry, entries); - free(np); -} - /* TailQ Deletion. */ -while (!STAILQ_EMPTY(&head)) { - n1 = STAILQ_FIRST(&head); - STAILQ_REMOVE_HEAD(&head, entries); - free(n1); -} - /* Faster TailQ Deletion. */ -n1 = STAILQ_FIRST(&head); -while (n1 != NULL) { - n2 = STAILQ_NEXT(n1, entries); - free(n1); - n1 = n2; -} -STAILQ_INIT(&head); -.Ed -.Sh LISTS -A list is headed by a structure defined by the -.Nm LIST_HEAD -macro. -This structure contains a single pointer to the first element -on the list. -The elements are doubly linked so that an arbitrary element can be -removed without traversing the list. -New elements can be added to the list after an existing element, -before an existing element, or at the head of the list. -A -.Fa LIST_HEAD -structure is declared as follows: -.Bd -literal -offset indent -LIST_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp -where -.Fa HEADNAME -is the name of the structure to be defined, and -.Fa TYPE -is the type of the elements to be linked into the list. -A pointer to the head of the list can later be declared as: -.Bd -literal -offset indent -struct HEADNAME *headp; -.Ed -.Pp -(The names -.Li head -and -.Li headp -are user selectable.) -.Pp -The macro -.Nm LIST_HEAD_INITIALIZER -evaluates to an initializer for the list -.Fa head . -.Pp -The macro -.Nm LIST_CONCAT -concatenates the list headed by -.Fa head2 -onto the end of the one headed by -.Fa head1 -removing all entries from the former. -Use of this macro should be avoided as it traverses the entirety of the -.Fa head1 -list. -A tail queue should be used if this macro is needed in -high-usage code paths or to operate on long lists. -.Pp -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 -declares a structure that connects the elements in -the list. -.Pp -The macro -.Nm LIST_FIRST -returns the first element in the list or NULL if the list -is empty. -.Pp -The macro -.Nm LIST_FOREACH -traverses the list referenced by -.Fa head -in the forward direction, assigning each element in turn to -.Fa var . -.Pp -The macro -.Nm LIST_FOREACH_FROM -behaves identically to -.Nm LIST_FOREACH -when -.Fa var -is NULL, else it treats -.Fa var -as a previously found LIST element and begins the loop at -.Fa var -instead of the first element in the LIST referenced by -.Fa head . -.Pp -The macro -.Nm LIST_FOREACH_SAFE -traverses the list referenced by -.Fa head -in the forward direction, assigning each element in turn to -.Fa var . -However, unlike -.Fn LIST_FOREACH -here it is permitted to both remove -.Fa var -as well as free it from within the loop safely without interfering with the -traversal. -.Pp -The macro -.Nm LIST_FOREACH_FROM_SAFE -behaves identically to -.Nm LIST_FOREACH_SAFE -when -.Fa var -is NULL, else it treats -.Fa var -as a previously found LIST element and begins the loop at -.Fa var -instead of the first element in the LIST referenced by -.Fa head . -.Pp -The macro -.Nm LIST_INIT -initializes the list referenced by -.Fa head . -.Pp -The macro -.Nm LIST_INSERT_HEAD -inserts the new element -.Fa elm -at the head of the list. -.Pp -The macro -.Nm LIST_INSERT_AFTER -inserts the new element -.Fa elm -after the element -.Fa listelm . -.Pp -The macro -.Nm LIST_INSERT_BEFORE -inserts the new element -.Fa elm -before the element -.Fa listelm . -.Pp -The macro -.Nm LIST_NEXT -returns the next element in the list, or NULL if this is the last. -.Pp -The macro -.Nm LIST_PREV -returns the previous element in the list, or NULL if this is the first. -List -.Fa head -must contain element -.Fa elm . -.Pp -The macro -.Nm LIST_REMOVE -removes the element -.Fa elm -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_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 -and -.Fa head2 . -.Sh LIST EXAMPLE -.Bd -literal -LIST_HEAD(listhead, entry) head = - LIST_HEAD_INITIALIZER(head); -struct listhead *headp; /* List head. */ -struct entry { - ... - LIST_ENTRY(entry) entries; /* List. */ - ... -} *n1, *n2, *n3, *np, *np_temp; - -LIST_INIT(&head); /* Initialize the list. */ - -n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ -LIST_INSERT_HEAD(&head, n1, entries); - -n2 = malloc(sizeof(struct entry)); /* Insert after. */ -LIST_INSERT_AFTER(n1, n2, entries); - -n3 = malloc(sizeof(struct entry)); /* Insert before. */ -LIST_INSERT_BEFORE(n2, n3, entries); - -LIST_REMOVE(n2, entries); /* Deletion. */ -free(n2); - /* Forward traversal. */ -LIST_FOREACH(np, &head, entries) - np-> ... - - /* Safe forward traversal. */ -LIST_FOREACH_SAFE(np, &head, entries, np_temp) { - np->do_stuff(); - ... - LIST_REMOVE(np, entries); - free(np); -} - -while (!LIST_EMPTY(&head)) { /* List Deletion. */ - n1 = LIST_FIRST(&head); - LIST_REMOVE(n1, entries); - free(n1); -} - -n1 = LIST_FIRST(&head); /* Faster List Deletion. */ -while (n1 != NULL) { - n2 = LIST_NEXT(n1, entries); - free(n1); - n1 = n2; -} -LIST_INIT(&head); -.Ed -.Sh TAIL QUEUES -A tail queue is headed by a structure defined by the -.Nm TAILQ_HEAD -macro. -This structure contains a pair of pointers, -one to the first element in the tail queue and the other to -the last element in the tail queue. -The elements are doubly linked so that an arbitrary element can be -removed without traversing the tail queue. -New elements can be added to the tail queue after an existing element, -before an existing element, at the head of the tail queue, -or at the end of the tail queue. -A -.Fa TAILQ_HEAD -structure is declared as follows: -.Bd -literal -offset indent -TAILQ_HEAD(HEADNAME, TYPE) head; -.Ed -.Pp -where -.Li HEADNAME -is the name of the structure to be defined, and -.Li TYPE -is the type of the elements to be linked into the tail queue. -A pointer to the head of the tail queue can later be declared as: -.Bd -literal -offset indent -struct HEADNAME *headp; -.Ed -.Pp -(The names -.Li head -and -.Li headp -are user selectable.) -.Pp -The macro -.Nm TAILQ_HEAD_INITIALIZER -evaluates to an initializer for the tail queue -.Fa head . -.Pp -The macro -.Nm TAILQ_CONCAT -concatenates the tail queue headed by -.Fa head2 -onto the end of the one headed by -.Fa head1 -removing all entries from the former. -.Pp -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 -declares a structure that connects the elements in -the tail queue. -.Pp -The macro -.Nm TAILQ_FIRST -returns the first item on the tail queue or NULL if the tail queue -is empty. -.Pp -The macro -.Nm TAILQ_FOREACH -traverses the tail queue referenced by -.Fa head -in the forward direction, assigning each element in turn to -.Fa var . -.Fa var -is set to -.Dv NULL -if the loop completes normally, or if there were no elements. -.Pp -The macro -.Nm TAILQ_FOREACH_FROM -behaves identically to -.Nm TAILQ_FOREACH -when -.Fa var -is NULL, else it treats -.Fa var -as a previously found TAILQ element and begins the loop at -.Fa var -instead of the first element in the TAILQ referenced by -.Fa head . -.Pp -The macro -.Nm TAILQ_FOREACH_REVERSE -traverses the tail queue referenced by -.Fa head -in the reverse direction, assigning each element in turn to -.Fa var . -.Pp -The macro -.Nm TAILQ_FOREACH_REVERSE_FROM -behaves identically to -.Nm TAILQ_FOREACH_REVERSE -when -.Fa var -is NULL, else it treats -.Fa var -as a previously found TAILQ element and begins the reverse loop at -.Fa var -instead of the last element in the TAILQ referenced by -.Fa head . -.Pp -The macros -.Nm TAILQ_FOREACH_SAFE -and -.Nm TAILQ_FOREACH_REVERSE_SAFE -traverse the list referenced by -.Fa head -in the forward or reverse direction respectively, -assigning each element in turn to -.Fa var . -However, unlike their unsafe counterparts, -.Nm TAILQ_FOREACH -and -.Nm TAILQ_FOREACH_REVERSE -permit to both remove -.Fa var -as well as free it from within the loop safely without interfering with the -traversal. -.Pp -The macro -.Nm TAILQ_FOREACH_FROM_SAFE -behaves identically to -.Nm TAILQ_FOREACH_SAFE -when -.Fa var -is NULL, else it treats -.Fa var -as a previously found TAILQ element and begins the loop at -.Fa var -instead of the first element in the TAILQ referenced by -.Fa head . -.Pp -The macro -.Nm TAILQ_FOREACH_REVERSE_FROM_SAFE -behaves identically to -.Nm TAILQ_FOREACH_REVERSE_SAFE -when -.Fa var -is NULL, else it treats -.Fa var -as a previously found TAILQ element and begins the reverse loop at -.Fa var -instead of the last element in the TAILQ referenced by -.Fa head . -.Pp -The macro -.Nm TAILQ_INIT -initializes the tail queue referenced by -.Fa head . -.Pp -The macro -.Nm TAILQ_INSERT_HEAD -inserts the new element -.Fa elm -at the head of the tail queue. -.Pp -The macro -.Nm TAILQ_INSERT_TAIL -inserts the new element -.Fa elm -at the end of the tail queue. -.Pp -The macro -.Nm TAILQ_INSERT_AFTER -inserts the new element -.Fa elm -after the element -.Fa listelm . -.Pp -The macro -.Nm TAILQ_INSERT_BEFORE -inserts the new element -.Fa elm -before the element -.Fa listelm . -.Pp -The macro -.Nm TAILQ_LAST -returns the last item on the tail queue. -If the tail queue is empty the return value is -.Dv NULL . -.Pp -The macro -.Nm TAILQ_NEXT -returns the next item on the tail queue, or NULL if this item is the last. -.Pp -The macro -.Nm TAILQ_PREV -returns the previous item on the tail queue, or NULL if this item -is the first. -.Pp -The macro -.Nm TAILQ_REMOVE -removes the element -.Fa elm -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_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 -and -.Fa head2 . -.Sh TAIL QUEUE EXAMPLE -.Bd -literal -TAILQ_HEAD(tailhead, entry) head = - TAILQ_HEAD_INITIALIZER(head); -struct tailhead *headp; /* Tail queue head. */ -struct entry { - ... - TAILQ_ENTRY(entry) entries; /* Tail queue. */ - ... -} *n1, *n2, *n3, *n4, *np; - -TAILQ_INIT(&head); /* Initialize the queue. */ - -n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ -TAILQ_INSERT_HEAD(&head, n1, entries); - -n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ -TAILQ_INSERT_TAIL(&head, n1, entries); - -n2 = malloc(sizeof(struct entry)); /* Insert after. */ -TAILQ_INSERT_AFTER(&head, n1, n2, entries); - -n3 = malloc(sizeof(struct entry)); /* Insert before. */ -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-> ... - /* Safe forward traversal. */ -TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { - np->do_stuff(); - ... - TAILQ_REMOVE(&head, np, entries); - free(np); -} - /* Reverse traversal. */ -TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) - np-> ... - /* TailQ Deletion. */ -while (!TAILQ_EMPTY(&head)) { - n1 = TAILQ_FIRST(&head); - TAILQ_REMOVE(&head, n1, entries); - free(n1); -} - /* Faster TailQ Deletion. */ -n1 = TAILQ_FIRST(&head); -while (n1 != NULL) { - n2 = TAILQ_NEXT(n1, entries); - free(n1); - n1 = n2; -} -TAILQ_INIT(&head); -.Ed -.Sh DIAGNOSTICS -.Nm queue(3) -provides several diagnostic and debugging facilities. -.Pp -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 overridden 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 occurred. -This behavior can be overridden by defining a custom -.Fn QMD_ASSERT -macro before first inclusion of -.In sys/queue.h . -.Pp -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 element -.Fa elm , -which must directly follow the element whose -.Va &SLIST_NEXT() -is -.Fa prev , -from the list. -This macro may insert, under conditions detailed above, check code that -validates that -.Fa elm -indeed follows -.Fa prev -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 -.Sh HISTORY -The -.Nm queue -functions first appeared in -.Bx 4.4 . diff --git a/share/man/man3/slist.3 b/share/man/man3/slist.3 new file mode 100644 --- /dev/null +++ b/share/man/man3/slist.3 @@ -0,0 +1,724 @@ +.\" Copyright (c) 1993 +.\" The Regents of the University of California. All rights reserved. +.\" Copyright (c) 2026 The FreeBSD Foundation. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.Dd January 18, 2026 +.Dt SLIST 3 +.Os +.Sh NAME +.Nm slist_concat , +.Nm slist_empty , +.Nm slist_empty_atomic , +.Nm slist_first , +.Nm slist_foreach , +.Nm slist_foreach_from , +.Nm slist_foreach_from_safe , +.Nm slist_foreach_safe , +.Nm slist_init , +.Nm slist_insert_after , +.Nm slist_insert_head , +.Nm slist_next , +.Nm slist_remove , +.Nm slist_remove_after , +.Nm slist_remove_head , +.Nm slist_remove_prevptr , +.Nm slist_split_after , +.Nm slist_swap , +.Nm SLIST_CLASS_ENTRY , +.Nm SLIST_CLASS_HEAD , +.Nm SLIST_CONCAT , +.Nm SLIST_EMPTY , +.Nm SLIST_EMPTY_ATOMIC , +.Nm SLIST_ENTRY , +.Nm SLIST_FIRST , +.Nm SLIST_FOREACH , +.Nm SLIST_FOREACH_FROM , +.Nm SLIST_FOREACH_FROM_SAFE , +.Nm SLIST_FOREACH_SAFE , +.Nm SLIST_HEAD , +.Nm SLIST_HEAD_INITIALIZER , +.Nm SLIST_INIT , +.Nm SLIST_INSERT_AFTER , +.Nm SLIST_INSERT_HEAD , +.Nm SLIST_NEXT , +.Nm SLIST_REMOVE , +.Nm SLIST_REMOVE_AFTER , +.Nm SLIST_REMOVE_HEAD , +.Nm SLIST_SPLIT_AFTER , +.Nm SLIST_SWAP +.Nd singly-linked list implementation +.Sh SYNOPSIS +.In sys/slist.h +.\" +.Ft void +.Fn slist_concat "struct slist *list1" "struct slist *list2" +.Ft bool +.Fn slist_empty "const struct slist *list" +.Ft bool +.Fn slist_empty_atomic "const struct slist *list" +.Ft "struct slist_node *" +.Fn slist_first "const struct slist *list" +.Fn slist_foreach "struct slist_node *var" "const struct slist *list" +.Fn slist_foreach_from "struct slist_node *var" "const struct slist *list" +.Fn slist_foreach_from_safe "struct slist_node *var" "const struct slist *list" "struct slist_node *tvar" +.Fn slist_foreach_safe "struct slist_node *var" "const struct slist *list" "struct slist_node *tvar" +.Ft void +.Fn slist_init "struct slist *list" +.Ft void +.Fn slist_insert_after "struct slist_node *slistnode" "struct slist_node *node" +.Ft void +.Fn slist_insert_head "struct slist *list" "struct slist_node *node" +.Ft "struct slist_node *" +.Fn slist_next "const struct slist_node *node" +.Ft void +.Fn slist_remove_after "struct slist_node *node" +.Ft void +.Fn slist_remove_head "struct slist *list" +.Ft void +.Fn slist_remove "struct slist *list" "struct slist_node *node" +.Ft void +.Fn slist_remove_prevptr "struct slist_node **prevp" "struct slist_node *node" +.Ft void +.Fn slist_split_after "struct slist *list" "struct slist_node *node" "struct slist *rest" +.Ft void +.Fn slist_swap "struct slist *list1" "struct slist *list2" +.\" +.In sys/queue.h +.\" +.Fn SLIST_CLASS_ENTRY "CLASSTYPE" +.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" +.Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" +.Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" +.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" +.Fn SLIST_HEAD "HEADNAME" "TYPE" +.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" +.Fn SLIST_INIT "SLIST_HEAD *head" +.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" +.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" +.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" +.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" +.\" +.Sh DESCRIPTION +Singly-linked lists are the simplest linked list data structure, +supporting only forward traversal. +They are ideal for applications with large datasets +and few or no removals, or for implementing a LIFO queue. +Singly-linked lists support the following operations: +.Bl -enum -compact -offset indent +.It +Insertion of a new entry at the head of the list. +.It +Insertion of a new entry after any element in the list. +.It +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. +.It +O(n) removal of any entry in the list. +.It +O(n) concatenation of two lists. +.El +.Pp +The +.Nm slist +implementation provides both a modern function-based API (recommended) +and a traditional macro-based API for compatibility. +The function-based API is recommended for new code as it provides: +.Bl -bullet -offset indent +.It +Type safety without requiring type parameters +.It +Better debugger support +.It +Simpler function signatures +.It +Compatible with both C and C++ +.El +.Ss Function-Based API +The function-based API uses standard structure types +.Vt struct slist +and +.Vt struct slist_node +defined in +.In sys/slist.h . +User-defined structures should embed +.Vt struct slist_node +and use +.Fa containerof +macro to convert node pointers to structure pointers. +.Pp +.Fn slist_concat +concatenates the list headed by +.Fa list2 +onto the end of the one headed by +.Fa list1 +removing all entries from the former. +Use of this function should be avoided as it traverses the entirety of the +.Fa list1 +list. +A singly-linked tail queue should be used if this operation is needed in +high-usage code paths or to operate on long lists. +.Pp +.Fn slist_empty +evaluates to true if there are no elements in the list. +.Fn slist_empty_atomic +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 +.Fn slist_first +returns the first element in the list or NULL if the list is empty. +.Pp +.Fn slist_foreach +traverses the list referenced by +.Fa list +in the forward direction, assigning each node in turn to +.Fa var . +.Pp +.Fn slist_foreach_from +behaves identically to +.Fn slist_foreach +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found node and begins the loop at +.Fa var +instead of the first node in the list referenced by +.Fa list . +.Pp +.Fn slist_foreach_safe +traverses the list referenced by +.Fa list +in the forward direction, assigning each node in turn to +.Fa var . +However, unlike +.Fn slist_foreach +here it is permitted to both remove +.Fa var +as well as free it from within the loop safely without interfering with the +traversal. +.Pp +.Fn slist_foreach_from_safe +behaves identically to +.Fn slist_foreach_safe +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found node and begins the loop at +.Fa var +instead of the first node in the list referenced by +.Fa list . +.Pp +.Fn slist_init +initializes the list referenced by +.Fa list . +.Pp +.Fn slist_insert_head +inserts the new element +.Fa node +at the head of the list. +.Pp +.Fn slist_insert_after +inserts the new element +.Fa node +after the element +.Fa slistnode . +.Pp +.Fn slist_next +returns the next element in the list. +.Pp +.Fn slist_remove_head +removes the element from the head of the list. +.Pp +.Fn slist_remove_after +removes the element after +.Fa node +from the list. +Unlike +.Fn slist_remove , +this function does not traverse the entire list. +.Pp +.Fn slist_remove +removes the element +.Fa node +from the list. +Use of this function should be avoided as it traverses the entire list. +A doubly-linked list should be used if this operation is needed in +high-usage code paths or to operate on long lists. +.Pp +.Fn slist_split_after +splits the list referenced by +.Fa list , +making +.Fa rest +reference the list formed by elements after +.Fa node +in +.Fa list . +.Pp +.Fn slist_swap +swaps the contents of +.Fa list1 +and +.Fa list2 . +.Ss Converting Between Node and Structure Pointers +Since the function-based API operates on node pointers +.Pf ( Vt struct slist_node ) , +user code needs to convert between node pointers and pointers to the +containing structure. +This is typically done using a +.Fn containerof +macro: +.Bd -literal -offset indent +containerof(ptr, type, member) +.Ed +.Pp +This macro takes a pointer to a structure member +.Fa ptr , +the type of the containing structure +.Fa type , +and the name of the member field +.Fa member , +and returns a pointer to the containing structure. +.Ss Macro-Based API +The macro-based API is provided for compatibility with existing code. +In the macro definitions, +.Fa TYPE +is the name of a user defined structure. +The structure must contain a field called +.Fa NAME +which is of type +.Li SLIST_ENTRY . +In the macro definitions, +.Fa CLASSTYPE +is the name of a user defined class. +The class must contain a field called +.Fa NAME +which is of type +.Li SLIST_CLASS_ENTRY . +The argument +.Fa HEADNAME +is the name of a user defined structure that must be declared +using the macros +.Li SLIST_HEAD +or +.Li SLIST_CLASS_HEAD . +See the examples below for further explanation of how these +macros are used. +.Pp +A singly-linked list is headed by a structure defined by the +.Nm SLIST_HEAD +macro. +This structure contains a single pointer to the first element +on the list. +The elements are singly linked for minimum space and pointer manipulation +overhead at the expense of O(n) removal for arbitrary elements. +New elements can be added to the list after an existing element or +at the head of the list. +An +.Fa SLIST_HEAD +structure is declared as follows: +.Bd -literal -offset indent +SLIST_HEAD(HEADNAME, TYPE) head; +.Ed +.Pp +where +.Fa HEADNAME +is the name of the structure to be defined, and +.Fa TYPE +is the type of the elements to be linked into the list. +A pointer to the head of the list can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The macro +.Nm SLIST_HEAD_INITIALIZER +evaluates to an initializer for the list +.Fa head . +.Pp +The macro +.Nm SLIST_CONCAT +concatenates the list headed by +.Fa head2 +onto the end of the one headed by +.Fa head1 +removing all entries from the former. +Use of this macro should be avoided as it traverses the entirety of the +.Fa head1 +list. +A singly-linked tail queue should be used if this macro is needed in +high-usage code paths or to operate on long lists. +.Pp +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 +declares a structure that connects the elements in +the list. +.Pp +The macro +.Nm SLIST_FIRST +returns the first element in the list or NULL if the list is empty. +.Pp +The macro +.Nm SLIST_FOREACH +traverses the list referenced by +.Fa head +in the forward direction, assigning each element in +turn to +.Fa var . +.Pp +The macro +.Nm SLIST_FOREACH_FROM +behaves identically to +.Nm SLIST_FOREACH +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found SLIST element and begins the loop at +.Fa var +instead of the first element in the SLIST referenced by +.Fa head . +.Pp +The macro +.Nm SLIST_FOREACH_SAFE +traverses the list referenced by +.Fa head +in the forward direction, assigning each element in +turn to +.Fa var . +However, unlike +.Fn SLIST_FOREACH +here it is permitted to both remove +.Fa var +as well as free it from within the loop safely without interfering with the +traversal. +.Pp +The macro +.Nm SLIST_FOREACH_FROM_SAFE +behaves identically to +.Nm SLIST_FOREACH_SAFE +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found SLIST element and begins the loop at +.Fa var +instead of the first element in the SLIST referenced by +.Fa head . +.Pp +The macro +.Nm SLIST_INIT +initializes the list referenced by +.Fa head . +.Pp +The macro +.Nm SLIST_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the list. +.Pp +The macro +.Nm SLIST_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Nm SLIST_NEXT +returns the next element in the list. +.Pp +The macro +.Nm SLIST_REMOVE_AFTER +removes the element after +.Fa elm +from the list. +Unlike +.Fa SLIST_REMOVE , +this macro does not traverse the entire list. +.Pp +The macro +.Nm SLIST_REMOVE_HEAD +removes the element +.Fa elm +from the head of the list. +For optimum efficiency, +elements being removed from the head of the list should explicitly use +this macro instead of the generic +.Fa SLIST_REMOVE +macro. +.Pp +The macro +.Nm SLIST_REMOVE +removes the element +.Fa elm +from the list. +Use of this macro should be avoided as it traverses the entire list. +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 +and +.Fa head2 . +.Sh EXAMPLES +.Ss Function-Based API Example +.Bd -literal +#include +#include + +struct entry { + ... + struct slist_node node; /* Singly-linked List. */ + ... +} *n1, *n2, *n3; +struct slist list; +struct slist_node *np, *np_temp; + +slist_init(&list); /* Initialize the list. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +slist_insert_head(&list, &n1->node); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +slist_insert_after(&n1->node, &n2->node); + +slist_remove(&list, &n2->node); /* Deletion. */ +free(n2); + +np = slist_first(&list); /* Deletion from the head. */ +slist_remove_head(&list); +n3 = containerof(np, struct entry, node); +free(n3); + /* Forward traversal. */ +slist_foreach(np, &list) { + n1 = containerof(np, struct entry, node); + n1-> ... +} + /* Safe forward traversal. */ +slist_foreach_safe(np, &list, np_temp) { + n1 = containerof(np, struct entry, entries); + n1->do_stuff(); + ... + slist_remove(&list, np); + free(n1); +} + /* List Deletion. */ +while (!slist_empty(&list)) { + np = slist_first(&list); + slist_remove_head(&list); + n1 = containerof(np, struct entry, entries); + free(n1); +} +.Ed +.Ss Macro-Based API Example +.Bd -literal +#include +#include + +SLIST_HEAD(slisthead, entry) head = + SLIST_HEAD_INITIALIZER(head); +struct slisthead *headp; /* Singly-linked List head. */ +struct entry { + ... + SLIST_ENTRY(entry) entries; /* Singly-linked List. */ + ... +} *n1, *n2, *n3, *np, *np_temp; + +SLIST_INIT(&head); /* Initialize the list. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +SLIST_INSERT_HEAD(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +SLIST_INSERT_AFTER(n1, n2, entries); + +SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */ +free(n2); + +n3 = SLIST_FIRST(&head); +SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */ +free(n3); + /* Forward traversal. */ +SLIST_FOREACH(np, &head, entries) + np-> ... + /* Safe forward traversal. */ +SLIST_FOREACH_SAFE(np, &head, entries, np_temp) { + np->do_stuff(); + ... + SLIST_REMOVE(&head, np, entry, entries); + free(np); +} + +while (!SLIST_EMPTY(&head)) { /* List Deletion. */ + n1 = SLIST_FIRST(&head); + SLIST_REMOVE_HEAD(&head, entries); + free(n1); +} +.Ed +.Sh DIAGNOSTICS +.In sys/queue.h +provides several diagnostic and debugging facilities. +.Pp +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 overridden 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 occurred. +This behavior can be overridden by defining a custom +.Fn QMD_ASSERT +macro before first inclusion of +.In sys/queue.h . +.Pp +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 element +.Fa elm , +which must directly follow the element whose +.Va &SLIST_NEXT() +is +.Fa prev , +from the list. +This macro may insert, under conditions detailed above, check code that +validates that +.Fa elm +indeed follows +.Fa prev +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 list 3 , +.Xr stailq 3 , +.Xr tailq 3 , +.Xr tree 3 +.Sh HISTORY +The +.Nm SLIST +macros first appeared in +.Bx 4.4 . +.Pp +The function-based API was introduced in +.Fx 15.1 . +.Sh AUTHORS +The function-based API was written by +.An Minsoo Choo Aq Mt minsoochoo0122@proton.me . diff --git a/share/man/man3/stailq.3 b/share/man/man3/stailq.3 new file mode 100644 --- /dev/null +++ b/share/man/man3/stailq.3 @@ -0,0 +1,761 @@ +.\" Copyright (c) 1993 +.\" The Regents of the University of California. All rights reserved. +.\" Copyright (c) 2026 The FreeBSD Foundation. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.Dd January 18, 2026 +.Dt STAILQ 3 +.Os +.Sh NAME +.Nm stailq_concat , +.Nm stailq_empty , +.Nm stailq_empty_atomic , +.Nm stailq_first , +.Nm stailq_foreach , +.Nm stailq_foreach_from , +.Nm stailq_foreach_from_safe , +.Nm stailq_foreach_safe , +.Nm stailq_init , +.Nm stailq_insert_after , +.Nm stailq_insert_head , +.Nm stailq_insert_tail , +.Nm stailq_last , +.Nm stailq_next , +.Nm stailq_remove , +.Nm stailq_remove_after , +.Nm stailq_remove_head , +.Nm stailq_reverse , +.Nm stailq_split_after , +.Nm stailq_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 , +.Nm STAILQ_FOREACH_FROM , +.Nm STAILQ_FOREACH_FROM_SAFE , +.Nm STAILQ_FOREACH_SAFE , +.Nm STAILQ_HEAD , +.Nm STAILQ_HEAD_INITIALIZER , +.Nm STAILQ_INIT , +.Nm STAILQ_INSERT_AFTER , +.Nm STAILQ_INSERT_HEAD , +.Nm STAILQ_INSERT_TAIL , +.Nm STAILQ_LAST , +.Nm STAILQ_NEXT , +.Nm STAILQ_REMOVE , +.Nm STAILQ_REMOVE_AFTER , +.Nm STAILQ_REMOVE_HEAD , +.Nm STAILQ_REVERSE , +.Nm STAILQ_SPLIT_AFTER , +.Nm STAILQ_SWAP +.Nd singly-linked tail queue implementation +.Sh SYNOPSIS +.In sys/stailq.h +.\" +.Ft void +.Fn stailq_concat "struct stailq *queue1" "struct stailq *queue2" +.Ft bool +.Fn stailq_empty "const struct stailq *queue" +.Ft bool +.Fn stailq_empty_atomic "const struct stailq *queue" +.Ft "struct stailq_node *" +.Fn stailq_first "const struct stailq *queue" +.Fn stailq_foreach "struct stailq_node *var" "const struct stailq *queue" +.Fn stailq_foreach_from "struct stailq_node *var" "const struct stailq *queue" +.Fn stailq_foreach_from_safe "struct stailq_node *var" "const struct stailq *queue" "struct stailq_node *tvar" +.Fn stailq_foreach_safe "struct stailq_node *var" "const struct stailq *queue" +.Ft void +.Fn stailq_init "struct stailq *queue" +.Ft void +.Fn stailq_insert_after "struct stailq *queue" "struct stailq_node *qnode" "struct stailq_node *node" +.Ft void +.Fn stailq_insert_head "struct stailq *queue" "struct stailq_node *node" +.Ft void +.Fn stailq_insert_tail "struct stailq *queue" "struct stailq_node *node" +.Ft "struct stailq_node *" +.Fn stailq_last "struct stailq *queue" +.Ft "struct stailq_node *" +.Fn stailq_next "const struct stailq_node *node" +.Ft void +.Fn stailq_remove_after "struct stailq *queue" "struct stailq_node *node" +.Ft void +.Fn stailq_remove_head "struct stailq *queue" +.Ft void +.Fn stailq_remove "struct stailq *queue" "struct stailq_node *node" +.Ft void +.Fn stailq_reverse "struct stailq *queue" +.Ft void +.Fn stailq_split_after "struct stailq *queue" "struct stailq_node *node" "struct stailq *rest" +.Ft void +.Fn stailq_swap "struct stailq *queue1" "struct stailq *queue2" +.\" +.In sys/queue.h +.\" +.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" +.Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" +.Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" +.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" +.Fn STAILQ_HEAD "HEADNAME" "TYPE" +.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" +.Fn STAILQ_INIT "STAILQ_HEAD *head" +.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" +.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" +.\" +.Sh DESCRIPTION +Singly-linked tail queues combine the benefits of singly-linked lists +with the ability to efficiently add elements at the tail. +They are ideal for applications with large datasets and +few or no removals, or for implementing a FIFO queue. +Singly-linked tail queues support the following operations: +.Bl -enum -compact -offset indent +.It +Insertion of a new entry at the head of the queue. +.It +Insertion of a new entry at the tail of the queue. +.It +Insertion of a new entry after any element in the queue. +.It +O(1) removal of an entry from the head of the queue. +.It +O(n) removal of any entry in the queue. +.It +Forward traversal through the queue. +.It +O(1) concatenation of two queues. +.It +Reversing the queue in place. +.It +Splitting a queue in two after any element in the queue. +.It +Swapping the contents of two queues. +.El +However: +.Bl -enum -compact -offset indent +.It +All queue insertions and removals must specify the head of the queue. +.It +Each head entry requires two pointers rather than one. +.It +Code size is about 15% greater and operations run about 20% slower +than singly-linked lists. +.El +.Pp +The +.Nm stailq +implementation provides both a modern function-based API (recommended) +and a traditional macro-based API for compatibility. +The function-based API is recommended for new code as it provides: +.Bl -bullet -offset indent +.It +Type safety without requiring type parameters +.It +Better debugger support +.It +Simpler function signatures +.It +Compatible with both C and C++ +.El +.Ss Function-Based API +The function-based API uses standard structure types +.Vt struct stailq +and +.Vt struct stailq_node +defined in +.In sys/stailq.h . +User-defined structures should embed +.Vt struct stailq_node +and use +.Fa containerof +macro to convert node pointers to structure pointers. +.Pp +.Fn stailq_concat +concatenates the tail queue headed by +.Fa queue2 +onto the end of the one headed by +.Fa queue1 +removing all entries from the former. +.Pp +.Fn stailq_empty +evaluates to true if there are no items on the tail queue. +.Fn stailq_empty_atomic +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 +.Fn stailq_first +returns the first item on the tail queue or NULL if the tail queue +is empty. +.Pp +.Fn stailq_foreach +traverses the tail queue referenced by +.Fa queue +in the forward direction, assigning each node in turn to +.Fa var . +.Pp +.Fn stailq_foreach_from +behaves identically to +.Fn stailq_foreach +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found node and begins the loop at +.Fa var +instead of the first node in the tail queue referenced by +.Fa queue . +.Pp +.Fn stailq_foreach_safe +traverses the tail queue referenced by +.Fa queue +in the forward direction, assigning each node in turn to +.Fa var . +However, unlike +.Fn stailq_foreach +here it is permitted to both remove +.Fa var +as well as free it from within the loop safely without interfering with the +traversal. +.Pp +.Fn stailq_foreach_from_safe +behaves identically to +.Fn stailq_foreach_safe +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found node and begins the loop at +.Fa var +instead of the first node in the tail queue referenced by +.Fa queue . +.Pp +.Fn stailq_init +initializes the tail queue referenced by +.Fa queue . +.Pp +.Fn stailq_insert_head +inserts the new element +.Fa node +at the head of the tail queue. +.Pp +.Fn stailq_insert_tail +inserts the new element +.Fa node +at the end of the tail queue. +.Pp +.Fn stailq_insert_after +inserts the new element +.Fa node +after the element +.Fa qnode . +.Pp +.Fn stailq_last +returns the last item on the tail queue or NULL if the tail queue +is empty. +.Pp +.Fn stailq_next +returns the next item on the tail queue, or NULL if this item is the last. +.Pp +.Fn stailq_remove_head +removes the element at the head of the tail queue. +For optimum efficiency, +elements being removed from the head of the tail queue should +use this function explicitly rather than the generic +.Fn stailq_remove . +.Pp +.Fn stailq_remove_after +removes the element after +.Fa node +from the tail queue. +Unlike +.Fn stailq_remove , +this function does not traverse the entire tail queue. +.Pp +.Fn stailq_remove +removes the element +.Fa node +from the tail queue. +Use of this function should be avoided as it traverses the entire queue. +A doubly-linked tail queue should be used if this operation is needed in +high-usage code paths or to operate on long tail queues. +.Pp +.Fn stailq_reverse +reverses the queue in place. +.Pp +.Fn stailq_split_after +splits the tail queue referenced by +.Fa queue , +making +.Fa rest +reference the tail queue formed by elements after +.Fa node +in +.Fa queue . +.Pp +.Fn stailq_swap +swaps the contents of +.Fa queue1 +and +.Fa queue2 . +.Ss Converting Between Node and Structure Pointers +Since the function-based API operates on node pointers +.Pf ( Vt struct stailq_node ) , +user code needs to convert between node pointers and pointers to the +containing structure. +This is typically done using a +.Fn containerof +macro: +.Bd -literal -offset indent +containerof(ptr, type, member) +.Ed +.Pp +This macro takes a pointer to a structure member +.Fa ptr , +the type of the containing structure +.Fa type , +and the name of the member field +.Fa member , +and returns a pointer to the containing structure. +.Ss Macro-Based API +The macro-based API is provided for compatibility with existing code. +In the macro definitions, +.Fa TYPE +is the name of a user defined structure. +The structure must contain a field called +.Fa NAME +which is of type +.Li STAILQ_ENTRY . +In the macro definitions, +.Fa CLASSTYPE +is the name of a user defined class. +The class must contain a field called +.Fa NAME +which is of type +.Li STAILQ_CLASS_ENTRY . +The argument +.Fa HEADNAME +is the name of a user defined structure that must be declared +using the macros +.Li STAILQ_HEAD , +.Li STAILQ_CLASS_HEAD. +See the examples below for further explanation of how these +macros are used. +.Pp +A singly-linked tail queue is headed by a structure defined by the +.Nm STAILQ_HEAD +macro. +This structure contains a pair of pointers, +one to the first element in the tail queue and the other to +the last element in the tail queue. +The elements are singly linked for minimum space and pointer +manipulation overhead at the expense of O(n) removal for arbitrary +elements. +New elements can be added to the tail queue after an existing element, +at the head of the tail queue, or at the end of the tail queue. +A +.Fa STAILQ_HEAD +structure is declared as follows: +.Bd -literal -offset indent +STAILQ_HEAD(HEADNAME, TYPE) head; +.Ed +.Pp +where +.Li HEADNAME +is the name of the structure to be defined, and +.Li TYPE +is the type of the elements to be linked into the tail queue. +A pointer to the head of the tail queue can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The macro +.Nm STAILQ_HEAD_INITIALIZER +evaluates to an initializer for the tail queue +.Fa head . +.Pp +The macro +.Nm STAILQ_CONCAT +concatenates the tail queue headed by +.Fa head2 +onto the end of the one headed by +.Fa head1 +removing all entries from the former. +.Pp +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 +declares a structure that connects the elements in +the tail queue. +.Pp +The macro +.Nm STAILQ_FIRST +returns the first item on the tail queue or NULL if the tail queue +is empty. +.Pp +The macro +.Nm STAILQ_FOREACH +traverses the tail queue referenced by +.Fa head +in the forward direction, assigning each element +in turn to +.Fa var . +.Pp +The macro +.Nm STAILQ_FOREACH_FROM +behaves identically to +.Nm STAILQ_FOREACH +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found STAILQ element and begins the loop at +.Fa var +instead of the first element in the STAILQ referenced by +.Fa head . +.Pp +The macro +.Nm STAILQ_FOREACH_SAFE +traverses the tail queue referenced by +.Fa head +in the forward direction, assigning each element +in turn to +.Fa var . +However, unlike +.Fn STAILQ_FOREACH +here it is permitted to both remove +.Fa var +as well as free it from within the loop safely without interfering with the +traversal. +.Pp +The macro +.Nm STAILQ_FOREACH_FROM_SAFE +behaves identically to +.Nm STAILQ_FOREACH_SAFE +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found STAILQ element and begins the loop at +.Fa var +instead of the first element in the STAILQ referenced by +.Fa head . +.Pp +The macro +.Nm STAILQ_INIT +initializes the tail queue referenced by +.Fa head . +.Pp +The macro +.Nm STAILQ_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the tail queue. +.Pp +The macro +.Nm STAILQ_INSERT_TAIL +inserts the new element +.Fa elm +at the end of the tail queue. +.Pp +The macro +.Nm STAILQ_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Nm STAILQ_LAST +returns the last item on the tail queue. +If the tail queue is empty the return value is +.Dv NULL . +.Pp +The macro +.Nm STAILQ_NEXT +returns the next item on the tail queue, or NULL this item is the last. +.Pp +The macro +.Nm STAILQ_REMOVE_AFTER +removes the element after +.Fa elm +from the tail queue. +Unlike +.Fa STAILQ_REMOVE , +this macro does not traverse the entire tail queue. +.Pp +The macro +.Nm STAILQ_REMOVE_HEAD +removes the element at the head of the tail queue. +For optimum efficiency, +elements being removed from the head of the tail queue should +use this macro explicitly rather than the generic +.Fa STAILQ_REMOVE +macro. +.Pp +The macro +.Nm STAILQ_REMOVE +removes the element +.Fa elm +from the tail queue. +Use of this macro should be avoided as it traverses the entire queue. +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 +and +.Fa head2 . +.Sh EXAMPLES +.Ss Function-Based API Example +.Bd -literal +#include +#include + +struct entry { + ... + struct stailq_node node; /* Tail queue. */ + ... +} *n1, *n2, *n3; +struct stailq queue; +struct stailq_node *np, *np_temp; + +stailq_init(&queue); /* Initialize the queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +stailq_insert_head(&queue, &n1->node); + +n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +stailq_insert_tail(&queue, &n2->node); + +n3 = malloc(sizeof(struct entry)); /* Insert after. */ +stailq_insert_after(&queue, &n1->node, &n3->node); + +stailq_remove(&queue, &n2->node); /* Deletion. */ +free(n2); + +np = stailq_first(&queue); /* Deletion from the head. */ +stailq_remove_head(&queue); +n1 = containerof(np, struct entry, node); +free(n1); + /* Forward traversal. */ +stailq_foreach(np, &queue) { + n1 = containerof(np, struct entry, node); + n1-> ... +} + /* Safe forward traversal. */ +stailq_foreach_safe(np, &queue, np_temp) { + n1 = containerof(np, struct entry, node); + n1->do_stuff(); + ... + stailq_remove(&queue, np); + free(n1); +} + /* TailQ Deletion. */ +while (!stailq_empty(&queue)) { + np = stailq_first(&queue); + stailq_remove_head(&queue); + n1 = containerof(np, struct entry, node); + free(n1); +} +.Ed +.Ss Macro-Based API Example +.Bd -literal +#include +#include + +STAILQ_HEAD(stailhead, entry) head = + STAILQ_HEAD_INITIALIZER(head); +struct stailhead *headp; /* Singly-linked tail queue head. */ +struct entry { + ... + STAILQ_ENTRY(entry) entries; /* Tail queue. */ + ... +} *n1, *n2, *n3, *np, *np_temp; + +STAILQ_INIT(&head); /* Initialize the queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +STAILQ_INSERT_HEAD(&head, n1, entries); + +n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +STAILQ_INSERT_TAIL(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +STAILQ_INSERT_AFTER(&head, n1, n2, entries); + /* Deletion. */ +STAILQ_REMOVE(&head, n2, entry, entries); +free(n2); + /* Deletion from the head. */ +n3 = STAILQ_FIRST(&head); +STAILQ_REMOVE_HEAD(&head, entries); +free(n3); + /* Forward traversal. */ +STAILQ_FOREACH(np, &head, entries) + np-> ... + /* Safe forward traversal. */ +STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { + np->do_stuff(); + ... + STAILQ_REMOVE(&head, np, entry, entries); + free(np); +} + /* TailQ Deletion. */ +while (!STAILQ_EMPTY(&head)) { + n1 = STAILQ_FIRST(&head); + STAILQ_REMOVE_HEAD(&head, entries); + free(n1); +} + /* Faster TailQ Deletion. */ +n1 = STAILQ_FIRST(&head); +while (n1 != NULL) { + n2 = STAILQ_NEXT(n1, entries); + free(n1); + n1 = n2; +} +STAILQ_INIT(&head); +.Ed +.Sh DIAGNOSTICS +.In sys/queue.h +provides several diagnostic and debugging facilities. +.Pp +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 overridden 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 occurred. +This behavior can be overridden by defining a custom +.Fn QMD_ASSERT +macro before first inclusion of +.In sys/queue.h . +.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 list 3 , +.Xr slist 3 , +.Xr tailq 3 , +.Xr tree 3 +.Sh HISTORY +The +.Nm STAILQ +macros first appeared in +.Bx 4.4 . +.Pp +The function-based API was introduced in +.Fx 15.1 . +.Sh AUTHORS +The function-based API was written by +.An Minsoo Choo Aq Mt minsoochoo0122@proton.me . diff --git a/share/man/man3/tailq.3 b/share/man/man3/tailq.3 new file mode 100644 --- /dev/null +++ b/share/man/man3/tailq.3 @@ -0,0 +1,881 @@ +.\" Copyright (c) 1993 +.\" The Regents of the University of California. All rights reserved. +.\" Copyright (c) 2026 The FreeBSD Foundation. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.Dd January 18, 2026 +.Dt TAILQ 3 +.Os +.Sh NAME +.Nm tailq_concat , +.Nm tailq_empty , +.Nm tailq_empty_atomic , +.Nm tailq_first , +.Nm tailq_foreach , +.Nm tailq_foreach_from , +.Nm tailq_foreach_from_safe , +.Nm tailq_foreach_reverse , +.Nm tailq_foreach_reverse_from , +.Nm tailq_foreach_reverse_from_safe , +.Nm tailq_foreach_reverse_safe , +.Nm tailq_foreach_safe , +.Nm tailq_init , +.Nm tailq_insert_after , +.Nm tailq_insert_before , +.Nm tailq_insert_head , +.Nm tailq_insert_tail , +.Nm tailq_last , +.Nm tailq_next , +.Nm tailq_prev , +.Nm tailq_remove , +.Nm tailq_replace , +.Nm tailq_split_after , +.Nm tailq_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 , +.Nm TAILQ_FOREACH_FROM , +.Nm TAILQ_FOREACH_FROM_SAFE , +.Nm TAILQ_FOREACH_REVERSE , +.Nm TAILQ_FOREACH_REVERSE_FROM , +.Nm TAILQ_FOREACH_REVERSE_FROM_SAFE , +.Nm TAILQ_FOREACH_REVERSE_SAFE , +.Nm TAILQ_FOREACH_SAFE , +.Nm TAILQ_HEAD , +.Nm TAILQ_HEAD_INITIALIZER , +.Nm TAILQ_INIT , +.Nm TAILQ_INSERT_AFTER , +.Nm TAILQ_INSERT_BEFORE , +.Nm TAILQ_INSERT_HEAD , +.Nm TAILQ_INSERT_TAIL , +.Nm TAILQ_LAST , +.Nm TAILQ_NEXT , +.Nm TAILQ_PREV , +.Nm TAILQ_REMOVE , +.Nm TAILQ_REPLACE , +.Nm TAILQ_SPLIT_AFTER , +.Nm TAILQ_SWAP +.Nd doubly-linked tail queue implementation +.Sh SYNOPSIS +.In sys/tailq.h +.\" +.Ft void +.Fn tailq_concat "struct tailq *queue1" "struct tailq *queue2" +.Ft bool +.Fn tailq_empty "const struct tailq *queue" +.Ft bool +.Fn tailq_empty_atomic "const struct tailq *queue" +.Ft "struct tailq_node *" +.Fn tailq_foreach "struct tailq_node *var" "const struct tailq *queue" +.Fn tailq_foreach_from "struct tailq_node *var" "const struct tailq *queue" +.Fn tailq_foreach_from_safe "struct tailq_node *var" "const struct tailq *queue" "struct tailq_node *tvar" +.Fn tailq_foreach_reverse "struct tailq_node *var" "const struct tailq *queue" +.Fn tailq_foreach_reverse_from "struct tailq_node *var" "const struct tailq *queue" +.Fn tailq_foreach_reverse_from_safe "struct tailq_node *var" "const struct tailq *queue" "struct tailq_node *tvar" +.Fn tailq_foreach_reverse_safe "struct tailq_node *var" "const struct tailq *queue" "struct tailq_node *tvar" +.Fn tailq_foreach_safe "struct tailq_node *var" "const struct tailq *queue" "struct tailq_node *tvar" +.Fn tailq_first "const struct tailq *queue" +.Ft void +.Fn tailq_init "struct tailq *queue" +.Ft void +.Fn tailq_insert_after "struct tailq *queue" "struct tailq_node *qnode" "struct tailq_node *node" +.Ft void +.Fn tailq_insert_before "struct tailq_node *qnode" "struct tailq_node *node" +.Ft void +.Fn tailq_insert_head "struct tailq *queue" "struct tailq_node *node" +.Ft void +.Fn tailq_insert_tail "struct tailq *queue" "struct tailq_node *node" +.Ft "struct tailq_node *" +.Fn tailq_last "const struct tailq *queue" +.Ft "struct tailq_node *" +.Fn tailq_next "const struct tailq_node *node" +.Ft "struct tailq_node *" +.Fn tailq_prev "const struct tailq_node *node" "const struct tailq *queue" +.Ft void +.Fn tailq_remove "struct tailq *queue" "struct tailq_node *node" +.Ft void +.Fn tailq_replace "struct tailq *queue" "struct tailq_node *node" "struct tailq_node *node2" +.Ft void +.Fn tailq_split_after "struct tailq *queue" "struct tailq_node *node" "struct tailq *rest" +.Ft void +.Fn tailq_swap "struct tailq *queue1" "struct tailq *queue2" +.\" +.In sys/queue.h +.\" +.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" +.Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" +.Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" +.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" +.Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" +.Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" +.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" +.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" +.Fn TAILQ_HEAD "HEADNAME" "TYPE" +.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" +.Fn TAILQ_INIT "TAILQ_HEAD *head" +.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" +.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" +.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" +.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" +.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" +.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_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 +Tail queues are doubly-linked lists with the ability to efficiently +add elements at both the head and tail. +The elements are doubly linked so that an arbitrary element can be +removed without traversing the tail queue, and bidirectional traversal is possible. +They are the most feature-rich of the queue implementations. +Tail queues support the following operations: +.Bl -enum -compact -offset indent +.It +Insertion of a new entry at the head of the queue. +.It +Insertion of a new entry at the tail of the queue. +.It +Insertion of a new entry after any element in the queue. +.It +Insertion of a new entry before any element in the queue. +.It +O(1) removal of any entry in the queue. +.It +Forward and backward traversal through the queue. +.It +O(1) concatenation of two queues. +.It +Splitting a queue in two after any element in the queue. +.It +Swapping the contents of two queues. +.El +However: +.Bl -enum -compact -offset indent +.It +All queue insertions and removals must specify the head of the queue. +.It +Each head entry requires two pointers rather than one. +.It +Each element requires two pointers rather than one. +.It +Code size is about 15% greater and operations run about 20% slower +than singly-linked lists. +.El +.Pp +The +.Nm tailq +implementation provides both a modern function-based API (recommended) +and a traditional macro-based API for compatibility. +The function-based API is recommended for new code as it provides: +.Bl -bullet +.It +Type safety without requiring type parameters +.It +Better debugger support +.It +Simpler function signatures +.It +Compatible with both C and C++ +.El +.Ss Function-Based API +The function-based API uses standard structure types +.Vt struct tailq +and +.Vt struct tailq_node +defined in +.In sys/tailq.h . +User-defined structures should embed +.Vt struct tailq_node +and use +.Fa containerof +macro to convert node pointers to structure pointers. +.Pp +.Fn tailq_concat +concatenates the tail queue headed by +.Fa queue2 +onto the end of the one headed by +.Fa queue1 +removing all entries from the former. +.Pp +.Fn tailq_empty +evaluates to true if there are no items on the tail queue. +.Fn tailq_empty_atomic +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 +.Fn tailq_first +returns the first item on the tail queue or NULL if the tail queue +is empty. +.Pp +.Fn tailq_foreach +traverses the tail queue referenced by +.Fa queue +in the forward direction, assigning each node in turn to +.Fa var . +.Pp +.Fn tailq_foreach_from +behaves identically to +.Fn tailq_foreach +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found node and begins the loop at +.Fa var +instead of the first node in the tail queue referenced by +.Fa queue . +.Pp +.Fn tailq_foreach_safe +traverses the tail queue referenced by +.Fa queue +in the forward direction, assigning each node in turn to +.Fa var . +However, unlike +.Fn tailq_foreach +here it is permitted to both remove +.Fa var +as well as free it from within the loop safely without interfering with the +traversal. +.Pp +.Fn tailq_foreach_from_safe +behaves identically to +.Fn tailq_foreach_safe +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found node and begins the loop at +.Fa var +instead of the first node in the tail queue referenced by +.Fa queue . +.Pp +.Fn tailq_foreach_reverse +traverses the tail queue referenced by +.Fa queue +in the reverse direction, assigning each node in turn to +.Fa var . +.Pp +.Fn tailq_foreach_reverse_from +behaves identically to +.Fn tailq_foreach_reverse +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found node and begins the reverse loop at +.Fa var +instead of the last node in the tail queue referenced by +.Fa queue . +.Pp +.Fn tailq_foreach_reverse_safe +traverses the tail queue referenced by +.Fa queue +in the reverse direction, assigning each node in turn to +.Fa var . +However, unlike +.Fn tailq_foreach_reverse +here it is permitted to both remove +.Fa var +as well as free it from within the loop safely without interfering with the +traversal. +.Pp +.Fn tailq_foreach_reverse_from_safe +behaves identically to +.Fn tailq_foreach_reverse_safe +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found node and begins the reverse loop at +.Fa var +instead of the last node in the tail queue referenced by +.Fa queue . +.Pp +.Fn tailq_init +initializes the tail queue referenced by +.Fa queue . +.Pp +.Fn tailq_insert_head +inserts the new element +.Fa node +at the head of the tail queue. +.Pp +.Fn tailq_insert_tail +inserts the new element +.Fa node +at the end of the tail queue. +.Pp +.Fn tailq_insert_after +inserts the new element +.Fa node +after the element +.Fa qnode . +.Pp +.Fn tailq_insert_before +inserts the new element +.Fa node +before the element +.Fa qnode . +.Pp +.Fn tailq_last +returns the last item on the tail queue. +If the tail queue is empty the return value is +.Dv NULL . +.Pp +.Fn tailq_next +returns the next item on the tail queue, or NULL if this item is the last. +.Pp +.Fn tailq_prev +returns the previous item on the tail queue, or NULL if this item +is the first. +.Pp +.Fn tailq_remove +removes the element +.Fa node +from the tail queue. +.Pp +.Fn tailq_replace +replaces the element +.Fa node +with +.Fa node2 +in the tail queue. +The element +.Fa node2 +must not already be on a queue. +.Pp +.Fn tailq_split_after +splits the tail queue referenced by +.Fa queue , +making +.Fa rest +reference the tail queue formed by elements after +.Fa node +in +.Fa queue . +.Pp +.Fn tailq_swap +swaps the contents of +.Fa queue1 +and +.Fa queue2 . +.Ss Converting Between Node and Structure Pointers +Since the function-based API operates on node pointers +.Pf ( Vt struct tailq_node ) , +user code needs to convert between node pointers and pointers to the +containing structure. +This is typically done using a +.Fn containerof +macro: +.Bd -literal -offset indent +containerof(ptr, type, member) +.Ed +.Pp +This macro takes a pointer to a structure member +.Fa ptr , +the type of the containing structure +.Fa type , +and the name of the member field +.Fa member , +and returns a pointer to the containing structure. +.Ss Macro-Based API +The macro-based API is provided for compatibility with existing code. +In the macro definitions, +.Fa TYPE +is the name of a user defined structure. +The structure must contain a field called +.Fa NAME +which is of type +.Li TAILQ_ENTRY . +In the macro definitions, +.Fa CLASSTYPE +is the name of a user defined class. +The class must contain a field called +.Fa NAME +which is of type +.Li TAILQ_CLASS_ENTRY . +The argument +.Fa HEADNAME +is the name of a user defined structure that must be declared +using the macros +.Li TAILQ_HEAD +or +.Li TAILQ_CLASS_HEAD . +See the examples below for further explanation of how these +macros are used. +.Pp +A tail queue is headed by a structure defined by the +.Nm TAILQ_HEAD +macro. +This structure contains a pair of pointers, +one to the first element in the tail queue and the other to +the last element in the tail queue. +The elements are doubly linked so that an arbitrary element can be +removed without traversing the tail queue. +New elements can be added to the tail queue after an existing element, +before an existing element, at the head of the tail queue, +or at the end of the tail queue. +A +.Fa TAILQ_HEAD +structure is declared as follows: +.Bd -literal -offset indent +TAILQ_HEAD(HEADNAME, TYPE) head; +.Ed +.Pp +where +.Li HEADNAME +is the name of the structure to be defined, and +.Li TYPE +is the type of the elements to be linked into the tail queue. +A pointer to the head of the tail queue can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The macro +.Nm TAILQ_HEAD_INITIALIZER +evaluates to an initializer for the tail queue +.Fa head . +.Pp +The macro +.Nm TAILQ_CONCAT +concatenates the tail queue headed by +.Fa head2 +onto the end of the one headed by +.Fa head1 +removing all entries from the former. +.Pp +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 +declares a structure that connects the elements in +the tail queue. +.Pp +The macro +.Nm TAILQ_FIRST +returns the first item on the tail queue or NULL if the tail queue +is empty. +.Pp +The macro +.Nm TAILQ_FOREACH +traverses the tail queue referenced by +.Fa head +in the forward direction, assigning each element in turn to +.Fa var . +.Fa var +is set to +.Dv NULL +if the loop completes normally, or if there were no elements. +.Pp +The macro +.Nm TAILQ_FOREACH_FROM +behaves identically to +.Nm TAILQ_FOREACH +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found TAILQ element and begins the loop at +.Fa var +instead of the first element in the TAILQ referenced by +.Fa head . +.Pp +The macro +.Nm TAILQ_FOREACH_REVERSE +traverses the tail queue referenced by +.Fa head +in the reverse direction, assigning each element in turn to +.Fa var . +.Pp +The macro +.Nm TAILQ_FOREACH_REVERSE_FROM +behaves identically to +.Nm TAILQ_FOREACH_REVERSE +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found TAILQ element and begins the reverse loop at +.Fa var +instead of the last element in the TAILQ referenced by +.Fa head . +.Pp +The macros +.Nm TAILQ_FOREACH_SAFE +and +.Nm TAILQ_FOREACH_REVERSE_SAFE +traverse the queue referenced by +.Fa head +in the forward or reverse direction respectively, +assigning each element in turn to +.Fa var . +However, unlike their unsafe counterparts, +.Nm TAILQ_FOREACH +and +.Nm TAILQ_FOREACH_REVERSE +permit to both remove +.Fa var +as well as free it from within the loop safely without interfering with the +traversal. +.Pp +The macro +.Nm TAILQ_FOREACH_FROM_SAFE +behaves identically to +.Nm TAILQ_FOREACH_SAFE +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found TAILQ element and begins the loop at +.Fa var +instead of the first element in the TAILQ referenced by +.Fa head . +.Pp +The macro +.Nm TAILQ_FOREACH_REVERSE_FROM_SAFE +behaves identically to +.Nm TAILQ_FOREACH_REVERSE_SAFE +when +.Fa var +is NULL, else it treats +.Fa var +as a previously found TAILQ element and begins the reverse loop at +.Fa var +instead of the last element in the TAILQ referenced by +.Fa head . +.Pp +The macro +.Nm TAILQ_INIT +initializes the tail queue referenced by +.Fa head . +.Pp +The macro +.Nm TAILQ_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the tail queue. +.Pp +The macro +.Nm TAILQ_INSERT_TAIL +inserts the new element +.Fa elm +at the end of the tail queue. +.Pp +The macro +.Nm TAILQ_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Nm TAILQ_INSERT_BEFORE +inserts the new element +.Fa elm +before the element +.Fa listelm . +.Pp +The macro +.Nm TAILQ_LAST +returns the last item on the tail queue. +If the tail queue is empty the return value is +.Dv NULL . +.Pp +The macro +.Nm TAILQ_NEXT +returns the next item on the tail queue, or NULL if this item is the last. +.Pp +The macro +.Nm TAILQ_PREV +returns the previous item on the tail queue, or NULL if this item +is the first. +.Pp +The macro +.Nm TAILQ_REMOVE +removes the element +.Fa elm +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_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 +and +.Fa head2 . +.Sh EXAMPLES +.Ss Function-Based API Example +.Bd -literal +#include +#include + +struct entry { + ... + struct tailq_node node; /* Tail queue. */ + ... +} *n1, *n2, *n3, *n4; +struct tailq queue; +struct tailq_node *np, *np_temp; + +tailq_init(&queue); /* Initialize the queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +tailq_insert_head(&queue, &n1->node); + +n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +tailq_insert_tail(&queue, &n2->node); + +n3 = malloc(sizeof(struct entry)); /* Insert after. */ +tailq_insert_after(&queue, &n1->node, &n3->node); + +n4 = malloc(sizeof(struct entry)); /* Insert before. */ +tailq_insert_before(&n2->node, &n4->node); + +tailq_remove(&queue, &n2->node); /* Deletion. */ +free(n2); + /* Replacement. */ +struct entry *n5 = malloc(sizeof(struct entry)); +tailq_replace(&queue, &n3->node, &n5->node); +free(n3); + /* Forward traversal. */ +tailq_foreach(np, &queue) { + n1 = containerof(np, struct entry, node); + n1-> ... +} + /* Safe forward traversal. */ +tailq_foreach_safe(np, &queue, np_temp) { + n1 = containerof(np, struct entry, node); + n1->do_stuff(); + ... + tailq_remove(&queue, np); + free(n1); +} + /* Reverse traversal. */ +tailq_foreach_reverse(np, &queue) { + n1 = containerof(np, struct entry, node); + n1-> ... +} + /* TailQ Deletion. */ +while (!tailq_empty(&queue)) { + np = tailq_first(&queue); + n1 = containerof(np, struct entry, node); + tailq_remove(&queue, &n1->node); + free(n1); +} + /* Faster TailQ Deletion. */ +np = tailq_first(&queue); +while (np != NULL) { + np_temp = tailq_next(np); + n1 = containerof(np, struct entry, node); + free(n1); + np = np_temp; +} +tailq_init(&queue); +.Ed +.Ss Macro-Based API Example +.Bd -literal +#include +#include + +TAILQ_HEAD(tailhead, entry) head = + TAILQ_HEAD_INITIALIZER(head); +struct tailhead *headp; /* Tail queue head. */ +struct entry { + ... + TAILQ_ENTRY(entry) entries; /* Tail queue. */ + ... +} *n1, *n2, *n3, *n4, *np; + +TAILQ_INIT(&head); /* Initialize the queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +TAILQ_INSERT_HEAD(&head, n1, entries); + +n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +TAILQ_INSERT_TAIL(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +TAILQ_INSERT_AFTER(&head, n1, n2, entries); + +n3 = malloc(sizeof(struct entry)); /* Insert before. */ +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-> ... + /* Safe forward traversal. */ +TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { + np->do_stuff(); + ... + TAILQ_REMOVE(&head, np, entries); + free(np); +} + /* Reverse traversal. */ +TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) + np-> ... + /* TailQ Deletion. */ +while (!TAILQ_EMPTY(&head)) { + n1 = TAILQ_FIRST(&head); + TAILQ_REMOVE(&head, n1, entries); + free(n1); +} + /* Faster TailQ Deletion. */ +n1 = TAILQ_FIRST(&head); +while (n1 != NULL) { + n2 = TAILQ_NEXT(n1, entries); + free(n1); + n1 = n2; +} +TAILQ_INIT(&head); +.Ed +.Sh DIAGNOSTICS +.In sys/queue.h +provides several diagnostic and debugging facilities. +.Pp +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 overridden 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 occurred. +This behavior can be overridden by defining a custom +.Fn QMD_ASSERT +macro before first inclusion of +.In sys/queue.h . +.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 list 3 , +.Xr slist 3 , +.Xr stailq 3 , +.Xr tree 3 +.Sh HISTORY +The +.Nm TAILQ +macros first appeared in +.Bx 4.4 . +.Pp +The function-based API was introduced in +.Fx 15.1 . +.Sh AUTHORS +The function-based API was written by +.An Minsoo Choo Aq Mt minsoochoo0122@proton.me . diff --git a/share/man/man3/tree.3 b/share/man/man3/tree.3 --- a/share/man/man3/tree.3 +++ b/share/man/man3/tree.3 @@ -28,7 +28,7 @@ .\" (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF .\" THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. .\" -.Dd August 2, 2024 +.Dd January 17, 2026 .Dt TREE 3 .Os .Sh NAME @@ -796,7 +796,10 @@ to indicate an error. .Sh SEE ALSO .Xr arb 3 , -.Xr queue 3 +.Xr list 3 , +.Xr slist 3 , +.Xr stailq 3 , +.Xr tailq 3 .Rs .%A "Bernhard Haeupler" .%A "Siddhartha Sen" diff --git a/share/man/man9/ifnet.9 b/share/man/man9/ifnet.9 --- a/share/man/man9/ifnet.9 +++ b/share/man/man9/ifnet.9 @@ -26,7 +26,7 @@ .\" OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.Dd December 10, 2024 +.Dd January 17, 2026 .Dt IFNET 9 .Os .Sh NAME @@ -356,7 +356,7 @@ The system keeps a linked list of interfaces using the .Li TAILQ macros defined in -.Xr queue 3 ; +.Xr tailq 3 ; this list is headed by a .Vt "struct ifnethead" called @@ -1163,7 +1163,7 @@ A link back to the interface structure. .It Va ifa_link .Pq Fn TAILQ_ENTRY ifaddr -.Xr queue 3 +.Xr tailq 3 glue for list of addresses on each interface. .It Va ifa_rtrequest See below. @@ -1220,7 +1220,7 @@ .Bl -tag -width ".Va ifma_refcount" -offset indent .It Va ifma_link .Pq Fn LIST_ENTRY ifmultiaddr -.Xr queue 3 +.Xr list 3 macro glue. .It Va ifma_addr .Pq Vt "struct sockaddr *" @@ -1672,8 +1672,9 @@ .Sh SEE ALSO .Xr ioctl 2 , .Xr link_addr 3 , -.Xr queue 3 , +.Xr list 3 , .Xr sysctl 3 , +.Xr tailq 3 , .Xr bpf 4 , .Xr ifmib 4 , .Xr lo 4 , diff --git a/share/man/man9/intro.9 b/share/man/man9/intro.9 --- a/share/man/man9/intro.9 +++ b/share/man/man9/intro.9 @@ -6,7 +6,7 @@ .\" This manual page was written by Mitchell Horne under .\" sponsorship from the FreeBSD Foundation. .\" -.Dd January 30, 2024 +.Dd January 17, 2026 .Dt INTRO 9 .Os .Sh NAME @@ -66,8 +66,14 @@ Hash map implementation. .It Xr nv 9 Name/value pairs. -.It Xr queue 3 -Singly-linked and doubly-linked lists, and queues. +.It Xr slist 3 +Singly-linked lists. +.It Xr list 3 +Doubly-linked lists. +.It Xr stailq 3 +Singly-linked queues. +.It Xr tailq 3 +Doubly-linked queues. .It Xr refcount 9 An SMP-safe implementation of reference counts. .It Xr sbuf 9 diff --git a/share/man/man9/mbuf_tags.9 b/share/man/man9/mbuf_tags.9 --- a/share/man/man9/mbuf_tags.9 +++ b/share/man/man9/mbuf_tags.9 @@ -18,7 +18,7 @@ .\" MERCHANTABILITY OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR .\" PURPOSE. .\" -.Dd December 28, 2021 +.Dd January 17, 2026 .Dt MBUF_TAGS 9 .Os .Sh NAME @@ -108,7 +108,7 @@ The .Va m_tag_link field is used to link tags together (see -.Xr queue 3 +.Xr slist 3 for more details). The .Va m_tag_id , m_tag_len @@ -275,7 +275,7 @@ Inlined functions are defined in .In sys/mbuf.h . .Sh SEE ALSO -.Xr queue 3 , +.Xr slist 3 , .Xr mbuf 9 .Sh HISTORY The packet tags first appeared in diff --git a/share/man/man9/style.9 b/share/man/man9/style.9 --- a/share/man/man9/style.9 +++ b/share/man/man9/style.9 @@ -22,7 +22,7 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.Dd July 28, 2025 +.Dd January 17, 2026 .Dt STYLE 9 .Os .Sh NAME @@ -384,7 +384,11 @@ .Ed .Pp Use -.Xr queue 3 +.Xr list 3 , +.Xr slist 3 , +.Xr stailq 3 , +and +.Xr tailq 3 macros rather than rolling your own lists, whenever possible. Thus, the previous example would be better written: @@ -1008,7 +1012,10 @@ not just at the start of blocks. .Pp Standard library containers should be used in preference to -.Xr queue 3 +.Xr list 3 , +.Xr slist 3 , +.Xr stailq 3 , +.Xr tailq 3 , or .Xr tree 3 macros. diff --git a/share/man/man9/sysctl_ctx_init.9 b/share/man/man9/sysctl_ctx_init.9 --- a/share/man/man9/sysctl_ctx_init.9 +++ b/share/man/man9/sysctl_ctx_init.9 @@ -25,7 +25,7 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.Dd July 31, 2014 +.Dd January 17, 2026 .Dt SYSCTL_CTX_INIT 9 .Os .Sh NAME @@ -88,7 +88,7 @@ and it will be updated with entries pointing to newly created OIDS. .Pp Internally, the context is represented as a -.Xr queue 3 +.Xr tailq 3 TAILQ linked list. The list consists of .Li struct sysctl_ctx_entry @@ -222,7 +222,7 @@ call, which starts by freeing the newest entries (leaves) and then proceeds to free the older entries (in this case the nodes). .Sh SEE ALSO -.Xr queue 3 , +.Xr tailq 3 , .Xr sysctl 8 , .Xr sysctl 9 , .Xr sysctl_add_oid 9 , diff --git a/share/man/man9/zone.9 b/share/man/man9/zone.9 --- a/share/man/man9/zone.9 +++ b/share/man/man9/zone.9 @@ -23,7 +23,7 @@ .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF .\" SUCH DAMAGE. .\" -.Dd January 16, 2023 +.Dd January 17, 2026 .Dt UMA 9 .Os .Sh NAME @@ -194,7 +194,11 @@ .Fa dtor callbacks might be to initialize a data structure embedded in the item, such as a -.Xr queue 3 +.Xr list 3 , +.Xr slist 3 , +.Xr stailq 3 , +or +.Xr tailq 3 head. .Pp The diff --git a/sys/sys/list.h b/sys/sys/list.h new file mode 100644 --- /dev/null +++ b/sys/sys/list.h @@ -0,0 +1,194 @@ +/* + * Copyright (c) 2026 The FreeBSD Foundation + * + * This software was developed by Minsoo Choo under sponsorship from the + * FreeBSD Foundation. + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#ifndef _SYS_LIST_H_ +#define _SYS_LIST_H_ + +#include +#include +#include + +/* + * This is a non-macro implementation of LIST_* equivalent to queue(3). + * + * A list is headed by a single forward pointer (or an array of forward + * pointers for a hash table header). The nodes are doubly linked + * so that an arbitrary node can be removed without a need to + * traverse the list. New nodes can be added to the list before + * or after an existing node or at the head of the list. A list + * may be traversed in either direction. + */ + +/* + * List declarations. + */ + +struct list_node { + struct list_node *next; /* next node */ + struct list_node **prev; /* address of previous next node */ +}; + +struct list { + struct list_node *first; /* first node */ +}; + +/* + * List functions and macros. + */ + +static inline bool list_empty(const struct list *); +static inline void list_init(struct list *); + +static inline void +list_concat(struct list *list1, struct list *list2) +{ + struct list_node *curnode = list1->first; + if (curnode == NULL) { + if ((list1->first = list2->first) != NULL) { + list2->first->prev = &list1->first; + list_init(list2); + } + } else if (list2->first != NULL) { + while (curnode->next != NULL) + curnode = curnode->next; + curnode->next = list2->first; + list2->first->prev = &curnode->next; + list_init(list2); + } +} + +static inline bool +list_empty(const struct list *list) +{ + return list->first == NULL; +} + +static inline bool +list_empty_atomic(const struct list *list) +{ + return atomic_load_ptr(&list->first) == NULL; +} + +static inline struct list_node * +list_first(const struct list *list) +{ + return list->first; +} + +#define list_foreach(var, list) \ + for ((var) = list_first(list); \ + (var) != NULL; \ + (var) = list_next(var)) + +#define list_foreach_from(var, list) \ + for ((var) = ((var) != NULL ? (var) : list_first(list)); \ + (var) != NULL; \ + (var) = list_next(var)) + +#define list_foreach_safe(var, list, tvar) \ + for ((var) = list_first(list); \ + (var) != NULL && ((tvar) = list_next(var), 1); \ + (var) = (tvar)) + +#define list_foreach_from_safe(var, list, tvar) \ + for ((var) = ((var) != NULL ? (var) : list_first(list)); \ + (var) != NULL && ((tvar) = list_next(var), 1); \ + (var) = (tvar)) + +static inline void +list_init(struct list *list) +{ + list->first = NULL; +} + +static inline void +list_insert_after(struct list_node *listnode, struct list_node *node) +{ + if ((node->next = listnode->next) != NULL) + listnode->next->prev = &node->next; + listnode->next = node; + node->prev = &listnode->next; +} + +static inline void +list_insert_before(struct list_node *listnode, struct list_node *node) +{ + node->prev = listnode->prev; + node->next = listnode; + *listnode->prev = node; + listnode->prev = &node->next; +} + +static inline void +list_insert_head(struct list *list, struct list_node *node) +{ + if ((node->next = list->first) != NULL) + list->first->prev = &node->next; + list->first = node; + node->prev = &list->first; +} + +static inline struct list_node * +list_next(const struct list_node *node) +{ + return node->next; +} + +static inline struct list_node * +list_prev(const struct list_node *node, const struct list *list) +{ + return node->prev == &list->first ? NULL : + (struct list_node *)((char *)node->prev - + offsetof(struct list_node, next)); +} + +static inline void +list_remove(struct list_node *node) +{ + if (node->next != NULL) + node->next->prev = node->prev; + *node->prev = node->next; +} + +static inline void +list_replace(struct list_node *node, struct list_node *node2) +{ + node2->next = node->next; + if (node2->next != NULL) + node2->next->prev = &node2->next; + node2->prev = node->prev; + *node2->prev = node2; +} + +static inline void +list_split_after(struct list *list, struct list_node *node, struct list *rest) +{ + if (node->next == NULL) { + /* 'node' is the last node in 'list'. */ + list_init(rest); + } else { + rest->first = node->next; + node->next->prev = &rest->first; + node->next = NULL; + } +} + +static inline void +list_swap(struct list *list1, struct list *list2) +{ + struct list_node *swap_tmp = list1->first; + list1->first = list2->first; + list2->first = swap_tmp; + if ((swap_tmp = list1->first) != NULL) + swap_tmp->prev = &list1->first; + if ((swap_tmp = list2->first) != NULL) + swap_tmp->prev = &list2->first; +} + +#endif /* !_SYS_LIST_H_ */ diff --git a/sys/sys/slist.h b/sys/sys/slist.h new file mode 100644 --- /dev/null +++ b/sys/sys/slist.h @@ -0,0 +1,174 @@ +/* + * Copyright (c) 2026 The FreeBSD Foundation + * + * This software was developed by Minsoo Choo under sponsorship from the + * FreeBSD Foundation. + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#ifndef _SYS_SLIST_H_ +#define _SYS_SLIST_H_ + +#include +#include +#include + +/* + * This is a non-macro implementation of SLIST_* equivalent to queue(3). + * + * A singly-linked list is headed by a single forward pointer. The nodes + * are singly linked for minimum space and pointer manipulation overhead at + * the expense of O(n) removal for arbitrary nodes. New nodes can be + * added to the list after an existing node or at the head of the list. + * Nodes being removed from the head of the list should use the explicit + * macro for this purpose for optimum efficiency. A singly-linked list may + * only be traversed in the forward direction. Singly-linked lists are ideal + * for applications with large datasets and few or no removals or for + * implementing a LIFO queue. + */ + +/* + * Singly-linked List declarations. + */ + +struct slist_node { + slist_node *next; /* next node */ +}; + +struct slist { + slist_node *first; /* first node */ +}; + +/* + * Singly-linked list functions and macros. + */ + +static inline void +slist_concat(struct slist *list1, struct slist *list2) +{ + slist_node *curr; + + if (list1->first == NULL) { + list1->first = list2->first; + } else if (list2->first != NULL) { + curr = list1->first; + while (curr->next != NULL) + curr = curr->next; + curr->next = list2->first; + } + + list2->first = NULL; +} + +static inline bool +slist_empty(const struct slist *list) +{ + return list->first == NULL; +} + +static inline bool +slist_empty_atomic(const struct slist *list) +{ + return (atomic_load_ptr(&(list)->first) == NULL); +} + +static inline struct slist_node * +slist_first(const struct slist *list) +{ + return list->first; +} + +#define slist_foreach(var, list) \ + for ((var) = slist_first(list); \ + (var) != NULL; \ + (var) = slist_next(var)) + +#define slist_foreach_from(var, list) \ + for ((var) = ((var) != NULL ? (var) : slist_first(list)); \ + (var) != NULL; \ + (var) = slist_next(var)) + +#define slist_foreach_safe(var, list, tvar) \ + for ((var) = slist_first(list); \ + (var) != NULL && ((tvar) = slist_next(var), 1); \ + (var) = (tvar)) + +#define slist_foreach_from_safe(var, list, tvar) \ + for ((var) = ((var) != NULL ? (var) : slist_first(list)); \ + (var) != NULL && ((tvar) = slist_next(var), 1); \ + (var) = (tvar)) + +inline void +slist_init(struct slist *list) +{ + list->first = NULL; +} + +static inline void +slist_insert_after(struct slist_node *slistnode, struct slist_node *node) +{ + node->next = slistnode->next; + slistnode->next = node; +} + +static inline void +slist_insert_head(struct slist *list, struct slist_node *node) +{ + node->next = list->first; + list->first = node; +} + +static inline struct slist_node * +slist_next(const struct slist_node *node) +{ + return node->next; +} + +static inline void +slist_remove_after(struct slist_node *node) +{ + node->next = node->next->next; +} + +static inline void +slist_remove_head(struct slist *list) +{ + list->first = list->first->next; +} + +static inline void +slist_remove(struct slist *list, struct slist_node *node) +{ + if (list->first == node) { + slist_remove_head(list); + } else { + struct slist_node *curnode = list->first; + while (curnode->next != node) + curnode = curnode->next; + slist_remove_after(curnode); + } +} + +static inline void +slist_remove_prevptr(struct slist_node **prevp, struct slist_node *node) +{ + *prevp = node->next; +} + +static inline void +slist_split_after(struct slist *list, struct slist_node *node, struct slist *rest) +{ + rest->first = node->next; + node->next = NULL; +} + +static inline void +slist_swap(struct slist *list1, struct slist *list2) +{ + struct slist_node *swap_first = list1->first; + list1->first = list2->first; + list2->first = swap_first; +} + +#endif /* !_SYS_SLIST_H_ */ diff --git a/sys/sys/stailq.h b/sys/sys/stailq.h new file mode 100644 --- /dev/null +++ b/sys/sys/stailq.h @@ -0,0 +1,219 @@ +/* + * Copyright (c) 2026 The FreeBSD Foundation + * + * This software was developed by Minsoo Choo under sponsorship from the + * FreeBSD Foundation. + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#ifndef _SYS_STAILQ_H_ +#define _SYS_STAILQ_H_ + +#include +#include +#include + +/* + * This is a non-macro implementation of STAILQ_* equivalent to queue(3). + * + * A singly-linked tail queue is headed by a pair of pointers, one to the + * head of the queue and the other to the tail of the queue. The nodes are + * singly linked for minimum space and pointer manipulation overhead at the + * expense of O(n) removal for arbitrary nodes. New nodes can be added + * to the queue after an existing node, at the head of the queue, or at the + * end of the queue. Nodes being removed from the head of the tail queue + * should use the explicit macro for this purpose for optimum efficiency. + * A singly-linked tail queue may only be traversed in the forward direction. + * Singly-linked tail queues are ideal for applications with large datasets + * and few or no removals or for implementing a FIFO queue. + */ + +/* + * Singly-linked tail queue functions. + */ + +struct stailq_node { + struct stailq_node *next; /* next node */ +}; + +struct stailq { + struct stailq_node *first; /* first node */ + struct stailq_node **last; /* addr of last next node */ +}; + +/* + * Singly-linked Tail queue functions and macros. + */ + +static inline bool stailq_empty(const struct stailq *); +static inline void stailq_init(struct stailq *); + +static inline void +stailq_concat(struct stailq *queue1, struct stailq *queue2) +{ + if (!stailq_empty(queue2)) { + *queue1->last = queue2->first; + queue1->last = queue2->last; + stailq_init(queue2); + } +} + +static inline bool +stailq_empty(const struct stailq *queue) +{ + return (queue->first == NULL); +} + +static inline bool +stailq_empty_atomic(const struct stailq *queue) +{ + return (atomic_load_ptr(&queue->first) == NULL); +} + +static inline struct stailq_node * +stailq_first(const struct stailq *queue) +{ + return queue->first; +} + +#define stailq_foreach(var, queue) \ + for ((var) = stailq_first(queue); \ + (var) != NULL; \ + (var) = stailq_next(var)) + +#define stailq_foreach_from(var, queue) \ + for ((var) = ((var) != NULL ? (var) : stailq_first(queue)); \ + (var) != NULL; \ + (var) = stailq_next(var)) + +#define stailq_foreach_safe(var, queue, tvar) \ + for ((var) = stailq_first(queue); \ + (var) != NULL && ((tvar) = stailq_next(var), 1); \ + (var) = (tvar)) + +#define stailq_foreach_from_safe(var, queue, tvar) \ + for ((var) = ((var) != NULL ? (var) : stailq_first(queue)); \ + (var) != NULL && ((tvar) = stailq_next(var), 1); \ + (var) = (tvar)) + +static inline void +stailq_init(struct stailq *queue) +{ + queue->first = NULL; + queue->last = &queue->first; +} + +static inline void +stailq_insert_after(struct stailq *queue, struct stailq_node *qnode, + struct stailq_node *node) +{ + if ((node->next = qnode->next) == NULL) + queue->last = &node->next; + qnode->next = node; +} + +static inline void +stailq_insert_head(struct stailq *queue, struct stailq_node *node) +{ + if ((node->next = queue->first) == NULL) + queue->last = &node->next; + queue->first = node; +} + +static inline void +stailq_insert_tail(struct stailq *queue, struct stailq_node *node) +{ + node->next = NULL; + *queue->last = node; + queue->last = &node->next; +} + +static inline struct stailq_node * +stailq_last(struct stailq *queue) +{ + return stailq_empty(queue) ? NULL : + (struct stailq_node *)((char *)queue->last - + offsetof(struct stailq_node, next)); +} + +static inline struct stailq_node * +stailq_next(const struct stailq_node *node) +{ + return node->next; +} + +static inline void +stailq_remove_after(struct stailq *queue, struct stailq_node *node) +{ + if ((node->next = node->next->next) == NULL) + queue->last = &node->next; +} + +static inline void +stailq_remove_head(struct stailq *queue) +{ + if ((queue->first = queue->first->next) == NULL) + queue->last = &queue->first; +} + +static inline void +stailq_remove(struct stailq *queue, struct stailq_node *node) +{ + if (queue->first == node) { + stailq_remove_head(queue); + } else { + struct stailq_node *curnode = queue->first; + while (curnode->next != node) + curnode = curnode->next; + stailq_remove_after(queue, curnode); + } +} + +static inline void +stailq_split_after(struct stailq *queue, struct stailq_node *node, + struct stailq *rest) +{ + if (node->next == NULL) { + /* 'node' is the last node in 'queue'. */ + stailq_init(rest); + } else { + rest->first = node->next; + rest->last = queue->last; + node->next = NULL; + queue->last = &node->next; + } +} + +static inline void +stailq_swap(struct stailq *queue1, struct stailq *queue2) +{ + struct stailq_node *swap_first = queue1->first; + struct stailq_node **swap_last = queue1->last; + queue1->first = queue2->first; + queue1->last = queue2->last; + queue2->first = swap_first; + queue2->last = swap_last; + if (queue1->first == NULL) + queue1->last = &queue1->first; + if (queue2->first == NULL) + queue2->last = &queue2->first; +} + +static inline void +stailq_reverse(struct stailq *queue) +{ + if (stailq_empty(queue)) + return; + struct stailq_node *var, *varp, *varn; + for (var = queue->first, varp = NULL; var != NULL; ) { + varn = var->next; + var->next = varp; + varp = var; + var = varn; + } + queue->last = &queue->first->next; + queue->first = varp; +} + +#endif /* !_SYS_STAILQ_H_ */ diff --git a/sys/sys/stddef.h b/sys/sys/stddef.h --- a/sys/sys/stddef.h +++ b/sys/sys/stddef.h @@ -46,6 +46,7 @@ #define _PTRDIFF_T_DECLARED #endif -#define offsetof(type, field) __offsetof(type, field) +#define offsetof(type, field) __offsetof(type, field) +#define containerof(ptr, type, member) __containerof(ptr, type, member) #endif /* !_SYS_STDDEF_H_ */ diff --git a/sys/sys/tailq.h b/sys/sys/tailq.h new file mode 100644 --- /dev/null +++ b/sys/sys/tailq.h @@ -0,0 +1,249 @@ +/* + * Copyright (c) 2026 The FreeBSD Foundation + * + * This software was developed by Minsoo Choo under sponsorship from the + * FreeBSD Foundation. + * + * SPDX-License-Identifier: BSD-2-Clause + */ + +#ifndef _SYS_TAILQ_H_ +#define _SYS_TAILQ_H_ + +#include +#include +#include + +/* + * This is a non-macro implementation of TAILQ_* equivalent to queue(3). + * + * A tail queue is headed by a pair of pointers, one to the head of the + * queue and the other to the tail of the queue. The nodes are doubly + * linked so that an arbitrary node can be removed without a need to + * traverse the queue. New nodes can be added to the queue before or + * after an existing node, at the head of the queue, or at the end of + * the queue. A tail queue may be traversed in either direction. + */ + +struct tailq_node { + struct tailq_node *next; /* next node */ + struct tailq_node **prev; /* address of previous next node */ +}; + +struct tailq { + struct tailq_node *first; /* first node */ + struct tailq_node **last; /* addr of last next node */ +}; + +/* + * Tail queue functions and macros. + */ + +static inline bool tailq_empty(const struct tailq *); +static inline void tailq_init(struct tailq *); + +static inline void +tailq_concat(struct tailq *queue1, struct tailq *queue2) +{ + if (!tailq_empty(queue2)) { + *queue1->last = queue2->first; + queue2->first->prev = queue1->last; + queue1->last = queue2->last; + tailq_init(queue2); + } +} + +static inline bool +tailq_empty(const struct tailq *queue) +{ + return (queue->first == NULL); +} + +static inline bool +tailq_empty_atomic(const struct tailq *queue) +{ + return (atomic_load_ptr(&queue->first) == NULL); +} + +static inline struct tailq_node * +ailq_first(const struct tailq *queue) +{ + return queue->first; +} + + +#define tailq_foreach(var, queue) \ + for ((var) = tailq_first(queue); \ + (var) != NULL; \ + (var) = tailq_next(var)) + +#define tailq_foreach_from(var, queue) \ + for ((var) = ((var) != NULL ? (var) : tailq_first(queue)); \ + (var) != NULL; \ + (var) = tailq_next(var)) + +#define tailq_foreach_safe(var, queue, tvar) \ + for ((var) = tailq_first(queue); \ + (var) != NULL && ((tvar) = tailq_next(var), 1); \ + (var) = (tvar)) + +#define tailq_foreach_from_safe(var, queue, tvar) \ + for ((var) = ((var) != NULL ? (var) : tailq_first(queue)); \ + (var) != NULL && ((tvar) = tailq_next(var), 1); \ + (var) = (tvar)) + +#define tailq_foreach_reverse(var, queue) \ + for ((var) = tailq_last(queue); \ + (var) != NULL; \ + (var) = tailq_prev(var, queue)) + +#define tailq_foreach_reverse_from(var, queue) \ + for ((var) = ((var) != NULL ? (var) : tailq_last(queue)); \ + (var) != NULL; \ + (var) = tailq_prev(var, queue)) + +#define tailq_foreach_reverse_safe(var, queue, tvar) \ + for ((var) = tailq_last(queue); \ + (var) != NULL && ((tvar) = tailq_prev(var, queue), 1); \ + (var) = (tvar)) + +#define tailq_foreach_reverse_from_safe(var, queue, tvar) \ + for ((var) = ((var) != NULL ? (var) : tailq_last(queue)); \ + (var) != NULL && ((tvar) = tailq_prev(var, queue), 1); \ + (var) = (tvar)) + +static inline void +tailq_init(struct tailq *queue) +{ + queue->first = NULL; + queue->last = &queue->first; +} + +static inline void +tailq_insert_after(struct tailq *queue, struct tailq_node *qnode, + struct tailq_node *node) +{ + if ((node->next = qnode->next) != NULL) + node->next->prev = &node->next; + else + queue->last = &node->next; + qnode->next = node; + node->prev = &qnode->next; +} + +static inline void +tailq_insert_before(struct tailq_node *qnode, struct tailq_node *node) +{ + node->prev = qnode->prev; + node->next = qnode; + *qnode->prev = node; + qnode->prev = &node->next; +} + +static inline void +tailq_insert_head(struct tailq *queue, struct tailq_node *node) +{ + if ((node->next = queue->first) != NULL) + queue->first->prev = &node->next; + else + queue->last = &node->next; + queue->first = node; + node->prev = &queue->first; +} + +static inline void +tailq_insert_tail(struct tailq *queue, struct tailq_node *node) +{ + node->next = NULL; + node->prev = queue->last; + *queue->last = node; + queue->last = &node->next; +} + +static inline struct tailq_node * +tailq_last(const struct tailq *queue) +{ + return tailq_empty(queue) ? NULL : + (struct tailq_node *)((char *)queue->last - + offsetof(struct tailq_node, next)); +} + +static inline struct tailq_node * +tailq_next(const struct tailq_node *node) +{ + return node->next; +} + +static inline struct tailq_node * +tailq_prev(const struct tailq_node *node, const struct tailq *queue) +{ + return node->prev == &queue->first ? NULL : + (struct tailq_node *)((char *)node->prev - + offsetof(struct tailq_node, next)); +} + +static inline void +tailq_remove(struct tailq *queue, struct tailq_node *node) +{ + if (node->next != NULL) + node->next->prev = node->prev; + else + queue->last = node->prev; + *node->prev = node->next; +} + +static inline void +tailq_remove_head(struct tailq *queue) +{ + tailq_remove(queue, queue->first); +} + +static inline void +tailq_replace(struct tailq *queue, struct tailq_node *node, + struct tailq_node *node2) +{ + node2->next = node->next; + if (node2->next != NULL) + node2->next->prev = &node2->next; + else + queue->last = &node2->next; + node2->prev = node->prev; + *node2->prev = node2; +} + +static inline void +tailq_split_after(struct tailq *queue, struct tailq_node *node, + struct tailq *rest) +{ + if (node->next == NULL) { + /* 'node' is the last node in 'queue'. */ + tailq_init(rest); + } else { + rest->first = node->next; + rest->last = queue->last; + node->next->prev = &rest->first; + node->next = NULL; + queue->last = &node->next; + } +} + +static inline void +tailq_swap(struct tailq *queue1, struct tailq *queue2) +{ + struct tailq_node *swap_first = queue1->first; + struct tailq_node **swap_last = queue1->last; + queue1->first = queue2->first; + queue1->last = queue2->last; + queue2->first = swap_first; + queue2->last = swap_last; + if ((swap_first = queue1->first) != NULL) + swap_first->prev = &queue1->first; + else + queue1->last = &queue1->first; + if ((swap_first = queue2->first) != NULL) + swap_first->prev = &queue2->first; + else + queue2->last = &queue2->first; +} + +#endif /* !_SYS_TAILQ_H_ */