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
39 .Nm SLIST_CLASS_ENTRY ,
40 .Nm SLIST_CLASS_HEAD ,
45 .Nm SLIST_FOREACH_FROM ,
46 .Nm SLIST_FOREACH_FROM_SAFE ,
47 .Nm SLIST_FOREACH_SAFE ,
49 .Nm SLIST_HEAD_INITIALIZER ,
51 .Nm SLIST_INSERT_AFTER ,
52 .Nm SLIST_INSERT_HEAD ,
55 .Nm SLIST_REMOVE_AFTER ,
56 .Nm SLIST_REMOVE_HEAD ,
58 .Nm STAILQ_CLASS_ENTRY ,
59 .Nm STAILQ_CLASS_HEAD ,
65 .Nm STAILQ_FOREACH_FROM ,
66 .Nm STAILQ_FOREACH_FROM_SAFE ,
67 .Nm STAILQ_FOREACH_SAFE ,
69 .Nm STAILQ_HEAD_INITIALIZER ,
71 .Nm STAILQ_INSERT_AFTER ,
72 .Nm STAILQ_INSERT_HEAD ,
73 .Nm STAILQ_INSERT_TAIL ,
77 .Nm STAILQ_REMOVE_AFTER ,
78 .Nm STAILQ_REMOVE_HEAD ,
80 .Nm LIST_CLASS_ENTRY ,
86 .Nm LIST_FOREACH_FROM ,
87 .Nm LIST_FOREACH_FROM_SAFE ,
88 .Nm LIST_FOREACH_SAFE ,
90 .Nm LIST_HEAD_INITIALIZER ,
92 .Nm LIST_INSERT_AFTER ,
93 .Nm LIST_INSERT_BEFORE ,
94 .Nm LIST_INSERT_HEAD ,
99 .Nm TAILQ_CLASS_ENTRY ,
100 .Nm TAILQ_CLASS_HEAD ,
106 .Nm TAILQ_FOREACH_FROM ,
107 .Nm TAILQ_FOREACH_FROM_SAFE ,
108 .Nm TAILQ_FOREACH_REVERSE ,
109 .Nm TAILQ_FOREACH_REVERSE_FROM ,
110 .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE ,
111 .Nm TAILQ_FOREACH_REVERSE_SAFE ,
112 .Nm TAILQ_FOREACH_SAFE ,
114 .Nm TAILQ_HEAD_INITIALIZER ,
116 .Nm TAILQ_INSERT_AFTER ,
117 .Nm TAILQ_INSERT_BEFORE ,
118 .Nm TAILQ_INSERT_HEAD ,
119 .Nm TAILQ_INSERT_TAIL ,
125 .Nd implementations of singly-linked lists, singly-linked tail queues,
126 lists and tail queues
130 .Fn SLIST_CLASS_ENTRY "CLASSTYPE"
131 .Fn SLIST_CLASS_HEAD "HEADNAME" "CLASSTYPE"
132 .Fn SLIST_EMPTY "SLIST_HEAD *head"
133 .Fn SLIST_ENTRY "TYPE"
134 .Fn SLIST_FIRST "SLIST_HEAD *head"
135 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
136 .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
137 .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
138 .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
139 .Fn SLIST_HEAD "HEADNAME" "TYPE"
140 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
141 .Fn SLIST_INIT "SLIST_HEAD *head"
142 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
143 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
144 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
145 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
146 .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
147 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
148 .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME"
150 .Fn STAILQ_CLASS_ENTRY "CLASSTYPE"
151 .Fn STAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE"
152 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
153 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
154 .Fn STAILQ_ENTRY "TYPE"
155 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
156 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
157 .Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
158 .Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
159 .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
160 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
161 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
162 .Fn STAILQ_INIT "STAILQ_HEAD *head"
163 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
164 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
165 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
166 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
167 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
168 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
169 .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
170 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
171 .Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "STAILQ_ENTRY NAME"
173 .Fn LIST_CLASS_ENTRY "CLASSTYPE"
174 .Fn LIST_CLASS_HEAD "HEADNAME" "CLASSTYPE"
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.
258 Singly-linked tail queues add the following functionality:
259 .Bl -enum -compact -offset indent
261 Entries can be added at the end of a list.
263 O(n) removal of any entry in the list.
265 They may be concatenated.
268 .Bl -enum -compact -offset indent
270 All list insertions must specify the head of the list.
272 Each head entry requires two pointers rather than one.
274 Code size is about 15% greater and operations run about 20% slower
275 than singly-linked lists.
278 Singly-linked tail queues are ideal for applications with large datasets and
280 or for implementing a FIFO queue.
282 All doubly linked types of data structures (lists and tail queues)
284 .Bl -enum -compact -offset indent
286 Insertion of a new entry before any element in the list.
288 O(1) removal of any entry in the list.
291 .Bl -enum -compact -offset indent
293 Each element requires two pointers rather than one.
295 Code size and execution time of operations (except for removal) is about
296 twice that of the singly-linked data-structures.
299 Linked lists are the simplest of the doubly linked data structures.
300 They add the following functionality over the above:
301 .Bl -enum -compact -offset indent
303 They may be traversed backwards.
306 .Bl -enum -compact -offset indent
308 To traverse backwards, an entry to begin the traversal and the list in
309 which it is contained must be specified.
312 Tail queues add the following functionality:
313 .Bl -enum -compact -offset indent
315 Entries can be added at the end of a list.
317 They may be traversed backwards, from tail to head.
319 They may be concatenated.
322 .Bl -enum -compact -offset indent
324 All list insertions and removals must specify the head of the list.
326 Each head entry requires two pointers rather than one.
328 Code size is about 15% greater and operations run about 20% slower
329 than singly-linked lists.
332 In the macro definitions,
334 is the name of a user defined structure.
335 The structure must contain a field called
343 In the macro definitions,
345 is the name of a user defined class.
346 The class must contain a field called
349 .Li SLIST_CLASS_ENTRY ,
350 .Li STAILQ_CLASS_ENTRY ,
351 .Li LIST_CLASS_ENTRY ,
353 .Li TAILQ_CLASS_ENTRY .
356 is the name of a user defined structure that must be declared
359 .Li SLIST_CLASS_HEAD ,
361 .Li STAILQ_CLASS_HEAD ,
363 .Li LIST_CLASS_HEAD ,
366 .Li TAILQ_CLASS_HEAD .
367 See the examples below for further explanation of how these
369 .Sh SINGLY-LINKED LISTS
370 A singly-linked list is headed by a structure defined by the
373 This structure contains a single pointer to the first element
375 The elements are singly linked for minimum space and pointer manipulation
376 overhead at the expense of O(n) removal for arbitrary elements.
377 New elements can be added to the list after an existing element or
378 at the head of the list.
381 structure is declared as follows:
382 .Bd -literal -offset indent
383 SLIST_HEAD(HEADNAME, TYPE) head;
388 is the name of the structure to be defined, and
390 is the type of the elements to be linked into the list.
391 A pointer to the head of the list can later be declared as:
392 .Bd -literal -offset indent
393 struct HEADNAME *headp;
400 are user selectable.)
403 .Nm SLIST_HEAD_INITIALIZER
404 evaluates to an initializer for the list
409 evaluates to true if there are no elements in the list.
413 declares a structure that connects the elements in
418 returns the first element in the list or NULL if the list is empty.
422 traverses the list referenced by
424 in the forward direction, assigning each element in
429 .Nm SLIST_FOREACH_FROM
430 behaves identically to
434 is NULL, else it treats
436 as a previously found SLIST element and begins the loop at
438 instead of the first element in the SLIST referenced by
442 .Nm SLIST_FOREACH_SAFE
443 traverses the list referenced by
445 in the forward direction, assigning each element in
450 here it is permitted to both remove
452 as well as free it from within the loop safely without interfering with the
456 .Nm SLIST_FOREACH_FROM_SAFE
457 behaves identically to
458 .Nm SLIST_FOREACH_SAFE
461 is NULL, else it treats
463 as a previously found SLIST element and begins the loop at
465 instead of the first element in the SLIST referenced by
470 initializes the list referenced by
474 .Nm SLIST_INSERT_HEAD
475 inserts the new element
477 at the head of the list.
480 .Nm SLIST_INSERT_AFTER
481 inserts the new element
488 returns the next element in the list.
491 .Nm SLIST_REMOVE_AFTER
492 removes the element after
497 this macro does not traverse the entire list.
500 .Nm SLIST_REMOVE_HEAD
503 from the head of the list.
504 For optimum efficiency,
505 elements being removed from the head of the list should explicitly use
506 this macro instead of the generic
518 swaps the contents of
522 .Sh SINGLY-LINKED LIST EXAMPLE
524 SLIST_HEAD(slisthead, entry) head =
525 SLIST_HEAD_INITIALIZER(head);
526 struct slisthead *headp; /* Singly-linked List head. */
529 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
531 } *n1, *n2, *n3, *np;
533 SLIST_INIT(&head); /* Initialize the list. */
535 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
536 SLIST_INSERT_HEAD(&head, n1, entries);
538 n2 = malloc(sizeof(struct entry)); /* Insert after. */
539 SLIST_INSERT_AFTER(n1, n2, entries);
541 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
544 n3 = SLIST_FIRST(&head);
545 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
547 /* Forward traversal. */
548 SLIST_FOREACH(np, &head, entries)
550 /* Safe forward traversal. */
551 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
554 SLIST_REMOVE(&head, np, entry, entries);
558 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
559 n1 = SLIST_FIRST(&head);
560 SLIST_REMOVE_HEAD(&head, entries);
564 .Sh SINGLY-LINKED TAIL QUEUES
565 A singly-linked tail queue is headed by a structure defined by the
568 This structure contains a pair of pointers,
569 one to the first element in the tail queue and the other to
570 the last element in the tail queue.
571 The elements are singly linked for minimum space and pointer
572 manipulation overhead at the expense of O(n) removal for arbitrary
574 New elements can be added to the tail queue after an existing element,
575 at the head of the tail queue, or at the end of the tail queue.
578 structure is declared as follows:
579 .Bd -literal -offset indent
580 STAILQ_HEAD(HEADNAME, TYPE) head;
585 is the name of the structure to be defined, and
587 is the type of the elements to be linked into the tail queue.
588 A pointer to the head of the tail queue can later be declared as:
589 .Bd -literal -offset indent
590 struct HEADNAME *headp;
597 are user selectable.)
600 .Nm STAILQ_HEAD_INITIALIZER
601 evaluates to an initializer for the tail queue
606 concatenates the tail queue headed by
608 onto the end of the one headed by
610 removing all entries from the former.
614 evaluates to true if there are no items on the tail queue.
618 declares a structure that connects the elements in
623 returns the first item on the tail queue or NULL if the tail queue
628 traverses the tail queue referenced by
630 in the forward direction, assigning each element
635 .Nm STAILQ_FOREACH_FROM
636 behaves identically to
640 is NULL, else it treats
642 as a previously found STAILQ element and begins the loop at
644 instead of the first element in the STAILQ referenced by
648 .Nm STAILQ_FOREACH_SAFE
649 traverses the tail queue referenced by
651 in the forward direction, assigning each element
656 here it is permitted to both remove
658 as well as free it from within the loop safely without interfering with the
662 .Nm STAILQ_FOREACH_FROM_SAFE
663 behaves identically to
664 .Nm STAILQ_FOREACH_SAFE
667 is NULL, else it treats
669 as a previously found STAILQ element and begins the loop at
671 instead of the first element in the STAILQ referenced by
676 initializes the tail queue referenced by
680 .Nm STAILQ_INSERT_HEAD
681 inserts the new element
683 at the head of the tail queue.
686 .Nm STAILQ_INSERT_TAIL
687 inserts the new element
689 at the end of the tail queue.
692 .Nm STAILQ_INSERT_AFTER
693 inserts the new element
700 returns the last item on the tail queue.
701 If the tail queue is empty the return value is
706 returns the next item on the tail queue, or NULL this item is the last.
709 .Nm STAILQ_REMOVE_AFTER
710 removes the element after
715 this macro does not traverse the entire tail queue.
718 .Nm STAILQ_REMOVE_HEAD
719 removes the element at the head of the tail queue.
720 For optimum efficiency,
721 elements being removed from the head of the tail queue should
722 use this macro explicitly rather than the generic
734 swaps the contents of
738 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
740 STAILQ_HEAD(stailhead, entry) head =
741 STAILQ_HEAD_INITIALIZER(head);
742 struct stailhead *headp; /* Singly-linked tail queue head. */
745 STAILQ_ENTRY(entry) entries; /* Tail queue. */
747 } *n1, *n2, *n3, *np;
749 STAILQ_INIT(&head); /* Initialize the queue. */
751 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
752 STAILQ_INSERT_HEAD(&head, n1, entries);
754 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
755 STAILQ_INSERT_TAIL(&head, n1, entries);
757 n2 = malloc(sizeof(struct entry)); /* Insert after. */
758 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
760 STAILQ_REMOVE(&head, n2, entry, entries);
762 /* Deletion from the head. */
763 n3 = STAILQ_FIRST(&head);
764 STAILQ_REMOVE_HEAD(&head, entries);
766 /* Forward traversal. */
767 STAILQ_FOREACH(np, &head, entries)
769 /* Safe forward traversal. */
770 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
773 STAILQ_REMOVE(&head, np, entry, entries);
776 /* TailQ Deletion. */
777 while (!STAILQ_EMPTY(&head)) {
778 n1 = STAILQ_FIRST(&head);
779 STAILQ_REMOVE_HEAD(&head, entries);
782 /* Faster TailQ Deletion. */
783 n1 = STAILQ_FIRST(&head);
785 n2 = STAILQ_NEXT(n1, entries);
792 A list is headed by a structure defined by the
795 This structure contains a single pointer to the first element
797 The elements are doubly linked so that an arbitrary element can be
798 removed without traversing the list.
799 New elements can be added to the list after an existing element,
800 before an existing element, or at the head of the list.
803 structure is declared as follows:
804 .Bd -literal -offset indent
805 LIST_HEAD(HEADNAME, TYPE) head;
810 is the name of the structure to be defined, and
812 is the type of the elements to be linked into the list.
813 A pointer to the head of the list can later be declared as:
814 .Bd -literal -offset indent
815 struct HEADNAME *headp;
822 are user selectable.)
825 .Nm LIST_HEAD_INITIALIZER
826 evaluates to an initializer for the list
831 evaluates to true if there are no elements in the list.
835 declares a structure that connects the elements in
840 returns the first element in the list or NULL if the list
845 traverses the list referenced by
847 in the forward direction, assigning each element in turn to
851 .Nm LIST_FOREACH_FROM
852 behaves identically to
856 is NULL, else it treats
858 as a previously found LIST element and begins the loop at
860 instead of the first element in the LIST referenced by
864 .Nm LIST_FOREACH_SAFE
865 traverses the list referenced by
867 in the forward direction, assigning each element in turn to
871 here it is permitted to both remove
873 as well as free it from within the loop safely without interfering with the
877 .Nm LIST_FOREACH_FROM_SAFE
878 behaves identically to
879 .Nm LIST_FOREACH_SAFE
882 is NULL, else it treats
884 as a previously found LIST element and begins the loop at
886 instead of the first element in the LIST referenced by
891 initializes the list referenced by
896 inserts the new element
898 at the head of the list.
901 .Nm LIST_INSERT_AFTER
902 inserts the new element
908 .Nm LIST_INSERT_BEFORE
909 inserts the new element
916 returns the next element in the list, or NULL if this is the last.
920 returns the previous element in the list, or NULL if this is the first.
934 swaps the contents of
940 LIST_HEAD(listhead, entry) head =
941 LIST_HEAD_INITIALIZER(head);
942 struct listhead *headp; /* List head. */
945 LIST_ENTRY(entry) entries; /* List. */
947 } *n1, *n2, *n3, *np, *np_temp;
949 LIST_INIT(&head); /* Initialize the list. */
951 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
952 LIST_INSERT_HEAD(&head, n1, entries);
954 n2 = malloc(sizeof(struct entry)); /* Insert after. */
955 LIST_INSERT_AFTER(n1, n2, entries);
957 n3 = malloc(sizeof(struct entry)); /* Insert before. */
958 LIST_INSERT_BEFORE(n2, n3, entries);
960 LIST_REMOVE(n2, entries); /* Deletion. */
962 /* Forward traversal. */
963 LIST_FOREACH(np, &head, entries)
966 /* Safe forward traversal. */
967 LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
970 LIST_REMOVE(np, entries);
974 while (!LIST_EMPTY(&head)) { /* List Deletion. */
975 n1 = LIST_FIRST(&head);
976 LIST_REMOVE(n1, entries);
980 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
982 n2 = LIST_NEXT(n1, entries);
989 A tail queue is headed by a structure defined by the
992 This structure contains a pair of pointers,
993 one to the first element in the tail queue and the other to
994 the last element in the tail queue.
995 The elements are doubly linked so that an arbitrary element can be
996 removed without traversing the tail queue.
997 New elements can be added to the tail queue after an existing element,
998 before an existing element, at the head of the tail queue,
999 or at the end of the tail queue.
1002 structure is declared as follows:
1003 .Bd -literal -offset indent
1004 TAILQ_HEAD(HEADNAME, TYPE) head;
1009 is the name of the structure to be defined, and
1011 is the type of the elements to be linked into the tail queue.
1012 A pointer to the head of the tail queue can later be declared as:
1013 .Bd -literal -offset indent
1014 struct HEADNAME *headp;
1021 are user selectable.)
1024 .Nm TAILQ_HEAD_INITIALIZER
1025 evaluates to an initializer for the tail queue
1030 concatenates the tail queue headed by
1032 onto the end of the one headed by
1034 removing all entries from the former.
1038 evaluates to true if there are no items on the tail queue.
1042 declares a structure that connects the elements in
1047 returns the first item on the tail queue or NULL if the tail queue
1052 traverses the tail queue referenced by
1054 in the forward direction, assigning each element in turn to
1059 if the loop completes normally, or if there were no elements.
1062 .Nm TAILQ_FOREACH_FROM
1063 behaves identically to
1067 is NULL, else it treats
1069 as a previously found TAILQ element and begins the loop at
1071 instead of the first element in the TAILQ referenced by
1075 .Nm TAILQ_FOREACH_REVERSE
1076 traverses the tail queue referenced by
1078 in the reverse direction, assigning each element in turn to
1082 .Nm TAILQ_FOREACH_REVERSE_FROM
1083 behaves identically to
1084 .Nm TAILQ_FOREACH_REVERSE
1087 is NULL, else it treats
1089 as a previously found TAILQ element and begins the reverse loop at
1091 instead of the last element in the TAILQ referenced by
1095 .Nm TAILQ_FOREACH_SAFE
1097 .Nm TAILQ_FOREACH_REVERSE_SAFE
1098 traverse the list referenced by
1100 in the forward or reverse direction respectively,
1101 assigning each element in turn to
1103 However, unlike their unsafe counterparts,
1106 .Nm TAILQ_FOREACH_REVERSE
1107 permit to both remove
1109 as well as free it from within the loop safely without interfering with the
1113 .Nm TAILQ_FOREACH_FROM_SAFE
1114 behaves identically to
1115 .Nm TAILQ_FOREACH_SAFE
1118 is NULL, else it treats
1120 as a previously found TAILQ element and begins the loop at
1122 instead of the first element in the TAILQ referenced by
1126 .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE
1127 behaves identically to
1128 .Nm TAILQ_FOREACH_REVERSE_SAFE
1131 is NULL, else it treats
1133 as a previously found TAILQ element and begins the reverse loop at
1135 instead of the last element in the TAILQ referenced by
1140 initializes the tail queue referenced by
1144 .Nm TAILQ_INSERT_HEAD
1145 inserts the new element
1147 at the head of the tail queue.
1150 .Nm TAILQ_INSERT_TAIL
1151 inserts the new element
1153 at the end of the tail queue.
1156 .Nm TAILQ_INSERT_AFTER
1157 inserts the new element
1163 .Nm TAILQ_INSERT_BEFORE
1164 inserts the new element
1171 returns the last item on the tail queue.
1172 If the tail queue is empty the return value is
1177 returns the next item on the tail queue, or NULL if this item is the last.
1181 returns the previous item on the tail queue, or NULL if this item
1188 from the tail queue.
1192 swaps the contents of
1196 .Sh TAIL QUEUE EXAMPLE
1198 TAILQ_HEAD(tailhead, entry) head =
1199 TAILQ_HEAD_INITIALIZER(head);
1200 struct tailhead *headp; /* Tail queue head. */
1203 TAILQ_ENTRY(entry) entries; /* Tail queue. */
1205 } *n1, *n2, *n3, *np;
1207 TAILQ_INIT(&head); /* Initialize the queue. */
1209 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
1210 TAILQ_INSERT_HEAD(&head, n1, entries);
1212 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
1213 TAILQ_INSERT_TAIL(&head, n1, entries);
1215 n2 = malloc(sizeof(struct entry)); /* Insert after. */
1216 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
1218 n3 = malloc(sizeof(struct entry)); /* Insert before. */
1219 TAILQ_INSERT_BEFORE(n2, n3, entries);
1221 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
1223 /* Forward traversal. */
1224 TAILQ_FOREACH(np, &head, entries)
1226 /* Safe forward traversal. */
1227 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
1230 TAILQ_REMOVE(&head, np, entries);
1233 /* Reverse traversal. */
1234 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
1236 /* TailQ Deletion. */
1237 while (!TAILQ_EMPTY(&head)) {
1238 n1 = TAILQ_FIRST(&head);
1239 TAILQ_REMOVE(&head, n1, entries);
1242 /* Faster TailQ Deletion. */
1243 n1 = TAILQ_FIRST(&head);
1244 while (n1 != NULL) {
1245 n2 = TAILQ_NEXT(n1, entries);
1256 functions first appeared in