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.3 2004/08/12 15:07:42 joerg Exp $
45 .Nm SLIST_HEAD_INITIALIZER ,
47 .Nm SLIST_INSERT_AFTER ,
48 .Nm SLIST_INSERT_HEAD ,
50 .Nm SLIST_REMOVE_HEAD ,
57 .Nm STAILQ_HEAD_INITIALIZER ,
59 .Nm STAILQ_INSERT_AFTER ,
60 .Nm STAILQ_INSERT_HEAD ,
61 .Nm STAILQ_INSERT_TAIL ,
64 .Nm STAILQ_REMOVE_HEAD ,
70 .Nm LIST_FOREACH_MUTABLE ,
72 .Nm LIST_HEAD_INITIALIZER ,
74 .Nm LIST_INSERT_AFTER ,
75 .Nm LIST_INSERT_BEFORE ,
76 .Nm LIST_INSERT_HEAD ,
83 .Nm TAILQ_FOREACH_MUTABLE ,
84 .Nm TAILQ_FOREACH_REVERSE ,
86 .Nm TAILQ_HEAD_INITIALIZER ,
88 .Nm TAILQ_INSERT_AFTER ,
89 .Nm TAILQ_INSERT_BEFORE ,
90 .Nm TAILQ_INSERT_HEAD ,
91 .Nm TAILQ_INSERT_TAIL ,
100 .Nm CIRCLEQ_FOREACH_REVERSE ,
102 .Nm CIRCLEQ_HEAD_INITIALIZER ,
104 .Nm CIRCLEQ_INSERT_AFTER ,
105 .Nm CIRCLEQ_INSERT_BEFORE ,
106 .Nm CIRCLEQ_INSERT_HEAD ,
107 .Nm CIRCLEQ_INSERT_TAIL ,
112 .Nd implementations of singly-linked lists, singly-linked tail queues,
113 lists, tail queues, and circular queues
117 .Fn SLIST_EMPTY "SLIST_HEAD *head"
118 .Fn SLIST_ENTRY "TYPE"
119 .Fn SLIST_FIRST "SLIST_HEAD *head"
120 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
121 .Fn SLIST_HEAD "HEADNAME" "TYPE"
122 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
123 .Fn SLIST_INIT "SLIST_HEAD *head"
124 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
125 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
126 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
127 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
128 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
130 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
131 .Fn STAILQ_ENTRY "TYPE"
132 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
133 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
134 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
135 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
136 .Fn STAILQ_INIT "STAILQ_HEAD *head"
137 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
138 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
139 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
140 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
141 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
142 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
143 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
145 .Fn LIST_EMPTY "LIST_HEAD *head"
146 .Fn LIST_ENTRY "TYPE"
147 .Fn LIST_FIRST "LIST_HEAD *head"
148 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
149 .Fn LIST_FOREACH_MUTABLE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
150 .Fn LIST_HEAD "HEADNAME" "TYPE"
151 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
152 .Fn LIST_INIT "LIST_HEAD *head"
153 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
154 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
155 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
156 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
157 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
159 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
160 .Fn TAILQ_ENTRY "TYPE"
161 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
162 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
163 .Fn TAILQ_FOREACH_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
164 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
165 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
166 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
167 .Fn TAILQ_INIT "TAILQ_HEAD *head"
168 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
169 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
170 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
171 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
172 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
173 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
174 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
175 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
177 .Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
178 .Fn CIRCLEQ_ENTRY "TYPE"
179 .Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
180 .Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
181 .Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
182 .Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
183 .Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
184 .Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
185 .Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
186 .Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
187 .Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
188 .Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
189 .Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
190 .Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
191 .Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
192 .Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
194 These macros define and operate on five types of data structures:
195 singly-linked lists, singly-linked tail queues, lists, tail queues,
197 All five structures support the following functionality:
198 .Bl -enum -compact -offset indent
200 Insertion of a new entry at the head of the list.
202 Insertion of a new entry after any element in the list.
204 O(1) removal of an entry from the head of the list.
206 O(n) removal of any entry in the list.
208 Forward traversal through the list.
211 Singly-linked lists are the simplest of the five data structures
212 and support only the above functionality.
213 Singly-linked lists are ideal for applications with large datasets
214 and few or no removals,
215 or for implementing a LIFO queue.
217 Singly-linked tail queues add the following functionality:
218 .Bl -enum -compact -offset indent
220 Entries can be added at the end of a list.
223 .Bl -enum -compact -offset indent
225 All list insertions must specify the head of the list.
227 Each head entry requires two pointers rather than one.
229 Code size is about 15% greater and operations run about 20% slower
230 than singly-linked lists.
233 Singly-linked tailqs are ideal for applications with large datasets and
235 or for implementing a FIFO queue.
237 All doubly linked types of data structures (lists, tail queues, and circle
238 queues) additionally allow:
239 .Bl -enum -compact -offset indent
241 Insertion of a new entry before any element in the list.
243 O(1) removal of any entry in the list.
246 .Bl -enum -compact -offset indent
248 Each elements requires two pointers rather than one.
250 Code size and execution time of operations (except for removal) is about
251 twice that of the singly-linked data-structures.
254 Linked lists are the simplest of the doubly linked data structures and support
255 only the above functionality over singly-linked lists.
257 Tail queues add the following functionality:
258 .Bl -enum -compact -offset indent
260 Entries can be added at the end of a list.
262 They may be traversed backwards, from tail to head.
265 .Bl -enum -compact -offset indent
267 All list insertions and removals must specify the head of the list.
269 Each head entry requires two pointers rather than one.
271 Code size is about 15% greater and operations run about 20% slower
272 than singly-linked lists.
275 Circular queues add the following functionality:
276 .Bl -enum -compact -offset indent
278 Entries can be added at the end of a list.
280 They may be traversed backwards, from tail to head.
283 .Bl -enum -compact -offset indent
285 All list insertions and removals must specify the head of the list.
287 Each head entry requires two pointers rather than one.
289 The termination condition for traversal is more complex.
291 Code size is about 40% greater and operations run about 45% slower
295 In the macro definitions,
297 is the name of a user defined structure,
298 that must contain a field of type
309 is the name of a user defined structure that must be declared
317 See the examples below for further explanation of how these
319 .Sh SINGLY-LINKED LISTS
320 A singly-linked list is headed by a structure defined by the
323 This structure contains a single pointer to the first element
325 The elements are singly linked for minimum space and pointer manipulation
326 overhead at the expense of O(n) removal for arbitrary elements.
327 New elements can be added to the list after an existing element or
328 at the head of the list.
331 structure is declared as follows:
332 .Bd -literal -offset indent
333 SLIST_HEAD(HEADNAME, TYPE) head;
338 is the name of the structure to be defined, and
340 is the type of the elements to be linked into the list.
341 A pointer to the head of the list can later be declared as:
342 .Bd -literal -offset indent
343 struct HEADNAME *headp;
350 are user selectable.)
353 .Nm SLIST_HEAD_INITIALIZER
354 evaluates to an initializer for the list
359 evaluates to true if there are no elements in the list.
363 declares a structure that connects the elements in
368 returns the first element in the list or NULL if the list is empty.
372 traverses the list referenced by
374 in the forward direction, assigning each element in
380 initializes the list referenced by
384 .Nm SLIST_INSERT_HEAD
385 inserts the new element
387 at the head of the list.
390 .Nm SLIST_INSERT_AFTER
391 inserts the new element
398 returns the next element in the list.
401 .Nm SLIST_REMOVE_HEAD
404 from the head of the list.
405 For optimum efficiency,
406 elements being removed from the head of the list should explicitly use
407 this macro instead of the generic
416 .Sh SINGLY-LINKED LIST EXAMPLE
418 SLIST_HEAD(slisthead, entry) head =
419 SLIST_HEAD_INITIALIZER(head);
420 struct slisthead *headp; /* Singly-linked List head. */
423 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
425 } *n1, *n2, *n3, *np;
427 SLIST_INIT(&head); /* Initialize the list. */
429 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
430 SLIST_INSERT_HEAD(&head, n1, entries);
432 n2 = malloc(sizeof(struct entry)); /* Insert after. */
433 SLIST_INSERT_AFTER(n1, n2, entries);
435 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
438 n3 = SLIST_FIRST(&head);
439 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
441 /* Forward traversal. */
442 SLIST_FOREACH(np, &head, entries)
445 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
446 n1 = SLIST_FIRST(&head);
447 SLIST_REMOVE_HEAD(&head, entries);
451 .Sh SINGLY-LINKED TAIL QUEUES
452 A singly-linked tail queue is headed by a structure defined by the
455 This structure contains a pair of pointers,
456 one to the first element in the tail queue and the other to
457 the last element in the tail queue.
458 The elements are singly linked for minimum space and pointer
459 manipulation overhead at the expense of O(n) removal for arbitrary
461 New elements can be added to the tail queue after an existing element,
462 at the head of the tail queue, or at the end of the tail queue.
465 structure is declared as follows:
466 .Bd -literal -offset indent
467 STAILQ_HEAD(HEADNAME, TYPE) head;
472 is the name of the structure to be defined, and
474 is the type of the elements to be linked into the tail queue.
475 A pointer to the head of the tail queue can later be declared as:
476 .Bd -literal -offset indent
477 struct HEADNAME *headp;
484 are user selectable.)
487 .Nm STAILQ_HEAD_INITIALIZER
488 evaluates to an initializer for the tail queue
493 evaluates to true if there are no items on the tail queue.
497 declares a structure that connects the elements in
502 returns the first item on the tail queue or NULL if the tail queue
507 traverses the tail queue referenced by
509 in the forward direction, assigning each element
515 initializes the tail queue referenced by
519 .Nm STAILQ_INSERT_HEAD
520 inserts the new element
522 at the head of the tail queue.
525 .Nm STAILQ_INSERT_TAIL
526 inserts the new element
528 at the end of the tail queue.
531 .Nm STAILQ_INSERT_AFTER
532 inserts the new element
539 returns the last item on the tail queue.
540 If the tail queue is empty the return value is undefined.
544 returns the next item on the tail queue, or NULL this item is the last.
547 .Nm STAILQ_REMOVE_HEAD
548 removes the element at the head of the tail queue.
549 For optimum efficiency,
550 elements being removed from the head of the tail queue should
551 use this macro explicitly rather than the generic
560 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
562 STAILQ_HEAD(stailhead, entry) head =
563 STAILQ_HEAD_INITIALIZER(head);
564 struct stailhead *headp; /* Singly-linked tail queue head. */
567 STAILQ_ENTRY(entry) entries; /* Tail queue. */
569 } *n1, *n2, *n3, *np;
571 STAILQ_INIT(&head); /* Initialize the queue. */
573 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
574 STAILQ_INSERT_HEAD(&head, n1, entries);
576 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
577 STAILQ_INSERT_TAIL(&head, n1, entries);
579 n2 = malloc(sizeof(struct entry)); /* Insert after. */
580 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
582 STAILQ_REMOVE(&head, n2, entry, entries);
584 /* Deletion from the head. */
585 n3 = STAILQ_FIRST(&head);
586 STAILQ_REMOVE_HEAD(&head, entries);
588 /* Forward traversal. */
589 STAILQ_FOREACH(np, &head, entries)
591 /* TailQ Deletion. */
592 while (!STAILQ_EMPTY(&head)) {
593 n1 = STAILQ_FIRST(&head);
594 STAILQ_REMOVE_HEAD(&head, entries);
597 /* Faster TailQ Deletion. */
598 n1 = STAILQ_FIRST(&head);
600 n2 = STAILQ_NEXT(n1, entries);
607 A list is headed by a structure defined by the
610 This structure contains a single pointer to the first element
612 The elements are doubly linked so that an arbitrary element can be
613 removed without traversing the list.
614 New elements can be added to the list after an existing element,
615 before an existing element, or at the head of the list.
618 structure is declared as follows:
619 .Bd -literal -offset indent
620 LIST_HEAD(HEADNAME, TYPE) head;
625 is the name of the structure to be defined, and
627 is the type of the elements to be linked into the list.
628 A pointer to the head of the list can later be declared as:
629 .Bd -literal -offset indent
630 struct HEADNAME *headp;
637 are user selectable.)
640 .Nm LIST_HEAD_INITIALIZER
641 evaluates to an initializer for the list
646 evaluates to true if their are no elements in the list.
650 declares a structure that connects the elements in
655 returns the first element in the list or NULL if the list
660 traverses the list referenced by
662 in the forward direction, assigning each element in turn to
666 .Nm LIST_FOREACH_MUTABLE
667 traverses the list referenced by
669 in the forward direction, assigning each element in turn to
673 it is permitted to remove
675 from the list without interfering with the traversal.
679 initializes the list referenced by
684 inserts the new element
686 at the head of the list.
689 .Nm LIST_INSERT_AFTER
690 inserts the new element
696 .Nm LIST_INSERT_BEFORE
697 inserts the new element
704 returns the next element in the list, or NULL if this is the last.
713 LIST_HEAD(listhead, entry) head =
714 LIST_HEAD_INITIALIZER(head);
715 struct listhead *headp; /* List head. */
718 LIST_ENTRY(entry) entries; /* List. */
720 } *n1, *n2, *n3, *np;
722 LIST_INIT(&head); /* Initialize the list. */
724 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
725 LIST_INSERT_HEAD(&head, n1, entries);
727 n2 = malloc(sizeof(struct entry)); /* Insert after. */
728 LIST_INSERT_AFTER(n1, n2, entries);
730 n3 = malloc(sizeof(struct entry)); /* Insert before. */
731 LIST_INSERT_BEFORE(n2, n3, entries);
733 LIST_REMOVE(n2, entries); /* Deletion. */
735 /* Forward traversal. */
736 LIST_FOREACH(np, &head, entries)
739 while (!LIST_EMPTY(&head)) { /* List Deletion. */
740 n1 = LIST_FIRST(&head);
741 LIST_REMOVE(n1, entries);
745 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
747 n2 = LIST_NEXT(n1, entries);
754 A tail queue is headed by a structure defined by the
757 This structure contains a pair of pointers,
758 one to the first element in the tail queue and the other to
759 the last element in the tail queue.
760 The elements are doubly linked so that an arbitrary element can be
761 removed without traversing the tail queue.
762 New elements can be added to the tail queue after an existing element,
763 before an existing element, at the head of the tail queue,
764 or at the end of the tail queue.
767 structure is declared as follows:
768 .Bd -literal -offset indent
769 TAILQ_HEAD(HEADNAME, TYPE) head;
774 is the name of the structure to be defined, and
776 is the type of the elements to be linked into the tail queue.
777 A pointer to the head of the tail queue can later be declared as:
778 .Bd -literal -offset indent
779 struct HEADNAME *headp;
786 are user selectable.)
789 .Nm TAILQ_HEAD_INITIALIZER
790 evaluates to an initializer for the tail queue
795 evaluates to true if there are no items on the tail queue.
799 declares a structure that connects the elements in
804 returns the first item on the tail queue or NULL if the tail queue
809 traverses the tail queue referenced by
811 in the forward direction, assigning each element in turn to
815 .Nm TAILQ_FOREACH_MUTABLE
816 traverses the tail queue referenced by
818 in the forward direction, assigning each element in turn to
822 it is permitted to remove
824 from the tail queue without interfering with the traversal.
827 .Nm TAILQ_FOREACH_REVERSE
828 traverses the tail queue referenced by
830 in the reverse direction, assigning each element in turn to
835 initializes the tail queue referenced by
839 .Nm TAILQ_INSERT_HEAD
840 inserts the new element
842 at the head of the tail queue.
845 .Nm TAILQ_INSERT_TAIL
846 inserts the new element
848 at the end of the tail queue.
851 .Nm TAILQ_INSERT_AFTER
852 inserts the new element
858 .Nm TAILQ_INSERT_BEFORE
859 inserts the new element
866 returns the last item on the tail queue.
867 If the tail queue is empty the return value is undefined.
871 returns the next item on the tail queue, or NULL if this item is the last.
875 returns the previous item on the tail queue, or NULL if this item
883 .Sh TAIL QUEUE EXAMPLE
885 TAILQ_HEAD(tailhead, entry) head =
886 TAILQ_HEAD_INITIALIZER(head);
887 struct tailhead *headp; /* Tail queue head. */
890 TAILQ_ENTRY(entry) entries; /* Tail queue. */
892 } *n1, *n2, *n3, *np;
894 TAILQ_INIT(&head); /* Initialize the queue. */
896 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
897 TAILQ_INSERT_HEAD(&head, n1, entries);
899 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
900 TAILQ_INSERT_TAIL(&head, n1, entries);
902 n2 = malloc(sizeof(struct entry)); /* Insert after. */
903 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
905 n3 = malloc(sizeof(struct entry)); /* Insert before. */
906 TAILQ_INSERT_BEFORE(n2, n3, entries);
908 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
910 /* Forward traversal. */
911 TAILQ_FOREACH(np, &head, entries)
913 /* Reverse traversal. */
914 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
916 /* TailQ Deletion. */
917 while (!TAILQ_EMPTY(&head)) {
918 n1 = TAILQ_FIRST(&head);
919 TAILQ_REMOVE(&head, n1, entries);
922 /* Faster TailQ Deletion. */
923 n1 = TAILQ_FIRST(&head);
925 n2 = TAILQ_NEXT(n1, entries);
932 A circular queue is headed by a structure defined by the
935 This structure contains a pair of pointers,
936 one to the first element in the circular queue and the other to the
937 last element in the circular queue.
938 The elements are doubly linked so that an arbitrary element can be
939 removed without traversing the queue.
940 New elements can be added to the queue after an existing element,
941 before an existing element, at the head of the queue, or at the end
945 structure is declared as follows:
946 .Bd -literal -offset indent
947 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
952 is the name of the structure to be defined, and
954 is the type of the elements to be linked into the circular queue.
955 A pointer to the head of the circular queue can later be declared as:
956 .Bd -literal -offset indent
957 struct HEADNAME *headp;
964 are user selectable.)
967 .Nm CIRCLEQ_HEAD_INITIALIZER
968 evaluates to an initializer for the circle queue
973 evaluates to true if there are no items on the circle queue.
977 declares a structure that connects the elements in
982 returns the first item on the circle queue.
986 traverses the circle queue referenced by
988 in the forward direction, assigning each element in turn to
992 .Nm CICRLEQ_FOREACH_REVERSE
993 traverses the circle queue referenced by
995 in the reverse direction, assigning each element in turn to
1000 initializes the circular queue referenced by
1004 .Nm CIRCLEQ_INSERT_HEAD
1005 inserts the new element
1007 at the head of the circular queue.
1010 .Nm CIRCLEQ_INSERT_TAIL
1011 inserts the new element
1013 at the end of the circular queue.
1016 .Nm CIRCLEQ_INSERT_AFTER
1017 inserts the new element
1023 .Nm CIRCLEQ_INSERT_BEFORE
1024 inserts the new element
1031 returns the last item on the circle queue.
1035 returns the next item on the circle queue.
1039 returns the previous item on the circle queue.
1045 from the circular queue.
1046 .Sh CIRCULAR QUEUE EXAMPLE
1048 CIRCLEQ_HEAD(circlehead, entry) head =
1049 CIRCLEQ_HEAD_INITIALIZER(head);
1050 struct circlehead *headp; /* Circular queue head. */
1053 CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
1057 CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
1059 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
1060 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
1062 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
1063 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
1065 n2 = malloc(sizeof(struct entry)); /* Insert after. */
1066 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
1068 n2 = malloc(sizeof(struct entry)); /* Insert before. */
1069 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
1071 CIRCLEQ_REMOVE(&head, n1, entries); /* Deletion. */
1073 /* Forward traversal. */
1074 CIRCLEQ_FOREACH(np, &head, entries)
1076 /* Reverse traversal. */
1077 CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
1079 /* CircleQ Deletion. */
1080 while (CIRCLEQ_FIRST(&head) != (void *)&head) {
1081 n1 = CIRCLEQ_HEAD(&head);
1082 CIRCLEQ_REMOVE(&head, n1, entries);
1085 /* Faster CircleQ Deletion. */
1086 n1 = CIRCLEQ_FIRST(&head);
1087 while (n1 != (void *)&head) {
1088 n2 = CIRCLEQ_NEXT(n1, entries);
1092 CIRCLEQ_INIT(&head);
1097 functions first appeared in