|
113
|
1 using System;
|
|
|
2 using System.Threading;
|
|
|
3
|
|
|
4 namespace Implab.Parallels {
|
|
|
5 public class MTLinkedList<TNode> where TNode : MTLinkedListNode<TNode> {
|
|
|
6 TNode m_first;
|
|
|
7 TNode m_last;
|
|
|
8
|
|
|
9 public void InsertAfter( TNode pos, TNode node) {
|
|
|
10 Safe.ArgumentNotNull(node, "node");
|
|
|
11 if (!Attach(node))
|
|
|
12 throw new InvalidOperationException("The specified node already attached to a list");
|
|
|
13
|
|
|
14 TNode next;
|
|
|
15
|
|
|
16 while (true) {
|
|
|
17 // insert first if pos == null
|
|
|
18 next = pos == null ? m_first : pos.next;
|
|
|
19 node.prev = pos;
|
|
|
20 node.next = next;
|
|
|
21 if (next == m_first) {
|
|
|
22 if (next != Interlocked.CompareExchange(ref m_first, node, next))
|
|
|
23 continue;
|
|
|
24 // race
|
|
|
25 } else {
|
|
|
26 if (next != Interlocked.CompareExchange(ref pos.next, node, next))
|
|
|
27 continue;
|
|
|
28 // race
|
|
|
29 }
|
|
|
30 break;
|
|
|
31 }
|
|
|
32
|
|
|
33 while (true) {
|
|
|
34 if (next == null) {
|
|
|
35 if (pos != Interlocked.CompareExchange(ref m_last, node, pos))
|
|
|
36 continue;
|
|
|
37 } else {
|
|
|
38 if (pos != Interlocked.CompareExchange(ref next.prev, node, pos))
|
|
|
39 continue;
|
|
|
40 }
|
|
|
41 break;
|
|
|
42 }
|
|
|
43 }
|
|
|
44
|
|
|
45 public void InsertBefore( TNode pos, TNode node) {
|
|
|
46 Safe.ArgumentNotNull(node, "node");
|
|
|
47
|
|
|
48 if (!Attach(node))
|
|
|
49 return;
|
|
|
50
|
|
|
51 TNode prev;
|
|
|
52
|
|
|
53 while (true) {
|
|
|
54 // insert first if pos == null
|
|
|
55 prev = pos == null ? m_last : pos.prev;
|
|
|
56 node.next = pos;
|
|
|
57 node.prev = prev;
|
|
|
58 if (prev == m_last) {
|
|
|
59 if (prev != Interlocked.CompareExchange(ref m_last, node, prev))
|
|
|
60 continue;
|
|
|
61 // race
|
|
|
62 } else {
|
|
|
63 if (prev != Interlocked.CompareExchange(ref pos.prev, node, prev))
|
|
|
64 continue;
|
|
|
65 // race
|
|
|
66 }
|
|
|
67 break;
|
|
|
68 }
|
|
|
69
|
|
|
70 while (true) {
|
|
|
71 if (prev == null) {
|
|
|
72 if (pos != Interlocked.CompareExchange(ref m_first, node, pos))
|
|
|
73 continue;
|
|
|
74 } else {
|
|
|
75 if (pos != Interlocked.CompareExchange(ref prev.next, node, pos))
|
|
|
76 continue;
|
|
|
77 }
|
|
|
78 break;
|
|
|
79 }
|
|
|
80 }
|
|
|
81
|
|
|
82 bool Detach(TNode node) {
|
|
|
83 MTLinkedList<TNode> parent;
|
|
|
84
|
|
|
85 do {
|
|
|
86 parent = node.parentList;
|
|
|
87 if (parent == null || parent != this)
|
|
|
88 return false;
|
|
|
89 } while(parent != Interlocked.CompareExchange(ref node.parentList, null, parent));
|
|
|
90 }
|
|
|
91
|
|
|
92 bool Attach(TNode node) {
|
|
|
93 MTLinkedList<TNode> parent;
|
|
|
94
|
|
|
95 do {
|
|
|
96 parent = node.parentList;
|
|
|
97 if (parent != null)
|
|
|
98 return false;
|
|
|
99 } while(parent != Interlocked.CompareExchange(ref node.parentList, this, parent));
|
|
|
100 }
|
|
|
101
|
|
|
102 public void Remove(TNode node) {
|
|
|
103 Safe.ArgumentNotNull(node, "node");
|
|
|
104
|
|
|
105 if (!Detach(node))
|
|
|
106 return;
|
|
|
107
|
|
|
108 TNode prev;
|
|
|
109 TNode next;
|
|
|
110
|
|
|
111 while (true) {
|
|
|
112 prev = node.prev;
|
|
|
113 next = node.next;
|
|
|
114
|
|
|
115 if (prev == null) {
|
|
|
116 if (node != Interlocked.CompareExchange(ref m_first, next, node))
|
|
|
117 continue;
|
|
|
118 } else {
|
|
|
119 if (node != Interlocked.CompareExchange(ref prev.next, next, node))
|
|
|
120 continue;
|
|
|
121 }
|
|
|
122
|
|
|
123 break;
|
|
|
124 }
|
|
|
125
|
|
|
126 while (true) {
|
|
|
127 if (next == null) {
|
|
|
128 if (node != Interlocked.CompareExchange(ref m_last, prev, node))
|
|
|
129 continue;
|
|
|
130 } else {
|
|
|
131 if (node != Interlocked.CompareExchange(ref next.prev, prev, node))
|
|
|
132 continue;
|
|
|
133 }
|
|
|
134 break;
|
|
|
135 }
|
|
|
136 }
|
|
|
137
|
|
|
138 }
|
|
|
139 }
|
|
|
140
|
