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