|
106
|
1 using System;
|
|
|
2 using System.Collections.Generic;
|
|
|
3 using System.Threading;
|
|
|
4 using System.Collections;
|
|
|
5
|
|
|
6 namespace Implab.Parallels {
|
|
|
7 public class MTCustomQueue<TNode> : IEnumerable<TNode> where TNode : MTCustomQueueNode<TNode> {
|
|
|
8 TNode m_first;
|
|
|
9 TNode m_last;
|
|
|
10
|
|
|
11 public void Enqueue(TNode next) {
|
|
|
12 Thread.MemoryBarrier();
|
|
|
13
|
|
|
14 var last = m_last;
|
|
|
15
|
|
|
16 // Interlocaked.CompareExchange implies Thread.MemoryBarrier();
|
|
|
17 // to ensure that the next node is completely constructed
|
|
|
18 while (last != Interlocked.CompareExchange(ref m_last, next, last))
|
|
|
19 last = m_last;
|
|
|
20
|
|
|
21 if (last != null)
|
|
|
22 last.next = next;
|
|
|
23 else
|
|
|
24 m_first = next;
|
|
|
25 }
|
|
|
26
|
|
|
27 public bool TryDequeue(out TNode node) {
|
|
|
28 TNode first;
|
|
|
29 TNode next;
|
|
|
30 node = null;
|
|
|
31
|
|
|
32 Thread.MemoryBarrier();
|
|
|
33 do {
|
|
|
34 first = m_first;
|
|
|
35 if (first == null)
|
|
|
36 return false;
|
|
|
37 next = first.next;
|
|
|
38 if (next == null) {
|
|
|
39 // this is the last element,
|
|
|
40 // then try to update the tail
|
|
|
41 if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
|
|
|
42 // this is the race condition
|
|
|
43 if (m_last == null)
|
|
|
44 // the queue is empty
|
|
|
45 return false;
|
|
|
46 // tail has been changed, we need to restart
|
|
|
47 continue;
|
|
|
48 }
|
|
|
49
|
|
|
50 // tail succesfully updated and first.next will never be changed
|
|
|
51 // other readers will fail due to inconsistency m_last != m_fist && m_first.next == null
|
|
|
52 // however the parallel writer may update the m_first since the m_last is null
|
|
|
53
|
|
|
54 // so we need to fix inconsistency by setting m_first to null or if it has been
|
|
|
55 // updated by the writer already then we should just to give up
|
|
|
56 Interlocked.CompareExchange(ref m_first, null, first);
|
|
|
57 break;
|
|
|
58
|
|
|
59 }
|
|
|
60 if (first == Interlocked.CompareExchange(ref m_first, next, first))
|
|
|
61 // head succesfully updated
|
|
|
62 break;
|
|
|
63 } while (true);
|
|
|
64
|
|
|
65 node = first;
|
|
|
66 return true;
|
|
|
67 }
|
|
|
68
|
|
|
69 #region IEnumerable implementation
|
|
|
70
|
|
|
71 class Enumerator : IEnumerator<TNode> {
|
|
|
72 TNode m_current;
|
|
|
73 TNode m_first;
|
|
|
74
|
|
|
75 public Enumerator(TNode first) {
|
|
|
76 m_first = first;
|
|
|
77 }
|
|
|
78
|
|
|
79 #region IEnumerator implementation
|
|
|
80
|
|
|
81 public bool MoveNext() {
|
|
|
82 m_current = m_current == null ? m_first : m_current.next;
|
|
|
83 return m_current != null;
|
|
|
84 }
|
|
|
85
|
|
|
86 public void Reset() {
|
|
|
87 m_current = null;
|
|
|
88 }
|
|
|
89
|
|
|
90 object IEnumerator.Current {
|
|
|
91 get {
|
|
|
92 if (m_current == null)
|
|
|
93 throw new InvalidOperationException();
|
|
|
94 return m_current;
|
|
|
95 }
|
|
|
96 }
|
|
|
97
|
|
|
98 #endregion
|
|
|
99
|
|
|
100 #region IDisposable implementation
|
|
|
101
|
|
|
102 public void Dispose() {
|
|
|
103 }
|
|
|
104
|
|
|
105 #endregion
|
|
|
106
|
|
|
107 #region IEnumerator implementation
|
|
|
108
|
|
|
109 public TNode Current {
|
|
|
110 get {
|
|
|
111 if (m_current == null)
|
|
|
112 throw new InvalidOperationException();
|
|
|
113 return m_current;
|
|
|
114 }
|
|
|
115 }
|
|
|
116
|
|
|
117 #endregion
|
|
|
118 }
|
|
|
119
|
|
|
120 public IEnumerator<TNode> GetEnumerator() {
|
|
|
121 return new Enumerator(m_first);
|
|
|
122 }
|
|
|
123
|
|
|
124 #endregion
|
|
|
125
|
|
|
126 #region IEnumerable implementation
|
|
|
127
|
|
|
128 IEnumerator IEnumerable.GetEnumerator() {
|
|
|
129 return GetEnumerator();
|
|
|
130 }
|
|
|
131
|
|
|
132 #endregion
|
|
|
133 }
|
|
|
134 }
|
|
|
135
|
