FreeBSD/Linux Kernel Cross Reference
sys/sys/queue.h
1 /* $NetBSD: queue.h,v 1.37 2004/03/23 10:50:31 he 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) \
87 struct name { \
88 struct type *lh_first; /* first element */ \
89 }
90
91 #define LIST_HEAD_INITIALIZER(head) \
92 { NULL }
93
94 #define LIST_ENTRY(type) \
95 struct { \
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 * Singly-linked List definitions.
176 */
177 #define SLIST_HEAD(name, type) \
178 struct name { \
179 struct type *slh_first; /* first element */ \
180 }
181
182 #define SLIST_HEAD_INITIALIZER(head) \
183 { NULL }
184
185 #define SLIST_ENTRY(type) \
186 struct { \
187 struct type *sle_next; /* next element */ \
188 }
189
190 /*
191 * Singly-linked List functions.
192 */
193 #define SLIST_EMPTY(head) ((head)->slh_first == NULL)
194 #define SLIST_FIRST(head) ((head)->slh_first)
195 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
196
197 #define SLIST_FOREACH(var, head, field) \
198 for((var) = (head)->slh_first; (var); (var) = (var)->field.sle_next)
199
200 #define SLIST_INIT(head) do { \
201 (head)->slh_first = NULL; \
202 } while (/*CONSTCOND*/0)
203
204 #define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
205 (elm)->field.sle_next = (slistelm)->field.sle_next; \
206 (slistelm)->field.sle_next = (elm); \
207 } while (/*CONSTCOND*/0)
208
209 #define SLIST_INSERT_HEAD(head, elm, field) do { \
210 (elm)->field.sle_next = (head)->slh_first; \
211 (head)->slh_first = (elm); \
212 } while (/*CONSTCOND*/0)
213
214 #define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
215
216 #define SLIST_REMOVE_HEAD(head, field) do { \
217 (head)->slh_first = (head)->slh_first->field.sle_next; \
218 } while (/*CONSTCOND*/0)
219
220 #define SLIST_REMOVE(head, elm, type, field) do { \
221 if ((head)->slh_first == (elm)) { \
222 SLIST_REMOVE_HEAD((head), field); \
223 } \
224 else { \
225 struct type *curelm = (head)->slh_first; \
226 while(curelm->field.sle_next != (elm)) \
227 curelm = curelm->field.sle_next; \
228 curelm->field.sle_next = \
229 curelm->field.sle_next->field.sle_next; \
230 } \
231 } while (/*CONSTCOND*/0)
232
233 /*
234 * Singly-linked Tail queue declarations.
235 */
236 #define STAILQ_HEAD(name, type) \
237 struct name { \
238 struct type *stqh_first; /* first element */ \
239 struct type **stqh_last; /* addr of last next element */ \
240 }
241
242 #define STAILQ_HEAD_INITIALIZER(head) \
243 { NULL, &(head).stqh_first }
244
245 #define STAILQ_ENTRY(type) \
246 struct { \
247 struct type *stqe_next; /* next element */ \
248 }
249
250 /*
251 * Singly-linked Tail queue functions.
252 */
253 #define STAILQ_INIT(head) do { \
254 (head)->stqh_first = NULL; \
255 (head)->stqh_last = &(head)->stqh_first; \
256 } while (/*CONSTCOND*/0)
257
258 #define STAILQ_INSERT_HEAD(head, elm, field) do { \
259 if (((elm)->field.stqe_next = (head)->stqh_first) == NULL) \
260 (head)->stqh_last = &(elm)->field.stqe_next; \
261 (head)->stqh_first = (elm); \
262 } while (/*CONSTCOND*/0)
263
264 #define STAILQ_INSERT_TAIL(head, elm, field) do { \
265 (elm)->field.stqe_next = NULL; \
266 *(head)->stqh_last = (elm); \
267 (head)->stqh_last = &(elm)->field.stqe_next; \
268 } while (/*CONSTCOND*/0)
269
270 #define STAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
271 if (((elm)->field.stqe_next = (listelm)->field.stqe_next) == NULL)\
272 (head)->stqh_last = &(elm)->field.stqe_next; \
273 (listelm)->field.stqe_next = (elm); \
274 } while (/*CONSTCOND*/0)
275
276 #define STAILQ_REMOVE_HEAD(head, field) do { \
277 if (((head)->stqh_first = (head)->stqh_first->field.stqe_next) == NULL) \
278 (head)->stqh_last = &(head)->stqh_first; \
279 } while (/*CONSTCOND*/0)
280
281 #define STAILQ_REMOVE(head, elm, type, field) do { \
282 if ((head)->stqh_first == (elm)) { \
283 STAILQ_REMOVE_HEAD((head), field); \
284 } else { \
285 struct type *curelm = (head)->stqh_first; \
286 while (curelm->field.stqe_next != (elm)) \
287 curelm = curelm->field.stqe_next; \
288 if ((curelm->field.stqe_next = \
289 curelm->field.stqe_next->field.stqe_next) == NULL) \
290 (head)->stqh_last = &(curelm)->field.stqe_next; \
291 } \
292 } while (/*CONSTCOND*/0)
293
294 #define STAILQ_FOREACH(var, head, field) \
295 for ((var) = ((head)->stqh_first); \
296 (var); \
297 (var) = ((var)->field.stqe_next))
298
299 #define STAILQ_EMPTY(head) ((head)->stqh_first == NULL)
300
301 #define STAILQ_FIRST(head) ((head)->stqh_first)
302
303 #define STAILQ_NEXT(elm, field) ((elm)->field.stqe_next)
304
305 /*
306 * Simple queue definitions.
307 */
308 #define SIMPLEQ_HEAD(name, type) \
309 struct name { \
310 struct type *sqh_first; /* first element */ \
311 struct type **sqh_last; /* addr of last next element */ \
312 }
313
314 #define SIMPLEQ_HEAD_INITIALIZER(head) \
315 { NULL, &(head).sqh_first }
316
317 #define SIMPLEQ_ENTRY(type) \
318 struct { \
319 struct type *sqe_next; /* next element */ \
320 }
321
322 /*
323 * Simple queue functions.
324 */
325 #define SIMPLEQ_INIT(head) do { \
326 (head)->sqh_first = NULL; \
327 (head)->sqh_last = &(head)->sqh_first; \
328 } while (/*CONSTCOND*/0)
329
330 #define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
331 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
332 (head)->sqh_last = &(elm)->field.sqe_next; \
333 (head)->sqh_first = (elm); \
334 } while (/*CONSTCOND*/0)
335
336 #define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
337 (elm)->field.sqe_next = NULL; \
338 *(head)->sqh_last = (elm); \
339 (head)->sqh_last = &(elm)->field.sqe_next; \
340 } while (/*CONSTCOND*/0)
341
342 #define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
343 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
344 (head)->sqh_last = &(elm)->field.sqe_next; \
345 (listelm)->field.sqe_next = (elm); \
346 } while (/*CONSTCOND*/0)
347
348 #define SIMPLEQ_REMOVE_HEAD(head, field) do { \
349 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
350 (head)->sqh_last = &(head)->sqh_first; \
351 } while (/*CONSTCOND*/0)
352
353 #define SIMPLEQ_REMOVE(head, elm, type, field) do { \
354 if ((head)->sqh_first == (elm)) { \
355 SIMPLEQ_REMOVE_HEAD((head), field); \
356 } else { \
357 struct type *curelm = (head)->sqh_first; \
358 while (curelm->field.sqe_next != (elm)) \
359 curelm = curelm->field.sqe_next; \
360 if ((curelm->field.sqe_next = \
361 curelm->field.sqe_next->field.sqe_next) == NULL) \
362 (head)->sqh_last = &(curelm)->field.sqe_next; \
363 } \
364 } while (/*CONSTCOND*/0)
365
366 #define SIMPLEQ_FOREACH(var, head, field) \
367 for ((var) = ((head)->sqh_first); \
368 (var); \
369 (var) = ((var)->field.sqe_next))
370
371 /*
372 * Simple queue access methods.
373 */
374 #define SIMPLEQ_EMPTY(head) ((head)->sqh_first == NULL)
375 #define SIMPLEQ_FIRST(head) ((head)->sqh_first)
376 #define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
377
378 /*
379 * Tail queue definitions.
380 */
381 #define TAILQ_HEAD(name, type) \
382 struct name { \
383 struct type *tqh_first; /* first element */ \
384 struct type **tqh_last; /* addr of last next element */ \
385 }
386
387 #define TAILQ_HEAD_INITIALIZER(head) \
388 { NULL, &(head).tqh_first }
389
390 #define TAILQ_ENTRY(type) \
391 struct { \
392 struct type *tqe_next; /* next element */ \
393 struct type **tqe_prev; /* address of previous next element */ \
394 }
395
396 /*
397 * Tail queue functions.
398 */
399 #if defined(_KERNEL) && defined(QUEUEDEBUG)
400 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field) \
401 if ((head)->tqh_first && \
402 (head)->tqh_first->field.tqe_prev != &(head)->tqh_first) \
403 panic("TAILQ_INSERT_HEAD %p %s:%d", (head), __FILE__, __LINE__);
404 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field) \
405 if (*(head)->tqh_last != NULL) \
406 panic("TAILQ_INSERT_TAIL %p %s:%d", (head), __FILE__, __LINE__);
407 #define QUEUEDEBUG_TAILQ_OP(elm, field) \
408 if ((elm)->field.tqe_next && \
409 (elm)->field.tqe_next->field.tqe_prev != \
410 &(elm)->field.tqe_next) \
411 panic("TAILQ_* forw %p %s:%d", (elm), __FILE__, __LINE__);\
412 if (*(elm)->field.tqe_prev != (elm)) \
413 panic("TAILQ_* back %p %s:%d", (elm), __FILE__, __LINE__);
414 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field) \
415 if ((elm)->field.tqe_next == NULL && \
416 (head)->tqh_last != &(elm)->field.tqe_next) \
417 panic("TAILQ_PREREMOVE head %p elm %p %s:%d", \
418 (head), (elm), __FILE__, __LINE__);
419 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field) \
420 (elm)->field.tqe_next = (void *)1L; \
421 (elm)->field.tqe_prev = (void *)1L;
422 #else
423 #define QUEUEDEBUG_TAILQ_INSERT_HEAD(head, elm, field)
424 #define QUEUEDEBUG_TAILQ_INSERT_TAIL(head, elm, field)
425 #define QUEUEDEBUG_TAILQ_OP(elm, field)
426 #define QUEUEDEBUG_TAILQ_PREREMOVE(head, elm, field)
427 #define QUEUEDEBUG_TAILQ_POSTREMOVE(elm, field)
428 #endif
429
430 #define TAILQ_INIT(head) do { \
431 (head)->tqh_first = NULL; \
432 (head)->tqh_last = &(head)->tqh_first; \
433 } while (/*CONSTCOND*/0)
434
435 #define TAILQ_INSERT_HEAD(head, elm, field) do { \
436 QUEUEDEBUG_TAILQ_INSERT_HEAD((head), (elm), field) \
437 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
438 (head)->tqh_first->field.tqe_prev = \
439 &(elm)->field.tqe_next; \
440 else \
441 (head)->tqh_last = &(elm)->field.tqe_next; \
442 (head)->tqh_first = (elm); \
443 (elm)->field.tqe_prev = &(head)->tqh_first; \
444 } while (/*CONSTCOND*/0)
445
446 #define TAILQ_INSERT_TAIL(head, elm, field) do { \
447 QUEUEDEBUG_TAILQ_INSERT_TAIL((head), (elm), field) \
448 (elm)->field.tqe_next = NULL; \
449 (elm)->field.tqe_prev = (head)->tqh_last; \
450 *(head)->tqh_last = (elm); \
451 (head)->tqh_last = &(elm)->field.tqe_next; \
452 } while (/*CONSTCOND*/0)
453
454 #define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
455 QUEUEDEBUG_TAILQ_OP((listelm), field) \
456 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
457 (elm)->field.tqe_next->field.tqe_prev = \
458 &(elm)->field.tqe_next; \
459 else \
460 (head)->tqh_last = &(elm)->field.tqe_next; \
461 (listelm)->field.tqe_next = (elm); \
462 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
463 } while (/*CONSTCOND*/0)
464
465 #define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
466 QUEUEDEBUG_TAILQ_OP((listelm), field) \
467 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
468 (elm)->field.tqe_next = (listelm); \
469 *(listelm)->field.tqe_prev = (elm); \
470 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
471 } while (/*CONSTCOND*/0)
472
473 #define TAILQ_REMOVE(head, elm, field) do { \
474 QUEUEDEBUG_TAILQ_PREREMOVE((head), (elm), field) \
475 QUEUEDEBUG_TAILQ_OP((elm), field) \
476 if (((elm)->field.tqe_next) != NULL) \
477 (elm)->field.tqe_next->field.tqe_prev = \
478 (elm)->field.tqe_prev; \
479 else \
480 (head)->tqh_last = (elm)->field.tqe_prev; \
481 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
482 QUEUEDEBUG_TAILQ_POSTREMOVE((elm), field); \
483 } while (/*CONSTCOND*/0)
484
485 /*
486 * Tail queue access methods.
487 */
488 #define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
489 #define TAILQ_FIRST(head) ((head)->tqh_first)
490 #define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
491
492 #define TAILQ_LAST(head, headname) \
493 (*(((struct headname *)((head)->tqh_last))->tqh_last))
494 #define TAILQ_PREV(elm, headname, field) \
495 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
496
497 #define TAILQ_FOREACH(var, head, field) \
498 for ((var) = ((head)->tqh_first); \
499 (var); \
500 (var) = ((var)->field.tqe_next))
501
502 #define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
503 for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \
504 (var); \
505 (var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
506
507 /*
508 * Circular queue definitions.
509 */
510 #define CIRCLEQ_HEAD(name, type) \
511 struct name { \
512 struct type *cqh_first; /* first element */ \
513 struct type *cqh_last; /* last element */ \
514 }
515
516 #define CIRCLEQ_HEAD_INITIALIZER(head) \
517 { (void *)&head, (void *)&head }
518
519 #define CIRCLEQ_ENTRY(type) \
520 struct { \
521 struct type *cqe_next; /* next element */ \
522 struct type *cqe_prev; /* previous element */ \
523 }
524
525 /*
526 * Circular queue functions.
527 */
528 #define CIRCLEQ_INIT(head) do { \
529 (head)->cqh_first = (void *)(head); \
530 (head)->cqh_last = (void *)(head); \
531 } while (/*CONSTCOND*/0)
532
533 #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
534 (elm)->field.cqe_next = (listelm)->field.cqe_next; \
535 (elm)->field.cqe_prev = (listelm); \
536 if ((listelm)->field.cqe_next == (void *)(head)) \
537 (head)->cqh_last = (elm); \
538 else \
539 (listelm)->field.cqe_next->field.cqe_prev = (elm); \
540 (listelm)->field.cqe_next = (elm); \
541 } while (/*CONSTCOND*/0)
542
543 #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
544 (elm)->field.cqe_next = (listelm); \
545 (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
546 if ((listelm)->field.cqe_prev == (void *)(head)) \
547 (head)->cqh_first = (elm); \
548 else \
549 (listelm)->field.cqe_prev->field.cqe_next = (elm); \
550 (listelm)->field.cqe_prev = (elm); \
551 } while (/*CONSTCOND*/0)
552
553 #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
554 (elm)->field.cqe_next = (head)->cqh_first; \
555 (elm)->field.cqe_prev = (void *)(head); \
556 if ((head)->cqh_last == (void *)(head)) \
557 (head)->cqh_last = (elm); \
558 else \
559 (head)->cqh_first->field.cqe_prev = (elm); \
560 (head)->cqh_first = (elm); \
561 } while (/*CONSTCOND*/0)
562
563 #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
564 (elm)->field.cqe_next = (void *)(head); \
565 (elm)->field.cqe_prev = (head)->cqh_last; \
566 if ((head)->cqh_first == (void *)(head)) \
567 (head)->cqh_first = (elm); \
568 else \
569 (head)->cqh_last->field.cqe_next = (elm); \
570 (head)->cqh_last = (elm); \
571 } while (/*CONSTCOND*/0)
572
573 #define CIRCLEQ_REMOVE(head, elm, field) do { \
574 if ((elm)->field.cqe_next == (void *)(head)) \
575 (head)->cqh_last = (elm)->field.cqe_prev; \
576 else \
577 (elm)->field.cqe_next->field.cqe_prev = \
578 (elm)->field.cqe_prev; \
579 if ((elm)->field.cqe_prev == (void *)(head)) \
580 (head)->cqh_first = (elm)->field.cqe_next; \
581 else \
582 (elm)->field.cqe_prev->field.cqe_next = \
583 (elm)->field.cqe_next; \
584 } while (/*CONSTCOND*/0)
585
586 #define CIRCLEQ_FOREACH(var, head, field) \
587 for ((var) = ((head)->cqh_first); \
588 (var) != (void *)(head); \
589 (var) = ((var)->field.cqe_next))
590
591 #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
592 for ((var) = ((head)->cqh_last); \
593 (var) != (void *)(head); \
594 (var) = ((var)->field.cqe_prev))
595
596 /*
597 * Circular queue access methods.
598 */
599 #define CIRCLEQ_EMPTY(head) ((head)->cqh_first == (void *)(head))
600 #define CIRCLEQ_FIRST(head) ((head)->cqh_first)
601 #define CIRCLEQ_LAST(head) ((head)->cqh_last)
602 #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
603 #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
604 #endif /* !_SYS_QUEUE_H_ */
Cache object: 13fab2f22e74124090222d44ff93dc28
|