1
// SplitOrderedList.cs
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
28
using System.Threading;
29
using System.Collections;
30
using System.Collections.Generic;
31
using System.Runtime.Serialization;
33
namespace ServiceStack.Net30.Collections.Concurrent
35
internal class SplitOrderedList<TKey, T>
45
public Node Init (ulong key, TKey subKey, T data)
57
// Used to create dummy node
58
public Node Init (ulong key)
61
this.Data = default (T);
65
this.SubKey = default (TKey);
70
// Used to create marked node
71
public Node Init (Node wrapped)
77
this.Data = default (T);
78
this.SubKey = default (TKey);
84
class NodeObjectPool : ObjectPool<Node> {
85
protected override Node Creator ()
90
static readonly NodeObjectPool pool = new NodeObjectPool ();
92
const int MaxLoad = 5;
93
const uint BucketSize = 512;
98
Node[] buckets = new Node [BucketSize];
102
SimpleRwLock slim = new SimpleRwLock ();
104
readonly IEqualityComparer<TKey> comparer;
106
public SplitOrderedList (IEqualityComparer<TKey> comparer)
108
this.comparer = comparer;
109
head = new Node ().Init (0);
110
tail = new Node ().Init (ulong.MaxValue);
121
public T InsertOrUpdate (uint key, TKey subKey, Func<T> addGetter, Func<T, T> updateGetter)
124
bool result = InsertInternal (key, subKey, default (T), addGetter, out current);
129
// FIXME: this should have a CAS-like behavior
130
return current.Data = updateGetter (current.Data);
133
public T InsertOrUpdate (uint key, TKey subKey, T addValue, T updateValue)
136
if (InsertInternal (key, subKey, addValue, null, out current))
139
// FIXME: this should have a CAS-like behavior
140
return current.Data = updateValue;
143
public bool Insert (uint key, TKey subKey, T data)
146
return InsertInternal (key, subKey, data, null, out current);
149
public T InsertOrGet (uint key, TKey subKey, T data, Func<T> dataCreator)
152
InsertInternal (key, subKey, data, dataCreator, out current);
156
bool InsertInternal (uint key, TKey subKey, T data, Func<T> dataCreator, out Node current)
158
Node node = pool.Take ().Init (ComputeRegularKey (key), subKey, data);
160
uint b = key % (uint)size;
163
if ((bucket = GetBucket (b)) == null)
164
bucket = InitializeBucket (b);
166
if (!ListInsert (node, bucket, out current, dataCreator))
170
if (Interlocked.Increment (ref count) / csize > MaxLoad && (csize & 0x40000000) == 0)
171
Interlocked.CompareExchange (ref size, 2 * csize, csize);
178
public bool Find (uint key, TKey subKey, out T data)
181
uint b = key % (uint)size;
185
if ((bucket = GetBucket (b)) == null)
186
bucket = InitializeBucket (b);
188
if (!ListFind (ComputeRegularKey (key), subKey, bucket, out node))
196
public bool CompareExchange (uint key, TKey subKey, T data, Func<T, bool> check)
199
uint b = key % (uint)size;
202
if ((bucket = GetBucket (b)) == null)
203
bucket = InitializeBucket (b);
205
if (!ListFind (ComputeRegularKey (key), subKey, bucket, out node))
208
if (!check (node.Data))
216
public bool Delete (uint key, TKey subKey, out T data)
218
uint b = key % (uint)size;
221
if ((bucket = GetBucket (b)) == null)
222
bucket = InitializeBucket (b);
224
if (!ListDelete (bucket, ComputeRegularKey (key), subKey, out data))
227
Interlocked.Decrement (ref count);
231
public IEnumerator<T> GetEnumerator ()
233
Node node = head.Next;
235
while (node != tail) {
236
while (node.Marked || (node.Key & 1) == 0) {
241
yield return node.Data;
246
Node InitializeBucket (uint b)
249
uint parent = GetParent (b);
252
if ((bucket = GetBucket (parent)) == null)
253
bucket = InitializeBucket (parent);
255
Node dummy = pool.Take ().Init (ComputeDummyKey (b));
256
if (!ListInsert (dummy, bucket, out current, null))
259
return SetBucket (b, dummy);
263
static uint GetParent (uint v)
267
// Find MSB position in v
268
var pos = (tt = v >> 16) > 0 ?
269
(t = tt >> 8) > 0 ? 24 + logTable[t] : 16 + logTable[tt] :
270
(t = v >> 8) > 0 ? 8 + logTable[t] : logTable[v];
272
return (uint)(v & ~(1 << pos));
275
// Reverse integer bits and make sure LSB is set
276
static ulong ComputeRegularKey (uint key)
278
return ComputeDummyKey (key) | 1;
281
// Reverse integer bits
282
static ulong ComputeDummyKey (uint key)
284
return ((ulong)(((uint)reverseTable[key & 0xff] << 24) |
285
((uint)reverseTable[(key >> 8) & 0xff] << 16) |
286
((uint)reverseTable[(key >> 16) & 0xff] << 8) |
287
((uint)reverseTable[(key >> 24) & 0xff]))) << 1;
290
// Bucket storage is abstracted in a simple two-layer tree to avoid too much memory resize
291
Node GetBucket (uint index)
293
if (index >= buckets.Length)
295
return buckets[index];
298
Node SetBucket (uint index, Node node)
301
slim.EnterReadLock ();
302
CheckSegment (index, true);
304
Interlocked.CompareExchange (ref buckets[index], node, null);
305
return buckets[index];
307
slim.ExitReadLock ();
311
// When we run out of space for bucket storage, we use a lock-based array resize
312
void CheckSegment (uint segment, bool readLockTaken)
314
if (segment < buckets.Length)
318
slim.ExitReadLock ();
320
slim.EnterWriteLock ();
321
while (segment >= buckets.Length)
322
Array.Resize (ref buckets, buckets.Length * 2);
324
slim.ExitWriteLock ();
327
slim.EnterReadLock ();
330
Node ListSearch (ulong key, TKey subKey, ref Node left, Node h)
332
Node leftNodeNext = null, rightNode = null;
340
leftNodeNext = tNext;
342
t = tNext.Marked ? tNext.Next : tNext;
347
} while (tNext.Marked || t.Key < key || (tNext.Key == key && !comparer.Equals (subKey, t.SubKey)));
351
if (leftNodeNext == rightNode) {
352
if (rightNode != tail && rightNode.Next.Marked)
358
if (Interlocked.CompareExchange (ref left.Next, rightNode, leftNodeNext) == leftNodeNext) {
359
pool.Release (leftNodeNext);
360
if (rightNode != tail && rightNode.Next.Marked)
368
bool ListDelete (Node startPoint, ulong key, TKey subKey, out T data)
370
Node rightNode = null, rightNodeNext = null, leftNode = null;
372
Node markedNode = null;
375
rightNode = ListSearch (key, subKey, ref leftNode, startPoint);
376
if (rightNode == tail || rightNode.Key != key)
379
data = rightNode.Data;
380
rightNodeNext = rightNode.Next;
382
if (!rightNodeNext.Marked) {
383
if (markedNode == null)
384
markedNode = pool.Take ();
385
markedNode.Init (rightNodeNext);
387
if (Interlocked.CompareExchange (ref rightNode.Next, markedNode, rightNodeNext) == rightNodeNext)
392
if (Interlocked.CompareExchange (ref leftNode.Next, rightNodeNext, rightNode) != rightNode)
393
ListSearch (rightNode.Key, subKey, ref leftNode, startPoint);
395
pool.Release (rightNode);
400
bool ListInsert (Node newNode, Node startPoint, out Node current, Func<T> dataCreator)
402
ulong key = newNode.Key;
403
Node rightNode = null, leftNode = null;
406
rightNode = current = ListSearch (key, newNode.SubKey, ref leftNode, startPoint);
407
if (rightNode != tail && rightNode.Key == key && comparer.Equals (newNode.SubKey, rightNode.SubKey))
410
newNode.Next = rightNode;
411
if (dataCreator != null)
412
newNode.Data = dataCreator ();
413
if (Interlocked.CompareExchange (ref leftNode.Next, newNode, rightNode) == rightNode)
418
bool ListFind (ulong key, TKey subKey, Node startPoint, out Node data)
420
Node rightNode = null, leftNode = null;
423
rightNode = ListSearch (key, subKey, ref leftNode, startPoint);
426
return rightNode != tail && rightNode.Key == key;
429
static readonly byte[] reverseTable = {
430
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
433
static readonly byte[] logTable = {
434
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
439
const int RwWait = 1;
440
const int RwWrite = 2;
441
const int RwRead = 4;
445
public void EnterReadLock ()
447
SpinWait sw = new SpinWait ();
449
while ((rwlock & (RwWrite | RwWait)) > 0)
452
if ((Interlocked.Add (ref rwlock, RwRead) & (RwWait | RwWait)) == 0)
455
Interlocked.Add (ref rwlock, -RwRead);
459
public void ExitReadLock ()
461
Interlocked.Add (ref rwlock, -RwRead);
464
public void EnterWriteLock ()
466
SpinWait sw = new SpinWait ();
469
if (state < RwWrite) {
470
if (Interlocked.CompareExchange (ref rwlock, RwWrite, state) == state)
474
// We register our interest in taking the Write lock (if upgradeable it's already done)
475
while ((state & RwWait) == 0 && Interlocked.CompareExchange (ref rwlock, state | RwWait, state) != state)
477
// Before falling to sleep
478
while (rwlock > RwWait)
483
public void ExitWriteLock ()
485
Interlocked.Add (ref rwlock, -RwWrite);
491
internal struct SpinWait
493
// The number of step until SpinOnce yield on multicore machine
495
const int maxTime = 200;
496
static readonly bool isSingleCpu = (Environment.ProcessorCount == 1);
500
public void SpinOnce ()
505
// On a single-CPU system, spinning does no good
508
if (ntime % step == 0)
511
// Multi-CPU system might be hyper-threaded, let other thread run
512
Thread.SpinWait (Math.Min (ntime, maxTime) << 1);
b'\\ No newline at end of file'