diff options
Diffstat (limited to 'src/mscorlib/src/System/Collections/Generic')
7 files changed, 282 insertions, 595 deletions
diff --git a/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs b/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs index b2fed9d78f..298ac3e177 100644 --- a/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs +++ b/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs @@ -17,6 +17,7 @@ namespace System.Collections.Generic using System; using System.Globalization; using System.Runtime.CompilerServices; + using System.Diagnostics; using System.Diagnostics.Contracts; using System.Runtime.Versioning; @@ -49,16 +50,7 @@ namespace System.Collections.Generic } internal static void ThrowOrIgnoreBadComparer(Object comparer) { - // This is hit when an invarant of QuickSort is violated due to a bad IComparer implementation (for - // example, imagine an IComparer that returns 0 when items are equal but -1 all other times). - // - // We could have thrown this exception on v4, but due to changes in v4.5 around how we partition arrays - // there are different sets of input where we would throw this exception. In order to reduce overall risk from - // an app compat persective, we're changing to never throw on v4. Instead, we'll return with a partially - // sorted array. - if(BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) { - throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", comparer)); - } + throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", comparer)); } } @@ -81,7 +73,6 @@ namespace System.Collections.Generic } } - [System.Security.SecuritySafeCritical] // auto-generated private static IArraySortHelper<T> CreateArraySortHelper() { if (typeof(IComparable<T>).IsAssignableFrom(typeof(T))) @@ -99,8 +90,8 @@ namespace System.Collections.Generic public void Sort(T[] keys, int index, int length, IComparer<T> comparer) { - Contract.Assert(keys != null, "Check the arguments in the caller!"); - Contract.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); + Debug.Assert(keys != null, "Check the arguments in the caller!"); + Debug.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); // Add a try block here to detect IComparers (or their // underlying IComparables, etc) that are bogus. @@ -111,22 +102,7 @@ namespace System.Collections.Generic comparer = Comparer<T>.Default; } -#if FEATURE_CORECLR - // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade - // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka - // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort. - - IntrospectiveSort(keys, index, length, comparer); -#else - if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) - { - IntrospectiveSort(keys, index, length, comparer); - } - else - { - DepthLimitedQuickSort(keys, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold); - } -#endif + IntrospectiveSort(keys, index, length, comparer.Compare); } catch (IndexOutOfRangeException) { @@ -157,6 +133,27 @@ namespace System.Collections.Generic #endregion + internal static void Sort(T[] keys, int index, int length, Comparison<T> comparer) + { + Debug.Assert(keys != null, "Check the arguments in the caller!"); + Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); + Debug.Assert(comparer != null, "Check the arguments in the caller!"); + + // Add a try block here to detect bogus comparisons + try + { + IntrospectiveSort(keys, index, length, comparer); + } + catch (IndexOutOfRangeException) + { + IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + } + catch (Exception e) + { + throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + } + } + internal static int InternalBinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer) { Contract.Requires(array != null, "Check the arguments in the caller!"); @@ -183,11 +180,11 @@ namespace System.Collections.Generic return ~lo; } - private static void SwapIfGreater(T[] keys, IComparer<T> comparer, int a, int b) + private static void SwapIfGreater(T[] keys, Comparison<T> comparer, int a, int b) { if (a != b) { - if (comparer.Compare(keys[a], keys[b]) > 0) + if (comparer(keys[a], keys[b]) > 0) { T key = keys[a]; keys[a] = keys[b]; @@ -198,7 +195,7 @@ namespace System.Collections.Generic private static void Swap(T[] a, int i, int j) { - if(i != j) + if (i != j) { T t = a[i]; a[i] = a[j]; @@ -206,63 +203,7 @@ namespace System.Collections.Generic } } - internal static void DepthLimitedQuickSort(T[] keys, int left, int right, IComparer<T> comparer, int depthLimit) - { - do - { - if (depthLimit == 0) - { - Heapsort(keys, left, right, comparer); - return; - } - - int i = left; - int j = right; - - // pre-sort the low, middle (pivot), and high values in place. - // this improves performance in the face of already sorted data, or - // data that is made up of multiple sorted runs appended together. - int middle = i + ((j - i) >> 1); - SwapIfGreater(keys, comparer, i, middle); // swap the low with the mid point - SwapIfGreater(keys, comparer, i, j); // swap the low with the high - SwapIfGreater(keys, comparer, middle, j); // swap the middle with the high - - T x = keys[middle]; - do - { - while (comparer.Compare(keys[i], x) < 0) i++; - while (comparer.Compare(x, keys[j]) < 0) j--; - Contract.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?"); - if (i > j) break; - if (i < j) - { - T key = keys[i]; - keys[i] = keys[j]; - keys[j] = key; - } - i++; - j--; - } while (i <= j); - - // The next iteration of the while loop is to "recursively" sort the larger half of the array and the - // following calls recursively sort the smaller half. So we subtract one from depthLimit here so - // both sorts see the new value. - depthLimit--; - - if (j - left <= right - i) - { - if (left < j) DepthLimitedQuickSort(keys, left, j, comparer, depthLimit); - left = i; - } - else - { - if (i < right) DepthLimitedQuickSort(keys, i, right, comparer, depthLimit); - right = j; - } - } while (left < right); - } - - internal static void IntrospectiveSort(T[] keys, int left, int length, IComparer<T> comparer) + internal static void IntrospectiveSort(T[] keys, int left, int length, Comparison<T> comparer) { Contract.Requires(keys != null); Contract.Requires(comparer != null); @@ -277,7 +218,7 @@ namespace System.Collections.Generic IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer); } - private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer<T> comparer) + private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, Comparison<T> comparer) { Contract.Requires(keys != null); Contract.Requires(comparer != null); @@ -324,7 +265,7 @@ namespace System.Collections.Generic } } - private static int PickPivotAndPartition(T[] keys, int lo, int hi, IComparer<T> comparer) + private static int PickPivotAndPartition(T[] keys, int lo, int hi, Comparison<T> comparer) { Contract.Requires(keys != null); Contract.Requires(comparer != null); @@ -347,8 +288,8 @@ namespace System.Collections.Generic while (left < right) { - while (comparer.Compare(keys[++left], pivot) < 0) ; - while (comparer.Compare(pivot, keys[--right]) < 0) ; + while (comparer(keys[++left], pivot) < 0) ; + while (comparer(pivot, keys[--right]) < 0) ; if (left >= right) break; @@ -361,7 +302,7 @@ namespace System.Collections.Generic return left; } - private static void Heapsort(T[] keys, int lo, int hi, IComparer<T> comparer) + private static void Heapsort(T[] keys, int lo, int hi, Comparison<T> comparer) { Contract.Requires(keys != null); Contract.Requires(comparer != null); @@ -381,7 +322,7 @@ namespace System.Collections.Generic } } - private static void DownHeap(T[] keys, int i, int n, int lo, IComparer<T> comparer) + private static void DownHeap(T[] keys, int i, int n, int lo, Comparison<T> comparer) { Contract.Requires(keys != null); Contract.Requires(comparer != null); @@ -393,11 +334,11 @@ namespace System.Collections.Generic while (i <= n / 2) { child = 2 * i; - if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0) + if (child < n && comparer(keys[lo + child - 1], keys[lo + child]) < 0) { child++; } - if (!(comparer.Compare(d, keys[lo + child - 1]) < 0)) + if (!(comparer(d, keys[lo + child - 1]) < 0)) break; keys[lo + i - 1] = keys[lo + child - 1]; i = child; @@ -405,7 +346,7 @@ namespace System.Collections.Generic keys[lo + i - 1] = d; } - private static void InsertionSort(T[] keys, int lo, int hi, IComparer<T> comparer) + private static void InsertionSort(T[] keys, int lo, int hi, Comparison<T> comparer) { Contract.Requires(keys != null); Contract.Requires(lo >= 0); @@ -418,7 +359,7 @@ namespace System.Collections.Generic { j = i; t = keys[i + 1]; - while (j >= lo && comparer.Compare(t, keys[j]) < 0) + while (j >= lo && comparer(t, keys[j]) < 0) { keys[j + 1] = keys[j]; j--; @@ -439,49 +380,18 @@ namespace System.Collections.Generic public void Sort(T[] keys, int index, int length, IComparer<T> comparer) { - Contract.Assert(keys != null, "Check the arguments in the caller!"); - Contract.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); + Debug.Assert(keys != null, "Check the arguments in the caller!"); + Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); try { - if (comparer == null || comparer == Comparer<T>.Default) { - -#if FEATURE_CORECLR - // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade - // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka - // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort. - + if (comparer == null || comparer == Comparer<T>.Default) + { IntrospectiveSort(keys, index, length); -#else - // call the faster version of our sort algorithm if the user doesn't provide a comparer - if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) - { - IntrospectiveSort(keys, index, length); - } - else - { - DepthLimitedQuickSort(keys, index, length + index - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold); - } -#endif } else { -#if FEATURE_CORECLR - // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade - // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka - // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort. - - ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer); -#else - if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) - { - ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer); - } - else - { - ArraySortHelper<T>.DepthLimitedQuickSort(keys, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold); - } -#endif + ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer.Compare); } } catch (IndexOutOfRangeException) @@ -496,8 +406,8 @@ namespace System.Collections.Generic public int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer) { - Contract.Assert(array != null, "Check the arguments in the caller!"); - Contract.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!"); + Debug.Assert(array != null, "Check the arguments in the caller!"); + Debug.Assert(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!"); try { @@ -583,78 +493,6 @@ namespace System.Collections.Generic } } - private static void DepthLimitedQuickSort(T[] keys, int left, int right, int depthLimit) - { - Contract.Requires(keys != null); - Contract.Requires(0 <= left && left < keys.Length); - Contract.Requires(0 <= right && right < keys.Length); - - // The code in this function looks very similar to QuickSort in ArraySortHelper<T> class. - // The difference is that T is constrainted to IComparable<T> here. - // So the IL code will be different. This function is faster than the one in ArraySortHelper<T>. - - do - { - if (depthLimit == 0) - { - Heapsort(keys, left, right); - return; - } - - int i = left; - int j = right; - - // pre-sort the low, middle (pivot), and high values in place. - // this improves performance in the face of already sorted data, or - // data that is made up of multiple sorted runs appended together. - int middle = i + ((j - i) >> 1); - SwapIfGreaterWithItems(keys, i, middle); // swap the low with the mid point - SwapIfGreaterWithItems(keys, i, j); // swap the low with the high - SwapIfGreaterWithItems(keys, middle, j); // swap the middle with the high - - T x = keys[middle]; - do - { - if (x == null) - { - // if x null, the loop to find two elements to be switched can be reduced. - while (keys[j] != null) j--; - } - else - { - while (x.CompareTo(keys[i]) > 0) i++; - while (x.CompareTo(keys[j]) < 0) j--; - } - Contract.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?"); - if (i > j) break; - if (i < j) - { - T key = keys[i]; - keys[i] = keys[j]; - keys[j] = key; - } - i++; - j--; - } while (i <= j); - - // The next iteration of the while loop is to "recursively" sort the larger half of the array and the - // following calls recursively sort the smaller half. So we subtract one from depthLimit here so - // both sorts see the new value. - depthLimit--; - - if (j - left <= right - i) - { - if (left < j) DepthLimitedQuickSort(keys, left, j, depthLimit); - left = i; - } - else - { - if (i < right) DepthLimitedQuickSort(keys, i, right, depthLimit); - right = j; - } - } while (left < right); - } - internal static void IntrospectiveSort(T[] keys, int left, int length) { Contract.Requires(keys != null); @@ -824,7 +662,7 @@ namespace System.Collections.Generic } } - #endregion +#endregion #region ArraySortHelper for paired key and value arrays @@ -851,7 +689,6 @@ namespace System.Collections.Generic } } - [System.Security.SecuritySafeCritical] // auto-generated private static IArraySortHelper<TKey, TValue> CreateArraySortHelper() { if (typeof(IComparable<TKey>).IsAssignableFrom(typeof(TKey))) @@ -867,8 +704,8 @@ namespace System.Collections.Generic public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer) { - Contract.Assert(keys != null, "Check the arguments in the caller!"); // Precondition on interface method - Contract.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); + Debug.Assert(keys != null, "Check the arguments in the caller!"); // Precondition on interface method + Debug.Assert(index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); // Add a try block here to detect IComparers (or their // underlying IComparables, etc) that are bogus. @@ -879,22 +716,7 @@ namespace System.Collections.Generic comparer = Comparer<TKey>.Default; } -#if FEATURE_CORECLR - // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade - // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka - // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort. - IntrospectiveSort(keys, values, index, length, comparer); -#else - if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) - { - IntrospectiveSort(keys, values, index, length, comparer); - } - else - { - DepthLimitedQuickSort(keys, values, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold); - } -#endif } catch (IndexOutOfRangeException) { @@ -947,68 +769,6 @@ namespace System.Collections.Generic } } - internal static void DepthLimitedQuickSort(TKey[] keys, TValue[] values, int left, int right, IComparer<TKey> comparer, int depthLimit) - { - do - { - if (depthLimit == 0) - { - Heapsort(keys, values, left, right, comparer); - return; - } - - int i = left; - int j = right; - - // pre-sort the low, middle (pivot), and high values in place. - // this improves performance in the face of already sorted data, or - // data that is made up of multiple sorted runs appended together. - int middle = i + ((j - i) >> 1); - SwapIfGreaterWithItems(keys, values, comparer, i, middle); // swap the low with the mid point - SwapIfGreaterWithItems(keys, values, comparer, i, j); // swap the low with the high - SwapIfGreaterWithItems(keys, values, comparer, middle, j); // swap the middle with the high - - TKey x = keys[middle]; - do - { - while (comparer.Compare(keys[i], x) < 0) i++; - while (comparer.Compare(x, keys[j]) < 0) j--; - Contract.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?"); - if (i > j) break; - if (i < j) - { - TKey key = keys[i]; - keys[i] = keys[j]; - keys[j] = key; - if (values != null) - { - TValue value = values[i]; - values[i] = values[j]; - values[j] = value; - } - } - i++; - j--; - } while (i <= j); - - // The next iteration of the while loop is to "recursively" sort the larger half of the array and the - // following calls recursively sort the smaller half. So we subtract one from depthLimit here so - // both sorts see the new value. - depthLimit--; - - if (j - left <= right - i) - { - if (left < j) DepthLimitedQuickSort(keys, values, left, j, comparer, depthLimit); - left = i; - } - else - { - if (i < right) DepthLimitedQuickSort(keys, values, i, right, comparer, depthLimit); - right = j; - } - } while (left < right); - } - internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length, IComparer<TKey> comparer) { Contract.Requires(keys != null); @@ -1199,8 +959,8 @@ namespace System.Collections.Generic { public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer) { - Contract.Assert(keys != null, "Check the arguments in the caller!"); - Contract.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); + Debug.Assert(keys != null, "Check the arguments in the caller!"); + Debug.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); // Add a try block here to detect IComparers (or their // underlying IComparables, etc) that are bogus. @@ -1208,44 +968,12 @@ namespace System.Collections.Generic { if (comparer == null || comparer == Comparer<TKey>.Default) { -#if FEATURE_CORECLR - // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade - // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka - // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort. - IntrospectiveSort(keys, values, index, length); -#else - // call the faster version of our sort algorithm if the user doesn't provide a comparer - if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) - { - IntrospectiveSort(keys, values, index, length); - } - else - { - DepthLimitedQuickSort(keys, values, index, length + index - 1, IntrospectiveSortUtilities.QuickSortDepthThreshold); - } -#endif } else { -#if FEATURE_CORECLR - // Since QuickSort and IntrospectiveSort produce different sorting sequence for equal keys the upgrade - // to IntrospectiveSort was quirked. However since the phone builds always shipped with the new sort aka - // IntrospectiveSort and we would want to continue using this sort moving forward CoreCLR always uses the new sort. - ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, index, length, comparer); -#else - if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) - { - ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, index, length, comparer); - } - else - { - ArraySortHelper<TKey, TValue>.DepthLimitedQuickSort(keys, values, index, length + index - 1, comparer, IntrospectiveSortUtilities.QuickSortDepthThreshold); - } -#endif } - } catch (IndexOutOfRangeException) { @@ -1292,80 +1020,6 @@ namespace System.Collections.Generic } } - private static void DepthLimitedQuickSort(TKey[] keys, TValue[] values, int left, int right, int depthLimit) - { - // The code in this function looks very similar to QuickSort in ArraySortHelper<T> class. - // The difference is that T is constrainted to IComparable<T> here. - // So the IL code will be different. This function is faster than the one in ArraySortHelper<T>. - - do - { - if (depthLimit == 0) - { - Heapsort(keys, values, left, right); - return; - } - - int i = left; - int j = right; - - // pre-sort the low, middle (pivot), and high values in place. - // this improves performance in the face of already sorted data, or - // data that is made up of multiple sorted runs appended together. - int middle = i + ((j - i) >> 1); - SwapIfGreaterWithItems(keys, values, i, middle); // swap the low with the mid point - SwapIfGreaterWithItems(keys, values, i, j); // swap the low with the high - SwapIfGreaterWithItems(keys, values, middle, j); // swap the middle with the high - - TKey x = keys[middle]; - do - { - if (x == null) - { - // if x null, the loop to find two elements to be switched can be reduced. - while (keys[j] != null) j--; - } - else - { - while (x.CompareTo(keys[i]) > 0) i++; - while (x.CompareTo(keys[j]) < 0) j--; - } - Contract.Assert(i >= left && j <= right, "(i>=left && j<=right) Sort failed - Is your IComparer bogus?"); - if (i > j) break; - if (i < j) - { - TKey key = keys[i]; - keys[i] = keys[j]; - keys[j] = key; - if (values != null) - { - TValue value = values[i]; - values[i] = values[j]; - values[j] = value; - } - } - i++; - j--; - } while (i <= j); - - // The next iteration of the while loop is to "recursively" sort the larger half of the array and the - // following calls recursively sort the smaller half. So we subtract one from depthLimit here so - // both sorts see the new value. - depthLimit--; - - if (j - left <= right - i) - { - if (left < j) DepthLimitedQuickSort(keys, values, left, j, depthLimit); - left = i; - } - else - { - if (i < right) DepthLimitedQuickSort(keys, values, i, right, depthLimit); - right = j; - } - } while (left < right); - } - internal static void IntrospectiveSort(TKey[] keys, TValue[] values, int left, int length) { Contract.Requires(keys != null); @@ -1554,5 +1208,3 @@ namespace System.Collections.Generic #endregion } - - diff --git a/src/mscorlib/src/System/Collections/Generic/Comparer.cs b/src/mscorlib/src/System/Collections/Generic/Comparer.cs index 9f1a8bff6f..4f06b0af69 100644 --- a/src/mscorlib/src/System/Collections/Generic/Comparer.cs +++ b/src/mscorlib/src/System/Collections/Generic/Comparer.cs @@ -7,6 +7,7 @@ using System; using System.Collections; using System.Collections.Generic; +using System.Diagnostics; using System.Diagnostics.Contracts; //using System.Globalization; using System.Runtime.CompilerServices; @@ -33,7 +34,7 @@ namespace System.Collections.Generic Contract.Ensures(Contract.Result<Comparer<T>>() != null); if (comparison == null) - throw new ArgumentNullException("comparison"); + throw new ArgumentNullException(nameof(comparison)); return new ComparisonComparer<T>(comparison); } @@ -42,7 +43,6 @@ namespace System.Collections.Generic // Note that logic in this method is replicated in vm\compile.cpp to ensure that NGen // saves the right instantiations // - [System.Security.SecuritySafeCritical] // auto-generated private static Comparer<T> CreateComparer() { object result = null; @@ -139,7 +139,7 @@ namespace System.Collections.Generic [Serializable] internal sealed class NullableComparer<T> : Comparer<T?> where T : struct, IComparable<T> { - public override int Compare(Nullable<T> x, Nullable<T> y) { + public override int Compare(T? x, T? y) { if (x.HasValue) { if (y.HasValue) return x.value.CompareTo(y.value); return 1; @@ -196,7 +196,7 @@ namespace System.Collections.Generic { public Int32EnumComparer() { - Contract.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); } // Used by the serialization engine. @@ -216,7 +216,6 @@ namespace System.Collections.Generic public override int GetHashCode() => GetType().GetHashCode(); - [SecurityCritical] public void GetObjectData(SerializationInfo info, StreamingContext context) { // Previously Comparer<T> was not specialized for enums, @@ -232,7 +231,7 @@ namespace System.Collections.Generic { public UInt32EnumComparer() { - Contract.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); } // Used by the serialization engine. @@ -252,7 +251,6 @@ namespace System.Collections.Generic public override int GetHashCode() => GetType().GetHashCode(); - [SecurityCritical] public void GetObjectData(SerializationInfo info, StreamingContext context) { info.SetType(typeof(ObjectComparer<T>)); @@ -264,7 +262,7 @@ namespace System.Collections.Generic { public Int64EnumComparer() { - Contract.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); } // Used by the serialization engine. @@ -284,7 +282,6 @@ namespace System.Collections.Generic public override int GetHashCode() => GetType().GetHashCode(); - [SecurityCritical] public void GetObjectData(SerializationInfo info, StreamingContext context) { info.SetType(typeof(ObjectComparer<T>)); @@ -296,7 +293,7 @@ namespace System.Collections.Generic { public UInt64EnumComparer() { - Contract.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); } // Used by the serialization engine. @@ -316,7 +313,6 @@ namespace System.Collections.Generic public override int GetHashCode() => GetType().GetHashCode(); - [SecurityCritical] public void GetObjectData(SerializationInfo info, StreamingContext context) { info.SetType(typeof(ObjectComparer<T>)); diff --git a/src/mscorlib/src/System/Collections/Generic/DebugView.cs b/src/mscorlib/src/System/Collections/Generic/DebugView.cs index 57b91eff51..d0711e551e 100644 --- a/src/mscorlib/src/System/Collections/Generic/DebugView.cs +++ b/src/mscorlib/src/System/Collections/Generic/DebugView.cs @@ -110,7 +110,7 @@ namespace System.Collections.Generic { public Mscorlib_KeyedCollectionDebugView(KeyedCollection<K, T> keyedCollection) { if (keyedCollection == null) { - throw new ArgumentNullException("keyedCollection"); + throw new ArgumentNullException(nameof(keyedCollection)); } Contract.EndContractBlock(); diff --git a/src/mscorlib/src/System/Collections/Generic/Dictionary.cs b/src/mscorlib/src/System/Collections/Generic/Dictionary.cs index 9cbfff5a57..c2b2da9ad2 100644 --- a/src/mscorlib/src/System/Collections/Generic/Dictionary.cs +++ b/src/mscorlib/src/System/Collections/Generic/Dictionary.cs @@ -91,12 +91,12 @@ namespace System.Collections.Generic { if (capacity > 0) Initialize(capacity); this.comparer = comparer ?? EqualityComparer<TKey>.Default; -#if FEATURE_RANDOMIZED_STRING_HASHING && FEATURE_CORECLR +#if FEATURE_RANDOMIZED_STRING_HASHING if (HashHelpers.s_UseRandomizedStringHashing && comparer == EqualityComparer<string>.Default) { this.comparer = (IEqualityComparer<TKey>) NonRandomizedStringEqualityComparer.Default; } -#endif // FEATURE_RANDOMIZED_STRING_HASHING && FEATURE_CORECLR +#endif // FEATURE_RANDOMIZED_STRING_HASHING } public Dictionary(IDictionary<TKey,TValue> dictionary): this(dictionary, null) {} @@ -129,6 +129,21 @@ namespace System.Collections.Generic { } } + public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection): + this(collection, null) { } + + public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer): + this((collection as ICollection<KeyValuePair<TKey, TValue>>)?.Count ?? 0, comparer) + { + if (collection == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); + } + + foreach (KeyValuePair<TKey, TValue> pair in collection) { + Add(pair.Key, pair.Value); + } + } + protected Dictionary(SerializationInfo info, StreamingContext context) { //We can't do anything with the keys and values until the entire graph has been deserialized //and we have a resonable estimate that GetHashCode is not going to fail. For the time being, @@ -263,7 +278,7 @@ namespace System.Collections.Generic { } if (index < 0 || index > array.Length ) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (array.Length - index < Count) { @@ -287,7 +302,6 @@ namespace System.Collections.Generic { return new Enumerator(this, Enumerator.KeyValuePair); } - [System.Security.SecurityCritical] // auto-generated_required public virtual void GetObjectData(SerializationInfo info, StreamingContext context) { if (info==null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.info); @@ -347,11 +361,7 @@ namespace System.Collections.Generic { for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) { if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { if (add) { -#if FEATURE_CORECLR ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key); -#else - ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); -#endif } entries[i].value = value; version++; @@ -386,8 +396,6 @@ namespace System.Collections.Generic { version++; #if FEATURE_RANDOMIZED_STRING_HASHING - -#if FEATURE_CORECLR // In case we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing // in this case will be EqualityComparer<string>.Default. // Note, randomized string hashing is turned on by default on coreclr so EqualityComparer<string>.Default will @@ -398,14 +406,6 @@ namespace System.Collections.Generic { comparer = (IEqualityComparer<TKey>) EqualityComparer<string>.Default; Resize(entries.Length, true); } -#else - if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) - { - comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer); - Resize(entries.Length, true); - } -#endif // FEATURE_CORECLR - #endif } @@ -459,7 +459,7 @@ namespace System.Collections.Generic { } private void Resize(int newSize, bool forceNewHashCodes) { - Contract.Assert(newSize >= entries.Length); + Debug.Assert(newSize >= entries.Length); int[] newBuckets = new int[newSize]; for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1; Entry[] newEntries = new Entry[newSize]; @@ -523,16 +523,19 @@ namespace System.Collections.Generic { return false; } - // This is a convenience method for the internal callers that were converted from using Hashtable. - // Many were combining key doesn't exist and key exists but null value (for non-value types) checks. - // This allows them to continue getting that behavior with minimal code delta. This is basically - // TryGetValue without the out param - internal TValue GetValueOrDefault(TKey key) { + // Method similar to TryGetValue that returns the value instead of putting it in an out param. + public TValue GetValueOrDefault(TKey key) => GetValueOrDefault(key, default(TValue)); + + // Method similar to TryGetValue that returns the value instead of putting it in an out param. If the entry + // doesn't exist, returns the defaultValue instead. + public TValue GetValueOrDefault(TKey key, TValue defaultValue) + { int i = FindEntry(key); - if (i >= 0) { + if (i >= 0) + { return entries[i].value; } - return default(TValue); + return defaultValue; } bool ICollection<KeyValuePair<TKey,TValue>>.IsReadOnly { @@ -557,7 +560,7 @@ namespace System.Collections.Generic { } if (index < 0 || index > array.Length) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (array.Length - index < Count) { @@ -580,7 +583,7 @@ namespace System.Collections.Generic { else { object[] objects = array as object[]; if (objects == null) { - ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } try { @@ -593,7 +596,7 @@ namespace System.Collections.Generic { } } catch(ArrayTypeMismatchException) { - ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } } } @@ -733,7 +736,7 @@ namespace System.Collections.Generic { public bool MoveNext() { if (version != dictionary.version) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } // Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends. @@ -762,7 +765,7 @@ namespace System.Collections.Generic { object IEnumerator.Current { get { if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); } if (getEnumeratorRetType == DictEntry) { @@ -775,7 +778,7 @@ namespace System.Collections.Generic { void IEnumerator.Reset() { if (version != dictionary.version) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } index = 0; @@ -785,7 +788,7 @@ namespace System.Collections.Generic { DictionaryEntry IDictionaryEnumerator.Entry { get { if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); } return new DictionaryEntry(current.Key, current.Value); @@ -795,7 +798,7 @@ namespace System.Collections.Generic { object IDictionaryEnumerator.Key { get { if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); } return current.Key; @@ -805,7 +808,7 @@ namespace System.Collections.Generic { object IDictionaryEnumerator.Value { get { if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); } return current.Value; @@ -837,7 +840,7 @@ namespace System.Collections.Generic { } if (index < 0 || index > array.Length) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (array.Length - index < dictionary.Count) { @@ -898,7 +901,7 @@ namespace System.Collections.Generic { } if (index < 0 || index > array.Length) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (array.Length - index < dictionary.Count) { @@ -912,7 +915,7 @@ namespace System.Collections.Generic { else { object[] objects = array as object[]; if (objects == null) { - ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } int count = dictionary.count; @@ -923,7 +926,7 @@ namespace System.Collections.Generic { } } catch(ArrayTypeMismatchException) { - ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } } } @@ -956,7 +959,7 @@ namespace System.Collections.Generic { public bool MoveNext() { if (version != dictionary.version) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } while ((uint)index < (uint)dictionary.count) { @@ -982,7 +985,7 @@ namespace System.Collections.Generic { Object System.Collections.IEnumerator.Current { get { if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); } return currentKey; @@ -991,7 +994,7 @@ namespace System.Collections.Generic { void System.Collections.IEnumerator.Reset() { if (version != dictionary.version) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } index = 0; @@ -1024,7 +1027,7 @@ namespace System.Collections.Generic { } if (index < 0 || index > array.Length) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (array.Length - index < dictionary.Count) { @@ -1085,7 +1088,7 @@ namespace System.Collections.Generic { } if (index < 0 || index > array.Length) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (array.Length - index < dictionary.Count) @@ -1098,7 +1101,7 @@ namespace System.Collections.Generic { else { object[] objects = array as object[]; if (objects == null) { - ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } int count = dictionary.count; @@ -1109,7 +1112,7 @@ namespace System.Collections.Generic { } } catch(ArrayTypeMismatchException) { - ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } } } @@ -1142,7 +1145,7 @@ namespace System.Collections.Generic { public bool MoveNext() { if (version != dictionary.version) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } while ((uint)index < (uint)dictionary.count) { @@ -1167,7 +1170,7 @@ namespace System.Collections.Generic { Object System.Collections.IEnumerator.Current { get { if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); } return currentValue; @@ -1176,7 +1179,7 @@ namespace System.Collections.Generic { void System.Collections.IEnumerator.Reset() { if (version != dictionary.version) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } index = 0; currentValue = default(TValue); diff --git a/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs b/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs index b845d64fed..3731114119 100644 --- a/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs +++ b/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs @@ -32,7 +32,6 @@ namespace System.Collections.Generic // Note that logic in this method is replicated in vm\compile.cpp to ensure that NGen // saves the right instantiations // - [System.Security.SecuritySafeCritical] // auto-generated private static EqualityComparer<T> CreateComparer() { Contract.Ensures(Contract.Result<EqualityComparer<T>>() != null); @@ -144,10 +143,7 @@ namespace System.Collections.Generic } [Pure] - public override int GetHashCode(T obj) { - if (obj == null) return 0; - return obj.GetHashCode(); - } + public override int GetHashCode(T obj) => obj?.GetHashCode() ?? 0; internal override int IndexOf(T[] array, T value, int startIndex, int count) { int endIndex = startIndex + count; @@ -179,22 +175,21 @@ namespace System.Collections.Generic return -1; } - // Equals method for the comparer itself. - public override bool Equals(Object obj){ - GenericEqualityComparer<T> comparer = obj as GenericEqualityComparer<T>; - return comparer != null; - } + // Equals method for the comparer itself. + // If in the future this type is made sealed, change the is check to obj != null && GetType() == obj.GetType(). + public override bool Equals(Object obj) => + obj is GenericEqualityComparer<T>; - public override int GetHashCode() { - return this.GetType().Name.GetHashCode(); - } + // If in the future this type is made sealed, change typeof(...) to GetType(). + public override int GetHashCode() => + typeof(GenericEqualityComparer<T>).GetHashCode(); } [Serializable] - internal class NullableEqualityComparer<T> : EqualityComparer<Nullable<T>> where T : struct, IEquatable<T> + internal sealed class NullableEqualityComparer<T> : EqualityComparer<T?> where T : struct, IEquatable<T> { [Pure] - public override bool Equals(Nullable<T> x, Nullable<T> y) { + public override bool Equals(T? x, T? y) { if (x.HasValue) { if (y.HasValue) return x.value.Equals(y.value); return false; @@ -204,11 +199,9 @@ namespace System.Collections.Generic } [Pure] - public override int GetHashCode(Nullable<T> obj) { - return obj.GetHashCode(); - } + public override int GetHashCode(T? obj) => obj.GetHashCode(); - internal override int IndexOf(Nullable<T>[] array, Nullable<T> value, int startIndex, int count) { + internal override int IndexOf(T?[] array, T? value, int startIndex, int count) { int endIndex = startIndex + count; if (!value.HasValue) { for (int i = startIndex; i < endIndex; i++) { @@ -223,7 +216,7 @@ namespace System.Collections.Generic return -1; } - internal override int LastIndexOf(Nullable<T>[] array, Nullable<T> value, int startIndex, int count) { + internal override int LastIndexOf(T?[] array, T? value, int startIndex, int count) { int endIndex = startIndex - count + 1; if (!value.HasValue) { for (int i = startIndex; i >= endIndex; i--) { @@ -238,19 +231,16 @@ namespace System.Collections.Generic return -1; } - // Equals method for the comparer itself. - public override bool Equals(Object obj){ - NullableEqualityComparer<T> comparer = obj as NullableEqualityComparer<T>; - return comparer != null; - } + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); - public override int GetHashCode() { - return this.GetType().Name.GetHashCode(); - } + public override int GetHashCode() => + GetType().GetHashCode(); } [Serializable] - internal class ObjectEqualityComparer<T>: EqualityComparer<T> + internal sealed class ObjectEqualityComparer<T>: EqualityComparer<T> { [Pure] public override bool Equals(T x, T y) { @@ -263,10 +253,7 @@ namespace System.Collections.Generic } [Pure] - public override int GetHashCode(T obj) { - if (obj == null) return 0; - return obj.GetHashCode(); - } + public override int GetHashCode(T obj) => obj?.GetHashCode() ?? 0; internal override int IndexOf(T[] array, T value, int startIndex, int count) { int endIndex = startIndex + count; @@ -298,25 +285,21 @@ namespace System.Collections.Generic return -1; } - // Equals method for the comparer itself. - public override bool Equals(Object obj){ - ObjectEqualityComparer<T> comparer = obj as ObjectEqualityComparer<T>; - return comparer != null; - } + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); - public override int GetHashCode() { - return this.GetType().Name.GetHashCode(); - } + public override int GetHashCode() => + GetType().GetHashCode(); } -#if FEATURE_CORECLR // NonRandomizedStringEqualityComparer is the comparer used by default with the Dictionary<string,...> // As the randomized string hashing is turned on by default on coreclr, we need to keep the performance not affected // as much as possible in the main stream scenarios like Dictionary<string,> // We use NonRandomizedStringEqualityComparer as default comparer as it doesnt use the randomized string hashing which // keep the perofrmance not affected till we hit collision threshold and then we switch to the comparer which is using // randomized string hashing GenericEqualityComparer<string> - + [Serializable] internal class NonRandomizedStringEqualityComparer : GenericEqualityComparer<string> { static IEqualityComparer<string> s_nonRandomizedComparer; @@ -335,12 +318,11 @@ namespace System.Collections.Generic return obj.GetLegacyNonRandomizedHashCode(); } } -#endif // FEATURE_CORECLR // Performance of IndexOf on byte array is very important for some scenarios. // We will call the C runtime function memchr, which is optimized. [Serializable] - internal class ByteEqualityComparer: EqualityComparer<byte> + internal sealed class ByteEqualityComparer: EqualityComparer<byte> { [Pure] public override bool Equals(byte x, byte y) { @@ -352,14 +334,13 @@ namespace System.Collections.Generic return b.GetHashCode(); } - [System.Security.SecuritySafeCritical] // auto-generated internal unsafe override int IndexOf(byte[] array, byte value, int startIndex, int count) { if (array==null) - throw new ArgumentNullException("array"); + throw new ArgumentNullException(nameof(array)); if (startIndex < 0) - throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index")); + throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_Index")); if (count < 0) - throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count")); + throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_Count")); if (count > array.Length - startIndex) throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); Contract.EndContractBlock(); @@ -377,15 +358,12 @@ namespace System.Collections.Generic return -1; } - // Equals method for the comparer itself. - public override bool Equals(Object obj){ - ByteEqualityComparer comparer = obj as ByteEqualityComparer; - return comparer != null; - } + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); - public override int GetHashCode() { - return this.GetType().Name.GetHashCode(); - } + public override int GetHashCode() => + GetType().GetHashCode(); } [Serializable] @@ -409,7 +387,6 @@ namespace System.Collections.Generic // This is used by the serialization engine. protected EnumEqualityComparer(SerializationInfo information, StreamingContext context) { } - [SecurityCritical] public void GetObjectData(SerializationInfo info, StreamingContext context) { // For back-compat we need to serialize the comparers for enums with underlying types other than int as ObjectEqualityComparer if (Type.GetTypeCode(Enum.GetUnderlyingType(typeof(T))) != TypeCode.Int32) { @@ -417,14 +394,35 @@ namespace System.Collections.Generic } } - // Equals method for the comparer itself. - public override bool Equals(Object obj){ - EnumEqualityComparer<T> comparer = obj as EnumEqualityComparer<T>; - return comparer != null; + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); + + public override int GetHashCode() => + GetType().GetHashCode(); + + internal override int IndexOf(T[] array, T value, int startIndex, int count) + { + int toFind = JitHelpers.UnsafeEnumCast(value); + int endIndex = startIndex + count; + for (int i = startIndex; i < endIndex; i++) + { + int current = JitHelpers.UnsafeEnumCast(array[i]); + if (toFind == current) return i; + } + return -1; } - public override int GetHashCode() { - return this.GetType().Name.GetHashCode(); + internal override int LastIndexOf(T[] array, T value, int startIndex, int count) + { + int toFind = JitHelpers.UnsafeEnumCast(value); + int endIndex = startIndex - count + 1; + for (int i = startIndex; i >= endIndex; i--) + { + int current = JitHelpers.UnsafeEnumCast(array[i]); + if (toFind == current) return i; + } + return -1; } } @@ -474,28 +472,48 @@ namespace System.Collections.Generic return x_final.GetHashCode(); } - // Equals method for the comparer itself. - public override bool Equals(Object obj){ - LongEnumEqualityComparer<T> comparer = obj as LongEnumEqualityComparer<T>; - return comparer != null; - } + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); - public override int GetHashCode() { - return this.GetType().Name.GetHashCode(); - } + public override int GetHashCode() => + GetType().GetHashCode(); public LongEnumEqualityComparer() { } // This is used by the serialization engine. public LongEnumEqualityComparer(SerializationInfo information, StreamingContext context) { } - [SecurityCritical] public void GetObjectData(SerializationInfo info, StreamingContext context) { // The LongEnumEqualityComparer does not exist on 4.0 so we need to serialize this comparer as ObjectEqualityComparer // to allow for roundtrip between 4.0 and 4.5. info.SetType(typeof(ObjectEqualityComparer<T>)); } + + internal override int IndexOf(T[] array, T value, int startIndex, int count) + { + long toFind = JitHelpers.UnsafeEnumCastLong(value); + int endIndex = startIndex + count; + for (int i = startIndex; i < endIndex; i++) + { + long current = JitHelpers.UnsafeEnumCastLong(array[i]); + if (toFind == current) return i; + } + return -1; + } + + internal override int LastIndexOf(T[] array, T value, int startIndex, int count) + { + long toFind = JitHelpers.UnsafeEnumCastLong(value); + int endIndex = startIndex - count + 1; + for (int i = startIndex; i >= endIndex; i--) + { + long current = JitHelpers.UnsafeEnumCastLong(array[i]); + if (toFind == current) return i; + } + return -1; + } } #if FEATURE_RANDOMIZED_STRING_HASHING @@ -528,14 +546,12 @@ namespace System.Collections.Generic } [Pure] - [SecuritySafeCritical] public int GetHashCode(String obj) { if(obj == null) return 0; return String.InternalMarvin32HashString(obj, obj.Length, _entropy); } [Pure] - [SecuritySafeCritical] public int GetHashCode(Object obj) { if(obj == null) return 0; @@ -552,7 +568,7 @@ namespace System.Collections.Generic } public override int GetHashCode() { - return (this.GetType().Name.GetHashCode() ^ ((int) (_entropy & 0x7FFFFFFF))); + return (this.GetType().GetHashCode() ^ ((int) (_entropy & 0x7FFFFFFF))); } @@ -587,7 +603,6 @@ namespace System.Collections.Generic } [Pure] - [SecuritySafeCritical] public int GetHashCode(Object obj) { if(obj == null) return 0; @@ -604,7 +619,7 @@ namespace System.Collections.Generic } public override int GetHashCode() { - return (this.GetType().Name.GetHashCode() ^ ((int) (_entropy & 0x7FFFFFFF))); + return (this.GetType().GetHashCode() ^ ((int) (_entropy & 0x7FFFFFFF))); } IEqualityComparer IWellKnownStringEqualityComparer.GetRandomizedEqualityComparer() { diff --git a/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs b/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs index 17e1c531f1..ad9f7472aa 100644 --- a/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs +++ b/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs @@ -18,6 +18,16 @@ namespace System.Collections.Generic { using System; using System.Text; + // Provides the Create factory method for KeyValuePair<TKey, TValue>. + public static class KeyValuePair + { + // Creates a new KeyValuePair<TKey, TValue> from the given values. + public static KeyValuePair<TKey, TValue> Create<TKey, TValue>(TKey key, TValue value) + { + return new KeyValuePair<TKey, TValue>(key, value); + } + } + // A KeyValuePair holds a key and a value from a dictionary. // It is used by the IEnumerable<T> implementation for both IDictionary<TKey, TValue> // and IReadOnlyDictionary<TKey, TValue>. @@ -52,5 +62,12 @@ namespace System.Collections.Generic { s.Append(']'); return StringBuilderCache.GetStringAndRelease(s); } + + // BLOCKED (do not add now): [EditorBrowsable(EditorBrowsableState.Never)] + public void Deconstruct(out TKey key, out TValue value) + { + key = Key; + value = Value; + } } } diff --git a/src/mscorlib/src/System/Collections/Generic/List.cs b/src/mscorlib/src/System/Collections/Generic/List.cs index ae3356d372..3e2947f5f9 100644 --- a/src/mscorlib/src/System/Collections/Generic/List.cs +++ b/src/mscorlib/src/System/Collections/Generic/List.cs @@ -91,14 +91,7 @@ namespace System.Collections.Generic { else { _size = 0; _items = _emptyArray; - // This enumerable could be empty. Let Add allocate a new array, if needed. - // Note it will also go to _defaultCapacity first, not 1, then 2, etc. - - using(IEnumerator<T> en = collection.GetEnumerator()) { - while(en.MoveNext()) { - Add(en.Current); - } - } + AddEnumerable(collection); } } @@ -274,7 +267,7 @@ namespace System.Collections.Generic { // public int BinarySearch(int index, int count, T item, IComparer<T> comparer) { if (index < 0) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); if (count < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); if (_size - index < count) @@ -369,7 +362,7 @@ namespace System.Collections.Generic { Array.Copy(_items, 0, array, arrayIndex, _size); } catch(ArrayTypeMismatchException){ - ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } } @@ -393,7 +386,7 @@ namespace System.Collections.Generic { } // Ensures that the capacity of this list is at least the given minimum - // value. If the currect capacity of the list is less than min, the + // value. If the current capacity of the list is less than min, the // capacity is increased to twice the current capacity or to min, // whichever is larger. private void EnsureCapacity(int min) { @@ -454,11 +447,11 @@ namespace System.Collections.Generic { public int FindIndex(int startIndex, int count, Predicate<T> match) { if( (uint)startIndex > (uint)_size ) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index); + ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index(); } if (count < 0 || startIndex > _size - count) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count); + ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count(); } if( match == null) { @@ -512,19 +505,19 @@ namespace System.Collections.Generic { if(_size == 0) { // Special case for 0 length List if( startIndex != -1) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index); + ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index(); } } else { // Make sure we're not out of range if ( (uint)startIndex >= (uint)_size) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index); + ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index(); } } // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0. if (count < 0 || startIndex - count + 1 < 0) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count); + ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count(); } int endIndex = startIndex - count; @@ -545,14 +538,14 @@ namespace System.Collections.Generic { int version = _version; for(int i = 0 ; i < _size; i++) { - if (version != _version && BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) { + if (version != _version) { break; } action(_items[i]); } - if (version != _version && BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + if (version != _version) + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } // Returns an enumerator for this list with the given @@ -575,7 +568,7 @@ namespace System.Collections.Generic { public List<T> GetRange(int index, int count) { if (index < 0) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (count < 0) { @@ -628,7 +621,7 @@ namespace System.Collections.Generic { // public int IndexOf(T item, int index) { if (index > _size) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); + ThrowHelper.ThrowArgumentOutOfRange_IndexException(); Contract.Ensures(Contract.Result<int>() >= -1); Contract.Ensures(Contract.Result<int>() < Count); Contract.EndContractBlock(); @@ -646,9 +639,9 @@ namespace System.Collections.Generic { // public int IndexOf(T item, int index, int count) { if (index > _size) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); + ThrowHelper.ThrowArgumentOutOfRange_IndexException(); - if (count <0 || index > _size - count) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count); + if (count <0 || index > _size - count) ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count(); Contract.Ensures(Contract.Result<int>() >= -1); Contract.Ensures(Contract.Result<int>() < Count); Contract.EndContractBlock(); @@ -698,7 +691,7 @@ namespace System.Collections.Generic { } if ((uint)index > (uint)_size) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); + ThrowHelper.ThrowArgumentOutOfRange_IndexException(); } Contract.EndContractBlock(); @@ -719,20 +712,24 @@ namespace System.Collections.Generic { Array.Copy(_items, index+count, _items, index*2, _size-index); } else { - T[] itemsToInsert = new T[count]; - c.CopyTo(itemsToInsert, 0); - itemsToInsert.CopyTo(_items, index); + c.CopyTo(_items, index); } _size += count; } } - else { + else if (index < _size) { + // We're inserting a lazy enumerable. Call Insert on each of the constituent items. using(IEnumerator<T> en = collection.GetEnumerator()) { while(en.MoveNext()) { Insert(index++, en.Current); } } } + else + { + // We're adding a lazy enumerable because the index is at the end of this list. + AddEnumerable(collection); + } _version++; } @@ -768,7 +765,7 @@ namespace System.Collections.Generic { public int LastIndexOf(T item, int index) { if (index >= _size) - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); + ThrowHelper.ThrowArgumentOutOfRange_IndexException(); Contract.Ensures(Contract.Result<int>() >= -1); Contract.Ensures(((Count == 0) && (Contract.Result<int>() == -1)) || ((Count > 0) && (Contract.Result<int>() <= index))); Contract.EndContractBlock(); @@ -786,7 +783,7 @@ namespace System.Collections.Generic { // public int LastIndexOf(T item, int index, int count) { if ((Count != 0) && (index < 0)) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if ((Count !=0) && (count < 0)) { @@ -885,7 +882,7 @@ namespace System.Collections.Generic { // public void RemoveRange(int index, int count) { if (index < 0) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (count < 0) { @@ -919,7 +916,7 @@ namespace System.Collections.Generic { // public void Reverse(int index, int count) { if (index < 0) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (count < 0) { @@ -930,22 +927,7 @@ namespace System.Collections.Generic { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); Contract.EndContractBlock(); - // The non-generic Array.Reverse is not used because it does not perform - // well for non-primitive value types. - // If/when a generic Array.Reverse<T> becomes available, the below code - // can be deleted and replaced with a call to Array.Reverse<T>. - int i = index; - int j = index + count - 1; - T[] array = _items; - while (i < j) - { - T temp = array[i]; - array[i] = array[j]; - array[j] = temp; - i++; - j--; - } - + Array.Reverse(_items, index, count); _version++; } @@ -973,7 +955,7 @@ namespace System.Collections.Generic { // public void Sort(int index, int count, IComparer<T> comparer) { if (index < 0) { - ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (count < 0) { @@ -995,8 +977,7 @@ namespace System.Collections.Generic { Contract.EndContractBlock(); if( _size > 0) { - IComparer<T> comparer = Comparer<T>.Create(comparison); - Array.Sort(_items, 0, _size, comparer); + ArraySortHelper<T>.Sort(_items, 0, _size, comparison); } } @@ -1006,12 +987,10 @@ namespace System.Collections.Generic { Contract.Ensures(Contract.Result<T[]>() != null); Contract.Ensures(Contract.Result<T[]>().Length == Count); -#if FEATURE_CORECLR if (_size == 0) { return _emptyArray; } -#endif T[] array = new T[_size]; Array.Copy(_items, 0, array, 0, _size); @@ -1048,6 +1027,31 @@ namespace System.Collections.Generic { return true; } + private void AddEnumerable(IEnumerable<T> enumerable) + { + Debug.Assert(enumerable != null); + Debug.Assert(!(enumerable is ICollection<T>), "We should have optimized for this beforehand."); + + using (IEnumerator<T> en = enumerable.GetEnumerator()) + { + _version++; // Even if the enumerable has no items, we can update _version. + + while (en.MoveNext()) + { + // Capture Current before doing anything else. If this throws + // an exception, we want to make a clean break. + T current = en.Current; + + if (_size == _items.Length) + { + EnsureCapacity(_size + 1); + } + + _items[_size++] = current; + } + } + } + [Serializable] public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator { @@ -1082,7 +1086,7 @@ namespace System.Collections.Generic { private bool MoveNextRare() { if (version != list._version) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } index = list._size + 1; @@ -1099,7 +1103,7 @@ namespace System.Collections.Generic { Object System.Collections.IEnumerator.Current { get { if( index == 0 || index == list._size + 1) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); } return Current; } @@ -1107,7 +1111,7 @@ namespace System.Collections.Generic { void System.Collections.IEnumerator.Reset() { if (version != list._version) { - ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } index = 0; |