1queue(3bsd)                          LOCAL                         queue(3bsd)
2

NAME

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

LIBRARY

30     Utility functions from BSD systems (libbsd, -lbsd)
31

SYNOPSIS

33     #include <sys/queue.h>
34     (See libbsd(7) for include usage.)
35
36     SLIST_CLASS_ENTRY(CLASSTYPE);
37
38     SLIST_CLASS_HEAD(HEADNAME, CLASSTYPE);
39
40     SLIST_CONCAT(SLIST_HEAD *head1, SLIST_HEAD *head2, TYPE,
41         SLIST_ENTRY NAME);
42
43     SLIST_EMPTY(SLIST_HEAD *head);
44
45     SLIST_ENTRY(TYPE);
46
47     SLIST_FIRST(SLIST_HEAD *head);
48
49     SLIST_FOREACH(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
50
51     SLIST_FOREACH_FROM(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
52
53     SLIST_FOREACH_FROM_SAFE(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME,
54         TYPE *temp_var);
55
56     SLIST_FOREACH_SAFE(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME,
57         TYPE *temp_var);
58
59     SLIST_HEAD(HEADNAME, TYPE);
60
61     SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
62
63     SLIST_INIT(SLIST_HEAD *head);
64
65     SLIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, SLIST_ENTRY NAME);
66
67     SLIST_INSERT_HEAD(SLIST_HEAD *head, TYPE *elm, SLIST_ENTRY NAME);
68
69     SLIST_NEXT(TYPE *elm, SLIST_ENTRY NAME);
70
71     SLIST_REMOVE(SLIST_HEAD *head, TYPE *elm, TYPE, SLIST_ENTRY NAME);
72
73     SLIST_REMOVE_AFTER(TYPE *elm, SLIST_ENTRY NAME);
74
75     SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME);
76
77     SLIST_SWAP(SLIST_HEAD *head1, SLIST_HEAD *head2, TYPE);
78
79     STAILQ_CLASS_ENTRY(CLASSTYPE);
80
81     STAILQ_CLASS_HEAD(HEADNAME, CLASSTYPE);
82
83     STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);
84
85     STAILQ_EMPTY(STAILQ_HEAD *head);
86
87     STAILQ_ENTRY(TYPE);
88
89     STAILQ_FIRST(STAILQ_HEAD *head);
90
91     STAILQ_FOREACH(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
92
93     STAILQ_FOREACH_FROM(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
94
95     STAILQ_FOREACH_FROM_SAFE(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME,
96         TYPE *temp_var);
97
98     STAILQ_FOREACH_SAFE(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME,
99         TYPE *temp_var);
100
101     STAILQ_HEAD(HEADNAME, TYPE);
102
103     STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
104
105     STAILQ_INIT(STAILQ_HEAD *head);
106
107     STAILQ_INSERT_AFTER(STAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
108         STAILQ_ENTRY NAME);
109
110     STAILQ_INSERT_HEAD(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
111
112     STAILQ_INSERT_TAIL(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
113
114     STAILQ_LAST(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
115
116     STAILQ_NEXT(TYPE *elm, STAILQ_ENTRY NAME);
117
118     STAILQ_REMOVE(STAILQ_HEAD *head, TYPE *elm, TYPE, STAILQ_ENTRY NAME);
119
120     STAILQ_REMOVE_AFTER(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
121
122     STAILQ_REMOVE_HEAD(STAILQ_HEAD *head, STAILQ_ENTRY NAME);
123
124     STAILQ_SWAP(STAILQ_HEAD *head1, STAILQ_HEAD *head2, TYPE);
125
126     LIST_CLASS_ENTRY(CLASSTYPE);
127
128     LIST_CLASS_HEAD(HEADNAME, CLASSTYPE);
129
130     LIST_CONCAT(LIST_HEAD *head1, LIST_HEAD *head2, TYPE, LIST_ENTRY NAME);
131
132     LIST_EMPTY(LIST_HEAD *head);
133
134     LIST_ENTRY(TYPE);
135
136     LIST_FIRST(LIST_HEAD *head);
137
138     LIST_FOREACH(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);
139
140     LIST_FOREACH_FROM(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);
141
142     LIST_FOREACH_FROM_SAFE(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME,
143         TYPE *temp_var);
144
145     LIST_FOREACH_SAFE(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME,
146         TYPE *temp_var);
147
148     LIST_HEAD(HEADNAME, TYPE);
149
150     LIST_HEAD_INITIALIZER(LIST_HEAD head);
151
152     LIST_INIT(LIST_HEAD *head);
153
154     LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);
155
156     LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);
157
158     LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME);
159
160     LIST_NEXT(TYPE *elm, LIST_ENTRY NAME);
161
162     LIST_PREV(TYPE *elm, LIST_HEAD *head, TYPE, LIST_ENTRY NAME);
163
164     LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);
165
166     LIST_SWAP(LIST_HEAD *head1, LIST_HEAD *head2, TYPE, LIST_ENTRY NAME);
167
168     TAILQ_CLASS_ENTRY(CLASSTYPE);
169
170     TAILQ_CLASS_HEAD(HEADNAME, CLASSTYPE);
171
172     TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TAILQ_ENTRY NAME);
173
174     TAILQ_EMPTY(TAILQ_HEAD *head);
175
176     TAILQ_ENTRY(TYPE);
177
178     TAILQ_FIRST(TAILQ_HEAD *head);
179
180     TAILQ_FOREACH(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME);
181
182     TAILQ_FOREACH_FROM(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME);
183
184     TAILQ_FOREACH_FROM_SAFE(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME,
185         TYPE *temp_var);
186
187     TAILQ_FOREACH_REVERSE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
188         TAILQ_ENTRY NAME);
189
190     TAILQ_FOREACH_REVERSE_FROM(TYPE *var, TAILQ_HEAD *head, HEADNAME,
191         TAILQ_ENTRY NAME);
192
193     TAILQ_FOREACH_REVERSE_FROM_SAFE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
194         TAILQ_ENTRY NAME, TYPE *temp_var);
195
196     TAILQ_FOREACH_REVERSE_SAFE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
197         TAILQ_ENTRY NAME, TYPE *temp_var);
198
199     TAILQ_FOREACH_SAFE(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME,
200         TYPE *temp_var);
201
202     TAILQ_HEAD(HEADNAME, TYPE);
203
204     TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
205
206     TAILQ_INIT(TAILQ_HEAD *head);
207
208     TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
209         TAILQ_ENTRY NAME);
210
211     TAILQ_INSERT_BEFORE(TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME);
212
213     TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
214
215     TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
216
217     TAILQ_LAST(TAILQ_HEAD *head, HEADNAME);
218
219     TAILQ_NEXT(TYPE *elm, TAILQ_ENTRY NAME);
220
221     TAILQ_PREV(TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);
222
223     TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
224
225     TAILQ_SWAP(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TYPE, TAILQ_ENTRY NAME);
226

DESCRIPTION

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
241     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
248     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
258     Singly-linked tail queues are ideal for applications with large datasets
259     and few or no removals, or for implementing a FIFO queue.
260
261     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
271     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
279     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
290     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

SINGLY-LINKED LISTS

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
311           SLIST_HEAD(HEADNAME, TYPE) head;
312
313     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
317           struct HEADNAME *headp;
318
319     (The names head and headp are user selectable.)
320
321     The macro SLIST_HEAD_INITIALIZER evaluates to an initializer for the list
322     head.
323
324     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
330     The macro SLIST_EMPTY evaluates to true if there are no elements in the
331     list.
332
333     The macro SLIST_ENTRY declares a structure that connects the elements in
334     the list.
335
336     The macro SLIST_FIRST returns the first element in the list or NULL if
337     the list is empty.
338
339     The macro SLIST_FOREACH traverses the list referenced by head in the for‐
340     ward direction, assigning each element in turn to var.
341
342     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
347     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
353     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
358     The macro SLIST_INIT initializes the list referenced by head.
359
360     The macro SLIST_INSERT_HEAD inserts the new element elm at the head of
361     the list.
362
363     The macro SLIST_INSERT_AFTER inserts the new element elm after the ele‐
364     ment listelm.
365
366     The macro SLIST_NEXT returns the next element in the list.
367
368     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
371     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
376     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
381     The macro SLIST_SWAP swaps the contents of head1 and head2.
382

SINGLY-LINKED LIST EXAMPLE

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
393     SLIST_INIT(&head);                      /* Initialize the list. */
394
395     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
396     SLIST_INSERT_HEAD(&head, n1, entries);
397
398     n2 = malloc(sizeof(struct entry));      /* Insert after. */
399     SLIST_INSERT_AFTER(n1, n2, entries);
400
401     SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
402     free(n2);
403
404     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
418     while (!SLIST_EMPTY(&head)) {           /* List Deletion. */
419             n1 = SLIST_FIRST(&head);
420             SLIST_REMOVE_HEAD(&head, entries);
421             free(n1);
422     }
423

SINGLY-LINKED TAIL QUEUES

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
434           STAILQ_HEAD(HEADNAME, TYPE) head;
435
436     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
440           struct HEADNAME *headp;
441
442     (The names head and headp are user selectable.)
443
444     The macro STAILQ_HEAD_INITIALIZER evaluates to an initializer for the
445     tail queue head.
446
447     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
450     The macro STAILQ_EMPTY evaluates to true if there are no items on the
451     tail queue.
452
453     The macro STAILQ_ENTRY declares a structure that connects the elements in
454     the tail queue.
455
456     The macro STAILQ_FIRST returns the first item on the tail queue or NULL
457     if the tail queue is empty.
458
459     The macro STAILQ_FOREACH traverses the tail queue referenced by head in
460     the forward direction, assigning each element in turn to var.
461
462     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
467     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
473     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
478     The macro STAILQ_INIT initializes the tail queue referenced by head.
479
480     The macro STAILQ_INSERT_HEAD inserts the new element elm at the head of
481     the tail queue.
482
483     The macro STAILQ_INSERT_TAIL inserts the new element elm at the end of
484     the tail queue.
485
486     The macro STAILQ_INSERT_AFTER inserts the new element elm after the ele‐
487     ment listelm.
488
489     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
492     The macro STAILQ_NEXT returns the next item on the tail queue, or NULL
493     this item is the last.
494
495     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
499     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
504     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
509     The macro STAILQ_SWAP swaps the contents of head1 and head2.
510

SINGLY-LINKED TAIL QUEUE EXAMPLE

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
521     STAILQ_INIT(&head);                     /* Initialize the queue. */
522
523     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
524     STAILQ_INSERT_HEAD(&head, n1, entries);
525
526     n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
527     STAILQ_INSERT_TAIL(&head, n1, entries);
528
529     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

LISTS

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
571           LIST_HEAD(HEADNAME, TYPE) head;
572
573     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
577           struct HEADNAME *headp;
578
579     (The names head and headp are user selectable.)
580
581     The macro LIST_HEAD_INITIALIZER evaluates to an initializer for the list
582     head.
583
584     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
590     The macro LIST_EMPTY evaluates to true if there are no elements in the
591     list.
592
593     The macro LIST_ENTRY declares a structure that connects the elements in
594     the list.
595
596     The macro LIST_FIRST returns the first element in the list or NULL if the
597     list is empty.
598
599     The macro LIST_FOREACH traverses the list referenced by head in the for‐
600     ward direction, assigning each element in turn to var.
601
602     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
607     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
613     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
618     The macro LIST_INIT initializes the list referenced by head.
619
620     The macro LIST_INSERT_HEAD inserts the new element elm at the head of the
621     list.
622
623     The macro LIST_INSERT_AFTER inserts the new element elm after the element
624     listelm.
625
626     The macro LIST_INSERT_BEFORE inserts the new element elm before the ele‐
627     ment listelm.
628
629     The macro LIST_NEXT returns the next element in the list, or NULL if this
630     is the last.
631
632     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
635     The macro LIST_REMOVE removes the element elm from the list.
636
637     The macro LIST_SWAP swaps the contents of head1 and head2.
638

LIST EXAMPLE

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
649     LIST_INIT(&head);                       /* Initialize the list. */
650
651     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
652     LIST_INSERT_HEAD(&head, n1, entries);
653
654     n2 = malloc(sizeof(struct entry));      /* Insert after. */
655     LIST_INSERT_AFTER(n1, n2, entries);
656
657     n3 = malloc(sizeof(struct entry));      /* Insert before. */
658     LIST_INSERT_BEFORE(n2, n3, entries);
659
660     LIST_REMOVE(n2, entries);               /* Deletion. */
661     free(n2);
662                                             /* Forward traversal. */
663     LIST_FOREACH(np, &head, entries)
664             np-> ...
665
666                                             /* 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
674     while (!LIST_EMPTY(&head)) {            /* List Deletion. */
675             n1 = LIST_FIRST(&head);
676             LIST_REMOVE(n1, entries);
677             free(n1);
678     }
679
680     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

TAIL QUEUES

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
698           TAILQ_HEAD(HEADNAME, TYPE) head;
699
700     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
704           struct HEADNAME *headp;
705
706     (The names head and headp are user selectable.)
707
708     The macro TAILQ_HEAD_INITIALIZER evaluates to an initializer for the tail
709     queue head.
710
711     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
714     The macro TAILQ_EMPTY evaluates to true if there are no items on the tail
715     queue.
716
717     The macro TAILQ_ENTRY declares a structure that connects the elements in
718     the tail queue.
719
720     The macro TAILQ_FIRST returns the first item on the tail queue or NULL if
721     the tail queue is empty.
722
723     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
727     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
732     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
735     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
740     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
747     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
752     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
757     The macro TAILQ_INIT initializes the tail queue referenced by head.
758
759     The macro TAILQ_INSERT_HEAD inserts the new element elm at the head of
760     the tail queue.
761
762     The macro TAILQ_INSERT_TAIL inserts the new element elm at the end of the
763     tail queue.
764
765     The macro TAILQ_INSERT_AFTER inserts the new element elm after the ele‐
766     ment listelm.
767
768     The macro TAILQ_INSERT_BEFORE inserts the new element elm before the ele‐
769     ment listelm.
770
771     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
774     The macro TAILQ_NEXT returns the next item on the tail queue, or NULL if
775     this item is the last.
776
777     The macro TAILQ_PREV returns the previous item on the tail queue, or NULL
778     if this item is the first.
779
780     The macro TAILQ_REMOVE removes the element elm from the tail queue.
781
782     The macro TAILQ_SWAP swaps the contents of head1 and head2.
783

TAIL QUEUE EXAMPLE

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
794     TAILQ_INIT(&head);                      /* Initialize the queue. */
795
796     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
797     TAILQ_INSERT_HEAD(&head, n1, entries);
798
799     n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
800     TAILQ_INSERT_TAIL(&head, n1, entries);
801
802     n2 = malloc(sizeof(struct entry));      /* Insert after. */
803     TAILQ_INSERT_AFTER(&head, n1, n2, entries);
804
805     n3 = malloc(sizeof(struct entry));      /* Insert before. */
806     TAILQ_INSERT_BEFORE(n2, n3, entries);
807
808     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

DIAGNOSTICS

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
842     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

SEE ALSO

849     tree(3bsd)
850

HISTORY

852     The queue functions first appeared in 4.4BSD.
853
854BSD                            September 8, 2016                           BSD
Impressum