From b7773bc70bb3d4b3e3552b4fce05cdda3fa16179 Mon Sep 17 00:00:00 2001
From: David Herrmann <dh.herrmann@googlemail.com>
Date: Sun, 22 Apr 2012 15:43:00 +0200
Subject: [PATCH] misc: add double-linked list implementation

This adds a generic double-linked list implementation so we don't have to
write all list-handling over and over again.

The list-type is similar to the kernel list where we use the same type for
heads and entries. This is a _very_ convenient list-type so we copy it.

Signed-off-by: David Herrmann <dh.herrmann@googlemail.com>
---
 src/misc.h | 62 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 62 insertions(+)

diff --git a/src/misc.h b/src/misc.h
index 2f53994..f1383d2 100644
--- a/src/misc.h
+++ b/src/misc.h
@@ -92,4 +92,66 @@ int kmscon_hashtable_insert(struct kmscon_hashtable *tbl, void *key,
 				void *data);
 bool kmscon_hashtable_find(struct kmscon_hashtable *tbl, void **out, void *key);
 
+/* double linked list */
+
+struct kmscon_dlist {
+	struct kmscon_dlist *next;
+	struct kmscon_dlist *prev;
+};
+
+#define KMSCON_DLIST_INIT(head) { &(head), &(head) }
+
+static inline void kmscon_dlist_init(struct kmscon_dlist *list)
+{
+	list->next = list;
+	list->prev = list;
+}
+
+static inline void kmscon_dlist__link(struct kmscon_dlist *prev,
+					struct kmscon_dlist *next,
+					struct kmscon_dlist *n)
+{
+	next->prev = n;
+	n->next = next;
+	n->prev = prev;
+	prev->next = n;
+}
+
+static inline void kmscon_dlist_link(struct kmscon_dlist *head,
+					struct kmscon_dlist *n)
+{
+	return kmscon_dlist__link(head, head->next, n);
+}
+
+static inline void kmscon_dlist_link_tail(struct kmscon_dlist *head,
+					struct kmscon_dlist *n)
+{
+	return kmscon_dlist__link(head->prev, head, n);
+}
+
+static inline void kmscon_dlist__unlink(struct kmscon_dlist *prev,
+					struct kmscon_dlist *next)
+{
+	next->prev = prev;
+	prev->next = next;
+}
+
+static inline void kmscon_dlist_unlink(struct kmscon_dlist *e)
+{
+	kmscon_dlist__unlink(e->prev, e->next);
+	e->prev = NULL;
+	e->next = NULL;
+}
+
+static inline bool kmscon_dlist_empty(struct kmscon_dlist *head)
+{
+	return head->next == head;
+}
+
+#define kmscon_dlist_entry(ptr, type, member) \
+	kmscon_offsetof((ptr), type, member)
+
+#define kmscon_dlist_for_each(iter, head) \
+	for (iter = (head)->next; iter != (head); iter = iter->next)
+
 #endif /* KMSCON_MISC_H */
-- 
2.7.4