mcs/class/Mono.Parallel/Mono.Collections.Concurrent/ConcurrentSkipList.cs

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