xref: /netbsd-src/share/man/man3/queue.3 (revision 5e4c038a45edbc7d63b7c2daa76e29f88b64a4e3)
1.\"	$NetBSD: queue.3,v 1.24 2002/06/01 23:50:53 lukem Exp $
2.\"
3.\" Copyright (c) 2000, 2002 The NetBSD Foundation, Inc.
4.\" All rights reserved.
5.\"
6.\" Redistribution and use in source and binary forms, with or without
7.\" modification, are permitted provided that the following conditions
8.\" are met:
9.\" 1. Redistributions of source code must retain the above copyright
10.\"    notice, this list of conditions and the following disclaimer.
11.\" 2. Redistributions in binary form must reproduce the above copyright
12.\"    notice, this list of conditions and the following disclaimer in the
13.\"    documentation and/or other materials provided with the distribution.
14.\" 3. All advertising materials mentioning features or use of this software
15.\"    must display the following acknowledgement:
16.\"        This product includes software developed by the NetBSD
17.\"        Foundation, Inc. and its contributors.
18.\" 4. Neither the name of The NetBSD Foundation nor the names of its
19.\"    contributors may be used to endorse or promote products derived
20.\"    from this software without specific prior written permission.
21.\"
22.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
23.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
24.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
25.\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
26.\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
27.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
28.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
29.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
30.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
31.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32.\" POSSIBILITY OF SUCH DAMAGE.
33.\"
34.\" Copyright (c) 1993 The Regents of the University of California.
35.\" All rights reserved.
36.\"
37.\" Redistribution and use in source and binary forms, with or without
38.\" modification, are permitted provided that the following conditions
39.\" are met:
40.\" 1. Redistributions of source code must retain the above copyright
41.\"    notice, this list of conditions and the following disclaimer.
42.\" 2. Redistributions in binary form must reproduce the above copyright
43.\"    notice, this list of conditions and the following disclaimer in the
44.\"    documentation and/or other materials provided with the distribution.
45.\" 3. All advertising materials mentioning features or use of this software
46.\"    must display the following acknowledgement:
47.\"	This product includes software developed by the University of
48.\"	California, Berkeley and its contributors.
49.\" 4. Neither the name of the University nor the names of its contributors
50.\"    may be used to endorse or promote products derived from this software
51.\"    without specific prior written permission.
52.\"
53.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
54.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
55.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
56.\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
57.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
58.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
59.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
60.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
61.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
62.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
63.\" SUCH DAMAGE.
64.\"
65.\"	@(#)queue.3	8.1 (Berkeley) 12/13/93
66.\"
67.Dd June 2, 2002
68.Dt QUEUE 3
69.Os
70.Sh NAME
71.Nm SLIST_ENTRY ,
72.Nm SLIST_HEAD ,
73.Nm SLIST_HEAD_INITIALIZER ,
74.Nm SLIST_INIT ,
75.Nm SLIST_INSERT_AFTER ,
76.Nm SLIST_INSERT_HEAD ,
77.Nm SLIST_REMOVE ,
78.Nm SLIST_REMOVE_HEAD ,
79.Nm SLIST_FOREACH ,
80.Nm SLIST_EMPTY ,
81.Nm SLIST_FIRST ,
82.Nm SLIST_NEXT ,
83.Nm SIMPLEQ_ENTRY ,
84.Nm SIMPLEQ_HEAD ,
85.Nm SIMPLEQ_HEAD_INITIALIZER ,
86.Nm SIMPLEQ_INIT ,
87.Nm SIMPLEQ_INSERT_HEAD ,
88.Nm SIMPLEQ_INSERT_TAIL ,
89.Nm SIMPLEQ_INSERT_AFTER ,
90.Nm SIMPLEQ_REMOVE ,
91.Nm SIMPLEQ_REMOVE_HEAD ,
92.Nm SIMPLEQ_FOREACH ,
93.Nm SIMPLEQ_EMPTY ,
94.Nm SIMPLEQ_FIRST ,
95.Nm SIMPLEQ_NEXT ,
96.Nm LIST_ENTRY ,
97.Nm LIST_HEAD ,
98.Nm LIST_HEAD_INITIALIZER ,
99.Nm LIST_INIT ,
100.Nm LIST_INSERT_AFTER ,
101.Nm LIST_INSERT_BEFORE ,
102.Nm LIST_INSERT_HEAD ,
103.Nm LIST_REMOVE ,
104.Nm LIST_FOREACH ,
105.Nm LIST_EMPTY ,
106.Nm LIST_FIRST ,
107.Nm LIST_NEXT ,
108.Nm TAILQ_ENTRY ,
109.Nm TAILQ_HEAD ,
110.Nm TAILQ_HEAD_INITIALIZER ,
111.Nm TAILQ_INIT ,
112.Nm TAILQ_INSERT_AFTER ,
113.Nm TAILQ_INSERT_BEFORE ,
114.Nm TAILQ_INSERT_HEAD ,
115.Nm TAILQ_INSERT_TAIL ,
116.Nm TAILQ_REMOVE ,
117.Nm TAILQ_FOREACH ,
118.Nm TAILQ_FOREACH_REVERSE ,
119.Nm TAILQ_EMPTY ,
120.Nm TAILQ_FIRST ,
121.Nm TAILQ_NEXT ,
122.Nm CIRCLEQ_ENTRY ,
123.Nm CIRCLEQ_HEAD ,
124.Nm CIRCLEQ_HEAD_INITIALIZER ,
125.Nm CIRCLEQ_INIT ,
126.Nm CIRCLEQ_INSERT_AFTER ,
127.Nm CIRCLEQ_INSERT_BEFORE ,
128.Nm CIRCLEQ_INSERT_HEAD ,
129.Nm CIRCLEQ_INSERT_TAIL ,
130.Nm CIRCLEQ_REMOVE ,
131.Nm CIRCLEQ_FOREACH ,
132.Nm CIRCLEQ_FOREACH_REVERSE ,
133.Nm CIRCLEQ_EMPTY ,
134.Nm CIRCLEQ_FIRST ,
135.Nm CIRCLEQ_LAST ,
136.Nm CIRCLEQ_NEXT ,
137.Nm CIRCLEQ_PREV
138.Nd "implementations of singly-linked lists, simple queues, lists, tail queues, and circular queues"
139.Sh SYNOPSIS
140.Fd #include \*[Lt]sys/queue.h\*[Gt]
141.sp
142.Fn SLIST_ENTRY "TYPE"
143.Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME"
144.Fn SLIST_HEAD "HEADNAME" "TYPE"
145.Fn SLIST_HEAD_INITIALIZER "head"
146.Fn SLIST_INIT "SLIST_HEAD *head"
147.Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME"
148.Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME"
149.Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME"
150.Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME"
151.Ft int
152.Fn SLIST_EMPTY "SLIST_HEAD *head"
153.Ft TYPE *
154.Fn SLIST_FIRST "SLIST_HEAD *head"
155.Ft TYPE *
156.Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME"
157.sp
158.Fn SIMPLEQ_ENTRY "TYPE"
159.Fn SIMPLEQ_FOREACH "TYPE *var" "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME"
160.Fn SIMPLEQ_HEAD "HEADNAME" "TYPE"
161.Fn SIMPLEQ_HEAD_INITIALIZER "head"
162.Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head"
163.Fn SIMPLEQ_INSERT_AFTER "SIMPLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
164.Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
165.Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "TYPE *elm" "SIMPLEQ_ENTRY NAME"
166.Fn SIMPLEQ_REMOVE "SIMPLEQ_HEAD *head" "TYPE *elm" "TYPE" "SIMPLEQ_ENTRY NAME"
167.Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "SIMPLEQ_ENTRY NAME"
168.Ft int
169.Fn SIMPLEQ_EMPTY "SIMPLEQ_HEAD *head"
170.Ft TYPE *
171.Fn SIMPLEQ_FIRST "SIMPLEQ_HEAD *head"
172.Ft TYPE *
173.Fn SIMPLEQ_NEXT "TYPE *elm" "SIMPLEQ_ENTRY NAME"
174.sp
175.Fn LIST_ENTRY "TYPE"
176.Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME"
177.Fn LIST_HEAD "HEADNAME" "TYPE"
178.Fn LIST_HEAD_INITIALIZER "head"
179.Fn LIST_INIT "LIST_HEAD *head"
180.Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
181.Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME"
182.Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME"
183.Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME"
184.Ft int
185.Fn LIST_EMPTY "LIST_HEAD *head"
186.Ft TYPE *
187.Fn LIST_FIRST "LIST_HEAD *head"
188.Ft TYPE *
189.Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME"
190.sp
191.Fn TAILQ_ENTRY "TYPE"
192.Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME"
193.Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME"
194.Fn TAILQ_HEAD "HEADNAME" "TYPE"
195.Fn TAILQ_HEAD_INITIALIZER "head"
196.Fn TAILQ_INIT "TAILQ_HEAD *head"
197.Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
198.Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME"
199.Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
200.Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
201.Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME"
202.Ft int
203.Fn TAILQ_EMPTY "TAILQ_HEAD *head"
204.Ft TYPE *
205.Fn TAILQ_FIRST "TAILQ_HEAD *head"
206.Ft TYPE *
207.Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME"
208.sp
209.Fn CIRCLEQ_ENTRY "TYPE"
210.Fn CIRCLEQ_FOREACH "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
211.Fn CIRCLEQ_FOREACH_REVERSE "TYPE *var" "CIRCLEQ_HEAD *head" "CIRCLEQ_ENTRY NAME"
212.Fn CIRCLEQ_HEAD "HEADNAME" "TYPE"
213.Fn CIRCLEQ_HEAD_INITIALIZER "head"
214.Fn CIRCLEQ_INIT "CIRCLEQ_HEAD *head"
215.Fn CIRCLEQ_INSERT_AFTER "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
216.Fn CIRCLEQ_INSERT_BEFORE "CIRCLEQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
217.Fn CIRCLEQ_INSERT_HEAD "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
218.Fn CIRCLEQ_INSERT_TAIL "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
219.Fn CIRCLEQ_REMOVE "CIRCLEQ_HEAD *head" "TYPE *elm" "CIRCLEQ_ENTRY NAME"
220.Ft int
221.Fn CIRCLEQ_EMPTY "CIRCLEQ_HEAD *head"
222.Ft TYPE *
223.Fn CIRCLEQ_FIRST "CIRCLEQ_HEAD *head"
224.Ft TYPE *
225.Fn CIRCLEQ_LAST "CIRCLEQ_HEAD *head"
226.Ft TYPE *
227.Fn CIRCLEQ_NEXT "TYPE *elm" "CIRCLEQ_ENTRY NAME"
228.Ft TYPE *
229.Fn CIRCLEQ_PREV "TYPE *elm" "CIRCLEQ_ENTRY NAME"
230.Sh DESCRIPTION
231These macros define and operate on five types of data structures:
232singly-linked lists, simple queues, lists, tail queues, and circular queues.
233All five 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 before or after any element in the list.
239.It
240Removal of any entry in the list.
241.It
242Forward traversal through the list.
243.El
244.Pp
245Singly-linked lists are the simplest of the five data structures and
246support only the above functionality.
247Singly-linked lists are ideal for applications with large datasets and
248few or no removals,
249or for implementing a LIFO queue.
250.Pp
251Simple queues add the following functionality:
252.Bl -enum -compact -offset indent
253.It
254Entries can be added at the end of a list.
255.El
256However:
257.Bl -enum -compact -offset indent
258.It
259Entries may not be added before any element in the list.
260.It
261All list insertions and removals must specify the head of the list.
262.It
263Each head entry requires two pointers rather than one.
264.El
265.Pp
266Simple queues are ideal for applications with large datasets and few or
267no removals, or for implementing a FIFO	queue.
268.Pp
269All doubly linked types of data structures (lists, tail queues, and circle
270queues) additionally allow:
271.Bl -enum -compact -offset indent
272.It
273Insertion of a new entry before any element in the list.
274.It
275O(1) removal of any entry in the list.
276.El
277However:
278.Bl -enum -compact -offset indent
279.It
280Each elements requires two pointers rather than one.
281.It
282Code size and execution time of operations (except for removal) is about
283twice that of the singly-linked data-structures.
284.El
285.Pp
286Linked lists are the simplest of the doubly linked data structures and
287support only the above functionality over singly-linked lists.
288.Pp
289Tail queues add the following functionality:
290.Bl -enum -compact -offset indent
291.It
292Entries can be added at the end of a list.
293.El
294However:
295.Bl -enum -compact -offset indent
296.It
297All list insertions and removals, except insertion before another element, must
298specify the head of the list.
299.It
300Each head entry requires two pointers rather than one.
301.It
302Code size is about 15% greater and operations run about 20% slower
303than lists.
304.El
305.Pp
306Circular queues add the following functionality:
307.Bl -enum -compact -offset indent
308.It
309Entries can be added at the end of a list.
310.It
311They may be traversed backwards, from tail to head.
312.El
313However:
314.Bl -enum -compact -offset indent
315.It
316All list insertions and removals must specify the head of the list.
317.It
318Each head entry requires two pointers rather than one.
319.It
320The termination condition for traversal is more complex.
321.It
322Code size is about 40% greater and operations run about 45% slower
323than lists.
324.El
325.Pp
326In the macro definitions,
327.Fa TYPE
328is the name of a user defined structure,
329that must contain a field of type
330.Li LIST_ENTRY ,
331.Li SIMPLEQ_ENTRY ,
332.Li SLIST_ENTRY ,
333.Li TAILQ_ENTRY ,
334or
335.Li CIRCLEQ_ENTRY ,
336named
337.Fa NAME .
338The argument
339.Fa HEADNAME
340is the name of a user defined structure that must be declared
341using the macros
342.Li LIST_HEAD ,
343.Li SIMPLEQ_HEAD ,
344.Li SLIST_HEAD ,
345.Li TAILQ_HEAD ,
346or
347.Li CIRCLEQ_HEAD .
348See the examples below for further explanation of how these
349macros are used.
350.Sh SINGLY-LINKED LISTS
351A singly-linked list is headed by a structure defined by the
352.Nm SLIST_HEAD
353macro.
354This structure contains a single pointer to the first element
355on the list.
356The elements are singly linked for minimum space and pointer manipulation
357overhead at the expense of O(n) removal for arbitrary elements.
358New elements can be added to the list after an existing element or
359at the head of the list.
360An
361.Fa SLIST_HEAD
362structure is declared as follows:
363.Bd -literal -offset indent
364SLIST_HEAD(HEADNAME, TYPE) head;
365.Ed
366.Pp
367where
368.Fa HEADNAME
369is the name of the structure to be defined, and
370.Fa TYPE
371is the type of the elements to be linked into the list.
372A pointer to the head of the list can later be declared as:
373.Bd -literal -offset indent
374struct HEADNAME *headp;
375.Ed
376.Pp
377(The names
378.Li head
379and
380.Li headp
381are user selectable.)
382.Pp
383The macro
384.Nm SLIST_HEAD_INITIALIZER
385evaluates to an initializer for the list
386.Fa head .
387.Pp
388The macro
389.Nm SLIST_EMPTY
390evaluates to true if there are no elements in the list.
391.Pp
392The macro
393.Nm SLIST_ENTRY
394declares a structure that connects the elements in
395the list.
396.Pp
397The macro
398.Nm SLIST_FIRST
399returns the first element in the list or NULL if the list is empty.
400.Pp
401The macro
402.Nm SLIST_FOREACH
403traverses the list referenced by
404.Fa head
405in the forward direction, assigning each element in
406turn to
407.Fa var .
408.Pp
409The macro
410.Nm SLIST_INIT
411initializes the list referenced by
412.Fa head .
413.Pp
414The macro
415.Nm SLIST_INSERT_HEAD
416inserts the new element
417.Fa elm
418at the head of the list.
419.Pp
420The macro
421.Nm SLIST_INSERT_AFTER
422inserts the new element
423.Fa elm
424after the element
425.Fa listelm .
426.Pp
427The macro
428.Nm SLIST_NEXT
429returns the next element in the list.
430.Pp
431The macro
432.Nm SLIST_REMOVE
433removes the element
434.Fa elm
435from the list.
436.Pp
437The macro
438.Nm SLIST_REMOVE_HEAD
439removes the first element from the head of the list.
440For optimum efficiency,
441elements being removed from the head of the list should explicitly use
442this macro instead of the generic
443.Nm SLIST_REMOVE
444macro.
445.Sh SINGLY-LINKED LIST EXAMPLE
446.Bd -literal
447SLIST_HEAD(slisthead, entry) head =
448    SLIST_HEAD_INITIALIZER(head);
449struct slisthead *headp;                /* Singly-linked List head. */
450struct entry {
451        ...
452        SLIST_ENTRY(entry) entries;     /* Singly-linked List. */
453        ...
454} *n1, *n2, *n3, *np;
455
456SLIST_INIT(\*[Am]head);                      /* Initialize the list. */
457
458n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
459SLIST_INSERT_HEAD(\*[Am]head, n1, entries);
460
461n2 = malloc(sizeof(struct entry));      /* Insert after. */
462SLIST_INSERT_AFTER(n1, n2, entries);
463
464SLIST_REMOVE(\*[Am]head, n2, entry, entries);/* Deletion. */
465free(n2);
466
467n3 = SLIST_FIRST(\*[Am]head);
468SLIST_REMOVE_HEAD(\*[Am]head, entries);      /* Deletion from the head. */
469free(n3);
470                                        /* Forward traversal. */
471SLIST_FOREACH(np, \*[Am]head, entries)
472        np-\*[Gt] ...
473
474while (!SLIST_EMPTY(\*[Am]head)) {           /* List Deletion. */
475        n1 = SLIST_FIRST(\*[Am]head);
476        SLIST_REMOVE_HEAD(\*[Am]head, entries);
477        free(n1);
478}
479.Ed
480.Sh SIMPLE QUEUES
481A simple queue is headed by a structure defined by the
482.Nm SIMPLEQ_HEAD
483macro.
484This structure contains a pair of pointers,
485one to the first element in the simple queue and the other to
486the last element in the simple queue.
487The elements are singly linked for minimum space and pointer manipulation
488overhead at the expense of O(n) removal for arbitrary elements.
489New elements can be added to the queue after an existing element,
490at the head of the queue, or at the end of the queue.
491A
492.Fa SIMPLEQ_HEAD
493structure is declared as follows:
494.Bd -literal -offset indent
495SIMPLEQ_HEAD(HEADNAME, TYPE) head;
496.Ed
497.sp
498where
499.Li HEADNAME
500is the name of the structure to be defined, and
501.Li TYPE
502is the type of the elements to be linked into the simple queue.
503A pointer to the head of the simple queue can later be declared as:
504.Bd -literal -offset indent
505struct HEADNAME *headp;
506.Ed
507.sp
508(The names
509.Li head
510and
511.Li headp
512are user selectable.)
513.Pp
514The macro
515.Nm SIMPLEQ_ENTRY
516declares a structure that connects the elements in
517the simple queue.
518.Pp
519The macro
520.Nm SIMPLEQ_HEAD_INITIALIZER
521provides a value which can be used to initialize a simple queue head at
522compile time, and is used at the point that the simple queue head
523variable is declared, like:
524.Bd -literal -offset indent
525struct HEADNAME head = SIMPLEQ_HEAD_INITIALIZER(head);
526.Ed
527.Pp
528The macro
529.Nm SIMPLEQ_INIT
530initializes the simple queue referenced by
531.Fa head .
532.Pp
533The macro
534.Nm SIMPLEQ_INSERT_HEAD
535inserts the new element
536.Fa elm
537at the head of the simple queue.
538.Pp
539The macro
540.Nm SIMPLEQ_INSERT_TAIL
541inserts the new element
542.Fa elm
543at the end of the simple queue.
544.Pp
545The macro
546.Nm SIMPLEQ_INSERT_AFTER
547inserts the new element
548.Fa elm
549after the element
550.Fa listelm .
551.Pp
552The macro
553.Nm SIMPLEQ_REMOVE
554removes
555.Fa elm
556from the simple queue.
557.Pp
558The macro
559.Nm SIMPLEQ_REMOVE_HEAD
560removes the first element from the head of the simple queue.
561For optimum efficiency,
562elements being removed from the head of the queue should explicitly use
563this macro instead of the generic
564.Nm SIMPLQ_REMOVE
565macro.
566.Pp
567The macro
568.Nm SIMPLEQ_EMPTY
569return true if the simple queue
570.Fa head
571has no elements.
572.Pp
573The macro
574.Nm SIMPLEQ_FIRST
575returns the first element of the simple queue
576.Fa head .
577.Pp
578The macro
579.Nm SIMPLEQ_FOREACH
580traverses the tail queue referenced by
581.Fa head
582in the forward direction, assigning each element
583in turn to
584.Fa var .
585.Pp
586The macro
587.Nm SIMPLEQ_NEXT
588returns the element after the element
589.Fa elm .
590.Sh SIMPLE QUEUE EXAMPLE
591.Bd -literal
592SIMPLEQ_HEAD(simplehead, entry) head;
593struct simplehead *headp;		/* Simple queue head. */
594struct entry {
595	...
596	SIMPLEQ_ENTRY(entry) entries;	/* Simple queue. */
597	...
598} *n1, *n2, *np;
599
600SIMPLEQ_INIT(\*[Am]head);			/* Initialize the queue. */
601
602n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
603SIMPLEQ_INSERT_HEAD(\*[Am]head, n1, entries);
604
605n1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
606SIMPLEQ_INSERT_TAIL(\*[Am]head, n1, entries);
607
608n2 = malloc(sizeof(struct entry));	/* Insert after. */
609SIMPLEQ_INSERT_AFTER(\*[Am]head, n1, n2, entries);
610					/* Forward traversal. */
611SIMPLEQ_FOREACH(np, \*[Am]head, entries)
612	np-\*[Gt] ...
613					/* Delete. */
614while (SIMPLEQ_FIRST(\*[Am]head) != NULL)
615	SIMPLEQ_REMOVE_HEAD(\*[Am]head, entries);
616if (SIMPLEQ_EMPTY(\*[Am]head))		/* Test for emptiness. */
617	printf("nothing to do\\n");
618.Ed
619.Sh LISTS
620A list is headed by a structure defined by the
621.Nm LIST_HEAD
622macro.
623This structure contains a single pointer to the first element
624on the list.
625The elements are doubly linked so that an arbitrary element can be
626removed without traversing the list.
627New elements can be added to the list after an existing element,
628before an existing element, or at the head of the list.
629A
630.Fa LIST_HEAD
631structure is declared as follows:
632.Bd -literal -offset indent
633LIST_HEAD(HEADNAME, TYPE) head;
634.Ed
635.sp
636where
637.Fa HEADNAME
638is the name of the structure to be defined, and
639.Fa TYPE
640is the type of the elements to be linked into the list.
641A pointer to the head of the list can later be declared as:
642.Bd -literal -offset indent
643struct HEADNAME *headp;
644.Ed
645.sp
646(The names
647.Li head
648and
649.Li headp
650are user selectable.)
651.Pp
652The macro
653.Nm LIST_ENTRY
654declares a structure that connects the elements in
655the list.
656.Pp
657The macro
658.Nm LIST_HEAD_INITIALIZER
659provides a value which can be used to initialize a list head at
660compile time, and is used at the point that the list head
661variable is declared, like:
662.Bd -literal -offset indent
663struct HEADNAME head = LIST_HEAD_INITIALIZER(head);
664.Ed
665.Pp
666The macro
667.Nm LIST_INIT
668initializes the list referenced by
669.Fa head .
670.Pp
671The macro
672.Nm LIST_INSERT_HEAD
673inserts the new element
674.Fa elm
675at the head of the list.
676.Pp
677The macro
678.Nm LIST_INSERT_AFTER
679inserts the new element
680.Fa elm
681after the element
682.Fa listelm .
683.Pp
684The macro
685.Nm LIST_INSERT_BEFORE
686inserts the new element
687.Fa elm
688before the element
689.Fa listelm .
690.Pp
691The macro
692.Nm LIST_REMOVE
693removes the element
694.Fa elm
695from the list.
696.Pp
697The macro
698.Nm LIST_EMPTY
699return true if the list
700.Fa head
701has no elements.
702.Pp
703The macro
704.Nm LIST_FIRST
705returns the first element of the list
706.Fa head .
707.Pp
708The macro
709.Nm LIST_FOREACH
710traverses the list referenced by
711.Fa head
712in the forward direction, assigning each element in turn to
713.Fa var .
714.Pp
715The macro
716.Nm LIST_NEXT
717returns the element after the element
718.Fa elm .
719.Sh LIST EXAMPLE
720.Bd -literal
721LIST_HEAD(listhead, entry) head;
722struct listhead *headp;		/* List head. */
723struct entry {
724	...
725	LIST_ENTRY(entry) entries;	/* List. */
726	...
727} *n1, *n2, *np;
728
729LIST_INIT(\*[Am]head);			/* Initialize the list. */
730
731n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
732LIST_INSERT_HEAD(\*[Am]head, n1, entries);
733
734n2 = malloc(sizeof(struct entry));	/* Insert after. */
735LIST_INSERT_AFTER(n1, n2, entries);
736
737n2 = malloc(sizeof(struct entry));	/* Insert before. */
738LIST_INSERT_BEFORE(n1, n2, entries);
739					/* Forward traversal. */
740LIST_FOREACH(np, \*[Am]head, entries)
741	np-\*[Gt] ...
742					/* Delete. */
743while (LIST_FIRST(\*[Am]head) != NULL)
744	LIST_REMOVE(LIST_FIRST(\*[Am]head), entries);
745if (LIST_EMPTY(\*[Am]head))			/* Test for emptiness. */
746	printf("nothing to do\\n");
747.Ed
748.Sh TAIL QUEUES
749A tail queue is headed by a structure defined by the
750.Nm TAILQ_HEAD
751macro.
752This structure contains a pair of pointers,
753one to the first element in the tail queue and the other to
754the last element in the tail queue.
755The elements are doubly linked so that an arbitrary element can be
756removed without traversing the tail queue.
757New elements can be added to the queue after an existing element,
758before an existing element, at the head of the queue, or at the end
759the queue.
760A
761.Fa TAILQ_HEAD
762structure is declared as follows:
763.Bd -literal -offset indent
764TAILQ_HEAD(HEADNAME, TYPE) head;
765.Ed
766.sp
767where
768.Li HEADNAME
769is the name of the structure to be defined, and
770.Li TYPE
771is the type of the elements to be linked into the tail queue.
772A pointer to the head of the tail queue can later be declared as:
773.Bd -literal -offset indent
774struct HEADNAME *headp;
775.Ed
776.sp
777(The names
778.Li head
779and
780.Li headp
781are user selectable.)
782.Pp
783The macro
784.Nm TAILQ_ENTRY
785declares a structure that connects the elements in
786the tail queue.
787.Pp
788The macro
789.Nm TAILQ_HEAD_INITIALIZER
790provides a value which can be used to initialize a tail queue head at
791compile time, and is used at the point that the tail queue head
792variable is declared, like:
793.Bd -literal -offset indent
794struct HEADNAME head = TAILQ_HEAD_INITIALIZER(head);
795.Ed
796.Pp
797The macro
798.Nm TAILQ_INIT
799initializes the tail queue referenced by
800.Fa head .
801.Pp
802The macro
803.Nm TAILQ_INSERT_HEAD
804inserts the new element
805.Fa elm
806at the head of the tail queue.
807.Pp
808The macro
809.Nm TAILQ_INSERT_TAIL
810inserts the new element
811.Fa elm
812at the end of the tail queue.
813.Pp
814The macro
815.Nm TAILQ_INSERT_AFTER
816inserts the new element
817.Fa elm
818after the element
819.Fa listelm .
820.Pp
821The macro
822.Nm TAILQ_INSERT_BEFORE
823inserts the new element
824.Fa elm
825before the element
826.Fa listelm .
827.Pp
828The macro
829.Nm TAILQ_REMOVE
830removes the element
831.Fa elm
832from the tail queue.
833.Pp
834The macro
835.Nm TAILQ_EMPTY
836return true if the tail queue
837.Fa head
838has no elements.
839.Pp
840The macro
841.Nm TAILQ_FIRST
842returns the first element of the tail queue
843.Fa head .
844.Pp
845The macro
846.Nm TAILQ_FOREACH
847traverses the tail queue referenced by
848.Fa head
849in the forward direction, assigning each element in turn to
850.Fa var .
851.Pp
852The macro
853.Nm TAILQ_FOREACH_REVERSE
854traverses the tail queue referenced by
855.Fa head
856in the reverse direction, assigning each element in turn to
857.Fa var .
858.Pp
859The macro
860.Nm TAILQ_NEXT
861returns the element after the element
862.Fa elm .
863.Sh TAIL QUEUE EXAMPLE
864.Bd -literal
865TAILQ_HEAD(tailhead, entry) head;
866struct tailhead *headp;		/* Tail queue head. */
867struct entry {
868	...
869	TAILQ_ENTRY(entry) entries;	/* Tail queue. */
870	...
871} *n1, *n2, *np;
872
873TAILQ_INIT(\*[Am]head);			/* Initialize the queue. */
874
875n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
876TAILQ_INSERT_HEAD(\*[Am]head, n1, entries);
877
878n1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
879TAILQ_INSERT_TAIL(\*[Am]head, n1, entries);
880
881n2 = malloc(sizeof(struct entry));	/* Insert after. */
882TAILQ_INSERT_AFTER(\*[Am]head, n1, n2, entries);
883
884n2 = malloc(sizeof(struct entry));	/* Insert before. */
885TAILQ_INSERT_BEFORE(n1, n2, entries);
886					/* Forward traversal. */
887TAILQ_FOREACH(np, \*[Am]head, entries)
888	np-\*[Gt] ...
889					/* Reverse traversal. */
890TAILQ_FOREACH_REVERSE(np, \*[Am]head, tailhead, entries)
891	np-\*[Gt] ...
892					/* Delete. */
893while (TAILQ_FIRST(\*[Am]head) != NULL)
894	TAILQ_REMOVE(\*[Am]head, TAILQ_FIRST(\*[Am]head), entries);
895if (TAILQ_EMPTY(\*[Am]head))			/* Test for emptiness. */
896	printf("nothing to do\\n");
897.Ed
898.Sh CIRCULAR QUEUES
899A circular queue is headed by a structure defined by the
900.Nm CIRCLEQ_HEAD
901macro.
902This structure contains a pair of pointers,
903one to the first element in the circular queue and the other to the
904last element in the circular queue.
905The elements are doubly linked so that an arbitrary element can be
906removed without traversing the queue.
907New elements can be added to the queue after an existing element,
908before an existing element, at the head of the queue, or at the end
909of the queue.
910A
911.Fa CIRCLEQ_HEAD
912structure is declared as follows:
913.Bd -literal -offset indent
914CIRCLEQ_HEAD(HEADNAME, TYPE) head;
915.Ed
916.sp
917where
918.Li HEADNAME
919is the name of the structure to be defined, and
920.Li TYPE
921is the type of the elements to be linked into the circular queue.
922A pointer to the head of the circular queue can later be declared as:
923.Bd -literal -offset indent
924struct HEADNAME *headp;
925.Ed
926.sp
927(The names
928.Li head
929and
930.Li headp
931are user selectable.)
932.Pp
933The macro
934.Nm CIRCLEQ_ENTRY
935declares a structure that connects the elements in
936the circular queue.
937.Pp
938The macro
939.Nm CIRCLEQ_HEAD_INITIALIZER
940provides a value which can be used to initialize a circular queue head at
941compile time, and is used at the point that the circular queue head
942variable is declared, like:
943.Bd -literal -offset indent
944struct HEADNAME head = CIRCLEQ_HEAD_INITIALIZER(head);
945.Ed
946.Pp
947The macro
948.Nm CIRCLEQ_INIT
949initializes the circular queue referenced by
950.Fa head .
951.Pp
952The macro
953.Nm CIRCLEQ_INSERT_HEAD
954inserts the new element
955.Fa elm
956at the head of the circular queue.
957.Pp
958The macro
959.Nm CIRCLEQ_INSERT_TAIL
960inserts the new element
961.Fa elm
962at the end of the circular queue.
963.Pp
964The macro
965.Nm CIRCLEQ_INSERT_AFTER
966inserts the new element
967.Fa elm
968after the element
969.Fa listelm .
970.Pp
971The macro
972.Nm CIRCLEQ_INSERT_BEFORE
973inserts the new element
974.Fa elm
975before the element
976.Fa listelm .
977.Pp
978The macro
979.Nm CIRCLEQ_REMOVE
980removes the element
981.Fa elm
982from the circular queue.
983.Pp
984The macro
985.Nm CIRCLEQ_EMPTY
986return true if the circular queue
987.Fa head
988has no elements.
989.Pp
990The macro
991.Nm CIRCLEQ_FIRST
992returns the first element of the circular queue
993.Fa head .
994.Pp
995The macro
996.Nm CICRLEQ_FOREACH
997traverses the circle queue referenced by
998.Fa head
999in the forward direction, assigning each element in turn to
1000.Fa var .
1001.Pp
1002The macro
1003.Nm CICRLEQ_FOREACH_REVERSE
1004traverses the circle queue referenced by
1005.Fa head
1006in the reverse direction, assigning each element in turn to
1007.Fa var .
1008.Pp
1009The macro
1010.Nm CIRCLEQ_LAST
1011returns the last element of the circular queue
1012.Fa head .
1013.Pp
1014The macro
1015.Nm CIRCLEQ_NEXT
1016returns the element after the element
1017.Fa elm .
1018.Pp
1019The macro
1020.Nm CIRCLEQ_PREV
1021returns the element before the element
1022.Fa elm .
1023.Sh CIRCULAR QUEUE EXAMPLE
1024.Bd -literal
1025CIRCLEQ_HEAD(circleq, entry) head;
1026struct circleq *headp;			/* Circular queue head. */
1027struct entry {
1028	...
1029	CIRCLEQ_ENTRY entries;		/* Circular queue. */
1030	...
1031} *n1, *n2, *np;
1032
1033CIRCLEQ_INIT(\*[Am]head);			/* Initialize the circular queue. */
1034
1035n1 = malloc(sizeof(struct entry));	/* Insert at the head. */
1036CIRCLEQ_INSERT_HEAD(\*[Am]head, n1, entries);
1037
1038n1 = malloc(sizeof(struct entry));	/* Insert at the tail. */
1039CIRCLEQ_INSERT_TAIL(\*[Am]head, n1, entries);
1040
1041n2 = malloc(sizeof(struct entry));	/* Insert after. */
1042CIRCLEQ_INSERT_AFTER(\*[Am]head, n1, n2, entries);
1043
1044n2 = malloc(sizeof(struct entry));	/* Insert before. */
1045CIRCLEQ_INSERT_BEFORE(\*[Am]head, n1, n2, entries);
1046					/* Forward traversal. */
1047CIRCLEQ_FOREACH(np, \*[Am]head, entries)
1048	np-\*[Gt] ...
1049					/* Reverse traversal. */
1050CIRCLEQ_FOREACH_REVERSE(np, \*[Am]head, entries)
1051	np-\*[Gt] ...
1052					/* Delete. */
1053while (CIRCLEQ_FIRST(\*[Am]head) != (void *)\*[Am]head)
1054	CIRCLEQ_REMOVE(\*[Am]head, CIRCLEQ_FIRST(\*[Am]head), entries);
1055if (CIRCLEQ_EMPTY(\*[Am]head))		/* Test for emptiness. */
1056	printf("nothing to do\\n");
1057.Ed
1058.Sh HISTORY
1059The
1060.Nm queue
1061functions first appeared in
1062.Bx 4.4 .
1063The
1064.Nm SIMPLEQ
1065functions first appeared in
1066.Nx 1.2 .
1067