share/man/man3/queue.3

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