annotate Implab/Parallels/MTQueue.cs @ 17:7cd4a843b4e4 promises

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