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 four types of data structures:
158 singly-linked lists, singly-linked tail queues, lists, and tail queues.
159 All four structures support the following functionality:
160 .Bl -enum -compact -offset indent
162 Insertion of a new entry at the head of the list.
164 Insertion of a new entry after any element in the list.
166 O(1) removal of an entry from the head of the list.
168 O(n) removal of any entry in the list.
170 Forward traversal through the list.
173 Singly-linked lists are the simplest of the five data structures
174 and support only the above functionality.
175 Singly-linked lists are ideal for applications with large datasets
176 and few or no removals,
177 or for implementing a LIFO queue.
179 Singly-linked tail queues add the following functionality:
180 .Bl -enum -compact -offset indent
182 Entries can be added at the end of a list.
185 .Bl -enum -compact -offset indent
187 All list insertions must specify the head of the list.
189 Each head entry requires two pointers rather than one.
191 Code size is about 15% greater and operations run about 20% slower
192 than singly-linked lists.
195 Singly-linked tailqs are ideal for applications with large datasets and
197 or for implementing a FIFO queue.
199 All doubly linked types of data structures (lists and tail queues)
201 .Bl -enum -compact -offset indent
203 Insertion of a new entry before any element in the list.
205 O(1) removal of any entry in the list.
208 .Bl -enum -compact -offset indent
210 Each elements requires two pointers rather than one.
212 Code size and execution time of operations (except for removal) is about
213 twice that of the singly-linked data-structures.
216 Linked lists are the simplest of the doubly linked data structures and support
217 only the above functionality over singly-linked lists.
219 Tail queues add the following functionality:
220 .Bl -enum -compact -offset indent
222 Entries can be added at the end of a list.
224 They may be traversed backwards, from tail to head.
227 .Bl -enum -compact -offset indent
229 All list insertions and removals 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 In the macro definitions,
239 is the name of a user defined structure,
240 that must contain a field of type
250 is the name of a user defined structure that must be declared
257 See the examples below for further explanation of how these
259 .Sh SINGLY-LINKED LISTS
260 A singly-linked list is headed by a structure defined by the
263 This structure contains a single pointer to the first element
265 The elements are singly linked for minimum space and pointer manipulation
266 overhead at the expense of O(n) removal for arbitrary elements.
267 New elements can be added to the list after an existing element or
268 at the head of the list.
271 structure is declared as follows:
272 .Bd -literal -offset indent
273 SLIST_HEAD(HEADNAME, TYPE) head;
278 is the name of the structure to be defined, and
280 is the type of the elements to be linked into the list.
281 A pointer to the head of the list can later be declared as:
282 .Bd -literal -offset indent
283 struct HEADNAME *headp;
290 are user selectable.)
293 .Nm SLIST_HEAD_INITIALIZER
294 evaluates to an initializer for the list
299 evaluates to true if there are no elements in the list.
303 declares a structure that connects the elements in
308 returns the first element in the list or NULL if the list is empty.
312 traverses the list referenced by
314 in the forward direction, assigning each element in
320 initializes the list referenced by
324 .Nm SLIST_INSERT_HEAD
325 inserts the new element
327 at the head of the list.
330 .Nm SLIST_INSERT_AFTER
331 inserts the new element
338 returns the next element in the list.
341 .Nm SLIST_REMOVE_HEAD
344 from the head of the list.
345 For optimum efficiency,
346 elements being removed from the head of the list should explicitly use
347 this macro instead of the generic
356 .Sh SINGLY-LINKED LIST EXAMPLE
358 SLIST_HEAD(slisthead, entry) head =
359 SLIST_HEAD_INITIALIZER(head);
360 struct slisthead *headp; /* Singly-linked List head. */
363 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
365 } *n1, *n2, *n3, *np;
367 SLIST_INIT(&head); /* Initialize the list. */
369 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
370 SLIST_INSERT_HEAD(&head, n1, entries);
372 n2 = malloc(sizeof(struct entry)); /* Insert after. */
373 SLIST_INSERT_AFTER(n1, n2, entries);
375 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
378 n3 = SLIST_FIRST(&head);
379 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
381 /* Forward traversal. */
382 SLIST_FOREACH(np, &head, entries)
385 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
386 n1 = SLIST_FIRST(&head);
387 SLIST_REMOVE_HEAD(&head, entries);
391 .Sh SINGLY-LINKED TAIL QUEUES
392 A singly-linked tail queue is headed by a structure defined by the
395 This structure contains a pair of pointers,
396 one to the first element in the tail queue and the other to
397 the last element in the tail queue.
398 The elements are singly linked for minimum space and pointer
399 manipulation overhead at the expense of O(n) removal for arbitrary
401 New elements can be added to the tail queue after an existing element,
402 at the head of the tail queue, or at the end of the tail queue.
405 structure is declared as follows:
406 .Bd -literal -offset indent
407 STAILQ_HEAD(HEADNAME, TYPE) head;
412 is the name of the structure to be defined, and
414 is the type of the elements to be linked into the tail queue.
415 A pointer to the head of the tail queue can later be declared as:
416 .Bd -literal -offset indent
417 struct HEADNAME *headp;
424 are user selectable.)
427 .Nm STAILQ_HEAD_INITIALIZER
428 evaluates to an initializer for the tail queue
433 evaluates to true if there are no items on the tail queue.
437 declares a structure that connects the elements in
442 returns the first item on the tail queue or NULL if the tail queue
447 traverses the tail queue referenced by
449 in the forward direction, assigning each element
455 initializes the tail queue referenced by
459 .Nm STAILQ_INSERT_HEAD
460 inserts the new element
462 at the head of the tail queue.
465 .Nm STAILQ_INSERT_TAIL
466 inserts the new element
468 at the end of the tail queue.
471 .Nm STAILQ_INSERT_AFTER
472 inserts the new element
479 returns the last item on the tail queue.
480 If the tail queue is empty the return value is undefined.
484 returns the next item on the tail queue, or NULL this item is the last.
487 .Nm STAILQ_REMOVE_HEAD
488 removes the element at the head of the tail queue.
489 For optimum efficiency,
490 elements being removed from the head of the tail queue should
491 use this macro explicitly rather than the generic
500 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
502 STAILQ_HEAD(stailhead, entry) head =
503 STAILQ_HEAD_INITIALIZER(head);
504 struct stailhead *headp; /* Singly-linked tail queue head. */
507 STAILQ_ENTRY(entry) entries; /* Tail queue. */
509 } *n1, *n2, *n3, *np;
511 STAILQ_INIT(&head); /* Initialize the queue. */
513 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
514 STAILQ_INSERT_HEAD(&head, n1, entries);
516 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
517 STAILQ_INSERT_TAIL(&head, n1, entries);
519 n2 = malloc(sizeof(struct entry)); /* Insert after. */
520 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
522 STAILQ_REMOVE(&head, n2, entry, entries);
524 /* Deletion from the head. */
525 n3 = STAILQ_FIRST(&head);
526 STAILQ_REMOVE_HEAD(&head, entries);
528 /* Forward traversal. */
529 STAILQ_FOREACH(np, &head, entries)
531 /* TailQ Deletion. */
532 while (!STAILQ_EMPTY(&head)) {
533 n1 = STAILQ_FIRST(&head);
534 STAILQ_REMOVE_HEAD(&head, entries);
537 /* Faster TailQ Deletion. */
538 n1 = STAILQ_FIRST(&head);
540 n2 = STAILQ_NEXT(n1, entries);
547 A list is headed by a structure defined by the
550 This structure contains a single pointer to the first element
552 The elements are doubly linked so that an arbitrary element can be
553 removed without traversing the list.
554 New elements can be added to the list after an existing element,
555 before an existing element, or at the head of the list.
558 structure is declared as follows:
559 .Bd -literal -offset indent
560 LIST_HEAD(HEADNAME, TYPE) head;
565 is the name of the structure to be defined, and
567 is the type of the elements to be linked into the list.
568 A pointer to the head of the list can later be declared as:
569 .Bd -literal -offset indent
570 struct HEADNAME *headp;
577 are user selectable.)
580 .Nm LIST_HEAD_INITIALIZER
581 evaluates to an initializer for the list
586 evaluates to true if their are no elements in the list.
590 declares a structure that connects the elements in
595 returns the first element in the list or NULL if the list
600 traverses the list referenced by
602 in the forward direction, assigning each element in turn to
607 initializes the list referenced by
612 inserts the new element
614 at the head of the list.
617 .Nm LIST_INSERT_AFTER
618 inserts the new element
624 .Nm LIST_INSERT_BEFORE
625 inserts the new element
632 returns the next element in the list, or NULL if this is the last.
641 LIST_HEAD(listhead, entry) head =
642 LIST_HEAD_INITIALIZER(head);
643 struct listhead *headp; /* List head. */
646 LIST_ENTRY(entry) entries; /* List. */
648 } *n1, *n2, *n3, *np;
650 LIST_INIT(&head); /* Initialize the list. */
652 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
653 LIST_INSERT_HEAD(&head, n1, entries);
655 n2 = malloc(sizeof(struct entry)); /* Insert after. */
656 LIST_INSERT_AFTER(n1, n2, entries);
658 n3 = malloc(sizeof(struct entry)); /* Insert before. */
659 LIST_INSERT_BEFORE(n2, n3, entries);
661 LIST_REMOVE(n2, entries); /* Deletion. */
663 /* Forward traversal. */
664 LIST_FOREACH(np, &head, entries)
667 while (!LIST_EMPTY(&head)) { /* List Deletion. */
668 n1 = LIST_FIRST(&head);
669 LIST_REMOVE(n1, entries);
673 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
675 n2 = LIST_NEXT(n1, entries);
682 A tail queue is headed by a structure defined by the
685 This structure contains a pair of pointers,
686 one to the first element in the tail queue and the other to
687 the last element in the tail queue.
688 The elements are doubly linked so that an arbitrary element can be
689 removed without traversing the tail queue.
690 New elements can be added to the tail queue after an existing element,
691 before an existing element, at the head of the tail queue,
692 or at the end of the tail queue.
695 structure is declared as follows:
696 .Bd -literal -offset indent
697 TAILQ_HEAD(HEADNAME, TYPE) head;
702 is the name of the structure to be defined, and
704 is the type of the elements to be linked into the tail queue.
705 A pointer to the head of the tail queue can later be declared as:
706 .Bd -literal -offset indent
707 struct HEADNAME *headp;
714 are user selectable.)
717 .Nm TAILQ_HEAD_INITIALIZER
718 evaluates to an initializer for the tail queue
723 evaluates to true if there are no items on the tail queue.
727 declares a structure that connects the elements in
732 returns the first item on the tail queue or NULL if the tail queue
737 traverses the tail queue referenced by
739 in the forward direction, assigning each element in turn to
743 .Nm TAILQ_FOREACH_REVERSE
744 traverses the tail queue referenced by
746 in the reverse direction, assigning each element in turn to
751 initializes the tail queue referenced by
755 .Nm TAILQ_INSERT_HEAD
756 inserts the new element
758 at the head of the tail queue.
761 .Nm TAILQ_INSERT_TAIL
762 inserts the new element
764 at the end of the tail queue.
767 .Nm TAILQ_INSERT_AFTER
768 inserts the new element
774 .Nm TAILQ_INSERT_BEFORE
775 inserts the new element
782 returns the last item on the tail queue.
783 If the tail queue is empty the return value is undefined.
787 returns the next item on the tail queue, or NULL if this item is the last.
791 returns the previous item on the tail queue, or NULL if this item
799 .Sh TAIL QUEUE EXAMPLE
801 TAILQ_HEAD(tailhead, entry) head =
802 TAILQ_HEAD_INITIALIZER(head);
803 struct tailhead *headp; /* Tail queue head. */
806 TAILQ_ENTRY(entry) entries; /* Tail queue. */
808 } *n1, *n2, *n3, *np;
810 TAILQ_INIT(&head); /* Initialize the queue. */
812 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
813 TAILQ_INSERT_HEAD(&head, n1, entries);
815 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
816 TAILQ_INSERT_TAIL(&head, n1, entries);
818 n2 = malloc(sizeof(struct entry)); /* Insert after. */
819 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
821 n3 = malloc(sizeof(struct entry)); /* Insert before. */
822 TAILQ_INSERT_BEFORE(n2, n3, entries);
824 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
826 /* Forward traversal. */
827 TAILQ_FOREACH(np, &head, entries)
829 /* Reverse traversal. */
830 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
832 /* TailQ Deletion. */
833 while (!TAILQ_EMPTY(&head)) {
834 n1 = TAILQ_FIRST(&head);
835 TAILQ_REMOVE(&head, n1, entries);
838 /* Faster TailQ Deletion. */
839 n1 = TAILQ_FIRST(&head);
841 n2 = TAILQ_NEXT(n1, entries);
850 functions first appeared in