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