1 files changed, 490 insertions, 0 deletions
diff --git a/other/ssharp/openbsd-compat/fake-queue.h b/other/ssharp/openbsd-compat/fake-queue.h
new file mode 100644
index 0000000..269af41
--- /dev/null
+++ b/other/ssharp/openbsd-compat/fake-queue.h
@@ -0,0 +1,490 @@
+/*      $OpenBSD: queue.h,v 1.16 2000/09/07 19:47:59 art Exp $  */
+/*      $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $       */
+/*
+ * Copyright (c) 1991, 1993
+ *      The Regents of the University of California.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *      This product includes software developed by the University of
+ *      California, Berkeley and its contributors.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ *
+ *      @(#)queue.h     8.5 (Berkeley) 8/20/94
+ */
+#ifndef _SYS_QUEUE_H_
+#define _SYS_QUEUE_H_
+/*
+ * This file defines five types of data structures: singly-linked lists, 
+ * lists, simple queues, tail queues, and circular queues.
+ *
+ *
+ * A singly-linked list is headed by a single forward pointer. The elements
+ * are singly linked for minimum space and pointer manipulation overhead at
+ * the expense of O(n) removal for arbitrary elements. New elements can be
+ * added to the list after an existing element or at the head of the list.
+ * Elements being removed from the head of the list should use the explicit
+ * macro for this purpose for optimum efficiency. A singly-linked list may
+ * only be traversed in the forward direction.  Singly-linked lists are ideal
+ * for applications with large datasets and few or no removals or for
+ * implementing a LIFO queue.
+ *
+ * A list is headed by a single forward pointer (or an array of forward
+ * pointers for a hash table header). The elements are doubly linked
+ * so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before
+ * or after an existing element or at the head of the list. A list
+ * may only be traversed in the forward direction.
+ *
+ * A simple queue is headed by a pair of pointers, one the head of the
+ * list and the other to the tail of the list. The elements are singly
+ * linked to save space, so elements can only be removed from the
+ * head of the list. New elements can be added to the list before or after
+ * an existing element, at the head of the list, or at the end of the
+ * list. A simple queue may only be traversed in the forward direction.
+ *
+ * A tail queue is headed by a pair of pointers, one to the head of the
+ * list and the other to the tail of the list. The elements are doubly
+ * linked so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before or
+ * after an existing element, at the head of the list, or at the end of
+ * the list. A tail queue may be traversed in either direction.
+ *
+ * A circle queue is headed by a pair of pointers, one to the head of the
+ * list and the other to the tail of the list. The elements are doubly
+ * linked so that an arbitrary element can be removed without a need to
+ * traverse the list. New elements can be added to the list before or after
+ * an existing element, at the head of the list, or at the end of the list.
+ * A circle queue may be traversed in either direction, but has a more
+ * complex end of list detection.
+ *
+ * For details on the use of these macros, see the queue(3) manual page.
+ */
+/*
+ * Singly-linked List definitions.
+ */
+#define SLIST_HEAD(name, type)                                          \
+struct name {                                                           \
+        struct type *slh_first; /* first element */                     \
+}
+ 
+#define SLIST_HEAD_INITIALIZER(head)                                    \
+        { NULL }
+ 
+#define SLIST_ENTRY(type)                                               \
+struct {                                                                \
+        struct type *sle_next;  /* next element */                      \
+}
+ 
+/*
+ * Singly-linked List access methods.
+ */
+#define SLIST_FIRST(head)       ((head)->slh_first)
+#define SLIST_END(head)         NULL
+#define SLIST_EMPTY(head)       (SLIST_FIRST(head) == SLIST_END(head))
+#define SLIST_NEXT(elm, field)  ((elm)->field.sle_next)
+#define SLIST_FOREACH(var, head, field)                                 \
+        for((var) = SLIST_FIRST(head);                                  \
+            (var) != SLIST_END(head);                                   \
+            (var) = SLIST_NEXT(var, field))
+/*
+ * Singly-linked List functions.
+ */
+#define SLIST_INIT(head) {                                              \
+        SLIST_FIRST(head) = SLIST_END(head);                            \
+}
+#define SLIST_INSERT_AFTER(slistelm, elm, field) do {                   \
+        (elm)->field.sle_next = (slistelm)->field.sle_next;             \
+        (slistelm)->field.sle_next = (elm);                             \
+} while (0)
+#define SLIST_INSERT_HEAD(head, elm, field) do {                        \
+        (elm)->field.sle_next = (head)->slh_first;                      \
+        (head)->slh_first = (elm);                                      \
+} while (0)
+#define SLIST_REMOVE_HEAD(head, field) do {                             \
+        (head)->slh_first = (head)->slh_first->field.sle_next;          \
+} while (0)
+/*
+ * List definitions.
+ */
+#define LIST_HEAD(name, type)                                           \
+struct name {                                                           \
+        struct type *lh_first;  /* first element */                     \
+}
+#define LIST_HEAD_INITIALIZER(head)                                     \
+        { NULL }
+#define LIST_ENTRY(type)                                                \
+struct {                                                                \
+        struct type *le_next;   /* next element */                      \
+        struct type **le_prev;  /* address of previous next element */  \
+}
+/*
+ * List access methods
+ */
+#define LIST_FIRST(head)                ((head)->lh_first)
+#define LIST_END(head)                  NULL
+#define LIST_EMPTY(head)                (LIST_FIRST(head) == LIST_END(head))
+#define LIST_NEXT(elm, field)           ((elm)->field.le_next)
+#define LIST_FOREACH(var, head, field)                                  \
+        for((var) = LIST_FIRST(head);                                   \
+            (var)!= LIST_END(head);                                     \
+            (var) = LIST_NEXT(var, field))
+/*
+ * List functions.
+ */
+#define LIST_INIT(head) do {                                            \
+        LIST_FIRST(head) = LIST_END(head);                              \
+} while (0)
+#define LIST_INSERT_AFTER(listelm, elm, field) do {                     \
+        if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)  \
+                (listelm)->field.le_next->field.le_prev =               \
+                    &(elm)->field.le_next;                              \
+        (listelm)->field.le_next = (elm);                               \
+        (elm)->field.le_prev = &(listelm)->field.le_next;               \
+} while (0)
+#define LIST_INSERT_BEFORE(listelm, elm, field) do {                    \
+        (elm)->field.le_prev = (listelm)->field.le_prev;                \
+        (elm)->field.le_next = (listelm);                               \
+        *(listelm)->field.le_prev = (elm);                              \
+        (listelm)->field.le_prev = &(elm)->field.le_next;               \
+} while (0)
+#define LIST_INSERT_HEAD(head, elm, field) do {                         \
+        if (((elm)->field.le_next = (head)->lh_first) != NULL)          \
+                (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
+        (head)->lh_first = (elm);                                       \
+        (elm)->field.le_prev = &(head)->lh_first;                       \
+} while (0)
+#define LIST_REMOVE(elm, field) do {                                    \
+        if ((elm)->field.le_next != NULL)                               \
+                (elm)->field.le_next->field.le_prev =                   \
+                    (elm)->field.le_prev;                               \
+        *(elm)->field.le_prev = (elm)->field.le_next;                   \
+} while (0)
+#define LIST_REPLACE(elm, elm2, field) do {                             \
+        if (((elm2)->field.le_next = (elm)->field.le_next) != NULL)     \
+                (elm2)->field.le_next->field.le_prev =                  \
+                    &(elm2)->field.le_next;                             \
+        (elm2)->field.le_prev = (elm)->field.le_prev;                   \
+        *(elm2)->field.le_prev = (elm2);                                \
+} while (0)
+/*
+ * Simple queue definitions.
+ */
+#define SIMPLEQ_HEAD(name, type)                                        \
+struct name {                                                           \
+        struct type *sqh_first; /* first element */                     \
+        struct type **sqh_last; /* addr of last next element */         \
+}
+#define SIMPLEQ_HEAD_INITIALIZER(head)                                  \
+        { NULL, &(head).sqh_first }
+#define SIMPLEQ_ENTRY(type)                                             \
+struct {                                                                \
+        struct type *sqe_next;  /* next element */                      \
+}
+/*
+ * Simple queue access methods.
+ */
+#define SIMPLEQ_FIRST(head)         ((head)->sqh_first)
+#define SIMPLEQ_END(head)           NULL
+#define SIMPLEQ_EMPTY(head)         (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
+#define SIMPLEQ_NEXT(elm, field)    ((elm)->field.sqe_next)
+#define SIMPLEQ_FOREACH(var, head, field)                               \
+        for((var) = SIMPLEQ_FIRST(head);                                \
+            (var) != SIMPLEQ_END(head);                                 \
+            (var) = SIMPLEQ_NEXT(var, field))
+/*
+ * Simple queue functions.
+ */
+#define SIMPLEQ_INIT(head) do {                                         \
+        (head)->sqh_first = NULL;                                       \
+        (head)->sqh_last = &(head)->sqh_first;                          \
+} while (0)
+#define SIMPLEQ_INSERT_HEAD(head, elm, field) do {                      \
+        if (((elm)->field.sqe_next = (head)->sqh_first) == NULL)        \
+                (head)->sqh_last = &(elm)->field.sqe_next;              \
+        (head)->sqh_first = (elm);                                      \
+} while (0)
+#define SIMPLEQ_INSERT_TAIL(head, elm, field) do {                      \
+        (elm)->field.sqe_next = NULL;                                   \
+        *(head)->sqh_last = (elm);                                      \
+        (head)->sqh_last = &(elm)->field.sqe_next;                      \
+} while (0)
+#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
+        if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
+                (head)->sqh_last = &(elm)->field.sqe_next;              \
+        (listelm)->field.sqe_next = (elm);                              \
+} while (0)
+#define SIMPLEQ_REMOVE_HEAD(head, elm, field) do {                      \
+        if (((head)->sqh_first = (elm)->field.sqe_next) == NULL)        \
+                (head)->sqh_last = &(head)->sqh_first;                  \
+} while (0)
+/*
+ * Tail queue definitions.
+ */
+#define TAILQ_HEAD(name, type)                                          \
+struct name {                                                           \
+        struct type *tqh_first; /* first element */                     \
+        struct type **tqh_last; /* addr of last next element */         \
+}
+#define TAILQ_HEAD_INITIALIZER(head)                                    \
+        { NULL, &(head).tqh_first }
+#define TAILQ_ENTRY(type)                                               \
+struct {                                                                \
+        struct type *tqe_next;  /* next element */                      \
+        struct type **tqe_prev; /* address of previous next element */  \
+}
+/* 
+ * tail queue access methods 
+ */
+#define TAILQ_FIRST(head)               ((head)->tqh_first)
+#define TAILQ_END(head)                 NULL
+#define TAILQ_NEXT(elm, field)          ((elm)->field.tqe_next)
+#define TAILQ_LAST(head, headname)                                      \
+        (*(((struct headname *)((head)->tqh_last))->tqh_last))
+/* XXX */
+#define TAILQ_PREV(elm, headname, field)                                \
+        (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
+#define TAILQ_EMPTY(head)                                               \
+        (TAILQ_FIRST(head) == TAILQ_END(head))
+#define TAILQ_FOREACH(var, head, field)                                 \
+        for((var) = TAILQ_FIRST(head);                                  \
+            (var) != TAILQ_END(head);                                   \
+            (var) = TAILQ_NEXT(var, field))
+#define TAILQ_FOREACH_REVERSE(var, head, field, headname)               \
+        for((var) = TAILQ_LAST(head, headname);                         \
+            (var) != TAILQ_END(head);                                   \
+            (var) = TAILQ_PREV(var, headname, field))
+/*
+ * Tail queue functions.
+ */
+#define TAILQ_INIT(head) do {                                           \
+        (head)->tqh_first = NULL;                                       \
+        (head)->tqh_last = &(head)->tqh_first;                          \
+} while (0)
+#define TAILQ_INSERT_HEAD(head, elm, field) do {                        \
+        if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
+                (head)->tqh_first->field.tqe_prev =                     \
+                    &(elm)->field.tqe_next;                             \
+        else                                                            \
+                (head)->tqh_last = &(elm)->field.tqe_next;              \
+        (head)->tqh_first = (elm);                                      \
+        (elm)->field.tqe_prev = &(head)->tqh_first;                     \
+} while (0)
+#define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
+        (elm)->field.tqe_next = NULL;                                   \
+        (elm)->field.tqe_prev = (head)->tqh_last;                       \
+        *(head)->tqh_last = (elm);                                      \
+        (head)->tqh_last = &(elm)->field.tqe_next;                      \
+} while (0)
+#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do {              \
+        if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
+                (elm)->field.tqe_next->field.tqe_prev =                 \
+                    &(elm)->field.tqe_next;                             \
+        else                                                            \
+                (head)->tqh_last = &(elm)->field.tqe_next;              \
+        (listelm)->field.tqe_next = (elm);                              \
+        (elm)->field.tqe_prev = &(listelm)->field.tqe_next;             \
+} while (0)
+#define TAILQ_INSERT_BEFORE(listelm, elm, field) do {                   \
+        (elm)->field.tqe_prev = (listelm)->field.tqe_prev;              \
+        (elm)->field.tqe_next = (listelm);                              \
+        *(listelm)->field.tqe_prev = (elm);                             \
+        (listelm)->field.tqe_prev = &(elm)->field.tqe_next;             \
+} while (0)
+#define TAILQ_REMOVE(head, elm, field) do {                             \
+        if (((elm)->field.tqe_next) != NULL)                            \
+                (elm)->field.tqe_next->field.tqe_prev =                 \
+                    (elm)->field.tqe_prev;                              \
+        else                                                            \
+                (head)->tqh_last = (elm)->field.tqe_prev;               \
+        *(elm)->field.tqe_prev = (elm)->field.tqe_next;                 \
+} while (0)
+#define TAILQ_REPLACE(head, elm, elm2, field) do {                      \
+        if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL)   \
+                (elm2)->field.tqe_next->field.tqe_prev =                \
+                    &(elm2)->field.tqe_next;                            \
+        else                                                            \
+                (head)->tqh_last = &(elm2)->field.tqe_next;             \
+        (elm2)->field.tqe_prev = (elm)->field.tqe_prev;                 \
+        *(elm2)->field.tqe_prev = (elm2);                               \
+} while (0)
+/*
+ * Circular queue definitions.
+ */
+#define CIRCLEQ_HEAD(name, type)                                        \
+struct name {                                                           \
+        struct type *cqh_first;         /* first element */             \
+        struct type *cqh_last;          /* last element */              \
+}
+#define CIRCLEQ_HEAD_INITIALIZER(head)                                  \
+        { CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
+#define CIRCLEQ_ENTRY(type)                                             \
+struct {                                                                \
+        struct type *cqe_next;          /* next element */              \
+        struct type *cqe_prev;          /* previous element */          \
+}
+/*
+ * Circular queue access methods 
+ */
+#define CIRCLEQ_FIRST(head)             ((head)->cqh_first)
+#define CIRCLEQ_LAST(head)              ((head)->cqh_last)
+#define CIRCLEQ_END(head)               ((void *)(head))
+#define CIRCLEQ_NEXT(elm, field)        ((elm)->field.cqe_next)
+#define CIRCLEQ_PREV(elm, field)        ((elm)->field.cqe_prev)
+#define CIRCLEQ_EMPTY(head)                                             \
+        (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
+#define CIRCLEQ_FOREACH(var, head, field)                               \
+        for((var) = CIRCLEQ_FIRST(head);                                \
+            (var) != CIRCLEQ_END(head);                                 \
+            (var) = CIRCLEQ_NEXT(var, field))
+#define CIRCLEQ_FOREACH_REVERSE(var, head, field)                       \
+        for((var) = CIRCLEQ_LAST(head);                                 \
+            (var) != CIRCLEQ_END(head);                                 \
+            (var) = CIRCLEQ_PREV(var, field))
+/*
+ * Circular queue functions.
+ */
+#define CIRCLEQ_INIT(head) do {                                         \
+        (head)->cqh_first = CIRCLEQ_END(head);                          \
+        (head)->cqh_last = CIRCLEQ_END(head);                           \
+} while (0)
+#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do {            \
+        (elm)->field.cqe_next = (listelm)->field.cqe_next;              \
+        (elm)->field.cqe_prev = (listelm);                              \
+        if ((listelm)->field.cqe_next == CIRCLEQ_END(head))             \
+                (head)->cqh_last = (elm);                               \
+        else                                                            \
+                (listelm)->field.cqe_next->field.cqe_prev = (elm);      \
+        (listelm)->field.cqe_next = (elm);                              \
+} while (0)
+#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do {           \
+        (elm)->field.cqe_next = (listelm);                              \
+        (elm)->field.cqe_prev = (listelm)->field.cqe_prev;              \
+        if ((listelm)->field.cqe_prev == CIRCLEQ_END(head))             \
+                (head)->cqh_first = (elm);                              \
+        else                                                            \
+                (listelm)->field.cqe_prev->field.cqe_next = (elm);      \
+        (listelm)->field.cqe_prev = (elm);                              \
+} while (0)
+#define CIRCLEQ_INSERT_HEAD(head, elm, field) do {                      \
+        (elm)->field.cqe_next = (head)->cqh_first;                      \
+        (elm)->field.cqe_prev = CIRCLEQ_END(head);                      \
+        if ((head)->cqh_last == CIRCLEQ_END(head))                      \
+                (head)->cqh_last = (elm);                               \
+        else                                                            \
+                (head)->cqh_first->field.cqe_prev = (elm);              \
+        (head)->cqh_first = (elm);                                      \
+} while (0)
+#define CIRCLEQ_INSERT_TAIL(head, elm, field) do {                      \
+        (elm)->field.cqe_next = CIRCLEQ_END(head);                      \
+        (elm)->field.cqe_prev = (head)->cqh_last;                       \
+        if ((head)->cqh_first == CIRCLEQ_END(head))                     \
+                (head)->cqh_first = (elm);                              \
+        else                                                            \
+                (head)->cqh_last->field.cqe_next = (elm);               \
+        (head)->cqh_last = (elm);                                       \
+} while (0)
+#define CIRCLEQ_REMOVE(head, elm, field) do {                           \
+        if ((elm)->field.cqe_next == CIRCLEQ_END(head))                 \
+                (head)->cqh_last = (elm)->field.cqe_prev;               \
+        else                                                            \
+                (elm)->field.cqe_next->field.cqe_prev =                 \
+                    (elm)->field.cqe_prev;                              \
+        if ((elm)->field.cqe_prev == CIRCLEQ_END(head))                 \
+                (head)->cqh_first = (elm)->field.cqe_next;              \
+        else                                                            \
+                (elm)->field.cqe_prev->field.cqe_next =                 \
+                    (elm)->field.cqe_next;                              \
+} while (0)
+#define CIRCLEQ_REPLACE(head, elm, elm2, field) do {                    \
+        if (((elm2)->field.cqe_next = (elm)->field.cqe_next) ==         \
+            CIRCLEQ_END(head))                                          \
+                (head).cqh_last = (elm2);                               \
+        else                                                            \
+                (elm2)->field.cqe_next->field.cqe_prev = (elm2);        \
+        if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) ==         \
+            CIRCLEQ_END(head))                                          \
+                (head).cqh_first = (elm2);                              \
+        else                                                            \
+                (elm2)->field.cqe_prev->field.cqe_next = (elm2);        \
+} while (0)
+#endif  /* !_SYS_QUEUE_H_ */

diff --git a/other/ssharp/openbsd-compat/fake-queue.h b/other/ssharp/openbsd-compat/fake-queue.h new file mode 100644 index 0000000..269af41 --- /dev/null +++ b/other/ssharp/openbsd-compat/fake-queue.h
@@ -0,0 +1,490 @@
	1	/* $OpenBSD: queue.h,v 1.16 2000/09/07 19:47:59 art Exp $ */
	2	/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
	3
	4	/*
	5	* Copyright (c) 1991, 1993
	6	* The Regents of the University of California. All rights reserved.
	7	*
	8	* Redistribution and use in source and binary forms, with or without
	9	* modification, are permitted provided that the following conditions
	10	* are met:
	11	* 1. Redistributions of source code must retain the above copyright
	12	* notice, this list of conditions and the following disclaimer.
	13	* 2. Redistributions in binary form must reproduce the above copyright
	14	* notice, this list of conditions and the following disclaimer in the
	15	* documentation and/or other materials provided with the distribution.
	16	* 3. All advertising materials mentioning features or use of this software
	17	* must display the following acknowledgement:
	18	* This product includes software developed by the University of
	19	* California, Berkeley and its contributors.
	20	* 4. Neither the name of the University nor the names of its contributors
	21	* may be used to endorse or promote products derived from this software
	22	* without specific prior written permission.
	23	*
	24	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	25	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	26	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	27	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	28	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	29	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	30	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	31	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	32	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	33	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	34	* SUCH DAMAGE.
	35	*
	36	* @(#)queue.h 8.5 (Berkeley) 8/20/94
	37	*/
	38
	39	#ifndef _SYS_QUEUE_H_
	40	#define _SYS_QUEUE_H_
	41
	42	/*
	43	* This file defines five types of data structures: singly-linked lists,
	44	* lists, simple queues, tail queues, and circular queues.
	45	*
	46	*
	47	* A singly-linked list is headed by a single forward pointer. The elements
	48	* are singly linked for minimum space and pointer manipulation overhead at
	49	* the expense of O(n) removal for arbitrary elements. New elements can be
	50	* added to the list after an existing element or at the head of the list.
	51	* Elements being removed from the head of the list should use the explicit
	52	* macro for this purpose for optimum efficiency. A singly-linked list may
	53	* only be traversed in the forward direction. Singly-linked lists are ideal
	54	* for applications with large datasets and few or no removals or for
	55	* implementing a LIFO queue.
	56	*
	57	* A list is headed by a single forward pointer (or an array of forward
	58	* pointers for a hash table header). The elements are doubly linked
	59	* so that an arbitrary element can be removed without a need to
	60	* traverse the list. New elements can be added to the list before
	61	* or after an existing element or at the head of the list. A list
	62	* may only be traversed in the forward direction.
	63	*
	64	* A simple queue is headed by a pair of pointers, one the head of the
	65	* list and the other to the tail of the list. The elements are singly
	66	* linked to save space, so elements can only be removed from the
	67	* head of the list. New elements can be added to the list before or after
	68	* an existing element, at the head of the list, or at the end of the
	69	* list. A simple queue may only be traversed in the forward direction.
	70	*
	71	* A tail queue is headed by a pair of pointers, one to the head of the
	72	* list and the other to the tail of the list. The elements are doubly
	73	* linked so that an arbitrary element can be removed without a need to
	74	* traverse the list. New elements can be added to the list before or
	75	* after an existing element, at the head of the list, or at the end of
	76	* the list. A tail queue may be traversed in either direction.
	77	*
	78	* A circle queue is headed by a pair of pointers, one to the head of the
	79	* list and the other to the tail of the list. The elements are doubly
	80	* linked so that an arbitrary element can be removed without a need to
	81	* traverse the list. New elements can be added to the list before or after
	82	* an existing element, at the head of the list, or at the end of the list.
	83	* A circle queue may be traversed in either direction, but has a more
	84	* complex end of list detection.
	85	*
	86	* For details on the use of these macros, see the queue(3) manual page.
	87	*/
	88
	89	/*
	90	* Singly-linked List definitions.
	91	*/
	92	#define SLIST_HEAD(name, type) \
	93	struct name { \
	94	struct type slh_first; / first element */ \
	95	}
	96
	97	#define SLIST_HEAD_INITIALIZER(head) \
	98	{ NULL }
	99
	100	#define SLIST_ENTRY(type) \
	101	struct { \
	102	struct type sle_next; / next element */ \
	103	}
	104
	105	/*
	106	* Singly-linked List access methods.
	107	*/
	108	#define SLIST_FIRST(head) ((head)->slh_first)
	109	#define SLIST_END(head) NULL
	110	#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
	111	#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
	112
	113	#define SLIST_FOREACH(var, head, field) \
	114	for((var) = SLIST_FIRST(head); \
	115	(var) != SLIST_END(head); \
	116	(var) = SLIST_NEXT(var, field))
	117
	118	/*
	119	* Singly-linked List functions.
	120	*/
	121	#define SLIST_INIT(head) { \
	122	SLIST_FIRST(head) = SLIST_END(head); \
	123	}
	124
	125	#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
	126	(elm)->field.sle_next = (slistelm)->field.sle_next; \
	127	(slistelm)->field.sle_next = (elm); \
	128	} while (0)
	129
	130	#define SLIST_INSERT_HEAD(head, elm, field) do { \
	131	(elm)->field.sle_next = (head)->slh_first; \
	132	(head)->slh_first = (elm); \
	133	} while (0)
	134
	135	#define SLIST_REMOVE_HEAD(head, field) do { \
	136	(head)->slh_first = (head)->slh_first->field.sle_next; \
	137	} while (0)
	138
	139	/*
	140	* List definitions.
	141	*/
	142	#define LIST_HEAD(name, type) \
	143	struct name { \
	144	struct type lh_first; / first element */ \
	145	}
	146
	147	#define LIST_HEAD_INITIALIZER(head) \
	148	{ NULL }
	149
	150	#define LIST_ENTRY(type) \
	151	struct { \
	152	struct type le_next; / next element */ \
	153	struct type *le_prev; / address of previous next element */ \
	154	}
	155
	156	/*
	157	* List access methods
	158	*/
	159	#define LIST_FIRST(head) ((head)->lh_first)
	160	#define LIST_END(head) NULL
	161	#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
	162	#define LIST_NEXT(elm, field) ((elm)->field.le_next)
	163
	164	#define LIST_FOREACH(var, head, field) \
	165	for((var) = LIST_FIRST(head); \
	166	(var)!= LIST_END(head); \
	167	(var) = LIST_NEXT(var, field))
	168
	169	/*
	170	* List functions.
	171	*/
	172	#define LIST_INIT(head) do { \
	173	LIST_FIRST(head) = LIST_END(head); \
	174	} while (0)
	175
	176	#define LIST_INSERT_AFTER(listelm, elm, field) do { \
	177	if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
	178	(listelm)->field.le_next->field.le_prev = \
	179	&(elm)->field.le_next; \
	180	(listelm)->field.le_next = (elm); \
	181	(elm)->field.le_prev = &(listelm)->field.le_next; \
	182	} while (0)
	183
	184	#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
	185	(elm)->field.le_prev = (listelm)->field.le_prev; \
	186	(elm)->field.le_next = (listelm); \
	187	*(listelm)->field.le_prev = (elm); \
	188	(listelm)->field.le_prev = &(elm)->field.le_next; \
	189	} while (0)
	190
	191	#define LIST_INSERT_HEAD(head, elm, field) do { \
	192	if (((elm)->field.le_next = (head)->lh_first) != NULL) \
	193	(head)->lh_first->field.le_prev = &(elm)->field.le_next;\
	194	(head)->lh_first = (elm); \
	195	(elm)->field.le_prev = &(head)->lh_first; \
	196	} while (0)
	197
	198	#define LIST_REMOVE(elm, field) do { \
	199	if ((elm)->field.le_next != NULL) \
	200	(elm)->field.le_next->field.le_prev = \
	201	(elm)->field.le_prev; \
	202	*(elm)->field.le_prev = (elm)->field.le_next; \
	203	} while (0)
	204
	205	#define LIST_REPLACE(elm, elm2, field) do { \
	206	if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
	207	(elm2)->field.le_next->field.le_prev = \
	208	&(elm2)->field.le_next; \
	209	(elm2)->field.le_prev = (elm)->field.le_prev; \
	210	*(elm2)->field.le_prev = (elm2); \
	211	} while (0)
	212
	213	/*
	214	* Simple queue definitions.
	215	*/
	216	#define SIMPLEQ_HEAD(name, type) \
	217	struct name { \
	218	struct type sqh_first; / first element */ \
	219	struct type *sqh_last; / addr of last next element */ \
	220	}
	221
	222	#define SIMPLEQ_HEAD_INITIALIZER(head) \
	223	{ NULL, &(head).sqh_first }
	224
	225	#define SIMPLEQ_ENTRY(type) \
	226	struct { \
	227	struct type sqe_next; / next element */ \
	228	}
	229
	230	/*
	231	* Simple queue access methods.
	232	*/
	233	#define SIMPLEQ_FIRST(head) ((head)->sqh_first)
	234	#define SIMPLEQ_END(head) NULL
	235	#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
	236	#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
	237
	238	#define SIMPLEQ_FOREACH(var, head, field) \
	239	for((var) = SIMPLEQ_FIRST(head); \
	240	(var) != SIMPLEQ_END(head); \
	241	(var) = SIMPLEQ_NEXT(var, field))
	242
	243	/*
	244	* Simple queue functions.
	245	*/
	246	#define SIMPLEQ_INIT(head) do { \
	247	(head)->sqh_first = NULL; \
	248	(head)->sqh_last = &(head)->sqh_first; \
	249	} while (0)
	250
	251	#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
	252	if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
	253	(head)->sqh_last = &(elm)->field.sqe_next; \
	254	(head)->sqh_first = (elm); \
	255	} while (0)
	256
	257	#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
	258	(elm)->field.sqe_next = NULL; \
	259	*(head)->sqh_last = (elm); \
	260	(head)->sqh_last = &(elm)->field.sqe_next; \
	261	} while (0)
	262
	263	#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
	264	if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
	265	(head)->sqh_last = &(elm)->field.sqe_next; \
	266	(listelm)->field.sqe_next = (elm); \
	267	} while (0)
	268
	269	#define SIMPLEQ_REMOVE_HEAD(head, elm, field) do { \
	270	if (((head)->sqh_first = (elm)->field.sqe_next) == NULL) \
	271	(head)->sqh_last = &(head)->sqh_first; \
	272	} while (0)
	273
	274	/*
	275	* Tail queue definitions.
	276	*/
	277	#define TAILQ_HEAD(name, type) \
	278	struct name { \
	279	struct type tqh_first; / first element */ \
	280	struct type *tqh_last; / addr of last next element */ \
	281	}
	282
	283	#define TAILQ_HEAD_INITIALIZER(head) \
	284	{ NULL, &(head).tqh_first }
	285
	286	#define TAILQ_ENTRY(type) \
	287	struct { \
	288	struct type tqe_next; / next element */ \
	289	struct type *tqe_prev; / address of previous next element */ \
	290	}
	291
	292	/*
	293	* tail queue access methods
	294	*/
	295	#define TAILQ_FIRST(head) ((head)->tqh_first)
	296	#define TAILQ_END(head) NULL
	297	#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
	298	#define TAILQ_LAST(head, headname) \
	299	((((struct headname )((head)->tqh_last))->tqh_last))
	300	/* XXX */
	301	#define TAILQ_PREV(elm, headname, field) \
	302	((((struct headname )((elm)->field.tqe_prev))->tqh_last))
	303	#define TAILQ_EMPTY(head) \
	304	(TAILQ_FIRST(head) == TAILQ_END(head))
	305
	306	#define TAILQ_FOREACH(var, head, field) \
	307	for((var) = TAILQ_FIRST(head); \
	308	(var) != TAILQ_END(head); \
	309	(var) = TAILQ_NEXT(var, field))
	310
	311	#define TAILQ_FOREACH_REVERSE(var, head, field, headname) \
	312	for((var) = TAILQ_LAST(head, headname); \
	313	(var) != TAILQ_END(head); \
	314	(var) = TAILQ_PREV(var, headname, field))
	315
	316	/*
	317	* Tail queue functions.
	318	*/
	319	#define TAILQ_INIT(head) do { \
	320	(head)->tqh_first = NULL; \
	321	(head)->tqh_last = &(head)->tqh_first; \
	322	} while (0)
	323
	324	#define TAILQ_INSERT_HEAD(head, elm, field) do { \
	325	if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
	326	(head)->tqh_first->field.tqe_prev = \
	327	&(elm)->field.tqe_next; \
	328	else \
	329	(head)->tqh_last = &(elm)->field.tqe_next; \
	330	(head)->tqh_first = (elm); \
	331	(elm)->field.tqe_prev = &(head)->tqh_first; \
	332	} while (0)
	333
	334	#define TAILQ_INSERT_TAIL(head, elm, field) do { \
	335	(elm)->field.tqe_next = NULL; \
	336	(elm)->field.tqe_prev = (head)->tqh_last; \
	337	*(head)->tqh_last = (elm); \
	338	(head)->tqh_last = &(elm)->field.tqe_next; \
	339	} while (0)
	340
	341	#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
	342	if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
	343	(elm)->field.tqe_next->field.tqe_prev = \
	344	&(elm)->field.tqe_next; \
	345	else \
	346	(head)->tqh_last = &(elm)->field.tqe_next; \
	347	(listelm)->field.tqe_next = (elm); \
	348	(elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
	349	} while (0)
	350
	351	#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
	352	(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
	353	(elm)->field.tqe_next = (listelm); \
	354	*(listelm)->field.tqe_prev = (elm); \
	355	(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
	356	} while (0)
	357
	358	#define TAILQ_REMOVE(head, elm, field) do { \
	359	if (((elm)->field.tqe_next) != NULL) \
	360	(elm)->field.tqe_next->field.tqe_prev = \
	361	(elm)->field.tqe_prev; \
	362	else \
	363	(head)->tqh_last = (elm)->field.tqe_prev; \
	364	*(elm)->field.tqe_prev = (elm)->field.tqe_next; \
	365	} while (0)
	366
	367	#define TAILQ_REPLACE(head, elm, elm2, field) do { \
	368	if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
	369	(elm2)->field.tqe_next->field.tqe_prev = \
	370	&(elm2)->field.tqe_next; \
	371	else \
	372	(head)->tqh_last = &(elm2)->field.tqe_next; \
	373	(elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
	374	*(elm2)->field.tqe_prev = (elm2); \
	375	} while (0)
	376
	377	/*
	378	* Circular queue definitions.
	379	*/
	380	#define CIRCLEQ_HEAD(name, type) \
	381	struct name { \
	382	struct type cqh_first; / first element */ \
	383	struct type cqh_last; / last element */ \
	384	}
	385
	386	#define CIRCLEQ_HEAD_INITIALIZER(head) \
	387	{ CIRCLEQ_END(&head), CIRCLEQ_END(&head) }
	388
	389	#define CIRCLEQ_ENTRY(type) \
	390	struct { \
	391	struct type cqe_next; / next element */ \
	392	struct type cqe_prev; / previous element */ \
	393	}
	394
	395	/*
	396	* Circular queue access methods
	397	*/
	398	#define CIRCLEQ_FIRST(head) ((head)->cqh_first)
	399	#define CIRCLEQ_LAST(head) ((head)->cqh_last)
	400	#define CIRCLEQ_END(head) ((void *)(head))
	401	#define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next)
	402	#define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev)
	403	#define CIRCLEQ_EMPTY(head) \
	404	(CIRCLEQ_FIRST(head) == CIRCLEQ_END(head))
	405
	406	#define CIRCLEQ_FOREACH(var, head, field) \
	407	for((var) = CIRCLEQ_FIRST(head); \
	408	(var) != CIRCLEQ_END(head); \
	409	(var) = CIRCLEQ_NEXT(var, field))
	410
	411	#define CIRCLEQ_FOREACH_REVERSE(var, head, field) \
	412	for((var) = CIRCLEQ_LAST(head); \
	413	(var) != CIRCLEQ_END(head); \
	414	(var) = CIRCLEQ_PREV(var, field))
	415
	416	/*
	417	* Circular queue functions.
	418	*/
	419	#define CIRCLEQ_INIT(head) do { \
	420	(head)->cqh_first = CIRCLEQ_END(head); \
	421	(head)->cqh_last = CIRCLEQ_END(head); \
	422	} while (0)
	423
	424	#define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
	425	(elm)->field.cqe_next = (listelm)->field.cqe_next; \
	426	(elm)->field.cqe_prev = (listelm); \
	427	if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \
	428	(head)->cqh_last = (elm); \
	429	else \
	430	(listelm)->field.cqe_next->field.cqe_prev = (elm); \
	431	(listelm)->field.cqe_next = (elm); \
	432	} while (0)
	433
	434	#define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \
	435	(elm)->field.cqe_next = (listelm); \
	436	(elm)->field.cqe_prev = (listelm)->field.cqe_prev; \
	437	if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \
	438	(head)->cqh_first = (elm); \
	439	else \
	440	(listelm)->field.cqe_prev->field.cqe_next = (elm); \
	441	(listelm)->field.cqe_prev = (elm); \
	442	} while (0)
	443
	444	#define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \
	445	(elm)->field.cqe_next = (head)->cqh_first; \
	446	(elm)->field.cqe_prev = CIRCLEQ_END(head); \
	447	if ((head)->cqh_last == CIRCLEQ_END(head)) \
	448	(head)->cqh_last = (elm); \
	449	else \
	450	(head)->cqh_first->field.cqe_prev = (elm); \
	451	(head)->cqh_first = (elm); \
	452	} while (0)
	453
	454	#define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \
	455	(elm)->field.cqe_next = CIRCLEQ_END(head); \
	456	(elm)->field.cqe_prev = (head)->cqh_last; \
	457	if ((head)->cqh_first == CIRCLEQ_END(head)) \
	458	(head)->cqh_first = (elm); \
	459	else \
	460	(head)->cqh_last->field.cqe_next = (elm); \
	461	(head)->cqh_last = (elm); \
	462	} while (0)
	463
	464	#define CIRCLEQ_REMOVE(head, elm, field) do { \
	465	if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \
	466	(head)->cqh_last = (elm)->field.cqe_prev; \
	467	else \
	468	(elm)->field.cqe_next->field.cqe_prev = \
	469	(elm)->field.cqe_prev; \
	470	if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \
	471	(head)->cqh_first = (elm)->field.cqe_next; \
	472	else \
	473	(elm)->field.cqe_prev->field.cqe_next = \
	474	(elm)->field.cqe_next; \
	475	} while (0)
	476
	477	#define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \
	478	if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \
	479	CIRCLEQ_END(head)) \
	480	(head).cqh_last = (elm2); \
	481	else \
	482	(elm2)->field.cqe_next->field.cqe_prev = (elm2); \
	483	if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \
	484	CIRCLEQ_END(head)) \
	485	(head).cqh_first = (elm2); \
	486	else \
	487	(elm2)->field.cqe_prev->field.cqe_next = (elm2); \
	488	} while (0)
	489
	490	#endif /* !_SYS_QUEUE_H_ */