Hi Alex, On Sun, 25 Oct 2020 at 11:24, Alejandro Colomar <colomar.6.4.3@xxxxxxxxx> 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@xxxxxxxxx> > Signed-off-by: Alejandro Colomar <colomar.6.4.3@xxxxxxxxx> > --- > 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/
