| .\" 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 4BSD |
| .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 . |