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