##// END OF EJS Templates
implab » ImplabNet
RSS
working on linked list
cin -
r113:468d156e434e v2-1
parent child
Show More
Show file before | Show file after | Hide comments
@@ -0,0 +1,140
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
Show file before | Show file after | Hide comments
@@ -0,0 +1,10
1 using System;
2
3 namespace Implab.Parallels {
4 public class MTLinkedListNode<TNode> where T : MTLinkedListNode<TNode> {
5 public MTLinkedList<TNode> parentList;
6 public TNode next;
7 public TNode prev;
8 }
9 }
10
Show file before | Show file after | Hide comments
@@ -150,6 +150,8
150 <Compile Include="PromiseEventType.cs" />
150 <Compile Include="PromiseEventType.cs" />
151 <Compile Include="Parallels\MTCustomQueue.cs" />
151 <Compile Include="Parallels\MTCustomQueue.cs" />
152 <Compile Include="Parallels\MTCustomQueueNode.cs" />
152 <Compile Include="Parallels\MTCustomQueueNode.cs" />
153 <Compile Include="Parallels\MTLinkedList.cs" />
154 <Compile Include="Parallels\MTLinkedListNode.cs" />
153 </ItemGroup>
155 </ItemGroup>
154 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
156 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
155 <ItemGroup />
157 <ItemGroup />
General Comments 0
You need to be logged in to leave comments. Login now