//#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();
    }
}