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

   1 // SplitOrderedList.cs
   2 //
   3 // Copyright (c) 2010 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 || BOOTSTRAP_NET_4_0
  26
  27 using System;
  28 using System.Threading;
  29 using System.Collections;
  30 using System.Collections.Generic;
  31 using System.Runtime.Serialization;
  32
  33 namespace System.Collections.Concurrent
  34 {
  35         internal class SplitOrderedList<T>
  36         {
  37                 static readonly byte[] reverseTable = {
  38                         0, 128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240, 8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120, 248, 4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180, 116, 244, 12, 140, 76, 204, 44, 172, 108, 236, 28, 156, 92, 220, 60, 188, 124, 252, 2, 130, 66, 194, 34, 162, 98, 226, 18, 146, 82, 210, 50, 178, 114, 242, 10, 138, 74, 202, 42, 170, 106, 234, 26, 154, 90, 218, 58, 186, 122, 250, 6, 134, 70, 198, 38, 166, 102, 230, 22, 150, 86, 214, 54, 182, 118, 246, 14, 142, 78, 206, 46, 174, 110, 238, 30, 158, 94, 222, 62, 190, 126, 254, 1, 129, 65, 193, 33, 161, 97, 225, 17, 145, 81, 209, 49, 177, 113, 241, 9, 137, 73, 201, 41, 169, 105, 233, 25, 153, 89, 217, 57, 185, 121, 249, 5, 133, 69, 197, 37, 165, 101, 229, 21, 149, 85, 213, 53, 181, 117, 245, 13, 141, 77, 205, 45, 173, 109, 237, 29, 157, 93, 221, 61, 189, 125, 253, 3, 131, 67, 195, 35, 163, 99, 227, 19, 147, 83, 211, 51, 179, 115, 243, 11, 139, 75, 203, 43, 171, 107, 235, 27, 155, 91, 219, 59, 187, 123, 251, 7, 135, 71, 199, 39, 167, 103, 231, 23, 151, 87, 215, 55, 183, 119, 247, 15, 143, 79, 207, 47, 175, 111, 239, 31, 159, 95, 223, 63, 191, 127, 255
  39                 };
  40
  41                 static readonly byte[] logTable = {
  42                         0xFF, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
  43                 };
  44
  45                 class Node
  46                 {
  47                         public readonly bool Marked;
  48                         public readonly uint Key;
  49                         public T Data;
  50
  51                         public Node Next;
  52
  53                         public Node (uint key, T data)
  54                                 : this (false)
  55                         {
  56                                 this.Key = key;
  57                                 this.Data = data;
  58                         }
  59
  60                         protected Node (bool marked)
  61                         {
  62                                 this.Marked = marked;
  63                         }
  64                 }
  65
  66                 class MarkedNode : Node
  67                 {
  68                         public MarkedNode (Node wrapped) : base (true)
  69                         {
  70                                 Next = wrapped;
  71                         }
  72                 }
  73
  74                 const int MaxLoad = 5;
  75                 const int SegmentSize = 50;
  76
  77                 [ThreadStatic]
  78                 Node[] segmentCache;
  79
  80                 Node head;
  81                 Node tail;
  82
  83                 Node[][] buckets = new Node[10][];
  84                 int count;
  85                 int size = 1;
  86
  87                 ManualResetEventSlim mres = new ManualResetEventSlim (true);
  88                 SpinLock mresLock = new SpinLock ();
  89
  90                 public SplitOrderedList ()
  91                 {
  92                         head = new Node (0, default (T));
  93                         tail = new Node (uint.MaxValue, default (T));
  94                         head.Next = tail;
  95                         SetBucket (0, head);
  96                 }
  97
  98                 public int Count {
  99                         get {
 100                                 return count;
 101                         }
 102                 }
 103
 104                 public T InsertOrUpdate (uint key, Func<T> addGetter, Func<T, T> updateGetter)
 105                 {
 106                         Node current;
 107                         bool result = InsertInternal (key, default (T), addGetter, out current);
 108
 109                         if (result)
 110                                 return current.Data;
 111
 112                         // FIXME: this should have a CAS-like behavior
 113                         return current.Data = updateGetter (current.Data);
 114                 }
 115
 116                 public bool Insert (uint key, T data)
 117                 {
 118                         Node current;
 119                         return InsertInternal (key, data, null, out current);
 120                 }
 121
 122                 public T InsertOrGet (uint key, T data, Func<T> dataCreator)
 123                 {
 124                         Node current;
 125                         InsertInternal (key, data, dataCreator, out current);
 126                         return current.Data;
 127                 }
 128
 129                 bool InsertInternal (uint key, T data, Func<T> dataCreator, out Node current)
 130                 {
 131                         Node node = new Node (ComputeRegularKey (key), data);
 132                         uint b = key % (uint)size;
 133
 134                         if (GetBucket (b) == null)
 135                                 InitializeBucket (b);
 136                         if (!ListInsert (node, GetBucket (b), out current, dataCreator))
 137                                 return false;
 138
 139                         int csize = size;
 140                         if (Interlocked.Increment (ref count) / csize > MaxLoad)
 141                                 Interlocked.CompareExchange (ref size, 2 * csize, csize);
 142
 143                         current = node;
 144
 145                         return true;
 146                 }
 147
 148                 public bool Find (uint key, out T data)
 149                 {
 150                         Node node;
 151                         uint b = key % (uint)size;
 152                         data = default (T);
 153
 154                         if (GetBucket (b) == null)
 155                                 InitializeBucket (b);
 156
 157                         if (!ListFind (ComputeRegularKey (key), GetBucket (b), out node))
 158                                 return false;
 159
 160                         data = node.Data;
 161
 162                         return !node.Marked;
 163                 }
 164
 165                 public bool CompareExchange (uint key, T data, Func<T, bool> check)
 166                 {
 167                         Node node;
 168                         uint b = key % (uint)size;
 169
 170                         if (GetBucket (b) == null)
 171                                 InitializeBucket (b);
 172
 173                         if (!ListFind (ComputeRegularKey (key), GetBucket (b), out node))
 174                                 return false;
 175
 176                         if (!check (node.Data))
 177                                 return false;
 178
 179                         node.Data = data;
 180
 181                         return true;
 182                 }
 183
 184                 public bool Delete (uint key, out T data)
 185                 {
 186                         uint b = key % (uint)size;
 187                         if (GetBucket (b) == null)
 188                                 InitializeBucket (b);
 189
 190                         if (!ListDelete (GetBucket (b), ComputeRegularKey (key), out data))
 191                                 return false;
 192
 193                         Interlocked.Decrement (ref count);
 194                         return true;
 195                 }
 196
 197                 public IEnumerator<T> GetEnumerator ()
 198                 {
 199                         Node node = head.Next;
 200
 201                         while (node != tail) {
 202                                 while (node.Marked || (node.Key & 1) == 0) {
 203                                         node = node.Next;
 204                                         if (node == tail)
 205                                                 yield break;
 206                                 }
 207                                 yield return node.Data;
 208                                 node = node.Next;
 209                         }
 210                 }
 211
 212                 void InitializeBucket (uint b)
 213                 {
 214                         Node current;
 215                         uint parent = GetParent (b);
 216                         if (GetBucket (parent) == null)
 217                                 InitializeBucket ((uint)parent);
 218
 219                         Node dummy = new Node (ComputeDummyKey (b), default (T));
 220                         if (!ListInsert (dummy, GetBucket (parent), out current, null))
 221                                 dummy = current;
 222
 223                         SetBucket (b, dummy);
 224                 }
 225
 226                 // Turn v's MSB off
 227                 uint GetParent (uint v)
 228                 {
 229                         uint t, tt;
 230
 231                         // Find MSB position in v
 232                         var pos = (tt = v >> 16) > 0 ?
 233                                 (t = tt >> 8) > 0 ? 24 + logTable[t] : 16 + logTable[tt] :
 234                                 (t = v >> 8) > 0 ? 8 + logTable[t] : logTable[v];
 235
 236                         return (uint)(v & ~(1 << pos));
 237                 }
 238
 239                 // Reverse integer bits and make sure LSB is set
 240                 uint ComputeRegularKey (uint key)
 241                 {
 242                         return ComputeDummyKey (key | 0x80000000);
 243                 }
 244
 245                 // Reverse integer bits
 246                 uint ComputeDummyKey (uint key)
 247                 {
 248                         return ((uint)reverseTable[key & 0xff] << 24) |
 249                                 ((uint)reverseTable[(key >> 8) & 0xff] << 16) |
 250                                 ((uint)reverseTable[(key >> 16) & 0xff] << 8) |
 251                                 ((uint)reverseTable[(key >> 24) & 0xff]);
 252                 }
 253
 254                 // Bucket storage is abstracted in a simple two-layer tree to avoid too much memory resize
 255                 Node GetBucket (uint index)
 256                 {
 257                         int segment = (int)(index / SegmentSize);
 258                         CheckSegment (segment);
 259                         if (buckets[segment] == null)
 260                                 return null;
 261
 262                         return buckets[segment][index % SegmentSize];
 263                 }
 264
 265                 void SetBucket (uint index, Node node)
 266                 {
 267                         int segment = (int)(index / SegmentSize);
 268                         CheckSegment (segment);
 269                         if (buckets[segment] == null) {
 270                                 // Cache segment creation in case CAS fails
 271                                 Node[] newSegment = segmentCache == null ? new Node[SegmentSize] : segmentCache;
 272                                 segmentCache = Interlocked.CompareExchange (ref buckets[segment], newSegment, null) == null ? null : newSegment;
 273                         }
 274                         buckets[segment][index % SegmentSize] = node;
 275                 }
 276
 277                 // When we run out of space for bucket storage, we use a lock-based array resize
 278                 void CheckSegment (int segment)
 279                 {
 280                         while (segment >= buckets.Length) {
 281                                 bool shouldResize = false;
 282                                 bool taken = false;
 283                                 try {
 284                                         mresLock.Enter (ref taken);
 285                                         if (mres.IsSet) {
 286                                                 shouldResize = true;
 287                                                 mres.Reset ();
 288                                         }
 289                                 } finally {
 290                                         if (taken)
 291                                                 mresLock.Exit ();
 292                                 }
 293
 294                                 if (shouldResize) {
 295                                         Array.Resize (ref buckets, buckets.Length * 2);
 296                                         mres.Set ();
 297                                 } else {
 298                                         mres.Wait ();
 299                                 }
 300                         }
 301                 }
 302
 303                 Node ListSearch (uint key, ref Node left, Node h)
 304                 {
 305                         Node leftNodeNext = null, rightNode = null;
 306
 307                 search_again:
 308                         do {
 309                                 Node t = h;
 310                                 Node tNext = h.Next;
 311
 312                                 do {
 313                                         if (!tNext.Marked) {
 314                                                 left = t;
 315                                                 leftNodeNext = tNext;
 316                                         }
 317
 318                                         t = tNext.Marked ? tNext.Next : tNext;
 319                                         if (t == tail)
 320                                                 break;
 321
 322                                         tNext = t.Next;
 323                                 } while (tNext.Marked || t.Key < key);
 324
 325                                 rightNode = t;
 326
 327                                 if (leftNodeNext == rightNode) {
 328                                         if (rightNode != tail && rightNode.Next.Marked)
 329                                                 goto search_again;
 330                                         else
 331                                                 return rightNode;
 332                                 }
 333
 334                                 if (Interlocked.CompareExchange (ref left.Next, rightNode, leftNodeNext) == leftNodeNext) {
 335                                         if (rightNode != tail && rightNode.Next.Marked)
 336                                                 goto search_again;
 337                                         else
 338                                                 return rightNode;
 339                                 }
 340                         } while (true);
 341                 }
 342
 343                 bool ListDelete (Node startPoint, uint key, out T data)
 344                 {
 345                         Node rightNode = null, rightNodeNext = null, leftNode = null;
 346                         data = default (T);
 347
 348                         do {
 349                                 rightNode = ListSearch (key, ref leftNode, startPoint);
 350                                 if (rightNode == tail || rightNode.Key != key)
 351                                         return false;
 352
 353                                 data = rightNode.Data;
 354
 355                                 rightNodeNext = rightNode.Next;
 356                                 if (!rightNodeNext.Marked)
 357                                         if (Interlocked.CompareExchange (ref rightNode.Next, new MarkedNode (rightNodeNext), rightNodeNext) == rightNodeNext)
 358                                                 break;
 359                         } while (true);
 360
 361                         if (Interlocked.CompareExchange (ref leftNode.Next, rightNode, rightNodeNext) != rightNodeNext)
 362                                 rightNode = ListSearch (rightNode.Key, ref leftNode, startPoint);
 363
 364                         return true;
 365                 }
 366
 367                 bool ListInsert (Node newNode, Node startPoint, out Node current, Func<T> dataCreator)
 368                 {
 369                         uint key = newNode.Key;
 370                         Node rightNode = null, leftNode = null;
 371
 372                         do {
 373                                 rightNode = current = ListSearch (key, ref leftNode, startPoint);
 374                                 if (rightNode != tail && rightNode.Key == key)
 375                                         return false;
 376
 377                                 newNode.Next = rightNode;
 378                                 if (dataCreator != null)
 379                                         newNode.Data = dataCreator ();
 380                                 if (Interlocked.CompareExchange (ref leftNode.Next, newNode, rightNode) == rightNode)
 381                                         return true;
 382                         } while (true);
 383                 }
 384
 385                 bool ListFind (uint key, Node startPoint, out Node data)
 386                 {
 387                         Node rightNode = null, leftNode = null;
 388                         data = null;
 389
 390                         rightNode = ListSearch (key, ref leftNode, startPoint);
 391                         data = rightNode;
 392
 393                         return rightNode != tail && rightNode.Key == key;
 394                 }
 395         }
 396 }
 397
 398 #endif