25 #if NET_4_0 || INSIDE_SYSTEM_WEB 33 namespace System.Collections.Concurrent
35 internal class SplitOrderedList<TKey, T>
45 public Node Init (ulong key, TKey subKey, T data)
58 public Node Init (ulong key)
61 this.Data =
default (T);
65 this.SubKey =
default (TKey);
71 public Node Init (Node wrapped)
77 this.Data =
default (T);
78 this.SubKey =
default (TKey);
84 const int MaxLoad = 5;
85 const uint BucketSize = 512;
90 Node[] buckets =
new Node [BucketSize];
94 SimpleRwLock slim =
new SimpleRwLock ();
96 readonly IEqualityComparer<TKey> comparer;
98 public SplitOrderedList (IEqualityComparer<TKey> comparer)
100 this.comparer = comparer;
101 head =
new Node ().Init (0);
102 tail =
new Node ().Init (ulong.MaxValue);
113 public T InsertOrUpdate (uint key, TKey subKey, Func<T> addGetter, Func<T, T> updateGetter)
116 bool result = InsertInternal (key, subKey,
default (T), addGetter, out current);
122 return current.Data = updateGetter (current.Data);
125 public T InsertOrUpdate (uint key, TKey subKey, T addValue, T updateValue)
128 if (InsertInternal (key, subKey, addValue, null, out current))
132 return current.Data = updateValue;
135 public bool Insert (uint key, TKey subKey, T data)
138 return InsertInternal (key, subKey, data, null, out current);
141 public T InsertOrGet (uint key, TKey subKey, T data, Func<T> dataCreator)
144 InsertInternal (key, subKey, data, dataCreator, out current);
148 bool InsertInternal (uint key, TKey subKey, T data, Func<T> dataCreator, out Node current)
150 Node node =
new Node ().Init (ComputeRegularKey (key), subKey, data);
152 uint b = key % (uint)size;
155 if ((bucket = GetBucket (b)) == null)
156 bucket = InitializeBucket (b);
158 if (!ListInsert (node, bucket, out current, dataCreator))
162 if (Interlocked.Increment (ref count) / csize > MaxLoad && (csize & 0x40000000) == 0)
163 Interlocked.CompareExchange (ref size, 2 * csize, csize);
170 public bool Find (uint key, TKey subKey, out T data)
173 uint b = key % (uint)size;
177 if ((bucket = GetBucket (b)) == null)
178 bucket = InitializeBucket (b);
180 if (!ListFind (ComputeRegularKey (key), subKey, bucket, out node))
188 public bool CompareExchange (uint key, TKey subKey, T data, Func<T, bool> check)
191 uint b = key % (uint)size;
194 if ((bucket = GetBucket (b)) == null)
195 bucket = InitializeBucket (b);
197 if (!ListFind (ComputeRegularKey (key), subKey, bucket, out node))
200 if (!check (node.Data))
208 public bool Delete (uint key, TKey subKey, out T data)
210 uint b = key % (uint)size;
213 if ((bucket = GetBucket (b)) == null)
214 bucket = InitializeBucket (b);
216 if (!ListDelete (bucket, ComputeRegularKey (key), subKey, out data))
219 Interlocked.Decrement (ref count);
223 public IEnumerator<T> GetEnumerator ()
225 Node node = head.Next;
227 while (node != tail) {
228 while (node.Marked || (node.Key & 1) == 0) {
233 yield
return node.Data;
238 Node InitializeBucket (uint b)
241 uint parent = GetParent (b);
244 if ((bucket = GetBucket (parent)) == null)
245 bucket = InitializeBucket (parent);
247 Node dummy =
new Node ().Init (ComputeDummyKey (b));
248 if (!ListInsert (dummy, bucket, out current, null))
251 return SetBucket (b, dummy);
255 static uint GetParent (uint v)
260 var pos = (tt = v >> 16) > 0 ?
261 (t = tt >> 8) > 0 ? 24 + logTable[t] : 16 + logTable[tt] :
262 (t = v >> 8) > 0 ? 8 + logTable[t] : logTable[v];
264 return (uint)(v & ~(1 << pos));
268 static ulong ComputeRegularKey (uint key)
270 return ComputeDummyKey (key) | 1;
274 static ulong ComputeDummyKey (uint key)
276 return ((ulong)(((uint)reverseTable[key & 0xff] << 24) |
277 ((uint)reverseTable[(key >> 8) & 0xff] << 16) |
278 ((uint)reverseTable[(key >> 16) & 0xff] << 8) |
279 ((uint)reverseTable[(key >> 24) & 0xff]))) << 1;
283 Node GetBucket (uint index)
285 if (index >= buckets.Length)
287 return buckets[index];
290 Node SetBucket (uint index, Node node)
293 slim.EnterReadLock ();
294 CheckSegment (index,
true);
297 return buckets[index];
299 slim.ExitReadLock ();
304 void CheckSegment (uint segment,
bool readLockTaken)
306 if (segment < buckets.Length)
310 slim.ExitReadLock ();
312 slim.EnterWriteLock ();
313 while (segment >= buckets.Length)
314 Array.Resize (ref buckets, buckets.Length * 2);
316 slim.ExitWriteLock ();
319 slim.EnterReadLock ();
322 Node ListSearch (ulong key, TKey subKey, ref Node left, Node h)
324 Node leftNodeNext = null, rightNode = null;
332 leftNodeNext = tNext;
334 t = tNext.Marked ? tNext.Next : tNext;
339 }
while (tNext.Marked || t.Key < key || (tNext.Key == key && !comparer.Equals (subKey, t.SubKey)));
343 if (leftNodeNext == rightNode) {
344 if (rightNode != tail && rightNode.Next.Marked)
350 if (
AotInterlocked.CompareExchange (ref left.Next, rightNode, leftNodeNext) == leftNodeNext) {
351 if (rightNode != tail && rightNode.Next.Marked)
359 bool ListDelete (Node startPoint, ulong key, TKey subKey, out T data)
361 Node rightNode = null, rightNodeNext = null, leftNode = null;
363 Node markedNode = null;
366 rightNode = ListSearch (key, subKey, ref leftNode, startPoint);
367 if (rightNode == tail || rightNode.Key != key || !comparer.Equals (subKey, rightNode.SubKey))
370 data = rightNode.Data;
371 rightNodeNext = rightNode.Next;
373 if (!rightNodeNext.Marked) {
374 if (markedNode == null)
375 markedNode =
new Node ();
376 markedNode.Init (rightNodeNext);
378 if (
AotInterlocked.CompareExchange (ref rightNode.Next, markedNode, rightNodeNext) == rightNodeNext)
383 if (
AotInterlocked.CompareExchange (ref leftNode.Next, rightNodeNext, rightNode) != rightNode)
384 ListSearch (rightNode.Key, subKey, ref leftNode, startPoint);
389 bool ListInsert (Node newNode, Node startPoint, out Node current, Func<T> dataCreator)
391 ulong key = newNode.Key;
392 Node rightNode = null, leftNode = null;
395 rightNode = current = ListSearch (key, newNode.SubKey, ref leftNode, startPoint);
396 if (rightNode != tail && rightNode.Key == key && comparer.Equals (newNode.SubKey, rightNode.SubKey))
399 newNode.Next = rightNode;
400 if (dataCreator != null)
401 newNode.Data = dataCreator ();
402 if (
AotInterlocked.CompareExchange (ref leftNode.Next, newNode, rightNode) == rightNode)
407 bool ListFind (ulong key, TKey subKey, Node startPoint, out Node data)
409 Node rightNode = null, leftNode = null;
412 rightNode = ListSearch (key, subKey, ref leftNode, startPoint);
415 return rightNode != tail && rightNode.Key == key && comparer.Equals (subKey, rightNode.SubKey);
418 static readonly byte[] reverseTable = {
419 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
422 static readonly byte[] logTable = {
423 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
428 const int RwWait = 1;
429 const int RwWrite = 2;
430 const int RwRead = 4;
434 public void EnterReadLock ()
438 while ((rwlock & (RwWrite | RwWait)) > 0)
441 if ((Interlocked.Add (ref rwlock, RwRead) & (RwWait | RwWait)) == 0)
444 Interlocked.Add (ref rwlock, -RwRead);
448 public void ExitReadLock ()
450 Interlocked.Add (ref rwlock, -RwRead);
453 public void EnterWriteLock ()
458 if (state < RwWrite) {
459 if (Interlocked.CompareExchange (ref rwlock, RwWrite, state) == state)
464 while ((state & RwWait) == 0 && Interlocked.CompareExchange (ref rwlock, state | RwWait, state) != state)
467 while (rwlock > RwWait)
472 public void ExitWriteLock ()
474 Interlocked.Add (ref rwlock, -RwWrite);
479 #if INSIDE_SYSTEM_WEB && !NET_4_0 484 const int maxTime = 200;
485 static readonly
bool isSingleCpu = (Environment.ProcessorCount == 1);
489 public void SpinOnce ()
497 if (ntime % step == 0)
501 Thread.SpinWait (Math.Min (ntime, maxTime) << 1);
Interlocked reference exchanges do not work with the older Mono AOT compiler so this type fudges arou...