| | //#define USE_INTERLOCKED // Uncomment to use Interlocked.CompareExchange version
#nullable disable
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Threading;
public static class Volatile
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T ReadInterlocked<T>(ref T location) where T : class? =>
Interlocked.CompareExchange(ref location, location, location);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T ReadMemoryBarrier<T>(ref T location) where T : class?
{
// return Volatile.Read(ref location);
// Volatile.Read implementation
T obj = location;
Thread.MemoryBarrier();
return obj;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static T Read<T>(ref T location) where T : class? =>
#if USE_INTERLOCKED
ReadInterlocked(ref location); // Fails if called
#else
ReadMemoryBarrier(ref location);
#endif
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static void Write<T>(ref T location, T value)
where T : class?
{
Interlocked.Exchange(ref location, value);
}
}
class Program
{
public static void Main()
{
for (int i = 0; i < 5; i++)
{
TestGetOrAddOrUpdate(5, 5, 5, 25000, true);
}
Console.WriteLine("Works");
}
private static void TestGetOrAddOrUpdate(int cLevel, int initSize, int threads, int addsPerThread, bool isAdd)
{
var dict = new ConcurrentDictionary2<int, int>(cLevel, 1);
var count = threads;
using (var mre = new ManualResetEvent(false))
{
for (var i = 0; i < threads; i++)
{
var ii = i;
new Thread(
() =>
{
for (var j = 0; j < addsPerThread; j++)
{
if (isAdd)
{
dict.GetOrAdd(j, -j);
}
else
{
dict.AddOrUpdate(j, -j, (k, v) => -j);
}
}
if (Interlocked.Decrement(ref count) == 0)
{
mre.Set();
}
}).Start();
}
mre.WaitOne();
}
foreach (var pair in dict)
{
if (pair.Key != -pair.Value) throw new Exception("Fail");
}
var gotKeys = new List<int>();
foreach (var pair in dict)
{
gotKeys.Add(pair.Key);
}
gotKeys.Sort();
var expectKeys = new List<int>();
for (var i = 0; i < addsPerThread; i++)
{
expectKeys.Add(i);
}
if (expectKeys.Count != gotKeys.Count) throw new Exception("Fail");
// Finally, let's verify that the count is reported correctly.
if (addsPerThread != dict.Count) throw new Exception("Fail");
if (addsPerThread != dict.ToArray().Length) throw new Exception("Fail");
}
}
internal static partial class HashHelpers
{
/// <summary>Returns approximate reciprocal of the divisor: ceil(2**64 / divisor).</summary>
/// <remarks>This should only be used on 64-bit.</remarks>
public static ulong GetFastModMultiplier(uint divisor) =>
ulong.MaxValue / divisor + 1;
/// <summary>Performs a mod operation using the multiplier pre-computed with <see cref="GetFastModMultiplier"/>.</summary>
/// <remarks>This should only be used on 64-bit.</remarks>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static uint FastMod(uint value, uint divisor, ulong multiplier)
{
// We use modified Daniel Lemire's fastmod algorithm (https://github.com/dotnet/runtime/pull/406),
// which allows to avoid the long multiplication if the divisor is less than 2**31.
Debug.Assert(divisor <= int.MaxValue);
// This is equivalent of (uint)Math.BigMul(multiplier * value, divisor, out _). This version
// is faster than BigMul currently because we only need the high bits.
uint highbits = (uint)(((((multiplier * value) >> 32) + 1) * divisor) >> 32);
Debug.Assert(highbits == value % divisor);
return highbits;
}
}
/// <summary>Represents a thread-safe collection of keys and values.</summary>
/// <typeparam name="TKey">The type of the keys in the dictionary.</typeparam>
/// <typeparam name="TValue">The type of the values in the dictionary.</typeparam>
/// <remarks>
/// All public and protected members of <see cref="ConcurrentDictionary2{TKey,TValue}"/> are thread-safe and may be used
/// concurrently from multiple threads.
/// </remarks>
[DebuggerDisplay("Count = {" + nameof(Count) + "}")]
public class ConcurrentDictionary2<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary where TKey : notnull
{
/// <summary>Internal tables of the dictionary.</summary>
private volatile Tables _tables;
/// <summary>Key equality comparer.</summary>
private readonly IEqualityComparer<TKey>? _comparer;
/// <summary>Default comparer for TKey.</summary>
/// <remarks>
/// Used to avoid repeatedly accessing the shared default generic static, in particular for reference types where it's
/// currently not devirtualized: https://github.com/dotnet/runtime/issues/10050.
/// </remarks>
private readonly EqualityComparer<TKey> _defaultComparer;
/// <summary>Whether to dynamically increase the size of the striped lock.</summary>
private readonly bool _growLockArray;
/// <summary>The maximum number of elements per lock before a resize operation is triggered.</summary>
private int _budget;
/// <summary>The default capacity, i.e. the initial # of buckets.</summary>
/// <remarks>
/// When choosing this value, we are making a trade-off between the size of a very small dictionary,
/// and the number of resizes when constructing a large dictionary. Also, the capacity should not be
/// divisible by a small prime.
/// </remarks>
private const int DefaultCapacity = 31;
/// <summary>
/// The maximum size of the striped lock that will not be exceeded when locks are automatically
/// added as the dictionary grows.
/// </summary>
/// <remarks>
/// The user is allowed to exceed this limit by passing
/// a concurrency level larger than MaxLockNumber into the constructor.
/// </remarks>
private const int MaxLockNumber = 1024;
/// <summary>Whether TValue is a type that can be written atomically (i.e., with no danger of torn reads).</summary>
private static readonly bool s_isValueWriteAtomic = IsValueWriteAtomic();
/// <summary>Determines whether type TValue can be written atomically.</summary>
private static bool IsValueWriteAtomic()
{
// Section 12.6.6 of ECMA CLI explains which types can be read and written atomically without
// the risk of tearing. See https://www.ecma-international.org/publications/files/ECMA-ST/ECMA-335.pdf
if (!typeof(TValue).IsValueType ||
typeof(TValue) == typeof(IntPtr) ||
typeof(TValue) == typeof(UIntPtr))
{
return true;
}
switch (Type.GetTypeCode(typeof(TValue)))
{
case TypeCode.Boolean:
case TypeCode.Byte:
case TypeCode.Char:
case TypeCode.Int16:
case TypeCode.Int32:
case TypeCode.SByte:
case TypeCode.Single:
case TypeCode.UInt16:
case TypeCode.UInt32:
return true;
case TypeCode.Double:
case TypeCode.Int64:
case TypeCode.UInt64:
return IntPtr.Size == 8;
default:
return false;
}
}
/// <summary>
/// Initializes a new instance of the <see cref="ConcurrentDictionary2{TKey,TValue}"/>
/// class that is empty, has the default concurrency level, has the default initial capacity, and
/// uses the default comparer for the key type.
/// </summary>
public ConcurrentDictionary2() : this(DefaultConcurrencyLevel, DefaultCapacity, growLockArray: true, null) { }
/// <summary>
/// Initializes a new instance of the <see cref="ConcurrentDictionary2{TKey,TValue}"/>
/// class that is empty, has the specified concurrency level and capacity, and uses the default
/// comparer for the key type.
/// </summary>
/// <param name="concurrencyLevel">The estimated number of threads that will update the
/// <see cref="ConcurrentDictionary2{TKey,TValue}"/> concurrently.</param>
/// <param name="capacity">The initial number of elements that the <see cref="ConcurrentDictionary2{TKey,TValue}"/> can contain.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="concurrencyLevel"/> is less than 1.</exception>
/// <exception cref="ArgumentOutOfRangeException"> <paramref name="capacity"/> is less than 0.</exception>
public ConcurrentDictionary2(int concurrencyLevel, int capacity) : this(concurrencyLevel, capacity, growLockArray: false, null) { }
/// <summary>
/// Initializes a new instance of the <see cref="ConcurrentDictionary2{TKey,TValue}"/>
/// class that contains elements copied from the specified <see cref="IEnumerable{T}"/>, has the default concurrency
/// level, has the default initial capacity, and uses the default comparer for the key type.
/// </summary>
/// <param name="collection">The <see
/// cref="IEnumerable{T}"/> whose elements are copied to the new <see cref="ConcurrentDictionary2{TKey,TValue}"/>.</param>
/// <exception cref="ArgumentNullException"><paramref name="collection"/> is a null reference (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentException"><paramref name="collection"/> contains one or more duplicate keys.</exception>
public ConcurrentDictionary2(IEnumerable<KeyValuePair<TKey, TValue>> collection) : this(collection, null) { }
/// <summary>
/// Initializes a new instance of the <see cref="ConcurrentDictionary2{TKey,TValue}"/>
/// class that is empty, has the specified concurrency level and capacity, and uses the specified
/// <see cref="IEqualityComparer{TKey}"/>.
/// </summary>
/// <param name="comparer">The <see cref="IEqualityComparer{TKey}"/> implementation to use when comparing keys.</param>
public ConcurrentDictionary2(IEqualityComparer<TKey>? comparer) : this(DefaultConcurrencyLevel, DefaultCapacity, growLockArray: true, comparer) { }
/// <summary>
/// Initializes a new instance of the <see cref="ConcurrentDictionary2{TKey,TValue}"/>
/// class that contains elements copied from the specified <see cref="IEnumerable"/>, has the default concurrency
/// level, has the default initial capacity, and uses the specified <see cref="IEqualityComparer{TKey}"/>.
/// </summary>
/// <param name="collection">The <see cref="IEnumerable{T}"/> whose elements are copied to the new <see cref="ConcurrentDictionary2{TKey,TValue}"/>.</param>
/// <param name="comparer">The <see cref="IEqualityComparer{TKey}"/> implementation to use when comparing keys.</param>
/// <exception cref="ArgumentNullException"><paramref name="collection"/> is a null reference (Nothing in Visual Basic).</exception>
public ConcurrentDictionary2(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey>? comparer)
: this(comparer)
{
if (collection is null)
{
throw new ArgumentNullException(nameof(collection));
}
InitializeFromCollection(collection);
}
/// <summary>
/// Initializes a new instance of the <see cref="ConcurrentDictionary2{TKey,TValue}"/>
/// class that contains elements copied from the specified <see cref="IEnumerable"/>,
/// has the specified concurrency level, has the specified initial capacity, and uses the specified
/// <see cref="IEqualityComparer{TKey}"/>.
/// </summary>
/// <param name="concurrencyLevel">
/// The estimated number of threads that will update the <see cref="ConcurrentDictionary2{TKey,TValue}"/> concurrently.
/// </param>
/// <param name="collection">The <see cref="IEnumerable{T}"/> whose elements are copied to the new
/// <see cref="ConcurrentDictionary2{TKey,TValue}"/>.</param>
/// <param name="comparer">The <see cref="IEqualityComparer{TKey}"/> implementation to use when comparing keys.</param>
/// <exception cref="ArgumentNullException"><paramref name="collection"/> is a null reference (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="concurrencyLevel"/> is less than 1.</exception>
/// <exception cref="ArgumentException"><paramref name="collection"/> contains one or more duplicate keys.</exception>
public ConcurrentDictionary2(int concurrencyLevel, IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey>? comparer)
: this(concurrencyLevel, DefaultCapacity, growLockArray: false, comparer)
{
if (collection is null)
{
throw new ArgumentNullException(nameof(collection));
}
InitializeFromCollection(collection);
}
private void InitializeFromCollection(IEnumerable<KeyValuePair<TKey, TValue>> collection)
{
foreach (KeyValuePair<TKey, TValue> pair in collection)
{
if (pair.Key is null)
{
throw new ArgumentNullException(nameof(pair.Key));
}
if (!TryAddInternal(pair.Key, null, pair.Value, updateIfExists: false, acquireLock: false, out _))
{
throw new ArgumentException("SourceContainsDuplicateKeys");
}
}
if (_budget == 0)
{
Tables tables = _tables;
_budget = tables._buckets.Length / tables._locks.Length;
}
}
/// <summary>
/// Initializes a new instance of the <see cref="ConcurrentDictionary2{TKey,TValue}"/>
/// class that is empty, has the specified concurrency level, has the specified initial capacity, and
/// uses the specified <see cref="IEqualityComparer{TKey}"/>.
/// </summary>
/// <param name="concurrencyLevel">The estimated number of threads that will update the <see cref="ConcurrentDictionary2{TKey,TValue}"/> concurrently.</param>
/// <param name="capacity">The initial number of elements that the <see cref="ConcurrentDictionary2{TKey,TValue}"/> can contain.</param>
/// <param name="comparer">The <see cref="IEqualityComparer{TKey}"/> implementation to use when comparing keys.</param>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="concurrencyLevel"/> is less than 1. -or- <paramref name="capacity"/> is less than 0.</exception>
public ConcurrentDictionary2(int concurrencyLevel, int capacity, IEqualityComparer<TKey>? comparer)
: this(concurrencyLevel, capacity, growLockArray: false, comparer)
{
}
internal ConcurrentDictionary2(int concurrencyLevel, int capacity, bool growLockArray, IEqualityComparer<TKey>? comparer)
{
if (concurrencyLevel < 1)
{
throw new ArgumentOutOfRangeException(nameof(concurrencyLevel), "ConcurrencyLevelMustBePositive");
}
if (capacity < 0)
{
throw new ArgumentOutOfRangeException(nameof(capacity), "CapacityMustNotBeNegative");
}
// The capacity should be at least as large as the concurrency level. Otherwise, we would have locks that don't guard
// any buckets.
if (capacity < concurrencyLevel)
{
capacity = concurrencyLevel;
}
var locks = new object[concurrencyLevel];
locks[0] = locks; // reuse array as the first lock object just to avoid an additional allocation
for (int i = 1; i < locks.Length; i++)
{
locks[i] = new object();
}
var countPerLock = new int[locks.Length];
var buckets = new Node[capacity];
_tables = new Tables(buckets, locks, countPerLock);
_defaultComparer = EqualityComparer<TKey>.Default;
if (comparer != null &&
!ReferenceEquals(comparer, _defaultComparer) && // if this is the default comparer, take the optimized path
!ReferenceEquals(comparer, StringComparer.Ordinal)) // strings as keys are extremely common, so special-case StringComparer.Ordinal, which is the same as the default comparer
{
_comparer = comparer;
}
_growLockArray = growLockArray;
_budget = buckets.Length / locks.Length;
}
/// <summary>
/// Attempts to add the specified key and value to the <see cref="ConcurrentDictionary2{TKey, TValue}"/>.
/// </summary>
/// <param name="key">The key of the element to add.</param>
/// <param name="value">The value of the element to add. The value can be a null reference (Nothing
/// in Visual Basic) for reference types.</param>
/// <returns>
/// true if the key/value pair was added to the <see cref="ConcurrentDictionary2{TKey, TValue}"/> successfully; otherwise, false.
/// </returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is null reference (Nothing in Visual Basic).</exception>
/// <exception cref="OverflowException">The <see cref="ConcurrentDictionary2{TKey, TValue}"/> contains too many elements.</exception>
public bool TryAdd(TKey key, TValue value)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
return TryAddInternal(key, null, value, updateIfExists: false, acquireLock: true, out _);
}
/// <summary>
/// Determines whether the <see cref="ConcurrentDictionary2{TKey, TValue}"/> contains the specified key.
/// </summary>
/// <param name="key">The key to locate in the <see cref="ConcurrentDictionary2{TKey, TValue}"/>.</param>
/// <returns>true if the <see cref="ConcurrentDictionary2{TKey, TValue}"/> contains an element with the specified key; otherwise, false.</returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference (Nothing in Visual Basic).</exception>
public bool ContainsKey(TKey key)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
return TryGetValue(key, out _);
}
/// <summary>
/// Attempts to remove and return the value with the specified key from the <see cref="ConcurrentDictionary2{TKey, TValue}"/>.
/// </summary>
/// <param name="key">The key of the element to remove and return.</param>
/// <param name="value">
/// When this method returns, <paramref name="value"/> contains the object removed from the
/// <see cref="ConcurrentDictionary2{TKey,TValue}"/> or the default value of <typeparamref
/// name="TValue"/> if the operation failed.
/// </param>
/// <returns>true if an object was removed successfully; otherwise, false.</returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference (Nothing in Visual Basic).</exception>
public bool TryRemove(TKey key, out TValue value)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
return TryRemoveInternal(key, out value, matchValue: false, default);
}
/// <summary>Removes a key and value from the dictionary.</summary>
/// <param name="item">The <see cref="KeyValuePair{TKey,TValue}"/> representing the key and value to remove.</param>
/// <returns>
/// true if the key and value represented by <paramref name="item"/> are successfully
/// found and removed; otherwise, false.
/// </returns>
/// <remarks>
/// Both the specified key and value must match the entry in the dictionary for it to be removed.
/// The key is compared using the dictionary's comparer (or the default comparer for <typeparamref name="TKey"/>
/// if no comparer was provided to the dictionary when it was constructed). The value is compared using the
/// default comparer for <typeparamref name="TValue"/>.
/// </remarks>
/// <exception cref="ArgumentNullException">
/// The <see cref="KeyValuePair{TKey, TValue}.Key"/> property of <paramref name="item"/> is a null reference.
/// </exception>
public bool TryRemove(KeyValuePair<TKey, TValue> item)
{
if (item.Key is null)
{
throw new ArgumentNullException(nameof(item), "ItemKeyIsNull");
}
return TryRemoveInternal(item.Key, out _, matchValue: true, item.Value);
}
/// <summary>
/// Removes the specified key from the dictionary if it exists and returns its associated value.
/// If matchValue flag is set, the key will be removed only if is associated with a particular
/// value.
/// </summary>
/// <param name="key">The key to search for and remove if it exists.</param>
/// <param name="value">The variable into which the removed value, if found, is stored.</param>
/// <param name="matchValue">Whether removal of the key is conditional on its value.</param>
/// <param name="oldValue">The conditional value to compare against if <paramref name="matchValue"/> is true</param>
private bool TryRemoveInternal(TKey key, out TValue value, bool matchValue, TValue? oldValue)
{
IEqualityComparer<TKey>? comparer = _comparer;
int hashcode = comparer is null ? key.GetHashCode() : comparer.GetHashCode(key);
while (true)
{
Tables tables = _tables;
object[] locks = tables._locks;
ref Node? bucket = ref tables.GetBucketAndLock(hashcode, out uint lockNo);
lock (locks[lockNo])
{
// If the table just got resized, we may not be holding the right lock, and must retry.
// This should be a rare occurrence.
if (tables != _tables)
{
continue;
}
Node? prev = null;
for (Node? curr = bucket; curr != null; curr = curr._next)
{
Debug.Assert((prev is null && curr == bucket) || prev!._next == curr);
if (hashcode == curr._hashcode && (comparer is null ? _defaultComparer.Equals(curr._key, key) : comparer.Equals(curr._key, key)))
{
if (matchValue)
{
bool valuesMatch = EqualityComparer<TValue>.Default.Equals(oldValue!, curr._value);
if (!valuesMatch)
{
value = default;
return false;
}
}
if (prev is null)
{
Volatile.Write(ref bucket, curr._next);
}
else
{
prev._next = curr._next;
}
value = curr._value;
tables._countPerLock[lockNo]--;
return true;
}
prev = curr;
}
}
value = default;
return false;
}
}
/// <summary>
/// Attempts to get the value associated with the specified key from the <see cref="ConcurrentDictionary2{TKey,TValue}"/>.
/// </summary>
/// <param name="key">The key of the value to get.</param>
/// <param name="value">
/// When this method returns, <paramref name="value"/> contains the object from
/// the <see cref="ConcurrentDictionary2{TKey,TValue}"/> with the specified key or the default value of
/// <typeparamref name="TValue"/>, if the operation failed.
/// </param>
/// <returns>true if the key was found in the <see cref="ConcurrentDictionary2{TKey,TValue}"/>; otherwise, false.</returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference (Nothing in Visual Basic).</exception>
public bool TryGetValue(TKey key, out TValue value)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
// We must capture the volatile _tables field into a local variable: it is set to a new table on each table resize.
// The Volatile.Read on the array element then ensures that we have a copy of the reference to tables._buckets[bucketNo]:
// this protects us from reading fields ('_hashcode', '_key', '_value' and '_next') of different instances.
Tables tables = _tables;
IEqualityComparer<TKey>? comparer = _comparer;
if (comparer is null)
{
int hashcode = key.GetHashCode();
if (typeof(TKey).IsValueType)
{
for (Node? n = Volatile.Read(ref tables.GetBucket(hashcode)); n != null; n = n._next)
{
if (hashcode == n._hashcode && EqualityComparer<TKey>.Default.Equals(n._key, key))
{
value = n._value;
return true;
}
}
}
else
{
for (Node? n = Volatile.Read(ref tables.GetBucket(hashcode)); n != null; n = n._next)
{
if (hashcode == n._hashcode && _defaultComparer.Equals(n._key, key))
{
value = n._value;
return true;
}
}
}
}
else
{
int hashcode = comparer.GetHashCode(key);
for (Node? n = Volatile.Read(ref tables.GetBucket(hashcode)); n != null; n = n._next)
{
if (hashcode == n._hashcode && comparer.Equals(n._key, key))
{
value = n._value;
return true;
}
}
}
value = default;
return false;
}
private bool TryGetValueInternal(TKey key, int hashcode, out TValue value)
{
Debug.Assert((_comparer is null ? key.GetHashCode() : _comparer.GetHashCode(key)) == hashcode);
// We must capture the volatile _tables field into a local variable: it is set to a new table on each table resize.
// The Volatile.Read on the array element then ensures that we have a copy of the reference to tables._buckets[bucketNo]:
// this protects us from reading fields ('_hashcode', '_key', '_value' and '_next') of different instances.
Tables tables = _tables;
IEqualityComparer<TKey>? comparer = _comparer;
if (comparer is null)
{
if (typeof(TKey).IsValueType)
{
for (Node? n = Volatile.Read(ref tables.GetBucket(hashcode)); n != null; n = n._next)
{
if (hashcode == n._hashcode && EqualityComparer<TKey>.Default.Equals(n._key, key))
{
value = n._value;
return true;
}
}
}
else
{
for (Node? n = Volatile.Read(ref tables.GetBucket(hashcode)); n != null; n = n._next)
{
if (hashcode == n._hashcode && _defaultComparer.Equals(n._key, key))
{
value = n._value;
return true;
}
}
}
}
else
{
for (Node? n = Volatile.Read(ref tables.GetBucket(hashcode)); n != null; n = n._next)
{
if (hashcode == n._hashcode && comparer.Equals(n._key, key))
{
value = n._value;
return true;
}
}
}
value = default;
return false;
}
/// <summary>
/// Updates the value associated with <paramref name="key"/> to <paramref name="newValue"/> if the existing value is equal
/// to <paramref name="comparisonValue"/>.
/// </summary>
/// <param name="key">The key whose value is compared with <paramref name="comparisonValue"/> and
/// possibly replaced.</param>
/// <param name="newValue">The value that replaces the value of the element with <paramref
/// name="key"/> if the comparison results in equality.</param>
/// <param name="comparisonValue">The value that is compared to the value of the element with
/// <paramref name="key"/>.</param>
/// <returns>
/// true if the value with <paramref name="key"/> was equal to <paramref name="comparisonValue"/> and
/// replaced with <paramref name="newValue"/>; otherwise, false.
/// </returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference.</exception>
public bool TryUpdate(TKey key, TValue newValue, TValue comparisonValue)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
return TryUpdateInternal(key, null, newValue, comparisonValue);
}
/// <summary>
/// Updates the value associated with <paramref name="key"/> to <paramref name="newValue"/> if the existing value is equal
/// to <paramref name="comparisonValue"/>.
/// </summary>
/// <param name="key">The key whose value is compared with <paramref name="comparisonValue"/> and
/// possibly replaced.</param>
/// <param name="nullableHashcode">The hashcode computed for <paramref name="key"/>.</param>
/// <param name="newValue">The value that replaces the value of the element with <paramref
/// name="key"/> if the comparison results in equality.</param>
/// <param name="comparisonValue">The value that is compared to the value of the element with
/// <paramref name="key"/>.</param>
/// <returns>
/// true if the value with <paramref name="key"/> was equal to <paramref name="comparisonValue"/> and
/// replaced with <paramref name="newValue"/>; otherwise, false.
/// </returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference.</exception>
private bool TryUpdateInternal(TKey key, int? nullableHashcode, TValue newValue, TValue comparisonValue)
{
IEqualityComparer<TKey>? comparer = _comparer;
Debug.Assert(
nullableHashcode is null ||
(comparer is null ? key.GetHashCode() : comparer.GetHashCode(key)) == nullableHashcode);
int hashcode =
nullableHashcode ??
(comparer is null ? key.GetHashCode() : comparer.GetHashCode(key));
EqualityComparer<TValue> valueComparer = EqualityComparer<TValue>.Default;
while (true)
{
Tables tables = _tables;
object[] locks = tables._locks;
ref Node? bucket = ref tables.GetBucketAndLock(hashcode, out uint lockNo);
lock (locks[lockNo])
{
// If the table just got resized, we may not be holding the right lock, and must retry.
// This should be a rare occurrence.
if (tables != _tables)
{
continue;
}
// Try to find this key in the bucket
Node? prev = null;
for (Node? node = bucket; node != null; node = node._next)
{
Debug.Assert((prev is null && node == bucket) || prev!._next == node);
if (hashcode == node._hashcode && (comparer is null ? _defaultComparer.Equals(node._key, key) : comparer.Equals(node._key, key)))
{
if (valueComparer.Equals(node._value, comparisonValue))
{
if (s_isValueWriteAtomic)
{
node._value = newValue;
}
else
{
var newNode = new Node(node._key, newValue, hashcode, node._next);
if (prev is null)
{
Volatile.Write(ref bucket, newNode);
}
else
{
prev._next = newNode;
}
}
return true;
}
return false;
}
prev = node;
}
// didn't find the key
return false;
}
}
}
/// <summary>
/// Removes all keys and values from the <see cref="ConcurrentDictionary2{TKey,TValue}"/>.
/// </summary>
public void Clear()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
// If the dictionary is already empty, then there's nothing to clear.
if (AreAllBucketsEmpty())
{
return;
}
Tables tables = _tables;
var newTables = new Tables(new Node[DefaultCapacity], tables._locks, new int[tables._countPerLock.Length]);
_tables = newTables;
_budget = Math.Max(1, newTables._buckets.Length / newTables._locks.Length);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
/// <summary>
/// Copies the elements of the <see cref="ICollection{T}"/> to an array of type <see cref="KeyValuePair{TKey,TValue}"/>,
/// starting at the specified array index.
/// </summary>
/// <param name="array">
/// The one-dimensional array of type <see cref="KeyValuePair{TKey,TValue}"/> that is the destination of the <see
/// cref="KeyValuePair{TKey,TValue}"/> elements copied from the <see cref="ICollection"/>. The array must have zero-based indexing.
/// </param>
/// <param name="index">The zero-based index in <paramref name="array"/> at which copying begins.</param>
/// <exception cref="ArgumentNullException"><paramref name="array"/> is a null reference (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is less than 0.</exception>
/// <exception cref="ArgumentException">
/// <paramref name="index"/> is equal to or greater than the length of the <paramref name="array"/>. -or- The number of
/// elements in the source <see cref="ICollection"/> is greater than the available space from <paramref name="index"/> to
/// the end of the destination <paramref name="array"/>.
/// </exception>
void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int index)
{
if (array is null)
{
throw new ArgumentNullException(nameof(array));
}
if (index < 0)
{
throw new ArgumentOutOfRangeException(nameof(index), "IndexIsNegative");
}
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
int count = 0;
int[] countPerLock = _tables._countPerLock;
for (int i = 0; i < countPerLock.Length && count >= 0; i++)
{
count += countPerLock[i];
}
if (array.Length - count < index || count < 0) //"count" itself or "count + index" can overflow
{
throw new ArgumentException("ArrayNotLargeEnough");
}
CopyToPairs(array, index);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
/// <summary>
/// Copies the key and value pairs stored in the <see cref="ConcurrentDictionary2{TKey,TValue}"/> to a
/// new array.
/// </summary>
/// <returns>A new array containing a snapshot of key and value pairs copied from the <see cref="ConcurrentDictionary2{TKey,TValue}"/>.
/// </returns>
public KeyValuePair<TKey, TValue>[] ToArray()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
int count = 0;
int[] countPerLock = _tables._countPerLock;
for (int i = 0; i < countPerLock.Length; i++)
{
checked
{
count += countPerLock[i];
}
}
if (count == 0)
{
return new KeyValuePair<TKey, TValue>[0];
}
var array = new KeyValuePair<TKey, TValue>[count];
CopyToPairs(array, 0);
return array;
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
/// <summary>Copy dictionary contents to an array - shared implementation between ToArray and CopyTo.</summary>
/// <remarks>Important: the caller must hold all locks in _locks before calling CopyToPairs.</remarks>
private void CopyToPairs(KeyValuePair<TKey, TValue>[] array, int index)
{
Node?[] buckets = _tables._buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node? current = buckets[i]; current != null; current = current._next)
{
array[index] = new KeyValuePair<TKey, TValue>(current._key, current._value);
index++; // this should never overflow, CopyToPairs is only called when there's no overflow risk
}
}
}
/// <summary>Copy dictionary contents to an array - shared implementation between ToArray and CopyTo.</summary>
/// <remarks>Important: the caller must hold all locks in _locks before calling CopyToPairs.</remarks>
private void CopyToEntries(DictionaryEntry[] array, int index)
{
Node?[] buckets = _tables._buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node? current = buckets[i]; current != null; current = current._next)
{
array[index] = new DictionaryEntry(current._key, current._value);
index++; //this should never flow, CopyToEntries is only called when there's no overflow risk
}
}
}
/// <summary>Copy dictionary contents to an array - shared implementation between ToArray and CopyTo.</summary>
/// <remarks>Important: the caller must hold all locks in _locks before calling CopyToPairs.</remarks>
private void CopyToObjects(object[] array, int index)
{
Node?[] buckets = _tables._buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node? current = buckets[i]; current != null; current = current._next)
{
array[index] = new KeyValuePair<TKey, TValue>(current._key, current._value);
index++; // this should never overflow, CopyToObjects is only called when there's no overflow risk
}
}
}
/// <summary>Returns an enumerator that iterates through the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>.</summary>
/// <returns>An enumerator for the <see cref="ConcurrentDictionary2{TKey,TValue}"/>.</returns>
/// <remarks>
/// The enumerator returned from the dictionary is safe to use concurrently with
/// reads and writes to the dictionary, however it does not represent a moment-in-time snapshot
/// of the dictionary. The contents exposed through the enumerator may contain modifications
/// made to the dictionary after <see cref="GetEnumerator"/> was called.
/// </remarks>
public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() => new Enumerator(this);
/// <summary>Provides an enumerator implementation for the dictionary.</summary>
private sealed class Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>
{
// Provides a manually-implemented version of (approximately) this iterator:
// Node?[] buckets = _tables._buckets;
// for (int i = 0; i < buckets.Length; i++)
// for (Node? current = Volatile.Read(ref buckets[i]); current != null; current = current._next)
// yield return new KeyValuePair<TKey, TValue>(current._key, current._value);
private readonly ConcurrentDictionary2<TKey, TValue> _dictionary;
private ConcurrentDictionary2<TKey, TValue>.Node?[]? _buckets;
private Node? _node;
private int _i;
private int _state;
private const int StateUninitialized = 0;
private const int StateOuterloop = 1;
private const int StateInnerLoop = 2;
private const int StateDone = 3;
public Enumerator(ConcurrentDictionary2<TKey, TValue> dictionary)
{
_dictionary = dictionary;
_i = -1;
}
public KeyValuePair<TKey, TValue> Current { get; private set; }
object IEnumerator.Current => Current;
public void Reset()
{
_buckets = null;
_node = null;
Current = default;
_i = -1;
_state = StateUninitialized;
}
public void Dispose() { }
public bool MoveNext()
{
switch (_state)
{
case StateUninitialized:
_buckets = _dictionary._tables._buckets;
_i = -1;
goto case StateOuterloop;
case StateOuterloop:
ConcurrentDictionary2<TKey, TValue>.Node?[]? buckets = _buckets;
Debug.Assert(buckets != null);
int i = ++_i;
if ((uint)i < (uint)buckets!.Length)
{
// The Volatile.Read ensures that we have a copy of the reference to buckets[i]:
// this protects us from reading fields ('_key', '_value' and '_next') of different instances.
_node = Volatile.Read(ref buckets[i]);
_state = StateInnerLoop;
goto case StateInnerLoop;
}
goto default;
case StateInnerLoop:
Node? node = _node;
if (node != null)
{
Current = new KeyValuePair<TKey, TValue>(node._key, node._value);
_node = node._next;
return true;
}
goto case StateOuterloop;
default:
_state = StateDone;
return false;
}
}
}
/// <summary>
/// Shared internal implementation for inserts and updates.
/// If key exists, we always return false; and if updateIfExists == true we force update with value;
/// If key doesn't exist, we always add value and return true;
/// </summary>
private bool TryAddInternal(TKey key, int? nullableHashcode, TValue value, bool updateIfExists, bool acquireLock, out TValue resultingValue)
{
IEqualityComparer<TKey>? comparer = _comparer;
Debug.Assert(
nullableHashcode is null ||
(comparer is null && key.GetHashCode() == nullableHashcode) ||
(comparer != null && comparer.GetHashCode(key) == nullableHashcode));
int hashcode =
nullableHashcode ??
(comparer is null ? key.GetHashCode() : comparer.GetHashCode(key));
while (true)
{
Tables tables = _tables;
object[] locks = tables._locks;
ref Node? bucket = ref tables.GetBucketAndLock(hashcode, out uint lockNo);
bool resizeDesired = false;
bool lockTaken = false;
try
{
if (acquireLock)
{
Monitor.Enter(locks[lockNo], ref lockTaken);
}
// If the table just got resized, we may not be holding the right lock, and must retry.
// This should be a rare occurrence.
if (tables != _tables)
{
continue;
}
// Try to find this key in the bucket
Node? prev = null;
for (Node? node = bucket; node != null; node = node._next)
{
Debug.Assert((prev is null && node == bucket) || prev!._next == node);
if (hashcode == node._hashcode && (comparer is null ? _defaultComparer.Equals(node._key, key) : comparer.Equals(node._key, key)))
{
// The key was found in the dictionary. If updates are allowed, update the value for that key.
// We need to create a new node for the update, in order to support TValue types that cannot
// be written atomically, since lock-free reads may be happening concurrently.
if (updateIfExists)
{
if (s_isValueWriteAtomic)
{
node._value = value;
}
else
{
var newNode = new Node(node._key, value, hashcode, node._next);
if (prev is null)
{
Volatile.Write(ref bucket, newNode);
}
else
{
prev._next = newNode;
}
}
resultingValue = value;
}
else
{
resultingValue = node._value;
}
return false;
}
prev = node;
}
// The key was not found in the bucket. Insert the key-value pair.
var resultNode = new Node(key, value, hashcode, bucket);
Volatile.Write(ref bucket, resultNode);
checked
{
tables._countPerLock[lockNo]++;
}
//
// If the number of elements guarded by this lock has exceeded the budget, resize the bucket table.
// It is also possible that GrowTable will increase the budget but won't resize the bucket table.
// That happens if the bucket table is found to be poorly utilized due to a bad hash function.
//
if (tables._countPerLock[lockNo] > _budget)
{
resizeDesired = true;
}
}
finally
{
if (lockTaken)
{
Monitor.Exit(locks[lockNo]);
}
}
//
// The fact that we got here means that we just performed an insertion. If necessary, we will grow the table.
//
// Concurrency notes:
// - Notice that we are not holding any locks at when calling GrowTable. This is necessary to prevent deadlocks.
// - As a result, it is possible that GrowTable will be called unnecessarily. But, GrowTable will obtain lock 0
// and then verify that the table we passed to it as the argument is still the current table.
//
if (resizeDesired)
{
GrowTable(tables);
}
resultingValue = value;
return true;
}
}
/// <summary>Gets or sets the value associated with the specified key.</summary>
/// <param name="key">The key of the value to get or set.</param>
/// <value>
/// The value associated with the specified key. If the specified key is not found, a get operation throws a
/// <see cref="KeyNotFoundException"/>, and a set operation creates a new element with the specified key.
/// </value>
/// <exception cref="ArgumentNullException">
/// <paramref name="key"/> is a null reference (Nothing in Visual Basic).
/// </exception>
/// <exception cref="KeyNotFoundException">
/// The property is retrieved and <paramref name="key"/> does not exist in the collection.
/// </exception>
public TValue this[TKey key]
{
get
{
if (!TryGetValue(key, out TValue? value))
{
ThrowKeyNotFoundException(key);
}
return value;
}
set
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
TryAddInternal(key, null, value, updateIfExists: true, acquireLock: true, out _);
}
}
/// <summary>Throws a KeyNotFoundException.</summary>
/// <remarks>Separate from ThrowHelper to avoid boxing at call site while reusing this generic instantiation.</remarks>
private static void ThrowKeyNotFoundException(TKey key) => throw new KeyNotFoundException(key.ToString());
/// <summary>
/// Gets the number of key/value pairs contained in the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>.
/// </summary>
/// <exception cref="OverflowException">The dictionary contains too many
/// elements.</exception>
/// <value>The number of key/value pairs contained in the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>.</value>
/// <remarks>Count has snapshot semantics and represents the number of items in the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>
/// at the moment when Count was accessed.</remarks>
public int Count
{
get
{
int acquiredLocks = 0;
try
{
// Acquire all locks
AcquireAllLocks(ref acquiredLocks);
return GetCountInternal();
}
finally
{
// Release locks that have been acquired earlier
ReleaseLocks(0, acquiredLocks);
}
}
}
/// <summary>
/// Gets the number of key/value pairs contained in the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>. Should only be used after all locks
/// have been acquired.
/// </summary>
/// <exception cref="OverflowException">The dictionary contains too many
/// elements.</exception>
/// <value>The number of key/value pairs contained in the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>.</value>
/// <remarks>Count has snapshot semantics and represents the number of items in the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>
/// at the moment when Count was accessed.</remarks>
private int GetCountInternal()
{
int count = 0;
int[] countPerLocks = _tables._countPerLock;
// Compute the count, we allow overflow
for (int i = 0; i < countPerLocks.Length; i++)
{
count += countPerLocks[i];
}
return count;
}
/// <summary>
/// Adds a key/value pair to the <see cref="ConcurrentDictionary2{TKey,TValue}"/>
/// if the key does not already exist.
/// </summary>
/// <param name="key">The key of the element to add.</param>
/// <param name="valueFactory">The function used to generate a value for the key</param>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentNullException"><paramref name="valueFactory"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="OverflowException">The dictionary contains too many
/// elements.</exception>
/// <returns>The value for the key. This will be either the existing value for the key if the
/// key is already in the dictionary, or the new value for the key as returned by valueFactory
/// if the key was not in the dictionary.</returns>
public TValue GetOrAdd(TKey key, Func<TKey, TValue> valueFactory)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
if (valueFactory is null)
{
throw new ArgumentNullException(nameof(valueFactory));
}
IEqualityComparer<TKey>? comparer = _comparer;
int hashcode = comparer is null ? key.GetHashCode() : comparer.GetHashCode(key);
if (!TryGetValueInternal(key, hashcode, out TValue? resultingValue))
{
TryAddInternal(key, hashcode, valueFactory(key), updateIfExists: false, acquireLock: true, out resultingValue);
}
return resultingValue;
}
/// <summary>
/// Adds a key/value pair to the <see cref="ConcurrentDictionary2{TKey,TValue}"/>
/// if the key does not already exist.
/// </summary>
/// <param name="key">The key of the element to add.</param>
/// <param name="valueFactory">The function used to generate a value for the key</param>
/// <param name="factoryArgument">An argument value to pass into <paramref name="valueFactory"/>.</param>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentNullException"><paramref name="valueFactory"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="OverflowException">The dictionary contains too many
/// elements.</exception>
/// <returns>The value for the key. This will be either the existing value for the key if the
/// key is already in the dictionary, or the new value for the key as returned by valueFactory
/// if the key was not in the dictionary.</returns>
public TValue GetOrAdd<TArg>(TKey key, Func<TKey, TArg, TValue> valueFactory, TArg factoryArgument)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
if (valueFactory is null)
{
throw new ArgumentNullException(nameof(valueFactory));
}
IEqualityComparer<TKey>? comparer = _comparer;
int hashcode = comparer is null ? key.GetHashCode() : comparer.GetHashCode(key);
if (!TryGetValueInternal(key, hashcode, out TValue? resultingValue))
{
TryAddInternal(key, hashcode, valueFactory(key, factoryArgument), updateIfExists: false, acquireLock: true, out resultingValue);
}
return resultingValue;
}
/// <summary>
/// Adds a key/value pair to the <see cref="ConcurrentDictionary2{TKey,TValue}"/>
/// if the key does not already exist.
/// </summary>
/// <param name="key">The key of the element to add.</param>
/// <param name="value">the value to be added, if the key does not already exist</param>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="OverflowException">The dictionary contains too many
/// elements.</exception>
/// <returns>The value for the key. This will be either the existing value for the key if the
/// key is already in the dictionary, or the new value if the key was not in the dictionary.</returns>
public TValue GetOrAdd(TKey key, TValue value)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
IEqualityComparer<TKey>? comparer = _comparer;
int hashcode = comparer is null ? key.GetHashCode() : comparer.GetHashCode(key);
if (!TryGetValueInternal(key, hashcode, out TValue? resultingValue))
{
TryAddInternal(key, hashcode, value, updateIfExists: false, acquireLock: true, out resultingValue);
}
return resultingValue;
}
/// <summary>
/// Adds a key/value pair to the <see cref="ConcurrentDictionary2{TKey,TValue}"/> if the key does not already
/// exist, or updates a key/value pair in the <see cref="ConcurrentDictionary2{TKey,TValue}"/> if the key
/// already exists.
/// </summary>
/// <param name="key">The key to be added or whose value should be updated</param>
/// <param name="addValueFactory">The function used to generate a value for an absent key</param>
/// <param name="updateValueFactory">The function used to generate a new value for an existing key
/// based on the key's existing value</param>
/// <param name="factoryArgument">An argument to pass into <paramref name="addValueFactory"/> and <paramref name="updateValueFactory"/>.</param>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentNullException"><paramref name="addValueFactory"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentNullException"><paramref name="updateValueFactory"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="OverflowException">The dictionary contains too many
/// elements.</exception>
/// <returns>The new value for the key. This will be either be the result of addValueFactory (if the key was
/// absent) or the result of updateValueFactory (if the key was present).</returns>
public TValue AddOrUpdate<TArg>(
TKey key, Func<TKey, TArg, TValue> addValueFactory, Func<TKey, TValue, TArg, TValue> updateValueFactory, TArg factoryArgument)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
if (addValueFactory is null)
{
throw new ArgumentNullException(nameof(addValueFactory));
}
if (updateValueFactory is null)
{
throw new ArgumentNullException(nameof(updateValueFactory));
}
IEqualityComparer<TKey>? comparer = _comparer;
int hashcode = comparer is null ? key.GetHashCode() : comparer.GetHashCode(key);
while (true)
{
if (TryGetValueInternal(key, hashcode, out TValue? oldValue))
{
// key exists, try to update
TValue newValue = updateValueFactory(key, oldValue, factoryArgument);
if (TryUpdateInternal(key, hashcode, newValue, oldValue))
{
return newValue;
}
}
else
{
// key doesn't exist, try to add
if (TryAddInternal(key, hashcode, addValueFactory(key, factoryArgument), updateIfExists: false, acquireLock: true, out TValue resultingValue))
{
return resultingValue;
}
}
}
}
/// <summary>
/// Adds a key/value pair to the <see cref="ConcurrentDictionary2{TKey,TValue}"/> if the key does not already
/// exist, or updates a key/value pair in the <see cref="ConcurrentDictionary2{TKey,TValue}"/> if the key
/// already exists.
/// </summary>
/// <param name="key">The key to be added or whose value should be updated</param>
/// <param name="addValueFactory">The function used to generate a value for an absent key</param>
/// <param name="updateValueFactory">The function used to generate a new value for an existing key
/// based on the key's existing value</param>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentNullException"><paramref name="addValueFactory"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentNullException"><paramref name="updateValueFactory"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="OverflowException">The dictionary contains too many
/// elements.</exception>
/// <returns>The new value for the key. This will be either the result of addValueFactory (if the key was
/// absent) or the result of updateValueFactory (if the key was present).</returns>
public TValue AddOrUpdate(TKey key, Func<TKey, TValue> addValueFactory, Func<TKey, TValue, TValue> updateValueFactory)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
if (addValueFactory is null)
{
throw new ArgumentNullException(nameof(addValueFactory));
}
if (updateValueFactory is null)
{
throw new ArgumentNullException(nameof(updateValueFactory));
}
IEqualityComparer<TKey>? comparer = _comparer;
int hashcode = comparer is null ? key.GetHashCode() : comparer.GetHashCode(key);
while (true)
{
if (TryGetValueInternal(key, hashcode, out TValue? oldValue))
{
// key exists, try to update
TValue newValue = updateValueFactory(key, oldValue);
if (TryUpdateInternal(key, hashcode, newValue, oldValue))
{
return newValue;
}
}
else
{
// key doesn't exist, try to add
if (TryAddInternal(key, hashcode, addValueFactory(key), updateIfExists: false, acquireLock: true, out TValue resultingValue))
{
return resultingValue;
}
}
}
}
/// <summary>
/// Adds a key/value pair to the <see cref="ConcurrentDictionary2{TKey,TValue}"/> if the key does not already
/// exist, or updates a key/value pair in the <see cref="ConcurrentDictionary2{TKey,TValue}"/> if the key
/// already exists.
/// </summary>
/// <param name="key">The key to be added or whose value should be updated</param>
/// <param name="addValue">The value to be added for an absent key</param>
/// <param name="updateValueFactory">The function used to generate a new value for an existing key based on
/// the key's existing value</param>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentNullException"><paramref name="updateValueFactory"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="OverflowException">The dictionary contains too many
/// elements.</exception>
/// <returns>The new value for the key. This will be either the value of addValue (if the key was
/// absent) or the result of updateValueFactory (if the key was present).</returns>
public TValue AddOrUpdate(TKey key, TValue addValue, Func<TKey, TValue, TValue> updateValueFactory)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
if (updateValueFactory is null)
{
throw new ArgumentNullException(nameof(updateValueFactory));
}
IEqualityComparer<TKey>? comparer = _comparer;
int hashcode = comparer is null ? key.GetHashCode() : comparer.GetHashCode(key);
while (true)
{
if (TryGetValueInternal(key, hashcode, out TValue? oldValue))
{
// key exists, try to update
TValue newValue = updateValueFactory(key, oldValue);
if (TryUpdateInternal(key, hashcode, newValue, oldValue))
{
return newValue;
}
}
else
{
// key doesn't exist, try to add
if (TryAddInternal(key, hashcode, addValue, updateIfExists: false, acquireLock: true, out TValue resultingValue))
{
return resultingValue;
}
}
}
}
/// <summary>
/// Gets a value that indicates whether the <see cref="ConcurrentDictionary2{TKey,TValue}"/> is empty.
/// </summary>
/// <value>true if the <see cref="ConcurrentDictionary2{TKey,TValue}"/> is empty; otherwise,
/// false.</value>
public bool IsEmpty
{
get
{
// Check if any buckets are non-empty, without acquiring any locks.
// This fast path should generally suffice as collections are usually not empty.
if (!AreAllBucketsEmpty())
{
return false;
}
// We didn't see any buckets containing items, however we can't be sure
// the collection was actually empty at any point in time as items may have been
// added and removed while iterating over the buckets such that we never saw an
// empty bucket, but there was always an item present in at least one bucket.
int acquiredLocks = 0;
try
{
// Acquire all locks
AcquireAllLocks(ref acquiredLocks);
return AreAllBucketsEmpty();
}
finally
{
// Release locks that have been acquired earlier
ReleaseLocks(0, acquiredLocks);
}
}
}
#region IDictionary<TKey,TValue> members
/// <summary>
/// Adds the specified key and value to the <see
/// cref="IDictionary{TKey,TValue}"/>.
/// </summary>
/// <param name="key">The object to use as the key of the element to add.</param>
/// <param name="value">The object to use as the value of the element to add.</param>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="OverflowException">The dictionary contains too many
/// elements.</exception>
/// <exception cref="ArgumentException">
/// An element with the same key already exists in the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>.</exception>
void IDictionary<TKey, TValue>.Add(TKey key, TValue value)
{
if (!TryAdd(key, value))
{
throw new ArgumentException("KeyAlreadyExisted");
}
}
/// <summary>
/// Removes the element with the specified key from the <see
/// cref="IDictionary{TKey,TValue}"/>.
/// </summary>
/// <param name="key">The key of the element to remove.</param>
/// <returns>true if the element is successfully remove; otherwise false. This method also returns
/// false if
/// <paramref name="key"/> was not found in the original <see
/// cref="IDictionary{TKey,TValue}"/>.
/// </returns>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
bool IDictionary<TKey, TValue>.Remove(TKey key) => TryRemove(key, out _);
/// <summary>
/// Gets a collection containing the keys in the <see
/// cref="Dictionary{TKey,TValue}"/>.
/// </summary>
/// <value>An <see cref="ICollection{TKey}"/> containing the keys in the
/// <see cref="Dictionary{TKey,TValue}"/>.</value>
public ICollection<TKey> Keys => GetKeys();
/// <summary>
/// Gets an <see cref="IEnumerable{TKey}"/> containing the keys of
/// the <see cref="IReadOnlyDictionary{TKey,TValue}"/>.
/// </summary>
/// <value>An <see cref="IEnumerable{TKey}"/> containing the keys of
/// the <see cref="IReadOnlyDictionary{TKey,TValue}"/>.</value>
//IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys => GetKeys();
/// <summary>
/// Gets a collection containing the values in the <see
/// cref="Dictionary{TKey,TValue}"/>.
/// </summary>
/// <value>An <see cref="ICollection{TValue}"/> containing the values in
/// the
/// <see cref="Dictionary{TKey,TValue}"/>.</value>
public ICollection<TValue> Values => GetValues();
/// <summary>
/// Gets an <see cref="IEnumerable{TValue}"/> containing the values
/// in the <see cref="IReadOnlyDictionary{TKey,TValue}"/>.
/// </summary>
/// <value>An <see cref="IEnumerable{TValue}"/> containing the
/// values in the <see cref="IReadOnlyDictionary{TKey,TValue}"/>.</value>
//IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values => GetValues();
#endregion
#region ICollection<KeyValuePair<TKey,TValue>> Members
/// <summary>
/// Adds the specified value to the <see cref="ICollection{TValue}"/>
/// with the specified key.
/// </summary>
/// <param name="keyValuePair">The <see cref="KeyValuePair{TKey,TValue}"/>
/// structure representing the key and value to add to the <see
/// cref="Dictionary{TKey,TValue}"/>.</param>
/// <exception cref="ArgumentNullException">The <paramref name="keyValuePair"/> of <paramref
/// name="keyValuePair"/> is null.</exception>
/// <exception cref="OverflowException">The <see
/// cref="Dictionary{TKey,TValue}"/>
/// contains too many elements.</exception>
/// <exception cref="ArgumentException">An element with the same key already exists in the
/// <see cref="Dictionary{TKey,TValue}"/></exception>
void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair) => ((IDictionary<TKey, TValue>)this).Add(keyValuePair.Key, keyValuePair.Value);
/// <summary>
/// Determines whether the <see cref="ICollection{T}"/>
/// contains a specific key and value.
/// </summary>
/// <param name="keyValuePair">The <see cref="KeyValuePair{TKey,TValue}"/>
/// structure to locate in the <see
/// cref="ICollection{TValue}"/>.</param>
/// <returns>true if the <paramref name="keyValuePair"/> is found in the <see
/// cref="ICollection{T}"/>; otherwise, false.</returns>
bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair)
{
if (!TryGetValue(keyValuePair.Key, out TValue? value))
{
return false;
}
return EqualityComparer<TValue>.Default.Equals(value, keyValuePair.Value);
}
/// <summary>
/// Gets a value indicating whether the dictionary is read-only.
/// </summary>
/// <value>true if the <see cref="ICollection{T}"/> is
/// read-only; otherwise, false. For <see
/// cref="Dictionary{TKey,TValue}"/>, this property always returns
/// false.</value>
bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly => false;
/// <summary>
/// Removes a key and value from the dictionary.
/// </summary>
/// <param name="keyValuePair">The <see
/// cref="KeyValuePair{TKey,TValue}"/>
/// structure representing the key and value to remove from the <see
/// cref="Dictionary{TKey,TValue}"/>.</param>
/// <returns>true if the key and value represented by <paramref name="keyValuePair"/> is successfully
/// found and removed; otherwise, false.</returns>
/// <exception cref="ArgumentNullException">The Key property of <paramref
/// name="keyValuePair"/> is a null reference (Nothing in Visual Basic).</exception>
bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> keyValuePair) =>
TryRemove(keyValuePair);
#endregion
#region IEnumerable Members
/// <summary>Returns an enumerator that iterates through the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>.</summary>
/// <returns>An enumerator for the <see cref="ConcurrentDictionary2{TKey,TValue}"/>.</returns>
/// <remarks>
/// The enumerator returned from the dictionary is safe to use concurrently with
/// reads and writes to the dictionary, however it does not represent a moment-in-time snapshot
/// of the dictionary. The contents exposed through the enumerator may contain modifications
/// made to the dictionary after <see cref="GetEnumerator"/> was called.
/// </remarks>
IEnumerator IEnumerable.GetEnumerator() => ((ConcurrentDictionary2<TKey, TValue>)this).GetEnumerator();
#endregion
#region IDictionary Members
/// <summary>
/// Adds the specified key and value to the dictionary.
/// </summary>
/// <param name="key">The object to use as the key.</param>
/// <param name="value">The object to use as the value.</param>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="OverflowException">The dictionary contains too many
/// elements.</exception>
/// <exception cref="ArgumentException">
/// <paramref name="key"/> is of a type that is not assignable to the key type <typeparamref
/// name="TKey"/> of the <see cref="Dictionary{TKey,TValue}"/>. -or-
/// <paramref name="value"/> is of a type that is not assignable to <typeparamref name="TValue"/>,
/// the type of values in the <see cref="Dictionary{TKey,TValue}"/>.
/// -or- A value with the same key already exists in the <see
/// cref="Dictionary{TKey,TValue}"/>.
/// </exception>
void IDictionary.Add(object key, object? value)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
if (!(key is TKey))
{
throw new ArgumentException("TypeOfKeyIncorrect");
}
ThrowIfInvalidObjectValue(value);
((IDictionary<TKey, TValue>)this).Add((TKey)key, (TValue)value!);
}
/// <summary>
/// Gets whether the <see cref="IDictionary"/> contains an
/// element with the specified key.
/// </summary>
/// <param name="key">The key to locate in the <see
/// cref="IDictionary"/>.</param>
/// <returns>true if the <see cref="IDictionary"/> contains
/// an element with the specified key; otherwise, false.</returns>
/// <exception cref="ArgumentNullException"> <paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
bool IDictionary.Contains(object key)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
return key is TKey tkey && ContainsKey(tkey);
}
/// <summary>Provides an <see cref="IDictionaryEnumerator"/> for the
/// <see cref="IDictionary"/>.</summary>
/// <returns>An <see cref="IDictionaryEnumerator"/> for the <see
/// cref="IDictionary"/>.</returns>
IDictionaryEnumerator IDictionary.GetEnumerator() => new DictionaryEnumerator(this);
/// <summary>
/// Gets a value indicating whether the <see
/// cref="IDictionary"/> has a fixed size.
/// </summary>
/// <value>true if the <see cref="IDictionary"/> has a
/// fixed size; otherwise, false. For <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>, this property always
/// returns false.</value>
bool IDictionary.IsFixedSize => false;
/// <summary>
/// Gets a value indicating whether the <see
/// cref="IDictionary"/> is read-only.
/// </summary>
/// <value>true if the <see cref="IDictionary"/> is
/// read-only; otherwise, false. For <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>, this property always
/// returns false.</value>
bool IDictionary.IsReadOnly => false;
/// <summary>
/// Gets an <see cref="ICollection"/> containing the keys of the <see
/// cref="IDictionary"/>.
/// </summary>
/// <value>An <see cref="ICollection"/> containing the keys of the <see
/// cref="IDictionary"/>.</value>
ICollection IDictionary.Keys => GetKeys();
/// <summary>
/// Removes the element with the specified key from the <see
/// cref="IDictionary"/>.
/// </summary>
/// <param name="key">The key of the element to remove.</param>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
void IDictionary.Remove(object key)
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
if (key is TKey tkey)
{
TryRemove(tkey, out _);
}
}
/// <summary>
/// Gets an <see cref="ICollection"/> containing the values in the <see
/// cref="IDictionary"/>.
/// </summary>
/// <value>An <see cref="ICollection"/> containing the values in the <see
/// cref="IDictionary"/>.</value>
ICollection IDictionary.Values => GetValues();
/// <summary>
/// Gets or sets the value associated with the specified key.
/// </summary>
/// <param name="key">The key of the value to get or set.</param>
/// <value>The value associated with the specified key, or a null reference (Nothing in Visual Basic)
/// if <paramref name="key"/> is not in the dictionary or <paramref name="key"/> is of a type that is
/// not assignable to the key type <typeparamref name="TKey"/> of the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>.</value>
/// <exception cref="ArgumentNullException"><paramref name="key"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentException">
/// A value is being assigned, and <paramref name="key"/> is of a type that is not assignable to the
/// key type <typeparamref name="TKey"/> of the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>. -or- A value is being
/// assigned, and <paramref name="key"/> is of a type that is not assignable to the value type
/// <typeparamref name="TValue"/> of the <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>
/// </exception>
object? IDictionary.this[object key]
{
get
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
if (key is TKey tkey && TryGetValue(tkey, out TValue? value))
{
return value;
}
return null;
}
set
{
if (key is null)
{
throw new ArgumentNullException(nameof(key));
}
if (!(key is TKey))
{
throw new ArgumentException("TypeOfKeyIncorrect");
}
ThrowIfInvalidObjectValue(value);
((ConcurrentDictionary2<TKey, TValue>)this)[(TKey)key] = (TValue)value!;
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static void ThrowIfInvalidObjectValue(object? value)
{
if (value != null)
{
if (!(value is TValue))
{
throw new ArgumentException("Type of value is incorrect");
}
}
else if (default(TValue) != null)
{
throw new ArgumentException("Type of value is incorrect");
}
}
#endregion
#region ICollection Members
/// <summary>
/// Copies the elements of the <see cref="ICollection"/> to an array, starting
/// at the specified array index.
/// </summary>
/// <param name="array">The one-dimensional array that is the destination of the elements copied from
/// the <see cref="ICollection"/>. The array must have zero-based
/// indexing.</param>
/// <param name="index">The zero-based index in <paramref name="array"/> at which copying
/// begins.</param>
/// <exception cref="ArgumentNullException"><paramref name="array"/> is a null reference
/// (Nothing in Visual Basic).</exception>
/// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is less than
/// 0.</exception>
/// <exception cref="ArgumentException"><paramref name="index"/> is equal to or greater than
/// the length of the <paramref name="array"/>. -or- The number of elements in the source <see
/// cref="ICollection"/>
/// is greater than the available space from <paramref name="index"/> to the end of the destination
/// <paramref name="array"/>.</exception>
void ICollection.CopyTo(Array array, int index)
{
if (array is null)
{
throw new ArgumentNullException(nameof(array));
}
if (index < 0)
{
throw new ArgumentOutOfRangeException(nameof(index), "IndexIsNegative");
}
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
Tables tables = _tables;
int count = 0;
int[] countPerLock = tables._countPerLock;
for (int i = 0; i < countPerLock.Length && count >= 0; i++)
{
count += countPerLock[i];
}
if (array.Length - count < index || count < 0) //"count" itself or "count + index" can overflow
{
throw new ArgumentException("ArrayNotLargeEnough");
}
// To be consistent with the behavior of ICollection.CopyTo() in Dictionary<TKey,TValue>,
// we recognize three types of target arrays:
// - an array of KeyValuePair<TKey, TValue> structs
// - an array of DictionaryEntry structs
// - an array of objects
if (array is KeyValuePair<TKey, TValue>[] pairs)
{
CopyToPairs(pairs, index);
return;
}
if (array is DictionaryEntry[] entries)
{
CopyToEntries(entries, index);
return;
}
if (array is object[] objects)
{
CopyToObjects(objects, index);
return;
}
throw new ArgumentException("ArrayIncorrectType", nameof(array));
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
/// <summary>
/// Gets a value indicating whether access to the <see cref="ICollection"/> is
/// synchronized with the SyncRoot.
/// </summary>
/// <value>true if access to the <see cref="ICollection"/> is synchronized
/// (thread safe); otherwise, false. For <see
/// cref="ConcurrentDictionary2{TKey,TValue}"/>, this property always
/// returns false.</value>
bool ICollection.IsSynchronized => false;
/// <summary>
/// Gets an object that can be used to synchronize access to the <see
/// cref="ICollection"/>. This property is not supported.
/// </summary>
/// <exception cref="NotSupportedException">The SyncRoot property is not supported.</exception>
object ICollection.SyncRoot => throw new NotSupportedException("SyncRoot_NotSupported");
#endregion
private bool AreAllBucketsEmpty()
{
int[] countPerLock = _tables._countPerLock;
for (int i = 0; i < countPerLock.Length; i++)
{
if (countPerLock[i] != 0)
{
return false;
}
}
return true;
}
/// <summary>
/// Replaces the bucket table with a larger one. To prevent multiple threads from resizing the
/// table as a result of races, the Tables instance that holds the table of buckets deemed too
/// small is passed in as an argument to GrowTable(). GrowTable() obtains a lock, and then checks
/// the Tables instance has been replaced in the meantime or not.
/// </summary>
private void GrowTable(Tables tables)
{
const int MaxArrayLength = 0X7FEFFFFF;
int locksAcquired = 0;
try
{
// The thread that first obtains _locks[0] will be the one doing the resize operation
AcquireLocks(0, 1, ref locksAcquired);
// Make sure nobody resized the table while we were waiting for lock 0:
if (tables != _tables)
{
// We assume that since the table reference is different, it was already resized (or the budget
// was adjusted). If we ever decide to do table shrinking, or replace the table for other reasons,
// we will have to revisit this logic.
return;
}
// Compute the (approx.) total size. Use an Int64 accumulation variable to avoid an overflow.
long approxCount = 0;
for (int i = 0; i < tables._countPerLock.Length; i++)
{
approxCount += tables._countPerLock[i];
}
//
// If the bucket array is too empty, double the budget instead of resizing the table
//
if (approxCount < tables._buckets.Length / 4)
{
_budget = 2 * _budget;
if (_budget < 0)
{
_budget = int.MaxValue;
}
return;
}
// Compute the new table size. We find the smallest integer larger than twice the previous table size, and not divisible by
// 2,3,5 or 7. We can consider a different table-sizing policy in the future.
int newLength = 0;
bool maximizeTableSize = false;
try
{
checked
{
// Double the size of the buckets table and add one, so that we have an odd integer.
newLength = tables._buckets.Length * 2 + 1;
// Now, we only need to check odd integers, and find the first that is not divisible
// by 3, 5 or 7.
while (newLength % 3 == 0 || newLength % 5 == 0 || newLength % 7 == 0)
{
newLength += 2;
}
Debug.Assert(newLength % 2 != 0);
if (newLength > MaxArrayLength)
{
maximizeTableSize = true;
}
}
}
catch (OverflowException)
{
maximizeTableSize = true;
}
if (maximizeTableSize)
{
newLength = MaxArrayLength;
// We want to make sure that GrowTable will not be called again, since table is at the maximum size.
// To achieve that, we set the budget to int.MaxValue.
//
// (There is one special case that would allow GrowTable() to be called in the future:
// calling Clear() on the ConcurrentDictionary2 will shrink the table and lower the budget.)
_budget = int.MaxValue;
}
// Now acquire all other locks for the table
AcquireLocks(1, tables._locks.Length, ref locksAcquired);
object[] newLocks = tables._locks;
// Add more locks
if (_growLockArray && tables._locks.Length < MaxLockNumber)
{
newLocks = new object[tables._locks.Length * 2];
Array.Copy(tables._locks, newLocks, tables._locks.Length);
for (int i = tables._locks.Length; i < newLocks.Length; i++)
{
newLocks[i] = new object();
}
}
var newBuckets = new Node[newLength];
var newCountPerLock = new int[newLocks.Length];
var newTables = new Tables(newBuckets, newLocks, newCountPerLock);
// Copy all data into a new table, creating new nodes for all elements
foreach (Node? bucket in tables._buckets)
{
Node? current = bucket;
while (current != null)
{
Node? next = current._next;
ref Node? newBucket = ref newTables.GetBucketAndLock(current._hashcode, out uint newLockNo);
newBucket = new Node(current._key, current._value, current._hashcode, newBucket);
checked
{
newCountPerLock[newLockNo]++;
}
current = next;
}
}
// Adjust the budget
_budget = Math.Max(1, newBuckets.Length / newLocks.Length);
// Replace tables with the new versions
_tables = newTables;
}
finally
{
// Release all locks that we took earlier
ReleaseLocks(0, locksAcquired);
}
}
/// <summary>The number of concurrent writes for which to optimize by default.</summary>
private static int DefaultConcurrencyLevel => Environment.ProcessorCount;
/// <summary>
/// Acquires all locks for this hash table, and increments locksAcquired by the number
/// of locks that were successfully acquired. The locks are acquired in an increasing
/// order.
/// </summary>
private void AcquireAllLocks(ref int locksAcquired)
{
// First, acquire lock 0
AcquireLocks(0, 1, ref locksAcquired);
// Now that we have lock 0, the _locks array will not change (i.e., grow),
// and so we can safely read _locks.Length.
AcquireLocks(1, _tables._locks.Length, ref locksAcquired);
Debug.Assert(locksAcquired == _tables._locks.Length);
}
/// <summary>
/// Acquires a contiguous range of locks for this hash table, and increments locksAcquired
/// by the number of locks that were successfully acquired. The locks are acquired in an
/// increasing order.
/// </summary>
private void AcquireLocks(int fromInclusive, int toExclusive, ref int locksAcquired)
{
Debug.Assert(fromInclusive <= toExclusive);
object[] locks = _tables._locks;
for (int i = fromInclusive; i < toExclusive; i++)
{
bool lockTaken = false;
try
{
Monitor.Enter(locks[i], ref lockTaken);
}
finally
{
if (lockTaken)
{
locksAcquired++;
}
}
}
}
/// <summary>
/// Releases a contiguous range of locks.
/// </summary>
private void ReleaseLocks(int fromInclusive, int toExclusive)
{
Debug.Assert(fromInclusive <= toExclusive);
Tables tables = _tables;
for (int i = fromInclusive; i < toExclusive; i++)
{
Monitor.Exit(tables._locks[i]);
}
}
/// <summary>
/// Gets a collection containing the keys in the dictionary.
/// </summary>
private ReadOnlyCollection<TKey> GetKeys()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
int count = GetCountInternal();
if (count < 0)
{
throw new OutOfMemoryException();
}
var keys = new List<TKey>(count);
Node?[] buckets = _tables._buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node? current = buckets[i]; current != null; current = current._next)
{
keys.Add(current._key);
}
}
return new ReadOnlyCollection<TKey>(keys);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
/// <summary>
/// Gets a collection containing the values in the dictionary.
/// </summary>
private ReadOnlyCollection<TValue> GetValues()
{
int locksAcquired = 0;
try
{
AcquireAllLocks(ref locksAcquired);
int count = GetCountInternal();
if (count < 0)
{
throw new OutOfMemoryException();
}
var values = new List<TValue>(count);
Node?[] buckets = _tables._buckets;
for (int i = 0; i < buckets.Length; i++)
{
for (Node? current = buckets[i]; current != null; current = current._next)
{
values.Add(current._value);
}
}
return new ReadOnlyCollection<TValue>(values);
}
finally
{
ReleaseLocks(0, locksAcquired);
}
}
/// <summary>
/// A node in a singly-linked list representing a particular hash table bucket.
/// </summary>
private sealed class Node
{
internal readonly TKey _key;
internal TValue _value;
internal volatile Node? _next;
internal readonly int _hashcode;
internal Node(TKey key, TValue value, int hashcode, Node? next)
{
_key = key;
_value = value;
_next = next;
_hashcode = hashcode;
}
}
/// <summary>Tables that hold the internal state of the ConcurrentDictionary2</summary>
/// <remarks>
/// Wrapping the three tables in a single object allows us to atomically
/// replace all tables at once.
/// </remarks>
private sealed class Tables
{
/// <summary>A singly-linked list for each bucket.</summary>
internal readonly Node?[] _buckets;
/// <summary>A set of locks, each guarding a section of the table.</summary>
internal readonly object[] _locks;
/// <summary>The number of elements guarded by each lock.</summary>
internal readonly int[] _countPerLock;
/// <summary>Pre-computed multiplier for use on 64-bit performing faster modulo operations.</summary>
internal readonly ulong _fastModBucketsMultiplier;
internal Tables(Node?[] buckets, object[] locks, int[] countPerLock)
{
_buckets = buckets;
_locks = locks;
_countPerLock = countPerLock;
if (IntPtr.Size == 8)
{
_fastModBucketsMultiplier = HashHelpers.GetFastModMultiplier((uint)buckets.Length);
}
}
/// <summary>Computes a ref to the bucket for a particular key.</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
internal ref Node? GetBucket(int hashcode)
{
Node?[] buckets = _buckets;
if (IntPtr.Size == 8)
{
return ref buckets[HashHelpers.FastMod((uint)hashcode, (uint)buckets.Length, _fastModBucketsMultiplier)];
}
else
{
return ref buckets[(uint)hashcode % (uint)buckets.Length];
}
}
/// <summary>Computes the bucket and lock number for a particular key.</summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
internal ref Node? GetBucketAndLock(int hashcode, out uint lockNo)
{
Node?[] buckets = _buckets;
uint bucketNo;
if (IntPtr.Size == 8)
{
bucketNo = HashHelpers.FastMod((uint)hashcode, (uint)buckets.Length, _fastModBucketsMultiplier);
}
else
{
bucketNo = (uint)hashcode % (uint)buckets.Length;
}
lockNo = bucketNo % (uint)_locks.Length; // doesn't use FastMod, as it would require maintaining a different multiplier
return ref buckets[bucketNo];
}
}
/// <summary>
/// A private class to represent enumeration over the dictionary that implements the
/// IDictionaryEnumerator interface.
/// </summary>
private sealed class DictionaryEnumerator : IDictionaryEnumerator
{
private readonly IEnumerator<KeyValuePair<TKey, TValue>> _enumerator; // Enumerator over the dictionary.
internal DictionaryEnumerator(ConcurrentDictionary2<TKey, TValue> dictionary) => _enumerator = dictionary.GetEnumerator();
public DictionaryEntry Entry => new DictionaryEntry(_enumerator.Current.Key, _enumerator.Current.Value);
public object Key => _enumerator.Current.Key;
public object? Value => _enumerator.Current.Value;
public object Current => Entry;
public bool MoveNext() => _enumerator.MoveNext();
public void Reset() => _enumerator.Reset();
}
}
|
