34.\"
35.Dd January 24, 1994
36.Dt QUEUE 3
37.Os
38.Sh NAME
39.Nm SLIST_EMPTY ,
40.Nm SLIST_ENTRY ,
41.Nm SLIST_FIRST ,
42.Nm SLIST_FOREACH ,
43.Nm SLIST_FOREACH_SAFE ,
44.Nm SLIST_HEAD ,
45.Nm SLIST_HEAD_INITIALIZER ,
46.Nm SLIST_INIT ,
47.Nm SLIST_INSERT_AFTER ,
48.Nm SLIST_INSERT_HEAD ,
49.Nm SLIST_NEXT ,
50.Nm SLIST_REMOVE_HEAD ,
51.Nm SLIST_REMOVE ,
52.Nm STAILQ_CONCAT ,
53.Nm STAILQ_EMPTY ,
54.Nm STAILQ_ENTRY ,
55.Nm STAILQ_FIRST ,
56.Nm STAILQ_FOREACH ,
57.Nm STAILQ_FOREACH_SAFE ,
58.Nm STAILQ_HEAD ,
59.Nm STAILQ_HEAD_INITIALIZER ,
60.Nm STAILQ_INIT ,
61.Nm STAILQ_INSERT_AFTER ,
62.Nm STAILQ_INSERT_HEAD ,
63.Nm STAILQ_INSERT_TAIL ,
64.Nm STAILQ_LAST ,
65.Nm STAILQ_NEXT ,
66.Nm STAILQ_REMOVE_HEAD ,
67.Nm STAILQ_REMOVE ,
68.Nm LIST_EMPTY ,
69.Nm LIST_ENTRY ,
70.Nm LIST_FIRST ,
71.Nm LIST_FOREACH ,
72.Nm LIST_FOREACH_SAFE ,
73.Nm LIST_HEAD ,
74.Nm LIST_HEAD_INITIALIZER ,
75.Nm LIST_INIT ,
76.Nm LIST_INSERT_AFTER ,
77.Nm LIST_INSERT_BEFORE ,
78.Nm LIST_INSERT_HEAD ,
79.Nm LIST_NEXT ,
80.Nm LIST_REMOVE ,
81.Nm TAILQ_CONCAT ,
82.Nm TAILQ_EMPTY ,
83.Nm TAILQ_ENTRY ,
84.Nm TAILQ_FIRST ,
85.Nm TAILQ_FOREACH ,
86.Nm TAILQ_FOREACH_SAFE ,
87.Nm TAILQ_FOREACH_REVERSE ,
88.Nm TAILQ_FOREACH_REVERSE_SAFE ,
89.Nm TAILQ_HEAD ,
90.Nm TAILQ_HEAD_INITIALIZER ,
91.Nm TAILQ_INIT ,
92.Nm TAILQ_INSERT_AFTER ,
93.Nm TAILQ_INSERT_BEFORE ,
94.Nm TAILQ_INSERT_HEAD ,
95.Nm TAILQ_INSERT_TAIL ,
96.Nm TAILQ_LAST ,
97.Nm TAILQ_NEXT ,
98.Nm TAILQ_PREV ,
99.Nm TAILQ_REMOVE
100.Nd implementations of singly-linked lists, singly-linked tail queues,
101lists and tail queues
102.Sh SYNOPSIS
103.In sys/queue.h
104.\"
105.Fn SLIST_EMPTY "SLIST_HEAD *head"
106.Fn SLIST_ENTRY "TYPE"
107.Fn SLIST_FIRST "SLIST_HEAD *head"
108.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
109.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
110.Fn SLIST_HEAD "HEADNAME" "TYPE"
111.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
112.Fn SLIST_INIT "SLIST_HEAD *head"
113.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
114.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
115.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
116.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
117.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
118.\"
119.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
120.Fn STAILQ_EMPTY "STAILQ_HEAD *head"
121.Fn STAILQ_ENTRY "TYPE"
122.Fn STAILQ_FIRST "STAILQ_HEAD *head"
123.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
124.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
125.Fn STAILQ_HEAD "HEADNAME" "TYPE"
126.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
127.Fn STAILQ_INIT "STAILQ_HEAD *head"
128.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
129.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
130.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
131.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
132.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
133.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
134.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
135.\"
136.Fn LIST_EMPTY "LIST_HEAD *head"
137.Fn LIST_ENTRY "TYPE"
138.Fn LIST_FIRST "LIST_HEAD *head"
139.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
140.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
141.Fn LIST_HEAD "HEADNAME" "TYPE"
142.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
143.Fn LIST_INIT "LIST_HEAD *head"
144.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
145.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
146.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
147.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
148.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
149.\"
150.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
151.Fn TAILQ_EMPTY "TAILQ_HEAD *head"
152.Fn TAILQ_ENTRY "TYPE"
153.Fn TAILQ_FIRST "TAILQ_HEAD *head"
154.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
155.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
156.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
157.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
158.Fn TAILQ_HEAD "HEADNAME" "TYPE"
159.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
160.Fn TAILQ_INIT "TAILQ_HEAD *head"
161.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
162.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
163.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
164.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
165.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
166.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
167.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
168.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
169.\"
170.Sh DESCRIPTION
171These macros define and operate on four types of data structures:
172singly-linked lists, singly-linked tail queues, lists, and tail queues.
173All four structures support the following functionality:
174.Bl -enum -compact -offset indent
175.It
176Insertion of a new entry at the head of the list.
177.It
178Insertion of a new entry after any element in the list.
179.It
180O(1) removal of an entry from the head of the list.
181.It
182O(n) removal of any entry in the list.
183.It
184Forward traversal through the list.
185.El
186.Pp
187Singly-linked lists are the simplest of the five data structures
188and support only the above functionality.
189Singly-linked lists are ideal for applications with large datasets
190and few or no removals,
191or for implementing a LIFO queue.
192.Pp
193Singly-linked tail queues add the following functionality:
194.Bl -enum -compact -offset indent
195.It
196Entries can be added at the end of a list.
197.It
198They may be concatenated.
199.El
200However:
201.Bl -enum -compact -offset indent
202.It
203All list insertions must specify the head of the list.
204.It
205Each head entry requires two pointers rather than one.
206.It
207Code size is about 15% greater and operations run about 20% slower
208than singly-linked lists.
209.El
210.Pp
211Singly-linked tailqs are ideal for applications with large datasets and
212few or no removals,
213or for implementing a FIFO queue.
214.Pp
215All doubly linked types of data structures (lists and tail queues)
216additionally allow:
217.Bl -enum -compact -offset indent
218.It
219Insertion of a new entry before any element in the list.
220.It
221O(1) removal of any entry in the list.
222.El
223However:
224.Bl -enum -compact -offset indent
225.It
226Each elements requires two pointers rather than one.
227.It
228Code size and execution time of operations (except for removal) is about
229twice that of the singly-linked data-structures.
230.El
231.Pp
232Linked lists are the simplest of the doubly linked data structures and support
233only the above functionality over singly-linked lists.
234.Pp
235Tail queues add the following functionality:
236.Bl -enum -compact -offset indent
237.It
238Entries can be added at the end of a list.
239.It
240They may be traversed backwards, from tail to head.
241.It
242They may be concatenated.
243.El
244However:
245.Bl -enum -compact -offset indent
246.It
247All list insertions and removals must specify the head of the list.
248.It
249Each head entry requires two pointers rather than one.
250.It
251Code size is about 15% greater and operations run about 20% slower
252than singly-linked lists.
253.El
254.Pp
255In the macro definitions,
256.Fa TYPE
257is the name of a user defined structure,
258that must contain a field of type
259.Li SLIST_ENTRY ,
260.Li STAILQ_ENTRY ,
261.Li LIST_ENTRY ,
262or
263.Li TAILQ_ENTRY ,
264named
265.Fa NAME .
266The argument
267.Fa HEADNAME
268is the name of a user defined structure that must be declared
269using the macros
270.Li SLIST_HEAD ,
271.Li STAILQ_HEAD ,
272.Li LIST_HEAD ,
273or
274.Li TAILQ_HEAD .
275See the examples below for further explanation of how these
276macros are used.
277.Sh SINGLY-LINKED LISTS
278A singly-linked list is headed by a structure defined by the
279.Nm SLIST_HEAD
280macro.
281This structure contains a single pointer to the first element
282on the list.
283The elements are singly linked for minimum space and pointer manipulation
284overhead at the expense of O(n) removal for arbitrary elements.
285New elements can be added to the list after an existing element or
286at the head of the list.
287An
288.Fa SLIST_HEAD
289structure is declared as follows:
290.Bd -literal -offset indent
291SLIST_HEAD(HEADNAME, TYPE) head;
292.Ed
293.Pp
294where
295.Fa HEADNAME
296is the name of the structure to be defined, and
297.Fa TYPE
298is the type of the elements to be linked into the list.
299A pointer to the head of the list can later be declared as:
300.Bd -literal -offset indent
301struct HEADNAME *headp;
302.Ed
303.Pp
304(The names
305.Li head
306and
307.Li headp
308are user selectable.)
309.Pp
310The macro
311.Nm SLIST_HEAD_INITIALIZER
312evaluates to an initializer for the list
313.Fa head .
314.Pp
315The macro
316.Nm SLIST_EMPTY
317evaluates to true if there are no elements in the list.
318.Pp
319The macro
320.Nm SLIST_ENTRY
321declares a structure that connects the elements in
322the list.
323.Pp
324The macro
325.Nm SLIST_FIRST
326returns the first element in the list or NULL if the list is empty.
327.Pp
328The macro
329.Nm SLIST_FOREACH
330traverses the list referenced by
331.Fa head
332in the forward direction, assigning each element in
333turn to
334.Fa var .
335.Pp
336The macro
337.Nm SLIST_FOREACH_SAFE
338traverses the list referenced by
339.Fa head
340in the forward direction, assigning each element in
341turn to
342.Fa var .
343However, unlike
344.Fn SLIST_FOREACH
345here it is permitted to both remove
346.Fa var
347as well as free it from within the loop safely without interfering with the
348traversal.
349.Pp
350The macro
351.Nm SLIST_INIT
352initializes the list referenced by
353.Fa head .
354.Pp
355The macro
356.Nm SLIST_INSERT_HEAD
357inserts the new element
358.Fa elm
359at the head of the list.
360.Pp
361The macro
362.Nm SLIST_INSERT_AFTER
363inserts the new element
364.Fa elm
365after the element
366.Fa listelm .
367.Pp
368The macro
369.Nm SLIST_NEXT
370returns the next element in the list.
371.Pp
372The macro
373.Nm SLIST_REMOVE_HEAD
374removes the element
375.Fa elm
376from the head of the list.
377For optimum efficiency,
378elements being removed from the head of the list should explicitly use
379this macro instead of the generic
380.Fa SLIST_REMOVE
381macro.
382.Pp
383The macro
384.Nm SLIST_REMOVE
385removes the element
386.Fa elm
387from the list.
388.Sh SINGLY-LINKED LIST EXAMPLE
389.Bd -literal
390SLIST_HEAD(slisthead, entry) head =
391 SLIST_HEAD_INITIALIZER(head);
392struct slisthead *headp; /* Singly-linked List head. */
393struct entry {
394 ...
395 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
396 ...
397} *n1, *n2, *n3, *np;
398
399SLIST_INIT(&head); /* Initialize the list. */
400
401n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
402SLIST_INSERT_HEAD(&head, n1, entries);
403
404n2 = malloc(sizeof(struct entry)); /* Insert after. */
405SLIST_INSERT_AFTER(n1, n2, entries);
406
407SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
408free(n2);
409
410n3 = SLIST_FIRST(&head);
411SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
412free(n3);
413 /* Forward traversal. */
414SLIST_FOREACH(np, &head, entries)
415 np-> ...
416 /* Safe forward traversal. */
417SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
418 np->do_stuff();
419 ...
420 SLIST_REMOVE(&head, np, entry, entries);
421 free(np);
422}
423
424while (!SLIST_EMPTY(&head)) { /* List Deletion. */
425 n1 = SLIST_FIRST(&head);
426 SLIST_REMOVE_HEAD(&head, entries);
427 free(n1);
428}
429.Ed
430.Sh SINGLY-LINKED TAIL QUEUES
431A singly-linked tail queue is headed by a structure defined by the
432.Nm STAILQ_HEAD
433macro.
434This structure contains a pair of pointers,
435one to the first element in the tail queue and the other to
436the last element in the tail queue.
437The elements are singly linked for minimum space and pointer
438manipulation overhead at the expense of O(n) removal for arbitrary
439elements.
440New elements can be added to the tail queue after an existing element,
441at the head of the tail queue, or at the end of the tail queue.
442A
443.Fa STAILQ_HEAD
444structure is declared as follows:
445.Bd -literal -offset indent
446STAILQ_HEAD(HEADNAME, TYPE) head;
447.Ed
448.Pp
449where
450.Li HEADNAME
451is the name of the structure to be defined, and
452.Li TYPE
453is the type of the elements to be linked into the tail queue.
454A pointer to the head of the tail queue can later be declared as:
455.Bd -literal -offset indent
456struct HEADNAME *headp;
457.Ed
458.Pp
459(The names
460.Li head
461and
462.Li headp
463are user selectable.)
464.Pp
465The macro
466.Nm STAILQ_HEAD_INITIALIZER
467evaluates to an initializer for the tail queue
468.Fa head .
469.Pp
470The macro
471.Nm STAILQ_CONCAT
472concatenates the tail queue headed by
473.Fa head2
474onto the end of the one headed by
475.Fa head1
476removing all entries from the former.
477.Pp
478The macro
479.Nm STAILQ_EMPTY
480evaluates to true if there are no items on the tail queue.
481.Pp
482The macro
483.Nm STAILQ_ENTRY
484declares a structure that connects the elements in
485the tail queue.
486.Pp
487The macro
488.Nm STAILQ_FIRST
489returns the first item on the tail queue or NULL if the tail queue
490is empty.
491.Pp
492The macro
493.Nm STAILQ_FOREACH
494traverses the tail queue referenced by
495.Fa head
496in the forward direction, assigning each element
497in turn to
498.Fa var .
499.Pp
500The macro
501.Nm STAILQ_FOREACH_SAFE
502traverses the tail queue referenced by
503.Fa head
504in the forward direction, assigning each element
505in turn to
506.Fa var .
507However, unlike
508.Fn STAILQ_FOREACH
509here it is permitted to both remove
510.Fa var
511as well as free it from within the loop safely without interfering with the
512traversal.
513.Pp
514The macro
515.Nm STAILQ_INIT
516initializes the tail queue referenced by
517.Fa head .
518.Pp
519The macro
520.Nm STAILQ_INSERT_HEAD
521inserts the new element
522.Fa elm
523at the head of the tail queue.
524.Pp
525The macro
526.Nm STAILQ_INSERT_TAIL
527inserts the new element
528.Fa elm
529at the end of the tail queue.
530.Pp
531The macro
532.Nm STAILQ_INSERT_AFTER
533inserts the new element
534.Fa elm
535after the element
536.Fa listelm .
537.Pp
538The macro
539.Nm STAILQ_LAST
540returns the last item on the tail queue.
541If the tail queue is empty the return value is undefined.
542.Pp
543The macro
544.Nm STAILQ_NEXT
545returns the next item on the tail queue, or NULL this item is the last.
546.Pp
547The macro
548.Nm STAILQ_REMOVE_HEAD
549removes the element at the head of the tail queue.
550For optimum efficiency,
551elements being removed from the head of the tail queue should
552use this macro explicitly rather than the generic
553.Fa STAILQ_REMOVE
554macro.
555.Pp
556The macro
557.Nm STAILQ_REMOVE
558removes the element
559.Fa elm
560from the tail queue.
561.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
562.Bd -literal
563STAILQ_HEAD(stailhead, entry) head =
564 STAILQ_HEAD_INITIALIZER(head);
565struct stailhead *headp; /* Singly-linked tail queue head. */
566struct entry {
567 ...
568 STAILQ_ENTRY(entry) entries; /* Tail queue. */
569 ...
570} *n1, *n2, *n3, *np;
571
572STAILQ_INIT(&head); /* Initialize the queue. */
573
574n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
575STAILQ_INSERT_HEAD(&head, n1, entries);
576
577n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
578STAILQ_INSERT_TAIL(&head, n1, entries);
579
580n2 = malloc(sizeof(struct entry)); /* Insert after. */
581STAILQ_INSERT_AFTER(&head, n1, n2, entries);
582 /* Deletion. */
583STAILQ_REMOVE(&head, n2, entry, entries);
584free(n2);
585 /* Deletion from the head. */
586n3 = STAILQ_FIRST(&head);
587STAILQ_REMOVE_HEAD(&head, entries);
588free(n3);
589 /* Forward traversal. */
590STAILQ_FOREACH(np, &head, entries)
591 np-> ...
592 /* Safe forward traversal. */
593STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
594 np->do_stuff();
595 ...
596 STAILQ_REMOVE(&head, np, entry, entries);
597 free(np);
598}
599 /* TailQ Deletion. */
600while (!STAILQ_EMPTY(&head)) {
601 n1 = STAILQ_FIRST(&head);
602 STAILQ_REMOVE_HEAD(&head, entries);
603 free(n1);
604}
605 /* Faster TailQ Deletion. */
606n1 = STAILQ_FIRST(&head);
607while (n1 != NULL) {
608 n2 = STAILQ_NEXT(n1, entries);
609 free(n1);
610 n1 = n2;
611}
612STAILQ_INIT(&head);
613.Ed
614.Sh LISTS
615A list is headed by a structure defined by the
616.Nm LIST_HEAD
617macro.
618This structure contains a single pointer to the first element
619on the list.
620The elements are doubly linked so that an arbitrary element can be
621removed without traversing the list.
622New elements can be added to the list after an existing element,
623before an existing element, or at the head of the list.
624A
625.Fa LIST_HEAD
626structure is declared as follows:
627.Bd -literal -offset indent
628LIST_HEAD(HEADNAME, TYPE) head;
629.Ed
630.Pp
631where
632.Fa HEADNAME
633is the name of the structure to be defined, and
634.Fa TYPE
635is the type of the elements to be linked into the list.
636A pointer to the head of the list can later be declared as:
637.Bd -literal -offset indent
638struct HEADNAME *headp;
639.Ed
640.Pp
641(The names
642.Li head
643and
644.Li headp
645are user selectable.)
646.Pp
647The macro
648.Nm LIST_HEAD_INITIALIZER
649evaluates to an initializer for the list
650.Fa head .
651.Pp
652The macro
653.Nm LIST_EMPTY
654evaluates to true if their are no elements in the list.
655.Pp
656The macro
657.Nm LIST_ENTRY
658declares a structure that connects the elements in
659the list.
660.Pp
661The macro
662.Nm LIST_FIRST
663returns the first element in the list or NULL if the list
664is empty.
665.Pp
666The macro
667.Nm LIST_FOREACH
668traverses the list referenced by
669.Fa head
670in the forward direction, assigning each element in turn to
671.Fa var .
672.Pp
673The macro
674.Nm LIST_FOREACH_SAFE
675traverses the list referenced by
676.Fa head
677in the forward direction, assigning each element in turn to
678.Fa var .
679However, unlike
680.Fn LIST_FOREACH
681here it is permitted to both remove
682.Fa var
683as well as free it from within the loop safely without interfering with the
684traversal.
685.Pp
686The macro
687.Nm LIST_INIT
688initializes the list referenced by
689.Fa head .
690.Pp
691The macro
692.Nm LIST_INSERT_HEAD
693inserts the new element
694.Fa elm
695at the head of the list.
696.Pp
697The macro
698.Nm LIST_INSERT_AFTER
699inserts the new element
700.Fa elm
701after the element
702.Fa listelm .
703.Pp
704The macro
705.Nm LIST_INSERT_BEFORE
706inserts the new element
707.Fa elm
708before the element
709.Fa listelm .
710.Pp
711The macro
712.Nm LIST_NEXT
713returns the next element in the list, or NULL if this is the last.
714.Pp
715The macro
716.Nm LIST_REMOVE
717removes the element
718.Fa elm
719from the list.
720.Sh LIST EXAMPLE
721.Bd -literal
722LIST_HEAD(listhead, entry) head =
723 LIST_HEAD_INITIALIZER(head);
724struct listhead *headp; /* List head. */
725struct entry {
726 ...
727 LIST_ENTRY(entry) entries; /* List. */
728 ...
729} *n1, *n2, *n3, *np, *np_temp;
730
731LIST_INIT(&head); /* Initialize the list. */
732
733n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
734LIST_INSERT_HEAD(&head, n1, entries);
735
736n2 = malloc(sizeof(struct entry)); /* Insert after. */
737LIST_INSERT_AFTER(n1, n2, entries);
738
739n3 = malloc(sizeof(struct entry)); /* Insert before. */
740LIST_INSERT_BEFORE(n2, n3, entries);
741
742LIST_REMOVE(n2, entries); /* Deletion. */
743free(n2);
744 /* Forward traversal. */
745LIST_FOREACH(np, &head, entries)
746 np-> ...
747
748 /* Safe forward traversal. */
749LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
750 np->do_stuff();
751 ...
752 LIST_REMOVE(np, entries);
753 free(np);
754}
755
756while (!LIST_EMPTY(&head)) { /* List Deletion. */
757 n1 = LIST_FIRST(&head);
758 LIST_REMOVE(n1, entries);
759 free(n1);
760}
761
762n1 = LIST_FIRST(&head); /* Faster List Deletion. */
763while (n1 != NULL) {
764 n2 = LIST_NEXT(n1, entries);
765 free(n1);
766 n1 = n2;
767}
768LIST_INIT(&head);
769.Ed
770.Sh TAIL QUEUES
771A tail queue is headed by a structure defined by the
772.Nm TAILQ_HEAD
773macro.
774This structure contains a pair of pointers,
775one to the first element in the tail queue and the other to
776the last element in the tail queue.
777The elements are doubly linked so that an arbitrary element can be
778removed without traversing the tail queue.
779New elements can be added to the tail queue after an existing element,
780before an existing element, at the head of the tail queue,
781or at the end of the tail queue.
782A
783.Fa TAILQ_HEAD
784structure is declared as follows:
785.Bd -literal -offset indent
786TAILQ_HEAD(HEADNAME, TYPE) head;
787.Ed
788.Pp
789where
790.Li HEADNAME
791is the name of the structure to be defined, and
792.Li TYPE
793is the type of the elements to be linked into the tail queue.
794A pointer to the head of the tail queue can later be declared as:
795.Bd -literal -offset indent
796struct HEADNAME *headp;
797.Ed
798.Pp
799(The names
800.Li head
801and
802.Li headp
803are user selectable.)
804.Pp
805The macro
806.Nm TAILQ_HEAD_INITIALIZER
807evaluates to an initializer for the tail queue
808.Fa head .
809.Pp
810The macro
811.Nm TAILQ_CONCAT
812concatenates the tail queue headed by
813.Fa head2
814onto the end of the one headed by
815.Fa head1
816removing all entries from the former.
817.Pp
818The macro
819.Nm TAILQ_EMPTY
820evaluates to true if there are no items on the tail queue.
821.Pp
822The macro
823.Nm TAILQ_ENTRY
824declares a structure that connects the elements in
825the tail queue.
826.Pp
827The macro
828.Nm TAILQ_FIRST
829returns the first item on the tail queue or NULL if the tail queue
830is empty.
831.Pp
832The macro
833.Nm TAILQ_FOREACH
834traverses the tail queue referenced by
835.Fa head
836in the forward direction, assigning each element in turn to
837.Fa var .
838.Fa var
839is set to
840.Dv NULL
841if the loop completes normally, or if there were no elements.
842.Pp
843The macro
844.Nm TAILQ_FOREACH_REVERSE
845traverses the tail queue referenced by
846.Fa head
847in the reverse direction, assigning each element in turn to
848.Fa var .
849.Pp
850The macros
851.Nm TAILQ_FOREACH_SAFE
852and
853.Nm TAILQ_FOREACH_REVERSE_SAFE
854traverse the list referenced by
855.Fa head
856in the forward or reverse direction respectively,
857assigning each element in turn to
858.Fa var .
859However, unlike their unsafe counterparts,
860.Nm TAILQ_FOREACH
861and
| 34.\"
35.Dd January 24, 1994
36.Dt QUEUE 3
37.Os
38.Sh NAME
39.Nm SLIST_EMPTY ,
40.Nm SLIST_ENTRY ,
41.Nm SLIST_FIRST ,
42.Nm SLIST_FOREACH ,
43.Nm SLIST_FOREACH_SAFE ,
44.Nm SLIST_HEAD ,
45.Nm SLIST_HEAD_INITIALIZER ,
46.Nm SLIST_INIT ,
47.Nm SLIST_INSERT_AFTER ,
48.Nm SLIST_INSERT_HEAD ,
49.Nm SLIST_NEXT ,
50.Nm SLIST_REMOVE_HEAD ,
51.Nm SLIST_REMOVE ,
52.Nm STAILQ_CONCAT ,
53.Nm STAILQ_EMPTY ,
54.Nm STAILQ_ENTRY ,
55.Nm STAILQ_FIRST ,
56.Nm STAILQ_FOREACH ,
57.Nm STAILQ_FOREACH_SAFE ,
58.Nm STAILQ_HEAD ,
59.Nm STAILQ_HEAD_INITIALIZER ,
60.Nm STAILQ_INIT ,
61.Nm STAILQ_INSERT_AFTER ,
62.Nm STAILQ_INSERT_HEAD ,
63.Nm STAILQ_INSERT_TAIL ,
64.Nm STAILQ_LAST ,
65.Nm STAILQ_NEXT ,
66.Nm STAILQ_REMOVE_HEAD ,
67.Nm STAILQ_REMOVE ,
68.Nm LIST_EMPTY ,
69.Nm LIST_ENTRY ,
70.Nm LIST_FIRST ,
71.Nm LIST_FOREACH ,
72.Nm LIST_FOREACH_SAFE ,
73.Nm LIST_HEAD ,
74.Nm LIST_HEAD_INITIALIZER ,
75.Nm LIST_INIT ,
76.Nm LIST_INSERT_AFTER ,
77.Nm LIST_INSERT_BEFORE ,
78.Nm LIST_INSERT_HEAD ,
79.Nm LIST_NEXT ,
80.Nm LIST_REMOVE ,
81.Nm TAILQ_CONCAT ,
82.Nm TAILQ_EMPTY ,
83.Nm TAILQ_ENTRY ,
84.Nm TAILQ_FIRST ,
85.Nm TAILQ_FOREACH ,
86.Nm TAILQ_FOREACH_SAFE ,
87.Nm TAILQ_FOREACH_REVERSE ,
88.Nm TAILQ_FOREACH_REVERSE_SAFE ,
89.Nm TAILQ_HEAD ,
90.Nm TAILQ_HEAD_INITIALIZER ,
91.Nm TAILQ_INIT ,
92.Nm TAILQ_INSERT_AFTER ,
93.Nm TAILQ_INSERT_BEFORE ,
94.Nm TAILQ_INSERT_HEAD ,
95.Nm TAILQ_INSERT_TAIL ,
96.Nm TAILQ_LAST ,
97.Nm TAILQ_NEXT ,
98.Nm TAILQ_PREV ,
99.Nm TAILQ_REMOVE
100.Nd implementations of singly-linked lists, singly-linked tail queues,
101lists and tail queues
102.Sh SYNOPSIS
103.In sys/queue.h
104.\"
105.Fn SLIST_EMPTY "SLIST_HEAD *head"
106.Fn SLIST_ENTRY "TYPE"
107.Fn SLIST_FIRST "SLIST_HEAD *head"
108.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
109.Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var"
110.Fn SLIST_HEAD "HEADNAME" "TYPE"
111.Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
112.Fn SLIST_INIT "SLIST_HEAD *head"
113.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
114.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
115.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
116.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
117.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
118.\"
119.Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
120.Fn STAILQ_EMPTY "STAILQ_HEAD *head"
121.Fn STAILQ_ENTRY "TYPE"
122.Fn STAILQ_FIRST "STAILQ_HEAD *head"
123.Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
124.Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
125.Fn STAILQ_HEAD "HEADNAME" "TYPE"
126.Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
127.Fn STAILQ_INIT "STAILQ_HEAD *head"
128.Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
129.Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
130.Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
131.Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME"
132.Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
133.Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
134.Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
135.\"
136.Fn LIST_EMPTY "LIST_HEAD *head"
137.Fn LIST_ENTRY "TYPE"
138.Fn LIST_FIRST "LIST_HEAD *head"
139.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
140.Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var"
141.Fn LIST_HEAD "HEADNAME" "TYPE"
142.Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
143.Fn LIST_INIT "LIST_HEAD *head"
144.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
145.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
146.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
147.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
148.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
149.\"
150.Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME"
151.Fn TAILQ_EMPTY "TAILQ_HEAD *head"
152.Fn TAILQ_ENTRY "TYPE"
153.Fn TAILQ_FIRST "TAILQ_HEAD *head"
154.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
155.Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var"
156.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
157.Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var"
158.Fn TAILQ_HEAD "HEADNAME" "TYPE"
159.Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
160.Fn TAILQ_INIT "TAILQ_HEAD *head"
161.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
162.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
163.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
164.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
165.Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
166.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
167.Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME"
168.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
169.\"
170.Sh DESCRIPTION
171These macros define and operate on four types of data structures:
172singly-linked lists, singly-linked tail queues, lists, and tail queues.
173All four structures support the following functionality:
174.Bl -enum -compact -offset indent
175.It
176Insertion of a new entry at the head of the list.
177.It
178Insertion of a new entry after any element in the list.
179.It
180O(1) removal of an entry from the head of the list.
181.It
182O(n) removal of any entry in the list.
183.It
184Forward traversal through the list.
185.El
186.Pp
187Singly-linked lists are the simplest of the five data structures
188and support only the above functionality.
189Singly-linked lists are ideal for applications with large datasets
190and few or no removals,
191or for implementing a LIFO queue.
192.Pp
193Singly-linked tail queues add the following functionality:
194.Bl -enum -compact -offset indent
195.It
196Entries can be added at the end of a list.
197.It
198They may be concatenated.
199.El
200However:
201.Bl -enum -compact -offset indent
202.It
203All list insertions must specify the head of the list.
204.It
205Each head entry requires two pointers rather than one.
206.It
207Code size is about 15% greater and operations run about 20% slower
208than singly-linked lists.
209.El
210.Pp
211Singly-linked tailqs are ideal for applications with large datasets and
212few or no removals,
213or for implementing a FIFO queue.
214.Pp
215All doubly linked types of data structures (lists and tail queues)
216additionally allow:
217.Bl -enum -compact -offset indent
218.It
219Insertion of a new entry before any element in the list.
220.It
221O(1) removal of any entry in the list.
222.El
223However:
224.Bl -enum -compact -offset indent
225.It
226Each elements requires two pointers rather than one.
227.It
228Code size and execution time of operations (except for removal) is about
229twice that of the singly-linked data-structures.
230.El
231.Pp
232Linked lists are the simplest of the doubly linked data structures and support
233only the above functionality over singly-linked lists.
234.Pp
235Tail queues add the following functionality:
236.Bl -enum -compact -offset indent
237.It
238Entries can be added at the end of a list.
239.It
240They may be traversed backwards, from tail to head.
241.It
242They may be concatenated.
243.El
244However:
245.Bl -enum -compact -offset indent
246.It
247All list insertions and removals must specify the head of the list.
248.It
249Each head entry requires two pointers rather than one.
250.It
251Code size is about 15% greater and operations run about 20% slower
252than singly-linked lists.
253.El
254.Pp
255In the macro definitions,
256.Fa TYPE
257is the name of a user defined structure,
258that must contain a field of type
259.Li SLIST_ENTRY ,
260.Li STAILQ_ENTRY ,
261.Li LIST_ENTRY ,
262or
263.Li TAILQ_ENTRY ,
264named
265.Fa NAME .
266The argument
267.Fa HEADNAME
268is the name of a user defined structure that must be declared
269using the macros
270.Li SLIST_HEAD ,
271.Li STAILQ_HEAD ,
272.Li LIST_HEAD ,
273or
274.Li TAILQ_HEAD .
275See the examples below for further explanation of how these
276macros are used.
277.Sh SINGLY-LINKED LISTS
278A singly-linked list is headed by a structure defined by the
279.Nm SLIST_HEAD
280macro.
281This structure contains a single pointer to the first element
282on the list.
283The elements are singly linked for minimum space and pointer manipulation
284overhead at the expense of O(n) removal for arbitrary elements.
285New elements can be added to the list after an existing element or
286at the head of the list.
287An
288.Fa SLIST_HEAD
289structure is declared as follows:
290.Bd -literal -offset indent
291SLIST_HEAD(HEADNAME, TYPE) head;
292.Ed
293.Pp
294where
295.Fa HEADNAME
296is the name of the structure to be defined, and
297.Fa TYPE
298is the type of the elements to be linked into the list.
299A pointer to the head of the list can later be declared as:
300.Bd -literal -offset indent
301struct HEADNAME *headp;
302.Ed
303.Pp
304(The names
305.Li head
306and
307.Li headp
308are user selectable.)
309.Pp
310The macro
311.Nm SLIST_HEAD_INITIALIZER
312evaluates to an initializer for the list
313.Fa head .
314.Pp
315The macro
316.Nm SLIST_EMPTY
317evaluates to true if there are no elements in the list.
318.Pp
319The macro
320.Nm SLIST_ENTRY
321declares a structure that connects the elements in
322the list.
323.Pp
324The macro
325.Nm SLIST_FIRST
326returns the first element in the list or NULL if the list is empty.
327.Pp
328The macro
329.Nm SLIST_FOREACH
330traverses the list referenced by
331.Fa head
332in the forward direction, assigning each element in
333turn to
334.Fa var .
335.Pp
336The macro
337.Nm SLIST_FOREACH_SAFE
338traverses the list referenced by
339.Fa head
340in the forward direction, assigning each element in
341turn to
342.Fa var .
343However, unlike
344.Fn SLIST_FOREACH
345here it is permitted to both remove
346.Fa var
347as well as free it from within the loop safely without interfering with the
348traversal.
349.Pp
350The macro
351.Nm SLIST_INIT
352initializes the list referenced by
353.Fa head .
354.Pp
355The macro
356.Nm SLIST_INSERT_HEAD
357inserts the new element
358.Fa elm
359at the head of the list.
360.Pp
361The macro
362.Nm SLIST_INSERT_AFTER
363inserts the new element
364.Fa elm
365after the element
366.Fa listelm .
367.Pp
368The macro
369.Nm SLIST_NEXT
370returns the next element in the list.
371.Pp
372The macro
373.Nm SLIST_REMOVE_HEAD
374removes the element
375.Fa elm
376from the head of the list.
377For optimum efficiency,
378elements being removed from the head of the list should explicitly use
379this macro instead of the generic
380.Fa SLIST_REMOVE
381macro.
382.Pp
383The macro
384.Nm SLIST_REMOVE
385removes the element
386.Fa elm
387from the list.
388.Sh SINGLY-LINKED LIST EXAMPLE
389.Bd -literal
390SLIST_HEAD(slisthead, entry) head =
391 SLIST_HEAD_INITIALIZER(head);
392struct slisthead *headp; /* Singly-linked List head. */
393struct entry {
394 ...
395 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
396 ...
397} *n1, *n2, *n3, *np;
398
399SLIST_INIT(&head); /* Initialize the list. */
400
401n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
402SLIST_INSERT_HEAD(&head, n1, entries);
403
404n2 = malloc(sizeof(struct entry)); /* Insert after. */
405SLIST_INSERT_AFTER(n1, n2, entries);
406
407SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
408free(n2);
409
410n3 = SLIST_FIRST(&head);
411SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
412free(n3);
413 /* Forward traversal. */
414SLIST_FOREACH(np, &head, entries)
415 np-> ...
416 /* Safe forward traversal. */
417SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
418 np->do_stuff();
419 ...
420 SLIST_REMOVE(&head, np, entry, entries);
421 free(np);
422}
423
424while (!SLIST_EMPTY(&head)) { /* List Deletion. */
425 n1 = SLIST_FIRST(&head);
426 SLIST_REMOVE_HEAD(&head, entries);
427 free(n1);
428}
429.Ed
430.Sh SINGLY-LINKED TAIL QUEUES
431A singly-linked tail queue is headed by a structure defined by the
432.Nm STAILQ_HEAD
433macro.
434This structure contains a pair of pointers,
435one to the first element in the tail queue and the other to
436the last element in the tail queue.
437The elements are singly linked for minimum space and pointer
438manipulation overhead at the expense of O(n) removal for arbitrary
439elements.
440New elements can be added to the tail queue after an existing element,
441at the head of the tail queue, or at the end of the tail queue.
442A
443.Fa STAILQ_HEAD
444structure is declared as follows:
445.Bd -literal -offset indent
446STAILQ_HEAD(HEADNAME, TYPE) head;
447.Ed
448.Pp
449where
450.Li HEADNAME
451is the name of the structure to be defined, and
452.Li TYPE
453is the type of the elements to be linked into the tail queue.
454A pointer to the head of the tail queue can later be declared as:
455.Bd -literal -offset indent
456struct HEADNAME *headp;
457.Ed
458.Pp
459(The names
460.Li head
461and
462.Li headp
463are user selectable.)
464.Pp
465The macro
466.Nm STAILQ_HEAD_INITIALIZER
467evaluates to an initializer for the tail queue
468.Fa head .
469.Pp
470The macro
471.Nm STAILQ_CONCAT
472concatenates the tail queue headed by
473.Fa head2
474onto the end of the one headed by
475.Fa head1
476removing all entries from the former.
477.Pp
478The macro
479.Nm STAILQ_EMPTY
480evaluates to true if there are no items on the tail queue.
481.Pp
482The macro
483.Nm STAILQ_ENTRY
484declares a structure that connects the elements in
485the tail queue.
486.Pp
487The macro
488.Nm STAILQ_FIRST
489returns the first item on the tail queue or NULL if the tail queue
490is empty.
491.Pp
492The macro
493.Nm STAILQ_FOREACH
494traverses the tail queue referenced by
495.Fa head
496in the forward direction, assigning each element
497in turn to
498.Fa var .
499.Pp
500The macro
501.Nm STAILQ_FOREACH_SAFE
502traverses the tail queue referenced by
503.Fa head
504in the forward direction, assigning each element
505in turn to
506.Fa var .
507However, unlike
508.Fn STAILQ_FOREACH
509here it is permitted to both remove
510.Fa var
511as well as free it from within the loop safely without interfering with the
512traversal.
513.Pp
514The macro
515.Nm STAILQ_INIT
516initializes the tail queue referenced by
517.Fa head .
518.Pp
519The macro
520.Nm STAILQ_INSERT_HEAD
521inserts the new element
522.Fa elm
523at the head of the tail queue.
524.Pp
525The macro
526.Nm STAILQ_INSERT_TAIL
527inserts the new element
528.Fa elm
529at the end of the tail queue.
530.Pp
531The macro
532.Nm STAILQ_INSERT_AFTER
533inserts the new element
534.Fa elm
535after the element
536.Fa listelm .
537.Pp
538The macro
539.Nm STAILQ_LAST
540returns the last item on the tail queue.
541If the tail queue is empty the return value is undefined.
542.Pp
543The macro
544.Nm STAILQ_NEXT
545returns the next item on the tail queue, or NULL this item is the last.
546.Pp
547The macro
548.Nm STAILQ_REMOVE_HEAD
549removes the element at the head of the tail queue.
550For optimum efficiency,
551elements being removed from the head of the tail queue should
552use this macro explicitly rather than the generic
553.Fa STAILQ_REMOVE
554macro.
555.Pp
556The macro
557.Nm STAILQ_REMOVE
558removes the element
559.Fa elm
560from the tail queue.
561.Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
562.Bd -literal
563STAILQ_HEAD(stailhead, entry) head =
564 STAILQ_HEAD_INITIALIZER(head);
565struct stailhead *headp; /* Singly-linked tail queue head. */
566struct entry {
567 ...
568 STAILQ_ENTRY(entry) entries; /* Tail queue. */
569 ...
570} *n1, *n2, *n3, *np;
571
572STAILQ_INIT(&head); /* Initialize the queue. */
573
574n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
575STAILQ_INSERT_HEAD(&head, n1, entries);
576
577n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
578STAILQ_INSERT_TAIL(&head, n1, entries);
579
580n2 = malloc(sizeof(struct entry)); /* Insert after. */
581STAILQ_INSERT_AFTER(&head, n1, n2, entries);
582 /* Deletion. */
583STAILQ_REMOVE(&head, n2, entry, entries);
584free(n2);
585 /* Deletion from the head. */
586n3 = STAILQ_FIRST(&head);
587STAILQ_REMOVE_HEAD(&head, entries);
588free(n3);
589 /* Forward traversal. */
590STAILQ_FOREACH(np, &head, entries)
591 np-> ...
592 /* Safe forward traversal. */
593STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
594 np->do_stuff();
595 ...
596 STAILQ_REMOVE(&head, np, entry, entries);
597 free(np);
598}
599 /* TailQ Deletion. */
600while (!STAILQ_EMPTY(&head)) {
601 n1 = STAILQ_FIRST(&head);
602 STAILQ_REMOVE_HEAD(&head, entries);
603 free(n1);
604}
605 /* Faster TailQ Deletion. */
606n1 = STAILQ_FIRST(&head);
607while (n1 != NULL) {
608 n2 = STAILQ_NEXT(n1, entries);
609 free(n1);
610 n1 = n2;
611}
612STAILQ_INIT(&head);
613.Ed
614.Sh LISTS
615A list is headed by a structure defined by the
616.Nm LIST_HEAD
617macro.
618This structure contains a single pointer to the first element
619on the list.
620The elements are doubly linked so that an arbitrary element can be
621removed without traversing the list.
622New elements can be added to the list after an existing element,
623before an existing element, or at the head of the list.
624A
625.Fa LIST_HEAD
626structure is declared as follows:
627.Bd -literal -offset indent
628LIST_HEAD(HEADNAME, TYPE) head;
629.Ed
630.Pp
631where
632.Fa HEADNAME
633is the name of the structure to be defined, and
634.Fa TYPE
635is the type of the elements to be linked into the list.
636A pointer to the head of the list can later be declared as:
637.Bd -literal -offset indent
638struct HEADNAME *headp;
639.Ed
640.Pp
641(The names
642.Li head
643and
644.Li headp
645are user selectable.)
646.Pp
647The macro
648.Nm LIST_HEAD_INITIALIZER
649evaluates to an initializer for the list
650.Fa head .
651.Pp
652The macro
653.Nm LIST_EMPTY
654evaluates to true if their are no elements in the list.
655.Pp
656The macro
657.Nm LIST_ENTRY
658declares a structure that connects the elements in
659the list.
660.Pp
661The macro
662.Nm LIST_FIRST
663returns the first element in the list or NULL if the list
664is empty.
665.Pp
666The macro
667.Nm LIST_FOREACH
668traverses the list referenced by
669.Fa head
670in the forward direction, assigning each element in turn to
671.Fa var .
672.Pp
673The macro
674.Nm LIST_FOREACH_SAFE
675traverses the list referenced by
676.Fa head
677in the forward direction, assigning each element in turn to
678.Fa var .
679However, unlike
680.Fn LIST_FOREACH
681here it is permitted to both remove
682.Fa var
683as well as free it from within the loop safely without interfering with the
684traversal.
685.Pp
686The macro
687.Nm LIST_INIT
688initializes the list referenced by
689.Fa head .
690.Pp
691The macro
692.Nm LIST_INSERT_HEAD
693inserts the new element
694.Fa elm
695at the head of the list.
696.Pp
697The macro
698.Nm LIST_INSERT_AFTER
699inserts the new element
700.Fa elm
701after the element
702.Fa listelm .
703.Pp
704The macro
705.Nm LIST_INSERT_BEFORE
706inserts the new element
707.Fa elm
708before the element
709.Fa listelm .
710.Pp
711The macro
712.Nm LIST_NEXT
713returns the next element in the list, or NULL if this is the last.
714.Pp
715The macro
716.Nm LIST_REMOVE
717removes the element
718.Fa elm
719from the list.
720.Sh LIST EXAMPLE
721.Bd -literal
722LIST_HEAD(listhead, entry) head =
723 LIST_HEAD_INITIALIZER(head);
724struct listhead *headp; /* List head. */
725struct entry {
726 ...
727 LIST_ENTRY(entry) entries; /* List. */
728 ...
729} *n1, *n2, *n3, *np, *np_temp;
730
731LIST_INIT(&head); /* Initialize the list. */
732
733n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
734LIST_INSERT_HEAD(&head, n1, entries);
735
736n2 = malloc(sizeof(struct entry)); /* Insert after. */
737LIST_INSERT_AFTER(n1, n2, entries);
738
739n3 = malloc(sizeof(struct entry)); /* Insert before. */
740LIST_INSERT_BEFORE(n2, n3, entries);
741
742LIST_REMOVE(n2, entries); /* Deletion. */
743free(n2);
744 /* Forward traversal. */
745LIST_FOREACH(np, &head, entries)
746 np-> ...
747
748 /* Safe forward traversal. */
749LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
750 np->do_stuff();
751 ...
752 LIST_REMOVE(np, entries);
753 free(np);
754}
755
756while (!LIST_EMPTY(&head)) { /* List Deletion. */
757 n1 = LIST_FIRST(&head);
758 LIST_REMOVE(n1, entries);
759 free(n1);
760}
761
762n1 = LIST_FIRST(&head); /* Faster List Deletion. */
763while (n1 != NULL) {
764 n2 = LIST_NEXT(n1, entries);
765 free(n1);
766 n1 = n2;
767}
768LIST_INIT(&head);
769.Ed
770.Sh TAIL QUEUES
771A tail queue is headed by a structure defined by the
772.Nm TAILQ_HEAD
773macro.
774This structure contains a pair of pointers,
775one to the first element in the tail queue and the other to
776the last element in the tail queue.
777The elements are doubly linked so that an arbitrary element can be
778removed without traversing the tail queue.
779New elements can be added to the tail queue after an existing element,
780before an existing element, at the head of the tail queue,
781or at the end of the tail queue.
782A
783.Fa TAILQ_HEAD
784structure is declared as follows:
785.Bd -literal -offset indent
786TAILQ_HEAD(HEADNAME, TYPE) head;
787.Ed
788.Pp
789where
790.Li HEADNAME
791is the name of the structure to be defined, and
792.Li TYPE
793is the type of the elements to be linked into the tail queue.
794A pointer to the head of the tail queue can later be declared as:
795.Bd -literal -offset indent
796struct HEADNAME *headp;
797.Ed
798.Pp
799(The names
800.Li head
801and
802.Li headp
803are user selectable.)
804.Pp
805The macro
806.Nm TAILQ_HEAD_INITIALIZER
807evaluates to an initializer for the tail queue
808.Fa head .
809.Pp
810The macro
811.Nm TAILQ_CONCAT
812concatenates the tail queue headed by
813.Fa head2
814onto the end of the one headed by
815.Fa head1
816removing all entries from the former.
817.Pp
818The macro
819.Nm TAILQ_EMPTY
820evaluates to true if there are no items on the tail queue.
821.Pp
822The macro
823.Nm TAILQ_ENTRY
824declares a structure that connects the elements in
825the tail queue.
826.Pp
827The macro
828.Nm TAILQ_FIRST
829returns the first item on the tail queue or NULL if the tail queue
830is empty.
831.Pp
832The macro
833.Nm TAILQ_FOREACH
834traverses the tail queue referenced by
835.Fa head
836in the forward direction, assigning each element in turn to
837.Fa var .
838.Fa var
839is set to
840.Dv NULL
841if the loop completes normally, or if there were no elements.
842.Pp
843The macro
844.Nm TAILQ_FOREACH_REVERSE
845traverses the tail queue referenced by
846.Fa head
847in the reverse direction, assigning each element in turn to
848.Fa var .
849.Pp
850The macros
851.Nm TAILQ_FOREACH_SAFE
852and
853.Nm TAILQ_FOREACH_REVERSE_SAFE
854traverse the list referenced by
855.Fa head
856in the forward or reverse direction respectively,
857assigning each element in turn to
858.Fa var .
859However, unlike their unsafe counterparts,
860.Nm TAILQ_FOREACH
861and
|