annotate Implab/Parallels/MTQueue.cs @ 111:0fdaf280c797 v1

minor fix
author cin
date Wed, 19 Nov 2014 03:18:42 +0400
parents 1714fd8678ef
children 4f20870d0816
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
1 using System;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
2 using System.Collections.Generic;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
3 using System.Linq;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
4 using System.Text;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
5 using System.Threading;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
6
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
7 namespace Implab.Parallels {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
8 public class MTQueue<T> {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
9 class Node {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
10 public Node(T value) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
11 this.value = value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
12 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
13 public readonly T value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
14 public Node next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
15 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
16
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
17 Node m_first;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
18 Node m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
19
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
20 public void Enqueue(T value) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
21 var last = m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
22 var next = new Node(value);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
23
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
24 while (last != Interlocked.CompareExchange(ref m_last, next, last))
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
25 last = m_last;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
26
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
27 if (last != null)
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
28 last.next = next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
29 else
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
30 m_first = next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
31 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
32
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
33 public bool TryDequeue(out T value) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
34 Node first;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
35 Node next = null;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
36 value = default(T);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
37
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
38 do {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
39 first = m_first;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
40 if (first == null)
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
41 return false;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
42 next = first.next;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
43 if (next == null) {
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
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
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
46 if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
47 // this is the race condition
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
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
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
50 return false;
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
51 // tail has been changed, we need to restart
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
52 continue;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
53 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
54
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
55 // tail succesfully updated and first.next will never be changed
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
56 // other readers will fail due to inconsistency m_last != m_fist && m_first.next == null
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
57 // however the parallel writer may update the m_first since the m_last is null
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
58
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
59 // so we need to fix inconsistency by setting m_first to null or if it has been
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
60 // updated by the writer already then we should just to give up
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
61 Interlocked.CompareExchange(ref m_first, null, first);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
62 break;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
63
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
64 } else {
71
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
65 if (first == Interlocked.CompareExchange(ref m_first, next, first))
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
66 // head succesfully updated
1714fd8678ef code cleanup
cin
parents: 24
diff changeset
67 break;
14
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
68 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
69 } while (true);
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
70
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
71 value = first.value;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
72 return true;
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
73 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
74 }
e943453e5039 Implemented interllocked queue
cin
parents:
diff changeset
75 }