1 /* $NetBSD: queue.h,v 1.42 2005/07/13 15:08:24 wiz Exp $ */
2
3 /*
4 * Copyright (c) 1991, 1993
5 * The Regents of the University of California. All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 * 3. Neither the name of the University nor the names of its contributors
16 * may be used to endorse or promote products derived from this software
17 * without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * SUCH DAMAGE.
30 *
31 * @(#)queue.h 8.5 (Berkeley) 8/20/94
32 */
33 /*
34 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
35 * Use is subject to license terms.
36 */
37
38 #ifndef _SYS_QUEUE_H
39 #define _SYS_QUEUE_H
40
41 #include <sys/note.h>
42
43 #ifdef __cplusplus
44 extern "C" {
45 #endif
46
47 /*
48 * This file defines five types of data structures: singly-linked lists,
49 * lists, simple queues, tail queues, and circular queues.
50 *
51 * A singly-linked list is headed by a single forward pointer. The
52 * elements are singly linked for minimum space and pointer manipulation
53 * overhead at the expense of O(n) removal for arbitrary elements. New
54 * elements can be added to the list after an existing element or at the
55 * head of the list. Elements being removed from the head of the list
56 * should use the explicit macro for this purpose for optimum
57 * efficiency. A singly-linked list may only be traversed in the forward
58 * direction. Singly-linked lists are ideal for applications with large
59 * datasets and few or no removals or for implementing a LIFO queue.
60 *
61 * A list is headed by a single forward pointer (or an array of forward
62 * pointers for a hash table header). The elements are doubly linked
63 * so that an arbitrary element can be removed without a need to
64 * traverse the list. New elements can be added to the list before
65 * or after an existing element or at the head of the list. A list
66 * may only be traversed in the forward direction.
67 *
68 * A simple queue is headed by a pair of pointers, one the head of the
69 * list and the other to the tail of the list. The elements are singly
70 * linked to save space, so elements can only be removed from the
71 * head of the list. New elements can be added to the list after
72 * an existing element, at the head of the list, or at the end of the
73 * list. A simple queue may only be traversed in the forward direction.
74 *
75 * A tail queue is headed by a pair of pointers, one to the head of the
76 * list and the other to the tail of the list. The elements are doubly
77 * linked so that an arbitrary element can be removed without a need to
78 * traverse the list. New elements can be added to the list before or
79 * after an existing element, at the head of the list, or at the end of
80 * the list. A tail queue may be traversed in either direction.
81 *
82 * A circle queue is headed by a pair of pointers, one to the head of the
83 * list and the other to the tail of the list. The elements are doubly
84 * linked so that an arbitrary element can be removed without a need to
85 * traverse the list. New elements can be added to the list before or after
86 * an existing element, at the head of the list, or at the end of the list.
87 * A circle queue may be traversed in either direction, but has a more
88 * complex end of list detection.
89 *
90 * For details on the use of these macros, see the queue(3) manual page.
91 */
92
93 /*
94 * List definitions.
95 */
96 #define LIST_HEAD(name, type) \
97 struct name { \
98 struct type *lh_first; /* first element */ \
99 }
100
101 #define LIST_HEAD_INITIALIZER(head) \
102 { NULL }
103
104 #define LIST_ENTRY(type) \
105 struct { \
106 struct type *le_next; /* next element */ \
107 struct type **le_prev; /* address of previous next element */ \
108 }
109
110 /*
111 * List functions.
112 */
113 #if defined(_KERNEL) && defined(QUEUEDEBUG)
114 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field) \
115 if ((head)->lh_first && \
116 (head)->lh_first->field.le_prev != &(head)->lh_first) \
117 panic("LIST_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
118 #define QUEUEDEBUG_LIST_OP(elm, field) \
119 if ((elm)->field.le_next && \
120 (elm)->field.le_next->field.le_prev != \
121 &(elm)->field.le_next) \
122 panic("LIST_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
123 if (*(elm)->field.le_prev != (elm)) \
124 panic("LIST_* back %p %s:%d", (elm), __FILE__, __LINE__);
125 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field) \
126 (elm)->field.le_next = (void *)1L; \
127 (elm)->field.le_prev = (void *)1L;
128 #else
129 #define QUEUEDEBUG_LIST_INSERT_HEAD(head, elm, field)
130 #define QUEUEDEBUG_LIST_OP(elm, field)
131 #define QUEUEDEBUG_LIST_POSTREMOVE(elm, field)
132 #endif
133
134 #define LIST_INIT(head) do { \
135 (head)->lh_first = NULL; \
136 _NOTE(CONSTCOND) \
137 } while (0)
138
139 #define LIST_INSERT_AFTER(listelm, elm, field) do { \
140 QUEUEDEBUG_LIST_OP((listelm), field) \
141 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
142 (listelm)->field.le_next->field.le_prev = \
143 &(elm)->field.le_next; \
144 (listelm)->field.le_next = (elm); \
145 (elm)->field.le_prev = &(listelm)->field.le_next; \
146 _NOTE(CONSTCOND) \
147 } while (0)
148
149 #define LIST_INSERT_BEFORE(listelm, elm, field) do { \
150 QUEUEDEBUG_LIST_OP((listelm), field) \
151 (elm)->field.le_prev = (listelm)->field.le_prev; \
152 (elm)->field.le_next = (listelm); \
153 *(listelm)->field.le_prev = (elm); \
154 (listelm)->field.le_prev = &(elm)->field.le_next; \
155 _NOTE(CONSTCOND) \
156 } while (0)
157
158 #define LIST_INSERT_HEAD(head, elm, field) do { \
159 QUEUEDEBUG_LIST_INSERT_HEAD((head), (elm), field) \
160 if (((elm)->field.le_next = (head)->lh_first) != NULL) \
161 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
162 (head)->lh_first = (elm); \
163 (elm)->field.le_prev = &(head)->lh_first; \
164 _NOTE(CONSTCOND) \
165 } while (0)
166
167 #define LIST_REMOVE(elm, field) do { \
168 QUEUEDEBUG_LIST_OP((elm), field) \
169 if ((elm)->field.le_next != NULL) \
170 (elm)->field.le_next->field.le_prev = \
171 (elm)->field.le_prev; \
172 *(elm)->field.le_prev = (elm)->field.le_next; \
173 QUEUEDEBUG_LIST_POSTREMOVE((elm), field) \
174 _NOTE(CONSTCOND) \
175 } while (0)
176
177 #define LIST_FOREACH(var, head, field) \
178 for ((var) = ((head)->lh_first); \
179 (var); \
180 (var) = ((var)->field.le_next))
181
182 /*
183 * List access methods.
184 */
185 #define LIST_EMPTY(head) ((head)->lh_first == NULL)
186 #define LIST_FIRST(head) ((head)->lh_first)
187 #define LIST_NEXT(elm, field) ((elm)->field.le_next)
188
189
190 /*
191 * Singly-linked List definitions.
192 */
193 #define SLIST_HEAD(name, type) \
194 struct name { \
195 struct type *slh_first; /* first element */ \
196 }
197
198 #define SLIST_HEAD_INITIALIZER(head) \
199 { NULL }
200
201 #define SLIST_ENTRY(type) \
202 struct { \
203 struct type *sle_next; /* next element */ \
204 }
205
206 /*
207 * Singly-linked List functions.
208 */
209 #define SLIST_INIT(head) do { \
210 (head)->slh_first = NULL; \
211 _NOTE(CONSTCOND) \
212 } while (0)
213
214 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
215 (elm)->field.sle_next = (slistelm)->field.sle_next; \
216 (slistelm)->field.sle_next = (elm); \
217 _NOTE(CONSTCOND) \
218 } while (0)
219
220 #define SLIST_INSERT_HEAD(head, elm, field) do { \
221 (elm)->field.sle_next = (head)->slh_first; \
222 (head)->slh_first = (elm); \
223 _NOTE(CONSTCOND) \
224 } while (0)
225
226 #define SLIST_REMOVE_HEAD(head, field) do { \
227 (head)->slh_first = (head)->slh_first->field.sle_next; \
228 _NOTE(CONSTCOND) \
229 } while (0)
230
231 #define SLIST_REMOVE(head, elm, type, field) do { \
232 if ((head)->slh_first == (elm)) { \
233 SLIST_REMOVE_HEAD((head), field); \
234 } \
235 else { \
236 struct type *curelm = (head)->slh_first; \
237 while (curelm->field.sle_next != (elm)) \
238 curelm = curelm->field.sle_next; \
239 curelm->field.sle_next = \
240 curelm->field.sle_next->field.sle_next; \
241 } \
242 _NOTE(CONSTCOND) \
243 } while (0)
244
245 #define SLIST_FOREACH(var, head, field) \
246 for ((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
247
248 /*
249 * Singly-linked List access methods.
250 */
251 #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
252 #define SLIST_FIRST(head) ((head)->slh_first)
253 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
254
255
256 /*
257 * Singly-linked Tail queue declarations.
258 */
259 #define STAILQ_HEAD(name, type) \
260 struct name { \
261 struct type *stqh_first; /* first element */ \
262 struct type **stqh_last; /* addr of last next element */ \
263 }
264
265 #define STAILQ_HEAD_INITIALIZER(head) \
266 { NULL, &(head).stqh_first }
267
268 #define STAILQ_ENTRY(type) \
269 struct { \
270 struct type *stqe_next; /* next element */ \
271 }
272
273 /*
274 * Singly-linked Tail queue functions.
275 */
276 #define STAILQ_INIT(head) do { \
277 (head)->stqh_first = NULL; \
278 (head)->stqh_last = &(head)->stqh_first; \
279 _NOTE(CONSTCOND) \
280 } while (0)
281
282 #define STAILQ_INSERT_HEAD(head, elm, field) do { \
283 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
284 (head)->stqh_last = &(elm)->field.stqe_next; \
285 (head)->stqh_first = (elm); \
286 _NOTE(CONSTCOND) \
287 } while (0)
288
289 #define STAILQ_INSERT_TAIL(head, elm, field) do { \
290 (elm)->field.stqe_next = NULL; \
291 *(head)->stqh_last = (elm); \
292 (head)->stqh_last = &(elm)->field.stqe_next; \
293 _NOTE(CONSTCOND) \
294 } while (0)
295
296 #define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
297 if (((elm)->field.stqe_next = (listelm)->field.stqe_next) \
298 == NULL) \
299 (head)->stqh_last = &(elm)->field.stqe_next; \
300 (listelm)->field.stqe_next = (elm); \
301 _NOTE(CONSTCOND) \
302 } while (0)
303
304 #define STAILQ_REMOVE_HEAD(head, field) do { \
305 if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) \
306 == NULL) \
307 (head)->stqh_last = &(head)->stqh_first; \
308 _NOTE(CONSTCOND) \
309 } while (0)
310
311 #define STAILQ_REMOVE(head, elm, type, field) do { \
312 if ((head)->stqh_first == (elm)) { \
313 STAILQ_REMOVE_HEAD((head), field); \
314 } else { \
315 struct type *curelm = (head)->stqh_first; \
316 while (curelm->field.stqe_next != (elm)) \
317 curelm = curelm->field.stqe_next; \
318 if ((curelm->field.stqe_next = \
319 curelm->field.stqe_next->field.stqe_next) == NULL) \
320 (head)->stqh_last = &(curelm)->field.stqe_next; \
321 } \
322 _NOTE(CONSTCOND) \
323 } while (0)
324
325 /*
326 * Singly-linked Tail queue access methods.
327 */
328 #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
329 #define STAILQ_FIRST(head) ((head)->stqh_first)
330 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
331
332 #define STAILQ_FOREACH(var, head, field) \
333 for ((var) = ((head)->stqh_first); \
334 (var); \
335 (var) = ((var)->field.stqe_next))
336
337 #define STAILQ_FOREACH_SAFE(var, head, field, tvar) \
338 for ((var) = STAILQ_FIRST((head)); \
339 (var) && ((tvar) = STAILQ_NEXT((var), field), 1); \
340 (var) = (tvar))
341
342
343 /*
344 * Simple queue definitions.
345 */
346 #define SIMPLEQ_HEAD(name, type) \
347 struct name { \
348 struct type *sqh_first; /* first element */ \
349 struct type **sqh_last; /* addr of last next element */ \
350 }
351
352 #define SIMPLEQ_HEAD_INITIALIZER(head) \
353 { NULL, &(head).sqh_first }
354
355 #define SIMPLEQ_ENTRY(type) \
356 struct { \
357 struct type *sqe_next; /* next element */ \
358 }
359
360 /*
361 * Simple queue functions.
362 */
363 #define SIMPLEQ_INIT(head) do { \
364 (head)->sqh_first = NULL; \
365 (head)->sqh_last = &(head)->sqh_first; \
366 _NOTE(CONSTCOND) \
367 } while (0)
368
369 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
370 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
371 (head)->sqh_last = &(elm)->field.sqe_next; \
372 (head)->sqh_first = (elm); \
373 _NOTE(CONSTCOND) \
374 } while (0)
375
376 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
377 (elm)->field.sqe_next = NULL; \
378 *(head)->sqh_last = (elm); \
379 (head)->sqh_last = &(elm)->field.sqe_next; \
380 _NOTE(CONSTCOND) \
381 } while (0)
382
383 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
384 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
385 (head)->sqh_last = &(elm)->field.sqe_next; \
386 (listelm)->field.sqe_next = (elm); \
387 _NOTE(CONSTCOND) \
388 } while (0)
389
390 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
391 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
392 (head)->sqh_last = &(head)->sqh_first; \
393 _NOTE(CONSTCOND) \
394 } while (0)
395
396 #define SIMPLEQ_REMOVE(head, elm, type, field) do { \
397 if ((head)->sqh_first == (elm)) { \
398 SIMPLEQ_REMOVE_HEAD((head), field); \
399 } else { \
400 struct type *curelm = (head)->sqh_first; \
401 while (curelm->field.sqe_next != (elm)) \
402 curelm = curelm->field.sqe_next; \
403 if ((curelm->field.sqe_next = \
404 curelm->field.sqe_next->field.sqe_next) == NULL) \
405 (head)->sqh_last = &(curelm)->field.sqe_next; \
406 } \
407 _NOTE(CONSTCOND) \
408 } while (0)
409
410 #define SIMPLEQ_FOREACH(var, head, field) \
411 for ((var) = ((head)->sqh_first); \
412 (var); \
413 (var) = ((var)->field.sqe_next))
414
415 /*
416 * Simple queue access methods.
417 */
418 #define SIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)
419 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
420 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
421
422
423 /*
424 * Tail queue definitions.
425 */
426 #define _TAILQ_HEAD(name, type) \
427 struct name { \
428 type *tqh_first; /* first element */ \
429 type **tqh_last; /* addr of last next element */ \
430 }
431 #define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type)
432
433 #define TAILQ_HEAD_INITIALIZER(head) \
434 { NULL, &(head).tqh_first }
435
436 #define _TAILQ_ENTRY(type) \
437 struct { \
438 type *tqe_next; /* next element */ \
439 type **tqe_prev; /* address of previous next element */\
440 }
441 #define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type)
442
443 /*
444 * Tail queue functions.
445 */
446 #if defined(_KERNEL) && defined(QUEUEDEBUG)
447 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) \
448 if ((head)->tqh_first && \
449 (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \
450 panic("TAILQ_INSERT_HEAD %p %s:%d", (void *)(head), \
451 __FILE__, __LINE__);
452 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) \
453 if (*(head)->tqh_last != NULL) \
454 panic("TAILQ_INSERT_TAIL %p %s:%d", (void *)(head), \
455 __FILE__, __LINE__);
456 #define QUEUEDEBUG_TAILQ_OP(elm, field) \
457 if ((elm)->field.tqe_next && \
458 (elm)->field.tqe_next->field.tqe_prev != \
459 &(elm)->field.tqe_next) \
460 panic("TAILQ_* forw %p %s:%d", (void *)(elm), \
461 __FILE__, __LINE__);\
462 if (*(elm)->field.tqe_prev != (elm)) \
463 panic("TAILQ_* back %p %s:%d", (void *)(elm), \
464 __FILE__, __LINE__);
465 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) \
466 if ((elm)->field.tqe_next == NULL && \
467 (head)->tqh_last != &(elm)->field.tqe_next) \
468 panic("TAILQ_PREREMOVE head %p elm %p %s:%d", \
469 (void *)(head), (void *)(elm), __FILE__, __LINE__);
470 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) \
471 (elm)->field.tqe_next = (void *)1L; \
472 (elm)->field.tqe_prev = (void *)1L;
473 #else
474 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
475 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
476 #define QUEUEDEBUG_TAILQ_OP(elm, field)
477 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)
478 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
479 #endif
480
481 #define TAILQ_INIT(head) do { \
482 (head)->tqh_first = NULL; \
483 (head)->tqh_last = &(head)->tqh_first; \
484 _NOTE(CONSTCOND) \
485 } while (0)
486
487 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
488 QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field) \
489 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
490 (head)->tqh_first->field.tqe_prev = \
491 &(elm)->field.tqe_next; \
492 else \
493 (head)->tqh_last = &(elm)->field.tqe_next; \
494 (head)->tqh_first = (elm); \
495 (elm)->field.tqe_prev = &(head)->tqh_first; \
496 _NOTE(CONSTCOND) \
497 } while (0)
498
499 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
500 QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field) \
501 (elm)->field.tqe_next = NULL; \
502 (elm)->field.tqe_prev = (head)->tqh_last; \
503 *(head)->tqh_last = (elm); \
504 (head)->tqh_last = &(elm)->field.tqe_next; \
505 _NOTE(CONSTCOND) \
506 } while (0)
507
508 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
509 QUEUEDEBUG_TAILQ_OP((listelm), field) \
510 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
511 (elm)->field.tqe_next->field.tqe_prev = \
512 &(elm)->field.tqe_next; \
513 else \
514 (head)->tqh_last = &(elm)->field.tqe_next; \
515 (listelm)->field.tqe_next = (elm); \
516 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
517 _NOTE(CONSTCOND) \
518 } while (0)
519
520 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
521 QUEUEDEBUG_TAILQ_OP((listelm), field) \
522 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
523 (elm)->field.tqe_next = (listelm); \
524 *(listelm)->field.tqe_prev = (elm); \
525 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
526 _NOTE(CONSTCOND) \
527 } while (0)
528
529 #define TAILQ_REMOVE(head, elm, field) do { \
530 QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field) \
531 QUEUEDEBUG_TAILQ_OP((elm), field) \
532 if (((elm)->field.tqe_next) != NULL) \
533 (elm)->field.tqe_next->field.tqe_prev = \
534 (elm)->field.tqe_prev; \
535 else \
536 (head)->tqh_last = (elm)->field.tqe_prev; \
537 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
538 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \
539 _NOTE(CONSTCOND) \
540 } while (0)
541
542 #define TAILQ_FOREACH(var, head, field) \
543 for ((var) = ((head)->tqh_first); \
544 (var); \
545 (var) = ((var)->field.tqe_next))
546
547 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
548 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last));\
549 (var); \
550 (var) = \
551 (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
552
553 /*
554 * Tail queue access methods.
555 */
556 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
557 #define TAILQ_FIRST(head) ((head)->tqh_first)
558 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
559
560 #define TAILQ_LAST(head, headname) \
561 (*(((struct headname *)((head)->tqh_last))->tqh_last))
562 #define TAILQ_PREV(elm, headname, field) \
563 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
564
565
566 /*
567 * Circular queue definitions.
568 */
569 #define CIRCLEQ_HEAD(name, type) \
570 struct name { \
571 struct type *cqh_first; /* first element */ \
572 struct type *cqh_last; /* last element */ \
573 }
574
575 #define CIRCLEQ_HEAD_INITIALIZER(head) \
576 { (void *)&head, (void *)&head }
577
578 #define CIRCLEQ_ENTRY(type) \
579 struct { \
580 struct type *cqe_next; /* next element */ \
581 struct type *cqe_prev; /* previous element */ \
582 }
583
584 /*
585 * Circular queue functions.
586 */
587 #define CIRCLEQ_INIT(head) do { \
588 (head)->cqh_first = (void *)(head); \
589 (head)->cqh_last = (void *)(head); \
590 _NOTE(CONSTCOND) \
591 } while (0)
592
593 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
594 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
595 (elm)->field.cqe_prev = (listelm); \
596 if ((listelm)->field.cqe_next == (void *)(head)) \
597 (head)->cqh_last = (elm); \
598 else \
599 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
600 (listelm)->field.cqe_next = (elm); \
601 _NOTE(CONSTCOND) \
602 } while (0)
603
604 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
605 (elm)->field.cqe_next = (listelm); \
606 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
607 if ((listelm)->field.cqe_prev == (void *)(head)) \
608 (head)->cqh_first = (elm); \
609 else \
610 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
611 (listelm)->field.cqe_prev = (elm); \
612 _NOTE(CONSTCOND) \
613 } while (0)
614
615 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
616 (elm)->field.cqe_next = (head)->cqh_first; \
617 (elm)->field.cqe_prev = (void *)(head); \
618 if ((head)->cqh_last == (void *)(head)) \
619 (head)->cqh_last = (elm); \
620 else \
621 (head)->cqh_first->field.cqe_prev = (elm); \
622 (head)->cqh_first = (elm); \
623 _NOTE(CONSTCOND) \
624 } while (0)
625
626 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
627 (elm)->field.cqe_next = (void *)(head); \
628 (elm)->field.cqe_prev = (head)->cqh_last; \
629 if ((head)->cqh_first == (void *)(head)) \
630 (head)->cqh_first = (elm); \
631 else \
632 (head)->cqh_last->field.cqe_next = (elm); \
633 (head)->cqh_last = (elm); \
634 _NOTE(CONSTCOND) \
635 } while (0)
636
637 #define CIRCLEQ_REMOVE(head, elm, field) do { \
638 if ((elm)->field.cqe_next == (void *)(head)) \
639 (head)->cqh_last = (elm)->field.cqe_prev; \
640 else \
641 (elm)->field.cqe_next->field.cqe_prev = \
642 (elm)->field.cqe_prev; \
643 if ((elm)->field.cqe_prev == (void *)(head)) \
644 (head)->cqh_first = (elm)->field.cqe_next; \
645 else \
646 (elm)->field.cqe_prev->field.cqe_next = \
647 (elm)->field.cqe_next; \
648 _NOTE(CONSTCOND) \
649 } while (0)
650
651 #define CIRCLEQ_FOREACH(var, head, field) \
652 for ((var) = ((head)->cqh_first); \
653 (var) != (void *)(head); \
654 (var) = ((var)->field.cqe_next))
655
656 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
657 for ((var) = ((head)->cqh_last); \
658 (var) != (void *)(head); \
659 (var) = ((var)->field.cqe_prev))
660
661 /*
662 * Circular queue access methods.
663 */
664 #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
665 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
666 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
667 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
668 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
669
670 #define CIRCLEQ_LOOP_NEXT(head, elm, field) \
671 (((elm)->field.cqe_next == (void *)(head)) \
672 ? ((head)->cqh_first) \
673 : (elm->field.cqe_next))
674 #define CIRCLEQ_LOOP_PREV(head, elm, field) \
675 (((elm)->field.cqe_prev == (void *)(head)) \
676 ? ((head)->cqh_last) \
677 : (elm->field.cqe_prev))
678
679 #ifdef __cplusplus
680 }
681 #endif
682
683 #endif /* !_SYS_QUEUE_H */