mcs/class/corlib/System.Collections.Concurrent/ConcurrentSkipList.cs

   1 #if NET_4_0 || BOOTSTRAP_NET_4_0
   2 // ConcurrentSkipList.cs
   3 //
   4 // Copyright (c) 2008 Jérémie "Garuma" Laval
   5 //
   6 // Permission is hereby granted, free of charge, to any person obtaining a copy
   7 // of this software and associated documentation files (the "Software"), to deal
   8 // in the Software without restriction, including without limitation the rights
   9 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10 // copies of the Software, and to permit persons to whom the Software is
  11 // furnished to do so, subject to the following conditions:
  12 //
  13 // The above copyright notice and this permission notice shall be included in
  14 // all copies or substantial portions of the Software.
  15 //
  16 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22 // THE SOFTWARE.
  23 //
  24 //
  25
  26 using System;
  27 using System.Threading;
  28 using System.Collections;
  29 using System.Collections.Generic;
  30
  31 namespace System.Collections.Concurrent
  32 {
  33
  34         internal class ConcurrentSkipList<T> : IProducerConsumerCollection<T>
  35         {
  36                 // Used for randomSeed
  37                 [ThreadStatic]
  38                 static Random r;
  39                 // Used in FindNodes and thus most others methods
  40                 // avoid heavy local array creation at each method call and use
  41                 // for thread locallity ThreadStatic attribute
  42                 [ThreadStatic]
  43                 static Node[] precedents;
  44                 [ThreadStatic]
  45                 static Node[] succedings;
  46                 [ThreadStatic]
  47                 static bool[] takenLocks;
  48
  49                 int count = 0;
  50
  51                 class Node
  52                 {
  53                         public readonly int      Key;
  54                         public T                 Value;
  55                         public readonly int      TopLayer;
  56                         public readonly Node[]   Nexts;
  57                         public volatile bool     Marked;
  58                         public volatile bool     FullyLinked;
  59                         public SpinLock  Lock;
  60
  61                         public Node (int key, T value, int heightValue)
  62                         {
  63                                 Key = key;
  64                                 Value = value;
  65                                 TopLayer = heightValue;
  66                                 Nexts = new Node [heightValue + 1];
  67                                 Lock = new SpinLock (true);
  68                                 Marked = FullyLinked = false;
  69                         }
  70                 }
  71
  72                 Node leftSentinel;
  73                 Node rightSentinel;
  74
  75                 const int MaxHeight = 200;
  76                 uint randomSeed;
  77
  78                 Func<T, int> GetKey;
  79
  80                 public ConcurrentSkipList () : this ((value) => value.GetHashCode ())
  81                 {
  82                 }
  83
  84                 public ConcurrentSkipList (IEqualityComparer<T> comparer)
  85                         : this ((value) => comparer.GetHashCode (value))
  86                 {
  87                 }
  88
  89                 public ConcurrentSkipList(Func<T, int> hasher)
  90                 {
  91                         GetKey = hasher;
  92                         Init ();
  93                 }
  94
  95                 void Init ()
  96                 {
  97                         leftSentinel = new Node (int.MinValue, default (T), MaxHeight);
  98                         rightSentinel = new Node (int.MaxValue, default (T), MaxHeight);
  99
 100                         for (int i = 0; i < MaxHeight; i++) {
 101                                 leftSentinel.Nexts [i] = rightSentinel;
 102                         }
 103                         // The or ensures that randomSeed != 0
 104                         randomSeed = ((uint)Math.Abs (Next())) | 0x0100;
 105                 }
 106
 107                 public bool TryAdd (T value)
 108                 {
 109                         if (value == null)
 110                                 throw new ArgumentNullException ("value");
 111
 112                         CleanArrays ();
 113                         int topLayer = GetRandomLevel ();
 114
 115                         int v = GetKey (value);
 116
 117                         while (true) {
 118                                 int found = FindNode (v, precedents, succedings);
 119                                 if (found != -1) {
 120                                         // A node with the same key already exists
 121                                         Node nodeFound = succedings [found];
 122                                         if (!nodeFound.Marked) {
 123                                                 SpinWait sw = new SpinWait ();
 124                                                 while (!nodeFound.FullyLinked)
 125                                                         sw.SpinOnce ();
 126
 127                                                 return false;
 128                                         }
 129                                         continue;
 130                                 }
 131                                 int highestLocked = -1;
 132                                 try {
 133                                         bool valid = LockNodes (topLayer, ref highestLocked, precedents, succedings,
 134                                                                 (layer, pred, succ) => !pred.Marked && !succ.Marked && pred.Nexts [layer] == succ);
 135                                         if (!valid)
 136                                                 continue;
 137
 138                                         Node newNode = new Node (v, value, topLayer);
 139                                         for (int layer = 0; layer <= topLayer; layer++) {
 140                                                 newNode.Nexts [layer] = succedings [layer];
 141                                                 precedents [layer].Nexts [layer] = newNode;
 142                                         }
 143                                         newNode.FullyLinked = true;
 144                                 } finally {
 145                                         Unlock (precedents, takenLocks, highestLocked);
 146                                 }
 147                                 Interlocked.Increment (ref count);
 148                                 return true;
 149                         }
 150                 }
 151
 152                 bool IProducerConsumerCollection<T>.TryTake (out T value)
 153                 {
 154                         throw new NotSupportedException ();
 155                 }
 156
 157                 public T[] ToArray ()
 158                 {
 159                         int countSnapshot = count;
 160                         T[] temp = new T [countSnapshot];
 161
 162                         CopyTo(temp, 0);
 163
 164                         return temp;
 165                 }
 166
 167                 public void CopyTo (T[] array, int startIndex)
 168                 {
 169                         IEnumerator<T> e = GetInternalEnumerator ();
 170                         for (int i = startIndex; i < array.Length; i++) {
 171                                 if (!e.MoveNext ())
 172                                         return;
 173                                 array [i] = e.Current;
 174                         }
 175                         e.Dispose ();
 176                 }
 177
 178                 void ICollection.CopyTo (Array array, int startIndex)
 179                 {
 180                         T[] temp = array as T[];
 181                         if (temp == null)
 182                                 return;
 183
 184                         CopyTo (temp, startIndex);
 185                 }
 186
 187                 object ICollection.SyncRoot {
 188                         get {
 189                                 return this;
 190                         }
 191                 }
 192
 193                 bool ICollection.IsSynchronized {
 194                         get {
 195                                 return true;
 196                         }
 197                 }
 198
 199                 public bool Remove (T value)
 200                 {
 201                         if (value == null)
 202                                 throw new ArgumentNullException ("value");
 203
 204                         CleanArrays();
 205                         Node toDelete = null;
 206                         bool isMarked = false;
 207                         int topLayer = -1;
 208                         int v = GetKey (value);
 209
 210                         while (true) {
 211                                 int found = FindNode (v, precedents, succedings);
 212                                 bool taken = false;
 213                                 int highestLocked = -1;
 214
 215                                 if (isMarked || (found != -1 && OkToDelete (succedings [found], found))) {
 216                                         // If not marked then logically delete the node
 217                                         try {
 218                                                 if (!isMarked) {
 219                                                         toDelete = succedings [found];
 220                                                         topLayer = toDelete.TopLayer;
 221
 222                                                         toDelete.Lock.Enter (ref taken);
 223                                                         // Now that we have the lock, check if the node hasn't already been marked
 224                                                         if (toDelete.Marked)
 225                                                                 return false;
 226
 227                                                         toDelete.Marked = true;
 228                                                         isMarked = true;
 229                                                 }
 230
 231                                                 bool valid = LockNodes (topLayer, ref highestLocked, precedents, succedings,
 232                                                                         (layer, pred, succ) => !pred.Marked && pred.Nexts [layer] == succ);
 233                                                 if (!valid)
 234                                                         continue;
 235
 236                                                 for (int layer = topLayer; layer >= 0; layer--)
 237                                                         precedents [layer].Nexts [layer] = toDelete.Nexts [layer];
 238                                         } finally {
 239                                                 if (taken)
 240                                                         toDelete.Lock.Exit ();
 241                                                 Unlock (precedents, takenLocks, highestLocked);
 242                                         }
 243
 244                                         Interlocked.Decrement (ref count);
 245                                         return true;
 246                                 } else {
 247                                         return false;
 248                                 }
 249                         }
 250                 }
 251
 252                 public bool Contains (T value)
 253                 {
 254                         if (value == null)
 255                                 throw new ArgumentNullException ("value");
 256
 257                         return ContainsFromHash (GetKey (value));
 258                 }
 259
 260                 internal bool ContainsFromHash (int hash)
 261                 {
 262                         CleanArrays ();
 263                         int found = FindNode (hash, precedents, succedings);
 264                         return found != -1 && succedings [found].FullyLinked && !succedings [found].Marked;
 265                 }
 266
 267                 internal bool GetFromHash (int hash, out T value)
 268                 {
 269                         value = default (T);
 270                         CleanArrays ();
 271                         // We are blindly supposing that the hash is correct
 272                         // i.e. I trust myself :-)
 273                         int found = FindNode (hash, precedents, succedings);
 274                         if (found == -1)
 275                                 return false;
 276
 277                         bool taken = false;
 278                         Node node = succedings [found];
 279
 280                         try {
 281                                 node.Lock.Enter (ref taken);
 282
 283                                 if (node.FullyLinked && !node.Marked) {
 284                                         value = node.Value;
 285                                         return true;
 286                                 }
 287                         } finally {
 288                                 if (taken)
 289                                         node.Lock.Exit ();
 290                         }
 291
 292                         return false;
 293                 }
 294
 295                 public int Count {
 296                         get {
 297                                 return count;
 298                         }
 299                 }
 300
 301                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 302                 {
 303                         return GetInternalEnumerator ();
 304                 }
 305
 306                 IEnumerator IEnumerable.GetEnumerator ()
 307                 {
 308                         return GetInternalEnumerator ();
 309                 }
 310
 311                 IEnumerator<T> GetInternalEnumerator ()
 312                 {
 313                         Node curr = leftSentinel;
 314                         while ((curr = curr.Nexts [0]) != rightSentinel) {
 315                                 // If there is an Add operation ongoing we wait a little
 316                                 // Possible optimization : use a helping scheme
 317                                 SpinWait sw = new SpinWait ();
 318                                 while (!curr.FullyLinked)
 319                                         sw.SpinOnce ();
 320
 321                                 yield return curr.Value;
 322                         }
 323                 }
 324
 325                 void Unlock (Node[] preds, bool[] takenLocks, int highestLocked)
 326                 {
 327                         for (int layer = 0; layer <= highestLocked; layer++)
 328                                 if (takenLocks [layer])
 329                                         preds [layer].Lock.Exit ();
 330                 }
 331
 332                 bool LockNodes (int topLayer, ref int highestLocked, Node[] preds, Node[] succs, Func<int, Node, Node, bool> validityTest)
 333                 {
 334                         Node pred, succ, prevPred = null;
 335                         bool valid = true;
 336
 337                         for (int layer = 0; valid && (layer <= topLayer); layer++) {
 338                                 pred = preds [layer];
 339                                 succ = succs [layer];
 340                                 takenLocks[layer] = false;
 341
 342                                 if (pred != prevPred) {
 343                                         // Possible optimization : limit topLayer to the first refused lock
 344                                         pred.Lock.Enter (ref takenLocks[layer]);
 345                                         highestLocked = layer;
 346                                         prevPred = pred;
 347                                 }
 348
 349                                 valid = validityTest (layer, pred, succ);
 350                         }
 351
 352                         return valid;
 353                 }
 354
 355                 int FindNode (int v, Node[] preds, Node[] succs)
 356                 {
 357                         // With preds and succs we record the path we use for searching v
 358                         if (preds.Length != MaxHeight || succs.Length != MaxHeight)
 359                                 throw new Exception ("preds or succs don't have the  good length");
 360
 361                         int found = -1;
 362                         Node pred = leftSentinel;
 363
 364                         // We start at the higher layer
 365                         for (int layer = MaxHeight - 1; layer >= 0; layer--) {
 366                                 Node curr = pred.Nexts [layer];
 367                                 // In the current layer we find the best position, then the operation will continue on the
 368                                 // layer just beneath
 369                                 while (v > curr.Key) {
 370                                         pred = curr;
 371                                         curr = curr.Nexts [layer];
 372                                 }
 373                                 if (found == -1 && v == curr.Key)
 374                                         found = layer;
 375                                 preds [layer] = pred;
 376                                 succs [layer] = curr;
 377                         }
 378
 379                         return found;
 380                 }
 381
 382                 bool OkToDelete (Node candidate, int found)
 383                 {
 384                         return candidate.FullyLinked && candidate.TopLayer == found && !candidate.Marked;
 385                 }
 386
 387                 // Taken from Doug Lea's code released in the public domain
 388                 int GetRandomLevel ()
 389                 {
 390                         uint x = randomSeed;
 391                         x ^= x << 13;
 392                         x ^= x >> 17;
 393                         x ^= x << 5;
 394                         randomSeed = x;
 395                         if ((x & 0x80000001) != 0) // test highest and lowest bits
 396                                 return 0;
 397                         int level = 1;
 398                         while (((x >>= 1) & 1) != 0) ++level;
 399                         return level;
 400                 }
 401
 402                 void CleanArrays ()
 403                 {
 404                         // If one is null, the others too
 405                         if (succedings == null) {
 406                                 succedings = new Node [MaxHeight];
 407                                 precedents = new Node [MaxHeight];
 408                                 takenLocks = new bool [MaxHeight];
 409
 410                                 return;
 411                         }
 412
 413                         // Hopefully these are more optimized than a bare for loop
 414                         // (I suppose it uses memset internally)
 415                         Array.Clear (precedents, 0, precedents.Length);
 416                         Array.Clear (succedings, 0, succedings.Length);
 417                         Array.Clear (takenLocks, 0, takenLocks.Length);
 418                 }
 419
 420                 int Next ()
 421                 {
 422                   if (r == null)
 423                         r = new Random ();
 424
 425                   return r.Next ();
 426                 }
 427         }
 428 }
 429 #endif