--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Parallels/MTLinkedList.cs	Wed Dec 10 01:29:53 2014 +0100
@@ -0,0 +1,140 @@
+using System;
+using System.Threading;
+
+namespace Implab.Parallels {
+    public class MTLinkedList<TNode> where TNode : MTLinkedListNode<TNode> {
+        TNode m_first;
+        TNode m_last;
+
+        public void InsertAfter( TNode pos, TNode node) {
+            Safe.ArgumentNotNull(node, "node");
+            if (!Attach(node))
+                throw new InvalidOperationException("The specified node already attached to a list");
+
+            TNode next;
+
+            while (true) {
+                // insert first if pos == null
+                next = pos == null ? m_first : pos.next;
+                node.prev = pos;
+                node.next = next;
+                if (next == m_first) {
+                    if (next != Interlocked.CompareExchange(ref m_first, node, next))
+                        continue;
+                    // race
+                } else {
+                    if (next != Interlocked.CompareExchange(ref pos.next, node, next))
+                        continue;
+                    // race
+                }
+                break;
+            }
+
+            while (true) {
+                if (next == null) {
+                    if (pos != Interlocked.CompareExchange(ref m_last, node, pos))
+                        continue;
+                } else {
+                    if (pos != Interlocked.CompareExchange(ref next.prev, node, pos))
+                        continue;
+                }
+                break;
+            }
+        }
+
+        public void InsertBefore( TNode pos, TNode node) {
+            Safe.ArgumentNotNull(node, "node");
+
+            if (!Attach(node))
+                return;
+
+            TNode prev;
+
+            while (true) {
+                // insert first if pos == null
+                prev = pos == null ? m_last : pos.prev;
+                node.next = pos;
+                node.prev = prev;
+                if (prev == m_last) {
+                    if (prev != Interlocked.CompareExchange(ref m_last, node, prev))
+                        continue;
+                    // race
+                } else {
+                    if (prev != Interlocked.CompareExchange(ref pos.prev, node, prev))
+                        continue;
+                    // race
+                }
+                break;
+            }
+
+            while (true) {
+                if (prev == null) {
+                    if (pos != Interlocked.CompareExchange(ref m_first, node, pos))
+                        continue;
+                } else {
+                    if (pos != Interlocked.CompareExchange(ref prev.next, node, pos))
+                        continue;
+                }
+                break;
+            }
+        }
+
+        bool Detach(TNode node) {
+            MTLinkedList<TNode> parent;
+
+            do {
+                parent = node.parentList;
+                if (parent == null || parent != this)
+                    return false;
+            } while(parent != Interlocked.CompareExchange(ref node.parentList, null, parent));
+        }
+
+        bool Attach(TNode node) {
+            MTLinkedList<TNode> parent;
+
+            do {
+                parent = node.parentList;
+                if (parent != null)
+                    return false;
+            } while(parent != Interlocked.CompareExchange(ref node.parentList, this, parent));
+        }
+
+        public void Remove(TNode node) {
+            Safe.ArgumentNotNull(node, "node");
+
+            if (!Detach(node))
+                return;
+
+            TNode prev;
+            TNode next;
+
+            while (true) {
+                prev = node.prev;
+                next = node.next;
+
+                if (prev == null) {
+                    if (node != Interlocked.CompareExchange(ref m_first, next, node))
+                        continue;
+                } else {
+                    if (node != Interlocked.CompareExchange(ref prev.next, next, node))
+                        continue;
+                }
+
+                break;
+            }
+
+            while (true) {
+                if (next == null) {
+                    if (node != Interlocked.CompareExchange(ref m_last, prev, node))
+                        continue;
+                } else {
+                    if (node != Interlocked.CompareExchange(ref next.prev, prev, node))
+                        continue;
+                }
+                break;
+            }
+        }
+
+    }
+}
+