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