|
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,
|
|
|
45 // then try to update tail
|
|
|
46 if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
|
|
|
47 // this is inconsistent situation which means that the queue is empty
|
|
|
48 if (m_last == null)
|
|
|
49 return false;
|
|
|
50 // tail has been changed, that means that we need to restart
|
|
|
51 continue;
|
|
|
52 }
|
|
|
53
|
|
|
54 // tail succesfully updated and first.next will never be changed
|
|
|
55 // other readers will fail due to inconsistency m_last != m_fist, but m_first.next == null
|
|
|
56 // but the writer may update the m_first since the m_last is null
|
|
|
57
|
|
|
58 // so we need to fix inconsistency by setting m_first to null, but if it already has been
|
|
|
59 // updated by a writer then we should just give up
|
|
|
60 Interlocked.CompareExchange(ref m_first, null, first);
|
|
|
61 break;
|
|
|
62
|
|
|
63 } else {
|
|
|
64 if (first == Interlocked.CompareExchange(ref m_first, next, first))
|
|
|
65 // head succesfully updated
|
|
|
66 break;
|
|
|
67 }
|
|
|
68 } while (true);
|
|
|
69
|
|
|
70 value = first.value;
|
|
|
71 return true;
|
|
|
72 }
|
|
|
73 }
|
|
|
74 }
|
