summaryrefslogtreecommitdiffstats
path: root/man7/queue.7
diff options
context:
space:
mode:
Diffstat (limited to 'man7/queue.7')
-rw-r--r--man7/queue.7138
1 files changed, 0 insertions, 138 deletions
diff --git a/man7/queue.7 b/man7/queue.7
deleted file mode 100644
index 469974f..0000000
--- a/man7/queue.7
+++ /dev/null
@@ -1,138 +0,0 @@
-.\" 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-10-31 "Linux man-pages 6.7"
-.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)