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