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