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