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
44 .Nm SLIST_HEAD_INITIALIZER ,
46 .Nm SLIST_INSERT_AFTER ,
47 .Nm SLIST_INSERT_HEAD ,
49 .Nm SLIST_REMOVE_HEAD ,
56 .Nm STAILQ_HEAD_INITIALIZER ,
58 .Nm STAILQ_INSERT_AFTER ,
59 .Nm STAILQ_INSERT_HEAD ,
60 .Nm STAILQ_INSERT_TAIL ,
63 .Nm STAILQ_REMOVE_HEAD ,
70 .Nm LIST_HEAD_INITIALIZER ,
72 .Nm LIST_INSERT_AFTER ,
73 .Nm LIST_INSERT_BEFORE ,
74 .Nm LIST_INSERT_HEAD ,
81 .Nm TAILQ_FOREACH_REVERSE ,
83 .Nm TAILQ_HEAD_INITIALIZER ,
85 .Nm TAILQ_INSERT_AFTER ,
86 .Nm TAILQ_INSERT_BEFORE ,
87 .Nm TAILQ_INSERT_HEAD ,
88 .Nm TAILQ_INSERT_TAIL ,
93 .Nd implementations of singly-linked lists, singly-linked tail queues,
96 .Fd #include <sys/queue.h>
98 .Fn SLIST_EMPTY "SLIST_HEAD *head"
99 .Fn SLIST_ENTRY "TYPE"
100 .Fn SLIST_FIRST "SLIST_HEAD *head"
101 .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
102 .Fn SLIST_HEAD "HEADNAME" "TYPE"
103 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
104 .Fn SLIST_INIT "SLIST_HEAD *head"
105 .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
106 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
107 .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
108 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
109 .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
111 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
112 .Fn STAILQ_ENTRY "TYPE"
113 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
114 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
115 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
116 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
117 .Fn STAILQ_INIT "STAILQ_HEAD *head"
118 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
119 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
120 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
121 .Fn STAILQ_LAST "STAILQ_HEAD *head"
122 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
123 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
124 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
126 .Fn LIST_EMPTY "LIST_HEAD *head"
127 .Fn LIST_ENTRY "TYPE"
128 .Fn LIST_FIRST "LIST_HEAD *head"
129 .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
130 .Fn LIST_HEAD "HEADNAME" "TYPE"
131 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
132 .Fn LIST_INIT "LIST_HEAD *head"
133 .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
134 .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
135 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
136 .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
137 .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
139 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
140 .Fn TAILQ_ENTRY "TYPE"
141 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
142 .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
143 .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
144 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
145 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
146 .Fn TAILQ_INIT "TAILQ_HEAD *head"
147 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
148 .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
149 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
150 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
151 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
152 .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
153 .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
154 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
157 These macros define and operate on five types of data structures:
158 singly-linked lists, singly-linked tail queues, lists, tail queues,
160 All five structures support the following functionality:
161 .Bl -enum -compact -offset indent
163 Insertion of a new entry at the head of the list.
165 Insertion of a new entry after any element in the list.
167 O(1) removal of an entry from the head of the list.
169 O(n) removal of any entry in the list.
171 Forward traversal through the list.
174 Singly-linked lists are the simplest of the five data structures
175 and support only the above functionality.
176 Singly-linked lists are ideal for applications with large datasets
177 and few or no removals,
178 or for implementing a LIFO queue.
180 Singly-linked tail queues add the following functionality:
181 .Bl -enum -compact -offset indent
183 Entries can be added at the end of a list.
186 .Bl -enum -compact -offset indent
188 All list insertions must specify the head of the list.
190 Each head entry requires two pointers rather than one.
192 Code size is about 15% greater and operations run about 20% slower
193 than singly-linked lists.
196 Singly-linked tailqs are ideal for applications with large datasets and
198 or for implementing a FIFO queue.
200 All doubly linked types of data structures (lists, tail queues, and circle
201 queues) additionally allow:
202 .Bl -enum -compact -offset indent
204 Insertion of a new entry before any element in the list.
206 O(1) removal of any entry in the list.
209 .Bl -enum -compact -offset indent
211 Each elements requires two pointers rather than one.
213 Code size and execution time of operations (except for removal) is about
214 twice that of the singly-linked data-structures.
217 Linked lists are the simplest of the doubly linked data structures and support
218 only the above functionality over singly-linked lists.
220 Tail queues add the following functionality:
221 .Bl -enum -compact -offset indent
223 Entries can be added at the end of a list.
225 They may be traversed backwards, from tail to head.
228 .Bl -enum -compact -offset indent
230 All list insertions and removals must specify the head of the list.
232 Each head entry requires two pointers rather than one.
234 Code size is about 15% greater and operations run about 20% slower
235 than singly-linked lists.
238 In the macro definitions,
240 is the name of a user defined structure,
241 that must contain a field of type
251 is the name of a user defined structure that must be declared
258 See the examples below for further explanation of how these
260 .Sh SINGLY-LINKED LISTS
261 A singly-linked list is headed by a structure defined by the
264 This structure contains a single pointer to the first element
266 The elements are singly linked for minimum space and pointer manipulation
267 overhead at the expense of O(n) removal for arbitrary elements.
268 New elements can be added to the list after an existing element or
269 at the head of the list.
272 structure is declared as follows:
273 .Bd -literal -offset indent
274 SLIST_HEAD(HEADNAME, TYPE) head;
279 is the name of the structure to be defined, and
281 is the type of the elements to be linked into the list.
282 A pointer to the head of the list can later be declared as:
283 .Bd -literal -offset indent
284 struct HEADNAME *headp;
291 are user selectable.)
294 .Nm SLIST_HEAD_INITIALIZER
295 evaluates to an initializer for the list
300 evaluates to true if there are no elements in the list.
304 declares a structure that connects the elements in
309 returns the first element in the list or NULL if the list is empty.
313 traverses the list referenced by
315 in the forward direction, assigning each element in
321 initializes the list referenced by
325 .Nm SLIST_INSERT_HEAD
326 inserts the new element
328 at the head of the list.
331 .Nm SLIST_INSERT_AFTER
332 inserts the new element
339 returns the next element in the list.
342 .Nm SLIST_REMOVE_HEAD
345 from the head of the list.
346 For optimum efficiency,
347 elements being removed from the head of the list should explicitly use
348 this macro instead of the generic
357 .Sh SINGLY-LINKED LIST EXAMPLE
359 SLIST_HEAD(slisthead, entry) head =
360 SLIST_HEAD_INITIALIZER(head);
361 struct slisthead *headp; /* Singly-linked List head. */
364 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
366 } *n1, *n2, *n3, *np;
368 SLIST_INIT(&head); /* Initialize the list. */
370 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
371 SLIST_INSERT_HEAD(&head, n1, entries);
373 n2 = malloc(sizeof(struct entry)); /* Insert after. */
374 SLIST_INSERT_AFTER(n1, n2, entries);
376 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
379 n3 = SLIST_FIRST(&head);
380 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
382 /* Forward traversal. */
383 SLIST_FOREACH(np, &head, entries)
386 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
387 n1 = SLIST_FIRST(&head);
388 SLIST_REMOVE_HEAD(&head, entries);
392 .Sh SINGLY-LINKED TAIL QUEUES
393 A singly-linked tail queue is headed by a structure defined by the
396 This structure contains a pair of pointers,
397 one to the first element in the tail queue and the other to
398 the last element in the tail queue.
399 The elements are singly linked for minimum space and pointer
400 manipulation overhead at the expense of O(n) removal for arbitrary
402 New elements can be added to the tail queue after an existing element,
403 at the head of the tail queue, or at the end of the tail queue.
406 structure is declared as follows:
407 .Bd -literal -offset indent
408 STAILQ_HEAD(HEADNAME, TYPE) head;
413 is the name of the structure to be defined, and
415 is the type of the elements to be linked into the tail queue.
416 A pointer to the head of the tail queue can later be declared as:
417 .Bd -literal -offset indent
418 struct HEADNAME *headp;
425 are user selectable.)
428 .Nm STAILQ_HEAD_INITIALIZER
429 evaluates to an initializer for the tail queue
434 evaluates to true if there are no items on the tail queue.
438 declares a structure that connects the elements in
443 returns the first item on the tail queue or NULL if the tail queue
448 traverses the tail queue referenced by
450 in the forward direction, assigning each element
456 initializes the tail queue referenced by
460 .Nm STAILQ_INSERT_HEAD
461 inserts the new element
463 at the head of the tail queue.
466 .Nm STAILQ_INSERT_TAIL
467 inserts the new element
469 at the end of the tail queue.
472 .Nm STAILQ_INSERT_AFTER
473 inserts the new element
480 returns the last item on the tail queue.
481 If the tail queue is empty the return value is undefined.
485 returns the next item on the tail queue, or NULL this item is the last.
488 .Nm STAILQ_REMOVE_HEAD
489 removes the element at the head of the tail queue.
490 For optimum efficiency,
491 elements being removed from the head of the tail queue should
492 use this macro explicitly rather than the generic
501 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
503 STAILQ_HEAD(stailhead, entry) head =
504 STAILQ_HEAD_INITIALIZER(head);
505 struct stailhead *headp; /* Singly-linked tail queue head. */
508 STAILQ_ENTRY(entry) entries; /* Tail queue. */
510 } *n1, *n2, *n3, *np;
512 STAILQ_INIT(&head); /* Initialize the queue. */
514 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
515 STAILQ_INSERT_HEAD(&head, n1, entries);
517 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
518 STAILQ_INSERT_TAIL(&head, n1, entries);
520 n2 = malloc(sizeof(struct entry)); /* Insert after. */
521 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
523 STAILQ_REMOVE(&head, n2, entry, entries);
525 /* Deletion from the head. */
526 n3 = STAILQ_FIRST(&head);
527 STAILQ_REMOVE_HEAD(&head, entries);
529 /* Forward traversal. */
530 STAILQ_FOREACH(np, &head, entries)
532 /* TailQ Deletion. */
533 while (!STAILQ_EMPTY(&head)) {
534 n1 = STAILQ_FIRST(&head);
535 STAILQ_REMOVE_HEAD(&head, entries);
538 /* Faster TailQ Deletion. */
539 n1 = STAILQ_FIRST(&head);
541 n2 = STAILQ_NEXT(n1, entries);
548 A list is headed by a structure defined by the
551 This structure contains a single pointer to the first element
553 The elements are doubly linked so that an arbitrary element can be
554 removed without traversing the list.
555 New elements can be added to the list after an existing element,
556 before an existing element, or at the head of the list.
559 structure is declared as follows:
560 .Bd -literal -offset indent
561 LIST_HEAD(HEADNAME, TYPE) head;
566 is the name of the structure to be defined, and
568 is the type of the elements to be linked into the list.
569 A pointer to the head of the list can later be declared as:
570 .Bd -literal -offset indent
571 struct HEADNAME *headp;
578 are user selectable.)
581 .Nm LIST_HEAD_INITIALIZER
582 evaluates to an initializer for the list
587 evaluates to true if their are no elements in the list.
591 declares a structure that connects the elements in
596 returns the first element in the list or NULL if the list
601 traverses the list referenced by
603 in the forward direction, assigning each element in turn to
608 initializes the list referenced by
613 inserts the new element
615 at the head of the list.
618 .Nm LIST_INSERT_AFTER
619 inserts the new element
625 .Nm LIST_INSERT_BEFORE
626 inserts the new element
633 returns the next element in the list, or NULL if this is the last.
642 LIST_HEAD(listhead, entry) head =
643 LIST_HEAD_INITIALIZER(head);
644 struct listhead *headp; /* List head. */
647 LIST_ENTRY(entry) entries; /* List. */
649 } *n1, *n2, *n3, *np;
651 LIST_INIT(&head); /* Initialize the list. */
653 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
654 LIST_INSERT_HEAD(&head, n1, entries);
656 n2 = malloc(sizeof(struct entry)); /* Insert after. */
657 LIST_INSERT_AFTER(n1, n2, entries);
659 n3 = malloc(sizeof(struct entry)); /* Insert before. */
660 LIST_INSERT_BEFORE(n2, n3, entries);
662 LIST_REMOVE(n2, entries); /* Deletion. */
664 /* Forward traversal. */
665 LIST_FOREACH(np, &head, entries)
668 while (!LIST_EMPTY(&head)) { /* List Deletion. */
669 n1 = LIST_FIRST(&head);
670 LIST_REMOVE(n1, entries);
674 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
676 n2 = LIST_NEXT(n1, entries);
683 A tail queue is headed by a structure defined by the
686 This structure contains a pair of pointers,
687 one to the first element in the tail queue and the other to
688 the last element in the tail queue.
689 The elements are doubly linked so that an arbitrary element can be
690 removed without traversing the tail queue.
691 New elements can be added to the tail queue after an existing element,
692 before an existing element, at the head of the tail queue,
693 or at the end of the tail queue.
696 structure is declared as follows:
697 .Bd -literal -offset indent
698 TAILQ_HEAD(HEADNAME, TYPE) head;
703 is the name of the structure to be defined, and
705 is the type of the elements to be linked into the tail queue.
706 A pointer to the head of the tail queue can later be declared as:
707 .Bd -literal -offset indent
708 struct HEADNAME *headp;
715 are user selectable.)
718 .Nm TAILQ_HEAD_INITIALIZER
719 evaluates to an initializer for the tail queue
724 evaluates to true if there are no items on the tail queue.
728 declares a structure that connects the elements in
733 returns the first item on the tail queue or NULL if the tail queue
738 traverses the tail queue referenced by
740 in the forward direction, assigning each element in turn to
744 .Nm TAILQ_FOREACH_REVERSE
745 traverses the tail queue referenced by
747 in the reverse direction, assigning each element in turn to
752 initializes the tail queue referenced by
756 .Nm TAILQ_INSERT_HEAD
757 inserts the new element
759 at the head of the tail queue.
762 .Nm TAILQ_INSERT_TAIL
763 inserts the new element
765 at the end of the tail queue.
768 .Nm TAILQ_INSERT_AFTER
769 inserts the new element
775 .Nm TAILQ_INSERT_BEFORE
776 inserts the new element
783 returns the last item on the tail queue.
784 If the tail queue is empty the return value is undefined.
788 returns the next item on the tail queue, or NULL if this item is the last.
792 returns the previous item on the tail queue, or NULL if this item
800 .Sh TAIL QUEUE EXAMPLE
802 TAILQ_HEAD(tailhead, entry) head =
803 TAILQ_HEAD_INITIALIZER(head);
804 struct tailhead *headp; /* Tail queue head. */
807 TAILQ_ENTRY(entry) entries; /* Tail queue. */
809 } *n1, *n2, *n3, *np;
811 TAILQ_INIT(&head); /* Initialize the queue. */
813 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
814 TAILQ_INSERT_HEAD(&head, n1, entries);
816 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
817 TAILQ_INSERT_TAIL(&head, n1, entries);
819 n2 = malloc(sizeof(struct entry)); /* Insert after. */
820 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
822 n3 = malloc(sizeof(struct entry)); /* Insert before. */
823 TAILQ_INSERT_BEFORE(n2, n3, entries);
825 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
827 /* Forward traversal. */
828 TAILQ_FOREACH(np, &head, entries)
830 /* Reverse traversal. */
831 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
833 /* TailQ Deletion. */
834 while (!TAILQ_EMPTY(&head)) {
835 n1 = TAILQ_FIRST(&head);
836 TAILQ_REMOVE(&head, n1, entries);
839 /* Faster TailQ Deletion. */
840 n1 = TAILQ_FIRST(&head);
842 n2 = TAILQ_NEXT(n1, entries);
851 functions first appeared in