--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Implab/Parallels/MTCustomQueue.cs	Mon Nov 10 18:00:28 2014 +0300
@@ -0,0 +1,135 @@
+using System;
+using System.Collections.Generic;
+using System.Threading;
+using System.Collections;
+
+namespace Implab.Parallels {
+    public class MTCustomQueue<TNode> : IEnumerable<TNode> where TNode : MTCustomQueueNode<TNode> {
+        TNode m_first;
+        TNode m_last;
+
+        public void Enqueue(TNode next) {
+            Thread.MemoryBarrier();
+
+            var last = m_last;
+
+            // Interlocaked.CompareExchange implies Thread.MemoryBarrier();
+            // to ensure that the next node is completely constructed
+            while (last != Interlocked.CompareExchange(ref m_last, next, last))
+                last = m_last;
+
+            if (last != null)
+                last.next = next;
+            else
+                m_first = next;
+        }
+
+        public bool TryDequeue(out TNode node) {
+            TNode first;
+            TNode next;
+            node = null;
+
+            Thread.MemoryBarrier();
+            do {
+                first = m_first;
+                if (first == null)
+                    return false;
+                next = first.next;
+                if (next == null) {
+                    // this is the last element,
+                    // then try to update the tail
+                    if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
+                        // this is the race condition
+                        if (m_last == null)
+                            // the queue is empty
+                            return false;
+                        // tail has been changed, we need to restart
+                        continue; 
+                    }
+
+                    // tail succesfully updated and first.next will never be changed
+                    // other readers will fail due to inconsistency m_last != m_fist && m_first.next == null
+                    // however the parallel writer may update the m_first since the m_last is null
+
+                    // so we need to fix inconsistency by setting m_first to null or if it has been
+                    // updated by the writer already then we should just to give up
+                    Interlocked.CompareExchange(ref m_first, null, first);
+                    break;
+
+                }
+                if (first == Interlocked.CompareExchange(ref m_first, next, first))
+                    // head succesfully updated
+                    break;
+            } while (true);
+
+            node = first;
+            return true;
+        }
+
+        #region IEnumerable implementation
+
+        class Enumerator : IEnumerator<TNode> {
+            TNode m_current;
+            TNode m_first;
+
+            public Enumerator(TNode first) {
+                m_first = first;
+            }
+
+            #region IEnumerator implementation
+
+            public bool MoveNext() {
+                m_current = m_current == null ? m_first : m_current.next;
+                return m_current != null;
+            }
+
+            public void Reset() {
+                m_current = null;
+            }
+
+            object IEnumerator.Current {
+                get {
+                    if (m_current == null)
+                        throw new InvalidOperationException();
+                    return m_current;
+                }
+            }
+
+            #endregion
+
+            #region IDisposable implementation
+
+            public void Dispose() {
+            }
+
+            #endregion
+
+            #region IEnumerator implementation
+
+            public TNode Current {
+                get {
+                    if (m_current == null)
+                        throw new InvalidOperationException();
+                    return m_current;
+                }
+            }
+
+            #endregion
+        }
+
+        public IEnumerator<TNode> GetEnumerator() {
+            return new Enumerator(m_first);
+        }
+
+        #endregion
+
+        #region IEnumerable implementation
+
+        IEnumerator IEnumerable.GetEnumerator() {
+            return GetEnumerator();
+        }
+
+        #endregion
+    }
+}
+