git.squeep.com Git - lemu/blob - 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 .