# HG changeset patch
# User cin
# Date 2014-12-10 00:29:53
# Node ID 468d156e434efb847dcfffc6d7463ad6e3f7f499
# Parent  38d6a4db35d7743284d2b6a08bc1dd899c116036

working on linked list

diff --git a/Implab/Implab.csproj b/Implab/Implab.csproj
--- a/Implab/Implab.csproj
+++ b/Implab/Implab.csproj
@@ -150,6 +150,8 @@
     <Compile Include="PromiseEventType.cs" />
     <Compile Include="Parallels\MTCustomQueue.cs" />
     <Compile Include="Parallels\MTCustomQueueNode.cs" />
+    <Compile Include="Parallels\MTLinkedList.cs" />
+    <Compile Include="Parallels\MTLinkedListNode.cs" />
   </ItemGroup>
   <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
   <ItemGroup />
diff --git a/Implab/Parallels/MTLinkedList.cs b/Implab/Parallels/MTLinkedList.cs
new file mode 100644
--- /dev/null
+++ b/Implab/Parallels/MTLinkedList.cs
@@ -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;
+            }
+        }
+
+    }
+}
+
diff --git a/Implab/Parallels/MTLinkedListNode.cs b/Implab/Parallels/MTLinkedListNode.cs
new file mode 100644
--- /dev/null
+++ b/Implab/Parallels/MTLinkedListNode.cs
@@ -0,0 +1,10 @@
+using System;
+
+namespace Implab.Parallels {
+    public class MTLinkedListNode<TNode> where T : MTLinkedListNode<TNode> {
+        public MTLinkedList<TNode> parentList;  
+        public TNode next;
+        public TNode prev;
+    }
+}
+