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