]>
Commit | Line | Data |
---|---|---|
fea681da | 1 | .\" Copyright (c) 1993 |
c0f21a05 | 2 | .\" The Regents of the University of California. All rights reserved. |
fea681da | 3 | .\" |
ed69ec52 | 4 | .\" %%%LICENSE_START(BSD_3_CLAUSE_UCB) |
fea681da MK |
5 | .\" Redistribution and use in source and binary forms, with or without |
6 | .\" modification, are permitted provided that the following conditions | |
7 | .\" are met: | |
8 | .\" 1. Redistributions of source code must retain the above copyright | |
9 | .\" notice, this list of conditions and the following disclaimer. | |
10 | .\" 2. Redistributions in binary form must reproduce the above copyright | |
11 | .\" notice, this list of conditions and the following disclaimer in the | |
12 | .\" documentation and/or other materials provided with the distribution. | |
c0f21a05 | 13 | .\" 3. Neither the name of the University nor the names of its contributors |
fea681da MK |
14 | .\" may be used to endorse or promote products derived from this software |
15 | .\" without specific prior written permission. | |
16 | .\" | |
17 | .\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND | |
18 | .\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
19 | .\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
20 | .\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE | |
21 | .\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
22 | .\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
23 | .\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
24 | .\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
25 | .\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
26 | .\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
27 | .\" SUCH DAMAGE. | |
ed69ec52 | 28 | .\" %%%LICENSE_END |
fea681da | 29 | .\" |
c0f21a05 MK |
30 | .\" @(#)queue.3 8.2 (Berkeley) 1/24/94 |
31 | .\" $FreeBSD$ | |
fea681da | 32 | .\" |
929ec2c6 | 33 | .Dd February 7, 2015 |
c0f21a05 MK |
34 | .Dt QUEUE 3 |
35 | .Os | |
36 | .Sh NAME | |
37 | .Nm SLIST_EMPTY , | |
38 | .Nm SLIST_ENTRY , | |
39 | .Nm SLIST_FIRST , | |
40 | .Nm SLIST_FOREACH , | |
6559169c MK |
41 | .\" .Nm SLIST_FOREACH_FROM , |
42 | .\" .Nm SLIST_FOREACH_SAFE , | |
43 | .\" .Nm SLIST_FOREACH_FROM_SAFE , | |
c0f21a05 MK |
44 | .Nm SLIST_HEAD , |
45 | .Nm SLIST_HEAD_INITIALIZER , | |
46 | .Nm SLIST_INIT , | |
47 | .Nm SLIST_INSERT_AFTER , | |
48 | .Nm SLIST_INSERT_HEAD , | |
49 | .Nm SLIST_NEXT , | |
6559169c | 50 | .\" .Nm SLIST_REMOVE_AFTER , |
c0f21a05 MK |
51 | .Nm SLIST_REMOVE_HEAD , |
52 | .Nm SLIST_REMOVE , | |
6559169c | 53 | .\" .Nm SLIST_SWAP , |
c0f21a05 MK |
54 | .Nm STAILQ_CONCAT , |
55 | .Nm STAILQ_EMPTY , | |
56 | .Nm STAILQ_ENTRY , | |
57 | .Nm STAILQ_FIRST , | |
58 | .Nm STAILQ_FOREACH , | |
6559169c MK |
59 | .\" .Nm STAILQ_FOREACH_FROM , |
60 | .\" .Nm STAILQ_FOREACH_SAFE , | |
61 | .\" .Nm STAILQ_FOREACH_FROM_SAFE , | |
c0f21a05 MK |
62 | .Nm STAILQ_HEAD , |
63 | .Nm STAILQ_HEAD_INITIALIZER , | |
64 | .Nm STAILQ_INIT , | |
65 | .Nm STAILQ_INSERT_AFTER , | |
66 | .Nm STAILQ_INSERT_HEAD , | |
67 | .Nm STAILQ_INSERT_TAIL , | |
6559169c | 68 | .\" .Nm STAILQ_LAST , |
c0f21a05 | 69 | .Nm STAILQ_NEXT , |
6559169c | 70 | .\" .Nm STAILQ_REMOVE_AFTER , |
c0f21a05 MK |
71 | .Nm STAILQ_REMOVE_HEAD , |
72 | .Nm STAILQ_REMOVE , | |
6559169c | 73 | .\" .Nm STAILQ_SWAP , |
c0f21a05 MK |
74 | .Nm LIST_EMPTY , |
75 | .Nm LIST_ENTRY , | |
76 | .Nm LIST_FIRST , | |
77 | .Nm LIST_FOREACH , | |
6559169c MK |
78 | .\" .Nm LIST_FOREACH_FROM , |
79 | .\" .Nm LIST_FOREACH_SAFE , | |
80 | .\" .Nm LIST_FOREACH_FROM_SAFE , | |
c0f21a05 MK |
81 | .Nm LIST_HEAD , |
82 | .Nm LIST_HEAD_INITIALIZER , | |
83 | .Nm LIST_INIT , | |
84 | .Nm LIST_INSERT_AFTER , | |
85 | .Nm LIST_INSERT_BEFORE , | |
86 | .Nm LIST_INSERT_HEAD , | |
87 | .Nm LIST_NEXT , | |
6559169c | 88 | .\" .Nm LIST_PREV , |
c0f21a05 | 89 | .Nm LIST_REMOVE , |
6559169c | 90 | .\" .Nm LIST_SWAP , |
c0f21a05 MK |
91 | .Nm TAILQ_CONCAT , |
92 | .Nm TAILQ_EMPTY , | |
93 | .Nm TAILQ_ENTRY , | |
94 | .Nm TAILQ_FIRST , | |
95 | .Nm TAILQ_FOREACH , | |
6559169c MK |
96 | .\" .Nm TAILQ_FOREACH_FROM , |
97 | .\" .Nm TAILQ_FOREACH_SAFE , | |
98 | .\" .Nm TAILQ_FOREACH_FROM_SAFE , | |
c0f21a05 | 99 | .Nm TAILQ_FOREACH_REVERSE , |
6559169c MK |
100 | .\" .Nm TAILQ_FOREACH_REVERSE_FROM , |
101 | .\" .Nm TAILQ_FOREACH_REVERSE_SAFE , | |
102 | .\" .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE , | |
c0f21a05 MK |
103 | .Nm TAILQ_HEAD , |
104 | .Nm TAILQ_HEAD_INITIALIZER , | |
105 | .Nm TAILQ_INIT , | |
106 | .Nm TAILQ_INSERT_AFTER , | |
107 | .Nm TAILQ_INSERT_BEFORE , | |
108 | .Nm TAILQ_INSERT_HEAD , | |
109 | .Nm TAILQ_INSERT_TAIL , | |
110 | .Nm TAILQ_LAST , | |
111 | .Nm TAILQ_NEXT , | |
112 | .Nm TAILQ_PREV , | |
113 | .Nm TAILQ_REMOVE , | |
114 | .Nm TAILQ_SWAP | |
115 | .Nd implementations of singly-linked lists, singly-linked tail queues, | |
116 | lists and tail queues | |
117 | .Sh SYNOPSIS | |
118 | .In sys/queue.h | |
fea681da | 119 | .\" |
c0f21a05 MK |
120 | .Fn SLIST_EMPTY "SLIST_HEAD *head" |
121 | .Fn SLIST_ENTRY "TYPE" | |
122 | .Fn SLIST_FIRST "SLIST_HEAD *head" | |
123 | .Fn SLIST_FOREACH "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" | |
6559169c MK |
124 | .\" .Fn SLIST_FOREACH_FROM "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" |
125 | .\" .Fn SLIST_FOREACH_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" | |
126 | .\" .Fn SLIST_FOREACH_FROM_SAFE "TYPE *var" "SLIST_HEAD *head" "SLIST_ENTRY NAME" "TYPE *temp_var" | |
c0f21a05 MK |
127 | .Fn SLIST_HEAD "HEADNAME" "TYPE" |
128 | .Fn SLIST_HEAD_INITIALIZER "SLIST_HEAD head" | |
129 | .Fn SLIST_INIT "SLIST_HEAD *head" | |
130 | .Fn SLIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "SLIST_ENTRY NAME" | |
131 | .Fn SLIST_INSERT_HEAD "SLIST_HEAD *head" "TYPE *elm" "SLIST_ENTRY NAME" | |
132 | .Fn SLIST_NEXT "TYPE *elm" "SLIST_ENTRY NAME" | |
6559169c | 133 | .\" .Fn SLIST_REMOVE_AFTER "TYPE *elm" "SLIST_ENTRY NAME" |
c0f21a05 MK |
134 | .Fn SLIST_REMOVE_HEAD "SLIST_HEAD *head" "SLIST_ENTRY NAME" |
135 | .Fn SLIST_REMOVE "SLIST_HEAD *head" "TYPE *elm" "TYPE" "SLIST_ENTRY NAME" | |
6559169c | 136 | .\" .Fn SLIST_SWAP "SLIST_HEAD *head1" "SLIST_HEAD *head2" "SLIST_ENTRY NAME" |
c0f21a05 MK |
137 | .\" |
138 | .Fn STAILQ_CONCAT "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" | |
139 | .Fn STAILQ_EMPTY "STAILQ_HEAD *head" | |
140 | .Fn STAILQ_ENTRY "TYPE" | |
141 | .Fn STAILQ_FIRST "STAILQ_HEAD *head" | |
142 | .Fn STAILQ_FOREACH "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" | |
6559169c MK |
143 | .\" .Fn STAILQ_FOREACH_FROM "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" |
144 | .\" .Fn STAILQ_FOREACH_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" | |
145 | .\" .Fn STAILQ_FOREACH_FROM_SAFE "TYPE *var" "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" "TYPE *temp_var" | |
c0f21a05 MK |
146 | .Fn STAILQ_HEAD "HEADNAME" "TYPE" |
147 | .Fn STAILQ_HEAD_INITIALIZER "STAILQ_HEAD head" | |
148 | .Fn STAILQ_INIT "STAILQ_HEAD *head" | |
149 | .Fn STAILQ_INSERT_AFTER "STAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "STAILQ_ENTRY NAME" | |
150 | .Fn STAILQ_INSERT_HEAD "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" | |
151 | .Fn STAILQ_INSERT_TAIL "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" | |
6559169c | 152 | .\" .Fn STAILQ_LAST "STAILQ_HEAD *head" "TYPE" "STAILQ_ENTRY NAME" |
c0f21a05 | 153 | .Fn STAILQ_NEXT "TYPE *elm" "STAILQ_ENTRY NAME" |
6559169c | 154 | .\" .Fn STAILQ_REMOVE_AFTER "STAILQ_HEAD *head" "TYPE *elm" "STAILQ_ENTRY NAME" |
c0f21a05 MK |
155 | .Fn STAILQ_REMOVE_HEAD "STAILQ_HEAD *head" "STAILQ_ENTRY NAME" |
156 | .Fn STAILQ_REMOVE "STAILQ_HEAD *head" "TYPE *elm" "TYPE" "STAILQ_ENTRY NAME" | |
6559169c | 157 | .\" .Fn STAILQ_SWAP "STAILQ_HEAD *head1" "STAILQ_HEAD *head2" "STAILQ_ENTRY NAME" |
c0f21a05 MK |
158 | .\" |
159 | .Fn LIST_EMPTY "LIST_HEAD *head" | |
160 | .Fn LIST_ENTRY "TYPE" | |
161 | .Fn LIST_FIRST "LIST_HEAD *head" | |
162 | .Fn LIST_FOREACH "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" | |
6559169c MK |
163 | .\" .Fn LIST_FOREACH_FROM "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" |
164 | .\" .Fn LIST_FOREACH_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" | |
165 | .\" .Fn LIST_FOREACH_FROM_SAFE "TYPE *var" "LIST_HEAD *head" "LIST_ENTRY NAME" "TYPE *temp_var" | |
c0f21a05 MK |
166 | .Fn LIST_HEAD "HEADNAME" "TYPE" |
167 | .Fn LIST_HEAD_INITIALIZER "LIST_HEAD head" | |
168 | .Fn LIST_INIT "LIST_HEAD *head" | |
169 | .Fn LIST_INSERT_AFTER "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" | |
170 | .Fn LIST_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "LIST_ENTRY NAME" | |
171 | .Fn LIST_INSERT_HEAD "LIST_HEAD *head" "TYPE *elm" "LIST_ENTRY NAME" | |
172 | .Fn LIST_NEXT "TYPE *elm" "LIST_ENTRY NAME" | |
6559169c | 173 | .\" .Fn LIST_PREV "TYPE *elm" "LIST_HEAD *head" "TYPE" "LIST_ENTRY NAME" |
c0f21a05 MK |
174 | .Fn LIST_REMOVE "TYPE *elm" "LIST_ENTRY NAME" |
175 | .Fn LIST_SWAP "LIST_HEAD *head1" "LIST_HEAD *head2" "TYPE" "LIST_ENTRY NAME" | |
176 | .\" | |
177 | .Fn TAILQ_CONCAT "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TAILQ_ENTRY NAME" | |
178 | .Fn TAILQ_EMPTY "TAILQ_HEAD *head" | |
179 | .Fn TAILQ_ENTRY "TYPE" | |
180 | .Fn TAILQ_FIRST "TAILQ_HEAD *head" | |
181 | .Fn TAILQ_FOREACH "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" | |
6559169c MK |
182 | .\" .Fn TAILQ_FOREACH_FROM "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" |
183 | .\" .Fn TAILQ_FOREACH_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" | |
184 | .\" .Fn TAILQ_FOREACH_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "TAILQ_ENTRY NAME" "TYPE *temp_var" | |
c0f21a05 | 185 | .Fn TAILQ_FOREACH_REVERSE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" |
6559169c MK |
186 | .\" .Fn TAILQ_FOREACH_REVERSE_FROM "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" |
187 | .\" .Fn TAILQ_FOREACH_REVERSE_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" | |
188 | .\" .Fn TAILQ_FOREACH_REVERSE_FROM_SAFE "TYPE *var" "TAILQ_HEAD *head" "HEADNAME" "TAILQ_ENTRY NAME" "TYPE *temp_var" | |
c0f21a05 MK |
189 | .Fn TAILQ_HEAD "HEADNAME" "TYPE" |
190 | .Fn TAILQ_HEAD_INITIALIZER "TAILQ_HEAD head" | |
191 | .Fn TAILQ_INIT "TAILQ_HEAD *head" | |
192 | .Fn TAILQ_INSERT_AFTER "TAILQ_HEAD *head" "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" | |
193 | .Fn TAILQ_INSERT_BEFORE "TYPE *listelm" "TYPE *elm" "TAILQ_ENTRY NAME" | |
194 | .Fn TAILQ_INSERT_HEAD "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" | |
195 | .Fn TAILQ_INSERT_TAIL "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" | |
196 | .Fn TAILQ_LAST "TAILQ_HEAD *head" "HEADNAME" | |
197 | .Fn TAILQ_NEXT "TYPE *elm" "TAILQ_ENTRY NAME" | |
198 | .Fn TAILQ_PREV "TYPE *elm" "HEADNAME" "TAILQ_ENTRY NAME" | |
199 | .Fn TAILQ_REMOVE "TAILQ_HEAD *head" "TYPE *elm" "TAILQ_ENTRY NAME" | |
200 | .Fn TAILQ_SWAP "TAILQ_HEAD *head1" "TAILQ_HEAD *head2" "TYPE" "TAILQ_ENTRY NAME" | |
201 | .\" | |
202 | .Sh DESCRIPTION | |
203 | These macros define and operate on four types of data structures: | |
204 | singly-linked lists, singly-linked tail queues, lists, and tail queues. | |
205 | All four structures support the following functionality: | |
206 | .Bl -enum -compact -offset indent | |
207 | .It | |
fea681da | 208 | Insertion of a new entry at the head of the list. |
c0f21a05 | 209 | .It |
fea681da | 210 | Insertion of a new entry after any element in the list. |
c0f21a05 MK |
211 | .It |
212 | O(1) removal of an entry from the head of the list. | |
213 | .It | |
fea681da | 214 | Forward traversal through the list. |
c0f21a05 MK |
215 | .It |
216 | Swapping the contents of two lists. | |
217 | .El | |
218 | .Pp | |
219 | Singly-linked lists are the simplest of the four data structures | |
220 | and support only the above functionality. | |
221 | Singly-linked lists are ideal for applications with large datasets | |
222 | and few or no removals, | |
223 | or for implementing a LIFO queue. | |
224 | Singly-linked lists add the following functionality: | |
225 | .Bl -enum -compact -offset indent | |
226 | .It | |
227 | O(n) removal of any entry in the list. | |
228 | .El | |
229 | .Pp | |
230 | Singly-linked tail queues add the following functionality: | |
231 | .Bl -enum -compact -offset indent | |
232 | .It | |
fea681da | 233 | Entries can be added at the end of a list. |
c0f21a05 MK |
234 | .It |
235 | O(n) removal of any entry in the list. | |
236 | .It | |
237 | They may be concatenated. | |
238 | .El | |
fea681da | 239 | However: |
c0f21a05 MK |
240 | .Bl -enum -compact -offset indent |
241 | .It | |
242 | All list insertions must specify the head of the list. | |
243 | .It | |
fea681da | 244 | Each head entry requires two pointers rather than one. |
c0f21a05 | 245 | .It |
fea681da | 246 | Code size is about 15% greater and operations run about 20% slower |
c0f21a05 MK |
247 | than singly-linked lists. |
248 | .El | |
249 | .Pp | |
250 | Singly-linked tail queues are ideal for applications with large datasets and | |
251 | few or no removals, | |
252 | or for implementing a FIFO queue. | |
253 | .Pp | |
254 | All doubly linked types of data structures (lists and tail queues) | |
255 | additionally allow: | |
256 | .Bl -enum -compact -offset indent | |
257 | .It | |
258 | Insertion of a new entry before any element in the list. | |
259 | .It | |
260 | O(1) removal of any entry in the list. | |
261 | .El | |
262 | However: | |
263 | .Bl -enum -compact -offset indent | |
264 | .It | |
265 | Each element requires two pointers rather than one. | |
266 | .It | |
267 | Code size and execution time of operations (except for removal) is about | |
268 | twice that of the singly-linked data-structures. | |
269 | .El | |
270 | .Pp | |
271 | Linked lists are the simplest of the doubly linked data structures. | |
272 | They add the following functionality over the above: | |
273 | .Bl -enum -compact -offset indent | |
274 | .It | |
275 | They may be traversed backwards. | |
276 | .El | |
277 | However: | |
278 | .Bl -enum -compact -offset indent | |
279 | .It | |
280 | To traverse backwards, an entry to begin the traversal and the list in | |
281 | which it is contained must be specified. | |
282 | .El | |
283 | .Pp | |
284 | Tail queues add the following functionality: | |
285 | .Bl -enum -compact -offset indent | |
286 | .It | |
fea681da | 287 | Entries can be added at the end of a list. |
c0f21a05 MK |
288 | .It |
289 | They may be traversed backwards, from tail to head. | |
290 | .It | |
291 | They may be concatenated. | |
292 | .El | |
fea681da | 293 | However: |
c0f21a05 MK |
294 | .Bl -enum -compact -offset indent |
295 | .It | |
fea681da | 296 | All list insertions and removals must specify the head of the list. |
c0f21a05 | 297 | .It |
fea681da | 298 | Each head entry requires two pointers rather than one. |
c0f21a05 MK |
299 | .It |
300 | Code size is about 15% greater and operations run about 20% slower | |
301 | than singly-linked lists. | |
302 | .El | |
303 | .Pp | |
fea681da | 304 | In the macro definitions, |
c0f21a05 MK |
305 | .Fa TYPE |
306 | is the name of a user defined structure, | |
fea681da | 307 | that must contain a field of type |
c0f21a05 MK |
308 | .Li SLIST_ENTRY , |
309 | .Li STAILQ_ENTRY , | |
310 | .Li LIST_ENTRY , | |
fea681da | 311 | or |
c0f21a05 | 312 | .Li TAILQ_ENTRY , |
fea681da | 313 | named |
c0f21a05 | 314 | .Fa NAME . |
fea681da | 315 | The argument |
c0f21a05 MK |
316 | .Fa HEADNAME |
317 | is the name of a user defined structure that must be declared | |
fea681da | 318 | using the macros |
c0f21a05 MK |
319 | .Li SLIST_HEAD , |
320 | .Li STAILQ_HEAD , | |
321 | .Li LIST_HEAD , | |
fea681da | 322 | or |
c0f21a05 | 323 | .Li TAILQ_HEAD . |
fea681da MK |
324 | See the examples below for further explanation of how these |
325 | macros are used. | |
d20b994c | 326 | .Ss Singly-linked lists |
c0f21a05 MK |
327 | A singly-linked list is headed by a structure defined by the |
328 | .Nm SLIST_HEAD | |
1df22133 | 329 | macro. |
fea681da MK |
330 | This structure contains a single pointer to the first element |
331 | on the list. | |
c0f21a05 MK |
332 | The elements are singly linked for minimum space and pointer manipulation |
333 | overhead at the expense of O(n) removal for arbitrary elements. | |
fea681da MK |
334 | New elements can be added to the list after an existing element or |
335 | at the head of the list. | |
c0f21a05 MK |
336 | An |
337 | .Fa SLIST_HEAD | |
fea681da | 338 | structure is declared as follows: |
c0f21a05 MK |
339 | .Bd -literal -offset indent |
340 | SLIST_HEAD(HEADNAME, TYPE) head; | |
341 | .Ed | |
342 | .Pp | |
fea681da | 343 | where |
c0f21a05 | 344 | .Fa HEADNAME |
fea681da | 345 | is the name of the structure to be defined, and |
c0f21a05 | 346 | .Fa TYPE |
fea681da MK |
347 | is the type of the elements to be linked into the list. |
348 | A pointer to the head of the list can later be declared as: | |
c0f21a05 | 349 | .Bd -literal -offset indent |
fea681da | 350 | struct HEADNAME *headp; |
c0f21a05 MK |
351 | .Ed |
352 | .Pp | |
fea681da | 353 | (The names |
c0f21a05 | 354 | .Li head |
fea681da | 355 | and |
c0f21a05 | 356 | .Li headp |
fea681da | 357 | are user selectable.) |
c0f21a05 MK |
358 | .Pp |
359 | The macro | |
360 | .Nm SLIST_HEAD_INITIALIZER | |
361 | evaluates to an initializer for the list | |
362 | .Fa head . | |
363 | .Pp | |
364 | The macro | |
365 | .Nm SLIST_EMPTY | |
366 | evaluates to true if there are no elements in the list. | |
367 | .Pp | |
fea681da | 368 | The macro |
c0f21a05 | 369 | .Nm SLIST_ENTRY |
fea681da MK |
370 | declares a structure that connects the elements in |
371 | the list. | |
c0f21a05 MK |
372 | .Pp |
373 | The macro | |
374 | .Nm SLIST_FIRST | |
375 | returns the first element in the list or NULL if the list is empty. | |
376 | .Pp | |
377 | The macro | |
378 | .Nm SLIST_FOREACH | |
379 | traverses the list referenced by | |
380 | .Fa head | |
381 | in the forward direction, assigning each element in | |
382 | turn to | |
383 | .Fa var . | |
6559169c MK |
384 | .\" .Pp |
385 | .\" The macro | |
386 | .\" .Nm SLIST_FOREACH_FROM | |
387 | .\" behaves identically to | |
388 | .\" .Nm SLIST_FOREACH | |
389 | .\" when | |
390 | .\" .Fa var | |
391 | .\" is NULL, else it treats | |
392 | .\" .Fa var | |
393 | .\" as a previously found SLIST element and begins the loop at | |
394 | .\" .Fa var | |
395 | .\" instead of the first element in the SLIST referenced by | |
396 | .\" .Fa head . | |
397 | .\" .Pp | |
398 | .\" The macro | |
399 | .\" .Nm SLIST_FOREACH_SAFE | |
400 | .\" traverses the list referenced by | |
401 | .\" .Fa head | |
402 | .\" in the forward direction, assigning each element in | |
403 | .\" turn to | |
404 | .\" .Fa var . | |
405 | .\" However, unlike | |
406 | .\" .Fn SLIST_FOREACH | |
407 | .\" here it is permitted to both remove | |
408 | .\" .Fa var | |
409 | .\" as well as free it from within the loop safely without interfering with the | |
410 | .\" traversal. | |
411 | .\" .Pp | |
412 | .\" The macro | |
413 | .\" .Nm SLIST_FOREACH_FROM_SAFE | |
414 | .\" behaves identically to | |
415 | .\" .Nm SLIST_FOREACH_SAFE | |
416 | .\" when | |
417 | .\" .Fa var | |
418 | .\" is NULL, else it treats | |
419 | .\" .Fa var | |
420 | .\" as a previously found SLIST element and begins the loop at | |
421 | .\" .Fa var | |
422 | .\" instead of the first element in the SLIST referenced by | |
423 | .\" .Fa head . | |
c0f21a05 MK |
424 | .Pp |
425 | The macro | |
426 | .Nm SLIST_INIT | |
fea681da | 427 | initializes the list referenced by |
c0f21a05 MK |
428 | .Fa head . |
429 | .Pp | |
fea681da | 430 | The macro |
c0f21a05 | 431 | .Nm SLIST_INSERT_HEAD |
fea681da | 432 | inserts the new element |
c0f21a05 | 433 | .Fa elm |
fea681da | 434 | at the head of the list. |
c0f21a05 | 435 | .Pp |
fea681da | 436 | The macro |
c0f21a05 | 437 | .Nm SLIST_INSERT_AFTER |
fea681da | 438 | inserts the new element |
c0f21a05 | 439 | .Fa elm |
fea681da | 440 | after the element |
c0f21a05 MK |
441 | .Fa listelm . |
442 | .Pp | |
443 | The macro | |
444 | .Nm SLIST_NEXT | |
445 | returns the next element in the list. | |
6559169c MK |
446 | .\" .Pp |
447 | .\" The macro | |
448 | .\" .Nm SLIST_REMOVE_AFTER | |
449 | .\" removes the element after | |
450 | .\" .Fa elm | |
451 | .\" from the list. | |
452 | .\" Unlike | |
453 | .\" .Fa SLIST_REMOVE , | |
454 | .\" this macro does not traverse the entire list. | |
c0f21a05 | 455 | .Pp |
fea681da | 456 | The macro |
c0f21a05 | 457 | .Nm SLIST_REMOVE_HEAD |
fea681da | 458 | removes the element |
c0f21a05 MK |
459 | .Fa elm |
460 | from the head of the list. | |
461 | For optimum efficiency, | |
462 | elements being removed from the head of the list should explicitly use | |
463 | this macro instead of the generic | |
464 | .Fa SLIST_REMOVE | |
465 | macro. | |
466 | .Pp | |
467 | The macro | |
468 | .Nm SLIST_REMOVE | |
469 | removes the element | |
470 | .Fa elm | |
fea681da | 471 | from the list. |
6559169c MK |
472 | .\" .Pp |
473 | .\" The macro | |
474 | .\" .Nm SLIST_SWAP | |
475 | .\" swaps the contents of | |
476 | .\" .Fa head1 | |
477 | .\" and | |
478 | .\" .Fa head2 . | |
d20b994c | 479 | .Ss Singly-linked list example |
c0f21a05 MK |
480 | .Bd -literal |
481 | SLIST_HEAD(slisthead, entry) head = | |
482 | SLIST_HEAD_INITIALIZER(head); | |
483 | struct slisthead *headp; /* Singly-linked List head. */ | |
fea681da | 484 | struct entry { |
c0f21a05 MK |
485 | ... |
486 | SLIST_ENTRY(entry) entries; /* Singly-linked List. */ | |
487 | ... | |
488 | } *n1, *n2, *n3, *np; | |
fea681da | 489 | |
c0f21a05 | 490 | SLIST_INIT(&head); /* Initialize the list. */ |
fea681da | 491 | |
c0f21a05 MK |
492 | n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ |
493 | SLIST_INSERT_HEAD(&head, n1, entries); | |
fea681da | 494 | |
c0f21a05 MK |
495 | n2 = malloc(sizeof(struct entry)); /* Insert after. */ |
496 | SLIST_INSERT_AFTER(n1, n2, entries); | |
fea681da | 497 | |
c0f21a05 MK |
498 | SLIST_REMOVE(&head, n2, entry, entries);/* Deletion. */ |
499 | free(n2); | |
500 | ||
501 | n3 = SLIST_FIRST(&head); | |
502 | SLIST_REMOVE_HEAD(&head, entries); /* Deletion from the head. */ | |
503 | free(n3); | |
504 | /* Forward traversal. */ | |
505 | SLIST_FOREACH(np, &head, entries) | |
43e48f9e | 506 | np\-> ... |
6559169c MK |
507 | .\" /* Safe forward traversal. */ |
508 | .\"SLIST_FOREACH_SAFE(np, &head, entries, np_temp) { | |
43e48f9e | 509 | .\" np\->do_stuff(); |
6559169c MK |
510 | .\" ... |
511 | .\" SLIST_REMOVE(&head, np, entry, entries); | |
512 | .\" free(np); | |
513 | .\"} | |
c0f21a05 MK |
514 | |
515 | while (!SLIST_EMPTY(&head)) { /* List Deletion. */ | |
516 | n1 = SLIST_FIRST(&head); | |
517 | SLIST_REMOVE_HEAD(&head, entries); | |
518 | free(n1); | |
519 | } | |
520 | .Ed | |
d20b994c | 521 | .Ss Singly-linked tail queues |
c0f21a05 MK |
522 | A singly-linked tail queue is headed by a structure defined by the |
523 | .Nm STAILQ_HEAD | |
415aed52 | 524 | macro. |
fea681da MK |
525 | This structure contains a pair of pointers, |
526 | one to the first element in the tail queue and the other to | |
527 | the last element in the tail queue. | |
c0f21a05 MK |
528 | The elements are singly linked for minimum space and pointer |
529 | manipulation overhead at the expense of O(n) removal for arbitrary | |
530 | elements. | |
fea681da MK |
531 | New elements can be added to the tail queue after an existing element, |
532 | at the head of the tail queue, or at the end of the tail queue. | |
533 | A | |
c0f21a05 | 534 | .Fa STAILQ_HEAD |
fea681da | 535 | structure is declared as follows: |
c0f21a05 MK |
536 | .Bd -literal -offset indent |
537 | STAILQ_HEAD(HEADNAME, TYPE) head; | |
538 | .Ed | |
539 | .Pp | |
fea681da | 540 | where |
c0f21a05 | 541 | .Li HEADNAME |
fea681da | 542 | is the name of the structure to be defined, and |
c0f21a05 | 543 | .Li TYPE |
fea681da MK |
544 | is the type of the elements to be linked into the tail queue. |
545 | A pointer to the head of the tail queue can later be declared as: | |
c0f21a05 | 546 | .Bd -literal -offset indent |
fea681da | 547 | struct HEADNAME *headp; |
c0f21a05 MK |
548 | .Ed |
549 | .Pp | |
fea681da | 550 | (The names |
c0f21a05 | 551 | .Li head |
fea681da | 552 | and |
c0f21a05 | 553 | .Li headp |
fea681da | 554 | are user selectable.) |
c0f21a05 MK |
555 | .Pp |
556 | The macro | |
557 | .Nm STAILQ_HEAD_INITIALIZER | |
558 | evaluates to an initializer for the tail queue | |
559 | .Fa head . | |
560 | .Pp | |
561 | The macro | |
562 | .Nm STAILQ_CONCAT | |
563 | concatenates the tail queue headed by | |
564 | .Fa head2 | |
565 | onto the end of the one headed by | |
566 | .Fa head1 | |
567 | removing all entries from the former. | |
568 | .Pp | |
fea681da | 569 | The macro |
c0f21a05 MK |
570 | .Nm STAILQ_EMPTY |
571 | evaluates to true if there are no items on the tail queue. | |
572 | .Pp | |
573 | The macro | |
574 | .Nm STAILQ_ENTRY | |
fea681da MK |
575 | declares a structure that connects the elements in |
576 | the tail queue. | |
c0f21a05 MK |
577 | .Pp |
578 | The macro | |
579 | .Nm STAILQ_FIRST | |
580 | returns the first item on the tail queue or NULL if the tail queue | |
581 | is empty. | |
582 | .Pp | |
fea681da | 583 | The macro |
c0f21a05 MK |
584 | .Nm STAILQ_FOREACH |
585 | traverses the tail queue referenced by | |
586 | .Fa head | |
587 | in the forward direction, assigning each element | |
588 | in turn to | |
589 | .Fa var . | |
6559169c MK |
590 | .\" .Pp |
591 | .\" The macro | |
592 | .\" .Nm STAILQ_FOREACH_FROM | |
593 | .\" behaves identically to | |
594 | .\" .Nm STAILQ_FOREACH | |
595 | .\" when | |
596 | .\" .Fa var | |
597 | .\" is NULL, else it treats | |
598 | .\" .Fa var | |
599 | .\" as a previously found STAILQ element and begins the loop at | |
600 | .\" .Fa var | |
601 | .\" instead of the first element in the STAILQ referenced by | |
602 | .\" .Fa head . | |
603 | .\" .Pp | |
604 | .\" The macro | |
605 | .\" .Nm STAILQ_FOREACH_SAFE | |
606 | .\" traverses the tail queue referenced by | |
607 | .\" .Fa head | |
608 | .\" in the forward direction, assigning each element | |
609 | .\" in turn to | |
610 | .\" .Fa var . | |
611 | .\" However, unlike | |
612 | .\" .Fn STAILQ_FOREACH | |
613 | .\" here it is permitted to both remove | |
614 | .\" .Fa var | |
615 | .\" as well as free it from within the loop safely without interfering with the | |
616 | .\" traversal. | |
617 | .\" .Pp | |
618 | .\" The macro | |
619 | .\" .Nm STAILQ_FOREACH_FROM_SAFE | |
620 | .\" behaves identically to | |
621 | .\" .Nm STAILQ_FOREACH_SAFE | |
622 | .\" when | |
623 | .\" .Fa var | |
624 | .\" is NULL, else it treats | |
625 | .\" .Fa var | |
626 | .\" as a previously found STAILQ element and begins the loop at | |
627 | .\" .Fa var | |
628 | .\" instead of the first element in the STAILQ referenced by | |
629 | .\" .Fa head . | |
c0f21a05 MK |
630 | .Pp |
631 | The macro | |
632 | .Nm STAILQ_INIT | |
fea681da | 633 | initializes the tail queue referenced by |
c0f21a05 MK |
634 | .Fa head . |
635 | .Pp | |
fea681da | 636 | The macro |
c0f21a05 | 637 | .Nm STAILQ_INSERT_HEAD |
fea681da | 638 | inserts the new element |
c0f21a05 | 639 | .Fa elm |
fea681da | 640 | at the head of the tail queue. |
c0f21a05 | 641 | .Pp |
fea681da | 642 | The macro |
c0f21a05 | 643 | .Nm STAILQ_INSERT_TAIL |
fea681da | 644 | inserts the new element |
c0f21a05 | 645 | .Fa elm |
fea681da | 646 | at the end of the tail queue. |
c0f21a05 | 647 | .Pp |
fea681da | 648 | The macro |
c0f21a05 | 649 | .Nm STAILQ_INSERT_AFTER |
fea681da | 650 | inserts the new element |
c0f21a05 | 651 | .Fa elm |
fea681da | 652 | after the element |
c0f21a05 | 653 | .Fa listelm . |
6559169c MK |
654 | .\" .Pp |
655 | .\" The macro | |
656 | .\" .Nm STAILQ_LAST | |
657 | .\" returns the last item on the tail queue. | |
658 | .\" If the tail queue is empty the return value is | |
659 | .\" .Dv NULL . | |
c0f21a05 MK |
660 | .Pp |
661 | The macro | |
662 | .Nm STAILQ_NEXT | |
663 | returns the next item on the tail queue, or NULL this item is the last. | |
6559169c MK |
664 | .\" .Pp |
665 | .\" The macro | |
666 | .\" .Nm STAILQ_REMOVE_AFTER | |
667 | .\" removes the element after | |
668 | .\" .Fa elm | |
669 | .\" from the tail queue. | |
670 | .\" Unlike | |
671 | .\" .Fa STAILQ_REMOVE , | |
672 | .\" this macro does not traverse the entire tail queue. | |
c0f21a05 MK |
673 | .Pp |
674 | The macro | |
675 | .Nm STAILQ_REMOVE_HEAD | |
676 | removes the element at the head of the tail queue. | |
677 | For optimum efficiency, | |
678 | elements being removed from the head of the tail queue should | |
679 | use this macro explicitly rather than the generic | |
680 | .Fa STAILQ_REMOVE | |
681 | macro. | |
682 | .Pp | |
fea681da | 683 | The macro |
c0f21a05 | 684 | .Nm STAILQ_REMOVE |
fea681da | 685 | removes the element |
c0f21a05 | 686 | .Fa elm |
fea681da | 687 | from the tail queue. |
6559169c MK |
688 | .\" .Pp |
689 | .\" The macro | |
690 | .\" .Nm STAILQ_SWAP | |
691 | .\" swaps the contents of | |
692 | .\" .Fa head1 | |
693 | .\" and | |
694 | .\" .Fa head2 . | |
d20b994c | 695 | .Ss Singly-linked tail queue example |
c0f21a05 MK |
696 | .Bd -literal |
697 | STAILQ_HEAD(stailhead, entry) head = | |
698 | STAILQ_HEAD_INITIALIZER(head); | |
699 | struct stailhead *headp; /* Singly-linked tail queue head. */ | |
fea681da | 700 | struct entry { |
c0f21a05 MK |
701 | ... |
702 | STAILQ_ENTRY(entry) entries; /* Tail queue. */ | |
703 | ... | |
704 | } *n1, *n2, *n3, *np; | |
fea681da | 705 | |
c0f21a05 | 706 | STAILQ_INIT(&head); /* Initialize the queue. */ |
fea681da | 707 | |
c0f21a05 MK |
708 | n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ |
709 | STAILQ_INSERT_HEAD(&head, n1, entries); | |
fea681da | 710 | |
c0f21a05 MK |
711 | n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ |
712 | STAILQ_INSERT_TAIL(&head, n1, entries); | |
fea681da | 713 | |
c0f21a05 MK |
714 | n2 = malloc(sizeof(struct entry)); /* Insert after. */ |
715 | STAILQ_INSERT_AFTER(&head, n1, n2, entries); | |
716 | /* Deletion. */ | |
717 | STAILQ_REMOVE(&head, n2, entry, entries); | |
718 | free(n2); | |
719 | /* Deletion from the head. */ | |
720 | n3 = STAILQ_FIRST(&head); | |
721 | STAILQ_REMOVE_HEAD(&head, entries); | |
722 | free(n3); | |
723 | /* Forward traversal. */ | |
724 | STAILQ_FOREACH(np, &head, entries) | |
43e48f9e | 725 | np\-> ... |
6559169c MK |
726 | .\" /* Safe forward traversal. */ |
727 | .\"STAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { | |
43e48f9e | 728 | .\" np\->do_stuff(); |
6559169c MK |
729 | .\" ... |
730 | .\" STAILQ_REMOVE(&head, np, entry, entries); | |
731 | .\" free(np); | |
732 | .\"} | |
c0f21a05 MK |
733 | /* TailQ Deletion. */ |
734 | while (!STAILQ_EMPTY(&head)) { | |
735 | n1 = STAILQ_FIRST(&head); | |
736 | STAILQ_REMOVE_HEAD(&head, entries); | |
737 | free(n1); | |
738 | } | |
739 | /* Faster TailQ Deletion. */ | |
740 | n1 = STAILQ_FIRST(&head); | |
741 | while (n1 != NULL) { | |
742 | n2 = STAILQ_NEXT(n1, entries); | |
743 | free(n1); | |
744 | n1 = n2; | |
745 | } | |
746 | STAILQ_INIT(&head); | |
747 | .Ed | |
d20b994c | 748 | .Ss Lists |
c0f21a05 MK |
749 | A list is headed by a structure defined by the |
750 | .Nm LIST_HEAD | |
415aed52 | 751 | macro. |
c0f21a05 MK |
752 | This structure contains a single pointer to the first element |
753 | on the list. | |
fea681da | 754 | The elements are doubly linked so that an arbitrary element can be |
c0f21a05 MK |
755 | removed without traversing the list. |
756 | New elements can be added to the list after an existing element, | |
757 | before an existing element, or at the head of the list. | |
fea681da | 758 | A |
c0f21a05 | 759 | .Fa LIST_HEAD |
fea681da | 760 | structure is declared as follows: |
c0f21a05 MK |
761 | .Bd -literal -offset indent |
762 | LIST_HEAD(HEADNAME, TYPE) head; | |
763 | .Ed | |
764 | .Pp | |
fea681da | 765 | where |
c0f21a05 | 766 | .Fa HEADNAME |
fea681da | 767 | is the name of the structure to be defined, and |
c0f21a05 MK |
768 | .Fa TYPE |
769 | is the type of the elements to be linked into the list. | |
770 | A pointer to the head of the list can later be declared as: | |
771 | .Bd -literal -offset indent | |
772 | struct HEADNAME *headp; | |
773 | .Ed | |
774 | .Pp | |
775 | (The names | |
776 | .Li head | |
777 | and | |
778 | .Li headp | |
779 | are user selectable.) | |
780 | .Pp | |
781 | The macro | |
782 | .Nm LIST_HEAD_INITIALIZER | |
783 | evaluates to an initializer for the list | |
784 | .Fa head . | |
785 | .Pp | |
786 | The macro | |
787 | .Nm LIST_EMPTY | |
788 | evaluates to true if there are no elements in the list. | |
789 | .Pp | |
790 | The macro | |
791 | .Nm LIST_ENTRY | |
792 | declares a structure that connects the elements in | |
793 | the list. | |
794 | .Pp | |
795 | The macro | |
796 | .Nm LIST_FIRST | |
797 | returns the first element in the list or NULL if the list | |
798 | is empty. | |
799 | .Pp | |
800 | The macro | |
801 | .Nm LIST_FOREACH | |
802 | traverses the list referenced by | |
803 | .Fa head | |
804 | in the forward direction, assigning each element in turn to | |
805 | .Fa var . | |
6559169c MK |
806 | .\" .Pp |
807 | .\" The macro | |
808 | .\" .Nm LIST_FOREACH_FROM | |
809 | .\" behaves identically to | |
810 | .\" .Nm LIST_FOREACH | |
811 | .\" when | |
812 | .\" .Fa var | |
813 | .\" is NULL, else it treats | |
814 | .\" .Fa var | |
815 | .\" as a previously found LIST element and begins the loop at | |
816 | .\" .Fa var | |
817 | .\" instead of the first element in the LIST referenced by | |
818 | .\" .Fa head . | |
819 | .\" .Pp | |
820 | .\" The macro | |
821 | .\" .Nm LIST_FOREACH_SAFE | |
822 | .\" traverses the list referenced by | |
823 | .\" .Fa head | |
824 | .\" in the forward direction, assigning each element in turn to | |
825 | .\" .Fa var . | |
826 | .\" However, unlike | |
827 | .\" .Fn LIST_FOREACH | |
828 | .\" here it is permitted to both remove | |
829 | .\" .Fa var | |
830 | .\" as well as free it from within the loop safely without interfering with the | |
831 | .\" traversal. | |
832 | .\" .Pp | |
833 | .\" The macro | |
834 | .\" .Nm LIST_FOREACH_FROM_SAFE | |
835 | .\" behaves identically to | |
836 | .\" .Nm LIST_FOREACH_SAFE | |
837 | .\" when | |
838 | .\" .Fa var | |
839 | .\" is NULL, else it treats | |
840 | .\" .Fa var | |
841 | .\" as a previously found LIST element and begins the loop at | |
842 | .\" .Fa var | |
843 | .\" instead of the first element in the LIST referenced by | |
844 | .\" .Fa head . | |
c0f21a05 MK |
845 | .Pp |
846 | The macro | |
847 | .Nm LIST_INIT | |
848 | initializes the list referenced by | |
849 | .Fa head . | |
850 | .Pp | |
851 | The macro | |
852 | .Nm LIST_INSERT_HEAD | |
853 | inserts the new element | |
854 | .Fa elm | |
855 | at the head of the list. | |
856 | .Pp | |
857 | The macro | |
858 | .Nm LIST_INSERT_AFTER | |
859 | inserts the new element | |
860 | .Fa elm | |
861 | after the element | |
862 | .Fa listelm . | |
863 | .Pp | |
864 | The macro | |
865 | .Nm LIST_INSERT_BEFORE | |
866 | inserts the new element | |
867 | .Fa elm | |
868 | before the element | |
869 | .Fa listelm . | |
870 | .Pp | |
871 | The macro | |
872 | .Nm LIST_NEXT | |
873 | returns the next element in the list, or NULL if this is the last. | |
6559169c MK |
874 | .\" .Pp |
875 | .\" The macro | |
876 | .\" .Nm LIST_PREV | |
877 | .\" returns the previous element in the list, or NULL if this is the first. | |
878 | .\" List | |
879 | .\" .Fa head | |
880 | .\" must contain element | |
881 | .\" .Fa elm . | |
c0f21a05 MK |
882 | .Pp |
883 | The macro | |
884 | .Nm LIST_REMOVE | |
885 | removes the element | |
886 | .Fa elm | |
887 | from the list. | |
6559169c MK |
888 | .\" .Pp |
889 | .\" The macro | |
890 | .\" .Nm LIST_SWAP | |
891 | .\" swaps the contents of | |
892 | .\" .Fa head1 | |
893 | .\" and | |
894 | .\" .Fa head2 . | |
d20b994c | 895 | .Ss List example |
c0f21a05 MK |
896 | .Bd -literal |
897 | LIST_HEAD(listhead, entry) head = | |
898 | LIST_HEAD_INITIALIZER(head); | |
899 | struct listhead *headp; /* List head. */ | |
900 | struct entry { | |
901 | ... | |
902 | LIST_ENTRY(entry) entries; /* List. */ | |
903 | ... | |
904 | } *n1, *n2, *n3, *np, *np_temp; | |
3233d665 | 905 | |
c0f21a05 MK |
906 | LIST_INIT(&head); /* Initialize the list. */ |
907 | ||
908 | n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ | |
909 | LIST_INSERT_HEAD(&head, n1, entries); | |
910 | ||
911 | n2 = malloc(sizeof(struct entry)); /* Insert after. */ | |
912 | LIST_INSERT_AFTER(n1, n2, entries); | |
913 | ||
914 | n3 = malloc(sizeof(struct entry)); /* Insert before. */ | |
915 | LIST_INSERT_BEFORE(n2, n3, entries); | |
916 | ||
917 | LIST_REMOVE(n2, entries); /* Deletion. */ | |
918 | free(n2); | |
919 | /* Forward traversal. */ | |
920 | LIST_FOREACH(np, &head, entries) | |
43e48f9e | 921 | np\-> ... |
c0f21a05 | 922 | |
6559169c MK |
923 | .\" /* Safe forward traversal. */ |
924 | .\" LIST_FOREACH_SAFE(np, &head, entries, np_temp) { | |
43e48f9e | 925 | .\" np\->do_stuff(); |
6559169c MK |
926 | .\" ... |
927 | .\" LIST_REMOVE(np, entries); | |
928 | .\" free(np); | |
929 | .\" } | |
8cc4d071 | 930 | .\" |
c0f21a05 MK |
931 | while (!LIST_EMPTY(&head)) { /* List Deletion. */ |
932 | n1 = LIST_FIRST(&head); | |
933 | LIST_REMOVE(n1, entries); | |
934 | free(n1); | |
935 | } | |
936 | ||
937 | n1 = LIST_FIRST(&head); /* Faster List Deletion. */ | |
938 | while (n1 != NULL) { | |
939 | n2 = LIST_NEXT(n1, entries); | |
940 | free(n1); | |
941 | n1 = n2; | |
942 | } | |
943 | LIST_INIT(&head); | |
944 | .Ed | |
d20b994c | 945 | .Ss Tail queues |
c0f21a05 MK |
946 | A tail queue is headed by a structure defined by the |
947 | .Nm TAILQ_HEAD | |
948 | macro. | |
949 | This structure contains a pair of pointers, | |
950 | one to the first element in the tail queue and the other to | |
951 | the last element in the tail queue. | |
952 | The elements are doubly linked so that an arbitrary element can be | |
953 | removed without traversing the tail queue. | |
954 | New elements can be added to the tail queue after an existing element, | |
955 | before an existing element, at the head of the tail queue, | |
956 | or at the end of the tail queue. | |
957 | A | |
958 | .Fa TAILQ_HEAD | |
959 | structure is declared as follows: | |
960 | .Bd -literal -offset indent | |
961 | TAILQ_HEAD(HEADNAME, TYPE) head; | |
962 | .Ed | |
963 | .Pp | |
964 | where | |
965 | .Li HEADNAME | |
966 | is the name of the structure to be defined, and | |
967 | .Li TYPE | |
968 | is the type of the elements to be linked into the tail queue. | |
969 | A pointer to the head of the tail queue can later be declared as: | |
970 | .Bd -literal -offset indent | |
fea681da | 971 | struct HEADNAME *headp; |
c0f21a05 MK |
972 | .Ed |
973 | .Pp | |
fea681da | 974 | (The names |
c0f21a05 | 975 | .Li head |
fea681da | 976 | and |
c0f21a05 | 977 | .Li headp |
fea681da | 978 | are user selectable.) |
c0f21a05 MK |
979 | .Pp |
980 | The macro | |
981 | .Nm TAILQ_HEAD_INITIALIZER | |
982 | evaluates to an initializer for the tail queue | |
983 | .Fa head . | |
984 | .Pp | |
985 | The macro | |
986 | .Nm TAILQ_CONCAT | |
987 | concatenates the tail queue headed by | |
988 | .Fa head2 | |
989 | onto the end of the one headed by | |
990 | .Fa head1 | |
991 | removing all entries from the former. | |
992 | .Pp | |
fea681da | 993 | The macro |
c0f21a05 MK |
994 | .Nm TAILQ_EMPTY |
995 | evaluates to true if there are no items on the tail queue. | |
996 | .Pp | |
997 | The macro | |
998 | .Nm TAILQ_ENTRY | |
fea681da | 999 | declares a structure that connects the elements in |
c0f21a05 MK |
1000 | the tail queue. |
1001 | .Pp | |
1002 | The macro | |
1003 | .Nm TAILQ_FIRST | |
1004 | returns the first item on the tail queue or NULL if the tail queue | |
1005 | is empty. | |
1006 | .Pp | |
1007 | The macro | |
1008 | .Nm TAILQ_FOREACH | |
1009 | traverses the tail queue referenced by | |
1010 | .Fa head | |
1011 | in the forward direction, assigning each element in turn to | |
1012 | .Fa var . | |
1013 | .Fa var | |
1014 | is set to | |
1015 | .Dv NULL | |
1016 | if the loop completes normally, or if there were no elements. | |
6559169c MK |
1017 | .\" .Pp |
1018 | .\" The macro | |
1019 | .\" .Nm TAILQ_FOREACH_FROM | |
1020 | .\" behaves identically to | |
1021 | .\" .Nm TAILQ_FOREACH | |
1022 | .\" when | |
1023 | .\" .Fa var | |
1024 | .\" is NULL, else it treats | |
1025 | .\" .Fa var | |
1026 | .\" as a previously found TAILQ element and begins the loop at | |
1027 | .\" .Fa var | |
1028 | .\" instead of the first element in the TAILQ referenced by | |
1029 | .\" .Fa head . | |
c0f21a05 | 1030 | .Pp |
fea681da | 1031 | The macro |
c0f21a05 MK |
1032 | .Nm TAILQ_FOREACH_REVERSE |
1033 | traverses the tail queue referenced by | |
1034 | .Fa head | |
1035 | in the reverse direction, assigning each element in turn to | |
1036 | .Fa var . | |
6559169c MK |
1037 | .\" .Pp |
1038 | .\" The macro | |
1039 | .\" .Nm TAILQ_FOREACH_REVERSE_FROM | |
1040 | .\" behaves identically to | |
1041 | .\" .Nm TAILQ_FOREACH_REVERSE | |
1042 | .\" when | |
1043 | .\" .Fa var | |
1044 | .\" is NULL, else it treats | |
1045 | .\" .Fa var | |
1046 | .\" as a previously found TAILQ element and begins the reverse loop at | |
1047 | .\" .Fa var | |
1048 | .\" instead of the last element in the TAILQ referenced by | |
1049 | .\" .Fa head . | |
1050 | .\" .Pp | |
1051 | .\" The macros | |
1052 | .\" .Nm TAILQ_FOREACH_SAFE | |
1053 | .\" and | |
1054 | .\" .Nm TAILQ_FOREACH_REVERSE_SAFE | |
1055 | .\" traverse the list referenced by | |
1056 | .\" .Fa head | |
1057 | .\" in the forward or reverse direction respectively, | |
1058 | .\" assigning each element in turn to | |
1059 | .\" .Fa var . | |
1060 | .\" However, unlike their unsafe counterparts, | |
1061 | .\" .Nm TAILQ_FOREACH | |
1062 | .\" and | |
1063 | .\" .Nm TAILQ_FOREACH_REVERSE | |
1064 | .\" permit to both remove | |
1065 | .\" .Fa var | |
1066 | .\" as well as free it from within the loop safely without interfering with the | |
1067 | .\" traversal. | |
1068 | .\" .Pp | |
1069 | .\" The macro | |
1070 | .\" .Nm TAILQ_FOREACH_FROM_SAFE | |
1071 | .\" behaves identically to | |
1072 | .\" .Nm TAILQ_FOREACH_SAFE | |
1073 | .\" when | |
1074 | .\" .Fa var | |
1075 | .\" is NULL, else it treats | |
1076 | .\" .Fa var | |
1077 | .\" as a previously found TAILQ element and begins the loop at | |
1078 | .\" .Fa var | |
1079 | .\" instead of the first element in the TAILQ referenced by | |
1080 | .\" .Fa head . | |
1081 | .\" .Pp | |
1082 | .\" The macro | |
1083 | .\" .Nm TAILQ_FOREACH_REVERSE_FROM_SAFE | |
1084 | .\" behaves identically to | |
1085 | .\" .Nm TAILQ_FOREACH_REVERSE_SAFE | |
1086 | .\" when | |
1087 | .\" .Fa var | |
1088 | .\" is NULL, else it treats | |
1089 | .\" .Fa var | |
1090 | .\" as a previously found TAILQ element and begins the reverse loop at | |
1091 | .\" .Fa var | |
1092 | .\" instead of the last element in the TAILQ referenced by | |
1093 | .\" .Fa head . | |
c0f21a05 MK |
1094 | .Pp |
1095 | The macro | |
1096 | .Nm TAILQ_INIT | |
1097 | initializes the tail queue referenced by | |
1098 | .Fa head . | |
1099 | .Pp | |
1100 | The macro | |
1101 | .Nm TAILQ_INSERT_HEAD | |
fea681da | 1102 | inserts the new element |
c0f21a05 MK |
1103 | .Fa elm |
1104 | at the head of the tail queue. | |
1105 | .Pp | |
fea681da | 1106 | The macro |
c0f21a05 | 1107 | .Nm TAILQ_INSERT_TAIL |
fea681da | 1108 | inserts the new element |
c0f21a05 MK |
1109 | .Fa elm |
1110 | at the end of the tail queue. | |
1111 | .Pp | |
fea681da | 1112 | The macro |
c0f21a05 | 1113 | .Nm TAILQ_INSERT_AFTER |
fea681da | 1114 | inserts the new element |
c0f21a05 | 1115 | .Fa elm |
fea681da | 1116 | after the element |
c0f21a05 MK |
1117 | .Fa listelm . |
1118 | .Pp | |
fea681da | 1119 | The macro |
c0f21a05 | 1120 | .Nm TAILQ_INSERT_BEFORE |
fea681da | 1121 | inserts the new element |
c0f21a05 | 1122 | .Fa elm |
fea681da | 1123 | before the element |
c0f21a05 MK |
1124 | .Fa listelm . |
1125 | .Pp | |
1126 | The macro | |
1127 | .Nm TAILQ_LAST | |
1128 | returns the last item on the tail queue. | |
1129 | If the tail queue is empty the return value is | |
1130 | .Dv NULL . | |
1131 | .Pp | |
fea681da | 1132 | The macro |
c0f21a05 MK |
1133 | .Nm TAILQ_NEXT |
1134 | returns the next item on the tail queue, or NULL if this item is the last. | |
1135 | .Pp | |
1136 | The macro | |
1137 | .Nm TAILQ_PREV | |
1138 | returns the previous item on the tail queue, or NULL if this item | |
1139 | is the first. | |
1140 | .Pp | |
1141 | The macro | |
1142 | .Nm TAILQ_REMOVE | |
fea681da | 1143 | removes the element |
c0f21a05 MK |
1144 | .Fa elm |
1145 | from the tail queue. | |
1146 | .Pp | |
1147 | The macro | |
1148 | .Nm TAILQ_SWAP | |
1149 | swaps the contents of | |
1150 | .Fa head1 | |
1151 | and | |
1152 | .Fa head2 . | |
d20b994c | 1153 | .Ss Tail queue example |
c0f21a05 MK |
1154 | .Bd -literal |
1155 | TAILQ_HEAD(tailhead, entry) head = | |
1156 | TAILQ_HEAD_INITIALIZER(head); | |
1157 | struct tailhead *headp; /* Tail queue head. */ | |
fea681da | 1158 | struct entry { |
c0f21a05 MK |
1159 | ... |
1160 | TAILQ_ENTRY(entry) entries; /* Tail queue. */ | |
1161 | ... | |
1162 | } *n1, *n2, *n3, *np; | |
fea681da | 1163 | |
c0f21a05 | 1164 | TAILQ_INIT(&head); /* Initialize the queue. */ |
fea681da | 1165 | |
c0f21a05 MK |
1166 | n1 = malloc(sizeof(struct entry)); /* Insert at the head. */ |
1167 | TAILQ_INSERT_HEAD(&head, n1, entries); | |
1168 | ||
1169 | n1 = malloc(sizeof(struct entry)); /* Insert at the tail. */ | |
1170 | TAILQ_INSERT_TAIL(&head, n1, entries); | |
fea681da | 1171 | |
c0f21a05 MK |
1172 | n2 = malloc(sizeof(struct entry)); /* Insert after. */ |
1173 | TAILQ_INSERT_AFTER(&head, n1, n2, entries); | |
fea681da | 1174 | |
c0f21a05 MK |
1175 | n3 = malloc(sizeof(struct entry)); /* Insert before. */ |
1176 | TAILQ_INSERT_BEFORE(n2, n3, entries); | |
fea681da | 1177 | |
c0f21a05 MK |
1178 | TAILQ_REMOVE(&head, n2, entries); /* Deletion. */ |
1179 | free(n2); | |
1180 | /* Forward traversal. */ | |
1181 | TAILQ_FOREACH(np, &head, entries) | |
43e48f9e | 1182 | np\-> ... |
6559169c MK |
1183 | .\" /* Safe forward traversal. */ |
1184 | .\" TAILQ_FOREACH_SAFE(np, &head, entries, np_temp) { | |
43e48f9e | 1185 | .\" np\->do_stuff(); |
6559169c MK |
1186 | .\" ... |
1187 | .\" TAILQ_REMOVE(&head, np, entries); | |
1188 | .\" free(np); | |
1189 | .\" } | |
c0f21a05 MK |
1190 | /* Reverse traversal. */ |
1191 | TAILQ_FOREACH_REVERSE(np, &head, tailhead, entries) | |
43e48f9e | 1192 | np\-> ... |
c0f21a05 MK |
1193 | /* TailQ Deletion. */ |
1194 | while (!TAILQ_EMPTY(&head)) { | |
1195 | n1 = TAILQ_FIRST(&head); | |
1196 | TAILQ_REMOVE(&head, n1, entries); | |
1197 | free(n1); | |
1198 | } | |
1199 | /* Faster TailQ Deletion. */ | |
1200 | n1 = TAILQ_FIRST(&head); | |
1201 | while (n1 != NULL) { | |
1202 | n2 = TAILQ_NEXT(n1, entries); | |
1203 | free(n1); | |
1204 | n1 = n2; | |
1205 | } | |
041abbe3 | 1206 | |
c0f21a05 | 1207 | TAILQ_INIT(&head); |
041abbe3 MK |
1208 | n2 = malloc(sizeof(struct entry)); /* Insert before. */ |
1209 | CIRCLEQ_INSERT_BEFORE(&head, n1, n2, entries); | |
1210 | /* Forward traversal. */ | |
1211 | for (np = head.cqh_first; np != (void *)&head; | |
1212 | np = np\->entries.cqe_next) | |
1213 | np\-> ... | |
1214 | /* Reverse traversal. */ | |
1215 | for (np = head.cqh_last; np != (void *)&head; np = np\->entries.cqe_prev) | |
1216 | np\-> ... | |
1217 | /* Delete. */ | |
1218 | while (head.cqh_first != (void *)&head) | |
1219 | CIRCLEQ_REMOVE(&head, head.cqh_first, entries); | |
c0f21a05 | 1220 | .Ed |
9a8f3114 MK |
1221 | .Sh CONFORMING TO |
1222 | Not in POSIX.1-2001 or POSIX.1-2008. | |
041abbe3 MK |
1223 | .SH CONFORMING TO |
1224 | Not in POSIX.1. | |
9a8f3114 | 1225 | Present on the BSDs. |
c0f21a05 MK |
1226 | .Nm queue |
1227 | functions first appeared in | |
1228 | .Bx 4.4 . | |
041abbe3 MK |
1229 | .\" .Sh SEE ALSO |
1230 | .\" .Xr tree 3 |