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