]>
Commit | Line | Data |
---|---|---|
1a575610 AC |
1 | .\" Copyright (c) 1993 |
2 | .\" The Regents of the University of California. All rights reserved. | |
cb0f97b2 | 3 | .\" and Copyright (c) 2020 by Alejandro Colomar <alx@kernel.org> |
1a575610 | 4 | .\" |
40fa0ff4 | 5 | .\" SPDX-License-Identifier: BSD-3-Clause |
1a575610 AC |
6 | .\" |
7 | .\" | |
ab47278f | 8 | .TH TAILQ 3 (date) "Linux man-pages (unreleased)" |
1a575610 | 9 | .SH NAME |
ace28997 AC |
10 | TAILQ_CONCAT, |
11 | TAILQ_EMPTY, | |
12 | TAILQ_ENTRY, | |
13 | TAILQ_FIRST, | |
14 | TAILQ_FOREACH, | |
15 | .\"TAILQ_FOREACH_FROM, | |
16 | .\"TAILQ_FOREACH_FROM_SAFE, | |
17 | TAILQ_FOREACH_REVERSE, | |
18 | .\"TAILQ_FOREACH_REVERSE_FROM, | |
19 | .\"TAILQ_FOREACH_REVERSE_FROM_SAFE, | |
20 | .\"TAILQ_FOREACH_REVERSE_SAFE, | |
21 | .\"TAILQ_FOREACH_SAFE, | |
22 | TAILQ_HEAD, | |
23 | TAILQ_HEAD_INITIALIZER, | |
24 | TAILQ_INIT, | |
25 | TAILQ_INSERT_AFTER, | |
26 | TAILQ_INSERT_BEFORE, | |
27 | TAILQ_INSERT_HEAD, | |
28 | TAILQ_INSERT_TAIL, | |
29 | TAILQ_LAST, | |
30 | TAILQ_NEXT, | |
31 | TAILQ_PREV, | |
32 | TAILQ_REMOVE | |
33 | .\"TAILQ_SWAP | |
df10ec35 | 34 | \- implementation of a doubly linked tail queue |
69f14064 AC |
35 | .SH LIBRARY |
36 | Standard C library | |
8fc3b2cf | 37 | .RI ( libc ", " \-lc ) |
1a575610 | 38 | .SH SYNOPSIS |
ace28997 | 39 | .nf |
ba273524 | 40 | .B #include <sys/queue.h> |
c6d039a3 | 41 | .P |
ace28997 | 42 | .B TAILQ_ENTRY(TYPE); |
c6d039a3 | 43 | .P |
ace28997 | 44 | .B TAILQ_HEAD(HEADNAME, TYPE); |
554afbe8 AC |
45 | .BI "TAILQ_HEAD TAILQ_HEAD_INITIALIZER(TAILQ_HEAD " head ); |
46 | .BI "void TAILQ_INIT(TAILQ_HEAD *" head ); | |
c6d039a3 | 47 | .P |
554afbe8 | 48 | .BI "int TAILQ_EMPTY(TAILQ_HEAD *" head ); |
c6d039a3 | 49 | .P |
554afbe8 AC |
50 | .BI "void TAILQ_INSERT_HEAD(TAILQ_HEAD *" head , |
51 | .BI " struct TYPE *" elm ", TAILQ_ENTRY " NAME ); | |
52 | .BI "void TAILQ_INSERT_TAIL(TAILQ_HEAD *" head , | |
53 | .BI " struct TYPE *" elm ", TAILQ_ENTRY " NAME ); | |
54 | .BI "void TAILQ_INSERT_BEFORE(struct TYPE *" listelm , | |
55 | .BI " struct TYPE *" elm ", TAILQ_ENTRY " NAME ); | |
56 | .BI "void TAILQ_INSERT_AFTER(TAILQ_HEAD *" head ", struct TYPE *" listelm , | |
57 | .BI " struct TYPE *" elm ", TAILQ_ENTRY " NAME ); | |
c6d039a3 | 58 | .P |
554afbe8 | 59 | .BI "struct TYPE *TAILQ_FIRST(TAILQ_HEAD *" head ); |
13e59b96 | 60 | .BI "struct TYPE *TAILQ_LAST(TAILQ_HEAD *" head ", HEADNAME);" |
554afbe8 AC |
61 | .BI "struct TYPE *TAILQ_PREV(struct TYPE *" elm ", HEADNAME, TAILQ_ENTRY " NAME ); |
62 | .BI "struct TYPE *TAILQ_NEXT(struct TYPE *" elm ", TAILQ_ENTRY " NAME ); | |
c6d039a3 | 63 | .P |
554afbe8 AC |
64 | .BI "TAILQ_FOREACH(struct TYPE *" var ", TAILQ_HEAD *" head , |
65 | .BI " TAILQ_ENTRY " NAME ); | |
66 | .\" .BI "TAILQ_FOREACH_FROM(struct TYPE *" var ", TAILQ_HEAD *" head , | |
67 | .\" .BI " TAILQ_ENTRY " NAME ); | |
68 | .BI "TAILQ_FOREACH_REVERSE(struct TYPE *" var ", TAILQ_HEAD *" head ", HEADNAME," | |
69 | .BI " TAILQ_ENTRY " NAME ); | |
70 | .\" .BI "TAILQ_FOREACH_REVERSE_FROM(struct TYPE *" var ", TAILQ_HEAD *" head ", HEADNAME," | |
71 | .\" .BI " TAILQ_ENTRY " NAME ); | |
c6d039a3 | 72 | .\" .P |
554afbe8 AC |
73 | .\" .BI "TAILQ_FOREACH_SAFE(struct TYPE *" var ", TAILQ_HEAD *" head , |
74 | .\" .BI " TAILQ_ENTRY " NAME , | |
75 | .\" .BI " struct TYPE *" temp_var ); | |
76 | .\" .BI "TAILQ_FOREACH_FROM_SAFE(struct TYPE *" var ", TAILQ_HEAD *" head , | |
77 | .\" .BI " TAILQ_ENTRY " NAME , | |
78 | .\" .BI " struct TYPE *" temp_var ); | |
79 | .\" .BI "TAILQ_FOREACH_REVERSE_SAFE(struct TYPE *" var ", TAILQ_HEAD *" head , | |
80 | .\" .BI " HEADNAME, TAILQ_ENTRY " NAME , | |
81 | .\" .BI " struct TYPE *" temp_var ); | |
82 | .\" .BI "TAILQ_FOREACH_REVERSE_FROM_SAFE(struct TYPE *" var ", TAILQ_HEAD *" head , | |
83 | .\" .BI " HEADNAME, TAILQ_ENTRY " NAME , | |
84 | .\" .BI " struct TYPE *" temp_var ); | |
c6d039a3 | 85 | .P |
554afbe8 AC |
86 | .BI "void TAILQ_REMOVE(TAILQ_HEAD *" head ", struct TYPE *" elm , |
87 | .BI " TAILQ_ENTRY " NAME ); | |
c6d039a3 | 88 | .P |
554afbe8 AC |
89 | .BI "void TAILQ_CONCAT(TAILQ_HEAD *" head1 ", TAILQ_HEAD *" head2 , |
90 | .BI " TAILQ_ENTRY " NAME ); | |
91 | .\" .BI "void TAILQ_SWAP(TAILQ_HEAD *" head1 ", TAILQ_HEAD *" head2 ", TYPE," | |
92 | .\" .BI " TAILQ_ENTRY " NAME ); | |
7a92eea0 | 93 | .fi |
1a575610 | 94 | .SH DESCRIPTION |
df10ec35 | 95 | These macros define and operate on doubly linked tail queues. |
c6d039a3 | 96 | .P |
32d12807 | 97 | In the macro definitions, |
ace28997 | 98 | .I TYPE |
32d12807 AC |
99 | is the name of a user defined structure, |
100 | that must contain a field of type | |
ace28997 | 101 | .IR TAILQ_ENTRY , |
32d12807 | 102 | named |
ace28997 | 103 | .IR NAME . |
32d12807 | 104 | The argument |
ace28997 | 105 | .I HEADNAME |
32d12807 | 106 | is the name of a user defined structure that must be declared |
cf5b6a77 | 107 | using the macro |
ace28997 | 108 | .BR TAILQ_HEAD (). |
554afbe8 | 109 | .SS Creation |
32d12807 | 110 | A tail queue is headed by a structure defined by the |
ace28997 | 111 | .BR TAILQ_HEAD () |
32d12807 AC |
112 | macro. |
113 | This structure contains a pair of pointers, | |
554afbe8 AC |
114 | one to the first element in the queue |
115 | and the other to the last element in the queue. | |
116 | The elements are doubly linked | |
117 | so that an arbitrary element can be removed without traversing the queue. | |
118 | New elements can be added to the queue | |
119 | after an existing element, | |
120 | before an existing element, | |
121 | at the head of the queue, | |
122 | or at the end of the queue. | |
32d12807 | 123 | A |
ace28997 | 124 | .I TAILQ_HEAD |
32d12807 | 125 | structure is declared as follows: |
c6d039a3 | 126 | .P |
ace28997 AC |
127 | .in +4 |
128 | .EX | |
32d12807 | 129 | TAILQ_HEAD(HEADNAME, TYPE) head; |
ace28997 AC |
130 | .EE |
131 | .in | |
c6d039a3 | 132 | .P |
32d12807 | 133 | where |
13e59b96 AC |
134 | .I struct HEADNAME |
135 | is the structure to be defined, and | |
136 | .I struct TYPE | |
554afbe8 AC |
137 | is the type of the elements to be linked into the queue. |
138 | A pointer to the head of the queue can later be declared as: | |
c6d039a3 | 139 | .P |
ace28997 AC |
140 | .in +4 |
141 | .EX | |
32d12807 | 142 | struct HEADNAME *headp; |
ace28997 AC |
143 | .EE |
144 | .in | |
c6d039a3 | 145 | .P |
32d12807 | 146 | (The names |
ace28997 | 147 | .I head |
32d12807 | 148 | and |
ace28997 | 149 | .I headp |
32d12807 | 150 | are user selectable.) |
c6d039a3 | 151 | .P |
554afbe8 AC |
152 | .BR TAILQ_ENTRY () |
153 | declares a structure that connects the elements in the queue. | |
c6d039a3 | 154 | .P |
ace28997 | 155 | .BR TAILQ_HEAD_INITIALIZER () |
554afbe8 | 156 | evaluates to an initializer for the queue |
ace28997 | 157 | .IR head . |
c6d039a3 | 158 | .P |
554afbe8 AC |
159 | .BR TAILQ_INIT () |
160 | initializes the queue referenced by | |
c6d039a3 | 161 | .P |
ace28997 | 162 | .BR TAILQ_EMPTY () |
554afbe8 AC |
163 | evaluates to true if there are no items on the queue. |
164 | .IR head . | |
165 | .SS Insertion | |
554afbe8 AC |
166 | .BR TAILQ_INSERT_HEAD () |
167 | inserts the new element | |
168 | .I elm | |
169 | at the head of the queue. | |
c6d039a3 | 170 | .P |
554afbe8 AC |
171 | .BR TAILQ_INSERT_TAIL () |
172 | inserts the new element | |
173 | .I elm | |
174 | at the end of the queue. | |
c6d039a3 | 175 | .P |
554afbe8 AC |
176 | .BR TAILQ_INSERT_BEFORE () |
177 | inserts the new element | |
178 | .I elm | |
179 | before the element | |
180 | .IR listelm . | |
c6d039a3 | 181 | .P |
554afbe8 AC |
182 | .BR TAILQ_INSERT_AFTER () |
183 | inserts the new element | |
184 | .I elm | |
185 | after the element | |
186 | .IR listelm . | |
187 | .SS Traversal | |
ace28997 | 188 | .BR TAILQ_FIRST () |
554afbe8 | 189 | returns the first item on the queue, or NULL if the queue is empty. |
c6d039a3 | 190 | .P |
554afbe8 AC |
191 | .BR TAILQ_LAST () |
192 | returns the last item on the queue. | |
193 | If the queue is empty the return value is NULL. | |
c6d039a3 | 194 | .P |
554afbe8 AC |
195 | .BR TAILQ_PREV () |
196 | returns the previous item on the queue, or NULL if this item is the first. | |
c6d039a3 | 197 | .P |
554afbe8 AC |
198 | .BR TAILQ_NEXT () |
199 | returns the next item on the queue, or NULL if this item is the last. | |
c6d039a3 | 200 | .P |
ace28997 | 201 | .BR TAILQ_FOREACH () |
554afbe8 | 202 | traverses the queue referenced by |
ace28997 | 203 | .I head |
554afbe8 AC |
204 | in the forward direction, |
205 | assigning each element in turn to | |
ace28997 AC |
206 | .IR var . |
207 | .I var | |
208 | is set to NULL if the loop completes normally, | |
209 | or if there were no elements. | |
c6d039a3 | 210 | .\" .P |
ace28997 | 211 | .\" .BR TAILQ_FOREACH_FROM () |
32d12807 | 212 | .\" behaves identically to |
ace28997 | 213 | .\" .BR TAILQ_FOREACH () |
32d12807 | 214 | .\" when |
ace28997 | 215 | .\" .I var |
32d12807 | 216 | .\" is NULL, else it treats |
ace28997 | 217 | .\" .I var |
32d12807 | 218 | .\" as a previously found TAILQ element and begins the loop at |
ace28997 | 219 | .\" .I var |
32d12807 | 220 | .\" instead of the first element in the TAILQ referenced by |
ace28997 | 221 | .\" .IR head . |
c6d039a3 | 222 | .P |
ace28997 | 223 | .BR TAILQ_FOREACH_REVERSE () |
554afbe8 | 224 | traverses the queue referenced by |
ace28997 | 225 | .I head |
554afbe8 AC |
226 | in the reverse direction, |
227 | assigning each element in turn to | |
ace28997 | 228 | .IR var . |
c6d039a3 | 229 | .\" .P |
ace28997 | 230 | .\" .BR TAILQ_FOREACH_REVERSE_FROM () |
32d12807 | 231 | .\" behaves identically to |
ace28997 | 232 | .\" .BR TAILQ_FOREACH_REVERSE () |
32d12807 | 233 | .\" when |
ace28997 | 234 | .\" .I var |
32d12807 | 235 | .\" is NULL, else it treats |
ace28997 | 236 | .\" .I var |
32d12807 | 237 | .\" as a previously found TAILQ element and begins the reverse loop at |
ace28997 | 238 | .\" .I var |
32d12807 | 239 | .\" instead of the last element in the TAILQ referenced by |
ace28997 | 240 | .\" .IR head . |
c6d039a3 | 241 | .\" .P |
ace28997 | 242 | .\" .BR TAILQ_FOREACH_SAFE () |
32d12807 | 243 | .\" and |
ace28997 | 244 | .\" .BR TAILQ_FOREACH_REVERSE_SAFE () |
32d12807 | 245 | .\" traverse the list referenced by |
ace28997 | 246 | .\" .I head |
32d12807 AC |
247 | .\" in the forward or reverse direction respectively, |
248 | .\" assigning each element in turn to | |
ace28997 | 249 | .\" .IR var . |
32d12807 | 250 | .\" However, unlike their unsafe counterparts, |
ace28997 | 251 | .\" .BR TAILQ_FOREACH () |
32d12807 | 252 | .\" and |
ace28997 | 253 | .\" .BR TAILQ_FOREACH_REVERSE () |
32d12807 | 254 | .\" permit to both remove |
ace28997 | 255 | .\" .I var |
32d12807 AC |
256 | .\" as well as free it from within the loop safely without interfering with the |
257 | .\" traversal. | |
c6d039a3 | 258 | .\" .P |
ace28997 | 259 | .\" .BR TAILQ_FOREACH_FROM_SAFE () |
32d12807 | 260 | .\" behaves identically to |
ace28997 | 261 | .\" .BR TAILQ_FOREACH_SAFE () |
32d12807 | 262 | .\" when |
ace28997 | 263 | .\" .I var |
32d12807 | 264 | .\" is NULL, else it treats |
ace28997 | 265 | .\" .I var |
32d12807 | 266 | .\" as a previously found TAILQ element and begins the loop at |
ace28997 | 267 | .\" .I var |
32d12807 | 268 | .\" instead of the first element in the TAILQ referenced by |
ace28997 | 269 | .\" .IR head . |
c6d039a3 | 270 | .\" .P |
ace28997 | 271 | .\" .BR TAILQ_FOREACH_REVERSE_FROM_SAFE () |
32d12807 | 272 | .\" behaves identically to |
ace28997 | 273 | .\" .BR TAILQ_FOREACH_REVERSE_SAFE () |
32d12807 | 274 | .\" when |
ace28997 | 275 | .\" .I var |
32d12807 | 276 | .\" is NULL, else it treats |
ace28997 | 277 | .\" .I var |
32d12807 | 278 | .\" as a previously found TAILQ element and begins the reverse loop at |
ace28997 | 279 | .\" .I var |
32d12807 | 280 | .\" instead of the last element in the TAILQ referenced by |
ace28997 | 281 | .\" .IR head . |
554afbe8 | 282 | .SS Removal |
ace28997 | 283 | .BR TAILQ_REMOVE () |
32d12807 | 284 | removes the element |
ace28997 | 285 | .I elm |
554afbe8 AC |
286 | from the queue. |
287 | .SS Other features | |
ace28997 | 288 | .\" .BR TAILQ_SWAP () |
32d12807 | 289 | .\" swaps the contents of |
ace28997 | 290 | .\" .I head1 |
32d12807 | 291 | .\" and |
ace28997 | 292 | .\" .IR head2 . |
c6d039a3 | 293 | .\" .P |
554afbe8 AC |
294 | .BR TAILQ_CONCAT () |
295 | concatenates the queue headed by | |
296 | .I head2 | |
297 | onto the end of the one headed by | |
298 | .I head1 | |
299 | removing all entries from the former. | |
1a575610 | 300 | .SH RETURN VALUE |
ec99c74d AC |
301 | .BR TAILQ_EMPTY () |
302 | returns nonzero if the queue is empty, | |
303 | and zero if the queue contains at least one entry. | |
c6d039a3 | 304 | .P |
ec99c74d AC |
305 | .BR TAILQ_FIRST (), |
306 | .BR TAILQ_LAST (), | |
554afbe8 | 307 | .BR TAILQ_PREV (), |
ec99c74d | 308 | and |
554afbe8 | 309 | .BR TAILQ_NEXT () |
3ded684c | 310 | return a pointer to the first, last, previous, or next |
ec99c74d AC |
311 | .I TYPE |
312 | structure, respectively. | |
c6d039a3 | 313 | .P |
ec99c74d AC |
314 | .BR TAILQ_HEAD_INITIALIZER () |
315 | returns an initializer that can be assigned to the queue | |
316 | .IR head . | |
3113c7f3 | 317 | .SH STANDARDS |
4131356c AC |
318 | BSD. |
319 | .SH HISTORY | |
320 | 4.4BSD. | |
321 | .SH CAVEATS | |
ec99c74d AC |
322 | .BR TAILQ_FOREACH () |
323 | and | |
324 | .BR TAILQ_FOREACH_REVERSE () | |
325 | don't allow | |
326 | .I var | |
327 | to be removed or freed within the loop, | |
328 | as it would interfere with the traversal. | |
ec99c74d AC |
329 | .BR TAILQ_FOREACH_SAFE () |
330 | and | |
331 | .BR TAILQ_FOREACH_REVERSE_SAFE (), | |
332 | which are present on the BSDs but are not present in glibc, | |
333 | fix this limitation by allowing | |
334 | .I var | |
335 | to safely be removed from the list and freed from within the loop | |
336 | without interfering with the traversal. | |
1a575610 | 337 | .SH EXAMPLES |
b0b6ab4e | 338 | .\" SRC BEGIN (tailq.c) |
ace28997 | 339 | .EX |
7b8d4bbf AC |
340 | #include <stddef.h> |
341 | #include <stdio.h> | |
342 | #include <stdlib.h> | |
343 | #include <sys/queue.h> | |
fe5dba13 | 344 | \& |
7b8d4bbf AC |
345 | struct entry { |
346 | int data; | |
c2e81ff9 | 347 | TAILQ_ENTRY(entry) entries; /* Tail queue */ |
7b8d4bbf | 348 | }; |
fe5dba13 | 349 | \& |
7b8d4bbf | 350 | TAILQ_HEAD(tailhead, entry); |
fe5dba13 | 351 | \& |
7b8d4bbf AC |
352 | int |
353 | main(void) | |
354 | { | |
cf5b6a77 | 355 | struct entry *n1, *n2, *n3, *np; |
c2e81ff9 | 356 | struct tailhead head; /* Tail queue head */ |
cf5b6a77 | 357 | int i; |
fe5dba13 | 358 | \& |
c2e81ff9 | 359 | TAILQ_INIT(&head); /* Initialize the queue */ |
fe5dba13 | 360 | \& |
c2e81ff9 | 361 | n1 = malloc(sizeof(struct entry)); /* Insert at the head */ |
7b8d4bbf | 362 | TAILQ_INSERT_HEAD(&head, n1, entries); |
fe5dba13 | 363 | \& |
c2e81ff9 | 364 | n1 = malloc(sizeof(struct entry)); /* Insert at the tail */ |
7b8d4bbf | 365 | TAILQ_INSERT_TAIL(&head, n1, entries); |
fe5dba13 | 366 | \& |
c2e81ff9 | 367 | n2 = malloc(sizeof(struct entry)); /* Insert after */ |
7b8d4bbf | 368 | TAILQ_INSERT_AFTER(&head, n1, n2, entries); |
fe5dba13 | 369 | \& |
c2e81ff9 | 370 | n3 = malloc(sizeof(struct entry)); /* Insert before */ |
7b8d4bbf | 371 | TAILQ_INSERT_BEFORE(n2, n3, entries); |
fe5dba13 | 372 | \& |
c2e81ff9 | 373 | TAILQ_REMOVE(&head, n2, entries); /* Deletion */ |
7b8d4bbf | 374 | free(n2); |
c2e81ff9 | 375 | /* Forward traversal */ |
7b8d4bbf AC |
376 | i = 0; |
377 | TAILQ_FOREACH(np, &head, entries) | |
d064d41a | 378 | np\->data = i++; |
c2e81ff9 | 379 | /* Reverse traversal */ |
7b8d4bbf | 380 | TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) |
d064d41a | 381 | printf("%i\en", np\->data); |
f52cb552 | 382 | /* TailQ deletion */ |
7b8d4bbf AC |
383 | n1 = TAILQ_FIRST(&head); |
384 | while (n1 != NULL) { | |
385 | n2 = TAILQ_NEXT(n1, entries); | |
386 | free(n1); | |
387 | n1 = n2; | |
388 | } | |
389 | TAILQ_INIT(&head); | |
fe5dba13 | 390 | \& |
7b8d4bbf AC |
391 | exit(EXIT_SUCCESS); |
392 | } | |
ace28997 | 393 | .EE |
b0b6ab4e | 394 | .\" SRC END |
1a575610 | 395 | .SH SEE ALSO |
ec99c74d | 396 | .BR insque (3), |
083d4e6a | 397 | .BR queue (7) |