1queue(3bsd) LOCAL queue(3bsd)
2
4 SLIST_CLASS_ENTRY, SLIST_CLASS_HEAD, SLIST_CONCAT, SLIST_EMPTY,
5 SLIST_ENTRY, SLIST_FIRST, SLIST_FOREACH, SLIST_FOREACH_FROM,
6 SLIST_FOREACH_FROM_SAFE, SLIST_FOREACH_SAFE, SLIST_HEAD,
7 SLIST_HEAD_INITIALIZER, SLIST_INIT, SLIST_INSERT_AFTER,
8 SLIST_INSERT_HEAD, SLIST_NEXT, SLIST_REMOVE, SLIST_REMOVE_AFTER,
9 SLIST_REMOVE_HEAD, SLIST_SWAP, STAILQ_CLASS_ENTRY, STAILQ_CLASS_HEAD,
10 STAILQ_CONCAT, STAILQ_EMPTY, STAILQ_ENTRY, STAILQ_FIRST, STAILQ_FOREACH,
11 STAILQ_FOREACH_FROM, STAILQ_FOREACH_FROM_SAFE, STAILQ_FOREACH_SAFE,
12 STAILQ_HEAD, STAILQ_HEAD_INITIALIZER, STAILQ_INIT, STAILQ_INSERT_AFTER,
13 STAILQ_INSERT_HEAD, STAILQ_INSERT_TAIL, STAILQ_LAST, STAILQ_NEXT,
14 STAILQ_REMOVE, STAILQ_REMOVE_AFTER, STAILQ_REMOVE_HEAD, STAILQ_SWAP,
15 LIST_CLASS_ENTRY, LIST_CLASS_HEAD, LIST_CONCAT, LIST_EMPTY, LIST_ENTRY,
16 LIST_FIRST, LIST_FOREACH, LIST_FOREACH_FROM, LIST_FOREACH_FROM_SAFE,
17 LIST_FOREACH_SAFE, LIST_HEAD, LIST_HEAD_INITIALIZER, LIST_INIT,
18 LIST_INSERT_AFTER, LIST_INSERT_BEFORE, LIST_INSERT_HEAD, LIST_NEXT,
19 LIST_PREV, LIST_REMOVE, LIST_SWAP, TAILQ_CLASS_ENTRY, TAILQ_CLASS_HEAD,
20 TAILQ_CONCAT, TAILQ_EMPTY, TAILQ_ENTRY, TAILQ_FIRST, TAILQ_FOREACH,
21 TAILQ_FOREACH_FROM, TAILQ_FOREACH_FROM_SAFE, TAILQ_FOREACH_REVERSE,
22 TAILQ_FOREACH_REVERSE_FROM, TAILQ_FOREACH_REVERSE_FROM_SAFE,
23 TAILQ_FOREACH_REVERSE_SAFE, TAILQ_FOREACH_SAFE, TAILQ_HEAD,
24 TAILQ_HEAD_INITIALIZER, TAILQ_INIT, TAILQ_INSERT_AFTER,
25 TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_INSERT_TAIL, TAILQ_LAST,
26 TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE, TAILQ_SWAP — implementations of
27 singly-linked lists, singly-linked tail queues, lists and tail queues
28
30 Utility functions from BSD systems (libbsd, -lbsd)
31
33 #include <sys/queue.h>
34 (See libbsd(7) for include usage.)
35
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
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
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
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
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
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
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
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
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
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
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
849 tree(3bsd)
850
852 The queue functions first appeared in 4.4BSD.
853
854BSD September 8, 2016 BSD