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