lib/list: Add double linked list management functions
Add a simple implementation of circular doubly-linked lists.
Apart from the struct itself, there are functions to add and remove
items, and check for emptyness.
Signed-off-by: Claudio Imbrenda <imbrenda@linux.ibm.com>
Message-Id: <20201002154420.292134-2-imbrenda@linux.ibm.com>
Signed-off-by: Paolo Bonzini <pbonzini@redhat.com>
diff --git a/lib/list.h b/lib/list.h
new file mode 100644
index 0000000..18d9516
--- /dev/null
+++ b/lib/list.h
@@ -0,0 +1,53 @@
+#ifndef LIST_H
+#define LIST_H
+
+#include <stdbool.h>
+
+/*
+ * Circular doubly-linked list. The pointer to the list is a list item itself,
+ * like in the kernel implementation.
+ */
+struct linked_list {
+ struct linked_list *prev;
+ struct linked_list *next;
+};
+
+/*
+ * An empty list is a list item whose prev and next both point to itself.
+ * Returns true if the list is empty.
+ */
+static inline bool is_list_empty(struct linked_list *p)
+{
+ return !p->next || !p->prev || p == p->next || p == p->prev;
+}
+
+/*
+ * Remove the given element from the list, if the list is not already empty.
+ * The removed element is returned.
+ */
+static inline struct linked_list *list_remove(struct linked_list *l)
+{
+ if (is_list_empty(l))
+ return NULL;
+
+ l->prev->next = l->next;
+ l->next->prev = l->prev;
+ l->prev = l->next = NULL;
+
+ return l;
+}
+
+/*
+ * Add the given element after the given list head.
+ */
+static inline void list_add(struct linked_list *head, struct linked_list *li)
+{
+ assert(li);
+ assert(head);
+ li->prev = head;
+ li->next = head->next;
+ head->next->prev = li;
+ head->next = li;
+}
+
+#endif
