summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--openbsd-compat/sys-queue.h260
1 files changed, 113 insertions, 147 deletions
diff --git a/openbsd-compat/sys-queue.h b/openbsd-compat/sys-queue.h
index 5108f394c..a171f8b55 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/*
@@ -127,8 +127,8 @@
127#undef CIRCLEQ_REPLACE 127#undef CIRCLEQ_REPLACE
128 128
129/* 129/*
130 * This file defines five types of data structures: singly-linked lists, 130 * This file defines five types of data structures: singly-linked lists,
131 * lists, simple queues, tail queues, and circular queues. 131 * lists, simple queues, tail queues and XOR simple queues.
132 * 132 *
133 * 133 *
134 * A singly-linked list is headed by a single forward pointer. The elements 134 * A singly-linked list is headed by a single forward pointer. The elements
@@ -148,7 +148,7 @@
148 * or after an existing element or at the head of the list. A list 148 * or after an existing element or at the head of the list. A list
149 * may only be traversed in the forward direction. 149 * may only be traversed in the forward direction.
150 * 150 *
151 * A simple queue is headed by a pair of pointers, one the head of the 151 * 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 152 * 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 153 * 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 154 * head of the list. New elements can be added to the list before or after
@@ -162,19 +162,17 @@
162 * after an existing element, at the head of the list, or at the end of 162 * 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. 163 * the list. A tail queue may be traversed in either direction.
164 * 164 *
165 * A circle queue is headed by a pair of pointers, one to the head of the 165 * 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 166 * 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 167 * 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 168 * 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 * 169 *
173 * For details on the use of these macros, see the queue(3) manual page. 170 * For details on the use of these macros, see the queue(3) manual page.
174 */ 171 */
175 172
176#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) 173#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
177#define _Q_INVALIDATE(a) (a) = ((void *)-1) 174#define _Q_INVALID ((void *)-1)
175#define _Q_INVALIDATE(a) (a) = _Q_INVALID
178#else 176#else
179#define _Q_INVALIDATE(a) 177#define _Q_INVALIDATE(a)
180#endif 178#endif
@@ -186,15 +184,15 @@
186struct name { \ 184struct name { \
187 struct type *slh_first; /* first element */ \ 185 struct type *slh_first; /* first element */ \
188} 186}
189 187
190#define SLIST_HEAD_INITIALIZER(head) \ 188#define SLIST_HEAD_INITIALIZER(head) \
191 { NULL } 189 { NULL }
192 190
193#define SLIST_ENTRY(type) \ 191#define SLIST_ENTRY(type) \
194struct { \ 192struct { \
195 struct type *sle_next; /* next element */ \ 193 struct type *sle_next; /* next element */ \
196} 194}
197 195
198/* 196/*
199 * Singly-linked List access methods. 197 * Singly-linked List access methods.
200 */ 198 */
@@ -248,8 +246,8 @@ struct { \
248 curelm = curelm->field.sle_next; \ 246 curelm = curelm->field.sle_next; \
249 curelm->field.sle_next = \ 247 curelm->field.sle_next = \
250 curelm->field.sle_next->field.sle_next; \ 248 curelm->field.sle_next->field.sle_next; \
251 _Q_INVALIDATE((elm)->field.sle_next); \
252 } \ 249 } \
250 _Q_INVALIDATE((elm)->field.sle_next); \
253} while (0) 251} while (0)
254 252
255/* 253/*
@@ -270,7 +268,7 @@ struct { \
270} 268}
271 269
272/* 270/*
273 * List access methods 271 * List access methods.
274 */ 272 */
275#define LIST_FIRST(head) ((head)->lh_first) 273#define LIST_FIRST(head) ((head)->lh_first)
276#define LIST_END(head) NULL 274#define LIST_END(head) NULL
@@ -407,6 +405,94 @@ struct { \
407 (head)->sqh_last = &(elm)->field.sqe_next; \ 405 (head)->sqh_last = &(elm)->field.sqe_next; \
408} while (0) 406} while (0)
409 407
408#define SIMPLEQ_CONCAT(head1, head2) do { \
409 if (!SIMPLEQ_EMPTY((head2))) { \
410 *(head1)->sqh_last = (head2)->sqh_first; \
411 (head1)->sqh_last = (head2)->sqh_last; \
412 SIMPLEQ_INIT((head2)); \
413 } \
414} while (0)
415
416/*
417 * XOR Simple queue definitions.
418 */
419#define XSIMPLEQ_HEAD(name, type) \
420struct name { \
421 struct type *sqx_first; /* first element */ \
422 struct type **sqx_last; /* addr of last next element */ \
423 unsigned long sqx_cookie; \
424}
425
426#define XSIMPLEQ_ENTRY(type) \
427struct { \
428 struct type *sqx_next; /* next element */ \
429}
430
431/*
432 * XOR Simple queue access methods.
433 */
434#define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \
435 (unsigned long)(ptr)))
436#define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first))
437#define XSIMPLEQ_END(head) NULL
438#define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
439#define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
440
441
442#define XSIMPLEQ_FOREACH(var, head, field) \
443 for ((var) = XSIMPLEQ_FIRST(head); \
444 (var) != XSIMPLEQ_END(head); \
445 (var) = XSIMPLEQ_NEXT(head, var, field))
446
447#define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
448 for ((var) = XSIMPLEQ_FIRST(head); \
449 (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \
450 (var) = (tvar))
451
452/*
453 * XOR Simple queue functions.
454 */
455#define XSIMPLEQ_INIT(head) do { \
456 arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
457 (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \
458 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
459} while (0)
460
461#define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
462 if (((elm)->field.sqx_next = (head)->sqx_first) == \
463 XSIMPLEQ_XOR(head, NULL)) \
464 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
465 (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \
466} while (0)
467
468#define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
469 (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \
470 *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
471 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
472} while (0)
473
474#define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
475 if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \
476 XSIMPLEQ_XOR(head, NULL)) \
477 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
478 (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \
479} while (0)
480
481#define XSIMPLEQ_REMOVE_HEAD(head, field) do { \
482 if (((head)->sqx_first = XSIMPLEQ_XOR(head, \
483 (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
484 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
485} while (0)
486
487#define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
488 if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \
489 (elm)->field.sqx_next)->field.sqx_next) \
490 == XSIMPLEQ_XOR(head, NULL)) \
491 (head)->sqx_last = \
492 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
493} while (0)
494
495
410/* 496/*
411 * Tail queue definitions. 497 * Tail queue definitions.
412 */ 498 */
@@ -425,8 +511,8 @@ struct { \
425 struct type **tqe_prev; /* address of previous next element */ \ 511 struct type **tqe_prev; /* address of previous next element */ \
426} 512}
427 513
428/* 514/*
429 * tail queue access methods 515 * Tail queue access methods.
430 */ 516 */
431#define TAILQ_FIRST(head) ((head)->tqh_first) 517#define TAILQ_FIRST(head) ((head)->tqh_first)
432#define TAILQ_END(head) NULL 518#define TAILQ_END(head) NULL
@@ -527,133 +613,13 @@ struct { \
527 _Q_INVALIDATE((elm)->field.tqe_next); \ 613 _Q_INVALIDATE((elm)->field.tqe_next); \
528} while (0) 614} while (0)
529 615
530/* 616#define TAILQ_CONCAT(head1, head2, field) do { \
531 * Circular queue definitions. 617 if (!TAILQ_EMPTY(head2)) { \
532 */ 618 *(head1)->tqh_last = (head2)->tqh_first; \
533#define CIRCLEQ_HEAD(name, type) \ 619 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
534struct name { \ 620 (head1)->tqh_last = (head2)->tqh_last; \
535 struct type *cqh_first; /* first element */ \ 621 TAILQ_INIT((head2)); \
536 struct type *cqh_last; /* last element */ \ 622 } \
537}
538
539#define CIRCLEQ_HEAD_INITIALIZER(head) \
540 { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
541
542#define CIRCLEQ_ENTRY(type) \
543struct { \
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) 623} while (0)
658 624
659#endif /* !_FAKE_QUEUE_H_ */ 625#endif /* !_SYS_QUEUE_H_ */