queue(3) - f30

1QUEUE(3)                 BSD Library Functions Manual                 QUEUE(3)
2

NAME

4     SLIST_EMPTY, SLIST_ENTRY, SLIST_FIRST, SLIST_FOREACH, SLIST_HEAD,
5     SLIST_HEAD_INITIALIZER, SLIST_INIT, SLIST_INSERT_AFTER,
6     SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE_HEAD, SLIST_REMOVE,
7     STAILQ_CONCAT, STAILQ_EMPTY, STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FOREACH,
8     STAILQ_HEAD, STAILQ_HEAD_INITIALIZER, STAILQ_INIT, STAILQ_INSERT_AFTER,
9     STAILQ_INSERT_HEAD, STAILQ_INSERT_TAIL, STAILQ_NEXT, STAILQ_REMOVE_HEAD,
10     STAILQ_REMOVE, LIST_EMPTY, LIST_ENTRY, LIST_FIRST, LIST_FOREACH,
11     LIST_HEAD, LIST_HEAD_INITIALIZER, LIST_INIT, LIST_INSERT_AFTER,
12     LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_NEXT, LIST_REMOVE,
13     TAILQ_CONCAT, TAILQ_EMPTY, TAILQ_ENTRY, TAILQ_FIRST, TAILQ_FOREACH,
14     TAILQ_FOREACH_REVERSE, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER, TAILQ_INIT,
15     TAILQ_INSERT_AFTER, TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD,
16     TAILQ_INSERT_TAIL, TAILQ_LAST, TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE,
17     TAILQ_SWAP — implementations of singly-linked lists, singly-linked tail
18     queues, lists and tail queues
19

SYNOPSIS

21     #include <sys/queue.h>
22
23     SLIST_EMPTY(SLIST_HEAD *head);
24
25     SLIST_ENTRY(TYPE);
26
27     SLIST_FIRST(SLIST_HEAD *head);
28
29     SLIST_FOREACH(TYPE *var, SLIST_HEAD *head, SLIST_ENTRY NAME);
30
31     SLIST_HEAD(HEADNAME, TYPE);
32
33     SLIST_HEAD_INITIALIZER(SLIST_HEAD head);
34
35     SLIST_INIT(SLIST_HEAD *head);
36
37     SLIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, SLIST_ENTRY NAME);
38
39     SLIST_INSERT_HEAD(SLIST_HEAD *head, TYPE *elm, SLIST_ENTRY NAME);
40
41     SLIST_NEXT(TYPE *elm, SLIST_ENTRY NAME);
42
43     SLIST_REMOVE_HEAD(SLIST_HEAD *head, SLIST_ENTRY NAME);
44
45     SLIST_REMOVE(SLIST_HEAD *head, TYPE *elm, TYPE, SLIST_ENTRY NAME);
46
47     STAILQ_CONCAT(STAILQ_HEAD *head1, STAILQ_HEAD *head2);
48
49     STAILQ_EMPTY(STAILQ_HEAD *head);
50
51     STAILQ_ENTRY(TYPE);
52
53     STAILQ_FIRST(STAILQ_HEAD *head);
54
55     STAILQ_FOREACH(TYPE *var, STAILQ_HEAD *head, STAILQ_ENTRY NAME);
56
57     STAILQ_HEAD(HEADNAME, TYPE);
58
59     STAILQ_HEAD_INITIALIZER(STAILQ_HEAD head);
60
61     STAILQ_INIT(STAILQ_HEAD *head);
62
63     STAILQ_INSERT_AFTER(STAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
64         STAILQ_ENTRY NAME);
65
66     STAILQ_INSERT_HEAD(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
67
68     STAILQ_INSERT_TAIL(STAILQ_HEAD *head, TYPE *elm, STAILQ_ENTRY NAME);
69
70     STAILQ_NEXT(TYPE *elm, STAILQ_ENTRY NAME);
71
72     STAILQ_REMOVE_HEAD(STAILQ_HEAD *head, STAILQ_ENTRY NAME);
73
74     STAILQ_REMOVE(STAILQ_HEAD *head, TYPE *elm, TYPE, STAILQ_ENTRY NAME);
75
76     LIST_EMPTY(LIST_HEAD *head);
77
78     LIST_ENTRY(TYPE);
79
80     LIST_FIRST(LIST_HEAD *head);
81
82     LIST_FOREACH(TYPE *var, LIST_HEAD *head, LIST_ENTRY NAME);
83
84     LIST_HEAD(HEADNAME, TYPE);
85
86     LIST_HEAD_INITIALIZER(LIST_HEAD head);
87
88     LIST_INIT(LIST_HEAD *head);
89
90     LIST_INSERT_AFTER(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);
91
92     LIST_INSERT_BEFORE(TYPE *listelm, TYPE *elm, LIST_ENTRY NAME);
93
94     LIST_INSERT_HEAD(LIST_HEAD *head, TYPE *elm, LIST_ENTRY NAME);
95
96     LIST_NEXT(TYPE *elm, LIST_ENTRY NAME);
97
98     LIST_REMOVE(TYPE *elm, LIST_ENTRY NAME);
99
100     LIST_SWAP(LIST_HEAD *head1, LIST_HEAD *head2, TYPE, LIST_ENTRY NAME);
101
102     TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TAILQ_ENTRY NAME);
103
104     TAILQ_EMPTY(TAILQ_HEAD *head);
105
106     TAILQ_ENTRY(TYPE);
107
108     TAILQ_FIRST(TAILQ_HEAD *head);
109
110     TAILQ_FOREACH(TYPE *var, TAILQ_HEAD *head, TAILQ_ENTRY NAME);
111
112     TAILQ_FOREACH_REVERSE(TYPE *var, TAILQ_HEAD *head, HEADNAME,
113         TAILQ_ENTRY NAME);
114
115     TAILQ_HEAD(HEADNAME, TYPE);
116
117     TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
118
119     TAILQ_INIT(TAILQ_HEAD *head);
120
121     TAILQ_INSERT_AFTER(TAILQ_HEAD *head, TYPE *listelm, TYPE *elm,
122         TAILQ_ENTRY NAME);
123
124     TAILQ_INSERT_BEFORE(TYPE *listelm, TYPE *elm, TAILQ_ENTRY NAME);
125
126     TAILQ_INSERT_HEAD(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
127
128     TAILQ_INSERT_TAIL(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
129
130     TAILQ_LAST(TAILQ_HEAD *head, HEADNAME);
131
132     TAILQ_NEXT(TYPE *elm, TAILQ_ENTRY NAME);
133
134     TAILQ_PREV(TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);
135
136     TAILQ_REMOVE(TAILQ_HEAD *head, TYPE *elm, TAILQ_ENTRY NAME);
137
138     TAILQ_SWAP(TAILQ_HEAD *head1, TAILQ_HEAD *head2, TYPE, TAILQ_ENTRY NAME);
139

DESCRIPTION

141     These macros define and operate on four types of data structures: singly-
142     linked lists, singly-linked tail queues, lists, and tail queues.  All
143     four structures support the following functionality:
144
145           1.   Insertion of a new entry at the head of the list.
146           2.   Insertion of a new entry after any element in the list.
147           3.   O(1) removal of an entry from the head of the list.
148           4.   Forward traversal through the list.
149           5.   Swapping the contents of two lists.
150
151     Singly-linked lists are the simplest of the four data structures and sup‐
152     port only the above functionality.  Singly-linked lists are ideal for
153     applications with large datasets and few or no removals, or for imple‐
154     menting a LIFO queue.  Singly-linked lists add the following functional‐
155     ity:
156
157           1.   O(n) removal of any entry in the list.
158
159     Singly-linked tail queues add the following functionality:
160
161           1.   Entries can be added at the end of a list.
162           2.   O(n) removal of any entry in the list.
163           3.   They may be concatenated.
164
165     However:
166
167           1.   All list insertions must specify the head of the list.
168           2.   Each head entry requires two pointers rather than one.
169           3.   Code size is about 15% greater and operations run about 20%
170                slower than singly-linked lists.
171
172     Singly-linked tail queues are ideal for applications with large datasets
173     and few or no removals, or for implementing a FIFO queue.
174
175     All doubly linked types of data structures (lists and tail queues) addi‐
176     tionally allow:
177
178           1.   Insertion of a new entry before any element in the list.
179           2.   O(1) removal of any entry in the list.
180
181     However:
182
183           1.   Each element requires two pointers rather than one.
184           2.   Code size and execution time of operations (except for
185                removal) is about twice that of the singly-linked data-struc‐
186                tures.
187
188     Linked lists are the simplest of the doubly linked data structures.  They
189     add the following functionality over the above:
190
191           1.   They may be traversed backwards.
192
193     However:
194
195           1.   To traverse backwards, an entry to begin the traversal and the
196                list in which it is contained must be specified.
197
198     Tail queues add the following functionality:
199           1.   Entries can be added at the end of a list.
200           2.   They may be traversed backwards, from tail to head.
201           3.   They may be concatenated.
202
203     However:
204
205           1.   All list insertions and removals must specify the head of the
206                list.
207           2.   Each head entry requires two pointers rather than one.
208           3.   Code size is about 15% greater and operations run about 20%
209                slower than singly-linked lists.
210
211     In the macro definitions, TYPE is the name of a user defined structure,
212     that must contain a field of type SLIST_ENTRY, STAILQ_ENTRY, LIST_ENTRY,
213     or TAILQ_ENTRY, named NAME.  The argument HEADNAME is the name of a user
214     defined structure that must be declared using the macros SLIST_HEAD,
215     STAILQ_HEAD, LIST_HEAD, or TAILQ_HEAD.  See the examples below for fur‐
216     ther explanation of how these macros are used.
217
218   Singly-linked lists
219     A singly-linked list is headed by a structure defined by the SLIST_HEAD
220     macro.  This structure contains a single pointer to the first element on
221     the list.  The elements are singly linked for minimum space and pointer
222     manipulation overhead at the expense of O(n) removal for arbitrary ele‐
223     ments.  New elements can be added to the list after an existing element
224     or at the head of the list.  An SLIST_HEAD structure is declared as fol‐
225     lows:
226
227           SLIST_HEAD(HEADNAME, TYPE) head;
228
229     where HEADNAME is the name of the structure to be defined, and TYPE is
230     the type of the elements to be linked into the list.  A pointer to the
231     head of the list can later be declared as:
232
233           struct HEADNAME *headp;
234
235     (The names head and headp are user selectable.)
236
237     The macro SLIST_HEAD_INITIALIZER evaluates to an initializer for the list
238     head.
239
240     The macro SLIST_EMPTY evaluates to true if there are no elements in the
241     list.
242
243     The macro SLIST_ENTRY declares a structure that connects the elements in
244     the list.
245
246     The macro SLIST_FIRST returns the first element in the list or NULL if
247     the list is empty.
248
249     The macro SLIST_FOREACH traverses the list referenced by head in the for‐
250     ward direction, assigning each element in turn to var.
251
252     The macro SLIST_INIT initializes the list referenced by head.
253
254     The macro SLIST_INSERT_HEAD inserts the new element elm at the head of
255     the list.
256
257     The macro SLIST_INSERT_AFTER inserts the new element elm after the ele‐
258     ment listelm.
259
260     The macro SLIST_NEXT returns the next element in the list.
261
262     The macro SLIST_REMOVE_HEAD removes the element elm from the head of the
263     list.  For optimum efficiency, elements being removed from the head of
264     the list should explicitly use this macro instead of the generic
265     SLIST_REMOVE macro.
266
267     The macro SLIST_REMOVE removes the element elm from the list.
268
269   Singly-linked list example
270     SLIST_HEAD(slisthead, entry) head =
271         SLIST_HEAD_INITIALIZER(head);
272     struct slisthead *headp;                /* Singly-linked List
273                                                head. */
274     struct entry {
275             ...
276             SLIST_ENTRY(entry) entries;     /* Singly-linked List. */
277             ...
278     } *n1, *n2, *n3, *np;
279
280     SLIST_INIT(&head);                      /* Initialize the list. */
281
282     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
283     SLIST_INSERT_HEAD(&head, n1, entries);
284
285     n2 = malloc(sizeof(struct entry));      /* Insert after. */
286     SLIST_INSERT_AFTER(n1, n2, entries);
287
288     SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */
289     free(n2);
290
291     n3 = SLIST_FIRST(&head);
292     SLIST_REMOVE_HEAD(&head, entries);      /* Deletion from the head. */
293     free(n3);
294                                             /* Forward traversal. */
295     SLIST_FOREACH(np, &head, entries)
296             np-> ...
297
298     while (!SLIST_EMPTY(&head)) {           /* List Deletion. */
299             n1 = SLIST_FIRST(&head);
300             SLIST_REMOVE_HEAD(&head, entries);
301             free(n1);
302     }
303
304   Singly-linked tail queues
305     A singly-linked tail queue is headed by a structure defined by the
306     STAILQ_HEAD macro.  This structure contains a pair of pointers, one to
307     the first element in the tail queue and the other to the last element in
308     the tail queue.  The elements are singly linked for minimum space and
309     pointer manipulation overhead at the expense of O(n) removal for arbi‐
310     trary elements.  New elements can be added to the tail queue after an
311     existing element, at the head of the tail queue, or at the end of the
312     tail queue.  A STAILQ_HEAD structure is declared as follows:
313
314           STAILQ_HEAD(HEADNAME, TYPE) head;
315
316     where HEADNAME is the name of the structure to be defined, and TYPE is
317     the type of the elements to be linked into the tail queue.  A pointer to
318     the head of the tail queue can later be declared as:
319
320           struct HEADNAME *headp;
321
322     (The names head and headp are user selectable.)
323
324     The macro STAILQ_HEAD_INITIALIZER evaluates to an initializer for the
325     tail queue head.
326
327     The macro STAILQ_CONCAT concatenates the tail queue headed by head2 onto
328     the end of the one headed by head1 removing all entries from the former.
329
330     The macro STAILQ_EMPTY evaluates to true if there are no items on the
331     tail queue.
332
333     The macro STAILQ_ENTRY declares a structure that connects the elements in
334     the tail queue.
335
336     The macro STAILQ_FIRST returns the first item on the tail queue or NULL
337     if the tail queue is empty.
338
339     The macro STAILQ_FOREACH traverses the tail queue referenced by head in
340     the forward direction, assigning each element in turn to var.
341
342     The macro STAILQ_INIT initializes the tail queue referenced by head.
343
344     The macro STAILQ_INSERT_HEAD inserts the new element elm at the head of
345     the tail queue.
346
347     The macro STAILQ_INSERT_TAIL inserts the new element elm at the end of
348     the tail queue.
349
350     The macro STAILQ_INSERT_AFTER inserts the new element elm after the ele‐
351     ment listelm.
352
353     The macro STAILQ_NEXT returns the next item on the tail queue, or NULL
354     this item is the last.
355
356     The macro STAILQ_REMOVE_HEAD removes the element at the head of the tail
357     queue.  For optimum efficiency, elements being removed from the head of
358     the tail queue should use this macro explicitly rather than the generic
359     STAILQ_REMOVE macro.
360
361     The macro STAILQ_REMOVE removes the element elm from the tail queue.
362
363   Singly-linked tail queue example
364     STAILQ_HEAD(stailhead, entry) head =
365         STAILQ_HEAD_INITIALIZER(head);
366     struct stailhead *headp;                /* Singly-linked tail queue head. */
367     struct entry {
368             ...
369             STAILQ_ENTRY(entry) entries;    /* Tail queue. */
370             ...
371     } *n1, *n2, *n3, *np;
372
373     STAILQ_INIT(&head);                     /* Initialize the queue. */
374
375     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
376     STAILQ_INSERT_HEAD(&head, n1, entries);
377
378     n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
379     STAILQ_INSERT_TAIL(&head, n1, entries);
380
381     n2 = malloc(sizeof(struct entry));      /* Insert after. */
382     STAILQ_INSERT_AFTER(&head, n1, n2, entries);
383                                             /* Deletion. */
384     STAILQ_REMOVE(&head, n2, entry, entries);
385     free(n2);
386                                             /* Deletion from the head. */
387     n3 = STAILQ_FIRST(&head);
388     STAILQ_REMOVE_HEAD(&head, entries);
389     free(n3);
390                                             /* Forward traversal. */
391     STAILQ_FOREACH(np, &head, entries)
392             np-> ...
393                                             /* TailQ Deletion. */
394     while (!STAILQ_EMPTY(&head)) {
395             n1 = STAILQ_FIRST(&head);
396             STAILQ_REMOVE_HEAD(&head, entries);
397             free(n1);
398     }
399                                             /* Faster TailQ Deletion. */
400     n1 = STAILQ_FIRST(&head);
401     while (n1 != NULL) {
402             n2 = STAILQ_NEXT(n1, entries);
403             free(n1);
404             n1 = n2;
405     }
406     STAILQ_INIT(&head);
407
408   Lists
409     A list is headed by a structure defined by the LIST_HEAD macro.  This
410     structure contains a single pointer to the first element on the list.
411     The elements are doubly linked so that an arbitrary element can be
412     removed without traversing the list.  New elements can be added to the
413     list after an existing element, before an existing element, or at the
414     head of the list.  A LIST_HEAD structure is declared as follows:
415
416           LIST_HEAD(HEADNAME, TYPE) head;
417
418     where HEADNAME is the name of the structure to be defined, and TYPE is
419     the type of the elements to be linked into the list.  A pointer to the
420     head of the list can later be declared as:
421
422           struct HEADNAME *headp;
423
424     (The names head and headp are user selectable.)
425
426     The macro LIST_HEAD_INITIALIZER evaluates to an initializer for the list
427     head.
428
429     The macro LIST_EMPTY evaluates to true if there are no elements in the
430     list.
431
432     The macro LIST_ENTRY declares a structure that connects the elements in
433     the list.
434
435     The macro LIST_FIRST returns the first element in the list or NULL if the
436     list is empty.
437
438     The macro LIST_FOREACH traverses the list referenced by head in the for‐
439     ward direction, assigning each element in turn to var.
440
441     The macro LIST_INIT initializes the list referenced by head.
442
443     The macro LIST_INSERT_HEAD inserts the new element elm at the head of the
444     list.
445
446     The macro LIST_INSERT_AFTER inserts the new element elm after the element
447     listelm.
448
449     The macro LIST_INSERT_BEFORE inserts the new element elm before the ele‐
450     ment listelm.
451
452     The macro LIST_NEXT returns the next element in the list, or NULL if this
453     is the last.
454
455     The macro LIST_REMOVE removes the element elm from the list.
456
457   List example
458     LIST_HEAD(listhead, entry) head =
459         LIST_HEAD_INITIALIZER(head);
460     struct listhead *headp;                 /* List head. */
461     struct entry {
462             ...
463             LIST_ENTRY(entry) entries;      /* List. */
464             ...
465     } *n1, *n2, *n3, *np, *np_temp;
466
467     LIST_INIT(&head);                       /* Initialize the list. */
468
469     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
470     LIST_INSERT_HEAD(&head, n1, entries);
471
472     n2 = malloc(sizeof(struct entry));      /* Insert after. */
473     LIST_INSERT_AFTER(n1, n2, entries);
474
475     n3 = malloc(sizeof(struct entry));      /* Insert before. */
476     LIST_INSERT_BEFORE(n2, n3, entries);
477
478     LIST_REMOVE(n2, entries);               /* Deletion. */
479     free(n2);
480                                             /* Forward traversal. */
481     LIST_FOREACH(np, &head, entries)
482             np-> ...
483
484     while (!LIST_EMPTY(&head)) {            /* List Deletion. */
485             n1 = LIST_FIRST(&head);
486             LIST_REMOVE(n1, entries);
487             free(n1);
488     }
489
490     n1 = LIST_FIRST(&head);                 /* Faster List Deletion. */
491     while (n1 != NULL) {
492             n2 = LIST_NEXT(n1, entries);
493             free(n1);
494             n1 = n2;
495     }
496     LIST_INIT(&head);
497
498   Tail queues
499     A tail queue is headed by a structure defined by the TAILQ_HEAD macro.
500     This structure contains a pair of pointers, one to the first element in
501     the tail queue and the other to the last element in the tail queue.  The
502     elements are doubly linked so that an arbitrary element can be removed
503     without traversing the tail queue.  New elements can be added to the tail
504     queue after an existing element, before an existing element, at the head
505     of the tail queue, or at the end of the tail queue.  A TAILQ_HEAD struc‐
506     ture is declared as follows:
507
508           TAILQ_HEAD(HEADNAME, TYPE) head;
509
510     where HEADNAME is the name of the structure to be defined, and TYPE is
511     the type of the elements to be linked into the tail queue.  A pointer to
512     the head of the tail queue can later be declared as:
513
514           struct HEADNAME *headp;
515
516     (The names head and headp are user selectable.)
517
518     The macro TAILQ_HEAD_INITIALIZER evaluates to an initializer for the tail
519     queue head.
520
521     The macro TAILQ_CONCAT concatenates the tail queue headed by head2 onto
522     the end of the one headed by head1 removing all entries from the former.
523
524     The macro TAILQ_EMPTY evaluates to true if there are no items on the tail
525     queue.
526
527     The macro TAILQ_ENTRY declares a structure that connects the elements in
528     the tail queue.
529
530     The macro TAILQ_FIRST returns the first item on the tail queue or NULL if
531     the tail queue is empty.
532
533     The macro TAILQ_FOREACH traverses the tail queue referenced by head in
534     the forward direction, assigning each element in turn to var.  var is set
535     to NULL if the loop completes normally, or if there were no elements.
536
537     The macro TAILQ_FOREACH_REVERSE traverses the tail queue referenced by
538     head in the reverse direction, assigning each element in turn to var.
539
540     The macro TAILQ_INIT initializes the tail queue referenced by head.
541
542     The macro TAILQ_INSERT_HEAD inserts the new element elm at the head of
543     the tail queue.
544
545     The macro TAILQ_INSERT_TAIL inserts the new element elm at the end of the
546     tail queue.
547
548     The macro TAILQ_INSERT_AFTER inserts the new element elm after the ele‐
549     ment listelm.
550
551     The macro TAILQ_INSERT_BEFORE inserts the new element elm before the ele‐
552     ment listelm.
553
554     The macro TAILQ_LAST returns the last item on the tail queue.  If the
555     tail queue is empty the return value is NULL.
556
557     The macro TAILQ_NEXT returns the next item on the tail queue, or NULL if
558     this item is the last.
559
560     The macro TAILQ_PREV returns the previous item on the tail queue, or NULL
561     if this item is the first.
562
563     The macro TAILQ_REMOVE removes the element elm from the tail queue.
564
565     The macro TAILQ_SWAP swaps the contents of head1 and head2.
566
567   Tail queue example
568     TAILQ_HEAD(tailhead, entry) head =
569         TAILQ_HEAD_INITIALIZER(head);
570     struct tailhead *headp;                 /* Tail queue head. */
571     struct entry {
572             ...
573             TAILQ_ENTRY(entry) entries;     /* Tail queue. */
574             ...
575     } *n1, *n2, *n3, *np;
576
577     TAILQ_INIT(&head);                      /* Initialize the queue. */
578
579     n1 = malloc(sizeof(struct entry));      /* Insert at the head. */
580     TAILQ_INSERT_HEAD(&head, n1, entries);
581
582     n1 = malloc(sizeof(struct entry));      /* Insert at the tail. */
583     TAILQ_INSERT_TAIL(&head, n1, entries);
584
585     n2 = malloc(sizeof(struct entry));      /* Insert after. */
586     TAILQ_INSERT_AFTER(&head, n1, n2, entries);
587
588     n3 = malloc(sizeof(struct entry));      /* Insert before. */
589     TAILQ_INSERT_BEFORE(n2, n3, entries);
590
591     TAILQ_REMOVE(&head, n2, entries);       /* Deletion. */
592     free(n2);
593                                             /* Forward traversal. */
594     TAILQ_FOREACH(np, &head, entries)
595             np-> ...
596                                             /* Reverse traversal. */
597     TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
598             np-> ...
599                                             /* TailQ Deletion. */
600     while (!TAILQ_EMPTY(&head)) {
601             n1 = TAILQ_FIRST(&head);
602             TAILQ_REMOVE(&head, n1, entries);
603             free(n1);
604     }
605                                             /* Faster TailQ Deletion. */
606     n1 = TAILQ_FIRST(&head);
607     while (n1 != NULL) {
608             n2 = TAILQ_NEXT(n1, entries);
609             free(n1);
610             n1 = n2;
611     }
612
613     TAILQ_INIT(&head);
614     n2 = malloc(sizeof(struct entry));  /* Insert before. */
615     CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries);
616                                         /* Forward traversal. */
617     for (np = head.cqh_first; np != (void *)&head;
618             np = np->entries.cqe_next)
619         np-> ...
620                                         /* Reverse traversal. */
621     for (np = head.cqh_last; np != (void *)&head; np = np->entries.cqe_prev)
622         np-> ...
623                                         /* Delete. */
624     while (head.cqh_first != (void *)&head)
625         CIRCLEQ_REMOVE(&head, head.cqh_first, entries);
626

CONFORMING TO

628     Not in POSIX.1, POSIX.1-2001 or POSIX.1-2008.  Present on the BSDs.
629     queue functions first appeared in 4.4BSD.
630

COLOPHON

635     This page is part of release 4.16 of the Linux man-pages project.  A
636     description of the project, information about reporting bugs, and the
637     latest version of this page, can be found at
638     https://www.kernel.org/doc/man-pages/.
639
640BSD                            February 7, 2015                            BSD

NAME

SYNOPSIS

DESCRIPTION

CONFORMING TO

SEE ALSO

COLOPHON