Mercurial > pub > ImplabNet
annotate Implab/Parallels/MTQueue.cs @ 169:54270c2f29f2 ref20160224
DFA refactoring
| author | cin |
|---|---|
| date | Thu, 03 Mar 2016 08:41:02 +0300 |
| parents | 4c945d94b9ab |
| children |
| rev | line source |
|---|---|
| 93 | 1 using System.Threading; |
| 97 | 2 using System.Collections.Generic; |
| 3 using System; | |
| 4 using System.Collections; | |
| 14 | 5 |
| 6 namespace Implab.Parallels { | |
| 97 | 7 public class MTQueue<T> : IEnumerable<T> { |
| 14 | 8 class Node { |
| 9 public Node(T value) { | |
| 10 this.value = value; | |
| 11 } | |
| 12 public readonly T value; | |
| 13 public Node next; | |
| 14 } | |
| 15 | |
| 16 Node m_first; | |
| 17 Node m_last; | |
| 18 | |
| 19 public void Enqueue(T value) { | |
| 80 | 20 Thread.MemoryBarrier(); |
| 21 | |
| 14 | 22 var last = m_last; |
| 23 var next = new Node(value); | |
| 24 | |
| 97 | 25 // Interlocaked.CompareExchange implies Thread.MemoryBarrier(); |
| 26 // to ensure that the next node is completely constructed | |
| 14 | 27 while (last != Interlocked.CompareExchange(ref m_last, next, last)) |
| 28 last = m_last; | |
| 29 | |
| 30 if (last != null) | |
| 31 last.next = next; | |
| 32 else | |
| 33 m_first = next; | |
| 34 } | |
| 35 | |
| 36 public bool TryDequeue(out T value) { | |
| 37 Node first; | |
| 93 | 38 Node next; |
| 14 | 39 value = default(T); |
| 40 | |
| 80 | 41 Thread.MemoryBarrier(); |
| 14 | 42 do { |
| 43 first = m_first; | |
| 44 if (first == null) | |
| 45 return false; | |
| 46 next = first.next; | |
| 47 if (next == null) { | |
| 48 // this is the last element, | |
|
19
e3935fdf59a2
Promise is rewritten to use interlocked operations instead of locks
cin
parents:
14
diff
changeset
|
49 // then try to update the tail |
| 14 | 50 if (first != Interlocked.CompareExchange(ref m_last, null, first)) { |
| 71 | 51 // this is the race condition |
| 14 | 52 if (m_last == null) |
|
19
e3935fdf59a2
Promise is rewritten to use interlocked operations instead of locks
cin
parents:
14
diff
changeset
|
53 // the queue is empty |
| 14 | 54 return false; |
| 71 | 55 // tail has been changed, we need to restart |
| 14 | 56 continue; |
| 57 } | |
| 58 | |
| 59 // tail succesfully updated and first.next will never be changed | |
| 71 | 60 // other readers will fail due to inconsistency m_last != m_fist && m_first.next == null |
| 61 // however the parallel writer may update the m_first since the m_last is null | |
| 14 | 62 |
| 71 | 63 // so we need to fix inconsistency by setting m_first to null or if it has been |
| 64 // updated by the writer already then we should just to give up | |
| 14 | 65 Interlocked.CompareExchange(ref m_first, null, first); |
| 66 break; | |
| 67 | |
| 68 } | |
| 93 | 69 if (first == Interlocked.CompareExchange(ref m_first, next, first)) |
| 70 // head succesfully updated | |
| 71 break; | |
| 14 | 72 } while (true); |
| 73 | |
| 74 value = first.value; | |
| 75 return true; | |
| 76 } | |
| 97 | 77 |
| 78 #region IEnumerable implementation | |
| 79 | |
| 80 class Enumerator : IEnumerator<T> { | |
| 81 Node m_current; | |
| 82 Node m_first; | |
| 83 | |
| 84 public Enumerator(Node first) { | |
| 85 m_first = first; | |
| 86 } | |
| 87 | |
| 88 #region IEnumerator implementation | |
| 89 | |
| 90 public bool MoveNext() { | |
| 91 m_current = m_current == null ? m_first : m_current.next; | |
| 92 return m_current != null; | |
| 93 } | |
| 94 | |
| 95 public void Reset() { | |
| 96 m_current = null; | |
| 97 } | |
| 98 | |
| 98 | 99 object IEnumerator.Current { |
| 97 | 100 get { |
| 101 if (m_current == null) | |
| 102 throw new InvalidOperationException(); | |
| 103 return m_current.value; | |
| 104 } | |
| 105 } | |
| 106 | |
| 107 #endregion | |
| 108 | |
| 109 #region IDisposable implementation | |
| 110 | |
| 111 public void Dispose() { | |
| 112 } | |
| 113 | |
| 114 #endregion | |
| 115 | |
| 116 #region IEnumerator implementation | |
| 117 | |
| 118 public T Current { | |
| 119 get { | |
| 120 if (m_current == null) | |
| 121 throw new InvalidOperationException(); | |
| 122 return m_current.value; | |
| 123 } | |
| 124 } | |
| 125 | |
| 126 #endregion | |
| 127 } | |
| 128 | |
| 129 public IEnumerator<T> GetEnumerator() { | |
| 130 return new Enumerator(m_first); | |
| 131 } | |
| 132 | |
| 133 #endregion | |
| 134 | |
| 135 #region IEnumerable implementation | |
| 136 | |
| 137 IEnumerator IEnumerable.GetEnumerator() { | |
| 138 return GetEnumerator(); | |
| 139 } | |
| 140 | |
| 141 #endregion | |
| 14 | 142 } |
| 143 } |