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_FROM ,
44 .Nm SLIST_FOREACH_SAFE ,
45 .Nm SLIST_FOREACH_FROM_SAFE ,
47 .Nm SLIST_HEAD_INITIALIZER ,
49 .Nm SLIST_INSERT_AFTER ,
50 .Nm SLIST_INSERT_HEAD ,
52 .Nm SLIST_REMOVE_AFTER ,
53 .Nm SLIST_REMOVE_HEAD ,
61 .Nm STAILQ_FOREACH_FROM ,
62 .Nm STAILQ_FOREACH_SAFE ,
63 .Nm STAILQ_FOREACH_FROM_SAFE ,
65 .Nm STAILQ_HEAD_INITIALIZER ,
67 .Nm STAILQ_INSERT_AFTER ,
68 .Nm STAILQ_INSERT_HEAD ,
69 .Nm STAILQ_INSERT_TAIL ,
72 .Nm STAILQ_REMOVE_AFTER ,
73 .Nm STAILQ_REMOVE_HEAD ,
80 .Nm LIST_FOREACH_FROM ,
81 .Nm LIST_FOREACH_SAFE ,
82 .Nm LIST_FOREACH_FROM_SAFE ,
84 .Nm LIST_HEAD_INITIALIZER ,
86 .Nm LIST_INSERT_AFTER ,
87 .Nm LIST_INSERT_BEFORE ,
88 .Nm LIST_INSERT_HEAD ,
98 .Nm TAILQ_FOREACH_FROM ,
99 .Nm TAILQ_FOREACH_SAFE ,
100 .Nm TAILQ_FOREACH_FROM_SAFE ,
101 .Nm TAILQ_FOREACH_REVERSE ,
102 .Nm TAILQ_FOREACH_REVERSE_FROM ,
103 .Nm TAILQ_FOREACH_REVERSE_SAFE ,
104 .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE ,
106 .Nm TAILQ_HEAD_INITIALIZER ,
108 .Nm TAILQ_INSERT_AFTER ,
109 .Nm TAILQ_INSERT_BEFORE ,
110 .Nm TAILQ_INSERT_HEAD ,
111 .Nm TAILQ_INSERT_TAIL ,
117 .Nd implementations of singly-linked lists, singly-linked tail queues,
118 lists and tail queues
122 .Fn SLIST_EMPTY "SLIST_HEAD *head"
123 .Fn SLIST_ENTRY "TYPE"
124 .Fn SLIST_FIRST "SLIST_HEAD *head"
125 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
126 .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
127 .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
128 .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
129 .Fn SLIST_HEAD "HEADNAME" "TYPE"
130 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
131 .Fn SLIST_INIT "SLIST_HEAD *head"
132 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
133 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
134 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
135 .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
136 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
137 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
138 .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME"
140 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
141 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
142 .Fn STAILQ_ENTRY "TYPE"
143 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
144 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
145 .Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
146 .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
147 .Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
148 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
149 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
150 .Fn STAILQ_INIT "STAILQ_HEAD *head"
151 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
152 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
153 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
154 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
155 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
156 .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
157 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
158 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
159 .Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "STAILQ_ENTRY NAME"
161 .Fn LIST_EMPTY "LIST_HEAD *head"
162 .Fn LIST_ENTRY "TYPE"
163 .Fn LIST_FIRST "LIST_HEAD *head"
164 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
165 .Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
166 .Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
167 .Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
168 .Fn LIST_HEAD "HEADNAME" "TYPE"
169 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
170 .Fn LIST_INIT "LIST_HEAD *head"
171 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
172 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
173 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
174 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
175 .Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME"
176 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
177 .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
179 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
180 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
181 .Fn TAILQ_ENTRY "TYPE"
182 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
183 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
184 .Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
185 .Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
186 .Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
187 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
188 .Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
189 .Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
190 .Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
191 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
192 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
193 .Fn TAILQ_INIT "TAILQ_HEAD *head"
194 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
195 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
196 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
197 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
198 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
199 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
200 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
201 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
202 .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME"
205 These macros define and operate on four types of data structures:
206 singly-linked lists, singly-linked tail queues, lists, and tail queues.
207 All four structures support the following functionality:
208 .Bl -enum -compact -offset indent
210 Insertion of a new entry at the head of the list.
212 Insertion of a new entry after any element in the list.
214 O(1) removal of an entry from the head of the list.
216 Forward traversal through the list.
218 Swapping the contents of two lists.
221 Singly-linked lists are the simplest of the four data structures
222 and support only the above functionality.
223 Singly-linked lists are ideal for applications with large datasets
224 and few or no removals,
225 or for implementing a LIFO queue.
226 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:
233 .Bl -enum -compact -offset indent
235 Entries can be added at the end of a list.
237 O(n) removal of any entry in the list.
239 They may be concatenated.
242 .Bl -enum -compact -offset indent
244 All list insertions must specify the head of the list.
246 Each head entry requires two pointers rather than one.
248 Code size is about 15% greater and operations run about 20% slower
249 than singly-linked lists.
252 Singly-linked tail queues are ideal for applications with large datasets and
254 or for implementing a FIFO queue.
256 All doubly linked types of data structures (lists and tail queues)
258 .Bl -enum -compact -offset indent
260 Insertion of a new entry before any element in the list.
262 O(1) removal of any entry in the list.
265 .Bl -enum -compact -offset indent
267 Each element requires two pointers rather than one.
269 Code size and execution time of operations (except for removal) is about
270 twice that of the singly-linked data-structures.
273 Linked lists are the simplest of the doubly linked data structures.
274 They add the following functionality over the above:
275 .Bl -enum -compact -offset indent
277 They may be traversed backwards.
280 .Bl -enum -compact -offset indent
282 To traverse backwards, an entry to begin the traversal and the list in
283 which it is contained must be specified.
286 Tail queues add the following functionality:
287 .Bl -enum -compact -offset indent
289 Entries can be added at the end of a list.
291 They may be traversed backwards, from tail to head.
293 They may be concatenated.
296 .Bl -enum -compact -offset indent
298 All list insertions and removals must specify the head of the list.
300 Each head entry requires two pointers rather than one.
302 Code size is about 15% greater and operations run about 20% slower
303 than singly-linked lists.
306 In the macro definitions,
308 is the name of a user defined structure,
309 that must contain a field of type
319 is the name of a user defined structure that must be declared
326 See the examples below for further explanation of how these
328 .Sh SINGLY-LINKED LISTS
329 A singly-linked list is headed by a structure defined by the
332 This structure contains a single pointer to the first element
334 The elements are singly linked for minimum space and pointer manipulation
335 overhead at the expense of O(n) removal for arbitrary elements.
336 New elements can be added to the list after an existing element or
337 at the head of the list.
340 structure is declared as follows:
341 .Bd -literal -offset indent
342 SLIST_HEAD(HEADNAME, TYPE) head;
347 is the name of the structure to be defined, and
349 is the type of the elements to be linked into the list.
350 A pointer to the head of the list can later be declared as:
351 .Bd -literal -offset indent
352 struct HEADNAME *headp;
359 are user selectable.)
362 .Nm SLIST_HEAD_INITIALIZER
363 evaluates to an initializer for the list
368 evaluates to true if there are no elements in the list.
372 declares a structure that connects the elements in
377 returns the first element in the list or NULL if the list is empty.
381 traverses the list referenced by
383 in the forward direction, assigning each element in
388 .Nm SLIST_FOREACH_FROM
389 behaves identically to
393 is NULL, else it treats
395 as a previously found SLIST element and begins the loop at
397 instead of the first element in the SLIST referenced by
401 .Nm SLIST_FOREACH_SAFE
402 traverses the list referenced by
404 in the forward direction, assigning each element in
409 here it is permitted to both remove
411 as well as free it from within the loop safely without interfering with the
415 .Nm SLIST_FOREACH_FROM_SAFE
416 behaves identically to
417 .Nm SLIST_FOREACH_SAFE
420 is NULL, else it treats
422 as a previously found SLIST element and begins the loop at
424 instead of the first element in the SLIST referenced by
429 initializes the list referenced by
433 .Nm SLIST_INSERT_HEAD
434 inserts the new element
436 at the head of the list.
439 .Nm SLIST_INSERT_AFTER
440 inserts the new element
447 returns the next element in the list.
450 .Nm SLIST_REMOVE_AFTER
451 removes the element after
456 this macro does not traverse the entire list.
459 .Nm SLIST_REMOVE_HEAD
462 from the head of the list.
463 For optimum efficiency,
464 elements being removed from the head of the list should explicitly use
465 this macro instead of the generic
477 swaps the contents of
481 .Sh SINGLY-LINKED LIST EXAMPLE
483 SLIST_HEAD(slisthead, entry) head =
484 SLIST_HEAD_INITIALIZER(head);
485 struct slisthead *headp; /* Singly-linked List head. */
488 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
490 } *n1, *n2, *n3, *np;
492 SLIST_INIT(&head); /* Initialize the list. */
494 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
495 SLIST_INSERT_HEAD(&head, n1, entries);
497 n2 = malloc(sizeof(struct entry)); /* Insert after. */
498 SLIST_INSERT_AFTER(n1, n2, entries);
500 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
503 n3 = SLIST_FIRST(&head);
504 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
506 /* Forward traversal. */
507 SLIST_FOREACH(np, &head, entries)
509 /* Safe forward traversal. */
510 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
513 SLIST_REMOVE(&head, np, entry, entries);
517 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
518 n1 = SLIST_FIRST(&head);
519 SLIST_REMOVE_HEAD(&head, entries);
523 .Sh SINGLY-LINKED TAIL QUEUES
524 A singly-linked tail queue is headed by a structure defined by the
527 This structure contains a pair of pointers,
528 one to the first element in the tail queue and the other to
529 the last element in the tail queue.
530 The elements are singly linked for minimum space and pointer
531 manipulation overhead at the expense of O(n) removal for arbitrary
533 New elements can be added to the tail queue after an existing element,
534 at the head of the tail queue, or at the end of the tail queue.
537 structure is declared as follows:
538 .Bd -literal -offset indent
539 STAILQ_HEAD(HEADNAME, TYPE) head;
544 is the name of the structure to be defined, and
546 is the type of the elements to be linked into the tail queue.
547 A pointer to the head of the tail queue can later be declared as:
548 .Bd -literal -offset indent
549 struct HEADNAME *headp;
556 are user selectable.)
559 .Nm STAILQ_HEAD_INITIALIZER
560 evaluates to an initializer for the tail queue
565 concatenates the tail queue headed by
567 onto the end of the one headed by
569 removing all entries from the former.
573 evaluates to true if there are no items on the tail queue.
577 declares a structure that connects the elements in
582 returns the first item on the tail queue or NULL if the tail queue
587 traverses the tail queue referenced by
589 in the forward direction, assigning each element
594 .Nm STAILQ_FOREACH_FROM
595 behaves identically to
599 is NULL, else it treats
601 as a previously found STAILQ element and begins the loop at
603 instead of the first element in the STAILQ referenced by
607 .Nm STAILQ_FOREACH_SAFE
608 traverses the tail queue referenced by
610 in the forward direction, assigning each element
615 here it is permitted to both remove
617 as well as free it from within the loop safely without interfering with the
621 .Nm STAILQ_FOREACH_FROM_SAFE
622 behaves identically to
623 .Nm STAILQ_FOREACH_SAFE
626 is NULL, else it treats
628 as a previously found STAILQ element and begins the loop at
630 instead of the first element in the STAILQ referenced by
635 initializes the tail queue referenced by
639 .Nm STAILQ_INSERT_HEAD
640 inserts the new element
642 at the head of the tail queue.
645 .Nm STAILQ_INSERT_TAIL
646 inserts the new element
648 at the end of the tail queue.
651 .Nm STAILQ_INSERT_AFTER
652 inserts the new element
659 returns the last item on the tail queue.
660 If the tail queue is empty the return value is
665 returns the next item on the tail queue, or NULL this item is the last.
668 .Nm STAILQ_REMOVE_AFTER
669 removes the element after
674 this macro does not traverse the entire tail queue.
677 .Nm STAILQ_REMOVE_HEAD
678 removes the element at the head of the tail queue.
679 For optimum efficiency,
680 elements being removed from the head of the tail queue should
681 use this macro explicitly rather than the generic
693 swaps the contents of
697 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
699 STAILQ_HEAD(stailhead, entry) head =
700 STAILQ_HEAD_INITIALIZER(head);
701 struct stailhead *headp; /* Singly-linked tail queue head. */
704 STAILQ_ENTRY(entry) entries; /* Tail queue. */
706 } *n1, *n2, *n3, *np;
708 STAILQ_INIT(&head); /* Initialize the queue. */
710 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
711 STAILQ_INSERT_HEAD(&head, n1, entries);
713 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
714 STAILQ_INSERT_TAIL(&head, n1, entries);
716 n2 = malloc(sizeof(struct entry)); /* Insert after. */
717 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
719 STAILQ_REMOVE(&head, n2, entry, entries);
721 /* Deletion from the head. */
722 n3 = STAILQ_FIRST(&head);
723 STAILQ_REMOVE_HEAD(&head, entries);
725 /* Forward traversal. */
726 STAILQ_FOREACH(np, &head, entries)
728 /* Safe forward traversal. */
729 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
732 STAILQ_REMOVE(&head, np, entry, entries);
735 /* TailQ Deletion. */
736 while (!STAILQ_EMPTY(&head)) {
737 n1 = STAILQ_FIRST(&head);
738 STAILQ_REMOVE_HEAD(&head, entries);
741 /* Faster TailQ Deletion. */
742 n1 = STAILQ_FIRST(&head);
744 n2 = STAILQ_NEXT(n1, entries);
751 A list is headed by a structure defined by the
754 This structure contains a single pointer to the first element
756 The elements are doubly linked so that an arbitrary element can be
757 removed without traversing the list.
758 New elements can be added to the list after an existing element,
759 before an existing element, or at the head of the list.
762 structure is declared as follows:
763 .Bd -literal -offset indent
764 LIST_HEAD(HEADNAME, TYPE) head;
769 is the name of the structure to be defined, and
771 is the type of the elements to be linked into the list.
772 A pointer to the head of the list can later be declared as:
773 .Bd -literal -offset indent
774 struct HEADNAME *headp;
781 are user selectable.)
784 .Nm LIST_HEAD_INITIALIZER
785 evaluates to an initializer for the list
790 evaluates to true if there are no elements in the list.
794 declares a structure that connects the elements in
799 returns the first element in the list or NULL if the list
804 traverses the list referenced by
806 in the forward direction, assigning each element in turn to
810 .Nm LIST_FOREACH_FROM
811 behaves identically to
815 is NULL, else it treats
817 as a previously found LIST element and begins the loop at
819 instead of the first element in the LIST referenced by
823 .Nm LIST_FOREACH_SAFE
824 traverses the list referenced by
826 in the forward direction, assigning each element in turn to
830 here it is permitted to both remove
832 as well as free it from within the loop safely without interfering with the
836 .Nm LIST_FOREACH_FROM_SAFE
837 behaves identically to
838 .Nm LIST_FOREACH_SAFE
841 is NULL, else it treats
843 as a previously found LIST element and begins the loop at
845 instead of the first element in the LIST referenced by
850 initializes the list referenced by
855 inserts the new element
857 at the head of the list.
860 .Nm LIST_INSERT_AFTER
861 inserts the new element
867 .Nm LIST_INSERT_BEFORE
868 inserts the new element
875 returns the next element in the list, or NULL if this is the last.
879 returns the previous element in the list, or NULL if this is the first.
893 swaps the contents of
899 LIST_HEAD(listhead, entry) head =
900 LIST_HEAD_INITIALIZER(head);
901 struct listhead *headp; /* List head. */
904 LIST_ENTRY(entry) entries; /* List. */
906 } *n1, *n2, *n3, *np, *np_temp;
908 LIST_INIT(&head); /* Initialize the list. */
910 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
911 LIST_INSERT_HEAD(&head, n1, entries);
913 n2 = malloc(sizeof(struct entry)); /* Insert after. */
914 LIST_INSERT_AFTER(n1, n2, entries);
916 n3 = malloc(sizeof(struct entry)); /* Insert before. */
917 LIST_INSERT_BEFORE(n2, n3, entries);
919 LIST_REMOVE(n2, entries); /* Deletion. */
921 /* Forward traversal. */
922 LIST_FOREACH(np, &head, entries)
925 /* Safe forward traversal. */
926 LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
929 LIST_REMOVE(np, entries);
933 while (!LIST_EMPTY(&head)) { /* List Deletion. */
934 n1 = LIST_FIRST(&head);
935 LIST_REMOVE(n1, entries);
939 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
941 n2 = LIST_NEXT(n1, entries);
948 A tail queue is headed by a structure defined by the
951 This structure contains a pair of pointers,
952 one to the first element in the tail queue and the other to
953 the last element in the tail queue.
954 The elements are doubly linked so that an arbitrary element can be
955 removed without traversing the tail queue.
956 New elements can be added to the tail queue after an existing element,
957 before an existing element, at the head of the tail queue,
958 or at the end of the tail queue.
961 structure is declared as follows:
962 .Bd -literal -offset indent
963 TAILQ_HEAD(HEADNAME, TYPE) head;
968 is the name of the structure to be defined, and
970 is the type of the elements to be linked into the tail queue.
971 A pointer to the head of the tail queue can later be declared as:
972 .Bd -literal -offset indent
973 struct HEADNAME *headp;
980 are user selectable.)
983 .Nm TAILQ_HEAD_INITIALIZER
984 evaluates to an initializer for the tail queue
989 concatenates the tail queue headed by
991 onto the end of the one headed by
993 removing all entries from the former.
997 evaluates to true if there are no items on the tail queue.
1001 declares a structure that connects the elements in
1006 returns the first item on the tail queue or NULL if the tail queue
1011 traverses the tail queue referenced by
1013 in the forward direction, assigning each element in turn to
1018 if the loop completes normally, or if there were no elements.
1021 .Nm TAILQ_FOREACH_FROM
1022 behaves identically to
1026 is NULL, else it treats
1028 as a previously found TAILQ element and begins the loop at
1030 instead of the first element in the TAILQ referenced by
1034 .Nm TAILQ_FOREACH_REVERSE
1035 traverses the tail queue referenced by
1037 in the reverse direction, assigning each element in turn to
1041 .Nm TAILQ_FOREACH_REVERSE_FROM
1042 behaves identically to
1043 .Nm TAILQ_FOREACH_REVERSE
1046 is NULL, else it treats
1048 as a previously found TAILQ element and begins the reverse loop at
1050 instead of the last element in the TAILQ referenced by
1054 .Nm TAILQ_FOREACH_SAFE
1056 .Nm TAILQ_FOREACH_REVERSE_SAFE
1057 traverse the list referenced by
1059 in the forward or reverse direction respectively,
1060 assigning each element in turn to
1062 However, unlike their unsafe counterparts,
1065 .Nm TAILQ_FOREACH_REVERSE
1066 permit to both remove
1068 as well as free it from within the loop safely without interfering with the
1072 .Nm TAILQ_FOREACH_FROM_SAFE
1073 behaves identically to
1074 .Nm TAILQ_FOREACH_SAFE
1077 is NULL, else it treats
1079 as a previously found TAILQ element and begins the loop at
1081 instead of the first element in the TAILQ referenced by
1085 .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE
1086 behaves identically to
1087 .Nm TAILQ_FOREACH_REVERSE_SAFE
1090 is NULL, else it treats
1092 as a previously found TAILQ element and begins the reverse loop at
1094 instead of the last element in the TAILQ referenced by
1099 initializes the tail queue referenced by
1103 .Nm TAILQ_INSERT_HEAD
1104 inserts the new element
1106 at the head of the tail queue.
1109 .Nm TAILQ_INSERT_TAIL
1110 inserts the new element
1112 at the end of the tail queue.
1115 .Nm TAILQ_INSERT_AFTER
1116 inserts the new element
1122 .Nm TAILQ_INSERT_BEFORE
1123 inserts the new element
1130 returns the last item on the tail queue.
1131 If the tail queue is empty the return value is
1136 returns the next item on the tail queue, or NULL if this item is the last.
1140 returns the previous item on the tail queue, or NULL if this item
1147 from the tail queue.
1151 swaps the contents of
1155 .Sh TAIL QUEUE EXAMPLE
1157 TAILQ_HEAD(tailhead, entry) head =
1158 TAILQ_HEAD_INITIALIZER(head);
1159 struct tailhead *headp; /* Tail queue head. */
1162 TAILQ_ENTRY(entry) entries; /* Tail queue. */
1164 } *n1, *n2, *n3, *np;
1166 TAILQ_INIT(&head); /* Initialize the queue. */
1168 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
1169 TAILQ_INSERT_HEAD(&head, n1, entries);
1171 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
1172 TAILQ_INSERT_TAIL(&head, n1, entries);
1174 n2 = malloc(sizeof(struct entry)); /* Insert after. */
1175 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
1177 n3 = malloc(sizeof(struct entry)); /* Insert before. */
1178 TAILQ_INSERT_BEFORE(n2, n3, entries);
1180 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
1182 /* Forward traversal. */
1183 TAILQ_FOREACH(np, &head, entries)
1185 /* Safe forward traversal. */
1186 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
1189 TAILQ_REMOVE(&head, np, entries);
1192 /* Reverse traversal. */
1193 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
1195 /* TailQ Deletion. */
1196 while (!TAILQ_EMPTY(&head)) {
1197 n1 = TAILQ_FIRST(&head);
1198 TAILQ_REMOVE(&head, n1, entries);
1201 /* Faster TailQ Deletion. */
1202 n1 = TAILQ_FIRST(&head);
1203 while (n1 != NULL) {
1204 n2 = TAILQ_NEXT(n1, entries);
1215 functions first appeared in