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