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