Mercurial > pub > ImplabNet
annotate Implab/Parallels/MTQueue.cs @ 94:a43745f81f10 v2
minor fixes
| author | cin |
|---|---|
| date | Thu, 23 Oct 2014 17:50:09 +0400 |
| parents | dc4942d09e74 |
| children | b11c7e9d93bc |
| rev | line source |
|---|---|
| 93 | 1 using System.Threading; |
| 14 | 2 |
| 3 namespace Implab.Parallels { | |
| 4 public class MTQueue<T> { | |
| 5 class Node { | |
| 6 public Node(T value) { | |
| 7 this.value = value; | |
| 8 } | |
| 9 public readonly T value; | |
| 10 public Node next; | |
| 11 } | |
| 12 | |
| 13 Node m_first; | |
| 14 Node m_last; | |
| 15 | |
| 16 public void Enqueue(T value) { | |
| 80 | 17 Thread.MemoryBarrier(); |
| 18 | |
| 14 | 19 var last = m_last; |
| 20 var next = new Node(value); | |
| 21 | |
| 22 while (last != Interlocked.CompareExchange(ref m_last, next, last)) | |
| 23 last = m_last; | |
| 24 | |
| 25 if (last != null) | |
| 26 last.next = next; | |
| 27 else | |
| 28 m_first = next; | |
| 29 } | |
| 30 | |
| 31 public bool TryDequeue(out T value) { | |
| 32 Node first; | |
| 93 | 33 Node next; |
| 14 | 34 value = default(T); |
| 35 | |
| 80 | 36 Thread.MemoryBarrier(); |
| 14 | 37 do { |
| 38 first = m_first; | |
| 39 if (first == null) | |
| 40 return false; | |
| 41 next = first.next; | |
| 42 if (next == null) { | |
| 43 // this is the last element, | |
|
19
e3935fdf59a2
Promise is rewritten to use interlocked operations instead of locks
cin
parents:
14
diff
changeset
|
44 // then try to update the tail |
| 14 | 45 if (first != Interlocked.CompareExchange(ref m_last, null, first)) { |
| 71 | 46 // this is the race condition |
| 14 | 47 if (m_last == null) |
|
19
e3935fdf59a2
Promise is rewritten to use interlocked operations instead of locks
cin
parents:
14
diff
changeset
|
48 // the queue is empty |
| 14 | 49 return false; |
| 71 | 50 // tail has been changed, we need to restart |
| 14 | 51 continue; |
| 52 } | |
| 53 | |
| 54 // tail succesfully updated and first.next will never be changed | |
| 71 | 55 // other readers will fail due to inconsistency m_last != m_fist && m_first.next == null |
| 56 // however the parallel writer may update the m_first since the m_last is null | |
| 14 | 57 |
| 71 | 58 // so we need to fix inconsistency by setting m_first to null or if it has been |
| 59 // updated by the writer already then we should just to give up | |
| 14 | 60 Interlocked.CompareExchange(ref m_first, null, first); |
| 61 break; | |
| 62 | |
| 63 } | |
| 93 | 64 if (first == Interlocked.CompareExchange(ref m_first, next, first)) |
| 65 // head succesfully updated | |
| 66 break; | |
| 14 | 67 } while (true); |
| 68 | |
| 69 value = first.value; | |
| 70 return true; | |
| 71 } | |
| 72 } | |
| 73 } |