man3/tailq.3

   1 .\" Copyright (c) 1993
   2 .\"    The Regents of the University of California.  All rights reserved.
   3 .\" and Copyright (c) 2020 by Alejandro Colomar <colomar.6.4.3@gmail.com>
   4 .\"
   5 .\" %%%LICENSE_START(BSD_3_CLAUSE_UCB)
   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 .\" 3. Neither the name of the University nor the names of its contributors
  15 .\"    may be used to endorse or promote products derived from this software
  16 .\"    without specific prior written permission.
  17 .\"
  18 .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  19 .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20 .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21 .\" ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  22 .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  23 .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  24 .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25 .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  26 .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  27 .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  28 .\" SUCH DAMAGE.
  29 .\" %%%LICENSE_END
  30 .\"
  31 .\"
  32 .TH TAILQ 3 2021-03-22 "GNU" "Linux Programmer's Manual"
  33 .SH NAME
  34 TAILQ_CONCAT,
  35 TAILQ_EMPTY,
  36 TAILQ_ENTRY,
  37 TAILQ_FIRST,
  38 TAILQ_FOREACH,
  39 .\"TAILQ_FOREACH_FROM,
  40 .\"TAILQ_FOREACH_FROM_SAFE,
  41 TAILQ_FOREACH_REVERSE,
  42 .\"TAILQ_FOREACH_REVERSE_FROM,
  43 .\"TAILQ_FOREACH_REVERSE_FROM_SAFE,
  44 .\"TAILQ_FOREACH_REVERSE_SAFE,
  45 .\"TAILQ_FOREACH_SAFE,
  46 TAILQ_HEAD,
  47 TAILQ_HEAD_INITIALIZER,
  48 TAILQ_INIT,
  49 TAILQ_INSERT_AFTER,
  50 TAILQ_INSERT_BEFORE,
  51 TAILQ_INSERT_HEAD,
  52 TAILQ_INSERT_TAIL,
  53 TAILQ_LAST,
  54 TAILQ_NEXT,
  55 TAILQ_PREV,
  56 TAILQ_REMOVE
  57 .\"TAILQ_SWAP
  58 \- implementation of a doubly linked tail queue
  59 .SH SYNOPSIS
  60 .nf
  61 .B #include <sys/queue.h>
  62 .PP
  63 .B TAILQ_ENTRY(TYPE);
  64 .PP
  65 .B TAILQ_HEAD(HEADNAME, TYPE);
  66 .BI "TAILQ_HEAD TAILQ_HEAD_INITIALIZER(TAILQ_HEAD " head );
  67 .BI "void TAILQ_INIT(TAILQ_HEAD *" head );
  68 .PP
  69 .BI "int TAILQ_EMPTY(TAILQ_HEAD *" head );
  70 .PP
  71 .BI "void TAILQ_INSERT_HEAD(TAILQ_HEAD *" head ,
  72 .BI "                         struct TYPE *" elm ", TAILQ_ENTRY " NAME );
  73 .BI "void TAILQ_INSERT_TAIL(TAILQ_HEAD *" head ,
  74 .BI "                         struct TYPE *" elm ", TAILQ_ENTRY " NAME );
  75 .BI "void TAILQ_INSERT_BEFORE(struct TYPE *" listelm ,
  76 .BI "                         struct TYPE *" elm ", TAILQ_ENTRY " NAME );
  77 .BI "void TAILQ_INSERT_AFTER(TAILQ_HEAD *" head ", struct TYPE *" listelm ,
  78 .BI "                         struct TYPE *" elm ", TAILQ_ENTRY " NAME );
  79 .PP
  80 .BI "struct TYPE *TAILQ_FIRST(TAILQ_HEAD *" head );
  81 .BI "struct TYPE *TAILQ_LAST(TAILQ_HEAD *" head ", HEADNAME);"
  82 .BI "struct TYPE *TAILQ_PREV(struct TYPE *" elm ", HEADNAME, TAILQ_ENTRY " NAME );
  83 .BI "struct TYPE *TAILQ_NEXT(struct TYPE *" elm ", TAILQ_ENTRY " NAME );
  84 .PP
  85 .BI "TAILQ_FOREACH(struct TYPE *" var ", TAILQ_HEAD *" head ,
  86 .BI "                         TAILQ_ENTRY " NAME );
  87 .\" .BI "TAILQ_FOREACH_FROM(struct TYPE *" var ", TAILQ_HEAD *" head ,
  88 .\" .BI "                                TAILQ_ENTRY " NAME );
  89 .BI "TAILQ_FOREACH_REVERSE(struct TYPE *" var ", TAILQ_HEAD *" head ", HEADNAME,"
  90 .BI "                         TAILQ_ENTRY " NAME );
  91 .\" .BI "TAILQ_FOREACH_REVERSE_FROM(struct TYPE *" var ", TAILQ_HEAD *" head ", HEADNAME,"
  92 .\" .BI "                                TAILQ_ENTRY " NAME );
  93 .\" .PP
  94 .\" .BI "TAILQ_FOREACH_SAFE(struct TYPE *" var ", TAILQ_HEAD *" head ,
  95 .\" .BI "                                TAILQ_ENTRY " NAME ,
  96 .\" .BI "                                struct TYPE *" temp_var );
  97 .\" .BI "TAILQ_FOREACH_FROM_SAFE(struct TYPE *" var ", TAILQ_HEAD *" head ,
  98 .\" .BI "                                TAILQ_ENTRY " NAME ,
  99 .\" .BI "                                struct TYPE *" temp_var );
 100 .\" .BI "TAILQ_FOREACH_REVERSE_SAFE(struct TYPE *" var ", TAILQ_HEAD *" head ,
 101 .\" .BI "                                HEADNAME, TAILQ_ENTRY " NAME ,
 102 .\" .BI "                                struct TYPE *" temp_var );
 103 .\" .BI "TAILQ_FOREACH_REVERSE_FROM_SAFE(struct TYPE *" var ", TAILQ_HEAD *" head ,
 104 .\" .BI "                                HEADNAME, TAILQ_ENTRY " NAME ,
 105 .\" .BI "                                struct TYPE *" temp_var );
 106 .PP
 107 .BI "void TAILQ_REMOVE(TAILQ_HEAD *" head ", struct TYPE *" elm ,
 108 .BI "                         TAILQ_ENTRY " NAME );
 109 .PP
 110 .BI "void TAILQ_CONCAT(TAILQ_HEAD *" head1 ", TAILQ_HEAD *" head2 ,
 111 .BI "                         TAILQ_ENTRY " NAME );
 112 .\" .BI "void TAILQ_SWAP(TAILQ_HEAD *" head1 ", TAILQ_HEAD *" head2 ", TYPE,"
 113 .\" .BI "                                TAILQ_ENTRY " NAME );
 114 .fi
 115 .SH DESCRIPTION
 116 These macros define and operate on doubly linked tail queues.
 117 .PP
 118 In the macro definitions,
 119 .I TYPE
 120 is the name of a user defined structure,
 121 that must contain a field of type
 122 .IR TAILQ_ENTRY ,
 123 named
 124 .IR NAME .
 125 The argument
 126 .I HEADNAME
 127 is the name of a user defined structure that must be declared
 128 using the macro
 129 .BR TAILQ_HEAD ().
 130 .SS Creation
 131 A tail queue is headed by a structure defined by the
 132 .BR TAILQ_HEAD ()
 133 macro.
 134 This structure contains a pair of pointers,
 135 one to the first element in the queue
 136 and the other to the last element in the queue.
 137 The elements are doubly linked
 138 so that an arbitrary element can be removed without traversing the queue.
 139 New elements can be added to the queue
 140 after an existing element,
 141 before an existing element,
 142 at the head of the queue,
 143 or at the end of the queue.
 144 A
 145 .I TAILQ_HEAD
 146 structure is declared as follows:
 147 .PP
 148 .in +4
 149 .EX
 150 TAILQ_HEAD(HEADNAME, TYPE) head;
 151 .EE
 152 .in
 153 .PP
 154 where
 155 .I struct HEADNAME
 156 is the structure to be defined, and
 157 .I struct TYPE
 158 is the type of the elements to be linked into the queue.
 159 A pointer to the head of the queue can later be declared as:
 160 .PP
 161 .in +4
 162 .EX
 163 struct HEADNAME *headp;
 164 .EE
 165 .in
 166 .PP
 167 (The names
 168 .I head
 169 and
 170 .I headp
 171 are user selectable.)
 172 .PP
 173 .BR TAILQ_ENTRY ()
 174 declares a structure that connects the elements in the queue.
 175 .PP
 176 .BR TAILQ_HEAD_INITIALIZER ()
 177 evaluates to an initializer for the queue
 178 .IR head .
 179 .PP
 180 .BR TAILQ_INIT ()
 181 initializes the queue referenced by
 182 .PP
 183 .BR TAILQ_EMPTY ()
 184 evaluates to true if there are no items on the queue.
 185 .IR head .
 186 .SS Insertion
 187 .BR TAILQ_INSERT_HEAD ()
 188 inserts the new element
 189 .I elm
 190 at the head of the queue.
 191 .PP
 192 .BR TAILQ_INSERT_TAIL ()
 193 inserts the new element
 194 .I elm
 195 at the end of the queue.
 196 .PP
 197 .BR TAILQ_INSERT_BEFORE ()
 198 inserts the new element
 199 .I elm
 200 before the element
 201 .IR listelm .
 202 .PP
 203 .BR TAILQ_INSERT_AFTER ()
 204 inserts the new element
 205 .I elm
 206 after the element
 207 .IR listelm .
 208 .SS Traversal
 209 .BR TAILQ_FIRST ()
 210 returns the first item on the queue, or NULL if the queue is empty.
 211 .PP
 212 .BR TAILQ_LAST ()
 213 returns the last item on the queue.
 214 If the queue is empty the return value is NULL.
 215 .PP
 216 .BR TAILQ_PREV ()
 217 returns the previous item on the queue, or NULL if this item is the first.
 218 .PP
 219 .BR TAILQ_NEXT ()
 220 returns the next item on the queue, or NULL if this item is the last.
 221 .PP
 222 .BR TAILQ_FOREACH ()
 223 traverses the queue referenced by
 224 .I head
 225 in the forward direction,
 226 assigning each element in turn to
 227 .IR var .
 228 .I var
 229 is set to NULL if the loop completes normally,
 230 or if there were no elements.
 231 .\" .PP
 232 .\" .BR TAILQ_FOREACH_FROM ()
 233 .\" behaves identically to
 234 .\" .BR TAILQ_FOREACH ()
 235 .\" when
 236 .\" .I var
 237 .\" is NULL, else it treats
 238 .\" .I var
 239 .\" as a previously found TAILQ element and begins the loop at
 240 .\" .I var
 241 .\" instead of the first element in the TAILQ referenced by
 242 .\" .IR head .
 243 .PP
 244 .BR TAILQ_FOREACH_REVERSE ()
 245 traverses the queue referenced by
 246 .I head
 247 in the reverse direction,
 248 assigning each element in turn to
 249 .IR var .
 250 .\" .PP
 251 .\" .BR TAILQ_FOREACH_REVERSE_FROM ()
 252 .\" behaves identically to
 253 .\" .BR TAILQ_FOREACH_REVERSE ()
 254 .\" when
 255 .\" .I var
 256 .\" is NULL, else it treats
 257 .\" .I var
 258 .\" as a previously found TAILQ element and begins the reverse loop at
 259 .\" .I var
 260 .\" instead of the last element in the TAILQ referenced by
 261 .\" .IR head .
 262 .\" .PP
 263 .\" .BR TAILQ_FOREACH_SAFE ()
 264 .\" and
 265 .\" .BR TAILQ_FOREACH_REVERSE_SAFE ()
 266 .\" traverse the list referenced by
 267 .\" .I head
 268 .\" in the forward or reverse direction respectively,
 269 .\" assigning each element in turn to
 270 .\" .IR var .
 271 .\" However, unlike their unsafe counterparts,
 272 .\" .BR TAILQ_FOREACH ()
 273 .\" and
 274 .\" .BR TAILQ_FOREACH_REVERSE ()
 275 .\" permit to both remove
 276 .\" .I var
 277 .\" as well as free it from within the loop safely without interfering with the
 278 .\" traversal.
 279 .\" .PP
 280 .\" .BR TAILQ_FOREACH_FROM_SAFE ()
 281 .\" behaves identically to
 282 .\" .BR TAILQ_FOREACH_SAFE ()
 283 .\" when
 284 .\" .I var
 285 .\" is NULL, else it treats
 286 .\" .I var
 287 .\" as a previously found TAILQ element and begins the loop at
 288 .\" .I var
 289 .\" instead of the first element in the TAILQ referenced by
 290 .\" .IR head .
 291 .\" .PP
 292 .\" .BR TAILQ_FOREACH_REVERSE_FROM_SAFE ()
 293 .\" behaves identically to
 294 .\" .BR TAILQ_FOREACH_REVERSE_SAFE ()
 295 .\" when
 296 .\" .I var
 297 .\" is NULL, else it treats
 298 .\" .I var
 299 .\" as a previously found TAILQ element and begins the reverse loop at
 300 .\" .I var
 301 .\" instead of the last element in the TAILQ referenced by
 302 .\" .IR head .
 303 .SS Removal
 304 .BR TAILQ_REMOVE ()
 305 removes the element
 306 .I elm
 307 from the queue.
 308 .SS Other features
 309 .\" .BR TAILQ_SWAP ()
 310 .\" swaps the contents of
 311 .\" .I head1
 312 .\" and
 313 .\" .IR head2 .
 314 .\" .PP
 315 .BR TAILQ_CONCAT ()
 316 concatenates the queue headed by
 317 .I head2
 318 onto the end of the one headed by
 319 .I head1
 320 removing all entries from the former.
 321 .SH RETURN VALUE
 322 .BR TAILQ_EMPTY ()
 323 returns nonzero if the queue is empty,
 324 and zero if the queue contains at least one entry.
 325 .PP
 326 .BR TAILQ_FIRST (),
 327 .BR TAILQ_LAST (),
 328 .BR TAILQ_PREV (),
 329 and
 330 .BR TAILQ_NEXT ()
 331 return a pointer to the first, last, previous, or next
 332 .I TYPE
 333 structure, respectively.
 334 .PP
 335 .BR TAILQ_HEAD_INITIALIZER ()
 336 returns an initializer that can be assigned to the queue
 337 .IR head .
 338 .SH CONFORMING TO
 339 Not in POSIX.1, POSIX.1-2001, or POSIX.1-2008.
 340 Present on the BSDs.
 341 (TAILQ functions first appeared in 4.4BSD).
 342 .SH BUGS
 343 .BR TAILQ_FOREACH ()
 344 and
 345 .BR TAILQ_FOREACH_REVERSE ()
 346 don't allow
 347 .I var
 348 to be removed or freed within the loop,
 349 as it would interfere with the traversal.
 350 .BR TAILQ_FOREACH_SAFE ()
 351 and
 352 .BR TAILQ_FOREACH_REVERSE_SAFE (),
 353 which are present on the BSDs but are not present in glibc,
 354 fix this limitation by allowing
 355 .I var
 356 to safely be removed from the list and freed from within the loop
 357 without interfering with the traversal.
 358 .SH EXAMPLES
 359 .EX
 360 #include <stddef.h>
 361 #include <stdio.h>
 362 #include <stdlib.h>
 363 #include <sys/queue.h>
 364
 365 struct entry {
 366     int data;
 367     TAILQ_ENTRY(entry) entries;             /* Tail queue */
 368 };
 369
 370 TAILQ_HEAD(tailhead, entry);
 371
 372 int
 373 main(void)
 374 {
 375     struct entry *n1, *n2, *n3, *np;
 376     struct tailhead head;                   /* Tail queue head */
 377     int i;
 378
 379     TAILQ_INIT(&head);                      /* Initialize the queue */
 380
 381     n1 = malloc(sizeof(struct entry));      /* Insert at the head */
 382     TAILQ_INSERT_HEAD(&head, n1, entries);
 383
 384     n1 = malloc(sizeof(struct entry));      /* Insert at the tail */
 385     TAILQ_INSERT_TAIL(&head, n1, entries);
 386
 387     n2 = malloc(sizeof(struct entry));      /* Insert after */
 388     TAILQ_INSERT_AFTER(&head, n1, n2, entries);
 389
 390     n3 = malloc(sizeof(struct entry));      /* Insert before */
 391     TAILQ_INSERT_BEFORE(n2, n3, entries);
 392
 393     TAILQ_REMOVE(&head, n2, entries);       /* Deletion */
 394     free(n2);
 395                                             /* Forward traversal */
 396     i = 0;
 397     TAILQ_FOREACH(np, &head, entries)
 398         np\->data = i++;
 399                                             /* Reverse traversal */
 400     TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
 401         printf("%i\en", np\->data);
 402                                             /* TailQ deletion */
 403     n1 = TAILQ_FIRST(&head);
 404     while (n1 != NULL) {
 405         n2 = TAILQ_NEXT(n1, entries);
 406         free(n1);
 407         n1 = n2;
 408     }
 409     TAILQ_INIT(&head);
 410
 411     exit(EXIT_SUCCESS);
 412 }
 413 .EE
 414 .SH SEE ALSO
 415 .BR insque (3),
 416 .BR queue (7)