Mercurial > pub > ImplabNet
annotate Implab/Parallels/MTQueue.cs @ 147:25cdef49102f v2
sync
author | cin |
---|---|
date | Tue, 17 Mar 2015 08:25:35 +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 } |