diff options
Diffstat (limited to 'man7/queue.7')
| -rw-r--r-- | man7/queue.7 | 138 |
1 files changed, 0 insertions, 138 deletions
diff --git a/man7/queue.7 b/man7/queue.7 deleted file mode 100644 index 2b58cb43a..000000000 --- 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 (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) |