3 // Copyright (c) 2010 Jérémie "Garuma" Laval
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:
12 // The above copyright notice and this permission notice shall be included in
13 // all copies or substantial portions of the Software.
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
27 using System.Threading;
28 using System.Collections;
29 using System.Collections.Generic;
30 using System.Runtime.Serialization;
32 namespace System.Collections.Concurrent
34 internal class SplitOrderedList<TKey, T>
44 public Node Init (ulong key, TKey subKey, T data)
56 // Used to create dummy node
57 public Node Init (ulong key)
60 this.Data = default (T);
64 this.SubKey = default (TKey);
69 // Used to create marked node
70 public Node Init (Node wrapped)
76 this.Data = default (T);
77 this.SubKey = default (TKey);
83 const int MaxLoad = 5;
84 const uint BucketSize = 512;
89 Node[] buckets = new Node [BucketSize];
93 SimpleRwLock slim = new SimpleRwLock ();
95 readonly IEqualityComparer<TKey> comparer;
97 public SplitOrderedList (IEqualityComparer<TKey> comparer)
99 this.comparer = comparer;
100 head = new Node ().Init (0);
101 tail = new Node ().Init (ulong.MaxValue);
112 public T InsertOrUpdate (uint key, TKey subKey, Func<T> addGetter, Func<T, T> updateGetter)
115 bool result = InsertInternal (key, subKey, default (T), addGetter, out current);
120 // FIXME: this should have a CAS-like behavior
121 return current.Data = updateGetter (current.Data);
124 public T InsertOrUpdate (uint key, TKey subKey, T addValue, T updateValue)
127 if (InsertInternal (key, subKey, addValue, null, out current))
130 // FIXME: this should have a CAS-like behavior
131 return current.Data = updateValue;
134 public bool Insert (uint key, TKey subKey, T data)
137 return InsertInternal (key, subKey, data, null, out current);
140 public T InsertOrGet (uint key, TKey subKey, T data, Func<T> dataCreator)
143 InsertInternal (key, subKey, data, dataCreator, out current);
147 bool InsertInternal (uint key, TKey subKey, T data, Func<T> dataCreator, out Node current)
149 Node node = new Node ().Init (ComputeRegularKey (key), subKey, data);
151 uint b = key % (uint)size;
154 if ((bucket = GetBucket (b)) == null)
155 bucket = InitializeBucket (b);
157 if (!ListInsert (node, bucket, out current, dataCreator))
161 if (Interlocked.Increment (ref count) / csize > MaxLoad && (csize & 0x40000000) == 0)
162 Interlocked.CompareExchange (ref size, 2 * csize, csize);
169 public bool Find (uint key, TKey subKey, out T data)
172 uint b = key % (uint)size;
176 if ((bucket = GetBucket (b)) == null)
177 bucket = InitializeBucket (b);
179 if (!ListFind (ComputeRegularKey (key), subKey, bucket, out node))
187 public bool CompareExchange (uint key, TKey subKey, T data, Func<T, bool> check)
190 uint b = key % (uint)size;
193 if ((bucket = GetBucket (b)) == null)
194 bucket = InitializeBucket (b);
196 if (!ListFind (ComputeRegularKey (key), subKey, bucket, out node))
199 if (!check (node.Data))
207 public bool Delete (uint key, TKey subKey, out T data)
209 uint b = key % (uint)size;
212 if ((bucket = GetBucket (b)) == null)
213 bucket = InitializeBucket (b);
215 if (!ListDelete (bucket, ComputeRegularKey (key), subKey, out data))
218 Interlocked.Decrement (ref count);
222 public IEnumerator<T> GetEnumerator ()
224 Node node = head.Next;
226 while (node != tail) {
227 while (node.Marked || (node.Key & 1) == 0) {
232 yield return node.Data;
237 Node InitializeBucket (uint b)
240 uint parent = GetParent (b);
243 if ((bucket = GetBucket (parent)) == null)
244 bucket = InitializeBucket (parent);
246 Node dummy = new Node ().Init (ComputeDummyKey (b));
247 if (!ListInsert (dummy, bucket, out current, null))
250 return SetBucket (b, dummy);
254 static uint GetParent (uint v)
258 // Find MSB position in v
259 var pos = (tt = v >> 16) > 0 ?
260 (t = tt >> 8) > 0 ? 24 + logTable[t] : 16 + logTable[tt] :
261 (t = v >> 8) > 0 ? 8 + logTable[t] : logTable[v];
263 return (uint)(v & ~(1 << pos));
266 // Reverse integer bits and make sure LSB is set
267 static ulong ComputeRegularKey (uint key)
269 return ComputeDummyKey (key) | 1;
272 // Reverse integer bits
273 static ulong ComputeDummyKey (uint key)
275 return ((ulong)(((uint)reverseTable[key & 0xff] << 24) |
276 ((uint)reverseTable[(key >> 8) & 0xff] << 16) |
277 ((uint)reverseTable[(key >> 16) & 0xff] << 8) |
278 ((uint)reverseTable[(key >> 24) & 0xff]))) << 1;
281 // Bucket storage is abstracted in a simple two-layer tree to avoid too much memory resize
282 Node GetBucket (uint index)
284 if (index >= buckets.Length)
286 return buckets[index];
289 Node SetBucket (uint index, Node node)
292 slim.EnterReadLock ();
293 CheckSegment (index, true);
295 Interlocked.CompareExchange (ref buckets[index], node, null);
296 return buckets[index];
298 slim.ExitReadLock ();
302 // When we run out of space for bucket storage, we use a lock-based array resize
303 void CheckSegment (uint segment, bool readLockTaken)
305 if (segment < buckets.Length)
309 slim.ExitReadLock ();
311 slim.EnterWriteLock ();
312 while (segment >= buckets.Length)
313 Array.Resize (ref buckets, buckets.Length * 2);
315 slim.ExitWriteLock ();
318 slim.EnterReadLock ();
321 Node ListSearch (ulong key, TKey subKey, ref Node left, Node h)
323 Node leftNodeNext = null, rightNode = null;
331 leftNodeNext = tNext;
333 t = tNext.Marked ? tNext.Next : tNext;
338 } while (tNext.Marked || t.Key < key || (tNext.Key == key && !comparer.Equals (subKey, t.SubKey)));
342 if (leftNodeNext == rightNode) {
343 if (rightNode != tail && rightNode.Next.Marked)
349 if (Interlocked.CompareExchange (ref left.Next, rightNode, leftNodeNext) == leftNodeNext) {
350 if (rightNode != tail && rightNode.Next.Marked)
358 bool ListDelete (Node startPoint, ulong key, TKey subKey, out T data)
360 Node rightNode = null, rightNodeNext = null, leftNode = null;
362 Node markedNode = null;
365 rightNode = ListSearch (key, subKey, ref leftNode, startPoint);
366 if (rightNode == tail || rightNode.Key != key || !comparer.Equals (subKey, rightNode.SubKey))
369 data = rightNode.Data;
370 rightNodeNext = rightNode.Next;
372 if (!rightNodeNext.Marked) {
373 if (markedNode == null)
374 markedNode = new Node ();
375 markedNode.Init (rightNodeNext);
377 if (Interlocked.CompareExchange (ref rightNode.Next, markedNode, rightNodeNext) == rightNodeNext)
382 if (Interlocked.CompareExchange (ref leftNode.Next, rightNodeNext, rightNode) != rightNode)
383 ListSearch (rightNode.Key, subKey, ref leftNode, startPoint);
388 bool ListInsert (Node newNode, Node startPoint, out Node current, Func<T> dataCreator)
390 ulong key = newNode.Key;
391 Node rightNode = null, leftNode = null;
394 rightNode = current = ListSearch (key, newNode.SubKey, ref leftNode, startPoint);
395 if (rightNode != tail && rightNode.Key == key && comparer.Equals (newNode.SubKey, rightNode.SubKey))
398 newNode.Next = rightNode;
399 if (dataCreator != null)
400 newNode.Data = dataCreator ();
401 if (Interlocked.CompareExchange (ref leftNode.Next, newNode, rightNode) == rightNode)
406 bool ListFind (ulong key, TKey subKey, Node startPoint, out Node data)
408 Node rightNode = null, leftNode = null;
411 rightNode = ListSearch (key, subKey, ref leftNode, startPoint);
414 return rightNode != tail && rightNode.Key == key && comparer.Equals (subKey, rightNode.SubKey);
417 static readonly byte[] reverseTable = {
418 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
421 static readonly byte[] logTable = {
422 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
427 const int RwWait = 1;
428 const int RwWrite = 2;
429 const int RwRead = 4;
433 public void EnterReadLock ()
435 SpinWait sw = new SpinWait ();
437 while ((rwlock & (RwWrite | RwWait)) > 0)
440 if ((Interlocked.Add (ref rwlock, RwRead) & (RwWait | RwWait)) == 0)
443 Interlocked.Add (ref rwlock, -RwRead);
447 public void ExitReadLock ()
449 Interlocked.Add (ref rwlock, -RwRead);
452 public void EnterWriteLock ()
454 SpinWait sw = new SpinWait ();
457 if (state < RwWrite) {
458 if (Interlocked.CompareExchange (ref rwlock, RwWrite, state) == state)
462 // We register our interest in taking the Write lock (if upgradeable it's already done)
463 while ((state & RwWait) == 0 && Interlocked.CompareExchange (ref rwlock, state | RwWait, state) != state)
465 // Before falling to sleep
466 while (rwlock > RwWait)
471 public void ExitWriteLock ()
473 Interlocked.Add (ref rwlock, -RwWrite);