d9b0dafd9ad07f65606e19377afd97eddeca41e3
[lemu] / bsd_queue.3
1 .\" $OpenBSD: queue.3,v 1.68 2020/12/30 13:33:38 millert Exp $
2 .\" $NetBSD: queue.3,v 1.4 1995/07/03 00:25:36 mycroft Exp $
3 .\"
4 .\" Copyright (c) 1993 The Regents of the University of California.
5 .\" All rights reserved.
6 .\"
7 .\" Redistribution and use in source and binary forms, with or without
8 .\" modification, are permitted provided that the following conditions
9 .\" are met:
10 .\" 1. Redistributions of source code must retain the above copyright
11 .\" notice, this list of conditions and the following disclaimer.
12 .\" 2. Redistributions in binary form must reproduce the above copyright
13 .\" notice, this list of conditions and the following disclaimer in the
14 .\" documentation and/or other materials provided with the distribution.
15 .\" 3. Neither the name of the University nor the names of its contributors
16 .\" may be used to endorse or promote products derived from this software
17 .\" without specific prior written permission.
18 .\"
19 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 .\" SUCH DAMAGE.
30 .\"
31 .\" @(#)queue.3 8.1 (Berkeley) 12/13/93
32 .\"
33 .Dd $Mdocdate: December 30 2020 $
34 .Dt SLIST_INIT 3
35 .Os
36 .Sh NAME
37 .Nm SLIST_ENTRY ,
38 .Nm SLIST_HEAD ,
39 .Nm SLIST_HEAD_INITIALIZER ,
40 .Nm SLIST_FIRST ,
41 .Nm SLIST_NEXT ,
42 .Nm SLIST_EMPTY ,
43 .Nm SLIST_FOREACH ,
44 .Nm SLIST_FOREACH_SAFE ,
45 .Nm SLIST_INIT ,
46 .Nm SLIST_INSERT_AFTER ,
47 .Nm SLIST_INSERT_HEAD ,
48 .Nm SLIST_REMOVE_AFTER ,
49 .Nm SLIST_REMOVE_HEAD ,
50 .Nm SLIST_REMOVE ,
51 .Nm LIST_ENTRY ,
52 .Nm LIST_HEAD ,
53 .Nm LIST_HEAD_INITIALIZER ,
54 .Nm LIST_FIRST ,
55 .Nm LIST_NEXT ,
56 .Nm LIST_EMPTY ,
57 .Nm LIST_FOREACH ,
58 .Nm LIST_FOREACH_SAFE ,
59 .Nm LIST_INIT ,
60 .Nm LIST_INSERT_AFTER ,
61 .Nm LIST_INSERT_BEFORE ,
62 .Nm LIST_INSERT_HEAD ,
63 .Nm LIST_REMOVE ,
64 .Nm LIST_REPLACE ,
65 .Nm SIMPLEQ_ENTRY ,
66 .Nm SIMPLEQ_HEAD ,
67 .Nm SIMPLEQ_HEAD_INITIALIZER ,
68 .Nm SIMPLEQ_FIRST ,
69 .Nm SIMPLEQ_NEXT ,
70 .Nm SIMPLEQ_EMPTY ,
71 .Nm SIMPLEQ_FOREACH ,
72 .Nm SIMPLEQ_FOREACH_SAFE ,
73 .Nm SIMPLEQ_INIT ,
74 .Nm SIMPLEQ_INSERT_AFTER ,
75 .Nm SIMPLEQ_INSERT_HEAD ,
76 .Nm SIMPLEQ_INSERT_TAIL ,
77 .Nm SIMPLEQ_REMOVE_AFTER ,
78 .Nm SIMPLEQ_REMOVE_HEAD ,
79 .Nm SIMPLEQ_CONCAT ,
80 .Nm STAILQ_ENTRY ,
81 .Nm STAILQ_HEAD ,
82 .Nm STAILQ_HEAD_INITIALIZER ,
83 .Nm STAILQ_FIRST ,
84 .Nm STAILQ_NEXT ,
85 .Nm STAILQ_LAST ,
86 .Nm STAILQ_EMPTY ,
87 .Nm STAILQ_FOREACH ,
88 .Nm STAILQ_FOREACH_SAFE ,
89 .Nm STAILQ_INIT ,
90 .Nm STAILQ_INSERT_AFTER ,
91 .Nm STAILQ_INSERT_HEAD ,
92 .Nm STAILQ_INSERT_TAIL ,
93 .Nm STAILQ_REMOVE ,
94 .Nm STAILQ_REMOVE_AFTER ,
95 .Nm STAILQ_REMOVE_HEAD ,
96 .Nm STAILQ_CONCAT ,
97 .Nm TAILQ_ENTRY ,
98 .Nm TAILQ_HEAD ,
99 .Nm TAILQ_HEAD_INITIALIZER ,
100 .Nm TAILQ_FIRST ,
101 .Nm TAILQ_NEXT ,
102 .Nm TAILQ_LAST ,
103 .Nm TAILQ_PREV ,
104 .Nm TAILQ_EMPTY ,
105 .Nm TAILQ_FOREACH ,
106 .Nm TAILQ_FOREACH_SAFE ,
107 .Nm TAILQ_FOREACH_REVERSE ,
108 .Nm TAILQ_FOREACH_REVERSE_SAFE ,
109 .Nm TAILQ_INIT ,
110 .Nm TAILQ_INSERT_AFTER ,
111 .Nm TAILQ_INSERT_BEFORE ,
112 .Nm TAILQ_INSERT_HEAD ,
113 .Nm TAILQ_INSERT_TAIL ,
114 .Nm TAILQ_REMOVE ,
115 .Nm TAILQ_REPLACE ,
116 .Nm TAILQ_CONCAT
117 .Nd intrusive singly-linked and doubly-linked lists, simple queues, singly-linked and doubly-linked tail queues
118 .Sh SYNOPSIS
119 .In sys/queue.h
120 .Pp
121 .Fn SLIST_ENTRY "TYPE"
122 .Fn SLIST_HEAD "HEADNAME" "TYPE"
123 .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head"
124 .Ft "struct TYPE *"
125 .Fn SLIST_FIRST "SLIST_HEAD *head"
126 .Ft "struct TYPE *"
127 .Fn SLIST_NEXT "struct TYPE *listelm" "FIELDNAME"
128 .Ft int
129 .Fn SLIST_EMPTY "SLIST_HEAD *head"
130 .Fn SLIST_FOREACH "VARNAME" "SLIST_HEAD *head" "FIELDNAME"
131 .Fn SLIST_FOREACH_SAFE "VARNAME" "SLIST_HEAD *head" "FIELDNAME" "TEMP_VARNAME"
132 .Ft void
133 .Fn SLIST_INIT "SLIST_HEAD *head"
134 .Ft void
135 .Fn SLIST_INSERT_AFTER "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME"
136 .Ft void
137 .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "struct TYPE *elm" "FIELDNAME"
138 .Ft void
139 .Fn SLIST_REMOVE_AFTER "struct TYPE *elm" "FIELDNAME"
140 .Ft void
141 .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "FIELDNAME"
142 .Ft void
143 .Fn SLIST_REMOVE "SLIST_HEAD *head" "struct TYPE *elm" "TYPE" "FIELDNAME"
144 .Pp
145 .Fn LIST_ENTRY "TYPE"
146 .Fn LIST_HEAD "HEADNAME" "TYPE"
147 .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head"
148 .Ft "struct TYPE *"
149 .Fn LIST_FIRST "LIST_HEAD *head"
150 .Ft "struct TYPE *"
151 .Fn LIST_NEXT "struct TYPE *listelm" "FIELDNAME"
152 .Ft int
153 .Fn LIST_EMPTY "LIST_HEAD *head"
154 .Fn LIST_FOREACH "VARNAME" "LIST_HEAD *head" "FIELDNAME"
155 .Fn LIST_FOREACH_SAFE "VARNAME" "LIST_HEAD *head" "FIELDNAME" "TEMP_VARNAME"
156 .Ft void
157 .Fn LIST_INIT "LIST_HEAD *head"
158 .Ft void
159 .Fn LIST_INSERT_AFTER "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME"
160 .Ft void
161 .Fn LIST_INSERT_BEFORE "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME"
162 .Ft void
163 .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "struct TYPE *elm" "FIELDNAME"
164 .Ft void
165 .Fn LIST_REMOVE "struct TYPE *elm" "FIELDNAME"
166 .Ft void
167 .Fn LIST_REPLACE "struct TYPE *elm" "struct TYPE *elm2" "FIELDNAME"
168 .Pp
169 .Fn SIMPLEQ_ENTRY "TYPE"
170 .Fn SIMPLEQ_HEAD "HEADNAME" "TYPE"
171 .Fn SIMPLEQ_HEAD_INITIALIZER "SIMPLEQ_HEAD head"
172 .Ft "struct TYPE *"
173 .Fn SIMPLEQ_FIRST "SIMPLEQ_HEAD *head"
174 .Ft "struct TYPE *"
175 .Fn SIMPLEQ_NEXT "struct TYPE *listelm" "FIELDNAME"
176 .Ft int
177 .Fn SIMPLEQ_EMPTY "SIMPLEQ_HEAD *head"
178 .Fn SIMPLEQ_FOREACH "VARNAME" "SIMPLEQ_HEAD *head" "FIELDNAME"
179 .Fn SIMPLEQ_FOREACH_SAFE "VARNAME" "SIMPLEQ_HEAD *head" "FIELDNAME" "TEMP_VARNAME"
180 .Ft void
181 .Fn SIMPLEQ_INIT "SIMPLEQ_HEAD *head"
182 .Ft void
183 .Fn SIMPLEQ_INSERT_AFTER "SIMPLEQ_HEAD *head" "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME"
184 .Ft void
185 .Fn SIMPLEQ_INSERT_HEAD "SIMPLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
186 .Ft void
187 .Fn SIMPLEQ_INSERT_TAIL "SIMPLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
188 .Ft void
189 .Fn SIMPLEQ_REMOVE_AFTER "SIMPLEQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
190 .Ft void
191 .Fn SIMPLEQ_REMOVE_HEAD "SIMPLEQ_HEAD *head" "FIELDNAME"
192 .Fn SIMPLEQ_CONCAT "SIMPLEQ_HEAD *head1" "SIMPLEQ_HEAD *head2"
193 .Pp
194 .Fn STAILQ_ENTRY "TYPE"
195 .Fn STAILQ_HEAD "HEADNAME" "TYPE"
196 .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head"
197 .Fn STAILQ_FIRST "STAILQ_HEAD *head"
198 .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME"
199 .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
200 .Fn STAILQ_EMPTY "STAILQ_HEAD *head"
201 .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
202 .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var"
203 .Fn STAILQ_INIT "STAILQ_HEAD *head"
204 .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME"
205 .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
206 .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
207 .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME"
208 .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME"
209 .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME"
210 .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2"
211 .Pp
212 .Fn TAILQ_ENTRY "TYPE"
213 .Fn TAILQ_HEAD "HEADNAME" "TYPE"
214 .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head"
215 .Ft "struct TYPE *"
216 .Fn TAILQ_FIRST "TAILQ_HEAD *head"
217 .Ft "struct TYPE *"
218 .Fn TAILQ_NEXT "struct TYPE *listelm" "FIELDNAME"
219 .Ft "struct TYPE *"
220 .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME"
221 .Ft "struct TYPE *"
222 .Fn TAILQ_PREV "struct TYPE *listelm" "HEADNAME" "FIELDNAME"
223 .Ft int
224 .Fn TAILQ_EMPTY "TAILQ_HEAD *head"
225 .Fn TAILQ_FOREACH "VARNAME" "TAILQ_HEAD *head" "FIELDNAME"
226 .Fn TAILQ_FOREACH_SAFE "VARNAME" "TAILQ_HEAD *head" "FIELDNAME" "TEMP_VARNAME"
227 .Fn TAILQ_FOREACH_REVERSE "VARNAME" "TAILQ_HEAD *head" "HEADNAME" "FIELDNAME"
228 .Fn TAILQ_FOREACH_REVERSE_SAFE "VARNAME" "TAILQ_HEAD *head" "HEADNAME" "FIELDNAME" "TEMP_VARNAME"
229 .Ft void
230 .Fn TAILQ_INIT "TAILQ_HEAD *head"
231 .Ft void
232 .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME"
233 .Ft void
234 .Fn TAILQ_INSERT_BEFORE "struct TYPE *listelm" "struct TYPE *elm" "FIELDNAME"
235 .Ft void
236 .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
237 .Ft void
238 .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
239 .Ft void
240 .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "struct TYPE *elm" "FIELDNAME"
241 .Ft void
242 .Fn TAILQ_REPLACE "TAILQ_HEAD *head" "struct TYPE *elm" "struct TYPE *elm2" "FIELDNAME"
243 .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "FIELDNAME"
244 .Sh DESCRIPTION
245 These macros define and operate on five types of data structures:
246 singly-linked lists, simple queues, lists, singly-linked tail queues,
247 and tail queues.
248 All five structures support the following functionality:
249 .Pp
250 .Bl -enum -compact -offset indent
251 .It
252 Insertion of a new entry at the head of the list.
253 .It
254 Insertion of a new entry after any element in the list.
255 .It
256 Removal of an entry from the head of the list.
257 .It
258 Forward traversal through the list.
259 .El
260 .Pp
261 The following table provides a quick overview
262 of which types support which additional macros:
263 .Bl -column -offset 6n "LAST, PREV, FOREACH_REVERSE" SLIST LIST SIMPLEQ STAILQ TAILQ
264 .It LAST, PREV, FOREACH_REVERSE Ta - Ta - Ta - Ta - Ta TAILQ
265 .It INSERT_BEFORE, REPLACE Ta - Ta LIST Ta - Ta - Ta TAILQ
266 .It INSERT_TAIL, CONCAT Ta - Ta - Ta SIMPLEQ Ta STAILQ Ta TAILQ
267 .It REMOVE_AFTER, REMOVE_HEAD Ta SLIST Ta - Ta SIMPLEQ Ta STAILQ Ta -
268 .It REMOVE Ta SLIST Ta LIST Ta - Ta STAILQ Ta TAILQ
269 .El
270 .Pp
271 Singly-linked lists are the simplest of the five data structures
272 and support only the above functionality.
273 Singly-linked lists are ideal for applications with large datasets
274 and few or no removals, or for implementing a LIFO queue.
275 .Pp
276 Simple queues and singly-linked tail queues add the following functionality:
277 .Pp
278 .Bl -enum -compact -offset indent
279 .It
280 Entries can be added at the end of a list.
281 .El
282 .Pp
283 However:
284 .Pp
285 .Bl -enum -compact -offset indent
286 .It
287 All list insertions must specify the head of the list.
288 .It
289 Each head entry requires two pointers rather than one.
290 .It
291 Code size is about 15% greater and operations run about 20% slower
292 than singly-linked lists.
293 .El
294 .Pp
295 Simple queues and singly-linked tail queues are ideal for applications with
296 large datasets and few or no removals, or for implementing a FIFO queue.
297 .Pp
298 All doubly linked types of data structures (lists and tail queues)
299 additionally allow:
300 .Pp
301 .Bl -enum -compact -offset indent
302 .It
303 Insertion of a new entry before any element in the list.
304 .It
305 Removal of any entry in the list.
306 .El
307 .Pp
308 However:
309 .Pp
310 .Bl -enum -compact -offset indent
311 .It
312 Each element requires two pointers rather than one.
313 .It
314 Code size and execution time of operations (except for removal) is about
315 twice that of the singly-linked data-structures.
316 .El
317 .Pp
318 Lists are the simplest of the doubly linked data structures and support
319 only the above functionality over singly-linked lists.
320 .Pp
321 Tail queues add the following functionality:
322 .Pp
323 .Bl -enum -compact -offset indent
324 .It
325 Entries can be added at the end of a list.
326 .It
327 They may be traversed backwards, at a cost.
328 .El
329 .Pp
330 However:
331 .Pp
332 .Bl -enum -compact -offset indent
333 .It
334 All list insertions and removals must specify the head of the list.
335 .It
336 Each head entry requires two pointers rather than one.
337 .It
338 Code size is about 15% greater and operations run about 20% slower
339 than singly-linked lists.
340 .El
341 .Pp
342 An additional type of data structure, circular queues, violated the C
343 language aliasing rules and were miscompiled as a result.
344 All code using them should be converted to another structure;
345 tail queues are usually the easiest to convert to.
346 .Pp
347 All these lists and queues are intrusive: they link together user
348 defined structures containing a field of type
349 .Li SLIST_ENTRY ,
350 .Li LIST_ENTRY ,
351 .Li SIMPLEQ_ENTRY ,
352 .Li STAILQ_ENTRY ,
353 or
354 .Li TAILQ_ENTRY .
355 In the macro definitions,
356 .Fa TYPE
357 is the name tag of the user defined structure and
358 .Fa FIELDNAME
359 is the name of the
360 .Li *_ENTRY
361 field.
362 If an instance of the user defined structure needs to be a member of
363 multiple lists at the same time, the structure requires multiple
364 .Li *_ENTRY
365 fields, one for each list.
366 .Pp
367 The argument
368 .Fa HEADNAME
369 is the name tag of a user defined structure that must be declared
370 using the macros
371 .Fn SLIST_HEAD ,
372 .Fn LIST_HEAD ,
373 .Fn SIMPLEQ_HEAD ,
374 .Fn STAILQ_HEAD ,
375 or
376 .Fn TAILQ_HEAD .
377 See the examples below for further explanation of how these macros are used.
378 .Sh SINGLY-LINKED LISTS
379 A singly-linked list is headed by a structure defined by the
380 .Fn SLIST_HEAD
381 macro.
382 This structure contains a single pointer to the first element on the list.
383 The elements are singly linked for minimum space and pointer manipulation
384 overhead at the expense of O(n) removal for arbitrary elements.
385 New elements can be added to the list after an existing element or
386 at the head of the list.
387 A
388 .Fa SLIST_HEAD
389 structure is declared as follows:
390 .Bd -literal -offset indent
391 SLIST_HEAD(HEADNAME, TYPE) head;
392 .Ed
393 .Pp
394 where
395 .Fa HEADNAME
396 is the name of the structure to be defined, and struct
397 .Fa TYPE
398 is the type of the elements to be linked into the list.
399 A pointer to the head of the list can later be declared as:
400 .Bd -literal -offset indent
401 struct HEADNAME *headp;
402 .Ed
403 .Pp
404 (The names
405 .Li head
406 and
407 .Li headp
408 are user selectable.)
409 .Pp
410 The
411 .Fa HEADNAME
412 facility is often not used, leading to the following bizarre code:
413 .Bd -literal -offset indent
414 SLIST_HEAD(, TYPE) head, *headp;
415 .Ed
416 .Pp
417 The
418 .Fn SLIST_ENTRY
419 macro declares a structure that connects the elements in the list.
420 .Pp
421 The
422 .Fn SLIST_INIT
423 macro initializes the list referenced by
424 .Fa head .
425 .Pp
426 The list can also be initialized statically by using the
427 .Fn SLIST_HEAD_INITIALIZER
428 macro like this:
429 .Bd -literal -offset indent
430 SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head);
431 .Ed
432 .Pp
433 The
434 .Fn SLIST_INSERT_HEAD
435 macro inserts the new element
436 .Fa elm
437 at the head of the list.
438 .Pp
439 The
440 .Fn SLIST_INSERT_AFTER
441 macro inserts the new element
442 .Fa elm
443 after the element
444 .Fa listelm .
445 .Pp
446 The
447 .Fn SLIST_REMOVE_HEAD
448 macro removes the first element of the list pointed by
449 .Fa head .
450 .Pp
451 The
452 .Fn SLIST_REMOVE_AFTER
453 macro removes the list element immediately following
454 .Fa elm .
455 .Pp
456 The
457 .Fn SLIST_REMOVE
458 macro removes the element
459 .Fa elm
460 of the list pointed by
461 .Fa head .
462 .Pp
463 The
464 .Fn SLIST_FIRST
465 and
466 .Fn SLIST_NEXT
467 macros can be used to traverse the list:
468 .Bd -literal -offset indent
469 for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, FIELDNAME))
470 .Ed
471 .Pp
472 Or, for simplicity, one can use the
473 .Fn SLIST_FOREACH
474 macro:
475 .Bd -literal -offset indent
476 SLIST_FOREACH(np, head, FIELDNAME)
477 .Ed
478 .Pp
479 The macro
480 .Fn SLIST_FOREACH_SAFE
481 traverses the list referenced by head in a
482 forward direction, assigning each element in turn to var.
483 However, unlike
484 .Fn SLIST_FOREACH
485 it is permitted to remove var as well
486 as free it from within the loop safely without interfering with the traversal.
487 .Pp
488 The
489 .Fn SLIST_EMPTY
490 macro should be used to check whether a simple list is empty.
491 .Sh SINGLY-LINKED LIST EXAMPLE
492 .Bd -literal
493 SLIST_HEAD(listhead, entry) head;
494 struct entry {
495 ...
496 SLIST_ENTRY(entry) entries; /* Simple list. */
497 ...
498 } *n1, *n2, *np;
499
500 SLIST_INIT(&head); /* Initialize simple list. */
501
502 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
503 SLIST_INSERT_HEAD(&head, n1, entries);
504
505 n2 = malloc(sizeof(struct entry)); /* Insert after. */
506 SLIST_INSERT_AFTER(n1, n2, entries);
507
508 SLIST_FOREACH(np, &head, entries) /* Forward traversal. */
509 np-> ...
510
511 while (!SLIST_EMPTY(&head)) { /* Delete. */
512 n1 = SLIST_FIRST(&head);
513 SLIST_REMOVE_HEAD(&head, entries);
514 free(n1);
515 }
516
517 .Ed
518 .Sh LISTS
519 A list is headed by a structure defined by the
520 .Fn LIST_HEAD
521 macro.
522 This structure contains a single pointer to the first element on the list.
523 The elements are doubly linked so that an arbitrary element can be
524 removed without traversing the list.
525 New elements can be added to the list after an existing element,
526 before an existing element, or at the head of the list.
527 A
528 .Fa LIST_HEAD
529 structure is declared as follows:
530 .Bd -literal -offset indent
531 LIST_HEAD(HEADNAME, TYPE) head;
532 .Ed
533 .Pp
534 where
535 .Fa HEADNAME
536 is the name of the structure to be defined, and struct
537 .Fa TYPE
538 is the type of the elements to be linked into the list.
539 A pointer to the head of the list can later be declared as:
540 .Bd -literal -offset indent
541 struct HEADNAME *headp;
542 .Ed
543 .Pp
544 (The names
545 .Li head
546 and
547 .Li headp
548 are user selectable.)
549 .Pp
550 The
551 .Fa HEADNAME
552 facility is often not used, leading to the following bizarre code:
553 .Bd -literal -offset indent
554 LIST_HEAD(, TYPE) head, *headp;
555 .Ed
556 .Pp
557 The
558 .Fn LIST_ENTRY
559 macro declares a structure that connects the elements in the list.
560 .Pp
561 The
562 .Fn LIST_INIT
563 macro initializes the list referenced by
564 .Fa head .
565 .Pp
566 The list can also be initialized statically by using the
567 .Fn LIST_HEAD_INITIALIZER
568 macro like this:
569 .Bd -literal -offset indent
570 LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head);
571 .Ed
572 .Pp
573 The
574 .Fn LIST_INSERT_HEAD
575 macro inserts the new element
576 .Fa elm
577 at the head of the list.
578 .Pp
579 The
580 .Fn LIST_INSERT_AFTER
581 macro inserts the new element
582 .Fa elm
583 after the element
584 .Fa listelm .
585 .Pp
586 The
587 .Fn LIST_INSERT_BEFORE
588 macro inserts the new element
589 .Fa elm
590 before the element
591 .Fa listelm .
592 .Pp
593 The
594 .Fn LIST_REMOVE
595 macro removes the element
596 .Fa elm
597 from the list.
598 .Pp
599 The
600 .Fn LIST_REPLACE
601 macro replaces the list element
602 .Fa elm
603 with the new element
604 .Fa elm2 .
605 .Pp
606 The
607 .Fn LIST_FIRST
608 and
609 .Fn LIST_NEXT
610 macros can be used to traverse the list:
611 .Bd -literal -offset indent
612 for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, FIELDNAME))
613 .Ed
614 .Pp
615 Or, for simplicity, one can use the
616 .Fn LIST_FOREACH
617 macro:
618 .Bd -literal -offset indent
619 LIST_FOREACH(np, head, FIELDNAME)
620 .Ed
621 .Pp
622 The macro
623 .Fn LIST_FOREACH_SAFE
624 traverses the list referenced by head in a
625 forward direction, assigning each element in turn to var.
626 However, unlike
627 .Fn LIST_FOREACH
628 it is permitted to remove var as well
629 as free it from within the loop safely without interfering with the traversal.
630 .Pp
631 The
632 .Fn LIST_EMPTY
633 macro should be used to check whether a list is empty.
634 .Sh LIST EXAMPLE
635 .Bd -literal
636 LIST_HEAD(listhead, entry) head;
637 struct entry {
638 ...
639 LIST_ENTRY(entry) entries; /* List. */
640 ...
641 } *n1, *n2, *np;
642
643 LIST_INIT(&head); /* Initialize list. */
644
645 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
646 LIST_INSERT_HEAD(&head, n1, entries);
647
648 n2 = malloc(sizeof(struct entry)); /* Insert after. */
649 LIST_INSERT_AFTER(n1, n2, entries);
650
651 n2 = malloc(sizeof(struct entry)); /* Insert before. */
652 LIST_INSERT_BEFORE(n1, n2, entries);
653 /* Forward traversal. */
654 LIST_FOREACH(np, &head, entries)
655 np-> ...
656
657 while (!LIST_EMPTY(&head)) { /* Delete. */
658 n1 = LIST_FIRST(&head);
659 LIST_REMOVE(n1, entries);
660 free(n1);
661 }
662 .Ed
663 .Sh SIMPLE QUEUES
664 A simple queue is headed by a structure defined by the
665 .Fn SIMPLEQ_HEAD
666 macro.
667 This structure contains a pair of pointers, one to the first element in the
668 simple queue and the other to the last element in the simple queue.
669 The elements are singly linked.
670 New elements can be added to the queue after an existing element,
671 at the head of the queue or at the tail of the queue.
672 A
673 .Fa SIMPLEQ_HEAD
674 structure is declared as follows:
675 .Bd -literal -offset indent
676 SIMPLEQ_HEAD(HEADNAME, TYPE) head;
677 .Ed
678 .Pp
679 where
680 .Fa HEADNAME
681 is the name of the structure to be defined, and struct
682 .Fa TYPE
683 is the type of the elements to be linked into the queue.
684 A pointer to the head of the queue can later be declared as:
685 .Bd -literal -offset indent
686 struct HEADNAME *headp;
687 .Ed
688 .Pp
689 (The names
690 .Li head
691 and
692 .Li headp
693 are user selectable.)
694 .Pp
695 The
696 .Fn SIMPLEQ_ENTRY
697 macro declares a structure that connects the elements in
698 the queue.
699 .Pp
700 The
701 .Fn SIMPLEQ_INIT
702 macro initializes the queue referenced by
703 .Fa head .
704 .Pp
705 The queue can also be initialized statically by using the
706 .Fn SIMPLEQ_HEAD_INITIALIZER
707 macro like this:
708 .Bd -literal -offset indent
709 SIMPLEQ_HEAD(HEADNAME, TYPE) head = SIMPLEQ_HEAD_INITIALIZER(head);
710 .Ed
711 .Pp
712 The
713 .Fn SIMPLEQ_INSERT_AFTER
714 macro inserts the new element
715 .Fa elm
716 after the element
717 .Fa listelm .
718 .Pp
719 The
720 .Fn SIMPLEQ_INSERT_HEAD
721 macro inserts the new element
722 .Fa elm
723 at the head of the queue.
724 .Pp
725 The
726 .Fn SIMPLEQ_INSERT_TAIL
727 macro inserts the new element
728 .Fa elm
729 at the end of the queue.
730 .Pp
731 The
732 .Fn SIMPLEQ_REMOVE_AFTER
733 macro removes the queue element immediately following
734 .Fa elm .
735 .Pp
736 The
737 .Fn SIMPLEQ_REMOVE_HEAD
738 macro removes the first element
739 from the queue.
740 .Pp
741 The
742 .Fn SIMPLEQ_CONCAT
743 macro concatenates all the elements of the queue referenced by
744 .Fa head2
745 to the end of the queue referenced by
746 .Fa head1 ,
747 emptying
748 .Fa head2
749 in the process.
750 This is more efficient than removing and inserting the individual elements
751 as it does not actually traverse
752 .Fa head2 .
753 .Pp
754 The
755 .Fn SIMPLEQ_FIRST
756 and
757 .Fn SIMPLEQ_NEXT
758 macros can be used to traverse the queue.
759 The
760 .Fn SIMPLEQ_FOREACH
761 is used for queue traversal:
762 .Bd -literal -offset indent
763 SIMPLEQ_FOREACH(np, head, FIELDNAME)
764 .Ed
765 .Pp
766 The macro
767 .Fn SIMPLEQ_FOREACH_SAFE
768 traverses the queue referenced by head in a
769 forward direction, assigning each element in turn to var.
770 However, unlike
771 .Fn SIMPLEQ_FOREACH
772 it is permitted to remove var as well
773 as free it from within the loop safely without interfering with the traversal.
774 .Pp
775 The
776 .Fn SIMPLEQ_EMPTY
777 macro should be used to check whether a list is empty.
778 .Sh SIMPLE QUEUE EXAMPLE
779 .Bd -literal
780 SIMPLEQ_HEAD(listhead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head);
781 struct entry {
782 ...
783 SIMPLEQ_ENTRY(entry) entries; /* Simple queue. */
784 ...
785 } *n1, *n2, *np;
786
787 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
788 SIMPLEQ_INSERT_HEAD(&head, n1, entries);
789
790 n2 = malloc(sizeof(struct entry)); /* Insert after. */
791 SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries);
792
793 n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */
794 SIMPLEQ_INSERT_TAIL(&head, n2, entries);
795 /* Forward traversal. */
796 SIMPLEQ_FOREACH(np, &head, entries)
797 np-> ...
798 /* Delete. */
799 while (!SIMPLEQ_EMPTY(&head)) {
800 n1 = SIMPLEQ_FIRST(&head);
801 SIMPLEQ_REMOVE_HEAD(&head, entries);
802 free(n1);
803 }
804 .Ed
805 .Sh SINGLY-LINKED TAIL QUEUES
806 A singly-linked tail queue is headed by a structure defined by the
807 .Fn STAILQ_HEAD
808 macro.
809 This structure contains a pair of pointers, one to the first element in
810 the tail queue and the other to the last element in the tail queue.
811 The elements are singly linked for minimum space and pointer manipulation
812 overhead at the expense of O(n) removal for arbitrary elements.
813 New elements can be added to the tail queue after an existing element,
814 at the head of the tail queue or at the end of the tail queue.
815 A
816 .Fa STAILQ_HEAD
817 structure is declared as follows:
818 .Bd -literal -offset indent
819 STAILQ_HEAD(HEADNAME, TYPE) head;
820 .Ed
821 .Pp
822 where
823 .Fa HEADNAME
824 is the name of the structure to be defined, and struct
825 .Fa TYPE
826 is the type of the elements to be linked into the tail queue.
827 A pointer to the head of the tail queue can later be declared as:
828 .Bd -literal -offset indent
829 struct HEADNAME *headp;
830 .Ed
831 .Pp
832 (The names
833 .Li head
834 and
835 .Li headp
836 are user selectable.)
837 .Pp
838 The
839 .Fn STAILQ_ENTRY
840 macro declares a structure that connects the elements in
841 the tail queue.
842 .Pp
843 The
844 .Fn STAILQ_INIT
845 macro initializes the tail queue referenced by
846 .Fa head .
847 .Pp
848 The tail queue can also be initialized statically by using the
849 .Fn STAILQ_HEAD_INITIALIZER
850 macro like this:
851 .Bd -literal -offset indent
852 STAILQ_HEAD(HEADNAME, TYPE) head = STAILQ_HEAD_INITIALIZER(head);
853 .Ed
854 .Pp
855 The
856 .Fn STAILQ_INSERT_AFTER
857 macro inserts the new element
858 .Fa elm
859 after the element
860 .Fa listelm .
861 .Pp
862 The
863 .Fn STAILQ_INSERT_HEAD
864 macro inserts the new element
865 .Fa elm
866 at the head of the tail queue.
867 .Pp
868 The
869 .Fn STAILQ_INSERT_TAIL
870 macro inserts the new element
871 .Fa elm
872 at the end of the tail queue.
873 .Pp
874 The
875 .Fn STAILQ_REMOVE_AFTER
876 macro removes the queue element immediately following
877 .Fa elm .
878 Unlike
879 .Fa STAILQ_REMOVE ,
880 this macro does not traverse the entire tail queue.
881 .Pp
882 The
883 .Fn STAILQ_REMOVE_HEAD
884 macro removes the first element
885 from the tail queue.
886 For optimum efficiency,
887 elements being removed from the head of the tail queue should
888 use this macro explicitly rather than the generic
889 .Fa STAILQ_REMOVE
890 macro.
891 .Pp
892 The
893 .Fn STAILQ_REMOVE
894 macro removes the element
895 .Fa elm
896 from the tail queue.
897 Use of this macro should be avoided as it traverses the entire list.
898 A doubly-linked tail queue should be used if this macro is needed in
899 high-usage code paths or to operate on long tail queues.
900 .Pp
901 The
902 .Fn STAILQ_CONCAT
903 macro concatenates all the elements of the tail queue referenced by
904 .Fa head2
905 to the end of the tail queue referenced by
906 .Fa head1 ,
907 emptying
908 .Fa head2
909 in the process.
910 This is more efficient than removing and inserting the individual elements
911 as it does not actually traverse
912 .Fa head2 .
913 .Pp
914 The
915 .Fn STAILQ_FOREACH
916 is used for queue traversal:
917 .Bd -literal -offset indent
918 STAILQ_FOREACH(np, head, FIELDNAME)
919 .Ed
920 .Pp
921 The macro
922 .Fn STAILQ_FOREACH_SAFE
923 traverses the queue referenced by head in a
924 forward direction, assigning each element in turn to var.
925 However, unlike
926 .Fn STAILQ_FOREACH
927 it is permitted to remove var as well
928 as free it from within the loop safely without interfering with the traversal.
929 .Pp
930 The
931 .Fn STAILQ_FIRST
932 .Fn STAILQ_NEXT ,
933 and
934 .Fn STAILQ_LAST
935 macros can be used to manually traverse a tail queue or an arbitrary part of
936 one.
937 The
938 .Fn STAILQ_EMPTY
939 macro should be used to check whether a tail queue is empty.
940 .Sh SINGLY-LINKED TAIL QUEUE EXAMPLE
941 .Bd -literal
942 STAILQ_HEAD(listhead, entry) head = STAILQ_HEAD_INITIALIZER(head);
943 struct entry {
944 ...
945 STAILQ_ENTRY(entry) entries; /* Singly-linked tail queue. */
946 ...
947 } *n1, *n2, *np;
948
949 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
950 STAILQ_INSERT_HEAD(&head, n1, entries);
951
952 n2 = malloc(sizeof(struct entry)); /* Insert at the tail. */
953 STAILQ_INSERT_TAIL(&head, n2, entries);
954
955 n2 = malloc(sizeof(struct entry)); /* Insert after. */
956 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
957
958 /* Deletion. */
959 STAILQ_REMOVE(&head, n2, entry, entries);
960 free(n2);
961 /* Deletion from the head. */
962 n3 = STAILQ_FIRST(&head);
963 STAILQ_REMOVE_HEAD(&head, entries);
964 free(n3);
965 /* Forward traversal. */
966 STAILQ_FOREACH(np, &head, entries)
967 np-> ...
968 /* Safe forward traversal. */
969 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
970 np-> ...
971 STAILQ_REMOVE(&head, np, entry, entries);
972 free(np);
973 }
974 /* Delete. */
975 while (!STAILQ_EMPTY(&head)) {
976 n1 = STAILQ_FIRST(&head);
977 STAILQ_REMOVE_HEAD(&head, entries);
978 free(n1);
979 }
980 .Ed
981 .Sh TAIL QUEUES
982 A tail queue is headed by a structure defined by the
983 .Fn TAILQ_HEAD
984 macro.
985 This structure contains a pair of pointers,
986 one to the first element in the tail queue and the other to
987 the last element in the tail queue.
988 The elements are doubly linked so that an arbitrary element can be
989 removed without traversing the tail queue.
990 New elements can be added to the queue after an existing element,
991 before an existing element, at the head of the queue, or at the end
992 of the queue.
993 A
994 .Fa TAILQ_HEAD
995 structure is declared as follows:
996 .Bd -literal -offset indent
997 TAILQ_HEAD(HEADNAME, TYPE) head;
998 .Ed
999 .Pp
1000 where
1001 .Fa HEADNAME
1002 is the name of the structure to be defined, and struct
1003 .Fa TYPE
1004 is the type of the elements to be linked into the tail queue.
1005 A pointer to the head of the tail queue can later be declared as:
1006 .Bd -literal -offset indent
1007 struct HEADNAME *headp;
1008 .Ed
1009 .Pp
1010 (The names
1011 .Li head
1012 and
1013 .Li headp
1014 are user selectable.)
1015 .Pp
1016 The
1017 .Fn TAILQ_ENTRY
1018 macro declares a structure that connects the elements in
1019 the tail queue.
1020 .Pp
1021 The
1022 .Fn TAILQ_INIT
1023 macro initializes the tail queue referenced by
1024 .Fa head .
1025 .Pp
1026 The tail queue can also be initialized statically by using the
1027 .Fn TAILQ_HEAD_INITIALIZER
1028 macro.
1029 .Pp
1030 The
1031 .Fn TAILQ_INSERT_HEAD
1032 macro inserts the new element
1033 .Fa elm
1034 at the head of the tail queue.
1035 .Pp
1036 The
1037 .Fn TAILQ_INSERT_TAIL
1038 macro inserts the new element
1039 .Fa elm
1040 at the end of the tail queue.
1041 .Pp
1042 The
1043 .Fn TAILQ_INSERT_AFTER
1044 macro inserts the new element
1045 .Fa elm
1046 after the element
1047 .Fa listelm .
1048 .Pp
1049 The
1050 .Fn TAILQ_INSERT_BEFORE
1051 macro inserts the new element
1052 .Fa elm
1053 before the element
1054 .Fa listelm .
1055 .Pp
1056 The
1057 .Fn TAILQ_REMOVE
1058 macro removes the element
1059 .Fa elm
1060 from the tail queue.
1061 .Pp
1062 The
1063 .Fn TAILQ_REPLACE
1064 macro replaces the list element
1065 .Fa elm
1066 with the new element
1067 .Fa elm2 .
1068 .Pp
1069 The
1070 .Fn TAILQ_CONCAT
1071 macro concatenates all the elements of the tail queue referenced by
1072 .Fa head2
1073 to the end of the tail queue referenced by
1074 .Fa head1 ,
1075 emptying
1076 .Fa head2
1077 in the process.
1078 This is more efficient than removing and inserting the individual elements
1079 as it does not actually traverse
1080 .Fa head2 .
1081 .Pp
1082 .Fn TAILQ_FOREACH
1083 and
1084 .Fn TAILQ_FOREACH_REVERSE
1085 are used for traversing a tail queue.
1086 .Fn TAILQ_FOREACH
1087 starts at the first element and proceeds towards the last.
1088 .Fn TAILQ_FOREACH_REVERSE
1089 starts at the last element and proceeds towards the first.
1090 .Bd -literal -offset indent
1091 TAILQ_FOREACH(np, &head, FIELDNAME)
1092 TAILQ_FOREACH_REVERSE(np, &head, HEADNAME, FIELDNAME)
1093 .Ed
1094 .Pp
1095 The macros
1096 .Fn TAILQ_FOREACH_SAFE
1097 and
1098 .Fn TAILQ_FOREACH_REVERSE_SAFE
1099 traverse the list referenced by head
1100 in a forward or reverse direction respectively,
1101 assigning each element in turn to var.
1102 However, unlike their unsafe counterparts,
1103 they permit both the removal of var
1104 as well as freeing it from within the loop safely
1105 without interfering with the traversal.
1106 .Pp
1107 The
1108 .Fn TAILQ_FIRST ,
1109 .Fn TAILQ_NEXT ,
1110 .Fn TAILQ_LAST
1111 and
1112 .Fn TAILQ_PREV
1113 macros can be used to manually traverse a tail queue or an arbitrary part of
1114 one.
1115 .Pp
1116 The
1117 .Fn TAILQ_EMPTY
1118 macro should be used to check whether a tail queue is empty.
1119 .Sh TAIL QUEUE EXAMPLE
1120 .Bd -literal
1121 TAILQ_HEAD(tailhead, entry) head;
1122 struct entry {
1123 ...
1124 TAILQ_ENTRY(entry) entries; /* Tail queue. */
1125 ...
1126 } *n1, *n2, *np;
1127
1128 TAILQ_INIT(&head); /* Initialize queue. */
1129
1130 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
1131 TAILQ_INSERT_HEAD(&head, n1, entries);
1132
1133 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
1134 TAILQ_INSERT_TAIL(&head, n1, entries);
1135
1136 n2 = malloc(sizeof(struct entry)); /* Insert after. */
1137 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
1138
1139 n2 = malloc(sizeof(struct entry)); /* Insert before. */
1140 TAILQ_INSERT_BEFORE(n1, n2, entries);
1141 /* Forward traversal. */
1142 TAILQ_FOREACH(np, &head, entries)
1143 np-> ...
1144 /* Manual forward traversal. */
1145 for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries))
1146 np-> ...
1147 /* Delete. */
1148 while ((np = TAILQ_FIRST(&head))) {
1149 TAILQ_REMOVE(&head, np, entries);
1150 free(np);
1151 }
1152
1153 .Ed
1154 .Sh SEE ALSO
1155 .Xr tree 3
1156 .Sh NOTES
1157 It is an error to assume the next and previous fields are preserved
1158 after an element has been removed from a list or queue.
1159 Using any macro (except the various forms of insertion) on an element
1160 removed from a list or queue is incorrect.
1161 An example of erroneous usage is removing the same element twice.
1162 .Pp
1163 The
1164 .Fn SLIST_END ,
1165 .Fn LIST_END ,
1166 .Fn SIMPLEQ_END ,
1167 .Fn STAILQ_END
1168 and
1169 .Fn TAILQ_END
1170 macros are deprecated; they provided symmetry with the historical
1171 .Fn CIRCLEQ_END
1172 and just expand to
1173 .Dv NULL .
1174 .Pp
1175 Trying to free a list in the following way is a common error:
1176 .Bd -literal -offset indent
1177 LIST_FOREACH(var, head, entry)
1178 free(var);
1179 free(head);
1180 .Ed
1181 .Pp
1182 Since
1183 .Va var
1184 is free'd, the FOREACH macros refer to a pointer that may have been
1185 reallocated already.
1186 A similar situation occurs when the current element is deleted
1187 from the list.
1188 In cases like these the data structure's FOREACH_SAFE macros should be used
1189 instead.
1190 .Sh HISTORY
1191 The
1192 .Nm queue
1193 functions first appeared in
1194 .Bx 4.4 .
1195 The historical circle queue macros were deprecated in
1196 .Ox 5.5 .