Mercurial > pub > ImplabNet

comparison Implab/Parallels/MTCustomQueue.cs @ 106:d4e38929ce36 v2

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
promises refactoring
author cin
date Mon, 10 Nov 2014 18:00:28 +0300
parents
children
comparison
equal deleted inserted replaced
105:4d308952fd5e 106:d4e38929ce36
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