Re: add support for STAILQ_* to queue.h
On 23/04/2020 16:18, Todd C. Miller wrote: On Thu, 23 Apr 2020 14:40:15 +0200, Denis Fondras wrote: I don't know if it is useful to anyone else but it is required by lsquic, a library that implements QUIC / HTTP3. sniproxy port also uses STAILQ_*, there is a patch in the port for the implementation. smime.p7s Description: S/MIME Cryptographic Signature
Re: add support for STAILQ_* to queue.h
On 2020/04/23 10:31, Theo de Raadt wrote: > Todd C. Miller wrote: > > > On Thu, 23 Apr 2020 08:41:05 -0600, "Theo de Raadt" wrote: > > > > > My questions boil down to: > > > > > > 1) When are too many APIs too may? (It seems there is some agreement > > > already) > > > > > > 2) Is STAILQ more ubiqitous? (I suspect so) > > > > STAILQ is supported by: FreeBSD, macOS, NetBSD, Solaris, Linux (via libbsd) > > SIMPLEQ is supported by: NetBSD, OpenBSD, Solaris > > > > So based on a quick survey, STAILQ is more ubiqitous. > > > > > 3) Can upstream be convinced to use STAILQ instead? > > > > Upstream *is* using STAILQ, we're the ones who only support SIMPLEQ. > > > > Personally, I would rather replace SIMPLEQ with STAILQ in our code, > > though I suspect that is not a popular opinion here. When I see > > STAILQ I know exactly what it means and it is consistent with the > > other macros. I find that the SIMPLEQ naming conveys very little > > meaning and I always have to go check to see if it is singly or > > doubly linked. Of course, like most things, you get used to the > > way things are... > > I would be happy wit such unification. > > Are there any objectors? > > (finishing this might need to be put off for about a month, tho) > No objection, after we're done with release builds I can do a test ports build for this.
Re: add support for STAILQ_* to queue.h
On Thu, Apr 23, 2020 at 10:31:53AM -0600, Theo de Raadt wrote: > I would be happy wit such unification. > > Are there any objectors? > > (finishing this might need to be put off for about a month, tho) > I am currently building base with a diff that converts SIMPLEQ_* to STAILQ_*
Re: add support for STAILQ_* to queue.h
Todd C. Miller wrote: > On Thu, 23 Apr 2020 08:41:05 -0600, "Theo de Raadt" wrote: > > > My questions boil down to: > > > > 1) When are too many APIs too may? (It seems there is some agreement > > already) > > > > 2) Is STAILQ more ubiqitous? (I suspect so) > > STAILQ is supported by: FreeBSD, macOS, NetBSD, Solaris, Linux (via libbsd) > SIMPLEQ is supported by: NetBSD, OpenBSD, Solaris > > So based on a quick survey, STAILQ is more ubiqitous. > > > 3) Can upstream be convinced to use STAILQ instead? > > Upstream *is* using STAILQ, we're the ones who only support SIMPLEQ. > > Personally, I would rather replace SIMPLEQ with STAILQ in our code, > though I suspect that is not a popular opinion here. When I see > STAILQ I know exactly what it means and it is consistent with the > other macros. I find that the SIMPLEQ naming conveys very little > meaning and I always have to go check to see if it is singly or > doubly linked. Of course, like most things, you get used to the > way things are... I would be happy wit such unification. Are there any objectors? (finishing this might need to be put off for about a month, tho)
Re: add support for STAILQ_* to queue.h
On Thu, 23 Apr 2020 08:41:05 -0600, "Theo de Raadt" wrote: > My questions boil down to: > > 1) When are too many APIs too may? (It seems there is some agreement already) > > 2) Is STAILQ more ubiqitous? (I suspect so) STAILQ is supported by: FreeBSD, macOS, NetBSD, Solaris, Linux (via libbsd) SIMPLEQ is supported by: NetBSD, OpenBSD, Solaris So based on a quick survey, STAILQ is more ubiqitous. > 3) Can upstream be convinced to use STAILQ instead? Upstream *is* using STAILQ, we're the ones who only support SIMPLEQ. Personally, I would rather replace SIMPLEQ with STAILQ in our code, though I suspect that is not a popular opinion here. When I see STAILQ I know exactly what it means and it is consistent with the other macros. I find that the SIMPLEQ naming conveys very little meaning and I always have to go check to see if it is singly or doubly linked. Of course, like most things, you get used to the way things are... - todd
Re: add support for STAILQ_* to queue.h
Todd C. Miller wrote: > On Thu, 23 Apr 2020 08:35:38 -0600, "Theo de Raadt" wrote: > > > SIMPLEQ arrived in 1997. Didn't it go to other systems? Did others > > invent STAIL on their own? > > FreeBSD added STAILQ (along with SLIST) in 1996. My questions boil down to: 1) When are too many APIs too may? (It seems there is some agreement already) 2) Is STAILQ more ubiqitous? (I suspect so) 3) Can upstream be convinced to use STAILQ instead?
Re: add support for STAILQ_* to queue.h
On Thu, 23 Apr 2020 08:35:38 -0600, "Theo de Raadt" wrote: > SIMPLEQ arrived in 1997. Didn't it go to other systems? Did others > invent STAIL on their own? FreeBSD added STAILQ (along with SLIST) in 1996. - todd
Re: add support for STAILQ_* to queue.h
Denis Fondras wrote: > On Thu, Apr 23, 2020 at 08:18:16AM -0600, Todd C. Miller wrote: > > Singly-linked tail queues are functionally equivalent to the "simple > > queues" we already have. Do we really need two implementations of > > what are effectively the same thing or should we just define STAIL_* > > in terms of SIMPLEQ_* and add any missing macros? > > > > Oh! Let's try that :) > Thank you Todd. SIMPLEQ arrived in 1997. Didn't it go to other systems? Did others invent STAIL on their own? Isn't some kind of convergence possible, rather than "two macros sets"?
Re: add support for STAILQ_* to queue.h
On Thu, Apr 23, 2020 at 08:18:16AM -0600, Todd C. Miller wrote: > Singly-linked tail queues are functionally equivalent to the "simple > queues" we already have. Do we really need two implementations of > what are effectively the same thing or should we just define STAIL_* > in terms of SIMPLEQ_* and add any missing macros? > Oh! Let's try that :) Thank you Todd.
Re: add support for STAILQ_* to queue.h
On Thu, 23 Apr 2020 14:40:15 +0200, Denis Fondras wrote: > I don't know if it is useful to anyone else but it is required by lsquic, a > library that implements QUIC / HTTP3. Singly-linked tail queues are functionally equivalent to the "simple queues" we already have. Do we really need two implementations of what are effectively the same thing or should we just define STAIL_* in terms of SIMPLEQ_* and add any missing macros? - todd
add support for STAILQ_* to queue.h
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 - 1.66
+++ share/man/man3/queue.3 23 Apr 2020 11:59:19 -
@@ -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())) {
}
.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 - 1.45
+++ sys/sys/queue.h 23 Apr 2020 11:59:20 -
@@ -533,4 +533,101 @@ struct {
\
} \
} while (0)
-#endif /* !_SYS_QUEUE_H_ */
+/*
+ * Singly-linked Tail queue declarations.
+ */
+#defineSTAILQ_HEAD(name, type)
\
+struct name { \
+ struct type *stqh_first;/* first element */ \
+ struct type **stqh_last;/* addr of last next element */ \
+}
+
+#defineSTAILQ_HEAD_INITIALIZER(head)
\
+ { NULL, &(head).stqh_first }
+
+#define
