##// END OF EJS Templates
implab » ImplabNet
RSS
fix MTQueue syntax error
cin -
r98:4c945d94b9ab v2
parent child
Show More
Show file before | Show file after | Hide comments
@@ -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 public object IEnumerator.Current {
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