mcs/class/corlib/System.Threading/Snzi.cs

   1 #if NET_4_0
   2 //
   3 // Snzi.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 using System.IO;
  30
  31 namespace System.Threading
  32 {
  33         internal interface ISnziNode
  34         {
  35                 bool Query { get; }
  36                 void Arrive ();
  37                 void Depart ();
  38                 bool Reset ();
  39         }
  40
  41         internal class Snzi
  42         {
  43                 readonly ISnziNode root;
  44                 readonly ISnziNode[] nodes;
  45
  46                 readonly int count = Environment.ProcessorCount;
  47
  48                 public Snzi ()
  49                 {
  50                         nodes = new ISnziNode[count];
  51                         root = new RootNode ();
  52                         for (int i = 0; i < count; i++)
  53                                 nodes[i] = new LeafNode (root);
  54                 }
  55
  56                 public void Increment ()
  57                 {
  58                         ISnziNode node = nodes[GetRandomIndex ()];
  59                         node.Arrive ();
  60                 }
  61
  62                 public void Decrement ()
  63                 {
  64                         ISnziNode node = nodes[GetRandomIndex ()];
  65                         node.Depart ();
  66                 }
  67
  68                 public void Reset ()
  69                 {
  70                         ISnziNode node = nodes[GetRandomIndex ()];
  71                         node.Reset ();
  72                 }
  73
  74                 public bool IsSet {
  75                         get {
  76                                 return !root.Query;
  77                         }
  78                 }
  79
  80                 int GetRandomIndex ()
  81                 {
  82                         return (Thread.CurrentThread.ManagedThreadId) % count;
  83                 }
  84
  85                 class UnsafeLeafNode : ISnziNode
  86                 {
  87                         ISnziNode parent;
  88                         int var;
  89
  90                         public UnsafeLeafNode (ISnziNode parent)
  91                         {
  92                                 this.parent = parent;
  93                         }
  94
  95                         #region ISnziNode implementation
  96                         public void Arrive ()
  97                         {
  98                                 int c = var++;
  99
 100                                 if (c == 0)
 101                                         parent.Arrive ();
 102                         }
 103
 104                         public void Depart ()
 105                         {
 106                                 int c = var--;
 107                                 if (c == 1)
 108                                         parent.Depart ();
 109                         }
 110
 111                         public bool Reset ()
 112                         {
 113                                 throw new System.NotImplementedException();
 114                         }
 115
 116                         public bool Query {
 117                                 get {
 118                                         return parent.Query;
 119                                 }
 120                         }
 121                         #endregion
 122
 123                 }
 124
 125                 class LeafNode : ISnziNode
 126                 {
 127                         ISnziNode parent;
 128                         int var;
 129
 130                         public LeafNode (ISnziNode parent)
 131                         {
 132                                 this.parent = parent;
 133                                 this.var = 0;
 134                         }
 135
 136                         #region ISnziNode implementation
 137                         public void Arrive ()
 138                         {
 139                                 bool succ = false;
 140                                 int undoArr = 0;
 141                                 while (!succ) {
 142                                         int x = var;
 143                                         short c, v;
 144                                         Decode (x, out c, out v);
 145
 146                                         if (c >= 1)
 147                                                 if (Interlocked.CompareExchange (ref var, Encode ((short)(c + 1), v), x) == x)
 148                                                         break;
 149
 150                                         if (c == 0) {
 151                                                 int temp = Encode (-1, (short)(v + 1));
 152                                                 if (Interlocked.CompareExchange (ref var, temp, x) == x) {
 153                                                         succ = true;
 154                                                         c = -1;
 155                                                         v += 1;
 156                                                         x = temp;
 157                                                 }
 158                                         }
 159
 160                                         if (c == - 1) {
 161                                                 parent.Arrive ();
 162                                                 if (Interlocked.CompareExchange (ref var, Encode (1, v), x) != x)
 163                                                         undoArr += 1;
 164                                         }
 165                                 }
 166                                 for (int i = 0; i < undoArr; i++)
 167                                         parent.Depart ();
 168                         }
 169
 170                         public void Depart ()
 171                         {
 172                                 while (true) {
 173                                         int x = var;
 174                                         short c, v;
 175                                         Decode (x, out c, out v);
 176
 177                                         if (Interlocked.CompareExchange (ref var, Encode ((short)(c - 1), v), x) == x) {
 178                                                 if (c == 1)
 179                                                         parent.Depart ();
 180                                                 return;
 181                                         }
 182                                 }
 183                         }
 184
 185                         public bool Reset ()
 186                         {
 187                                 throw new System.NotImplementedException();
 188                         }
 189
 190                         public bool Query {
 191                                 get {
 192                                         return parent.Query;
 193                                 }
 194                         }
 195                         #endregion
 196
 197                         int Encode (short c, short v)
 198                         {
 199                                 uint temp = 0;
 200                                 temp |= (uint)c;
 201                                 temp |= ((uint)v) << 16;
 202
 203                                 return (int)temp;
 204                         }
 205
 206                         void Decode (int value, out short c, out short v)
 207                         {
 208                                 uint temp = (uint)value;
 209                                 c = (short)(temp & 0xFFFF);
 210                                 v = (short)(temp >> 16);
 211                         }
 212                 }
 213
 214                 class RootNode : ISnziNode
 215                 {
 216                         int var = 0;
 217                         int state = 0;
 218
 219                         #region ISnziNode implementation
 220                         public void Arrive ()
 221                         {
 222                                 int temp, x = 0;
 223                                 short c, v;
 224                                 bool a;
 225
 226                                 do {
 227                                         x = var;
 228
 229                                         Decode (x, out c, out a, out v);
 230
 231                                         if (c == 0)
 232                                                 temp = Encode (1, true, (short)(v + 1));
 233                                         else
 234                                                 temp = Encode ((short)(c + 1), a, v);
 235                                 } while (Interlocked.CompareExchange (ref var, temp, x) != x);
 236
 237                                 Decode (temp, out c, out a, out v);
 238
 239                                 if (a) {
 240                                         while (true) {
 241                                                 int i = state;
 242                                                 int newI = (i & 0x7FFFFFFF) + 1;
 243                                                 newI = (int)(((uint)newI) | 0x80000000);
 244                                                 if (Interlocked.CompareExchange (ref state, newI, i) == i) {
 245                                                         break;
 246                                                 }
 247                                         }
 248                                         Interlocked.CompareExchange (ref var, Encode (c, false, v), temp);
 249                                 }
 250                         }
 251
 252                         public void Depart ()
 253                         {
 254                                 while (true) {
 255                                         int x = var;
 256                                         short c, v;
 257                                         bool a;
 258                                         Decode (x, out c, out a, out v);
 259
 260                                         if (Interlocked.CompareExchange (ref var, Encode ((short)(c - 1), false, v), x) == x) {
 261                                                 if (c >= 2)
 262                                                         return;
 263                                                 while (true) {
 264                                                         int i = state;
 265                                                         if (((short)(var >> 16)) != v)
 266                                                                 return;
 267                                                         int newI = (i & 0x7FFFFFFF) + 1;
 268                                                         if (Interlocked.CompareExchange (ref state, newI, i) == i) {
 269                                                                 return;
 270                                                         }
 271                                                 }
 272                                         }
 273                                 }
 274                         }
 275
 276                         public bool Reset ()
 277                         {
 278                                 throw new System.NotImplementedException();
 279                         }
 280
 281                         public bool Query {
 282                                 get {
 283                                         return (state & 0x80000000) > 0;
 284                                 }
 285                         }
 286                         #endregion
 287
 288                         int Encode (short c, bool a, short v)
 289                         {
 290                                 uint temp = 0;
 291                                 temp |= (uint)c;
 292                                 temp |= (uint)(a ? 0x8000 : 0);
 293                                 temp |= ((uint)v) << 16;
 294
 295                                 return (int)temp;
 296                         }
 297
 298                         void Decode (int value, out short c, out bool a, out short v)
 299                         {
 300                                 uint temp = (uint)value;
 301                                 c = (short)(temp & 0x7FFF);
 302                                 a = (temp & 0x8000) > 0;
 303                                 v = (short)(temp >> 16);
 304                         }
 305                 }
 306         }
 307 }
 308 #endif