diff options
Diffstat (limited to 'openbsd-compat/sys-queue.h')
-rw-r--r-- | openbsd-compat/sys-queue.h | 375 |
1 files changed, 172 insertions, 203 deletions
diff --git a/openbsd-compat/sys-queue.h b/openbsd-compat/sys-queue.h index 5108f394c..816c15cd4 100644 --- a/openbsd-compat/sys-queue.h +++ b/openbsd-compat/sys-queue.h | |||
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: queue.h,v 1.36 2012/04/11 13:29:14 naddy Exp $ */ | 1 | /* $OpenBSD: queue.h,v 1.45 2018/07/12 14:22:54 sashan Exp $ */ |
2 | /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ | 2 | /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ |
3 | 3 | ||
4 | /* | 4 | /* |
@@ -41,94 +41,97 @@ | |||
41 | * Require for OS/X and other platforms that have old/broken/incomplete | 41 | * Require for OS/X and other platforms that have old/broken/incomplete |
42 | * <sys/queue.h>. | 42 | * <sys/queue.h>. |
43 | */ | 43 | */ |
44 | #undef SLIST_HEAD | 44 | #undef CIRCLEQ_EMPTY |
45 | #undef SLIST_HEAD_INITIALIZER | 45 | #undef CIRCLEQ_END |
46 | #undef SLIST_ENTRY | 46 | #undef CIRCLEQ_ENTRY |
47 | #undef SLIST_FOREACH_PREVPTR | 47 | #undef CIRCLEQ_FIRST |
48 | #undef SLIST_FOREACH_SAFE | 48 | #undef CIRCLEQ_FOREACH |
49 | #undef SLIST_FIRST | 49 | #undef CIRCLEQ_FOREACH_REVERSE |
50 | #undef SLIST_END | 50 | #undef CIRCLEQ_HEAD |
51 | #undef SLIST_EMPTY | 51 | #undef CIRCLEQ_HEAD_INITIALIZER |
52 | #undef SLIST_NEXT | 52 | #undef CIRCLEQ_INIT |
53 | #undef SLIST_FOREACH | 53 | #undef CIRCLEQ_INSERT_AFTER |
54 | #undef SLIST_INIT | 54 | #undef CIRCLEQ_INSERT_BEFORE |
55 | #undef SLIST_INSERT_AFTER | 55 | #undef CIRCLEQ_INSERT_HEAD |
56 | #undef SLIST_INSERT_HEAD | 56 | #undef CIRCLEQ_INSERT_TAIL |
57 | #undef SLIST_REMOVE_HEAD | 57 | #undef CIRCLEQ_LAST |
58 | #undef SLIST_REMOVE_AFTER | 58 | #undef CIRCLEQ_NEXT |
59 | #undef SLIST_REMOVE | 59 | #undef CIRCLEQ_PREV |
60 | #undef SLIST_REMOVE_NEXT | 60 | #undef CIRCLEQ_REMOVE |
61 | #undef LIST_HEAD | 61 | #undef CIRCLEQ_REPLACE |
62 | #undef LIST_HEAD_INITIALIZER | 62 | #undef LIST_EMPTY |
63 | #undef LIST_END | ||
63 | #undef LIST_ENTRY | 64 | #undef LIST_ENTRY |
64 | #undef LIST_FIRST | 65 | #undef LIST_FIRST |
65 | #undef LIST_END | ||
66 | #undef LIST_EMPTY | ||
67 | #undef LIST_NEXT | ||
68 | #undef LIST_FOREACH | 66 | #undef LIST_FOREACH |
69 | #undef LIST_FOREACH_SAFE | 67 | #undef LIST_FOREACH_SAFE |
68 | #undef LIST_HEAD | ||
69 | #undef LIST_HEAD_INITIALIZER | ||
70 | #undef LIST_INIT | 70 | #undef LIST_INIT |
71 | #undef LIST_INSERT_AFTER | 71 | #undef LIST_INSERT_AFTER |
72 | #undef LIST_INSERT_BEFORE | 72 | #undef LIST_INSERT_BEFORE |
73 | #undef LIST_INSERT_HEAD | 73 | #undef LIST_INSERT_HEAD |
74 | #undef LIST_NEXT | ||
74 | #undef LIST_REMOVE | 75 | #undef LIST_REMOVE |
75 | #undef LIST_REPLACE | 76 | #undef LIST_REPLACE |
76 | #undef SIMPLEQ_HEAD | 77 | #undef SIMPLEQ_CONCAT |
77 | #undef SIMPLEQ_HEAD_INITIALIZER | 78 | #undef SIMPLEQ_EMPTY |
79 | #undef SIMPLEQ_END | ||
78 | #undef SIMPLEQ_ENTRY | 80 | #undef SIMPLEQ_ENTRY |
79 | #undef SIMPLEQ_FIRST | 81 | #undef SIMPLEQ_FIRST |
80 | #undef SIMPLEQ_END | ||
81 | #undef SIMPLEQ_EMPTY | ||
82 | #undef SIMPLEQ_NEXT | ||
83 | #undef SIMPLEQ_FOREACH | 82 | #undef SIMPLEQ_FOREACH |
84 | #undef SIMPLEQ_FOREACH_SAFE | 83 | #undef SIMPLEQ_FOREACH_SAFE |
84 | #undef SIMPLEQ_HEAD | ||
85 | #undef SIMPLEQ_HEAD_INITIALIZER | ||
85 | #undef SIMPLEQ_INIT | 86 | #undef SIMPLEQ_INIT |
87 | #undef SIMPLEQ_INSERT_AFTER | ||
86 | #undef SIMPLEQ_INSERT_HEAD | 88 | #undef SIMPLEQ_INSERT_HEAD |
87 | #undef SIMPLEQ_INSERT_TAIL | 89 | #undef SIMPLEQ_INSERT_TAIL |
88 | #undef SIMPLEQ_INSERT_AFTER | 90 | #undef SIMPLEQ_NEXT |
91 | #undef SIMPLEQ_REMOVE_AFTER | ||
89 | #undef SIMPLEQ_REMOVE_HEAD | 92 | #undef SIMPLEQ_REMOVE_HEAD |
90 | #undef TAILQ_HEAD | 93 | #undef SLIST_EMPTY |
91 | #undef TAILQ_HEAD_INITIALIZER | 94 | #undef SLIST_END |
95 | #undef SLIST_ENTRY | ||
96 | #undef SLIST_FIRST | ||
97 | #undef SLIST_FOREACH | ||
98 | #undef SLIST_FOREACH_PREVPTR | ||
99 | #undef SLIST_FOREACH_SAFE | ||
100 | #undef SLIST_HEAD | ||
101 | #undef SLIST_HEAD_INITIALIZER | ||
102 | #undef SLIST_INIT | ||
103 | #undef SLIST_INSERT_AFTER | ||
104 | #undef SLIST_INSERT_HEAD | ||
105 | #undef SLIST_NEXT | ||
106 | #undef SLIST_REMOVE | ||
107 | #undef SLIST_REMOVE_AFTER | ||
108 | #undef SLIST_REMOVE_HEAD | ||
109 | #undef SLIST_REMOVE_NEXT | ||
110 | #undef TAILQ_CONCAT | ||
111 | #undef TAILQ_EMPTY | ||
112 | #undef TAILQ_END | ||
92 | #undef TAILQ_ENTRY | 113 | #undef TAILQ_ENTRY |
93 | #undef TAILQ_FIRST | 114 | #undef TAILQ_FIRST |
94 | #undef TAILQ_END | ||
95 | #undef TAILQ_NEXT | ||
96 | #undef TAILQ_LAST | ||
97 | #undef TAILQ_PREV | ||
98 | #undef TAILQ_EMPTY | ||
99 | #undef TAILQ_FOREACH | 115 | #undef TAILQ_FOREACH |
100 | #undef TAILQ_FOREACH_REVERSE | 116 | #undef TAILQ_FOREACH_REVERSE |
101 | #undef TAILQ_FOREACH_SAFE | ||
102 | #undef TAILQ_FOREACH_REVERSE_SAFE | 117 | #undef TAILQ_FOREACH_REVERSE_SAFE |
118 | #undef TAILQ_FOREACH_SAFE | ||
119 | #undef TAILQ_HEAD | ||
120 | #undef TAILQ_HEAD_INITIALIZER | ||
103 | #undef TAILQ_INIT | 121 | #undef TAILQ_INIT |
104 | #undef TAILQ_INSERT_HEAD | ||
105 | #undef TAILQ_INSERT_TAIL | ||
106 | #undef TAILQ_INSERT_AFTER | 122 | #undef TAILQ_INSERT_AFTER |
107 | #undef TAILQ_INSERT_BEFORE | 123 | #undef TAILQ_INSERT_BEFORE |
124 | #undef TAILQ_INSERT_HEAD | ||
125 | #undef TAILQ_INSERT_TAIL | ||
126 | #undef TAILQ_LAST | ||
127 | #undef TAILQ_NEXT | ||
128 | #undef TAILQ_PREV | ||
108 | #undef TAILQ_REMOVE | 129 | #undef TAILQ_REMOVE |
109 | #undef TAILQ_REPLACE | 130 | #undef TAILQ_REPLACE |
110 | #undef CIRCLEQ_HEAD | ||
111 | #undef CIRCLEQ_HEAD_INITIALIZER | ||
112 | #undef CIRCLEQ_ENTRY | ||
113 | #undef CIRCLEQ_FIRST | ||
114 | #undef CIRCLEQ_LAST | ||
115 | #undef CIRCLEQ_END | ||
116 | #undef CIRCLEQ_NEXT | ||
117 | #undef CIRCLEQ_PREV | ||
118 | #undef CIRCLEQ_EMPTY | ||
119 | #undef CIRCLEQ_FOREACH | ||
120 | #undef CIRCLEQ_FOREACH_REVERSE | ||
121 | #undef CIRCLEQ_INIT | ||
122 | #undef CIRCLEQ_INSERT_AFTER | ||
123 | #undef CIRCLEQ_INSERT_BEFORE | ||
124 | #undef CIRCLEQ_INSERT_HEAD | ||
125 | #undef CIRCLEQ_INSERT_TAIL | ||
126 | #undef CIRCLEQ_REMOVE | ||
127 | #undef CIRCLEQ_REPLACE | ||
128 | 131 | ||
129 | /* | 132 | /* |
130 | * This file defines five types of data structures: singly-linked lists, | 133 | * This file defines five types of data structures: singly-linked lists, |
131 | * lists, simple queues, tail queues, and circular queues. | 134 | * lists, simple queues, tail queues and XOR simple queues. |
132 | * | 135 | * |
133 | * | 136 | * |
134 | * A singly-linked list is headed by a single forward pointer. The elements | 137 | * A singly-linked list is headed by a single forward pointer. The elements |
@@ -148,7 +151,7 @@ | |||
148 | * or after an existing element or at the head of the list. A list | 151 | * or after an existing element or at the head of the list. A list |
149 | * may only be traversed in the forward direction. | 152 | * may only be traversed in the forward direction. |
150 | * | 153 | * |
151 | * A simple queue is headed by a pair of pointers, one the head of the | 154 | * A simple queue is headed by a pair of pointers, one to the head of the |
152 | * list and the other to the tail of the list. The elements are singly | 155 | * list and the other to the tail of the list. The elements are singly |
153 | * linked to save space, so elements can only be removed from the | 156 | * linked to save space, so elements can only be removed from the |
154 | * head of the list. New elements can be added to the list before or after | 157 | * head of the list. New elements can be added to the list before or after |
@@ -162,19 +165,17 @@ | |||
162 | * after an existing element, at the head of the list, or at the end of | 165 | * after an existing element, at the head of the list, or at the end of |
163 | * the list. A tail queue may be traversed in either direction. | 166 | * the list. A tail queue may be traversed in either direction. |
164 | * | 167 | * |
165 | * A circle queue is headed by a pair of pointers, one to the head of the | 168 | * An XOR simple queue is used in the same way as a regular simple queue. |
166 | * list and the other to the tail of the list. The elements are doubly | 169 | * The difference is that the head structure also includes a "cookie" that |
167 | * linked so that an arbitrary element can be removed without a need to | 170 | * is XOR'd with the queue pointer (first, last or next) to generate the |
168 | * traverse the list. New elements can be added to the list before or after | 171 | * real pointer value. |
169 | * an existing element, at the head of the list, or at the end of the list. | ||
170 | * A circle queue may be traversed in either direction, but has a more | ||
171 | * complex end of list detection. | ||
172 | * | 172 | * |
173 | * For details on the use of these macros, see the queue(3) manual page. | 173 | * For details on the use of these macros, see the queue(3) manual page. |
174 | */ | 174 | */ |
175 | 175 | ||
176 | #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) | 176 | #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) |
177 | #define _Q_INVALIDATE(a) (a) = ((void *)-1) | 177 | #define _Q_INVALID ((void *)-1) |
178 | #define _Q_INVALIDATE(a) (a) = _Q_INVALID | ||
178 | #else | 179 | #else |
179 | #define _Q_INVALIDATE(a) | 180 | #define _Q_INVALIDATE(a) |
180 | #endif | 181 | #endif |
@@ -186,15 +187,15 @@ | |||
186 | struct name { \ | 187 | struct name { \ |
187 | struct type *slh_first; /* first element */ \ | 188 | struct type *slh_first; /* first element */ \ |
188 | } | 189 | } |
189 | 190 | ||
190 | #define SLIST_HEAD_INITIALIZER(head) \ | 191 | #define SLIST_HEAD_INITIALIZER(head) \ |
191 | { NULL } | 192 | { NULL } |
192 | 193 | ||
193 | #define SLIST_ENTRY(type) \ | 194 | #define SLIST_ENTRY(type) \ |
194 | struct { \ | 195 | struct { \ |
195 | struct type *sle_next; /* next element */ \ | 196 | struct type *sle_next; /* next element */ \ |
196 | } | 197 | } |
197 | 198 | ||
198 | /* | 199 | /* |
199 | * Singly-linked List access methods. | 200 | * Singly-linked List access methods. |
200 | */ | 201 | */ |
@@ -248,8 +249,8 @@ struct { \ | |||
248 | curelm = curelm->field.sle_next; \ | 249 | curelm = curelm->field.sle_next; \ |
249 | curelm->field.sle_next = \ | 250 | curelm->field.sle_next = \ |
250 | curelm->field.sle_next->field.sle_next; \ | 251 | curelm->field.sle_next->field.sle_next; \ |
251 | _Q_INVALIDATE((elm)->field.sle_next); \ | ||
252 | } \ | 252 | } \ |
253 | _Q_INVALIDATE((elm)->field.sle_next); \ | ||
253 | } while (0) | 254 | } while (0) |
254 | 255 | ||
255 | /* | 256 | /* |
@@ -270,7 +271,7 @@ struct { \ | |||
270 | } | 271 | } |
271 | 272 | ||
272 | /* | 273 | /* |
273 | * List access methods | 274 | * List access methods. |
274 | */ | 275 | */ |
275 | #define LIST_FIRST(head) ((head)->lh_first) | 276 | #define LIST_FIRST(head) ((head)->lh_first) |
276 | #define LIST_END(head) NULL | 277 | #define LIST_END(head) NULL |
@@ -407,6 +408,94 @@ struct { \ | |||
407 | (head)->sqh_last = &(elm)->field.sqe_next; \ | 408 | (head)->sqh_last = &(elm)->field.sqe_next; \ |
408 | } while (0) | 409 | } while (0) |
409 | 410 | ||
411 | #define SIMPLEQ_CONCAT(head1, head2) do { \ | ||
412 | if (!SIMPLEQ_EMPTY((head2))) { \ | ||
413 | *(head1)->sqh_last = (head2)->sqh_first; \ | ||
414 | (head1)->sqh_last = (head2)->sqh_last; \ | ||
415 | SIMPLEQ_INIT((head2)); \ | ||
416 | } \ | ||
417 | } while (0) | ||
418 | |||
419 | /* | ||
420 | * XOR Simple queue definitions. | ||
421 | */ | ||
422 | #define XSIMPLEQ_HEAD(name, type) \ | ||
423 | struct name { \ | ||
424 | struct type *sqx_first; /* first element */ \ | ||
425 | struct type **sqx_last; /* addr of last next element */ \ | ||
426 | unsigned long sqx_cookie; \ | ||
427 | } | ||
428 | |||
429 | #define XSIMPLEQ_ENTRY(type) \ | ||
430 | struct { \ | ||
431 | struct type *sqx_next; /* next element */ \ | ||
432 | } | ||
433 | |||
434 | /* | ||
435 | * XOR Simple queue access methods. | ||
436 | */ | ||
437 | #define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \ | ||
438 | (unsigned long)(ptr))) | ||
439 | #define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first)) | ||
440 | #define XSIMPLEQ_END(head) NULL | ||
441 | #define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head)) | ||
442 | #define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next)) | ||
443 | |||
444 | |||
445 | #define XSIMPLEQ_FOREACH(var, head, field) \ | ||
446 | for ((var) = XSIMPLEQ_FIRST(head); \ | ||
447 | (var) != XSIMPLEQ_END(head); \ | ||
448 | (var) = XSIMPLEQ_NEXT(head, var, field)) | ||
449 | |||
450 | #define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ | ||
451 | for ((var) = XSIMPLEQ_FIRST(head); \ | ||
452 | (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \ | ||
453 | (var) = (tvar)) | ||
454 | |||
455 | /* | ||
456 | * XOR Simple queue functions. | ||
457 | */ | ||
458 | #define XSIMPLEQ_INIT(head) do { \ | ||
459 | arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \ | ||
460 | (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \ | ||
461 | (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \ | ||
462 | } while (0) | ||
463 | |||
464 | #define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \ | ||
465 | if (((elm)->field.sqx_next = (head)->sqx_first) == \ | ||
466 | XSIMPLEQ_XOR(head, NULL)) \ | ||
467 | (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ | ||
468 | (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \ | ||
469 | } while (0) | ||
470 | |||
471 | #define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \ | ||
472 | (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \ | ||
473 | *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \ | ||
474 | (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ | ||
475 | } while (0) | ||
476 | |||
477 | #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ | ||
478 | if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \ | ||
479 | XSIMPLEQ_XOR(head, NULL)) \ | ||
480 | (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ | ||
481 | (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \ | ||
482 | } while (0) | ||
483 | |||
484 | #define XSIMPLEQ_REMOVE_HEAD(head, field) do { \ | ||
485 | if (((head)->sqx_first = XSIMPLEQ_XOR(head, \ | ||
486 | (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \ | ||
487 | (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \ | ||
488 | } while (0) | ||
489 | |||
490 | #define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ | ||
491 | if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \ | ||
492 | (elm)->field.sqx_next)->field.sqx_next) \ | ||
493 | == XSIMPLEQ_XOR(head, NULL)) \ | ||
494 | (head)->sqx_last = \ | ||
495 | XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ | ||
496 | } while (0) | ||
497 | |||
498 | |||
410 | /* | 499 | /* |
411 | * Tail queue definitions. | 500 | * Tail queue definitions. |
412 | */ | 501 | */ |
@@ -425,8 +514,8 @@ struct { \ | |||
425 | struct type **tqe_prev; /* address of previous next element */ \ | 514 | struct type **tqe_prev; /* address of previous next element */ \ |
426 | } | 515 | } |
427 | 516 | ||
428 | /* | 517 | /* |
429 | * tail queue access methods | 518 | * Tail queue access methods. |
430 | */ | 519 | */ |
431 | #define TAILQ_FIRST(head) ((head)->tqh_first) | 520 | #define TAILQ_FIRST(head) ((head)->tqh_first) |
432 | #define TAILQ_END(head) NULL | 521 | #define TAILQ_END(head) NULL |
@@ -527,133 +616,13 @@ struct { \ | |||
527 | _Q_INVALIDATE((elm)->field.tqe_next); \ | 616 | _Q_INVALIDATE((elm)->field.tqe_next); \ |
528 | } while (0) | 617 | } while (0) |
529 | 618 | ||
530 | /* | 619 | #define TAILQ_CONCAT(head1, head2, field) do { \ |
531 | * Circular queue definitions. | 620 | if (!TAILQ_EMPTY(head2)) { \ |
532 | */ | 621 | *(head1)->tqh_last = (head2)->tqh_first; \ |
533 | #define CIRCLEQ_HEAD(name, type) \ | 622 | (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ |
534 | struct name { \ | 623 | (head1)->tqh_last = (head2)->tqh_last; \ |
535 | struct type *cqh_first; /* first element */ \ | 624 | TAILQ_INIT((head2)); \ |
536 | struct type *cqh_last; /* last element */ \ | 625 | } \ |
537 | } | ||
538 | |||
539 | #define CIRCLEQ_HEAD_INITIALIZER(head) \ | ||
540 | { CIRCLEQ_END(&head), CIRCLEQ_END(&head) } | ||
541 | |||
542 | #define CIRCLEQ_ENTRY(type) \ | ||
543 | struct { \ | ||
544 | struct type *cqe_next; /* next element */ \ | ||
545 | struct type *cqe_prev; /* previous element */ \ | ||
546 | } | ||
547 | |||
548 | /* | ||
549 | * Circular queue access methods | ||
550 | */ | ||
551 | #define CIRCLEQ_FIRST(head) ((head)->cqh_first) | ||
552 | #define CIRCLEQ_LAST(head) ((head)->cqh_last) | ||
553 | #define CIRCLEQ_END(head) ((void *)(head)) | ||
554 | #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) | ||
555 | #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) | ||
556 | #define CIRCLEQ_EMPTY(head) \ | ||
557 | (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head)) | ||
558 | |||
559 | #define CIRCLEQ_FOREACH(var, head, field) \ | ||
560 | for((var) = CIRCLEQ_FIRST(head); \ | ||
561 | (var) != CIRCLEQ_END(head); \ | ||
562 | (var) = CIRCLEQ_NEXT(var, field)) | ||
563 | |||
564 | #define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \ | ||
565 | for ((var) = CIRCLEQ_FIRST(head); \ | ||
566 | (var) != CIRCLEQ_END(head) && \ | ||
567 | ((tvar) = CIRCLEQ_NEXT(var, field), 1); \ | ||
568 | (var) = (tvar)) | ||
569 | |||
570 | #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ | ||
571 | for((var) = CIRCLEQ_LAST(head); \ | ||
572 | (var) != CIRCLEQ_END(head); \ | ||
573 | (var) = CIRCLEQ_PREV(var, field)) | ||
574 | |||
575 | #define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ | ||
576 | for ((var) = CIRCLEQ_LAST(head, headname); \ | ||
577 | (var) != CIRCLEQ_END(head) && \ | ||
578 | ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \ | ||
579 | (var) = (tvar)) | ||
580 | |||
581 | /* | ||
582 | * Circular queue functions. | ||
583 | */ | ||
584 | #define CIRCLEQ_INIT(head) do { \ | ||
585 | (head)->cqh_first = CIRCLEQ_END(head); \ | ||
586 | (head)->cqh_last = CIRCLEQ_END(head); \ | ||
587 | } while (0) | ||
588 | |||
589 | #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ | ||
590 | (elm)->field.cqe_next = (listelm)->field.cqe_next; \ | ||
591 | (elm)->field.cqe_prev = (listelm); \ | ||
592 | if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \ | ||
593 | (head)->cqh_last = (elm); \ | ||
594 | else \ | ||
595 | (listelm)->field.cqe_next->field.cqe_prev = (elm); \ | ||
596 | (listelm)->field.cqe_next = (elm); \ | ||
597 | } while (0) | ||
598 | |||
599 | #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ | ||
600 | (elm)->field.cqe_next = (listelm); \ | ||
601 | (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ | ||
602 | if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \ | ||
603 | (head)->cqh_first = (elm); \ | ||
604 | else \ | ||
605 | (listelm)->field.cqe_prev->field.cqe_next = (elm); \ | ||
606 | (listelm)->field.cqe_prev = (elm); \ | ||
607 | } while (0) | ||
608 | |||
609 | #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ | ||
610 | (elm)->field.cqe_next = (head)->cqh_first; \ | ||
611 | (elm)->field.cqe_prev = CIRCLEQ_END(head); \ | ||
612 | if ((head)->cqh_last == CIRCLEQ_END(head)) \ | ||
613 | (head)->cqh_last = (elm); \ | ||
614 | else \ | ||
615 | (head)->cqh_first->field.cqe_prev = (elm); \ | ||
616 | (head)->cqh_first = (elm); \ | ||
617 | } while (0) | ||
618 | |||
619 | #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ | ||
620 | (elm)->field.cqe_next = CIRCLEQ_END(head); \ | ||
621 | (elm)->field.cqe_prev = (head)->cqh_last; \ | ||
622 | if ((head)->cqh_first == CIRCLEQ_END(head)) \ | ||
623 | (head)->cqh_first = (elm); \ | ||
624 | else \ | ||
625 | (head)->cqh_last->field.cqe_next = (elm); \ | ||
626 | (head)->cqh_last = (elm); \ | ||
627 | } while (0) | ||
628 | |||
629 | #define CIRCLEQ_REMOVE(head, elm, field) do { \ | ||
630 | if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \ | ||
631 | (head)->cqh_last = (elm)->field.cqe_prev; \ | ||
632 | else \ | ||
633 | (elm)->field.cqe_next->field.cqe_prev = \ | ||
634 | (elm)->field.cqe_prev; \ | ||
635 | if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \ | ||
636 | (head)->cqh_first = (elm)->field.cqe_next; \ | ||
637 | else \ | ||
638 | (elm)->field.cqe_prev->field.cqe_next = \ | ||
639 | (elm)->field.cqe_next; \ | ||
640 | _Q_INVALIDATE((elm)->field.cqe_prev); \ | ||
641 | _Q_INVALIDATE((elm)->field.cqe_next); \ | ||
642 | } while (0) | ||
643 | |||
644 | #define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \ | ||
645 | if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \ | ||
646 | CIRCLEQ_END(head)) \ | ||
647 | (head).cqh_last = (elm2); \ | ||
648 | else \ | ||
649 | (elm2)->field.cqe_next->field.cqe_prev = (elm2); \ | ||
650 | if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \ | ||
651 | CIRCLEQ_END(head)) \ | ||
652 | (head).cqh_first = (elm2); \ | ||
653 | else \ | ||
654 | (elm2)->field.cqe_prev->field.cqe_next = (elm2); \ | ||
655 | _Q_INVALIDATE((elm)->field.cqe_prev); \ | ||
656 | _Q_INVALIDATE((elm)->field.cqe_next); \ | ||
657 | } while (0) | 626 | } while (0) |
658 | 627 | ||
659 | #endif /* !_FAKE_QUEUE_H_ */ | 628 | #endif /* !_SYS_QUEUE_H_ */ |