|
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
|
|
|
18 // the writer creates the a new node, moves m_last to this node and
|
|
|
19 // only after that restores the reference from the previous node
|
|
|
20 // making available the reader to read the new node.
|
|
|
21
|
|
|
22 Node m_first; // position on the node which is already read
|
|
|
23 Node m_last; // position on the node which is already written
|
|
|
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;
|
|
|
38
|
|
|
39 }
|
|
|
40
|
|
|
41 public bool TryDequeue(out T value) {
|
|
|
42 Node first;
|
|
|
43 Node next;
|
|
|
44
|
|
|
45 Thread.MemoryBarrier(); // ensure m_first is fresh
|
|
|
46 SpinWait spin = new SpinWait();
|
|
|
47 do {
|
|
|
48 first = m_first;
|
|
|
49 // aquire-fence
|
|
|
50 next = first.next;
|
|
|
51 if (next == null) {
|
|
|
52 value = default(T);
|
|
|
53 return false;
|
|
|
54 }
|
|
|
55
|
|
|
56 if (first == Interlocked.CompareExchange(ref m_first, next, first))
|
|
|
57 // head succesfully updated
|
|
|
58 break;
|
|
|
59 spin.SpinOnce();
|
|
|
60 } while (true);
|
|
|
61
|
|
|
62 value = next.value;
|
|
|
63 return true;
|
|
|
64 }
|
|
|
65
|
|
|
66 #region IEnumerable implementation
|
|
|
67
|
|
|
68 class Enumerator : IEnumerator<T> {
|
|
|
69 Node m_current;
|
|
|
70 Node m_first;
|
|
|
71
|
|
|
72 public Enumerator(Node first) {
|
|
|
73 m_first = first;
|
|
|
74 }
|
|
|
75
|
|
|
76 #region IEnumerator implementation
|
|
|
77
|
|
|
78 public bool MoveNext() {
|
|
|
79 m_current = m_current == null ? m_first : m_current.next;
|
|
|
80 return m_current != null;
|
|
|
81 }
|
|
|
82
|
|
|
83 public void Reset() {
|
|
|
84 m_current = null;
|
|
|
85 }
|
|
|
86
|
|
|
87 object IEnumerator.Current {
|
|
|
88 get {
|
|
|
89 if (m_current == null)
|
|
|
90 throw new InvalidOperationException();
|
|
|
91 return m_current.value;
|
|
|
92 }
|
|
|
93 }
|
|
|
94
|
|
|
95 #endregion
|
|
|
96
|
|
|
97 #region IDisposable implementation
|
|
|
98
|
|
|
99 public void Dispose() {
|
|
|
100 }
|
|
|
101
|
|
|
102 #endregion
|
|
|
103
|
|
|
104 #region IEnumerator implementation
|
|
|
105
|
|
|
106 public T Current {
|
|
|
107 get {
|
|
|
108 if (m_current == null)
|
|
|
109 throw new InvalidOperationException();
|
|
|
110 return m_current.value;
|
|
|
111 }
|
|
|
112 }
|
|
|
113
|
|
|
114 #endregion
|
|
|
115 }
|
|
|
116
|
|
|
117 public IEnumerator<T> GetEnumerator() {
|
|
|
118 return new Enumerator(m_first);
|
|
|
119 }
|
|
|
120
|
|
|
121 #endregion
|
|
|
122
|
|
|
123 #region IEnumerable implementation
|
|
|
124
|
|
|
125 IEnumerator IEnumerable.GetEnumerator() {
|
|
|
126 return GetEnumerator();
|
|
|
127 }
|
|
|
128
|
|
|
129 #endregion
|
|
|
130 }
|
|
|
131 }
|
