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. Neither the name of the University nor the names of its contributors
13 .\" may be used to endorse or promote products derived from this software
14 .\" without specific prior written permission.
16 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
17 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
20 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
28 .\" @(#)queue.3 8.2 (Berkeley) 1/24/94
35 .Nm SLIST_CLASS_ENTRY ,
36 .Nm SLIST_CLASS_HEAD ,
42 .Nm SLIST_FOREACH_FROM ,
43 .Nm SLIST_FOREACH_FROM_SAFE ,
44 .Nm SLIST_FOREACH_SAFE ,
46 .Nm SLIST_HEAD_INITIALIZER ,
48 .Nm SLIST_INSERT_AFTER ,
49 .Nm SLIST_INSERT_HEAD ,
52 .Nm SLIST_REMOVE_AFTER ,
53 .Nm SLIST_REMOVE_HEAD ,
55 .Nm STAILQ_CLASS_ENTRY ,
56 .Nm STAILQ_CLASS_HEAD ,
62 .Nm STAILQ_FOREACH_FROM ,
63 .Nm STAILQ_FOREACH_FROM_SAFE ,
64 .Nm STAILQ_FOREACH_SAFE ,
66 .Nm STAILQ_HEAD_INITIALIZER ,
68 .Nm STAILQ_INSERT_AFTER ,
69 .Nm STAILQ_INSERT_HEAD ,
70 .Nm STAILQ_INSERT_TAIL ,
74 .Nm STAILQ_REMOVE_AFTER ,
75 .Nm STAILQ_REMOVE_HEAD ,
77 .Nm LIST_CLASS_ENTRY ,
84 .Nm LIST_FOREACH_FROM ,
85 .Nm LIST_FOREACH_FROM_SAFE ,
86 .Nm LIST_FOREACH_SAFE ,
88 .Nm LIST_HEAD_INITIALIZER ,
90 .Nm LIST_INSERT_AFTER ,
91 .Nm LIST_INSERT_BEFORE ,
92 .Nm LIST_INSERT_HEAD ,
97 .Nm TAILQ_CLASS_ENTRY ,
98 .Nm TAILQ_CLASS_HEAD ,
104 .Nm TAILQ_FOREACH_FROM ,
105 .Nm TAILQ_FOREACH_FROM_SAFE ,
106 .Nm TAILQ_FOREACH_REVERSE ,
107 .Nm TAILQ_FOREACH_REVERSE_FROM ,
108 .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE ,
109 .Nm TAILQ_FOREACH_REVERSE_SAFE ,
110 .Nm TAILQ_FOREACH_SAFE ,
112 .Nm TAILQ_HEAD_INITIALIZER ,
114 .Nm TAILQ_INSERT_AFTER ,
115 .Nm TAILQ_INSERT_BEFORE ,
116 .Nm TAILQ_INSERT_HEAD ,
117 .Nm TAILQ_INSERT_TAIL ,
123 .Nd implementations of singly-linked lists, singly-linked tail queues,
124 lists and tail queues
128 .Fn SLIST_CLASS_ENTRY "CLASSTYPE"
129 .Fn SLIST_CLASS_HEAD "HEADNAME" "CLASSTYPE"
130 .Fn SLIST_CONCAT "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" "SLIST_ENTRY NAME"
131 .Fn SLIST_EMPTY "SLIST_HEAD *head"
132 .Fn SLIST_ENTRY "TYPE"
133 .Fn SLIST_FIRST "SLIST_HEAD *head"
134 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
135 .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
136 .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
137 .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
138 .Fn SLIST_HEAD "HEADNAME" "TYPE"
139 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
140 .Fn SLIST_INIT "SLIST_HEAD *head"
141 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
142 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
143 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
144 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
145 .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
146 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
147 .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE"
149 .Fn STAILQ_CLASS_ENTRY "CLASSTYPE"
150 .Fn STAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE"
151 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
152 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
153 .Fn STAILQ_ENTRY "TYPE"
154 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
155 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
156 .Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
157 .Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
158 .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
159 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
160 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
161 .Fn STAILQ_INIT "STAILQ_HEAD *head"
162 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
163 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
164 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
165 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
166 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
167 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
168 .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
169 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
170 .Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "TYPE"
172 .Fn LIST_CLASS_ENTRY "CLASSTYPE"
173 .Fn LIST_CLASS_HEAD "HEADNAME" "CLASSTYPE"
174 .Fn LIST_CONCAT "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
175 .Fn LIST_EMPTY "LIST_HEAD *head"
176 .Fn LIST_ENTRY "TYPE"
177 .Fn LIST_FIRST "LIST_HEAD *head"
178 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
179 .Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
180 .Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
181 .Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
182 .Fn LIST_HEAD "HEADNAME" "TYPE"
183 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
184 .Fn LIST_INIT "LIST_HEAD *head"
185 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
186 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
187 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
188 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
189 .Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME"
190 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
191 .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
193 .Fn TAILQ_CLASS_ENTRY "CLASSTYPE"
194 .Fn TAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE"
195 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
196 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
197 .Fn TAILQ_ENTRY "TYPE"
198 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
199 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
200 .Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
201 .Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
202 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
203 .Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
204 .Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
205 .Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
206 .Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
207 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
208 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
209 .Fn TAILQ_INIT "TAILQ_HEAD *head"
210 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
211 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
212 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
213 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
214 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
215 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
216 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
217 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
218 .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME"
221 These macros define and operate on four types of data structures which
222 can be used in both C and C++ source code:
223 .Bl -enum -compact -offset indent
229 Singly-linked tail queues
233 All four structures support the following functionality:
234 .Bl -enum -compact -offset indent
236 Insertion of a new entry at the head of the list.
238 Insertion of a new entry after any element in the list.
240 O(1) removal of an entry from the head of the list.
242 Forward traversal through the list.
244 Swapping the contents of two lists.
247 Singly-linked lists are the simplest of the four data structures
248 and support only the above functionality.
249 Singly-linked lists are ideal for applications with large datasets
250 and few or no removals,
251 or for implementing a LIFO queue.
252 Singly-linked lists add the following functionality:
253 .Bl -enum -compact -offset indent
255 O(n) removal of any entry in the list.
257 O(n) concatenation of two lists.
260 Singly-linked tail queues add the following functionality:
261 .Bl -enum -compact -offset indent
263 Entries can be added at the end of a list.
265 O(n) removal of any entry in the list.
267 They may be concatenated.
270 .Bl -enum -compact -offset indent
272 All list insertions must specify the head of the list.
274 Each head entry requires two pointers rather than one.
276 Code size is about 15% greater and operations run about 20% slower
277 than singly-linked lists.
280 Singly-linked tail queues are ideal for applications with large datasets and
282 or for implementing a FIFO queue.
284 All doubly linked types of data structures (lists and tail queues)
286 .Bl -enum -compact -offset indent
288 Insertion of a new entry before any element in the list.
290 O(1) removal of any entry in the list.
293 .Bl -enum -compact -offset indent
295 Each element requires two pointers rather than one.
297 Code size and execution time of operations (except for removal) is about
298 twice that of the singly-linked data-structures.
301 Linked lists are the simplest of the doubly linked data structures.
302 They add the following functionality over the above:
303 .Bl -enum -compact -offset indent
305 O(n) concatenation of two lists.
307 They may be traversed backwards.
310 .Bl -enum -compact -offset indent
312 To traverse backwards, an entry to begin the traversal and the list in
313 which it is contained must be specified.
316 Tail queues add the following functionality:
317 .Bl -enum -compact -offset indent
319 Entries can be added at the end of a list.
321 They may be traversed backwards, from tail to head.
323 They may be concatenated.
326 .Bl -enum -compact -offset indent
328 All list insertions and removals must specify the head of the list.
330 Each head entry requires two pointers rather than one.
332 Code size is about 15% greater and operations run about 20% slower
333 than singly-linked lists.
336 In the macro definitions,
338 is the name of a user defined structure.
339 The structure must contain a field called
347 In the macro definitions,
349 is the name of a user defined class.
350 The class must contain a field called
353 .Li SLIST_CLASS_ENTRY ,
354 .Li STAILQ_CLASS_ENTRY ,
355 .Li LIST_CLASS_ENTRY ,
357 .Li TAILQ_CLASS_ENTRY .
360 is the name of a user defined structure that must be declared
363 .Li SLIST_CLASS_HEAD ,
365 .Li STAILQ_CLASS_HEAD ,
367 .Li LIST_CLASS_HEAD ,
370 .Li TAILQ_CLASS_HEAD .
371 See the examples below for further explanation of how these
373 .Sh SINGLY-LINKED LISTS
374 A singly-linked list is headed by a structure defined by the
377 This structure contains a single pointer to the first element
379 The elements are singly linked for minimum space and pointer manipulation
380 overhead at the expense of O(n) removal for arbitrary elements.
381 New elements can be added to the list after an existing element or
382 at the head of the list.
385 structure is declared as follows:
386 .Bd -literal -offset indent
387 SLIST_HEAD(HEADNAME, TYPE) head;
392 is the name of the structure to be defined, and
394 is the type of the elements to be linked into the list.
395 A pointer to the head of the list can later be declared as:
396 .Bd -literal -offset indent
397 struct HEADNAME *headp;
404 are user selectable.)
407 .Nm SLIST_HEAD_INITIALIZER
408 evaluates to an initializer for the list
413 concatenates the list headed by
415 onto the end of the one headed by
417 removing all entries from the former.
418 Use of this macro should be avoided as it traverses the entirety of the
421 A singly-linked tail queue should be used if this macro is needed in
422 high-usage code paths or to operate on long lists.
426 evaluates to true if there are no elements in the list.
430 declares a structure that connects the elements in
435 returns the first element in the list or NULL if the list is empty.
439 traverses the list referenced by
441 in the forward direction, assigning each element in
446 .Nm SLIST_FOREACH_FROM
447 behaves identically to
451 is NULL, else it treats
453 as a previously found SLIST element and begins the loop at
455 instead of the first element in the SLIST referenced by
459 .Nm SLIST_FOREACH_SAFE
460 traverses the list referenced by
462 in the forward direction, assigning each element in
467 here it is permitted to both remove
469 as well as free it from within the loop safely without interfering with the
473 .Nm SLIST_FOREACH_FROM_SAFE
474 behaves identically to
475 .Nm SLIST_FOREACH_SAFE
478 is NULL, else it treats
480 as a previously found SLIST element and begins the loop at
482 instead of the first element in the SLIST referenced by
487 initializes the list referenced by
491 .Nm SLIST_INSERT_HEAD
492 inserts the new element
494 at the head of the list.
497 .Nm SLIST_INSERT_AFTER
498 inserts the new element
505 returns the next element in the list.
508 .Nm SLIST_REMOVE_AFTER
509 removes the element after
514 this macro does not traverse the entire list.
517 .Nm SLIST_REMOVE_HEAD
520 from the head of the list.
521 For optimum efficiency,
522 elements being removed from the head of the list should explicitly use
523 this macro instead of the generic
532 Use of this macro should be avoided as it traverses the entire list.
533 A doubly-linked list should be used if this macro is needed in
534 high-usage code paths or to operate on long lists.
538 swaps the contents of
542 .Sh SINGLY-LINKED LIST EXAMPLE
544 SLIST_HEAD(slisthead, entry) head =
545 SLIST_HEAD_INITIALIZER(head);
546 struct slisthead *headp; /* Singly-linked List head. */
549 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
551 } *n1, *n2, *n3, *np;
553 SLIST_INIT(&head); /* Initialize the list. */
555 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
556 SLIST_INSERT_HEAD(&head, n1, entries);
558 n2 = malloc(sizeof(struct entry)); /* Insert after. */
559 SLIST_INSERT_AFTER(n1, n2, entries);
561 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
564 n3 = SLIST_FIRST(&head);
565 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
567 /* Forward traversal. */
568 SLIST_FOREACH(np, &head, entries)
570 /* Safe forward traversal. */
571 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
574 SLIST_REMOVE(&head, np, entry, entries);
578 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
579 n1 = SLIST_FIRST(&head);
580 SLIST_REMOVE_HEAD(&head, entries);
584 .Sh SINGLY-LINKED TAIL QUEUES
585 A singly-linked tail queue is headed by a structure defined by the
588 This structure contains a pair of pointers,
589 one to the first element in the tail queue and the other to
590 the last element in the tail queue.
591 The elements are singly linked for minimum space and pointer
592 manipulation overhead at the expense of O(n) removal for arbitrary
594 New elements can be added to the tail queue after an existing element,
595 at the head of the tail queue, or at the end of the tail queue.
598 structure is declared as follows:
599 .Bd -literal -offset indent
600 STAILQ_HEAD(HEADNAME, TYPE) head;
605 is the name of the structure to be defined, and
607 is the type of the elements to be linked into the tail queue.
608 A pointer to the head of the tail queue can later be declared as:
609 .Bd -literal -offset indent
610 struct HEADNAME *headp;
617 are user selectable.)
620 .Nm STAILQ_HEAD_INITIALIZER
621 evaluates to an initializer for the tail queue
626 concatenates the tail queue headed by
628 onto the end of the one headed by
630 removing all entries from the former.
634 evaluates to true if there are no items on the tail queue.
638 declares a structure that connects the elements in
643 returns the first item on the tail queue or NULL if the tail queue
648 traverses the tail queue referenced by
650 in the forward direction, assigning each element
655 .Nm STAILQ_FOREACH_FROM
656 behaves identically to
660 is NULL, else it treats
662 as a previously found STAILQ element and begins the loop at
664 instead of the first element in the STAILQ referenced by
668 .Nm STAILQ_FOREACH_SAFE
669 traverses the tail queue referenced by
671 in the forward direction, assigning each element
676 here it is permitted to both remove
678 as well as free it from within the loop safely without interfering with the
682 .Nm STAILQ_FOREACH_FROM_SAFE
683 behaves identically to
684 .Nm STAILQ_FOREACH_SAFE
687 is NULL, else it treats
689 as a previously found STAILQ element and begins the loop at
691 instead of the first element in the STAILQ referenced by
696 initializes the tail queue referenced by
700 .Nm STAILQ_INSERT_HEAD
701 inserts the new element
703 at the head of the tail queue.
706 .Nm STAILQ_INSERT_TAIL
707 inserts the new element
709 at the end of the tail queue.
712 .Nm STAILQ_INSERT_AFTER
713 inserts the new element
720 returns the last item on the tail queue.
721 If the tail queue is empty the return value is
726 returns the next item on the tail queue, or NULL this item is the last.
729 .Nm STAILQ_REMOVE_AFTER
730 removes the element after
735 this macro does not traverse the entire tail queue.
738 .Nm STAILQ_REMOVE_HEAD
739 removes the element at the head of the tail queue.
740 For optimum efficiency,
741 elements being removed from the head of the tail queue should
742 use this macro explicitly rather than the generic
751 Use of this macro should be avoided as it traverses the entire list.
752 A doubly-linked tail queue should be used if this macro is needed in
753 high-usage code paths or to operate on long tail queues.
757 swaps the contents of
761 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
763 STAILQ_HEAD(stailhead, entry) head =
764 STAILQ_HEAD_INITIALIZER(head);
765 struct stailhead *headp; /* Singly-linked tail queue head. */
768 STAILQ_ENTRY(entry) entries; /* Tail queue. */
770 } *n1, *n2, *n3, *np;
772 STAILQ_INIT(&head); /* Initialize the queue. */
774 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
775 STAILQ_INSERT_HEAD(&head, n1, entries);
777 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
778 STAILQ_INSERT_TAIL(&head, n1, entries);
780 n2 = malloc(sizeof(struct entry)); /* Insert after. */
781 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
783 STAILQ_REMOVE(&head, n2, entry, entries);
785 /* Deletion from the head. */
786 n3 = STAILQ_FIRST(&head);
787 STAILQ_REMOVE_HEAD(&head, entries);
789 /* Forward traversal. */
790 STAILQ_FOREACH(np, &head, entries)
792 /* Safe forward traversal. */
793 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
796 STAILQ_REMOVE(&head, np, entry, entries);
799 /* TailQ Deletion. */
800 while (!STAILQ_EMPTY(&head)) {
801 n1 = STAILQ_FIRST(&head);
802 STAILQ_REMOVE_HEAD(&head, entries);
805 /* Faster TailQ Deletion. */
806 n1 = STAILQ_FIRST(&head);
808 n2 = STAILQ_NEXT(n1, entries);
815 A list is headed by a structure defined by the
818 This structure contains a single pointer to the first element
820 The elements are doubly linked so that an arbitrary element can be
821 removed without traversing the list.
822 New elements can be added to the list after an existing element,
823 before an existing element, or at the head of the list.
826 structure is declared as follows:
827 .Bd -literal -offset indent
828 LIST_HEAD(HEADNAME, TYPE) head;
833 is the name of the structure to be defined, and
835 is the type of the elements to be linked into the list.
836 A pointer to the head of the list can later be declared as:
837 .Bd -literal -offset indent
838 struct HEADNAME *headp;
845 are user selectable.)
848 .Nm LIST_HEAD_INITIALIZER
849 evaluates to an initializer for the list
854 concatenates the list headed by
856 onto the end of the one headed by
858 removing all entries from the former.
859 Use of this macro should be avoided as it traverses the entirety of the
862 A tail queue should be used if this macro is needed in
863 high-usage code paths or to operate on long lists.
867 evaluates to true if there are no elements in the list.
871 declares a structure that connects the elements in
876 returns the first element in the list or NULL if the list
881 traverses the list referenced by
883 in the forward direction, assigning each element in turn to
887 .Nm LIST_FOREACH_FROM
888 behaves identically to
892 is NULL, else it treats
894 as a previously found LIST element and begins the loop at
896 instead of the first element in the LIST referenced by
900 .Nm LIST_FOREACH_SAFE
901 traverses the list referenced by
903 in the forward direction, assigning each element in turn to
907 here it is permitted to both remove
909 as well as free it from within the loop safely without interfering with the
913 .Nm LIST_FOREACH_FROM_SAFE
914 behaves identically to
915 .Nm LIST_FOREACH_SAFE
918 is NULL, else it treats
920 as a previously found LIST element and begins the loop at
922 instead of the first element in the LIST referenced by
927 initializes the list referenced by
932 inserts the new element
934 at the head of the list.
937 .Nm LIST_INSERT_AFTER
938 inserts the new element
944 .Nm LIST_INSERT_BEFORE
945 inserts the new element
952 returns the next element in the list, or NULL if this is the last.
956 returns the previous element in the list, or NULL if this is the first.
970 swaps the contents of
976 LIST_HEAD(listhead, entry) head =
977 LIST_HEAD_INITIALIZER(head);
978 struct listhead *headp; /* List head. */
981 LIST_ENTRY(entry) entries; /* List. */
983 } *n1, *n2, *n3, *np, *np_temp;
985 LIST_INIT(&head); /* Initialize the list. */
987 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
988 LIST_INSERT_HEAD(&head, n1, entries);
990 n2 = malloc(sizeof(struct entry)); /* Insert after. */
991 LIST_INSERT_AFTER(n1, n2, entries);
993 n3 = malloc(sizeof(struct entry)); /* Insert before. */
994 LIST_INSERT_BEFORE(n2, n3, entries);
996 LIST_REMOVE(n2, entries); /* Deletion. */
998 /* Forward traversal. */
999 LIST_FOREACH(np, &head, entries)
1002 /* Safe forward traversal. */
1003 LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
1006 LIST_REMOVE(np, entries);
1010 while (!LIST_EMPTY(&head)) { /* List Deletion. */
1011 n1 = LIST_FIRST(&head);
1012 LIST_REMOVE(n1, entries);
1016 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
1017 while (n1 != NULL) {
1018 n2 = LIST_NEXT(n1, entries);
1025 A tail queue is headed by a structure defined by the
1028 This structure contains a pair of pointers,
1029 one to the first element in the tail queue and the other to
1030 the last element in the tail queue.
1031 The elements are doubly linked so that an arbitrary element can be
1032 removed without traversing the tail queue.
1033 New elements can be added to the tail queue after an existing element,
1034 before an existing element, at the head of the tail queue,
1035 or at the end of the tail queue.
1038 structure is declared as follows:
1039 .Bd -literal -offset indent
1040 TAILQ_HEAD(HEADNAME, TYPE) head;
1045 is the name of the structure to be defined, and
1047 is the type of the elements to be linked into the tail queue.
1048 A pointer to the head of the tail queue can later be declared as:
1049 .Bd -literal -offset indent
1050 struct HEADNAME *headp;
1057 are user selectable.)
1060 .Nm TAILQ_HEAD_INITIALIZER
1061 evaluates to an initializer for the tail queue
1066 concatenates the tail queue headed by
1068 onto the end of the one headed by
1070 removing all entries from the former.
1074 evaluates to true if there are no items on the tail queue.
1078 declares a structure that connects the elements in
1083 returns the first item on the tail queue or NULL if the tail queue
1088 traverses the tail queue referenced by
1090 in the forward direction, assigning each element in turn to
1095 if the loop completes normally, or if there were no elements.
1098 .Nm TAILQ_FOREACH_FROM
1099 behaves identically to
1103 is NULL, else it treats
1105 as a previously found TAILQ element and begins the loop at
1107 instead of the first element in the TAILQ referenced by
1111 .Nm TAILQ_FOREACH_REVERSE
1112 traverses the tail queue referenced by
1114 in the reverse direction, assigning each element in turn to
1118 .Nm TAILQ_FOREACH_REVERSE_FROM
1119 behaves identically to
1120 .Nm TAILQ_FOREACH_REVERSE
1123 is NULL, else it treats
1125 as a previously found TAILQ element and begins the reverse loop at
1127 instead of the last element in the TAILQ referenced by
1131 .Nm TAILQ_FOREACH_SAFE
1133 .Nm TAILQ_FOREACH_REVERSE_SAFE
1134 traverse the list referenced by
1136 in the forward or reverse direction respectively,
1137 assigning each element in turn to
1139 However, unlike their unsafe counterparts,
1142 .Nm TAILQ_FOREACH_REVERSE
1143 permit to both remove
1145 as well as free it from within the loop safely without interfering with the
1149 .Nm TAILQ_FOREACH_FROM_SAFE
1150 behaves identically to
1151 .Nm TAILQ_FOREACH_SAFE
1154 is NULL, else it treats
1156 as a previously found TAILQ element and begins the loop at
1158 instead of the first element in the TAILQ referenced by
1162 .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE
1163 behaves identically to
1164 .Nm TAILQ_FOREACH_REVERSE_SAFE
1167 is NULL, else it treats
1169 as a previously found TAILQ element and begins the reverse loop at
1171 instead of the last element in the TAILQ referenced by
1176 initializes the tail queue referenced by
1180 .Nm TAILQ_INSERT_HEAD
1181 inserts the new element
1183 at the head of the tail queue.
1186 .Nm TAILQ_INSERT_TAIL
1187 inserts the new element
1189 at the end of the tail queue.
1192 .Nm TAILQ_INSERT_AFTER
1193 inserts the new element
1199 .Nm TAILQ_INSERT_BEFORE
1200 inserts the new element
1207 returns the last item on the tail queue.
1208 If the tail queue is empty the return value is
1213 returns the next item on the tail queue, or NULL if this item is the last.
1217 returns the previous item on the tail queue, or NULL if this item
1224 from the tail queue.
1228 swaps the contents of
1232 .Sh TAIL QUEUE EXAMPLE
1234 TAILQ_HEAD(tailhead, entry) head =
1235 TAILQ_HEAD_INITIALIZER(head);
1236 struct tailhead *headp; /* Tail queue head. */
1239 TAILQ_ENTRY(entry) entries; /* Tail queue. */
1241 } *n1, *n2, *n3, *np;
1243 TAILQ_INIT(&head); /* Initialize the queue. */
1245 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
1246 TAILQ_INSERT_HEAD(&head, n1, entries);
1248 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
1249 TAILQ_INSERT_TAIL(&head, n1, entries);
1251 n2 = malloc(sizeof(struct entry)); /* Insert after. */
1252 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
1254 n3 = malloc(sizeof(struct entry)); /* Insert before. */
1255 TAILQ_INSERT_BEFORE(n2, n3, entries);
1257 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
1259 /* Forward traversal. */
1260 TAILQ_FOREACH(np, &head, entries)
1262 /* Safe forward traversal. */
1263 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
1266 TAILQ_REMOVE(&head, np, entries);
1269 /* Reverse traversal. */
1270 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
1272 /* TailQ Deletion. */
1273 while (!TAILQ_EMPTY(&head)) {
1274 n1 = TAILQ_FIRST(&head);
1275 TAILQ_REMOVE(&head, n1, entries);
1278 /* Faster TailQ Deletion. */
1279 n1 = TAILQ_FIRST(&head);
1280 while (n1 != NULL) {
1281 n2 = TAILQ_NEXT(n1, entries);
1290 it can be useful to trace queue changes.
1291 To enable tracing, define the macro
1292 .Va QUEUE_MACRO_DEBUG_TRACE
1295 It can also be useful to trash pointers that have been unlinked from a queue,
1296 to detect use after removal.
1297 To enable pointer trashing, define the macro
1298 .Va QUEUE_MACRO_DEBUG_TRASH
1301 .Fn QMD_IS_TRASHED "void *ptr"
1304 has been trashed by the
1305 .Va QUEUE_MACRO_DEBUG_TRASH
1311 .Fn SLIST_REMOVE_PREVPTR
1312 macro is available to aid debugging:
1313 .Bl -hang -offset indent
1314 .It Fn SLIST_REMOVE_PREVPTR "TYPE **prev" "TYPE *elm" "SLIST_ENTRY NAME"
1318 which must directly follow the element whose
1323 This macro validates that
1337 functions first appeared in