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
33 .\" $FreeBSD: src/share/man/man3/queue.3,v 1.15.2.7 2001/12/18 10:09:02 ru Exp $
34 .\" $DragonFly: src/share/man/man3/queue.3,v 1.8 2008/10/17 12:41:38 swildner Exp $
45 .Nm SLIST_HEAD_INITIALIZER ,
47 .Nm SLIST_INSERT_AFTER ,
48 .Nm SLIST_INSERT_HEAD ,
50 .Nm SLIST_REMOVE_HEAD ,
57 .Nm STAILQ_FOREACH_MUTABLE ,
59 .Nm STAILQ_HEAD_INITIALIZER ,
61 .Nm STAILQ_INSERT_AFTER ,
62 .Nm STAILQ_INSERT_HEAD ,
63 .Nm STAILQ_INSERT_TAIL ,
66 .Nm STAILQ_REMOVE_HEAD ,
72 .Nm LIST_FOREACH_MUTABLE ,
74 .Nm LIST_HEAD_INITIALIZER ,
76 .Nm LIST_INSERT_AFTER ,
77 .Nm LIST_INSERT_BEFORE ,
78 .Nm LIST_INSERT_HEAD ,
86 .Nm TAILQ_FOREACH_SAFE ,
87 .Nm TAILQ_FOREACH_MUTABLE ,
88 .Nm TAILQ_FOREACH_REVERSE ,
90 .Nm TAILQ_HEAD_INITIALIZER ,
92 .Nm TAILQ_INSERT_AFTER ,
93 .Nm TAILQ_INSERT_BEFORE ,
94 .Nm TAILQ_INSERT_HEAD ,
95 .Nm TAILQ_INSERT_TAIL ,
103 .Nm CIRCLEQ_FOREACH ,
104 .Nm CIRCLEQ_FOREACH_REVERSE ,
106 .Nm CIRCLEQ_HEAD_INITIALIZER ,
108 .Nm CIRCLEQ_INSERT_AFTER ,
109 .Nm CIRCLEQ_INSERT_BEFORE ,
110 .Nm CIRCLEQ_INSERT_HEAD ,
111 .Nm CIRCLEQ_INSERT_TAIL ,
116 .Nd implementations of singly-linked lists, singly-linked tail queues,
117 lists, tail queues, and circular queues
121 .Fn SLIST_EMPTY "SLIST_HEAD *head"
122 .Fn SLIST_ENTRY "TYPE"
123 .Fn SLIST_FIRST "SLIST_HEAD *head"
124 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
125 .Fn SLIST_HEAD "HEADNAME" "TYPE"
126 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
127 .Fn SLIST_INIT "SLIST_HEAD *head"
128 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
129 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
130 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
131 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
132 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
134 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
135 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
136 .Fn STAILQ_ENTRY "TYPE"
137 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
138 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
139 .Fn STAILQ_FOREACH_MUTABLE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE * temp_var"
140 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
141 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
142 .Fn STAILQ_INIT "STAILQ_HEAD *head"
143 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
144 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
145 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
146 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
147 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
148 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
149 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
151 .Fn LIST_EMPTY "LIST_HEAD *head"
152 .Fn LIST_ENTRY "TYPE"
153 .Fn LIST_FIRST "LIST_HEAD *head"
154 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
155 .Fn LIST_FOREACH_MUTABLE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
156 .Fn LIST_HEAD "HEADNAME" "TYPE"
157 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
158 .Fn LIST_INIT "LIST_HEAD *head"
159 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
160 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
161 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
162 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
163 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
165 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
166 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
167 .Fn TAILQ_ENTRY "TYPE"
168 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
169 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
170 .Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
171 .Fn TAILQ_FOREACH_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
172 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
173 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
174 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
175 .Fn TAILQ_INIT "TAILQ_HEAD *head"
176 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
177 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
178 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
179 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
180 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
181 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
182 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
183 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
185 .Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
186 .Fn CIRCLEQ_ENTRY "TYPE"
187 .Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
188 .Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
189 .Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
190 .Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
191 .Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
192 .Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
193 .Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
194 .Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
195 .Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
196 .Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
197 .Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
198 .Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
199 .Fn CIRCLEQ_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
200 .Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
202 These macros define and operate on five types of data structures:
203 singly-linked lists, singly-linked tail queues, lists, tail queues,
205 All five structures support the following functionality:
206 .Bl -enum -compact -offset indent
208 Insertion of a new entry at the head of the list.
210 Insertion of a new entry after any element in the list.
212 O(1) removal of an entry from the head of the list.
214 O(n) removal of any entry in the list.
216 Forward traversal through the list.
219 Singly-linked lists are the simplest of the five data structures
220 and support only the above functionality.
221 Singly-linked lists are ideal for applications with large datasets
222 and few or no removals,
223 or for implementing a LIFO queue.
225 Singly-linked tail queues add the following functionality:
226 .Bl -enum -compact -offset indent
228 Entries can be added at the end of a list.
231 .Bl -enum -compact -offset indent
233 All list insertions must specify the head of the list.
235 Each head entry requires two pointers rather than one.
237 Code size is about 15% greater and operations run about 20% slower
238 than singly-linked lists.
241 Singly-linked tailqs are ideal for applications with large datasets and
243 or for implementing a FIFO queue.
245 All doubly linked types of data structures (lists, tail queues, and circle
246 queues) additionally allow:
247 .Bl -enum -compact -offset indent
249 Insertion of a new entry before any element in the list.
251 O(1) removal of any entry in the list.
254 .Bl -enum -compact -offset indent
256 Each elements requires two pointers rather than one.
258 Code size and execution time of operations (except for removal) is about
259 twice that of the singly-linked data-structures.
262 Linked lists are the simplest of the doubly linked data structures and support
263 only the above functionality over singly-linked lists.
265 Tail queues add the following functionality:
266 .Bl -enum -compact -offset indent
268 Entries can be added at the end of a list.
270 They may be traversed backwards, from tail to head.
273 .Bl -enum -compact -offset indent
275 All list insertions and removals must specify the head of the list.
277 Each head entry requires two pointers rather than one.
279 Code size is about 15% greater and operations run about 20% slower
280 than singly-linked lists.
283 Circular queues add the following functionality:
284 .Bl -enum -compact -offset indent
286 Entries can be added at the end of a list.
288 They may be traversed backwards, from tail to head.
291 .Bl -enum -compact -offset indent
293 All list insertions and removals must specify the head of the list.
295 Each head entry requires two pointers rather than one.
297 The termination condition for traversal is more complex.
299 Code size is about 40% greater and operations run about 45% slower
303 In the macro definitions,
305 is the name of a user defined structure,
306 that must contain a field of type
317 is the name of a user defined structure that must be declared
325 See the examples below for further explanation of how these
327 .Sh SINGLY-LINKED LISTS
328 A singly-linked list is headed by a structure defined by the
331 This structure contains a single pointer to the first element
333 The elements are singly linked for minimum space and pointer manipulation
334 overhead at the expense of O(n) removal for arbitrary elements.
335 New elements can be added to the list after an existing element or
336 at the head of the list.
339 structure is declared as follows:
340 .Bd -literal -offset indent
341 SLIST_HEAD(HEADNAME, TYPE) head;
346 is the name of the structure to be defined, and
348 is the type of the elements to be linked into the list.
349 A pointer to the head of the list can later be declared as:
350 .Bd -literal -offset indent
351 struct HEADNAME *headp;
358 are user selectable.)
361 .Nm SLIST_HEAD_INITIALIZER
362 evaluates to an initializer for the list
367 evaluates to true if there are no elements in the list.
371 declares a structure that connects the elements in
376 returns the first element in the list or NULL if the list is empty.
380 traverses the list referenced by
382 in the forward direction, assigning each element in
388 initializes the list referenced by
392 .Nm SLIST_INSERT_HEAD
393 inserts the new element
395 at the head of the list.
398 .Nm SLIST_INSERT_AFTER
399 inserts the new element
406 returns the next element in the list.
409 .Nm SLIST_REMOVE_HEAD
412 from the head of the list.
413 For optimum efficiency,
414 elements being removed from the head of the list should explicitly use
415 this macro instead of the generic
424 .Sh SINGLY-LINKED LIST EXAMPLE
426 SLIST_HEAD(slisthead, entry) head =
427 SLIST_HEAD_INITIALIZER(head);
428 struct slisthead *headp; /* Singly-linked List head. */
431 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
433 } *n1, *n2, *n3, *np;
435 SLIST_INIT(&head); /* Initialize the list. */
437 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
438 SLIST_INSERT_HEAD(&head, n1, entries);
440 n2 = malloc(sizeof(struct entry)); /* Insert after. */
441 SLIST_INSERT_AFTER(n1, n2, entries);
443 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
446 n3 = SLIST_FIRST(&head);
447 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
449 /* Forward traversal. */
450 SLIST_FOREACH(np, &head, entries)
453 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
454 n1 = SLIST_FIRST(&head);
455 SLIST_REMOVE_HEAD(&head, entries);
459 .Sh SINGLY-LINKED TAIL QUEUES
460 A singly-linked tail queue is headed by a structure defined by the
463 This structure contains a pair of pointers,
464 one to the first element in the tail queue and the other to
465 the last element in the tail queue.
466 The elements are singly linked for minimum space and pointer
467 manipulation overhead at the expense of O(n) removal for arbitrary
469 New elements can be added to the tail queue after an existing element,
470 at the head of the tail queue, or at the end of the tail queue.
473 structure is declared as follows:
474 .Bd -literal -offset indent
475 STAILQ_HEAD(HEADNAME, TYPE) head;
480 is the name of the structure to be defined, and
482 is the type of the elements to be linked into the tail queue.
483 A pointer to the head of the tail queue can later be declared as:
484 .Bd -literal -offset indent
485 struct HEADNAME *headp;
492 are user selectable.)
495 .Nm STAILQ_HEAD_INITIALIZER
496 evaluates to an initializer for the tail queue
501 concatenates the tail queue headed by
503 onto the end of the one headed by
505 removing all entries from the former.
509 evaluates to true if there are no items on the tail queue.
513 declares a structure that connects the elements in
518 returns the first item on the tail queue or NULL if the tail queue
523 traverses the tail queue referenced by
525 in the forward direction, assigning each element
530 .Nm STAILQ_FOREACH_MUTABLE
531 traverses the tail queue referenced by
533 in the forward direction, assigning each element
538 here it is permitted to both remove
540 as well as free it from within the loop safely without interfering with the
545 initializes the tail queue referenced by
549 .Nm STAILQ_INSERT_HEAD
550 inserts the new element
552 at the head of the tail queue.
555 .Nm STAILQ_INSERT_TAIL
556 inserts the new element
558 at the end of the tail queue.
561 .Nm STAILQ_INSERT_AFTER
562 inserts the new element
569 returns the last item on the tail queue.
570 If the tail queue is empty the return value is undefined.
574 returns the next item on the tail queue, or NULL this item is the last.
577 .Nm STAILQ_REMOVE_HEAD
578 removes the element at the head of the tail queue.
579 For optimum efficiency,
580 elements being removed from the head of the tail queue should
581 use this macro explicitly rather than the generic
590 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
592 STAILQ_HEAD(stailhead, entry) head =
593 STAILQ_HEAD_INITIALIZER(head);
594 struct stailhead *headp; /* Singly-linked tail queue head. */
597 STAILQ_ENTRY(entry) entries; /* Tail queue. */
599 } *n1, *n2, *n3, *np;
601 STAILQ_INIT(&head); /* Initialize the queue. */
603 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
604 STAILQ_INSERT_HEAD(&head, n1, entries);
606 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
607 STAILQ_INSERT_TAIL(&head, n1, entries);
609 n2 = malloc(sizeof(struct entry)); /* Insert after. */
610 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
612 STAILQ_REMOVE(&head, n2, entry, entries);
614 /* Deletion from the head. */
615 n3 = STAILQ_FIRST(&head);
616 STAILQ_REMOVE_HEAD(&head, entries);
618 /* Forward traversal. */
619 STAILQ_FOREACH(np, &head, entries)
621 /* TailQ Deletion. */
622 while (!STAILQ_EMPTY(&head)) {
623 n1 = STAILQ_FIRST(&head);
624 STAILQ_REMOVE_HEAD(&head, entries);
627 /* Faster TailQ Deletion. */
628 n1 = STAILQ_FIRST(&head);
630 n2 = STAILQ_NEXT(n1, entries);
637 A list is headed by a structure defined by the
640 This structure contains a single pointer to the first element
642 The elements are doubly linked so that an arbitrary element can be
643 removed without traversing the list.
644 New elements can be added to the list after an existing element,
645 before an existing element, or at the head of the list.
648 structure is declared as follows:
649 .Bd -literal -offset indent
650 LIST_HEAD(HEADNAME, TYPE) head;
655 is the name of the structure to be defined, and
657 is the type of the elements to be linked into the list.
658 A pointer to the head of the list can later be declared as:
659 .Bd -literal -offset indent
660 struct HEADNAME *headp;
667 are user selectable.)
670 .Nm LIST_HEAD_INITIALIZER
671 evaluates to an initializer for the list
676 evaluates to true if there are no elements in the list.
680 declares a structure that connects the elements in
685 returns the first element in the list or NULL if the list
690 traverses the list referenced by
692 in the forward direction, assigning each element in turn to
696 .Nm LIST_FOREACH_MUTABLE
697 traverses the list referenced by
699 in the forward direction, assigning each element in turn to
703 it is permitted to remove
705 from the list without interfering with the traversal.
709 initializes the list referenced by
714 inserts the new element
716 at the head of the list.
719 .Nm LIST_INSERT_AFTER
720 inserts the new element
726 .Nm LIST_INSERT_BEFORE
727 inserts the new element
734 returns the next element in the list, or NULL if this is the last.
743 LIST_HEAD(listhead, entry) head =
744 LIST_HEAD_INITIALIZER(head);
745 struct listhead *headp; /* List head. */
748 LIST_ENTRY(entry) entries; /* List. */
750 } *n1, *n2, *n3, *np;
752 LIST_INIT(&head); /* Initialize the list. */
754 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
755 LIST_INSERT_HEAD(&head, n1, entries);
757 n2 = malloc(sizeof(struct entry)); /* Insert after. */
758 LIST_INSERT_AFTER(n1, n2, entries);
760 n3 = malloc(sizeof(struct entry)); /* Insert before. */
761 LIST_INSERT_BEFORE(n2, n3, entries);
763 LIST_REMOVE(n2, entries); /* Deletion. */
765 /* Forward traversal. */
766 LIST_FOREACH(np, &head, entries)
769 while (!LIST_EMPTY(&head)) { /* List Deletion. */
770 n1 = LIST_FIRST(&head);
771 LIST_REMOVE(n1, entries);
775 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
777 n2 = LIST_NEXT(n1, entries);
784 A tail queue is headed by a structure defined by the
787 This structure contains a pair of pointers,
788 one to the first element in the tail queue and the other to
789 the last element in the tail queue.
790 The elements are doubly linked so that an arbitrary element can be
791 removed without traversing the tail queue.
792 New elements can be added to the tail queue after an existing element,
793 before an existing element, at the head of the tail queue,
794 or at the end of the tail queue.
797 structure is declared as follows:
798 .Bd -literal -offset indent
799 TAILQ_HEAD(HEADNAME, TYPE) head;
804 is the name of the structure to be defined, and
806 is the type of the elements to be linked into the tail queue.
807 A pointer to the head of the tail queue can later be declared as:
808 .Bd -literal -offset indent
809 struct HEADNAME *headp;
816 are user selectable.)
819 .Nm TAILQ_HEAD_INITIALIZER
820 evaluates to an initializer for the tail queue
825 concatenates the tail queue headed by
827 onto the end of the one headed by
829 removing all entries from the former.
833 evaluates to true if there are no items on the tail queue.
837 declares a structure that connects the elements in
842 returns the first item on the tail queue or NULL if the tail queue
847 traverses the tail queue referenced by
849 in the forward direction, assigning each element in turn to
853 .Nm TAILQ_FOREACH_MUTABLE
854 traverses the tail queue referenced by
856 in the forward direction, assigning each element in turn to
860 it is permitted to remove
862 from the tail queue without interfering with the traversal.
865 .Nm TAILQ_FOREACH_REVERSE
866 traverses the tail queue referenced by
868 in the reverse direction, assigning each element in turn to
872 .Nm TAILQ_FOREACH_SAFE
873 traverses the list referenced by
875 in the forward direction,
876 assigning each element in turn to
878 However, unlike its unsafe counterpart,
879 .Nm TAILQ_FOREACH_SAVE
880 permits to both remove
882 as well as free it from within the loop safely without interfering with the
887 initializes the tail queue referenced by
891 .Nm TAILQ_INSERT_HEAD
892 inserts the new element
894 at the head of the tail queue.
897 .Nm TAILQ_INSERT_TAIL
898 inserts the new element
900 at the end of the tail queue.
903 .Nm TAILQ_INSERT_AFTER
904 inserts the new element
910 .Nm TAILQ_INSERT_BEFORE
911 inserts the new element
918 returns the last item on the tail queue.
919 If the tail queue is empty the return value is undefined.
923 returns the next item on the tail queue, or NULL if this item is the last.
927 returns the previous item on the tail queue, or NULL if this item
935 .Sh TAIL QUEUE EXAMPLE
937 TAILQ_HEAD(tailhead, entry) head =
938 TAILQ_HEAD_INITIALIZER(head);
939 struct tailhead *headp; /* Tail queue head. */
942 TAILQ_ENTRY(entry) entries; /* Tail queue. */
944 } *n1, *n2, *n3, *np;
946 TAILQ_INIT(&head); /* Initialize the queue. */
948 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
949 TAILQ_INSERT_HEAD(&head, n1, entries);
951 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
952 TAILQ_INSERT_TAIL(&head, n1, entries);
954 n2 = malloc(sizeof(struct entry)); /* Insert after. */
955 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
957 n3 = malloc(sizeof(struct entry)); /* Insert before. */
958 TAILQ_INSERT_BEFORE(n2, n3, entries);
960 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
962 /* Forward traversal. */
963 TAILQ_FOREACH(np, &head, entries)
965 /* Safe forward traversal. */
966 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
969 TAILQ_REMOVE(&head, np, entries);
972 /* Reverse traversal. */
973 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
975 /* TailQ Deletion. */
976 while (!TAILQ_EMPTY(&head)) {
977 n1 = TAILQ_FIRST(&head);
978 TAILQ_REMOVE(&head, n1, entries);
981 /* Faster TailQ Deletion. */
982 n1 = TAILQ_FIRST(&head);
984 n2 = TAILQ_NEXT(n1, entries);
991 A circular queue is headed by a structure defined by the
994 This structure contains a pair of pointers,
995 one to the first element in the circular queue and the other to the
996 last element in the circular queue.
997 The elements are doubly linked so that an arbitrary element can be
998 removed without traversing the queue.
999 New elements can be added to the queue after an existing element,
1000 before an existing element, at the head of the queue, or at the end
1004 structure is declared as follows:
1005 .Bd -literal -offset indent
1006 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
1011 is the name of the structure to be defined, and
1013 is the type of the elements to be linked into the circular queue.
1014 A pointer to the head of the circular queue can later be declared as:
1015 .Bd -literal -offset indent
1016 struct HEADNAME *headp;
1023 are user selectable.)
1026 .Nm CIRCLEQ_HEAD_INITIALIZER
1027 evaluates to an initializer for the circle queue
1032 evaluates to true if there are no items on the circle queue.
1036 declares a structure that connects the elements in
1041 returns the first item on the circle queue.
1045 traverses the circle queue referenced by
1047 in the forward direction, assigning each element in turn to
1051 .Nm CICRLEQ_FOREACH_REVERSE
1052 traverses the circle queue referenced by
1054 in the reverse direction, assigning each element in turn to
1059 initializes the circular queue referenced by
1063 .Nm CIRCLEQ_INSERT_HEAD
1064 inserts the new element
1066 at the head of the circular queue.
1069 .Nm CIRCLEQ_INSERT_TAIL
1070 inserts the new element
1072 at the end of the circular queue.
1075 .Nm CIRCLEQ_INSERT_AFTER
1076 inserts the new element
1082 .Nm CIRCLEQ_INSERT_BEFORE
1083 inserts the new element
1090 returns the last item on the circle queue.
1094 returns the next item on the circle queue.
1098 returns the previous item on the circle queue.
1104 from the circular queue.
1105 .Sh CIRCULAR QUEUE EXAMPLE
1107 CIRCLEQ_HEAD(circlehead, entry) head =
1108 CIRCLEQ_HEAD_INITIALIZER(head);
1109 struct circlehead *headp; /* Circular queue head. */
1112 CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
1116 CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
1118 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
1119 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
1121 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
1122 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
1124 n2 = malloc(sizeof(struct entry)); /* Insert after. */
1125 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
1127 n2 = malloc(sizeof(struct entry)); /* Insert before. */
1128 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
1130 CIRCLEQ_REMOVE(&head, n1, entries); /* Deletion. */
1132 /* Forward traversal. */
1133 CIRCLEQ_FOREACH(np, &head, entries)
1135 /* Reverse traversal. */
1136 CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
1138 /* CircleQ Deletion. */
1139 while (CIRCLEQ_FIRST(&head) != (void *)&head) {
1140 n1 = CIRCLEQ_HEAD(&head);
1141 CIRCLEQ_REMOVE(&head, n1, entries);
1144 /* Faster CircleQ Deletion. */
1145 n1 = CIRCLEQ_FIRST(&head);
1146 while (n1 != (void *)&head) {
1147 n2 = CIRCLEQ_NEXT(n1, entries);
1151 CIRCLEQ_INIT(&head);
1156 functions first appeared in