* [PATCH 1/2] queue.3: Add self to copyright notice
@ 2020-10-25 10:21 Alejandro Colomar
2020-10-25 10:21 ` [PATCH 2/2] queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3 Alejandro Colomar
2020-10-25 11:40 ` [PATCH 1/2] queue.3: Add self to copyright notice Michael Kerrisk (man-pages)
0 siblings, 2 replies; 5+ messages in thread
From: Alejandro Colomar @ 2020-10-25 10:21 UTC (permalink / raw)
To: mtk.manpages; +Cc: Alejandro Colomar, linux-man, libc-alpha
Signed-off-by: Alejandro Colomar <colomar.6.4.3@gmail.com>
---
Hi Michael,
After these 2 patches, I think I'll only add one more patch
to all of the pages improving a bit the SYNOPSIS
(taking a good idea from OpenBSD's queue(3)).
I guess you're about to release, so please wait for that one :)
I'll have it in a few minutes, anyway :p
Cheers,
Alex
man3/queue.3 | 3 ++-
1 file changed, 2 insertions(+), 1 deletion(-)
diff --git a/man3/queue.3 b/man3/queue.3
index 1c9a6f573..3931f8c96 100644
--- a/man3/queue.3
+++ b/man3/queue.3
@@ -1,5 +1,6 @@
.\" Copyright (c) 1993
-.\" The Regents of the University of California. All rights reserved.
+.\" The Regents of the University of California. All rights reserved.
+.\" and Copyright (c) 2020 by Alejandro Colomar <colomar.6.4.3@gmail.com>
.\"
.\" %%%LICENSE_START(BSD_3_CLAUSE_UCB)
.\" Redistribution and use in source and binary forms, with or without
--
2.28.0
^ permalink raw reply [flat|nested] 5+ messages in thread
* [PATCH 2/2] queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3
2020-10-25 10:21 [PATCH 1/2] queue.3: Add self to copyright notice Alejandro Colomar
@ 2020-10-25 10:21 ` Alejandro Colomar
2020-10-25 11:41 ` Michael Kerrisk (man-pages)
2020-10-25 11:40 ` [PATCH 1/2] queue.3: Add self to copyright notice Michael Kerrisk (man-pages)
1 sibling, 1 reply; 5+ messages in thread
From: Alejandro Colomar @ 2020-10-25 10:21 UTC (permalink / raw)
To: mtk.manpages; +Cc: Alejandro Colomar, linux-man, libc-alpha
- ffix: Use man markup
- Remove specific notes about code size increase
and execution time increase,
as they were (at least) inaccurate.
Instead, a generic note has been added.
- Structure the text into subsections.
- Remove sections that were empty after the forks.
- Clearly relate macro names (SLIST, TAILQ, ...)
to a human readable name of which data structure
they implement.
Reported-by: Michael Kerrisk <mtk.manpages@gmail.com>
Signed-off-by: Alejandro Colomar <colomar.6.4.3@gmail.com>
---
man3/queue.3 | 189 ++++++++++++++++++++-------------------------------
1 file changed, 75 insertions(+), 114 deletions(-)
diff --git a/man3/queue.3 b/man3/queue.3
index 3931f8c96..c1b8a72a8 100644
--- a/man3/queue.3
+++ b/man3/queue.3
@@ -28,160 +28,121 @@
.\" SUCH DAMAGE.
.\" %%%LICENSE_END
.\"
-.\" @(#)queue.3 8.2 (Berkeley) 1/24/94
-.\" $FreeBSD$
.\"
-.Dd February 7, 2015
-.Dt QUEUE 3
-.Os
-.Sh NAME
-.Nd implementations of singly-linked lists, singly-linked tail queues,
-lists, tail queues, and circular queues
-.Sh SYNOPSIS
-.Sh DESCRIPTION
-These macros define and operate on five types of data structures:
-singly-linked lists, singly-linked tail queues, lists, tail queues, and
-circular queues.
-All five structures support the following functionality:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.TH QUEUE 3 2015-02-7 "GNU" "Linux Programmer's Manual"
+.SH NAME
+queue \- implementations of linked lists and queues
+.SH DESCRIPTION
+The
+.I <sys/queue.h>
+header file provides a set of macros that
+define and operate on the following data structures:
+.IP * 3
+singly-linked lists (SLIST)
+.IP *
+doubly-linked lists (LIST)
+.IP *
+singly-linked tail queues (STAILQ)
+.IP *
+doubly-linked tail queues (TAILQ)
+.IP *
+doubly-linked circular queues (CIRCLEQ)
+.PP
+All structures support the following functionality:
+.IP * 3
Insertion of a new entry at the head of the list.
-.It
+.IP *
Insertion of a new entry after any element in the list.
-.It
+.IP *
O(1) removal of an entry from the head of the list.
-.It
+.IP *
Forward traversal through the list.
-.\" .It
+.\".IP *
.\" Swapping the contents of two lists.
-.El
-.Pp
-Singly-linked lists are the simplest of the four data structures
+.PP
+Code size and execution time
+depend on the complexity of the data structure being used,
+so programmers should take care of choosing the appropriate one.
+.SS Singly-linked lists (SLIST)
+Singly-linked lists are the simplest
and support only the above functionality.
-Singly-linked lists are ideal for applications with large datasets
-and few or no removals,
+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:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
O(n) removal of any entry in the list.
-.El
-.Pp
+.SS Singly-linked tail queues (STAILQ)
Singly-linked tail queues add the following functionality:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
Entries can be added at the end of a list.
-.It
+.IP *
O(n) removal of any entry in the list.
-.It
+.IP *
They may be concatenated.
-.El
-.Pp
+.PP
However:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
All list insertions must specify the head of the list.
-.It
+.IP *
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,
+.PP
+Singly-linked tail queues are ideal for applications with
+large datasets and few or no removals,
or for implementing a FIFO queue.
-.Pp
+.SS Doubly-linked data structures
All doubly linked types of data structures (lists and tail queues)
additionally allow:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
Insertion of a new entry before any element in the list.
-.It
+.IP *
O(1) removal of any entry in the list.
-.El
-.Pp
+.PP
However:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
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
+.SS Doubly-linked lists (LIST)
Linked lists are the simplest of the doubly linked data structures.
They add the following functionality over the above:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
They may be traversed backwards.
-.El
-.Pp
+.PP
However:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
To traverse backwards, an entry to begin the traversal and the list in
which it is contained must be specified.
-.El
-.Pp
+.SS Doubly-linked tail queues (TAILQ)
Tail queues add the following functionality:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
Entries can be added at the end of a list.
-.It
+.IP *
They may be traversed backwards, from tail to head.
-.It
+.IP *
They may be concatenated.
-.El
-.Pp
+.PP
However:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
All list insertions and removals must specify the head of the list.
-.It
+.IP *
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
+.SS Doubly-linked circular queues (CIRCLEQ)
Circular queues add the following functionality over the above:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
The first and last entries are connected.
-.El
-.Pp
+.PP
However:
-.Pp
-.Bl -enum -compact -offset indent
-.It
+.IP * 3
The termination condition for traversal is more complex.
-.It
-Code size is about 40% greater and operations run about 45% slower than lists.
-.El
-.Sh EXAMPLES
-.Sh CONFORMING TO
+.SH CONFORMING TO
Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008.
Present on the BSDs.
-.Nm queue
-functions first appeared in
-.Bx 4.4 .
-.Sh SEE ALSO
-.Xr circleq 3
-.Xr insque 3
-.Xr list 3
-.Xr slist 3
-.Xr stailq 3
-.Xr tailq 3
-.\" .Xr tree 3
+.I <sys/queue.h>
+macros first appeared in 4.4BSD.
+.SH SEE ALSO
+.BR circleq (3),
+.BR insque (3),
+.BR list (3),
+.BR slist (3),
+.BR stailq (3),
+.BR tailq (3)
+.\" .BR tree (3)
--
2.28.0
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH 1/2] queue.3: Add self to copyright notice
2020-10-25 10:21 [PATCH 1/2] queue.3: Add self to copyright notice Alejandro Colomar
2020-10-25 10:21 ` [PATCH 2/2] queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3 Alejandro Colomar
@ 2020-10-25 11:40 ` Michael Kerrisk (man-pages)
1 sibling, 0 replies; 5+ messages in thread
From: Michael Kerrisk (man-pages) @ 2020-10-25 11:40 UTC (permalink / raw)
To: Alejandro Colomar; +Cc: linux-man, libc-alpha
Hi Alex,
On Sun, 25 Oct 2020 at 11:24, Alejandro Colomar <colomar.6.4.3@gmail.com> wrote:
>
> Signed-off-by: Alejandro Colomar <colomar.6.4.3@gmail.com>
Thanks. Applied.
> ---
>
> Hi Michael,
>
> After these 2 patches, I think I'll only add one more patch
> to all of the pages improving a bit the SYNOPSIS
> (taking a good idea from OpenBSD's queue(3)).
Thanks for the background.
> I guess you're about to release, so please wait for that one :)
Yes, within the next week or so.
Thanks,
Michael
> I'll have it in a few minutes, anyway :p
>
> Cheers,
>
> Alex
>
> man3/queue.3 | 3 ++-
> 1 file changed, 2 insertions(+), 1 deletion(-)
>
> diff --git a/man3/queue.3 b/man3/queue.3
> index 1c9a6f573..3931f8c96 100644
> --- a/man3/queue.3
> +++ b/man3/queue.3
> @@ -1,5 +1,6 @@
> .\" Copyright (c) 1993
> -.\" The Regents of the University of California. All rights reserved.
> +.\" The Regents of the University of California. All rights reserved.
> +.\" and Copyright (c) 2020 by Alejandro Colomar <colomar.6.4.3@gmail.com>
> .\"
> .\" %%%LICENSE_START(BSD_3_CLAUSE_UCB)
> .\" Redistribution and use in source and binary forms, with or without
> --
> 2.28.0
>
--
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH 2/2] queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3
2020-10-25 10:21 ` [PATCH 2/2] queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3 Alejandro Colomar
@ 2020-10-25 11:41 ` Michael Kerrisk (man-pages)
2020-10-25 20:18 ` Alejandro Colomar
0 siblings, 1 reply; 5+ messages in thread
From: Michael Kerrisk (man-pages) @ 2020-10-25 11:41 UTC (permalink / raw)
To: Alejandro Colomar; +Cc: linux-man, libc-alpha
Hi Alex,
On Sun, 25 Oct 2020 at 11:24, Alejandro Colomar <colomar.6.4.3@gmail.com> wrote:
>
> - ffix: Use man markup
> - Remove specific notes about code size increase
> and execution time increase,
> as they were (at least) inaccurate.
> Instead, a generic note has been added.
> - Structure the text into subsections.
> - Remove sections that were empty after the forks.
> - Clearly relate macro names (SLIST, TAILQ, ...)
> to a human readable name of which data structure
> they implement.
Good clean-up! Thanks!
Applied.
Cheers,
Michael
> Reported-by: Michael Kerrisk <mtk.manpages@gmail.com>
> Signed-off-by: Alejandro Colomar <colomar.6.4.3@gmail.com>
> ---
> man3/queue.3 | 189 ++++++++++++++++++++-------------------------------
> 1 file changed, 75 insertions(+), 114 deletions(-)
>
> diff --git a/man3/queue.3 b/man3/queue.3
> index 3931f8c96..c1b8a72a8 100644
> --- a/man3/queue.3
> +++ b/man3/queue.3
> @@ -28,160 +28,121 @@
> .\" SUCH DAMAGE.
> .\" %%%LICENSE_END
> .\"
> -.\" @(#)queue.3 8.2 (Berkeley) 1/24/94
> -.\" $FreeBSD$
> .\"
> -.Dd February 7, 2015
> -.Dt QUEUE 3
> -.Os
> -.Sh NAME
> -.Nd implementations of singly-linked lists, singly-linked tail queues,
> -lists, tail queues, and circular queues
> -.Sh SYNOPSIS
> -.Sh DESCRIPTION
> -These macros define and operate on five types of data structures:
> -singly-linked lists, singly-linked tail queues, lists, tail queues, and
> -circular queues.
> -All five structures support the following functionality:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.TH QUEUE 3 2015-02-7 "GNU" "Linux Programmer's Manual"
> +.SH NAME
> +queue \- implementations of linked lists and queues
> +.SH DESCRIPTION
> +The
> +.I <sys/queue.h>
> +header file provides a set of macros that
> +define and operate on the following data structures:
> +.IP * 3
> +singly-linked lists (SLIST)
> +.IP *
> +doubly-linked lists (LIST)
> +.IP *
> +singly-linked tail queues (STAILQ)
> +.IP *
> +doubly-linked tail queues (TAILQ)
> +.IP *
> +doubly-linked circular queues (CIRCLEQ)
> +.PP
> +All structures support the following functionality:
> +.IP * 3
> Insertion of a new entry at the head of the list.
> -.It
> +.IP *
> Insertion of a new entry after any element in the list.
> -.It
> +.IP *
> O(1) removal of an entry from the head of the list.
> -.It
> +.IP *
> Forward traversal through the list.
> -.\" .It
> +.\".IP *
> .\" Swapping the contents of two lists.
> -.El
> -.Pp
> -Singly-linked lists are the simplest of the four data structures
> +.PP
> +Code size and execution time
> +depend on the complexity of the data structure being used,
> +so programmers should take care of choosing the appropriate one.
> +.SS Singly-linked lists (SLIST)
> +Singly-linked lists are the simplest
> and support only the above functionality.
> -Singly-linked lists are ideal for applications with large datasets
> -and few or no removals,
> +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:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> O(n) removal of any entry in the list.
> -.El
> -.Pp
> +.SS Singly-linked tail queues (STAILQ)
> Singly-linked tail queues add the following functionality:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> Entries can be added at the end of a list.
> -.It
> +.IP *
> O(n) removal of any entry in the list.
> -.It
> +.IP *
> They may be concatenated.
> -.El
> -.Pp
> +.PP
> However:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> All list insertions must specify the head of the list.
> -.It
> +.IP *
> 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,
> +.PP
> +Singly-linked tail queues are ideal for applications with
> +large datasets and few or no removals,
> or for implementing a FIFO queue.
> -.Pp
> +.SS Doubly-linked data structures
> All doubly linked types of data structures (lists and tail queues)
> additionally allow:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> Insertion of a new entry before any element in the list.
> -.It
> +.IP *
> O(1) removal of any entry in the list.
> -.El
> -.Pp
> +.PP
> However:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> 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
> +.SS Doubly-linked lists (LIST)
> Linked lists are the simplest of the doubly linked data structures.
> They add the following functionality over the above:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> They may be traversed backwards.
> -.El
> -.Pp
> +.PP
> However:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> To traverse backwards, an entry to begin the traversal and the list in
> which it is contained must be specified.
> -.El
> -.Pp
> +.SS Doubly-linked tail queues (TAILQ)
> Tail queues add the following functionality:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> Entries can be added at the end of a list.
> -.It
> +.IP *
> They may be traversed backwards, from tail to head.
> -.It
> +.IP *
> They may be concatenated.
> -.El
> -.Pp
> +.PP
> However:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> All list insertions and removals must specify the head of the list.
> -.It
> +.IP *
> 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
> +.SS Doubly-linked circular queues (CIRCLEQ)
> Circular queues add the following functionality over the above:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> The first and last entries are connected.
> -.El
> -.Pp
> +.PP
> However:
> -.Pp
> -.Bl -enum -compact -offset indent
> -.It
> +.IP * 3
> The termination condition for traversal is more complex.
> -.It
> -Code size is about 40% greater and operations run about 45% slower than lists.
> -.El
> -.Sh EXAMPLES
> -.Sh CONFORMING TO
> +.SH CONFORMING TO
> Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008.
> Present on the BSDs.
> -.Nm queue
> -functions first appeared in
> -.Bx 4.4 .
> -.Sh SEE ALSO
> -.Xr circleq 3
> -.Xr insque 3
> -.Xr list 3
> -.Xr slist 3
> -.Xr stailq 3
> -.Xr tailq 3
> -.\" .Xr tree 3
> +.I <sys/queue.h>
> +macros first appeared in 4.4BSD.
> +.SH SEE ALSO
> +.BR circleq (3),
> +.BR insque (3),
> +.BR list (3),
> +.BR slist (3),
> +.BR stailq (3),
> +.BR tailq (3)
> +.\" .BR tree (3)
> --
> 2.28.0
>
--
Michael Kerrisk
Linux man-pages maintainer; http://www.kernel.org/doc/man-pages/
Linux/UNIX System Programming Training: http://man7.org/training/
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH 2/2] queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3
2020-10-25 11:41 ` Michael Kerrisk (man-pages)
@ 2020-10-25 20:18 ` Alejandro Colomar
0 siblings, 0 replies; 5+ messages in thread
From: Alejandro Colomar @ 2020-10-25 20:18 UTC (permalink / raw)
To: mtk.manpages; +Cc: linux-man, libc-alpha
On 2020-10-25 12:41, Michael Kerrisk (man-pages) wrote:
> Hi Alex,
>
> On Sun, 25 Oct 2020 at 11:24, Alejandro Colomar <colomar.6.4.3@gmail.com> wrote:
>>
>> - ffix: Use man markup
>> - Remove specific notes about code size increase
>> and execution time increase,
>> as they were (at least) inaccurate.
>> Instead, a generic note has been added.
>> - Structure the text into subsections.
>> - Remove sections that were empty after the forks.
>> - Clearly relate macro names (SLIST, TAILQ, ...)
>> to a human readable name of which data structure
>> they implement.
>
> Good clean-up! Thanks!
:-)
Thanks,
Alex
>
> Applied.
>
> Cheers,
>
> Michael
>
>> Reported-by: Michael Kerrisk <mtk.manpages@gmail.com>
>> Signed-off-by: Alejandro Colomar <colomar.6.4.3@gmail.com>
>> ---
>> man3/queue.3 | 189 ++++++++++++++++++++-------------------------------
>> 1 file changed, 75 insertions(+), 114 deletions(-)
>>
>> diff --git a/man3/queue.3 b/man3/queue.3
>> index 3931f8c96..c1b8a72a8 100644
>> --- a/man3/queue.3
>> +++ b/man3/queue.3
>> @@ -28,160 +28,121 @@
>> .\" SUCH DAMAGE.
>> .\" %%%LICENSE_END
>> .\"
>> -.\" @(#)queue.3 8.2 (Berkeley) 1/24/94
>> -.\" $FreeBSD$
>> .\"
>> -.Dd February 7, 2015
>> -.Dt QUEUE 3
>> -.Os
>> -.Sh NAME
>> -.Nd implementations of singly-linked lists, singly-linked tail queues,
>> -lists, tail queues, and circular queues
>> -.Sh SYNOPSIS
>> -.Sh DESCRIPTION
>> -These macros define and operate on five types of data structures:
>> -singly-linked lists, singly-linked tail queues, lists, tail queues, and
>> -circular queues.
>> -All five structures support the following functionality:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.TH QUEUE 3 2015-02-7 "GNU" "Linux Programmer's Manual"
>> +.SH NAME
>> +queue \- implementations of linked lists and queues
>> +.SH DESCRIPTION
>> +The
>> +.I <sys/queue.h>
>> +header file provides a set of macros that
>> +define and operate on the following data structures:
>> +.IP * 3
>> +singly-linked lists (SLIST)
>> +.IP *
>> +doubly-linked lists (LIST)
>> +.IP *
>> +singly-linked tail queues (STAILQ)
>> +.IP *
>> +doubly-linked tail queues (TAILQ)
>> +.IP *
>> +doubly-linked circular queues (CIRCLEQ)
>> +.PP
>> +All structures support the following functionality:
>> +.IP * 3
>> Insertion of a new entry at the head of the list.
>> -.It
>> +.IP *
>> Insertion of a new entry after any element in the list.
>> -.It
>> +.IP *
>> O(1) removal of an entry from the head of the list.
>> -.It
>> +.IP *
>> Forward traversal through the list.
>> -.\" .It
>> +.\".IP *
>> .\" Swapping the contents of two lists.
>> -.El
>> -.Pp
>> -Singly-linked lists are the simplest of the four data structures
>> +.PP
>> +Code size and execution time
>> +depend on the complexity of the data structure being used,
>> +so programmers should take care of choosing the appropriate one.
>> +.SS Singly-linked lists (SLIST)
>> +Singly-linked lists are the simplest
>> and support only the above functionality.
>> -Singly-linked lists are ideal for applications with large datasets
>> -and few or no removals,
>> +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:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> O(n) removal of any entry in the list.
>> -.El
>> -.Pp
>> +.SS Singly-linked tail queues (STAILQ)
>> Singly-linked tail queues add the following functionality:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> Entries can be added at the end of a list.
>> -.It
>> +.IP *
>> O(n) removal of any entry in the list.
>> -.It
>> +.IP *
>> They may be concatenated.
>> -.El
>> -.Pp
>> +.PP
>> However:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> All list insertions must specify the head of the list.
>> -.It
>> +.IP *
>> 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,
>> +.PP
>> +Singly-linked tail queues are ideal for applications with
>> +large datasets and few or no removals,
>> or for implementing a FIFO queue.
>> -.Pp
>> +.SS Doubly-linked data structures
>> All doubly linked types of data structures (lists and tail queues)
>> additionally allow:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> Insertion of a new entry before any element in the list.
>> -.It
>> +.IP *
>> O(1) removal of any entry in the list.
>> -.El
>> -.Pp
>> +.PP
>> However:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> 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
>> +.SS Doubly-linked lists (LIST)
>> Linked lists are the simplest of the doubly linked data structures.
>> They add the following functionality over the above:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> They may be traversed backwards.
>> -.El
>> -.Pp
>> +.PP
>> However:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> To traverse backwards, an entry to begin the traversal and the list in
>> which it is contained must be specified.
>> -.El
>> -.Pp
>> +.SS Doubly-linked tail queues (TAILQ)
>> Tail queues add the following functionality:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> Entries can be added at the end of a list.
>> -.It
>> +.IP *
>> They may be traversed backwards, from tail to head.
>> -.It
>> +.IP *
>> They may be concatenated.
>> -.El
>> -.Pp
>> +.PP
>> However:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> All list insertions and removals must specify the head of the list.
>> -.It
>> +.IP *
>> 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
>> +.SS Doubly-linked circular queues (CIRCLEQ)
>> Circular queues add the following functionality over the above:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> The first and last entries are connected.
>> -.El
>> -.Pp
>> +.PP
>> However:
>> -.Pp
>> -.Bl -enum -compact -offset indent
>> -.It
>> +.IP * 3
>> The termination condition for traversal is more complex.
>> -.It
>> -Code size is about 40% greater and operations run about 45% slower than lists.
>> -.El
>> -.Sh EXAMPLES
>> -.Sh CONFORMING TO
>> +.SH CONFORMING TO
>> Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008.
>> Present on the BSDs.
>> -.Nm queue
>> -functions first appeared in
>> -.Bx 4.4 .
>> -.Sh SEE ALSO
>> -.Xr circleq 3
>> -.Xr insque 3
>> -.Xr list 3
>> -.Xr slist 3
>> -.Xr stailq 3
>> -.Xr tailq 3
>> -.\" .Xr tree 3
>> +.I <sys/queue.h>
>> +macros first appeared in 4.4BSD.
>> +.SH SEE ALSO
>> +.BR circleq (3),
>> +.BR insque (3),
>> +.BR list (3),
>> +.BR slist (3),
>> +.BR stailq (3),
>> +.BR tailq (3)
>> +.\" .BR tree (3)
>> --
>> 2.28.0
>>
>
>
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2020-10-25 20:18 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-10-25 10:21 [PATCH 1/2] queue.3: Add self to copyright notice Alejandro Colomar
2020-10-25 10:21 ` [PATCH 2/2] queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3 Alejandro Colomar
2020-10-25 11:41 ` Michael Kerrisk (man-pages)
2020-10-25 20:18 ` Alejandro Colomar
2020-10-25 11:40 ` [PATCH 1/2] queue.3: Add self to copyright notice Michael Kerrisk (man-pages)
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).