Re: [PATCH 2/2] queue.3: Fix & update after forking circleq.3, list.3, slist.3, stailq.3 & tailq.3

["Michael Kerrisk (man-pages)" <mtk.manpages@gmail.com>]

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/