xref: /freebsd/share/man/man3/queue.3 (revision fa38579f317d5c2ff2926fab9b12ee6d429bd155)
1.\" Copyright (c) 1993
2.\"	The Regents of the University of California.  All rights reserved.
3.\"
4.\" Redistribution and use in source and binary forms, with or without
5.\" modification, are permitted provided that the following conditions
6.\" are met:
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. Neither the name of the University nor the names of its contributors
13.\"    may be used to endorse or promote products derived from this software
14.\"    without specific prior written permission.
15.\"
16.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
17.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
20.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
22.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
23.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
24.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
25.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26.\" SUCH DAMAGE.
27.\"
28.Dd April 28, 2025
29.Dt QUEUE 3
30.Os
31.Sh NAME
32.Nm SLIST_CLASS_ENTRY ,
33.Nm SLIST_CLASS_HEAD ,
34.Nm SLIST_CONCAT ,
35.Nm SLIST_EMPTY ,
36.Nm SLIST_EMPTY_ATOMIC ,
37.Nm SLIST_ENTRY ,
38.Nm SLIST_FIRST ,
39.Nm SLIST_FOREACH ,
40.Nm SLIST_FOREACH_FROM ,
41.Nm SLIST_FOREACH_FROM_SAFE ,
42.Nm SLIST_FOREACH_SAFE ,
43.Nm SLIST_HEAD ,
44.Nm SLIST_HEAD_INITIALIZER ,
45.Nm SLIST_INIT ,
46.Nm SLIST_INSERT_AFTER ,
47.Nm SLIST_INSERT_HEAD ,
48.Nm SLIST_NEXT ,
49.Nm SLIST_REMOVE ,
50.Nm SLIST_REMOVE_AFTER ,
51.Nm SLIST_REMOVE_HEAD ,
52.Nm SLIST_SPLIT_AFTER ,
53.Nm SLIST_SWAP ,
54.Nm STAILQ_CLASS_ENTRY ,
55.Nm STAILQ_CLASS_HEAD ,
56.Nm STAILQ_CONCAT ,
57.Nm STAILQ_EMPTY ,
58.Nm STAILQ_EMPTY_ATOMIC ,
59.Nm STAILQ_ENTRY ,
60.Nm STAILQ_FIRST ,
61.Nm STAILQ_FOREACH ,
62.Nm STAILQ_FOREACH_FROM ,
63.Nm STAILQ_FOREACH_FROM_SAFE ,
64.Nm STAILQ_FOREACH_SAFE ,
65.Nm STAILQ_HEAD ,
66.Nm STAILQ_HEAD_INITIALIZER ,
67.Nm STAILQ_INIT ,
68.Nm STAILQ_INSERT_AFTER ,
69.Nm STAILQ_INSERT_HEAD ,
70.Nm STAILQ_INSERT_TAIL ,
71.Nm STAILQ_LAST ,
72.Nm STAILQ_NEXT ,
73.Nm STAILQ_REMOVE ,
74.Nm STAILQ_REMOVE_AFTER ,
75.Nm STAILQ_REMOVE_HEAD ,
76.Nm STAILQ_SPLIT_AFTER ,
77.Nm STAILQ_SWAP ,
78.Nm LIST_CLASS_ENTRY ,
79.Nm LIST_CLASS_HEAD ,
80.Nm LIST_CONCAT ,
81.Nm LIST_EMPTY ,
82.Nm LIST_EMPTY_ATOMIC ,
83.Nm LIST_ENTRY ,
84.Nm LIST_FIRST ,
85.Nm LIST_FOREACH ,
86.Nm LIST_FOREACH_FROM ,
87.Nm LIST_FOREACH_FROM_SAFE ,
88.Nm LIST_FOREACH_SAFE ,
89.Nm LIST_HEAD ,
90.Nm LIST_HEAD_INITIALIZER ,
91.Nm LIST_INIT ,
92.Nm LIST_INSERT_AFTER ,
93.Nm LIST_INSERT_BEFORE ,
94.Nm LIST_INSERT_HEAD ,
95.Nm LIST_NEXT ,
96.Nm LIST_PREV ,
97.Nm LIST_REMOVE ,
98.Nm LIST_REPLACE ,
99.Nm LIST_SPLIT_AFTER ,
100.Nm LIST_SWAP ,
101.Nm TAILQ_CLASS_ENTRY ,
102.Nm TAILQ_CLASS_HEAD ,
103.Nm TAILQ_CONCAT ,
104.Nm TAILQ_EMPTY ,
105.Nm TAILQ_EMPTY_ATOMIC ,
106.Nm TAILQ_ENTRY ,
107.Nm TAILQ_FIRST ,
108.Nm TAILQ_FOREACH ,
109.Nm TAILQ_FOREACH_FROM ,
110.Nm TAILQ_FOREACH_FROM_SAFE ,
111.Nm TAILQ_FOREACH_REVERSE ,
112.Nm TAILQ_FOREACH_REVERSE_FROM ,
113.Nm TAILQ_FOREACH_REVERSE_FROM_SAFE ,
114.Nm TAILQ_FOREACH_REVERSE_SAFE ,
115.Nm TAILQ_FOREACH_SAFE ,
116.Nm TAILQ_HEAD ,
117.Nm TAILQ_HEAD_INITIALIZER ,
118.Nm TAILQ_INIT ,
119.Nm TAILQ_INSERT_AFTER ,
120.Nm TAILQ_INSERT_BEFORE ,
121.Nm TAILQ_INSERT_HEAD ,
122.Nm TAILQ_INSERT_TAIL ,
123.Nm TAILQ_LAST ,
124.Nm TAILQ_NEXT ,
125.Nm TAILQ_PREV ,
126.Nm TAILQ_REMOVE ,
127.Nm TAILQ_REPLACE ,
128.Nm TAILQ_SPLIT_AFTER ,
129.Nm TAILQ_SWAP
130.Nd implementations of singly-linked lists, singly-linked tail queues,
131lists and tail queues
132.Sh SYNOPSIS
133.In sys/queue.h
134.\"
135.Fn SLIST_CLASS_ENTRY "CLASSTYPE"
136.Fn SLIST_CLASS_HEAD "HEADNAME" "CLASSTYPE"
137.Fn SLIST_CONCAT "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE" "SLIST_ENTRY NAME"
138.Fn SLIST_EMPTY "SLIST_HEAD *head"
139.Fn SLIST_EMPTY_ATOMIC "SLIST_HEAD *head"
140.Fn SLIST_ENTRY "TYPE"
141.Fn SLIST_FIRST "SLIST_HEAD *head"
142.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
143.Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
144.Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
145.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
146.Fn SLIST_HEAD "HEADNAME" "TYPE"
147.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
148.Fn SLIST_INIT "SLIST_HEAD *head"
149.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
150.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
151.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
152.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
153.Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME"
154.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
155.Fn SLIST_SPLIT_AFTER "SLIST_HEAD *head" "TYPE *elm" "SLIST_HEAD *rest" "SLIST_ENTRY NAME"
156.Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "TYPE"
157.\"
158.Fn STAILQ_CLASS_ENTRY "CLASSTYPE"
159.Fn STAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE"
160.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
161.Fn STAILQ_EMPTY "STAILQ_HEAD *head"
162.Fn STAILQ_EMPTY_ATOMIC "STAILQ_HEAD *head"
163.Fn STAILQ_ENTRY "TYPE"
164.Fn STAILQ_FIRST "STAILQ_HEAD *head"
165.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
166.Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
167.Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
168.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
169.Fn STAILQ_HEAD "HEADNAME" "TYPE"
170.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
171.Fn STAILQ_INIT "STAILQ_HEAD *head"
172.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
173.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
174.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
175.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
176.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
177.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
178.Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
179.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
180.Fn STAILQ_SPLIT_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_HEAD *rest" "STAILQ_ENTRY NAME"
181.Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "TYPE"
182.\"
183.Fn LIST_CLASS_ENTRY "CLASSTYPE"
184.Fn LIST_CLASS_HEAD "HEADNAME" "CLASSTYPE"
185.Fn LIST_CONCAT "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
186.Fn LIST_EMPTY "LIST_HEAD *head"
187.Fn LIST_EMPTY_ATOMIC "LIST_HEAD *head"
188.Fn LIST_ENTRY "TYPE"
189.Fn LIST_FIRST "LIST_HEAD *head"
190.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
191.Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
192.Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
193.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
194.Fn LIST_HEAD "HEADNAME" "TYPE"
195.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
196.Fn LIST_INIT "LIST_HEAD *head"
197.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
198.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
199.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
200.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
201.Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME"
202.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
203.Fn LIST_REPLACE "TYPE *elm" "TYPE *new" "LIST_ENTRY NAME"
204.Fn LIST_SPLIT_AFTER "LIST_HEAD *head" "TYPE *elm" "LIST_HEAD *rest" "LIST_ENTRY NAME"
205.Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME"
206.\"
207.Fn TAILQ_CLASS_ENTRY "CLASSTYPE"
208.Fn TAILQ_CLASS_HEAD "HEADNAME" "CLASSTYPE"
209.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
210.Fn TAILQ_EMPTY "TAILQ_HEAD *head"
211.Fn TAILQ_EMPTY_ATOMIC "TAILQ_HEAD *head"
212.Fn TAILQ_ENTRY "TYPE"
213.Fn TAILQ_FIRST "TAILQ_HEAD *head"
214.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
215.Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
216.Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
217.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
218.Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
219.Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
220.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
221.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
222.Fn TAILQ_HEAD "HEADNAME" "TYPE"
223.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
224.Fn TAILQ_INIT "TAILQ_HEAD *head"
225.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
226.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
227.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
228.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
229.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
230.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
231.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
232.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
233.Fn TAILQ_REPLACE "TAILQ_HEAD *head" "TYPE *elm" "TYPE *new" "TAILQ_ENTRY NAME"
234.Fn TAILQ_SPLIT_AFTER "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_HEAD *rest" "TAILQ_ENTRY NAME"
235.Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME"
236.\"
237.Sh DESCRIPTION
238These macros define and operate on four types of data structures which
239can be used in both C and C++ source code:
240.Bl -enum -compact -offset indent
241.It
242Lists
243.It
244Singly-linked lists
245.It
246Singly-linked tail queues
247.It
248Tail queues
249.El
250All four structures support the following functionality:
251.Bl -enum -compact -offset indent
252.It
253Insertion of a new entry at the head of the list.
254.It
255Insertion of a new entry after any element in the list.
256.It
257O(1) removal of an entry from the head of the list.
258.It
259Forward traversal through the list.
260.It
261Splitting a list in two after any element in the list.
262.It
263Swapping the contents of two lists.
264.El
265.Pp
266Singly-linked lists are the simplest of the four data structures
267and support only the above functionality.
268Singly-linked lists are ideal for applications with large datasets
269and few or no removals,
270or for implementing a LIFO queue.
271Singly-linked lists add the following functionality:
272.Bl -enum -compact -offset indent
273.It
274O(n) removal of any entry in the list.
275.It
276O(n) concatenation of two lists.
277.El
278.Pp
279Singly-linked tail queues add the following functionality:
280.Bl -enum -compact -offset indent
281.It
282Entries can be added at the end of a list.
283.It
284O(n) removal of any entry in the list.
285.It
286They may be concatenated.
287.El
288However:
289.Bl -enum -compact -offset indent
290.It
291All list insertions must specify the head of the list.
292.It
293Each head entry requires two pointers rather than one.
294.It
295Code size is about 15% greater and operations run about 20% slower
296than singly-linked lists.
297.El
298.Pp
299Singly-linked tail queues are ideal for applications with large datasets and
300few or no removals,
301or for implementing a FIFO queue.
302.Pp
303All doubly linked types of data structures (lists and tail queues)
304additionally allow:
305.Bl -enum -compact -offset indent
306.It
307Insertion of a new entry before any element in the list.
308.It
309O(1) removal of any entry in the list.
310.El
311However:
312.Bl -enum -compact -offset indent
313.It
314Each element requires two pointers rather than one.
315.It
316Code size and execution time of operations (except for removal) is about
317twice that of the singly-linked data-structures.
318.El
319.Pp
320Linked lists are the simplest of the doubly linked data structures.
321They add the following functionality over the above:
322.Bl -enum -compact -offset indent
323.It
324O(n) concatenation of two lists.
325.It
326They may be traversed backwards.
327.El
328However:
329.Bl -enum -compact -offset indent
330.It
331To traverse backwards, an entry to begin the traversal and the list in
332which it is contained must be specified.
333.El
334.Pp
335Tail queues add the following functionality:
336.Bl -enum -compact -offset indent
337.It
338Entries can be added at the end of a list.
339.It
340They may be traversed backwards, from tail to head.
341.It
342They may be concatenated.
343.El
344However:
345.Bl -enum -compact -offset indent
346.It
347All list insertions and removals must specify the head of the list.
348.It
349Each head entry requires two pointers rather than one.
350.It
351Code size is about 15% greater and operations run about 20% slower
352than singly-linked lists.
353.El
354.Pp
355In the macro definitions,
356.Fa TYPE
357is the name of a user defined structure.
358The structure must contain a field called
359.Fa NAME
360which is of type
361.Li SLIST_ENTRY ,
362.Li STAILQ_ENTRY ,
363.Li LIST_ENTRY ,
364or
365.Li TAILQ_ENTRY .
366In the macro definitions,
367.Fa CLASSTYPE
368is the name of a user defined class.
369The class must contain a field called
370.Fa NAME
371which is of type
372.Li SLIST_CLASS_ENTRY ,
373.Li STAILQ_CLASS_ENTRY ,
374.Li LIST_CLASS_ENTRY ,
375or
376.Li TAILQ_CLASS_ENTRY .
377The argument
378.Fa HEADNAME
379is the name of a user defined structure that must be declared
380using the macros
381.Li SLIST_HEAD ,
382.Li SLIST_CLASS_HEAD ,
383.Li STAILQ_HEAD ,
384.Li STAILQ_CLASS_HEAD ,
385.Li LIST_HEAD ,
386.Li LIST_CLASS_HEAD ,
387.Li TAILQ_HEAD ,
388or
389.Li TAILQ_CLASS_HEAD .
390See the examples below for further explanation of how these
391macros are used.
392.Sh SINGLY-LINKED LISTS
393A singly-linked list is headed by a structure defined by the
394.Nm SLIST_HEAD
395macro.
396This structure contains a single pointer to the first element
397on the list.
398The elements are singly linked for minimum space and pointer manipulation
399overhead at the expense of O(n) removal for arbitrary elements.
400New elements can be added to the list after an existing element or
401at the head of the list.
402An
403.Fa SLIST_HEAD
404structure is declared as follows:
405.Bd -literal -offset indent
406SLIST_HEAD(HEADNAME, TYPE) head;
407.Ed
408.Pp
409where
410.Fa HEADNAME
411is the name of the structure to be defined, and
412.Fa TYPE
413is the type of the elements to be linked into the list.
414A pointer to the head of the list can later be declared as:
415.Bd -literal -offset indent
416struct HEADNAME *headp;
417.Ed
418.Pp
419(The names
420.Li head
421and
422.Li headp
423are user selectable.)
424.Pp
425The macro
426.Nm SLIST_HEAD_INITIALIZER
427evaluates to an initializer for the list
428.Fa head .
429.Pp
430The macro
431.Nm SLIST_CONCAT
432concatenates the list headed by
433.Fa head2
434onto the end of the one headed by
435.Fa head1
436removing all entries from the former.
437Use of this macro should be avoided as it traverses the entirety of the
438.Fa head1
439list.
440A singly-linked tail queue should be used if this macro is needed in
441high-usage code paths or to operate on long lists.
442.Pp
443The macro
444.Nm SLIST_EMPTY
445evaluates to true if there are no elements in the list.
446The
447.Nm SLIST_EMPTY_ATOMIC
448variant has the same behavior, but can be safely used in contexts where it is
449possible that a different thread is concurrently updating the list.
450.Pp
451The macro
452.Nm SLIST_ENTRY
453declares a structure that connects the elements in
454the list.
455.Pp
456The macro
457.Nm SLIST_FIRST
458returns the first element in the list or NULL if the list is empty.
459.Pp
460The macro
461.Nm SLIST_FOREACH
462traverses the list referenced by
463.Fa head
464in the forward direction, assigning each element in
465turn to
466.Fa var .
467.Pp
468The macro
469.Nm SLIST_FOREACH_FROM
470behaves identically to
471.Nm SLIST_FOREACH
472when
473.Fa var
474is NULL, else it treats
475.Fa var
476as a previously found SLIST element and begins the loop at
477.Fa var
478instead of the first element in the SLIST referenced by
479.Fa head .
480.Pp
481The macro
482.Nm SLIST_FOREACH_SAFE
483traverses the list referenced by
484.Fa head
485in the forward direction, assigning each element in
486turn to
487.Fa var .
488However, unlike
489.Fn SLIST_FOREACH
490here it is permitted to both remove
491.Fa var
492as well as free it from within the loop safely without interfering with the
493traversal.
494.Pp
495The macro
496.Nm SLIST_FOREACH_FROM_SAFE
497behaves identically to
498.Nm SLIST_FOREACH_SAFE
499when
500.Fa var
501is NULL, else it treats
502.Fa var
503as a previously found SLIST element and begins the loop at
504.Fa var
505instead of the first element in the SLIST referenced by
506.Fa head .
507.Pp
508The macro
509.Nm SLIST_INIT
510initializes the list referenced by
511.Fa head .
512.Pp
513The macro
514.Nm SLIST_INSERT_HEAD
515inserts the new element
516.Fa elm
517at the head of the list.
518.Pp
519The macro
520.Nm SLIST_INSERT_AFTER
521inserts the new element
522.Fa elm
523after the element
524.Fa listelm .
525.Pp
526The macro
527.Nm SLIST_NEXT
528returns the next element in the list.
529.Pp
530The macro
531.Nm SLIST_REMOVE_AFTER
532removes the element after
533.Fa elm
534from the list.
535Unlike
536.Fa SLIST_REMOVE ,
537this macro does not traverse the entire list.
538.Pp
539The macro
540.Nm SLIST_REMOVE_HEAD
541removes the element
542.Fa elm
543from the head of the list.
544For optimum efficiency,
545elements being removed from the head of the list should explicitly use
546this macro instead of the generic
547.Fa SLIST_REMOVE
548macro.
549.Pp
550The macro
551.Nm SLIST_REMOVE
552removes the element
553.Fa elm
554from the list.
555Use of this macro should be avoided as it traverses the entire list.
556A doubly-linked list should be used if this macro is needed in
557high-usage code paths or to operate on long lists.
558.Pp
559The macro
560.Nm SLIST_SPLIT_AFTER
561splits the list referenced by
562.Fa head ,
563making
564.Fa rest
565reference the list formed by elements after
566.Fa elm
567in
568.Fa head .
569.Pp
570The macro
571.Nm SLIST_SWAP
572swaps the contents of
573.Fa head1
574and
575.Fa head2 .
576.Sh SINGLY-LINKED LIST EXAMPLE
577.Bd -literal
578SLIST_HEAD(slisthead, entry) head =
579    SLIST_HEAD_INITIALIZER(head);
580struct slisthead *headp;		/* Singly-linked List head. */
581struct entry {
582	...
583	SLIST_ENTRY(entry) entries;	/* Singly-linked List. */
584	...
585} *n1, *n2, *n3, *np;
586
587SLIST_INIT(&head);			/* Initialize the list. */
588
589n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
590SLIST_INSERT_HEAD(&head, n1, entries);
591
592n2 = malloc(sizeof(struct entry));	/* Insert after. */
593SLIST_INSERT_AFTER(n1, n2, entries);
594
595SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
596free(n2);
597
598n3 = SLIST_FIRST(&head);
599SLIST_REMOVE_HEAD(&head, entries);	/* Deletion from the head. */
600free(n3);
601					/* Forward traversal. */
602SLIST_FOREACH(np, &head, entries)
603	np-> ...
604					/* Safe forward traversal. */
605SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
606	np->do_stuff();
607	...
608	SLIST_REMOVE(&head, np, entry, entries);
609	free(np);
610}
611
612while (!SLIST_EMPTY(&head)) {		/* List Deletion. */
613	n1 = SLIST_FIRST(&head);
614	SLIST_REMOVE_HEAD(&head, entries);
615	free(n1);
616}
617.Ed
618.Sh SINGLY-LINKED TAIL QUEUES
619A singly-linked tail queue is headed by a structure defined by the
620.Nm STAILQ_HEAD
621macro.
622This structure contains a pair of pointers,
623one to the first element in the tail queue and the other to
624the last element in the tail queue.
625The elements are singly linked for minimum space and pointer
626manipulation overhead at the expense of O(n) removal for arbitrary
627elements.
628New elements can be added to the tail queue after an existing element,
629at the head of the tail queue, or at the end of the tail queue.
630A
631.Fa STAILQ_HEAD
632structure is declared as follows:
633.Bd -literal -offset indent
634STAILQ_HEAD(HEADNAME, TYPE) head;
635.Ed
636.Pp
637where
638.Li HEADNAME
639is the name of the structure to be defined, and
640.Li TYPE
641is the type of the elements to be linked into the tail queue.
642A pointer to the head of the tail queue can later be declared as:
643.Bd -literal -offset indent
644struct HEADNAME *headp;
645.Ed
646.Pp
647(The names
648.Li head
649and
650.Li headp
651are user selectable.)
652.Pp
653The macro
654.Nm STAILQ_HEAD_INITIALIZER
655evaluates to an initializer for the tail queue
656.Fa head .
657.Pp
658The macro
659.Nm STAILQ_CONCAT
660concatenates the tail queue headed by
661.Fa head2
662onto the end of the one headed by
663.Fa head1
664removing all entries from the former.
665.Pp
666The macro
667.Nm STAILQ_EMPTY
668evaluates to true if there are no items on the tail queue.
669The
670.Nm STAILQ_EMPTY_ATOMIC
671variant has the same behavior, but can be safely used in contexts where it is
672possible that a different thread is concurrently updating the queue.
673.Pp
674The macro
675.Nm STAILQ_ENTRY
676declares a structure that connects the elements in
677the tail queue.
678.Pp
679The macro
680.Nm STAILQ_FIRST
681returns the first item on the tail queue or NULL if the tail queue
682is empty.
683.Pp
684The macro
685.Nm STAILQ_FOREACH
686traverses the tail queue referenced by
687.Fa head
688in the forward direction, assigning each element
689in turn to
690.Fa var .
691.Pp
692The macro
693.Nm STAILQ_FOREACH_FROM
694behaves identically to
695.Nm STAILQ_FOREACH
696when
697.Fa var
698is NULL, else it treats
699.Fa var
700as a previously found STAILQ element and begins the loop at
701.Fa var
702instead of the first element in the STAILQ referenced by
703.Fa head .
704.Pp
705The macro
706.Nm STAILQ_FOREACH_SAFE
707traverses the tail queue referenced by
708.Fa head
709in the forward direction, assigning each element
710in turn to
711.Fa var .
712However, unlike
713.Fn STAILQ_FOREACH
714here it is permitted to both remove
715.Fa var
716as well as free it from within the loop safely without interfering with the
717traversal.
718.Pp
719The macro
720.Nm STAILQ_FOREACH_FROM_SAFE
721behaves identically to
722.Nm STAILQ_FOREACH_SAFE
723when
724.Fa var
725is NULL, else it treats
726.Fa var
727as a previously found STAILQ element and begins the loop at
728.Fa var
729instead of the first element in the STAILQ referenced by
730.Fa head .
731.Pp
732The macro
733.Nm STAILQ_INIT
734initializes the tail queue referenced by
735.Fa head .
736.Pp
737The macro
738.Nm STAILQ_INSERT_HEAD
739inserts the new element
740.Fa elm
741at the head of the tail queue.
742.Pp
743The macro
744.Nm STAILQ_INSERT_TAIL
745inserts the new element
746.Fa elm
747at the end of the tail queue.
748.Pp
749The macro
750.Nm STAILQ_INSERT_AFTER
751inserts the new element
752.Fa elm
753after the element
754.Fa listelm .
755.Pp
756The macro
757.Nm STAILQ_LAST
758returns the last item on the tail queue.
759If the tail queue is empty the return value is
760.Dv NULL .
761.Pp
762The macro
763.Nm STAILQ_NEXT
764returns the next item on the tail queue, or NULL this item is the last.
765.Pp
766The macro
767.Nm STAILQ_REMOVE_AFTER
768removes the element after
769.Fa elm
770from the tail queue.
771Unlike
772.Fa STAILQ_REMOVE ,
773this macro does not traverse the entire tail queue.
774.Pp
775The macro
776.Nm STAILQ_REMOVE_HEAD
777removes the element at the head of the tail queue.
778For optimum efficiency,
779elements being removed from the head of the tail queue should
780use this macro explicitly rather than the generic
781.Fa STAILQ_REMOVE
782macro.
783.Pp
784The macro
785.Nm STAILQ_REMOVE
786removes the element
787.Fa elm
788from the tail queue.
789Use of this macro should be avoided as it traverses the entire list.
790A doubly-linked tail queue should be used if this macro is needed in
791high-usage code paths or to operate on long tail queues.
792.Pp
793The macro
794.Nm STAILQ_SPLIT_AFTER
795splits the tail queue referenced by
796.Fa head ,
797making
798.Fa rest
799reference the tail queue formed by elements after
800.Fa elm
801in
802.Fa head .
803.Pp
804The macro
805.Nm STAILQ_SWAP
806swaps the contents of
807.Fa head1
808and
809.Fa head2 .
810.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
811.Bd -literal
812STAILQ_HEAD(stailhead, entry) head =
813    STAILQ_HEAD_INITIALIZER(head);
814struct stailhead *headp;		/* Singly-linked tail queue head. */
815struct entry {
816	...
817	STAILQ_ENTRY(entry) entries;	/* Tail queue. */
818	...
819} *n1, *n2, *n3, *np;
820
821STAILQ_INIT(&head);			/* Initialize the queue. */
822
823n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
824STAILQ_INSERT_HEAD(&head, n1, entries);
825
826n1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
827STAILQ_INSERT_TAIL(&head, n1, entries);
828
829n2 = malloc(sizeof(struct entry));	/* Insert after. */
830STAILQ_INSERT_AFTER(&head, n1, n2, entries);
831					/* Deletion. */
832STAILQ_REMOVE(&head, n2, entry, entries);
833free(n2);
834					/* Deletion from the head. */
835n3 = STAILQ_FIRST(&head);
836STAILQ_REMOVE_HEAD(&head, entries);
837free(n3);
838					/* Forward traversal. */
839STAILQ_FOREACH(np, &head, entries)
840	np-> ...
841					/* Safe forward traversal. */
842STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
843	np->do_stuff();
844	...
845	STAILQ_REMOVE(&head, np, entry, entries);
846	free(np);
847}
848					/* TailQ Deletion. */
849while (!STAILQ_EMPTY(&head)) {
850	n1 = STAILQ_FIRST(&head);
851	STAILQ_REMOVE_HEAD(&head, entries);
852	free(n1);
853}
854					/* Faster TailQ Deletion. */
855n1 = STAILQ_FIRST(&head);
856while (n1 != NULL) {
857	n2 = STAILQ_NEXT(n1, entries);
858	free(n1);
859	n1 = n2;
860}
861STAILQ_INIT(&head);
862.Ed
863.Sh LISTS
864A list is headed by a structure defined by the
865.Nm LIST_HEAD
866macro.
867This structure contains a single pointer to the first element
868on the list.
869The elements are doubly linked so that an arbitrary element can be
870removed without traversing the list.
871New elements can be added to the list after an existing element,
872before an existing element, or at the head of the list.
873A
874.Fa LIST_HEAD
875structure is declared as follows:
876.Bd -literal -offset indent
877LIST_HEAD(HEADNAME, TYPE) head;
878.Ed
879.Pp
880where
881.Fa HEADNAME
882is the name of the structure to be defined, and
883.Fa TYPE
884is the type of the elements to be linked into the list.
885A pointer to the head of the list can later be declared as:
886.Bd -literal -offset indent
887struct HEADNAME *headp;
888.Ed
889.Pp
890(The names
891.Li head
892and
893.Li headp
894are user selectable.)
895.Pp
896The macro
897.Nm LIST_HEAD_INITIALIZER
898evaluates to an initializer for the list
899.Fa head .
900.Pp
901The macro
902.Nm LIST_CONCAT
903concatenates the list headed by
904.Fa head2
905onto the end of the one headed by
906.Fa head1
907removing all entries from the former.
908Use of this macro should be avoided as it traverses the entirety of the
909.Fa head1
910list.
911A tail queue should be used if this macro is needed in
912high-usage code paths or to operate on long lists.
913.Pp
914The macro
915.Nm LIST_EMPTY
916evaluates to true if there are no elements in the list.
917The
918.Nm LIST_EMPTY_ATOMIC
919variant has the same behavior, but can be safely used in contexts where it is
920possible that a different thread is concurrently updating the list.
921.Pp
922The macro
923.Nm LIST_ENTRY
924declares a structure that connects the elements in
925the list.
926.Pp
927The macro
928.Nm LIST_FIRST
929returns the first element in the list or NULL if the list
930is empty.
931.Pp
932The macro
933.Nm LIST_FOREACH
934traverses the list referenced by
935.Fa head
936in the forward direction, assigning each element in turn to
937.Fa var .
938.Pp
939The macro
940.Nm LIST_FOREACH_FROM
941behaves identically to
942.Nm LIST_FOREACH
943when
944.Fa var
945is NULL, else it treats
946.Fa var
947as a previously found LIST element and begins the loop at
948.Fa var
949instead of the first element in the LIST referenced by
950.Fa head .
951.Pp
952The macro
953.Nm LIST_FOREACH_SAFE
954traverses the list referenced by
955.Fa head
956in the forward direction, assigning each element in turn to
957.Fa var .
958However, unlike
959.Fn LIST_FOREACH
960here it is permitted to both remove
961.Fa var
962as well as free it from within the loop safely without interfering with the
963traversal.
964.Pp
965The macro
966.Nm LIST_FOREACH_FROM_SAFE
967behaves identically to
968.Nm LIST_FOREACH_SAFE
969when
970.Fa var
971is NULL, else it treats
972.Fa var
973as a previously found LIST element and begins the loop at
974.Fa var
975instead of the first element in the LIST referenced by
976.Fa head .
977.Pp
978The macro
979.Nm LIST_INIT
980initializes the list referenced by
981.Fa head .
982.Pp
983The macro
984.Nm LIST_INSERT_HEAD
985inserts the new element
986.Fa elm
987at the head of the list.
988.Pp
989The macro
990.Nm LIST_INSERT_AFTER
991inserts the new element
992.Fa elm
993after the element
994.Fa listelm .
995.Pp
996The macro
997.Nm LIST_INSERT_BEFORE
998inserts the new element
999.Fa elm
1000before the element
1001.Fa listelm .
1002.Pp
1003The macro
1004.Nm LIST_NEXT
1005returns the next element in the list, or NULL if this is the last.
1006.Pp
1007The macro
1008.Nm LIST_PREV
1009returns the previous element in the list, or NULL if this is the first.
1010List
1011.Fa head
1012must contain element
1013.Fa elm .
1014.Pp
1015The macro
1016.Nm LIST_REMOVE
1017removes the element
1018.Fa elm
1019from the list.
1020.Pp
1021The macro
1022.Fn LIST_REPLACE
1023replaces the element
1024.Fa elm
1025with
1026.Fa new
1027in the list.
1028The element
1029.Fa new
1030must not already be on a list.
1031.Pp
1032The macro
1033.Nm LIST_SPLIT_AFTER
1034splits the list referenced by
1035.Fa head ,
1036making
1037.Fa rest
1038reference the list formed by elements after
1039.Fa elm
1040in
1041.Fa head .
1042.Pp
1043The macro
1044.Nm LIST_SWAP
1045swaps the contents of
1046.Fa head1
1047and
1048.Fa head2 .
1049.Sh LIST EXAMPLE
1050.Bd -literal
1051LIST_HEAD(listhead, entry) head =
1052    LIST_HEAD_INITIALIZER(head);
1053struct listhead *headp;			/* List head. */
1054struct entry {
1055	...
1056	LIST_ENTRY(entry) entries;	/* List. */
1057	...
1058} *n1, *n2, *n3, *np, *np_temp;
1059
1060LIST_INIT(&head);			/* Initialize the list. */
1061
1062n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
1063LIST_INSERT_HEAD(&head, n1, entries);
1064
1065n2 = malloc(sizeof(struct entry));	/* Insert after. */
1066LIST_INSERT_AFTER(n1, n2, entries);
1067
1068n3 = malloc(sizeof(struct entry));	/* Insert before. */
1069LIST_INSERT_BEFORE(n2, n3, entries);
1070
1071LIST_REMOVE(n2, entries);		/* Deletion. */
1072free(n2);
1073					/* Forward traversal. */
1074LIST_FOREACH(np, &head, entries)
1075	np-> ...
1076
1077					/* Safe forward traversal. */
1078LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
1079	np->do_stuff();
1080	...
1081	LIST_REMOVE(np, entries);
1082	free(np);
1083}
1084
1085while (!LIST_EMPTY(&head)) {		/* List Deletion. */
1086	n1 = LIST_FIRST(&head);
1087	LIST_REMOVE(n1, entries);
1088	free(n1);
1089}
1090
1091n1 = LIST_FIRST(&head);			/* Faster List Deletion. */
1092while (n1 != NULL) {
1093	n2 = LIST_NEXT(n1, entries);
1094	free(n1);
1095	n1 = n2;
1096}
1097LIST_INIT(&head);
1098.Ed
1099.Sh TAIL QUEUES
1100A tail queue is headed by a structure defined by the
1101.Nm TAILQ_HEAD
1102macro.
1103This structure contains a pair of pointers,
1104one to the first element in the tail queue and the other to
1105the last element in the tail queue.
1106The elements are doubly linked so that an arbitrary element can be
1107removed without traversing the tail queue.
1108New elements can be added to the tail queue after an existing element,
1109before an existing element, at the head of the tail queue,
1110or at the end of the tail queue.
1111A
1112.Fa TAILQ_HEAD
1113structure is declared as follows:
1114.Bd -literal -offset indent
1115TAILQ_HEAD(HEADNAME, TYPE) head;
1116.Ed
1117.Pp
1118where
1119.Li HEADNAME
1120is the name of the structure to be defined, and
1121.Li TYPE
1122is the type of the elements to be linked into the tail queue.
1123A pointer to the head of the tail queue can later be declared as:
1124.Bd -literal -offset indent
1125struct HEADNAME *headp;
1126.Ed
1127.Pp
1128(The names
1129.Li head
1130and
1131.Li headp
1132are user selectable.)
1133.Pp
1134The macro
1135.Nm TAILQ_HEAD_INITIALIZER
1136evaluates to an initializer for the tail queue
1137.Fa head .
1138.Pp
1139The macro
1140.Nm TAILQ_CONCAT
1141concatenates the tail queue headed by
1142.Fa head2
1143onto the end of the one headed by
1144.Fa head1
1145removing all entries from the former.
1146.Pp
1147The macro
1148.Nm TAILQ_EMPTY
1149evaluates to true if there are no items on the tail queue.
1150The
1151.Nm TAILQ_EMPTY_ATOMIC
1152variant has the same behavior, but can be safely used in contexts where it is
1153possible that a different thread is concurrently updating the queue.
1154.Pp
1155The macro
1156.Nm TAILQ_ENTRY
1157declares a structure that connects the elements in
1158the tail queue.
1159.Pp
1160The macro
1161.Nm TAILQ_FIRST
1162returns the first item on the tail queue or NULL if the tail queue
1163is empty.
1164.Pp
1165The macro
1166.Nm TAILQ_FOREACH
1167traverses the tail queue referenced by
1168.Fa head
1169in the forward direction, assigning each element in turn to
1170.Fa var .
1171.Fa var
1172is set to
1173.Dv NULL
1174if the loop completes normally, or if there were no elements.
1175.Pp
1176The macro
1177.Nm TAILQ_FOREACH_FROM
1178behaves identically to
1179.Nm TAILQ_FOREACH
1180when
1181.Fa var
1182is NULL, else it treats
1183.Fa var
1184as a previously found TAILQ element and begins the loop at
1185.Fa var
1186instead of the first element in the TAILQ referenced by
1187.Fa head .
1188.Pp
1189The macro
1190.Nm TAILQ_FOREACH_REVERSE
1191traverses the tail queue referenced by
1192.Fa head
1193in the reverse direction, assigning each element in turn to
1194.Fa var .
1195.Pp
1196The macro
1197.Nm TAILQ_FOREACH_REVERSE_FROM
1198behaves identically to
1199.Nm TAILQ_FOREACH_REVERSE
1200when
1201.Fa var
1202is NULL, else it treats
1203.Fa var
1204as a previously found TAILQ element and begins the reverse loop at
1205.Fa var
1206instead of the last element in the TAILQ referenced by
1207.Fa head .
1208.Pp
1209The macros
1210.Nm TAILQ_FOREACH_SAFE
1211and
1212.Nm TAILQ_FOREACH_REVERSE_SAFE
1213traverse the list referenced by
1214.Fa head
1215in the forward or reverse direction respectively,
1216assigning each element in turn to
1217.Fa var .
1218However, unlike their unsafe counterparts,
1219.Nm TAILQ_FOREACH
1220and
1221.Nm TAILQ_FOREACH_REVERSE
1222permit to both remove
1223.Fa var
1224as well as free it from within the loop safely without interfering with the
1225traversal.
1226.Pp
1227The macro
1228.Nm TAILQ_FOREACH_FROM_SAFE
1229behaves identically to
1230.Nm TAILQ_FOREACH_SAFE
1231when
1232.Fa var
1233is NULL, else it treats
1234.Fa var
1235as a previously found TAILQ element and begins the loop at
1236.Fa var
1237instead of the first element in the TAILQ referenced by
1238.Fa head .
1239.Pp
1240The macro
1241.Nm TAILQ_FOREACH_REVERSE_FROM_SAFE
1242behaves identically to
1243.Nm TAILQ_FOREACH_REVERSE_SAFE
1244when
1245.Fa var
1246is NULL, else it treats
1247.Fa var
1248as a previously found TAILQ element and begins the reverse loop at
1249.Fa var
1250instead of the last element in the TAILQ referenced by
1251.Fa head .
1252.Pp
1253The macro
1254.Nm TAILQ_INIT
1255initializes the tail queue referenced by
1256.Fa head .
1257.Pp
1258The macro
1259.Nm TAILQ_INSERT_HEAD
1260inserts the new element
1261.Fa elm
1262at the head of the tail queue.
1263.Pp
1264The macro
1265.Nm TAILQ_INSERT_TAIL
1266inserts the new element
1267.Fa elm
1268at the end of the tail queue.
1269.Pp
1270The macro
1271.Nm TAILQ_INSERT_AFTER
1272inserts the new element
1273.Fa elm
1274after the element
1275.Fa listelm .
1276.Pp
1277The macro
1278.Nm TAILQ_INSERT_BEFORE
1279inserts the new element
1280.Fa elm
1281before the element
1282.Fa listelm .
1283.Pp
1284The macro
1285.Nm TAILQ_LAST
1286returns the last item on the tail queue.
1287If the tail queue is empty the return value is
1288.Dv NULL .
1289.Pp
1290The macro
1291.Nm TAILQ_NEXT
1292returns the next item on the tail queue, or NULL if this item is the last.
1293.Pp
1294The macro
1295.Nm TAILQ_PREV
1296returns the previous item on the tail queue, or NULL if this item
1297is the first.
1298.Pp
1299The macro
1300.Nm TAILQ_REMOVE
1301removes the element
1302.Fa elm
1303from the tail queue.
1304.Pp
1305The macro
1306.Fn TAILQ_REPLACE
1307replaces the element
1308.Fa elm
1309with
1310.Fa new
1311in the tail queue.
1312The element
1313.Fa new
1314must not already be on a list.
1315.Pp
1316The macro
1317.Nm TAILQ_SPLIT_AFTER
1318splits the tail queue referenced by
1319.Fa head ,
1320making
1321.Fa rest
1322reference the tail queue formed by elements after
1323.Fa elm
1324in
1325.Fa head .
1326.Pp
1327The macro
1328.Nm TAILQ_SWAP
1329swaps the contents of
1330.Fa head1
1331and
1332.Fa head2 .
1333.Sh TAIL QUEUE EXAMPLE
1334.Bd -literal
1335TAILQ_HEAD(tailhead, entry) head =
1336    TAILQ_HEAD_INITIALIZER(head);
1337struct tailhead *headp;			/* Tail queue head. */
1338struct entry {
1339	...
1340	TAILQ_ENTRY(entry) entries;	/* Tail queue. */
1341	...
1342} *n1, *n2, *n3, *n4, *np;
1343
1344TAILQ_INIT(&head);			/* Initialize the queue. */
1345
1346n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
1347TAILQ_INSERT_HEAD(&head, n1, entries);
1348
1349n1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
1350TAILQ_INSERT_TAIL(&head, n1, entries);
1351
1352n2 = malloc(sizeof(struct entry));	/* Insert after. */
1353TAILQ_INSERT_AFTER(&head, n1, n2, entries);
1354
1355n3 = malloc(sizeof(struct entry));	/* Insert before. */
1356TAILQ_INSERT_BEFORE(n2, n3, entries);
1357
1358TAILQ_REMOVE(&head, n2, entries);	/* Deletion. */
1359free(n2);
1360
1361n4 = malloc(sizeof(struct entry));	/* Replacement. */
1362TAILQ_REPLACE(&head, n3, n4, entries);
1363free(n3);
1364					/* Forward traversal. */
1365TAILQ_FOREACH(np, &head, entries)
1366	np-> ...
1367					/* Safe forward traversal. */
1368TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
1369	np->do_stuff();
1370	...
1371	TAILQ_REMOVE(&head, np, entries);
1372	free(np);
1373}
1374					/* Reverse traversal. */
1375TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
1376	np-> ...
1377					/* TailQ Deletion. */
1378while (!TAILQ_EMPTY(&head)) {
1379	n1 = TAILQ_FIRST(&head);
1380	TAILQ_REMOVE(&head, n1, entries);
1381	free(n1);
1382}
1383					/* Faster TailQ Deletion. */
1384n1 = TAILQ_FIRST(&head);
1385while (n1 != NULL) {
1386	n2 = TAILQ_NEXT(n1, entries);
1387	free(n1);
1388	n1 = n2;
1389}
1390TAILQ_INIT(&head);
1391.Ed
1392.Sh DIAGNOSTICS
1393.Nm queue(3)
1394provides several diagnostic and debugging facilities.
1395.Pp
1396Check code that performs basic integrity and API conformance checks is
1397automatically inserted when using queue macros in the kernel if compiling it
1398with
1399.Va INVARIANTS .
1400One can request insertion or elision of check code by respectively defining one
1401of the macros
1402.Va QUEUE_MACRO_DEBUG_ASSERTIONS
1403or
1404.Va QUEUE_MACRO_NO_DEBUG_ASSERTIONS
1405before first inclusion of
1406.In sys/queue.h .
1407When check code encounters an anomaly, it panics the kernel or aborts the
1408program.
1409To this end, in the kernel or in
1410.Va _STANDALONE
1411builds, it by default calls
1412.Fn panic ,
1413while in userland builds it prints the diagnostic message on
1414.Dv stderr
1415and then calls
1416.Fn abort .
1417These behaviors can be overriden by defining a custom
1418.Fn QMD_PANIC
1419macro before first inclusion of
1420.In sys/queue.h .
1421The diagnostic messages automatically include the source file, line and function
1422where the failing check occured.
1423This behavior can be overriden by defining a custom
1424.Fn QMD_ASSERT
1425macro before first inclusion of
1426.In sys/queue.h .
1427.Pp
1428The
1429.Fn SLIST_REMOVE_PREVPTR
1430macro is available to aid debugging:
1431.Bl -hang -offset indent
1432.It Fn SLIST_REMOVE_PREVPTR "TYPE **prev" "TYPE *elm" "SLIST_ENTRY NAME"
1433.Pp
1434Removes element
1435.Fa elm ,
1436which must directly follow the element whose
1437.Va &SLIST_NEXT()
1438is
1439.Fa prev ,
1440from the list.
1441This macro may insert, under conditions detailed above, check code that
1442validates that
1443.Fa elm
1444indeed follows
1445.Fa prev
1446in the list
1447.Po
1448through the
1449.Fn QMD_SLIST_CHECK_PREVPTR
1450macro
1451.Pc .
1452.El
1453.Pp
1454When debugging, it can be useful to trace queue changes.
1455To enable tracing, define the macro
1456.Va QUEUE_MACRO_DEBUG_TRACE .
1457Note that, at the moment, only macros for regular tail queues have been
1458instrumented.
1459.Pp
1460It can also be useful to trash pointers that have been unlinked from a queue,
1461to detect use after removal.
1462To enable pointer trashing, define the macro
1463.Va QUEUE_MACRO_DEBUG_TRASH
1464at compile time.
1465Note that, at the moment, only a limited number of macros have been
1466instrumented.
1467The macro
1468.Fn QMD_IS_TRASHED "void *ptr"
1469returns true if
1470.Fa ptr
1471has been trashed by the
1472.Va QUEUE_MACRO_DEBUG_TRASH
1473option.
1474.Sh SEE ALSO
1475.Xr arb 3 ,
1476.Xr tree 3
1477.Sh HISTORY
1478The
1479.Nm queue
1480functions first appeared in
1481.Bx 4.4 .
1482