src/ext/tor_queue.txt

   1 Below follows the manpage for tor_queue.h, as included with OpenBSD's
   2 sys/queue.h.  License follows at the end of the file.
   3
   4 ======================================================================
   5 QUEUE(3)                  OpenBSD Programmer's Manual                 QUEUE(3)
   6
   7 NAME
   8      SLIST_ENTRY, SLIST_HEAD, SLIST_HEAD_INITIALIZER, SLIST_FIRST, SLIST_NEXT,
   9      SLIST_END, SLIST_EMPTY, SLIST_FOREACH, SLIST_FOREACH_SAFE, SLIST_INIT,
  10      SLIST_INSERT_AFTER, SLIST_INSERT_HEAD, SLIST_REMOVE_AFTER,
  11      SLIST_REMOVE_HEAD, SLIST_REMOVE, LIST_ENTRY, LIST_HEAD,
  12      LIST_HEAD_INITIALIZER, LIST_FIRST, LIST_NEXT, LIST_END, LIST_EMPTY,
  13      LIST_FOREACH, LIST_FOREACH_SAFE, LIST_INIT, LIST_INSERT_AFTER,
  14      LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_REMOVE, LIST_REPLACE,
  15      SIMPLEQ_ENTRY, SIMPLEQ_HEAD, SIMPLEQ_HEAD_INITIALIZER, SIMPLEQ_FIRST,
  16      SIMPLEQ_NEXT, SIMPLEQ_END, SIMPLEQ_EMPTY, SIMPLEQ_FOREACH,
  17      SIMPLEQ_FOREACH_SAFE, SIMPLEQ_INIT, SIMPLEQ_INSERT_AFTER,
  18      SIMPLEQ_INSERT_HEAD, SIMPLEQ_INSERT_TAIL, SIMPLEQ_REMOVE_AFTER,
  19      SIMPLEQ_REMOVE_HEAD, TAILQ_ENTRY, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER,
  20      TAILQ_FIRST, TAILQ_NEXT, TAILQ_END, TAILQ_LAST, TAILQ_PREV, TAILQ_EMPTY,
  21      TAILQ_FOREACH, TAILQ_FOREACH_SAFE, TAILQ_FOREACH_REVERSE,
  22      TAILQ_FOREACH_REVERSE_SAFE, TAILQ_INIT, TAILQ_INSERT_AFTER,
  23      TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_REMOVE,
  24      TAILQ_REPLACE, CIRCLEQ_ENTRY, CIRCLEQ_HEAD, CIRCLEQ_HEAD_INITIALIZER,
  25      CIRCLEQ_FIRST, CIRCLEQ_LAST, CIRCLEQ_END, CIRCLEQ_NEXT, CIRCLEQ_PREV,
  26      CIRCLEQ_EMPTY, CIRCLEQ_FOREACH, CIRCLEQ_FOREACH_SAFE,
  27      CIRCLEQ_FOREACH_REVERSE_SAFE, CIRCLEQ_INIT, CIRCLEQ_INSERT_AFTER,
  28      CIRCLEQ_INSERT_BEFORE, CIRCLEQ_INSERT_HEAD, CIRCLEQ_INSERT_TAIL,
  29      CIRCLEQ_REMOVE, CIRCLEQ_REPLACE - implementations of singly-linked lists,
  30      doubly-linked lists, simple queues, tail queues, and circular queues
  31
  32 SYNOPSIS
  33      #include <sys/queue.h>
  34
  35      SLIST_ENTRY(TYPE);
  36
  37      SLIST_HEAD(HEADNAME, TYPE);
  38
  39      SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
  40
  41      struct TYPE *
  42      SLIST_FIRST(SLIST_HEAD *head);
  43
  44      struct TYPE *
  45      SLIST_NEXT(struct TYPE *listelm, SLIST_ENTRY NAME);
  46
  47      struct TYPE *
  48      SLIST_END(SLIST_HEAD *head);
  49
  50      int
  51      SLIST_EMPTY(SLIST_HEAD *head);
  52
  53      SLIST_FOREACH(VARNAME, SLIST_HEAD *head, SLIST_ENTRY NAME);
  54
  55      SLIST_FOREACH_SAFE(VARNAME, SLIST_HEAD *head, SLIST_ENTRY
  56      NAME, TEMP_VARNAME);
  57
  58      void
  59      SLIST_INIT(SLIST_HEAD *head);
  60
  61      void
  62      SLIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm, SLIST_ENTRY
  63      NAME);
  64
  65      void
  66      SLIST_INSERT_HEAD(SLIST_HEAD *head, struct TYPE *elm, SLIST_ENTRY NAME);
  67
  68      void
  69      SLIST_REMOVE_AFTER(struct TYPE *elm, SLIST_ENTRY NAME);
  70
  71      void
  72      SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME);
  73
  74      void
  75      SLIST_REMOVE(SLIST_HEAD *head, struct TYPE *elm, TYPE, SLIST_ENTRY NAME);
  76
  77      LIST_ENTRY(TYPE);
  78
  79      LIST_HEAD(HEADNAME, TYPE);
  80
  81      LIST_HEAD_INITIALIZER(LIST_HEAD head);
  82
  83      struct TYPE *
  84      LIST_FIRST(LIST_HEAD *head);
  85
  86      struct TYPE *
  87      LIST_NEXT(struct TYPE *listelm, LIST_ENTRY NAME);
  88
  89      struct TYPE *
  90      LIST_END(LIST_HEAD *head);
  91
  92      int
  93      LIST_EMPTY(LIST_HEAD *head);
  94
  95      LIST_FOREACH(VARNAME, LIST_HEAD *head, LIST_ENTRY NAME);
  96
  97      LIST_FOREACH_SAFE(VARNAME, LIST_HEAD *head, LIST_ENTRY
  98      NAME, TEMP_VARNAME);
  99
 100      void
 101      LIST_INIT(LIST_HEAD *head);
 102
 103      void
 104      LIST_INSERT_AFTER(struct TYPE *listelm, struct TYPE *elm, LIST_ENTRY
 105      NAME);
 106
 107      void
 108      LIST_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm, LIST_ENTRY
 109      NAME);
 110
 111      void
 112      LIST_INSERT_HEAD(LIST_HEAD *head, struct TYPE *elm, LIST_ENTRY NAME);
 113
 114      void
 115      LIST_REMOVE(struct TYPE *elm, LIST_ENTRY NAME);
 116
 117      void
 118      LIST_REPLACE(struct TYPE *elm, struct TYPE *elm2, LIST_ENTRY NAME);
 119
 120      SIMPLEQ_ENTRY(TYPE);
 121
 122      SIMPLEQ_HEAD(HEADNAME, TYPE);
 123
 124      SIMPLEQ_HEAD_INITIALIZER(SIMPLEQ_HEAD head);
 125
 126      struct TYPE *
 127      SIMPLEQ_FIRST(SIMPLEQ_HEAD *head);
 128
 129      struct TYPE *
 130      SIMPLEQ_NEXT(struct TYPE *listelm, SIMPLEQ_ENTRY NAME);
 131
 132      struct TYPE *
 133      SIMPLEQ_END(SIMPLEQ_HEAD *head);
 134
 135      int
 136      SIMPLEQ_EMPTY(SIMPLEQ_HEAD *head);
 137
 138      SIMPLEQ_FOREACH(VARNAME, SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY NAME);
 139
 140      SIMPLEQ_FOREACH_SAFE(VARNAME, SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY
 141      NAME, TEMP_VARNAME);
 142
 143      void
 144      SIMPLEQ_INIT(SIMPLEQ_HEAD *head);
 145
 146      void
 147      SIMPLEQ_INSERT_AFTER(SIMPLEQ_HEAD *head, struct TYPE *listelm, struct
 148      TYPE *elm, SIMPLEQ_ENTRY NAME);
 149
 150      void
 151      SIMPLEQ_INSERT_HEAD(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY
 152      NAME);
 153
 154      void
 155      SIMPLEQ_INSERT_TAIL(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY
 156      NAME);
 157
 158      void
 159      SIMPLEQ_REMOVE_AFTER(SIMPLEQ_HEAD *head, struct TYPE *elm, SIMPLEQ_ENTRY
 160      NAME);
 161
 162      void
 163      SIMPLEQ_REMOVE_HEAD(SIMPLEQ_HEAD *head, SIMPLEQ_ENTRY NAME);
 164
 165      TAILQ_ENTRY(TYPE);
 166
 167      TAILQ_HEAD(HEADNAME, TYPE);
 168
 169      TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
 170
 171      struct TYPE *
 172      TAILQ_FIRST(TAILQ_HEAD *head);
 173
 174      struct TYPE *
 175      TAILQ_NEXT(struct TYPE *listelm, TAILQ_ENTRY NAME);
 176
 177      struct TYPE *
 178      TAILQ_END(TAILQ_HEAD *head);
 179
 180      struct TYPE *
 181      TAILQ_LAST(TAILQ_HEAD *head, HEADNAME NAME);
 182
 183      struct TYPE *
 184      TAILQ_PREV(struct TYPE *listelm, HEADNAME NAME, TAILQ_ENTRY NAME);
 185
 186      int
 187      TAILQ_EMPTY(TAILQ_HEAD *head);
 188
 189      TAILQ_FOREACH(VARNAME, TAILQ_HEAD *head, TAILQ_ENTRY NAME);
 190
 191      TAILQ_FOREACH_SAFE(VARNAME, TAILQ_HEAD *head, TAILQ_ENTRY
 192      NAME, TEMP_VARNAME);
 193
 194      TAILQ_FOREACH_REVERSE(VARNAME, TAILQ_HEAD *head, HEADNAME, TAILQ_ENTRY
 195      NAME);
 196
 197      TAILQ_FOREACH_REVERSE_SAFE(VARNAME, TAILQ_HEAD
 198      *head, HEADNAME, TAILQ_ENTRY NAME, TEMP_VARNAME);
 199
 200      void
 201      TAILQ_INIT(TAILQ_HEAD *head);
 202
 203      void
 204      TAILQ_INSERT_AFTER(TAILQ_HEAD *head, struct TYPE *listelm, struct TYPE
 205      *elm, TAILQ_ENTRY NAME);
 206
 207      void
 208      TAILQ_INSERT_BEFORE(struct TYPE *listelm, struct TYPE *elm, TAILQ_ENTRY
 209      NAME);
 210
 211      void
 212      TAILQ_INSERT_HEAD(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME);
 213
 214      void
 215      TAILQ_INSERT_TAIL(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME);
 216
 217      void
 218      TAILQ_REMOVE(TAILQ_HEAD *head, struct TYPE *elm, TAILQ_ENTRY NAME);
 219
 220      void
 221      TAILQ_REPLACE(TAILQ_HEAD *head, struct TYPE *elm, struct TYPE
 222      *elm2, TAILQ_ENTRY NAME);
 223
 224      CIRCLEQ_ENTRY(TYPE);
 225
 226      CIRCLEQ_HEAD(HEADNAME, TYPE);
 227
 228      CIRCLEQ_HEAD_INITIALIZER(CIRCLEQ_HEAD head);
 229
 230      struct TYPE *
 231      CIRCLEQ_FIRST(CIRCLEQ_HEAD *head);
 232
 233      struct TYPE *
 234      CIRCLEQ_LAST(CIRCLEQ_HEAD *head);
 235
 236      struct TYPE *
 237      CIRCLEQ_END(CIRCLEQ_HEAD *head);
 238
 239      struct TYPE *
 240      CIRCLEQ_NEXT(struct TYPE *listelm, CIRCLEQ_ENTRY NAME);
 241
 242      struct TYPE *
 243      CIRCLEQ_PREV(struct TYPE *listelm, CIRCLEQ_ENTRY NAME);
 244
 245      int
 246      CIRCLEQ_EMPTY(CIRCLEQ_HEAD *head);
 247
 248      CIRCLEQ_FOREACH(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME);
 249
 250      CIRCLEQ_FOREACH_SAFE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY
 251      NAME, TEMP_VARNAME);
 252
 253      CIRCLEQ_FOREACH_REVERSE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY NAME);
 254
 255      CIRCLEQ_FOREACH_REVERSE_SAFE(VARNAME, CIRCLEQ_HEAD *head, CIRCLEQ_ENTRY
 256      NAME, TEMP_VARNAME);
 257
 258      void
 259      CIRCLEQ_INIT(CIRCLEQ_HEAD *head);
 260
 261      void
 262      CIRCLEQ_INSERT_AFTER(CIRCLEQ_HEAD *head, struct TYPE *listelm, struct
 263      TYPE *elm, CIRCLEQ_ENTRY NAME);
 264
 265      void
 266      CIRCLEQ_INSERT_BEFORE(CIRCLEQ_HEAD *head, struct TYPE *listelm, struct
 267      TYPE *elm, CIRCLEQ_ENTRY NAME);
 268
 269      void
 270      CIRCLEQ_INSERT_HEAD(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY
 271      NAME);
 272
 273      void
 274      CIRCLEQ_INSERT_TAIL(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY
 275      NAME);
 276
 277      void
 278      CIRCLEQ_REMOVE(CIRCLEQ_HEAD *head, struct TYPE *elm, CIRCLEQ_ENTRY NAME);
 279
 280      void
 281      CIRCLEQ_REPLACE(CIRCLEQ_HEAD *head, struct TYPE *elm, struct TYPE
 282      *elm2, CIRCLEQ_ENTRY NAME);
 283
 284 DESCRIPTION
 285      These macros define and operate on five types of data structures: singly-
 286      linked lists, simple queues, lists, tail queues, and circular queues.
 287      All five structures support the following functionality:
 288
 289            1.   Insertion of a new entry at the head of the list.
 290            2.   Insertion of a new entry after any element in the list.
 291            3.   Removal of an entry from the head of the list.
 292            4.   Forward traversal through the list.
 293
 294      Singly-linked lists are the simplest of the five data structures and
 295      support only the above functionality.  Singly-linked lists are ideal for
 296      applications with large datasets and few or no removals, or for
 297      implementing a LIFO queue.
 298
 299      Simple queues add the following functionality:
 300
 301            1.   Entries can be added at the end of a list.
 302
 303      However:
 304
 305            1.   All list insertions must specify the head of the list.
 306            2.   Each head entry requires two pointers rather than one.
 307            3.   Code size is about 15% greater and operations run about 20%
 308                 slower than singly-linked lists.
 309
 310      Simple queues are ideal for applications with large datasets and few or
 311      no removals, or for implementing a FIFO queue.
 312
 313      All doubly linked types of data structures (lists, tail queues, and
 314      circle queues) additionally allow:
 315
 316            1.   Insertion of a new entry before any element in the list.
 317            2.   Removal of any entry in the list.
 318
 319      However:
 320
 321            1.   Each element requires two pointers rather than one.
 322            2.   Code size and execution time of operations (except for
 323                 removal) is about twice that of the singly-linked data-
 324                 structures.
 325
 326      Lists are the simplest of the doubly linked data structures and support
 327      only the above functionality over singly-linked lists.
 328
 329      Tail queues add the following functionality:
 330
 331            1.   Entries can be added at the end of a list.
 332            2.   They may be traversed backwards, at a cost.
 333
 334      However:
 335
 336            1.   All list insertions and removals must specify the head of the
 337                 list.
 338            2.   Each head entry requires two pointers rather than one.
 339            3.   Code size is about 15% greater and operations run about 20%
 340                 slower than singly-linked lists.
 341
 342      Circular queues add the following functionality:
 343
 344            1.   Entries can be added at the end of a list.
 345            2.   They may be traversed backwards, from tail to head.
 346
 347      However:
 348
 349            1.   All list insertions and removals must specify the head of the
 350                 list.
 351            2.   Each head entry requires two pointers rather than one.
 352            3.   The termination condition for traversal is more complex.
 353            4.   Code size is about 40% greater and operations run about 45%
 354                 slower than lists.
 355
 356      In the macro definitions, TYPE is the name tag of a user defined
 357      structure that must contain a field of type SLIST_ENTRY, LIST_ENTRY,
 358      SIMPLEQ_ENTRY, TAILQ_ENTRY, or CIRCLEQ_ENTRY, named NAME.  The argument
 359      HEADNAME is the name tag of a user defined structure that must be
 360      declared using the macros SLIST_HEAD(), LIST_HEAD(), SIMPLEQ_HEAD(),
 361      TAILQ_HEAD(), or CIRCLEQ_HEAD().  See the examples below for further
 362      explanation of how these macros are used.
 363
 364 SINGLY-LINKED LISTS
 365      A singly-linked list is headed by a structure defined by the SLIST_HEAD()
 366      macro.  This structure contains a single pointer to the first element on
 367      the list.  The elements are singly linked for minimum space and pointer
 368      manipulation overhead at the expense of O(n) removal for arbitrary
 369      elements.  New elements can be added to the list after an existing
 370      element or at the head of the list.  A SLIST_HEAD structure is declared
 371      as follows:
 372
 373            SLIST_HEAD(HEADNAME, TYPE) head;
 374
 375      where HEADNAME is the name of the structure to be defined, and struct
 376      TYPE is the type of the elements to be linked into the list.  A pointer
 377      to the head of the list can later be declared as:
 378
 379            struct HEADNAME *headp;
 380
 381      (The names head and headp are user selectable.)
 382
 383      The HEADNAME facility is often not used, leading to the following bizarre
 384      code:
 385
 386            SLIST_HEAD(, TYPE) head, *headp;
 387
 388      The SLIST_ENTRY() macro declares a structure that connects the elements
 389      in the list.
 390
 391      The SLIST_INIT() macro initializes the list referenced by head.
 392
 393      The list can also be initialized statically by using the
 394      SLIST_HEAD_INITIALIZER() macro like this:
 395
 396            SLIST_HEAD(HEADNAME, TYPE) head = SLIST_HEAD_INITIALIZER(head);
 397
 398      The SLIST_INSERT_HEAD() macro inserts the new element elm at the head of
 399      the list.
 400
 401      The SLIST_INSERT_AFTER() macro inserts the new element elm after the
 402      element listelm.
 403
 404      The SLIST_REMOVE_HEAD() macro removes the first element of the list
 405      pointed by head.
 406
 407      The SLIST_REMOVE_AFTER() macro removes the list element immediately
 408      following elm.
 409
 410      The SLIST_REMOVE() macro removes the element elm of the list pointed by
 411      head.
 412
 413      The SLIST_FIRST() and SLIST_NEXT() macros can be used to traverse the
 414      list:
 415
 416            for (np = SLIST_FIRST(&head); np != NULL; np = SLIST_NEXT(np, NAME))
 417
 418      Or, for simplicity, one can use the SLIST_FOREACH() macro:
 419
 420            SLIST_FOREACH(np, head, NAME)
 421
 422      The macro SLIST_FOREACH_SAFE() traverses the list referenced by head in a
 423      forward direction, assigning each element in turn to var.  However,
 424      unlike SLIST_FOREACH() it is permitted to remove var as well as free it
 425      from within the loop safely without interfering with the traversal.
 426
 427      The SLIST_EMPTY() macro should be used to check whether a simple list is
 428      empty.
 429
 430 SINGLY-LINKED LIST EXAMPLE
 431      SLIST_HEAD(listhead, entry) head;
 432      struct entry {
 433              ...
 434              SLIST_ENTRY(entry) entries;     /* Simple list. */
 435              ...
 436      } *n1, *n2, *np;
 437
 438      SLIST_INIT(&head);                      /* Initialize simple list. */
 439
 440      n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 441      SLIST_INSERT_HEAD(&head, n1, entries);
 442
 443      n2 = malloc(sizeof(struct entry));      /* Insert after. */
 444      SLIST_INSERT_AFTER(n1, n2, entries);
 445
 446      SLIST_FOREACH(np, &head, entries)       /* Forward traversal. */
 447              np-> ...
 448
 449      while (!SLIST_EMPTY(&head)) {           /* Delete. */
 450              n1 = SLIST_FIRST(&head);
 451              SLIST_REMOVE_HEAD(&head, entries);
 452              free(n1);
 453      }
 454
 455
 456 LISTS
 457      A list is headed by a structure defined by the LIST_HEAD() macro.  This
 458      structure contains a single pointer to the first element on the list.
 459      The elements are doubly linked so that an arbitrary element can be
 460      removed without traversing the list.  New elements can be added to the
 461      list after an existing element, before an existing element, or at the
 462      head of the list.  A LIST_HEAD structure is declared as follows:
 463
 464            LIST_HEAD(HEADNAME, TYPE) head;
 465
 466      where HEADNAME is the name of the structure to be defined, and struct
 467      TYPE is the type of the elements to be linked into the list.  A pointer
 468      to the head of the list can later be declared as:
 469
 470            struct HEADNAME *headp;
 471
 472      (The names head and headp are user selectable.)
 473
 474      The HEADNAME facility is often not used, leading to the following bizarre
 475      code:
 476
 477            LIST_HEAD(, TYPE) head, *headp;
 478
 479      The LIST_ENTRY() macro declares a structure that connects the elements in
 480      the list.
 481
 482      The LIST_INIT() macro initializes the list referenced by head.
 483
 484      The list can also be initialized statically by using the
 485      LIST_HEAD_INITIALIZER() macro like this:
 486
 487            LIST_HEAD(HEADNAME, TYPE) head = LIST_HEAD_INITIALIZER(head);
 488
 489      The LIST_INSERT_HEAD() macro inserts the new element elm at the head of
 490      the list.
 491
 492      The LIST_INSERT_AFTER() macro inserts the new element elm after the
 493      element listelm.
 494
 495      The LIST_INSERT_BEFORE() macro inserts the new element elm before the
 496      element listelm.
 497
 498      The LIST_REMOVE() macro removes the element elm from the list.
 499
 500      The LIST_REPLACE() macro replaces the list element elm with the new
 501      element elm2.
 502
 503      The LIST_FIRST() and LIST_NEXT() macros can be used to traverse the list:
 504
 505            for (np = LIST_FIRST(&head); np != NULL; np = LIST_NEXT(np, NAME))
 506
 507      Or, for simplicity, one can use the LIST_FOREACH() macro:
 508
 509            LIST_FOREACH(np, head, NAME)
 510
 511      The macro LIST_FOREACH_SAFE() traverses the list referenced by head in a
 512      forward direction, assigning each element in turn to var.  However,
 513      unlike LIST_FOREACH() it is permitted to remove var as well as free it
 514      from within the loop safely without interfering with the traversal.
 515
 516      The LIST_EMPTY() macro should be used to check whether a list is empty.
 517
 518 LIST EXAMPLE
 519      LIST_HEAD(listhead, entry) head;
 520      struct entry {
 521              ...
 522              LIST_ENTRY(entry) entries;      /* List. */
 523              ...
 524      } *n1, *n2, *np;
 525
 526      LIST_INIT(&head);                       /* Initialize list. */
 527
 528      n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 529      LIST_INSERT_HEAD(&head, n1, entries);
 530
 531      n2 = malloc(sizeof(struct entry));      /* Insert after. */
 532      LIST_INSERT_AFTER(n1, n2, entries);
 533
 534      n2 = malloc(sizeof(struct entry));      /* Insert before. */
 535      LIST_INSERT_BEFORE(n1, n2, entries);
 536                                              /* Forward traversal. */
 537      LIST_FOREACH(np, &head, entries)
 538              np-> ...
 539
 540      while (!LIST_EMPTY(&head))              /* Delete. */
 541              n1 = LIST_FIRST(&head);
 542              LIST_REMOVE(n1, entries);
 543              free(n1);
 544      }
 545
 546 SIMPLE QUEUES
 547      A simple queue is headed by a structure defined by the SIMPLEQ_HEAD()
 548      macro.  This structure contains a pair of pointers, one to the first
 549      element in the simple queue and the other to the last element in the
 550      simple queue.  The elements are singly linked.  New elements can be added
 551      to the queue after an existing element, at the head of the queue or at
 552      the tail of the queue.  A SIMPLEQ_HEAD structure is declared as follows:
 553
 554            SIMPLEQ_HEAD(HEADNAME, TYPE) head;
 555
 556      where HEADNAME is the name of the structure to be defined, and struct
 557      TYPE is the type of the elements to be linked into the queue.  A pointer
 558      to the head of the queue can later be declared as:
 559
 560            struct HEADNAME *headp;
 561
 562      (The names head and headp are user selectable.)
 563
 564      The SIMPLEQ_ENTRY() macro declares a structure that connects the elements
 565      in the queue.
 566
 567      The SIMPLEQ_INIT() macro initializes the queue referenced by head.
 568
 569      The queue can also be initialized statically by using the
 570      SIMPLEQ_HEAD_INITIALIZER() macro like this:
 571
 572            SIMPLEQ_HEAD(HEADNAME, TYPE) head = SIMPLEQ_HEAD_INITIALIZER(head);
 573
 574      The SIMPLEQ_INSERT_AFTER() macro inserts the new element elm after the
 575      element listelm.
 576
 577      The SIMPLEQ_INSERT_HEAD() macro inserts the new element elm at the head
 578      of the queue.
 579
 580      The SIMPLEQ_INSERT_TAIL() macro inserts the new element elm at the end of
 581      the queue.
 582
 583      The SIMPLEQ_REMOVE_AFTER() macro removes the queue element immediately
 584      following elm.
 585
 586      The SIMPLEQ_REMOVE_HEAD() macro removes the first element from the queue.
 587
 588      The SIMPLEQ_FIRST() and SIMPLEQ_NEXT() macros can be used to traverse the
 589      queue.  The SIMPLEQ_FOREACH() is used for queue traversal:
 590
 591            SIMPLEQ_FOREACH(np, head, NAME)
 592
 593      The macro SIMPLEQ_FOREACH_SAFE() traverses the queue referenced by head
 594      in a forward direction, assigning each element in turn to var.  However,
 595      unlike SIMPLEQ_FOREACH() it is permitted to remove var as well as free it
 596      from within the loop safely without interfering with the traversal.
 597
 598      The SIMPLEQ_EMPTY() macro should be used to check whether a list is
 599      empty.
 600
 601 SIMPLE QUEUE EXAMPLE
 602      SIMPLEQ_HEAD(listhead, entry) head = SIMPLEQ_HEAD_INITIALIZER(head);
 603      struct entry {
 604              ...
 605              SIMPLEQ_ENTRY(entry) entries;   /* Simple queue. */
 606              ...
 607      } *n1, *n2, *np;
 608
 609      n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 610      SIMPLEQ_INSERT_HEAD(&head, n1, entries);
 611
 612      n2 = malloc(sizeof(struct entry));      /* Insert after. */
 613      SIMPLEQ_INSERT_AFTER(&head, n1, n2, entries);
 614
 615      n2 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 616      SIMPLEQ_INSERT_TAIL(&head, n2, entries);
 617                                              /* Forward traversal. */
 618      SIMPLEQ_FOREACH(np, &head, entries)
 619              np-> ...
 620                                              /* Delete. */
 621      while (!SIMPLEQ_EMPTY(&head)) {
 622              n1 = SIMPLEQ_FIRST(&head);
 623              SIMPLEQ_REMOVE_HEAD(&head, entries);
 624              free(n1);
 625      }
 626
 627 TAIL QUEUES
 628      A tail queue is headed by a structure defined by the TAILQ_HEAD() macro.
 629      This structure contains a pair of pointers, one to the first element in
 630      the tail queue and the other to the last element in the tail queue.  The
 631      elements are doubly linked so that an arbitrary element can be removed
 632      without traversing the tail queue.  New elements can be added to the
 633      queue after an existing element, before an existing element, at the head
 634      of the queue, or at the end of the queue.  A TAILQ_HEAD structure is
 635      declared as follows:
 636
 637            TAILQ_HEAD(HEADNAME, TYPE) head;
 638
 639      where HEADNAME is the name of the structure to be defined, and struct
 640      TYPE is the type of the elements to be linked into the tail queue.  A
 641      pointer to the head of the tail queue can later be declared as:
 642
 643            struct HEADNAME *headp;
 644
 645      (The names head and headp are user selectable.)
 646
 647      The TAILQ_ENTRY() macro declares a structure that connects the elements
 648      in the tail queue.
 649
 650      The TAILQ_INIT() macro initializes the tail queue referenced by head.
 651
 652      The tail queue can also be initialized statically by using the
 653      TAILQ_HEAD_INITIALIZER() macro.
 654
 655      The TAILQ_INSERT_HEAD() macro inserts the new element elm at the head of
 656      the tail queue.
 657
 658      The TAILQ_INSERT_TAIL() macro inserts the new element elm at the end of
 659      the tail queue.
 660
 661      The TAILQ_INSERT_AFTER() macro inserts the new element elm after the
 662      element listelm.
 663
 664      The TAILQ_INSERT_BEFORE() macro inserts the new element elm before the
 665      element listelm.
 666
 667      The TAILQ_REMOVE() macro removes the element elm from the tail queue.
 668
 669      The TAILQ_REPLACE() macro replaces the list element elm with the new
 670      element elm2.
 671
 672      TAILQ_FOREACH() and TAILQ_FOREACH_REVERSE() are used for traversing a
 673      tail queue.  TAILQ_FOREACH() starts at the first element and proceeds
 674      towards the last.  TAILQ_FOREACH_REVERSE() starts at the last element and
 675      proceeds towards the first.
 676
 677            TAILQ_FOREACH(np, &head, NAME)
 678            TAILQ_FOREACH_REVERSE(np, &head, HEADNAME, NAME)
 679
 680      The macros TAILQ_FOREACH_SAFE() and TAILQ_FOREACH_REVERSE_SAFE() traverse
 681      the list referenced by head in a forward or reverse direction
 682      respectively, assigning each element in turn to var.  However, unlike
 683      their unsafe counterparts, they permit both the removal of var as well as
 684      freeing it from within the loop safely without interfering with the
 685      traversal.
 686
 687      The TAILQ_FIRST(), TAILQ_NEXT(), TAILQ_LAST() and TAILQ_PREV() macros can
 688      be used to manually traverse a tail queue or an arbitrary part of one.
 689
 690      The TAILQ_EMPTY() macro should be used to check whether a tail queue is
 691      empty.
 692
 693 TAIL QUEUE EXAMPLE
 694      TAILQ_HEAD(tailhead, entry) head;
 695      struct entry {
 696              ...
 697              TAILQ_ENTRY(entry) entries;     /* Tail queue. */
 698              ...
 699      } *n1, *n2, *np;
 700
 701      TAILQ_INIT(&head);                      /* Initialize queue. */
 702
 703      n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 704      TAILQ_INSERT_HEAD(&head, n1, entries);
 705
 706      n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 707      TAILQ_INSERT_TAIL(&head, n1, entries);
 708
 709      n2 = malloc(sizeof(struct entry));      /* Insert after. */
 710      TAILQ_INSERT_AFTER(&head, n1, n2, entries);
 711
 712      n2 = malloc(sizeof(struct entry));      /* Insert before. */
 713      TAILQ_INSERT_BEFORE(n1, n2, entries);
 714                                              /* Forward traversal. */
 715      TAILQ_FOREACH(np, &head, entries)
 716              np-> ...
 717                                              /* Manual forward traversal. */
 718      for (np = n2; np != NULL; np = TAILQ_NEXT(np, entries))
 719              np-> ...
 720                                              /* Delete. */
 721      while ((np = TAILQ_FIRST(&head))) {
 722              TAILQ_REMOVE(&head, np, entries);
 723              free(np);
 724      }
 725
 726
 727 CIRCULAR QUEUES
 728      A circular queue is headed by a structure defined by the CIRCLEQ_HEAD()
 729      macro.  This structure contains a pair of pointers, one to the first
 730      element in the circular queue and the other to the last element in the
 731      circular queue.  The elements are doubly linked so that an arbitrary
 732      element can be removed without traversing the queue.  New elements can be
 733      added to the queue after an existing element, before an existing element,
 734      at the head of the queue, or at the end of the queue.  A CIRCLEQ_HEAD
 735      structure is declared as follows:
 736
 737            CIRCLEQ_HEAD(HEADNAME, TYPE) head;
 738
 739      where HEADNAME is the name of the structure to be defined, and struct
 740      TYPE is the type of the elements to be linked into the circular queue.  A
 741      pointer to the head of the circular queue can later be declared as:
 742
 743            struct HEADNAME *headp;
 744
 745      (The names head and headp are user selectable.)
 746
 747      The CIRCLEQ_ENTRY() macro declares a structure that connects the elements
 748      in the circular queue.
 749
 750      The CIRCLEQ_INIT() macro initializes the circular queue referenced by
 751      head.
 752
 753      The circular queue can also be initialized statically by using the
 754      CIRCLEQ_HEAD_INITIALIZER() macro.
 755
 756      The CIRCLEQ_INSERT_HEAD() macro inserts the new element elm at the head
 757      of the circular queue.
 758
 759      The CIRCLEQ_INSERT_TAIL() macro inserts the new element elm at the end of
 760      the circular queue.
 761
 762      The CIRCLEQ_INSERT_AFTER() macro inserts the new element elm after the
 763      element listelm.
 764
 765      The CIRCLEQ_INSERT_BEFORE() macro inserts the new element elm before the
 766      element listelm.
 767
 768      The CIRCLEQ_REMOVE() macro removes the element elm from the circular
 769      queue.
 770
 771      The CIRCLEQ_REPLACE() macro replaces the list element elm with the new
 772      element elm2.
 773
 774      The CIRCLEQ_FIRST(), CIRCLEQ_LAST(), CIRCLEQ_END(), CIRCLEQ_NEXT() and
 775      CIRCLEQ_PREV() macros can be used to traverse a circular queue.  The
 776      CIRCLEQ_FOREACH() is used for circular queue forward traversal:
 777
 778            CIRCLEQ_FOREACH(np, head, NAME)
 779
 780      The CIRCLEQ_FOREACH_REVERSE() macro acts like CIRCLEQ_FOREACH() but
 781      traverses the circular queue backwards.
 782
 783      The macros CIRCLEQ_FOREACH_SAFE() and CIRCLEQ_FOREACH_REVERSE_SAFE()
 784      traverse the list referenced by head in a forward or reverse direction
 785      respectively, assigning each element in turn to var.  However, unlike
 786      their unsafe counterparts, they permit both the removal of var as well as
 787      freeing it from within the loop safely without interfering with the
 788      traversal.
 789
 790      The CIRCLEQ_EMPTY() macro should be used to check whether a circular
 791      queue is empty.
 792
 793 CIRCULAR QUEUE EXAMPLE
 794      CIRCLEQ_HEAD(circleq, entry) head;
 795      struct entry {
 796              ...
 797              CIRCLEQ_ENTRY(entry) entries;   /* Circular queue. */
 798              ...
 799      } *n1, *n2, *np;
 800
 801      CIRCLEQ_INIT(&head);                    /* Initialize circular queue. */
 802
 803      n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
 804      CIRCLEQ_INSERT_HEAD(&head, n1, entries);
 805
 806      n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
 807      CIRCLEQ_INSERT_TAIL(&head, n1, entries);
 808
 809      n2 = malloc(sizeof(struct entry));      /* Insert after. */
 810      CIRCLEQ_INSERT_AFTER(&head, n1, n2, entries);
 811
 812      n2 = malloc(sizeof(struct entry));      /* Insert before. */
 813      CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
 814                                              /* Forward traversal. */
 815      CIRCLEQ_FOREACH(np, &head, entries)
 816              np-> ...
 817                                              /* Reverse traversal. */
 818      CIRCLEQ_FOREACH_REVERSE(np, &head, entries)
 819              np-> ...
 820                                              /* Delete. */
 821      while (!CIRCLEQ_EMPTY(&head)) {
 822              n1 = CIRCLEQ_FIRST(&head);
 823              CIRCLEQ_REMOVE(&head, n1, entries);
 824              free(n1);
 825      }
 826
 827 NOTES
 828      It is an error to assume the next and previous fields are preserved after
 829      an element has been removed from a list or queue.  Using any macro
 830      (except the various forms of insertion) on an element removed from a list
 831      or queue is incorrect.  An example of erroneous usage is removing the
 832      same element twice.
 833
 834      The SLIST_END(), LIST_END(), SIMPLEQ_END() and TAILQ_END() macros are
 835      provided for symmetry with CIRCLEQ_END().  They expand to NULL and don't
 836      serve any useful purpose.
 837
 838      Trying to free a list in the following way is a common error:
 839
 840            LIST_FOREACH(var, head, entry)
 841                    free(var);
 842            free(head);
 843
 844      Since var is free'd, the FOREACH macros refer to a pointer that may have
 845      been reallocated already.  A similar situation occurs when the current
 846      element is deleted from the list.  In cases like these the data
 847      structure's FOREACH_SAFE macros should be used instead.
 848
 849 HISTORY
 850      The queue functions first appeared in 4.4BSD.
 851
 852 OpenBSD 5.0                     April 11, 2012                     OpenBSD 5.0
 853 ======================================================================
 854 .\"     $OpenBSD: queue.3,v 1.56 2012/04/11 13:29:14 naddy Exp $
 855 .\"     $NetBSD: queue.3,v 1.4 1995/07/03 00:25:36 mycroft Exp $
 856 .\"
 857 .\" Copyright (c) 1993 The Regents of the University of California.
 858 .\" All rights reserved.
 859 .\"
 860 .\" Redistribution and use in source and binary forms, with or without
 861 .\" modification, are permitted provided that the following conditions
 862 .\" are met:
 863 .\" 1. Redistributions of source code must retain the above copyright
 864 .\"    notice, this list of conditions and the following disclaimer.
 865 .\" 2. Redistributions in binary form must reproduce the above copyright
 866 .\"    notice, this list of conditions and the following disclaimer in the
 867 .\"    documentation and/or other materials provided with the distribution.
 868 .\" 3. Neither the name of the University nor the names of its contributors
 869 .\"    may be used to endorse or promote products derived from this software
 870 .\"    without specific prior written permission.
 871 .\"
 872 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 873 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 874 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 875 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 876 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 877 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 878 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 879 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 880 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 881 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 882 .\" SUCH DAMAGE.
 883