diff options
Diffstat (limited to 'static/netbsd/man3/queue.3')
| -rw-r--r-- | static/netbsd/man3/queue.3 | 1103 |
1 files changed, 1103 insertions, 0 deletions
diff --git a/static/netbsd/man3/queue.3 b/static/netbsd/man3/queue.3 new file mode 100644 index 00000000..095c5b7c --- /dev/null +++ b/static/netbsd/man3/queue.3 @@ -0,0 +1,1103 @@ +.\" $NetBSD: queue.3,v 1.61 2020/10/20 23:27:57 kamil Exp $ +.\" +.\" Copyright (c) 2000, 2002 The NetBSD Foundation, Inc. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS +.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR +.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS +.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +.\" POSSIBILITY OF SUCH DAMAGE. +.\" +.\" Copyright (c) 1993 The Regents of the University of California. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. Neither the name of the University nor the names of its contributors +.\" may be used to endorse or promote products derived from this software +.\" without specific prior written permission. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" @(#)queue.3 8.1 (Berkeley) 12/13/93 +.\" +.Dd October 1, 2017 +.Dt QUEUE 3 +.Os +.Sh NAME +.Nm SLIST_HEAD , +.Nm SLIST_HEAD_INITIALIZER , +.Nm SLIST_ENTRY , +.Nm SLIST_FIRST , +.Nm SLIST_EMPTY , +.Nm SLIST_NEXT , +.Nm SLIST_FOREACH , +.Nm SLIST_FOREACH_SAFE , +.Nm SLIST_INIT , +.Nm SLIST_INSERT_AFTER , +.Nm SLIST_INSERT_HEAD , +.Nm SLIST_REMOVE_AFTER , +.Nm SLIST_REMOVE_HEAD , +.Nm SLIST_REMOVE , +.Nm LIST_HEAD , +.Nm LIST_HEAD_INITIALIZER , +.Nm LIST_ENTRY , +.Nm LIST_FIRST , +.Nm LIST_EMPTY , +.Nm LIST_NEXT , +.Nm LIST_FOREACH , +.Nm LIST_FOREACH_SAFE , +.Nm LIST_INIT , +.Nm LIST_INSERT_AFTER , +.Nm LIST_INSERT_BEFORE , +.Nm LIST_INSERT_HEAD , +.Nm LIST_REMOVE , +.Nm LIST_REPLACE , +.Nm LIST_MOVE , +.Nm SIMPLEQ_HEAD , +.Nm SIMPLEQ_HEAD_INITIALIZER , +.Nm SIMPLEQ_ENTRY , +.Nm SIMPLEQ_FIRST , +.Nm SIMPLEQ_EMPTY , +.Nm SIMPLEQ_NEXT , +.Nm SIMPLEQ_LAST , +.Nm SIMPLEQ_FOREACH , +.Nm SIMPLEQ_FOREACH_SAFE , +.Nm SIMPLEQ_INIT , +.Nm SIMPLEQ_INSERT_AFTER , +.Nm SIMPLEQ_INSERT_HEAD , +.Nm SIMPLEQ_INSERT_TAIL , +.Nm SIMPLEQ_REMOVE_AFTER , +.Nm SIMPLEQ_REMOVE_HEAD , +.Nm SIMPLEQ_REMOVE , +.Nm SIMPLEQ_CONCAT , +.Nm TAILQ_HEAD , +.Nm TAILQ_HEAD_INITIALIZER , +.Nm TAILQ_ENTRY , +.Nm TAILQ_FIRST , +.Nm TAILQ_NEXT , +.Nm TAILQ_LAST , +.Nm TAILQ_PREV , +.Nm TAILQ_EMPTY , +.Nm TAILQ_FOREACH , +.Nm TAILQ_FOREACH_SAFE , +.Nm TAILQ_FOREACH_REVERSE , +.Nm TAILQ_FOREACH_REVERSE_SAFE , +.Nm TAILQ_INIT , +.Nm TAILQ_INSERT_AFTER , +.Nm TAILQ_INSERT_BEFORE , +.Nm TAILQ_INSERT_HEAD , +.Nm TAILQ_INSERT_TAIL , +.Nm TAILQ_REMOVE , +.Nm TAILQ_REPLACE , +.Nm TAILQ_CONCAT , +.Nm STAILQ_HEAD , +.Nm STAILQ_HEAD_INITIALIZER , +.Nm STAILQ_ENTRY , +.Nm STAILQ_FIRST , +.Nm STAILQ_EMPTY , +.Nm STAILQ_NEXT , +.Nm STAILQ_LAST , +.Nm STAILQ_FOREACH , +.Nm STAILQ_FOREACH_SAFE , +.Nm STAILQ_INIT , +.Nm STAILQ_INSERT_AFTER , +.Nm STAILQ_INSERT_HEAD , +.Nm STAILQ_INSERT_TAIL , +.Nm STAILQ_REMOVE_HEAD , +.Nm STAILQ_REMOVE , +.Nm STAILQ_CONCAT +.Nd implementations of singly-linked lists, lists, simple queues, tail queues, and singly-linked tail queues +.Sh SYNOPSIS +.In sys/queue.h +.Pp +.Fn SLIST_HEAD "HEADNAME" "TYPE" +.Fn SLIST_HEAD_INITIALIZER "head" +.Fn SLIST_ENTRY "TYPE" +.Ft TYPE * +.Fn SLIST_FIRST "SLIST_HEAD *head" +.Ft int +.Fn SLIST_EMPTY "SLIST_HEAD *head" +.Ft TYPE * +.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" +.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" +.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *tmp" +.Fn SLIST_INIT "SLIST_HEAD *head" +.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" +.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" +.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" +.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" +.Pp +.Fn LIST_HEAD "HEADNAME" "TYPE" +.Fn LIST_HEAD_INITIALIZER "head" +.Fn LIST_ENTRY "TYPE" +.Ft TYPE * +.Fn LIST_FIRST "LIST_HEAD *head" +.Ft TYPE * +.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" +.Ft int +.Fn LIST_EMPTY "LIST_HEAD *head" +.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" +.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *tmp" +.Fn LIST_INIT "LIST_HEAD *head" +.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" +.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" +.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" +.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" +.Fn LIST_REPLACE "TYPE *elm" "TYPE *new" "LIST_ENTRY NAME" +.Fn LIST_MOVE "LIST_HEAD *head1" "LIST_HEAD *head2" "LIST_ENTRY NAME" +.Pp +.Fn SIMPLEQ_HEAD "HEADNAME" "TYPE" +.Fn SIMPLEQ_HEAD_INITIALIZER "head" +.Fn SIMPLEQ_ENTRY "TYPE" +.Ft TYPE * +.Fn SIMPLEQ_FIRST "SIMPLEQ_HEAD *head" +.Ft int +.Fn SIMPLEQ_EMPTY "SIMPLEQ_HEAD *head" +.Ft TYPE * +.Fn SIMPLEQ_NEXT "TYPE *elm" "SIMPLEQ_ENTRY NAME" +.Ft TYPE * +.Fn SIMPLEQ_LAST "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" +.Fn SIMPLEQ_FOREACH "TYPE *var" "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME" +.Fn SIMPLEQ_FOREACH_SAFE "TYPE *var" "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME" "TYPE *tmp" +.Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head" +.Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" +.Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" +.Fn SIMPLEQ_INSERT_AFTER "SIMPLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "SIMPLEQ_ENTRY NAME" +.Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME" +.Fn SIMPLEQ_REMOVE_AFTER "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME" +.Fn SIMPLEQ_REMOVE "SIMPLEQ_HEAD *head" "TYPE *elm" "TYPE" "SIMPLEQ_ENTRY NAME" +.Fn SIMPLEQ_CONCAT "SIMPLEQ_HEAD *head1" "SIMPLEQ_HEAD *head2" +.Pp +.Fn TAILQ_HEAD "HEADNAME" "TYPE" +.Fn TAILQ_HEAD_INITIALIZER "head" +.Fn TAILQ_ENTRY "TYPE" +.Ft TYPE * +.Fn TAILQ_FIRST "TAILQ_HEAD *head" +.Ft TYPE * +.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" +.Ft TYPE * +.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" +.Ft TYPE * +.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" +.Ft int +.Fn TAILQ_EMPTY "TAILQ_HEAD *head" +.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" +.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *tmp" +.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" +.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *tmp" +.Fn TAILQ_INIT "TAILQ_HEAD *head" +.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" +.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" +.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" +.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" +.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" +.Fn TAILQ_REPLACE "TAILQ_HEAD *head" "TYPE *elm" "TYPE *new" "TAILQ_ENTRY NAME" +.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME" +.Pp +.Fn STAILQ_HEAD "HEADNAME" "TYPE" +.Fn STAILQ_HEAD_INITIALIZER "head" +.Fn STAILQ_ENTRY "TYPE" +.Ft TYPE * +.Fn STAILQ_FIRST "STAILQ_HEAD *head" +.Ft int +.Fn STAILQ_EMPTY "STAILQ_HEAD *head" +.Ft TYPE * +.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" +.Ft TYPE * +.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" +.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *tmp" +.Fn STAILQ_INIT "STAILQ_HEAD *head" +.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" +.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" +.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" +.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" +.Sh DESCRIPTION +These macros define and operate on five types of data structures: +singly-linked lists, simple queues, lists, tail queues, and singly-linked +tail queues. +All five structures support the following functionality: +.Bl -enum -compact -offset indent +.It +Insertion of a new entry at the head of the list. +.It +Insertion of a new entry after any element in the list. +.It +Removal of any entry in the list. +.It +Forward traversal through the list. +.El +.Pp +Singly-linked lists are the simplest of the four data structures 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. +.Pp +Simple queues add the following functionality: +.Bl -enum -compact -offset indent +.It +Entries can be added at the end of a list. +.It +They may be concatenated. +.El +However: +.Bl -enum -compact -offset indent +.It +Entries may not be added before any element in the list. +.It +All list insertions and removals must specify the head of the list. +.It +Each head entry requires two pointers rather than one. +.El +.Pp +Simple queues are ideal for applications with large datasets and few or +no removals, or for implementing a FIFO queue. +.Pp +All doubly linked types of data structures (lists and tail queues) +additionally allow: +.Bl -enum -compact -offset indent +.It +Insertion of a new entry before any element in the list. +.It +O(1) removal of any entry in the list. +.El +However: +.Bl -enum -compact -offset indent +.It +Each element requires two pointers rather than one. +.It +Code size and execution time of operations (except for removal) is about +twice that of the singly-linked data-structures. +.El +.Pp +Linked lists are the simplest of the doubly linked data structures and +support only the above functionality over singly-linked lists. +.Pp +Tail queues add the following functionality: +.Bl -enum -compact -offset indent +.It +Entries can be added at the end of a list. +.It +They may be concatenated. +.El +However: +.Bl -enum -compact -offset indent +.It +All list insertions and removals, except insertion before another element, must +specify the head of the list. +.It +Each head entry requires two pointers rather than one. +.It +Code size is about 15% greater and operations run about 20% slower +than lists. +.El +.Pp +Circular queues add the following functionality: +.Bl -enum -compact -offset indent +.It +Entries can be added at the end of a list. +.It +They may be traversed backwards, from tail to head. +.El +However: +.Bl -enum -compact -offset indent +.It +All list insertions and removals must specify the head of the list. +.It +Each head entry requires two pointers rather than one. +.It +The termination condition for traversal is more complex. +.It +Code size is about 40% greater and operations run about 45% slower +than lists. +.El +.Pp +In the macro definitions, +.Fa TYPE +is the name of a user defined structure, +that must contain a field of type +.Li SLIST_ENTRY , +.Li LIST_ENTRY , +.Li SIMPLEQ_ENTRY , +.Li TAILQ_ENTRY , +or +.Li STAILQ_ENTRY , +named +.Fa NAME . +The argument +.Fa HEADNAME +is the name of a user defined structure that must be declared +using the macros +.Li LIST_HEAD , +.Li SIMPLEQ_HEAD , +.Li SLIST_HEAD , +or +.Li TAILQ_HEAD . +See the examples below for further explanation of how these +macros are used. +.Ss Summary of Operations +The following table summarizes the supported macros for each type +of data structure. +.Pp +.TS +box tab(:); +l | c | c | c | c | c +l | c | c | c | c | c +l | c | c | c | c | c +l | c | c | c | c | c +l | c | c | c | c | c +l | c | c | c | c | c. +:SLIST:LIST:SIMPLEQ:TAILQ:STAILQ +_ +_FIRST:+:+:+:+:+ +_EMPTY:+:+:+:+:+ +_NEXT:+:+:+:+:+ +_PREV:-:-:-:+:- +_LAST:-:-:+:+:+ +_FOREACH:+:+:+:+:+ +_FOREACH_SAFE:+:+:+:+:+ +_FOREACH_REVERSE:-:-:-:+:- +_FOREACH_REVERSE_SAFE:-:-:-:+:- +_INSERT_HEAD:+:+:+:+:+ +_INSERT_AFTER:+:+:+:+:+ +_INSERT_BEFORE:-:+:-:+:- +_INSERT_TAIL:-:-:+:+:+ +_REMOVE:+:+:+:+:+ +_REMOVE_HEAD:+:-:+:-:+ +_REMOVE_AFTER:-:-:+:-:+ +_REPLACE:-:+:-:+:- +_CONCAT:-:-:+:+:+ +.TE +.Sh SINGLY-LINKED LISTS +A singly-linked list is headed by a structure defined by the +.Fn SLIST_HEAD +macro. +This structure contains a single pointer to the first element +on the list. +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 list after an existing element or +at the head of the list. +An +.Fa SLIST_HEAD +structure is declared as follows: +.Bd -literal -offset indent +SLIST_HEAD(HEADNAME, TYPE) head; +.Ed +.Pp +where +.Fa HEADNAME +is the name of the structure to be defined, and +.Fa TYPE +is the type of the elements to be linked into the list. +A pointer to the head of the list can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The macro +.Fn SLIST_HEAD_INITIALIZER +evaluates to an initializer for the list +.Fa head . +.Pp +The macro +.Fn SLIST_ENTRY +declares a structure that connects the elements in +the list. +.Pp +The macro +.Fn SLIST_FIRST +returns the first element in the list or NULL if the list is empty. +.Pp +The macro +.Fn SLIST_EMPTY +evaluates to true if there are no elements in the list. +.Pp +The macro +.Fn SLIST_NEXT +returns the next element in the list. +.Pp +.Fn SLIST_FOREACH +traverses the list referenced by +.Fa head +in the forward direction, assigning each element in +turn to +.Fa var . +.Pp +The SAFE version uses +.Fa tmp +to hold the next element, so +.Fa var +may be freed or removed from the list. +.Pp +The macro +.Fn SLIST_INIT +initializes the list referenced by +.Fa head . +.Pp +The macro +.Fn SLIST_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the list. +.Pp +The macro +.Fn SLIST_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Fn SLIST_REMOVE +removes the element +.Fa elm +from the list. +.Pp +The macro +.Fn SLIST_REMOVE_HEAD +removes the first element from the head of the list. +For optimum efficiency, +elements being removed from the head of the list should explicitly use +this macro instead of the generic +.Fn SLIST_REMOVE +macro. +.Pp +The macro +.Fn SLIST_REMOVE_AFTER +removes the element after the one specified. +For optimum efficiency, +elements being removed after a specified one should explicitly use +this macro instead of the generic +.Fn SLIST_REMOVE +.Sh SINGLY-LINKED LIST EXAMPLE +.Bd -literal +SLIST_HEAD(slisthead, entry) head = + SLIST_HEAD_INITIALIZER(head); +struct slisthead *headp; /* Singly-linked List head. */ +struct entry { + ... + SLIST_ENTRY(entry) entries; /* Singly-linked List. */ + ... +} *n1, *n2, *n3, *np; + +SLIST_INIT(&head); /* Initialize the list. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +SLIST_INSERT_HEAD(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +SLIST_INSERT_AFTER(n1, n2, entries); + +SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */ +free(n2); + +n3 = SLIST_FIRST(&head); +SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */ +free(n3); + +SLIST_FOREACH(np, &head, entries) /* Forward traversal. */ + np-> ... + +while (!SLIST_EMPTY(&head)) { /* List Deletion. */ + n1 = SLIST_FIRST(&head); + SLIST_REMOVE_HEAD(&head, entries); + free(n1); +} +.Ed +.Sh LISTS +A list is headed by a structure defined by the +.Fn LIST_HEAD +macro. +This structure contains a single pointer to the first element +on the list. +The elements are doubly linked so that an arbitrary element can be +removed without traversing the list. +New elements can be added to the list after an existing element, +before an existing element, or at the head of the list. +A +.Fa LIST_HEAD +structure is declared as follows: +.Bd -literal -offset indent +LIST_HEAD(HEADNAME, TYPE) head; +.Ed +.Pp +where +.Fa HEADNAME +is the name of the structure to be defined, and +.Fa TYPE +is the type of the elements to be linked into the list. +A pointer to the head of the list can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The macro +.Fn LIST_ENTRY +declares a structure that connects the elements in +the list. +.Pp +The macro +.Fn LIST_HEAD_INITIALIZER +provides a value which can be used to initialize a list head at +compile time, and is used at the point that the list head +variable is declared, like: +.Bd -literal -offset indent +struct HEADNAME head = LIST_HEAD_INITIALIZER(head); +.Ed +.Pp +The macro +.Fn LIST_FIRST +returns the first element of the list +.Fa head . +.Pp +The macro +.Fn LIST_EMPTY +returns true if the list +.Fa head +has no elements. +.Pp +The macro +.Fn LIST_NEXT +returns the element after the element +.Fa elm . +.Pp +The macro +.Fn LIST_FOREACH +traverses the list referenced by +.Fa head +in the forward direction, assigning each element in turn to +.Fa var . +.Pp +The SAFE version uses +.Fa tmp +to hold the next element, so +.Fa var +may be freed or removed from the list. +.Pp +The macro +.Fn LIST_INIT +initializes the list referenced by +.Fa head . +.Pp +The macro +.Fn LIST_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Fn LIST_INSERT_BEFORE +inserts the new element +.Fa elm +before the element +.Fa listelm . +.Pp +The macro +.Fn LIST_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the list. +.Pp +The macro +.Fn LIST_REMOVE +removes the element +.Fa elm +from the list. +.Pp +The macro +.Fn LIST_REPLACE +replaces the element +.Fa elm +with +.Fa new +in the list. +.Pp +The macro +.Fn LIST_MOVE +moves the list headed by +.Fa head1 +onto the list headed by +.Fa head2 , +always making the former empty. +.Sh LIST EXAMPLE +.Bd -literal +LIST_HEAD(listhead, entry) head; +struct listhead *headp; /* List head. */ +struct entry { + ... + LIST_ENTRY(entry) entries; /* List. */ + ... +} *n1, *n2, *np; + +LIST_INIT(&head); /* Initialize the list. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +LIST_INSERT_HEAD(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +LIST_INSERT_AFTER(n1, n2, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert before. */ +LIST_INSERT_BEFORE(n1, n2, entries); + +LIST_FOREACH(np, &head, entries) /* Forward traversal. */ + np-> ... + +while (LIST_FIRST(&head) != NULL) /* Delete. */ + LIST_REMOVE(LIST_FIRST(&head), entries); +if (LIST_EMPTY(&head)) /* Test for emptiness. */ + printf("nothing to do\\n"); +.Ed +.Sh SIMPLE QUEUES +A simple queue is headed by a structure defined by the +.Fn SIMPLEQ_HEAD +macro. +This structure contains a pair of pointers, +one to the first element in the simple queue and the other to +the last element in the simple 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 queue after an existing element, +at the head of the queue, or at the end of the queue. +A +.Fa SIMPLEQ_HEAD +structure is declared as follows: +.Bd -literal -offset indent +SIMPLEQ_HEAD(HEADNAME, TYPE) head; +.Ed +.Pp +where +.Li HEADNAME +is the name of the structure to be defined, and +.Li TYPE +is the type of the elements to be linked into the simple queue. +A pointer to the head of the simple queue can later be declared as: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The macro +.Fn SIMPLEQ_ENTRY +declares a structure that connects the elements in +the simple queue. +.Pp +The macro +.Fn SIMPLEQ_HEAD_INITIALIZER +provides a value which can be used to initialize a simple queue head at +compile time, and is used at the point that the simple queue head +variable is declared, like: +.Bd -literal -offset indent +struct HEADNAME head = SIMPLEQ_HEAD_INITIALIZER(head); +.Ed +.Pp +The macro +.Fn SIMPLEQ_FIRST +returns the first element of the simple queue +.Fa head . +.Pp +The macro +.Fn SIMPLEQ_EMPTY +returns true if the simple queue +.Fa head +has no elements. +.Pp +The macro +.Fn SIMPLEQ_NEXT +returns the element after the element +.Fa elm . +.Pp +The macro +.Fn SIMPLEQ_LAST +returns the last item on the simple queue. +If the simple queue is empty the return value is +.Dv NULL . +.Pp +The macro +.Fn SIMPLEQ_FOREACH +traverses the simple queue referenced by +.Fa head +in the forward direction, assigning each element +in turn to +.Fa var . +.Pp +The SAFE version uses +.Fa tmp +to hold the next element, so +.Fa var +may be freed or removed from the list. +.Pp +The macro +.Fn SIMPLEQ_INIT +initializes the simple queue referenced by +.Fa head . +.Pp +The macro +.Fn SIMPLEQ_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the simple queue. +.Pp +The macro +.Fn SIMPLEQ_INSERT_TAIL +inserts the new element +.Fa elm +at the end of the simple queue. +.Pp +The macro +.Fn SIMPLEQ_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Fn SIMPLEQ_REMOVE_HEAD +removes the first element from the head of the simple queue. +For optimum efficiency, +elements being removed from the head of the queue should explicitly use +this macro instead of the generic +.Fn SIMPLEQ_REMOVE +macro. +.Pp +The macro +.Fn SIMPLEQ_REMOVE_AFTER +removes the element after the one specified from the simple queue. +For optimum efficiency, +elements being removed after specified elements should explicitly use +this macro instead of the generic +.Fn SIMPLEQ_REMOVE +macro. +.Pp +The macro +.Fn SIMPLEQ_REMOVE +removes +.Fa elm +from the simple queue. +.Pp +The macro +.Fn SIMPLEQ_CONCAT +concatenates the simple queue headed by +.Fa head2 +onto the end of the one headed by +.Fa head1 , +removing all entries from the former. +.Sh SIMPLE QUEUE EXAMPLE +.Bd -literal +SIMPLEQ_HEAD(simplehead, entry) head; +struct simplehead *headp; /* Simple queue head. */ +struct entry { + ... + SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */ + ... +} *n1, *n2, *np; + +SIMPLEQ_INIT(&head); /* Initialize the queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +SIMPLEQ_INSERT_HEAD(&head, n1, entries); + +n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +SIMPLEQ_INSERT_TAIL(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries); + +SIMPLEQ_FOREACH(np, &head, entries) /* Forward traversal. */ + np-> ... + +while (SIMPLEQ_FIRST(&head) != NULL) /* Delete. */ + SIMPLEQ_REMOVE_HEAD(&head, entries); +if (SIMPLEQ_EMPTY(&head)) /* Test for emptiness. */ + printf("nothing to do\\n"); +.Ed +.Sh TAIL QUEUES +A tail queue is headed by a structure defined by the +.Fn TAILQ_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 doubly linked so that an arbitrary element can be +removed without traversing the tail queue. +New elements can be added to the queue after an existing element, +before an existing element, at the head of the queue, or at the end +the queue. +A +.Fa TAILQ_HEAD +structure is declared as follows: +.Bd -literal -offset indent +TAILQ_HEAD(HEADNAME, TYPE) head; +.Ed +.Pp +where +.Li HEADNAME +is the name of the structure to be defined, and +.Li 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: +.Bd -literal -offset indent +struct HEADNAME *headp; +.Ed +.Pp +(The names +.Li head +and +.Li headp +are user selectable.) +.Pp +The macro +.Fn TAILQ_ENTRY +declares a structure that connects the elements in +the tail queue. +.Pp +The macro +.Fn TAILQ_HEAD_INITIALIZER +provides a value which can be used to initialize a tail queue head at +compile time, and is used at the point that the tail queue head +variable is declared, like: +.Bd -literal -offset indent +struct HEADNAME head = TAILQ_HEAD_INITIALIZER(head); +.Ed +.Pp +The macro +.Fn TAILQ_FIRST +returns the first element of the tail queue +.Fa head . +.Pp +The macro +.Fn TAILQ_NEXT +returns the element after the element +.Fa elm . +.Pp +The macro +.Fn TAILQ_LAST +returns the last item on the tail queue. +If the tail queue is empty the return value is +.Dv NULL . +.Pp +The macro +.Fn TAILQ_PREV +returns the previous item on the tail queue, from the one specified. +If the tail queue is empty the return value is +.Dv NULL . +.Pp +The macro +.Fn TAILQ_EMPTY +returns true if the tail queue +.Fa head +has no elements. +.Pp +The macros +.Fn TAILQ_FOREACH , +.Fn TAILQ_FOREACH_REVERSE , +.Fn TAILQ_FOREACH_SAFE , +and +.Fn TAILQ_FOREACH_REVERSE_SAFE +traverse the tail queue referenced by +.Fa head +in the forward or reverse direction, assigning each element in turn to +.Fa var . +.Pp +The SAFE versions use +.Fa tmp +to hold the next element, so +.Fa var +may be freed or removed from the list. +.Pp +The macro +.Fn TAILQ_INIT +initializes the tail queue referenced by +.Fa head . +.Pp +The macro +.Fn TAILQ_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the tail queue. +.Pp +The macro +.Fn TAILQ_INSERT_TAIL +inserts the new element +.Fa elm +at the end of the tail queue. +.Pp +The macro +.Fn TAILQ_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Fn TAILQ_INSERT_BEFORE +inserts the new element +.Fa elm +before the element +.Fa listelm . +.Pp +The macro +.Fn TAILQ_REMOVE +removes the element +.Fa elm +from the tail queue. +.Pp +The macro +.Fn TAILQ_REPLACE +replaces the element +.Fa elm +with the +.Fa new +one specified in the tail queue. +.Pp +The macro +.Fn TAILQ_CONCAT +concatenates the tail queue headed by +.Fa head2 +onto the end of the one headed by +.Fa head1 , +removing all entries from the former. +.Sh TAIL QUEUE EXAMPLE +.Bd -literal +TAILQ_HEAD(tailhead, entry) head; +struct tailhead *headp; /* Tail queue head. */ +struct entry { + ... + TAILQ_ENTRY(entry) entries; /* Tail queue. */ + ... +} *n1, *n2, *np; + +TAILQ_INIT(&head); /* Initialize the queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +TAILQ_INSERT_HEAD(&head, n1, entries); + +n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +TAILQ_INSERT_TAIL(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +TAILQ_INSERT_AFTER(&head, n1, n2, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert before. */ +TAILQ_INSERT_BEFORE(n1, n2, entries); + +TAILQ_FOREACH(np, &head, entries) /* Forward traversal. */ + np-> ... + /* Reverse traversal. */ +TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) + np-> ... + +while (TAILQ_FIRST(&head) != NULL) /* Delete. */ + TAILQ_REMOVE(&head, TAILQ_FIRST(&head), entries); +if (TAILQ_EMPTY(&head)) /* Test for emptiness. */ + printf("nothing to do\\n"); +.Ed +.Sh SINGLY LINKED TAIL QUEUES +The macros prefixed with +.Do Nm STAILQ_ Dc ( +.Fn STAILQ_HEAD , +.Fn STAILQ_HEAD_INITIALIZER , +.Fn STAILQ_ENTRY , +.Fn STAILQ_FOREACH , +.Fn STAILQ_FOREACH_SAFE , +.Fn STAILQ_FIRST , +.Fn STAILQ_EMPTY , +.Fn STAILQ_NEXT , +.Fn STAILQ_LAST , +.Fn STAILQ_INIT , +.Fn STAILQ_INSERT_HEAD , +.Fn STAILQ_INSERT_TAIL , +.Fn STAILQ_INSERT_AFTER , +.Fn STAILQ_REMOVE_HEAD , +.Fn STAILQ_REMOVE , +and +.Fn STAILQ_CONCAT ) +are functionally identical to these simple queue functions, +and are provided for compatibility with +.Fx . +.Sh NOTES +Some of these macros or functions perform no error checking, +and invalid usage leads to undefined behaviour. +In the case of macros or functions that expect their arguments +to be elements that are present in the list or queue, passing an element +that is not present is invalid. +.Sh HISTORY +The +.Nm queue +functions first appeared in +.Bx 4.4 . +The +.Nm SIMPLEQ +functions first appeared in +.Nx 1.2 . +The +.Nm SLIST +and +.Nm STAILQ +functions first appeared in +.Fx 2.1.5 . +.Pp +The +.Nm CIRCLEQ +functions first appeared in +.Bx 4.4 +and were deprecated in +.Nx 7 +and removed in +.Nx 10 +due to the pointer aliasing violations. |