##// 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
@@ -1,225 +1,227
1 1 ο»Ώ<?xml version="1.0" encoding="utf-8"?>
2 2 <Project DefaultTargets="Build" ToolsVersion="4.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
3 3 <PropertyGroup>
4 4 <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
5 5 <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
6 6 <ProjectGuid>{F550F1F8-8746-4AD0-9614-855F4C4B7F05}</ProjectGuid>
7 7 <OutputType>Library</OutputType>
8 8 <RootNamespace>Implab</RootNamespace>
9 9 <AssemblyName>Implab</AssemblyName>
10 10 </PropertyGroup>
11 11 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug|AnyCPU' ">
12 12 <DebugSymbols>true</DebugSymbols>
13 13 <DebugType>full</DebugType>
14 14 <Optimize>false</Optimize>
15 15 <OutputPath>bin\Debug</OutputPath>
16 16 <DefineConstants>TRACE;DEBUG;</DefineConstants>
17 17 <ErrorReport>prompt</ErrorReport>
18 18 <WarningLevel>4</WarningLevel>
19 19 <ConsolePause>false</ConsolePause>
20 20 <RunCodeAnalysis>true</RunCodeAnalysis>
21 21 </PropertyGroup>
22 22 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
23 23 <DebugType>full</DebugType>
24 24 <Optimize>true</Optimize>
25 25 <OutputPath>bin\Release</OutputPath>
26 26 <ErrorReport>prompt</ErrorReport>
27 27 <WarningLevel>4</WarningLevel>
28 28 <ConsolePause>false</ConsolePause>
29 29 </PropertyGroup>
30 30 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Debug 4.5|AnyCPU' ">
31 31 <DebugSymbols>true</DebugSymbols>
32 32 <DebugType>full</DebugType>
33 33 <Optimize>false</Optimize>
34 34 <OutputPath>bin\Debug</OutputPath>
35 35 <DefineConstants>TRACE;DEBUG;NET_4_5</DefineConstants>
36 36 <ErrorReport>prompt</ErrorReport>
37 37 <WarningLevel>4</WarningLevel>
38 38 <RunCodeAnalysis>true</RunCodeAnalysis>
39 39 <ConsolePause>false</ConsolePause>
40 40 </PropertyGroup>
41 41 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release 4.5|AnyCPU' ">
42 42 <Optimize>true</Optimize>
43 43 <OutputPath>bin\Release</OutputPath>
44 44 <ErrorReport>prompt</ErrorReport>
45 45 <WarningLevel>4</WarningLevel>
46 46 <ConsolePause>false</ConsolePause>
47 47 <DefineConstants>NET_4_5</DefineConstants>
48 48 </PropertyGroup>
49 49 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'DebugMono|AnyCPU' ">
50 50 <DebugSymbols>true</DebugSymbols>
51 51 <DebugType>full</DebugType>
52 52 <Optimize>false</Optimize>
53 53 <OutputPath>bin\Debug</OutputPath>
54 54 <DefineConstants>TRACE;DEBUG;NET_4_5;MONO</DefineConstants>
55 55 <ErrorReport>prompt</ErrorReport>
56 56 <WarningLevel>4</WarningLevel>
57 57 <RunCodeAnalysis>true</RunCodeAnalysis>
58 58 <ConsolePause>false</ConsolePause>
59 59 </PropertyGroup>
60 60 <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'ReleaseMono|AnyCPU' ">
61 61 <Optimize>true</Optimize>
62 62 <OutputPath>bin\Release</OutputPath>
63 63 <DefineConstants>NET_4_5;MONO;</DefineConstants>
64 64 <ErrorReport>prompt</ErrorReport>
65 65 <WarningLevel>4</WarningLevel>
66 66 <ConsolePause>false</ConsolePause>
67 67 </PropertyGroup>
68 68 <ItemGroup>
69 69 <Reference Include="System" />
70 70 <Reference Include="System.Xml" />
71 71 </ItemGroup>
72 72 <ItemGroup>
73 73 <Compile Include="Component.cs" />
74 74 <Compile Include="CustomEqualityComparer.cs" />
75 75 <Compile Include="Diagnostics\ConsoleTraceListener.cs" />
76 76 <Compile Include="Diagnostics\EventText.cs" />
77 77 <Compile Include="Diagnostics\IEventTextFormatter.cs" />
78 78 <Compile Include="Diagnostics\LogChannel.cs" />
79 79 <Compile Include="Diagnostics\LogicalOperation.cs" />
80 80 <Compile Include="Diagnostics\TextFileListener.cs" />
81 81 <Compile Include="Diagnostics\TextListenerBase.cs" />
82 82 <Compile Include="Diagnostics\TraceLog.cs" />
83 83 <Compile Include="Diagnostics\TraceEvent.cs" />
84 84 <Compile Include="Diagnostics\TraceEventType.cs" />
85 85 <Compile Include="Disposable.cs" />
86 86 <Compile Include="ICancellable.cs" />
87 87 <Compile Include="IProgressHandler.cs" />
88 88 <Compile Include="IProgressNotifier.cs" />
89 89 <Compile Include="IPromiseT.cs" />
90 90 <Compile Include="IPromise.cs" />
91 91 <Compile Include="IServiceLocator.cs" />
92 92 <Compile Include="ITaskController.cs" />
93 93 <Compile Include="JSON\JSONElementContext.cs" />
94 94 <Compile Include="JSON\JSONElementType.cs" />
95 95 <Compile Include="JSON\JSONGrammar.cs" />
96 96 <Compile Include="JSON\JSONParser.cs" />
97 97 <Compile Include="JSON\JSONScanner.cs" />
98 98 <Compile Include="JSON\JsonTokenType.cs" />
99 99 <Compile Include="JSON\JSONWriter.cs" />
100 100 <Compile Include="JSON\JSONXmlReader.cs" />
101 101 <Compile Include="JSON\JSONXmlReaderOptions.cs" />
102 102 <Compile Include="JSON\StringTranslator.cs" />
103 103 <Compile Include="Parallels\DispatchPool.cs" />
104 104 <Compile Include="Parallels\ArrayTraits.cs" />
105 105 <Compile Include="Parallels\MTQueue.cs" />
106 106 <Compile Include="Parallels\WorkerPool.cs" />
107 107 <Compile Include="Parsing\Alphabet.cs" />
108 108 <Compile Include="Parsing\AlphabetBase.cs" />
109 109 <Compile Include="Parsing\AltToken.cs" />
110 110 <Compile Include="Parsing\BinaryToken.cs" />
111 111 <Compile Include="Parsing\CatToken.cs" />
112 112 <Compile Include="Parsing\CDFADefinition.cs" />
113 113 <Compile Include="Parsing\DFABuilder.cs" />
114 114 <Compile Include="Parsing\DFADefinitionBase.cs" />
115 115 <Compile Include="Parsing\DFAStateDescriptor.cs" />
116 116 <Compile Include="Parsing\DFAutomaton.cs" />
117 117 <Compile Include="Parsing\EDFADefinition.cs" />
118 118 <Compile Include="Parsing\EmptyToken.cs" />
119 119 <Compile Include="Parsing\EndToken.cs" />
120 120 <Compile Include="Parsing\EnumAlphabet.cs" />
121 121 <Compile Include="Parsing\Grammar.cs" />
122 122 <Compile Include="Parsing\IAlphabet.cs" />
123 123 <Compile Include="Parsing\IDFADefinition.cs" />
124 124 <Compile Include="Parsing\IVisitor.cs" />
125 125 <Compile Include="Parsing\ParserException.cs" />
126 126 <Compile Include="Parsing\Scanner.cs" />
127 127 <Compile Include="Parsing\StarToken.cs" />
128 128 <Compile Include="Parsing\SymbolToken.cs" />
129 129 <Compile Include="Parsing\Token.cs" />
130 130 <Compile Include="SafePool.cs" />
131 131 <Compile Include="ServiceLocator.cs" />
132 132 <Compile Include="TaskController.cs" />
133 133 <Compile Include="ProgressInitEventArgs.cs" />
134 134 <Compile Include="Properties\AssemblyInfo.cs" />
135 135 <Compile Include="Promise.cs" />
136 136 <Compile Include="Parallels\AsyncPool.cs" />
137 137 <Compile Include="Safe.cs" />
138 138 <Compile Include="ValueEventArgs.cs" />
139 139 <Compile Include="PromiseExtensions.cs" />
140 140 <Compile Include="TransientPromiseException.cs" />
141 141 <Compile Include="SyncContextPromise.cs" />
142 142 <Compile Include="ObjectPool.cs" />
143 143 <Compile Include="Diagnostics\OperationContext.cs" />
144 144 <Compile Include="Diagnostics\TraceContext.cs" />
145 145 <Compile Include="Diagnostics\LogEventArgs.cs" />
146 146 <Compile Include="Diagnostics\LogEventArgsT.cs" />
147 147 <Compile Include="Diagnostics\Extensions.cs" />
148 148 <Compile Include="IComponentContainer.cs" />
149 149 <Compile Include="MTComponentContainer.cs" />
150 150 <Compile Include="PromiseEventType.cs" />
151 151 <Compile Include="Parallels\MTCustomQueue.cs" />
152 152 <Compile Include="Parallels\MTCustomQueueNode.cs" />
153 <Compile Include="Parallels\MTLinkedList.cs" />
154 <Compile Include="Parallels\MTLinkedListNode.cs" />
153 155 </ItemGroup>
154 156 <Import Project="$(MSBuildBinPath)\Microsoft.CSharp.targets" />
155 157 <ItemGroup />
156 158 <ProjectExtensions>
157 159 <MonoDevelop>
158 160 <Properties>
159 161 <Policies>
160 162 <CSharpFormattingPolicy IndentSwitchBody="True" NamespaceBraceStyle="EndOfLine" ClassBraceStyle="EndOfLine" InterfaceBraceStyle="EndOfLine" StructBraceStyle="EndOfLine" EnumBraceStyle="EndOfLine" MethodBraceStyle="EndOfLine" ConstructorBraceStyle="EndOfLine" DestructorBraceStyle="EndOfLine" BeforeMethodDeclarationParentheses="False" BeforeMethodCallParentheses="False" BeforeConstructorDeclarationParentheses="False" NewLineBeforeConstructorInitializerColon="NewLine" NewLineAfterConstructorInitializerColon="SameLine" BeforeIndexerDeclarationBracket="False" BeforeDelegateDeclarationParentheses="False" NewParentheses="False" SpacesBeforeBrackets="False" inheritsSet="Mono" inheritsScope="text/x-csharp" scope="text/x-csharp" />
161 163 <TextStylePolicy FileWidth="120" EolMarker="Unix" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/x-csharp" />
162 164 <DotNetNamingPolicy DirectoryNamespaceAssociation="PrefixedHierarchical" ResourceNamePolicy="MSBuild" />
163 165 <TextStylePolicy FileWidth="120" TabsToSpaces="False" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="application/xml" />
164 166 <XmlFormattingPolicy inheritsSet="Mono" inheritsScope="application/xml" scope="application/xml" />
165 167 <TextStylePolicy FileWidth="120" TabsToSpaces="False" inheritsSet="VisualStudio" inheritsScope="text/plain" scope="text/plain" />
166 168 <NameConventionPolicy>
167 169 <Rules>
168 170 <NamingRule Name="Namespaces" AffectedEntity="Namespace" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
169 171 <NamingRule Name="Types" AffectedEntity="Class, Struct, Enum, Delegate" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
170 172 <NamingRule Name="Interfaces" AffectedEntity="Interface" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
171 173 <RequiredPrefixes>
172 174 <String>I</String>
173 175 </RequiredPrefixes>
174 176 </NamingRule>
175 177 <NamingRule Name="Attributes" AffectedEntity="CustomAttributes" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
176 178 <RequiredSuffixes>
177 179 <String>Attribute</String>
178 180 </RequiredSuffixes>
179 181 </NamingRule>
180 182 <NamingRule Name="Event Arguments" AffectedEntity="CustomEventArgs" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
181 183 <RequiredSuffixes>
182 184 <String>EventArgs</String>
183 185 </RequiredSuffixes>
184 186 </NamingRule>
185 187 <NamingRule Name="Exceptions" AffectedEntity="CustomExceptions" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
186 188 <RequiredSuffixes>
187 189 <String>Exception</String>
188 190 </RequiredSuffixes>
189 191 </NamingRule>
190 192 <NamingRule Name="Methods" AffectedEntity="Methods" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
191 193 <NamingRule Name="Static Readonly Fields" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Protected, Public" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True" />
192 194 <NamingRule Name="Fields (Non Private)" AffectedEntity="Field" VisibilityMask="Internal, Public" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
193 195 <NamingRule Name="ReadOnly Fields (Non Private)" AffectedEntity="ReadonlyField" VisibilityMask="Internal, Public" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False" />
194 196 <NamingRule Name="Fields (Private)" AffectedEntity="Field, ReadonlyField" VisibilityMask="Private, Protected" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
195 197 <RequiredPrefixes>
196 198 <String>m_</String>
197 199 </RequiredPrefixes>
198 200 </NamingRule>
199 201 <NamingRule Name="Static Fields (Private)" AffectedEntity="Field" VisibilityMask="Private" NamingStyle="CamelCase" IncludeInstanceMembers="False" IncludeStaticEntities="True">
200 202 <RequiredPrefixes>
201 203 <String>_</String>
202 204 </RequiredPrefixes>
203 205 </NamingRule>
204 206 <NamingRule Name="ReadOnly Fields (Private)" AffectedEntity="ReadonlyField" VisibilityMask="Private, Protected" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="False">
205 207 <RequiredPrefixes>
206 208 <String>m_</String>
207 209 </RequiredPrefixes>
208 210 </NamingRule>
209 211 <NamingRule Name="Constant Fields" AffectedEntity="ConstantField" VisibilityMask="VisibilityMask" NamingStyle="AllUpper" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
210 212 <NamingRule Name="Properties" AffectedEntity="Property" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
211 213 <NamingRule Name="Events" AffectedEntity="Event" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
212 214 <NamingRule Name="Enum Members" AffectedEntity="EnumMember" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
213 215 <NamingRule Name="Parameters" AffectedEntity="Parameter, LocalVariable" VisibilityMask="VisibilityMask" NamingStyle="CamelCase" IncludeInstanceMembers="True" IncludeStaticEntities="True" />
214 216 <NamingRule Name="Type Parameters" AffectedEntity="TypeParameter" VisibilityMask="VisibilityMask" NamingStyle="PascalCase" IncludeInstanceMembers="True" IncludeStaticEntities="True">
215 217 <RequiredPrefixes>
216 218 <String>T</String>
217 219 </RequiredPrefixes>
218 220 </NamingRule>
219 221 </Rules>
220 222 </NameConventionPolicy>
221 223 </Policies>
222 224 </Properties>
223 225 </MonoDevelop>
224 226 </ProjectExtensions>
225 227 </Project> No newline at end of file
General Comments 0
You need to be logged in to leave comments. Login now