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