diff options
Diffstat (limited to 'man3/queue.3')
| -rw-r--r-- | man3/queue.3 | 456 |
1 files changed, 456 insertions, 0 deletions
diff --git a/man3/queue.3 b/man3/queue.3 new file mode 100644 index 000000000..755e70940 --- /dev/null +++ b/man3/queue.3 @@ -0,0 +1,456 @@ +.\" 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. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed by the University of +.\" California, Berkeley and its contributors. +.\" 4. 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.2 (Berkeley) 1/24/94 +.\" +.\" hch, 2002-03-25 +.Dd January 24, 1994 +.Dt QUEUE 3 +.Os BSD 4 +.Sh NAME +.Nm LIST_ENTRY , +.Nm LIST_HEAD , +.Nm LIST_INIT , +.Nm LIST_INSERT_AFTER , +.Nm LIST_INSERT_HEAD , +.Nm LIST_REMOVE , +.Nm TAILQ_ENTRY , +.Nm TAILQ_HEAD , +.Nm TAILQ_INIT , +.Nm TAILQ_INSERT_AFTER , +.Nm TAILQ_INSERT_HEAD , +.Nm TAILQ_INSERT_TAIL , +.Nm TAILQ_REMOVE , +.Nm CIRCLEQ_ENTRY , +.Nm CIRCLEQ_HEAD , +.Nm CIRCLEQ_INIT , +.Nm CIRCLEQ_INSERT_AFTER , +.Nm CIRCLEQ_INSERT_BEFORE , +.Nm CIRCLEQ_INSERT_HEAD , +.Nm CIRCLEQ_INSERT_TAIL , +.Nm CIRCLEQ_REMOVE +.Nd implementations of lists, tail queues, and circular queues +.Sh SYNOPSIS +.Fd #include <sys/queue.h> +.\" +.Fn LIST_ENTRY "TYPE" +.Fn LIST_HEAD "HEADNAME" "TYPE" +.Fn LIST_INIT "LIST_HEAD *head" +.Fn LIST_INSERT_AFTER "LIST_ENTRY *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 TAILQ_ENTRY "TYPE" +.Fn TAILQ_HEAD "HEADNAME" "TYPE" +.Fn TAILQ_INIT "TAILQ_HEAD *head" +.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" +.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_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" +.\" +.Fn CIRCLEQ_ENTRY "TYPE" +.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE" +.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head" +.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" +.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME" +.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" +.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" +.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME" +.Sh DESCRIPTION +These macros define and operate on three types of data structures: +lists, tail queues, and circular queues. +All three 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 +Lists are the simplest of the three data structures and support +only the above functionality. +.Pp +Tail queues add the following functionality: +.Bl -enum -compact -offset indent +.It +Entries can be added at the end of a list. +.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 +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 +Entries can be added before another entry. +.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 LIST_ENTRY , +.Li TAILQ_ENTRY , +or +.Li CIRCLEQ_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 TAILQ_HEAD , +or +.Li CIRCLEQ_HEAD . +See the examples below for further explanation of how these +macros are used. +.Sh LISTS +A list is headed by a structure defined by the +.Nm 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 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 +.Nm LIST_ENTRY +declares a structure that connects the elements in +the list. +.Pp +The macro +.Nm LIST_INIT +initializes the list referenced by +.Fa head . +.Pp +The macro +.Nm LIST_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the list. +.Pp +The macro +.Nm LIST_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Nm LIST_REMOVE +removes the element +.Fa elm +from the list. +.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); + /* Forward traversal. */ +for (np = head.lh_first; np != NULL; np = np->entries.le_next) + np-> ... + +while (head.lh_first != NULL) /* Delete. */ + LIST_REMOVE(head.lh_first, entries); +.Ed +.Sh TAIL QUEUES +A tail queue is headed by a structure defined by the +.Nm 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 tail queue after an existing element, +at the head of the tail queue, or at the end of the tail 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 +.Nm TAILQ_ENTRY +declares a structure that connects the elements in +the tail queue. +.Pp +The macro +.Nm TAILQ_INIT +initializes the tail queue referenced by +.Fa head . +.Pp +The macro +.Nm TAILQ_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the tail queue. +.Pp +The macro +.Nm TAILQ_INSERT_TAIL +inserts the new element +.Fa elm +at the end of the tail queue. +.Pp +The macro +.Nm TAILQ_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Nm TAILQ_REMOVE +removes the element +.Fa elm +from the tail queue. +.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); + /* Forward traversal. */ +for (np = head.tqh_first; np != NULL; np = np->entries.tqe_next) + np-> ... + /* Delete. */ +while (head.tqh_first != NULL) + TAILQ_REMOVE(&head, head.tqh_first, entries); +.Ed +.Sh CIRCULAR QUEUES +A circular queue is headed by a structure defined by the +.Nm CIRCLEQ_HEAD +macro. +This structure contains a pair of pointers, +one to the first element in the circular queue and the other to the +last element in the circular queue. +The elements are doubly linked so that an arbitrary element can be +removed without traversing the 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 +of the queue. +A +.Fa CIRCLEQ_HEAD +structure is declared as follows: +.Bd -literal -offset indent +CIRCLEQ_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 circular queue. +A pointer to the head of the circular 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 +.Nm CIRCLEQ_ENTRY +declares a structure that connects the elements in +the circular queue. +.Pp +The macro +.Nm CIRCLEQ_INIT +initializes the circular queue referenced by +.Fa head . +.Pp +The macro +.Nm CIRCLEQ_INSERT_HEAD +inserts the new element +.Fa elm +at the head of the circular queue. +.Pp +The macro +.Nm CIRCLEQ_INSERT_TAIL +inserts the new element +.Fa elm +at the end of the circular queue. +.Pp +The macro +.Nm CIRCLEQ_INSERT_AFTER +inserts the new element +.Fa elm +after the element +.Fa listelm . +.Pp +The macro +.Nm CIRCLEQ_INSERT_BEFORE +inserts the new element +.Fa elm +before the element +.Fa listelm . +.Pp +The macro +.Nm CIRCLEQ_REMOVE +removes the element +.Fa elm +from the circular queue. +.Sh CIRCULAR QUEUE EXAMPLE +.Bd -literal +CIRCLEQ_HEAD(circleq, entry) head; +struct circleq *headp; /* Circular queue head. */ +struct entry { + ... + CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */ + ... +} *n1, *n2, *np; + +CIRCLEQ_INIT(&head); /* Initialize the circular queue. */ + +n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ +CIRCLEQ_INSERT_HEAD(&head, n1, entries); + +n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ +CIRCLEQ_INSERT_TAIL(&head, n1, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert after. */ +CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries); + +n2 = malloc(sizeof(struct entry)); /* Insert before. */ +CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); + /* Forward traversal. */ +for (np = head.cqh_first; np != (void *)&head; np = np->entries.cqe_next) + np-> ... + /* Reverse traversal. */ +for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev) + np-> ... + /* Delete. */ +while (head.cqh_first != (void *)&head) + CIRCLEQ_REMOVE(&head, head.cqh_first, entries); +.Ed +.Sh HISTORY +The +.Nm queue +functions first appeared in +.Bx 4.4 . |