Adding upstream version 6.05.01.upstream/6.05.01

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 138 insertions, 0 deletions

diff --git a/man7/queue.7 b/man7/queue.7
new file mode 100644
index 0000000..6f2d5ab
--- /dev/null
+++ b/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 2023-03-30 "Linux man-pages 6.05.01"
+.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
+.PP
+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 *
+.\" 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 \[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.
+.PP
+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.
+.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 \[bu] 3
+Insertion of a new entry before any element in the list.
+.IP \[bu]
+O(1) removal of any entry in the list.
+.PP
+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.
+.PP
+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.
+.PP
+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.
+.PP
+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)