xref: /freebsd/share/man/man3/queue.3 (revision dda5b39711dab90ae1c5624bdd6ff7453177df31)
1afe61c15SRodney W. Grimes.\" Copyright (c) 1993
2afe61c15SRodney W. Grimes.\"	The Regents of the University of California.  All rights reserved.
3afe61c15SRodney W. Grimes.\"
4afe61c15SRodney W. Grimes.\" Redistribution and use in source and binary forms, with or without
5afe61c15SRodney W. Grimes.\" modification, are permitted provided that the following conditions
6afe61c15SRodney W. Grimes.\" are met:
7afe61c15SRodney W. Grimes.\" 1. Redistributions of source code must retain the above copyright
8afe61c15SRodney W. Grimes.\"    notice, this list of conditions and the following disclaimer.
9afe61c15SRodney W. Grimes.\" 2. Redistributions in binary form must reproduce the above copyright
10afe61c15SRodney W. Grimes.\"    notice, this list of conditions and the following disclaimer in the
11afe61c15SRodney W. Grimes.\"    documentation and/or other materials provided with the distribution.
12*dda5b397SEitan Adler.\" 3. Neither the name of the University nor the names of its contributors
13afe61c15SRodney W. Grimes.\"    may be used to endorse or promote products derived from this software
14afe61c15SRodney W. Grimes.\"    without specific prior written permission.
15afe61c15SRodney W. Grimes.\"
16afe61c15SRodney W. Grimes.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
17afe61c15SRodney W. Grimes.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18afe61c15SRodney W. Grimes.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19afe61c15SRodney W. Grimes.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
20afe61c15SRodney W. Grimes.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21afe61c15SRodney W. Grimes.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22afe61c15SRodney W. Grimes.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23afe61c15SRodney W. Grimes.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24afe61c15SRodney W. Grimes.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25afe61c15SRodney W. Grimes.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26afe61c15SRodney W. Grimes.\" SUCH DAMAGE.
27afe61c15SRodney W. Grimes.\"
28afe61c15SRodney W. Grimes.\"	@(#)queue.3	8.2 (Berkeley) 1/24/94
297f3dea24SPeter Wemm.\" $FreeBSD$
30afe61c15SRodney W. Grimes.\"
317ecb4019SLawrence Stewart.Dd June 17, 2013
32afe61c15SRodney W. Grimes.Dt QUEUE 3
333d45e180SRuslan Ermilov.Os
34afe61c15SRodney W. Grimes.Sh NAME
35aea88892SPoul-Henning Kamp.Nm SLIST_EMPTY ,
364a775e8fSJustin T. Gibbs.Nm SLIST_ENTRY ,
37aea88892SPoul-Henning Kamp.Nm SLIST_FIRST ,
3879ea9bc4SAlexey Zelkin.Nm SLIST_FOREACH ,
397ecb4019SLawrence Stewart.Nm SLIST_FOREACH_FROM ,
402724bce2SAlexander Kabaev.Nm SLIST_FOREACH_SAFE ,
417ecb4019SLawrence Stewart.Nm SLIST_FOREACH_FROM_SAFE ,
424a775e8fSJustin T. Gibbs.Nm SLIST_HEAD ,
4303763fe0SJake Burkholder.Nm SLIST_HEAD_INITIALIZER ,
444a775e8fSJustin T. Gibbs.Nm SLIST_INIT ,
454a775e8fSJustin T. Gibbs.Nm SLIST_INSERT_AFTER ,
464a775e8fSJustin T. Gibbs.Nm SLIST_INSERT_HEAD ,
47aea88892SPoul-Henning Kamp.Nm SLIST_NEXT ,
483d98b75bSEd Schouten.Nm SLIST_REMOVE_AFTER ,
494a775e8fSJustin T. Gibbs.Nm SLIST_REMOVE_HEAD ,
504a775e8fSJustin T. Gibbs.Nm SLIST_REMOVE ,
51359295cdSMatthew D Fleming.Nm SLIST_SWAP ,
52d57e28adSThomas Moestl.Nm STAILQ_CONCAT ,
5379ea9bc4SAlexey Zelkin.Nm STAILQ_EMPTY ,
544a775e8fSJustin T. Gibbs.Nm STAILQ_ENTRY ,
5579ea9bc4SAlexey Zelkin.Nm STAILQ_FIRST ,
5679ea9bc4SAlexey Zelkin.Nm STAILQ_FOREACH ,
577ecb4019SLawrence Stewart.Nm STAILQ_FOREACH_FROM ,
582724bce2SAlexander Kabaev.Nm STAILQ_FOREACH_SAFE ,
597ecb4019SLawrence Stewart.Nm STAILQ_FOREACH_FROM_SAFE ,
604a775e8fSJustin T. Gibbs.Nm STAILQ_HEAD ,
6103763fe0SJake Burkholder.Nm STAILQ_HEAD_INITIALIZER ,
624a775e8fSJustin T. Gibbs.Nm STAILQ_INIT ,
634a775e8fSJustin T. Gibbs.Nm STAILQ_INSERT_AFTER ,
644a775e8fSJustin T. Gibbs.Nm STAILQ_INSERT_HEAD ,
654a775e8fSJustin T. Gibbs.Nm STAILQ_INSERT_TAIL ,
6679ea9bc4SAlexey Zelkin.Nm STAILQ_LAST ,
6779ea9bc4SAlexey Zelkin.Nm STAILQ_NEXT ,
683d98b75bSEd Schouten.Nm STAILQ_REMOVE_AFTER ,
694a775e8fSJustin T. Gibbs.Nm STAILQ_REMOVE_HEAD ,
704a775e8fSJustin T. Gibbs.Nm STAILQ_REMOVE ,
71359295cdSMatthew D Fleming.Nm STAILQ_SWAP ,
7279ea9bc4SAlexey Zelkin.Nm LIST_EMPTY ,
73afe61c15SRodney W. Grimes.Nm LIST_ENTRY ,
7479ea9bc4SAlexey Zelkin.Nm LIST_FIRST ,
7579ea9bc4SAlexey Zelkin.Nm LIST_FOREACH ,
767ecb4019SLawrence Stewart.Nm LIST_FOREACH_FROM ,
774250a68eSBosko Milekic.Nm LIST_FOREACH_SAFE ,
787ecb4019SLawrence Stewart.Nm LIST_FOREACH_FROM_SAFE ,
79afe61c15SRodney W. Grimes.Nm LIST_HEAD ,
8003763fe0SJake Burkholder.Nm LIST_HEAD_INITIALIZER ,
81afe61c15SRodney W. Grimes.Nm LIST_INIT ,
82afe61c15SRodney W. Grimes.Nm LIST_INSERT_AFTER ,
837658b0a2SJustin T. Gibbs.Nm LIST_INSERT_BEFORE ,
84afe61c15SRodney W. Grimes.Nm LIST_INSERT_HEAD ,
8579ea9bc4SAlexey Zelkin.Nm LIST_NEXT ,
864170b083SEd Schouten.Nm LIST_PREV ,
87afe61c15SRodney W. Grimes.Nm LIST_REMOVE ,
88359295cdSMatthew D Fleming.Nm LIST_SWAP ,
89d57e28adSThomas Moestl.Nm TAILQ_CONCAT ,
90c5c15c16SPoul-Henning Kamp.Nm TAILQ_EMPTY ,
91afe61c15SRodney W. Grimes.Nm TAILQ_ENTRY ,
92c5c15c16SPoul-Henning Kamp.Nm TAILQ_FIRST ,
9379ea9bc4SAlexey Zelkin.Nm TAILQ_FOREACH ,
947ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_FROM ,
952724bce2SAlexander Kabaev.Nm TAILQ_FOREACH_SAFE ,
967ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_FROM_SAFE ,
976c1d0fbfSArchie Cobbs.Nm TAILQ_FOREACH_REVERSE ,
987ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_REVERSE_FROM ,
992724bce2SAlexander Kabaev.Nm TAILQ_FOREACH_REVERSE_SAFE ,
1007ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_REVERSE_FROM_SAFE ,
101afe61c15SRodney W. Grimes.Nm TAILQ_HEAD ,
10203763fe0SJake Burkholder.Nm TAILQ_HEAD_INITIALIZER ,
103afe61c15SRodney W. Grimes.Nm TAILQ_INIT ,
104afe61c15SRodney W. Grimes.Nm TAILQ_INSERT_AFTER ,
1057658b0a2SJustin T. Gibbs.Nm TAILQ_INSERT_BEFORE ,
106afe61c15SRodney W. Grimes.Nm TAILQ_INSERT_HEAD ,
107afe61c15SRodney W. Grimes.Nm TAILQ_INSERT_TAIL ,
108c5c15c16SPoul-Henning Kamp.Nm TAILQ_LAST ,
109c5c15c16SPoul-Henning Kamp.Nm TAILQ_NEXT ,
11079ea9bc4SAlexey Zelkin.Nm TAILQ_PREV ,
111359295cdSMatthew D Fleming.Nm TAILQ_REMOVE ,
112359295cdSMatthew D Fleming.Nm TAILQ_SWAP
1134a775e8fSJustin T. Gibbs.Nd implementations of singly-linked lists, singly-linked tail queues,
11424b85d18SPoul-Henning Kamplists and tail queues
115afe61c15SRodney W. Grimes.Sh SYNOPSIS
11632eef9aeSRuslan Ermilov.In sys/queue.h
1178f20a914SMike Pritchard.\"
118aea88892SPoul-Henning Kamp.Fn SLIST_EMPTY "SLIST_HEAD *head"
1194a775e8fSJustin T. Gibbs.Fn SLIST_ENTRY "TYPE"
120aea88892SPoul-Henning Kamp.Fn SLIST_FIRST "SLIST_HEAD *head"
12179ea9bc4SAlexey Zelkin.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
1227ecb4019SLawrence Stewart.Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
1232724bce2SAlexander Kabaev.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
1247ecb4019SLawrence Stewart.Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
1254a775e8fSJustin T. Gibbs.Fn SLIST_HEAD "HEADNAME" "TYPE"
12603763fe0SJake Burkholder.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
1274a775e8fSJustin T. Gibbs.Fn SLIST_INIT "SLIST_HEAD *head"
1284a775e8fSJustin T. Gibbs.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
1294a775e8fSJustin T. Gibbs.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
130aea88892SPoul-Henning Kamp.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
1313d98b75bSEd Schouten.Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
1324a775e8fSJustin T. Gibbs.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
1334a775e8fSJustin T. Gibbs.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
134359295cdSMatthew D Fleming.Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME"
1358f20a914SMike Pritchard.\"
136d57e28adSThomas Moestl.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
13779ea9bc4SAlexey Zelkin.Fn STAILQ_EMPTY "STAILQ_HEAD *head"
1384a775e8fSJustin T. Gibbs.Fn STAILQ_ENTRY "TYPE"
13979ea9bc4SAlexey Zelkin.Fn STAILQ_FIRST "STAILQ_HEAD *head"
14079ea9bc4SAlexey Zelkin.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
1417ecb4019SLawrence Stewart.Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
1422724bce2SAlexander Kabaev.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
1437ecb4019SLawrence Stewart.Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
1444a775e8fSJustin T. Gibbs.Fn STAILQ_HEAD "HEADNAME" "TYPE"
14503763fe0SJake Burkholder.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
1464a775e8fSJustin T. Gibbs.Fn STAILQ_INIT "STAILQ_HEAD *head"
1474a775e8fSJustin T. Gibbs.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
1484a775e8fSJustin T. Gibbs.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
1494a775e8fSJustin T. Gibbs.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
150f36b6e4bSMaxim Sobolev.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
15179ea9bc4SAlexey Zelkin.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
1523d98b75bSEd Schouten.Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
15302a98699SBruce Evans.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
1544a775e8fSJustin T. Gibbs.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
155359295cdSMatthew D Fleming.Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "STAILQ_ENTRY NAME"
1568f20a914SMike Pritchard.\"
15779ea9bc4SAlexey Zelkin.Fn LIST_EMPTY "LIST_HEAD *head"
158afe61c15SRodney W. Grimes.Fn LIST_ENTRY "TYPE"
15979ea9bc4SAlexey Zelkin.Fn LIST_FIRST "LIST_HEAD *head"
16079ea9bc4SAlexey Zelkin.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
1617ecb4019SLawrence Stewart.Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
1624250a68eSBosko Milekic.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
1637ecb4019SLawrence Stewart.Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
164afe61c15SRodney W. Grimes.Fn LIST_HEAD "HEADNAME" "TYPE"
16503763fe0SJake Burkholder.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
166afe61c15SRodney W. Grimes.Fn LIST_INIT "LIST_HEAD *head"
1674a775e8fSJustin T. Gibbs.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
1684a775e8fSJustin T. Gibbs.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
169afe61c15SRodney W. Grimes.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
17079ea9bc4SAlexey Zelkin.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
1714170b083SEd Schouten.Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME"
172afe61c15SRodney W. Grimes.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
173359295cdSMatthew D Fleming.Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
1748f20a914SMike Pritchard.\"
175d57e28adSThomas Moestl.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
176c5c15c16SPoul-Henning Kamp.Fn TAILQ_EMPTY "TAILQ_HEAD *head"
177afe61c15SRodney W. Grimes.Fn TAILQ_ENTRY "TYPE"
178c5c15c16SPoul-Henning Kamp.Fn TAILQ_FIRST "TAILQ_HEAD *head"
17979ea9bc4SAlexey Zelkin.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
1807ecb4019SLawrence Stewart.Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
1812724bce2SAlexander Kabaev.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
1827ecb4019SLawrence Stewart.Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
1836c1d0fbfSArchie Cobbs.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
1847ecb4019SLawrence Stewart.Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
1852724bce2SAlexander Kabaev.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
1867ecb4019SLawrence Stewart.Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
187afe61c15SRodney W. Grimes.Fn TAILQ_HEAD "HEADNAME" "TYPE"
18803763fe0SJake Burkholder.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
189afe61c15SRodney W. Grimes.Fn TAILQ_INIT "TAILQ_HEAD *head"
190afe61c15SRodney W. Grimes.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
1913652ff55SJustin T. Gibbs.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
192afe61c15SRodney W. Grimes.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
193afe61c15SRodney W. Grimes.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
19479ea9bc4SAlexey Zelkin.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
195c5c15c16SPoul-Henning Kamp.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
19679ea9bc4SAlexey Zelkin.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
197afe61c15SRodney W. Grimes.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
198359295cdSMatthew D Fleming.Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME"
1998f20a914SMike Pritchard.\"
200afe61c15SRodney W. Grimes.Sh DESCRIPTION
201b86388c1SDima DorfmanThese macros define and operate on four types of data structures:
202b86388c1SDima Dorfmansingly-linked lists, singly-linked tail queues, lists, and tail queues.
203b86388c1SDima DorfmanAll four structures support the following functionality:
204afe61c15SRodney W. Grimes.Bl -enum -compact -offset indent
205afe61c15SRodney W. Grimes.It
206afe61c15SRodney W. GrimesInsertion of a new entry at the head of the list.
207afe61c15SRodney W. Grimes.It
208afe61c15SRodney W. GrimesInsertion of a new entry after any element in the list.
209afe61c15SRodney W. Grimes.It
2104a775e8fSJustin T. GibbsO(1) removal of an entry from the head of the list.
2117658b0a2SJustin T. Gibbs.It
212afe61c15SRodney W. GrimesForward traversal through the list.
213359295cdSMatthew D Fleming.It
214f9257802SRalf S. EngelschallSwapping the contents of two lists.
215afe61c15SRodney W. Grimes.El
216afe61c15SRodney W. Grimes.Pp
217d5fd66e1SEd MasteSingly-linked lists are the simplest of the four data structures
2184a775e8fSJustin T. Gibbsand support only the above functionality.
2194a775e8fSJustin T. GibbsSingly-linked lists are ideal for applications with large datasets
2204a775e8fSJustin T. Gibbsand few or no removals,
2214a775e8fSJustin T. Gibbsor for implementing a LIFO queue.
222ed741d4eSDavid E. O'BrienSingly-linked lists add the following functionality:
223ed741d4eSDavid E. O'Brien.Bl -enum -compact -offset indent
224ed741d4eSDavid E. O'Brien.It
225ed741d4eSDavid E. O'BrienO(n) removal of any entry in the list.
226ed741d4eSDavid E. O'Brien.El
2274a775e8fSJustin T. Gibbs.Pp
2284a775e8fSJustin T. GibbsSingly-linked tail queues add the following functionality:
2294a775e8fSJustin T. Gibbs.Bl -enum -compact -offset indent
2304a775e8fSJustin T. Gibbs.It
2314a775e8fSJustin T. GibbsEntries can be added at the end of a list.
232d57e28adSThomas Moestl.It
233ed741d4eSDavid E. O'BrienO(n) removal of any entry in the list.
234ed741d4eSDavid E. O'Brien.It
235d57e28adSThomas MoestlThey may be concatenated.
2364a775e8fSJustin T. Gibbs.El
2374a775e8fSJustin T. GibbsHowever:
2384a775e8fSJustin T. Gibbs.Bl -enum -compact -offset indent
2394a775e8fSJustin T. Gibbs.It
2404a775e8fSJustin T. GibbsAll list insertions must specify the head of the list.
2414a775e8fSJustin T. Gibbs.It
2424a775e8fSJustin T. GibbsEach head entry requires two pointers rather than one.
2434a775e8fSJustin T. Gibbs.It
2444a775e8fSJustin T. GibbsCode size is about 15% greater and operations run about 20% slower
2454a775e8fSJustin T. Gibbsthan singly-linked lists.
2464a775e8fSJustin T. Gibbs.El
2474a775e8fSJustin T. Gibbs.Pp
248f9257802SRalf S. EngelschallSingly-linked tail queues are ideal for applications with large datasets and
2494a775e8fSJustin T. Gibbsfew or no removals,
2504a775e8fSJustin T. Gibbsor for implementing a FIFO queue.
2514a775e8fSJustin T. Gibbs.Pp
252b86388c1SDima DorfmanAll doubly linked types of data structures (lists and tail queues)
253b86388c1SDima Dorfmanadditionally allow:
2544a775e8fSJustin T. Gibbs.Bl -enum -compact -offset indent
2554a775e8fSJustin T. Gibbs.It
2564a775e8fSJustin T. GibbsInsertion of a new entry before any element in the list.
2574a775e8fSJustin T. Gibbs.It
2584a775e8fSJustin T. GibbsO(1) removal of any entry in the list.
2594a775e8fSJustin T. Gibbs.El
2604a775e8fSJustin T. GibbsHowever:
2614a775e8fSJustin T. Gibbs.Bl -enum -compact -offset indent
2624a775e8fSJustin T. Gibbs.It
263ad035dafSChristian BruefferEach element requires two pointers rather than one.
2644a775e8fSJustin T. Gibbs.It
2654a775e8fSJustin T. GibbsCode size and execution time of operations (except for removal) is about
2664a775e8fSJustin T. Gibbstwice that of the singly-linked data-structures.
2674a775e8fSJustin T. Gibbs.El
2684a775e8fSJustin T. Gibbs.Pp
2694170b083SEd SchoutenLinked lists are the simplest of the doubly linked data structures.
2704170b083SEd SchoutenThey add the following functionality over the above:
2714170b083SEd Schouten.Bl -enum -compact -offset indent
2724170b083SEd Schouten.It
2734170b083SEd SchoutenThey may be traversed backwards.
2744170b083SEd Schouten.El
2754170b083SEd SchoutenHowever:
2764170b083SEd Schouten.Bl -enum -compact -offset indent
2774170b083SEd Schouten.It
2784170b083SEd SchoutenTo traverse backwards, an entry to begin the traversal and the list in
2794170b083SEd Schoutenwhich it is contained must be specified.
2804170b083SEd Schouten.El
281afe61c15SRodney W. Grimes.Pp
282afe61c15SRodney W. GrimesTail queues add the following functionality:
283afe61c15SRodney W. Grimes.Bl -enum -compact -offset indent
284afe61c15SRodney W. Grimes.It
285afe61c15SRodney W. GrimesEntries can be added at the end of a list.
2866c1d0fbfSArchie Cobbs.It
2876c1d0fbfSArchie CobbsThey may be traversed backwards, from tail to head.
288d57e28adSThomas Moestl.It
289d57e28adSThomas MoestlThey may be concatenated.
290afe61c15SRodney W. Grimes.El
291afe61c15SRodney W. GrimesHowever:
292afe61c15SRodney W. Grimes.Bl -enum -compact -offset indent
293afe61c15SRodney W. Grimes.It
294afe61c15SRodney W. GrimesAll list insertions and removals must specify the head of the list.
295afe61c15SRodney W. Grimes.It
296afe61c15SRodney W. GrimesEach head entry requires two pointers rather than one.
297afe61c15SRodney W. Grimes.It
298afe61c15SRodney W. GrimesCode size is about 15% greater and operations run about 20% slower
2994a775e8fSJustin T. Gibbsthan singly-linked lists.
300afe61c15SRodney W. Grimes.El
301afe61c15SRodney W. Grimes.Pp
302afe61c15SRodney W. GrimesIn the macro definitions,
303afe61c15SRodney W. Grimes.Fa TYPE
304afe61c15SRodney W. Grimesis the name of a user defined structure,
305afe61c15SRodney W. Grimesthat must contain a field of type
3064a775e8fSJustin T. Gibbs.Li SLIST_ENTRY ,
3074a775e8fSJustin T. Gibbs.Li STAILQ_ENTRY ,
308afe61c15SRodney W. Grimes.Li LIST_ENTRY ,
309afe61c15SRodney W. Grimesor
31024b85d18SPoul-Henning Kamp.Li TAILQ_ENTRY ,
311afe61c15SRodney W. Grimesnamed
312afe61c15SRodney W. Grimes.Fa NAME .
313afe61c15SRodney W. GrimesThe argument
314afe61c15SRodney W. Grimes.Fa HEADNAME
315afe61c15SRodney W. Grimesis the name of a user defined structure that must be declared
316afe61c15SRodney W. Grimesusing the macros
3174a775e8fSJustin T. Gibbs.Li SLIST_HEAD ,
3184a775e8fSJustin T. Gibbs.Li STAILQ_HEAD ,
319afe61c15SRodney W. Grimes.Li LIST_HEAD ,
320afe61c15SRodney W. Grimesor
32124b85d18SPoul-Henning Kamp.Li TAILQ_HEAD .
322afe61c15SRodney W. GrimesSee the examples below for further explanation of how these
323afe61c15SRodney W. Grimesmacros are used.
3244a775e8fSJustin T. Gibbs.Sh SINGLY-LINKED LISTS
3254a775e8fSJustin T. GibbsA singly-linked list is headed by a structure defined by the
3264a775e8fSJustin T. Gibbs.Nm SLIST_HEAD
3274a775e8fSJustin T. Gibbsmacro.
3284a775e8fSJustin T. GibbsThis structure contains a single pointer to the first element
3294a775e8fSJustin T. Gibbson the list.
3304a775e8fSJustin T. GibbsThe elements are singly linked for minimum space and pointer manipulation
3314a775e8fSJustin T. Gibbsoverhead at the expense of O(n) removal for arbitrary elements.
3324a775e8fSJustin T. GibbsNew elements can be added to the list after an existing element or
3334a775e8fSJustin T. Gibbsat the head of the list.
3344a775e8fSJustin T. GibbsAn
3354a775e8fSJustin T. Gibbs.Fa SLIST_HEAD
3364a775e8fSJustin T. Gibbsstructure is declared as follows:
3374a775e8fSJustin T. Gibbs.Bd -literal -offset indent
3384a775e8fSJustin T. GibbsSLIST_HEAD(HEADNAME, TYPE) head;
3394a775e8fSJustin T. Gibbs.Ed
3408f20a914SMike Pritchard.Pp
3414a775e8fSJustin T. Gibbswhere
3424a775e8fSJustin T. Gibbs.Fa HEADNAME
3434a775e8fSJustin T. Gibbsis the name of the structure to be defined, and
3444a775e8fSJustin T. Gibbs.Fa TYPE
3454a775e8fSJustin T. Gibbsis the type of the elements to be linked into the list.
3464a775e8fSJustin T. GibbsA pointer to the head of the list can later be declared as:
3474a775e8fSJustin T. Gibbs.Bd -literal -offset indent
3484a775e8fSJustin T. Gibbsstruct HEADNAME *headp;
3494a775e8fSJustin T. Gibbs.Ed
3508f20a914SMike Pritchard.Pp
3514a775e8fSJustin T. Gibbs(The names
3524a775e8fSJustin T. Gibbs.Li head
3534a775e8fSJustin T. Gibbsand
3544a775e8fSJustin T. Gibbs.Li headp
3554a775e8fSJustin T. Gibbsare user selectable.)
3564a775e8fSJustin T. Gibbs.Pp
3574a775e8fSJustin T. GibbsThe macro
35803763fe0SJake Burkholder.Nm SLIST_HEAD_INITIALIZER
35903763fe0SJake Burkholderevaluates to an initializer for the list
36003763fe0SJake Burkholder.Fa head .
36103763fe0SJake Burkholder.Pp
36203763fe0SJake BurkholderThe macro
36379ea9bc4SAlexey Zelkin.Nm SLIST_EMPTY
36479ea9bc4SAlexey Zelkinevaluates to true if there are no elements in the list.
36579ea9bc4SAlexey Zelkin.Pp
36679ea9bc4SAlexey ZelkinThe macro
3674a775e8fSJustin T. Gibbs.Nm SLIST_ENTRY
3684a775e8fSJustin T. Gibbsdeclares a structure that connects the elements in
3694a775e8fSJustin T. Gibbsthe list.
3704a775e8fSJustin T. Gibbs.Pp
3714a775e8fSJustin T. GibbsThe macro
37279ea9bc4SAlexey Zelkin.Nm SLIST_FIRST
37379ea9bc4SAlexey Zelkinreturns the first element in the list or NULL if the list is empty.
37479ea9bc4SAlexey Zelkin.Pp
37579ea9bc4SAlexey ZelkinThe macro
37679ea9bc4SAlexey Zelkin.Nm SLIST_FOREACH
37779ea9bc4SAlexey Zelkintraverses the list referenced by
37879ea9bc4SAlexey Zelkin.Fa head
37979ea9bc4SAlexey Zelkinin the forward direction, assigning each element in
38079ea9bc4SAlexey Zelkinturn to
38179ea9bc4SAlexey Zelkin.Fa var .
38279ea9bc4SAlexey Zelkin.Pp
38379ea9bc4SAlexey ZelkinThe macro
3847ecb4019SLawrence Stewart.Nm SLIST_FOREACH_FROM
3857ecb4019SLawrence Stewartbehaves identically to
3867ecb4019SLawrence Stewart.Nm SLIST_FOREACH
3877ecb4019SLawrence Stewartwhen
3887ecb4019SLawrence Stewart.Fa var
3897ecb4019SLawrence Stewartis NULL, else it treats
3907ecb4019SLawrence Stewart.Fa var
3917ecb4019SLawrence Stewartas a previously found SLIST element and begins the loop at
3927ecb4019SLawrence Stewart.Fa var
3937ecb4019SLawrence Stewartinstead of the first element in the SLIST referenced by
3947ecb4019SLawrence Stewart.Fa head .
3957ecb4019SLawrence Stewart.Pp
3967ecb4019SLawrence StewartThe macro
3972724bce2SAlexander Kabaev.Nm SLIST_FOREACH_SAFE
3982724bce2SAlexander Kabaevtraverses the list referenced by
3992724bce2SAlexander Kabaev.Fa head
4002724bce2SAlexander Kabaevin the forward direction, assigning each element in
4012724bce2SAlexander Kabaevturn to
4022724bce2SAlexander Kabaev.Fa var .
4032724bce2SAlexander KabaevHowever, unlike
4042724bce2SAlexander Kabaev.Fn SLIST_FOREACH
4052724bce2SAlexander Kabaevhere it is permitted to both remove
4062724bce2SAlexander Kabaev.Fa var
4072724bce2SAlexander Kabaevas well as free it from within the loop safely without interfering with the
4082724bce2SAlexander Kabaevtraversal.
4092724bce2SAlexander Kabaev.Pp
4102724bce2SAlexander KabaevThe macro
4117ecb4019SLawrence Stewart.Nm SLIST_FOREACH_FROM_SAFE
4127ecb4019SLawrence Stewartbehaves identically to
4137ecb4019SLawrence Stewart.Nm SLIST_FOREACH_SAFE
4147ecb4019SLawrence Stewartwhen
4157ecb4019SLawrence Stewart.Fa var
4167ecb4019SLawrence Stewartis NULL, else it treats
4177ecb4019SLawrence Stewart.Fa var
4187ecb4019SLawrence Stewartas a previously found SLIST element and begins the loop at
4197ecb4019SLawrence Stewart.Fa var
4207ecb4019SLawrence Stewartinstead of the first element in the SLIST referenced by
4217ecb4019SLawrence Stewart.Fa head .
4227ecb4019SLawrence Stewart.Pp
4237ecb4019SLawrence StewartThe macro
4244a775e8fSJustin T. Gibbs.Nm SLIST_INIT
4254a775e8fSJustin T. Gibbsinitializes the list referenced by
4264a775e8fSJustin T. Gibbs.Fa head .
4274a775e8fSJustin T. Gibbs.Pp
4284a775e8fSJustin T. GibbsThe macro
4294a775e8fSJustin T. Gibbs.Nm SLIST_INSERT_HEAD
4304a775e8fSJustin T. Gibbsinserts the new element
4314a775e8fSJustin T. Gibbs.Fa elm
4324a775e8fSJustin T. Gibbsat the head of the list.
4334a775e8fSJustin T. Gibbs.Pp
4344a775e8fSJustin T. GibbsThe macro
4354a775e8fSJustin T. Gibbs.Nm SLIST_INSERT_AFTER
4364a775e8fSJustin T. Gibbsinserts the new element
4374a775e8fSJustin T. Gibbs.Fa elm
4384a775e8fSJustin T. Gibbsafter the element
4394a775e8fSJustin T. Gibbs.Fa listelm .
4404a775e8fSJustin T. Gibbs.Pp
4414a775e8fSJustin T. GibbsThe macro
44279ea9bc4SAlexey Zelkin.Nm SLIST_NEXT
44379ea9bc4SAlexey Zelkinreturns the next element in the list.
44479ea9bc4SAlexey Zelkin.Pp
44579ea9bc4SAlexey ZelkinThe macro
4463d98b75bSEd Schouten.Nm SLIST_REMOVE_AFTER
4473d98b75bSEd Schoutenremoves the element after
4483d98b75bSEd Schouten.Fa elm
449bc106255SEitan Adlerfrom the list.
450bc106255SEitan AdlerUnlike
4513d98b75bSEd Schouten.Fa SLIST_REMOVE ,
4523d98b75bSEd Schoutenthis macro does not traverse the entire list.
4533d98b75bSEd Schouten.Pp
4543d98b75bSEd SchoutenThe macro
4554a775e8fSJustin T. Gibbs.Nm SLIST_REMOVE_HEAD
4564a775e8fSJustin T. Gibbsremoves the element
4574a775e8fSJustin T. Gibbs.Fa elm
4584a775e8fSJustin T. Gibbsfrom the head of the list.
4594a775e8fSJustin T. GibbsFor optimum efficiency,
4604a775e8fSJustin T. Gibbselements being removed from the head of the list should explicitly use
4614a775e8fSJustin T. Gibbsthis macro instead of the generic
4624a775e8fSJustin T. Gibbs.Fa SLIST_REMOVE
4634a775e8fSJustin T. Gibbsmacro.
4644a775e8fSJustin T. Gibbs.Pp
4654a775e8fSJustin T. GibbsThe macro
4664a775e8fSJustin T. Gibbs.Nm SLIST_REMOVE
4674a775e8fSJustin T. Gibbsremoves the element
4684a775e8fSJustin T. Gibbs.Fa elm
4694a775e8fSJustin T. Gibbsfrom the list.
470359295cdSMatthew D Fleming.Pp
471359295cdSMatthew D FlemingThe macro
472359295cdSMatthew D Fleming.Nm SLIST_SWAP
473359295cdSMatthew D Flemingswaps the contents of
474359295cdSMatthew D Fleming.Fa head1
475359295cdSMatthew D Flemingand
476359295cdSMatthew D Fleming.Fa head2 .
4774a775e8fSJustin T. Gibbs.Sh SINGLY-LINKED LIST EXAMPLE
4784a775e8fSJustin T. Gibbs.Bd -literal
47903763fe0SJake BurkholderSLIST_HEAD(slisthead, entry) head =
48003763fe0SJake Burkholder    SLIST_HEAD_INITIALIZER(head);
4814a775e8fSJustin T. Gibbsstruct slisthead *headp;		/* Singly-linked List head. */
4824a775e8fSJustin T. Gibbsstruct entry {
4834a775e8fSJustin T. Gibbs	...
4844a775e8fSJustin T. Gibbs	SLIST_ENTRY(entry) entries;	/* Singly-linked List. */
4854a775e8fSJustin T. Gibbs	...
4864a775e8fSJustin T. Gibbs} *n1, *n2, *n3, *np;
4874a775e8fSJustin T. Gibbs
4884a775e8fSJustin T. GibbsSLIST_INIT(&head);			/* Initialize the list. */
4894a775e8fSJustin T. Gibbs
4904a775e8fSJustin T. Gibbsn1 = malloc(sizeof(struct entry));	/* Insert at the head. */
4914a775e8fSJustin T. GibbsSLIST_INSERT_HEAD(&head, n1, entries);
4924a775e8fSJustin T. Gibbs
4934a775e8fSJustin T. Gibbsn2 = malloc(sizeof(struct entry));	/* Insert after. */
4944a775e8fSJustin T. GibbsSLIST_INSERT_AFTER(n1, n2, entries);
4954a775e8fSJustin T. Gibbs
4964a775e8fSJustin T. GibbsSLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
4974a775e8fSJustin T. Gibbsfree(n2);
4984a775e8fSJustin T. Gibbs
49979ea9bc4SAlexey Zelkinn3 = SLIST_FIRST(&head);
50003763fe0SJake BurkholderSLIST_REMOVE_HEAD(&head, entries);	/* Deletion from the head. */
5014a775e8fSJustin T. Gibbsfree(n3);
5024a775e8fSJustin T. Gibbs					/* Forward traversal. */
50379ea9bc4SAlexey ZelkinSLIST_FOREACH(np, &head, entries)
5044a775e8fSJustin T. Gibbs	np-> ...
5052724bce2SAlexander Kabaev					/* Safe forward traversal. */
5062724bce2SAlexander KabaevSLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
5072724bce2SAlexander Kabaev	np->do_stuff();
5082724bce2SAlexander Kabaev	...
5092724bce2SAlexander Kabaev	SLIST_REMOVE(&head, np, entry, entries);
5102724bce2SAlexander Kabaev	free(np);
5112724bce2SAlexander Kabaev}
5124a775e8fSJustin T. Gibbs
51379ea9bc4SAlexey Zelkinwhile (!SLIST_EMPTY(&head)) {		/* List Deletion. */
51479ea9bc4SAlexey Zelkin	n1 = SLIST_FIRST(&head);
5154a775e8fSJustin T. Gibbs	SLIST_REMOVE_HEAD(&head, entries);
5164a775e8fSJustin T. Gibbs	free(n1);
5174a775e8fSJustin T. Gibbs}
5184a775e8fSJustin T. Gibbs.Ed
5194a775e8fSJustin T. Gibbs.Sh SINGLY-LINKED TAIL QUEUES
5204a775e8fSJustin T. GibbsA singly-linked tail queue is headed by a structure defined by the
5214a775e8fSJustin T. Gibbs.Nm STAILQ_HEAD
5224a775e8fSJustin T. Gibbsmacro.
5234a775e8fSJustin T. GibbsThis structure contains a pair of pointers,
5244a775e8fSJustin T. Gibbsone to the first element in the tail queue and the other to
5254a775e8fSJustin T. Gibbsthe last element in the tail queue.
5264a775e8fSJustin T. GibbsThe elements are singly linked for minimum space and pointer
5274a775e8fSJustin T. Gibbsmanipulation overhead at the expense of O(n) removal for arbitrary
5284a775e8fSJustin T. Gibbselements.
5294a775e8fSJustin T. GibbsNew elements can be added to the tail queue after an existing element,
5304a775e8fSJustin T. Gibbsat the head of the tail queue, or at the end of the tail queue.
5314a775e8fSJustin T. GibbsA
5324a775e8fSJustin T. Gibbs.Fa STAILQ_HEAD
5334a775e8fSJustin T. Gibbsstructure is declared as follows:
5344a775e8fSJustin T. Gibbs.Bd -literal -offset indent
5354a775e8fSJustin T. GibbsSTAILQ_HEAD(HEADNAME, TYPE) head;
5364a775e8fSJustin T. Gibbs.Ed
5378f20a914SMike Pritchard.Pp
5384a775e8fSJustin T. Gibbswhere
5394a775e8fSJustin T. Gibbs.Li HEADNAME
5404a775e8fSJustin T. Gibbsis the name of the structure to be defined, and
5414a775e8fSJustin T. Gibbs.Li TYPE
5424a775e8fSJustin T. Gibbsis the type of the elements to be linked into the tail queue.
5434a775e8fSJustin T. GibbsA pointer to the head of the tail queue can later be declared as:
5444a775e8fSJustin T. Gibbs.Bd -literal -offset indent
5454a775e8fSJustin T. Gibbsstruct HEADNAME *headp;
5464a775e8fSJustin T. Gibbs.Ed
5478f20a914SMike Pritchard.Pp
5484a775e8fSJustin T. Gibbs(The names
5494a775e8fSJustin T. Gibbs.Li head
5504a775e8fSJustin T. Gibbsand
5514a775e8fSJustin T. Gibbs.Li headp
5524a775e8fSJustin T. Gibbsare user selectable.)
5534a775e8fSJustin T. Gibbs.Pp
5544a775e8fSJustin T. GibbsThe macro
55503763fe0SJake Burkholder.Nm STAILQ_HEAD_INITIALIZER
55603763fe0SJake Burkholderevaluates to an initializer for the tail queue
55703763fe0SJake Burkholder.Fa head .
55803763fe0SJake Burkholder.Pp
55903763fe0SJake BurkholderThe macro
560d57e28adSThomas Moestl.Nm STAILQ_CONCAT
561d57e28adSThomas Moestlconcatenates the tail queue headed by
562d57e28adSThomas Moestl.Fa head2
563d57e28adSThomas Moestlonto the end of the one headed by
564d57e28adSThomas Moestl.Fa head1
565d57e28adSThomas Moestlremoving all entries from the former.
566d57e28adSThomas Moestl.Pp
567d57e28adSThomas MoestlThe macro
56879ea9bc4SAlexey Zelkin.Nm STAILQ_EMPTY
56979ea9bc4SAlexey Zelkinevaluates to true if there are no items on the tail queue.
57079ea9bc4SAlexey Zelkin.Pp
57179ea9bc4SAlexey ZelkinThe macro
5724a775e8fSJustin T. Gibbs.Nm STAILQ_ENTRY
5734a775e8fSJustin T. Gibbsdeclares a structure that connects the elements in
5744a775e8fSJustin T. Gibbsthe tail queue.
5754a775e8fSJustin T. Gibbs.Pp
5764a775e8fSJustin T. GibbsThe macro
57779ea9bc4SAlexey Zelkin.Nm STAILQ_FIRST
57879ea9bc4SAlexey Zelkinreturns the first item on the tail queue or NULL if the tail queue
57979ea9bc4SAlexey Zelkinis empty.
58079ea9bc4SAlexey Zelkin.Pp
58179ea9bc4SAlexey ZelkinThe macro
58279ea9bc4SAlexey Zelkin.Nm STAILQ_FOREACH
58379ea9bc4SAlexey Zelkintraverses the tail queue referenced by
58479ea9bc4SAlexey Zelkin.Fa head
58579ea9bc4SAlexey Zelkinin the forward direction, assigning each element
58679ea9bc4SAlexey Zelkinin turn to
58779ea9bc4SAlexey Zelkin.Fa var .
58879ea9bc4SAlexey Zelkin.Pp
58979ea9bc4SAlexey ZelkinThe macro
5907ecb4019SLawrence Stewart.Nm STAILQ_FOREACH_FROM
5917ecb4019SLawrence Stewartbehaves identically to
5927ecb4019SLawrence Stewart.Nm STAILQ_FOREACH
5937ecb4019SLawrence Stewartwhen
5947ecb4019SLawrence Stewart.Fa var
5957ecb4019SLawrence Stewartis NULL, else it treats
5967ecb4019SLawrence Stewart.Fa var
5977ecb4019SLawrence Stewartas a previously found STAILQ element and begins the loop at
5987ecb4019SLawrence Stewart.Fa var
5997ecb4019SLawrence Stewartinstead of the first element in the STAILQ referenced by
6007ecb4019SLawrence Stewart.Fa head .
6017ecb4019SLawrence Stewart.Pp
6027ecb4019SLawrence StewartThe macro
6032724bce2SAlexander Kabaev.Nm STAILQ_FOREACH_SAFE
6042724bce2SAlexander Kabaevtraverses the tail queue referenced by
6052724bce2SAlexander Kabaev.Fa head
6062724bce2SAlexander Kabaevin the forward direction, assigning each element
6072724bce2SAlexander Kabaevin turn to
6082724bce2SAlexander Kabaev.Fa var .
6092724bce2SAlexander KabaevHowever, unlike
6102724bce2SAlexander Kabaev.Fn STAILQ_FOREACH
6112724bce2SAlexander Kabaevhere it is permitted to both remove
6122724bce2SAlexander Kabaev.Fa var
6132724bce2SAlexander Kabaevas well as free it from within the loop safely without interfering with the
6142724bce2SAlexander Kabaevtraversal.
6152724bce2SAlexander Kabaev.Pp
6162724bce2SAlexander KabaevThe macro
6177ecb4019SLawrence Stewart.Nm STAILQ_FOREACH_FROM_SAFE
6187ecb4019SLawrence Stewartbehaves identically to
6197ecb4019SLawrence Stewart.Nm STAILQ_FOREACH_SAFE
6207ecb4019SLawrence Stewartwhen
6217ecb4019SLawrence Stewart.Fa var
6227ecb4019SLawrence Stewartis NULL, else it treats
6237ecb4019SLawrence Stewart.Fa var
6247ecb4019SLawrence Stewartas a previously found STAILQ element and begins the loop at
6257ecb4019SLawrence Stewart.Fa var
6267ecb4019SLawrence Stewartinstead of the first element in the STAILQ referenced by
6277ecb4019SLawrence Stewart.Fa head .
6287ecb4019SLawrence Stewart.Pp
6297ecb4019SLawrence StewartThe macro
6304a775e8fSJustin T. Gibbs.Nm STAILQ_INIT
6314a775e8fSJustin T. Gibbsinitializes the tail queue referenced by
6324a775e8fSJustin T. Gibbs.Fa head .
6334a775e8fSJustin T. Gibbs.Pp
6344a775e8fSJustin T. GibbsThe macro
6354a775e8fSJustin T. Gibbs.Nm STAILQ_INSERT_HEAD
6364a775e8fSJustin T. Gibbsinserts the new element
6374a775e8fSJustin T. Gibbs.Fa elm
6384a775e8fSJustin T. Gibbsat the head of the tail queue.
6394a775e8fSJustin T. Gibbs.Pp
6404a775e8fSJustin T. GibbsThe macro
6414a775e8fSJustin T. Gibbs.Nm STAILQ_INSERT_TAIL
6424a775e8fSJustin T. Gibbsinserts the new element
6434a775e8fSJustin T. Gibbs.Fa elm
6444a775e8fSJustin T. Gibbsat the end of the tail queue.
6454a775e8fSJustin T. Gibbs.Pp
6464a775e8fSJustin T. GibbsThe macro
6474a775e8fSJustin T. Gibbs.Nm STAILQ_INSERT_AFTER
6484a775e8fSJustin T. Gibbsinserts the new element
6494a775e8fSJustin T. Gibbs.Fa elm
6504a775e8fSJustin T. Gibbsafter the element
6514a775e8fSJustin T. Gibbs.Fa listelm .
6524a775e8fSJustin T. Gibbs.Pp
6534a775e8fSJustin T. GibbsThe macro
65479ea9bc4SAlexey Zelkin.Nm STAILQ_LAST
65579ea9bc4SAlexey Zelkinreturns the last item on the tail queue.
656982ba1cbSKirk McKusickIf the tail queue is empty the return value is
657982ba1cbSKirk McKusick.Dv NULL .
65879ea9bc4SAlexey Zelkin.Pp
65979ea9bc4SAlexey ZelkinThe macro
66079ea9bc4SAlexey Zelkin.Nm STAILQ_NEXT
66179ea9bc4SAlexey Zelkinreturns the next item on the tail queue, or NULL this item is the last.
66279ea9bc4SAlexey Zelkin.Pp
66379ea9bc4SAlexey ZelkinThe macro
6643d98b75bSEd Schouten.Nm STAILQ_REMOVE_AFTER
6653d98b75bSEd Schoutenremoves the element after
6663d98b75bSEd Schouten.Fa elm
667bc106255SEitan Adlerfrom the tail queue.
668bc106255SEitan AdlerUnlike
6693d98b75bSEd Schouten.Fa STAILQ_REMOVE ,
6703d98b75bSEd Schoutenthis macro does not traverse the entire tail queue.
6713d98b75bSEd Schouten.Pp
6723d98b75bSEd SchoutenThe macro
6734a775e8fSJustin T. Gibbs.Nm STAILQ_REMOVE_HEAD
674ce900f03SAlfred Perlsteinremoves the element at the head of the tail queue.
6754a775e8fSJustin T. GibbsFor optimum efficiency,
6764a775e8fSJustin T. Gibbselements being removed from the head of the tail queue should
6774a775e8fSJustin T. Gibbsuse this macro explicitly rather than the generic
6784a775e8fSJustin T. Gibbs.Fa STAILQ_REMOVE
6794a775e8fSJustin T. Gibbsmacro.
6804a775e8fSJustin T. Gibbs.Pp
6814a775e8fSJustin T. GibbsThe macro
6824a775e8fSJustin T. Gibbs.Nm STAILQ_REMOVE
6834a775e8fSJustin T. Gibbsremoves the element
6844a775e8fSJustin T. Gibbs.Fa elm
6854a775e8fSJustin T. Gibbsfrom the tail queue.
686359295cdSMatthew D Fleming.Pp
687359295cdSMatthew D FlemingThe macro
688359295cdSMatthew D Fleming.Nm STAILQ_SWAP
689359295cdSMatthew D Flemingswaps the contents of
690359295cdSMatthew D Fleming.Fa head1
691359295cdSMatthew D Flemingand
692359295cdSMatthew D Fleming.Fa head2 .
6934a775e8fSJustin T. Gibbs.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
6944a775e8fSJustin T. Gibbs.Bd -literal
69503763fe0SJake BurkholderSTAILQ_HEAD(stailhead, entry) head =
69603763fe0SJake Burkholder    STAILQ_HEAD_INITIALIZER(head);
6974a775e8fSJustin T. Gibbsstruct stailhead *headp;		/* Singly-linked tail queue head. */
6984a775e8fSJustin T. Gibbsstruct entry {
6994a775e8fSJustin T. Gibbs	...
7004a775e8fSJustin T. Gibbs	STAILQ_ENTRY(entry) entries;	/* Tail queue. */
7014a775e8fSJustin T. Gibbs	...
7024a775e8fSJustin T. Gibbs} *n1, *n2, *n3, *np;
7034a775e8fSJustin T. Gibbs
7044a775e8fSJustin T. GibbsSTAILQ_INIT(&head);			/* Initialize the queue. */
7054a775e8fSJustin T. Gibbs
7064a775e8fSJustin T. Gibbsn1 = malloc(sizeof(struct entry));	/* Insert at the head. */
7074a775e8fSJustin T. GibbsSTAILQ_INSERT_HEAD(&head, n1, entries);
7084a775e8fSJustin T. Gibbs
7094a775e8fSJustin T. Gibbsn1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
7104a775e8fSJustin T. GibbsSTAILQ_INSERT_TAIL(&head, n1, entries);
7114a775e8fSJustin T. Gibbs
7124a775e8fSJustin T. Gibbsn2 = malloc(sizeof(struct entry));	/* Insert after. */
7134a775e8fSJustin T. GibbsSTAILQ_INSERT_AFTER(&head, n1, n2, entries);
7144a775e8fSJustin T. Gibbs					/* Deletion. */
7154a775e8fSJustin T. GibbsSTAILQ_REMOVE(&head, n2, entry, entries);
7164a775e8fSJustin T. Gibbsfree(n2);
71703763fe0SJake Burkholder					/* Deletion from the head. */
71879ea9bc4SAlexey Zelkinn3 = STAILQ_FIRST(&head);
7194a775e8fSJustin T. GibbsSTAILQ_REMOVE_HEAD(&head, entries);
7204a775e8fSJustin T. Gibbsfree(n3);
7214a775e8fSJustin T. Gibbs					/* Forward traversal. */
72279ea9bc4SAlexey ZelkinSTAILQ_FOREACH(np, &head, entries)
7234a775e8fSJustin T. Gibbs	np-> ...
7242724bce2SAlexander Kabaev					/* Safe forward traversal. */
7252724bce2SAlexander KabaevSTAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
7262724bce2SAlexander Kabaev	np->do_stuff();
7272724bce2SAlexander Kabaev	...
7282724bce2SAlexander Kabaev	STAILQ_REMOVE(&head, np, entry, entries);
7292724bce2SAlexander Kabaev	free(np);
7302724bce2SAlexander Kabaev}
7314a775e8fSJustin T. Gibbs					/* TailQ Deletion. */
73279ea9bc4SAlexey Zelkinwhile (!STAILQ_EMPTY(&head)) {
73303763fe0SJake Burkholder	n1 = STAILQ_FIRST(&head);
734266e33fdSJohn Baldwin	STAILQ_REMOVE_HEAD(&head, entries);
7354a775e8fSJustin T. Gibbs	free(n1);
7364a775e8fSJustin T. Gibbs}
7374a775e8fSJustin T. Gibbs					/* Faster TailQ Deletion. */
73879ea9bc4SAlexey Zelkinn1 = STAILQ_FIRST(&head);
7394a775e8fSJustin T. Gibbswhile (n1 != NULL) {
74079ea9bc4SAlexey Zelkin	n2 = STAILQ_NEXT(n1, entries);
7414a775e8fSJustin T. Gibbs	free(n1);
7424a775e8fSJustin T. Gibbs	n1 = n2;
7434a775e8fSJustin T. Gibbs}
7444a775e8fSJustin T. GibbsSTAILQ_INIT(&head);
7454a775e8fSJustin T. Gibbs.Ed
746afe61c15SRodney W. Grimes.Sh LISTS
747afe61c15SRodney W. GrimesA list is headed by a structure defined by the
748afe61c15SRodney W. Grimes.Nm LIST_HEAD
749afe61c15SRodney W. Grimesmacro.
750afe61c15SRodney W. GrimesThis structure contains a single pointer to the first element
751afe61c15SRodney W. Grimeson the list.
752afe61c15SRodney W. GrimesThe elements are doubly linked so that an arbitrary element can be
753afe61c15SRodney W. Grimesremoved without traversing the list.
7544a775e8fSJustin T. GibbsNew elements can be added to the list after an existing element,
7554a775e8fSJustin T. Gibbsbefore an existing element, or at the head of the list.
756afe61c15SRodney W. GrimesA
757afe61c15SRodney W. Grimes.Fa LIST_HEAD
758afe61c15SRodney W. Grimesstructure is declared as follows:
759afe61c15SRodney W. Grimes.Bd -literal -offset indent
760afe61c15SRodney W. GrimesLIST_HEAD(HEADNAME, TYPE) head;
761afe61c15SRodney W. Grimes.Ed
7628f20a914SMike Pritchard.Pp
763afe61c15SRodney W. Grimeswhere
764afe61c15SRodney W. Grimes.Fa HEADNAME
765afe61c15SRodney W. Grimesis the name of the structure to be defined, and
766afe61c15SRodney W. Grimes.Fa TYPE
767afe61c15SRodney W. Grimesis the type of the elements to be linked into the list.
768afe61c15SRodney W. GrimesA pointer to the head of the list can later be declared as:
769afe61c15SRodney W. Grimes.Bd -literal -offset indent
770afe61c15SRodney W. Grimesstruct HEADNAME *headp;
771afe61c15SRodney W. Grimes.Ed
7728f20a914SMike Pritchard.Pp
773afe61c15SRodney W. Grimes(The names
774afe61c15SRodney W. Grimes.Li head
775afe61c15SRodney W. Grimesand
776afe61c15SRodney W. Grimes.Li headp
777afe61c15SRodney W. Grimesare user selectable.)
778afe61c15SRodney W. Grimes.Pp
779afe61c15SRodney W. GrimesThe macro
78003763fe0SJake Burkholder.Nm LIST_HEAD_INITIALIZER
78103763fe0SJake Burkholderevaluates to an initializer for the list
78203763fe0SJake Burkholder.Fa head .
78303763fe0SJake Burkholder.Pp
78403763fe0SJake BurkholderThe macro
78579ea9bc4SAlexey Zelkin.Nm LIST_EMPTY
786ddbb94adSTom Rhodesevaluates to true if there are no elements in the list.
78779ea9bc4SAlexey Zelkin.Pp
78879ea9bc4SAlexey ZelkinThe macro
789afe61c15SRodney W. Grimes.Nm LIST_ENTRY
790afe61c15SRodney W. Grimesdeclares a structure that connects the elements in
791afe61c15SRodney W. Grimesthe list.
792afe61c15SRodney W. Grimes.Pp
793afe61c15SRodney W. GrimesThe macro
79479ea9bc4SAlexey Zelkin.Nm LIST_FIRST
79579ea9bc4SAlexey Zelkinreturns the first element in the list or NULL if the list
79679ea9bc4SAlexey Zelkinis empty.
79779ea9bc4SAlexey Zelkin.Pp
79879ea9bc4SAlexey ZelkinThe macro
79979ea9bc4SAlexey Zelkin.Nm LIST_FOREACH
80079ea9bc4SAlexey Zelkintraverses the list referenced by
80179ea9bc4SAlexey Zelkin.Fa head
80279ea9bc4SAlexey Zelkinin the forward direction, assigning each element in turn to
80379ea9bc4SAlexey Zelkin.Fa var .
80479ea9bc4SAlexey Zelkin.Pp
80579ea9bc4SAlexey ZelkinThe macro
8067ecb4019SLawrence Stewart.Nm LIST_FOREACH_FROM
8077ecb4019SLawrence Stewartbehaves identically to
8087ecb4019SLawrence Stewart.Nm LIST_FOREACH
8097ecb4019SLawrence Stewartwhen
8107ecb4019SLawrence Stewart.Fa var
8117ecb4019SLawrence Stewartis NULL, else it treats
8127ecb4019SLawrence Stewart.Fa var
8137ecb4019SLawrence Stewartas a previously found LIST element and begins the loop at
8147ecb4019SLawrence Stewart.Fa var
8157ecb4019SLawrence Stewartinstead of the first element in the LIST referenced by
8167ecb4019SLawrence Stewart.Fa head .
8177ecb4019SLawrence Stewart.Pp
8187ecb4019SLawrence StewartThe macro
8194250a68eSBosko Milekic.Nm LIST_FOREACH_SAFE
8204250a68eSBosko Milekictraverses the list referenced by
8214250a68eSBosko Milekic.Fa head
8224250a68eSBosko Milekicin the forward direction, assigning each element in turn to
8234250a68eSBosko Milekic.Fa var .
8244250a68eSBosko MilekicHowever, unlike
8254250a68eSBosko Milekic.Fn LIST_FOREACH
8264250a68eSBosko Milekichere it is permitted to both remove
8274250a68eSBosko Milekic.Fa var
8284250a68eSBosko Milekicas well as free it from within the loop safely without interfering with the
8294250a68eSBosko Milekictraversal.
8304250a68eSBosko Milekic.Pp
8314250a68eSBosko MilekicThe macro
8327ecb4019SLawrence Stewart.Nm LIST_FOREACH_FROM_SAFE
8337ecb4019SLawrence Stewartbehaves identically to
8347ecb4019SLawrence Stewart.Nm LIST_FOREACH_SAFE
8357ecb4019SLawrence Stewartwhen
8367ecb4019SLawrence Stewart.Fa var
8377ecb4019SLawrence Stewartis NULL, else it treats
8387ecb4019SLawrence Stewart.Fa var
8397ecb4019SLawrence Stewartas a previously found LIST element and begins the loop at
8407ecb4019SLawrence Stewart.Fa var
8417ecb4019SLawrence Stewartinstead of the first element in the LIST referenced by
8427ecb4019SLawrence Stewart.Fa head .
8437ecb4019SLawrence Stewart.Pp
8447ecb4019SLawrence StewartThe macro
845afe61c15SRodney W. Grimes.Nm LIST_INIT
846afe61c15SRodney W. Grimesinitializes the list referenced by
847afe61c15SRodney W. Grimes.Fa head .
848afe61c15SRodney W. Grimes.Pp
849afe61c15SRodney W. GrimesThe macro
850afe61c15SRodney W. Grimes.Nm LIST_INSERT_HEAD
851afe61c15SRodney W. Grimesinserts the new element
852afe61c15SRodney W. Grimes.Fa elm
853afe61c15SRodney W. Grimesat the head of the list.
854afe61c15SRodney W. Grimes.Pp
855afe61c15SRodney W. GrimesThe macro
856afe61c15SRodney W. Grimes.Nm LIST_INSERT_AFTER
857afe61c15SRodney W. Grimesinserts the new element
858afe61c15SRodney W. Grimes.Fa elm
859afe61c15SRodney W. Grimesafter the element
860afe61c15SRodney W. Grimes.Fa listelm .
861afe61c15SRodney W. Grimes.Pp
862afe61c15SRodney W. GrimesThe macro
8637658b0a2SJustin T. Gibbs.Nm LIST_INSERT_BEFORE
8647658b0a2SJustin T. Gibbsinserts the new element
8657658b0a2SJustin T. Gibbs.Fa elm
8667658b0a2SJustin T. Gibbsbefore the element
8677658b0a2SJustin T. Gibbs.Fa listelm .
8687658b0a2SJustin T. Gibbs.Pp
8697658b0a2SJustin T. GibbsThe macro
87079ea9bc4SAlexey Zelkin.Nm LIST_NEXT
87179ea9bc4SAlexey Zelkinreturns the next element in the list, or NULL if this is the last.
87279ea9bc4SAlexey Zelkin.Pp
87379ea9bc4SAlexey ZelkinThe macro
8744170b083SEd Schouten.Nm LIST_PREV
8754170b083SEd Schoutenreturns the previous element in the list, or NULL if this is the first.
8764170b083SEd SchoutenList
8774170b083SEd Schouten.Fa head
8784170b083SEd Schoutenmust contain element
8794170b083SEd Schouten.Fa elm .
8804170b083SEd Schouten.Pp
8814170b083SEd SchoutenThe macro
882afe61c15SRodney W. Grimes.Nm LIST_REMOVE
883afe61c15SRodney W. Grimesremoves the element
884afe61c15SRodney W. Grimes.Fa elm
885afe61c15SRodney W. Grimesfrom the list.
886359295cdSMatthew D Fleming.Pp
887359295cdSMatthew D FlemingThe macro
888359295cdSMatthew D Fleming.Nm LIST_SWAP
889359295cdSMatthew D Flemingswaps the contents of
890359295cdSMatthew D Fleming.Fa head1
891359295cdSMatthew D Flemingand
892359295cdSMatthew D Fleming.Fa head2 .
893afe61c15SRodney W. Grimes.Sh LIST EXAMPLE
894afe61c15SRodney W. Grimes.Bd -literal
89503763fe0SJake BurkholderLIST_HEAD(listhead, entry) head =
89603763fe0SJake Burkholder    LIST_HEAD_INITIALIZER(head);
897afe61c15SRodney W. Grimesstruct listhead *headp;			/* List head. */
898afe61c15SRodney W. Grimesstruct entry {
899afe61c15SRodney W. Grimes	...
900afe61c15SRodney W. Grimes	LIST_ENTRY(entry) entries;	/* List. */
901afe61c15SRodney W. Grimes	...
9024250a68eSBosko Milekic} *n1, *n2, *n3, *np, *np_temp;
903afe61c15SRodney W. Grimes
904afe61c15SRodney W. GrimesLIST_INIT(&head);			/* Initialize the list. */
905afe61c15SRodney W. Grimes
906afe61c15SRodney W. Grimesn1 = malloc(sizeof(struct entry));	/* Insert at the head. */
907afe61c15SRodney W. GrimesLIST_INSERT_HEAD(&head, n1, entries);
908afe61c15SRodney W. Grimes
909afe61c15SRodney W. Grimesn2 = malloc(sizeof(struct entry));	/* Insert after. */
910afe61c15SRodney W. GrimesLIST_INSERT_AFTER(n1, n2, entries);
9117658b0a2SJustin T. Gibbs
9127658b0a2SJustin T. Gibbsn3 = malloc(sizeof(struct entry));	/* Insert before. */
9137658b0a2SJustin T. GibbsLIST_INSERT_BEFORE(n2, n3, entries);
9147658b0a2SJustin T. Gibbs
9157658b0a2SJustin T. GibbsLIST_REMOVE(n2, entries);		/* Deletion. */
9167658b0a2SJustin T. Gibbsfree(n2);
917afe61c15SRodney W. Grimes					/* Forward traversal. */
91879ea9bc4SAlexey ZelkinLIST_FOREACH(np, &head, entries)
919afe61c15SRodney W. Grimes	np-> ...
920afe61c15SRodney W. Grimes
9214250a68eSBosko Milekic					/* Safe forward traversal. */
9224250a68eSBosko MilekicLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
9234250a68eSBosko Milekic	np->do_stuff();
9244250a68eSBosko Milekic	...
9254250a68eSBosko Milekic	LIST_REMOVE(np, entries);
9264250a68eSBosko Milekic	free(np);
9274250a68eSBosko Milekic}
9284250a68eSBosko Milekic
92979ea9bc4SAlexey Zelkinwhile (!LIST_EMPTY(&head)) {		/* List Deletion. */
93079ea9bc4SAlexey Zelkin	n1 = LIST_FIRST(&head);
9317658b0a2SJustin T. Gibbs	LIST_REMOVE(n1, entries);
9327658b0a2SJustin T. Gibbs	free(n1);
9337658b0a2SJustin T. Gibbs}
9347658b0a2SJustin T. Gibbs
93503763fe0SJake Burkholdern1 = LIST_FIRST(&head);			/* Faster List Deletion. */
9367658b0a2SJustin T. Gibbswhile (n1 != NULL) {
93779ea9bc4SAlexey Zelkin	n2 = LIST_NEXT(n1, entries);
9387658b0a2SJustin T. Gibbs	free(n1);
9397658b0a2SJustin T. Gibbs	n1 = n2;
9407658b0a2SJustin T. Gibbs}
9417658b0a2SJustin T. GibbsLIST_INIT(&head);
942afe61c15SRodney W. Grimes.Ed
943afe61c15SRodney W. Grimes.Sh TAIL QUEUES
944afe61c15SRodney W. GrimesA tail queue is headed by a structure defined by the
945afe61c15SRodney W. Grimes.Nm TAILQ_HEAD
946afe61c15SRodney W. Grimesmacro.
947afe61c15SRodney W. GrimesThis structure contains a pair of pointers,
948afe61c15SRodney W. Grimesone to the first element in the tail queue and the other to
949afe61c15SRodney W. Grimesthe last element in the tail queue.
950afe61c15SRodney W. GrimesThe elements are doubly linked so that an arbitrary element can be
951afe61c15SRodney W. Grimesremoved without traversing the tail queue.
952afe61c15SRodney W. GrimesNew elements can be added to the tail queue after an existing element,
9534a775e8fSJustin T. Gibbsbefore an existing element, at the head of the tail queue,
9544a775e8fSJustin T. Gibbsor at the end of the tail queue.
955afe61c15SRodney W. GrimesA
956afe61c15SRodney W. Grimes.Fa TAILQ_HEAD
957afe61c15SRodney W. Grimesstructure is declared as follows:
958afe61c15SRodney W. Grimes.Bd -literal -offset indent
959afe61c15SRodney W. GrimesTAILQ_HEAD(HEADNAME, TYPE) head;
960afe61c15SRodney W. Grimes.Ed
9618f20a914SMike Pritchard.Pp
962afe61c15SRodney W. Grimeswhere
963afe61c15SRodney W. Grimes.Li HEADNAME
964afe61c15SRodney W. Grimesis the name of the structure to be defined, and
965afe61c15SRodney W. Grimes.Li TYPE
966afe61c15SRodney W. Grimesis the type of the elements to be linked into the tail queue.
967afe61c15SRodney W. GrimesA pointer to the head of the tail queue can later be declared as:
968afe61c15SRodney W. Grimes.Bd -literal -offset indent
969afe61c15SRodney W. Grimesstruct HEADNAME *headp;
970afe61c15SRodney W. Grimes.Ed
9718f20a914SMike Pritchard.Pp
972afe61c15SRodney W. Grimes(The names
973afe61c15SRodney W. Grimes.Li head
974afe61c15SRodney W. Grimesand
975afe61c15SRodney W. Grimes.Li headp
976afe61c15SRodney W. Grimesare user selectable.)
977afe61c15SRodney W. Grimes.Pp
978afe61c15SRodney W. GrimesThe macro
97903763fe0SJake Burkholder.Nm TAILQ_HEAD_INITIALIZER
98003763fe0SJake Burkholderevaluates to an initializer for the tail queue
98103763fe0SJake Burkholder.Fa head .
98203763fe0SJake Burkholder.Pp
98303763fe0SJake BurkholderThe macro
984d57e28adSThomas Moestl.Nm TAILQ_CONCAT
985d57e28adSThomas Moestlconcatenates the tail queue headed by
986d57e28adSThomas Moestl.Fa head2
987d57e28adSThomas Moestlonto the end of the one headed by
988d57e28adSThomas Moestl.Fa head1
989d57e28adSThomas Moestlremoving all entries from the former.
990d57e28adSThomas Moestl.Pp
991d57e28adSThomas MoestlThe macro
992c5c15c16SPoul-Henning Kamp.Nm TAILQ_EMPTY
993c5c15c16SPoul-Henning Kampevaluates to true if there are no items on the tail queue.
994c5c15c16SPoul-Henning Kamp.Pp
995c5c15c16SPoul-Henning KampThe macro
996afe61c15SRodney W. Grimes.Nm TAILQ_ENTRY
997afe61c15SRodney W. Grimesdeclares a structure that connects the elements in
998afe61c15SRodney W. Grimesthe tail queue.
999afe61c15SRodney W. Grimes.Pp
1000afe61c15SRodney W. GrimesThe macro
1001c5c15c16SPoul-Henning Kamp.Nm TAILQ_FIRST
1002c5c15c16SPoul-Henning Kampreturns the first item on the tail queue or NULL if the tail queue
1003c5c15c16SPoul-Henning Kampis empty.
1004c5c15c16SPoul-Henning Kamp.Pp
1005c5c15c16SPoul-Henning KampThe macro
100679ea9bc4SAlexey Zelkin.Nm TAILQ_FOREACH
100779ea9bc4SAlexey Zelkintraverses the tail queue referenced by
100879ea9bc4SAlexey Zelkin.Fa head
100979ea9bc4SAlexey Zelkinin the forward direction, assigning each element in turn to
101079ea9bc4SAlexey Zelkin.Fa var .
1011fb5293cfSRuslan Ermilov.Fa var
1012fb5293cfSRuslan Ermilovis set to
1013fb5293cfSRuslan Ermilov.Dv NULL
1014fb5293cfSRuslan Ermilovif the loop completes normally, or if there were no elements.
101579ea9bc4SAlexey Zelkin.Pp
101679ea9bc4SAlexey ZelkinThe macro
10177ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_FROM
10187ecb4019SLawrence Stewartbehaves identically to
10197ecb4019SLawrence Stewart.Nm TAILQ_FOREACH
10207ecb4019SLawrence Stewartwhen
10217ecb4019SLawrence Stewart.Fa var
10227ecb4019SLawrence Stewartis NULL, else it treats
10237ecb4019SLawrence Stewart.Fa var
10247ecb4019SLawrence Stewartas a previously found TAILQ element and begins the loop at
10257ecb4019SLawrence Stewart.Fa var
10267ecb4019SLawrence Stewartinstead of the first element in the TAILQ referenced by
10277ecb4019SLawrence Stewart.Fa head .
10287ecb4019SLawrence Stewart.Pp
10297ecb4019SLawrence StewartThe macro
10306c1d0fbfSArchie Cobbs.Nm TAILQ_FOREACH_REVERSE
10316c1d0fbfSArchie Cobbstraverses the tail queue referenced by
10326c1d0fbfSArchie Cobbs.Fa head
10336c1d0fbfSArchie Cobbsin the reverse direction, assigning each element in turn to
10346c1d0fbfSArchie Cobbs.Fa var .
10356c1d0fbfSArchie Cobbs.Pp
10367ecb4019SLawrence StewartThe macro
10377ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_REVERSE_FROM
10387ecb4019SLawrence Stewartbehaves identically to
10397ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_REVERSE
10407ecb4019SLawrence Stewartwhen
10417ecb4019SLawrence Stewart.Fa var
10427ecb4019SLawrence Stewartis NULL, else it treats
10437ecb4019SLawrence Stewart.Fa var
10447ecb4019SLawrence Stewartas a previously found TAILQ element and begins the reverse loop at
10457ecb4019SLawrence Stewart.Fa var
10467ecb4019SLawrence Stewartinstead of the last element in the TAILQ referenced by
10477ecb4019SLawrence Stewart.Fa head .
10487ecb4019SLawrence Stewart.Pp
10492724bce2SAlexander KabaevThe macros
10502724bce2SAlexander Kabaev.Nm TAILQ_FOREACH_SAFE
10512724bce2SAlexander Kabaevand
10522724bce2SAlexander Kabaev.Nm TAILQ_FOREACH_REVERSE_SAFE
10532724bce2SAlexander Kabaevtraverse the list referenced by
10542724bce2SAlexander Kabaev.Fa head
10552724bce2SAlexander Kabaevin the forward or reverse direction respectively,
10562724bce2SAlexander Kabaevassigning each element in turn to
10572724bce2SAlexander Kabaev.Fa var .
10583b96c71fSMike PritchardHowever, unlike their unsafe counterparts,
10592724bce2SAlexander Kabaev.Nm TAILQ_FOREACH
10602724bce2SAlexander Kabaevand
10612724bce2SAlexander Kabaev.Nm TAILQ_FOREACH_REVERSE
10622724bce2SAlexander Kabaevpermit to both remove
10632724bce2SAlexander Kabaev.Fa var
10642724bce2SAlexander Kabaevas well as free it from within the loop safely without interfering with the
10652724bce2SAlexander Kabaevtraversal.
10662724bce2SAlexander Kabaev.Pp
10676c1d0fbfSArchie CobbsThe macro
10687ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_FROM_SAFE
10697ecb4019SLawrence Stewartbehaves identically to
10707ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_SAFE
10717ecb4019SLawrence Stewartwhen
10727ecb4019SLawrence Stewart.Fa var
10737ecb4019SLawrence Stewartis NULL, else it treats
10747ecb4019SLawrence Stewart.Fa var
10757ecb4019SLawrence Stewartas a previously found TAILQ element and begins the loop at
10767ecb4019SLawrence Stewart.Fa var
10777ecb4019SLawrence Stewartinstead of the first element in the TAILQ referenced by
10787ecb4019SLawrence Stewart.Fa head .
10797ecb4019SLawrence Stewart.Pp
10807ecb4019SLawrence StewartThe macro
10817ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_REVERSE_FROM_SAFE
10827ecb4019SLawrence Stewartbehaves identically to
10837ecb4019SLawrence Stewart.Nm TAILQ_FOREACH_REVERSE_SAFE
10847ecb4019SLawrence Stewartwhen
10857ecb4019SLawrence Stewart.Fa var
10867ecb4019SLawrence Stewartis NULL, else it treats
10877ecb4019SLawrence Stewart.Fa var
10887ecb4019SLawrence Stewartas a previously found TAILQ element and begins the reverse loop at
10897ecb4019SLawrence Stewart.Fa var
10907ecb4019SLawrence Stewartinstead of the last element in the TAILQ referenced by
10917ecb4019SLawrence Stewart.Fa head .
10927ecb4019SLawrence Stewart.Pp
10937ecb4019SLawrence StewartThe macro
1094afe61c15SRodney W. Grimes.Nm TAILQ_INIT
1095afe61c15SRodney W. Grimesinitializes the tail queue referenced by
1096afe61c15SRodney W. Grimes.Fa head .
1097afe61c15SRodney W. Grimes.Pp
1098afe61c15SRodney W. GrimesThe macro
1099afe61c15SRodney W. Grimes.Nm TAILQ_INSERT_HEAD
1100afe61c15SRodney W. Grimesinserts the new element
1101afe61c15SRodney W. Grimes.Fa elm
1102afe61c15SRodney W. Grimesat the head of the tail queue.
1103afe61c15SRodney W. Grimes.Pp
1104afe61c15SRodney W. GrimesThe macro
1105afe61c15SRodney W. Grimes.Nm TAILQ_INSERT_TAIL
1106afe61c15SRodney W. Grimesinserts the new element
1107afe61c15SRodney W. Grimes.Fa elm
1108afe61c15SRodney W. Grimesat the end of the tail queue.
1109afe61c15SRodney W. Grimes.Pp
1110afe61c15SRodney W. GrimesThe macro
1111afe61c15SRodney W. Grimes.Nm TAILQ_INSERT_AFTER
1112afe61c15SRodney W. Grimesinserts the new element
1113afe61c15SRodney W. Grimes.Fa elm
1114afe61c15SRodney W. Grimesafter the element
1115afe61c15SRodney W. Grimes.Fa listelm .
1116afe61c15SRodney W. Grimes.Pp
1117afe61c15SRodney W. GrimesThe macro
11187658b0a2SJustin T. Gibbs.Nm TAILQ_INSERT_BEFORE
11197658b0a2SJustin T. Gibbsinserts the new element
11207658b0a2SJustin T. Gibbs.Fa elm
11217658b0a2SJustin T. Gibbsbefore the element
11227658b0a2SJustin T. Gibbs.Fa listelm .
11237658b0a2SJustin T. Gibbs.Pp
11247658b0a2SJustin T. GibbsThe macro
1125c5c15c16SPoul-Henning Kamp.Nm TAILQ_LAST
1126c5c15c16SPoul-Henning Kampreturns the last item on the tail queue.
1127982ba1cbSKirk McKusickIf the tail queue is empty the return value is
1128982ba1cbSKirk McKusick.Dv NULL .
1129c5c15c16SPoul-Henning Kamp.Pp
1130c5c15c16SPoul-Henning KampThe macro
1131c5c15c16SPoul-Henning Kamp.Nm TAILQ_NEXT
113279ea9bc4SAlexey Zelkinreturns the next item on the tail queue, or NULL if this item is the last.
113379ea9bc4SAlexey Zelkin.Pp
113479ea9bc4SAlexey ZelkinThe macro
113579ea9bc4SAlexey Zelkin.Nm TAILQ_PREV
113679ea9bc4SAlexey Zelkinreturns the previous item on the tail queue, or NULL if this item
113779ea9bc4SAlexey Zelkinis the first.
1138c5c15c16SPoul-Henning Kamp.Pp
1139c5c15c16SPoul-Henning KampThe macro
1140afe61c15SRodney W. Grimes.Nm TAILQ_REMOVE
1141afe61c15SRodney W. Grimesremoves the element
1142afe61c15SRodney W. Grimes.Fa elm
1143afe61c15SRodney W. Grimesfrom the tail queue.
1144359295cdSMatthew D Fleming.Pp
1145359295cdSMatthew D FlemingThe macro
1146359295cdSMatthew D Fleming.Nm TAILQ_SWAP
1147359295cdSMatthew D Flemingswaps the contents of
1148359295cdSMatthew D Fleming.Fa head1
1149359295cdSMatthew D Flemingand
1150359295cdSMatthew D Fleming.Fa head2 .
1151afe61c15SRodney W. Grimes.Sh TAIL QUEUE EXAMPLE
1152afe61c15SRodney W. Grimes.Bd -literal
115303763fe0SJake BurkholderTAILQ_HEAD(tailhead, entry) head =
115403763fe0SJake Burkholder    TAILQ_HEAD_INITIALIZER(head);
1155afe61c15SRodney W. Grimesstruct tailhead *headp;			/* Tail queue head. */
1156afe61c15SRodney W. Grimesstruct entry {
1157afe61c15SRodney W. Grimes	...
1158afe61c15SRodney W. Grimes	TAILQ_ENTRY(entry) entries;	/* Tail queue. */
1159afe61c15SRodney W. Grimes	...
11607658b0a2SJustin T. Gibbs} *n1, *n2, *n3, *np;
1161afe61c15SRodney W. Grimes
1162afe61c15SRodney W. GrimesTAILQ_INIT(&head);			/* Initialize the queue. */
1163afe61c15SRodney W. Grimes
1164afe61c15SRodney W. Grimesn1 = malloc(sizeof(struct entry));	/* Insert at the head. */
1165afe61c15SRodney W. GrimesTAILQ_INSERT_HEAD(&head, n1, entries);
1166afe61c15SRodney W. Grimes
1167afe61c15SRodney W. Grimesn1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
1168afe61c15SRodney W. GrimesTAILQ_INSERT_TAIL(&head, n1, entries);
1169afe61c15SRodney W. Grimes
1170afe61c15SRodney W. Grimesn2 = malloc(sizeof(struct entry));	/* Insert after. */
1171afe61c15SRodney W. GrimesTAILQ_INSERT_AFTER(&head, n1, n2, entries);
11727658b0a2SJustin T. Gibbs
11737658b0a2SJustin T. Gibbsn3 = malloc(sizeof(struct entry));	/* Insert before. */
11743652ff55SJustin T. GibbsTAILQ_INSERT_BEFORE(n2, n3, entries);
11757658b0a2SJustin T. Gibbs
11767658b0a2SJustin T. GibbsTAILQ_REMOVE(&head, n2, entries);	/* Deletion. */
11777658b0a2SJustin T. Gibbsfree(n2);
1178afe61c15SRodney W. Grimes					/* Forward traversal. */
117979ea9bc4SAlexey ZelkinTAILQ_FOREACH(np, &head, entries)
1180afe61c15SRodney W. Grimes	np-> ...
11812724bce2SAlexander Kabaev					/* Safe forward traversal. */
11822724bce2SAlexander KabaevTAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
11832724bce2SAlexander Kabaev	np->do_stuff();
11842724bce2SAlexander Kabaev	...
11852724bce2SAlexander Kabaev	TAILQ_REMOVE(&head, np, entries);
11862724bce2SAlexander Kabaev	free(np);
11872724bce2SAlexander Kabaev}
11886c1d0fbfSArchie Cobbs					/* Reverse traversal. */
11896c1d0fbfSArchie CobbsTAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
11906c1d0fbfSArchie Cobbs	np-> ...
11917658b0a2SJustin T. Gibbs					/* TailQ Deletion. */
1192d6c63818SMark Murraywhile (!TAILQ_EMPTY(&head)) {
1193c5c15c16SPoul-Henning Kamp	n1 = TAILQ_FIRST(&head);
119479ea9bc4SAlexey Zelkin	TAILQ_REMOVE(&head, n1, entries);
11957658b0a2SJustin T. Gibbs	free(n1);
11967658b0a2SJustin T. Gibbs}
11977658b0a2SJustin T. Gibbs					/* Faster TailQ Deletion. */
1198c5c15c16SPoul-Henning Kampn1 = TAILQ_FIRST(&head);
11997658b0a2SJustin T. Gibbswhile (n1 != NULL) {
1200c5c15c16SPoul-Henning Kamp	n2 = TAILQ_NEXT(n1, entries);
12017658b0a2SJustin T. Gibbs	free(n1);
12027658b0a2SJustin T. Gibbs	n1 = n2;
12037658b0a2SJustin T. Gibbs}
12047658b0a2SJustin T. GibbsTAILQ_INIT(&head);
1205afe61c15SRodney W. Grimes.Ed
1206b9ec8f3bSSimon L. B. Nielsen.Sh SEE ALSO
1207b9ec8f3bSSimon L. B. Nielsen.Xr tree 3
1208afe61c15SRodney W. Grimes.Sh HISTORY
1209afe61c15SRodney W. GrimesThe
1210afe61c15SRodney W. Grimes.Nm queue
121121421932SMike Pritchardfunctions first appeared in
121221421932SMike Pritchard.Bx 4.4 .
1213