annotate Implab/Parallels/MTCustomQueue.cs @ 113:468d156e434e v2-1

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