diff options
| author | Alejandro Colomar <alx@kernel.org> | 2024-04-26 15:06:49 +0200 |
|---|---|---|
| committer | Alejandro Colomar <alx@kernel.org> | 2024-05-02 01:24:19 +0200 |
| commit | dcde2f70372b49ec43efc5db864c9ff585d0a2dd (patch) | |
| tree | 78b9b7425130e4a5858e4c01a524d802423879ed /man/man7/queue.7 | |
| parent | 12aca537ce78a41bbcdaf485209691e10f8002d7 (diff) | |
| download | man-pages-dcde2f70372b49ec43efc5db864c9ff585d0a2dd.tar.gz | |
man/, share/mk/: Move man*/ to man/
This is a scripted change:
$ mkdir man/;
$ mv man* man/;
$ ln -st . man/man*;
$ find share/mk/ -type f \
| xargs grep -l '^MANDIR *:=' \
| xargs sed -i '/^MANDIR *:=/s,$,/man,';
$ find share/mk/dist/ -type f \
| xargs grep -l man \
| xargs sed -i 's,man%,man/%,g';
Link: <https://lore.kernel.org/linux-man/YxcV4h+Xn7cd6+q2@pevik/T/>
Cc: Petr Vorel <pvorel@suse.cz>
Cc: Jakub Wilk <jwilk@jwilk.net>
Cc: Stefan Puiu <stefan.puiu@gmail.com>
Signed-off-by: Alejandro Colomar <alx@kernel.org>
Diffstat (limited to 'man/man7/queue.7')
| -rw-r--r-- | man/man7/queue.7 | 138 |
1 files changed, 138 insertions, 0 deletions
diff --git a/man/man7/queue.7 b/man/man7/queue.7 new file mode 100644 index 0000000000..2b58cb43a5 --- /dev/null +++ b/man/man7/queue.7 @@ -0,0 +1,138 @@ +.\" Copyright (c) 1993 +.\" The Regents of the University of California. All rights reserved. +.\" and Copyright (c) 2020 by Alejandro Colomar <alx@kernel.org> +.\" +.\" SPDX-License-Identifier: BSD-3-Clause +.\" +.\" +.TH queue 7 (date) "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: +.TP +SLIST +singly linked lists +.TP +LIST +doubly linked lists +.TP +STAILQ +singly linked tail queues +.TP +TAILQ +doubly linked tail queues +.TP +CIRCLEQ +doubly linked circular queues +.P +All structures support the following functionality: +.IP \[bu] 3 +Insertion of a new entry at the head of the list. +.IP \[bu] +Insertion of a new entry after any element in the list. +.IP \[bu] +O(1) removal of an entry from the head of the list. +.IP \[bu] +Forward traversal through the list. +.\".IP \[bu] +.\" Swapping the contents of two lists. +.P +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 \[bu] 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 \[bu] 3 +Entries can be added at the end of a list. +.IP \[bu] +O(n) removal of any entry in the list. +.IP \[bu] +They may be concatenated. +.P +However: +.IP \[bu] 3 +All list insertions must specify the head of the list. +.IP \[bu] +Each head entry requires two pointers rather than one. +.P +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 \[bu] 3 +Insertion of a new entry before any element in the list. +.IP \[bu] +O(1) removal of any entry in the list. +.P +However: +.IP \[bu] 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 \[bu] 3 +They may be traversed backwards. +.P +However: +.IP \[bu] 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 \[bu] 3 +Entries can be added at the end of a list. +.IP \[bu] +They may be traversed backwards, from tail to head. +.IP \[bu] +They may be concatenated. +.P +However: +.IP \[bu] 3 +All list insertions and removals must specify the head of the list. +.IP \[bu] +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 \[bu] 3 +The first and last entries are connected. +.P +However: +.IP \[bu] 3 +The termination condition for traversal is more complex. +.SH STANDARDS +BSD. +.SH HISTORY +.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) |