annotate Implab/Parallels/MTQueue.cs @ 187:dd4a3590f9c6 ref20160224

Reworked cancelation handling, if the cancel handler isn't specified the OperationCanceledException will be handled by the error handler Any unhandled OperationCanceledException will cause the promise cancelation
author cin
date Tue, 19 Apr 2016 17:35:20 +0300
parents 4c945d94b9ab
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
93
dc4942d09e74 improved tracing
cin
parents: 80
diff changeset
1 using System.Threading;
97
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
2 using System.Collections.Generic;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
3 using System;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
4 using System.Collections;
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
5
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
6 namespace Implab.Parallels {
97
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
7 public class MTQueue<T> : IEnumerable<T> {
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
8 class Node {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
9 public Node(T value) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
10 this.value = value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
11 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
12 public readonly T value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
13 public Node next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
14 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
15
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
16 Node m_first;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
17 Node m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
18
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
19 public void Enqueue(T value) {
80
4f20870d0816 added memory barriers
cin
parents: 71
diff changeset
20 Thread.MemoryBarrier();
4f20870d0816 added memory barriers
cin
parents: 71
diff changeset
21
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
22 var last = m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
23 var next = new Node(value);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
24
97
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
25 // Interlocaked.CompareExchange implies Thread.MemoryBarrier();
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
26 // to ensure that the next node is completely constructed
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
27 while (last != Interlocked.CompareExchange(ref m_last, next, last))
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
28 last = m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
29
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
30 if (last != null)
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
31 last.next = next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
32 else
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
33 m_first = next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
34 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
35
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
36 public bool TryDequeue(out T value) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
37 Node first;
93
dc4942d09e74 improved tracing
cin
parents: 80
diff changeset
38 Node next;
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
39 value = default(T);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
40
80
4f20870d0816 added memory barriers
cin
parents: 71
diff changeset
41 Thread.MemoryBarrier();
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
42 do {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
43 first = m_first;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
44 if (first == null)
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
45 return false;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
46 next = first.next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
47 if (next == null) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
48 // this is the last element,
19
e3935fdf59a2 Promise is rewritten to use interlocked operations instead of locks
cin
parents: 14
diff changeset
49 // then try to update the tail
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
50 if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
51 // this is the race condition
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
52 if (m_last == null)
19
e3935fdf59a2 Promise is rewritten to use interlocked operations instead of locks
cin
parents: 14
diff changeset
53 // the queue is empty
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
54 return false;
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
55 // tail has been changed, we need to restart
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
56 continue;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
57 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
58
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
59 // tail succesfully updated and first.next will never be changed
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
60 // other readers will fail due to inconsistency m_last != m_fist && m_first.next == null
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
61 // however the parallel writer may update the m_first since the m_last is null
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
62
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
63 // so we need to fix inconsistency by setting m_first to null or if it has been
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
64 // updated by the writer already then we should just to give up
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
65 Interlocked.CompareExchange(ref m_first, null, first);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
66 break;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
67
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
68 }
93
dc4942d09e74 improved tracing
cin
parents: 80
diff changeset
69 if (first == Interlocked.CompareExchange(ref m_first, next, first))
dc4942d09e74 improved tracing
cin
parents: 80
diff changeset
70 // head succesfully updated
dc4942d09e74 improved tracing
cin
parents: 80
diff changeset
71 break;
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
72 } while (true);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
73
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
74 value = first.value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
75 return true;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
76 }
97
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
77
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
78 #region IEnumerable implementation
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
79
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
80 class Enumerator : IEnumerator<T> {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
81 Node m_current;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
82 Node m_first;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
83
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
84 public Enumerator(Node first) {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
85 m_first = first;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
86 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
87
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
88 #region IEnumerator implementation
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
89
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
90 public bool MoveNext() {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
91 m_current = m_current == null ? m_first : m_current.next;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
92 return m_current != null;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
93 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
94
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
95 public void Reset() {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
96 m_current = null;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
97 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
98
98
4c945d94b9ab fix MTQueue syntax error
cin
parents: 97
diff changeset
99 object IEnumerator.Current {
97
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
100 get {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
101 if (m_current == null)
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
102 throw new InvalidOperationException();
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
103 return m_current.value;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
104 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
105 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
106
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
107 #endregion
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
108
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
109 #region IDisposable implementation
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
110
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
111 public void Dispose() {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
112 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
113
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
114 #endregion
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
115
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
116 #region IEnumerator implementation
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
117
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
118 public T Current {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
119 get {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
120 if (m_current == null)
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
121 throw new InvalidOperationException();
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
122 return m_current.value;
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
123 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
124 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
125
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
126 #endregion
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
127 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
128
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
129 public IEnumerator<T> GetEnumerator() {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
130 return new Enumerator(m_first);
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
131 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
132
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
133 #endregion
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
134
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
135 #region IEnumerable implementation
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
136
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
137 IEnumerator IEnumerable.GetEnumerator() {
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
138 return GetEnumerator();
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
139 }
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
140
b11c7e9d93bc added enumerable interface to MTQueue
cin
parents: 93
diff changeset
141 #endregion
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
142 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
143 }