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

[Alejandro Colomar <colomar.6.4.3@gmail.com>]

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
>>
> 
>