diff options
| author | Alejandro Colomar <alx.manpages@gmail.com> | 2022-09-05 23:03:38 +0200 |
|---|---|---|
| committer | Alejandro Colomar <alx.manpages@gmail.com> | 2022-09-05 23:03:47 +0200 |
| commit | 70ac1c4785fc1e158ab2349a962dba2526bf4fbc (patch) | |
| tree | bff270e2496dd284bccfc1271b43946f5d225224 /man/man7/queue.7 | |
| parent | 5423a6f86b2b920a5f3e8cf8d759b513050f2d33 (diff) | |
| download | man-pages-70ac1c4785fc1e158ab2349a962dba2526bf4fbc.tar.gz | |
src.mk, All pages: Move man* to man/
The root of the repository is becoming a bit overpopulated and
unorganized, due to the recent addition of more mandirs, and more
informative and configuration files too. Let's create a specific
mandir <man/> that contains the mandirs <man[1-8]*>.
Signed-off-by: Alejandro Colomar <alx.manpages@gmail.com>
Diffstat (limited to 'man/man7/queue.7')
| -rw-r--r-- | man/man7/queue.7 | 133 |
1 files changed, 133 insertions, 0 deletions
diff --git a/man/man7/queue.7 b/man/man7/queue.7 new file mode 100644 index 0000000000..87efb9e0d5 --- /dev/null +++ b/man/man7/queue.7 @@ -0,0 +1,133 @@ +.\" 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> +.\" +.\" SPDX-License-Identifier: BSD-3-Clause +.\" +.\" +.TH QUEUE 7 2021-03-22 "Linux man-pages (unreleased)" +.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 STANDARDS +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 NOTES +Some BSDs provide SIMPLEQ instead of STAILQ. +They are identical, but for historical reasons +they were named differently on different BSDs. +STAILQ originated on FreeBSD, and SIMPLEQ originated on NetBSD. +For compatibility reasons, some systems provide both sets of macros. +Glibc provides both STAILQ and SIMPLEQ, +which are identical except for a missing SIMPLEQ equivalent to +.BR STAILQ_CONCAT (). +.SH SEE ALSO +.BR circleq (3), +.BR insque (3), +.BR list (3), +.BR slist (3), +.BR stailq (3), +.BR tailq (3) +.\" .BR tree (3) |