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/list.3 b/share/man/man3/list.3 new file mode 100644 --- /dev/null +++ b/share/man/man3/list.3 @@ -0,0 +1,392 @@ +.\" Copyright (c) 1993 The Regents of the University of California +.\" Copyright (c) 2026 The FreeBSD Foundation +.\" +.\" SPDX-License-Identifier: BSD-3-Clause +.\" +.Dd January 17, 2026 +.Dt LIST 3 +.Os +.Sh NAME +.Nm list_concat , +.Nm list_empty , +.Nm list_empty_atomic , +.Nm list_first , +.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_remove_head , +.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 *head1" "struct list *head2" +.Ft bool +.Fn list_empty "const struct list *head" +.Ft bool +.Fn list_empty_atomic "const struct list *head" +.Ft "struct list_node *" +.Fn list_first "const struct list *head" +.Ft void +.Fn list_init "struct list *head" +.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 *head" "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 *head" +.Ft void +.Fn list_remove "struct list_node *node" +.Ft void +.Fn list_remove_head "struct list *head" +.Ft void +.Fn list_replace "struct list_node *node" "struct list_node *node2" +.Ft void +.Fn list_split_after "struct list *head" "struct list_node *node" "struct list *rest" +.Ft void +.Fn list_swap "struct list *head1" "struct list *head2" +.\" +.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. +.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 +.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 containerof-style macros to convert between node pointers and +structure pointers. +.Pp +Doubly-linked lists support the following operations: +.Bl -enum -compact +.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 +.Pp +However: +.Bl -enum -compact +.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 +.Fn list_init +initializes the list referenced by +.Fa head . +.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_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 head +must contain element +.Fa node . +.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_remove +removes the element +.Fa node +from the list. +.Pp +.Fn list_remove_head +removes the first element 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_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 function should be avoided as it traverses the entirety of the +.Fa head1 +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_split_after +splits the list referenced by +.Fa head , +making +.Fa rest +reference the list formed by elements after +.Fa node +in +.Fa head . +.Pp +.Fn list_swap +swaps the contents of +.Fa head1 +and +.Fa head2 . +.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 +#define containerof(ptr, type, member) \\ + ((type *)((char *)(ptr) - offsetof(type, member))) +.Ed +.Ss Macro-Based API +The macro-based API is provided for compatibility with existing code. +A doubly-linked 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. +.Pp +See the macro-based API section of +.Xr queue 3 +for full details on all available macros. +.Sh EXAMPLES +.Ss Function-Based API Example +.Bd -literal +#include +#include + +struct entry { + int data; + struct list_node entries; /* List. */ +}; + +struct list head; +struct entry *n1, *n2, *n3; +struct list_node *np, *prev_np; + +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->entries, &n2->entries); + +n3 = malloc(sizeof(struct entry)); /* Insert before. */ +list_insert_before(&n2->entries, &n3->entries); + +list_remove(&n2->entries); /* Deletion. */ +free(n2); + /* Forward traversal. */ +for (np = list_first(&head); np != NULL; np = list_next(np)) { + struct entry *e = containerof(np, struct entry, entries); + /* Process e->data */ +} + /* Backward traversal. */ +prev_np = list_prev(&n1->entries, &head); +while (prev_np != NULL) { + struct entry *e = containerof(prev_np, struct entry, entries); + /* Process e->data */ + prev_np = list_prev(prev_np, &head); +} + +while (!list_empty(&head)) { /* List Deletion. */ + np = list_first(&head); + list_remove(np); + n1 = containerof(np, struct entry, entries); + free(n1); +} +.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 { + int data; + 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->data = 0; + + /* 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 SEE ALSO +.Xr slist 3 , +.Xr stailq 3 , +.Xr tailq 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 . \ No newline at end of file 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,386 @@ +.\" Copyright (c) 1993 The Regents of the University of California +.\" Copyright (c) 2026 The FreeBSD Foundation +.\" +.\" SPDX-License-Identifier: BSD-3-Clause +.\" +.Dd January 17, 2026 +.Dt SLIST 3 +.Os +.Sh NAME +.Nm slist_concat , +.Nm slist_empty , +.Nm slist_empty_atomic , +.Nm slist_first , +.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 *head1" "struct slist *head2" +.Ft bool +.Fn slist_empty "const struct slist *head" +.Ft bool +.Fn slist_empty_atomic "const struct slist *head" +.Ft "struct slist_node *" +.Fn slist_first "const struct slist *head" +.Ft void +.Fn slist_init "struct slist *head" +.Ft void +.Fn slist_insert_after "struct slist_node *slistnode" "struct slist_node *node" +.Ft void +.Fn slist_insert_head "struct slist *head" "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 *head" +.Ft void +.Fn slist_remove "struct slist *head" "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 *head" "struct slist_node *node" "struct slist *rest" +.Ft void +.Fn slist_swap "struct slist *head1" "struct slist *head2" +.\" +.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. +.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 +.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 containerof-style macros to convert between node pointers and +structure pointers. +.Pp +Singly-linked lists support the following operations: +.Bl -enum -compact +.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 +O(n) removal of any entry in the list. +.It +Forward 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 +.Pp +.Fn slist_init +initializes the list referenced by +.Fa head . +.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_next +returns the next element in the 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_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_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 function should be avoided as it traverses the entirety of the +.Fa head1 +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_split_after +splits the list referenced by +.Fa head , +making +.Fa rest +reference the list formed by elements after +.Fa node +in +.Fa head . +.Pp +.Fn slist_swap +swaps the contents of +.Fa head1 +and +.Fa head2 . +.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 +#define containerof(ptr, type, member) \\ + ((type *)((char *)(ptr) - offsetof(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. +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. +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 macro +.Nm SLIST_ENTRY +declares a structure that connects the elements in +the list. +.Pp +The macro +.Nm SLIST_HEAD_INITIALIZER +evaluates to an initializer for the list +.Fa head . +.Pp +See the macro-based API section of +.Xr queue 3 +for full details on all available macros. +.Sh EXAMPLES +.Ss Function-Based API Example +.Bd -literal +#include +#include + +struct entry { + int data; + struct slist_node entries; /* Singly-linked List. */ +}; + +struct slist head; +struct entry *n1, *n2, *n3; +struct slist_node *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->entries, &n2->entries); + +slist_remove(&head, &n2->entries); /* Deletion. */ +free(n2); + +np = slist_first(&head); /* Deletion from the head. */ +slist_remove_head(&head); +n3 = containerof(np, struct entry, entries); +free(n3); + /* Forward traversal. */ +for (np = slist_first(&head); np != NULL; np = slist_next(np)) { + struct entry *e = containerof(np, struct entry, entries); + /* Process e->data */ +} + +while (!slist_empty(&head)) { /* List Deletion. */ + np = slist_first(&head); + slist_remove_head(&head); + 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 { + int data; + 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->data = 0; + /* 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 SEE ALSO +.Xr list 3 , +.Xr stailq 3 , +.Xr tailq 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 . \ No newline at end of file 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,404 @@ +.\" Copyright (c) 1993 The Regents of the University of California +.\" Copyright (c) 2026 The FreeBSD Foundation +.\" +.\" SPDX-License-Identifier: BSD-3-Clause +.\" +.Dd January 17, 2026 +.Dt STAILQ 3 +.Os +.Sh NAME +.Nm stailq_concat , +.Nm stailq_empty , +.Nm stailq_empty_atomic , +.Nm stailq_first , +.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 *head1" "struct stailq *head2" +.Ft bool +.Fn stailq_empty "const struct stailq *head" +.Ft bool +.Fn stailq_empty_atomic "const struct stailq *head" +.Ft "struct stailq_node *" +.Fn stailq_first "const struct stailq *head" +.Ft void +.Fn stailq_init "struct stailq *head" +.Ft void +.Fn stailq_insert_after "struct stailq *head" "struct stailq_node *tqnode" "struct stailq_node *node" +.Ft void +.Fn stailq_insert_head "struct stailq *head" "struct stailq_node *node" +.Ft void +.Fn stailq_insert_tail "struct stailq *head" "struct stailq_node *node" +.Ft "struct stailq_node *" +.Fn stailq_last "struct stailq *head" +.Ft "struct stailq_node *" +.Fn stailq_next "const struct stailq_node *node" +.Ft void +.Fn stailq_remove_after "struct stailq *head" "struct stailq_node *node" +.Ft void +.Fn stailq_remove_head "struct stailq *head" +.Ft void +.Fn stailq_remove "struct stailq *head" "struct stailq_node *node" +.Ft void +.Fn stailq_reverse "struct stailq *head" +.Ft void +.Fn stailq_split_after "struct stailq *head" "struct stailq_node *node" "struct stailq *rest" +.Ft void +.Fn stailq_swap "struct stailq *head1" "struct stailq *head2" +.\" +.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. +.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 +.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 containerof-style macros to convert between node pointers and +structure pointers. +.Pp +Singly-linked tail queues support the following operations: +.Bl -enum -compact +.It +Insertion of a new entry at the head of the list. +.It +Insertion of a new entry at the tail 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 +O(n) removal of any entry in the list. +.It +Forward traversal through the list. +.It +O(1) concatenation of two lists. +.It +Reversing the list in place. +.It +Splitting a list in two after any element in the list. +.It +Swapping the contents of two lists. +.El +.Pp +However: +.Bl -enum -compact +.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 +.Fn stailq_init +initializes the tail queue referenced by +.Fa head . +.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_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_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 tqnode . +.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 list. +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_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 +.Fn stailq_split_after +splits the tail queue referenced by +.Fa head , +making +.Fa rest +reference the tail queue formed by elements after +.Fa node +in +.Fa head . +.Pp +.Fn stailq_swap +swaps the contents of +.Fa head1 +and +.Fa head2 . +.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 +#define containerof(ptr, type, member) \\ + ((type *)((char *)(ptr) - offsetof(type, member))) +.Ed +.Ss Macro-Based API +The macro-based API is provided for compatibility with existing code. +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. +.Pp +See the macro-based API section of +.Xr queue 3 +for full details on all available macros. +.Sh EXAMPLES +.Ss Function-Based API Example +.Bd -literal +#include +#include + +struct entry { + int data; + struct stailq_node entries; /* Tail queue. */ +}; + +struct stailq head; +struct entry *n1, *n2, *n3; +struct stailq_node *np; + +stailq_init(&head); /* Initialize the queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +stailq_insert_head(&head, &n1->entries); + +n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +stailq_insert_tail(&head, &n2->entries); + +n3 = malloc(sizeof(struct entry)); /* Insert after. */ +stailq_insert_after(&head, &n1->entries, &n3->entries); + +stailq_remove(&head, &n2->entries); /* Deletion. */ +free(n2); + +np = stailq_first(&head); /* Deletion from the head. */ +stailq_remove_head(&head); +n1 = containerof(np, struct entry, entries); +free(n1); + /* Forward traversal. */ +for (np = stailq_first(&head); np != NULL; np = stailq_next(np)) { + struct entry *e = containerof(np, struct entry, entries); + /* Process e->data */ +} + +while (!stailq_empty(&head)) { /* TailQ Deletion. */ + np = stailq_first(&head); + stailq_remove_head(&head); + n1 = containerof(np, struct entry, entries); + 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 { + int data; + 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->data = 0; + /* 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 SEE ALSO +.Xr list 3 , +.Xr slist 3 , +.Xr tailq 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 . \ No newline at end of file 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,434 @@ +.\" Copyright (c) 1993 The Regents of the University of California +.\" Copyright (c) 2026 The FreeBSD Foundation +.\" +.\" SPDX-License-Identifier: BSD-3-Clause +.\" +.Dd January 17, 2026 +.Dt TAILQ 3 +.Os +.Sh NAME +.Nm tailq_concat , +.Nm tailq_empty , +.Nm tailq_empty_atomic , +.Nm tailq_first , +.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_remove_head , +.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 *head1" "struct tailq *head2" +.Ft bool +.Fn tailq_empty "const struct tailq *head" +.Ft bool +.Fn tailq_empty_atomic "const struct tailq *head" +.Ft "struct tailq_node *" +.Fn tailq_first "const struct tailq *head" +.Ft void +.Fn tailq_init "struct tailq *head" +.Ft void +.Fn tailq_insert_after "struct tailq *head" "struct tailq_node *listnode" "struct tailq_node *node" +.Ft void +.Fn tailq_insert_before "struct tailq_node *listnode" "struct tailq_node *node" +.Ft void +.Fn tailq_insert_head "struct tailq *head" "struct tailq_node *node" +.Ft void +.Fn tailq_insert_tail "struct tailq *head" "struct tailq_node *node" +.Ft "struct tailq_node *" +.Fn tailq_last "const struct tailq *head" +.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 *head" +.Ft void +.Fn tailq_remove "struct tailq *head" "struct tailq_node *node" +.Ft void +.Fn tailq_remove_head "struct tailq *head" +.Ft void +.Fn tailq_replace "struct tailq *head" "struct tailq_node *node" "struct tailq_node *node2" +.Ft void +.Fn tailq_split_after "struct tailq *head" "struct tailq_node *node" "struct tailq *rest" +.Ft void +.Fn tailq_swap "struct tailq *head1" "struct tailq *head2" +.\" +.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. +.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 containerof-style macros to convert between node pointers and +structure pointers. +.Pp +Tail queues support the following operations: +.Bl -enum -compact +.It +Insertion of a new entry at the head of the list. +.It +Insertion of a new entry at the tail 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(1) concatenation of two lists. +.It +Splitting a list in two after any element in the list. +.It +Swapping the contents of two lists. +.El +.Pp +However: +.Bl -enum -compact +.It +All list insertions and removals must specify the head of the list. +.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 +.Fn tailq_init +initializes the tail queue referenced by +.Fa head . +.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_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_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 listnode . +.Pp +.Fn tailq_insert_before +inserts the new element +.Fa node +before the element +.Fa listnode . +.Pp +.Fn tailq_remove +removes the element +.Fa node +from the tail queue. +.Pp +.Fn tailq_remove_head +removes the first element 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 list. +.Pp +.Fn 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 +.Fn tailq_split_after +splits the tail queue referenced by +.Fa head , +making +.Fa rest +reference the tail queue formed by elements after +.Fa node +in +.Fa head . +.Pp +.Fn tailq_swap +swaps the contents of +.Fa head1 +and +.Fa head2 . +.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 +#define containerof(ptr, type, member) \\ + ((type *)((char *)(ptr) - offsetof(type, member))) +.Ed +.Ss Macro-Based API +The macro-based API is provided for compatibility with existing code. +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. +.Pp +See the macro-based API section of +.Xr queue 3 +for full details on all available macros. +.Sh EXAMPLES +.Ss Function-Based API Example +.Bd -literal +#include +#include + +struct entry { + int data; + struct tailq_node entries; /* Tail queue. */ +}; + +struct tailq head; +struct entry *n1, *n2, *n3, *n4; +struct tailq_node *np; + +tailq_init(&head); /* Initialize the queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +tailq_insert_head(&head, &n1->entries); + +n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +tailq_insert_tail(&head, &n2->entries); + +n3 = malloc(sizeof(struct entry)); /* Insert after. */ +tailq_insert_after(&head, &n1->entries, &n3->entries); + +n4 = malloc(sizeof(struct entry)); /* Insert before. */ +tailq_insert_before(&n2->entries, &n4->entries); + +tailq_remove(&head, &n2->entries); /* Deletion. */ +free(n2); + +struct entry *n5 = malloc(sizeof(struct entry)); /* Replacement. */ +tailq_replace(&head, &n3->entries, &n5->entries); +free(n3); + /* Forward traversal. */ +for (np = tailq_first(&head); np != NULL; np = tailq_next(np)) { + struct entry *e = containerof(np, struct entry, entries); + /* Process e->data */ +} + /* Reverse traversal. */ +np = tailq_last(&head); +while (np != NULL) { + struct entry *e = containerof(np, struct entry, entries); + /* Process e->data */ + np = tailq_prev(np, &head); +} + +while (!tailq_empty(&head)) { /* TailQ Deletion. */ + np = tailq_first(&head); + tailq_remove_head(&head); + n1 = containerof(np, struct entry, entries); + free(n1); +} +.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 { + int data; + 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->data = 0; + /* 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->data = 0; + /* 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 SEE ALSO +.Xr list 3 , +.Xr slist 3 , +.Xr stailq 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 . \ No newline at end of file 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,216 @@ +/* + * 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. + */ + +/* + * LIST_ASSERT_CHECK_NEXT(struct list_node *node) + * + * If a node follows 'node' in the list, validates that the next node + * points back at 'node'. + */ +#define LIST_ASSERT_CHECK_NEXT(node) \ + _Static_assert((node)->next == NULL || \ + (node)->next->prev == &((node)->next), \ + "Bad link node " #node " next->prev != node") + +/* + * LIST_ASSERT_CHECK_PREV(struct list_node *node) + * + * Validates that the previous node (or head of the list) points to 'node'. + */ +#define LIST_ASSERT_CHECK_PREV(node) \ + _Static_assert(*((node)->prev) == (node), \ + "Bad link node " #node " prev->next != node") + +/* + * LIST_ASSERT_CHECK_HEAD(struct list *head) + * + * If the list is non-empty, validates that the first node of the list + * points back at itself. + */ +#define LIST_ASSERT_CHECK_HEAD(head) \ + _Static_assert((head)->first == NULL || \ + (head)->first->prev == &((head)->first), \ + "Bad list head " #head " first->prev != &first") + +#define LIST_ASSERT_EMPTY(head) \ + _Static_assert(list_empty((head)), \ + "list " #head " is not empty") + +#define LIST_ASSERT_NONEMPTY(head) \ + _Static_assert(!list_empty((head)), \ + "list " #head " is empty") + +static inline bool +list_empty(const struct list *head) +{ + return head->first == NULL; +} + +static inline bool +list_empty_atomic(const struct list *head) +{ + return atomic_load_ptr(&head->first) == NULL; +} + +static inline struct list_node * +list_first(const struct list *head) +{ + return head->first; +} + +static inline void +list_init(struct list *head) +{ + head->first = NULL; +} + +static inline void +list_concat(struct list *head1, struct list *head2) +{ + struct list_node *curnode = head1->first; + if (curnode == NULL) { + if ((head1->first = head2->first) != NULL) { + head2->first->prev = &head1->first; + list_init(head2); + } + } else if (head2->first != NULL) { + while (curnode->next != NULL) + curnode = curnode->next; + curnode->next = head2->first; + head2->first->prev = &curnode->next; + list_init(head2); + } +} + +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 *head, struct list_node *node) +{ + if ((node->next = head->first) != NULL) + head->first->prev = &node->next; + head->first = node; + node->prev = &head->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 *head) +{ + return node->prev == &head->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_remove_head(struct list *head) +{ + list_remove(head->first); +} + +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 *head, struct list_node *node, struct list *rest) +{ + if (node->next == NULL) { + /* 'node' is the last node in 'head'. */ + list_init(rest); + } else { + rest->first = node->next; + node->next->prev = &rest->first; + node->next = NULL; + } +} + +static inline void +list_swap(struct list *head1, struct list *head2) +{ + struct list_node *swap_tmp = head1->first; + head1->first = head2->first; + head2->first = swap_tmp; + if ((swap_tmp = head1->first) != NULL) + swap_tmp->prev = &head1->first; + if ((swap_tmp = head2->first) != NULL) + swap_tmp->prev = &head2->first; +} + +#endif /* !_SYS_LIST_H_ */ \ No newline at end of file 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,161 @@ +/* + * 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. + */ + +#define SLIST_ASSERT_EMPTY(head) \ + _Static_assert(slist_empty((head)), "slist " #head " is not empty") + +#define SLIST_ASSERT_NONEMPTY(head) \ + _Static_assert(!slist_empty((head)), "slist " #head " is empty") + + +static inline bool +slist_empty(const struct slist *head) +{ + return head->first == NULL; +} + +static inline bool +slist_empty_atomic(const struct slist *head) +{ + return (atomic_load_ptr(&(head)->first) == NULL); +} + +static inline struct slist_node * +slist_first(const struct slist *head) +{ + return head->first; +} + +inline void +slist_init(struct slist *head) +{ + head->first = NULL; +} + +static inline void +slist_concat(struct slist *head1, struct slist *head2) +{ + slist_node *curr; + + if (head1->first == NULL) { + head1->first = head2->first; + } else if (head2->first != NULL) { + curr = head1->first; + while (curr->next != NULL) + curr = curr->next; + curr->next = head2->first; + } + + head2->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 *head, struct slist_node *node) +{ + node->next = head->first; + head->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 *head) +{ + head->first = head->first->next; +} + +static inline void +slist_remove(struct slist *head, struct slist_node *node) +{ + if (head->first == node) { + slist_remove_head(head); + } else { + struct slist_node *curnode = head->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 *head, struct slist_node *node, struct slist *rest) +{ + rest->first = node->next; + node->next = NULL; +} + +static inline void +slist_swap(struct slist *head1, struct slist *head2) +{ + struct slist_node *swap_first = head1->first; + head1->first = head2->first; + head2->first = swap_first; +} + +#endif /* !_SYS_SLIST_H_ */ \ No newline at end of file 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,223 @@ +/* + * 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 list and the other to the tail of the list. 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, at the head of the list, or at the + * end of the list. 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. + */ + +/* + * STAILQ_ASSERT_CHECK_EMPTY(struct stailq *head) + * + * Validates that the stailq head's pointer to the last node's next pointer + * actually points to the head's first node pointer field. + */ +#define STAILQ_ASSERT_CHECK_EMPTY(head) \ + _Static_assert((head)->last == &(head)->first, \ + "Empty stailq " #head "->last is not &" #head "->first") + +/* + * STAILQ_ASSERT_CHECK_TAIL(struct stailq *head) + * + * Validates that the stailq's last node's next pointer is NULL. + */ +#define STAILQ_ASSERT_CHECK_TAIL(head) \ + _Static_assert(*(head)->last == NULL, \ + "Stailq " #head " last node's next pointer is not NULL") + +#define STAILQ_ASSERT_EMPTY(head) \ + _Static_assert(stailq_empty((head)), \ + "stailq " #head " is not empty") + +#define STAILQ_ASSERT_NONEMPTY(head) \ + _Static_assert(!stailq_empty((head)), \ + "stailq " #head " is empty") + +static inline bool +stailq_empty(const struct stailq *head) +{ + return (head->first == NULL); +} + +static inline bool +stailq_empty_atomic(const struct stailq *head) +{ + return (atomic_load_ptr(&head->first) == NULL); +} + +static inline struct stailq_node * +stailq_first(const struct stailq *head) +{ + return head->first; +} + +static inline void +stailq_init(struct stailq *head) +{ + head->first = NULL; + head->last = &head->first; +} + +static inline void +stailq_concat(struct stailq *head1, struct stailq *head2) +{ + if (!stailq_empty(head2)) { + *head1->last = head2->first; + head1->last = head2->last; + stailq_init(head2); + } +} + +static inline void +stailq_insert_after(struct stailq *head, struct stailq_node *tqnode, + struct stailq_node *node) +{ + if ((node->next = tqnode->next) == NULL) + head->last = &node->next; + tqnode->next = node; +} + +static inline void +stailq_insert_head(struct stailq *head, struct stailq_node *node) +{ + if ((node->next = head->first) == NULL) + head->last = &node->next; + head->first = node; +} + +static inline void +stailq_insert_tail(struct stailq *head, struct stailq_node *node) +{ + node->next = NULL; + *head->last = node; + head->last = &node->next; +} + +static inline struct stailq_node * +stailq_last(struct stailq *head) +{ + return stailq_empty(head) ? NULL : + (struct stailq_node *)((char *)head->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 *head, struct stailq_node *node) +{ + if ((node->next = node->next->next) == NULL) + head->last = &node->next; +} + +static inline void +stailq_remove_head(struct stailq *head) +{ + if ((head->first = head->first->next) == NULL) + head->last = &head->first; +} + +static inline void +stailq_remove(struct stailq *head, struct stailq_node *node) +{ + if (head->first == node) { + stailq_remove_head(head); + } else { + struct stailq_node *curnode = head->first; + while (curnode->next != node) + curnode = curnode->next; + stailq_remove_after(head, curnode); + } +} + +static inline void +stailq_split_after(struct stailq *head, struct stailq_node *node, + struct stailq *rest) +{ + if (node->next == NULL) { + /* 'node' is the last node in 'head'. */ + stailq_init(rest); + } else { + rest->first = node->next; + rest->last = head->last; + node->next = NULL; + head->last = &node->next; + } +} + +static inline void +stailq_swap(struct stailq *head1, struct stailq *head2) +{ + struct stailq_node *swap_first = head1->first; + struct stailq_node **swap_last = head1->last; + head1->first = head2->first; + head1->last = head2->last; + head2->first = swap_first; + head2->last = swap_last; + if (head1->first == NULL) + head1->last = &head1->first; + if (head2->first == NULL) + head2->last = &head2->first; +} + +static inline void +stailq_reverse(struct stailq *head) +{ + if (stailq_empty(head)) + return; + struct stailq_node *var, *varp, *varn; + for (var = head->first, varp = NULL; var != NULL; ) { + varn = var->next; + var->next = varp; + varp = var; + var = varn; + } + head->last = &head->first->next; + head->first = varp; +} + +#endif /* !_SYS_STAILQ_H_ */ \ No newline at end of file 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,253 @@ +/* + * 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 + * list and the other to the tail of the list. 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, at the head of the list, or at the end of + * the list. 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. + */ + +/* + * TAILQ_ASSERT_CHECK_HEAD(struct tailq *head) + * + * If the tailq is non-empty, validates that the first node of the tailq + * points back at 'head.' + */ +#define TAILQ_ASSERT_CHECK_HEAD(head) \ + _Static_assert(tailq_empty(head) || \ + (head)->first->prev == &(head)->first, \ + "Bad tailq head " #head " first->prev != &first") + +/* + * TAILQ_ASSERT_CHECK_TAIL(struct tailq *head) + * + * Validates that the tail of the tailq is a pointer to pointer to NULL. + */ +#define TAILQ_ASSERT_CHECK_TAIL(head) \ + _Static_assert(*(head)->last == NULL, \ + "Bad tailq " #head " NEXT(last) != NULL") + +/* + * TAILQ_ASSERT_CHECK_NEXT(struct tailq_node *node) + * + * If a node follows 'node' in the tailq, validates that the next node + * points back at 'node.' + */ +#define TAILQ_ASSERT_CHECK_NEXT(node) \ + _Static_assert((node)->next == NULL || \ + (node)->next->prev == &(node)->next, \ + "Bad link node " #node " next->prev != &node->next") + +/* + * TAILQ_ASSERT_CHECK_PREV(struct tailq_node *node) + * + * Validates that the previous node (or head of the tailq) points to 'node.' + */ +#define TAILQ_ASSERT_CHECK_PREV(node) \ + _Static_assert(*(node)->prev == (node), \ + "Bad link node " #node " prev->next != node") + +#define TAILQ_ASSERT_EMPTY(head) \ + _Static_assert(tailq_empty((head)), \ + "tailq " #head " is not empty") + +#define TAILQ_ASSERT_NONEMPTY(head) \ + _Static_assert(!tailq_empty((head)), \ + "tailq " #head " is empty") + +static inline bool +tailq_empty(const struct tailq *head) +{ + return (head->first == NULL); +} + +static inline bool +tailq_empty_atomic(const struct tailq *head) +{ + return (atomic_load_ptr(&head->first) == NULL); +} + +static inline struct tailq_node * +ailq_first(const struct tailq *head) +{ + return head->first; +} + +static inline void +tailq_init(struct tailq *head) +{ + head->first = NULL; + head->last = &head->first; +} + +static inline void +tailq_concat(struct tailq *head1, struct tailq *head2) +{ + if (!tailq_empty(head2)) { + *head1->last = head2->first; + head2->first->prev = head1->last; + head1->last = head2->last; + tailq_init(head2); + } +} + +static inline void +tailq_insert_after(struct tailq *head, struct tailq_node *listnode, + struct tailq_node *node) +{ + if ((node->next = listnode->next) != NULL) + node->next->prev = &node->next; + else + head->last = &node->next; + listnode->next = node; + node->prev = &listnode->next; +} + +static inline void +tailq_insert_before(struct tailq_node *listnode, struct tailq_node *node) +{ + node->prev = listnode->prev; + node->next = listnode; + *listnode->prev = node; + listnode->prev = &node->next; +} + +static inline void +tailq_insert_head(struct tailq *head, struct tailq_node *node) +{ + if ((node->next = head->first) != NULL) + head->first->prev = &node->next; + else + head->last = &node->next; + head->first = node; + node->prev = &head->first; +} + +static inline void +tailq_insert_tail(struct tailq *head, struct tailq_node *node) +{ + node->next = NULL; + node->prev = head->last; + *head->last = node; + head->last = &node->next; +} + +static inline struct tailq_node * +tailq_last(const struct tailq *head) +{ + return tailq_empty(head) ? NULL : + (struct tailq_node *)((char *)head->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 *head) +{ + return node->prev == &head->first ? NULL : + (struct tailq_node *)((char *)node->prev - + offsetof(struct tailq_node, next)); +} + +static inline void +tailq_remove(struct tailq *head, struct tailq_node *node) +{ + if (node->next != NULL) + node->next->prev = node->prev; + else + head->last = node->prev; + *node->prev = node->next; +} + +static inline void +tailq_remove_head(struct tailq *head) +{ + tailq_remove(head, head->first); +} + +static inline void +tailq_replace(struct tailq *head, struct tailq_node *node, + struct tailq_node *node2) +{ + node2->next = node->next; + if (node2->next != NULL) + node2->next->prev = &node2->next; + else + head->last = &node2->next; + node2->prev = node->prev; + *node2->prev = node2; +} + +static inline void +tailq_split_after(struct tailq *head, struct tailq_node *node, + struct tailq *rest) +{ + if (node->next == NULL) { + /* 'node' is the last node in 'head'. */ + tailq_init(rest); + } else { + rest->first = node->next; + rest->last = head->last; + node->next->prev = &rest->first; + node->next = NULL; + head->last = &node->next; + } +} + +static inline void +tailq_swap(struct tailq *head1, struct tailq *head2) +{ + struct tailq_node *swap_first = head1->first; + struct tailq_node **swap_last = head1->last; + head1->first = head2->first; + head1->last = head2->last; + head2->first = swap_first; + head2->last = swap_last; + if ((swap_first = head1->first) != NULL) + swap_first->prev = &head1->first; + else + head1->last = &head1->first; + if ((swap_first = head2->first) != NULL) + swap_first->prev = &head2->first; + else + head2->last = &head2->first; +} + +#endif /* !_SYS_TAILQ_H_ */ \ No newline at end of file