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