From 35b86e64b110a008f50312eb2331c778abe888a8 Mon Sep 17 00:00:00 2001 From: Stephen Toub Date: Fri, 8 Jun 2018 22:41:27 -0400 Subject: [PATCH] Remove ConcurrentDictionary from CoreLib (dotnet/coreclr#18308) Commit migrated from https://github.com/dotnet/coreclr/commit/b4617616dfc57d993f49e015cae45240f82f163b --- .../System.Private.CoreLib/Resources/Strings.resx | 33 - .../System.Private.CoreLib.csproj | 1 - .../Collections/Concurrent/ConcurrentDictionary.cs | 1590 -------------------- .../src/System/ThrowHelper.cs | 11 - 4 files changed, 1635 deletions(-) delete mode 100644 src/coreclr/src/System.Private.CoreLib/src/System/Collections/Concurrent/ConcurrentDictionary.cs diff --git a/src/coreclr/src/System.Private.CoreLib/Resources/Strings.resx b/src/coreclr/src/System.Private.CoreLib/Resources/Strings.resx index a21c2bc..b21ebe9 100644 --- a/src/coreclr/src/System.Private.CoreLib/Resources/Strings.resx +++ b/src/coreclr/src/System.Private.CoreLib/Resources/Strings.resx @@ -1993,33 +1993,6 @@ The SyncRoot property may not be used for the synchronization of concurrent collections. - - The array is multidimensional, or the type parameter for the set cannot be cast automatically to the type of the destination array. - - - The index is equal to or greater than the length of the array, or the number of elements in the dictionary is greater than the available space from index to the end of the destination array. - - - The capacity argument must be greater than or equal to zero. - - - The concurrencyLevel argument must be positive. - - - The index argument is less than zero. - - - TKey is a reference type and item.Key is null. - - - The key already existed in the dictionary. - - - The key was of an incorrect type for this dictionary. - - - The value was of an incorrect type for this dictionary. - Barrier finishing phase {1}. @@ -2029,9 +2002,6 @@ ConcurrentBag stealing in TryTake. - - ConcurrentDictionary acquiring all locks on {0} bucket(s). - Pop from ConcurrentStack spun {0} time(s). @@ -3691,9 +3661,6 @@ The startIndex argument must be greater than or equal to zero. - - The source argument contains duplicate keys. - This method is not supported on signature types. diff --git a/src/coreclr/src/System.Private.CoreLib/System.Private.CoreLib.csproj b/src/coreclr/src/System.Private.CoreLib/System.Private.CoreLib.csproj index 05b529e..b2387ce 100644 --- a/src/coreclr/src/System.Private.CoreLib/System.Private.CoreLib.csproj +++ b/src/coreclr/src/System.Private.CoreLib/System.Private.CoreLib.csproj @@ -558,7 +558,6 @@ - diff --git a/src/coreclr/src/System.Private.CoreLib/src/System/Collections/Concurrent/ConcurrentDictionary.cs b/src/coreclr/src/System.Private.CoreLib/src/System/Collections/Concurrent/ConcurrentDictionary.cs deleted file mode 100644 index cc6033f..0000000 --- a/src/coreclr/src/System.Private.CoreLib/src/System/Collections/Concurrent/ConcurrentDictionary.cs +++ /dev/null @@ -1,1590 +0,0 @@ -// 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. - -/*============================================================ -** -** Class: ConcurrentDictionary -** -** -** Purpose: A scalable dictionary for concurrent access -** -** -===========================================================*/ - -using System.Collections.Generic; -using System.Collections.ObjectModel; -using System.Diagnostics; -using System.Diagnostics.CodeAnalysis; -using System.Reflection; -using System.Runtime.CompilerServices; -using System.Threading; - -namespace System.Collections.Concurrent -{ - /// - /// Represents a thread-safe collection of keys and values. - /// - /// The type of the keys in the dictionary. - /// The type of the values in the dictionary. - /// - /// All public and protected members of are thread-safe and may be used - /// concurrently from multiple threads. - /// - [DebuggerTypeProxy(typeof(IDictionaryDebugView<,>))] - [DebuggerDisplay("Count = {Count}")] - internal class ConcurrentDictionary : IDictionary, IDictionary, IReadOnlyDictionary - { - /// - /// 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. - /// - private sealed class Tables - { - internal readonly Node[] _buckets; // A singly-linked list for each bucket. - internal readonly object[] _locks; // A set of locks, each guarding a section of the table. - internal volatile int[] _countPerLock; // The number of elements guarded by each lock. - - internal Tables(Node[] buckets, object[] locks, int[] countPerLock) - { - _buckets = buckets; - _locks = locks; - _countPerLock = countPerLock; - } - } - - private volatile Tables _tables; // Internal tables of the dictionary - private IEqualityComparer _comparer; // Key equality comparer - private readonly bool _growLockArray; // Whether to dynamically increase the size of the striped lock - private int _budget; // The maximum number of elements per lock before a resize operation is triggered - - // 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 DefaultCapacity = 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 MaxLockNumber into the constructor. - private const int MaxLockNumber = 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(); - - /// - /// Determines whether type TValue can be written atomically - /// - 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 http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-335.pdf - // - Type valueType = typeof(TValue); - if (!valueType.IsValueType) - { - return true; - } - if (valueType.IsEnum) - { - valueType = Enum.GetUnderlyingType(valueType); - } - - switch (Type.GetTypeCode(valueType)) - { - 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.Int64: - case TypeCode.Double: - case TypeCode.UInt64: - return IntPtr.Size == 8; - default: - return false; - } - } - - /// - /// Initializes a new instance of the - /// class that is empty, has the default concurrency level, has the default initial capacity, and - /// uses the default comparer for the key type. - /// - public ConcurrentDictionary() : this(DefaultConcurrencyLevel, DefaultCapacity, true, null) { } - - internal ConcurrentDictionary(int concurrencyLevel, int capacity, bool growLockArray, IEqualityComparer comparer) - { - if (concurrencyLevel < 1) - { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.concurrencyLevel, ExceptionResource.ConcurrentDictionary_ConcurrencyLevelMustBePositive); - } - if (capacity < 0) - { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ConcurrentDictionary_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; - } - - 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]; - _tables = new Tables(buckets, locks, countPerLock); - - _comparer = comparer ?? EqualityComparer.Default; - _growLockArray = growLockArray; - _budget = buckets.Length / locks.Length; - } - - /// - /// Attempts to add the specified key and value to the . - /// - /// The key of the element to add. - /// The value of the element to add. The value can be a null reference (Nothing - /// in Visual Basic) for reference types. - /// true if the key/value pair was added to the - /// successfully; otherwise, false. - /// is null reference - /// (Nothing in Visual Basic). - /// The - /// contains too many elements. - public bool TryAdd(TKey key, TValue value) - { - if (key == null) ThrowKeyNullException(); - TValue dummy; - return TryAddInternal(key, _comparer.GetHashCode(key), value, false, true, out dummy); - } - - /// - /// Determines whether the contains the specified - /// key. - /// - /// The key to locate in the . - /// true if the contains an element with - /// the specified key; otherwise, false. - /// is a null reference - /// (Nothing in Visual Basic). - public bool ContainsKey(TKey key) - { - if (key == null) ThrowKeyNullException(); - - TValue throwAwayValue; - return TryGetValue(key, out throwAwayValue); - } - - /// - /// Attempts to remove and return the value with the specified key from the - /// . - /// - /// The key of the element to remove and return. - /// When this method returns, contains the object removed from the - /// or the default value of - /// if the operation failed. - /// true if an object was removed successfully; otherwise, false. - /// is a null reference - /// (Nothing in Visual Basic). - public bool TryRemove(TKey key, out TValue value) - { - if (key == null) ThrowKeyNullException(); - - return TryRemoveInternal(key, out value, false, default); - } - - /// - /// 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. - /// - /// The key to search for and remove if it exists. - /// The variable into which the removed value, if found, is stored. - /// Whether removal of the key is conditional on its value. - /// The conditional value to compare against if is true - /// - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "Reviewed for thread safety")] - private bool TryRemoveInternal(TKey key, out TValue value, bool matchValue, TValue oldValue) - { - int hashcode = _comparer.GetHashCode(key); - while (true) - { - Tables tables = _tables; - - int bucketNo, lockNo; - GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, tables._buckets.Length, tables._locks.Length); - - lock (tables._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 = tables._buckets[bucketNo]; curr != null; curr = curr._next) - { - Debug.Assert((prev == null && curr == tables._buckets[bucketNo]) || prev._next == curr); - - if (hashcode == curr._hashcode && _comparer.Equals(curr._key, key)) - { - if (matchValue) - { - bool valuesMatch = EqualityComparer.Default.Equals(oldValue, curr._value); - if (!valuesMatch) - { - value = default; - return false; - } - } - - if (prev == null) - { - Volatile.Write(ref tables._buckets[bucketNo], curr._next); - } - else - { - prev._next = curr._next; - } - - value = curr._value; - tables._countPerLock[lockNo]--; - return true; - } - prev = curr; - } - } - - value = default; - return false; - } - } - - /// - /// Attempts to get the value associated with the specified key from the . - /// - /// The key of the value to get. - /// When this method returns, contains the object from - /// the - /// with the specified key or the default value of - /// , if the operation failed. - /// true if the key was found in the ; - /// otherwise, false. - /// is a null reference - /// (Nothing in Visual Basic). - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "Reviewed for thread safety")] - public bool TryGetValue(TKey key, out TValue value) - { - if (key == null) ThrowKeyNullException(); - return TryGetValueInternal(key, _comparer.GetHashCode(key), out value); - } - - private bool TryGetValueInternal(TKey key, int hashcode, out TValue value) - { - Debug.Assert(_comparer.GetHashCode(key) == hashcode); - - // We must capture the _buckets field in a local variable. It is set to a new table on each table resize. - Tables tables = _tables; - - int bucketNo = GetBucket(hashcode, tables._buckets.Length); - - // We can get away w/out a lock here. - // The Volatile.Read 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. - Node n = Volatile.Read(ref tables._buckets[bucketNo]); - - while (n != null) - { - if (hashcode == n._hashcode && _comparer.Equals(n._key, key)) - { - value = n._value; - return true; - } - n = n._next; - } - - value = default; - return false; - } - - /// - /// Removes all keys and values from the . - /// - public void Clear() - { - int locksAcquired = 0; - try - { - AcquireAllLocks(ref locksAcquired); - - Tables 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); - } - } - - /// - /// Copies the elements of the to an array of - /// type , starting at the - /// specified array index. - /// - /// The one-dimensional array of type - /// that is the destination of the elements copied from the . The array must have zero-based indexing. - /// The zero-based index in at which copying - /// begins. - /// is a null reference - /// (Nothing in Visual Basic). - /// is less than - /// 0. - /// is equal to or greater than - /// the length of the . -or- The number of elements in the source - /// is greater than the available space from to the end of the destination - /// . - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] - void ICollection>.CopyTo(KeyValuePair[] array, int index) - { - if (array == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); - if (index < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ConcurrentDictionary_IndexIsNegative); - - int locksAcquired = 0; - try - { - AcquireAllLocks(ref locksAcquired); - - int count = 0; - - for (int i = 0; i < _tables._locks.Length && count >= 0; i++) - { - count += _tables._countPerLock[i]; - } - - if (array.Length - count < index || count < 0) //"count" itself or "count + index" can overflow - { - ThrowHelper.ThrowArgumentException(ExceptionResource.ConcurrentDictionary_ArrayNotLargeEnough); - } - - CopyToPairs(array, index); - } - finally - { - ReleaseLocks(0, locksAcquired); - } - } - - /// - /// Copies the key and value pairs stored in the to a - /// new array. - /// - /// A new array containing a snapshot of key and value pairs copied from the . - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] - public KeyValuePair[] ToArray() - { - int locksAcquired = 0; - try - { - AcquireAllLocks(ref locksAcquired); - int count = 0; - checked - { - for (int i = 0; i < _tables._locks.Length; i++) - { - count += _tables._countPerLock[i]; - } - } - - if (count == 0) - { - return Array.Empty>(); - } - - KeyValuePair[] array = new KeyValuePair[count]; - CopyToPairs(array, 0); - return array; - } - finally - { - ReleaseLocks(0, locksAcquired); - } - } - - /// - /// Copy dictionary contents to an array - shared implementation between ToArray and CopyTo. - /// - /// Important: the caller must hold all locks in _locks before calling CopyToPairs. - /// - private void CopyToPairs(KeyValuePair[] 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(current._key, current._value); - index++; //this should never flow, CopyToPairs is only called when there's no overflow risk - } - } - } - - /// - /// Copy dictionary contents to an array - shared implementation between ToArray and CopyTo. - /// - /// Important: the caller must hold all locks in _locks before calling CopyToEntries. - /// - 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 - } - } - } - - /// - /// Copy dictionary contents to an array - shared implementation between ToArray and CopyTo. - /// - /// Important: the caller must hold all locks in _locks before calling CopyToObjects. - /// - 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(current._key, current._value); - index++; //this should never flow, CopyToObjects is only called when there's no overflow risk - } - } - } - - /// Returns an enumerator that iterates through the . - /// An enumerator for the . - /// - /// 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 was called. - /// - public IEnumerator> GetEnumerator() - { - Node[] buckets = _tables._buckets; - - for (int i = 0; i < buckets.Length; i++) - { - // 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 current = Volatile.Read(ref buckets[i]); - - while (current != null) - { - yield return new KeyValuePair(current._key, current._value); - current = current._next; - } - } - } - - /// - /// 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; - /// - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "Reviewed for thread safety")] - private bool TryAddInternal(TKey key, int hashcode, TValue value, bool updateIfExists, bool acquireLock, out TValue resultingValue) - { - Debug.Assert(_comparer.GetHashCode(key) == hashcode); - - while (true) - { - int bucketNo, lockNo; - - Tables tables = _tables; - GetBucketAndLockNo(hashcode, out bucketNo, out lockNo, tables._buckets.Length, tables._locks.Length); - - bool resizeDesired = false; - bool lockTaken = false; - try - { - if (acquireLock) - Monitor.Enter(tables._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 = tables._buckets[bucketNo]; node != null; node = node._next) - { - Debug.Assert((prev == null && node == tables._buckets[bucketNo]) || prev._next == node); - if (hashcode == node._hashcode && _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 - { - Node newNode = new Node(node._key, value, hashcode, node._next); - if (prev == null) - { - Volatile.Write(ref tables._buckets[bucketNo], 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. - Volatile.Write(ref tables._buckets[bucketNo], new Node(key, value, hashcode, tables._buckets[bucketNo])); - 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(tables._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; - } - } - - /// - /// Gets or sets the value associated with the specified key. - /// - /// The key of the value to get or set. - /// The value associated with the specified key. If the specified key is not found, a get - /// operation throws a - /// , and a set operation creates a new - /// element with the specified key. - /// is a null reference - /// (Nothing in Visual Basic). - /// The property is retrieved and - /// - /// does not exist in the collection. - public TValue this[TKey key] - { - get - { - TValue value; - if (!TryGetValue(key, out value)) - { - ThrowKeyNotFoundException(key); - } - return value; - } - set - { - if (key == null) ThrowKeyNullException(); - TValue dummy; - TryAddInternal(key, _comparer.GetHashCode(key), value, true, true, out dummy); - } - } - - // These exception throwing sites have been extracted into their own methods as these are - // uncommonly needed and when inlined are observed to prevent the inlining of important - // methods like TryGetValue and ContainsKey. - - private static void ThrowKeyNotFoundException(object key) - { - throw new KeyNotFoundException(SR.Format(SR.Arg_KeyNotFoundWithKey, key.ToString())); - } - - private static void ThrowKeyNullException() - { - throw new ArgumentNullException("key"); - } - - /// - /// Gets the number of key/value pairs contained in the . - /// - /// The dictionary contains too many - /// elements. - /// The number of key/value pairs contained in the . - /// Count has snapshot semantics and represents the number of items in the - /// at the moment when Count was accessed. - public int Count - { - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] - get - { - int acquiredLocks = 0; - try - { - // Acquire all locks - AcquireAllLocks(ref acquiredLocks); - - return GetCountInternal(); - } - finally - { - // Release locks that have been acquired earlier - ReleaseLocks(0, acquiredLocks); - } - } - } - - /// - /// Gets the number of key/value pairs contained in the . Should only be used after all locks - /// have been acquired. - /// - /// The dictionary contains too many - /// elements. - /// The number of key/value pairs contained in the . - /// Count has snapshot semantics and represents the number of items in the - /// at the moment when Count was accessed. - private int GetCountInternal() - { - int count = 0; - - // Compute the count, we allow overflow - for (int i = 0; i < _tables._countPerLock.Length; i++) - { - count += _tables._countPerLock[i]; - } - - return count; - } - - /// - /// Gets a value that indicates whether the is empty. - /// - /// true if the is empty; otherwise, - /// false. - 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 < _tables._countPerLock.Length; i++) - { - if (_tables._countPerLock[i] != 0) - { - return false; - } - } - } - finally - { - // Release locks that have been acquired earlier - ReleaseLocks(0, acquiredLocks); - } - - return true; - } - } - - #region IDictionary members - - /// - /// Adds the specified key and value to the . - /// - /// The object to use as the key of the element to add. - /// The object to use as the value of the element to add. - /// is a null reference - /// (Nothing in Visual Basic). - /// The dictionary contains too many - /// elements. - /// - /// An element with the same key already exists in the . - void IDictionary.Add(TKey key, TValue value) - { - if (!TryAdd(key, value)) - { - ThrowHelper.ThrowArgumentException(ExceptionResource.ConcurrentDictionary_KeyAlreadyExisted, ExceptionArgument.key); - } - } - - /// - /// Removes the element with the specified key from the . - /// - /// The key of the element to remove. - /// true if the element is successfully remove; otherwise false. This method also returns - /// false if - /// was not found in the original . - /// - /// is a null reference - /// (Nothing in Visual Basic). - bool IDictionary.Remove(TKey key) - { - TValue throwAwayValue; - return TryRemove(key, out throwAwayValue); - } - - /// - /// Gets a collection containing the keys in the . - /// - /// An containing the keys in the - /// . - public ICollection Keys - { - get { return GetKeys(); } - } - - /// - /// Gets an containing the keys of - /// the . - /// - /// An containing the keys of - /// the . - IEnumerable IReadOnlyDictionary.Keys - { - get { return GetKeys(); } - } - - /// - /// Gets a collection containing the values in the . - /// - /// An containing the values in - /// the - /// . - public ICollection Values - { - get { return GetValues(); } - } - - /// - /// Gets an containing the values - /// in the . - /// - /// An containing the - /// values in the . - IEnumerable IReadOnlyDictionary.Values - { - get { return GetValues(); } - } - #endregion - - #region ICollection> Members - - /// - /// Adds the specified value to the - /// with the specified key. - /// - /// The - /// structure representing the key and value to add to the . - /// The of is null. - /// The - /// contains too many elements. - /// An element with the same key already exists in the - /// - void ICollection>.Add(KeyValuePair keyValuePair) - { - ((IDictionary)this).Add(keyValuePair.Key, keyValuePair.Value); - } - - /// - /// Determines whether the - /// contains a specific key and value. - /// - /// The - /// structure to locate in the . - /// true if the is found in the ; otherwise, false. - bool ICollection>.Contains(KeyValuePair keyValuePair) - { - TValue value; - if (!TryGetValue(keyValuePair.Key, out value)) - { - return false; - } - return EqualityComparer.Default.Equals(value, keyValuePair.Value); - } - - /// - /// Gets a value indicating whether the dictionary is read-only. - /// - /// true if the is - /// read-only; otherwise, false. For , this property always returns - /// false. - bool ICollection>.IsReadOnly - { - get { return false; } - } - - /// - /// Removes a key and value from the dictionary. - /// - /// The - /// structure representing the key and value to remove from the . - /// true if the key and value represented by is successfully - /// found and removed; otherwise, false. - /// The Key property of is a null reference (Nothing in Visual Basic). - bool ICollection>.Remove(KeyValuePair keyValuePair) - { - if (keyValuePair.Key == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keyValuePair, ExceptionResource.ConcurrentDictionary_ItemKeyIsNull); - - TValue throwAwayValue; - return TryRemoveInternal(keyValuePair.Key, out throwAwayValue, true, keyValuePair.Value); - } - - #endregion - - #region IEnumerable Members - - /// Returns an enumerator that iterates through the . - /// An enumerator for the . - /// - /// 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 was called. - /// - IEnumerator IEnumerable.GetEnumerator() - { - return ((ConcurrentDictionary)this).GetEnumerator(); - } - - #endregion - - #region IDictionary Members - - /// - /// Adds the specified key and value to the dictionary. - /// - /// The object to use as the key. - /// The object to use as the value. - /// is a null reference - /// (Nothing in Visual Basic). - /// The dictionary contains too many - /// elements. - /// - /// is of a type that is not assignable to the key type of the . -or- - /// is of a type that is not assignable to , - /// the type of values in the . - /// -or- A value with the same key already exists in the . - /// - void IDictionary.Add(object key, object value) - { - if (key == null) ThrowKeyNullException(); - if (!(key is TKey)) ThrowHelper.ThrowArgumentException(ExceptionResource.ConcurrentDictionary_TypeOfKeyIncorrect, ExceptionArgument.key); - - TValue typedValue; - try - { - typedValue = (TValue)value; - } - catch (InvalidCastException) - { - ThrowHelper.ThrowArgumentException(ExceptionResource.ConcurrentDictionary_TypeOfValueIncorrect, ExceptionArgument.value); - return; - } - - ((IDictionary)this).Add((TKey)key, typedValue); - } - - /// - /// Gets whether the contains an - /// element with the specified key. - /// - /// The key to locate in the . - /// true if the contains - /// an element with the specified key; otherwise, false. - /// is a null reference - /// (Nothing in Visual Basic). - bool IDictionary.Contains(object key) - { - if (key == null) ThrowKeyNullException(); - - return (key is TKey) && this.ContainsKey((TKey)key); - } - - /// Provides an for the - /// . - /// An for the . - IDictionaryEnumerator IDictionary.GetEnumerator() - { - return new DictionaryEnumerator(this); - } - - /// - /// Gets a value indicating whether the has a fixed size. - /// - /// true if the has a - /// fixed size; otherwise, false. For , this property always - /// returns false. - bool IDictionary.IsFixedSize - { - get { return false; } - } - - /// - /// Gets a value indicating whether the is read-only. - /// - /// true if the is - /// read-only; otherwise, false. For , this property always - /// returns false. - bool IDictionary.IsReadOnly - { - get { return false; } - } - - /// - /// Gets an containing the keys of the . - /// - /// An containing the keys of the . - ICollection IDictionary.Keys - { - get { return GetKeys(); } - } - - /// - /// Removes the element with the specified key from the . - /// - /// The key of the element to remove. - /// is a null reference - /// (Nothing in Visual Basic). - void IDictionary.Remove(object key) - { - if (key == null) ThrowKeyNullException(); - - TValue throwAwayValue; - if (key is TKey) - { - TryRemove((TKey)key, out throwAwayValue); - } - } - - /// - /// Gets an containing the values in the . - /// - /// An containing the values in the . - ICollection IDictionary.Values - { - get { return GetValues(); } - } - - /// - /// Gets or sets the value associated with the specified key. - /// - /// The key of the value to get or set. - /// The value associated with the specified key, or a null reference (Nothing in Visual Basic) - /// if is not in the dictionary or is of a type that is - /// not assignable to the key type of the . - /// is a null reference - /// (Nothing in Visual Basic). - /// - /// A value is being assigned, and is of a type that is not assignable to the - /// key type of the . -or- A value is being - /// assigned, and is of a type that is not assignable to the value type - /// of the - /// - object IDictionary.this[object key] - { - get - { - if (key == null) ThrowKeyNullException(); - - TValue value; - if (key is TKey && TryGetValue((TKey)key, out value)) - { - return value; - } - - return null; - } - set - { - if (key == null) ThrowKeyNullException(); - - if (!(key is TKey)) ThrowHelper.ThrowArgumentException(ExceptionResource.ConcurrentDictionary_TypeOfKeyIncorrect, ExceptionArgument.key); - if (!(value is TValue)) ThrowHelper.ThrowArgumentException(ExceptionResource.ConcurrentDictionary_TypeOfValueIncorrect, ExceptionArgument.value); - - ((ConcurrentDictionary)this)[(TKey)key] = (TValue)value; - } - } - - #endregion - - #region ICollection Members - - /// - /// Copies the elements of the to an array, starting - /// at the specified array index. - /// - /// The one-dimensional array that is the destination of the elements copied from - /// the . The array must have zero-based - /// indexing. - /// The zero-based index in at which copying - /// begins. - /// is a null reference - /// (Nothing in Visual Basic). - /// is less than - /// 0. - /// is equal to or greater than - /// the length of the . -or- The number of elements in the source - /// is greater than the available space from to the end of the destination - /// . - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] - void ICollection.CopyTo(Array array, int index) - { - if (array == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); - if (index < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ConcurrentDictionary_IndexIsNegative); - - int locksAcquired = 0; - try - { - AcquireAllLocks(ref locksAcquired); - Tables tables = _tables; - - int count = 0; - - for (int i = 0; i < tables._locks.Length && count >= 0; i++) - { - count += tables._countPerLock[i]; - } - - if (array.Length - count < index || count < 0) //"count" itself or "count + index" can overflow - { - ThrowHelper.ThrowArgumentException(ExceptionResource.ConcurrentDictionary_ArrayNotLargeEnough); - } - - // To be consistent with the behavior of ICollection.CopyTo() in Dictionary, - // we recognize three types of target arrays: - // - an array of KeyValuePair structs - // - an array of DictionaryEntry structs - // - an array of objects - - KeyValuePair[] pairs = array as KeyValuePair[]; - 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; - } - - ThrowHelper.ThrowArgumentException(ExceptionResource.ConcurrentDictionary_ArrayIncorrectType, ExceptionArgument.array); - } - finally - { - ReleaseLocks(0, locksAcquired); - } - } - - /// - /// Gets a value indicating whether access to the is - /// synchronized with the SyncRoot. - /// - /// true if access to the is synchronized - /// (thread safe); otherwise, false. For , this property always - /// returns false. - bool ICollection.IsSynchronized - { - get { return false; } - } - - /// - /// Gets an object that can be used to synchronize access to the . This property is not supported. - /// - /// The SyncRoot property is not supported. - object ICollection.SyncRoot - { - get - { - ThrowHelper.ThrowNotSupportedException(ExceptionResource.ConcurrentCollection_SyncRoot_NotSupported); - return default; - } - } - - #endregion - - /// - /// 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. - /// - 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 ConcurrentDictionary 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, 0, newLocks, 0, tables._locks.Length); - for (int i = tables._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._buckets.Length; i++) - { - Node current = tables._buckets[i]; - while (current != null) - { - Node next = current._next; - int newBucketNo, newLockNo; - GetBucketAndLockNo(current._hashcode, out newBucketNo, out newLockNo, newBuckets.Length, newLocks.Length); - - newBuckets[newBucketNo] = new Node(current._key, current._value, current._hashcode, newBuckets[newBucketNo]); - - checked - { - newCountPerLock[newLockNo]++; - } - - current = next; - } - } - - // Adjust the budget - _budget = Math.Max(1, newBuckets.Length / newLocks.Length); - - // Replace tables with the new versions - _tables = new Tables(newBuckets, newLocks, newCountPerLock); - } - finally - { - // Release all locks that we took earlier - ReleaseLocks(0, locksAcquired); - } - } - - /// - /// Computes the bucket for a particular key. - /// - private static int GetBucket(int hashcode, int bucketCount) - { - int bucketNo = (hashcode & 0x7fffffff) % bucketCount; - Debug.Assert(bucketNo >= 0 && bucketNo < bucketCount); - return bucketNo; - } - - /// - /// Computes the bucket and lock number for a particular key. - /// - private static void GetBucketAndLockNo(int hashcode, out int bucketNo, out int lockNo, int bucketCount, int lockCount) - { - bucketNo = (hashcode & 0x7fffffff) % bucketCount; - lockNo = bucketNo % lockCount; - - Debug.Assert(bucketNo >= 0 && bucketNo < bucketCount); - Debug.Assert(lockNo >= 0 && lockNo < lockCount); - } - - /// - /// The number of concurrent writes for which to optimize by default. - /// - private static int DefaultConcurrencyLevel - { - get { return PlatformHelper.ProcessorCount; } - } - - /// - /// 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. - /// - 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); - } - - /// - /// 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. - /// - 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++; - } - } - } - } - - /// - /// Releases a contiguous range of locks. - /// - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "Reviewed for thread safety")] - private void ReleaseLocks(int fromInclusive, int toExclusive) - { - Debug.Assert(fromInclusive <= toExclusive); - - for (int i = fromInclusive; i < toExclusive; i++) - { - Monitor.Exit(_tables._locks[i]); - } - } - - /// - /// Gets a collection containing the keys in the dictionary. - /// - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] - private ReadOnlyCollection GetKeys() - { - int locksAcquired = 0; - try - { - AcquireAllLocks(ref locksAcquired); - - int count = GetCountInternal(); - if (count < 0) ThrowHelper.ThrowOutOfMemoryException(); - - List keys = new List(count); - for (int i = 0; i < _tables._buckets.Length; i++) - { - Node current = _tables._buckets[i]; - while (current != null) - { - keys.Add(current._key); - current = current._next; - } - } - - return new ReadOnlyCollection(keys); - } - finally - { - ReleaseLocks(0, locksAcquired); - } - } - - /// - /// Gets a collection containing the values in the dictionary. - /// - [SuppressMessage("Microsoft.Concurrency", "CA8001", Justification = "ConcurrencyCop just doesn't know about these locks")] - private ReadOnlyCollection GetValues() - { - int locksAcquired = 0; - try - { - AcquireAllLocks(ref locksAcquired); - - int count = GetCountInternal(); - if (count < 0) ThrowHelper.ThrowOutOfMemoryException(); - - List values = new List(count); - for (int i = 0; i < _tables._buckets.Length; i++) - { - Node current = _tables._buckets[i]; - while (current != null) - { - values.Add(current._value); - current = current._next; - } - } - - return new ReadOnlyCollection(values); - } - finally - { - ReleaseLocks(0, locksAcquired); - } - } - - /// - /// A node in a singly-linked list representing a particular hash table bucket. - /// - 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; - } - } - - /// - /// A private class to represent enumeration over the dictionary that implements the - /// IDictionaryEnumerator interface. - /// - private sealed class DictionaryEnumerator : IDictionaryEnumerator - { - IEnumerator> _enumerator; // Enumerator over the dictionary. - - internal DictionaryEnumerator(ConcurrentDictionary dictionary) - { - _enumerator = dictionary.GetEnumerator(); - } - - public DictionaryEntry Entry - { - get { return new DictionaryEntry(_enumerator.Current.Key, _enumerator.Current.Value); } - } - - public object Key - { - get { return _enumerator.Current.Key; } - } - - public object Value - { - get { return _enumerator.Current.Value; } - } - - public object Current - { - get { return Entry; } - } - - public bool MoveNext() - { - return _enumerator.MoveNext(); - } - - public void Reset() - { - _enumerator.Reset(); - } - } - } -} diff --git a/src/coreclr/src/System.Private.CoreLib/src/System/ThrowHelper.cs b/src/coreclr/src/System.Private.CoreLib/src/System/ThrowHelper.cs index 7ec7a57..e7f73b5 100644 --- a/src/coreclr/src/System.Private.CoreLib/src/System/ThrowHelper.cs +++ b/src/coreclr/src/System.Private.CoreLib/src/System/ThrowHelper.cs @@ -461,7 +461,6 @@ namespace System beginMethod, continuationOptions, continuationAction, - concurrencyLevel, text, callBack, type, @@ -470,7 +469,6 @@ namespace System values, task, s, - keyValuePair, input, pointer, start, @@ -576,15 +574,6 @@ namespace System MemoryDisposed, Memory_OutstandingReferences, InvalidOperation_WrongAsyncResultOrEndCalledMultiple, - ConcurrentDictionary_ConcurrencyLevelMustBePositive, - ConcurrentDictionary_CapacityMustNotBeNegative, - ConcurrentDictionary_TypeOfValueIncorrect, - ConcurrentDictionary_TypeOfKeyIncorrect, - ConcurrentDictionary_KeyAlreadyExisted, - ConcurrentDictionary_ItemKeyIsNull, - ConcurrentDictionary_IndexIsNegative, - ConcurrentDictionary_ArrayNotLargeEnough, - ConcurrentDictionary_ArrayIncorrectType, ConcurrentCollection_SyncRoot_NotSupported, ArgumentOutOfRange_Enum, InvalidOperation_HandleIsNotInitialized, -- 2.7.4