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.2 2003/06/17 04:36:58 dillon 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 ,
71 .Nm LIST_HEAD_INITIALIZER ,
73 .Nm LIST_INSERT_AFTER ,
74 .Nm LIST_INSERT_BEFORE ,
75 .Nm LIST_INSERT_HEAD ,
82 .Nm TAILQ_FOREACH_REVERSE ,
84 .Nm TAILQ_HEAD_INITIALIZER ,
86 .Nm TAILQ_INSERT_AFTER ,
87 .Nm TAILQ_INSERT_BEFORE ,
88 .Nm TAILQ_INSERT_HEAD ,
89 .Nm TAILQ_INSERT_TAIL ,
98 .Nm CIRCLEQ_FOREACH_REVERSE ,
100 .Nm CIRCLEQ_HEAD_INITIALIZER ,
102 .Nm CIRCLEQ_INSERT_AFTER ,
103 .Nm CIRCLEQ_INSERT_BEFORE ,
104 .Nm CIRCLEQ_INSERT_HEAD ,
105 .Nm CIRCLEQ_INSERT_TAIL ,
110 .Nd implementations of singly-linked lists, singly-linked tail queues,
111 lists, tail queues, and circular queues
115 .Fn SLIST_EMPTY "SLIST_HEAD *head"
116 .Fn SLIST_ENTRY "TYPE"
117 .Fn SLIST_FIRST "SLIST_HEAD *head"
118 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
119 .Fn SLIST_HEAD "HEADNAME" "TYPE"
120 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
121 .Fn SLIST_INIT "SLIST_HEAD *head"
122 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
123 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
124 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
125 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
126 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
128 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
129 .Fn STAILQ_ENTRY "TYPE"
130 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
131 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
132 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
133 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
134 .Fn STAILQ_INIT "STAILQ_HEAD *head"
135 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
136 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
137 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
138 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
139 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
140 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
141 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
143 .Fn LIST_EMPTY "LIST_HEAD *head"
144 .Fn LIST_ENTRY "TYPE"
145 .Fn LIST_FIRST "LIST_HEAD *head"
146 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
147 .Fn LIST_HEAD "HEADNAME" "TYPE"
148 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
149 .Fn LIST_INIT "LIST_HEAD *head"
150 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
151 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
152 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
153 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
154 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
156 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
157 .Fn TAILQ_ENTRY "TYPE"
158 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
159 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
160 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
161 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
162 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
163 .Fn TAILQ_INIT "TAILQ_HEAD *head"
164 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
165 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
166 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
167 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
168 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
169 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
170 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
171 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
173 .Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
174 .Fn CIRCLEQ_ENTRY "TYPE"
175 .Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
176 .Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
177 .Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
178 .Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
179 .Fn CIRCLEQ_HEAD_INITIALIZER "CIRCLEQ_HEAD head"
180 .Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
181 .Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
182 .Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
183 .Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
184 .Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
185 .Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
186 .Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
187 .Fn CIRCLE_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
188 .Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
190 These macros define and operate on five types of data structures:
191 singly-linked lists, singly-linked tail queues, lists, tail queues,
193 All five structures support the following functionality:
194 .Bl -enum -compact -offset indent
196 Insertion of a new entry at the head of the list.
198 Insertion of a new entry after any element in the list.
200 O(1) removal of an entry from the head of the list.
202 O(n) removal of any entry in the list.
204 Forward traversal through the list.
207 Singly-linked lists are the simplest of the five data structures
208 and support only the above functionality.
209 Singly-linked lists are ideal for applications with large datasets
210 and few or no removals,
211 or for implementing a LIFO queue.
213 Singly-linked tail queues add the following functionality:
214 .Bl -enum -compact -offset indent
216 Entries can be added at the end of a list.
219 .Bl -enum -compact -offset indent
221 All list insertions must specify the head of the list.
223 Each head entry requires two pointers rather than one.
225 Code size is about 15% greater and operations run about 20% slower
226 than singly-linked lists.
229 Singly-linked tailqs are ideal for applications with large datasets and
231 or for implementing a FIFO queue.
233 All doubly linked types of data structures (lists, tail queues, and circle
234 queues) additionally allow:
235 .Bl -enum -compact -offset indent
237 Insertion of a new entry before any element in the list.
239 O(1) removal of any entry in the list.
242 .Bl -enum -compact -offset indent
244 Each elements requires two pointers rather than one.
246 Code size and execution time of operations (except for removal) is about
247 twice that of the singly-linked data-structures.
250 Linked lists are the simplest of the doubly linked data structures and support
251 only the above functionality over singly-linked lists.
253 Tail queues add the following functionality:
254 .Bl -enum -compact -offset indent
256 Entries can be added at the end of a list.
258 They may be traversed backwards, from tail to head.
261 .Bl -enum -compact -offset indent
263 All list insertions and removals must specify the head of the list.
265 Each head entry requires two pointers rather than one.
267 Code size is about 15% greater and operations run about 20% slower
268 than singly-linked lists.
271 Circular queues add the following functionality:
272 .Bl -enum -compact -offset indent
274 Entries can be added at the end of a list.
276 They may be traversed backwards, from tail to head.
279 .Bl -enum -compact -offset indent
281 All list insertions and removals must specify the head of the list.
283 Each head entry requires two pointers rather than one.
285 The termination condition for traversal is more complex.
287 Code size is about 40% greater and operations run about 45% slower
291 In the macro definitions,
293 is the name of a user defined structure,
294 that must contain a field of type
305 is the name of a user defined structure that must be declared
313 See the examples below for further explanation of how these
315 .Sh SINGLY-LINKED LISTS
316 A singly-linked list is headed by a structure defined by the
319 This structure contains a single pointer to the first element
321 The elements are singly linked for minimum space and pointer manipulation
322 overhead at the expense of O(n) removal for arbitrary elements.
323 New elements can be added to the list after an existing element or
324 at the head of the list.
327 structure is declared as follows:
328 .Bd -literal -offset indent
329 SLIST_HEAD(HEADNAME, TYPE) head;
334 is the name of the structure to be defined, and
336 is the type of the elements to be linked into the list.
337 A pointer to the head of the list can later be declared as:
338 .Bd -literal -offset indent
339 struct HEADNAME *headp;
346 are user selectable.)
349 .Nm SLIST_HEAD_INITIALIZER
350 evaluates to an initializer for the list
355 evaluates to true if there are no elements in the list.
359 declares a structure that connects the elements in
364 returns the first element in the list or NULL if the list is empty.
368 traverses the list referenced by
370 in the forward direction, assigning each element in
376 initializes the list referenced by
380 .Nm SLIST_INSERT_HEAD
381 inserts the new element
383 at the head of the list.
386 .Nm SLIST_INSERT_AFTER
387 inserts the new element
394 returns the next element in the list.
397 .Nm SLIST_REMOVE_HEAD
400 from the head of the list.
401 For optimum efficiency,
402 elements being removed from the head of the list should explicitly use
403 this macro instead of the generic
412 .Sh SINGLY-LINKED LIST EXAMPLE
414 SLIST_HEAD(slisthead, entry) head =
415 SLIST_HEAD_INITIALIZER(head);
416 struct slisthead *headp; /* Singly-linked List head. */
419 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
421 } *n1, *n2, *n3, *np;
423 SLIST_INIT(&head); /* Initialize the list. */
425 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
426 SLIST_INSERT_HEAD(&head, n1, entries);
428 n2 = malloc(sizeof(struct entry)); /* Insert after. */
429 SLIST_INSERT_AFTER(n1, n2, entries);
431 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
434 n3 = SLIST_FIRST(&head);
435 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
437 /* Forward traversal. */
438 SLIST_FOREACH(np, &head, entries)
441 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
442 n1 = SLIST_FIRST(&head);
443 SLIST_REMOVE_HEAD(&head, entries);
447 .Sh SINGLY-LINKED TAIL QUEUES
448 A singly-linked tail queue is headed by a structure defined by the
451 This structure contains a pair of pointers,
452 one to the first element in the tail queue and the other to
453 the last element in the tail queue.
454 The elements are singly linked for minimum space and pointer
455 manipulation overhead at the expense of O(n) removal for arbitrary
457 New elements can be added to the tail queue after an existing element,
458 at the head of the tail queue, or at the end of the tail queue.
461 structure is declared as follows:
462 .Bd -literal -offset indent
463 STAILQ_HEAD(HEADNAME, TYPE) head;
468 is the name of the structure to be defined, and
470 is the type of the elements to be linked into the tail queue.
471 A pointer to the head of the tail queue can later be declared as:
472 .Bd -literal -offset indent
473 struct HEADNAME *headp;
480 are user selectable.)
483 .Nm STAILQ_HEAD_INITIALIZER
484 evaluates to an initializer for the tail queue
489 evaluates to true if there are no items on the tail queue.
493 declares a structure that connects the elements in
498 returns the first item on the tail queue or NULL if the tail queue
503 traverses the tail queue referenced by
505 in the forward direction, assigning each element
511 initializes the tail queue referenced by
515 .Nm STAILQ_INSERT_HEAD
516 inserts the new element
518 at the head of the tail queue.
521 .Nm STAILQ_INSERT_TAIL
522 inserts the new element
524 at the end of the tail queue.
527 .Nm STAILQ_INSERT_AFTER
528 inserts the new element
535 returns the last item on the tail queue.
536 If the tail queue is empty the return value is undefined.
540 returns the next item on the tail queue, or NULL this item is the last.
543 .Nm STAILQ_REMOVE_HEAD
544 removes the element at the head of the tail queue.
545 For optimum efficiency,
546 elements being removed from the head of the tail queue should
547 use this macro explicitly rather than the generic
556 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
558 STAILQ_HEAD(stailhead, entry) head =
559 STAILQ_HEAD_INITIALIZER(head);
560 struct stailhead *headp; /* Singly-linked tail queue head. */
563 STAILQ_ENTRY(entry) entries; /* Tail queue. */
565 } *n1, *n2, *n3, *np;
567 STAILQ_INIT(&head); /* Initialize the queue. */
569 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
570 STAILQ_INSERT_HEAD(&head, n1, entries);
572 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
573 STAILQ_INSERT_TAIL(&head, n1, entries);
575 n2 = malloc(sizeof(struct entry)); /* Insert after. */
576 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
578 STAILQ_REMOVE(&head, n2, entry, entries);
580 /* Deletion from the head. */
581 n3 = STAILQ_FIRST(&head);
582 STAILQ_REMOVE_HEAD(&head, entries);
584 /* Forward traversal. */
585 STAILQ_FOREACH(np, &head, entries)
587 /* TailQ Deletion. */
588 while (!STAILQ_EMPTY(&head)) {
589 n1 = STAILQ_FIRST(&head);
590 STAILQ_REMOVE_HEAD(&head, entries);
593 /* Faster TailQ Deletion. */
594 n1 = STAILQ_FIRST(&head);
596 n2 = STAILQ_NEXT(n1, entries);
603 A list is headed by a structure defined by the
606 This structure contains a single pointer to the first element
608 The elements are doubly linked so that an arbitrary element can be
609 removed without traversing the list.
610 New elements can be added to the list after an existing element,
611 before an existing element, or at the head of the list.
614 structure is declared as follows:
615 .Bd -literal -offset indent
616 LIST_HEAD(HEADNAME, TYPE) head;
621 is the name of the structure to be defined, and
623 is the type of the elements to be linked into the list.
624 A pointer to the head of the list can later be declared as:
625 .Bd -literal -offset indent
626 struct HEADNAME *headp;
633 are user selectable.)
636 .Nm LIST_HEAD_INITIALIZER
637 evaluates to an initializer for the list
642 evaluates to true if their are no elements in the list.
646 declares a structure that connects the elements in
651 returns the first element in the list or NULL if the list
656 traverses the list referenced by
658 in the forward direction, assigning each element in turn to
663 initializes the list referenced by
668 inserts the new element
670 at the head of the list.
673 .Nm LIST_INSERT_AFTER
674 inserts the new element
680 .Nm LIST_INSERT_BEFORE
681 inserts the new element
688 returns the next element in the list, or NULL if this is the last.
697 LIST_HEAD(listhead, entry) head =
698 LIST_HEAD_INITIALIZER(head);
699 struct listhead *headp; /* List head. */
702 LIST_ENTRY(entry) entries; /* List. */
704 } *n1, *n2, *n3, *np;
706 LIST_INIT(&head); /* Initialize the list. */
708 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
709 LIST_INSERT_HEAD(&head, n1, entries);
711 n2 = malloc(sizeof(struct entry)); /* Insert after. */
712 LIST_INSERT_AFTER(n1, n2, entries);
714 n3 = malloc(sizeof(struct entry)); /* Insert before. */
715 LIST_INSERT_BEFORE(n2, n3, entries);
717 LIST_REMOVE(n2, entries); /* Deletion. */
719 /* Forward traversal. */
720 LIST_FOREACH(np, &head, entries)
723 while (!LIST_EMPTY(&head)) { /* List Deletion. */
724 n1 = LIST_FIRST(&head);
725 LIST_REMOVE(n1, entries);
729 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
731 n2 = LIST_NEXT(n1, entries);
738 A tail queue is headed by a structure defined by the
741 This structure contains a pair of pointers,
742 one to the first element in the tail queue and the other to
743 the last element in the tail queue.
744 The elements are doubly linked so that an arbitrary element can be
745 removed without traversing the tail queue.
746 New elements can be added to the tail queue after an existing element,
747 before an existing element, at the head of the tail queue,
748 or at the end of the tail queue.
751 structure is declared as follows:
752 .Bd -literal -offset indent
753 TAILQ_HEAD(HEADNAME, TYPE) head;
758 is the name of the structure to be defined, and
760 is the type of the elements to be linked into the tail queue.
761 A pointer to the head of the tail queue can later be declared as:
762 .Bd -literal -offset indent
763 struct HEADNAME *headp;
770 are user selectable.)
773 .Nm TAILQ_HEAD_INITIALIZER
774 evaluates to an initializer for the tail queue
779 evaluates to true if there are no items on the tail queue.
783 declares a structure that connects the elements in
788 returns the first item on the tail queue or NULL if the tail queue
793 traverses the tail queue referenced by
795 in the forward direction, assigning each element in turn to
799 .Nm TAILQ_FOREACH_REVERSE
800 traverses the tail queue referenced by
802 in the reverse direction, assigning each element in turn to
807 initializes the tail queue referenced by
811 .Nm TAILQ_INSERT_HEAD
812 inserts the new element
814 at the head of the tail queue.
817 .Nm TAILQ_INSERT_TAIL
818 inserts the new element
820 at the end of the tail queue.
823 .Nm TAILQ_INSERT_AFTER
824 inserts the new element
830 .Nm TAILQ_INSERT_BEFORE
831 inserts the new element
838 returns the last item on the tail queue.
839 If the tail queue is empty the return value is undefined.
843 returns the next item on the tail queue, or NULL if this item is the last.
847 returns the previous item on the tail queue, or NULL if this item
855 .Sh TAIL QUEUE EXAMPLE
857 TAILQ_HEAD(tailhead, entry) head =
858 TAILQ_HEAD_INITIALIZER(head);
859 struct tailhead *headp; /* Tail queue head. */
862 TAILQ_ENTRY(entry) entries; /* Tail queue. */
864 } *n1, *n2, *n3, *np;
866 TAILQ_INIT(&head); /* Initialize the queue. */
868 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
869 TAILQ_INSERT_HEAD(&head, n1, entries);
871 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
872 TAILQ_INSERT_TAIL(&head, n1, entries);
874 n2 = malloc(sizeof(struct entry)); /* Insert after. */
875 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
877 n3 = malloc(sizeof(struct entry)); /* Insert before. */
878 TAILQ_INSERT_BEFORE(n2, n3, entries);
880 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
882 /* Forward traversal. */
883 TAILQ_FOREACH(np, &head, entries)
885 /* Reverse traversal. */
886 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
888 /* TailQ Deletion. */
889 while (!TAILQ_EMPTY(&head)) {
890 n1 = TAILQ_FIRST(&head);
891 TAILQ_REMOVE(&head, n1, entries);
894 /* Faster TailQ Deletion. */
895 n1 = TAILQ_FIRST(&head);
897 n2 = TAILQ_NEXT(n1, entries);
904 A circular queue is headed by a structure defined by the
907 This structure contains a pair of pointers,
908 one to the first element in the circular queue and the other to the
909 last element in the circular queue.
910 The elements are doubly linked so that an arbitrary element can be
911 removed without traversing the queue.
912 New elements can be added to the queue after an existing element,
913 before an existing element, at the head of the queue, or at the end
917 structure is declared as follows:
918 .Bd -literal -offset indent
919 CIRCLEQ_HEAD(HEADNAME, TYPE) head;
924 is the name of the structure to be defined, and
926 is the type of the elements to be linked into the circular queue.
927 A pointer to the head of the circular queue can later be declared as:
928 .Bd -literal -offset indent
929 struct HEADNAME *headp;
936 are user selectable.)
939 .Nm CIRCLEQ_HEAD_INITIALIZER
940 evaluates to an initializer for the circle queue
945 evaluates to true if there are no items on the circle queue.
949 declares a structure that connects the elements in
954 returns the first item on the circle queue.
958 traverses the circle queue referenced by
960 in the forward direction, assigning each element in turn to
964 .Nm CICRLEQ_FOREACH_REVERSE
965 traverses the circle queue referenced by
967 in the reverse direction, assigning each element in turn to
972 initializes the circular queue referenced by
976 .Nm CIRCLEQ_INSERT_HEAD
977 inserts the new element
979 at the head of the circular queue.
982 .Nm CIRCLEQ_INSERT_TAIL
983 inserts the new element
985 at the end of the circular queue.
988 .Nm CIRCLEQ_INSERT_AFTER
989 inserts the new element
995 .Nm CIRCLEQ_INSERT_BEFORE
996 inserts the new element
1003 returns the last item on the circle queue.
1007 returns the next item on the circle queue.
1011 returns the previous item on the circle queue.
1017 from the circular queue.
1018 .Sh CIRCULAR QUEUE EXAMPLE
1020 CIRCLEQ_HEAD(circlehead, entry) head =
1021 CIRCLEQ_HEAD_INITIALIZER(head);
1022 struct circlehead *headp; /* Circular queue head. */
1025 CIRCLEQ_ENTRY(entry) entries; /* Circular queue. */
1029 CIRCLEQ_INIT(&head); /* Initialize the circular queue. */
1031 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
1032 CIRCLEQ_INSERT_HEAD(&head, n1, entries);
1034 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
1035 CIRCLEQ_INSERT_TAIL(&head, n1, entries);
1037 n2 = malloc(sizeof(struct entry)); /* Insert after. */
1038 CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
1040 n2 = malloc(sizeof(struct entry)); /* Insert before. */
1041 CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
1043 CIRCLEQ_REMOVE(&head, n1, entries); /* Deletion. */
1045 /* Forward traversal. */
1046 CIRCLEQ_FOREACH(np, &head, entries)
1048 /* Reverse traversal. */
1049 CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
1051 /* CircleQ Deletion. */
1052 while (CIRCLEQ_FIRST(&head) != (void *)&head) {
1053 n1 = CIRCLEQ_HEAD(&head);
1054 CIRCLEQ_REMOVE(&head, n1, entries);
1057 /* Faster CircleQ Deletion. */
1058 n1 = CIRCLEQ_FIRST(&head);
1059 while (n1 != (void *)&head) {
1060 n2 = CIRCLEQ_NEXT(n1, entries);
1064 CIRCLEQ_INIT(&head);
1069 functions first appeared in