MTCustomQueue.cs
135 lines
| 3.9 KiB
| text/x-csharp
|
CSharpLexer
cin
|
r106 | 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 | ||||
| } | ||||
| } | ||||