|
233
|
1 using System.Threading;
|
|
|
2 using System.Collections.Generic;
|
|
|
3 using System;
|
|
|
4 using System.Collections;
|
|
|
5
|
|
|
6 namespace Implab.Parallels {
|
|
|
7 public class SimpleAsyncQueue<T> : IEnumerable<T> {
|
|
|
8 class Node {
|
|
|
9 public Node(T value) {
|
|
|
10 this.value = value;
|
|
|
11 }
|
|
|
12 public readonly T value;
|
|
|
13 public volatile Node next;
|
|
|
14 }
|
|
|
15
|
|
|
16 // the reader and the writer are mainteined completely independent,
|
|
|
17 // the reader can read next item when m_first.next is not null
|
|
242
|
18 // the writer creates a new node, moves m_last to this node and
|
|
233
|
19 // only after that restores the reference from the previous node
|
|
242
|
20 // making the reader be able to read the new node.
|
|
233
|
21
|
|
242
|
22 volatile Node m_first; // position on the node which is already read
|
|
|
23 volatile Node m_last; // position on the node which is already written
|
|
233
|
24
|
|
|
25 public SimpleAsyncQueue() {
|
|
|
26 m_first = m_last = new Node(default(T));
|
|
|
27 }
|
|
|
28
|
|
|
29 public void Enqueue(T value) {
|
|
|
30 var next = new Node(value);
|
|
|
31
|
|
|
32 // Interlocaked.CompareExchange implies Thread.MemoryBarrier();
|
|
|
33 // to ensure that the next node is completely constructed
|
|
|
34 var last = Interlocked.Exchange(ref m_last, next);
|
|
|
35
|
|
|
36 // release-fence
|
|
|
37 last.next = next;
|
|
242
|
38
|
|
233
|
39 }
|
|
|
40
|
|
|
41 public bool TryDequeue(out T value) {
|
|
242
|
42 Node first = m_first; ;
|
|
|
43 Node next = first.next; ;
|
|
|
44
|
|
|
45 if (next == null) {
|
|
|
46 value = default(T);
|
|
|
47 return false;
|
|
|
48 }
|
|
|
49
|
|
|
50 var first2 = Interlocked.CompareExchange(ref m_first, next, first);
|
|
|
51
|
|
|
52 if (first != first2) {
|
|
|
53 // head is updated by someone else
|
|
233
|
54
|
|
242
|
55 SpinWait spin = new SpinWait();
|
|
|
56 do {
|
|
|
57 first = first2;
|
|
|
58 next = first.next;
|
|
|
59 if (next == null) {
|
|
|
60 value = default(T);
|
|
|
61 return false;
|
|
|
62 }
|
|
|
63
|
|
|
64 first2 = Interlocked.CompareExchange(ref m_first, next, first);
|
|
|
65 if (first == first2)
|
|
|
66 break;
|
|
|
67 spin.SpinOnce();
|
|
|
68 } while (true);
|
|
|
69 }
|
|
233
|
70
|
|
|
71 value = next.value;
|
|
|
72 return true;
|
|
|
73 }
|
|
|
74
|
|
|
75 #region IEnumerable implementation
|
|
|
76
|
|
|
77 class Enumerator : IEnumerator<T> {
|
|
|
78 Node m_current;
|
|
|
79 Node m_first;
|
|
|
80
|
|
|
81 public Enumerator(Node first) {
|
|
|
82 m_first = first;
|
|
|
83 }
|
|
|
84
|
|
|
85 #region IEnumerator implementation
|
|
|
86
|
|
|
87 public bool MoveNext() {
|
|
|
88 m_current = m_current == null ? m_first : m_current.next;
|
|
|
89 return m_current != null;
|
|
|
90 }
|
|
|
91
|
|
|
92 public void Reset() {
|
|
|
93 m_current = null;
|
|
|
94 }
|
|
|
95
|
|
|
96 object IEnumerator.Current {
|
|
|
97 get {
|
|
|
98 if (m_current == null)
|
|
|
99 throw new InvalidOperationException();
|
|
|
100 return m_current.value;
|
|
|
101 }
|
|
|
102 }
|
|
|
103
|
|
|
104 #endregion
|
|
|
105
|
|
|
106 #region IDisposable implementation
|
|
|
107
|
|
|
108 public void Dispose() {
|
|
|
109 }
|
|
|
110
|
|
|
111 #endregion
|
|
|
112
|
|
|
113 #region IEnumerator implementation
|
|
|
114
|
|
|
115 public T Current {
|
|
|
116 get {
|
|
|
117 if (m_current == null)
|
|
|
118 throw new InvalidOperationException();
|
|
|
119 return m_current.value;
|
|
|
120 }
|
|
|
121 }
|
|
|
122
|
|
|
123 #endregion
|
|
|
124 }
|
|
|
125
|
|
|
126 public IEnumerator<T> GetEnumerator() {
|
|
|
127 return new Enumerator(m_first);
|
|
|
128 }
|
|
|
129
|
|
|
130 #endregion
|
|
|
131
|
|
|
132 #region IEnumerable implementation
|
|
|
133
|
|
|
134 IEnumerator IEnumerable.GetEnumerator() {
|
|
|
135 return GetEnumerator();
|
|
|
136 }
|
|
|
137
|
|
|
138 #endregion
|
|
|
139 }
|
|
|
140 }
|
