0001-Add-embedded-list-interface-header-only.patch

diff --git a/src/include/utils/ilist.h b/src/include/utils/ilist.h
new file mode 100644
index 0000000..03dae63
--- /dev/null
+++ b/src/include/utils/ilist.h
@@ -0,0 +1,253 @@
+#ifndef ILIST_H
+#define ILIST_H
+
+#ifdef __GNUC__
+#define unused_attr __attribute__((unused))
+#else
+#define unused_attr
+#endif
+
+#ifndef USE_INLINE
+#error "a compiler supporting static inlines is required"
+#endif
+
+#include <assert.h>
+
+typedef struct ilist_d_node ilist_d_node;
+
+struct ilist_d_node
+{
+	ilist_d_node* prev;
+	ilist_d_node* next;
+};
+
+typedef struct
+{
+	ilist_d_node head;
+} ilist_d_head;
+
+typedef struct ilist_s_node ilist_s_node;
+
+struct ilist_s_node
+{
+	ilist_s_node* next;
+};
+
+typedef struct
+{
+	ilist_s_node head;
+} ilist_s_head;
+
+#ifdef ILIST_DEBUG
+void ilist_d_check(ilist_d_head* head);
+#else
+static inline void ilist_d_check(ilist_d_head* head)
+{
+}
+#endif
+
+static inline void ilist_d_init(ilist_d_head *head)
+{
+	head->head.next = head->head.prev = &head->head;
+	ilist_d_check(head);
+}
+
+/*
+ * adds a node at the beginning of the list
+ */
+static inline void ilist_d_push_front(ilist_d_head *head, ilist_d_node *node)
+{
+	node->next = head->head.next;
+	node->prev = &head->head;
+	node->next->prev = node;
+	head->head.next = node;
+	ilist_d_check(head);
+}
+
+
+/*
+ * adds a node at the end of the list
+ */
+static inline void ilist_d_push_back(ilist_d_head *head, ilist_d_node *node)
+{
+	node->next = &head->head;
+	node->prev = head->head.prev;
+	node->prev->next = node;
+	head->head.prev = node;
+	ilist_d_check(head);
+}
+
+
+/*
+ * adds a node after another *in the same list*
+ */
+static inline void ilist_d_add_after(unused_attr ilist_d_head *head, ilist_d_node *after, ilist_d_node *node)
+{
+	node->prev = after;
+	node->next = after->next;
+	after->next = node;
+	node->next->prev = node;
+	ilist_d_check(head);
+}
+
+/*
+ * adds a node after another *in the same list*
+ */
+static inline void ilist_d_add_before(unused_attr ilist_d_head *head, ilist_d_node *before, ilist_d_node *node)
+{
+	node->prev = before->prev;
+	node->next = before;
+	before->prev = node;
+	node->prev->next = node;
+	ilist_d_check(head);
+}
+
+
+/*
+ * removes a node from a list
+ */
+static inline void ilist_d_remove(unused_attr ilist_d_head *head, ilist_d_node *node)
+{
+	ilist_d_check(head);
+	node->prev->next = node->next;
+	node->next->prev = node->prev;
+	ilist_d_check(head);
+}
+
+/*
+ * removes the first node from a list or returns NULL
+ */
+static inline ilist_d_node* ilist_d_pop_front(ilist_d_head *head)
+{
+	ilist_d_node* ret;
+
+	if (&head->head == head->head.next)
+		return NULL;
+
+	ret = head->head.next;
+	ilist_d_remove(head, head->head.next);
+	return ret;
+}
+
+
+static inline bool ilist_d_has_next(ilist_d_head *head, ilist_d_node *node)
+{
+	return node->next != &head->head;
+}
+
+static inline bool ilist_d_has_prev(ilist_d_head *head, ilist_d_node *node)
+{
+	return node->prev != &head->head;
+}
+
+static inline bool ilist_d_is_empty(ilist_d_head *head)
+{
+	return head->head.next == &head->head;
+}
+
+#define ilist_d_front(type, membername, ptr) (&((ptr)->head) == (ptr)->head.next) ? \
+	NULL : ilist_container(type, membername, (ptr)->head.next)
+
+#define ilist_d_front_unchecked(type, membername, ptr) ilist_container(type, membername, (ptr)->head.next)
+
+#define ilist_d_back(type, membername, ptr)  (&((ptr)->head) == (ptr)->head.prev) ? \
+	NULL : ilist_container(type, membername, (ptr)->head.prev)
+
+#define ilist_container(type, membername, ptr) ((type*)((char*)(ptr) - offsetof(type, membername)))
+
+#define ilist_d_foreach(name, ptr) for(name = (ptr)->head.next;	\
+                                     name != &(ptr)->head;	\
+                                     name = name->next)
+
+#define ilist_d_foreach_modify(name, nxt, ptr) for(name = (ptr)->head.next,    \
+	                                                   nxt = name->next;       \
+                                                   name != &(ptr)->head        \
+	                                                   ;                       \
+                                                   name = nxt, nxt = name->next)
+
+static inline void ilist_s_init(ilist_s_head *head)
+{
+	head->head.next = NULL;
+}
+
+static inline void ilist_s_push_front(ilist_s_head *head, ilist_s_node *node)
+{
+	node->next = head->head.next;
+	head->head.next = node;
+}
+
+/*
+ * fails if the list is empty
+ */
+static inline ilist_s_node* ilist_s_pop_front(ilist_s_head *head)
+{
+	ilist_s_node* front = head->head.next;
+	head->head.next = head->head.next->next;
+	return front;
+}
+
+/*
+ * removes a node from a list
+ * Attention: O(n)
+ */
+static inline void ilist_s_remove(ilist_s_head *head,
+                                  ilist_s_node *node)
+{
+	ilist_s_node *last = &head->head;
+	ilist_s_node *cur;
+#ifndef NDEBUG
+	bool found = false;
+#endif
+	while ((cur = last->next))
+	{
+		if (cur == node)
+		{
+			last->next = cur->next;
+#ifndef NDEBUG
+			found = true;
+#endif
+			break;
+		}
+		last = cur;
+	}
+	assert(found);
+}
+
+
+static inline void ilist_s_add_after(unused_attr ilist_s_head *head,
+                                     ilist_s_node *after, ilist_s_node *node)
+{
+	node->next = after->next;
+	after->next = node;
+}
+
+
+static inline bool ilist_s_is_empty(ilist_s_head *head)
+{
+	return head->head.next == NULL;
+}
+
+static inline bool ilist_s_has_next(unused_attr ilist_s_head* head,
+                                    ilist_s_node *node)
+{
+	return node->next != NULL;
+}
+
+
+#define ilist_s_front(type, membername, ptr) (ilist_s_is_empty(ptr) ? \
+	ilist_container(type, membername, (ptr).next) : NULL
+
+#define ilist_s_front_unchecked(type, membername, ptr) \
+	ilist_container(type, membername, (ptr)->head.next)
+
+#define ilist_s_foreach(name, ptr) for(name = (ptr)->head.next;         \
+                                       name != NULL;                    \
+                                       name = name->next)
+
+#define ilist_s_foreach_modify(name, nxt, ptr) for(name = (ptr)->head.next, \
+	                                                   nxt = name ? name->next : NULL; \
+                                                   name != NULL;            \
+                                                   name = nxt, nxt = name ? name->next : NULL)
+
+
+#endif