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