diff options
Diffstat (limited to 'src/mscorlib/src/System/Collections/Concurrent/ConcurrentDictionary.cs')
-rw-r--r-- | src/mscorlib/src/System/Collections/Concurrent/ConcurrentDictionary.cs | 2095 |
1 files changed, 2095 insertions, 0 deletions
diff --git a/src/mscorlib/src/System/Collections/Concurrent/ConcurrentDictionary.cs b/src/mscorlib/src/System/Collections/Concurrent/ConcurrentDictionary.cs new file mode 100644 index 0000000000..d805dc8be7 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Concurrent/ConcurrentDictionary.cs @@ -0,0 +1,2095 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +// +/*============================================================ +** +** +** +** Purpose: A scalable dictionary for concurrent access +** +** +===========================================================*/ + +using System; +using System.Collections; +using System.Collections.Generic; +using System.Collections.ObjectModel; +using System.Diagnostics; +using System.Diagnostics.CodeAnalysis; +using System.Diagnostics.Contracts; +using System.Runtime.InteropServices; +using System.Runtime.Serialization; +using System.Text; +using System.Threading; +using System.Security; +using System.Security.Permissions; + +namespace System.Collections.Concurrent +{ + + /// <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="ConcurrentDictionary{TKey,TValue}"/> are thread-safe and may be used + /// concurrently from multiple threads. + /// </remarks> +#if !FEATURE_CORECLR + [Serializable] +#endif + [ComVisible(false)] + [DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))] + [DebuggerDisplay("Count = {Count}")] + [HostProtection(Synchronization = true, ExternalThreading = true)] + public class ConcurrentDictionary<TKey, TValue> : IDictionary<TKey, TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue> + { + /// <summary> + /// Tables that hold the internal state of the ConcurrentDictionary + /// + /// Wrapping the three tables in a single object allows us to atomically + /// replace all tables at once. + /// </summary> + private class Tables + { + internal readonly Node[] m_buckets; // A singly-linked list for each bucket. + internal readonly object[] m_locks; // A set of locks, each guarding a section of the table. + internal volatile int[] m_countPerLock; // The number of elements guarded by each lock. + internal readonly IEqualityComparer<TKey> m_comparer; // Key equality comparer + + internal Tables(Node[] buckets, object[] locks, int[] countPerLock, IEqualityComparer<TKey> comparer) + { + m_buckets = buckets; + m_locks = locks; + m_countPerLock = countPerLock; + m_comparer = comparer; + } + } +#if !FEATURE_CORECLR + [NonSerialized] +#endif + private volatile Tables m_tables; // Internal tables of the dictionary + // NOTE: this is only used for compat reasons to serialize the comparer. + // This should not be accessed from anywhere else outside of the serialization methods. + internal IEqualityComparer<TKey> m_comparer; +#if !FEATURE_CORECLR + [NonSerialized] +#endif + private readonly bool m_growLockArray; // Whether to dynamically increase the size of the striped lock + + // How many times we resized becaused of collisions. + // This is used to make sure we don't resize the dictionary because of multi-threaded Add() calls + // that generate collisions. Whenever a GrowTable() should be the only place that changes this +#if !FEATURE_CORECLR + // The field should be have been marked as NonSerialized but because we shipped it without that attribute in 4.5.1. + // we can't add it back without breaking compat. To maximize compat we are going to keep the OptionalField attribute + // This will prevent cases where the field was not serialized. + [OptionalField] +#endif + private int m_keyRehashCount; + +#if !FEATURE_CORECLR + [NonSerialized] +#endif + private int m_budget; // The maximum number of elements per lock before a resize operation is triggered + +#if !FEATURE_CORECLR // These fields are not used in CoreCLR + private KeyValuePair<TKey, TValue>[] m_serializationArray; // Used for custom serialization + + private int m_serializationConcurrencyLevel; // used to save the concurrency level in serialization + + private int m_serializationCapacity; // used to save the capacity in serialization +#endif + // The default concurrency level is DEFAULT_CONCURRENCY_MULTIPLIER * #CPUs. The higher the + // DEFAULT_CONCURRENCY_MULTIPLIER, the more concurrent writes can take place without interference + // and blocking, but also the more expensive operations that require all locks become (e.g. table + // resizing, ToArray, Count, etc). According to brief benchmarks that we ran, 4 seems like a good + // compromise. + private const int DEFAULT_CONCURRENCY_MULTIPLIER = 4; + + // The default capacity, i.e. the initial # of buckets. 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. + private const int DEFAULT_CAPACITY = 31; + + // The maximum size of the striped lock that will not be exceeded when locks are automatically + // added as the dictionary grows. However, the user is allowed to exceed this limit by passing + // a concurrency level larger than MAX_LOCK_NUMBER into the constructor. + private const int MAX_LOCK_NUMBER = 1024; + + // Whether TValue is a type that can be written atomically (i.e., with no danger of torn reads) + private static readonly bool s_isValueWriteAtomic = IsValueWriteAtomic(); + + + /// <summary> + /// Determines whether type TValue can be written atomically + /// </summary> + private static bool IsValueWriteAtomic() + { + Type valueType = typeof(TValue); + + // + // Section 12.6.6 of ECMA CLI explains which types can be read and written atomically without + // the risk of tearing. + // + // See http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-335.pdf + // + bool isAtomic = + (valueType.IsClass) + || valueType == typeof(Boolean) + || valueType == typeof(Char) + || valueType == typeof(Byte) + || valueType == typeof(SByte) + || valueType == typeof(Int16) + || valueType == typeof(UInt16) + || valueType == typeof(Int32) + || valueType == typeof(UInt32) + || valueType == typeof(Single); + + if (!isAtomic && IntPtr.Size == 8) + { + isAtomic |= valueType == typeof(Double) || valueType == typeof(Int64); + } + + return isAtomic; + } + + /// <summary> + /// Initializes a new instance of the <see + /// cref="ConcurrentDictionary{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 ConcurrentDictionary() : this(DefaultConcurrencyLevel, DEFAULT_CAPACITY, true, EqualityComparer<TKey>.Default) { } + + /// <summary> + /// Initializes a new instance of the <see + /// cref="ConcurrentDictionary{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="ConcurrentDictionary{TKey,TValue}"/> concurrently.</param> + /// <param name="capacity">The initial number of elements that the <see + /// cref="ConcurrentDictionary{TKey,TValue}"/> + /// can contain.</param> + /// <exception cref="T:System.ArgumentOutOfRangeException"><paramref name="concurrencyLevel"/> is + /// less than 1.</exception> + /// <exception cref="T:System.ArgumentOutOfRangeException"> <paramref name="capacity"/> is less than + /// 0.</exception> + public ConcurrentDictionary(int concurrencyLevel, int capacity) : this(concurrencyLevel, capacity, false, EqualityComparer<TKey>.Default) { } + + /// <summary> + /// Initializes a new instance of the <see cref="ConcurrentDictionary{TKey,TValue}"/> + /// class that contains elements copied from the specified <see + /// cref="T:System.Collections.IEnumerable{KeyValuePair{TKey,TValue}}"/>, 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="T:System.Collections.IEnumerable{KeyValuePair{TKey,TValue}}"/> whose elements are copied to + /// the new + /// <see cref="ConcurrentDictionary{TKey,TValue}"/>.</param> + /// <exception cref="T:System.ArgumentNullException"><paramref name="collection"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.ArgumentException"><paramref name="collection"/> contains one or more + /// duplicate keys.</exception> + public ConcurrentDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection) : this(collection, EqualityComparer<TKey>.Default) { } + + /// <summary> + /// Initializes a new instance of the <see cref="ConcurrentDictionary{TKey,TValue}"/> + /// class that is empty, has the specified concurrency level and capacity, and uses the specified + /// <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/>. + /// </summary> + /// <param name="comparer">The <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/> + /// implementation to use when comparing keys.</param> + /// <exception cref="T:System.ArgumentNullException"><paramref name="comparer"/> is a null reference + /// (Nothing in Visual Basic).</exception> + public ConcurrentDictionary(IEqualityComparer<TKey> comparer) : this(DefaultConcurrencyLevel, DEFAULT_CAPACITY, true, comparer) { } + + /// <summary> + /// Initializes a new instance of the <see cref="ConcurrentDictionary{TKey,TValue}"/> + /// class that contains elements copied from the specified <see + /// cref="T:System.Collections.IEnumerable"/>, has the default concurrency level, has the default + /// initial capacity, and uses the specified + /// <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/>. + /// </summary> + /// <param name="collection">The <see + /// cref="T:System.Collections.IEnumerable{KeyValuePair{TKey,TValue}}"/> whose elements are copied to + /// the new + /// <see cref="ConcurrentDictionary{TKey,TValue}"/>.</param> + /// <param name="comparer">The <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/> + /// implementation to use when comparing keys.</param> + /// <exception cref="T:System.ArgumentNullException"><paramref name="collection"/> is a null reference + /// (Nothing in Visual Basic). -or- + /// <paramref name="comparer"/> is a null reference (Nothing in Visual Basic). + /// </exception> + public ConcurrentDictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer) + : this(comparer) + { + if (collection == null) throw new ArgumentNullException("collection"); + + InitializeFromCollection(collection); + } + + /// <summary> + /// Initializes a new instance of the <see cref="ConcurrentDictionary{TKey,TValue}"/> + /// class that contains elements copied from the specified <see cref="T:System.Collections.IEnumerable"/>, + /// has the specified concurrency level, has the specified initial capacity, and uses the specified + /// <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/>. + /// </summary> + /// <param name="concurrencyLevel">The estimated number of threads that will update the + /// <see cref="ConcurrentDictionary{TKey,TValue}"/> concurrently.</param> + /// <param name="collection">The <see cref="T:System.Collections.IEnumerable{KeyValuePair{TKey,TValue}}"/> whose elements are copied to the new + /// <see cref="ConcurrentDictionary{TKey,TValue}"/>.</param> + /// <param name="comparer">The <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/> implementation to use + /// when comparing keys.</param> + /// <exception cref="T:System.ArgumentNullException"> + /// <paramref name="collection"/> is a null reference (Nothing in Visual Basic). + /// -or- + /// <paramref name="comparer"/> is a null reference (Nothing in Visual Basic). + /// </exception> + /// <exception cref="T:System.ArgumentOutOfRangeException"> + /// <paramref name="concurrencyLevel"/> is less than 1. + /// </exception> + /// <exception cref="T:System.ArgumentException"><paramref name="collection"/> contains one or more duplicate keys.</exception> + public ConcurrentDictionary( + int concurrencyLevel, IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer) + : this(concurrencyLevel, DEFAULT_CAPACITY, false, comparer) + { + if (collection == null) throw new ArgumentNullException("collection"); + if (comparer == null) throw new ArgumentNullException("comparer"); + + InitializeFromCollection(collection); + } + + private void InitializeFromCollection(IEnumerable<KeyValuePair<TKey, TValue>> collection) + { + TValue dummy; + foreach (KeyValuePair<TKey, TValue> pair in collection) + { + if (pair.Key == null) throw new ArgumentNullException("key"); + + if (!TryAddInternal(pair.Key, pair.Value, false, false, out dummy)) + { + throw new ArgumentException(GetResource("ConcurrentDictionary_SourceContainsDuplicateKeys")); + } + } + + if (m_budget == 0) + { + m_budget = m_tables.m_buckets.Length / m_tables.m_locks.Length; + } + + } + + /// <summary> + /// Initializes a new instance of the <see cref="ConcurrentDictionary{TKey,TValue}"/> + /// class that is empty, has the specified concurrency level, has the specified initial capacity, and + /// uses the specified <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/>. + /// </summary> + /// <param name="concurrencyLevel">The estimated number of threads that will update the + /// <see cref="ConcurrentDictionary{TKey,TValue}"/> concurrently.</param> + /// <param name="capacity">The initial number of elements that the <see + /// cref="ConcurrentDictionary{TKey,TValue}"/> + /// can contain.</param> + /// <param name="comparer">The <see cref="T:System.Collections.Generic.IEqualityComparer{TKey}"/> + /// implementation to use when comparing keys.</param> + /// <exception cref="T:System.ArgumentOutOfRangeException"> + /// <paramref name="concurrencyLevel"/> is less than 1. -or- + /// <paramref name="capacity"/> is less than 0. + /// </exception> + /// <exception cref="T:System.ArgumentNullException"><paramref name="comparer"/> is a null reference + /// (Nothing in Visual Basic).</exception> + public ConcurrentDictionary(int concurrencyLevel, int capacity, IEqualityComparer<TKey> comparer) + : this(concurrencyLevel, capacity, false, comparer) + { + } + + internal ConcurrentDictionary(int concurrencyLevel, int capacity, bool growLockArray, IEqualityComparer<TKey> comparer) + { + if (concurrencyLevel < 1) + { + throw new ArgumentOutOfRangeException("concurrencyLevel", GetResource("ConcurrentDictionary_ConcurrencyLevelMustBePositive")); + } + if (capacity < 0) + { + throw new ArgumentOutOfRangeException("capacity", GetResource("ConcurrentDictionary_CapacityMustNotBeNegative")); + } + if (comparer == null) throw new ArgumentNullException("comparer"); + + // 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; + } + + object[] locks = new object[concurrencyLevel]; + for (int i = 0; i < locks.Length; i++) + { + locks[i] = new object(); + } + + int[] countPerLock = new int[locks.Length]; + Node[] buckets = new Node[capacity]; + m_tables = new Tables(buckets, locks, countPerLock, comparer); + + m_growLockArray = growLockArray; + m_budget = buckets.Length / locks.Length; + } + + + /// <summary> + /// Attempts to add the specified key and value to the <see cref="ConcurrentDictionary{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="ConcurrentDictionary{TKey, + /// TValue}"/> + /// successfully; otherwise, false.</returns> + /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.OverflowException">The <see cref="ConcurrentDictionary{TKey, TValue}"/> + /// contains too many elements.</exception> + public bool TryAdd(TKey key, TValue value) + { + if (key == null) throw new ArgumentNullException("key"); + TValue dummy; + return TryAddInternal(key, value, false, true, out dummy); + } + + /// <summary> + /// Determines whether the <see cref="ConcurrentDictionary{TKey, TValue}"/> contains the specified + /// key. + /// </summary> + /// <param name="key">The key to locate in the <see cref="ConcurrentDictionary{TKey, + /// TValue}"/>.</param> + /// <returns>true if the <see cref="ConcurrentDictionary{TKey, TValue}"/> contains an element with + /// the specified key; otherwise, false.</returns> + /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + public bool ContainsKey(TKey key) + { + if (key == null) throw new ArgumentNullException("key"); + + TValue throwAwayValue; + return TryGetValue(key, out throwAwayValue); + } + + /// <summary> + /// Attempts to remove and return the the value with the specified key from the + /// <see cref="ConcurrentDictionary{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="ConcurrentDictionary{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="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + public bool TryRemove(TKey key, out TValue value) + { + if (key == null) throw new ArgumentNullException("key"); + + return TryRemoveInternal(key, out value, false, default(TValue)); + } + + /// <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> + /// <returns></returns> + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "Reviewed for thread safety")] + private bool TryRemoveInternal(TKey key, out TValue value, bool matchValue, TValue oldValue) + { + while (true) + { + Tables tables = m_tables; + + IEqualityComparer<TKey> comparer = tables.m_comparer; + + int bucketNo, lockNo; + GetBucketAndLockNo(comparer.GetHashCode(key), out bucketNo, out lockNo, tables.m_buckets.Length, tables.m_locks.Length); + + lock (tables.m_locks[lockNo]) + { + // If the table just got resized, we may not be holding the right lock, and must retry. + // This should be a rare occurence. + if (tables != m_tables) + { + continue; + } + + Node prev = null; + for (Node curr = tables.m_buckets[bucketNo]; curr != null; curr = curr.m_next) + { + Assert((prev == null && curr == tables.m_buckets[bucketNo]) || prev.m_next == curr); + + if (comparer.Equals(curr.m_key, key)) + { + if (matchValue) + { + bool valuesMatch = EqualityComparer<TValue>.Default.Equals(oldValue, curr.m_value); + if (!valuesMatch) + { + value = default(TValue); + return false; + } + } + + if (prev == null) + { + Volatile.Write<Node>(ref tables.m_buckets[bucketNo], curr.m_next); + } + else + { + prev.m_next = curr.m_next; + } + + value = curr.m_value; + tables.m_countPerLock[lockNo]--; + return true; + } + prev = curr; + } + } + + value = default(TValue); + return false; + } + } + + /// <summary> + /// Attempts to get the value associated with the specified key from the <see + /// cref="ConcurrentDictionary{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="ConcurrentDictionary{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="ConcurrentDictionary{TKey,TValue}"/>; + /// otherwise, false.</returns> + /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "Reviewed for thread safety")] + public bool TryGetValue(TKey key, out TValue value) + { + if (key == null) throw new ArgumentNullException("key"); + + int bucketNo, lockNoUnused; + + // We must capture the m_buckets field in a local variable. It is set to a new table on each table resize. + Tables tables = m_tables; + IEqualityComparer<TKey> comparer = tables.m_comparer; + GetBucketAndLockNo(comparer.GetHashCode(key), out bucketNo, out lockNoUnused, tables.m_buckets.Length, tables.m_locks.Length); + + // We can get away w/out a lock here. + // The Volatile.Read ensures that the load of the fields of 'n' doesn't move before the load from buckets[i]. + Node n = Volatile.Read<Node>(ref tables.m_buckets[bucketNo]); + + while (n != null) + { + if (comparer.Equals(n.m_key, key)) + { + value = n.m_value; + return true; + } + n = n.m_next; + } + + value = default(TValue); + return false; + } + + /// <summary> + /// Compares the existing value for the specified key with a specified value, and if they're equal, + /// updates the key with a third value. + /// </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="T:System.ArgumentNullException"><paramref name="key"/> is a null + /// reference.</exception> + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "Reviewed for thread safety")] + public bool TryUpdate(TKey key, TValue newValue, TValue comparisonValue) + { + if (key == null) throw new ArgumentNullException("key"); + + IEqualityComparer<TValue> valueComparer = EqualityComparer<TValue>.Default; + + while (true) + { + int bucketNo; + int lockNo; + int hashcode; + + Tables tables = m_tables; + IEqualityComparer<TKey> comparer = tables.m_comparer; + + hashcode = comparer.GetHashCode(key); + GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, tables.m_buckets.Length, tables.m_locks.Length); + + lock (tables.m_locks[lockNo]) + { + // If the table just got resized, we may not be holding the right lock, and must retry. + // This should be a rare occurence. + if (tables != m_tables) + { + continue; + } + + // Try to find this key in the bucket + Node prev = null; + for (Node node = tables.m_buckets[bucketNo]; node != null; node = node.m_next) + { + Assert((prev == null && node == tables.m_buckets[bucketNo]) || prev.m_next == node); + if (comparer.Equals(node.m_key, key)) + { + if (valueComparer.Equals(node.m_value, comparisonValue)) + { + if (s_isValueWriteAtomic) + { + node.m_value = newValue; + } + else + { + Node newNode = new Node(node.m_key, newValue, hashcode, node.m_next); + + if (prev == null) + { + tables.m_buckets[bucketNo] = newNode; + } + else + { + prev.m_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="ConcurrentDictionary{TKey,TValue}"/>. + /// </summary> + public void Clear() + { + int locksAcquired = 0; + try + { + AcquireAllLocks(ref locksAcquired); + + Tables newTables = new Tables(new Node[DEFAULT_CAPACITY], m_tables.m_locks, new int[m_tables.m_countPerLock.Length], m_tables.m_comparer); + m_tables = newTables; + m_budget = Math.Max(1, newTables.m_buckets.Length / newTables.m_locks.Length); + } + finally + { + ReleaseLocks(0, locksAcquired); + } + } + + /// <summary> + /// Copies the elements of the <see cref="T:System.Collections.Generic.ICollection"/> to an array of + /// type <see cref="T:System.Collections.Generic.KeyValuePair{TKey,TValue}"/>, starting at the + /// specified array index. + /// </summary> + /// <param name="array">The one-dimensional array of type <see + /// cref="T:System.Collections.Generic.KeyValuePair{TKey,TValue}"/> + /// that is the destination of the <see + /// cref="T:System.Collections.Generic.KeyValuePair{TKey,TValue}"/> elements copied from the <see + /// cref="T:System.Collections.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="T:System.ArgumentNullException"><paramref name="array"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.ArgumentOutOfRangeException"><paramref name="index"/> is less than + /// 0.</exception> + /// <exception cref="T:System.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="T:System.Collections.ICollection"/> + /// is greater than the available space from <paramref name="index"/> to the end of the destination + /// <paramref name="array"/>.</exception> + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] + void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int index) + { + if (array == null) throw new ArgumentNullException("array"); + if (index < 0) throw new ArgumentOutOfRangeException("index", GetResource("ConcurrentDictionary_IndexIsNegative")); + + int locksAcquired = 0; + try + { + AcquireAllLocks(ref locksAcquired); + + int count = 0; + + for (int i = 0; i < m_tables.m_locks.Length && count >= 0; i++) + { + count += m_tables.m_countPerLock[i]; + } + + if (array.Length - count < index || count < 0) //"count" itself or "count + index" can overflow + { + throw new ArgumentException(GetResource("ConcurrentDictionary_ArrayNotLargeEnough")); + } + + CopyToPairs(array, index); + } + finally + { + ReleaseLocks(0, locksAcquired); + } + } + + /// <summary> + /// Copies the key and value pairs stored in the <see cref="ConcurrentDictionary{TKey,TValue}"/> to a + /// new array. + /// </summary> + /// <returns>A new array containing a snapshot of key and value pairs copied from the <see + /// cref="ConcurrentDictionary{TKey,TValue}"/>.</returns> + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] + public KeyValuePair<TKey, TValue>[] ToArray() + { + int locksAcquired = 0; + try + { + AcquireAllLocks(ref locksAcquired); + int count = 0; + checked + { + for (int i = 0; i < m_tables.m_locks.Length; i++) + { + count += m_tables.m_countPerLock[i]; + } + } + + KeyValuePair<TKey, TValue>[] 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. + /// + /// Important: the caller must hold all locks in m_locks before calling CopyToPairs. + /// </summary> + private void CopyToPairs(KeyValuePair<TKey, TValue>[] array, int index) + { + Node[] buckets = m_tables.m_buckets; + for (int i = 0; i < buckets.Length; i++) + { + for (Node current = buckets[i]; current != null; current = current.m_next) + { + array[index] = new KeyValuePair<TKey, TValue>(current.m_key, current.m_value); + index++; //this should never flow, CopyToPairs is only called when there's no overflow risk + } + } + } + + /// <summary> + /// Copy dictionary contents to an array - shared implementation between ToArray and CopyTo. + /// + /// Important: the caller must hold all locks in m_locks before calling CopyToEntries. + /// </summary> + private void CopyToEntries(DictionaryEntry[] array, int index) + { + Node[] buckets = m_tables.m_buckets; + for (int i = 0; i < buckets.Length; i++) + { + for (Node current = buckets[i]; current != null; current = current.m_next) + { + array[index] = new DictionaryEntry(current.m_key, current.m_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. + /// + /// Important: the caller must hold all locks in m_locks before calling CopyToObjects. + /// </summary> + private void CopyToObjects(object[] array, int index) + { + Node[] buckets = m_tables.m_buckets; + for (int i = 0; i < buckets.Length; i++) + { + for (Node current = buckets[i]; current != null; current = current.m_next) + { + array[index] = new KeyValuePair<TKey, TValue>(current.m_key, current.m_value); + index++; //this should never flow, CopyToObjects is only called when there's no overflow risk + } + } + } + + /// <summary>Returns an enumerator that iterates through the <see + /// cref="ConcurrentDictionary{TKey,TValue}"/>.</summary> + /// <returns>An enumerator for the <see cref="ConcurrentDictionary{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() + { + Node[] buckets = m_tables.m_buckets; + + for (int i = 0; i < buckets.Length; i++) + { + // The Volatile.Read ensures that the load of the fields of 'current' doesn't move before the load from buckets[i]. + Node current = Volatile.Read<Node>(ref buckets[i]); + + while (current != null) + { + yield return new KeyValuePair<TKey, TValue>(current.m_key, current.m_value); + current = current.m_next; + } + } + } + + /// <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> + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "Reviewed for thread safety")] + private bool TryAddInternal(TKey key, TValue value, bool updateIfExists, bool acquireLock, out TValue resultingValue) + { + while (true) + { + int bucketNo, lockNo; + int hashcode; + + Tables tables = m_tables; + IEqualityComparer<TKey> comparer = tables.m_comparer; + hashcode = comparer.GetHashCode(key); + GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, tables.m_buckets.Length, tables.m_locks.Length); + + bool resizeDesired = false; + bool lockTaken = false; +#if FEATURE_RANDOMIZED_STRING_HASHING +#if !FEATURE_CORECLR + bool resizeDueToCollisions = false; +#endif // !FEATURE_CORECLR +#endif + + try + { + if (acquireLock) + Monitor.Enter(tables.m_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 occurence. + if (tables != m_tables) + { + continue; + } + +#if FEATURE_RANDOMIZED_STRING_HASHING +#if !FEATURE_CORECLR + int collisionCount = 0; +#endif // !FEATURE_CORECLR +#endif + + // Try to find this key in the bucket + Node prev = null; + for (Node node = tables.m_buckets[bucketNo]; node != null; node = node.m_next) + { + Assert((prev == null && node == tables.m_buckets[bucketNo]) || prev.m_next == node); + if (comparer.Equals(node.m_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.m_value = value; + } + else + { + Node newNode = new Node(node.m_key, value, hashcode, node.m_next); + if (prev == null) + { + tables.m_buckets[bucketNo] = newNode; + } + else + { + prev.m_next = newNode; + } + } + resultingValue = value; + } + else + { + resultingValue = node.m_value; + } + return false; + } + prev = node; + +#if FEATURE_RANDOMIZED_STRING_HASHING +#if !FEATURE_CORECLR + collisionCount++; +#endif // !FEATURE_CORECLR +#endif + } + +#if FEATURE_RANDOMIZED_STRING_HASHING +#if !FEATURE_CORECLR + if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) + { + resizeDesired = true; + resizeDueToCollisions = true; + } +#endif // !FEATURE_CORECLR +#endif + + // The key was not found in the bucket. Insert the key-value pair. + Volatile.Write<Node>(ref tables.m_buckets[bucketNo], new Node(key, value, hashcode, tables.m_buckets[bucketNo])); + checked + { + tables.m_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.m_countPerLock[lockNo] > m_budget) + { + resizeDesired = true; + } + } + finally + { + if (lockTaken) + Monitor.Exit(tables.m_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) + { +#if FEATURE_RANDOMIZED_STRING_HASHING +#if !FEATURE_CORECLR + if (resizeDueToCollisions) + { + GrowTable(tables, (IEqualityComparer<TKey>)HashHelpers.GetRandomizedEqualityComparer(comparer), true, m_keyRehashCount); + } + else +#endif // !FEATURE_CORECLR + { + GrowTable(tables, tables.m_comparer, false, m_keyRehashCount); + } +#else + GrowTable(tables, tables.m_comparer, false, m_keyRehashCount); +#endif + } + + 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="T:Sytem.Collections.Generic.KeyNotFoundException"/>, and a set operation creates a new + /// element with the specified key.</value> + /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.Collections.Generic.KeyNotFoundException">The property is retrieved and + /// <paramref name="key"/> + /// does not exist in the collection.</exception> + public TValue this[TKey key] + { + get + { + TValue value; + if (!TryGetValue(key, out value)) + { + throw new KeyNotFoundException(); + } + return value; + } + set + { + if (key == null) throw new ArgumentNullException("key"); + TValue dummy; + TryAddInternal(key, value, true, true, out dummy); + } + } + + /// <summary> + /// Gets the number of key/value pairs contained in the <see + /// cref="ConcurrentDictionary{TKey,TValue}"/>. + /// </summary> + /// <exception cref="T:System.OverflowException">The dictionary contains too many + /// elements.</exception> + /// <value>The number of key/value paris contained in the <see + /// cref="ConcurrentDictionary{TKey,TValue}"/>.</value> + /// <remarks>Count has snapshot semantics and represents the number of items in the <see + /// cref="ConcurrentDictionary{TKey,TValue}"/> + /// at the moment when Count was accessed.</remarks> + public int Count + { + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] + get + { + int count = 0; + + int acquiredLocks = 0; + try + { + // Acquire all locks + AcquireAllLocks(ref acquiredLocks); + + // Compute the count, we allow overflow + for (int i = 0; i < m_tables.m_countPerLock.Length; i++) + { + count += m_tables.m_countPerLock[i]; + } + + } + finally + { + // Release locks that have been acquired earlier + ReleaseLocks(0, acquiredLocks); + } + + return count; + } + } + + /// <summary> + /// Adds a key/value pair to the <see cref="ConcurrentDictionary{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="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.ArgumentNullException"><paramref name="valueFactory"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.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 == null) throw new ArgumentNullException("key"); + if (valueFactory == null) throw new ArgumentNullException("valueFactory"); + + TValue resultingValue; + if (TryGetValue(key, out resultingValue)) + { + return resultingValue; + } + TryAddInternal(key, valueFactory(key), false, true, out resultingValue); + return resultingValue; + } + + /// <summary> + /// Adds a key/value pair to the <see cref="ConcurrentDictionary{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="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.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 == null) throw new ArgumentNullException("key"); + + TValue resultingValue; + TryAddInternal(key, value, false, true, out resultingValue); + return resultingValue; + } + + /// <summary> + /// Adds a key/value pair to the <see cref="ConcurrentDictionary{TKey,TValue}"/> if the key does not already + /// exist, or updates a key/value pair in the <see cref="ConcurrentDictionary{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="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.ArgumentNullException"><paramref name="addValueFactory"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.ArgumentNullException"><paramref name="updateValueFactory"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.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(TKey key, Func<TKey, TValue> addValueFactory, Func<TKey, TValue, TValue> updateValueFactory) + { + if (key == null) throw new ArgumentNullException("key"); + if (addValueFactory == null) throw new ArgumentNullException("addValueFactory"); + if (updateValueFactory == null) throw new ArgumentNullException("updateValueFactory"); + + TValue newValue, resultingValue; + while (true) + { + TValue oldValue; + if (TryGetValue(key, out oldValue)) + //key exists, try to update + { + newValue = updateValueFactory(key, oldValue); + if (TryUpdate(key, newValue, oldValue)) + { + return newValue; + } + } + else //try add + { + newValue = addValueFactory(key); + if (TryAddInternal(key, newValue, false, true, out resultingValue)) + { + return resultingValue; + } + } + } + } + + /// <summary> + /// Adds a key/value pair to the <see cref="ConcurrentDictionary{TKey,TValue}"/> if the key does not already + /// exist, or updates a key/value pair in the <see cref="ConcurrentDictionary{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="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.ArgumentNullException"><paramref name="updateValueFactory"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.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(TKey key, TValue addValue, Func<TKey, TValue, TValue> updateValueFactory) + { + if (key == null) throw new ArgumentNullException("key"); + if (updateValueFactory == null) throw new ArgumentNullException("updateValueFactory"); + TValue newValue, resultingValue; + while (true) + { + TValue oldValue; + if (TryGetValue(key, out oldValue)) + //key exists, try to update + { + newValue = updateValueFactory(key, oldValue); + if (TryUpdate(key, newValue, oldValue)) + { + return newValue; + } + } + else //try add + { + if (TryAddInternal(key, addValue, false, true, out resultingValue)) + { + return resultingValue; + } + } + } + } + + + + /// <summary> + /// Gets a value that indicates whether the <see cref="ConcurrentDictionary{TKey,TValue}"/> is empty. + /// </summary> + /// <value>true if the <see cref="ConcurrentDictionary{TKey,TValue}"/> is empty; otherwise, + /// false.</value> + public bool IsEmpty + { + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] + get + { + int acquiredLocks = 0; + try + { + // Acquire all locks + AcquireAllLocks(ref acquiredLocks); + + for (int i = 0; i < m_tables.m_countPerLock.Length; i++) + { + if (m_tables.m_countPerLock[i] != 0) + { + return false; + } + } + } + finally + { + // Release locks that have been acquired earlier + ReleaseLocks(0, acquiredLocks); + } + + return true; + } + } + + #region IDictionary<TKey,TValue> members + + /// <summary> + /// Adds the specified key and value to the <see + /// cref="T:System.Collections.Generic.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="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.OverflowException">The dictionary contains too many + /// elements.</exception> + /// <exception cref="T:System.ArgumentException"> + /// An element with the same key already exists in the <see + /// cref="ConcurrentDictionary{TKey,TValue}"/>.</exception> + void IDictionary<TKey, TValue>.Add(TKey key, TValue value) + { + if (!TryAdd(key, value)) + { + throw new ArgumentException(GetResource("ConcurrentDictionary_KeyAlreadyExisted")); + } + } + + /// <summary> + /// Removes the element with the specified key from the <see + /// cref="T:System.Collections.Generic.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="T:System.Collections.Generic.IDictionary{TKey,TValue}"/>. + /// </returns> + /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + bool IDictionary<TKey, TValue>.Remove(TKey key) + { + TValue throwAwayValue; + return TryRemove(key, out throwAwayValue); + } + + /// <summary> + /// Gets a collection containing the keys in the <see + /// cref="T:System.Collections.Generic.Dictionary{TKey,TValue}"/>. + /// </summary> + /// <value>An <see cref="T:System.Collections.Generic.ICollection{TKey}"/> containing the keys in the + /// <see cref="T:System.Collections.Generic.Dictionary{TKey,TValue}"/>.</value> + public ICollection<TKey> Keys + { + get { return GetKeys(); } + } + + /// <summary> + /// Gets an <see cref="T:System.Collections.Generic.IEnumerable{TKey}"/> containing the keys of + /// the <see cref="T:System.Collections.Generic.IReadOnlyDictionary{TKey,TValue}"/>. + /// </summary> + /// <value>An <see cref="T:System.Collections.Generic.IEnumerable{TKey}"/> containing the keys of + /// the <see cref="T:System.Collections.Generic.IReadOnlyDictionary{TKey,TValue}"/>.</value> + IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys + { + get { return GetKeys(); } + } + + /// <summary> + /// Gets a collection containing the values in the <see + /// cref="T:System.Collections.Generic.Dictionary{TKey,TValue}"/>. + /// </summary> + /// <value>An <see cref="T:System.Collections.Generic.ICollection{TValue}"/> containing the values in + /// the + /// <see cref="T:System.Collections.Generic.Dictionary{TKey,TValue}"/>.</value> + public ICollection<TValue> Values + { + get { return GetValues(); } + } + + /// <summary> + /// Gets an <see cref="T:System.Collections.Generic.IEnumerable{TValue}"/> containing the values + /// in the <see cref="T:System.Collections.Generic.IReadOnlyDictionary{TKey,TValue}"/>. + /// </summary> + /// <value>An <see cref="T:System.Collections.Generic.IEnumerable{TValue}"/> containing the + /// values in the <see cref="T:System.Collections.Generic.IReadOnlyDictionary{TKey,TValue}"/>.</value> + IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values + { + get { return GetValues(); } + } + #endregion + + #region ICollection<KeyValuePair<TKey,TValue>> Members + + /// <summary> + /// Adds the specified value to the <see cref="T:System.Collections.Generic.ICollection{TValue}"/> + /// with the specified key. + /// </summary> + /// <param name="keyValuePair">The <see cref="T:System.Collections.Generic.KeyValuePair{TKey,TValue}"/> + /// structure representing the key and value to add to the <see + /// cref="T:System.Collections.Generic.Dictionary{TKey,TValue}"/>.</param> + /// <exception cref="T:System.ArgumentNullException">The <paramref name="keyValuePair"/> of <paramref + /// name="keyValuePair"/> is null.</exception> + /// <exception cref="T:System.OverflowException">The <see + /// cref="T:System.Collections.Generic.Dictionary{TKey,TValue}"/> + /// contains too many elements.</exception> + /// <exception cref="T:System.ArgumentException">An element with the same key already exists in the + /// <see cref="T:System.Collections.Generic.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="T:System.Collections.Generic.ICollection{TKey,TValue}"/> + /// contains a specific key and value. + /// </summary> + /// <param name="keyValuePair">The <see cref="T:System.Collections.Generic.KeyValuePair{TKey,TValue}"/> + /// structure to locate in the <see + /// cref="T:System.Collections.Generic.ICollection{TValue}"/>.</param> + /// <returns>true if the <paramref name="keyValuePair"/> is found in the <see + /// cref="T:System.Collections.Generic.ICollection{TKey,TValue}"/>; otherwise, false.</returns> + bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair) + { + TValue value; + if (!TryGetValue(keyValuePair.Key, out 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="T:System.Collections.Generic.ICollection{TKey,TValue}"/> is + /// read-only; otherwise, false. For <see + /// cref="T:System.Collections.Generic.Dictionary{TKey,TValue}"/>, this property always returns + /// false.</value> + bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly + { + get { return false; } + } + + /// <summary> + /// Removes a key and value from the dictionary. + /// </summary> + /// <param name="keyValuePair">The <see + /// cref="T:System.Collections.Generic.KeyValuePair{TKey,TValue}"/> + /// structure representing the key and value to remove from the <see + /// cref="T:System.Collections.Generic.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="T:System.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) + { + if (keyValuePair.Key == null) throw new ArgumentNullException(GetResource("ConcurrentDictionary_ItemKeyIsNull")); + + TValue throwAwayValue; + return TryRemoveInternal(keyValuePair.Key, out throwAwayValue, true, keyValuePair.Value); + } + + #endregion + + #region IEnumerable Members + + /// <summary>Returns an enumerator that iterates through the <see + /// cref="ConcurrentDictionary{TKey,TValue}"/>.</summary> + /// <returns>An enumerator for the <see cref="ConcurrentDictionary{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() + { + return ((ConcurrentDictionary<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="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.OverflowException">The dictionary contains too many + /// elements.</exception> + /// <exception cref="T:System.ArgumentException"> + /// <paramref name="key"/> is of a type that is not assignable to the key type <typeparamref + /// name="TKey"/> of the <see cref="T:System.Collections.Generic.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="T:System.Collections.Generic.Dictionary{TKey,TValue}"/>. + /// -or- A value with the same key already exists in the <see + /// cref="T:System.Collections.Generic.Dictionary{TKey,TValue}"/>. + /// </exception> + void IDictionary.Add(object key, object value) + { + if (key == null) throw new ArgumentNullException("key"); + if (!(key is TKey)) throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfKeyIncorrect")); + + TValue typedValue; + try + { + typedValue = (TValue)value; + } + catch (InvalidCastException) + { + throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfValueIncorrect")); + } + + ((IDictionary<TKey, TValue>)this).Add((TKey)key, typedValue); + } + + /// <summary> + /// Gets whether the <see cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/> contains an + /// element with the specified key. + /// </summary> + /// <param name="key">The key to locate in the <see + /// cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/>.</param> + /// <returns>true if the <see cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/> contains + /// an element with the specified key; otherwise, false.</returns> + /// <exception cref="T:System.ArgumentNullException"> <paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + bool IDictionary.Contains(object key) + { + if (key == null) throw new ArgumentNullException("key"); + + return (key is TKey) && ((ConcurrentDictionary<TKey, TValue>)this).ContainsKey((TKey)key); + } + + /// <summary>Provides an <see cref="T:System.Collections.Generics.IDictionaryEnumerator"/> for the + /// <see cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/>.</summary> + /// <returns>An <see cref="T:System.Collections.Generics.IDictionaryEnumerator"/> for the <see + /// cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/>.</returns> + IDictionaryEnumerator IDictionary.GetEnumerator() + { + return new DictionaryEnumerator(this); + } + + /// <summary> + /// Gets a value indicating whether the <see + /// cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/> has a fixed size. + /// </summary> + /// <value>true if the <see cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/> has a + /// fixed size; otherwise, false. For <see + /// cref="T:System.Collections.Generic.ConcurrentDictionary{TKey,TValue}"/>, this property always + /// returns false.</value> + bool IDictionary.IsFixedSize + { + get { return false; } + } + + /// <summary> + /// Gets a value indicating whether the <see + /// cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/> is read-only. + /// </summary> + /// <value>true if the <see cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/> is + /// read-only; otherwise, false. For <see + /// cref="T:System.Collections.Generic.ConcurrentDictionary{TKey,TValue}"/>, this property always + /// returns false.</value> + bool IDictionary.IsReadOnly + { + get { return false; } + } + + /// <summary> + /// Gets an <see cref="T:System.Collections.ICollection"/> containing the keys of the <see + /// cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/>. + /// </summary> + /// <value>An <see cref="T:System.Collections.ICollection"/> containing the keys of the <see + /// cref="T:System.Collections.Generic.IDictionary{TKey,TValue}"/>.</value> + ICollection IDictionary.Keys + { + get { return GetKeys(); } + } + + /// <summary> + /// Removes the element with the specified key from the <see + /// cref="T:System.Collections.IDictionary"/>. + /// </summary> + /// <param name="key">The key of the element to remove.</param> + /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + void IDictionary.Remove(object key) + { + if (key == null) throw new ArgumentNullException("key"); + + TValue throwAwayValue; + if (key is TKey) + { + this.TryRemove((TKey)key, out throwAwayValue); + } + } + + /// <summary> + /// Gets an <see cref="T:System.Collections.ICollection"/> containing the values in the <see + /// cref="T:System.Collections.IDictionary"/>. + /// </summary> + /// <value>An <see cref="T:System.Collections.ICollection"/> containing the values in the <see + /// cref="T:System.Collections.IDictionary"/>.</value> + ICollection IDictionary.Values + { + get { return 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="T:System.Collections.Generic.ConcurrentDictionary{TKey,TValue}"/>.</value> + /// <exception cref="T:System.ArgumentNullException"><paramref name="key"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.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="T:System.Collections.Generic.ConcurrentDictionary{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="T:System.Collections.Generic.ConcurrentDictionary{TKey,TValue}"/> + /// </exception> + object IDictionary.this[object key] + { + get + { + if (key == null) throw new ArgumentNullException("key"); + + TValue value; + if (key is TKey && this.TryGetValue((TKey)key, out value)) + { + return value; + } + + return null; + } + set + { + if (key == null) throw new ArgumentNullException("key"); + + if (!(key is TKey)) throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfKeyIncorrect")); + if (!(value is TValue)) throw new ArgumentException(GetResource("ConcurrentDictionary_TypeOfValueIncorrect")); + + ((ConcurrentDictionary<TKey, TValue>)this)[(TKey)key] = (TValue)value; + } + } + + #endregion + + #region ICollection Members + + /// <summary> + /// Copies the elements of the <see cref="T:System.Collections.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="T:System.Collections.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="T:System.ArgumentNullException"><paramref name="array"/> is a null reference + /// (Nothing in Visual Basic).</exception> + /// <exception cref="T:System.ArgumentOutOfRangeException"><paramref name="index"/> is less than + /// 0.</exception> + /// <exception cref="T:System.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="T:System.Collections.ICollection"/> + /// is greater than the available space from <paramref name="index"/> to the end of the destination + /// <paramref name="array"/>.</exception> + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] + void ICollection.CopyTo(Array array, int index) + { + if (array == null) throw new ArgumentNullException("array"); + if (index < 0) throw new ArgumentOutOfRangeException("index", GetResource("ConcurrentDictionary_IndexIsNegative")); + + int locksAcquired = 0; + try + { + AcquireAllLocks(ref locksAcquired); + Tables tables = m_tables; + + int count = 0; + + for (int i = 0; i < tables.m_locks.Length && count >= 0; i++) + { + count += tables.m_countPerLock[i]; + } + + if (array.Length - count < index || count < 0) //"count" itself or "count + index" can overflow + { + throw new ArgumentException(GetResource("ConcurrentDictionary_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 + + KeyValuePair<TKey, TValue>[] pairs = array as KeyValuePair<TKey, TValue>[]; + if (pairs != null) + { + CopyToPairs(pairs, index); + return; + } + + DictionaryEntry[] entries = array as DictionaryEntry[]; + if (entries != null) + { + CopyToEntries(entries, index); + return; + } + + object[] objects = array as object[]; + if (objects != null) + { + CopyToObjects(objects, index); + return; + } + + throw new ArgumentException(GetResource("ConcurrentDictionary_ArrayIncorrectType"), "array"); + } + finally + { + ReleaseLocks(0, locksAcquired); + } + } + + /// <summary> + /// Gets a value indicating whether access to the <see cref="T:System.Collections.ICollection"/> is + /// synchronized with the SyncRoot. + /// </summary> + /// <value>true if access to the <see cref="T:System.Collections.ICollection"/> is synchronized + /// (thread safe); otherwise, false. For <see + /// cref="T:System.Collections.Concurrent.ConcurrentDictionary{TKey,TValue}"/>, this property always + /// returns false.</value> + bool ICollection.IsSynchronized + { + get { return false; } + } + + /// <summary> + /// Gets an object that can be used to synchronize access to the <see + /// cref="T:System.Collections.ICollection"/>. This property is not supported. + /// </summary> + /// <exception cref="T:System.NotSupportedException">The SyncRoot property is not supported.</exception> + object ICollection.SyncRoot + { + get + { + throw new NotSupportedException(Environment.GetResourceString("ConcurrentCollection_SyncRoot_NotSupported")); + } + } + + #endregion + + /// <summary> + /// Replaces the bucket table with a larger one. To prevent multiple threads from resizing the + /// table as a result of a race condition, 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. + /// The <paramref name="rehashCount"/> will be used to ensure that we don't do two subsequent resizes + /// because of a collision + /// </summary> + private void GrowTable(Tables tables, IEqualityComparer<TKey> newComparer, bool regenerateHashKeys, int rehashCount) + { + int locksAcquired = 0; + try + { + // The thread that first obtains m_locks[0] will be the one doing the resize operation + AcquireLocks(0, 1, ref locksAcquired); + + if (regenerateHashKeys && rehashCount == m_keyRehashCount) + { + // This method is called with regenerateHashKeys==true when we detected + // more than HashHelpers.HashCollisionThreshold collisions when adding a new element. + // In that case we are in the process of switching to another (randomized) comparer + // and we have to re-hash all the keys in the table. + // We are only going to do this if we did not just rehash the entire table while waiting for the lock + tables = m_tables; + } + else + { + // If we don't require a regeneration of hash keys we want to make sure we don't do work when + // we don't have to + if (tables != m_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.m_countPerLock.Length; i++) + { + approxCount += tables.m_countPerLock[i]; + } + + // + // If the bucket array is too empty, double the budget instead of resizing the table + // + if (approxCount < tables.m_buckets.Length / 4) + { + m_budget = 2 * m_budget; + if (m_budget < 0) + { + m_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.m_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; + } + + Assert(newLength % 2 != 0); + + if (newLength > Array.MaxArrayLength) + { + maximizeTableSize = true; + } + } + } + catch (OverflowException) + { + maximizeTableSize = true; + } + + if (maximizeTableSize) + { + newLength = Array.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 ConcurrentDictionary will shrink the table and lower the budget.) + m_budget = int.MaxValue; + } + + // Now acquire all other locks for the table + AcquireLocks(1, tables.m_locks.Length, ref locksAcquired); + + object[] newLocks = tables.m_locks; + + // Add more locks + if (m_growLockArray && tables.m_locks.Length < MAX_LOCK_NUMBER) + { + newLocks = new object[tables.m_locks.Length * 2]; + Array.Copy(tables.m_locks, newLocks, tables.m_locks.Length); + + for (int i = tables.m_locks.Length; i < newLocks.Length; i++) + { + newLocks[i] = new object(); + } + } + + Node[] newBuckets = new Node[newLength]; + int[] newCountPerLock = new int[newLocks.Length]; + + // Copy all data into a new table, creating new nodes for all elements + for (int i = 0; i < tables.m_buckets.Length; i++) + { + Node current = tables.m_buckets[i]; + while (current != null) + { + Node next = current.m_next; + int newBucketNo, newLockNo; + int nodeHashCode = current.m_hashcode; + + if (regenerateHashKeys) + { + // Recompute the hash from the key + nodeHashCode = newComparer.GetHashCode(current.m_key); + } + + GetBucketAndLockNo(nodeHashCode, out newBucketNo, out newLockNo, newBuckets.Length, newLocks.Length); + + newBuckets[newBucketNo] = new Node(current.m_key, current.m_value, nodeHashCode, newBuckets[newBucketNo]); + + checked + { + newCountPerLock[newLockNo]++; + } + + current = next; + } + } + + // If this resize regenerated the hashkeys, increment the count + if (regenerateHashKeys) + { + // We use unchecked here because we don't want to throw an exception if + // an overflow happens + unchecked + { + m_keyRehashCount++; + } + } + + // Adjust the budget + m_budget = Math.Max(1, newBuckets.Length / newLocks.Length); + + // Replace tables with the new versions + m_tables = new Tables(newBuckets, newLocks, newCountPerLock, newComparer); + } + finally + { + // Release all locks that we took earlier + ReleaseLocks(0, locksAcquired); + } + } + + /// <summary> + /// Computes the bucket and lock number for a particular key. + /// </summary> + private void GetBucketAndLockNo( + int hashcode, out int bucketNo, out int lockNo, int bucketCount, int lockCount) + { + bucketNo = (hashcode & 0x7fffffff) % bucketCount; + lockNo = bucketNo % lockCount; + + Assert(bucketNo >= 0 && bucketNo < bucketCount); + Assert(lockNo >= 0 && lockNo < lockCount); + } + + /// <summary> + /// The number of concurrent writes for which to optimize by default. + /// </summary> + private static int DefaultConcurrencyLevel + { + + get { return DEFAULT_CONCURRENCY_MULTIPLIER * PlatformHelper.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) + { +#if !FEATURE_CORECLR + if (CDSCollectionETWBCLProvider.Log.IsEnabled()) + { + CDSCollectionETWBCLProvider.Log.ConcurrentDictionary_AcquiringAllLocks(m_tables.m_buckets.Length); + } +#endif //!FEATURE_CORECLR + + // First, acquire lock 0 + AcquireLocks(0, 1, ref locksAcquired); + + // Now that we have lock 0, the m_locks array will not change (i.e., grow), + // and so we can safely read m_locks.Length. + AcquireLocks(1, m_tables.m_locks.Length, ref locksAcquired); + Assert(locksAcquired == m_tables.m_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) + { + Assert(fromInclusive <= toExclusive); + object[] locks = m_tables.m_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> + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "Reviewed for thread safety")] + private void ReleaseLocks(int fromInclusive, int toExclusive) + { + Assert(fromInclusive <= toExclusive); + + for (int i = fromInclusive; i < toExclusive; i++) + { + Monitor.Exit(m_tables.m_locks[i]); + } + } + + /// <summary> + /// Gets a collection containing the keys in the dictionary. + /// </summary> + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] + private ReadOnlyCollection<TKey> GetKeys() + { + int locksAcquired = 0; + try + { + AcquireAllLocks(ref locksAcquired); + List<TKey> keys = new List<TKey>(); + + for (int i = 0; i < m_tables.m_buckets.Length; i++) + { + Node current = m_tables.m_buckets[i]; + while (current != null) + { + keys.Add(current.m_key); + current = current.m_next; + } + } + + return new ReadOnlyCollection<TKey>(keys); + } + finally + { + ReleaseLocks(0, locksAcquired); + } + } + + /// <summary> + /// Gets a collection containing the values in the dictionary. + /// </summary> + [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] + private ReadOnlyCollection<TValue> GetValues() + { + int locksAcquired = 0; + try + { + AcquireAllLocks(ref locksAcquired); + List<TValue> values = new List<TValue>(); + + for (int i = 0; i < m_tables.m_buckets.Length; i++) + { + Node current = m_tables.m_buckets[i]; + while (current != null) + { + values.Add(current.m_value); + current = current.m_next; + } + } + + return new ReadOnlyCollection<TValue>(values); + } + finally + { + ReleaseLocks(0, locksAcquired); + } + } + + /// <summary> + /// A helper method for asserts. + /// </summary> + [Conditional("DEBUG")] + private void Assert(bool condition) + { + Contract.Assert(condition); + } + + /// <summary> + /// A helper function to obtain the string for a particular resource key. + /// </summary> + /// <param name="key"></param> + /// <returns></returns> + private string GetResource(string key) + { + Assert(key != null); + + return Environment.GetResourceString(key); + } + + /// <summary> + /// A node in a singly-linked list representing a particular hash table bucket. + /// </summary> + private class Node + { + internal TKey m_key; + internal TValue m_value; + internal volatile Node m_next; + internal int m_hashcode; + + internal Node(TKey key, TValue value, int hashcode, Node next) + { + m_key = key; + m_value = value; + m_next = next; + m_hashcode = hashcode; + } + } + + /// <summary> + /// A private class to represent enumeration over the dictionary that implements the + /// IDictionaryEnumerator interface. + /// </summary> + private class DictionaryEnumerator : IDictionaryEnumerator + { + IEnumerator<KeyValuePair<TKey, TValue>> m_enumerator; // Enumerator over the dictionary. + + internal DictionaryEnumerator(ConcurrentDictionary<TKey, TValue> dictionary) + { + m_enumerator = dictionary.GetEnumerator(); + } + + public DictionaryEntry Entry + { + get { return new DictionaryEntry(m_enumerator.Current.Key, m_enumerator.Current.Value); } + } + + public object Key + { + get { return m_enumerator.Current.Key; } + } + + public object Value + { + get { return m_enumerator.Current.Value; } + } + + public object Current + { + get { return this.Entry; } + } + + public bool MoveNext() + { + return m_enumerator.MoveNext(); + } + + public void Reset() + { + m_enumerator.Reset(); + } + } + +#if !FEATURE_CORECLR + /// <summary> + /// Get the data array to be serialized + /// </summary> + [OnSerializing] + private void OnSerializing(StreamingContext context) + { + Tables tables = m_tables; + + // save the data into the serialization array to be saved + m_serializationArray = ToArray(); + m_serializationConcurrencyLevel = tables.m_locks.Length; + m_serializationCapacity = tables.m_buckets.Length; + m_comparer = (IEqualityComparer<TKey>)HashHelpers.GetEqualityComparerForSerialization(tables.m_comparer); + } + + /// <summary> + /// Construct the dictionary from a previously serialized one + /// </summary> + [OnDeserialized] + private void OnDeserialized(StreamingContext context) + { + KeyValuePair<TKey, TValue>[] array = m_serializationArray; + + var buckets = new Node[m_serializationCapacity]; + var countPerLock = new int[m_serializationConcurrencyLevel]; + + var locks = new object[m_serializationConcurrencyLevel]; + for (int i = 0; i < locks.Length; i++) + { + locks[i] = new object(); + } + + m_tables = new Tables(buckets, locks, countPerLock, m_comparer); + + InitializeFromCollection(array); + m_serializationArray = null; + + } +#endif + } +} |