[virglrenderer-devel] [PATCH 1/5] utils: added intrusive linked-list implem

[Nathan Gauer]

Signed-off-by: Nathan Gauer <nathan at gauer.org>
---
 src/util/list.c | 75 +++++++++++++++++++++++++++++++++++++++++++++++++
 src/util/list.h | 31 ++++++++++++++++++++
 2 files changed, 106 insertions(+)
 create mode 100644 src/util/list.c
 create mode 100644 src/util/list.h

diff --git a/src/util/list.c b/src/util/list.c
new file mode 100644
index 0000000..d214aef
--- /dev/null
+++ b/src/util/list.c
@@ -0,0 +1,75 @@
+#include <assert.h>
+#include <stdlib.h>
+
+#include "list.h"
+
+void list_init(struct list *head)
+{
+    head->next = head;
+    head->prev = head;
+}
+
+size_t list_length(struct list *head)
+{
+    size_t len = 0;
+    struct list *n = head->next;
+
+    for (; n != head; n = n->next) {
+        len += 1;
+    }
+
+    return len;
+}
+
+void list_append(struct list *head, struct list *n)
+{
+    assert(head && "invalid list pointer");
+    assert(n && "invalid elt pointer");
+
+
+    n->next = head;
+    n->prev = head->prev;
+    n->prev->next = n;
+    head->prev = n;
+}
+
+void list_insert(struct list *head, struct list *n, size_t pos)
+{
+    assert(head && "invalid list pointer");
+    assert(n && "invalid elt pointer");
+
+    struct list *it = head->next;
+    for (; pos > 0; pos--) {
+        if (it == head)
+            break;
+
+        it = it->next;
+    }
+
+    n->prev = it->prev;
+    n->next = it;
+    n->prev->next = n;
+    it->prev = n;
+}
+
+int list_remove(struct list *head, size_t pos)
+{
+    assert(head && "invalid list pointer");
+
+    struct list *it = head->next;
+
+    for (; pos > 0; pos--) {
+        it = it->next;
+
+        if (it == head)
+            return 1;
+    }
+
+    it->prev->next = it->next;
+    it->next->prev = it->prev;
+
+    it->next = it;
+    it->prev = it;
+
+    return 0;
+}
diff --git a/src/util/list.h b/src/util/list.h
new file mode 100644
index 0000000..c9269aa
--- /dev/null
+++ b/src/util/list.h
@@ -0,0 +1,31 @@
+#pragma once
+
+#include "stddef.h"
+
+struct list {
+    struct list *next;
+    struct list *prev;
+};
+
+
+#define LIST_FOR_EACH(Var, List, Field) \
+    for (Var = CONTAINER_OF(List.next, typeof(*Var), Field) ; \
+         &(Var->Field) != &List; \
+         Var = CONTAINER_OF(Var->Field.next, typeof(*Var), Field))
+
+#define CONTAINER_OF(List, Type, Field) \
+    (Type*)((char*)List - offsetof(Type, Field))
+
+
+#define LIST_FRONT(Var, List, Field) \
+    it = CONTAINER_OF(List.next, typeof(*Var), Field)
+
+#define LIST_BACK(Var, List, Field) \
+    it = CONTAINER_OF(List.prev, typeof(*Var), Field)
+
+void list_init(struct list *head);
+
+size_t  list_length(struct list *head);
+void    list_append(struct list *head, struct list *n);
+void    list_insert(struct list *head, struct list *n, size_t pos);
+int     list_remove(struct list *head, size_t pos);
-- 
2.18.0