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