From 0abcaa8189595e45578ae7ae35a4871a12799b9b Mon Sep 17 00:00:00 2001
From: TimePath <andrew.hardaker1995@gmail.com>
Date: Fri, 16 Oct 2015 09:10:48 +1100
Subject: [PATCH] lib: add LinkedList

---
 qcsrc/lib/_all.inc      |  1 +
 qcsrc/lib/linkedlist.qh | 57 +++++++++++++++++++++++++++++++++++++++++
 2 files changed, 58 insertions(+)
 create mode 100644 qcsrc/lib/linkedlist.qh

diff --git a/qcsrc/lib/_all.inc b/qcsrc/lib/_all.inc
index 49b8ef7798..9bc9ca2aef 100644
--- a/qcsrc/lib/_all.inc
+++ b/qcsrc/lib/_all.inc
@@ -41,6 +41,7 @@
 #include "int.qh"
 #include "iter.qh"
 #include "lazy.qh"
+#include "linkedlist.qh"
 #include "log.qh"
 #include "math.qh"
 #include "misc.qh"
diff --git a/qcsrc/lib/linkedlist.qh b/qcsrc/lib/linkedlist.qh
new file mode 100644
index 0000000000..be57bb5bf9
--- /dev/null
+++ b/qcsrc/lib/linkedlist.qh
@@ -0,0 +1,57 @@
+#ifndef LINKEDLIST_H
+#define LINKEDLIST_H
+
+CLASS(LinkedListNode, Object)
+    ATTRIB(LinkedListNode, ll_data, entity, NULL)
+    ATTRIB(LinkedListNode, ll_prev, LinkedListNode, NULL)
+    ATTRIB(LinkedListNode, ll_next, LinkedListNode, NULL)
+ENDCLASS(LinkedListNode)
+
+CLASS(LinkedList, Object)
+    ATTRIB(LinkedList, ll_head, LinkedListNode, NULL);
+    ATTRIB(LinkedList, ll_tail, LinkedListNode, NULL);
+ENDCLASS(LinkedList)
+
+#define LL_NEW() NEW(LinkedList)
+
+/**
+ * Push to tail
+ */
+entity LL_PUSH(LinkedList this, entity e) {
+    LinkedListNode n = NEW(LinkedListNode);
+    n.ll_data = e;
+    n.ll_prev = this.ll_tail;
+    LinkedListNode tail = this.ll_tail;
+    if (tail) {
+        tail.ll_next = n;
+    } else {
+        this.ll_head = this.ll_tail = n;
+    }
+    return e;
+}
+
+/**
+ * Pop from tail
+ */
+entity LL_POP(LinkedList this) {
+    if (!this.ll_tail) return NULL;
+    LinkedListNode n = this.ll_tail;
+    entity e = n.ll_data;
+    LinkedListNode prev = n.ll_prev;
+    if (prev) {
+        prev.ll_next = NULL;
+    } else {
+        this.ll_head = this.ll_tail = NULL;
+    }
+    return e;
+}
+
+#define LL_EACH(list, cond, body) do {                                  \
+    noref int i = 0;                                                    \
+    for (entity _it = list.ll_head; _it; (_it = _it.ll_next, ++i)) {    \
+        noref entity it = _it.ll_data;                                  \
+        if (cond) { body }                                              \
+    }                                                                   \
+} while(0)
+
+#endif
-- 
2.39.2