diff options
Diffstat (limited to 'man/man3/stailq.3')
| -rw-r--r-- | man/man3/stailq.3 | 377 |
1 files changed, 377 insertions, 0 deletions
diff --git a/man/man3/stailq.3 b/man/man3/stailq.3 new file mode 100644 index 000000000..eca802cbd --- /dev/null +++ b/man/man3/stailq.3 @@ -0,0 +1,377 @@ +.\" 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 STAILQ 3 (date) "Linux man-pages (unreleased)" +.SH NAME +.\"SIMPLEQ_CONCAT, +SIMPLEQ_EMPTY, +SIMPLEQ_ENTRY, +SIMPLEQ_FIRST, +SIMPLEQ_FOREACH, +.\"SIMPLEQ_FOREACH_FROM, +.\"SIMPLEQ_FOREACH_FROM_SAFE, +.\"SIMPLEQ_FOREACH_SAFE, +SIMPLEQ_HEAD, +SIMPLEQ_HEAD_INITIALIZER, +SIMPLEQ_INIT, +SIMPLEQ_INSERT_AFTER, +SIMPLEQ_INSERT_HEAD, +SIMPLEQ_INSERT_TAIL, +.\"SIMPLEQ_LAST, +SIMPLEQ_NEXT, +SIMPLEQ_REMOVE, +.\"SIMPLEQ_REMOVE_AFTER, +SIMPLEQ_REMOVE_HEAD, +.\"SIMPLEQ_SWAP, +STAILQ_CONCAT, +STAILQ_EMPTY, +STAILQ_ENTRY, +STAILQ_FIRST, +STAILQ_FOREACH, +.\"STAILQ_FOREACH_FROM, +.\"STAILQ_FOREACH_FROM_SAFE, +.\"STAILQ_FOREACH_SAFE, +STAILQ_HEAD, +STAILQ_HEAD_INITIALIZER, +STAILQ_INIT, +STAILQ_INSERT_AFTER, +STAILQ_INSERT_HEAD, +STAILQ_INSERT_TAIL, +.\"STAILQ_LAST, +STAILQ_NEXT, +STAILQ_REMOVE, +.\"STAILQ_REMOVE_AFTER, +STAILQ_REMOVE_HEAD, +.\"STAILQ_SWAP +\- implementation of a singly linked tail queue +.SH LIBRARY +Standard C library +.RI ( libc ", " \-lc ) +.SH SYNOPSIS +.nf +.B #include <sys/queue.h> +.P +.B STAILQ_ENTRY(TYPE); +.P +.B STAILQ_HEAD(HEADNAME, TYPE); +.BI "STAILQ_HEAD STAILQ_HEAD_INITIALIZER(STAILQ_HEAD " head ); +.BI "void STAILQ_INIT(STAILQ_HEAD *" head ); +.P +.BI "int STAILQ_EMPTY(STAILQ_HEAD *" head ); +.P +.BI "void STAILQ_INSERT_HEAD(STAILQ_HEAD *" head , +.BI " struct TYPE *" elm ", STAILQ_ENTRY " NAME ); +.BI "void STAILQ_INSERT_TAIL(STAILQ_HEAD *" head , +.BI " struct TYPE *" elm ", STAILQ_ENTRY " NAME ); +.BI "void STAILQ_INSERT_AFTER(STAILQ_HEAD *" head ", struct TYPE *" listelm , +.BI " struct TYPE *" elm ", STAILQ_ENTRY " NAME ); +.P +.BI "struct TYPE *STAILQ_FIRST(STAILQ_HEAD *" head ); +.\" .BI "struct TYPE *STAILQ_LAST(STAILQ_HEAD *" head ", struct TYPE *" elm , +.\" .BI " STAILQ_ENTRY " NAME ); +.BI "struct TYPE *STAILQ_NEXT(struct TYPE *" elm ", STAILQ_ENTRY " NAME ); +.P +.BI "STAILQ_FOREACH(struct TYPE *" var ", STAILQ_HEAD *" head ", STAILQ_ENTRY " NAME ); +.\" .BI "STAILQ_FOREACH_FROM(struct TYPE *" var ", STAILQ_HEAD *" head , +.\" .BI " STAILQ_ENTRY " NAME ); +.\" .P +.\" .BI "STAILQ_FOREACH_SAFE(struct TYPE *" var ", STAILQ_HEAD *" head , +.\" .BI " STAILQ_ENTRY " NAME ", struct TYPE *" temp_var ); +.\" .BI "STAILQ_FOREACH_FROM_SAFE(struct TYPE *" var ", STAILQ_HEAD *" head , +.\" .BI " STAILQ_ENTRY " NAME ", struct TYPE *" temp_var ); +.P +.BI "void STAILQ_REMOVE(STAILQ_HEAD *" head ", struct TYPE *" elm ", TYPE," +.BI " STAILQ_ENTRY " NAME ); +.BI "void STAILQ_REMOVE_HEAD(STAILQ_HEAD *" head , +.BI " STAILQ_ENTRY " NAME ); +.\" .BI "void STAILQ_REMOVE_AFTER(STAILQ_HEAD *" head ", struct TYPE *" elm , +.\" .BI " STAILQ_ENTRY " NAME ); +.P +.BI "void STAILQ_CONCAT(STAILQ_HEAD *" head1 ", STAILQ_HEAD *" head2 ); +.\" .BI "void STAILQ_SWAP(STAILQ_HEAD *" head1 ", STAILQ_HEAD *" head2 , +.\" .BI " STAILQ_ENTRY " NAME ); +.fi +.IR Note : +Identical macros prefixed with SIMPLEQ instead of STAILQ exist; see NOTES. +.SH DESCRIPTION +These macros define and operate on singly linked tail queues. +.P +In the macro definitions, +.I TYPE +is the name of a user-defined structure, +that must contain a field of type +.IR STAILQ_ENTRY , +named +.IR NAME . +The argument +.I HEADNAME +is the name of a user-defined structure that must be declared +using the macro +.BR STAILQ_HEAD (). +.SS Creation +A singly linked tail queue is headed by a structure defined by the +.BR STAILQ_HEAD () +macro. +This structure contains a pair of pointers, +one to the first element in the tail queue and the other to +the last element in the tail queue. +The elements are singly linked for minimum space and pointer +manipulation overhead at the expense of O(n) removal for arbitrary elements. +New elements can be added to the tail queue after an existing element, +at the head of the tail queue, or at the end of the tail queue. +A +.I STAILQ_HEAD +structure is declared as follows: +.P +.in +4 +.EX +STAILQ_HEAD(HEADNAME, TYPE) head; +.EE +.in +.P +where +.I struct HEADNAME +is the structure to be defined, and +.I struct TYPE +is the type of the elements to be linked into the tail queue. +A pointer to the head of the tail queue can later be declared as: +.P +.in +4 +.EX +struct HEADNAME *headp; +.EE +.in +.P +(The names +.I head +and +.I headp +are user selectable.) +.P +.BR STAILQ_ENTRY () +declares a structure that connects the elements in the tail queue. +.P +.BR STAILQ_HEAD_INITIALIZER () +evaluates to an initializer for the tail queue +.IR head . +.P +.BR STAILQ_INIT () +initializes the tail queue referenced by +.IR head . +.P +.BR STAILQ_EMPTY () +evaluates to true if there are no items on the tail queue. +.SS Insertion +.BR STAILQ_INSERT_HEAD () +inserts the new element +.I elm +at the head of the tail queue. +.P +.BR STAILQ_INSERT_TAIL () +inserts the new element +.I elm +at the end of the tail queue. +.P +.BR STAILQ_INSERT_AFTER () +inserts the new element +.I elm +after the element +.IR listelm . +.SS Traversal +.BR STAILQ_FIRST () +returns the first item on the tail queue or NULL if the tail queue is empty. +.\" .P +.\" .BR STAILQ_LAST () +.\" returns the last item on the tail queue. +.\" If the tail queue is empty the return value is NULL . +.P +.BR STAILQ_NEXT () +returns the next item on the tail queue, or NULL this item is the last. +.P +.BR STAILQ_FOREACH () +traverses the tail queue referenced by +.I head +in the forward direction, +assigning each element in turn to +.IR var . +.\" .P +.\" .BR STAILQ_FOREACH_FROM () +.\" behaves identically to +.\" .BR STAILQ_FOREACH () +.\" when +.\" .I var +.\" is NULL, else it treats +.\" .I var +.\" as a previously found STAILQ element and begins the loop at +.\" .I var +.\" instead of the first element in the STAILQ referenced by +.\" .IR head . +.\" .P +.\" .BR STAILQ_FOREACH_SAFE () +.\" traverses the tail queue referenced by +.\" .I head +.\" in the forward direction, assigning each element +.\" in turn to +.\" .IR var . +.\" However, unlike +.\" .BR STAILQ_FOREACH () +.\" here it is permitted to both remove +.\" .I var +.\" as well as free it from within the loop safely without interfering with the +.\" traversal. +.\" .P +.\" .BR STAILQ_FOREACH_FROM_SAFE () +.\" behaves identically to +.\" .BR STAILQ_FOREACH_SAFE () +.\" when +.\" .I var +.\" is NULL, else it treats +.\" .I var +.\" as a previously found STAILQ element and begins the loop at +.\" .I var +.\" instead of the first element in the STAILQ referenced by +.\" .IR head . +.SS Removal +.BR STAILQ_REMOVE () +removes the element +.I elm +from the tail queue. +.P +.BR STAILQ_REMOVE_HEAD () +removes the element at the head of the tail queue. +For optimum efficiency, +elements being removed from the head of the tail queue should +use this macro explicitly rather than the generic +.BR STAILQ_REMOVE () +macro. +.\" .P +.\" .BR STAILQ_REMOVE_AFTER () +.\" removes the element after +.\" .I elm +.\" from the tail queue. +.\" Unlike +.\" .BR STAILQ_REMOVE (), +.\" this macro does not traverse the entire tail queue. +.SS Other features +.BR STAILQ_CONCAT () +concatenates the tail queue headed by +.I head2 +onto the end of the one headed by +.I head1 +removing all entries from the former. +.\" .P +.\" .BR STAILQ_SWAP () +.\" swaps the contents of +.\" .I head1 +.\" and +.\" .IR head2 . +.SH RETURN VALUE +.BR STAILQ_EMPTY () +returns nonzero if the queue is empty, +and zero if the queue contains at least one entry. +.P +.BR STAILQ_FIRST (), +and +.BR STAILQ_NEXT () +return a pointer to the first or next +.I TYPE +structure, respectively. +.P +.BR STAILQ_HEAD_INITIALIZER () +returns an initializer that can be assigned to the queue +.IR head . +.SH VERSIONS +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 BUGS +.BR STAILQ_FOREACH () +doesn't allow +.I var +to be removed or freed within the loop, +as it would interfere with the traversal. +.BR STAILQ_FOREACH_SAFE (), +which is present on the BSDs but is not present in glibc, +fixes this limitation by allowing +.I var +to safely be removed from the list and freed from within the loop +without interfering with the traversal. +.SH STANDARDS +BSD. +.SH HISTORY +4.4BSD. +.SH EXAMPLES +.\" SRC BEGIN (stailq.c) +.EX +#include <stddef.h> +#include <stdio.h> +#include <stdlib.h> +#include <sys/queue.h> +\& +struct entry { + int data; + STAILQ_ENTRY(entry) entries; /* Singly linked tail queue */ +}; +\& +STAILQ_HEAD(stailhead, entry); +\& +int +main(void) +{ + struct entry *n1, *n2, *n3, *np; + struct stailhead head; /* Singly linked tail queue + head */ +\& + STAILQ_INIT(&head); /* Initialize the queue */ +\& + n1 = malloc(sizeof(struct entry)); /* Insert at the head */ + STAILQ_INSERT_HEAD(&head, n1, entries); +\& + n1 = malloc(sizeof(struct entry)); /* Insert at the tail */ + STAILQ_INSERT_TAIL(&head, n1, entries); +\& + n2 = malloc(sizeof(struct entry)); /* Insert after */ + STAILQ_INSERT_AFTER(&head, n1, n2, entries); +\& + STAILQ_REMOVE(&head, n2, entry, entries); /* Deletion */ + free(n2); +\& + n3 = STAILQ_FIRST(&head); + STAILQ_REMOVE_HEAD(&head, entries); /* Deletion from the head */ + free(n3); +\& + n1 = STAILQ_FIRST(&head); + n1\->data = 0; + for (unsigned int i = 1; i < 5; i++) { + n1 = malloc(sizeof(struct entry)); + STAILQ_INSERT_HEAD(&head, n1, entries); + n1\->data = i; + } + /* Forward traversal */ + STAILQ_FOREACH(np, &head, entries) + printf("%i\en", np\->data); + /* TailQ deletion */ + n1 = STAILQ_FIRST(&head); + while (n1 != NULL) { + n2 = STAILQ_NEXT(n1, entries); + free(n1); + n1 = n2; + } + STAILQ_INIT(&head); +\& + exit(EXIT_SUCCESS); +} +.EE +.\" SRC END +.SH SEE ALSO +.BR insque (3), +.BR queue (7) |