I don't know if it is useful to anyone else but it is required by lsquic, a
library that implements QUIC / HTTP3.
Index: share/man/man3/queue.3
===================================================================
RCS file: /cvs/src/share/man/man3/queue.3,v
retrieving revision 1.66
diff -u -p -r1.66 queue.3
--- share/man/man3/queue.3 30 Dec 2019 17:25:39 -0000 1.66
+++ share/man/man3/queue.3 23 Apr 2020 11:59:19 -0000
@@ -96,8 +96,24 @@
.Nm TAILQ_INSERT_TAIL ,
.Nm TAILQ_REMOVE ,
.Nm TAILQ_REPLACE ,
-.Nm TAILQ_CONCAT
-.Nd intrusive singly-linked and doubly-linked lists, simple queues, and tail
queues
+.Nm TAILQ_CONCAT ,
+.Nm STAILQ_HEAD ,
+.Nm STAILQ_HEAD_INITIALIZER ,
+.Nm STAILQ_ENTRY ,
+.Nm STAILQ_FIRST ,
+.Nm STAILQ_EMPTY ,
+.Nm STAILQ_NEXT ,
+.Nm STAILQ_LAST ,
+.Nm STAILQ_FOREACH ,
+.Nm STAILQ_FOREACH_SAFE ,
+.Nm STAILQ_INIT ,
+.Nm STAILQ_INSERT_AFTER ,
+.Nm STAILQ_INSERT_HEAD ,
+.Nm STAILQ_INSERT_TAIL ,
+.Nm STAILQ_REMOVE_HEAD ,
+.Nm STAILQ_REMOVE ,
+.Nm STAILQ_CONCAT
+.Nd intrusive singly-linked and doubly-linked lists, simple queues, tail
queue, and singly-linked tail queues
.Sh SYNOPSIS
.In sys/queue.h
.Pp
@@ -206,10 +222,32 @@
.Ft void
.Fn TAILQ_REPLACE "TAILQ_HEAD *head" "struct TYPE *elm" "struct TYPE *elm2"
"FIELDNAME"
.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "FIELDNAME"
+.Pp
+.Fn STAILQ_ENTRY "TYPE"
+.Fn STAILQ_HEAD "HEADNAME" "TYPE"
+.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
+.Ft "struct TYPE *"
+.Fn STAILQ_FIRST "STAILQ_HEAD *head"
+.Ft int
+.Fn STAILQ_EMPTY "STAILQ_HEAD *head"
+.Ft "struct TYPE *"
+.Fn STAILQ_NEXT "struct TYPE *listelm" "FILEDNAME"
+.Ft "struct TYPE *"
+.Fn STAILQ_LAST "STAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
+.Fn STAILQ_FOREACH "VARNAME" "STAILQ_HEAD *head" "FIELDNAME"
+.Fn STAILQ_FOREACH_SAFE "VARNAME" "STAILQ_HEAD *head" "FIELDNAME"
"TEMP_VARNAME"
+.Fn STAILQ_INIT "STAILQ_HEAD *head"
+.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
+.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
+.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "struct TYPE *listelm" "TYPE *elm"
"FIELDNAME"
+.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "FIELDNAME"
+.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "struct TYPE *elm" "TYPE" "FIELDNAME"
+.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
.Sh DESCRIPTION
-These macros define and operate on four types of data structures:
-singly-linked lists, simple queues, lists, and tail queues.
-All four structures support the following functionality:
+These macros define and operate on five types of data structures:
+singly-linked lists, simple queues, lists, tail queues, and singly-linked
+tail queues.
+All five structures support the following functionality:
.Pp
.Bl -enum -compact -offset indent
.It
@@ -303,8 +341,9 @@ defined structures containing a field of
.Li SLIST_ENTRY ,
.Li LIST_ENTRY ,
.Li SIMPLEQ_ENTRY ,
+.Li TAILQ_ENTRY ,
or
-.Li TAILQ_ENTRY .
+.Li STAILQ_ENTRY .
In the macro definitions,
.Fa TYPE
is the name tag of the user defined structure and
@@ -324,8 +363,9 @@ using the macros
.Fn SLIST_HEAD ,
.Fn LIST_HEAD ,
.Fn SIMPLEQ_HEAD ,
+.Fn TAILQ_HEAD ,
or
-.Fn TAILQ_HEAD .
+.Fn STAILQ_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
@@ -927,6 +967,27 @@ while ((np = TAILQ_FIRST(&head))) {
}
.Ed
+.Sh SINGLY LINKED TAIL QUEUES
+The macros prefixed with
+.Do Nm STAILQ_ Dc (
+.Fn STAILQ_HEAD ,
+.Fn STAILQ_HEAD_INITIALIZER ,
+.Fn STAILQ_ENTRY ,
+.Fn STAILQ_FOREACH ,
+.Fn STAILQ_FOREACH_SAFE ,
+.Fn STAILQ_FIRST ,
+.Fn STAILQ_EMPTY ,
+.Fn STAILQ_NEXT ,
+.Fn STAILQ_LAST ,
+.Fn STAILQ_INIT ,
+.Fn STAILQ_INSERT_HEAD ,
+.Fn STAILQ_INSERT_TAIL ,
+.Fn STAILQ_INSERT_AFTER ,
+.Fn STAILQ_REMOVE_HEAD ,
+.Fn STAILQ_REMOVE ,
+and
+.Fn STAILQ_CONCAT )
+are functionally identical to these simple queue functions.
.Sh SEE ALSO
.Xr tree 3
.Sh NOTES
Index: sys/sys/queue.h
===================================================================
RCS file: /cvs/src/sys/sys/queue.h,v
retrieving revision 1.45
diff -u -p -r1.45 queue.h
--- sys/sys/queue.h 12 Jul 2018 14:22:54 -0000 1.45
+++ sys/sys/queue.h 23 Apr 2020 11:59:20 -0000
@@ -533,4 +533,101 @@ struct {
\
} \
} while (0)
-#endif /* !_SYS_QUEUE_H_ */
+/*
+ * Singly-linked Tail queue declarations.
+ */
+#define STAILQ_HEAD(name, type)
\
+struct name { \
+ struct type *stqh_first; /* first element */ \
+ struct type **stqh_last; /* addr of last next element */ \
+}
+
+#define STAILQ_HEAD_INITIALIZER(head)
\
+ { NULL, &(head).stqh_first }
+
+#define STAILQ_ENTRY(type)
\
+struct { \
+ struct type *stqe_next; /* next element */ \
+}
+
+/*
+ * Singly-linked Tail queue access methods.
+ */
+#define STAILQ_FIRST(head) ((head)->stqh_first)
+#define STAILQ_END(head) NULL
+#define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
+#define STAILQ_EMPTY(head) (STAILQ_FIRST(head) == STAILQ_END(head))
+
+/*
+ * Singly-linked Tail queue functions.
+ */
+#define STAILQ_INIT(head) do {
\
+ (head)->stqh_first = NULL; \
+ (head)->stqh_last = &(head)->stqh_first; \
+} while (0)
+
+#define STAILQ_INSERT_HEAD(head, elm, field) do {
\
+ if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
+ (head)->stqh_last = &(elm)->field.stqe_next; \
+ (head)->stqh_first = (elm); \
+} while (0)
+
+#define STAILQ_INSERT_TAIL(head, elm, field) do {
\
+ (elm)->field.stqe_next = NULL; \
+ *(head)->stqh_last = (elm); \
+ (head)->stqh_last = &(elm)->field.stqe_next; \
+} while (0)
+
+#define STAILQ_INSERT_AFTER(head, listelm, elm, field) do {
\
+ if (((elm)->field.stqe_next = \
+ (listelm)->field.stqe_next) == NULL) \
+ (head)->stqh_last = &(elm)->field.stqe_next; \
+ (listelm)->field.stqe_next = (elm); \
+} while (0)
+
+#define STAILQ_REMOVE_HEAD(head, field) do {
\
+ if (((head)->stqh_first = \
+ (head)->stqh_first->field.stqe_next) == NULL) \
+ (head)->stqh_last = &(head)->stqh_first; \
+} while (0)
+
+#define STAILQ_REMOVE(head, elm, type, field) do {
\
+ if ((head)->stqh_first == (elm)) { \
+ STAILQ_REMOVE_HEAD((head), field); \
+ } else { \
+ struct type *curelm = (head)->stqh_first; \
+ while (curelm->field.stqe_next != (elm)) \
+ curelm = curelm->field.stqe_next; \
+ if ((curelm->field.stqe_next = \
+ curelm->field.stqe_next->field.stqe_next) == NULL)\
+ (head)->stqh_last = \
+ &(curelm)->field.stqe_next; \
+ } \
+ _Q_INVALIDATE((elm)->field.stqh_next); \
+} while (0)
+
+#define STAILQ_FOREACH(var, head, field)
\
+ for ((var) = ((head)->stqh_first); \
+ (var); \
+ (var) = ((var)->field.stqe_next))
+
+#define STAILQ_FOREACH_SAFE(var, head, field, tvar)
\
+ for ((var) = STAILQ_FIRST((head)); \
+ (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
+ (var) = (tvar))
+
+#define STAILQ_CONCAT(head1, head2) do {
\
+ if (!STAILQ_EMPTY((head2))) { \
+ *(head1)->stqh_last = (head2)->stqh_first; \
+ (head1)->stqh_last = (head2)->stqh_last; \
+ STAILQ_INIT((head2)); \
+ } \
+} while (0)
+
+#define STAILQ_LAST(head, type, field)
\
+ (STAILQ_EMPTY((head)) ? \
+ NULL : \
+ ((struct type *)(void *) \
+ ((char *)((head)->stqh_last) - offsetof(struct type, field))))
+
+#endif /* !_SYS_QUEUE_H_ */
