diff options
Diffstat (limited to 'src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs')
-rw-r--r-- | src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs | 452 |
1 files changed, 52 insertions, 400 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 } - - |