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

   1 #if 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                 [ThreadStaticAttribute]
  43                 static Node[] preds;
  44                 [ThreadStaticAttribute]
  45                 static Node[] succs;
  46
  47                 int count = 0;
  48
  49                 class Node
  50                 {
  51                         public readonly int      Key;
  52                         public T                 Value;
  53                         public readonly int      TopLayer;
  54                         public readonly Node[]   Nexts;
  55                         public volatile bool     Marked;
  56                         public volatile bool     FullyLinked;
  57                         public readonly SpinLock SpinLock;
  58
  59                         public Node (int key, T value, int heightValue)
  60                         {
  61                                 Key = key;
  62                                 Value = value;
  63                                 TopLayer = heightValue;
  64                                 Nexts = new Node [heightValue + 1];
  65                                 SpinLock = new SpinLock (false);
  66                                 Marked = FullyLinked = false;
  67                         }
  68                 }
  69
  70                 Node leftSentinel;
  71                 Node rightSentinel;
  72
  73                 const int MaxHeight = 200;
  74                 uint randomSeed;
  75
  76                 Func<T, int> GetKey;
  77
  78                 public ConcurrentSkipList () : this ((value) => value.GetHashCode ())
  79                 {
  80                 }
  81
  82                 public ConcurrentSkipList (IEqualityComparer<T> comparer)
  83                         : this ((value) => comparer.GetHashCode (value))
  84                 {
  85                 }
  86
  87                 public ConcurrentSkipList(Func<T, int> hasher)
  88                 {
  89                         GetKey = hasher;
  90                         Init ();
  91                 }
  92
  93                 void Init ()
  94                 {
  95                         if (succs == null)
  96                                 succs = new Node [MaxHeight];
  97                         if (preds == null)
  98                                 preds = new Node [MaxHeight];
  99
 100                         leftSentinel = new Node (int.MinValue, default (T), MaxHeight);
 101                         rightSentinel = new Node (int.MaxValue, default (T), MaxHeight);
 102
 103                         for (int i = 0; i < MaxHeight; i++) {
 104                                 leftSentinel.Nexts [i] = rightSentinel;
 105                         }
 106                         // The or ensures that randomSeed != 0
 107                         randomSeed = ((uint)Math.Abs (Next())) | 0x0100;
 108                 }
 109
 110                 public bool TryAdd (T value)
 111                 {
 112                         if (value == null)
 113                                 throw new ArgumentNullException ("value");
 114
 115                         CleanArrays ();
 116                         int topLayer = GetRandomLevel ();
 117
 118                         int v = GetKey (value);
 119
 120                         while (true) {
 121                                 int found = FindNode (v, preds, succs);
 122                                 if (found != -1) {
 123                                         // A node with the same key already exists
 124                                         Node nodeFound = succs [found];
 125                                         if (!nodeFound.Marked) {
 126                                                 SpinWait sw = new SpinWait ();
 127                                                 while (!nodeFound.FullyLinked) {
 128                                                         sw.SpinOnce ();
 129                                                 }
 130                                                 return false;
 131                                         }
 132                                         continue;
 133                                 }
 134                                 int highestLocked = -1;
 135                                 try {
 136                                         bool valid = LockNodes (topLayer, ref highestLocked,
 137                                                                 (layer, pred, succ) => !pred.Marked && !succ.Marked && pred.Nexts [layer] == succ);
 138                                         if (!valid)
 139                                                 continue;
 140
 141                                         Node newNode = new Node (v, value, topLayer);
 142                                         for (int layer = 0; layer <= topLayer; layer++) {
 143                                                 newNode.Nexts [layer] = succs [layer];
 144                                                 preds [layer].Nexts [layer] = newNode;
 145                                         }
 146                                         newNode.FullyLinked = true;
 147                                 } finally {
 148                                         Unlock (preds, highestLocked);
 149                                 }
 150                                 Interlocked.Increment (ref count);
 151                                 return true;
 152                         }
 153                 }
 154
 155                 bool IProducerConsumerCollection<T>.TryTake (out T value)
 156                 {
 157                         throw new NotSupportedException ();
 158                 }
 159
 160                 public T[] ToArray ()
 161                 {
 162                         int countSnapshot = count;
 163                         T[] temp = new T [countSnapshot];
 164
 165                         CopyTo(temp, 0);
 166
 167                         return temp;
 168                 }
 169
 170                 public void CopyTo (T[] array, int startIndex)
 171                 {
 172                         IEnumerator<T> e = GetInternalEnumerator ();
 173                         for (int i = startIndex; i < array.Length; i++) {
 174                                 if (!e.MoveNext ())
 175                                         return;
 176                                 array [i] = e.Current;
 177                         }
 178                         e.Dispose ();
 179                 }
 180
 181                 void ICollection.CopyTo (Array array, int startIndex)
 182                 {
 183                         T[] temp = array as T[];
 184                         if (temp == null)
 185                                 return;
 186
 187                         CopyTo (temp, startIndex);
 188                 }
 189
 190                 object ICollection.SyncRoot {
 191                         get {
 192                                 return this;
 193                         }
 194                 }
 195
 196                 bool ICollection.IsSynchronized {
 197                         get {
 198                                 return true;
 199                         }
 200                 }
 201
 202                 public bool Remove (T value)
 203                 {
 204                         if (value == null)
 205                                 throw new ArgumentNullException ("value");
 206
 207                         CleanArrays();
 208                         Node toDelete = null;
 209                         bool isMarked = false;
 210                         int topLayer = -1;
 211                         int v = GetKey (value);
 212
 213                         while (true) {
 214                                 int found = FindNode (v, preds, succs);
 215
 216                                 if (isMarked || (found != -1 && OkToDelete (succs [found], found))) {
 217                                         // If not marked then logically delete the node
 218                                         if (!isMarked) {
 219                                                 toDelete = succs [found];
 220                                                 topLayer = toDelete.TopLayer;
 221                                                 bool taken = false;
 222                                                 do {
 223                                                         toDelete.SpinLock.Enter (ref taken);
 224                                                 } while (!taken);
 225                                                 // Now that we have the lock, check if the node hasn't already been marked
 226                                                 if (toDelete.Marked) {
 227                                                         toDelete.SpinLock.Exit (true);
 228                                                         return false;
 229                                                 }
 230                                                 toDelete.Marked = true;
 231                                                 isMarked = true;
 232                                         }
 233                                         int highestLocked = -1;
 234                                         try {
 235                                                 bool valid = LockNodes (topLayer, ref highestLocked,
 236                                                                         (layer, pred, succ) => !pred.Marked && pred.Nexts [layer] == succ);
 237                                                 if (!valid)
 238                                                         continue;
 239
 240                                                 for (int layer = topLayer; layer >= 0; layer--) {
 241                                                         preds [layer].Nexts [layer] = toDelete.Nexts [layer];
 242                                                 }
 243                                                 toDelete.SpinLock.Exit (true);
 244                                         } finally {
 245                                                 Unlock (preds, highestLocked);
 246                                         }
 247                                         Interlocked.Decrement (ref count);
 248                                         return true;
 249                                 } else {
 250                                         return false;
 251                                 }
 252                         }
 253                 }
 254
 255                 public bool Contains (T value)
 256                 {
 257                         if (value == null)
 258                                 throw new ArgumentNullException ("value");
 259
 260                         return ContainsFromHash (GetKey (value));
 261                 }
 262
 263                 internal bool ContainsFromHash (int hash)
 264                 {
 265                         CleanArrays ();
 266                         int found = FindNode (hash, preds, succs);
 267                         return found != -1 && succs [found].FullyLinked && !succs [found].Marked;
 268                 }
 269
 270                 internal bool GetFromHash (int hash, out T value)
 271                 {
 272                         value = default (T);
 273                         CleanArrays ();
 274                         // We are blindly supposing that the hash is correct
 275                         // i.e. I trust myself :-)
 276                         int found = FindNode (hash, preds, succs);
 277                         if (found == -1)
 278                                 return false;
 279
 280                         try {
 281                                 bool taken = false;
 282                                 do {
 283                                         succs [found].SpinLock.Enter (ref taken);
 284                                 } while (!taken);
 285                                 Node node = succs [found];
 286                                 if (node.FullyLinked && !node.Marked) {
 287                                         value = node.Value;
 288                                         return true;
 289                                 }
 290                         } finally {
 291                                 succs [found].SpinLock.Exit (true);
 292                         }
 293
 294                         return false;
 295                 }
 296
 297                 public int Count {
 298                         get {
 299                                 return count;
 300                         }
 301                 }
 302
 303                 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
 304                 {
 305                         return GetInternalEnumerator ();
 306                 }
 307
 308                 IEnumerator IEnumerable.GetEnumerator ()
 309                 {
 310                         return GetInternalEnumerator ();
 311                 }
 312
 313                 IEnumerator<T> GetInternalEnumerator ()
 314                 {
 315                         Node curr = leftSentinel;
 316                         while ((curr = curr.Nexts [0]) != rightSentinel) {
 317                                 // If there is an Add operation ongoing we wait a little
 318                                 // Possible optimization : use a helping scheme
 319                                 SpinWait sw = new SpinWait ();
 320                                 while (!curr.FullyLinked) {
 321                                         sw.SpinOnce ();
 322                                 }
 323                                 yield return curr.Value;
 324                         }
 325                 }
 326
 327                 void Unlock(Node[] preds, int highestLocked)
 328                 {
 329                         for (int i = 0; i <= highestLocked; i++) {
 330                                 preds [i].SpinLock.Exit (true);
 331                         }
 332                 }
 333
 334                 bool LockNodes (int topLayer, ref int highestLocked, Func<int, Node, Node, bool> validityTest)
 335                 {
 336                         Node pred, succ, prevPred = null;
 337                         bool valid = true;
 338
 339                         for (int layer = 0; valid && (layer <= topLayer); layer++) {
 340                                 pred = preds [layer];
 341                                 succ = succs [layer];
 342                                 if (pred != prevPred) {
 343                                         // Possible optimization : limit topLayer to the first refused lock
 344                                         bool taken = false;
 345                                         do {
 346                                                 pred.SpinLock.Enter (ref taken);
 347                                         } while (!taken);
 348                                         highestLocked = layer;
 349                                         prevPred = pred;
 350                                 }
 351                                 valid = validityTest (layer, pred, succ);
 352                         }
 353
 354                         return valid;
 355                 }
 356
 357                 int FindNode (int v, Node[] preds, Node[] succs)
 358                 {
 359                         // With preds and succs we record the path we use for searching v
 360                         if (preds.Length != MaxHeight || succs.Length != MaxHeight)
 361                                 throw new Exception ("precs or succs don't have the  good length");
 362
 363                         int found = -1;
 364                         Node pred = leftSentinel;
 365
 366                         // We start at the higher layer
 367                         for (int layer = MaxHeight - 1; layer >= 0; layer--) {
 368                                 Node curr = pred.Nexts [layer];
 369                                 // In the current layer we find the best position, then the operation will continue on the
 370                                 // layer just beneath
 371                                 while (v > curr.Key) {
 372                                         pred = curr;
 373                                         curr = curr.Nexts [layer];
 374                                 }
 375                                 if (found == -1 && v == curr.Key)
 376                                         found = layer;
 377                                 preds [layer] = pred;
 378                                 succs [layer] = curr;
 379                         }
 380
 381                         return found;
 382                 }
 383
 384                 bool OkToDelete (Node candidate, int found)
 385                 {
 386                         return candidate.FullyLinked && candidate.TopLayer == found && !candidate.Marked;
 387                 }
 388
 389                 // Taken from Doug Lea's code released in the public domain
 390                 int GetRandomLevel ()
 391                 {
 392                         uint x = randomSeed;
 393                         x ^= x << 13;
 394                         x ^= x >> 17;
 395                         x ^= x << 5;
 396                         randomSeed = x;
 397                         if ((x & 0x80000001) != 0) // test highest and lowest bits
 398                                 return 0;
 399                         int level = 1;
 400                         while (((x >>= 1) & 1) != 0) ++level;
 401                         return level;
 402                 }
 403
 404                 void CleanArrays ()
 405                 {
 406                         if (succs == null)
 407                                 succs = new Node [MaxHeight];
 408                         if (preds == null)
 409                                 preds = new Node [MaxHeight];
 410
 411                         // Hopefully these are more optimized than a bare for loop
 412                         // (I suppose it uses memset internally)
 413                         Array.Clear (preds, 0, preds.Length);
 414                         Array.Clear (succs, 0, succs.Length);
 415                 }
 416
 417                 int Next ()
 418                 {
 419                   if (r == null)
 420                         r = new Random ();
 421
 422                   return r.Next ();
 423                 }
 424         }
 425 }
 426 #endif