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
43 .Nm SLIST_FOREACH_SAFE ,
45 .Nm SLIST_HEAD_INITIALIZER ,
47 .Nm SLIST_INSERT_AFTER ,
48 .Nm SLIST_INSERT_HEAD ,
50 .Nm SLIST_REMOVE_AFTER ,
51 .Nm SLIST_REMOVE_HEAD ,
59 .Nm STAILQ_FOREACH_SAFE ,
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 ,
76 .Nm LIST_FOREACH_SAFE ,
78 .Nm LIST_HEAD_INITIALIZER ,
80 .Nm LIST_INSERT_AFTER ,
81 .Nm LIST_INSERT_BEFORE ,
82 .Nm LIST_INSERT_HEAD ,
91 .Nm TAILQ_FOREACH_SAFE ,
92 .Nm TAILQ_FOREACH_REVERSE ,
93 .Nm TAILQ_FOREACH_REVERSE_SAFE ,
95 .Nm TAILQ_HEAD_INITIALIZER ,
97 .Nm TAILQ_INSERT_AFTER ,
98 .Nm TAILQ_INSERT_BEFORE ,
99 .Nm TAILQ_INSERT_HEAD ,
100 .Nm TAILQ_INSERT_TAIL ,
106 .Nd implementations of singly-linked lists, singly-linked tail queues,
107 lists and tail queues
111 .Fn SLIST_EMPTY "SLIST_HEAD *head"
112 .Fn SLIST_ENTRY "TYPE"
113 .Fn SLIST_FIRST "SLIST_HEAD *head"
114 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
115 .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
116 .Fn SLIST_HEAD "HEADNAME" "TYPE"
117 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
118 .Fn SLIST_INIT "SLIST_HEAD *head"
119 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
120 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
121 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
122 .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
123 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
124 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
125 .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME"
127 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
128 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
129 .Fn STAILQ_ENTRY "TYPE"
130 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
131 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
132 .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
133 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
134 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
135 .Fn STAILQ_INIT "STAILQ_HEAD *head"
136 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
137 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
138 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
139 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
140 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
141 .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
142 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
143 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
144 .Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "STAILQ_ENTRY NAME"
146 .Fn LIST_EMPTY "LIST_HEAD *head"
147 .Fn LIST_ENTRY "TYPE"
148 .Fn LIST_FIRST "LIST_HEAD *head"
149 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
150 .Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
151 .Fn LIST_HEAD "HEADNAME" "TYPE"
152 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
153 .Fn LIST_INIT "LIST_HEAD *head"
154 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
155 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
156 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
157 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
158 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
159 .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
161 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
162 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
163 .Fn TAILQ_ENTRY "TYPE"
164 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
165 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
166 .Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
167 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
168 .Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
169 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
170 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
171 .Fn TAILQ_INIT "TAILQ_HEAD *head"
172 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
173 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
174 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
175 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
176 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
177 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
178 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
179 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
180 .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME"
183 These macros define and operate on four types of data structures:
184 singly-linked lists, singly-linked tail queues, lists, and tail queues.
185 All four structures support the following functionality:
186 .Bl -enum -compact -offset indent
188 Insertion of a new entry at the head of the list.
190 Insertion of a new entry after any element in the list.
192 O(1) removal of an entry from the head of the list.
194 Forward traversal through the list.
196 Swapping the contents of two lists.
199 Singly-linked lists are the simplest of the four data structures
200 and support only the above functionality.
201 Singly-linked lists are ideal for applications with large datasets
202 and few or no removals,
203 or for implementing a LIFO queue.
204 Singly-linked lists add the following functionality:
205 .Bl -enum -compact -offset indent
207 O(n) removal of any entry in the list.
210 Singly-linked tail queues add the following functionality:
211 .Bl -enum -compact -offset indent
213 Entries can be added at the end of a list.
215 O(n) removal of any entry in the list.
217 They may be concatenated.
220 .Bl -enum -compact -offset indent
222 All list insertions must specify the head of the list.
224 Each head entry requires two pointers rather than one.
226 Code size is about 15% greater and operations run about 20% slower
227 than singly-linked lists.
230 Singly-linked tail queues are ideal for applications with large datasets and
232 or for implementing a FIFO queue.
234 All doubly linked types of data structures (lists and tail queues)
236 .Bl -enum -compact -offset indent
238 Insertion of a new entry before any element in the list.
240 O(1) removal of any entry in the list.
243 .Bl -enum -compact -offset indent
245 Each element requires two pointers rather than one.
247 Code size and execution time of operations (except for removal) is about
248 twice that of the singly-linked data-structures.
251 Linked lists are the simplest of the doubly linked data structures and support
252 only the above functionality over singly-linked lists.
254 Tail queues add the following functionality:
255 .Bl -enum -compact -offset indent
257 Entries can be added at the end of a list.
259 They may be traversed backwards, from tail to head.
261 They may be concatenated.
264 .Bl -enum -compact -offset indent
266 All list insertions and removals must specify the head of the list.
268 Each head entry requires two pointers rather than one.
270 Code size is about 15% greater and operations run about 20% slower
271 than singly-linked lists.
274 In the macro definitions,
276 is the name of a user defined structure,
277 that must contain a field of type
287 is the name of a user defined structure that must be declared
294 See the examples below for further explanation of how these
296 .Sh SINGLY-LINKED LISTS
297 A singly-linked list is headed by a structure defined by the
300 This structure contains a single pointer to the first element
302 The elements are singly linked for minimum space and pointer manipulation
303 overhead at the expense of O(n) removal for arbitrary elements.
304 New elements can be added to the list after an existing element or
305 at the head of the list.
308 structure is declared as follows:
309 .Bd -literal -offset indent
310 SLIST_HEAD(HEADNAME, TYPE) head;
315 is the name of the structure to be defined, and
317 is the type of the elements to be linked into the list.
318 A pointer to the head of the list can later be declared as:
319 .Bd -literal -offset indent
320 struct HEADNAME *headp;
327 are user selectable.)
330 .Nm SLIST_HEAD_INITIALIZER
331 evaluates to an initializer for the list
336 evaluates to true if there are no elements in the list.
340 declares a structure that connects the elements in
345 returns the first element in the list or NULL if the list is empty.
349 traverses the list referenced by
351 in the forward direction, assigning each element in
356 .Nm SLIST_FOREACH_SAFE
357 traverses the list referenced by
359 in the forward direction, assigning each element in
364 here it is permitted to both remove
366 as well as free it from within the loop safely without interfering with the
371 initializes the list referenced by
375 .Nm SLIST_INSERT_HEAD
376 inserts the new element
378 at the head of the list.
381 .Nm SLIST_INSERT_AFTER
382 inserts the new element
389 returns the next element in the list.
392 .Nm SLIST_REMOVE_AFTER
393 removes the element after
395 from the list. Unlike
397 this macro does not traverse the entire list.
400 .Nm SLIST_REMOVE_HEAD
403 from the head of the list.
404 For optimum efficiency,
405 elements being removed from the head of the list should explicitly use
406 this macro instead of the generic
418 swaps the contents of
422 .Sh SINGLY-LINKED LIST EXAMPLE
424 SLIST_HEAD(slisthead, entry) head =
425 SLIST_HEAD_INITIALIZER(head);
426 struct slisthead *headp; /* Singly-linked List head. */
429 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
431 } *n1, *n2, *n3, *np;
433 SLIST_INIT(&head); /* Initialize the list. */
435 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
436 SLIST_INSERT_HEAD(&head, n1, entries);
438 n2 = malloc(sizeof(struct entry)); /* Insert after. */
439 SLIST_INSERT_AFTER(n1, n2, entries);
441 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
444 n3 = SLIST_FIRST(&head);
445 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
447 /* Forward traversal. */
448 SLIST_FOREACH(np, &head, entries)
450 /* Safe forward traversal. */
451 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
454 SLIST_REMOVE(&head, np, entry, entries);
458 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
459 n1 = SLIST_FIRST(&head);
460 SLIST_REMOVE_HEAD(&head, entries);
464 .Sh SINGLY-LINKED TAIL QUEUES
465 A singly-linked tail queue is headed by a structure defined by the
468 This structure contains a pair of pointers,
469 one to the first element in the tail queue and the other to
470 the last element in the tail queue.
471 The elements are singly linked for minimum space and pointer
472 manipulation overhead at the expense of O(n) removal for arbitrary
474 New elements can be added to the tail queue after an existing element,
475 at the head of the tail queue, or at the end of the tail queue.
478 structure is declared as follows:
479 .Bd -literal -offset indent
480 STAILQ_HEAD(HEADNAME, TYPE) head;
485 is the name of the structure to be defined, and
487 is the type of the elements to be linked into the tail queue.
488 A pointer to the head of the tail queue can later be declared as:
489 .Bd -literal -offset indent
490 struct HEADNAME *headp;
497 are user selectable.)
500 .Nm STAILQ_HEAD_INITIALIZER
501 evaluates to an initializer for the tail queue
506 concatenates the tail queue headed by
508 onto the end of the one headed by
510 removing all entries from the former.
514 evaluates to true if there are no items on the tail queue.
518 declares a structure that connects the elements in
523 returns the first item on the tail queue or NULL if the tail queue
528 traverses the tail queue referenced by
530 in the forward direction, assigning each element
535 .Nm STAILQ_FOREACH_SAFE
536 traverses the tail queue referenced by
538 in the forward direction, assigning each element
543 here it is permitted to both remove
545 as well as free it from within the loop safely without interfering with the
550 initializes the tail queue referenced by
554 .Nm STAILQ_INSERT_HEAD
555 inserts the new element
557 at the head of the tail queue.
560 .Nm STAILQ_INSERT_TAIL
561 inserts the new element
563 at the end of the tail queue.
566 .Nm STAILQ_INSERT_AFTER
567 inserts the new element
574 returns the last item on the tail queue.
575 If the tail queue is empty the return value is
580 returns the next item on the tail queue, or NULL this item is the last.
583 .Nm STAILQ_REMOVE_AFTER
584 removes the element after
586 from the tail queue. Unlike
588 this macro does not traverse the entire tail queue.
591 .Nm STAILQ_REMOVE_HEAD
592 removes the element at the head of the tail queue.
593 For optimum efficiency,
594 elements being removed from the head of the tail queue should
595 use this macro explicitly rather than the generic
607 swaps the contents of
611 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
613 STAILQ_HEAD(stailhead, entry) head =
614 STAILQ_HEAD_INITIALIZER(head);
615 struct stailhead *headp; /* Singly-linked tail queue head. */
618 STAILQ_ENTRY(entry) entries; /* Tail queue. */
620 } *n1, *n2, *n3, *np;
622 STAILQ_INIT(&head); /* Initialize the queue. */
624 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
625 STAILQ_INSERT_HEAD(&head, n1, entries);
627 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
628 STAILQ_INSERT_TAIL(&head, n1, entries);
630 n2 = malloc(sizeof(struct entry)); /* Insert after. */
631 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
633 STAILQ_REMOVE(&head, n2, entry, entries);
635 /* Deletion from the head. */
636 n3 = STAILQ_FIRST(&head);
637 STAILQ_REMOVE_HEAD(&head, entries);
639 /* Forward traversal. */
640 STAILQ_FOREACH(np, &head, entries)
642 /* Safe forward traversal. */
643 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
646 STAILQ_REMOVE(&head, np, entry, entries);
649 /* TailQ Deletion. */
650 while (!STAILQ_EMPTY(&head)) {
651 n1 = STAILQ_FIRST(&head);
652 STAILQ_REMOVE_HEAD(&head, entries);
655 /* Faster TailQ Deletion. */
656 n1 = STAILQ_FIRST(&head);
658 n2 = STAILQ_NEXT(n1, entries);
665 A list is headed by a structure defined by the
668 This structure contains a single pointer to the first element
670 The elements are doubly linked so that an arbitrary element can be
671 removed without traversing the list.
672 New elements can be added to the list after an existing element,
673 before an existing element, or at the head of the list.
676 structure is declared as follows:
677 .Bd -literal -offset indent
678 LIST_HEAD(HEADNAME, TYPE) head;
683 is the name of the structure to be defined, and
685 is the type of the elements to be linked into the list.
686 A pointer to the head of the list can later be declared as:
687 .Bd -literal -offset indent
688 struct HEADNAME *headp;
695 are user selectable.)
698 .Nm LIST_HEAD_INITIALIZER
699 evaluates to an initializer for the list
704 evaluates to true if there are no elements in the list.
708 declares a structure that connects the elements in
713 returns the first element in the list or NULL if the list
718 traverses the list referenced by
720 in the forward direction, assigning each element in turn to
724 .Nm LIST_FOREACH_SAFE
725 traverses the list referenced by
727 in the forward direction, assigning each element in turn to
731 here it is permitted to both remove
733 as well as free it from within the loop safely without interfering with the
738 initializes the list referenced by
743 inserts the new element
745 at the head of the list.
748 .Nm LIST_INSERT_AFTER
749 inserts the new element
755 .Nm LIST_INSERT_BEFORE
756 inserts the new element
763 returns the next element in the list, or NULL if this is the last.
773 swaps the contents of
779 LIST_HEAD(listhead, entry) head =
780 LIST_HEAD_INITIALIZER(head);
781 struct listhead *headp; /* List head. */
784 LIST_ENTRY(entry) entries; /* List. */
786 } *n1, *n2, *n3, *np, *np_temp;
788 LIST_INIT(&head); /* Initialize the list. */
790 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
791 LIST_INSERT_HEAD(&head, n1, entries);
793 n2 = malloc(sizeof(struct entry)); /* Insert after. */
794 LIST_INSERT_AFTER(n1, n2, entries);
796 n3 = malloc(sizeof(struct entry)); /* Insert before. */
797 LIST_INSERT_BEFORE(n2, n3, entries);
799 LIST_REMOVE(n2, entries); /* Deletion. */
801 /* Forward traversal. */
802 LIST_FOREACH(np, &head, entries)
805 /* Safe forward traversal. */
806 LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
809 LIST_REMOVE(np, entries);
813 while (!LIST_EMPTY(&head)) { /* List Deletion. */
814 n1 = LIST_FIRST(&head);
815 LIST_REMOVE(n1, entries);
819 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
821 n2 = LIST_NEXT(n1, entries);
828 A tail queue is headed by a structure defined by the
831 This structure contains a pair of pointers,
832 one to the first element in the tail queue and the other to
833 the last element in the tail queue.
834 The elements are doubly linked so that an arbitrary element can be
835 removed without traversing the tail queue.
836 New elements can be added to the tail queue after an existing element,
837 before an existing element, at the head of the tail queue,
838 or at the end of the tail queue.
841 structure is declared as follows:
842 .Bd -literal -offset indent
843 TAILQ_HEAD(HEADNAME, TYPE) head;
848 is the name of the structure to be defined, and
850 is the type of the elements to be linked into the tail queue.
851 A pointer to the head of the tail queue can later be declared as:
852 .Bd -literal -offset indent
853 struct HEADNAME *headp;
860 are user selectable.)
863 .Nm TAILQ_HEAD_INITIALIZER
864 evaluates to an initializer for the tail queue
869 concatenates the tail queue headed by
871 onto the end of the one headed by
873 removing all entries from the former.
877 evaluates to true if there are no items on the tail queue.
881 declares a structure that connects the elements in
886 returns the first item on the tail queue or NULL if the tail queue
891 traverses the tail queue referenced by
893 in the forward direction, assigning each element in turn to
898 if the loop completes normally, or if there were no elements.
901 .Nm TAILQ_FOREACH_REVERSE
902 traverses the tail queue referenced by
904 in the reverse direction, assigning each element in turn to
908 .Nm TAILQ_FOREACH_SAFE
910 .Nm TAILQ_FOREACH_REVERSE_SAFE
911 traverse the list referenced by
913 in the forward or reverse direction respectively,
914 assigning each element in turn to
916 However, unlike their unsafe counterparts,
919 .Nm TAILQ_FOREACH_REVERSE
920 permit to both remove
922 as well as free it from within the loop safely without interfering with the
927 initializes the tail queue referenced by
931 .Nm TAILQ_INSERT_HEAD
932 inserts the new element
934 at the head of the tail queue.
937 .Nm TAILQ_INSERT_TAIL
938 inserts the new element
940 at the end of the tail queue.
943 .Nm TAILQ_INSERT_AFTER
944 inserts the new element
950 .Nm TAILQ_INSERT_BEFORE
951 inserts the new element
958 returns the last item on the tail queue.
959 If the tail queue is empty the return value is
964 returns the next item on the tail queue, or NULL if this item is the last.
968 returns the previous item on the tail queue, or NULL if this item
979 swaps the contents of
983 .Sh TAIL QUEUE EXAMPLE
985 TAILQ_HEAD(tailhead, entry) head =
986 TAILQ_HEAD_INITIALIZER(head);
987 struct tailhead *headp; /* Tail queue head. */
990 TAILQ_ENTRY(entry) entries; /* Tail queue. */
992 } *n1, *n2, *n3, *np;
994 TAILQ_INIT(&head); /* Initialize the queue. */
996 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
997 TAILQ_INSERT_HEAD(&head, n1, entries);
999 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
1000 TAILQ_INSERT_TAIL(&head, n1, entries);
1002 n2 = malloc(sizeof(struct entry)); /* Insert after. */
1003 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
1005 n3 = malloc(sizeof(struct entry)); /* Insert before. */
1006 TAILQ_INSERT_BEFORE(n2, n3, entries);
1008 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
1010 /* Forward traversal. */
1011 TAILQ_FOREACH(np, &head, entries)
1013 /* Safe forward traversal. */
1014 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
1017 TAILQ_REMOVE(&head, np, entries);
1020 /* Reverse traversal. */
1021 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
1023 /* TailQ Deletion. */
1024 while (!TAILQ_EMPTY(&head)) {
1025 n1 = TAILQ_FIRST(&head);
1026 TAILQ_REMOVE(&head, n1, entries);
1029 /* Faster TailQ Deletion. */
1030 n1 = TAILQ_FIRST(&head);
1031 while (n1 != NULL) {
1032 n2 = TAILQ_NEXT(n1, entries);
1043 functions first appeared in