1 files changed, 136 insertions, 0 deletions
diff --git a/dll.h b/dll.h
new file mode 100644
index 0000000..19556d0
--- /dev/null
+++ b/dll.h
@@ -0,0 +1,136 @@
+/*
+ *  Copyright (C) 2019 - Vito Caputo - <vcaputo@pengaru.com>
+ *
+ *  This program is free software: you can redistribute it and/or modify it
+ *  under the terms of the GNU General Public License version 3 as published
+ *  by the Free Software Foundation.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+/* (circular) Doubly-Linked List header */
+
+/* I've been using the Linux kernel's list.h for ages, so it definitely
+ * takes some inspiration from that API.
+ */
+
+#ifndef _DLL_H
+#define _DLL_H
+
+
+#include <stddef.h>	/* offsetof() */
+
+
+typedef struct dll_t dll_t;
+
+struct dll_t {
+	dll_t	*next, *previous;
+};
+
+
+/* This is analagous to container_of */
+#define DLL_ENTRY(_ptr, _type, _member) \
+	(_type *)((char *)(_ptr) - offsetof(_type, _member))
+
+
+/* Declare and initialize an empty list named _name */
+#define DLL_INIT(_name) \
+	dll_t	_name = { .next = &_name, .previous = &_name }
+
+
+/* Iterate list */
+#define DLL_FOR_EACH(_head, _node)		\
+	for (	(_node) = (_head)->next;	\
+		(_node) != (_head);		\
+		(_node) = (_node)->next		\
+	)
+
+
+/* Iterate list in a removal-safe fashion */
+#define DLL_FOR_EACH_SAFE(_head, _node, _next)				\
+	for (	(_node) = (_head)->next, (_next) = (_node)->next;	\
+		(_node) != (_head);					\
+		(_node) = (_next), (_next) = (_next->next)		\
+	)
+
+
+/* Iterate list as containers */
+#define DLL_FOR_EACH_ENTRY(_head, _entry, _type, _member)			\
+	for (	(_entry) = DLL_ENTRY((_head)->next, _type, _member);		\
+		&(_entry)->_member != (_head);					\
+		(_entry) = DLL_ENTRY((_entry)->_member.next, _type, _member)	\
+	)
+
+
+/* Iterate list as containers in a removal-safe fashion */
+#define DLL_FOR_EACH_ENTRY_SAFE(_head, _entry, _next, _type, _member)		\
+	for (	(_entry) = DLL_ENTRY((_head)->next, _type, _member),		\
+		(_next) = DLL_ENTRY((_entry)->_member.next, _type, _member);	\
+		&(_entry)->_member != (_head);					\
+		(_entry) = (_next),						\
+		(_next) = DLL_ENTRY((_next)->_member.next, _type, _member)	\
+	)
+
+
+/* Initialize node to an empty list state,
+ * node is returned for convenience.
+ */
+static inline dll_t * dll_init(dll_t *node)
+{
+	return node->next = node->previous = node;
+}
+
+
+/* Delete node from the list it belongs to,
+ * node is returned for convenience.
+ */
+static inline dll_t * dll_del(dll_t *node)
+{
+	node->next->previous = node->previous;
+	node->previous->next = node->next;
+
+	return dll_init(node);
+}
+
+
+/* Insert node immediately before where,
+ * node is returned for convenience.
+ */
+static inline dll_t * dll_pre(dll_t *where, dll_t *node)
+{
+	node->next = where;
+	node->previous = where->previous;
+	where->previous->next = node;
+	where->previous = node;
+
+	return node;
+}
+
+
+/* Append node immediately after where,
+ * node is returned for convenience.
+ */
+static inline dll_t * dll_post(dll_t *where, dll_t *node)
+{
+	node->next = where->next;
+	node->previous = where;
+	where->next->previous = node;
+	where->next = node;
+
+	return node;
+}
+
+
+static inline int dll_empty(dll_t *dll)
+{
+	return (dll->next == dll && dll->next == dll->previous);
+}
+
+
+#endif