DLIST_* type/operations.

1 files changed, 73 insertions, 1 deletions

diff --git a/sys/sys/queue.h b/sys/sys/queue.h
index d2aeeba377d..a4773aefa56 100644
--- a/sys/sys/queue.h
+++ b/sys/sys/queue.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: queue.h,v 1.17 2000/11/16 20:02:20 provos Exp $	*/
+/*	$OpenBSD: queue.h,v 1.18 2001/06/23 03:47:58 angelos Exp $	*/
 /*	$NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $	*/
 
 /*
@@ -224,6 +224,78 @@ struct {								\
 } while (0)
 
 /*
+ * Doubly-linked list with a single head pointer. This is
+ * the same as the LIST_* type, except that le_prev of the
+ * first element does not point to the list head.
+ */
+#define DLIST_HEAD(name, type)						\
+struct name {								\
+	struct type dh_first;	/* first element */			\
+}
+
+#define DLIST_HEAD_INITIALIZER(head)					\
+	{ NULL }
+
+#define DLIST_ENTRY(type)						\
+struct {								\
+	struct type *de_next;	/* next element */	       		\
+	struct type **de_prev;	/* address of previous next element */	\
+}
+
+/*
+ * List access methods
+ */
+#define	DLIST_FIRST(head)		((head)->dh_first)
+#define	DLIST_END(head)			NULL
+#define	DLIST_EMPTY(head)		(LIST_FIRST(head) == LIST_END(head))
+#define	DLIST_NEXT(elm, field)		((elm)->field.de_next)
+
+#define DLIST_FOREACH(var, head, field)					\
+	for((var) = DLIST_FIRST(head);					\
+	    (var)!= DLIST_END(head);					\
+	    (var) = DLIST_NEXT(var, field))
+
+/*
+ * List functions.
+ */
+#define	DLIST_INIT(head) do {						\
+	DLIST_FIRST(head) = DLIST_END(head);				\
+} while (0)
+
+#define DLIST_INSERT_AFTER(listelm, elm, field) do {			\
+	if (((elm)->field.de_next = (listelm)->field.de_next) != NULL)	\
+		(listelm)->field.de_next->field.de_prev =		\
+		    &(elm)->field.de_next;				\
+	(listelm)->field.de_next = (elm);				\
+	(elm)->field.de_prev = &(listelm)->field.de_next;		\
+} while (0)
+
+#define	DLIST_INSERT_BEFORE(listelm, elm, field) do {			\
+	(elm)->field.de_prev = (listelm)->field.de_prev;		\
+	(elm)->field.de_next = (listelm);				\
+	if ((listelm)->field.de_prev != NULL)				\
+		*(listelm)->field.de_prev = (elm);		       	\
+	(listelm)->field.de_prev = &(elm)->field.de_next;		\
+} while (0)
+
+#define DLIST_INSERT_HEAD(head, elm, field) do {			\
+	if (((elm)->field.de_next = (head)->dh_first) != NULL)		\
+		(head)->dh_first->field.de_prev = &(elm)->field.de_next;\
+	(head)->lh_first = (elm);					\
+	(elm)->field.le_prev = NULL;					\
+} while (0)
+
+#define DLIST_REMOVE(head, elm, field) do {				\
+	if ((elm)->field.le_next != NULL)				\
+		(elm)->field.le_next->field.le_prev =			\
+		    (elm)->field.le_prev;				\
+	if ((elm)->field.le_prev != NULL)				\
+		*(elm)->field.le_prev = (elm)->field.le_next;		\
+	else								\
+		(head)->dh_first = DLIST_END(head);			\
+} while (0)
+
+/*
  * Simple queue definitions.
  */
 #define SIMPLEQ_HEAD(name, type)					\