1 //
2 // CSnzi.cs
3 //
4 // Author:
5 //       Jérémie "Garuma" Laval <jeremie.laval@gmail.com>
6 //
7 // Copyright (c) 2009 Jérémie "Garuma" Laval
8 //
9 // Permission is hereby granted, free of charge, to any person obtaining a copy
10 // of this software and associated documentation files (the "Software"), to deal
11 // in the Software without restriction, including without limitation the rights
12 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
13 // copies of the Software, and to permit persons to whom the Software is
14 // furnished to do so, subject to the following conditions:
15 //
16 // The above copyright notice and this permission notice shall be included in
17 // all copies or substantial portions of the Software.
18 //
19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
20 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
21 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
22 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
23 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
24 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
25 // THE SOFTWARE.
26 
27 using System;
28 using System.Threading;
29 
30 namespace Mono.Threading
31 {
32 	public abstract class CSnziNode
33 	{
Arrive()34 		internal abstract bool Arrive ();
Depart()35 		internal abstract bool Depart ();
36 	}
37 
38 	public enum CSnziState
39 	{
40 		Open,
41 		Closed
42 	}
43 
44 	internal class CSnziLeafNode : CSnziNode
45 	{
46 		int count;
47 		readonly CSnziNode parent;
48 
CSnziLeafNode(CSnziNode parent)49 		public CSnziLeafNode (CSnziNode parent)
50 		{
51 			this.parent = parent;
52 		}
53 
54 		#region CSnziNode implementation
Arrive()55 		internal override bool Arrive ()
56 		{
57 			bool arrivedAtParent = false;
58 			int x;
59 
60 			do {
61 				x = count;
62 				if (x == 0 && !arrivedAtParent) {
63 					if (parent.Arrive ())
64 						arrivedAtParent = true;
65 					else
66 						return false;
67 				}
68 			} while (Interlocked.CompareExchange (ref count, x + 1, x) != x);
69 
70 			if (arrivedAtParent && x != 0)
71 				parent.Depart ();
72 
73 			return true;
74 		}
75 
Depart()76 		internal override bool Depart ()
77 		{
78 			int x = Interlocked.Decrement (ref count);
79 			if (x == 1)
80 				return parent.Depart ();
81 			else
82 				return true;
83 		}
84 		#endregion
85 
86 	}
87 
88 	internal class CSnziRootNode : CSnziNode
89 	{
90 		int root;
91 
92 		public int Count {
93 			get {
94 				return root & 0x7FFFFFFF;
95 			}
96 		}
97 
98 		public CSnziState State {
99 			get {
100 				return (root >> 31) > 0 ? CSnziState.Open : CSnziState.Closed;
101 			}
102 		}
103 
CSnziRootNode()104 		public CSnziRootNode () : this (0, CSnziState.Open)
105 		{
106 
107 		}
108 
CSnziRootNode(int count, CSnziState state)109 		public CSnziRootNode (int count, CSnziState state)
110 		{
111 			root = Encode (count, state);
112 		}
113 
114 		#region CSnziNode implementation
Arrive()115 		internal override bool Arrive ()
116 		{
117 			int old;
118 			int c;
119 			CSnziState s;
120 
121 			do {
122 				old = root;
123 
124 				Decode (old, out c, out s);
125 
126 				if (c == 0 && s == CSnziState.Closed)
127 					return false;
128 			} while (Interlocked.CompareExchange (ref root, Encode (c + 1, s), old) != old);
129 
130 			return true;
131 		}
132 
Depart()133 		internal override bool Depart ()
134 		{
135 			int old;
136 			int c;
137 			CSnziState s;
138 
139 			do {
140 				old = root;
141 				Decode (old, out c, out s);
142 			} while (Interlocked.CompareExchange (ref root, Encode (c - 1, s), old) != old);
143 
144 			return c != 0 && s != CSnziState.Closed;
145 		}
146 		#endregion
147 
Open()148 		public void Open ()
149 		{
150 			root = Encode (0, CSnziState.Open);
151 		}
152 
Close()153 		public bool Close ()
154 		{
155 			int old, newRoot;
156 			int c;
157 			CSnziState s;
158 
159 			do {
160 				old = root;
161 
162 				Decode (old, out c, out s);
163 				if (s != CSnziState.Open)
164 					return false;
165 
166 				newRoot = Encode (c, CSnziState.Closed);
167 			} while (Interlocked.CompareExchange (ref root, newRoot, old) != old);
168 
169 			return c == 0;
170 		}
171 
Encode(int count, CSnziState state)172 		int Encode (int count, CSnziState state)
173 		{
174 			return (state == CSnziState.Open) ? (int)(((uint)count) | 0x80000000) : count & 0x7FFFFFFF;
175 		}
176 
Decode(int code, out int count, out CSnziState state)177 		void Decode (int code, out int count, out CSnziState state)
178 		{
179 			count = code & 0x7FFFFFFF;
180 			state = (code >> 31) > 0 ? CSnziState.Open : CSnziState.Closed;
181 		}
182 	}
183 
184 	public class CSnzi
185 	{
186 		CSnziRootNode root;
187 		CSnziLeafNode[] leafs;
188 
189 		readonly int LeafCount = Environment.ProcessorCount * 2;
190 
CSnzi()191 		public CSnzi ()
192 		{
193 			leafs = new CSnziLeafNode[LeafCount];
194 			root = new CSnziRootNode ();
195 
196 			for (int i = 0; i < leafs.Length; i++) {
197 				leafs[i] = new CSnziLeafNode (root);
198 			}
199 		}
200 
Arrive()201 		public CSnziNode Arrive ()
202 		{
203 			while (true) {
204 				if (root.State != CSnziState.Open)
205 					return null;
206 
207 				CSnziNode leaf = leafs[GetLeafIndex ()];
208 				if (leaf.Arrive ())
209 					return leaf;
210 				else {
211 					return null;
212 				}
213 			}
214 		}
215 
Depart(CSnziNode node)216 		public bool Depart (CSnziNode node)
217 		{
218 			return node.Depart ();
219 		}
220 
Close()221 		public bool Close ()
222 		{
223 			return root.Close ();
224 		}
225 
Open()226 		public void Open ()
227 		{
228 			root.Open ();
229 		}
230 
Query()231 		public Tuple<bool, CSnziState> Query ()
232 		{
233 			CSnziRootNode copy = root;
234 
235 			return Tuple.Create (copy.Count > 0, copy.State);
236 		}
237 
GetLeafIndex()238 		int GetLeafIndex ()
239 		{
240 			return (Thread.CurrentThread.ManagedThreadId - 1) % leafs.Length;
241 		}
242 	}
243 }
244