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 ,
58 .Nm STAILQ_FOREACH_SAFE ,
60 .Nm STAILQ_HEAD_INITIALIZER ,
62 .Nm STAILQ_INSERT_AFTER ,
63 .Nm STAILQ_INSERT_HEAD ,
64 .Nm STAILQ_INSERT_TAIL ,
67 .Nm STAILQ_REMOVE_AFTER ,
68 .Nm STAILQ_REMOVE_HEAD ,
74 .Nm LIST_FOREACH_SAFE ,
76 .Nm LIST_HEAD_INITIALIZER ,
78 .Nm LIST_INSERT_AFTER ,
79 .Nm LIST_INSERT_BEFORE ,
80 .Nm LIST_INSERT_HEAD ,
88 .Nm TAILQ_FOREACH_SAFE ,
89 .Nm TAILQ_FOREACH_REVERSE ,
90 .Nm TAILQ_FOREACH_REVERSE_SAFE ,
92 .Nm TAILQ_HEAD_INITIALIZER ,
94 .Nm TAILQ_INSERT_AFTER ,
95 .Nm TAILQ_INSERT_BEFORE ,
96 .Nm TAILQ_INSERT_HEAD ,
97 .Nm TAILQ_INSERT_TAIL ,
102 .Nd implementations of singly-linked lists, singly-linked tail queues,
103 lists and tail queues
107 .Fn SLIST_EMPTY "SLIST_HEAD *head"
108 .Fn SLIST_ENTRY "TYPE"
109 .Fn SLIST_FIRST "SLIST_HEAD *head"
110 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
111 .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
112 .Fn SLIST_HEAD "HEADNAME" "TYPE"
113 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
114 .Fn SLIST_INIT "SLIST_HEAD *head"
115 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
116 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
117 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
118 .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
119 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
120 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
122 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
123 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
124 .Fn STAILQ_ENTRY "TYPE"
125 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
126 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
127 .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
128 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
129 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
130 .Fn STAILQ_INIT "STAILQ_HEAD *head"
131 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
132 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
133 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
134 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
135 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
136 .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
137 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
138 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
140 .Fn LIST_EMPTY "LIST_HEAD *head"
141 .Fn LIST_ENTRY "TYPE"
142 .Fn LIST_FIRST "LIST_HEAD *head"
143 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
144 .Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
145 .Fn LIST_HEAD "HEADNAME" "TYPE"
146 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
147 .Fn LIST_INIT "LIST_HEAD *head"
148 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
149 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
150 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
151 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
152 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
154 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
155 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
156 .Fn TAILQ_ENTRY "TYPE"
157 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
158 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
159 .Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
160 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
161 .Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
162 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
163 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
164 .Fn TAILQ_INIT "TAILQ_HEAD *head"
165 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
166 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
167 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
168 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
169 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
170 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
171 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
172 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
175 These macros define and operate on four types of data structures:
176 singly-linked lists, singly-linked tail queues, lists, and tail queues.
177 All four structures support the following functionality:
178 .Bl -enum -compact -offset indent
180 Insertion of a new entry at the head of the list.
182 Insertion of a new entry after any element in the list.
184 O(1) removal of an entry from the head of the list.
186 Forward traversal through the list.
189 Singly-linked lists are the simplest of the four data structures
190 and support only the above functionality.
191 Singly-linked lists are ideal for applications with large datasets
192 and few or no removals,
193 or for implementing a LIFO queue.
194 Singly-linked lists add the following functionality:
195 .Bl -enum -compact -offset indent
197 O(n) removal of any entry in the list.
200 Singly-linked tail queues add the following functionality:
201 .Bl -enum -compact -offset indent
203 Entries can be added at the end of a list.
205 O(n) removal of any entry in the list.
207 They may be concatenated.
210 .Bl -enum -compact -offset indent
212 All list insertions must specify the head of the list.
214 Each head entry requires two pointers rather than one.
216 Code size is about 15% greater and operations run about 20% slower
217 than singly-linked lists.
220 Singly-linked tailqs are ideal for applications with large datasets and
222 or for implementing a FIFO queue.
224 All doubly linked types of data structures (lists and tail queues)
226 .Bl -enum -compact -offset indent
228 Insertion of a new entry before any element in the list.
230 O(1) removal of any entry in the list.
233 .Bl -enum -compact -offset indent
235 Each element requires two pointers rather than one.
237 Code size and execution time of operations (except for removal) is about
238 twice that of the singly-linked data-structures.
241 Linked lists are the simplest of the doubly linked data structures and support
242 only the above functionality over singly-linked lists.
244 Tail queues add the following functionality:
245 .Bl -enum -compact -offset indent
247 Entries can be added at the end of a list.
249 They may be traversed backwards, from tail to head.
251 They may be concatenated.
254 .Bl -enum -compact -offset indent
256 All list insertions and removals must specify the head of the list.
258 Each head entry requires two pointers rather than one.
260 Code size is about 15% greater and operations run about 20% slower
261 than singly-linked lists.
264 In the macro definitions,
266 is the name of a user defined structure,
267 that must contain a field of type
277 is the name of a user defined structure that must be declared
284 See the examples below for further explanation of how these
286 .Sh SINGLY-LINKED LISTS
287 A singly-linked list is headed by a structure defined by the
290 This structure contains a single pointer to the first element
292 The elements are singly linked for minimum space and pointer manipulation
293 overhead at the expense of O(n) removal for arbitrary elements.
294 New elements can be added to the list after an existing element or
295 at the head of the list.
298 structure is declared as follows:
299 .Bd -literal -offset indent
300 SLIST_HEAD(HEADNAME, TYPE) head;
305 is the name of the structure to be defined, and
307 is the type of the elements to be linked into the list.
308 A pointer to the head of the list can later be declared as:
309 .Bd -literal -offset indent
310 struct HEADNAME *headp;
317 are user selectable.)
320 .Nm SLIST_HEAD_INITIALIZER
321 evaluates to an initializer for the list
326 evaluates to true if there are no elements in the list.
330 declares a structure that connects the elements in
335 returns the first element in the list or NULL if the list is empty.
339 traverses the list referenced by
341 in the forward direction, assigning each element in
346 .Nm SLIST_FOREACH_SAFE
347 traverses the list referenced by
349 in the forward direction, assigning each element in
354 here it is permitted to both remove
356 as well as free it from within the loop safely without interfering with the
361 initializes the list referenced by
365 .Nm SLIST_INSERT_HEAD
366 inserts the new element
368 at the head of the list.
371 .Nm SLIST_INSERT_AFTER
372 inserts the new element
379 returns the next element in the list.
382 .Nm SLIST_REMOVE_AFTER
383 removes the element after
385 from the list. Unlike
387 this macro does not traverse the entire list.
390 .Nm SLIST_REMOVE_HEAD
393 from the head of the list.
394 For optimum efficiency,
395 elements being removed from the head of the list should explicitly use
396 this macro instead of the generic
405 .Sh SINGLY-LINKED LIST EXAMPLE
407 SLIST_HEAD(slisthead, entry) head =
408 SLIST_HEAD_INITIALIZER(head);
409 struct slisthead *headp; /* Singly-linked List head. */
412 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
414 } *n1, *n2, *n3, *np;
416 SLIST_INIT(&head); /* Initialize the list. */
418 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
419 SLIST_INSERT_HEAD(&head, n1, entries);
421 n2 = malloc(sizeof(struct entry)); /* Insert after. */
422 SLIST_INSERT_AFTER(n1, n2, entries);
424 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
427 n3 = SLIST_FIRST(&head);
428 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
430 /* Forward traversal. */
431 SLIST_FOREACH(np, &head, entries)
433 /* Safe forward traversal. */
434 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
437 SLIST_REMOVE(&head, np, entry, entries);
441 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
442 n1 = SLIST_FIRST(&head);
443 SLIST_REMOVE_HEAD(&head, entries);
447 .Sh SINGLY-LINKED TAIL QUEUES
448 A singly-linked tail queue is headed by a structure defined by the
451 This structure contains a pair of pointers,
452 one to the first element in the tail queue and the other to
453 the last element in the tail queue.
454 The elements are singly linked for minimum space and pointer
455 manipulation overhead at the expense of O(n) removal for arbitrary
457 New elements can be added to the tail queue after an existing element,
458 at the head of the tail queue, or at the end of the tail queue.
461 structure is declared as follows:
462 .Bd -literal -offset indent
463 STAILQ_HEAD(HEADNAME, TYPE) head;
468 is the name of the structure to be defined, and
470 is the type of the elements to be linked into the tail queue.
471 A pointer to the head of the tail queue can later be declared as:
472 .Bd -literal -offset indent
473 struct HEADNAME *headp;
480 are user selectable.)
483 .Nm STAILQ_HEAD_INITIALIZER
484 evaluates to an initializer for the tail queue
489 concatenates the tail queue headed by
491 onto the end of the one headed by
493 removing all entries from the former.
497 evaluates to true if there are no items on the tail queue.
501 declares a structure that connects the elements in
506 returns the first item on the tail queue or NULL if the tail queue
511 traverses the tail queue referenced by
513 in the forward direction, assigning each element
518 .Nm STAILQ_FOREACH_SAFE
519 traverses the tail queue referenced by
521 in the forward direction, assigning each element
526 here it is permitted to both remove
528 as well as free it from within the loop safely without interfering with the
533 initializes the tail queue referenced by
537 .Nm STAILQ_INSERT_HEAD
538 inserts the new element
540 at the head of the tail queue.
543 .Nm STAILQ_INSERT_TAIL
544 inserts the new element
546 at the end of the tail queue.
549 .Nm STAILQ_INSERT_AFTER
550 inserts the new element
557 returns the last item on the tail queue.
558 If the tail queue is empty the return value is
563 returns the next item on the tail queue, or NULL this item is the last.
566 .Nm STAILQ_REMOVE_AFTER
567 removes the element after
569 from the tail queue. Unlike
571 this macro does not traverse the entire tail queue.
574 .Nm STAILQ_REMOVE_HEAD
575 removes the element at the head of the tail queue.
576 For optimum efficiency,
577 elements being removed from the head of the tail queue should
578 use this macro explicitly rather than the generic
587 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
589 STAILQ_HEAD(stailhead, entry) head =
590 STAILQ_HEAD_INITIALIZER(head);
591 struct stailhead *headp; /* Singly-linked tail queue head. */
594 STAILQ_ENTRY(entry) entries; /* Tail queue. */
596 } *n1, *n2, *n3, *np;
598 STAILQ_INIT(&head); /* Initialize the queue. */
600 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
601 STAILQ_INSERT_HEAD(&head, n1, entries);
603 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
604 STAILQ_INSERT_TAIL(&head, n1, entries);
606 n2 = malloc(sizeof(struct entry)); /* Insert after. */
607 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
609 STAILQ_REMOVE(&head, n2, entry, entries);
611 /* Deletion from the head. */
612 n3 = STAILQ_FIRST(&head);
613 STAILQ_REMOVE_HEAD(&head, entries);
615 /* Forward traversal. */
616 STAILQ_FOREACH(np, &head, entries)
618 /* Safe forward traversal. */
619 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
622 STAILQ_REMOVE(&head, np, entry, entries);
625 /* TailQ Deletion. */
626 while (!STAILQ_EMPTY(&head)) {
627 n1 = STAILQ_FIRST(&head);
628 STAILQ_REMOVE_HEAD(&head, entries);
631 /* Faster TailQ Deletion. */
632 n1 = STAILQ_FIRST(&head);
634 n2 = STAILQ_NEXT(n1, entries);
641 A list is headed by a structure defined by the
644 This structure contains a single pointer to the first element
646 The elements are doubly linked so that an arbitrary element can be
647 removed without traversing the list.
648 New elements can be added to the list after an existing element,
649 before an existing element, or at the head of the list.
652 structure is declared as follows:
653 .Bd -literal -offset indent
654 LIST_HEAD(HEADNAME, TYPE) head;
659 is the name of the structure to be defined, and
661 is the type of the elements to be linked into the list.
662 A pointer to the head of the list can later be declared as:
663 .Bd -literal -offset indent
664 struct HEADNAME *headp;
671 are user selectable.)
674 .Nm LIST_HEAD_INITIALIZER
675 evaluates to an initializer for the list
680 evaluates to true if there are no elements in the list.
684 declares a structure that connects the elements in
689 returns the first element in the list or NULL if the list
694 traverses the list referenced by
696 in the forward direction, assigning each element in turn to
700 .Nm LIST_FOREACH_SAFE
701 traverses the list referenced by
703 in the forward direction, assigning each element in turn to
707 here it is permitted to both remove
709 as well as free it from within the loop safely without interfering with the
714 initializes the list referenced by
719 inserts the new element
721 at the head of the list.
724 .Nm LIST_INSERT_AFTER
725 inserts the new element
731 .Nm LIST_INSERT_BEFORE
732 inserts the new element
739 returns the next element in the list, or NULL if this is the last.
748 LIST_HEAD(listhead, entry) head =
749 LIST_HEAD_INITIALIZER(head);
750 struct listhead *headp; /* List head. */
753 LIST_ENTRY(entry) entries; /* List. */
755 } *n1, *n2, *n3, *np, *np_temp;
757 LIST_INIT(&head); /* Initialize the list. */
759 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
760 LIST_INSERT_HEAD(&head, n1, entries);
762 n2 = malloc(sizeof(struct entry)); /* Insert after. */
763 LIST_INSERT_AFTER(n1, n2, entries);
765 n3 = malloc(sizeof(struct entry)); /* Insert before. */
766 LIST_INSERT_BEFORE(n2, n3, entries);
768 LIST_REMOVE(n2, entries); /* Deletion. */
770 /* Forward traversal. */
771 LIST_FOREACH(np, &head, entries)
774 /* Safe forward traversal. */
775 LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
778 LIST_REMOVE(np, entries);
782 while (!LIST_EMPTY(&head)) { /* List Deletion. */
783 n1 = LIST_FIRST(&head);
784 LIST_REMOVE(n1, entries);
788 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
790 n2 = LIST_NEXT(n1, entries);
797 A tail queue is headed by a structure defined by the
800 This structure contains a pair of pointers,
801 one to the first element in the tail queue and the other to
802 the last element in the tail queue.
803 The elements are doubly linked so that an arbitrary element can be
804 removed without traversing the tail queue.
805 New elements can be added to the tail queue after an existing element,
806 before an existing element, at the head of the tail queue,
807 or at the end of the tail queue.
810 structure is declared as follows:
811 .Bd -literal -offset indent
812 TAILQ_HEAD(HEADNAME, TYPE) head;
817 is the name of the structure to be defined, and
819 is the type of the elements to be linked into the tail queue.
820 A pointer to the head of the tail queue can later be declared as:
821 .Bd -literal -offset indent
822 struct HEADNAME *headp;
829 are user selectable.)
832 .Nm TAILQ_HEAD_INITIALIZER
833 evaluates to an initializer for the tail queue
838 concatenates the tail queue headed by
840 onto the end of the one headed by
842 removing all entries from the former.
846 evaluates to true if there are no items on the tail queue.
850 declares a structure that connects the elements in
855 returns the first item on the tail queue or NULL if the tail queue
860 traverses the tail queue referenced by
862 in the forward direction, assigning each element in turn to
867 if the loop completes normally, or if there were no elements.
870 .Nm TAILQ_FOREACH_REVERSE
871 traverses the tail queue referenced by
873 in the reverse direction, assigning each element in turn to
877 .Nm TAILQ_FOREACH_SAFE
879 .Nm TAILQ_FOREACH_REVERSE_SAFE
880 traverse the list referenced by
882 in the forward or reverse direction respectively,
883 assigning each element in turn to
885 However, unlike their unsafe counterparts,
888 .Nm TAILQ_FOREACH_REVERSE
889 permit to both remove
891 as well as free it from within the loop safely without interfering with the
896 initializes the tail queue referenced by
900 .Nm TAILQ_INSERT_HEAD
901 inserts the new element
903 at the head of the tail queue.
906 .Nm TAILQ_INSERT_TAIL
907 inserts the new element
909 at the end of the tail queue.
912 .Nm TAILQ_INSERT_AFTER
913 inserts the new element
919 .Nm TAILQ_INSERT_BEFORE
920 inserts the new element
927 returns the last item on the tail queue.
928 If the tail queue is empty the return value is
933 returns the next item on the tail queue, or NULL if this item is the last.
937 returns the previous item on the tail queue, or NULL if this item
945 .Sh TAIL QUEUE EXAMPLE
947 TAILQ_HEAD(tailhead, entry) head =
948 TAILQ_HEAD_INITIALIZER(head);
949 struct tailhead *headp; /* Tail queue head. */
952 TAILQ_ENTRY(entry) entries; /* Tail queue. */
954 } *n1, *n2, *n3, *np;
956 TAILQ_INIT(&head); /* Initialize the queue. */
958 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
959 TAILQ_INSERT_HEAD(&head, n1, entries);
961 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
962 TAILQ_INSERT_TAIL(&head, n1, entries);
964 n2 = malloc(sizeof(struct entry)); /* Insert after. */
965 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
967 n3 = malloc(sizeof(struct entry)); /* Insert before. */
968 TAILQ_INSERT_BEFORE(n2, n3, entries);
970 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
972 /* Forward traversal. */
973 TAILQ_FOREACH(np, &head, entries)
975 /* Safe forward traversal. */
976 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
979 TAILQ_REMOVE(&head, np, entries);
982 /* Reverse traversal. */
983 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
985 /* TailQ Deletion. */
986 while (!TAILQ_EMPTY(&head)) {
987 n1 = TAILQ_FIRST(&head);
988 TAILQ_REMOVE(&head, n1, entries);
991 /* Faster TailQ Deletion. */
992 n1 = TAILQ_FIRST(&head);
994 n2 = TAILQ_NEXT(n1, entries);
1005 functions first appeared in