1queue(3bsd) LOCAL queue(3bsd)
2
4 SLIST_CLASS_ENTRY, SLIST_CLASS_HEAD, SLIST_CONCAT, SLIST_EMPTY,
5 SLIST_ENTRY, SLIST_FIRST, SLIST_FOREACH, SLIST_FOREACH_FROM,
6 SLIST_FOREACH_FROM_SAFE, SLIST_FOREACH_SAFE, SLIST_HEAD,
7 SLIST_HEAD_INITIALIZER, SLIST_INIT, SLIST_INSERT_AFTER,
8 SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE, SLIST_REMOVE_AFTER,
9 SLIST_REMOVE_HEAD, SLIST_SWAP, STAILQ_CLASS_ENTRY, STAILQ_CLASS_HEAD,
10 STAILQ_CONCAT, STAILQ_EMPTY, STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FOREACH,
11 STAILQ_FOREACH_FROM, STAILQ_FOREACH_FROM_SAFE, STAILQ_FOREACH_SAFE,
12 STAILQ_HEAD, STAILQ_HEAD_INITIALIZER, STAILQ_INIT, STAILQ_INSERT_AFTER,
13 STAILQ_INSERT_HEAD, STAILQ_INSERT_TAIL, STAILQ_LAST, STAILQ_NEXT,
14 STAILQ_REMOVE, STAILQ_REMOVE_AFTER, STAILQ_REMOVE_HEAD, STAILQ_SWAP,
15 LIST_CLASS_ENTRY, LIST_CLASS_HEAD, LIST_CONCAT, LIST_EMPTY, LIST_ENTRY,
16 LIST_FIRST, LIST_FOREACH, LIST_FOREACH_FROM, LIST_FOREACH_FROM_SAFE,
17 LIST_FOREACH_SAFE, LIST_HEAD, LIST_HEAD_INITIALIZER, LIST_INIT,
18 LIST_INSERT_AFTER, LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_NEXT,
19 LIST_PREV, LIST_REMOVE, LIST_SWAP, TAILQ_CLASS_ENTRY, TAILQ_CLASS_HEAD,
20 TAILQ_CONCAT, TAILQ_EMPTY, TAILQ_ENTRY, TAILQ_FIRST, TAILQ_FOREACH,
21 TAILQ_FOREACH_FROM, TAILQ_FOREACH_FROM_SAFE, TAILQ_FOREACH_REVERSE,
22 TAILQ_FOREACH_REVERSE_FROM, TAILQ_FOREACH_REVERSE_FROM_SAFE,
23 TAILQ_FOREACH_REVERSE_SAFE, TAILQ_FOREACH_SAFE, TAILQ_HEAD,
24 TAILQ_HEAD_INITIALIZER, TAILQ_INIT, TAILQ_INSERT_AFTER,
25 TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_LAST,
26 TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE, TAILQ_SWAP — implementations of
27 singly-linked lists, singly-linked tail queues, lists and tail queues
28
30 Utility functions from BSD systems (libbsd, -lbsd)
31
33 #include <sys/queue.h>
34 (See libbsd(7) for include usage.)
35 SLIST_CLASS_ENTRY(CLASSTYPE);
37 SLIST_CLASS_HEAD(HEADNAME, CLASSTYPE);
39 SLIST_CONCAT(SLIST_HEAD *head1, SLIST_HEAD *head2, TYPE,
41 SLIST_ENTRY NAME);
42 SLIST_EMPTY(SLIST_HEAD *head);
44 SLIST_ENTRY(TYPE);
46 SLIST_FIRST(SLIST_HEAD *head);
48 SLIST_FOREACH(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
50 SLIST_FOREACH_FROM(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
52 SLIST_FOREACH_FROM_SAFE(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME,
54 TYPE *temp_var);
55 SLIST_FOREACH_SAFE(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME,
57 TYPE *temp_var);
58 SLIST_HEAD(HEADNAME, TYPE);
60 SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
62 SLIST_INIT(SLIST_HEAD *head);
64 SLIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, SLIST_ENTRY NAME);
66 SLIST_INSERT_HEAD(SLIST_HEAD *head, TYPE *elm, SLIST_ENTRY NAME);
68 SLIST_NEXT(TYPE *elm, SLIST_ENTRY NAME);
70 SLIST_REMOVE(SLIST_HEAD *head, TYPE *elm, TYPE, SLIST_ENTRY NAME);
72 SLIST_REMOVE_AFTER(TYPE *elm, SLIST_ENTRY NAME);
74 SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME);
76 SLIST_SWAP(SLIST_HEAD *head1, SLIST_HEAD *head2, TYPE);
78 STAILQ_CLASS_ENTRY(CLASSTYPE);
80 STAILQ_CLASS_HEAD(HEADNAME, CLASSTYPE);
82 STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);
84 STAILQ_EMPTY(STAILQ_HEAD *head);
86 STAILQ_ENTRY(TYPE);
88 STAILQ_FIRST(STAILQ_HEAD *head);
90 STAILQ_FOREACH(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
92 STAILQ_FOREACH_FROM(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
94 STAILQ_FOREACH_FROM_SAFE(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME,
96 TYPE *temp_var);
97 STAILQ_FOREACH_SAFE(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME,
99 TYPE *temp_var);
100 STAILQ_HEAD(HEADNAME, TYPE);
102 STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
104 STAILQ_INIT(STAILQ_HEAD *head);
106 STAILQ_INSERT_AFTER(STAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
108 STAILQ_ENTRY NAME);
109 STAILQ_INSERT_HEAD(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
111 STAILQ_INSERT_TAIL(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
113 STAILQ_LAST(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
115 STAILQ_NEXT(TYPE *elm, STAILQ_ENTRY NAME);
117 STAILQ_REMOVE(STAILQ_HEAD *head, TYPE *elm, TYPE, STAILQ_ENTRY NAME);
119 STAILQ_REMOVE_AFTER(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
121 STAILQ_REMOVE_HEAD(STAILQ_HEAD *head, STAILQ_ENTRY NAME);
123 STAILQ_SWAP(STAILQ_HEAD *head1, STAILQ_HEAD *head2, TYPE);
125 LIST_CLASS_ENTRY(CLASSTYPE);
127 LIST_CLASS_HEAD(HEADNAME, CLASSTYPE);
129 LIST_CONCAT(LIST_HEAD *head1, LIST_HEAD *head2, TYPE, LIST_ENTRY NAME);
131 LIST_EMPTY(LIST_HEAD *head);
133 LIST_ENTRY(TYPE);
135 LIST_FIRST(LIST_HEAD *head);
137 LIST_FOREACH(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);
139 LIST_FOREACH_FROM(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);
141 LIST_FOREACH_FROM_SAFE(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME,
143 TYPE *temp_var);
144 LIST_FOREACH_SAFE(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME,
146 TYPE *temp_var);
147 LIST_HEAD(HEADNAME, TYPE);
149 LIST_HEAD_INITIALIZER(LIST_HEAD head);
151 LIST_INIT(LIST_HEAD *head);
153 LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);
155 LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);
157 LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME);
159 LIST_NEXT(TYPE *elm, LIST_ENTRY NAME);
161 LIST_PREV(TYPE *elm, LIST_HEAD *head, TYPE, LIST_ENTRY NAME);
163 LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);
165 LIST_SWAP(LIST_HEAD *head1, LIST_HEAD *head2, TYPE, LIST_ENTRY NAME);
167 TAILQ_CLASS_ENTRY(CLASSTYPE);
169 TAILQ_CLASS_HEAD(HEADNAME, CLASSTYPE);
171 TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TAILQ_ENTRY NAME);
173 TAILQ_EMPTY(TAILQ_HEAD *head);
175 TAILQ_ENTRY(TYPE);
177 TAILQ_FIRST(TAILQ_HEAD *head);
179 TAILQ_FOREACH(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME);
181 TAILQ_FOREACH_FROM(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME);
183 TAILQ_FOREACH_FROM_SAFE(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME,
185 TYPE *temp_var);
186 TAILQ_FOREACH_REVERSE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
188 TAILQ_ENTRY NAME);
189 TAILQ_FOREACH_REVERSE_FROM(TYPE *var, TAILQ_HEAD *head, HEADNAME,
191 TAILQ_ENTRY NAME);
192 TAILQ_FOREACH_REVERSE_FROM_SAFE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
194 TAILQ_ENTRY NAME, TYPE *temp_var);
195 TAILQ_FOREACH_REVERSE_SAFE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
197 TAILQ_ENTRY NAME, TYPE *temp_var);
198 TAILQ_FOREACH_SAFE(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME,
200 TYPE *temp_var);
201 TAILQ_HEAD(HEADNAME, TYPE);
203 TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
205 TAILQ_INIT(TAILQ_HEAD *head);
207 TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
209 TAILQ_ENTRY NAME);
210 TAILQ_INSERT_BEFORE(TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME);
212 TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
214 TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
216 TAILQ_LAST(TAILQ_HEAD *head, HEADNAME);
218 TAILQ_NEXT(TYPE *elm, TAILQ_ENTRY NAME);
220 TAILQ_PREV(TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);
222 TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
224 TAILQ_SWAP(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TYPE, TAILQ_ENTRY NAME);
226
228 These macros define and operate on four types of data structures which
229 can be used in both C and C++ source code:
230 1. Lists
231 2. Singly-linked lists
232 3. Singly-linked tail queues
233 4. Tail queues
234 All four structures support the following functionality:
235 1. Insertion of a new entry at the head of the list.
236 2. Insertion of a new entry after any element in the list.
237 3. O(1) removal of an entry from the head of the list.
238 4. Forward traversal through the list.
239 5. Swapping the contents of two lists.
240 Singly-linked lists are the simplest of the four data structures and sup‐
242 port only the above functionality. Singly-linked lists are ideal for ap‐
243 plications with large datasets and few or no removals, or for implement‐
244 ing a LIFO queue. Singly-linked lists add the following functionality:
245 1. O(n) removal of any entry in the list.
246 2. O(n) concatenation of two lists.
247 Singly-linked tail queues add the following functionality:
249 1. Entries can be added at the end of a list.
250 2. O(n) removal of any entry in the list.
251 3. They may be concatenated.
252 However:
253 1. All list insertions must specify the head of the list.
254 2. Each head entry requires two pointers rather than one.
255 3. Code size is about 15% greater and operations run about 20%
256 slower than singly-linked lists.
257 Singly-linked tail queues are ideal for applications with large datasets
259 and few or no removals, or for implementing a FIFO queue.
260 All doubly linked types of data structures (lists and tail queues) addi‐
262 tionally allow:
263 1. Insertion of a new entry before any element in the list.
264 2. O(1) removal of any entry in the list.
265 However:
266 1. Each element requires two pointers rather than one.
267 2. Code size and execution time of operations (except for re‐
268 moval) is about twice that of the singly-linked data-struc‐
269 tures.
270 Linked lists are the simplest of the doubly linked data structures. They
272 add the following functionality over the above:
273 1. O(n) concatenation of two lists.
274 2. They may be traversed backwards.
275 However:
276 1. To traverse backwards, an entry to begin the traversal and the
277 list in which it is contained must be specified.
278 Tail queues add the following functionality:
280 1. Entries can be added at the end of a list.
281 2. They may be traversed backwards, from tail to head.
282 3. They may be concatenated.
283 However:
284 1. All list insertions and removals must specify the head of the
285 list.
286 2. Each head entry requires two pointers rather than one.
287 3. Code size is about 15% greater and operations run about 20%
288 slower than singly-linked lists.
289 In the macro definitions, TYPE is the name of a user defined structure.
291 The structure must contain a field called NAME which is of type
292 SLIST_ENTRY, STAILQ_ENTRY, LIST_ENTRY, or TAILQ_ENTRY. In the macro def‐
293 initions, CLASSTYPE is the name of a user defined class. The class must
294 contain a field called NAME which is of type SLIST_CLASS_ENTRY,
295 STAILQ_CLASS_ENTRY, LIST_CLASS_ENTRY, or TAILQ_CLASS_ENTRY. The argument
296 HEADNAME is the name of a user defined structure that must be declared
297 using the macros SLIST_HEAD, SLIST_CLASS_HEAD, STAILQ_HEAD,
298 STAILQ_CLASS_HEAD, LIST_HEAD, LIST_CLASS_HEAD, TAILQ_HEAD, or
299 TAILQ_CLASS_HEAD. See the examples below for further explanation of how
300 these macros are used.
301
303 A singly-linked list is headed by a structure defined by the SLIST_HEAD
304 macro. This structure contains a single pointer to the first element on
305 the list. The elements are singly linked for minimum space and pointer
306 manipulation overhead at the expense of O(n) removal for arbitrary ele‐
307 ments. New elements can be added to the list after an existing element
308 or at the head of the list. An SLIST_HEAD structure is declared as fol‐
309 lows:
310 SLIST_HEAD(HEADNAME, TYPE) head;
312 where HEADNAME is the name of the structure to be defined, and TYPE is
314 the type of the elements to be linked into the list. A pointer to the
315 head of the list can later be declared as:
316 struct HEADNAME *headp;
318 (The names head and headp are user selectable.)
320 The macro SLIST_HEAD_INITIALIZER evaluates to an initializer for the list
322 head.
323 The macro SLIST_CONCAT concatenates the list headed by head2 onto the end
325 of the one headed by head1 removing all entries from the former. Use of
326 this macro should be avoided as it traverses the entirety of the head1
327 list. A singly-linked tail queue should be used if this macro is needed
328 in high-usage code paths or to operate on long lists.
329 The macro SLIST_EMPTY evaluates to true if there are no elements in the
331 list.
332 The macro SLIST_ENTRY declares a structure that connects the elements in
334 the list.
335 The macro SLIST_FIRST returns the first element in the list or NULL if
337 the list is empty.
338 The macro SLIST_FOREACH traverses the list referenced by head in the for‐
340 ward direction, assigning each element in turn to var.
341 The macro SLIST_FOREACH_FROM behaves identically to SLIST_FOREACH when
343 var is NULL, else it treats var as a previously found SLIST element and
344 begins the loop at var instead of the first element in the SLIST refer‐
345 enced by head.
346 The macro SLIST_FOREACH_SAFE traverses the list referenced by head in the
348 forward direction, assigning each element in turn to var. However, un‐
349 like SLIST_FOREACH() here it is permitted to both remove var as well as
350 free it from within the loop safely without interfering with the traver‐
351 sal.
352 The macro SLIST_FOREACH_FROM_SAFE behaves identically to
354 SLIST_FOREACH_SAFE when var is NULL, else it treats var as a previously
355 found SLIST element and begins the loop at var instead of the first ele‐
356 ment in the SLIST referenced by head.
357 The macro SLIST_INIT initializes the list referenced by head.
359 The macro SLIST_INSERT_HEAD inserts the new element elm at the head of
361 the list.
362 The macro SLIST_INSERT_AFTER inserts the new element elm after the ele‐
364 ment listelm.
365 The macro SLIST_NEXT returns the next element in the list.
367 The macro SLIST_REMOVE_AFTER removes the element after elm from the list.
369 Unlike SLIST_REMOVE, this macro does not traverse the entire list.
370 The macro SLIST_REMOVE_HEAD removes the element elm from the head of the
372 list. For optimum efficiency, elements being removed from the head of
373 the list should explicitly use this macro instead of the generic
374 SLIST_REMOVE macro.
375 The macro SLIST_REMOVE removes the element elm from the list. Use of
377 this macro should be avoided as it traverses the entire list. A doubly-
378 linked list should be used if this macro is needed in high-usage code
379 paths or to operate on long lists.
380 The macro SLIST_SWAP swaps the contents of head1 and head2.
382
384 SLIST_HEAD(slisthead, entry) head =
385 SLIST_HEAD_INITIALIZER(head);
386 struct slisthead *headp; /* Singly-linked List head. */
387 struct entry {
388 ...
389 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
390 ...
391 } *n1, *n2, *n3, *np;
392 SLIST_INIT(&head); /* Initialize the list. */
394 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
396 SLIST_INSERT_HEAD(&head, n1, entries);
397 n2 = malloc(sizeof(struct entry)); /* Insert after. */
399 SLIST_INSERT_AFTER(n1, n2, entries);
400 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
402 free(n2);
403 n3 = SLIST_FIRST(&head);
405 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
406 free(n3);
407 /* Forward traversal. */
408 SLIST_FOREACH(np, &head, entries)
409 np-> ...
410 /* Safe forward traversal. */
411 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
412 np->do_stuff();
413 ...
414 SLIST_REMOVE(&head, np, entry, entries);
415 free(np);
416 }
417 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
419 n1 = SLIST_FIRST(&head);
420 SLIST_REMOVE_HEAD(&head, entries);
421 free(n1);
422 }
423
425 A singly-linked tail queue is headed by a structure defined by the
426 STAILQ_HEAD macro. This structure contains a pair of pointers, one to
427 the first element in the tail queue and the other to the last element in
428 the tail queue. The elements are singly linked for minimum space and
429 pointer manipulation overhead at the expense of O(n) removal for arbi‐
430 trary elements. New elements can be added to the tail queue after an ex‐
431 isting element, at the head of the tail queue, or at the end of the tail
432 queue. A STAILQ_HEAD structure is declared as follows:
433 STAILQ_HEAD(HEADNAME, TYPE) head;
435 where HEADNAME is the name of the structure to be defined, and TYPE is
437 the type of the elements to be linked into the tail queue. A pointer to
438 the head of the tail queue can later be declared as:
439 struct HEADNAME *headp;
441 (The names head and headp are user selectable.)
443 The macro STAILQ_HEAD_INITIALIZER evaluates to an initializer for the
445 tail queue head.
446 The macro STAILQ_CONCAT concatenates the tail queue headed by head2 onto
448 the end of the one headed by head1 removing all entries from the former.
449 The macro STAILQ_EMPTY evaluates to true if there are no items on the
451 tail queue.
452 The macro STAILQ_ENTRY declares a structure that connects the elements in
454 the tail queue.
455 The macro STAILQ_FIRST returns the first item on the tail queue or NULL
457 if the tail queue is empty.
458 The macro STAILQ_FOREACH traverses the tail queue referenced by head in
460 the forward direction, assigning each element in turn to var.
461 The macro STAILQ_FOREACH_FROM behaves identically to STAILQ_FOREACH when
463 var is NULL, else it treats var as a previously found STAILQ element and
464 begins the loop at var instead of the first element in the STAILQ refer‐
465 enced by head.
466 The macro STAILQ_FOREACH_SAFE traverses the tail queue referenced by head
468 in the forward direction, assigning each element in turn to var. How‐
469 ever, unlike STAILQ_FOREACH() here it is permitted to both remove var as
470 well as free it from within the loop safely without interfering with the
471 traversal.
472 The macro STAILQ_FOREACH_FROM_SAFE behaves identically to
474 STAILQ_FOREACH_SAFE when var is NULL, else it treats var as a previously
475 found STAILQ element and begins the loop at var instead of the first ele‐
476 ment in the STAILQ referenced by head.
477 The macro STAILQ_INIT initializes the tail queue referenced by head.
479 The macro STAILQ_INSERT_HEAD inserts the new element elm at the head of
481 the tail queue.
482 The macro STAILQ_INSERT_TAIL inserts the new element elm at the end of
484 the tail queue.
485 The macro STAILQ_INSERT_AFTER inserts the new element elm after the ele‐
487 ment listelm.
488 The macro STAILQ_LAST returns the last item on the tail queue. If the
490 tail queue is empty the return value is NULL.
491 The macro STAILQ_NEXT returns the next item on the tail queue, or NULL
493 this item is the last.
494 The macro STAILQ_REMOVE_AFTER removes the element after elm from the tail
496 queue. Unlike STAILQ_REMOVE, this macro does not traverse the entire
497 tail queue.
498 The macro STAILQ_REMOVE_HEAD removes the element at the head of the tail
500 queue. For optimum efficiency, elements being removed from the head of
501 the tail queue should use this macro explicitly rather than the generic
502 STAILQ_REMOVE macro.
503 The macro STAILQ_REMOVE removes the element elm from the tail queue. Use
505 of this macro should be avoided as it traverses the entire list. A dou‐
506 bly-linked tail queue should be used if this macro is needed in high-us‐
507 age code paths or to operate on long tail queues.
508 The macro STAILQ_SWAP swaps the contents of head1 and head2.
510
512 STAILQ_HEAD(stailhead, entry) head =
513 STAILQ_HEAD_INITIALIZER(head);
514 struct stailhead *headp; /* Singly-linked tail queue head. */
515 struct entry {
516 ...
517 STAILQ_ENTRY(entry) entries; /* Tail queue. */
518 ...
519 } *n1, *n2, *n3, *np;
520 STAILQ_INIT(&head); /* Initialize the queue. */
522 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
524 STAILQ_INSERT_HEAD(&head, n1, entries);
525 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
527 STAILQ_INSERT_TAIL(&head, n1, entries);
528 n2 = malloc(sizeof(struct entry)); /* Insert after. */
530 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
531 /* Deletion. */
532 STAILQ_REMOVE(&head, n2, entry, entries);
533 free(n2);
534 /* Deletion from the head. */
535 n3 = STAILQ_FIRST(&head);
536 STAILQ_REMOVE_HEAD(&head, entries);
537 free(n3);
538 /* Forward traversal. */
539 STAILQ_FOREACH(np, &head, entries)
540 np-> ...
541 /* Safe forward traversal. */
542 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
543 np->do_stuff();
544 ...
545 STAILQ_REMOVE(&head, np, entry, entries);
546 free(np);
547 }
548 /* TailQ Deletion. */
549 while (!STAILQ_EMPTY(&head)) {
550 n1 = STAILQ_FIRST(&head);
551 STAILQ_REMOVE_HEAD(&head, entries);
552 free(n1);
553 }
554 /* Faster TailQ Deletion. */
555 n1 = STAILQ_FIRST(&head);
556 while (n1 != NULL) {
557 n2 = STAILQ_NEXT(n1, entries);
558 free(n1);
559 n1 = n2;
560 }
561 STAILQ_INIT(&head);
562
564 A list is headed by a structure defined by the LIST_HEAD macro. This
565 structure contains a single pointer to the first element on the list.
566 The elements are doubly linked so that an arbitrary element can be re‐
567 moved without traversing the list. New elements can be added to the list
568 after an existing element, before an existing element, or at the head of
569 the list. A LIST_HEAD structure is declared as follows:
570 LIST_HEAD(HEADNAME, TYPE) head;
572 where HEADNAME is the name of the structure to be defined, and TYPE is
574 the type of the elements to be linked into the list. A pointer to the
575 head of the list can later be declared as:
576 struct HEADNAME *headp;
578 (The names head and headp are user selectable.)
580 The macro LIST_HEAD_INITIALIZER evaluates to an initializer for the list
582 head.
583 The macro LIST_CONCAT concatenates the list headed by head2 onto the end
585 of the one headed by head1 removing all entries from the former. Use of
586 this macro should be avoided as it traverses the entirety of the head1
587 list. A tail queue should be used if this macro is needed in high-usage
588 code paths or to operate on long lists.
589 The macro LIST_EMPTY evaluates to true if there are no elements in the
591 list.
592 The macro LIST_ENTRY declares a structure that connects the elements in
594 the list.
595 The macro LIST_FIRST returns the first element in the list or NULL if the
597 list is empty.
598 The macro LIST_FOREACH traverses the list referenced by head in the for‐
600 ward direction, assigning each element in turn to var.
601 The macro LIST_FOREACH_FROM behaves identically to LIST_FOREACH when var
603 is NULL, else it treats var as a previously found LIST element and begins
604 the loop at var instead of the first element in the LIST referenced by
605 head.
606 The macro LIST_FOREACH_SAFE traverses the list referenced by head in the
608 forward direction, assigning each element in turn to var. However, un‐
609 like LIST_FOREACH() here it is permitted to both remove var as well as
610 free it from within the loop safely without interfering with the traver‐
611 sal.
612 The macro LIST_FOREACH_FROM_SAFE behaves identically to LIST_FOREACH_SAFE
614 when var is NULL, else it treats var as a previously found LIST element
615 and begins the loop at var instead of the first element in the LIST ref‐
616 erenced by head.
617 The macro LIST_INIT initializes the list referenced by head.
619 The macro LIST_INSERT_HEAD inserts the new element elm at the head of the
621 list.
622 The macro LIST_INSERT_AFTER inserts the new element elm after the element
624 listelm.
625 The macro LIST_INSERT_BEFORE inserts the new element elm before the ele‐
627 ment listelm.
628 The macro LIST_NEXT returns the next element in the list, or NULL if this
630 is the last.
631 The macro LIST_PREV returns the previous element in the list, or NULL if
633 this is the first. List head must contain element elm.
634 The macro LIST_REMOVE removes the element elm from the list.
636 The macro LIST_SWAP swaps the contents of head1 and head2.
638
640 LIST_HEAD(listhead, entry) head =
641 LIST_HEAD_INITIALIZER(head);
642 struct listhead *headp; /* List head. */
643 struct entry {
644 ...
645 LIST_ENTRY(entry) entries; /* List. */
646 ...
647 } *n1, *n2, *n3, *np, *np_temp;
648 LIST_INIT(&head); /* Initialize the list. */
650 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
652 LIST_INSERT_HEAD(&head, n1, entries);
653 n2 = malloc(sizeof(struct entry)); /* Insert after. */
655 LIST_INSERT_AFTER(n1, n2, entries);
656 n3 = malloc(sizeof(struct entry)); /* Insert before. */
658 LIST_INSERT_BEFORE(n2, n3, entries);
659 LIST_REMOVE(n2, entries); /* Deletion. */
661 free(n2);
662 /* Forward traversal. */
663 LIST_FOREACH(np, &head, entries)
664 np-> ...
665 /* Safe forward traversal. */
667 LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
668 np->do_stuff();
669 ...
670 LIST_REMOVE(np, entries);
671 free(np);
672 }
673 while (!LIST_EMPTY(&head)) { /* List Deletion. */
675 n1 = LIST_FIRST(&head);
676 LIST_REMOVE(n1, entries);
677 free(n1);
678 }
679 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
681 while (n1 != NULL) {
682 n2 = LIST_NEXT(n1, entries);
683 free(n1);
684 n1 = n2;
685 }
686 LIST_INIT(&head);
687
689 A tail queue is headed by a structure defined by the TAILQ_HEAD macro.
690 This structure contains a pair of pointers, one to the first element in
691 the tail queue and the other to the last element in the tail queue. The
692 elements are doubly linked so that an arbitrary element can be removed
693 without traversing the tail queue. New elements can be added to the tail
694 queue after an existing element, before an existing element, at the head
695 of the tail queue, or at the end of the tail queue. A TAILQ_HEAD struc‐
696 ture is declared as follows:
697 TAILQ_HEAD(HEADNAME, TYPE) head;
699 where HEADNAME is the name of the structure to be defined, and TYPE is
701 the type of the elements to be linked into the tail queue. A pointer to
702 the head of the tail queue can later be declared as:
703 struct HEADNAME *headp;
705 (The names head and headp are user selectable.)
707 The macro TAILQ_HEAD_INITIALIZER evaluates to an initializer for the tail
709 queue head.
710 The macro TAILQ_CONCAT concatenates the tail queue headed by head2 onto
712 the end of the one headed by head1 removing all entries from the former.
713 The macro TAILQ_EMPTY evaluates to true if there are no items on the tail
715 queue.
716 The macro TAILQ_ENTRY declares a structure that connects the elements in
718 the tail queue.
719 The macro TAILQ_FIRST returns the first item on the tail queue or NULL if
721 the tail queue is empty.
722 The macro TAILQ_FOREACH traverses the tail queue referenced by head in
724 the forward direction, assigning each element in turn to var. var is set
725 to NULL if the loop completes normally, or if there were no elements.
726 The macro TAILQ_FOREACH_FROM behaves identically to TAILQ_FOREACH when
728 var is NULL, else it treats var as a previously found TAILQ element and
729 begins the loop at var instead of the first element in the TAILQ refer‐
730 enced by head.
731 The macro TAILQ_FOREACH_REVERSE traverses the tail queue referenced by
733 head in the reverse direction, assigning each element in turn to var.
734 The macro TAILQ_FOREACH_REVERSE_FROM behaves identically to
736 TAILQ_FOREACH_REVERSE when var is NULL, else it treats var as a previ‐
737 ously found TAILQ element and begins the reverse loop at var instead of
738 the last element in the TAILQ referenced by head.
739 The macros TAILQ_FOREACH_SAFE and TAILQ_FOREACH_REVERSE_SAFE traverse the
741 list referenced by head in the forward or reverse direction respectively,
742 assigning each element in turn to var. However, unlike their unsafe
743 counterparts, TAILQ_FOREACH and TAILQ_FOREACH_REVERSE make it possible to
744 both remove var as well as free it from within the loop safely without
745 interfering with the traversal.
746 The macro TAILQ_FOREACH_FROM_SAFE behaves identically to
748 TAILQ_FOREACH_SAFE when var is NULL, else it treats var as a previously
749 found TAILQ element and begins the loop at var instead of the first ele‐
750 ment in the TAILQ referenced by head.
751 The macro TAILQ_FOREACH_REVERSE_FROM_SAFE behaves identically to
753 TAILQ_FOREACH_REVERSE_SAFE when var is NULL, else it treats var as a pre‐
754 viously found TAILQ element and begins the reverse loop at var instead of
755 the last element in the TAILQ referenced by head.
756 The macro TAILQ_INIT initializes the tail queue referenced by head.
758 The macro TAILQ_INSERT_HEAD inserts the new element elm at the head of
760 the tail queue.
761 The macro TAILQ_INSERT_TAIL inserts the new element elm at the end of the
763 tail queue.
764 The macro TAILQ_INSERT_AFTER inserts the new element elm after the ele‐
766 ment listelm.
767 The macro TAILQ_INSERT_BEFORE inserts the new element elm before the ele‐
769 ment listelm.
770 The macro TAILQ_LAST returns the last item on the tail queue. If the
772 tail queue is empty the return value is NULL.
773 The macro TAILQ_NEXT returns the next item on the tail queue, or NULL if
775 this item is the last.
776 The macro TAILQ_PREV returns the previous item on the tail queue, or NULL
778 if this item is the first.
779 The macro TAILQ_REMOVE removes the element elm from the tail queue.
781 The macro TAILQ_SWAP swaps the contents of head1 and head2.
783
785 TAILQ_HEAD(tailhead, entry) head =
786 TAILQ_HEAD_INITIALIZER(head);
787 struct tailhead *headp; /* Tail queue head. */
788 struct entry {
789 ...
790 TAILQ_ENTRY(entry) entries; /* Tail queue. */
791 ...
792 } *n1, *n2, *n3, *np;
793 TAILQ_INIT(&head); /* Initialize the queue. */
795 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
797 TAILQ_INSERT_HEAD(&head, n1, entries);
798 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
800 TAILQ_INSERT_TAIL(&head, n1, entries);
801 n2 = malloc(sizeof(struct entry)); /* Insert after. */
803 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
804 n3 = malloc(sizeof(struct entry)); /* Insert before. */
806 TAILQ_INSERT_BEFORE(n2, n3, entries);
807 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
809 free(n2);
810 /* Forward traversal. */
811 TAILQ_FOREACH(np, &head, entries)
812 np-> ...
813 /* Safe forward traversal. */
814 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
815 np->do_stuff();
816 ...
817 TAILQ_REMOVE(&head, np, entries);
818 free(np);
819 }
820 /* Reverse traversal. */
821 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
822 np-> ...
823 /* TailQ Deletion. */
824 while (!TAILQ_EMPTY(&head)) {
825 n1 = TAILQ_FIRST(&head);
826 TAILQ_REMOVE(&head, n1, entries);
827 free(n1);
828 }
829 /* Faster TailQ Deletion. */
830 n1 = TAILQ_FIRST(&head);
831 while (n1 != NULL) {
832 n2 = TAILQ_NEXT(n1, entries);
833 free(n1);
834 n1 = n2;
835 }
836 TAILQ_INIT(&head);
837
839 When debugging queue(3), it can be useful to trace queue changes. To en‐
840 able tracing, define the macro QUEUE_MACRO_DEBUG_TRACE at compile time.
841 It can also be useful to trash pointers that have been unlinked from a
843 queue, to detect use after removal. To enable pointer trashing, define
844 the macro QUEUE_MACRO_DEBUG_TRASH at compile time. The macro
845 QMD_IS_TRASHED(void *ptr) returns true if ptr has been trashed by the
846 QUEUE_MACRO_DEBUG_TRASH option.
847
849 tree(3bsd)
850
852 The queue functions first appeared in 4.4BSD.
853BSD September 8, 2016 BSD