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.46 2011/01/11 13:33:42 gavin Exp $
43 .Nm SLIST_FOREACH_MUTABLE ,
44 .Nm SLIST_FOREACH_PREVPTR ,
46 .Nm SLIST_HEAD_INITIALIZER ,
48 .Nm SLIST_INSERT_AFTER ,
49 .Nm SLIST_INSERT_HEAD ,
51 .Nm SLIST_REMOVE_AFTER ,
52 .Nm SLIST_REMOVE_HEAD ,
59 .Nm STAILQ_FOREACH_MUTABLE ,
61 .Nm STAILQ_HEAD_INITIALIZER ,
63 .Nm STAILQ_INSERT_AFTER ,
64 .Nm STAILQ_INSERT_HEAD ,
65 .Nm STAILQ_INSERT_TAIL ,
68 .Nm STAILQ_REMOVE_AFTER ,
69 .Nm STAILQ_REMOVE_HEAD ,
75 .Nm LIST_FOREACH_MUTABLE ,
77 .Nm LIST_HEAD_INITIALIZER ,
79 .Nm LIST_INSERT_AFTER ,
80 .Nm LIST_INSERT_BEFORE ,
81 .Nm LIST_INSERT_HEAD ,
89 .Nm TAILQ_FOREACH_MUTABLE ,
90 .Nm TAILQ_FOREACH_REVERSE ,
91 .Nm TAILQ_FOREACH_REVERSE_MUTABLE ,
93 .Nm TAILQ_HEAD_INITIALIZER ,
95 .Nm TAILQ_INSERT_AFTER ,
96 .Nm TAILQ_INSERT_BEFORE ,
97 .Nm TAILQ_INSERT_HEAD ,
98 .Nm TAILQ_INSERT_TAIL ,
103 .Nd implementations of singly-linked lists, singly-linked tail queues,
104 lists and tail queues
108 .Fn SLIST_EMPTY "SLIST_HEAD *head"
109 .Fn SLIST_ENTRY "TYPE"
110 .Fn SLIST_FIRST "SLIST_HEAD *head"
111 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
112 .Fn SLIST_FOREACH_MUTABLE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
113 .Fn SLIST_FOREACH_PREVPTR "TYPE *var" "TYPE *varp" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
114 .Fn SLIST_HEAD "HEADNAME" "TYPE"
115 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
116 .Fn SLIST_INIT "SLIST_HEAD *head"
117 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
118 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
119 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
120 .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
121 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
122 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
124 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
125 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
126 .Fn STAILQ_ENTRY "TYPE"
127 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
128 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
129 .Fn STAILQ_FOREACH_MUTABLE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
130 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
131 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
132 .Fn STAILQ_INIT "STAILQ_HEAD *head"
133 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
134 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
135 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
136 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
137 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
138 .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
139 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
140 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
142 .Fn LIST_EMPTY "LIST_HEAD *head"
143 .Fn LIST_ENTRY "TYPE"
144 .Fn LIST_FIRST "LIST_HEAD *head"
145 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
146 .Fn LIST_FOREACH_MUTABLE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
147 .Fn LIST_HEAD "HEADNAME" "TYPE"
148 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
149 .Fn LIST_INIT "LIST_HEAD *head"
150 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
151 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
152 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
153 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
154 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
156 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
157 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
158 .Fn TAILQ_ENTRY "TYPE"
159 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
160 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
161 .Fn TAILQ_FOREACH_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
162 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
163 .Fn TAILQ_FOREACH_REVERSE_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
164 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
165 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
166 .Fn TAILQ_INIT "TAILQ_HEAD *head"
167 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
168 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
169 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
170 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
171 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
172 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
173 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
174 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
177 These macros define and operate on four types of data structures:
178 singly-linked lists, singly-linked tail queues, lists, and tail queues.
179 All four structures support the following functionality:
180 .Bl -enum -compact -offset indent
182 Insertion of a new entry at the head of the list.
184 Insertion of a new entry after any element in the list.
186 O(1) removal of an entry from the head of the list.
188 Forward traversal through the list.
191 Singly-linked lists are the simplest of the four data structures
192 and support only the above functionality.
193 Singly-linked lists are ideal for applications with large datasets
194 and few or no removals,
195 or for implementing a LIFO queue.
196 Singly-linked lists add the following functionality:
197 .Bl -enum -compact -offset indent
199 O(n) removal of any entry in the list.
202 Singly-linked tail queues add the following functionality:
203 .Bl -enum -compact -offset indent
205 Entries can be added at the end of a list.
207 O(n) removal of any entry in the list.
209 They may be concatenated.
212 .Bl -enum -compact -offset indent
214 All list insertions must specify the head of the list.
216 Each head entry requires two pointers rather than one.
218 Code size is about 15% greater and operations run about 20% slower
219 than singly-linked lists.
222 Singly-linked tailqs are ideal for applications with large datasets and
224 or for implementing a FIFO queue.
226 All doubly linked types of data structures (lists and tail queues)
228 .Bl -enum -compact -offset indent
230 Insertion of a new entry before any element in the list.
232 O(1) removal of any entry in the list.
235 .Bl -enum -compact -offset indent
237 Each element requires two pointers rather than one.
239 Code size and execution time of operations (except for removal) is about
240 twice that of the singly-linked data-structures.
243 Linked lists are the simplest of the doubly linked data structures and support
244 only the above functionality over singly-linked lists.
246 Tail queues add the following functionality:
247 .Bl -enum -compact -offset indent
249 Entries can be added at the end of a list.
251 They may be traversed backwards, from tail to head.
253 They may be concatenated.
256 .Bl -enum -compact -offset indent
258 All list insertions and removals must specify the head of the list.
260 Each head entry requires two pointers rather than one.
262 Code size is about 15% greater and operations run about 20% slower
263 than singly-linked lists.
266 In the macro definitions,
268 is the name of a user defined structure,
269 that must contain a field of type
279 is the name of a user defined structure that must be declared
286 See the examples below for further explanation of how these
288 .Sh SINGLY-LINKED LISTS
289 A singly-linked list is headed by a structure defined by the
292 This structure contains a single pointer to the first element
294 The elements are singly linked for minimum space and pointer manipulation
295 overhead at the expense of O(n) removal for arbitrary elements.
296 New elements can be added to the list after an existing element or
297 at the head of the list.
300 structure is declared as follows:
301 .Bd -literal -offset indent
302 SLIST_HEAD(HEADNAME, TYPE) head;
307 is the name of the structure to be defined, and
309 is the type of the elements to be linked into the list.
310 A pointer to the head of the list can later be declared as:
311 .Bd -literal -offset indent
312 struct HEADNAME *headp;
319 are user selectable.)
322 .Nm SLIST_HEAD_INITIALIZER
323 evaluates to an initializer for the list
328 evaluates to true if there are no elements in the list.
332 declares a structure that connects the elements in
337 returns the first element in the list or NULL if the list is empty.
341 traverses the list referenced by
343 in the forward direction, assigning each element in
348 .Nm SLIST_FOREACH_MUTABLE
349 traverses the list referenced by
351 in the forward direction, assigning each element in
356 here it is permitted to both remove
358 as well as free it from within the loop safely without interfering with the
362 .Nm SLIST_FOREACH_PREVPTR
365 except that it stores a pointer to the previous element in
367 This provides access to the previous element while traversing the list,
368 as one would have with a doubly-linked list.
372 initializes the list referenced by
376 .Nm SLIST_INSERT_HEAD
377 inserts the new element
379 at the head of the list.
382 .Nm SLIST_INSERT_AFTER
383 inserts the new element
390 returns the next element in the list.
393 .Nm SLIST_REMOVE_AFTER
394 removes the element after
396 from the list. Unlike
398 this macro does not traverse the entire list.
401 .Nm SLIST_REMOVE_HEAD
404 from the head of the list.
405 For optimum efficiency,
406 elements being removed from the head of the list should explicitly use
407 this macro instead of the generic
416 .Sh SINGLY-LINKED LIST EXAMPLE
418 SLIST_HEAD(slisthead, entry) head =
419 SLIST_HEAD_INITIALIZER(head);
420 struct slisthead *headp; /* Singly-linked List head. */
423 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
425 } *n1, *n2, *n3, *np;
427 SLIST_INIT(&head); /* Initialize the list. */
429 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
430 SLIST_INSERT_HEAD(&head, n1, entries);
432 n2 = malloc(sizeof(struct entry)); /* Insert after. */
433 SLIST_INSERT_AFTER(n1, n2, entries);
435 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
438 n3 = SLIST_FIRST(&head);
439 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
441 /* Forward traversal. */
442 SLIST_FOREACH(np, &head, entries)
444 /* Safe forward traversal. */
445 SLIST_FOREACH_MUTABLE(np, &head, entries, np_temp) {
448 SLIST_REMOVE(&head, np, entry, entries);
452 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
453 n1 = SLIST_FIRST(&head);
454 SLIST_REMOVE_HEAD(&head, entries);
458 .Sh SINGLY-LINKED TAIL QUEUES
459 A singly-linked tail queue is headed by a structure defined by the
462 This structure contains a pair of pointers,
463 one to the first element in the tail queue and the other to
464 the last element in the tail queue.
465 The elements are singly linked for minimum space and pointer
466 manipulation overhead at the expense of O(n) removal for arbitrary
468 New elements can be added to the tail queue after an existing element,
469 at the head of the tail queue, or at the end of the tail queue.
472 structure is declared as follows:
473 .Bd -literal -offset indent
474 STAILQ_HEAD(HEADNAME, TYPE) head;
479 is the name of the structure to be defined, and
481 is the type of the elements to be linked into the tail queue.
482 A pointer to the head of the tail queue can later be declared as:
483 .Bd -literal -offset indent
484 struct HEADNAME *headp;
491 are user selectable.)
494 .Nm STAILQ_HEAD_INITIALIZER
495 evaluates to an initializer for the tail queue
500 concatenates the tail queue headed by
502 onto the end of the one headed by
504 removing all entries from the former.
508 evaluates to true if there are no items on the tail queue.
512 declares a structure that connects the elements in
517 returns the first item on the tail queue or NULL if the tail queue
522 traverses the tail queue referenced by
524 in the forward direction, assigning each element
529 .Nm STAILQ_FOREACH_MUTABLE
530 traverses the tail queue referenced by
532 in the forward direction, assigning each element
537 here it is permitted to both remove
539 as well as free it from within the loop safely without interfering with the
544 initializes the tail queue referenced by
548 .Nm STAILQ_INSERT_HEAD
549 inserts the new element
551 at the head of the tail queue.
554 .Nm STAILQ_INSERT_TAIL
555 inserts the new element
557 at the end of the tail queue.
560 .Nm STAILQ_INSERT_AFTER
561 inserts the new element
568 returns the last item on the tail queue.
569 If the tail queue is empty the return value is
574 returns the next item on the tail queue, or NULL this item is the last.
577 .Nm STAILQ_REMOVE_AFTER
578 removes the element after
580 from the tail queue. Unlike
582 this macro does not traverse the entire tail queue.
585 .Nm STAILQ_REMOVE_HEAD
586 removes the element at the head of the tail queue.
587 For optimum efficiency,
588 elements being removed from the head of the tail queue should
589 use this macro explicitly rather than the generic
598 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
600 STAILQ_HEAD(stailhead, entry) head =
601 STAILQ_HEAD_INITIALIZER(head);
602 struct stailhead *headp; /* Singly-linked tail queue head. */
605 STAILQ_ENTRY(entry) entries; /* Tail queue. */
607 } *n1, *n2, *n3, *np;
609 STAILQ_INIT(&head); /* Initialize the queue. */
611 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
612 STAILQ_INSERT_HEAD(&head, n1, entries);
614 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
615 STAILQ_INSERT_TAIL(&head, n1, entries);
617 n2 = malloc(sizeof(struct entry)); /* Insert after. */
618 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
620 STAILQ_REMOVE(&head, n2, entry, entries);
622 /* Deletion from the head. */
623 n3 = STAILQ_FIRST(&head);
624 STAILQ_REMOVE_HEAD(&head, entries);
626 /* Forward traversal. */
627 STAILQ_FOREACH(np, &head, entries)
629 /* Safe forward traversal. */
630 STAILQ_FOREACH_MUTABLE(np, &head, entries, np_temp) {
633 STAILQ_REMOVE(&head, np, entry, entries);
636 /* TailQ Deletion. */
637 while (!STAILQ_EMPTY(&head)) {
638 n1 = STAILQ_FIRST(&head);
639 STAILQ_REMOVE_HEAD(&head, entries);
642 /* Faster TailQ Deletion. */
643 n1 = STAILQ_FIRST(&head);
645 n2 = STAILQ_NEXT(n1, entries);
652 A list is headed by a structure defined by the
655 This structure contains a single pointer to the first element
657 The elements are doubly linked so that an arbitrary element can be
658 removed without traversing the list.
659 New elements can be added to the list after an existing element,
660 before an existing element, or at the head of the list.
663 structure is declared as follows:
664 .Bd -literal -offset indent
665 LIST_HEAD(HEADNAME, TYPE) head;
670 is the name of the structure to be defined, and
672 is the type of the elements to be linked into the list.
673 A pointer to the head of the list can later be declared as:
674 .Bd -literal -offset indent
675 struct HEADNAME *headp;
682 are user selectable.)
685 .Nm LIST_HEAD_INITIALIZER
686 evaluates to an initializer for the list
691 evaluates to true if there are no elements in the list.
695 declares a structure that connects the elements in
700 returns the first element in the list or NULL if the list
705 traverses the list referenced by
707 in the forward direction, assigning each element in turn to
711 .Nm LIST_FOREACH_MUTABLE
712 traverses the list referenced by
714 in the forward direction, assigning each element in turn to
718 here it is permitted to both remove
720 as well as free it from within the loop safely without interfering with the
725 initializes the list referenced by
730 inserts the new element
732 at the head of the list.
735 .Nm LIST_INSERT_AFTER
736 inserts the new element
742 .Nm LIST_INSERT_BEFORE
743 inserts the new element
750 returns the next element in the list, or NULL if this is the last.
759 LIST_HEAD(listhead, entry) head =
760 LIST_HEAD_INITIALIZER(head);
761 struct listhead *headp; /* List head. */
764 LIST_ENTRY(entry) entries; /* List. */
766 } *n1, *n2, *n3, *np, *np_temp;
768 LIST_INIT(&head); /* Initialize the list. */
770 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
771 LIST_INSERT_HEAD(&head, n1, entries);
773 n2 = malloc(sizeof(struct entry)); /* Insert after. */
774 LIST_INSERT_AFTER(n1, n2, entries);
776 n3 = malloc(sizeof(struct entry)); /* Insert before. */
777 LIST_INSERT_BEFORE(n2, n3, entries);
779 LIST_REMOVE(n2, entries); /* Deletion. */
781 /* Forward traversal. */
782 LIST_FOREACH(np, &head, entries)
785 /* Safe forward traversal. */
786 LIST_FOREACH_MUTABLE(np, &head, entries, np_temp) {
789 LIST_REMOVE(np, entries);
793 while (!LIST_EMPTY(&head)) { /* List Deletion. */
794 n1 = LIST_FIRST(&head);
795 LIST_REMOVE(n1, entries);
799 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
801 n2 = LIST_NEXT(n1, entries);
808 A tail queue is headed by a structure defined by the
811 This structure contains a pair of pointers,
812 one to the first element in the tail queue and the other to
813 the last element in the tail queue.
814 The elements are doubly linked so that an arbitrary element can be
815 removed without traversing the tail queue.
816 New elements can be added to the tail queue after an existing element,
817 before an existing element, at the head of the tail queue,
818 or at the end of the tail queue.
821 structure is declared as follows:
822 .Bd -literal -offset indent
823 TAILQ_HEAD(HEADNAME, TYPE) head;
828 is the name of the structure to be defined, and
830 is the type of the elements to be linked into the tail queue.
831 A pointer to the head of the tail queue can later be declared as:
832 .Bd -literal -offset indent
833 struct HEADNAME *headp;
840 are user selectable.)
843 .Nm TAILQ_HEAD_INITIALIZER
844 evaluates to an initializer for the tail queue
849 concatenates the tail queue headed by
851 onto the end of the one headed by
853 removing all entries from the former.
857 evaluates to true if there are no items on the tail queue.
861 declares a structure that connects the elements in
866 returns the first item on the tail queue or NULL if the tail queue
871 traverses the tail queue referenced by
873 in the forward direction, assigning each element in turn to
878 if the loop completes normally, or if there were no elements.
881 .Nm TAILQ_FOREACH_REVERSE
882 traverses the tail queue referenced by
884 in the reverse direction, assigning each element in turn to
888 .Nm TAILQ_FOREACH_MUTABLE
890 .Nm TAILQ_FOREACH_REVERSE_MUTABLE
891 traverse the list referenced by
893 in the forward or reverse direction respectively,
894 assigning each element in turn to
896 However, unlike their unsafe counterparts,
899 .Nm TAILQ_FOREACH_REVERSE
900 permit to both remove
902 as well as free it from within the loop safely without interfering with the
907 initializes the tail queue referenced by
911 .Nm TAILQ_INSERT_HEAD
912 inserts the new element
914 at the head of the tail queue.
917 .Nm TAILQ_INSERT_TAIL
918 inserts the new element
920 at the end of the tail queue.
923 .Nm TAILQ_INSERT_AFTER
924 inserts the new element
930 .Nm TAILQ_INSERT_BEFORE
931 inserts the new element
938 returns the last item on the tail queue.
939 If the tail queue is empty the return value is
944 returns the next item on the tail queue, or NULL if this item is the last.
948 returns the previous item on the tail queue, or NULL if this item
956 .Sh TAIL QUEUE EXAMPLE
958 TAILQ_HEAD(tailhead, entry) head =
959 TAILQ_HEAD_INITIALIZER(head);
960 struct tailhead *headp; /* Tail queue head. */
963 TAILQ_ENTRY(entry) entries; /* Tail queue. */
965 } *n1, *n2, *n3, *np;
967 TAILQ_INIT(&head); /* Initialize the queue. */
969 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
970 TAILQ_INSERT_HEAD(&head, n1, entries);
972 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
973 TAILQ_INSERT_TAIL(&head, n1, entries);
975 n2 = malloc(sizeof(struct entry)); /* Insert after. */
976 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
978 n3 = malloc(sizeof(struct entry)); /* Insert before. */
979 TAILQ_INSERT_BEFORE(n2, n3, entries);
981 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
983 /* Forward traversal. */
984 TAILQ_FOREACH(np, &head, entries)
986 /* Safe forward traversal. */
987 TAILQ_FOREACH_MUTABLE(np, &head, entries, np_temp) {
990 TAILQ_REMOVE(&head, np, entries);
993 /* Reverse traversal. */
994 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
996 /* TailQ Deletion. */
997 while (!TAILQ_EMPTY(&head)) {
998 n1 = TAILQ_FIRST(&head);
999 TAILQ_REMOVE(&head, n1, entries);
1002 /* Faster TailQ Deletion. */
1003 n1 = TAILQ_FIRST(&head);
1004 while (n1 != NULL) {
1005 n2 = TAILQ_NEXT(n1, entries);
1016 functions first appeared in