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.5 2007/01/28 15:52:02 swildner Exp $
45 .Nm SLIST_HEAD_INITIALIZER ,
47 .Nm SLIST_INSERT_AFTER ,
48 .Nm SLIST_INSERT_HEAD ,
50 .Nm SLIST_REMOVE_HEAD ,
58 .Nm STAILQ_HEAD_INITIALIZER ,
60 .Nm STAILQ_INSERT_AFTER ,
61 .Nm STAILQ_INSERT_HEAD ,
62 .Nm STAILQ_INSERT_TAIL ,
65 .Nm STAILQ_REMOVE_HEAD ,
71 .Nm LIST_FOREACH_MUTABLE ,
73 .Nm LIST_HEAD_INITIALIZER ,
75 .Nm LIST_INSERT_AFTER ,
76 .Nm LIST_INSERT_BEFORE ,
77 .Nm LIST_INSERT_HEAD ,
85 .Nm TAILQ_FOREACH_MUTABLE ,
86 .Nm TAILQ_FOREACH_REVERSE ,
88 .Nm TAILQ_HEAD_INITIALIZER ,
90 .Nm TAILQ_INSERT_AFTER ,
91 .Nm TAILQ_INSERT_BEFORE ,
92 .Nm TAILQ_INSERT_HEAD ,
93 .Nm TAILQ_INSERT_TAIL ,
101 .Nm CIRCLEQ_FOREACH ,
102 .Nm CIRCLEQ_FOREACH_REVERSE ,
104 .Nm CIRCLEQ_HEAD_INITIALIZER ,
106 .Nm CIRCLEQ_INSERT_AFTER ,
107 .Nm CIRCLEQ_INSERT_BEFORE ,
108 .Nm CIRCLEQ_INSERT_HEAD ,
109 .Nm CIRCLEQ_INSERT_TAIL ,
114 .Nd implementations of singly-linked lists, singly-linked tail queues,
115 lists, tail queues, and circular queues
119 .Fn SLIST_EMPTY "SLIST_HEAD *head"
120 .Fn SLIST_ENTRY "TYPE"
121 .Fn SLIST_FIRST "SLIST_HEAD *head"
122 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
123 .Fn SLIST_HEAD "HEADNAME" "TYPE"
124 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
125 .Fn SLIST_INIT "SLIST_HEAD *head"
126 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
127 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
128 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
129 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
130 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
132 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
133 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
134 .Fn STAILQ_ENTRY "TYPE"
135 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
136 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
137 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
138 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
139 .Fn STAILQ_INIT "STAILQ_HEAD *head"
140 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
141 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
142 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
143 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
144 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
145 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
146 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
148 .Fn LIST_EMPTY "LIST_HEAD *head"
149 .Fn LIST_ENTRY "TYPE"
150 .Fn LIST_FIRST "LIST_HEAD *head"
151 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
152 .Fn LIST_FOREACH_MUTABLE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
153 .Fn LIST_HEAD "HEADNAME" "TYPE"
154 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
155 .Fn LIST_INIT "LIST_HEAD *head"
156 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
157 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
158 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
159 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
160 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
162 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
163 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
164 .Fn TAILQ_ENTRY "TYPE"
165 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
166 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
167 .Fn TAILQ_FOREACH_MUTABLE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
168 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
169 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
170 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
171 .Fn TAILQ_INIT "TAILQ_HEAD *head"
172 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
173 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
174 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
175 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
176 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
177 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
178 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
179 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
181 .Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
182 .Fn CIRCLEQ_ENTRY "TYPE"
183 .Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
184 .Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
185 .Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
186 .Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
187 .Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
188 .Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
189 .Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
190 .Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
191 .Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
192 .Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
193 .Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
194 .Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
195 .Fn CIRCLEQ_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
196 .Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
198 These macros define and operate on five types of data structures:
199 singly-linked lists, singly-linked tail queues, lists, tail queues,
201 All five structures support the following functionality:
202 .Bl -enum -compact -offset indent
204 Insertion of a new entry at the head of the list.
206 Insertion of a new entry after any element in the list.
208 O(1) removal of an entry from the head of the list.
210 O(n) removal of any entry in the list.
212 Forward traversal through the list.
215 Singly-linked lists are the simplest of the five data structures
216 and support only the above functionality.
217 Singly-linked lists are ideal for applications with large datasets
218 and few or no removals,
219 or for implementing a LIFO queue.
221 Singly-linked tail queues add the following functionality:
222 .Bl -enum -compact -offset indent
224 Entries can be added at the end of a list.
227 .Bl -enum -compact -offset indent
229 All list insertions must specify the head of the list.
231 Each head entry requires two pointers rather than one.
233 Code size is about 15% greater and operations run about 20% slower
234 than singly-linked lists.
237 Singly-linked tailqs are ideal for applications with large datasets and
239 or for implementing a FIFO queue.
241 All doubly linked types of data structures (lists, tail queues, and circle
242 queues) additionally allow:
243 .Bl -enum -compact -offset indent
245 Insertion of a new entry before any element in the list.
247 O(1) removal of any entry in the list.
250 .Bl -enum -compact -offset indent
252 Each elements requires two pointers rather than one.
254 Code size and execution time of operations (except for removal) is about
255 twice that of the singly-linked data-structures.
258 Linked lists are the simplest of the doubly linked data structures and support
259 only the above functionality over singly-linked lists.
261 Tail queues add the following functionality:
262 .Bl -enum -compact -offset indent
264 Entries can be added at the end of a list.
266 They may be traversed backwards, from tail to head.
269 .Bl -enum -compact -offset indent
271 All list insertions and removals must specify the head of the list.
273 Each head entry requires two pointers rather than one.
275 Code size is about 15% greater and operations run about 20% slower
276 than singly-linked lists.
279 Circular queues add the following functionality:
280 .Bl -enum -compact -offset indent
282 Entries can be added at the end of a list.
284 They may be traversed backwards, from tail to head.
287 .Bl -enum -compact -offset indent
289 All list insertions and removals must specify the head of the list.
291 Each head entry requires two pointers rather than one.
293 The termination condition for traversal is more complex.
295 Code size is about 40% greater and operations run about 45% slower
299 In the macro definitions,
301 is the name of a user defined structure,
302 that must contain a field of type
313 is the name of a user defined structure that must be declared
321 See the examples below for further explanation of how these
323 .Sh SINGLY-LINKED LISTS
324 A singly-linked list is headed by a structure defined by the
327 This structure contains a single pointer to the first element
329 The elements are singly linked for minimum space and pointer manipulation
330 overhead at the expense of O(n) removal for arbitrary elements.
331 New elements can be added to the list after an existing element or
332 at the head of the list.
335 structure is declared as follows:
336 .Bd -literal -offset indent
337 SLIST_HEAD(HEADNAME, TYPE) head;
342 is the name of the structure to be defined, and
344 is the type of the elements to be linked into the list.
345 A pointer to the head of the list can later be declared as:
346 .Bd -literal -offset indent
347 struct HEADNAME *headp;
354 are user selectable.)
357 .Nm SLIST_HEAD_INITIALIZER
358 evaluates to an initializer for the list
363 evaluates to true if there are no elements in the list.
367 declares a structure that connects the elements in
372 returns the first element in the list or NULL if the list is empty.
376 traverses the list referenced by
378 in the forward direction, assigning each element in
384 initializes the list referenced by
388 .Nm SLIST_INSERT_HEAD
389 inserts the new element
391 at the head of the list.
394 .Nm SLIST_INSERT_AFTER
395 inserts the new element
402 returns the next element in the list.
405 .Nm SLIST_REMOVE_HEAD
408 from the head of the list.
409 For optimum efficiency,
410 elements being removed from the head of the list should explicitly use
411 this macro instead of the generic
420 .Sh SINGLY-LINKED LIST EXAMPLE
422 SLIST_HEAD(slisthead, entry) head =
423 SLIST_HEAD_INITIALIZER(head);
424 struct slisthead *headp; /* Singly-linked List head. */
427 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
429 } *n1, *n2, *n3, *np;
431 SLIST_INIT(&head); /* Initialize the list. */
433 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
434 SLIST_INSERT_HEAD(&head, n1, entries);
436 n2 = malloc(sizeof(struct entry)); /* Insert after. */
437 SLIST_INSERT_AFTER(n1, n2, entries);
439 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
442 n3 = SLIST_FIRST(&head);
443 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
445 /* Forward traversal. */
446 SLIST_FOREACH(np, &head, entries)
449 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
450 n1 = SLIST_FIRST(&head);
451 SLIST_REMOVE_HEAD(&head, entries);
455 .Sh SINGLY-LINKED TAIL QUEUES
456 A singly-linked tail queue is headed by a structure defined by the
459 This structure contains a pair of pointers,
460 one to the first element in the tail queue and the other to
461 the last element in the tail queue.
462 The elements are singly linked for minimum space and pointer
463 manipulation overhead at the expense of O(n) removal for arbitrary
465 New elements can be added to the tail queue after an existing element,
466 at the head of the tail queue, or at the end of the tail queue.
469 structure is declared as follows:
470 .Bd -literal -offset indent
471 STAILQ_HEAD(HEADNAME, TYPE) head;
476 is the name of the structure to be defined, and
478 is the type of the elements to be linked into the tail queue.
479 A pointer to the head of the tail queue can later be declared as:
480 .Bd -literal -offset indent
481 struct HEADNAME *headp;
488 are user selectable.)
491 .Nm STAILQ_HEAD_INITIALIZER
492 evaluates to an initializer for the tail queue
497 concatenates the tail queue headed by
499 onto the end of the one headed by
501 removing all entries from the former.
505 evaluates to true if there are no items on the tail queue.
509 declares a structure that connects the elements in
514 returns the first item on the tail queue or NULL if the tail queue
519 traverses the tail queue referenced by
521 in the forward direction, assigning each element
527 initializes the tail queue referenced by
531 .Nm STAILQ_INSERT_HEAD
532 inserts the new element
534 at the head of the tail queue.
537 .Nm STAILQ_INSERT_TAIL
538 inserts the new element
540 at the end of the tail queue.
543 .Nm STAILQ_INSERT_AFTER
544 inserts the new element
551 returns the last item on the tail queue.
552 If the tail queue is empty the return value is undefined.
556 returns the next item on the tail queue, or NULL this item is the last.
559 .Nm STAILQ_REMOVE_HEAD
560 removes the element at the head of the tail queue.
561 For optimum efficiency,
562 elements being removed from the head of the tail queue should
563 use this macro explicitly rather than the generic
572 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
574 STAILQ_HEAD(stailhead, entry) head =
575 STAILQ_HEAD_INITIALIZER(head);
576 struct stailhead *headp; /* Singly-linked tail queue head. */
579 STAILQ_ENTRY(entry) entries; /* Tail queue. */
581 } *n1, *n2, *n3, *np;
583 STAILQ_INIT(&head); /* Initialize the queue. */
585 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
586 STAILQ_INSERT_HEAD(&head, n1, entries);
588 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
589 STAILQ_INSERT_TAIL(&head, n1, entries);
591 n2 = malloc(sizeof(struct entry)); /* Insert after. */
592 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
594 STAILQ_REMOVE(&head, n2, entry, entries);
596 /* Deletion from the head. */
597 n3 = STAILQ_FIRST(&head);
598 STAILQ_REMOVE_HEAD(&head, entries);
600 /* Forward traversal. */
601 STAILQ_FOREACH(np, &head, entries)
603 /* TailQ Deletion. */
604 while (!STAILQ_EMPTY(&head)) {
605 n1 = STAILQ_FIRST(&head);
606 STAILQ_REMOVE_HEAD(&head, entries);
609 /* Faster TailQ Deletion. */
610 n1 = STAILQ_FIRST(&head);
612 n2 = STAILQ_NEXT(n1, entries);
619 A list is headed by a structure defined by the
622 This structure contains a single pointer to the first element
624 The elements are doubly linked so that an arbitrary element can be
625 removed without traversing the list.
626 New elements can be added to the list after an existing element,
627 before an existing element, or at the head of the list.
630 structure is declared as follows:
631 .Bd -literal -offset indent
632 LIST_HEAD(HEADNAME, TYPE) head;
637 is the name of the structure to be defined, and
639 is the type of the elements to be linked into the list.
640 A pointer to the head of the list can later be declared as:
641 .Bd -literal -offset indent
642 struct HEADNAME *headp;
649 are user selectable.)
652 .Nm LIST_HEAD_INITIALIZER
653 evaluates to an initializer for the list
658 evaluates to true if their are no elements in the list.
662 declares a structure that connects the elements in
667 returns the first element in the list or NULL if the list
672 traverses the list referenced by
674 in the forward direction, assigning each element in turn to
678 .Nm LIST_FOREACH_MUTABLE
679 traverses the list referenced by
681 in the forward direction, assigning each element in turn to
685 it is permitted to remove
687 from the list without interfering with the traversal.
691 initializes the list referenced by
696 inserts the new element
698 at the head of the list.
701 .Nm LIST_INSERT_AFTER
702 inserts the new element
708 .Nm LIST_INSERT_BEFORE
709 inserts the new element
716 returns the next element in the list, or NULL if this is the last.
725 LIST_HEAD(listhead, entry) head =
726 LIST_HEAD_INITIALIZER(head);
727 struct listhead *headp; /* List head. */
730 LIST_ENTRY(entry) entries; /* List. */
732 } *n1, *n2, *n3, *np;
734 LIST_INIT(&head); /* Initialize the list. */
736 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
737 LIST_INSERT_HEAD(&head, n1, entries);
739 n2 = malloc(sizeof(struct entry)); /* Insert after. */
740 LIST_INSERT_AFTER(n1, n2, entries);
742 n3 = malloc(sizeof(struct entry)); /* Insert before. */
743 LIST_INSERT_BEFORE(n2, n3, entries);
745 LIST_REMOVE(n2, entries); /* Deletion. */
747 /* Forward traversal. */
748 LIST_FOREACH(np, &head, entries)
751 while (!LIST_EMPTY(&head)) { /* List Deletion. */
752 n1 = LIST_FIRST(&head);
753 LIST_REMOVE(n1, entries);
757 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
759 n2 = LIST_NEXT(n1, entries);
766 A tail queue is headed by a structure defined by the
769 This structure contains a pair of pointers,
770 one to the first element in the tail queue and the other to
771 the last element in the tail queue.
772 The elements are doubly linked so that an arbitrary element can be
773 removed without traversing the tail queue.
774 New elements can be added to the tail queue after an existing element,
775 before an existing element, at the head of the tail queue,
776 or at the end of the tail queue.
779 structure is declared as follows:
780 .Bd -literal -offset indent
781 TAILQ_HEAD(HEADNAME, TYPE) head;
786 is the name of the structure to be defined, and
788 is the type of the elements to be linked into the tail queue.
789 A pointer to the head of the tail queue can later be declared as:
790 .Bd -literal -offset indent
791 struct HEADNAME *headp;
798 are user selectable.)
801 .Nm TAILQ_HEAD_INITIALIZER
802 evaluates to an initializer for the tail queue
807 concatenates the tail queue headed by
809 onto the end of the one headed by
811 removing all entries from the former.
815 evaluates to true if there are no items on the tail queue.
819 declares a structure that connects the elements in
824 returns the first item on the tail queue or NULL if the tail queue
829 traverses the tail queue referenced by
831 in the forward direction, assigning each element in turn to
835 .Nm TAILQ_FOREACH_MUTABLE
836 traverses the tail queue referenced by
838 in the forward direction, assigning each element in turn to
842 it is permitted to remove
844 from the tail queue without interfering with the traversal.
847 .Nm TAILQ_FOREACH_REVERSE
848 traverses the tail queue referenced by
850 in the reverse direction, assigning each element in turn to
855 initializes the tail queue referenced by
859 .Nm TAILQ_INSERT_HEAD
860 inserts the new element
862 at the head of the tail queue.
865 .Nm TAILQ_INSERT_TAIL
866 inserts the new element
868 at the end of the tail queue.
871 .Nm TAILQ_INSERT_AFTER
872 inserts the new element
878 .Nm TAILQ_INSERT_BEFORE
879 inserts the new element
886 returns the last item on the tail queue.
887 If the tail queue is empty the return value is undefined.
891 returns the next item on the tail queue, or NULL if this item is the last.
895 returns the previous item on the tail queue, or NULL if this item
903 .Sh TAIL QUEUE EXAMPLE
905 TAILQ_HEAD(tailhead, entry) head =
906 TAILQ_HEAD_INITIALIZER(head);
907 struct tailhead *headp; /* Tail queue head. */
910 TAILQ_ENTRY(entry) entries; /* Tail queue. */
912 } *n1, *n2, *n3, *np;
914 TAILQ_INIT(&head); /* Initialize the queue. */
916 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
917 TAILQ_INSERT_HEAD(&head, n1, entries);
919 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
920 TAILQ_INSERT_TAIL(&head, n1, entries);
922 n2 = malloc(sizeof(struct entry)); /* Insert after. */
923 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
925 n3 = malloc(sizeof(struct entry)); /* Insert before. */
926 TAILQ_INSERT_BEFORE(n2, n3, entries);
928 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
930 /* Forward traversal. */
931 TAILQ_FOREACH(np, &head, entries)
933 /* Reverse traversal. */
934 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
936 /* TailQ Deletion. */
937 while (!TAILQ_EMPTY(&head)) {
938 n1 = TAILQ_FIRST(&head);
939 TAILQ_REMOVE(&head, n1, entries);
942 /* Faster TailQ Deletion. */
943 n1 = TAILQ_FIRST(&head);
945 n2 = TAILQ_NEXT(n1, entries);
952 A circular queue is headed by a structure defined by the
955 This structure contains a pair of pointers,
956 one to the first element in the circular queue and the other to the
957 last element in the circular queue.
958 The elements are doubly linked so that an arbitrary element can be
959 removed without traversing the queue.
960 New elements can be added to the queue after an existing element,
961 before an existing element, at the head of the queue, or at the end
965 structure is declared as follows:
966 .Bd -literal -offset indent
967 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
972 is the name of the structure to be defined, and
974 is the type of the elements to be linked into the circular queue.
975 A pointer to the head of the circular queue can later be declared as:
976 .Bd -literal -offset indent
977 struct HEADNAME *headp;
984 are user selectable.)
987 .Nm CIRCLEQ_HEAD_INITIALIZER
988 evaluates to an initializer for the circle queue
993 evaluates to true if there are no items on the circle queue.
997 declares a structure that connects the elements in
1002 returns the first item on the circle queue.
1006 traverses the circle queue referenced by
1008 in the forward direction, assigning each element in turn to
1012 .Nm CICRLEQ_FOREACH_REVERSE
1013 traverses the circle queue referenced by
1015 in the reverse direction, assigning each element in turn to
1020 initializes the circular queue referenced by
1024 .Nm CIRCLEQ_INSERT_HEAD
1025 inserts the new element
1027 at the head of the circular queue.
1030 .Nm CIRCLEQ_INSERT_TAIL
1031 inserts the new element
1033 at the end of the circular queue.
1036 .Nm CIRCLEQ_INSERT_AFTER
1037 inserts the new element
1043 .Nm CIRCLEQ_INSERT_BEFORE
1044 inserts the new element
1051 returns the last item on the circle queue.
1055 returns the next item on the circle queue.
1059 returns the previous item on the circle queue.
1065 from the circular queue.
1066 .Sh CIRCULAR QUEUE EXAMPLE
1068 CIRCLEQ_HEAD(circlehead, entry) head =
1069 CIRCLEQ_HEAD_INITIALIZER(head);
1070 struct circlehead *headp; /* Circular queue head. */
1073 CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
1077 CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
1079 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
1080 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
1082 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
1083 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
1085 n2 = malloc(sizeof(struct entry)); /* Insert after. */
1086 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
1088 n2 = malloc(sizeof(struct entry)); /* Insert before. */
1089 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
1091 CIRCLEQ_REMOVE(&head, n1, entries); /* Deletion. */
1093 /* Forward traversal. */
1094 CIRCLEQ_FOREACH(np, &head, entries)
1096 /* Reverse traversal. */
1097 CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
1099 /* CircleQ Deletion. */
1100 while (CIRCLEQ_FIRST(&head) != (void *)&head) {
1101 n1 = CIRCLEQ_HEAD(&head);
1102 CIRCLEQ_REMOVE(&head, n1, entries);
1105 /* Faster CircleQ Deletion. */
1106 n1 = CIRCLEQ_FIRST(&head);
1107 while (n1 != (void *)&head) {
1108 n2 = CIRCLEQ_NEXT(n1, entries);
1112 CIRCLEQ_INIT(&head);
1117 functions first appeared in