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