DotNext by .NET Foundation and Contributors

<PackageReference Include="DotNext" Version="4.6.0" />

 ConcurrentCache<TKey, TValue>

public class ConcurrentCache<TKey, TValue> : IReadOnlyDictionary<TKey, TValue>, IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable, IReadOnlyCollection<KeyValuePair<TKey, TValue>>
Represents concurrect cache.
using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics.CodeAnalysis; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using System.Threading; namespace DotNext.Runtime.Caching { [System.Runtime.CompilerServices.NullableContext(1)] [System.Runtime.CompilerServices.Nullable(0)] public class ConcurrentCache<TKey, [System.Runtime.CompilerServices.Nullable(2)] TValue> : IReadOnlyDictionary<TKey, TValue>, IEnumerable<KeyValuePair<TKey, TValue>>, IEnumerable, IReadOnlyCollection<KeyValuePair<TKey, TValue>> { private class KeyValuePair { internal readonly int KeyHashCode; internal readonly TKey Key; internal volatile KeyValuePair Next; internal (KeyValuePair Previous, KeyValuePair Next) Links; private protected KeyValuePair(TKey key, int hashCode) { Key = key; KeyHashCode = hashCode; } internal void Clear() { Links = default((KeyValuePair, KeyValuePair)); Next = null; } } private sealed class KeyValuePairAtomicAccess : KeyValuePair { internal TValue Value; internal KeyValuePairAtomicAccess(TKey key, TValue value, int hashCode) : base(key, hashCode) { Value = value; } public override string ToString() { return "Key = {Key} Value = {Value}"; } } private sealed class KeyValuePairNonAtomicAccess : KeyValuePair { private sealed class ValueHolder { internal readonly TValue Value; internal ValueHolder(TValue value) { Value = value; } } private ValueHolder holder; internal TValue Value { get { return holder.Value; } set { holder = new ValueHolder(value); } } internal KeyValuePairNonAtomicAccess(TKey key, TValue value, int hashCode) : base(key, hashCode) { holder = new ValueHolder(value); } public override string ToString() { return "Key = {Key} Value = {Value}"; } } private sealed class Command { private Func<KeyValuePair, KeyValuePair> invoker; private KeyValuePair target; internal volatile Command Next; internal void Initialize(Func<KeyValuePair, KeyValuePair> invoker, KeyValuePair target) { this.invoker = invoker; this.target = target; } internal void Clear() { invoker = null; target = null; } internal KeyValuePair Invoke() { return invoker(target); } } private static readonly bool IsValueWriteAtomic; private readonly int concurrencyLevel; private readonly KeyValuePair[] buckets; private readonly object[] locks; private readonly IEqualityComparer<TKey> keyComparer; private volatile int count; private readonly object evictionLock = new object(); private readonly Action<TKey, TValue> evictionHandler; private readonly Func<KeyValuePair, KeyValuePair> addCommand; private readonly Func<KeyValuePair, KeyValuePair> removeCommand; private readonly Func<KeyValuePair, KeyValuePair> readCommand; private int evictionListSize; private KeyValuePair firstPair; private KeyValuePair lastPair; private volatile bool rateLimitReached; private volatile Command commandQueueWritePosition; private Command commandQueueReadPosition; private Command pooledCommand; private static int RecommendedConcurrencyLevel { get { int processorCount = Environment.ProcessorCount; return processorCount + (processorCount + 1) / 2; } } IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys { get { return <System.Collections.Generic.IReadOnlyDictionary<TKey,TValue>.get_Keys>g__GetKeys|8_0(buckets); } } IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values { get { return <System.Collections.Generic.IReadOnlyDictionary<TKey,TValue>.get_Values>g__GetValues|10_0(buckets); } } public int Count => count; public TValue this[TKey key] { get { if (!TryGetValue(key, out TValue value)) throw new KeyNotFoundException(); return value; } set { IEqualityComparer<TKey> equalityComparer = keyComparer; int hashCode = equalityComparer?.GetHashCode(key) ?? key.GetHashCode(); TryAdd(key, equalityComparer, hashCode, value, true, out TValue _); } } [System.Runtime.CompilerServices.Nullable(new byte[] { 2, 1, 1 })] public Action<TKey, TValue> Eviction { [return: System.Runtime.CompilerServices.Nullable(new byte[] { 2, 1, 1 })] get { return evictionHandler; } [param: System.Runtime.CompilerServices.Nullable(new byte[] { 2, 1, 1 })] set { evictionHandler = value; } } public bool ExecuteEvictionAsynchronously { get; set; } public ConcurrentCache(int capacity, int concurrencyLevel, CacheEvictionPolicy evictionPolicy, [System.Runtime.CompilerServices.Nullable(new byte[] { 2, 1 })] IEqualityComparer<TKey> keyComparer = null) { if (capacity < 1) throw new ArgumentOutOfRangeException("capacity"); if (concurrencyLevel < 1) throw new ArgumentOutOfRangeException("concurrencyLevel"); if (!Enum.IsDefined<CacheEvictionPolicy>(evictionPolicy)) throw new ArgumentOutOfRangeException("evictionPolicy"); buckets = new KeyValuePair[capacity]; Span.Initialize<object>((Span<object>)(locks = new object[capacity])); this.keyComparer = keyComparer; this.concurrencyLevel = concurrencyLevel; addCommand = OnAdd; removeCommand = OnRemove; Func<KeyValuePair, KeyValuePair> func = readCommand = ((evictionPolicy != CacheEvictionPolicy.LFU) ? new Func<KeyValuePair, KeyValuePair>(OnReadLRU) : new Func<KeyValuePair, KeyValuePair>(OnReadLFU)); commandQueueReadPosition = (commandQueueWritePosition = new Command()); } public ConcurrentCache(int capacity, CacheEvictionPolicy evictionPolicy, [System.Runtime.CompilerServices.Nullable(new byte[] { 2, 1 })] IEqualityComparer<TKey> keyComparer = null) : this(capacity, RecommendedConcurrencyLevel, evictionPolicy, keyComparer) { } public void Clear() { int acquiredLocks = 0; bool lockTaken = false; try { Monitor.Enter(evictionLock, ref lockTaken); acquiredLocks = AcquireAllLocks(); RemoveAllKeys(); firstPair = (lastPair = null); } finally { ReleaseLocks(acquiredLocks); if (lockTaken) Monitor.Exit(evictionLock); } } bool IReadOnlyDictionary<TKey, TValue>.ContainsKey(TKey key) { TValue value; return TryGetValue(key, out value); } [return: System.Runtime.CompilerServices.Nullable(new byte[] { 1, 0, 1, 1 })] public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() { return <GetEnumerator>g__GetEnumerator|14_0(buckets); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static TValue GetValue(KeyValuePair pair) { if (!IsValueWriteAtomic) return Unsafe.As<KeyValuePairNonAtomicAccess>((object)pair).Value; return Unsafe.As<KeyValuePairAtomicAccess>((object)pair).Value; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static void SetValue(KeyValuePair pair, TValue value) { if (IsValueWriteAtomic) Unsafe.As<KeyValuePairAtomicAccess>((object)pair).Value = value; else Unsafe.As<KeyValuePairNonAtomicAccess>((object)pair).Value = value; } [MethodImpl(MethodImplOptions.AggressiveInlining)] private ref KeyValuePair GetBucket(int hashCode) { uint num = (uint)hashCode % (uint)buckets.Length; return ref Unsafe.Add<KeyValuePair>(ref MemoryMarshal.GetArrayDataReference<KeyValuePair>(buckets), (UIntPtr)num); } private ref KeyValuePair GetBucket(int hashCode, out object bucketLock) { uint num = (uint)hashCode % (uint)buckets.Length; bucketLock = Unsafe.Add<object>(ref MemoryMarshal.GetArrayDataReference<object>(locks), (UIntPtr)num); return ref Unsafe.Add<KeyValuePair>(ref MemoryMarshal.GetArrayDataReference<KeyValuePair>(buckets), (UIntPtr)num); } private void Remove(KeyValuePair expected) { object bucketLock; ref KeyValuePair bucket = ref GetBucket(expected.KeyHashCode, out bucketLock); lock (bucketLock) { KeyValuePair keyValuePair = Volatile.Read<KeyValuePair>(ref bucket); KeyValuePair keyValuePair2 = null; while (true) { if (keyValuePair == null) return; if (expected == keyValuePair) break; keyValuePair2 = keyValuePair; keyValuePair = keyValuePair.Next; } if (keyValuePair2 == null) Volatile.Write<KeyValuePair>(ref bucket, keyValuePair.Next); else keyValuePair2.Next = keyValuePair.Next; OnRemoved(); } } private void OnAdded() { Interlocked.Increment(ref count); } private void OnRemoved() { Interlocked.Decrement(ref count); } private bool TryAdd(TKey key, IEqualityComparer<TKey> keyComparer, int hashCode, TValue value, bool updateIfExists, out TValue previous) { object bucketLock; ref KeyValuePair bucket = ref GetBucket(hashCode, out bucketLock); bool result = default(bool); Func<KeyValuePair, KeyValuePair> invoker = default(Func<KeyValuePair, KeyValuePair>); KeyValuePair keyValuePair2 = default(KeyValuePair); lock (bucketLock) { if (keyComparer == null) { KeyValuePair keyValuePair = Volatile.Read<KeyValuePair>(ref bucket); while (keyValuePair != null) { if (hashCode != keyValuePair.KeyHashCode || !(typeof(TKey).IsValueType ? EqualityComparer<TKey>.Default.Equals(key, keyValuePair.Key) : keyValuePair.Key.Equals(key))) { keyValuePair = keyValuePair.Next; continue; } previous = GetValue(keyValuePair); result = false; if (!updateIfExists) return result; SetValue(keyValuePair, value); invoker = readCommand; keyValuePair2 = keyValuePair; goto end_IL_0010; } } else { KeyValuePair keyValuePair3 = Volatile.Read<KeyValuePair>(ref bucket); while (keyValuePair3 != null) { if (hashCode != keyValuePair3.KeyHashCode || !keyComparer.Equals(key, keyValuePair3.Key)) { keyValuePair3 = keyValuePair3.Next; continue; } previous = GetValue(keyValuePair3); result = false; if (!updateIfExists) return result; SetValue(keyValuePair3, value); invoker = readCommand; keyValuePair2 = keyValuePair3; goto end_IL_0010; } } previous = default(TValue); keyValuePair2 = (IsValueWriteAtomic ? ((KeyValuePair)new KeyValuePairAtomicAccess(key, value, hashCode)) : ((KeyValuePair)new KeyValuePairNonAtomicAccess(key, value, hashCode))); keyValuePair2.Next = bucket; Volatile.Write<KeyValuePair>(ref bucket, keyValuePair2); invoker = addCommand; result = true; OnAdded(); end_IL_0010:; } EnqueueAndDrain(invoker, keyValuePair2); return result; } public bool TryAdd(TKey key, TValue value) { IEqualityComparer<TKey> equalityComparer = keyComparer; int hashCode = equalityComparer?.GetHashCode(key) ?? key.GetHashCode(); TValue previous; return TryAdd(key, equalityComparer, hashCode, value, false, out previous); } public TValue AddOrUpdate(TKey key, TValue value, out bool added) { IEqualityComparer<TKey> equalityComparer = keyComparer; int hashCode = equalityComparer?.GetHashCode(key) ?? key.GetHashCode(); if (!(added = TryAdd(key, equalityComparer, hashCode, value, true, out TValue previous))) return previous; previous = value; return previous; } public TValue GetOrAdd(TKey key, TValue value, out bool added) { IEqualityComparer<TKey> equalityComparer = keyComparer; int hashCode = equalityComparer?.GetHashCode(key) ?? key.GetHashCode(); if (TryGetValue(key, equalityComparer, hashCode, out TValue value2)) added = false; else if (added = TryAdd(key, equalityComparer, hashCode, value, false, out value2)) { value2 = value; return value2; } return value2; } public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value) { IEqualityComparer<TKey> equalityComparer = keyComparer; int hashCode = equalityComparer?.GetHashCode(key) ?? key.GetHashCode(); return TryGetValue(key, equalityComparer, hashCode, out value); } private bool TryGetValue(TKey key, IEqualityComparer<TKey> keyComparer, int hashCode, [MaybeNullWhen(false)] out TValue value) { if (keyComparer == null) { for (KeyValuePair keyValuePair = Volatile.Read<KeyValuePair>(ref GetBucket(hashCode)); keyValuePair != null; keyValuePair = keyValuePair.Next) { if (hashCode == keyValuePair.KeyHashCode && (typeof(TKey).IsValueType ? EqualityComparer<TKey>.Default.Equals(key, keyValuePair.Key) : keyValuePair.Key.Equals(key))) { EnqueueAndDrain(readCommand, keyValuePair); value = GetValue(keyValuePair); return true; } } } else { for (KeyValuePair keyValuePair = Volatile.Read<KeyValuePair>(ref GetBucket(hashCode)); keyValuePair != null; keyValuePair = keyValuePair.Next) { if (hashCode == keyValuePair.KeyHashCode && keyComparer.Equals(key, keyValuePair.Key)) { EnqueueAndDrain(readCommand, keyValuePair); value = GetValue(keyValuePair); return true; } } } value = default(TValue); return false; } public bool TryRemove(TKey key, [MaybeNullWhen(false)] out TValue value) { Unsafe.SkipInit<TValue>(out value); bool num = TryRemove(key, false, ref value); if (!num) value = default(TValue); return num; } public bool TryRemove([System.Runtime.CompilerServices.Nullable(new byte[] { 0, 1, 1 })] KeyValuePair<TKey, TValue> pair) { KeyValuePair<TKey, TValue> keyValuePair = pair; keyValuePair.Deconstruct(out TKey key, out TValue value); TKey key2 = key; TValue value2 = value; return TryRemove(key2, true, ref value2); } private bool TryRemove(TKey key, bool matchValue, ref TValue value) { IEqualityComparer<TKey> equalityComparer = keyComparer; int num = equalityComparer?.GetHashCode(key) ?? key.GetHashCode(); object bucketLock; ref KeyValuePair bucket = ref GetBucket(num, out bucketLock); KeyValuePair target = default(KeyValuePair); lock (bucketLock) { if (equalityComparer == null) { KeyValuePair keyValuePair = Volatile.Read<KeyValuePair>(ref bucket); KeyValuePair keyValuePair2 = null; while (keyValuePair != null) { if (num != keyValuePair.KeyHashCode || !(typeof(TKey).IsValueType ? EqualityComparer<TKey>.Default.Equals(key, keyValuePair.Key) : keyValuePair.Key.Equals(key)) || (matchValue && !EqualityComparer<TValue>.Default.Equals(value, GetValue(keyValuePair)))) { keyValuePair2 = keyValuePair; keyValuePair = keyValuePair.Next; continue; } target = keyValuePair; if (keyValuePair2 == null) Volatile.Write<KeyValuePair>(ref bucket, keyValuePair.Next); else keyValuePair2.Next = keyValuePair.Next; OnRemoved(); value = GetValue(keyValuePair); goto end_IL_0031; } } else { KeyValuePair keyValuePair3 = Volatile.Read<KeyValuePair>(ref bucket); KeyValuePair keyValuePair4 = null; while (keyValuePair3 != null) { if (num != keyValuePair3.KeyHashCode || !equalityComparer.Equals(key, keyValuePair3.Key) || (matchValue && !EqualityComparer<TValue>.Default.Equals(value, GetValue(keyValuePair3)))) { keyValuePair4 = keyValuePair3; keyValuePair3 = keyValuePair3.Next; continue; } target = keyValuePair3; if (keyValuePair4 == null) Volatile.Write<KeyValuePair>(ref bucket, keyValuePair3.Next); else keyValuePair4.Next = keyValuePair3.Next; OnRemoved(); value = GetValue(keyValuePair3); goto end_IL_0031; } } value = default(TValue); return false; end_IL_0031:; } EnqueueAndDrain(removeCommand, target); return true; } public bool TryUpdate(TKey key, TValue newValue, TValue expectedValue) { IEqualityComparer<TKey> equalityComparer = keyComparer; int num = equalityComparer?.GetHashCode(key) ?? key.GetHashCode(); object bucketLock; ref KeyValuePair bucket = ref GetBucket(num, out bucketLock); KeyValuePair target = default(KeyValuePair); lock (bucketLock) { if (equalityComparer == null) { KeyValuePair keyValuePair = Volatile.Read<KeyValuePair>(ref bucket); while (keyValuePair != null) { if (num != keyValuePair.KeyHashCode || !(typeof(TKey).IsValueType ? EqualityComparer<TKey>.Default.Equals(key, keyValuePair.Key) : keyValuePair.Key.Equals(key)) || !EqualityComparer<TValue>.Default.Equals(expectedValue, GetValue(keyValuePair))) { keyValuePair = keyValuePair.Next; continue; } SetValue(target = keyValuePair, newValue); goto end_IL_0031; } } else { KeyValuePair keyValuePair2 = Volatile.Read<KeyValuePair>(ref bucket); while (keyValuePair2 != null) { if (num != keyValuePair2.KeyHashCode || !equalityComparer.Equals(key, keyValuePair2.Key) || !EqualityComparer<TValue>.Default.Equals(expectedValue, GetValue(keyValuePair2))) { keyValuePair2 = keyValuePair2.Next; continue; } SetValue(target = keyValuePair2, newValue); goto end_IL_0031; } } return false; end_IL_0031:; } EnqueueAndDrain(readCommand, target); return true; } private int AcquireAllLocks() { int i; for (i = 0; i < locks.Length; i++) { Monitor.Enter(locks[i]); } return i; } private void ReleaseLocks(int acquiredLocks) { for (int i = 0; i < acquiredLocks; i++) { Monitor.Exit(locks[i]); } } private void RemoveAllKeys() { Span<KeyValuePair> span = MemoryExtensions.AsSpan<KeyValuePair>(buckets); for (int i = 0; i < span.Length; i++) { ref KeyValuePair location = ref span[i]; for (KeyValuePair keyValuePair = Volatile.Read<KeyValuePair>(ref location); keyValuePair != null; keyValuePair = keyValuePair.Next) { keyValuePair.Clear(); } Volatile.Write<KeyValuePair>(ref location, (KeyValuePair)null); } count = 0; } [MethodImpl(MethodImplOptions.NoInlining)] private KeyValuePair OnAdd(KeyValuePair target) { AddFirst(target); evictionListSize++; if (evictionListSize <= buckets.Length) return null; return Evict(); } [MethodImpl(MethodImplOptions.NoInlining)] private KeyValuePair OnRemove(KeyValuePair target) { Detach(target); evictionListSize--; return null; } [MethodImpl(MethodImplOptions.NoInlining)] private KeyValuePair OnReadLFU(KeyValuePair target) { KeyValuePair item = target.Links.Previous; KeyValuePair keyValuePair = (item != null) ? item.Links.Previous : null; Detach(target); if (keyValuePair == null) AddFirst(target); else Append(keyValuePair, target); return null; } [MethodImpl(MethodImplOptions.NoInlining)] private KeyValuePair OnReadLRU(KeyValuePair target) { Detach(target); AddFirst(target); return null; } private static void Append(KeyValuePair parent, KeyValuePair child) { child.Links.Previous = parent; if ((child.Links.Next = parent.Links.Next) != null) child.Links.Next.Links.Previous = child; } private void AddFirst(KeyValuePair pair) { if (firstPair == null || lastPair == null) firstPair = (lastPair = pair); else { lastPair.Links.Previous = pair; pair.Links.Next = firstPair; firstPair = pair; } } private KeyValuePair Evict() { KeyValuePair keyValuePair = lastPair; Detach(keyValuePair); Remove(keyValuePair); keyValuePair.Next = null; evictionListSize--; return keyValuePair; } private void Detach(KeyValuePair pair) { if (firstPair == pair) firstPair = pair.Links.Next; if (lastPair == pair) lastPair = pair.Links.Previous; MakeLink(pair.Links.Previous, pair.Links.Next); } private static void MakeLink(KeyValuePair previous, KeyValuePair next) { if (previous != null) previous.Links.Next = next; if (next != null) next.Links.Previous = previous; } private static void OnEviction(KeyValuePair pair, Action<TKey, TValue> evictionHandler) { while (pair != null) { KeyValuePair next = pair.Next; pair.Clear(); evictionHandler(pair.Key, GetValue(pair)); pair = next; } } private void OnEviction(KeyValuePair pair) { if (pair != null && evictionHandler != null) { if (ExecuteEvictionAsynchronously) ThreadPool.QueueUserWorkItem<(KeyValuePair, Action<TKey, TValue>)>((Action<(KeyValuePair, Action<TKey, TValue>)>)delegate((KeyValuePair pair, Action<TKey, TValue> evictionHandler) args) { OnEviction(args.pair, args.evictionHandler); }, (pair, evictionHandler), true); else OnEviction(pair, evictionHandler); } } private Command RentCommand() { Command command = Volatile.Read<Command>(ref pooledCommand); Command command2; do { if (command == null) { command2 = new Command(); break; } command2 = command; } while ((command = Interlocked.CompareExchange<Command>(ref pooledCommand, command2.Next, command2)) != command2); command2.Next = null; return command2; } private void ReturnCommand(Command command) { command.Clear(); Command comparand = command.Next = Volatile.Read<Command>(ref pooledCommand); Interlocked.CompareExchange<Command>(ref pooledCommand, command, comparand); } private void EnqueueAndDrain(Func<KeyValuePair, KeyValuePair> invoker, KeyValuePair target) { Enqueue(invoker, target); if (TryEnterEvictionLock()) { KeyValuePair pair = default(KeyValuePair); try { pair = DrainQueue(); } finally { Monitor.Exit(evictionLock); } OnEviction(pair); } } private bool TryEnterEvictionLock() { if (!rateLimitReached) return Monitor.TryEnter(evictionLock); Monitor.Enter(evictionLock); return true; } private void Enqueue(Func<KeyValuePair, KeyValuePair> invoker, KeyValuePair target) { Command command = RentCommand(); command.Initialize(invoker, target); Interlocked.Exchange<Command>(ref commandQueueWritePosition, command).Next = command; } private KeyValuePair DrainQueue() { KeyValuePair head = null; KeyValuePair tail = null; bool flag = false; Command next = commandQueueReadPosition.Next; int num = 0; while (next != null) { if (num >= concurrencyLevel) { flag = true; break; } KeyValuePair keyValuePair = next.Invoke(); if (keyValuePair != null && evictionHandler != null) <DrainQueue>g__AddToEvictionList|82_0(keyValuePair, ref head, ref tail); ReturnCommand(commandQueueReadPosition); commandQueueReadPosition = next; next = next.Next; num++; } rateLimitReached = flag; return head; } static ConcurrentCache() { bool isValueWriteAtomic; switch (Type.GetTypeCode(typeof(TValue))) { case TypeCode.DBNull: case TypeCode.Boolean: case TypeCode.Char: case TypeCode.SByte: case TypeCode.Byte: case TypeCode.Int16: case TypeCode.UInt16: case TypeCode.Int32: case TypeCode.UInt32: case TypeCode.Single: case TypeCode.String: isValueWriteAtomic = true; break; case TypeCode.Int64: case TypeCode.UInt64: case TypeCode.Double: isValueWriteAtomic = (IntPtr.Size == 8); break; default: isValueWriteAtomic = (Unsafe.SizeOf<TValue>() == IntPtr.Size && RuntimeHelpers.IsReferenceOrContainsReferences<TValue>()); break; } IsValueWriteAtomic = isValueWriteAtomic; } } }