diff options
| author | Alejandro Colomar <colomar.6.4.3@gmail.com> | 2020-10-25 21:46:16 +0100 |
|---|---|---|
| committer | Michael Kerrisk <mtk.manpages@gmail.com> | 2020-10-25 22:17:05 +0100 |
| commit | d9a0505f71de386ffd570ea043512a1b86874c93 (patch) | |
| tree | 8f029de62b2f37c3dfce17ad42340eec7a720301 /man7/queue.7 | |
| parent | 11fd5e7c2adf91e562465bea8250e019aebaad2f (diff) | |
| download | man-pages-d9a0505f71de386ffd570ea043512a1b86874c93.tar.gz | |
queue.3, queue.7: Move queue.3 to queue.7
After forking slist.3, list.3, tailq.3, stailq.3 & circleq.3
in the previous commits,
this page no longer belongs in Section 3 of the manual pages.
According to its contents, the most suitable section is Section 7.
Because of legacy reasons, a link queue.3 -> queue(7)
would be appropriate.
Signed-off-by: Alejandro Colomar <colomar.6.4.3@gmail.com>
Signed-off-by: Michael Kerrisk <mtk.manpages@gmail.com>
Diffstat (limited to 'man7/queue.7')
| -rw-r--r-- | man7/queue.7 | 148 |
1 files changed, 148 insertions, 0 deletions
diff --git a/man7/queue.7 b/man7/queue.7 new file mode 100644 index 0000000000..1fe48bd57b --- /dev/null +++ b/man7/queue.7 @@ -0,0 +1,148 @@ +.\" Copyright (c) 1993 +.\" 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 +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" %%%LICENSE_END +.\" +.\" +.TH QUEUE 7 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. +.IP * +Insertion of a new entry after any element in the list. +.IP * +O(1) removal of an entry from the head of the list. +.IP * +Forward traversal through the list. +.\".IP * +.\" Swapping the contents of two lists. +.PP +Code size and execution time +depend on the complexity of the data structure being used, +so programmers should take care to choose 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, +or for implementing a LIFO queue. +Singly linked lists add the following functionality: +.IP * 3 +O(n) removal of any entry in the list. +.SS Singly linked tail queues (STAILQ) +Singly linked tail queues add the following functionality: +.IP * 3 +Entries can be added at the end of a list. +.IP * +O(n) removal of any entry in the list. +.IP * +They may be concatenated. +.PP +However: +.IP * 3 +All list insertions must specify the head of the list. +.IP * +Each head entry requires two pointers rather than one. +.PP +Singly linked tail queues are ideal for applications with +large datasets and few or no removals, +or for implementing a FIFO queue. +.SS Doubly linked data structures +All doubly linked types of data structures (lists and tail queues) +additionally allow: +.IP * 3 +Insertion of a new entry before any element in the list. +.IP * +O(1) removal of any entry in the list. +.PP +However: +.IP * 3 +Each element requires two pointers rather than one. +.SS Doubly linked lists (LIST) +Linked lists are the simplest of the doubly linked data structures. +They add the following functionality over the above: +.IP * 3 +They may be traversed backwards. +.PP +However: +.IP * 3 +To traverse backwards, an entry to begin the traversal and the list in +which it is contained must be specified. +.SS Doubly linked tail queues (TAILQ) +Tail queues add the following functionality: +.IP * 3 +Entries can be added at the end of a list. +.IP * +They may be traversed backwards, from tail to head. +.IP * +They may be concatenated. +.PP +However: +.IP * 3 +All list insertions and removals must specify the head of the list. +.IP * +Each head entry requires two pointers rather than one. +.SS Doubly linked circular queues (CIRCLEQ) +Circular queues add the following functionality over the above: +.IP * 3 +The first and last entries are connected. +.PP +However: +.IP * 3 +The termination condition for traversal is more complex. +.SH CONFORMING TO +Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008. +Present on the BSDs. +.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) |