1QUEUE(3bsd)                          LOCAL                         QUEUE(3bsd)
2

NAME

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

SYNOPSIS

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

DESCRIPTION

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
211     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
218     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
228     Singly-linked tail queues are ideal for applications with large datasets
229     and few or no removals, or for implementing a FIFO queue.
230
231     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
241     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
248     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
259     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

SINGLY-LINKED LISTS

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
275           SLIST_HEAD(HEADNAME, TYPE) head;
276
277     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
281           struct HEADNAME *headp;
282
283     (The names head and headp are user selectable.)
284
285     The macro SLIST_HEAD_INITIALIZER evaluates to an initializer for the list
286     head.
287
288     The macro SLIST_EMPTY evaluates to true if there are no elements in the
289     list.
290
291     The macro SLIST_ENTRY declares a structure that connects the elements in
292     the list.
293
294     The macro SLIST_FIRST returns the first element in the list or NULL if
295     the list is empty.
296
297     The macro SLIST_FOREACH traverses the list referenced by head in the for‐
298     ward direction, assigning each element in turn to var.
299
300     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
305     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
311     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
316     The macro SLIST_INIT initializes the list referenced by head.
317
318     The macro SLIST_INSERT_HEAD inserts the new element elm at the head of
319     the list.
320
321     The macro SLIST_INSERT_AFTER inserts the new element elm after the ele‐
322     ment listelm.
323
324     The macro SLIST_NEXT returns the next element in the list.
325
326     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
329     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
334     The macro SLIST_REMOVE removes the element elm from the list.
335
336     The macro SLIST_SWAP swaps the contents of head1 and head2.
337

SINGLY-LINKED LIST EXAMPLE

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
348     SLIST_INIT(&head);                      /* Initialize the list. */
349
350     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
351     SLIST_INSERT_HEAD(&head, n1, entries);
352
353     n2 = malloc(sizeof(struct entry));      /* Insert after. */
354     SLIST_INSERT_AFTER(n1, n2, entries);
355
356     SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
357     free(n2);
358
359     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
373     while (!SLIST_EMPTY(&head)) {           /* List Deletion. */
374             n1 = SLIST_FIRST(&head);
375             SLIST_REMOVE_HEAD(&head, entries);
376             free(n1);
377     }
378

SINGLY-LINKED TAIL QUEUES

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
389           STAILQ_HEAD(HEADNAME, TYPE) head;
390
391     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
395           struct HEADNAME *headp;
396
397     (The names head and headp are user selectable.)
398
399     The macro STAILQ_HEAD_INITIALIZER evaluates to an initializer for the
400     tail queue head.
401
402     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
405     The macro STAILQ_EMPTY evaluates to true if there are no items on the
406     tail queue.
407
408     The macro STAILQ_ENTRY declares a structure that connects the elements in
409     the tail queue.
410
411     The macro STAILQ_FIRST returns the first item on the tail queue or NULL
412     if the tail queue is empty.
413
414     The macro STAILQ_FOREACH traverses the tail queue referenced by head in
415     the forward direction, assigning each element in turn to var.
416
417     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
422     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
428     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
433     The macro STAILQ_INIT initializes the tail queue referenced by head.
434
435     The macro STAILQ_INSERT_HEAD inserts the new element elm at the head of
436     the tail queue.
437
438     The macro STAILQ_INSERT_TAIL inserts the new element elm at the end of
439     the tail queue.
440
441     The macro STAILQ_INSERT_AFTER inserts the new element elm after the ele‐
442     ment listelm.
443
444     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
447     The macro STAILQ_NEXT returns the next item on the tail queue, or NULL
448     this item is the last.
449
450     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
454     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
459     The macro STAILQ_REMOVE removes the element elm from the tail queue.
460
461     The macro STAILQ_SWAP swaps the contents of head1 and head2.
462

SINGLY-LINKED TAIL QUEUE EXAMPLE

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
473     STAILQ_INIT(&head);                     /* Initialize the queue. */
474
475     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
476     STAILQ_INSERT_HEAD(&head, n1, entries);
477
478     n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
479     STAILQ_INSERT_TAIL(&head, n1, entries);
480
481     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

LISTS

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
523           LIST_HEAD(HEADNAME, TYPE) head;
524
525     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
529           struct HEADNAME *headp;
530
531     (The names head and headp are user selectable.)
532
533     The macro LIST_HEAD_INITIALIZER evaluates to an initializer for the list
534     head.
535
536     The macro LIST_EMPTY evaluates to true if there are no elements in the
537     list.
538
539     The macro LIST_ENTRY declares a structure that connects the elements in
540     the list.
541
542     The macro LIST_FIRST returns the first element in the list or NULL if the
543     list is empty.
544
545     The macro LIST_FOREACH traverses the list referenced by head in the for‐
546     ward direction, assigning each element in turn to var.
547
548     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
553     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
559     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
564     The macro LIST_INIT initializes the list referenced by head.
565
566     The macro LIST_INSERT_HEAD inserts the new element elm at the head of the
567     list.
568
569     The macro LIST_INSERT_AFTER inserts the new element elm after the element
570     listelm.
571
572     The macro LIST_INSERT_BEFORE inserts the new element elm before the ele‐
573     ment listelm.
574
575     The macro LIST_NEXT returns the next element in the list, or NULL if this
576     is the last.
577
578     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
581     The macro LIST_REMOVE removes the element elm from the list.
582
583     The macro LIST_SWAP swaps the contents of head1 and head2.
584

LIST EXAMPLE

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
595     LIST_INIT(&head);                       /* Initialize the list. */
596
597     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
598     LIST_INSERT_HEAD(&head, n1, entries);
599
600     n2 = malloc(sizeof(struct entry));      /* Insert after. */
601     LIST_INSERT_AFTER(n1, n2, entries);
602
603     n3 = malloc(sizeof(struct entry));      /* Insert before. */
604     LIST_INSERT_BEFORE(n2, n3, entries);
605
606     LIST_REMOVE(n2, entries);               /* Deletion. */
607     free(n2);
608                                             /* Forward traversal. */
609     LIST_FOREACH(np, &head, entries)
610             np-> ...
611
612                                             /* 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
620     while (!LIST_EMPTY(&head)) {            /* List Deletion. */
621             n1 = LIST_FIRST(&head);
622             LIST_REMOVE(n1, entries);
623             free(n1);
624     }
625
626     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

TAIL QUEUES

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
644           TAILQ_HEAD(HEADNAME, TYPE) head;
645
646     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
650           struct HEADNAME *headp;
651
652     (The names head and headp are user selectable.)
653
654     The macro TAILQ_HEAD_INITIALIZER evaluates to an initializer for the tail
655     queue head.
656
657     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
660     The macro TAILQ_EMPTY evaluates to true if there are no items on the tail
661     queue.
662
663     The macro TAILQ_ENTRY declares a structure that connects the elements in
664     the tail queue.
665
666     The macro TAILQ_FIRST returns the first item on the tail queue or NULL if
667     the tail queue is empty.
668
669     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
673     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
678     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
681     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
686     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
693     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
698     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
703     The macro TAILQ_INIT initializes the tail queue referenced by head.
704
705     The macro TAILQ_INSERT_HEAD inserts the new element elm at the head of
706     the tail queue.
707
708     The macro TAILQ_INSERT_TAIL inserts the new element elm at the end of the
709     tail queue.
710
711     The macro TAILQ_INSERT_AFTER inserts the new element elm after the ele‐
712     ment listelm.
713
714     The macro TAILQ_INSERT_BEFORE inserts the new element elm before the ele‐
715     ment listelm.
716
717     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
720     The macro TAILQ_NEXT returns the next item on the tail queue, or NULL if
721     this item is the last.
722
723     The macro TAILQ_PREV returns the previous item on the tail queue, or NULL
724     if this item is the first.
725
726     The macro TAILQ_REMOVE removes the element elm from the tail queue.
727
728     The macro TAILQ_SWAP swaps the contents of head1 and head2.
729

TAIL QUEUE EXAMPLE

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
740     TAILQ_INIT(&head);                      /* Initialize the queue. */
741
742     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
743     TAILQ_INSERT_HEAD(&head, n1, entries);
744
745     n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
746     TAILQ_INSERT_TAIL(&head, n1, entries);
747
748     n2 = malloc(sizeof(struct entry));      /* Insert after. */
749     TAILQ_INSERT_AFTER(&head, n1, n2, entries);
750
751     n3 = malloc(sizeof(struct entry));      /* Insert before. */
752     TAILQ_INSERT_BEFORE(n2, n3, entries);
753
754     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

SEE ALSO

785     tree(3bsd)
786

HISTORY

788     The queue functions first appeared in 4.4BSD.
789
790BSD                              June 17, 2013                             BSD
Impressum