2 .\" The Regents of the University of California. All rights reserved.
4 .\" Redistribution and use in source and binary forms, with or without
5 .\" modification, are permitted provided that the following conditions
7 .\" 1. Redistributions of source code must retain the above copyright
8 .\" notice, this list of conditions and the following disclaimer.
9 .\" 2. Redistributions in binary form must reproduce the above copyright
10 .\" notice, this list of conditions and the following disclaimer in the
11 .\" documentation and/or other materials provided with the distribution.
12 .\" 3. All advertising materials mentioning features or use of this software
13 .\" must display the following acknowledgement:
14 .\" This product includes software developed by the University of
15 .\" California, Berkeley and its contributors.
16 .\" 4. Neither the name of the University nor the names of its contributors
17 .\" may be used to endorse or promote products derived from this software
18 .\" without specific prior written permission.
20 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 .\" @(#)queue.3 8.2 (Berkeley) 1/24/94
33 .\" $FreeBSD: src/share/man/man3/queue.3,v 1.42 2008/05/22 14:40:03 ed Exp $
34 .\" $DragonFly: src/share/man/man3/queue.3,v 1.8 2008/10/17 12:41:38 swildner Exp $
44 .Nm SLIST_FOREACH_MUTABLE ,
45 .Nm SLIST_FOREACH_PREVPTR ,
47 .Nm SLIST_HEAD_INITIALIZER ,
49 .Nm SLIST_INSERT_AFTER ,
50 .Nm SLIST_INSERT_HEAD ,
52 .Nm SLIST_REMOVE_HEAD ,
53 .Nm SLIST_REMOVE_NEXT ,
60 .Nm STAILQ_FOREACH_MUTABLE ,
62 .Nm STAILQ_HEAD_INITIALIZER ,
64 .Nm STAILQ_INSERT_AFTER ,
65 .Nm STAILQ_INSERT_HEAD ,
66 .Nm STAILQ_INSERT_TAIL ,
69 .Nm STAILQ_REMOVE_HEAD ,
70 .Nm STAILQ_REMOVE_NEXT ,
76 .Nm LIST_FOREACH_MUTABLE ,
78 .Nm LIST_HEAD_INITIALIZER ,
80 .Nm LIST_INSERT_AFTER ,
81 .Nm LIST_INSERT_BEFORE ,
82 .Nm LIST_INSERT_HEAD ,
90 .Nm TAILQ_FOREACH_MUTABLE ,
91 .Nm TAILQ_FOREACH_REVERSE ,
92 .Nm TAILQ_FOREACH_REVERSE_MUTABLE ,
94 .Nm TAILQ_HEAD_INITIALIZER ,
96 .Nm TAILQ_INSERT_AFTER ,
97 .Nm TAILQ_INSERT_BEFORE ,
98 .Nm TAILQ_INSERT_HEAD ,
99 .Nm TAILQ_INSERT_TAIL ,
104 .Nd implementations of singly-linked lists, singly-linked tail queues,
105 lists and tail queues
109 .Fn SLIST_EMPTY "SLIST_HEAD *head"
110 .Fn SLIST_ENTRY "TYPE"
111 .Fn SLIST_FIRST "SLIST_HEAD *head"
112 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
113 .Fn SLIST_FOREACH_MUTABLE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
114 .Fn SLIST_FOREACH_PREVPTR "TYPE *var" "TYPE *varp" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
115 .Fn SLIST_HEAD "HEADNAME" "TYPE"
116 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
117 .Fn SLIST_INIT "SLIST_HEAD *head"
118 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
119 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
120 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
121 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
122 .Fn SLIST_REMOVE_NEXT "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
123 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
125 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
126 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
127 .Fn STAILQ_ENTRY "TYPE"
128 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
129 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
130 .Fn STAILQ_FOREACH_MUTABLE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
131 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
132 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
133 .Fn STAILQ_INIT "STAILQ_HEAD *head"
134 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
135 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
136 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
137 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
138 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
139 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
140 .Fn STAILQ_REMOVE_NEXT "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
141 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
143 .Fn LIST_EMPTY "LIST_HEAD *head"
144 .Fn LIST_ENTRY "TYPE"
145 .Fn LIST_FIRST "LIST_HEAD *head"
146 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
147 .Fn LIST_FOREACH_MUTABLE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
148 .Fn LIST_HEAD "HEADNAME" "TYPE"
149 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
150 .Fn LIST_INIT "LIST_HEAD *head"
151 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
152 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
153 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
154 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
155 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
157 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
158 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
159 .Fn TAILQ_ENTRY "TYPE"
160 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
161 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
162 .Fn TAILQ_FOREACH_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
163 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
164 .Fn TAILQ_FOREACH_REVERSE_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
165 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
166 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
167 .Fn TAILQ_INIT "TAILQ_HEAD *head"
168 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
169 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
170 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
171 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
172 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
173 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
174 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
175 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
178 These macros define and operate on four types of data structures:
179 singly-linked lists, singly-linked tail queues, lists, and tail queues.
180 All four structures support the following functionality:
181 .Bl -enum -compact -offset indent
183 Insertion of a new entry at the head of the list.
185 Insertion of a new entry after any element in the list.
187 O(1) removal of an entry from the head of the list.
189 Forward traversal through the list.
192 O(n) removal of any entry in the list.
193 Singly-linked lists are the simplest of the four data structures
194 and support only the above functionality.
195 Singly-linked lists are ideal for applications with large datasets
196 and few or no removals,
197 or for implementing a LIFO queue.
198 Singly-linked lists add the following functionality:
199 .Bl -enum -compact -offset indent
201 O(n) removal of any entry in the list.
204 Singly-linked tail queues add the following functionality:
205 .Bl -enum -compact -offset indent
207 Entries can be added at the end of a list.
209 O(n) removal of any entry in the list.
211 They may be concatenated.
214 .Bl -enum -compact -offset indent
216 All list insertions must specify the head of the list.
218 Each head entry requires two pointers rather than one.
220 Code size is about 15% greater and operations run about 20% slower
221 than singly-linked lists.
224 Singly-linked tailqs are ideal for applications with large datasets and
226 or for implementing a FIFO queue.
228 All doubly linked types of data structures (lists and tail queues)
230 .Bl -enum -compact -offset indent
232 Insertion of a new entry before any element in the list.
234 O(1) removal of any entry in the list.
237 .Bl -enum -compact -offset indent
239 Each element requires two pointers rather than one.
241 Code size and execution time of operations (except for removal) is about
242 twice that of the singly-linked data-structures.
245 Linked lists are the simplest of the doubly linked data structures and support
246 only the above functionality over singly-linked lists.
248 Tail queues add the following functionality:
249 .Bl -enum -compact -offset indent
251 Entries can be added at the end of a list.
253 They may be traversed backwards, from tail to head.
255 They may be concatenated.
258 .Bl -enum -compact -offset indent
260 All list insertions and removals must specify the head of the list.
262 Each head entry requires two pointers rather than one.
264 Code size is about 15% greater and operations run about 20% slower
265 than singly-linked lists.
268 In the macro definitions,
270 is the name of a user defined structure,
271 that must contain a field of type
281 is the name of a user defined structure that must be declared
288 See the examples below for further explanation of how these
290 .Sh SINGLY-LINKED LISTS
291 A singly-linked list is headed by a structure defined by the
294 This structure contains a single pointer to the first element
296 The elements are singly linked for minimum space and pointer manipulation
297 overhead at the expense of O(n) removal for arbitrary elements.
298 New elements can be added to the list after an existing element or
299 at the head of the list.
302 structure is declared as follows:
303 .Bd -literal -offset indent
304 SLIST_HEAD(HEADNAME, TYPE) head;
309 is the name of the structure to be defined, and
311 is the type of the elements to be linked into the list.
312 A pointer to the head of the list can later be declared as:
313 .Bd -literal -offset indent
314 struct HEADNAME *headp;
321 are user selectable.)
324 .Nm SLIST_HEAD_INITIALIZER
325 evaluates to an initializer for the list
330 evaluates to true if there are no elements in the list.
334 declares a structure that connects the elements in
339 returns the first element in the list or NULL if the list is empty.
343 traverses the list referenced by
345 in the forward direction, assigning each element in
350 .Nm SLIST_FOREACH_MUTABLE
351 traverses the list referenced by
353 in the forward direction, assigning each element in
358 here it is permitted to both remove
360 as well as free it from within the loop safely without interfering with the
364 .Nm SLIST_FOREACH_PREVPTR
367 except that it stores a pointer to the previous element in
369 This provides access to the previous element while traversing the list,
370 as one would have with a doubly-linked list.
374 initializes the list referenced by
378 .Nm SLIST_INSERT_HEAD
379 inserts the new element
381 at the head of the list.
384 .Nm SLIST_INSERT_AFTER
385 inserts the new element
392 returns the next element in the list.
395 .Nm SLIST_REMOVE_HEAD
398 from the head of the list.
399 For optimum efficiency,
400 elements being removed from the head of the list should explicitly use
401 this macro instead of the generic
406 .Nm SLIST_REMOVE_NEXT
407 removes the element after
409 from the list. Unlike
411 this macro does not traverse the entire list.
418 .Sh SINGLY-LINKED LIST EXAMPLE
420 SLIST_HEAD(slisthead, entry) head =
421 SLIST_HEAD_INITIALIZER(head);
422 struct slisthead *headp; /* Singly-linked List head. */
425 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
427 } *n1, *n2, *n3, *np;
429 SLIST_INIT(&head); /* Initialize the list. */
431 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
432 SLIST_INSERT_HEAD(&head, n1, entries);
434 n2 = malloc(sizeof(struct entry)); /* Insert after. */
435 SLIST_INSERT_AFTER(n1, n2, entries);
437 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
440 n3 = SLIST_FIRST(&head);
441 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
443 /* Forward traversal. */
444 SLIST_FOREACH(np, &head, entries)
446 /* Safe forward traversal. */
447 SLIST_FOREACH_MUTABLE(np, &head, entries, np_temp) {
450 SLIST_REMOVE(&head, np, entry, entries);
454 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
455 n1 = SLIST_FIRST(&head);
456 SLIST_REMOVE_HEAD(&head, entries);
460 .Sh SINGLY-LINKED TAIL QUEUES
461 A singly-linked tail queue is headed by a structure defined by the
464 This structure contains a pair of pointers,
465 one to the first element in the tail queue and the other to
466 the last element in the tail queue.
467 The elements are singly linked for minimum space and pointer
468 manipulation overhead at the expense of O(n) removal for arbitrary
470 New elements can be added to the tail queue after an existing element,
471 at the head of the tail queue, or at the end of the tail queue.
474 structure is declared as follows:
475 .Bd -literal -offset indent
476 STAILQ_HEAD(HEADNAME, TYPE) head;
481 is the name of the structure to be defined, and
483 is the type of the elements to be linked into the tail queue.
484 A pointer to the head of the tail queue can later be declared as:
485 .Bd -literal -offset indent
486 struct HEADNAME *headp;
493 are user selectable.)
496 .Nm STAILQ_HEAD_INITIALIZER
497 evaluates to an initializer for the tail queue
502 concatenates the tail queue headed by
504 onto the end of the one headed by
506 removing all entries from the former.
510 evaluates to true if there are no items on the tail queue.
514 declares a structure that connects the elements in
519 returns the first item on the tail queue or NULL if the tail queue
524 traverses the tail queue referenced by
526 in the forward direction, assigning each element
531 .Nm STAILQ_FOREACH_MUTABLE
532 traverses the tail queue referenced by
534 in the forward direction, assigning each element
539 here it is permitted to both remove
541 as well as free it from within the loop safely without interfering with the
546 initializes the tail queue referenced by
550 .Nm STAILQ_INSERT_HEAD
551 inserts the new element
553 at the head of the tail queue.
556 .Nm STAILQ_INSERT_TAIL
557 inserts the new element
559 at the end of the tail queue.
562 .Nm STAILQ_INSERT_AFTER
563 inserts the new element
570 returns the last item on the tail queue.
571 If the tail queue is empty the return value is
576 returns the next item on the tail queue, or NULL this item is the last.
579 .Nm STAILQ_REMOVE_HEAD
580 removes the element at the head of the tail queue.
581 For optimum efficiency,
582 elements being removed from the head of the tail queue should
583 use this macro explicitly rather than the generic
588 .Nm STAILQ_REMOVE_NEXT
589 removes the element after
591 from the tail queue. Unlike
593 this macro does not traverse the entire tail queue.
600 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
602 STAILQ_HEAD(stailhead, entry) head =
603 STAILQ_HEAD_INITIALIZER(head);
604 struct stailhead *headp; /* Singly-linked tail queue head. */
607 STAILQ_ENTRY(entry) entries; /* Tail queue. */
609 } *n1, *n2, *n3, *np;
611 STAILQ_INIT(&head); /* Initialize the queue. */
613 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
614 STAILQ_INSERT_HEAD(&head, n1, entries);
616 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
617 STAILQ_INSERT_TAIL(&head, n1, entries);
619 n2 = malloc(sizeof(struct entry)); /* Insert after. */
620 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
622 STAILQ_REMOVE(&head, n2, entry, entries);
624 /* Deletion from the head. */
625 n3 = STAILQ_FIRST(&head);
626 STAILQ_REMOVE_HEAD(&head, entries);
628 /* Forward traversal. */
629 STAILQ_FOREACH(np, &head, entries)
631 /* Safe forward traversal. */
632 STAILQ_FOREACH_MUTABLE(np, &head, entries, np_temp) {
635 STAILQ_REMOVE(&head, np, entry, entries);
638 /* TailQ Deletion. */
639 while (!STAILQ_EMPTY(&head)) {
640 n1 = STAILQ_FIRST(&head);
641 STAILQ_REMOVE_HEAD(&head, entries);
644 /* Faster TailQ Deletion. */
645 n1 = STAILQ_FIRST(&head);
647 n2 = STAILQ_NEXT(n1, entries);
654 A list is headed by a structure defined by the
657 This structure contains a single pointer to the first element
659 The elements are doubly linked so that an arbitrary element can be
660 removed without traversing the list.
661 New elements can be added to the list after an existing element,
662 before an existing element, or at the head of the list.
665 structure is declared as follows:
666 .Bd -literal -offset indent
667 LIST_HEAD(HEADNAME, TYPE) head;
672 is the name of the structure to be defined, and
674 is the type of the elements to be linked into the list.
675 A pointer to the head of the list can later be declared as:
676 .Bd -literal -offset indent
677 struct HEADNAME *headp;
684 are user selectable.)
687 .Nm LIST_HEAD_INITIALIZER
688 evaluates to an initializer for the list
693 evaluates to true if there are no elements in the list.
697 declares a structure that connects the elements in
702 returns the first element in the list or NULL if the list
707 traverses the list referenced by
709 in the forward direction, assigning each element in turn to
713 .Nm LIST_FOREACH_MUTABLE
714 traverses the list referenced by
716 in the forward direction, assigning each element in turn to
720 here it is permitted to both remove
722 as well as free it from within the loop safely without interfering with the
727 initializes the list referenced by
732 inserts the new element
734 at the head of the list.
737 .Nm LIST_INSERT_AFTER
738 inserts the new element
744 .Nm LIST_INSERT_BEFORE
745 inserts the new element
752 returns the next element in the list, or NULL if this is the last.
761 LIST_HEAD(listhead, entry) head =
762 LIST_HEAD_INITIALIZER(head);
763 struct listhead *headp; /* List head. */
766 LIST_ENTRY(entry) entries; /* List. */
768 } *n1, *n2, *n3, *np, *np_temp;
770 LIST_INIT(&head); /* Initialize the list. */
772 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
773 LIST_INSERT_HEAD(&head, n1, entries);
775 n2 = malloc(sizeof(struct entry)); /* Insert after. */
776 LIST_INSERT_AFTER(n1, n2, entries);
778 n3 = malloc(sizeof(struct entry)); /* Insert before. */
779 LIST_INSERT_BEFORE(n2, n3, entries);
781 LIST_REMOVE(n2, entries); /* Deletion. */
783 /* Forward traversal. */
784 LIST_FOREACH(np, &head, entries)
787 /* Safe forward traversal. */
788 LIST_FOREACH_MUTABLE(np, &head, entries, np_temp) {
791 LIST_REMOVE(np, entries);
795 while (!LIST_EMPTY(&head)) { /* List Deletion. */
796 n1 = LIST_FIRST(&head);
797 LIST_REMOVE(n1, entries);
801 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
803 n2 = LIST_NEXT(n1, entries);
810 A tail queue is headed by a structure defined by the
813 This structure contains a pair of pointers,
814 one to the first element in the tail queue and the other to
815 the last element in the tail queue.
816 The elements are doubly linked so that an arbitrary element can be
817 removed without traversing the tail queue.
818 New elements can be added to the tail queue after an existing element,
819 before an existing element, at the head of the tail queue,
820 or at the end of the tail queue.
823 structure is declared as follows:
824 .Bd -literal -offset indent
825 TAILQ_HEAD(HEADNAME, TYPE) head;
830 is the name of the structure to be defined, and
832 is the type of the elements to be linked into the tail queue.
833 A pointer to the head of the tail queue can later be declared as:
834 .Bd -literal -offset indent
835 struct HEADNAME *headp;
842 are user selectable.)
845 .Nm TAILQ_HEAD_INITIALIZER
846 evaluates to an initializer for the tail queue
851 concatenates the tail queue headed by
853 onto the end of the one headed by
855 removing all entries from the former.
859 evaluates to true if there are no items on the tail queue.
863 declares a structure that connects the elements in
868 returns the first item on the tail queue or NULL if the tail queue
873 traverses the tail queue referenced by
875 in the forward direction, assigning each element in turn to
880 if the loop completes normally, or if there were no elements.
883 .Nm TAILQ_FOREACH_REVERSE
884 traverses the tail queue referenced by
886 in the reverse direction, assigning each element in turn to
890 .Nm TAILQ_FOREACH_MUTABLE
892 .Nm TAILQ_FOREACH_REVERSE_MUTABLE
893 traverse the list referenced by
895 in the forward or reverse direction respectively,
896 assigning each element in turn to
898 However, unlike their unsafe counterparts,
901 .Nm TAILQ_FOREACH_REVERSE
902 permit to both remove
904 as well as free it from within the loop safely without interfering with the
909 initializes the tail queue referenced by
913 .Nm TAILQ_INSERT_HEAD
914 inserts the new element
916 at the head of the tail queue.
919 .Nm TAILQ_INSERT_TAIL
920 inserts the new element
922 at the end of the tail queue.
925 .Nm TAILQ_INSERT_AFTER
926 inserts the new element
932 .Nm TAILQ_INSERT_BEFORE
933 inserts the new element
940 returns the last item on the tail queue.
941 If the tail queue is empty the return value is
946 returns the next item on the tail queue, or NULL if this item is the last.
950 returns the previous item on the tail queue, or NULL if this item
958 .Sh TAIL QUEUE EXAMPLE
960 TAILQ_HEAD(tailhead, entry) head =
961 TAILQ_HEAD_INITIALIZER(head);
962 struct tailhead *headp; /* Tail queue head. */
965 TAILQ_ENTRY(entry) entries; /* Tail queue. */
967 } *n1, *n2, *n3, *np;
969 TAILQ_INIT(&head); /* Initialize the queue. */
971 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
972 TAILQ_INSERT_HEAD(&head, n1, entries);
974 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
975 TAILQ_INSERT_TAIL(&head, n1, entries);
977 n2 = malloc(sizeof(struct entry)); /* Insert after. */
978 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
980 n3 = malloc(sizeof(struct entry)); /* Insert before. */
981 TAILQ_INSERT_BEFORE(n2, n3, entries);
983 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
985 /* Forward traversal. */
986 TAILQ_FOREACH(np, &head, entries)
988 /* Safe forward traversal. */
989 TAILQ_FOREACH_MUTABLE(np, &head, entries, np_temp) {
992 TAILQ_REMOVE(&head, np, entries);
995 /* Reverse traversal. */
996 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
998 /* TailQ Deletion. */
999 while (!TAILQ_EMPTY(&head)) {
1000 n1 = TAILQ_FIRST(&head);
1001 TAILQ_REMOVE(&head, n1, entries);
1004 /* Faster TailQ Deletion. */
1005 n1 = TAILQ_FIRST(&head);
1006 while (n1 != NULL) {
1007 n2 = TAILQ_NEXT(n1, entries);
1016 functions first appeared in