diff options
Diffstat (limited to 'man7/queue.7')
| -rw-r--r-- | man7/queue.7 | 138 |
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) |