##// 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 1 using System.Threading;
2 using System.Collections.Generic;
3 using System;
4 using System.Collections;
2 5
3 6 namespace Implab.Parallels {
4 public class MTQueue<T> {
7 public class MTQueue<T> : IEnumerable<T> {
5 8 class Node {
6 9 public Node(T value) {
7 10 this.value = value;
8 11 }
9 12 public readonly T value;
10 13 public Node next;
11 14 }
12 15
13 16 Node m_first;
14 17 Node m_last;
15 18
16 19 public void Enqueue(T value) {
17 20 Thread.MemoryBarrier();
18 21
19 22 var last = m_last;
20 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 27 while (last != Interlocked.CompareExchange(ref m_last, next, last))
23 28 last = m_last;
24 29
25 30 if (last != null)
26 31 last.next = next;
27 32 else
28 33 m_first = next;
29 34 }
30 35
31 36 public bool TryDequeue(out T value) {
32 37 Node first;
33 38 Node next;
34 39 value = default(T);
35 40
36 41 Thread.MemoryBarrier();
37 42 do {
38 43 first = m_first;
39 44 if (first == null)
40 45 return false;
41 46 next = first.next;
42 47 if (next == null) {
43 48 // this is the last element,
44 49 // then try to update the tail
45 50 if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
46 51 // this is the race condition
47 52 if (m_last == null)
48 53 // the queue is empty
49 54 return false;
50 55 // tail has been changed, we need to restart
51 56 continue;
52 57 }
53 58
54 59 // tail succesfully updated and first.next will never be changed
55 60 // other readers will fail due to inconsistency m_last != m_fist && m_first.next == null
56 61 // however the parallel writer may update the m_first since the m_last is null
57 62
58 63 // so we need to fix inconsistency by setting m_first to null or if it has been
59 64 // updated by the writer already then we should just to give up
60 65 Interlocked.CompareExchange(ref m_first, null, first);
61 66 break;
62 67
63 68 }
64 69 if (first == Interlocked.CompareExchange(ref m_first, next, first))
65 70 // head succesfully updated
66 71 break;
67 72 } while (true);
68 73
69 74 value = first.value;
70 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