Page MenuHomeFreeBSD
Files F143038117

D54753.id169934.diff
No OneTemporary
Actions

D54753.id169934.diff
View Options

diff --git a/share/man/man3/queue.3 b/share/man/man3/queue.3
--- a/share/man/man3/queue.3
+++ b/share/man/man3/queue.3
@@ -25,7 +25,7 @@
.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
.\"
-.Dd April 28, 2025
+.Dd January 16, 2026
.Dt QUEUE 3
.Os
.Sh NAME
@@ -127,7 +127,69 @@
.Nm TAILQ_REMOVE ,
.Nm TAILQ_REPLACE ,
.Nm TAILQ_SPLIT_AFTER ,
-.Nm TAILQ_SWAP
+.Nm TAILQ_SWAP ,
+.Nm slist_concat ,
+.Nm slist_empty ,
+.Nm slist_empty_atomic ,
+.Nm slist_first ,
+.Nm slist_init ,
+.Nm slist_next ,
+.Nm slist_insert_after ,
+.Nm slist_insert_head ,
+.Nm slist_remove ,
+.Nm slist_remove_after ,
+.Nm slist_remove_head ,
+.Nm slist_remove_prevptr ,
+.Nm slist_split_after ,
+.Nm slist_swap ,
+.Nm stailq_concat ,
+.Nm stailq_empty ,
+.Nm stailq_empty_atomic ,
+.Nm stailq_first ,
+.Nm stailq_init ,
+.Nm stailq_next ,
+.Nm stailq_insert_after ,
+.Nm stailq_insert_head ,
+.Nm stailq_insert_tail ,
+.Nm stailq_last ,
+.Nm stailq_remove ,
+.Nm stailq_remove_after ,
+.Nm stailq_remove_head ,
+.Nm stailq_reverse ,
+.Nm stailq_split_after ,
+.Nm stailq_swap ,
+.Nm list_concat ,
+.Nm list_empty ,
+.Nm list_empty_atomic ,
+.Nm list_first ,
+.Nm list_init ,
+.Nm list_next ,
+.Nm list_insert_after ,
+.Nm list_insert_before ,
+.Nm list_insert_head ,
+.Nm list_prev ,
+.Nm list_remove ,
+.Nm list_remove_head ,
+.Nm list_replace ,
+.Nm list_split_after ,
+.Nm list_swap ,
+.Nm tailq_concat ,
+.Nm tailq_empty ,
+.Nm tailq_empty_atomic ,
+.Nm tailq_first ,
+.Nm tailq_init ,
+.Nm tailq_next ,
+.Nm tailq_insert_after ,
+.Nm tailq_insert_before ,
+.Nm tailq_insert_head ,
+.Nm tailq_insert_tail ,
+.Nm tailq_last ,
+.Nm tailq_prev ,
+.Nm tailq_remove ,
+.Nm tailq_remove_head ,
+.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
@@ -236,6 +298,141 @@
.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"
.\"
+.\"
+.\" Non-macro function-based API
+.\"
+.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/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/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/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"
+.\"
.Sh DESCRIPTION
These macros define and operate on four types of data structures which
can be used in both C and C++ source code:
@@ -391,6 +588,110 @@
.Li TAILQ_CLASS_HEAD .
See the examples below for further explanation of how these
macros are used.
+.Sh FUNCTION-BASED API
+In addition to the traditional macro-based API described in this manual,
+FreeBSD provides a set of inline function-based APIs for queue operations
+through the following headers:
+.Bl -tag -width "sys/stailq.h"
+.It In sys/slist.h
+Singly-linked list operations using
+.Vt struct slist
+and
+.Vt struct slist_node .
+.It In sys/stailq.h
+Singly-linked tail queue operations using
+.Vt struct stailq
+and
+.Vt struct stailq_node .
+.It In sys/list.h
+Doubly-linked list operations using
+.Vt struct list
+and
+.Vt struct list_node .
+.It In sys/tailq.h
+Doubly-linked tail queue operations using
+.Vt struct tailq
+and
+.Vt struct tailq_node .
+.El
+.Pp
+The function-based API provides the following advantages over the macro-based API:
+.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
+.Pp
+The function-based API uses standard structure types defined in the respective
+headers and provides inline functions that operate on these structures.
+To use the function-based API, user-defined structures should embed the
+appropriate node structure
+.Pf ( Vt struct slist_node ,
+.Vt struct stailq_node ,
+.Vt struct list_node ,
+or
+.Vt struct tailq_node )
+and use containerof-style macros to convert between node pointers and
+structure pointers when needed.
+.Pp
+For example, to use a singly-linked list with the function-based API:
+.Bd -literal -offset indent
+#include <sys/slist.h>
+
+struct my_entry {
+ int data;
+ struct slist_node node;
+};
+
+struct slist head;
+slist_init(&head);
+
+struct my_entry *entry = malloc(sizeof(*entry));
+entry->data = 42;
+slist_insert_head(&head, &entry->node);
+.Ed
+.Pp
+The function-based API is recommended for new code.
+The macro-based API remains available for compatibility with existing code.
+.Ss Converting Between Node and Structure Pointers
+Since the function-based API operates on node pointers
+.Pf ( Vt struct slist_node ,
+.Vt struct stailq_node ,
+.Vt struct list_node ,
+.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)
+.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.
+For example:
+.Bd -literal -offset indent
+struct my_entry {
+ int data;
+ struct list_node node;
+};
+
+struct list_node *np = list_first(&head);
+struct my_entry *entry = containerof(np, struct my_entry, node);
+.Ed
+.Pp
+This pattern is used throughout the examples below.
.Sh SINGLY-LINKED LISTS
A singly-linked list is headed by a structure defined by the
.Nm SLIST_HEAD
@@ -617,6 +918,49 @@
free(n1);
}
.Ed
+.Ss Function-Based Singly-Linked List Example
+.Bd -literal
+#include <sys/slist.h>
+#include <stdlib.h>
+
+struct entry {
+ ...
+ 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);
+ e-> ...
+}
+
+while (!slist_empty(&head)) { /* List Deletion. */
+ np = slist_first(&head);
+ slist_remove_head(&head);
+ n1 = containerof(np, struct entry, 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
@@ -866,6 +1210,52 @@
}
STAILQ_INIT(&head);
.Ed
+.Ss Function-Based Singly-Linked Tail Queue Example
+.Bd -literal
+#include <sys/stailq.h>
+#include <stdlib.h>
+
+struct entry {
+ ...
+ 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);
+ e-> ...
+}
+
+while (!stailq_empty(&head)) { /* TailQ Deletion. */
+ np = stailq_first(&head);
+ stailq_remove_head(&head);
+ n1 = containerof(np, struct entry, entries);
+ free(n1);
+}
+.Ed
.Sh LISTS
A list is headed by a structure defined by the
.Nm LIST_HEAD
@@ -1102,6 +1492,54 @@
}
LIST_INIT(&head);
.Ed
+.Ss Function-Based Doubly-Linked List Example
+.Bd -literal
+#include <sys/list.h>
+#include <stdlib.h>
+
+struct entry {
+ ...
+ 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);
+ e-> ...
+}
+ /* Backward traversal. */
+prev_np = list_prev(&n1->entries, &head);
+while (prev_np != NULL) {
+ struct entry *e = containerof(prev_np, struct entry, entries);
+ e-> ...
+ 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
.Sh TAIL QUEUES
A tail queue is headed by a structure defined by the
.Nm TAILQ_HEAD
@@ -1395,6 +1833,61 @@
}
TAILQ_INIT(&head);
.Ed
+.Ss Function-Based Doubly-Linked Tail Queue Example
+.Bd -literal
+#include <sys/tailq.h>
+#include <stdlib.h>
+
+struct entry {
+ ...
+ 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);
+ e-> ...
+}
+ /* Reverse traversal. */
+np = tailq_last(&head);
+while (np != NULL) {
+ struct entry *e = containerof(np, struct entry, entries);
+ e-> ...
+ 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
.Sh DIAGNOSTICS
.Nm queue(3)
provides several diagnostic and debugging facilities.
@@ -1485,3 +1978,6 @@
.Nm queue
functions first appeared in
.Bx 4.4 .
+.Pp
+The function-based API using inline functions was introduced in
+.Fx 15.1 .
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,215 @@
+/*
+ * 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 <sys/atomic_common.h>
+#include <sys/stddef.h>
+
+/*
+ * 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,160 @@
+/*
+ * 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 <sys/atomic_common.h>
+#include <sys/stddef.h>
+
+/*
+ * 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,222 @@
+/*
+ * 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 <sys/atomic_common.h>
+#include <sys/stddef.h>
+
+/*
+ * 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,252 @@
+/*
+ * 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 <sys/atomic_common.h>
+#include <sys/stddef.h>
+
+/*
+ * 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

File Metadata

Mime Type
text/plain
Expires
Mon, Jan 26, 10:33 AM (9 h, 1 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
27982100
Default Alt Text
D54753.id169934.diff (36 KB)

Event Timeline