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