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 ,
46 .Nm SLIST_HEAD_INITIALIZER ,
48 .Nm SLIST_INSERT_AFTER ,
49 .Nm SLIST_INSERT_HEAD ,
51 .Nm SLIST_REMOVE_HEAD ,
52 .Nm SLIST_REMOVE_NEXT ,
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_HEAD ,
69 .Nm STAILQ_REMOVE_NEXT ,
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_HEAD "HEADNAME" "TYPE"
114 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
115 .Fn SLIST_INIT "SLIST_HEAD *head"
116 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
117 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
118 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
119 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
120 .Fn SLIST_REMOVE_NEXT "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
121 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
123 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
124 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
125 .Fn STAILQ_ENTRY "TYPE"
126 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
127 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
128 .Fn STAILQ_FOREACH_MUTABLE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
129 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
130 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
131 .Fn STAILQ_INIT "STAILQ_HEAD *head"
132 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
133 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
134 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
135 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
136 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
137 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
138 .Fn STAILQ_REMOVE_NEXT "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
139 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
141 .Fn LIST_EMPTY "LIST_HEAD *head"
142 .Fn LIST_ENTRY "TYPE"
143 .Fn LIST_FIRST "LIST_HEAD *head"
144 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
145 .Fn LIST_FOREACH_MUTABLE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
146 .Fn LIST_HEAD "HEADNAME" "TYPE"
147 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
148 .Fn LIST_INIT "LIST_HEAD *head"
149 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
150 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
151 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
152 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
153 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
155 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
156 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
157 .Fn TAILQ_ENTRY "TYPE"
158 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
159 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
160 .Fn TAILQ_FOREACH_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
161 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
162 .Fn TAILQ_FOREACH_REVERSE_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
163 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
164 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
165 .Fn TAILQ_INIT "TAILQ_HEAD *head"
166 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
167 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
168 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
169 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
170 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
171 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
172 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
173 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
176 These macros define and operate on four types of data structures:
177 singly-linked lists, singly-linked tail queues, lists, and tail queues.
178 All four structures support the following functionality:
179 .Bl -enum -compact -offset indent
181 Insertion of a new entry at the head of the list.
183 Insertion of a new entry after any element in the list.
185 O(1) removal of an entry from the head of the list.
187 Forward traversal through the list.
190 O(n) removal of any entry in 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 elements 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
363 initializes the list referenced by
367 .Nm SLIST_INSERT_HEAD
368 inserts the new element
370 at the head of the list.
373 .Nm SLIST_INSERT_AFTER
374 inserts the new element
381 returns the next element in the list.
384 .Nm SLIST_REMOVE_HEAD
387 from the head of the list.
388 For optimum efficiency,
389 elements being removed from the head of the list should explicitly use
390 this macro instead of the generic
395 .Nm SLIST_REMOVE_NEXT
396 removes the element after
398 from the list. Unlike
400 this macro does not traverse the entire list.
407 .Sh SINGLY-LINKED LIST EXAMPLE
409 SLIST_HEAD(slisthead, entry) head =
410 SLIST_HEAD_INITIALIZER(head);
411 struct slisthead *headp; /* Singly-linked List head. */
414 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
416 } *n1, *n2, *n3, *np;
418 SLIST_INIT(&head); /* Initialize the list. */
420 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
421 SLIST_INSERT_HEAD(&head, n1, entries);
423 n2 = malloc(sizeof(struct entry)); /* Insert after. */
424 SLIST_INSERT_AFTER(n1, n2, entries);
426 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
429 n3 = SLIST_FIRST(&head);
430 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
432 /* Forward traversal. */
433 SLIST_FOREACH(np, &head, entries)
435 /* Safe forward traversal. */
436 SLIST_FOREACH_MUTABLE(np, &head, entries, np_temp) {
439 SLIST_REMOVE(&head, np, entry, entries);
443 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
444 n1 = SLIST_FIRST(&head);
445 SLIST_REMOVE_HEAD(&head, entries);
449 .Sh SINGLY-LINKED TAIL QUEUES
450 A singly-linked tail queue is headed by a structure defined by the
453 This structure contains a pair of pointers,
454 one to the first element in the tail queue and the other to
455 the last element in the tail queue.
456 The elements are singly linked for minimum space and pointer
457 manipulation overhead at the expense of O(n) removal for arbitrary
459 New elements can be added to the tail queue after an existing element,
460 at the head of the tail queue, or at the end of the tail queue.
463 structure is declared as follows:
464 .Bd -literal -offset indent
465 STAILQ_HEAD(HEADNAME, TYPE) head;
470 is the name of the structure to be defined, and
472 is the type of the elements to be linked into the tail queue.
473 A pointer to the head of the tail queue can later be declared as:
474 .Bd -literal -offset indent
475 struct HEADNAME *headp;
482 are user selectable.)
485 .Nm STAILQ_HEAD_INITIALIZER
486 evaluates to an initializer for the tail queue
491 concatenates the tail queue headed by
493 onto the end of the one headed by
495 removing all entries from the former.
499 evaluates to true if there are no items on the tail queue.
503 declares a structure that connects the elements in
508 returns the first item on the tail queue or NULL if the tail queue
513 traverses the tail queue referenced by
515 in the forward direction, assigning each element
520 .Nm STAILQ_FOREACH_MUTABLE
521 traverses the tail queue referenced by
523 in the forward direction, assigning each element
528 here it is permitted to both remove
530 as well as free it from within the loop safely without interfering with the
535 initializes the tail queue referenced by
539 .Nm STAILQ_INSERT_HEAD
540 inserts the new element
542 at the head of the tail queue.
545 .Nm STAILQ_INSERT_TAIL
546 inserts the new element
548 at the end of the tail queue.
551 .Nm STAILQ_INSERT_AFTER
552 inserts the new element
559 returns the last item on the tail queue.
560 If the tail queue is empty the return value is
565 returns the next item on the tail queue, or NULL this item is the last.
568 .Nm STAILQ_REMOVE_HEAD
569 removes the element at the head of the tail queue.
570 For optimum efficiency,
571 elements being removed from the head of the tail queue should
572 use this macro explicitly rather than the generic
577 .Nm STAILQ_REMOVE_NEXT
578 removes the element after
580 from the tail queue. Unlike
582 this macro does not traverse the entire tail queue.
589 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
591 STAILQ_HEAD(stailhead, entry) head =
592 STAILQ_HEAD_INITIALIZER(head);
593 struct stailhead *headp; /* Singly-linked tail queue head. */
596 STAILQ_ENTRY(entry) entries; /* Tail queue. */
598 } *n1, *n2, *n3, *np;
600 STAILQ_INIT(&head); /* Initialize the queue. */
602 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
603 STAILQ_INSERT_HEAD(&head, n1, entries);
605 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
606 STAILQ_INSERT_TAIL(&head, n1, entries);
608 n2 = malloc(sizeof(struct entry)); /* Insert after. */
609 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
611 STAILQ_REMOVE(&head, n2, entry, entries);
613 /* Deletion from the head. */
614 n3 = STAILQ_FIRST(&head);
615 STAILQ_REMOVE_HEAD(&head, entries);
617 /* Forward traversal. */
618 STAILQ_FOREACH(np, &head, entries)
620 /* Safe forward traversal. */
621 STAILQ_FOREACH_MUTABLE(np, &head, entries, np_temp) {
624 STAILQ_REMOVE(&head, np, entry, entries);
627 /* TailQ Deletion. */
628 while (!STAILQ_EMPTY(&head)) {
629 n1 = STAILQ_FIRST(&head);
630 STAILQ_REMOVE_HEAD(&head, entries);
633 /* Faster TailQ Deletion. */
634 n1 = STAILQ_FIRST(&head);
636 n2 = STAILQ_NEXT(n1, entries);
643 A list is headed by a structure defined by the
646 This structure contains a single pointer to the first element
648 The elements are doubly linked so that an arbitrary element can be
649 removed without traversing the list.
650 New elements can be added to the list after an existing element,
651 before an existing element, or at the head of the list.
654 structure is declared as follows:
655 .Bd -literal -offset indent
656 LIST_HEAD(HEADNAME, TYPE) head;
661 is the name of the structure to be defined, and
663 is the type of the elements to be linked into the list.
664 A pointer to the head of the list can later be declared as:
665 .Bd -literal -offset indent
666 struct HEADNAME *headp;
673 are user selectable.)
676 .Nm LIST_HEAD_INITIALIZER
677 evaluates to an initializer for the list
682 evaluates to true if there are no elements in the list.
686 declares a structure that connects the elements in
691 returns the first element in the list or NULL if the list
696 traverses the list referenced by
698 in the forward direction, assigning each element in turn to
702 .Nm LIST_FOREACH_MUTABLE
703 traverses the list referenced by
705 in the forward direction, assigning each element in turn to
709 here it is permitted to both remove
711 as well as free it from within the loop safely without interfering with the
716 initializes the list referenced by
721 inserts the new element
723 at the head of the list.
726 .Nm LIST_INSERT_AFTER
727 inserts the new element
733 .Nm LIST_INSERT_BEFORE
734 inserts the new element
741 returns the next element in the list, or NULL if this is the last.
750 LIST_HEAD(listhead, entry) head =
751 LIST_HEAD_INITIALIZER(head);
752 struct listhead *headp; /* List head. */
755 LIST_ENTRY(entry) entries; /* List. */
757 } *n1, *n2, *n3, *np, *np_temp;
759 LIST_INIT(&head); /* Initialize the list. */
761 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
762 LIST_INSERT_HEAD(&head, n1, entries);
764 n2 = malloc(sizeof(struct entry)); /* Insert after. */
765 LIST_INSERT_AFTER(n1, n2, entries);
767 n3 = malloc(sizeof(struct entry)); /* Insert before. */
768 LIST_INSERT_BEFORE(n2, n3, entries);
770 LIST_REMOVE(n2, entries); /* Deletion. */
772 /* Forward traversal. */
773 LIST_FOREACH(np, &head, entries)
776 /* Safe forward traversal. */
777 LIST_FOREACH_MUTABLE(np, &head, entries, np_temp) {
780 LIST_REMOVE(np, entries);
784 while (!LIST_EMPTY(&head)) { /* List Deletion. */
785 n1 = LIST_FIRST(&head);
786 LIST_REMOVE(n1, entries);
790 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
792 n2 = LIST_NEXT(n1, entries);
799 A tail queue is headed by a structure defined by the
802 This structure contains a pair of pointers,
803 one to the first element in the tail queue and the other to
804 the last element in the tail queue.
805 The elements are doubly linked so that an arbitrary element can be
806 removed without traversing the tail queue.
807 New elements can be added to the tail queue after an existing element,
808 before an existing element, at the head of the tail queue,
809 or at the end of the tail queue.
812 structure is declared as follows:
813 .Bd -literal -offset indent
814 TAILQ_HEAD(HEADNAME, TYPE) head;
819 is the name of the structure to be defined, and
821 is the type of the elements to be linked into the tail queue.
822 A pointer to the head of the tail queue can later be declared as:
823 .Bd -literal -offset indent
824 struct HEADNAME *headp;
831 are user selectable.)
834 .Nm TAILQ_HEAD_INITIALIZER
835 evaluates to an initializer for the tail queue
840 concatenates the tail queue headed by
842 onto the end of the one headed by
844 removing all entries from the former.
848 evaluates to true if there are no items on the tail queue.
852 declares a structure that connects the elements in
857 returns the first item on the tail queue or NULL if the tail queue
862 traverses the tail queue referenced by
864 in the forward direction, assigning each element in turn to
869 if the loop completes normally, or if there were no elements.
872 .Nm TAILQ_FOREACH_REVERSE
873 traverses the tail queue referenced by
875 in the reverse direction, assigning each element in turn to
879 .Nm TAILQ_FOREACH_MUTABLE
881 .Nm TAILQ_FOREACH_REVERSE_MUTABLE
882 traverse the list referenced by
884 in the forward or reverse direction respectively,
885 assigning each element in turn to
887 However, unlike their unsafe counterparts,
890 .Nm TAILQ_FOREACH_REVERSE
891 permit to both remove
893 as well as free it from within the loop safely without interfering with the
898 initializes the tail queue referenced by
902 .Nm TAILQ_INSERT_HEAD
903 inserts the new element
905 at the head of the tail queue.
908 .Nm TAILQ_INSERT_TAIL
909 inserts the new element
911 at the end of the tail queue.
914 .Nm TAILQ_INSERT_AFTER
915 inserts the new element
921 .Nm TAILQ_INSERT_BEFORE
922 inserts the new element
929 returns the last item on the tail queue.
930 If the tail queue is empty the return value is
935 returns the next item on the tail queue, or NULL if this item is the last.
939 returns the previous item on the tail queue, or NULL if this item
947 .Sh TAIL QUEUE EXAMPLE
949 TAILQ_HEAD(tailhead, entry) head =
950 TAILQ_HEAD_INITIALIZER(head);
951 struct tailhead *headp; /* Tail queue head. */
954 TAILQ_ENTRY(entry) entries; /* Tail queue. */
956 } *n1, *n2, *n3, *np;
958 TAILQ_INIT(&head); /* Initialize the queue. */
960 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
961 TAILQ_INSERT_HEAD(&head, n1, entries);
963 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
964 TAILQ_INSERT_TAIL(&head, n1, entries);
966 n2 = malloc(sizeof(struct entry)); /* Insert after. */
967 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
969 n3 = malloc(sizeof(struct entry)); /* Insert before. */
970 TAILQ_INSERT_BEFORE(n2, n3, entries);
972 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
974 /* Forward traversal. */
975 TAILQ_FOREACH(np, &head, entries)
977 /* Safe forward traversal. */
978 TAILQ_FOREACH_MUTABLE(np, &head, entries, np_temp) {
981 TAILQ_REMOVE(&head, np, entries);
984 /* Reverse traversal. */
985 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
987 /* TailQ Deletion. */
988 while (!TAILQ_EMPTY(&head)) {
989 n1 = TAILQ_FIRST(&head);
990 TAILQ_REMOVE(&head, n1, entries);
993 /* Faster TailQ Deletion. */
994 n1 = TAILQ_FIRST(&head);
996 n2 = TAILQ_NEXT(n1, entries);
1005 functions first appeared in