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