##// END OF EJS Templates
implab » ImplabNet
RSS
added enumerable interface to MTQueue
cin -
r97:b11c7e9d93bc v2
parent child
Show More
Show file before | Show file after | Hide comments
@@ -1,73 +1,143
1 using System.Threading;
1 using System.Threading;
2 using System.Collections.Generic;
3 using System;
4 using System.Collections;
2
5
3 namespace Implab.Parallels {
6 namespace Implab.Parallels {
4 public class MTQueue<T> {
7 public class MTQueue<T> : IEnumerable<T> {
5 class Node {
8 class Node {
6 public Node(T value) {
9 public Node(T value) {
7 this.value = value;
10 this.value = value;
8 }
11 }
9 public readonly T value;
12 public readonly T value;
10 public Node next;
13 public Node next;
11 }
14 }
12
15
13 Node m_first;
16 Node m_first;
14 Node m_last;
17 Node m_last;
15
18
16 public void Enqueue(T value) {
19 public void Enqueue(T value) {
17 Thread.MemoryBarrier();
20 Thread.MemoryBarrier();
18
21
19 var last = m_last;
22 var last = m_last;
20 var next = new Node(value);
23 var next = new Node(value);
21
24
25 // Interlocaked.CompareExchange implies Thread.MemoryBarrier();
26 // to ensure that the next node is completely constructed
22 while (last != Interlocked.CompareExchange(ref m_last, next, last))
27 while (last != Interlocked.CompareExchange(ref m_last, next, last))
23 last = m_last;
28 last = m_last;
24
29
25 if (last != null)
30 if (last != null)
26 last.next = next;
31 last.next = next;
27 else
32 else
28 m_first = next;
33 m_first = next;
29 }
34 }
30
35
31 public bool TryDequeue(out T value) {
36 public bool TryDequeue(out T value) {
32 Node first;
37 Node first;
33 Node next;
38 Node next;
34 value = default(T);
39 value = default(T);
35
40
36 Thread.MemoryBarrier();
41 Thread.MemoryBarrier();
37 do {
42 do {
38 first = m_first;
43 first = m_first;
39 if (first == null)
44 if (first == null)
40 return false;
45 return false;
41 next = first.next;
46 next = first.next;
42 if (next == null) {
47 if (next == null) {
43 // this is the last element,
48 // this is the last element,
44 // then try to update the tail
49 // then try to update the tail
45 if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
50 if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
46 // this is the race condition
51 // this is the race condition
47 if (m_last == null)
52 if (m_last == null)
48 // the queue is empty
53 // the queue is empty
49 return false;
54 return false;
50 // tail has been changed, we need to restart
55 // tail has been changed, we need to restart
51 continue;
56 continue;
52 }
57 }
53
58
54 // tail succesfully updated and first.next will never be changed
59 // tail succesfully updated and first.next will never be changed
55 // 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
56 // 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
57
62
58 // 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
59 // 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
60 Interlocked.CompareExchange(ref m_first, null, first);
65 Interlocked.CompareExchange(ref m_first, null, first);
61 break;
66 break;
62
67
63 }
68 }
64 if (first == Interlocked.CompareExchange(ref m_first, next, first))
69 if (first == Interlocked.CompareExchange(ref m_first, next, first))
65 // head succesfully updated
70 // head succesfully updated
66 break;
71 break;
67 } while (true);
72 } while (true);
68
73
69 value = first.value;
74 value = first.value;
70 return true;
75 return true;
71 }
76 }
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
99 public object IEnumerator.Current {
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
72 }
142 }
73 }
143 }
General Comments 0
You need to be logged in to leave comments. Login now