2 .\" The Regents of the University of California. All rights reserved.
4 .\" %%%LICENSE_START(BSD_3_CLAUSE_UCB)
5 .\" Redistribution and use in source and binary forms, with or without
6 .\" modification, are permitted provided that the following conditions
8 .\" 1. Redistributions of source code must retain the above copyright
9 .\" notice, this list of conditions and the following disclaimer.
10 .\" 2. Redistributions in binary form must reproduce the above copyright
11 .\" notice, this list of conditions and the following disclaimer in the
12 .\" documentation and/or other materials provided with the distribution.
13 .\" 3. Neither the name of the University nor the names of its contributors
14 .\" may be used to endorse or promote products derived from this software
15 .\" without specific prior written permission.
17 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 .\" @(#)queue.3 8.2 (Berkeley) 1/24/94
41 .\" .Nm SLIST_FOREACH_FROM ,
42 .\" .Nm SLIST_FOREACH_SAFE ,
43 .\" .Nm SLIST_FOREACH_FROM_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_FROM ,
60 .\" .Nm STAILQ_FOREACH_SAFE ,
61 .\" .Nm STAILQ_FOREACH_FROM_SAFE ,
63 .Nm STAILQ_HEAD_INITIALIZER ,
65 .Nm STAILQ_INSERT_AFTER ,
66 .Nm STAILQ_INSERT_HEAD ,
67 .Nm STAILQ_INSERT_TAIL ,
70 .\" .Nm STAILQ_REMOVE_AFTER ,
71 .Nm STAILQ_REMOVE_HEAD ,
78 .\" .Nm LIST_FOREACH_FROM ,
79 .\" .Nm LIST_FOREACH_SAFE ,
80 .\" .Nm LIST_FOREACH_FROM_SAFE ,
82 .Nm LIST_HEAD_INITIALIZER ,
84 .Nm LIST_INSERT_AFTER ,
85 .Nm LIST_INSERT_BEFORE ,
86 .Nm LIST_INSERT_HEAD ,
96 .\" .Nm TAILQ_FOREACH_FROM ,
97 .\" .Nm TAILQ_FOREACH_SAFE ,
98 .\" .Nm TAILQ_FOREACH_FROM_SAFE ,
99 .Nm TAILQ_FOREACH_REVERSE ,
100 .\" .Nm TAILQ_FOREACH_REVERSE_FROM ,
101 .\" .Nm TAILQ_FOREACH_REVERSE_SAFE ,
102 .\" .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE ,
104 .Nm TAILQ_HEAD_INITIALIZER ,
106 .Nm TAILQ_INSERT_AFTER ,
107 .Nm TAILQ_INSERT_BEFORE ,
108 .Nm TAILQ_INSERT_HEAD ,
109 .Nm TAILQ_INSERT_TAIL ,
115 .Nd implementations of singly-linked lists, singly-linked tail queues,
116 lists and tail queues
120 .Fn SLIST_EMPTY "SLIST_HEAD *head"
121 .Fn SLIST_ENTRY "TYPE"
122 .Fn SLIST_FIRST "SLIST_HEAD *head"
123 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
124 .\" .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
125 .\" .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
126 .\" .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
127 .Fn SLIST_HEAD "HEADNAME" "TYPE"
128 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
129 .Fn SLIST_INIT "SLIST_HEAD *head"
130 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
131 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
132 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
133 .\" .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
134 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
135 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
136 .\" .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME"
138 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
139 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
140 .Fn STAILQ_ENTRY "TYPE"
141 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
142 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
143 .\" .Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
144 .\" .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
145 .\" .Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
146 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
147 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
148 .Fn STAILQ_INIT "STAILQ_HEAD *head"
149 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
150 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
151 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
152 .\" .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
153 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
154 .\" .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
155 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
156 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
157 .\" .Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "STAILQ_ENTRY NAME"
159 .Fn LIST_EMPTY "LIST_HEAD *head"
160 .Fn LIST_ENTRY "TYPE"
161 .Fn LIST_FIRST "LIST_HEAD *head"
162 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
163 .\" .Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
164 .\" .Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
165 .\" .Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
166 .Fn LIST_HEAD "HEADNAME" "TYPE"
167 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
168 .Fn LIST_INIT "LIST_HEAD *head"
169 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
170 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
171 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
172 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
173 .\" .Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME"
174 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
175 .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
177 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
178 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
179 .Fn TAILQ_ENTRY "TYPE"
180 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
181 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
182 .\" .Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
183 .\" .Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
184 .\" .Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
185 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
186 .\" .Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
187 .\" .Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
188 .\" .Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
189 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
190 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
191 .Fn TAILQ_INIT "TAILQ_HEAD *head"
192 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
193 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
194 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
195 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
196 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
197 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
198 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
199 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
200 .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME"
203 These macros define and operate on four types of data structures:
204 singly-linked lists, singly-linked tail queues, lists, and tail queues.
205 All four structures support the following functionality:
207 .Bl -enum -compact -offset indent
209 Insertion of a new entry at the head of the list.
211 Insertion of a new entry after any element in the list.
213 O(1) removal of an entry from the head of the list.
215 Forward traversal through the list.
217 Swapping the contents of two lists.
220 Singly-linked lists are the simplest of the four data structures
221 and support only the above functionality.
222 Singly-linked lists are ideal for applications with large datasets
223 and few or no removals,
224 or for implementing a LIFO queue.
225 Singly-linked lists add the following functionality:
227 .Bl -enum -compact -offset indent
229 O(n) removal of any entry in the list.
232 Singly-linked tail queues add the following functionality:
234 .Bl -enum -compact -offset indent
236 Entries can be added at the end of a list.
238 O(n) removal of any entry in the list.
240 They may be concatenated.
245 .Bl -enum -compact -offset indent
247 All list insertions must specify the head of the list.
249 Each head entry requires two pointers rather than one.
251 Code size is about 15% greater and operations run about 20% slower
252 than singly-linked lists.
255 Singly-linked tail queues are ideal for applications with large datasets and
257 or for implementing a FIFO queue.
259 All doubly linked types of data structures (lists and tail queues)
262 .Bl -enum -compact -offset indent
264 Insertion of a new entry before any element in the list.
266 O(1) removal of any entry in the list.
271 .Bl -enum -compact -offset indent
273 Each element requires two pointers rather than one.
275 Code size and execution time of operations (except for removal) is about
276 twice that of the singly-linked data-structures.
279 Linked lists are the simplest of the doubly linked data structures.
280 They add the following functionality over the above:
282 .Bl -enum -compact -offset indent
284 They may be traversed backwards.
289 .Bl -enum -compact -offset indent
291 To traverse backwards, an entry to begin the traversal and the list in
292 which it is contained must be specified.
295 Tail queues add the following functionality:
296 .Bl -enum -compact -offset indent
298 Entries can be added at the end of a list.
300 They may be traversed backwards, from tail to head.
302 They may be concatenated.
307 .Bl -enum -compact -offset indent
309 All list insertions and removals must specify the head of the list.
311 Each head entry requires two pointers rather than one.
313 Code size is about 15% greater and operations run about 20% slower
314 than singly-linked lists.
317 In the macro definitions,
319 is the name of a user defined structure,
320 that must contain a field of type
330 is the name of a user defined structure that must be declared
337 See the examples below for further explanation of how these
339 .Ss Singly-linked lists
340 A singly-linked list is headed by a structure defined by the
343 This structure contains a single pointer to the first element
345 The elements are singly linked for minimum space and pointer manipulation
346 overhead at the expense of O(n) removal for arbitrary elements.
347 New elements can be added to the list after an existing element or
348 at the head of the list.
351 structure is declared as follows:
352 .Bd -literal -offset indent
353 SLIST_HEAD(HEADNAME, TYPE) head;
358 is the name of the structure to be defined, and
360 is the type of the elements to be linked into the list.
361 A pointer to the head of the list can later be declared as:
362 .Bd -literal -offset indent
363 struct HEADNAME *headp;
370 are user selectable.)
373 .Nm SLIST_HEAD_INITIALIZER
374 evaluates to an initializer for the list
379 evaluates to true if there are no elements in the list.
383 declares a structure that connects the elements in
388 returns the first element in the list or NULL if the list is empty.
392 traverses the list referenced by
394 in the forward direction, assigning each element in
399 .\" .Nm SLIST_FOREACH_FROM
400 .\" behaves identically to
401 .\" .Nm SLIST_FOREACH
404 .\" is NULL, else it treats
406 .\" as a previously found SLIST element and begins the loop at
408 .\" instead of the first element in the SLIST referenced by
412 .\" .Nm SLIST_FOREACH_SAFE
413 .\" traverses the list referenced by
415 .\" in the forward direction, assigning each element in
419 .\" .Fn SLIST_FOREACH
420 .\" here it is permitted to both remove
422 .\" as well as free it from within the loop safely without interfering with the
426 .\" .Nm SLIST_FOREACH_FROM_SAFE
427 .\" behaves identically to
428 .\" .Nm SLIST_FOREACH_SAFE
431 .\" is NULL, else it treats
433 .\" as a previously found SLIST element and begins the loop at
435 .\" instead of the first element in the SLIST referenced by
440 initializes the list referenced by
444 .Nm SLIST_INSERT_HEAD
445 inserts the new element
447 at the head of the list.
450 .Nm SLIST_INSERT_AFTER
451 inserts the new element
458 returns the next element in the list.
461 .\" .Nm SLIST_REMOVE_AFTER
462 .\" removes the element after
466 .\" .Fa SLIST_REMOVE ,
467 .\" this macro does not traverse the entire list.
470 .Nm SLIST_REMOVE_HEAD
473 from the head of the list.
474 For optimum efficiency,
475 elements being removed from the head of the list should explicitly use
476 this macro instead of the generic
488 .\" swaps the contents of
492 .Ss Singly-linked list example
494 SLIST_HEAD(slisthead, entry) head =
495 SLIST_HEAD_INITIALIZER(head);
496 struct slisthead *headp; /* Singly-linked List
500 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
502 } *n1, *n2, *n3, *np;
504 SLIST_INIT(&head); /* Initialize the list. */
506 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
507 SLIST_INSERT_HEAD(&head, n1, entries);
509 n2 = malloc(sizeof(struct entry)); /* Insert after. */
510 SLIST_INSERT_AFTER(n1, n2, entries);
512 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
515 n3 = SLIST_FIRST(&head);
516 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
518 /* Forward traversal. */
519 SLIST_FOREACH(np, &head, entries)
521 .\" /* Safe forward traversal. */
522 .\"SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
525 .\" SLIST_REMOVE(&head, np, entry, entries);
529 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
530 n1 = SLIST_FIRST(&head);
531 SLIST_REMOVE_HEAD(&head, entries);
535 .Ss Singly-linked tail queues
536 A singly-linked tail queue is headed by a structure defined by the
539 This structure contains a pair of pointers,
540 one to the first element in the tail queue and the other to
541 the last element in the tail queue.
542 The elements are singly linked for minimum space and pointer
543 manipulation overhead at the expense of O(n) removal for arbitrary
545 New elements can be added to the tail queue after an existing element,
546 at the head of the tail queue, or at the end of the tail queue.
549 structure is declared as follows:
550 .Bd -literal -offset indent
551 STAILQ_HEAD(HEADNAME, TYPE) head;
556 is the name of the structure to be defined, and
558 is the type of the elements to be linked into the tail queue.
559 A pointer to the head of the tail queue can later be declared as:
560 .Bd -literal -offset indent
561 struct HEADNAME *headp;
568 are user selectable.)
571 .Nm STAILQ_HEAD_INITIALIZER
572 evaluates to an initializer for the tail queue
577 concatenates the tail queue headed by
579 onto the end of the one headed by
581 removing all entries from the former.
585 evaluates to true if there are no items on the tail queue.
589 declares a structure that connects the elements in
594 returns the first item on the tail queue or NULL if the tail queue
599 traverses the tail queue referenced by
601 in the forward direction, assigning each element
606 .\" .Nm STAILQ_FOREACH_FROM
607 .\" behaves identically to
608 .\" .Nm STAILQ_FOREACH
611 .\" is NULL, else it treats
613 .\" as a previously found STAILQ element and begins the loop at
615 .\" instead of the first element in the STAILQ referenced by
619 .\" .Nm STAILQ_FOREACH_SAFE
620 .\" traverses the tail queue referenced by
622 .\" in the forward direction, assigning each element
626 .\" .Fn STAILQ_FOREACH
627 .\" here it is permitted to both remove
629 .\" as well as free it from within the loop safely without interfering with the
633 .\" .Nm STAILQ_FOREACH_FROM_SAFE
634 .\" behaves identically to
635 .\" .Nm STAILQ_FOREACH_SAFE
638 .\" is NULL, else it treats
640 .\" as a previously found STAILQ element and begins the loop at
642 .\" instead of the first element in the STAILQ referenced by
647 initializes the tail queue referenced by
651 .Nm STAILQ_INSERT_HEAD
652 inserts the new element
654 at the head of the tail queue.
657 .Nm STAILQ_INSERT_TAIL
658 inserts the new element
660 at the end of the tail queue.
663 .Nm STAILQ_INSERT_AFTER
664 inserts the new element
671 .\" returns the last item on the tail queue.
672 .\" If the tail queue is empty the return value is
677 returns the next item on the tail queue, or NULL this item is the last.
680 .\" .Nm STAILQ_REMOVE_AFTER
681 .\" removes the element after
683 .\" from the tail queue.
685 .\" .Fa STAILQ_REMOVE ,
686 .\" this macro does not traverse the entire tail queue.
689 .Nm STAILQ_REMOVE_HEAD
690 removes the element at the head of the tail queue.
691 For optimum efficiency,
692 elements being removed from the head of the tail queue should
693 use this macro explicitly rather than the generic
705 .\" swaps the contents of
709 .Ss Singly-linked tail queue example
711 STAILQ_HEAD(stailhead, entry) head =
712 STAILQ_HEAD_INITIALIZER(head);
713 struct stailhead *headp; /* Singly-linked tail queue head. */
716 STAILQ_ENTRY(entry) entries; /* Tail queue. */
718 } *n1, *n2, *n3, *np;
720 STAILQ_INIT(&head); /* Initialize the queue. */
722 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
723 STAILQ_INSERT_HEAD(&head, n1, entries);
725 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
726 STAILQ_INSERT_TAIL(&head, n1, entries);
728 n2 = malloc(sizeof(struct entry)); /* Insert after. */
729 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
731 STAILQ_REMOVE(&head, n2, entry, entries);
733 /* Deletion from the head. */
734 n3 = STAILQ_FIRST(&head);
735 STAILQ_REMOVE_HEAD(&head, entries);
737 /* Forward traversal. */
738 STAILQ_FOREACH(np, &head, entries)
740 .\" /* Safe forward traversal. */
741 .\"STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
744 .\" STAILQ_REMOVE(&head, np, entry, entries);
747 /* TailQ Deletion. */
748 while (!STAILQ_EMPTY(&head)) {
749 n1 = STAILQ_FIRST(&head);
750 STAILQ_REMOVE_HEAD(&head, entries);
753 /* Faster TailQ Deletion. */
754 n1 = STAILQ_FIRST(&head);
756 n2 = STAILQ_NEXT(n1, entries);
763 A list is headed by a structure defined by the
766 This structure contains a single pointer to the first element
768 The elements are doubly linked so that an arbitrary element can be
769 removed without traversing the list.
770 New elements can be added to the list after an existing element,
771 before an existing element, or at the head of the list.
774 structure is declared as follows:
775 .Bd -literal -offset indent
776 LIST_HEAD(HEADNAME, TYPE) head;
781 is the name of the structure to be defined, and
783 is the type of the elements to be linked into the list.
784 A pointer to the head of the list can later be declared as:
785 .Bd -literal -offset indent
786 struct HEADNAME *headp;
793 are user selectable.)
796 .Nm LIST_HEAD_INITIALIZER
797 evaluates to an initializer for the list
802 evaluates to true if there are no elements in the list.
806 declares a structure that connects the elements in
811 returns the first element in the list or NULL if the list
816 traverses the list referenced by
818 in the forward direction, assigning each element in turn to
822 .\" .Nm LIST_FOREACH_FROM
823 .\" behaves identically to
827 .\" is NULL, else it treats
829 .\" as a previously found LIST element and begins the loop at
831 .\" instead of the first element in the LIST referenced by
835 .\" .Nm LIST_FOREACH_SAFE
836 .\" traverses the list referenced by
838 .\" in the forward direction, assigning each element in turn to
842 .\" here it is permitted to both remove
844 .\" as well as free it from within the loop safely without interfering with the
848 .\" .Nm LIST_FOREACH_FROM_SAFE
849 .\" behaves identically to
850 .\" .Nm LIST_FOREACH_SAFE
853 .\" is NULL, else it treats
855 .\" as a previously found LIST element and begins the loop at
857 .\" instead of the first element in the LIST referenced by
862 initializes the list referenced by
867 inserts the new element
869 at the head of the list.
872 .Nm LIST_INSERT_AFTER
873 inserts the new element
879 .Nm LIST_INSERT_BEFORE
880 inserts the new element
887 returns the next element in the list, or NULL if this is the last.
891 .\" returns the previous element in the list, or NULL if this is the first.
894 .\" must contain element
905 .\" swaps the contents of
911 LIST_HEAD(listhead, entry) head =
912 LIST_HEAD_INITIALIZER(head);
913 struct listhead *headp; /* List head. */
916 LIST_ENTRY(entry) entries; /* List. */
918 } *n1, *n2, *n3, *np, *np_temp;
920 LIST_INIT(&head); /* Initialize the list. */
922 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
923 LIST_INSERT_HEAD(&head, n1, entries);
925 n2 = malloc(sizeof(struct entry)); /* Insert after. */
926 LIST_INSERT_AFTER(n1, n2, entries);
928 n3 = malloc(sizeof(struct entry)); /* Insert before. */
929 LIST_INSERT_BEFORE(n2, n3, entries);
931 LIST_REMOVE(n2, entries); /* Deletion. */
933 /* Forward traversal. */
934 LIST_FOREACH(np, &head, entries)
937 .\" /* Safe forward traversal. */
938 .\" LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
941 .\" LIST_REMOVE(np, entries);
945 while (!LIST_EMPTY(&head)) { /* List Deletion. */
946 n1 = LIST_FIRST(&head);
947 LIST_REMOVE(n1, entries);
951 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
953 n2 = LIST_NEXT(n1, entries);
960 A tail queue is headed by a structure defined by the
963 This structure contains a pair of pointers,
964 one to the first element in the tail queue and the other to
965 the last element in the tail queue.
966 The elements are doubly linked so that an arbitrary element can be
967 removed without traversing the tail queue.
968 New elements can be added to the tail queue after an existing element,
969 before an existing element, at the head of the tail queue,
970 or at the end of the tail queue.
973 structure is declared as follows:
974 .Bd -literal -offset indent
975 TAILQ_HEAD(HEADNAME, TYPE) head;
980 is the name of the structure to be defined, and
982 is the type of the elements to be linked into the tail queue.
983 A pointer to the head of the tail queue can later be declared as:
984 .Bd -literal -offset indent
985 struct HEADNAME *headp;
992 are user selectable.)
995 .Nm TAILQ_HEAD_INITIALIZER
996 evaluates to an initializer for the tail queue
1001 concatenates the tail queue headed by
1003 onto the end of the one headed by
1005 removing all entries from the former.
1009 evaluates to true if there are no items on the tail queue.
1013 declares a structure that connects the elements in
1018 returns the first item on the tail queue or NULL if the tail queue
1023 traverses the tail queue referenced by
1025 in the forward direction, assigning each element in turn to
1030 if the loop completes normally, or if there were no elements.
1033 .\" .Nm TAILQ_FOREACH_FROM
1034 .\" behaves identically to
1035 .\" .Nm TAILQ_FOREACH
1038 .\" is NULL, else it treats
1040 .\" as a previously found TAILQ element and begins the loop at
1042 .\" instead of the first element in the TAILQ referenced by
1046 .Nm TAILQ_FOREACH_REVERSE
1047 traverses the tail queue referenced by
1049 in the reverse direction, assigning each element in turn to
1053 .\" .Nm TAILQ_FOREACH_REVERSE_FROM
1054 .\" behaves identically to
1055 .\" .Nm TAILQ_FOREACH_REVERSE
1058 .\" is NULL, else it treats
1060 .\" as a previously found TAILQ element and begins the reverse loop at
1062 .\" instead of the last element in the TAILQ referenced by
1066 .\" .Nm TAILQ_FOREACH_SAFE
1068 .\" .Nm TAILQ_FOREACH_REVERSE_SAFE
1069 .\" traverse the list referenced by
1071 .\" in the forward or reverse direction respectively,
1072 .\" assigning each element in turn to
1074 .\" However, unlike their unsafe counterparts,
1075 .\" .Nm TAILQ_FOREACH
1077 .\" .Nm TAILQ_FOREACH_REVERSE
1078 .\" permit to both remove
1080 .\" as well as free it from within the loop safely without interfering with the
1084 .\" .Nm TAILQ_FOREACH_FROM_SAFE
1085 .\" behaves identically to
1086 .\" .Nm TAILQ_FOREACH_SAFE
1089 .\" is NULL, else it treats
1091 .\" as a previously found TAILQ element and begins the loop at
1093 .\" instead of the first element in the TAILQ referenced by
1097 .\" .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE
1098 .\" behaves identically to
1099 .\" .Nm TAILQ_FOREACH_REVERSE_SAFE
1102 .\" is NULL, else it treats
1104 .\" as a previously found TAILQ element and begins the reverse loop at
1106 .\" instead of the last element in the TAILQ referenced by
1111 initializes the tail queue referenced by
1115 .Nm TAILQ_INSERT_HEAD
1116 inserts the new element
1118 at the head of the tail queue.
1121 .Nm TAILQ_INSERT_TAIL
1122 inserts the new element
1124 at the end of the tail queue.
1127 .Nm TAILQ_INSERT_AFTER
1128 inserts the new element
1134 .Nm TAILQ_INSERT_BEFORE
1135 inserts the new element
1142 returns the last item on the tail queue.
1143 If the tail queue is empty the return value is
1148 returns the next item on the tail queue, or NULL if this item is the last.
1152 returns the previous item on the tail queue, or NULL if this item
1159 from the tail queue.
1163 swaps the contents of
1167 .Ss Tail queue example
1169 TAILQ_HEAD(tailhead, entry) head =
1170 TAILQ_HEAD_INITIALIZER(head);
1171 struct tailhead *headp; /* Tail queue head. */
1174 TAILQ_ENTRY(entry) entries; /* Tail queue. */
1176 } *n1, *n2, *n3, *np;
1178 TAILQ_INIT(&head); /* Initialize the queue. */
1180 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
1181 TAILQ_INSERT_HEAD(&head, n1, entries);
1183 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
1184 TAILQ_INSERT_TAIL(&head, n1, entries);
1186 n2 = malloc(sizeof(struct entry)); /* Insert after. */
1187 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
1189 n3 = malloc(sizeof(struct entry)); /* Insert before. */
1190 TAILQ_INSERT_BEFORE(n2, n3, entries);
1192 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
1194 /* Forward traversal. */
1195 TAILQ_FOREACH(np, &head, entries)
1197 .\" /* Safe forward traversal. */
1198 .\" TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
1199 .\" np\->do_stuff();
1201 .\" TAILQ_REMOVE(&head, np, entries);
1204 /* Reverse traversal. */
1205 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
1207 /* TailQ Deletion. */
1208 while (!TAILQ_EMPTY(&head)) {
1209 n1 = TAILQ_FIRST(&head);
1210 TAILQ_REMOVE(&head, n1, entries);
1213 /* Faster TailQ Deletion. */
1214 n1 = TAILQ_FIRST(&head);
1215 while (n1 != NULL) {
1216 n2 = TAILQ_NEXT(n1, entries);
1222 n2 = malloc(sizeof(struct entry)); /* Insert before. */
1223 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
1224 /* Forward traversal. */
1225 for (np = head.cqh_first; np != (void *)&head;
1226 np = np\->entries.cqe_next)
1228 /* Reverse traversal. */
1229 for (np = head.cqh_last; np != (void *)&head; np = np\->entries.cqe_prev)
1232 while (head.cqh_first != (void *)&head)
1233 CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
1236 Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008.
1237 Present on the BSDs.
1239 functions first appeared in