man3/stailq.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 STAILQ 3 (date) "Linux man-pages (unreleased)"
   9 .SH NAME
  10 .\"SIMPLEQ_CONCAT,
  11 SIMPLEQ_EMPTY,
  12 SIMPLEQ_ENTRY,
  13 SIMPLEQ_FIRST,
  14 SIMPLEQ_FOREACH,
  15 .\"SIMPLEQ_FOREACH_FROM,
  16 .\"SIMPLEQ_FOREACH_FROM_SAFE,
  17 .\"SIMPLEQ_FOREACH_SAFE,
  18 SIMPLEQ_HEAD,
  19 SIMPLEQ_HEAD_INITIALIZER,
  20 SIMPLEQ_INIT,
  21 SIMPLEQ_INSERT_AFTER,
  22 SIMPLEQ_INSERT_HEAD,
  23 SIMPLEQ_INSERT_TAIL,
  24 .\"SIMPLEQ_LAST,
  25 SIMPLEQ_NEXT,
  26 SIMPLEQ_REMOVE,
  27 .\"SIMPLEQ_REMOVE_AFTER,
  28 SIMPLEQ_REMOVE_HEAD,
  29 .\"SIMPLEQ_SWAP,
  30 STAILQ_CONCAT,
  31 STAILQ_EMPTY,
  32 STAILQ_ENTRY,
  33 STAILQ_FIRST,
  34 STAILQ_FOREACH,
  35 .\"STAILQ_FOREACH_FROM,
  36 .\"STAILQ_FOREACH_FROM_SAFE,
  37 .\"STAILQ_FOREACH_SAFE,
  38 STAILQ_HEAD,
  39 STAILQ_HEAD_INITIALIZER,
  40 STAILQ_INIT,
  41 STAILQ_INSERT_AFTER,
  42 STAILQ_INSERT_HEAD,
  43 STAILQ_INSERT_TAIL,
  44 .\"STAILQ_LAST,
  45 STAILQ_NEXT,
  46 STAILQ_REMOVE,
  47 .\"STAILQ_REMOVE_AFTER,
  48 STAILQ_REMOVE_HEAD,
  49 .\"STAILQ_SWAP
  50 \- implementation of a singly linked tail queue
  51 .SH LIBRARY
  52 Standard C library
  53 .RI ( libc ", " \-lc )
  54 .SH SYNOPSIS
  55 .nf
  56 .B #include <sys/queue.h>
  57 .P
  58 .B STAILQ_ENTRY(TYPE);
  59 .P
  60 .B STAILQ_HEAD(HEADNAME, TYPE);
  61 .BI "STAILQ_HEAD STAILQ_HEAD_INITIALIZER(STAILQ_HEAD " head );
  62 .BI "void STAILQ_INIT(STAILQ_HEAD *" head );
  63 .P
  64 .BI "int STAILQ_EMPTY(STAILQ_HEAD *" head );
  65 .P
  66 .BI "void STAILQ_INSERT_HEAD(STAILQ_HEAD *" head ,
  67 .BI "                         struct TYPE *" elm ", STAILQ_ENTRY " NAME );
  68 .BI "void STAILQ_INSERT_TAIL(STAILQ_HEAD *" head ,
  69 .BI "                         struct TYPE *" elm ", STAILQ_ENTRY " NAME );
  70 .BI "void STAILQ_INSERT_AFTER(STAILQ_HEAD *" head ", struct TYPE *" listelm ,
  71 .BI "                         struct TYPE *" elm ", STAILQ_ENTRY " NAME );
  72 .P
  73 .BI "struct TYPE *STAILQ_FIRST(STAILQ_HEAD *" head );
  74 .\" .BI "struct TYPE *STAILQ_LAST(STAILQ_HEAD *" head ", struct TYPE *" elm ,
  75 .\" .BI "                          STAILQ_ENTRY " NAME );
  76 .BI "struct TYPE *STAILQ_NEXT(struct TYPE *" elm ", STAILQ_ENTRY " NAME );
  77 .P
  78 .BI "STAILQ_FOREACH(struct TYPE *" var ", STAILQ_HEAD *" head ", STAILQ_ENTRY " NAME );
  79 .\" .BI "STAILQ_FOREACH_FROM(struct TYPE *" var ", STAILQ_HEAD *" head ,
  80 .\" .BI "                          STAILQ_ENTRY " NAME );
  81 .\" .P
  82 .\" .BI "STAILQ_FOREACH_SAFE(struct TYPE *" var ", STAILQ_HEAD *" head ,
  83 .\" .BI "                          STAILQ_ENTRY " NAME ", struct TYPE *" temp_var );
  84 .\" .BI "STAILQ_FOREACH_FROM_SAFE(struct TYPE *" var ", STAILQ_HEAD *" head ,
  85 .\" .BI "                          STAILQ_ENTRY " NAME ", struct TYPE *" temp_var );
  86 .P
  87 .BI "void STAILQ_REMOVE(STAILQ_HEAD *" head ", struct TYPE *" elm ", TYPE,"
  88 .BI "                         STAILQ_ENTRY " NAME );
  89 .BI "void STAILQ_REMOVE_HEAD(STAILQ_HEAD *" head ,
  90 .BI "                         STAILQ_ENTRY " NAME );
  91 .\" .BI "void STAILQ_REMOVE_AFTER(STAILQ_HEAD *" head ", struct TYPE *" elm ,
  92 .\" .BI "                          STAILQ_ENTRY " NAME );
  93 .P
  94 .BI "void STAILQ_CONCAT(STAILQ_HEAD *" head1 ", STAILQ_HEAD *" head2 );
  95 .\" .BI "void STAILQ_SWAP(STAILQ_HEAD *" head1 ", STAILQ_HEAD *" head2 ,
  96 .\" .BI "                          STAILQ_ENTRY " NAME );
  97 .fi
  98 .IR Note :
  99 Identical macros prefixed with SIMPLEQ instead of STAILQ exist; see NOTES.
 100 .SH DESCRIPTION
 101 These macros define and operate on singly linked tail queues.
 102 .P
 103 In the macro definitions,
 104 .I TYPE
 105 is the name of a user-defined structure,
 106 that must contain a field of type
 107 .IR STAILQ_ENTRY ,
 108 named
 109 .IR NAME .
 110 The argument
 111 .I HEADNAME
 112 is the name of a user-defined structure that must be declared
 113 using the macro
 114 .BR STAILQ_HEAD ().
 115 .SS Creation
 116 A singly linked tail queue is headed by a structure defined by the
 117 .BR STAILQ_HEAD ()
 118 macro.
 119 This structure contains a pair of pointers,
 120 one to the first element in the tail queue and the other to
 121 the last element in the tail queue.
 122 The elements are singly linked for minimum space and pointer
 123 manipulation overhead at the expense of O(n) removal for arbitrary elements.
 124 New elements can be added to the tail queue after an existing element,
 125 at the head of the tail queue, or at the end of the tail queue.
 126 A
 127 .I STAILQ_HEAD
 128 structure is declared as follows:
 129 .P
 130 .in +4
 131 .EX
 132 STAILQ_HEAD(HEADNAME, TYPE) head;
 133 .EE
 134 .in
 135 .P
 136 where
 137 .I struct HEADNAME
 138 is the structure to be defined, and
 139 .I struct TYPE
 140 is the type of the elements to be linked into the tail queue.
 141 A pointer to the head of the tail queue can later be declared as:
 142 .P
 143 .in +4
 144 .EX
 145 struct HEADNAME *headp;
 146 .EE
 147 .in
 148 .P
 149 (The names
 150 .I head
 151 and
 152 .I headp
 153 are user selectable.)
 154 .P
 155 .BR STAILQ_ENTRY ()
 156 declares a structure that connects the elements in the tail queue.
 157 .P
 158 .BR STAILQ_HEAD_INITIALIZER ()
 159 evaluates to an initializer for the tail queue
 160 .IR head .
 161 .P
 162 .BR STAILQ_INIT ()
 163 initializes the tail queue referenced by
 164 .IR head .
 165 .P
 166 .BR STAILQ_EMPTY ()
 167 evaluates to true if there are no items on the tail queue.
 168 .SS Insertion
 169 .BR STAILQ_INSERT_HEAD ()
 170 inserts the new element
 171 .I elm
 172 at the head of the tail queue.
 173 .P
 174 .BR STAILQ_INSERT_TAIL ()
 175 inserts the new element
 176 .I elm
 177 at the end of the tail queue.
 178 .P
 179 .BR STAILQ_INSERT_AFTER ()
 180 inserts the new element
 181 .I elm
 182 after the element
 183 .IR listelm .
 184 .SS Traversal
 185 .BR STAILQ_FIRST ()
 186 returns the first item on the tail queue or NULL if the tail queue is empty.
 187 .\" .P
 188 .\" .BR STAILQ_LAST ()
 189 .\" returns the last item on the tail queue.
 190 .\" If the tail queue is empty the return value is NULL .
 191 .P
 192 .BR STAILQ_NEXT ()
 193 returns the next item on the tail queue, or NULL this item is the last.
 194 .P
 195 .BR STAILQ_FOREACH ()
 196 traverses the tail queue referenced by
 197 .I head
 198 in the forward direction,
 199 assigning each element in turn to
 200 .IR var .
 201 .\" .P
 202 .\" .BR STAILQ_FOREACH_FROM ()
 203 .\" behaves identically to
 204 .\" .BR STAILQ_FOREACH ()
 205 .\" when
 206 .\" .I var
 207 .\" is NULL, else it treats
 208 .\" .I var
 209 .\" as a previously found STAILQ element and begins the loop at
 210 .\" .I var
 211 .\" instead of the first element in the STAILQ referenced by
 212 .\" .IR head .
 213 .\" .P
 214 .\" .BR STAILQ_FOREACH_SAFE ()
 215 .\" traverses the tail queue referenced by
 216 .\" .I head
 217 .\" in the forward direction, assigning each element
 218 .\" in turn to
 219 .\" .IR var .
 220 .\" However, unlike
 221 .\" .BR STAILQ_FOREACH ()
 222 .\" here it is permitted to both remove
 223 .\" .I var
 224 .\" as well as free it from within the loop safely without interfering with the
 225 .\" traversal.
 226 .\" .P
 227 .\" .BR STAILQ_FOREACH_FROM_SAFE ()
 228 .\" behaves identically to
 229 .\" .BR STAILQ_FOREACH_SAFE ()
 230 .\" when
 231 .\" .I var
 232 .\" is NULL, else it treats
 233 .\" .I var
 234 .\" as a previously found STAILQ element and begins the loop at
 235 .\" .I var
 236 .\" instead of the first element in the STAILQ referenced by
 237 .\" .IR head .
 238 .SS Removal
 239 .BR STAILQ_REMOVE ()
 240 removes the element
 241 .I elm
 242 from the tail queue.
 243 .P
 244 .BR STAILQ_REMOVE_HEAD ()
 245 removes the element at the head of the tail queue.
 246 For optimum efficiency,
 247 elements being removed from the head of the tail queue should
 248 use this macro explicitly rather than the generic
 249 .BR STAILQ_REMOVE ()
 250 macro.
 251 .\" .P
 252 .\" .BR STAILQ_REMOVE_AFTER ()
 253 .\" removes the element after
 254 .\" .I elm
 255 .\" from the tail queue.
 256 .\" Unlike
 257 .\" .BR STAILQ_REMOVE (),
 258 .\" this macro does not traverse the entire tail queue.
 259 .SS Other features
 260 .BR STAILQ_CONCAT ()
 261 concatenates the tail queue headed by
 262 .I head2
 263 onto the end of the one headed by
 264 .I head1
 265 removing all entries from the former.
 266 .\" .P
 267 .\" .BR STAILQ_SWAP ()
 268 .\" swaps the contents of
 269 .\" .I head1
 270 .\" and
 271 .\" .IR head2 .
 272 .SH RETURN VALUE
 273 .BR STAILQ_EMPTY ()
 274 returns nonzero if the queue is empty,
 275 and zero if the queue contains at least one entry.
 276 .P
 277 .BR STAILQ_FIRST (),
 278 and
 279 .BR STAILQ_NEXT ()
 280 return a pointer to the first or next
 281 .I TYPE
 282 structure, respectively.
 283 .P
 284 .BR STAILQ_HEAD_INITIALIZER ()
 285 returns an initializer that can be assigned to the queue
 286 .IR head .
 287 .SH VERSIONS
 288 Some BSDs provide SIMPLEQ instead of STAILQ.
 289 They are identical, but for historical reasons
 290 they were named differently on different BSDs.
 291 STAILQ originated on FreeBSD, and SIMPLEQ originated on NetBSD.
 292 For compatibility reasons, some systems provide both sets of macros.
 293 glibc provides both STAILQ and SIMPLEQ,
 294 which are identical except for a missing SIMPLEQ equivalent to
 295 .BR STAILQ_CONCAT ().
 296 .SH BUGS
 297 .BR STAILQ_FOREACH ()
 298 doesn't allow
 299 .I var
 300 to be removed or freed within the loop,
 301 as it would interfere with the traversal.
 302 .BR STAILQ_FOREACH_SAFE (),
 303 which is present on the BSDs but is not present in glibc,
 304 fixes this limitation by allowing
 305 .I var
 306 to safely be removed from the list and freed from within the loop
 307 without interfering with the traversal.
 308 .SH STANDARDS
 309 BSD.
 310 .SH HISTORY
 311 4.4BSD.
 312 .SH EXAMPLES
 313 .\" SRC BEGIN (stailq.c)
 314 .EX
 315 #include <stddef.h>
 316 #include <stdio.h>
 317 #include <stdlib.h>
 318 #include <sys/queue.h>
 319 \&
 320 struct entry {
 321     int data;
 322     STAILQ_ENTRY(entry) entries;        /* Singly linked tail queue */
 323 };
 324 \&
 325 STAILQ_HEAD(stailhead, entry);
 326 \&
 327 int
 328 main(void)
 329 {
 330     struct entry *n1, *n2, *n3, *np;
 331     struct stailhead head;                  /* Singly linked tail queue
 332                                                head */
 333 \&
 334     STAILQ_INIT(&head);                     /* Initialize the queue */
 335 \&
 336     n1 = malloc(sizeof(struct entry));      /* Insert at the head */
 337     STAILQ_INSERT_HEAD(&head, n1, entries);
 338 \&
 339     n1 = malloc(sizeof(struct entry));      /* Insert at the tail */
 340     STAILQ_INSERT_TAIL(&head, n1, entries);
 341 \&
 342     n2 = malloc(sizeof(struct entry));      /* Insert after */
 343     STAILQ_INSERT_AFTER(&head, n1, n2, entries);
 344 \&
 345     STAILQ_REMOVE(&head, n2, entry, entries); /* Deletion */
 346     free(n2);
 347 \&
 348     n3 = STAILQ_FIRST(&head);
 349     STAILQ_REMOVE_HEAD(&head, entries);     /* Deletion from the head */
 350     free(n3);
 351 \&
 352     n1 = STAILQ_FIRST(&head);
 353     n1\->data = 0;
 354     for (unsigned int i = 1; i < 5; i++) {
 355         n1 = malloc(sizeof(struct entry));
 356         STAILQ_INSERT_HEAD(&head, n1, entries);
 357         n1\->data = i;
 358     }
 359                                             /* Forward traversal */
 360     STAILQ_FOREACH(np, &head, entries)
 361         printf("%i\en", np\->data);
 362                                             /* TailQ deletion */
 363     n1 = STAILQ_FIRST(&head);
 364     while (n1 != NULL) {
 365         n2 = STAILQ_NEXT(n1, entries);
 366         free(n1);
 367         n1 = n2;
 368     }
 369     STAILQ_INIT(&head);
 370 \&
 371     exit(EXIT_SUCCESS);
 372 }
 373 .EE
 374 .\" SRC END
 375 .SH SEE ALSO
 376 .BR insque (3),
 377 .BR queue (7)