1TAILQ(3) Linux Programmer's Manual TAILQ(3)
2
6 TAILQ_CONCAT, TAILQ_EMPTY, TAILQ_ENTRY, TAILQ_FIRST, TAILQ_FOREACH,
7 TAILQ_FOREACH_REVERSE, TAILQ_HEAD, TAILQ_HEAD_INITIALIZER, TAILQ_INIT,
8 TAILQ_INSERT_AFTER, TAILQ_INSERT_BEFORE, TAILQ_INSERT_HEAD, TAILQ_IN‐
9 SERT_TAIL, TAILQ_LAST, TAILQ_NEXT, TAILQ_PREV, TAILQ_REMOVE - implemen‐
10 tation of a doubly linked tail queue
11
13 #include <sys/queue.h>
14 TAILQ_ENTRY(TYPE);
16 TAILQ_HEAD(HEADNAME, TYPE);
18 TAILQ_HEAD TAILQ_HEAD_INITIALIZER(TAILQ_HEAD head);
19 void TAILQ_INIT(TAILQ_HEAD *head);
20 int TAILQ_EMPTY(TAILQ_HEAD *head);
22 void TAILQ_INSERT_HEAD(TAILQ_HEAD *head,
24 struct TYPE *elm, TAILQ_ENTRY NAME);
25 void TAILQ_INSERT_TAIL(TAILQ_HEAD *head,
26 struct TYPE *elm, TAILQ_ENTRY NAME);
27 void TAILQ_INSERT_BEFORE(struct TYPE *listelm,
28 struct TYPE *elm, TAILQ_ENTRY NAME);
29 void TAILQ_INSERT_AFTER(TAILQ_HEAD *head, struct TYPE *listelm,
30 struct TYPE *elm, TAILQ_ENTRY NAME);
31 struct TYPE *TAILQ_FIRST(TAILQ_HEAD *head);
33 struct TYPE *TAILQ_LAST(TAILQ_HEAD *head, HEADNAME);
34 struct TYPE *TAILQ_PREV(struct TYPE *elm, HEADNAME, TAILQ_ENTRY NAME);
35 struct TYPE *TAILQ_NEXT(struct TYPE *elm, TAILQ_ENTRY NAME);
36 TAILQ_FOREACH(struct TYPE *var, TAILQ_HEAD *head,
38 TAILQ_ENTRY NAME);
39 TAILQ_FOREACH_REVERSE(struct TYPE *var, TAILQ_HEAD *head, HEADNAME,
40 TAILQ_ENTRY NAME);
41 void TAILQ_REMOVE(TAILQ_HEAD *head, struct TYPE *elm,
43 TAILQ_ENTRY NAME);
44 void TAILQ_CONCAT(TAILQ_HEAD *head1, TAILQ_HEAD *head2,
46 TAILQ_ENTRY NAME);
47
49 These macros define and operate on doubly linked tail queues.
50 In the macro definitions, TYPE is the name of a user defined structure,
52 that must contain a field of type TAILQ_ENTRY, named NAME. The argu‐
53 ment HEADNAME is the name of a user defined structure that must be de‐
54 clared using the macro TAILQ_HEAD().
55 Creation
57 A tail queue is headed by a structure defined by the TAILQ_HEAD()
58 macro. This structure contains a pair of pointers, one to the first
59 element in the queue and the other to the last element in the queue.
60 The elements are doubly linked so that an arbitrary element can be re‐
61 moved without traversing the queue. New elements can be added to the
62 queue after an existing element, before an existing element, at the
63 head of the queue, or at the end of the queue. A TAILQ_HEAD structure
64 is declared as follows:
65 TAILQ_HEAD(HEADNAME, TYPE) head;
67 where struct HEADNAME is the structure to be defined, and struct TYPE
69 is the type of the elements to be linked into the queue. A pointer to
70 the head of the queue can later be declared as:
71 struct HEADNAME *headp;
73 (The names head and headp are user selectable.)
75 TAILQ_ENTRY() declares a structure that connects the elements in the
77 queue.
78 TAILQ_HEAD_INITIALIZER() evaluates to an initializer for the queue
80 head.
81 TAILQ_INIT() initializes the queue referenced by
83 TAILQ_EMPTY() evaluates to true if there are no items on the queue.
85 head.
86 Insertion
88 TAILQ_INSERT_HEAD() inserts the new element elm at the head of the
89 queue.
90 TAILQ_INSERT_TAIL() inserts the new element elm at the end of the
92 queue.
93 TAILQ_INSERT_BEFORE() inserts the new element elm before the element
95 listelm.
96 TAILQ_INSERT_AFTER() inserts the new element elm after the element lis‐
98 telm.
99 Traversal
101 TAILQ_FIRST() returns the first item on the queue, or NULL if the queue
102 is empty.
103 TAILQ_LAST() returns the last item on the queue. If the queue is empty
105 the return value is NULL.
106 TAILQ_PREV() returns the previous item on the queue, or NULL if this
108 item is the first.
109 TAILQ_NEXT() returns the next item on the queue, or NULL if this item
111 is the last.
112 TAILQ_FOREACH() traverses the queue referenced by head in the forward
114 direction, assigning each element in turn to var. var is set to NULL
115 if the loop completes normally, or if there were no elements.
116 TAILQ_FOREACH_REVERSE() traverses the queue referenced by head in the
118 reverse direction, assigning each element in turn to var.
119 Removal
121 TAILQ_REMOVE() removes the element elm from the queue.
122 Other features
124 TAILQ_CONCAT() concatenates the queue headed by head2 onto the end of
125 the one headed by head1 removing all entries from the former.
126
128 TAILQ_EMPTY() returns nonzero if the queue is empty, and zero if the
129 queue contains at least one entry.
130 TAILQ_FIRST(), TAILQ_LAST(), TAILQ_PREV(), and TAILQ_NEXT() return a
132 pointer to the first, last, previous, or next TYPE structure, respec‐
133 tively.
134 TAILQ_HEAD_INITIALIZER() returns an initializer that can be assigned to
136 the queue head.
137
139 Not in POSIX.1, POSIX.1-2001, or POSIX.1-2008. Present on the BSDs.
140 (TAILQ functions first appeared in 4.4BSD).
141
143 TAILQ_FOREACH() and TAILQ_FOREACH_REVERSE() don't allow var to be re‐
144 moved or freed within the loop, as it would interfere with the traver‐
145 sal. TAILQ_FOREACH_SAFE() and TAILQ_FOREACH_REVERSE_SAFE(), which are
146 present on the BSDs but are not present in glibc, fix this limitation
147 by allowing var to safely be removed from the list and freed from
148 within the loop without interfering with the traversal.
149
151 #include <stddef.h>
152 #include <stdio.h>
153 #include <stdlib.h>
154 #include <sys/queue.h>
155 struct entry {
157 int data;
158 TAILQ_ENTRY(entry) entries; /* Tail queue */
159 };
160 TAILQ_HEAD(tailhead, entry);
162 int
164 main(void)
165 {
166 struct entry *n1, *n2, *n3, *np;
167 struct tailhead head; /* Tail queue head */
168 int i;
169 TAILQ_INIT(&head); /* Initialize the queue */
171 n1 = malloc(sizeof(struct entry)); /* Insert at the head */
173 TAILQ_INSERT_HEAD(&head, n1, entries);
174 n1 = malloc(sizeof(struct entry)); /* Insert at the tail */
176 TAILQ_INSERT_TAIL(&head, n1, entries);
177 n2 = malloc(sizeof(struct entry)); /* Insert after */
179 TAILQ_INSERT_AFTER(&head, n1, n2, entries);
180 n3 = malloc(sizeof(struct entry)); /* Insert before */
182 TAILQ_INSERT_BEFORE(n2, n3, entries);
183 TAILQ_REMOVE(&head, n2, entries); /* Deletion */
185 free(n2);
186 /* Forward traversal */
187 i = 0;
188 TAILQ_FOREACH(np, &head, entries)
189 np->data = i++;
190 /* Reverse traversal */
191 TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries)
192 printf("%i\n", np->data);
193 /* TailQ deletion */
194 n1 = TAILQ_FIRST(&head);
195 while (n1 != NULL) {
196 n2 = TAILQ_NEXT(n1, entries);
197 free(n1);
198 n1 = n2;
199 }
200 TAILQ_INIT(&head);
201 exit(EXIT_SUCCESS);
203 }
204
206 insque(3), queue(7)
207
209 This page is part of release 5.12 of the Linux man-pages project. A
210 description of the project, information about reporting bugs, and the
211 latest version of this page, can be found at
212 https://www.kernel.org/doc/man-pages/.
213GNU 2021-03-22 TAILQ(3)