1QUEUE(3bsd) LOCAL QUEUE(3bsd)
2
4 SLIST_EMPTY, SLIST_ENTRY, SLIST_FIRST, SLIST_FOREACH, SLIST_FOREACH_FROM,
5 SLIST_FOREACH_SAFE, SLIST_FOREACH_FROM_SAFE, SLIST_HEAD,
6 SLIST_HEAD_INITIALIZER, SLIST_INIT, SLIST_INSERT_AFTER,
7 SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE_AFTER, SLIST_REMOVE_HEAD,
8 SLIST_REMOVE, SLIST_SWAP, STAILQ_CONCAT, STAILQ_EMPTY, STAILQ_ENTRY,
9 STAILQ_FIRST, STAILQ_FOREACH, STAILQ_FOREACH_FROM, STAILQ_FOREACH_SAFE,
10 STAILQ_FOREACH_FROM_SAFE, STAILQ_HEAD, STAILQ_HEAD_INITIALIZER,
11 STAILQ_INIT, STAILQ_INSERT_AFTER, STAILQ_INSERT_HEAD, STAILQ_INSERT_TAIL,
12 STAILQ_LAST, STAILQ_NEXT, STAILQ_REMOVE_AFTER, STAILQ_REMOVE_HEAD,
13 STAILQ_REMOVE, STAILQ_SWAP, LIST_EMPTY, LIST_ENTRY, LIST_FIRST,
14 LIST_FOREACH, LIST_FOREACH_FROM, LIST_FOREACH_SAFE,
15 LIST_FOREACH_FROM_SAFE, LIST_HEAD, LIST_HEAD_INITIALIZER, LIST_INIT,
16 LIST_INSERT_AFTER, LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_NEXT,
17 LIST_PREV, LIST_REMOVE, LIST_SWAP, TAILQ_CONCAT, TAILQ_EMPTY,
18 TAILQ_ENTRY, TAILQ_FIRST, TAILQ_FOREACH, TAILQ_FOREACH_FROM,
19 TAILQ_FOREACH_SAFE, TAILQ_FOREACH_FROM_SAFE, TAILQ_FOREACH_REVERSE,
20 TAILQ_FOREACH_REVERSE_FROM, TAILQ_FOREACH_REVERSE_SAFE,
21 TAILQ_FOREACH_REVERSE_FROM_SAFE, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER,
22 TAILQ_INIT, TAILQ_INSERT_AFTER, TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD,
23 TAILQ_INSERT_TAIL, TAILQ_LAST, TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE,
24 TAILQ_SWAP — implementations of singly-linked lists, singly-linked tail
25 queues, lists and tail queues
26
28 #include <sys/queue.h>
29 (See libbsd(7) for include usage.)
30 SLIST_EMPTY(SLIST_HEAD *head);
32 SLIST_ENTRY(TYPE);
34 SLIST_FIRST(SLIST_HEAD *head);
36 SLIST_FOREACH(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
38 SLIST_FOREACH_FROM(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
40 SLIST_FOREACH_SAFE(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME,
42 TYPE *temp_var);
43 SLIST_FOREACH_FROM_SAFE(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME,
45 TYPE *temp_var);
46 SLIST_HEAD(HEADNAME, TYPE);
48 SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
50 SLIST_INIT(SLIST_HEAD *head);
52 SLIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, SLIST_ENTRY NAME);
54 SLIST_INSERT_HEAD(SLIST_HEAD *head, TYPE *elm, SLIST_ENTRY NAME);
56 SLIST_NEXT(TYPE *elm, SLIST_ENTRY NAME);
58 SLIST_REMOVE_AFTER(TYPE *elm, SLIST_ENTRY NAME);
60 SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME);
62 SLIST_REMOVE(SLIST_HEAD *head, TYPE *elm, TYPE, SLIST_ENTRY NAME);
64 SLIST_SWAP(SLIST_HEAD *head1, SLIST_HEAD *head2, SLIST_ENTRY NAME);
66 STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);
68 STAILQ_EMPTY(STAILQ_HEAD *head);
70 STAILQ_ENTRY(TYPE);
72 STAILQ_FIRST(STAILQ_HEAD *head);
74 STAILQ_FOREACH(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
76 STAILQ_FOREACH_FROM(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
78 STAILQ_FOREACH_SAFE(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME,
80 TYPE *temp_var);
81 STAILQ_FOREACH_FROM_SAFE(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME,
83 TYPE *temp_var);
84 STAILQ_HEAD(HEADNAME, TYPE);
86 STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
88 STAILQ_INIT(STAILQ_HEAD *head);
90 STAILQ_INSERT_AFTER(STAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
92 STAILQ_ENTRY NAME);
93 STAILQ_INSERT_HEAD(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
95 STAILQ_INSERT_TAIL(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
97 STAILQ_LAST(STAILQ_HEAD *head, TYPE, STAILQ_ENTRY NAME);
99 STAILQ_NEXT(TYPE *elm, STAILQ_ENTRY NAME);
101 STAILQ_REMOVE_AFTER(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
103 STAILQ_REMOVE_HEAD(STAILQ_HEAD *head, STAILQ_ENTRY NAME);
105 STAILQ_REMOVE(STAILQ_HEAD *head, TYPE *elm, TYPE, STAILQ_ENTRY NAME);
107 STAILQ_SWAP(STAILQ_HEAD *head1, STAILQ_HEAD *head2, STAILQ_ENTRY NAME);
109 LIST_EMPTY(LIST_HEAD *head);
111 LIST_ENTRY(TYPE);
113 LIST_FIRST(LIST_HEAD *head);
115 LIST_FOREACH(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);
117 LIST_FOREACH_FROM(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);
119 LIST_FOREACH_SAFE(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME,
121 TYPE *temp_var);
122 LIST_FOREACH_FROM_SAFE(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME,
124 TYPE *temp_var);
125 LIST_HEAD(HEADNAME, TYPE);
127 LIST_HEAD_INITIALIZER(LIST_HEAD head);
129 LIST_INIT(LIST_HEAD *head);
131 LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);
133 LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);
135 LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME);
137 LIST_NEXT(TYPE *elm, LIST_ENTRY NAME);
139 LIST_PREV(TYPE *elm, LIST_HEAD *head, TYPE, LIST_ENTRY NAME);
141 LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);
143 LIST_SWAP(LIST_HEAD *head1, LIST_HEAD *head2, TYPE, LIST_ENTRY NAME);
145 TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TAILQ_ENTRY NAME);
147 TAILQ_EMPTY(TAILQ_HEAD *head);
149 TAILQ_ENTRY(TYPE);
151 TAILQ_FIRST(TAILQ_HEAD *head);
153 TAILQ_FOREACH(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME);
155 TAILQ_FOREACH_FROM(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME);
157 TAILQ_FOREACH_SAFE(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME,
159 TYPE *temp_var);
160 TAILQ_FOREACH_FROM_SAFE(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME,
162 TYPE *temp_var);
163 TAILQ_FOREACH_REVERSE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
165 TAILQ_ENTRY NAME);
166 TAILQ_FOREACH_REVERSE_FROM(TYPE *var, TAILQ_HEAD *head, HEADNAME,
168 TAILQ_ENTRY NAME);
169 TAILQ_FOREACH_REVERSE_SAFE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
171 TAILQ_ENTRY NAME, TYPE *temp_var);
172 TAILQ_FOREACH_REVERSE_FROM_SAFE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
174 TAILQ_ENTRY NAME, TYPE *temp_var);
175 TAILQ_HEAD(HEADNAME, TYPE);
177 TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
179 TAILQ_INIT(TAILQ_HEAD *head);
181 TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
183 TAILQ_ENTRY NAME);
184 TAILQ_INSERT_BEFORE(TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME);
186 TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
188 TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
190 TAILQ_LAST(TAILQ_HEAD *head, HEADNAME);
192 TAILQ_NEXT(TYPE *elm, TAILQ_ENTRY NAME);
194 TAILQ_PREV(TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);
196 TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
198 TAILQ_SWAP(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TYPE, TAILQ_ENTRY NAME);
200
202 These macros define and operate on four types of data structures: singly-
203 linked lists, singly-linked tail queues, lists, and tail queues. All
204 four structures support the following functionality:
205 1. Insertion of a new entry at the head of the list.
206 2. Insertion of a new entry after any element in the list.
207 3. O(1) removal of an entry from the head of the list.
208 4. Forward traversal through the list.
209 5. Swapping the contents of two lists.
210 Singly-linked lists are the simplest of the four data structures and sup‐
212 port only the above functionality. Singly-linked lists are ideal for
213 applications with large datasets and few or no removals, or for imple‐
214 menting a LIFO queue. Singly-linked lists add the following functional‐
215 ity:
216 1. O(n) removal of any entry in the list.
217 Singly-linked tail queues add the following functionality:
219 1. Entries can be added at the end of a list.
220 2. O(n) removal of any entry in the list.
221 3. They may be concatenated.
222 However:
223 1. All list insertions must specify the head of the list.
224 2. Each head entry requires two pointers rather than one.
225 3. Code size is about 15% greater and operations run about 20%
226 slower than singly-linked lists.
227 Singly-linked tail queues are ideal for applications with large datasets
229 and few or no removals, or for implementing a FIFO queue.
230 All doubly linked types of data structures (lists and tail queues) addi‐
232 tionally allow:
233 1. Insertion of a new entry before any element in the list.
234 2. O(1) removal of any entry in the list.
235 However:
236 1. Each element requires two pointers rather than one.
237 2. Code size and execution time of operations (except for
238 removal) is about twice that of the singly-linked data-struc‐
239 tures.
240 Linked lists are the simplest of the doubly linked data structures. They
242 add the following functionality over the above:
243 1. They may be traversed backwards.
244 However:
245 1. To traverse backwards, an entry to begin the traversal and the
246 list in which it is contained must be specified.
247 Tail queues add the following functionality:
249 1. Entries can be added at the end of a list.
250 2. They may be traversed backwards, from tail to head.
251 3. They may be concatenated.
252 However:
253 1. All list insertions and removals must specify the head of the
254 list.
255 2. Each head entry requires two pointers rather than one.
256 3. Code size is about 15% greater and operations run about 20%
257 slower than singly-linked lists.
258 In the macro definitions, TYPE is the name of a user defined structure,
260 that must contain a field of type SLIST_ENTRY, STAILQ_ENTRY, LIST_ENTRY,
261 or TAILQ_ENTRY, named NAME. The argument HEADNAME is the name of a user
262 defined structure that must be declared using the macros SLIST_HEAD,
263 STAILQ_HEAD, LIST_HEAD, or TAILQ_HEAD. See the examples below for fur‐
264 ther explanation of how these macros are used.
265
267 A singly-linked list is headed by a structure defined by the SLIST_HEAD
268 macro. This structure contains a single pointer to the first element on
269 the list. The elements are singly linked for minimum space and pointer
270 manipulation overhead at the expense of O(n) removal for arbitrary ele‐
271 ments. New elements can be added to the list after an existing element
272 or at the head of the list. An SLIST_HEAD structure is declared as fol‐
273 lows:
274 SLIST_HEAD(HEADNAME, TYPE) head;
276 where HEADNAME is the name of the structure to be defined, and TYPE is
278 the type of the elements to be linked into the list. A pointer to the
279 head of the list can later be declared as:
280 struct HEADNAME *headp;
282 (The names head and headp are user selectable.)
284 The macro SLIST_HEAD_INITIALIZER evaluates to an initializer for the list
286 head.
287 The macro SLIST_EMPTY evaluates to true if there are no elements in the
289 list.
290 The macro SLIST_ENTRY declares a structure that connects the elements in
292 the list.
293 The macro SLIST_FIRST returns the first element in the list or NULL if
295 the list is empty.
296 The macro SLIST_FOREACH traverses the list referenced by head in the for‐
298 ward direction, assigning each element in turn to var.
299 The macro SLIST_FOREACH_FROM behaves identically to SLIST_FOREACH when
301 var is NULL, else it treats var as a previously found SLIST element and
302 begins the loop at var instead of the first element in the SLIST refer‐
303 enced by head.
304 The macro SLIST_FOREACH_SAFE traverses the list referenced by head in the
306 forward direction, assigning each element in turn to var. However,
307 unlike SLIST_FOREACH() here it is permitted to both remove var as well as
308 free it from within the loop safely without interfering with the traver‐
309 sal.
310 The macro SLIST_FOREACH_FROM_SAFE behaves identically to
312 SLIST_FOREACH_SAFE when var is NULL, else it treats var as a previously
313 found SLIST element and begins the loop at var instead of the first ele‐
314 ment in the SLIST referenced by head.
315 The macro SLIST_INIT initializes the list referenced by head.
317 The macro SLIST_INSERT_HEAD inserts the new element elm at the head of
319 the list.
320 The macro SLIST_INSERT_AFTER inserts the new element elm after the ele‐
322 ment listelm.
323 The macro SLIST_NEXT returns the next element in the list.
325 The macro SLIST_REMOVE_AFTER removes the element after elm from the list.
327 Unlike SLIST_REMOVE, this macro does not traverse the entire list.
328 The macro SLIST_REMOVE_HEAD removes the element elm from the head of the
330 list. For optimum efficiency, elements being removed from the head of
331 the list should explicitly use this macro instead of the generic
332 SLIST_REMOVE macro.
333 The macro SLIST_REMOVE removes the element elm from the list.
335 The macro SLIST_SWAP swaps the contents of head1 and head2.
337
339 SLIST_HEAD(slisthead, entry) head =
340 SLIST_HEAD_INITIALIZER(head);
341 struct slisthead *headp; /* Singly-linked List head. */
342 struct entry {
343 ...
344 SLIST_ENTRY(entry) entries; /* Singly-linked List. */
345 ...
346 } *n1, *n2, *n3, *np;
347 SLIST_INIT(&head); /* Initialize the list. */
349 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
351 SLIST_INSERT_HEAD(&head, n1, entries);
352 n2 = malloc(sizeof(struct entry)); /* Insert after. */
354 SLIST_INSERT_AFTER(n1, n2, entries);
355 SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
357 free(n2);
358 n3 = SLIST_FIRST(&head);
360 SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */
361 free(n3);
362 /* Forward traversal. */
363 SLIST_FOREACH(np, &head, entries)
364 np-> ...
365 /* Safe forward traversal. */
366 SLIST_FOREACH_SAFE(np, &head, entries, np_temp) {
367 np->do_stuff();
368 ...
369 SLIST_REMOVE(&head, np, entry, entries);
370 free(np);
371 }
372 while (!SLIST_EMPTY(&head)) { /* List Deletion. */
374 n1 = SLIST_FIRST(&head);
375 SLIST_REMOVE_HEAD(&head, entries);
376 free(n1);
377 }
378
380 A singly-linked tail queue is headed by a structure defined by the
381 STAILQ_HEAD macro. This structure contains a pair of pointers, one to
382 the first element in the tail queue and the other to the last element in
383 the tail queue. The elements are singly linked for minimum space and
384 pointer manipulation overhead at the expense of O(n) removal for arbi‐
385 trary elements. New elements can be added to the tail queue after an
386 existing element, at the head of the tail queue, or at the end of the
387 tail queue. A STAILQ_HEAD structure is declared as follows:
388 STAILQ_HEAD(HEADNAME, TYPE) head;
390 where HEADNAME is the name of the structure to be defined, and TYPE is
392 the type of the elements to be linked into the tail queue. A pointer to
393 the head of the tail queue can later be declared as:
394 struct HEADNAME *headp;
396 (The names head and headp are user selectable.)
398 The macro STAILQ_HEAD_INITIALIZER evaluates to an initializer for the
400 tail queue head.
401 The macro STAILQ_CONCAT concatenates the tail queue headed by head2 onto
403 the end of the one headed by head1 removing all entries from the former.
404 The macro STAILQ_EMPTY evaluates to true if there are no items on the
406 tail queue.
407 The macro STAILQ_ENTRY declares a structure that connects the elements in
409 the tail queue.
410 The macro STAILQ_FIRST returns the first item on the tail queue or NULL
412 if the tail queue is empty.
413 The macro STAILQ_FOREACH traverses the tail queue referenced by head in
415 the forward direction, assigning each element in turn to var.
416 The macro STAILQ_FOREACH_FROM behaves identically to STAILQ_FOREACH when
418 var is NULL, else it treats var as a previously found STAILQ element and
419 begins the loop at var instead of the first element in the STAILQ refer‐
420 enced by head.
421 The macro STAILQ_FOREACH_SAFE traverses the tail queue referenced by head
423 in the forward direction, assigning each element in turn to var. How‐
424 ever, unlike STAILQ_FOREACH() here it is permitted to both remove var as
425 well as free it from within the loop safely without interfering with the
426 traversal.
427 The macro STAILQ_FOREACH_FROM_SAFE behaves identically to
429 STAILQ_FOREACH_SAFE when var is NULL, else it treats var as a previously
430 found STAILQ element and begins the loop at var instead of the first ele‐
431 ment in the STAILQ referenced by head.
432 The macro STAILQ_INIT initializes the tail queue referenced by head.
434 The macro STAILQ_INSERT_HEAD inserts the new element elm at the head of
436 the tail queue.
437 The macro STAILQ_INSERT_TAIL inserts the new element elm at the end of
439 the tail queue.
440 The macro STAILQ_INSERT_AFTER inserts the new element elm after the ele‐
442 ment listelm.
443 The macro STAILQ_LAST returns the last item on the tail queue. If the
445 tail queue is empty the return value is NULL.
446 The macro STAILQ_NEXT returns the next item on the tail queue, or NULL
448 this item is the last.
449 The macro STAILQ_REMOVE_AFTER removes the element after elm from the tail
451 queue. Unlike STAILQ_REMOVE, this macro does not traverse the entire
452 tail queue.
453 The macro STAILQ_REMOVE_HEAD removes the element at the head of the tail
455 queue. For optimum efficiency, elements being removed from the head of
456 the tail queue should use this macro explicitly rather than the generic
457 STAILQ_REMOVE macro.
458 The macro STAILQ_REMOVE removes the element elm from the tail queue.
460 The macro STAILQ_SWAP swaps the contents of head1 and head2.
462
464 STAILQ_HEAD(stailhead, entry) head =
465 STAILQ_HEAD_INITIALIZER(head);
466 struct stailhead *headp; /* Singly-linked tail queue head. */
467 struct entry {
468 ...
469 STAILQ_ENTRY(entry) entries; /* Tail queue. */
470 ...
471 } *n1, *n2, *n3, *np;
472 STAILQ_INIT(&head); /* Initialize the queue. */
474 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
476 STAILQ_INSERT_HEAD(&head, n1, entries);
477 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
479 STAILQ_INSERT_TAIL(&head, n1, entries);
480 n2 = malloc(sizeof(struct entry)); /* Insert after. */
482 STAILQ_INSERT_AFTER(&head, n1, n2, entries);
483 /* Deletion. */
484 STAILQ_REMOVE(&head, n2, entry, entries);
485 free(n2);
486 /* Deletion from the head. */
487 n3 = STAILQ_FIRST(&head);
488 STAILQ_REMOVE_HEAD(&head, entries);
489 free(n3);
490 /* Forward traversal. */
491 STAILQ_FOREACH(np, &head, entries)
492 np-> ...
493 /* Safe forward traversal. */
494 STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
495 np->do_stuff();
496 ...
497 STAILQ_REMOVE(&head, np, entry, entries);
498 free(np);
499 }
500 /* TailQ Deletion. */
501 while (!STAILQ_EMPTY(&head)) {
502 n1 = STAILQ_FIRST(&head);
503 STAILQ_REMOVE_HEAD(&head, entries);
504 free(n1);
505 }
506 /* Faster TailQ Deletion. */
507 n1 = STAILQ_FIRST(&head);
508 while (n1 != NULL) {
509 n2 = STAILQ_NEXT(n1, entries);
510 free(n1);
511 n1 = n2;
512 }
513 STAILQ_INIT(&head);
514
516 A list is headed by a structure defined by the LIST_HEAD macro. This
517 structure contains a single pointer to the first element on the list.
518 The elements are doubly linked so that an arbitrary element can be
519 removed without traversing the list. New elements can be added to the
520 list after an existing element, before an existing element, or at the
521 head of the list. A LIST_HEAD structure is declared as follows:
522 LIST_HEAD(HEADNAME, TYPE) head;
524 where HEADNAME is the name of the structure to be defined, and TYPE is
526 the type of the elements to be linked into the list. A pointer to the
527 head of the list can later be declared as:
528 struct HEADNAME *headp;
530 (The names head and headp are user selectable.)
532 The macro LIST_HEAD_INITIALIZER evaluates to an initializer for the list
534 head.
535 The macro LIST_EMPTY evaluates to true if there are no elements in the
537 list.
538 The macro LIST_ENTRY declares a structure that connects the elements in
540 the list.
541 The macro LIST_FIRST returns the first element in the list or NULL if the
543 list is empty.
544 The macro LIST_FOREACH traverses the list referenced by head in the for‐
546 ward direction, assigning each element in turn to var.
547 The macro LIST_FOREACH_FROM behaves identically to LIST_FOREACH when var
549 is NULL, else it treats var as a previously found LIST element and begins
550 the loop at var instead of the first element in the LIST referenced by
551 head.
552 The macro LIST_FOREACH_SAFE traverses the list referenced by head in the
554 forward direction, assigning each element in turn to var. However,
555 unlike LIST_FOREACH() here it is permitted to both remove var as well as
556 free it from within the loop safely without interfering with the traver‐
557 sal.
558 The macro LIST_FOREACH_FROM_SAFE behaves identically to LIST_FOREACH_SAFE
560 when var is NULL, else it treats var as a previously found LIST element
561 and begins the loop at var instead of the first element in the LIST ref‐
562 erenced by head.
563 The macro LIST_INIT initializes the list referenced by head.
565 The macro LIST_INSERT_HEAD inserts the new element elm at the head of the
567 list.
568 The macro LIST_INSERT_AFTER inserts the new element elm after the element
570 listelm.
571 The macro LIST_INSERT_BEFORE inserts the new element elm before the ele‐
573 ment listelm.
574 The macro LIST_NEXT returns the next element in the list, or NULL if this
576 is the last.
577 The macro LIST_PREV returns the previous element in the list, or NULL if
579 this is the first. List head must contain element elm.
580 The macro LIST_REMOVE removes the element elm from the list.
582 The macro LIST_SWAP swaps the contents of head1 and head2.
584
586 LIST_HEAD(listhead, entry) head =
587 LIST_HEAD_INITIALIZER(head);
588 struct listhead *headp; /* List head. */
589 struct entry {
590 ...
591 LIST_ENTRY(entry) entries; /* List. */
592 ...
593 } *n1, *n2, *n3, *np, *np_temp;
594 LIST_INIT(&head); /* Initialize the list. */
596 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
598 LIST_INSERT_HEAD(&head, n1, entries);
599 n2 = malloc(sizeof(struct entry)); /* Insert after. */
601 LIST_INSERT_AFTER(n1, n2, entries);
602 n3 = malloc(sizeof(struct entry)); /* Insert before. */
604 LIST_INSERT_BEFORE(n2, n3, entries);
605 LIST_REMOVE(n2, entries); /* Deletion. */
607 free(n2);
608 /* Forward traversal. */
609 LIST_FOREACH(np, &head, entries)
610 np-> ...
611 /* Safe forward traversal. */
613 LIST_FOREACH_SAFE(np, &head, entries, np_temp) {
614 np->do_stuff();
615 ...
616 LIST_REMOVE(np, entries);
617 free(np);
618 }
619 while (!LIST_EMPTY(&head)) { /* List Deletion. */
621 n1 = LIST_FIRST(&head);
622 LIST_REMOVE(n1, entries);
623 free(n1);
624 }
625 n1 = LIST_FIRST(&head); /* Faster List Deletion. */
627 while (n1 != NULL) {
628 n2 = LIST_NEXT(n1, entries);
629 free(n1);
630 n1 = n2;
631 }
632 LIST_INIT(&head);
633
635 A tail queue is headed by a structure defined by the TAILQ_HEAD macro.
636 This structure contains a pair of pointers, one to the first element in
637 the tail queue and the other to the last element in the tail queue. The
638 elements are doubly linked so that an arbitrary element can be removed
639 without traversing the tail queue. New elements can be added to the tail
640 queue after an existing element, before an existing element, at the head
641 of the tail queue, or at the end of the tail queue. A TAILQ_HEAD struc‐
642 ture is declared as follows:
643 TAILQ_HEAD(HEADNAME, TYPE) head;
645 where HEADNAME is the name of the structure to be defined, and TYPE is
647 the type of the elements to be linked into the tail queue. A pointer to
648 the head of the tail queue can later be declared as:
649 struct HEADNAME *headp;
651 (The names head and headp are user selectable.)
653 The macro TAILQ_HEAD_INITIALIZER evaluates to an initializer for the tail
655 queue head.
656 The macro TAILQ_CONCAT concatenates the tail queue headed by head2 onto
658 the end of the one headed by head1 removing all entries from the former.
659 The macro TAILQ_EMPTY evaluates to true if there are no items on the tail
661 queue.
662 The macro TAILQ_ENTRY declares a structure that connects the elements in
664 the tail queue.
665 The macro TAILQ_FIRST returns the first item on the tail queue or NULL if
667 the tail queue is empty.
668 The macro TAILQ_FOREACH traverses the tail queue referenced by head in
670 the forward direction, assigning each element in turn to var. var is set
671 to NULL if the loop completes normally, or if there were no elements.
672 The macro TAILQ_FOREACH_FROM behaves identically to TAILQ_FOREACH when
674 var is NULL, else it treats var as a previously found TAILQ element and
675 begins the loop at var instead of the first element in the TAILQ refer‐
676 enced by head.
677 The macro TAILQ_FOREACH_REVERSE traverses the tail queue referenced by
679 head in the reverse direction, assigning each element in turn to var.
680 The macro TAILQ_FOREACH_REVERSE_FROM behaves identically to
682 TAILQ_FOREACH_REVERSE when var is NULL, else it treats var as a previ‐
683 ously found TAILQ element and begins the reverse loop at var instead of
684 the last element in the TAILQ referenced by head.
685 The macros TAILQ_FOREACH_SAFE and TAILQ_FOREACH_REVERSE_SAFE traverse the
687 list referenced by head in the forward or reverse direction respectively,
688 assigning each element in turn to var. However, unlike their unsafe
689 counterparts, TAILQ_FOREACH and TAILQ_FOREACH_REVERSE make it possible to
690 both remove var as well as free it from within the loop safely without
691 interfering with the traversal.
692 The macro TAILQ_FOREACH_FROM_SAFE behaves identically to
694 TAILQ_FOREACH_SAFE when var is NULL, else it treats var as a previously
695 found TAILQ element and begins the loop at var instead of the first ele‐
696 ment in the TAILQ referenced by head.
697 The macro TAILQ_FOREACH_REVERSE_FROM_SAFE behaves identically to
699 TAILQ_FOREACH_REVERSE_SAFE when var is NULL, else it treats var as a pre‐
700 viously found TAILQ element and begins the reverse loop at var instead of
701 the last element in the TAILQ referenced by head.
702 The macro TAILQ_INIT initializes the tail queue referenced by head.
704 The macro TAILQ_INSERT_HEAD inserts the new element elm at the head of
706 the tail queue.
707 The macro TAILQ_INSERT_TAIL inserts the new element elm at the end of the
709 tail queue.
710 The macro TAILQ_INSERT_AFTER inserts the new element elm after the ele‐
712 ment listelm.
713 The macro TAILQ_INSERT_BEFORE inserts the new element elm before the ele‐
715 ment listelm.
716 The macro TAILQ_LAST returns the last item on the tail queue. If the
718 tail queue is empty the return value is NULL.
719 The macro TAILQ_NEXT returns the next item on the tail queue, or NULL if
721 this item is the last.
722 The macro TAILQ_PREV returns the previous item on the tail queue, or NULL
724 if this item is the first.
725 The macro TAILQ_REMOVE removes the element elm from the tail queue.
727 The macro TAILQ_SWAP swaps the contents of head1 and head2.
729
731 TAILQ_HEAD(tailhead, entry) head =
732 TAILQ_HEAD_INITIALIZER(head);
733 struct tailhead *headp; /* Tail queue head. */
734 struct entry {
735 ...
736 TAILQ_ENTRY(entry) entries; /* Tail queue. */
737 ...
738 } *n1, *n2, *n3, *np;
739 TAILQ_INIT(&head); /* Initialize the queue. */
741 n1 = malloc(sizeof(struct entry)); /* Insert at the head. */
743 TAILQ_INSERT_HEAD(&head, n1, entries);
744 n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */
746 TAILQ_INSERT_TAIL(&head, n1, entries);
747 n2 = malloc(sizeof(struct entry)); /* Insert after. */
749 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
750 n3 = malloc(sizeof(struct entry)); /* Insert before. */
752 TAILQ_INSERT_BEFORE(n2, n3, entries);
753 TAILQ_REMOVE(&head, n2, entries); /* Deletion. */
755 free(n2);
756 /* Forward traversal. */
757 TAILQ_FOREACH(np, &head, entries)
758 np-> ...
759 /* Safe forward traversal. */
760 TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) {
761 np->do_stuff();
762 ...
763 TAILQ_REMOVE(&head, np, entries);
764 free(np);
765 }
766 /* Reverse traversal. */
767 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
768 np-> ...
769 /* TailQ Deletion. */
770 while (!TAILQ_EMPTY(&head)) {
771 n1 = TAILQ_FIRST(&head);
772 TAILQ_REMOVE(&head, n1, entries);
773 free(n1);
774 }
775 /* Faster TailQ Deletion. */
776 n1 = TAILQ_FIRST(&head);
777 while (n1 != NULL) {
778 n2 = TAILQ_NEXT(n1, entries);
779 free(n1);
780 n1 = n2;
781 }
782 TAILQ_INIT(&head);
783
785 tree(3bsd)
786
788 The queue functions first appeared in 4.4BSD.
789BSD June 17, 2013 BSD