class/corlib/System.Threading/CSnzi.cs

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