OpenWrt – Blame information for rev 4
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
4 | office | 1 | /* |
2 | * Copyright (c) 1991, 1993 |
||
3 | * The Regents of the University of California. All rights reserved. |
||
4 | * |
||
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. |
||
13 | * 3. Neither the name of the University nor the names of its contributors |
||
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. |
||
28 | * |
||
29 | * @(#)queue.h 8.5 (Berkeley) 8/20/94 |
||
30 | */ |
||
31 | |||
32 | #ifndef _SYS_QUEUE_H_ |
||
33 | #define _SYS_QUEUE_H_ |
||
34 | |||
35 | /* |
||
36 | * This file defines five types of data structures: singly-linked lists, |
||
37 | * lists, simple queues, tail queues, and circular queues. |
||
38 | * |
||
39 | * A singly-linked list is headed by a single forward pointer. The |
||
40 | * elements are singly linked for minimum space and pointer manipulation |
||
41 | * overhead at the expense of O(n) removal for arbitrary elements. New |
||
42 | * elements can be added to the list after an existing element or at the |
||
43 | * head of the list. Elements being removed from the head of the list |
||
44 | * should use the explicit macro for this purpose for optimum |
||
45 | * efficiency. A singly-linked list may only be traversed in the forward |
||
46 | * direction. Singly-linked lists are ideal for applications with large |
||
47 | * datasets and few or no removals or for implementing a LIFO queue. |
||
48 | * |
||
49 | * A list is headed by a single forward pointer (or an array of forward |
||
50 | * pointers for a hash table header). The elements are doubly linked |
||
51 | * so that an arbitrary element can be removed without a need to |
||
52 | * traverse the list. New elements can be added to the list before |
||
53 | * or after an existing element or at the head of the list. A list |
||
54 | * may only be traversed in the forward direction. |
||
55 | * |
||
56 | * A simple queue is headed by a pair of pointers, one the head of the |
||
57 | * list and the other to the tail of the list. The elements are singly |
||
58 | * linked to save space, so elements can only be removed from the |
||
59 | * head of the list. New elements can be added to the list after |
||
60 | * an existing element, at the head of the list, or at the end of the |
||
61 | * list. A simple queue may only be traversed in the forward direction. |
||
62 | * |
||
63 | * A tail queue is headed by a pair of pointers, one to the head of the |
||
64 | * list and the other to the tail of the list. The elements are doubly |
||
65 | * linked so that an arbitrary element can be removed without a need to |
||
66 | * traverse the list. New elements can be added to the list before or |
||
67 | * after an existing element, at the head of the list, or at the end of |
||
68 | * the list. A tail queue may be traversed in either direction. |
||
69 | * |
||
70 | * A circle queue is headed by a pair of pointers, one to the head of the |
||
71 | * list and the other to the tail of the list. The elements are doubly |
||
72 | * linked so that an arbitrary element can be removed without a need to |
||
73 | * traverse the list. New elements can be added to the list before or after |
||
74 | * an existing element, at the head of the list, or at the end of the list. |
||
75 | * A circle queue may be traversed in either direction, but has a more |
||
76 | * complex end of list detection. |
||
77 | * |
||
78 | * For details on the use of these macros, see the queue(3) manual page. |
||
79 | */ |
||
80 | |||
81 | /* |
||
82 | * List definitions. |
||
83 | */ |
||
84 | #define LIST_HEAD(name, type) \ |
||
85 | struct name { \ |
||
86 | struct type *lh_first; /* first element */ \ |
||
87 | } |
||
88 | |||
89 | #define LIST_HEAD_INITIALIZER(head) \ |
||
90 | { NULL } |
||
91 | |||
92 | #define LIST_ENTRY(type) \ |
||
93 | struct { \ |
||
94 | struct type *le_next; /* next element */ \ |
||
95 | struct type **le_prev; /* address of previous next element */ \ |
||
96 | } |
||
97 | |||
98 | /* |
||
99 | * List functions. |
||
100 | */ |
||
101 | #define LIST_INIT(head) do { \ |
||
102 | (head)->lh_first = NULL; \ |
||
103 | } while (/*CONSTCOND*/0) |
||
104 | |||
105 | #define LIST_INSERT_AFTER(listelm, elm, field) do { \ |
||
106 | if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \ |
||
107 | (listelm)->field.le_next->field.le_prev = \ |
||
108 | &(elm)->field.le_next; \ |
||
109 | (listelm)->field.le_next = (elm); \ |
||
110 | (elm)->field.le_prev = &(listelm)->field.le_next; \ |
||
111 | } while (/*CONSTCOND*/0) |
||
112 | |||
113 | #define LIST_INSERT_BEFORE(listelm, elm, field) do { \ |
||
114 | (elm)->field.le_prev = (listelm)->field.le_prev; \ |
||
115 | (elm)->field.le_next = (listelm); \ |
||
116 | *(listelm)->field.le_prev = (elm); \ |
||
117 | (listelm)->field.le_prev = &(elm)->field.le_next; \ |
||
118 | } while (/*CONSTCOND*/0) |
||
119 | |||
120 | #define LIST_INSERT_HEAD(head, elm, field) do { \ |
||
121 | if (((elm)->field.le_next = (head)->lh_first) != NULL) \ |
||
122 | (head)->lh_first->field.le_prev = &(elm)->field.le_next;\ |
||
123 | (head)->lh_first = (elm); \ |
||
124 | (elm)->field.le_prev = &(head)->lh_first; \ |
||
125 | } while (/*CONSTCOND*/0) |
||
126 | |||
127 | #define LIST_REMOVE(elm, field) do { \ |
||
128 | if ((elm)->field.le_next != NULL) \ |
||
129 | (elm)->field.le_next->field.le_prev = \ |
||
130 | (elm)->field.le_prev; \ |
||
131 | *(elm)->field.le_prev = (elm)->field.le_next; \ |
||
132 | } while (/*CONSTCOND*/0) |
||
133 | |||
134 | #define LIST_FOREACH(var, head, field) \ |
||
135 | for ((var) = ((head)->lh_first); \ |
||
136 | (var); \ |
||
137 | (var) = ((var)->field.le_next)) |
||
138 | |||
139 | /* |
||
140 | * List access methods. |
||
141 | */ |
||
142 | #define LIST_EMPTY(head) ((head)->lh_first == NULL) |
||
143 | #define LIST_FIRST(head) ((head)->lh_first) |
||
144 | #define LIST_NEXT(elm, field) ((elm)->field.le_next) |
||
145 | |||
146 | |||
147 | /* |
||
148 | * Singly-linked List definitions. |
||
149 | */ |
||
150 | #define SLIST_HEAD(name, type) \ |
||
151 | struct name { \ |
||
152 | struct type *slh_first; /* first element */ \ |
||
153 | } |
||
154 | |||
155 | #define SLIST_HEAD_INITIALIZER(head) \ |
||
156 | { NULL } |
||
157 | |||
158 | #define SLIST_ENTRY(type) \ |
||
159 | struct { \ |
||
160 | struct type *sle_next; /* next element */ \ |
||
161 | } |
||
162 | |||
163 | /* |
||
164 | * Singly-linked List functions. |
||
165 | */ |
||
166 | #define SLIST_INIT(head) do { \ |
||
167 | (head)->slh_first = NULL; \ |
||
168 | } while (/*CONSTCOND*/0) |
||
169 | |||
170 | #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \ |
||
171 | (elm)->field.sle_next = (slistelm)->field.sle_next; \ |
||
172 | (slistelm)->field.sle_next = (elm); \ |
||
173 | } while (/*CONSTCOND*/0) |
||
174 | |||
175 | #define SLIST_INSERT_HEAD(head, elm, field) do { \ |
||
176 | (elm)->field.sle_next = (head)->slh_first; \ |
||
177 | (head)->slh_first = (elm); \ |
||
178 | } while (/*CONSTCOND*/0) |
||
179 | |||
180 | #define SLIST_REMOVE_HEAD(head, field) do { \ |
||
181 | (head)->slh_first = (head)->slh_first->field.sle_next; \ |
||
182 | } while (/*CONSTCOND*/0) |
||
183 | |||
184 | #define SLIST_REMOVE(head, elm, type, field) do { \ |
||
185 | if ((head)->slh_first == (elm)) { \ |
||
186 | SLIST_REMOVE_HEAD((head), field); \ |
||
187 | } \ |
||
188 | else { \ |
||
189 | struct type *curelm = (head)->slh_first; \ |
||
190 | while(curelm->field.sle_next != (elm)) \ |
||
191 | curelm = curelm->field.sle_next; \ |
||
192 | curelm->field.sle_next = \ |
||
193 | curelm->field.sle_next->field.sle_next; \ |
||
194 | } \ |
||
195 | } while (/*CONSTCOND*/0) |
||
196 | |||
197 | #define SLIST_FOREACH(var, head, field) \ |
||
198 | for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next) |
||
199 | |||
200 | /* |
||
201 | * Singly-linked List access methods. |
||
202 | */ |
||
203 | #define SLIST_EMPTY(head) ((head)->slh_first == NULL) |
||
204 | #define SLIST_FIRST(head) ((head)->slh_first) |
||
205 | #define SLIST_NEXT(elm, field) ((elm)->field.sle_next) |
||
206 | |||
207 | |||
208 | /* |
||
209 | * Singly-linked Tail queue declarations. |
||
210 | */ |
||
211 | #define STAILQ_HEAD(name, type) \ |
||
212 | struct name { \ |
||
213 | struct type *stqh_first; /* first element */ \ |
||
214 | struct type **stqh_last; /* addr of last next element */ \ |
||
215 | } |
||
216 | |||
217 | #define STAILQ_HEAD_INITIALIZER(head) \ |
||
218 | { NULL, &(head).stqh_first } |
||
219 | |||
220 | #define STAILQ_ENTRY(type) \ |
||
221 | struct { \ |
||
222 | struct type *stqe_next; /* next element */ \ |
||
223 | } |
||
224 | |||
225 | /* |
||
226 | * Singly-linked Tail queue functions. |
||
227 | */ |
||
228 | #define STAILQ_INIT(head) do { \ |
||
229 | (head)->stqh_first = NULL; \ |
||
230 | (head)->stqh_last = &(head)->stqh_first; \ |
||
231 | } while (/*CONSTCOND*/0) |
||
232 | |||
233 | #define STAILQ_INSERT_HEAD(head, elm, field) do { \ |
||
234 | if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \ |
||
235 | (head)->stqh_last = &(elm)->field.stqe_next; \ |
||
236 | (head)->stqh_first = (elm); \ |
||
237 | } while (/*CONSTCOND*/0) |
||
238 | |||
239 | #define STAILQ_INSERT_TAIL(head, elm, field) do { \ |
||
240 | (elm)->field.stqe_next = NULL; \ |
||
241 | *(head)->stqh_last = (elm); \ |
||
242 | (head)->stqh_last = &(elm)->field.stqe_next; \ |
||
243 | } while (/*CONSTCOND*/0) |
||
244 | |||
245 | #define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ |
||
246 | if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\ |
||
247 | (head)->stqh_last = &(elm)->field.stqe_next; \ |
||
248 | (listelm)->field.stqe_next = (elm); \ |
||
249 | } while (/*CONSTCOND*/0) |
||
250 | |||
251 | #define STAILQ_REMOVE_HEAD(head, field) do { \ |
||
252 | if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \ |
||
253 | (head)->stqh_last = &(head)->stqh_first; \ |
||
254 | } while (/*CONSTCOND*/0) |
||
255 | |||
256 | #define STAILQ_REMOVE(head, elm, type, field) do { \ |
||
257 | if ((head)->stqh_first == (elm)) { \ |
||
258 | STAILQ_REMOVE_HEAD((head), field); \ |
||
259 | } else { \ |
||
260 | struct type *curelm = (head)->stqh_first; \ |
||
261 | while (curelm->field.stqe_next != (elm)) \ |
||
262 | curelm = curelm->field.stqe_next; \ |
||
263 | if ((curelm->field.stqe_next = \ |
||
264 | curelm->field.stqe_next->field.stqe_next) == NULL) \ |
||
265 | (head)->stqh_last = &(curelm)->field.stqe_next; \ |
||
266 | } \ |
||
267 | } while (/*CONSTCOND*/0) |
||
268 | |||
269 | #define STAILQ_FOREACH(var, head, field) \ |
||
270 | for ((var) = ((head)->stqh_first); \ |
||
271 | (var); \ |
||
272 | (var) = ((var)->field.stqe_next)) |
||
273 | |||
274 | #define STAILQ_CONCAT(head1, head2) do { \ |
||
275 | if (!STAILQ_EMPTY((head2))) { \ |
||
276 | *(head1)->stqh_last = (head2)->stqh_first; \ |
||
277 | (head1)->stqh_last = (head2)->stqh_last; \ |
||
278 | STAILQ_INIT((head2)); \ |
||
279 | } \ |
||
280 | } while (/*CONSTCOND*/0) |
||
281 | |||
282 | /* |
||
283 | * Singly-linked Tail queue access methods. |
||
284 | */ |
||
285 | #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL) |
||
286 | #define STAILQ_FIRST(head) ((head)->stqh_first) |
||
287 | #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next) |
||
288 | |||
289 | |||
290 | /* |
||
291 | * Simple queue definitions. |
||
292 | */ |
||
293 | #define SIMPLEQ_HEAD(name, type) \ |
||
294 | struct name { \ |
||
295 | struct type *sqh_first; /* first element */ \ |
||
296 | struct type **sqh_last; /* addr of last next element */ \ |
||
297 | } |
||
298 | |||
299 | #define SIMPLEQ_HEAD_INITIALIZER(head) \ |
||
300 | { NULL, &(head).sqh_first } |
||
301 | |||
302 | #define SIMPLEQ_ENTRY(type) \ |
||
303 | struct { \ |
||
304 | struct type *sqe_next; /* next element */ \ |
||
305 | } |
||
306 | |||
307 | /* |
||
308 | * Simple queue functions. |
||
309 | */ |
||
310 | #define SIMPLEQ_INIT(head) do { \ |
||
311 | (head)->sqh_first = NULL; \ |
||
312 | (head)->sqh_last = &(head)->sqh_first; \ |
||
313 | } while (/*CONSTCOND*/0) |
||
314 | |||
315 | #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \ |
||
316 | if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \ |
||
317 | (head)->sqh_last = &(elm)->field.sqe_next; \ |
||
318 | (head)->sqh_first = (elm); \ |
||
319 | } while (/*CONSTCOND*/0) |
||
320 | |||
321 | #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \ |
||
322 | (elm)->field.sqe_next = NULL; \ |
||
323 | *(head)->sqh_last = (elm); \ |
||
324 | (head)->sqh_last = &(elm)->field.sqe_next; \ |
||
325 | } while (/*CONSTCOND*/0) |
||
326 | |||
327 | #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ |
||
328 | if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\ |
||
329 | (head)->sqh_last = &(elm)->field.sqe_next; \ |
||
330 | (listelm)->field.sqe_next = (elm); \ |
||
331 | } while (/*CONSTCOND*/0) |
||
332 | |||
333 | #define SIMPLEQ_REMOVE_HEAD(head, field) do { \ |
||
334 | if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \ |
||
335 | (head)->sqh_last = &(head)->sqh_first; \ |
||
336 | } while (/*CONSTCOND*/0) |
||
337 | |||
338 | #define SIMPLEQ_REMOVE(head, elm, type, field) do { \ |
||
339 | if ((head)->sqh_first == (elm)) { \ |
||
340 | SIMPLEQ_REMOVE_HEAD((head), field); \ |
||
341 | } else { \ |
||
342 | struct type *curelm = (head)->sqh_first; \ |
||
343 | while (curelm->field.sqe_next != (elm)) \ |
||
344 | curelm = curelm->field.sqe_next; \ |
||
345 | if ((curelm->field.sqe_next = \ |
||
346 | curelm->field.sqe_next->field.sqe_next) == NULL) \ |
||
347 | (head)->sqh_last = &(curelm)->field.sqe_next; \ |
||
348 | } \ |
||
349 | } while (/*CONSTCOND*/0) |
||
350 | |||
351 | #define SIMPLEQ_FOREACH(var, head, field) \ |
||
352 | for ((var) = ((head)->sqh_first); \ |
||
353 | (var); \ |
||
354 | (var) = ((var)->field.sqe_next)) |
||
355 | |||
356 | /* |
||
357 | * Simple queue access methods. |
||
358 | */ |
||
359 | #define SIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL) |
||
360 | #define SIMPLEQ_FIRST(head) ((head)->sqh_first) |
||
361 | #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next) |
||
362 | |||
363 | |||
364 | /* |
||
365 | * Tail queue definitions. |
||
366 | */ |
||
367 | #define _TAILQ_HEAD(name, type, qual) \ |
||
368 | struct name { \ |
||
369 | qual type *tqh_first; /* first element */ \ |
||
370 | qual type *qual *tqh_last; /* addr of last next element */ \ |
||
371 | } |
||
372 | #define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,) |
||
373 | |||
374 | #define TAILQ_HEAD_INITIALIZER(head) \ |
||
375 | { NULL, &(head).tqh_first } |
||
376 | |||
377 | #define _TAILQ_ENTRY(type, qual) \ |
||
378 | struct { \ |
||
379 | qual type *tqe_next; /* next element */ \ |
||
380 | qual type *qual *tqe_prev; /* address of previous next element */\ |
||
381 | } |
||
382 | #define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,) |
||
383 | |||
384 | /* |
||
385 | * Tail queue functions. |
||
386 | */ |
||
387 | #define TAILQ_INIT(head) do { \ |
||
388 | (head)->tqh_first = NULL; \ |
||
389 | (head)->tqh_last = &(head)->tqh_first; \ |
||
390 | } while (/*CONSTCOND*/0) |
||
391 | |||
392 | #define TAILQ_INSERT_HEAD(head, elm, field) do { \ |
||
393 | if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \ |
||
394 | (head)->tqh_first->field.tqe_prev = \ |
||
395 | &(elm)->field.tqe_next; \ |
||
396 | else \ |
||
397 | (head)->tqh_last = &(elm)->field.tqe_next; \ |
||
398 | (head)->tqh_first = (elm); \ |
||
399 | (elm)->field.tqe_prev = &(head)->tqh_first; \ |
||
400 | } while (/*CONSTCOND*/0) |
||
401 | |||
402 | #define TAILQ_INSERT_TAIL(head, elm, field) do { \ |
||
403 | (elm)->field.tqe_next = NULL; \ |
||
404 | (elm)->field.tqe_prev = (head)->tqh_last; \ |
||
405 | *(head)->tqh_last = (elm); \ |
||
406 | (head)->tqh_last = &(elm)->field.tqe_next; \ |
||
407 | } while (/*CONSTCOND*/0) |
||
408 | |||
409 | #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \ |
||
410 | if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\ |
||
411 | (elm)->field.tqe_next->field.tqe_prev = \ |
||
412 | &(elm)->field.tqe_next; \ |
||
413 | else \ |
||
414 | (head)->tqh_last = &(elm)->field.tqe_next; \ |
||
415 | (listelm)->field.tqe_next = (elm); \ |
||
416 | (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \ |
||
417 | } while (/*CONSTCOND*/0) |
||
418 | |||
419 | #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \ |
||
420 | (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \ |
||
421 | (elm)->field.tqe_next = (listelm); \ |
||
422 | *(listelm)->field.tqe_prev = (elm); \ |
||
423 | (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \ |
||
424 | } while (/*CONSTCOND*/0) |
||
425 | |||
426 | #define TAILQ_REMOVE(head, elm, field) do { \ |
||
427 | if (((elm)->field.tqe_next) != NULL) \ |
||
428 | (elm)->field.tqe_next->field.tqe_prev = \ |
||
429 | (elm)->field.tqe_prev; \ |
||
430 | else \ |
||
431 | (head)->tqh_last = (elm)->field.tqe_prev; \ |
||
432 | *(elm)->field.tqe_prev = (elm)->field.tqe_next; \ |
||
433 | } while (/*CONSTCOND*/0) |
||
434 | |||
435 | #define TAILQ_FOREACH(var, head, field) \ |
||
436 | for ((var) = ((head)->tqh_first); \ |
||
437 | (var); \ |
||
438 | (var) = ((var)->field.tqe_next)) |
||
439 | |||
440 | #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \ |
||
441 | for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \ |
||
442 | (var); \ |
||
443 | (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last))) |
||
444 | |||
445 | #define TAILQ_CONCAT(head1, head2, field) do { \ |
||
446 | if (!TAILQ_EMPTY(head2)) { \ |
||
447 | *(head1)->tqh_last = (head2)->tqh_first; \ |
||
448 | (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ |
||
449 | (head1)->tqh_last = (head2)->tqh_last; \ |
||
450 | TAILQ_INIT((head2)); \ |
||
451 | } \ |
||
452 | } while (/*CONSTCOND*/0) |
||
453 | |||
454 | /* |
||
455 | * Tail queue access methods. |
||
456 | */ |
||
457 | #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL) |
||
458 | #define TAILQ_FIRST(head) ((head)->tqh_first) |
||
459 | #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next) |
||
460 | |||
461 | #define TAILQ_LAST(head, headname) \ |
||
462 | (*(((struct headname *)((head)->tqh_last))->tqh_last)) |
||
463 | #define TAILQ_PREV(elm, headname, field) \ |
||
464 | (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last)) |
||
465 | |||
466 | |||
467 | /* |
||
468 | * Circular queue definitions. |
||
469 | */ |
||
470 | #define CIRCLEQ_HEAD(name, type) \ |
||
471 | struct name { \ |
||
472 | struct type *cqh_first; /* first element */ \ |
||
473 | struct type *cqh_last; /* last element */ \ |
||
474 | } |
||
475 | |||
476 | #define CIRCLEQ_HEAD_INITIALIZER(head) \ |
||
477 | { (void *)&head, (void *)&head } |
||
478 | |||
479 | #define CIRCLEQ_ENTRY(type) \ |
||
480 | struct { \ |
||
481 | struct type *cqe_next; /* next element */ \ |
||
482 | struct type *cqe_prev; /* previous element */ \ |
||
483 | } |
||
484 | |||
485 | /* |
||
486 | * Circular queue functions. |
||
487 | */ |
||
488 | #define CIRCLEQ_INIT(head) do { \ |
||
489 | (head)->cqh_first = (void *)(head); \ |
||
490 | (head)->cqh_last = (void *)(head); \ |
||
491 | } while (/*CONSTCOND*/0) |
||
492 | |||
493 | #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ |
||
494 | (elm)->field.cqe_next = (listelm)->field.cqe_next; \ |
||
495 | (elm)->field.cqe_prev = (listelm); \ |
||
496 | if ((listelm)->field.cqe_next == (void *)(head)) \ |
||
497 | (head)->cqh_last = (elm); \ |
||
498 | else \ |
||
499 | (listelm)->field.cqe_next->field.cqe_prev = (elm); \ |
||
500 | (listelm)->field.cqe_next = (elm); \ |
||
501 | } while (/*CONSTCOND*/0) |
||
502 | |||
503 | #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ |
||
504 | (elm)->field.cqe_next = (listelm); \ |
||
505 | (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ |
||
506 | if ((listelm)->field.cqe_prev == (void *)(head)) \ |
||
507 | (head)->cqh_first = (elm); \ |
||
508 | else \ |
||
509 | (listelm)->field.cqe_prev->field.cqe_next = (elm); \ |
||
510 | (listelm)->field.cqe_prev = (elm); \ |
||
511 | } while (/*CONSTCOND*/0) |
||
512 | |||
513 | #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ |
||
514 | (elm)->field.cqe_next = (head)->cqh_first; \ |
||
515 | (elm)->field.cqe_prev = (void *)(head); \ |
||
516 | if ((head)->cqh_last == (void *)(head)) \ |
||
517 | (head)->cqh_last = (elm); \ |
||
518 | else \ |
||
519 | (head)->cqh_first->field.cqe_prev = (elm); \ |
||
520 | (head)->cqh_first = (elm); \ |
||
521 | } while (/*CONSTCOND*/0) |
||
522 | |||
523 | #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ |
||
524 | (elm)->field.cqe_next = (void *)(head); \ |
||
525 | (elm)->field.cqe_prev = (head)->cqh_last; \ |
||
526 | if ((head)->cqh_first == (void *)(head)) \ |
||
527 | (head)->cqh_first = (elm); \ |
||
528 | else \ |
||
529 | (head)->cqh_last->field.cqe_next = (elm); \ |
||
530 | (head)->cqh_last = (elm); \ |
||
531 | } while (/*CONSTCOND*/0) |
||
532 | |||
533 | #define CIRCLEQ_REMOVE(head, elm, field) do { \ |
||
534 | if ((elm)->field.cqe_next == (void *)(head)) \ |
||
535 | (head)->cqh_last = (elm)->field.cqe_prev; \ |
||
536 | else \ |
||
537 | (elm)->field.cqe_next->field.cqe_prev = \ |
||
538 | (elm)->field.cqe_prev; \ |
||
539 | if ((elm)->field.cqe_prev == (void *)(head)) \ |
||
540 | (head)->cqh_first = (elm)->field.cqe_next; \ |
||
541 | else \ |
||
542 | (elm)->field.cqe_prev->field.cqe_next = \ |
||
543 | (elm)->field.cqe_next; \ |
||
544 | } while (/*CONSTCOND*/0) |
||
545 | |||
546 | #define CIRCLEQ_FOREACH(var, head, field) \ |
||
547 | for ((var) = ((head)->cqh_first); \ |
||
548 | (var) != (const void *)(head); \ |
||
549 | (var) = ((var)->field.cqe_next)) |
||
550 | |||
551 | #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ |
||
552 | for ((var) = ((head)->cqh_last); \ |
||
553 | (var) != (const void *)(head); \ |
||
554 | (var) = ((var)->field.cqe_prev)) |
||
555 | |||
556 | /* |
||
557 | * Circular queue access methods. |
||
558 | */ |
||
559 | #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head)) |
||
560 | #define CIRCLEQ_FIRST(head) ((head)->cqh_first) |
||
561 | #define CIRCLEQ_LAST(head) ((head)->cqh_last) |
||
562 | #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) |
||
563 | #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) |
||
564 | |||
565 | #define CIRCLEQ_LOOP_NEXT(head, elm, field) \ |
||
566 | (((elm)->field.cqe_next == (void *)(head)) \ |
||
567 | ? ((head)->cqh_first) \ |
||
568 | : (elm->field.cqe_next)) |
||
569 | #define CIRCLEQ_LOOP_PREV(head, elm, field) \ |
||
570 | (((elm)->field.cqe_prev == (void *)(head)) \ |
||
571 | ? ((head)->cqh_last) \ |
||
572 | : (elm->field.cqe_prev)) |
||
573 | |||
574 | #endif /* sys/queue.h */ |