diff options
Diffstat (limited to 'src/mscorlib/src/System/Collections/Generic')
18 files changed, 5424 insertions, 0 deletions
diff --git a/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs b/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs new file mode 100644 index 0000000000..b2fed9d78f --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs @@ -0,0 +1,1558 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +/*============================================================ +** +** +** +** +** +** Purpose: class to sort arrays +** +** +===========================================================*/ +namespace System.Collections.Generic +{ + using System; + using System.Globalization; + using System.Runtime.CompilerServices; + using System.Diagnostics.Contracts; + using System.Runtime.Versioning; + + #region ArraySortHelper for single arrays + + internal interface IArraySortHelper<TKey> + { + void Sort(TKey[] keys, int index, int length, IComparer<TKey> comparer); + int BinarySearch(TKey[] keys, int index, int length, TKey value, IComparer<TKey> comparer); + } + + internal static class IntrospectiveSortUtilities + { + // This is the threshold where Introspective sort switches to Insertion sort. + // Imperically, 16 seems to speed up most cases without slowing down others, at least for integers. + // Large value types may benefit from a smaller number. + internal const int IntrosortSizeThreshold = 16; + + internal const int QuickSortDepthThreshold = 32; + + internal static int FloorLog2(int n) + { + int result = 0; + while (n >= 1) + { + result++; + n = n / 2; + } + return result; + } + + 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)); + } + } + + } + + [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`1")] + internal class ArraySortHelper<T> + : IArraySortHelper<T> + { + static volatile IArraySortHelper<T> defaultArraySortHelper; + + public static IArraySortHelper<T> Default + { + get + { + IArraySortHelper<T> sorter = defaultArraySortHelper; + if (sorter == null) + sorter = CreateArraySortHelper(); + + return sorter; + } + } + + [System.Security.SecuritySafeCritical] // auto-generated + private static IArraySortHelper<T> CreateArraySortHelper() + { + if (typeof(IComparable<T>).IsAssignableFrom(typeof(T))) + { + defaultArraySortHelper = (IArraySortHelper<T>)RuntimeTypeHandle.Allocate(typeof(GenericArraySortHelper<string>).TypeHandle.Instantiate(new Type[] { typeof(T) })); + } + else + { + defaultArraySortHelper = new ArraySortHelper<T>(); + } + return defaultArraySortHelper; + } + + #region IArraySortHelper<T> Members + + 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!"); + + // Add a try block here to detect IComparers (or their + // underlying IComparables, etc) that are bogus. + 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. + + 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 + } + catch (IndexOutOfRangeException) + { + IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + } + catch (Exception e) + { + throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + } + } + + public int BinarySearch(T[] array, int index, int length, T value, IComparer<T> comparer) + { + try + { + if (comparer == null) + { + comparer = Comparer<T>.Default; + } + + return InternalBinarySearch(array, index, length, value, comparer); + } + catch (Exception e) + { + throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + } + } + + #endregion + + 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!"); + Contract.Requires(index >= 0 && length >= 0 && (array.Length - index >= length), "Check the arguments in the caller!"); + + int lo = index; + int hi = index + length - 1; + while (lo <= hi) + { + int i = lo + ((hi - lo) >> 1); + int order = comparer.Compare(array[i], value); + + if (order == 0) return i; + if (order < 0) + { + lo = i + 1; + } + else + { + hi = i - 1; + } + } + + return ~lo; + } + + private static void SwapIfGreater(T[] keys, IComparer<T> comparer, int a, int b) + { + if (a != b) + { + if (comparer.Compare(keys[a], keys[b]) > 0) + { + T key = keys[a]; + keys[a] = keys[b]; + keys[b] = key; + } + } + } + + private static void Swap(T[] a, int i, int j) + { + if(i != j) + { + T t = a[i]; + a[i] = a[j]; + a[j] = t; + } + } + + 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) + { + Contract.Requires(keys != null); + Contract.Requires(comparer != null); + Contract.Requires(left >= 0); + Contract.Requires(length >= 0); + Contract.Requires(length <= keys.Length); + Contract.Requires(length + left <= keys.Length); + + if (length < 2) + return; + + 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) + { + Contract.Requires(keys != null); + Contract.Requires(comparer != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi < keys.Length); + + while (hi > lo) + { + int partitionSize = hi - lo + 1; + if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) + { + if (partitionSize == 1) + { + return; + } + if (partitionSize == 2) + { + SwapIfGreater(keys, comparer, lo, hi); + return; + } + if (partitionSize == 3) + { + SwapIfGreater(keys, comparer, lo, hi-1); + SwapIfGreater(keys, comparer, lo, hi); + SwapIfGreater(keys, comparer, hi-1, hi); + return; + } + + InsertionSort(keys, lo, hi, comparer); + return; + } + + if (depthLimit == 0) + { + Heapsort(keys, lo, hi, comparer); + return; + } + depthLimit--; + + int p = PickPivotAndPartition(keys, lo, hi, comparer); + // Note we've already partitioned around the pivot and do not have to move the pivot again. + IntroSort(keys, p + 1, hi, depthLimit, comparer); + hi = p - 1; + } + } + + private static int PickPivotAndPartition(T[] keys, int lo, int hi, IComparer<T> comparer) + { + Contract.Requires(keys != null); + Contract.Requires(comparer != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi > lo); + Contract.Requires(hi < keys.Length); + Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi); + + // Compute median-of-three. But also partition them, since we've done the comparison. + int middle = lo + ((hi - lo) / 2); + + // Sort lo, mid and hi appropriately, then pick mid as the pivot. + SwapIfGreater(keys, comparer, lo, middle); // swap the low with the mid point + SwapIfGreater(keys, comparer, lo, hi); // swap the low with the high + SwapIfGreater(keys, comparer, middle, hi); // swap the middle with the high + + T pivot = keys[middle]; + Swap(keys, middle, hi - 1); + int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. + + while (left < right) + { + while (comparer.Compare(keys[++left], pivot) < 0) ; + while (comparer.Compare(pivot, keys[--right]) < 0) ; + + if (left >= right) + break; + + Swap(keys, left, right); + } + + // Put pivot in the right location. + Swap(keys, left, (hi - 1)); + return left; + } + + private static void Heapsort(T[] keys, int lo, int hi, IComparer<T> comparer) + { + Contract.Requires(keys != null); + Contract.Requires(comparer != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi > lo); + Contract.Requires(hi < keys.Length); + + int n = hi - lo + 1; + for (int i = n / 2; i >= 1; i = i - 1) + { + DownHeap(keys, i, n, lo, comparer); + } + for (int i = n; i > 1; i = i - 1) + { + Swap(keys, lo, lo + i - 1); + DownHeap(keys, 1, i - 1, lo, comparer); + } + } + + private static void DownHeap(T[] keys, int i, int n, int lo, IComparer<T> comparer) + { + Contract.Requires(keys != null); + Contract.Requires(comparer != null); + Contract.Requires(lo >= 0); + Contract.Requires(lo < keys.Length); + + T d = keys[lo + i - 1]; + int child; + while (i <= n / 2) + { + child = 2 * i; + if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0) + { + child++; + } + if (!(comparer.Compare(d, keys[lo + child - 1]) < 0)) + break; + keys[lo + i - 1] = keys[lo + child - 1]; + i = child; + } + keys[lo + i - 1] = d; + } + + private static void InsertionSort(T[] keys, int lo, int hi, IComparer<T> comparer) + { + Contract.Requires(keys != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi >= lo); + Contract.Requires(hi <= keys.Length); + + int i, j; + T t; + for (i = lo; i < hi; i++) + { + j = i; + t = keys[i + 1]; + while (j >= lo && comparer.Compare(t, keys[j]) < 0) + { + keys[j + 1] = keys[j]; + j--; + } + keys[j + 1] = t; + } + } + } + + [Serializable()] + internal class GenericArraySortHelper<T> + : IArraySortHelper<T> + where T : IComparable<T> + { + // Do not add a constructor to this class because ArraySortHelper<T>.CreateSortHelper will not execute it + + #region IArraySortHelper<T> Members + + 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!"); + + 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. + + 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 + } + } + catch (IndexOutOfRangeException) + { + IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + } + catch (Exception e) + { + throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + } + } + + 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!"); + + try + { + if (comparer == null || comparer == Comparer<T>.Default) + { + return BinarySearch(array, index, length, value); + } + else + { + return ArraySortHelper<T>.InternalBinarySearch(array, index, length, value, comparer); + } + } + catch (Exception e) + { + throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + } + } + + #endregion + + // This function is called when the user doesn't specify any comparer. + // Since T is constrained here, we can call IComparable<T>.CompareTo here. + // We can avoid boxing for value type and casting for reference types. + private static int BinarySearch(T[] array, int index, int length, T value) + { + int lo = index; + int hi = index + length - 1; + while (lo <= hi) + { + int i = lo + ((hi - lo) >> 1); + int order; + if (array[i] == null) + { + order = (value == null) ? 0 : -1; + } + else + { + order = array[i].CompareTo(value); + } + + if (order == 0) + { + return i; + } + + if (order < 0) + { + lo = i + 1; + } + else + { + hi = i - 1; + } + } + + return ~lo; + } + + private static void SwapIfGreaterWithItems(T[] keys, int a, int b) + { + Contract.Requires(keys != null); + Contract.Requires(0 <= a && a < keys.Length); + Contract.Requires(0 <= b && b < keys.Length); + + if (a != b) + { + if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0) + { + T key = keys[a]; + keys[a] = keys[b]; + keys[b] = key; + } + } + } + + private static void Swap(T[] a, int i, int j) + { + if(i!=j) + { + T t = a[i]; + a[i] = a[j]; + a[j] = t; + } + } + + 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); + Contract.Requires(left >= 0); + Contract.Requires(length >= 0); + Contract.Requires(length <= keys.Length); + Contract.Requires(length + left <= keys.Length); + + if (length < 2) + return; + + IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length)); + } + + private static void IntroSort(T[] keys, int lo, int hi, int depthLimit) + { + Contract.Requires(keys != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi < keys.Length); + + while (hi > lo) + { + int partitionSize = hi - lo + 1; + if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) + { + if (partitionSize == 1) + { + return; + } + if (partitionSize == 2) + { + SwapIfGreaterWithItems(keys, lo, hi); + return; + } + if (partitionSize == 3) + { + SwapIfGreaterWithItems(keys, lo, hi-1); + SwapIfGreaterWithItems(keys, lo, hi); + SwapIfGreaterWithItems(keys, hi-1, hi); + return; + } + + InsertionSort(keys, lo, hi); + return; + } + + if (depthLimit == 0) + { + Heapsort(keys, lo, hi); + return; + } + depthLimit--; + + int p = PickPivotAndPartition(keys, lo, hi); + // Note we've already partitioned around the pivot and do not have to move the pivot again. + IntroSort(keys, p + 1, hi, depthLimit); + hi = p - 1; + } + } + + private static int PickPivotAndPartition(T[] keys, int lo, int hi) + { + Contract.Requires(keys != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi > lo); + Contract.Requires(hi < keys.Length); + Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi); + + // Compute median-of-three. But also partition them, since we've done the comparison. + int middle = lo + ((hi - lo) / 2); + + // Sort lo, mid and hi appropriately, then pick mid as the pivot. + SwapIfGreaterWithItems(keys, lo, middle); // swap the low with the mid point + SwapIfGreaterWithItems(keys, lo, hi); // swap the low with the high + SwapIfGreaterWithItems(keys, middle, hi); // swap the middle with the high + + T pivot = keys[middle]; + Swap(keys, middle, hi - 1); + int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. + + while (left < right) + { + if (pivot == null) + { + while (left < (hi - 1) && keys[++left] == null) ; + while (right > lo && keys[--right] != null) ; + } + else + { + while (pivot.CompareTo(keys[++left]) > 0) ; + while (pivot.CompareTo(keys[--right]) < 0) ; + } + + if (left >= right) + break; + + Swap(keys, left, right); + } + + // Put pivot in the right location. + Swap(keys, left, (hi - 1)); + return left; + } + + private static void Heapsort(T[] keys, int lo, int hi) + { + Contract.Requires(keys != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi > lo); + Contract.Requires(hi < keys.Length); + + int n = hi - lo + 1; + for (int i = n / 2; i >= 1; i = i - 1) + { + DownHeap(keys, i, n, lo); + } + for (int i = n; i > 1; i = i - 1) + { + Swap(keys, lo, lo + i - 1); + DownHeap(keys, 1, i - 1, lo); + } + } + + private static void DownHeap(T[] keys, int i, int n, int lo) + { + Contract.Requires(keys != null); + Contract.Requires(lo >= 0); + Contract.Requires(lo < keys.Length); + + T d = keys[lo + i - 1]; + int child; + while (i <= n / 2) + { + child = 2 * i; + if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0)) + { + child++; + } + if (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(d) < 0) + break; + keys[lo + i - 1] = keys[lo + child - 1]; + i = child; + } + keys[lo + i - 1] = d; + } + + private static void InsertionSort(T[] keys, int lo, int hi) + { + Contract.Requires(keys != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi >= lo); + Contract.Requires(hi <= keys.Length); + + int i, j; + T t; + for (i = lo; i < hi; i++) + { + j = i; + t = keys[i + 1]; + while (j >= lo && (t == null || t.CompareTo(keys[j]) < 0)) + { + keys[j + 1] = keys[j]; + j--; + } + keys[j + 1] = t; + } + } + } + + #endregion + + #region ArraySortHelper for paired key and value arrays + + internal interface IArraySortHelper<TKey, TValue> + { + void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer); + } + + [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`2")] + internal class ArraySortHelper<TKey, TValue> + : IArraySortHelper<TKey, TValue> + { + static volatile IArraySortHelper<TKey, TValue> defaultArraySortHelper; + + public static IArraySortHelper<TKey, TValue> Default + { + get + { + IArraySortHelper<TKey, TValue> sorter = defaultArraySortHelper; + if (sorter == null) + sorter = CreateArraySortHelper(); + + return sorter; + } + } + + [System.Security.SecuritySafeCritical] // auto-generated + private static IArraySortHelper<TKey, TValue> CreateArraySortHelper() + { + if (typeof(IComparable<TKey>).IsAssignableFrom(typeof(TKey))) + { + defaultArraySortHelper = (IArraySortHelper<TKey, TValue>)RuntimeTypeHandle.Allocate(typeof(GenericArraySortHelper<string, string>).TypeHandle.Instantiate(new Type[] { typeof(TKey), typeof(TValue) })); + } + else + { + defaultArraySortHelper = new ArraySortHelper<TKey, TValue>(); + } + return defaultArraySortHelper; + } + + 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!"); + + // Add a try block here to detect IComparers (or their + // underlying IComparables, etc) that are bogus. + try + { + if (comparer == null || comparer == Comparer<TKey>.Default) + { + 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) + { + IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + } + catch (Exception e) + { + throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + } + } + + private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, IComparer<TKey> comparer, int a, int b) + { + Contract.Requires(keys != null); + Contract.Requires(values == null || values.Length >= keys.Length); + Contract.Requires(comparer != null); + Contract.Requires(0 <= a && a < keys.Length); + Contract.Requires(0 <= b && b < keys.Length); + + if (a != b) + { + if (comparer.Compare(keys[a], keys[b]) > 0) + { + TKey key = keys[a]; + keys[a] = keys[b]; + keys[b] = key; + if (values != null) + { + TValue value = values[a]; + values[a] = values[b]; + values[b] = value; + } + } + } + } + + private static void Swap(TKey[] keys, TValue[] values, int i, int j) + { + if(i!=j) + { + TKey k = keys[i]; + keys[i] = keys[j]; + keys[j] = k; + if(values != null) + { + TValue v = values[i]; + values[i] = values[j]; + values[j] = v; + } + } + } + + 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); + Contract.Requires(values != null); + Contract.Requires(comparer != null); + Contract.Requires(left >= 0); + Contract.Requires(length >= 0); + Contract.Requires(length <= keys.Length); + Contract.Requires(length + left <= keys.Length); + Contract.Requires(length + left <= values.Length); + + if (length < 2) + return; + + IntroSort(keys, values, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer); + } + + private static void IntroSort(TKey[] keys, TValue[] values, int lo, int hi, int depthLimit, IComparer<TKey> comparer) + { + Contract.Requires(keys != null); + Contract.Requires(values != null); + Contract.Requires(comparer != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi < keys.Length); + + while (hi > lo) + { + int partitionSize = hi - lo + 1; + if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) + { + if (partitionSize == 1) + { + return; + } + if (partitionSize == 2) + { + SwapIfGreaterWithItems(keys, values, comparer, lo, hi); + return; + } + if (partitionSize == 3) + { + SwapIfGreaterWithItems(keys, values, comparer, lo, hi-1); + SwapIfGreaterWithItems(keys, values, comparer, lo, hi); + SwapIfGreaterWithItems(keys, values, comparer, hi-1, hi); + return; + } + + InsertionSort(keys, values, lo, hi, comparer); + return; + } + + if (depthLimit == 0) + { + Heapsort(keys, values, lo, hi, comparer); + return; + } + depthLimit--; + + int p = PickPivotAndPartition(keys, values, lo, hi, comparer); + // Note we've already partitioned around the pivot and do not have to move the pivot again. + IntroSort(keys, values, p + 1, hi, depthLimit, comparer); + hi = p - 1; + } + } + + private static int PickPivotAndPartition(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer) + { + Contract.Requires(keys != null); + Contract.Requires(values != null); + Contract.Requires(comparer != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi > lo); + Contract.Requires(hi < keys.Length); + Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi); + + // Compute median-of-three. But also partition them, since we've done the comparison. + int middle = lo + ((hi - lo) / 2); + + // Sort lo, mid and hi appropriately, then pick mid as the pivot. + SwapIfGreaterWithItems(keys, values, comparer, lo, middle); // swap the low with the mid point + SwapIfGreaterWithItems(keys, values, comparer, lo, hi); // swap the low with the high + SwapIfGreaterWithItems(keys, values, comparer, middle, hi); // swap the middle with the high + + TKey pivot = keys[middle]; + Swap(keys, values, middle, hi - 1); + int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. + + while (left < right) + { + while (comparer.Compare(keys[++left], pivot) < 0) ; + while (comparer.Compare(pivot, keys[--right]) < 0) ; + + if (left >= right) + break; + + Swap(keys, values, left, right); + } + + // Put pivot in the right location. + Swap(keys, values, left, (hi - 1)); + return left; + } + + private static void Heapsort(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer) + { + Contract.Requires(keys != null); + Contract.Requires(values != null); + Contract.Requires(comparer != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi > lo); + Contract.Requires(hi < keys.Length); + + int n = hi - lo + 1; + for (int i = n / 2; i >= 1; i = i - 1) + { + DownHeap(keys, values, i, n, lo, comparer); + } + for (int i = n; i > 1; i = i - 1) + { + Swap(keys, values, lo, lo + i - 1); + DownHeap(keys, values, 1, i - 1, lo, comparer); + } + } + + private static void DownHeap(TKey[] keys, TValue[] values, int i, int n, int lo, IComparer<TKey> comparer) + { + Contract.Requires(keys != null); + Contract.Requires(comparer != null); + Contract.Requires(lo >= 0); + Contract.Requires(lo < keys.Length); + + TKey d = keys[lo + i - 1]; + TValue dValue = (values != null) ? values[lo + i - 1] : default(TValue); + int child; + while (i <= n / 2) + { + child = 2 * i; + if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0) + { + child++; + } + if (!(comparer.Compare(d, keys[lo + child - 1]) < 0)) + break; + keys[lo + i - 1] = keys[lo + child - 1]; + if(values != null) + values[lo + i - 1] = values[lo + child - 1]; + i = child; + } + keys[lo + i - 1] = d; + if(values != null) + values[lo + i - 1] = dValue; + } + + private static void InsertionSort(TKey[] keys, TValue[] values, int lo, int hi, IComparer<TKey> comparer) + { + Contract.Requires(keys != null); + Contract.Requires(values != null); + Contract.Requires(comparer != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi >= lo); + Contract.Requires(hi <= keys.Length); + + int i, j; + TKey t; + TValue tValue; + for (i = lo; i < hi; i++) + { + j = i; + t = keys[i + 1]; + tValue = (values != null) ? values[i + 1] : default(TValue); + while (j >= lo && comparer.Compare(t, keys[j]) < 0) + { + keys[j + 1] = keys[j]; + if(values != null) + values[j + 1] = values[j]; + j--; + } + keys[j + 1] = t; + if(values != null) + values[j + 1] = tValue; + } + } + } + + internal class GenericArraySortHelper<TKey, TValue> + : IArraySortHelper<TKey, TValue> + where TKey : IComparable<TKey> + { + 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!"); + + // Add a try block here to detect IComparers (or their + // underlying IComparables, etc) that are bogus. + try + { + 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) + { + IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); + } + catch (Exception e) + { + throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + } + } + + private static void SwapIfGreaterWithItems(TKey[] keys, TValue[] values, int a, int b) + { + if (a != b) + { + if (keys[a] != null && keys[a].CompareTo(keys[b]) > 0) + { + TKey key = keys[a]; + keys[a] = keys[b]; + keys[b] = key; + if (values != null) + { + TValue value = values[a]; + values[a] = values[b]; + values[b] = value; + } + } + } + } + + private static void Swap(TKey[] keys, TValue[] values, int i, int j) + { + if(i != j) + { + TKey k = keys[i]; + keys[i] = keys[j]; + keys[j] = k; + if(values != null) + { + TValue v = values[i]; + values[i] = values[j]; + values[j] = v; + } + } + } + + 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); + Contract.Requires(values != null); + Contract.Requires(left >= 0); + Contract.Requires(length >= 0); + Contract.Requires(length <= keys.Length); + Contract.Requires(length + left <= keys.Length); + Contract.Requires(length + left <= values.Length); + + if (length < 2) + return; + + IntroSort(keys, values, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length)); + } + + private static void IntroSort(TKey[] keys, TValue[] values, int lo, int hi, int depthLimit) + { + Contract.Requires(keys != null); + Contract.Requires(values != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi < keys.Length); + + while (hi > lo) + { + int partitionSize = hi - lo + 1; + if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold) + { + if (partitionSize == 1) + { + return; + } + if (partitionSize == 2) + { + SwapIfGreaterWithItems(keys, values, lo, hi); + return; + } + if (partitionSize == 3) + { + SwapIfGreaterWithItems(keys, values, lo, hi-1); + SwapIfGreaterWithItems(keys, values, lo, hi); + SwapIfGreaterWithItems(keys, values, hi-1, hi); + return; + } + + InsertionSort(keys, values, lo, hi); + return; + } + + if (depthLimit == 0) + { + Heapsort(keys, values, lo, hi); + return; + } + depthLimit--; + + int p = PickPivotAndPartition(keys, values, lo, hi); + // Note we've already partitioned around the pivot and do not have to move the pivot again. + IntroSort(keys, values, p + 1, hi, depthLimit); + hi = p - 1; + } + } + + private static int PickPivotAndPartition(TKey[] keys, TValue[] values, int lo, int hi) + { + Contract.Requires(keys != null); + Contract.Requires(values != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi > lo); + Contract.Requires(hi < keys.Length); + Contract.Ensures(Contract.Result<int>() >= lo && Contract.Result<int>() <= hi); + + // Compute median-of-three. But also partition them, since we've done the comparison. + int middle = lo + ((hi - lo) / 2); + + // Sort lo, mid and hi appropriately, then pick mid as the pivot. + SwapIfGreaterWithItems(keys, values, lo, middle); // swap the low with the mid point + SwapIfGreaterWithItems(keys, values, lo, hi); // swap the low with the high + SwapIfGreaterWithItems(keys, values, middle, hi); // swap the middle with the high + + TKey pivot = keys[middle]; + Swap(keys, values, middle, hi - 1); + int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. + + while (left < right) + { + if(pivot == null) + { + while (left < (hi - 1) && keys[++left] == null) ; + while (right > lo && keys[--right] != null); + } + else + { + while (pivot.CompareTo(keys[++left]) > 0) ; + while (pivot.CompareTo(keys[--right]) < 0) ; + } + + if (left >= right) + break; + + Swap(keys, values, left, right); + } + + // Put pivot in the right location. + Swap(keys, values, left, (hi - 1)); + return left; + } + + private static void Heapsort(TKey[] keys, TValue[] values, int lo, int hi) + { + Contract.Requires(keys != null); + Contract.Requires(values != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi > lo); + Contract.Requires(hi < keys.Length); + + int n = hi - lo + 1; + for (int i = n / 2; i >= 1; i = i - 1) + { + DownHeap(keys, values, i, n, lo); + } + for (int i = n; i > 1; i = i - 1) + { + Swap(keys, values, lo, lo + i - 1); + DownHeap(keys, values, 1, i - 1, lo); + } + } + + private static void DownHeap(TKey[] keys, TValue[] values, int i, int n, int lo) + { + Contract.Requires(keys != null); + Contract.Requires(lo >= 0); + Contract.Requires(lo < keys.Length); + + TKey d = keys[lo + i - 1]; + TValue dValue = (values != null) ? values[lo + i - 1] : default(TValue); + int child; + while (i <= n / 2) + { + child = 2 * i; + if (child < n && (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(keys[lo + child]) < 0)) + { + child++; + } + if (keys[lo + child - 1] == null || keys[lo + child - 1].CompareTo(d) < 0) + break; + keys[lo + i - 1] = keys[lo + child - 1]; + if(values != null) + values[lo + i - 1] = values[lo + child - 1]; + i = child; + } + keys[lo + i - 1] = d; + if(values != null) + values[lo + i - 1] = dValue; + } + + private static void InsertionSort(TKey[] keys, TValue[] values, int lo, int hi) + { + Contract.Requires(keys != null); + Contract.Requires(values != null); + Contract.Requires(lo >= 0); + Contract.Requires(hi >= lo); + Contract.Requires(hi <= keys.Length); + + int i, j; + TKey t; + TValue tValue; + for (i = lo; i < hi; i++) + { + j = i; + t = keys[i + 1]; + tValue = (values != null)? values[i + 1] : default(TValue); + while (j >= lo && (t == null || t.CompareTo(keys[j]) < 0)) + { + keys[j + 1] = keys[j]; + if(values != null) + values[j + 1] = values[j]; + j--; + } + keys[j + 1] = t; + if(values != null) + values[j + 1] = tValue; + } + } + } + + #endregion +} + + diff --git a/src/mscorlib/src/System/Collections/Generic/Comparer.cs b/src/mscorlib/src/System/Collections/Generic/Comparer.cs new file mode 100644 index 0000000000..9f1a8bff6f --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/Comparer.cs @@ -0,0 +1,325 @@ +// 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. + +// + +using System; +using System.Collections; +using System.Collections.Generic; +using System.Diagnostics.Contracts; +//using System.Globalization; +using System.Runtime.CompilerServices; +using System.Security; +using System.Runtime.Serialization; + +namespace System.Collections.Generic +{ + [Serializable] + [TypeDependencyAttribute("System.Collections.Generic.ObjectComparer`1")] + public abstract class Comparer<T> : IComparer, IComparer<T> + { + static readonly Comparer<T> defaultComparer = CreateComparer(); + + public static Comparer<T> Default { + get { + Contract.Ensures(Contract.Result<Comparer<T>>() != null); + return defaultComparer; + } + } + + public static Comparer<T> Create(Comparison<T> comparison) + { + Contract.Ensures(Contract.Result<Comparer<T>>() != null); + + if (comparison == null) + throw new ArgumentNullException("comparison"); + + return new ComparisonComparer<T>(comparison); + } + + // + // 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; + RuntimeType t = (RuntimeType)typeof(T); + + // If T implements IComparable<T> return a GenericComparer<T> + if (typeof(IComparable<T>).IsAssignableFrom(t)) + { + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericComparer<int>), t); + } + else if (default(T) == null) + { + // If T is a Nullable<U> where U implements IComparable<U> return a NullableComparer<U> + if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) { + RuntimeType u = (RuntimeType)t.GetGenericArguments()[0]; + if (typeof(IComparable<>).MakeGenericType(u).IsAssignableFrom(u)) { + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableComparer<int>), u); + } + } + } + else if (t.IsEnum) + { + // Explicitly call Enum.GetUnderlyingType here. Although GetTypeCode + // ends up doing this anyway, we end up avoiding an unnecessary P/Invoke + // and virtual method call. + TypeCode underlyingTypeCode = Type.GetTypeCode(Enum.GetUnderlyingType(t)); + + // Depending on the enum type, we need to special case the comparers so that we avoid boxing + // Specialize differently for signed/unsigned types so we avoid problems with large numbers + switch (underlyingTypeCode) + { + case TypeCode.SByte: + case TypeCode.Int16: + case TypeCode.Int32: + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(Int32EnumComparer<int>), t); + break; + case TypeCode.Byte: + case TypeCode.UInt16: + case TypeCode.UInt32: + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(UInt32EnumComparer<uint>), t); + break; + // 64-bit enums: use UnsafeEnumCastLong + case TypeCode.Int64: + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(Int64EnumComparer<long>), t); + break; + case TypeCode.UInt64: + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(UInt64EnumComparer<ulong>), t); + break; + } + } + + return result != null ? + (Comparer<T>)result : + new ObjectComparer<T>(); // Fallback to ObjectComparer, which uses boxing + } + + public abstract int Compare(T x, T y); + + int IComparer.Compare(object x, object y) { + if (x == null) return y == null ? 0 : -1; + if (y == null) return 1; + if (x is T && y is T) return Compare((T)x, (T)y); + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArgumentForComparison); + return 0; + } + } + + // Note: although there is a lot of shared code in the following + // comparers, we do not incorporate it into a base class for perf + // reasons. Adding another base class (even one with no fields) + // means another generic instantiation, which can be costly esp. + // for value types. + + [Serializable] + internal sealed class GenericComparer<T> : Comparer<T> where T : IComparable<T> + { + public override int Compare(T x, T y) { + if (x != null) { + if (y != null) return x.CompareTo(y); + return 1; + } + if (y != null) return -1; + return 0; + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); + + public override int GetHashCode() => + GetType().GetHashCode(); + } + + [Serializable] + internal sealed class NullableComparer<T> : Comparer<T?> where T : struct, IComparable<T> + { + public override int Compare(Nullable<T> x, Nullable<T> y) { + if (x.HasValue) { + if (y.HasValue) return x.value.CompareTo(y.value); + return 1; + } + if (y.HasValue) return -1; + return 0; + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); + + public override int GetHashCode() => + GetType().GetHashCode(); + } + + [Serializable] + internal sealed class ObjectComparer<T> : Comparer<T> + { + public override int Compare(T x, T y) { + return System.Collections.Comparer.Default.Compare(x, y); + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); + + public override int GetHashCode() => + GetType().GetHashCode(); + } + + [Serializable] + internal sealed class ComparisonComparer<T> : Comparer<T> + { + private readonly Comparison<T> _comparison; + + public ComparisonComparer(Comparison<T> comparison) { + _comparison = comparison; + } + + public override int Compare(T x, T y) { + return _comparison(x, y); + } + } + + // Enum comparers (specialized to avoid boxing) + // NOTE: Each of these needs to implement ISerializable + // and have a SerializationInfo/StreamingContext ctor, + // since we want to serialize as ObjectComparer for + // back-compat reasons (see below). + + [Serializable] + internal sealed class Int32EnumComparer<T> : Comparer<T>, ISerializable where T : struct + { + public Int32EnumComparer() + { + Contract.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + } + + // Used by the serialization engine. + private Int32EnumComparer(SerializationInfo info, StreamingContext context) { } + + public override int Compare(T x, T y) + { + int ix = JitHelpers.UnsafeEnumCast(x); + int iy = JitHelpers.UnsafeEnumCast(y); + return ix.CompareTo(iy); + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); + + public override int GetHashCode() => + GetType().GetHashCode(); + + [SecurityCritical] + public void GetObjectData(SerializationInfo info, StreamingContext context) + { + // Previously Comparer<T> was not specialized for enums, + // and instead fell back to ObjectComparer which uses boxing. + // Set the type as ObjectComparer here so code that serializes + // Comparer for enums will not break. + info.SetType(typeof(ObjectComparer<T>)); + } + } + + [Serializable] + internal sealed class UInt32EnumComparer<T> : Comparer<T>, ISerializable where T : struct + { + public UInt32EnumComparer() + { + Contract.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + } + + // Used by the serialization engine. + private UInt32EnumComparer(SerializationInfo info, StreamingContext context) { } + + public override int Compare(T x, T y) + { + uint ix = (uint)JitHelpers.UnsafeEnumCast(x); + uint iy = (uint)JitHelpers.UnsafeEnumCast(y); + return ix.CompareTo(iy); + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); + + public override int GetHashCode() => + GetType().GetHashCode(); + + [SecurityCritical] + public void GetObjectData(SerializationInfo info, StreamingContext context) + { + info.SetType(typeof(ObjectComparer<T>)); + } + } + + [Serializable] + internal sealed class Int64EnumComparer<T> : Comparer<T>, ISerializable where T : struct + { + public Int64EnumComparer() + { + Contract.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + } + + // Used by the serialization engine. + private Int64EnumComparer(SerializationInfo info, StreamingContext context) { } + + public override int Compare(T x, T y) + { + long lx = JitHelpers.UnsafeEnumCastLong(x); + long ly = JitHelpers.UnsafeEnumCastLong(y); + return lx.CompareTo(ly); + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); + + public override int GetHashCode() => + GetType().GetHashCode(); + + [SecurityCritical] + public void GetObjectData(SerializationInfo info, StreamingContext context) + { + info.SetType(typeof(ObjectComparer<T>)); + } + } + + [Serializable] + internal sealed class UInt64EnumComparer<T> : Comparer<T>, ISerializable where T : struct + { + public UInt64EnumComparer() + { + Contract.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + } + + // Used by the serialization engine. + private UInt64EnumComparer(SerializationInfo info, StreamingContext context) { } + + public override int Compare(T x, T y) + { + ulong lx = (ulong)JitHelpers.UnsafeEnumCastLong(x); + ulong ly = (ulong)JitHelpers.UnsafeEnumCastLong(y); + return lx.CompareTo(ly); + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj) => + obj != null && GetType() == obj.GetType(); + + 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 new file mode 100644 index 0000000000..57b91eff51 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/DebugView.cs @@ -0,0 +1,129 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +/*============================================================================= +** +** +** +** Purpose: DebugView class for generic collections +** +** +** +** +=============================================================================*/ + +namespace System.Collections.Generic { + using System; + using System.Collections.ObjectModel; + using System.Security.Permissions; + using System.Diagnostics; + using System.Diagnostics.Contracts; + + // + // VS IDE can't differentiate between types with the same name from different + // assembly. So we need to use different names for collection debug view for + // collections in mscorlib.dll and system.dll. + // + internal sealed class Mscorlib_CollectionDebugView<T> { + private ICollection<T> collection; + + public Mscorlib_CollectionDebugView(ICollection<T> collection) { + if (collection == null) + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); + + this.collection = collection; + } + + [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] + public T[] Items { + get { + T[] items = new T[collection.Count]; + collection.CopyTo(items, 0); + return items; + } + } + } + + internal sealed class Mscorlib_DictionaryKeyCollectionDebugView<TKey, TValue> { + private ICollection<TKey> collection; + + public Mscorlib_DictionaryKeyCollectionDebugView(ICollection<TKey> collection) { + if (collection == null) + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); + + this.collection = collection; + } + + [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] + public TKey[] Items { + get { + TKey[] items = new TKey[collection.Count]; + collection.CopyTo(items, 0); + return items; + } + } + } + + internal sealed class Mscorlib_DictionaryValueCollectionDebugView<TKey, TValue> { + private ICollection<TValue> collection; + + public Mscorlib_DictionaryValueCollectionDebugView(ICollection<TValue> collection) { + if (collection == null) + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); + + this.collection = collection; + } + + [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] + public TValue[] Items { + get { + TValue[] items = new TValue[collection.Count]; + collection.CopyTo(items, 0); + return items; + } + } + } + + internal sealed class Mscorlib_DictionaryDebugView<K, V> { + private IDictionary<K, V> dict; + + public Mscorlib_DictionaryDebugView(IDictionary<K, V> dictionary) { + if (dictionary == null) + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); + + this.dict = dictionary; + } + + [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] + public KeyValuePair<K, V>[] Items { + get { + KeyValuePair<K, V>[] items = new KeyValuePair<K, V>[dict.Count]; + dict.CopyTo(items, 0); + return items; + } + } + } + + internal sealed class Mscorlib_KeyedCollectionDebugView<K, T> { + private KeyedCollection<K, T> kc; + + public Mscorlib_KeyedCollectionDebugView(KeyedCollection<K, T> keyedCollection) { + if (keyedCollection == null) { + throw new ArgumentNullException("keyedCollection"); + } + Contract.EndContractBlock(); + + kc = keyedCollection; + } + + [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] + public T[] Items { + get { + T[] items = new T[kc.Count]; + kc.CopyTo(items, 0); + return items; + } + } + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/Dictionary.cs b/src/mscorlib/src/System/Collections/Generic/Dictionary.cs new file mode 100644 index 0000000000..9cbfff5a57 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/Dictionary.cs @@ -0,0 +1,1187 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +/*============================================================ +** +** +** +** +** Purpose: Generic hash table implementation +** +** #DictionaryVersusHashtableThreadSafety +** Hashtable has multiple reader/single writer (MR/SW) thread safety built into +** certain methods and properties, whereas Dictionary doesn't. If you're +** converting framework code that formerly used Hashtable to Dictionary, it's +** important to consider whether callers may have taken a dependence on MR/SW +** thread safety. If a reader writer lock is available, then that may be used +** with a Dictionary to get the same thread safety guarantee. +** +** Reader writer locks don't exist in silverlight, so we do the following as a +** result of removing non-generic collections from silverlight: +** 1. If the Hashtable was fully synchronized, then we replace it with a +** Dictionary with full locks around reads/writes (same thread safety +** guarantee). +** 2. Otherwise, the Hashtable has the default MR/SW thread safety behavior, +** so we do one of the following on a case-by-case basis: +** a. If the race condition can be addressed by rearranging the code and using a temp +** variable (for example, it's only populated immediately after created) +** then we address the race condition this way and use Dictionary. +** b. If there's concern about degrading performance with the increased +** locking, we ifdef with FEATURE_NONGENERIC_COLLECTIONS so we can at +** least use Hashtable in the desktop build, but Dictionary with full +** locks in silverlight builds. Note that this is heavier locking than +** MR/SW, but this is the only option without rewriting (or adding back) +** the reader writer lock. +** c. If there's no performance concern (e.g. debug-only code) we +** consistently replace Hashtable with Dictionary plus full locks to +** reduce complexity. +** d. Most of serialization is dead code in silverlight. Instead of updating +** those Hashtable occurences in serialization, we carved out references +** to serialization such that this code doesn't need to build in +** silverlight. +===========================================================*/ +namespace System.Collections.Generic { + + using System; + using System.Collections; + using System.Diagnostics; + using System.Diagnostics.Contracts; + using System.Runtime.Serialization; + using System.Security.Permissions; + + [DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))] + [DebuggerDisplay("Count = {Count}")] + [Serializable] + [System.Runtime.InteropServices.ComVisible(false)] + public class Dictionary<TKey,TValue>: IDictionary<TKey,TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback { + + private struct Entry { + public int hashCode; // Lower 31 bits of hash code, -1 if unused + public int next; // Index of next entry, -1 if last + public TKey key; // Key of entry + public TValue value; // Value of entry + } + + private int[] buckets; + private Entry[] entries; + private int count; + private int version; + private int freeList; + private int freeCount; + private IEqualityComparer<TKey> comparer; + private KeyCollection keys; + private ValueCollection values; + private Object _syncRoot; + + // constants for serialization + private const String VersionName = "Version"; + private const String HashSizeName = "HashSize"; // Must save buckets.Length + private const String KeyValuePairsName = "KeyValuePairs"; + private const String ComparerName = "Comparer"; + + public Dictionary(): this(0, null) {} + + public Dictionary(int capacity): this(capacity, null) {} + + public Dictionary(IEqualityComparer<TKey> comparer): this(0, comparer) {} + + public Dictionary(int capacity, IEqualityComparer<TKey> comparer) { + if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity); + if (capacity > 0) Initialize(capacity); + this.comparer = comparer ?? EqualityComparer<TKey>.Default; + +#if FEATURE_RANDOMIZED_STRING_HASHING && FEATURE_CORECLR + if (HashHelpers.s_UseRandomizedStringHashing && comparer == EqualityComparer<string>.Default) + { + this.comparer = (IEqualityComparer<TKey>) NonRandomizedStringEqualityComparer.Default; + } +#endif // FEATURE_RANDOMIZED_STRING_HASHING && FEATURE_CORECLR + } + + public Dictionary(IDictionary<TKey,TValue> dictionary): this(dictionary, null) {} + + public Dictionary(IDictionary<TKey,TValue> dictionary, IEqualityComparer<TKey> comparer): + this(dictionary != null? dictionary.Count: 0, comparer) { + + if( dictionary == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); + } + + // It is likely that the passed-in dictionary is Dictionary<TKey,TValue>. When this is the case, + // avoid the enumerator allocation and overhead by looping through the entries array directly. + // We only do this when dictionary is Dictionary<TKey,TValue> and not a subclass, to maintain + // back-compat with subclasses that may have overridden the enumerator behavior. + if (dictionary.GetType() == typeof(Dictionary<TKey,TValue>)) { + Dictionary<TKey,TValue> d = (Dictionary<TKey,TValue>)dictionary; + int count = d.count; + Entry[] entries = d.entries; + for (int i = 0; i < count; i++) { + if (entries[i].hashCode >= 0) { + Add(entries[i].key, entries[i].value); + } + } + return; + } + + foreach (KeyValuePair<TKey,TValue> pair in dictionary) { + 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, + //we'll just cache this. The graph is not valid until OnDeserialization has been called. + HashHelpers.SerializationInfoTable.Add(this, info); + } + + public IEqualityComparer<TKey> Comparer { + get { + return comparer; + } + } + + public int Count { + get { return count - freeCount; } + } + + public KeyCollection Keys { + get { + Contract.Ensures(Contract.Result<KeyCollection>() != null); + if (keys == null) keys = new KeyCollection(this); + return keys; + } + } + + ICollection<TKey> IDictionary<TKey, TValue>.Keys { + get { + if (keys == null) keys = new KeyCollection(this); + return keys; + } + } + + IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys { + get { + if (keys == null) keys = new KeyCollection(this); + return keys; + } + } + + public ValueCollection Values { + get { + Contract.Ensures(Contract.Result<ValueCollection>() != null); + if (values == null) values = new ValueCollection(this); + return values; + } + } + + ICollection<TValue> IDictionary<TKey, TValue>.Values { + get { + if (values == null) values = new ValueCollection(this); + return values; + } + } + + IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values { + get { + if (values == null) values = new ValueCollection(this); + return values; + } + } + + public TValue this[TKey key] { + get { + int i = FindEntry(key); + if (i >= 0) return entries[i].value; + ThrowHelper.ThrowKeyNotFoundException(); + return default(TValue); + } + set { + Insert(key, value, false); + } + } + + public void Add(TKey key, TValue value) { + Insert(key, value, true); + } + + void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair) { + Add(keyValuePair.Key, keyValuePair.Value); + } + + bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> keyValuePair) { + int i = FindEntry(keyValuePair.Key); + if( i >= 0 && EqualityComparer<TValue>.Default.Equals(entries[i].value, keyValuePair.Value)) { + return true; + } + return false; + } + + bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> keyValuePair) { + int i = FindEntry(keyValuePair.Key); + if( i >= 0 && EqualityComparer<TValue>.Default.Equals(entries[i].value, keyValuePair.Value)) { + Remove(keyValuePair.Key); + return true; + } + return false; + } + + public void Clear() { + if (count > 0) { + for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; + Array.Clear(entries, 0, count); + freeList = -1; + count = 0; + freeCount = 0; + version++; + } + } + + public bool ContainsKey(TKey key) { + return FindEntry(key) >= 0; + } + + public bool ContainsValue(TValue value) { + if (value == null) { + for (int i = 0; i < count; i++) { + if (entries[i].hashCode >= 0 && entries[i].value == null) return true; + } + } + else { + EqualityComparer<TValue> c = EqualityComparer<TValue>.Default; + for (int i = 0; i < count; i++) { + if (entries[i].hashCode >= 0 && c.Equals(entries[i].value, value)) return true; + } + } + return false; + } + + private void CopyTo(KeyValuePair<TKey,TValue>[] array, int index) { + if (array == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (index < 0 || index > array.Length ) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (array.Length - index < Count) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + } + + int count = this.count; + Entry[] entries = this.entries; + for (int i = 0; i < count; i++) { + if (entries[i].hashCode >= 0) { + array[index++] = new KeyValuePair<TKey,TValue>(entries[i].key, entries[i].value); + } + } + } + + public Enumerator GetEnumerator() { + return new Enumerator(this, Enumerator.KeyValuePair); + } + + IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator() { + 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); + } + info.AddValue(VersionName, version); + +#if FEATURE_RANDOMIZED_STRING_HASHING + info.AddValue(ComparerName, HashHelpers.GetEqualityComparerForSerialization(comparer), typeof(IEqualityComparer<TKey>)); +#else + info.AddValue(ComparerName, comparer, typeof(IEqualityComparer<TKey>)); +#endif + + info.AddValue(HashSizeName, buckets == null ? 0 : buckets.Length); //This is the length of the bucket array. + if( buckets != null) { + KeyValuePair<TKey, TValue>[] array = new KeyValuePair<TKey, TValue>[Count]; + CopyTo(array, 0); + info.AddValue(KeyValuePairsName, array, typeof(KeyValuePair<TKey, TValue>[])); + } + } + + private int FindEntry(TKey key) { + if( key == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + + if (buckets != null) { + int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; + for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) { + if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i; + } + } + return -1; + } + + private void Initialize(int capacity) { + int size = HashHelpers.GetPrime(capacity); + buckets = new int[size]; + for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; + entries = new Entry[size]; + freeList = -1; + } + + private void Insert(TKey key, TValue value, bool add) { + + if( key == null ) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + + if (buckets == null) Initialize(0); + int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; + int targetBucket = hashCode % buckets.Length; + +#if FEATURE_RANDOMIZED_STRING_HASHING + int collisionCount = 0; +#endif + + 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++; + return; + } + +#if FEATURE_RANDOMIZED_STRING_HASHING + collisionCount++; +#endif + } + int index; + if (freeCount > 0) { + index = freeList; + freeList = entries[index].next; + freeCount--; + } + else { + if (count == entries.Length) + { + Resize(); + targetBucket = hashCode % buckets.Length; + } + index = count; + count++; + } + + entries[index].hashCode = hashCode; + entries[index].next = buckets[targetBucket]; + entries[index].key = key; + entries[index].value = value; + buckets[targetBucket] = index; + 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 + // be using randomized string hashing + + if (collisionCount > HashHelpers.HashCollisionThreshold && comparer == NonRandomizedStringEqualityComparer.Default) + { + 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 + + } + + public virtual void OnDeserialization(Object sender) { + SerializationInfo siInfo; + HashHelpers.SerializationInfoTable.TryGetValue(this, out siInfo); + + if (siInfo==null) { + // It might be necessary to call OnDeserialization from a container if the container object also implements + // OnDeserialization. However, remoting will call OnDeserialization again. + // We can return immediately if this function is called twice. + // Note we set remove the serialization info from the table at the end of this method. + return; + } + + int realVersion = siInfo.GetInt32(VersionName); + int hashsize = siInfo.GetInt32(HashSizeName); + comparer = (IEqualityComparer<TKey>)siInfo.GetValue(ComparerName, typeof(IEqualityComparer<TKey>)); + + if( hashsize != 0) { + buckets = new int[hashsize]; + for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; + entries = new Entry[hashsize]; + freeList = -1; + + KeyValuePair<TKey, TValue>[] array = (KeyValuePair<TKey, TValue>[]) + siInfo.GetValue(KeyValuePairsName, typeof(KeyValuePair<TKey, TValue>[])); + + if (array==null) { + ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MissingKeys); + } + + for (int i=0; i<array.Length; i++) { + if ( array[i].Key == null) { + ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_NullKey); + } + Insert(array[i].Key, array[i].Value, true); + } + } + else { + buckets = null; + } + + version = realVersion; + HashHelpers.SerializationInfoTable.Remove(this); + } + + private void Resize() { + Resize(HashHelpers.ExpandPrime(count), false); + } + + private void Resize(int newSize, bool forceNewHashCodes) { + Contract.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]; + Array.Copy(entries, 0, newEntries, 0, count); + if(forceNewHashCodes) { + for (int i = 0; i < count; i++) { + if(newEntries[i].hashCode != -1) { + newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF); + } + } + } + for (int i = 0; i < count; i++) { + if (newEntries[i].hashCode >= 0) { + int bucket = newEntries[i].hashCode % newSize; + newEntries[i].next = newBuckets[bucket]; + newBuckets[bucket] = i; + } + } + buckets = newBuckets; + entries = newEntries; + } + + public bool Remove(TKey key) { + if(key == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + + if (buckets != null) { + int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; + int bucket = hashCode % buckets.Length; + int last = -1; + for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) { + if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { + if (last < 0) { + buckets[bucket] = entries[i].next; + } + else { + entries[last].next = entries[i].next; + } + entries[i].hashCode = -1; + entries[i].next = freeList; + entries[i].key = default(TKey); + entries[i].value = default(TValue); + freeList = i; + freeCount++; + version++; + return true; + } + } + } + return false; + } + + public bool TryGetValue(TKey key, out TValue value) { + int i = FindEntry(key); + if (i >= 0) { + value = entries[i].value; + return true; + } + value = default(TValue); + 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) { + int i = FindEntry(key); + if (i >= 0) { + return entries[i].value; + } + return default(TValue); + } + + bool ICollection<KeyValuePair<TKey,TValue>>.IsReadOnly { + get { return false; } + } + + void ICollection<KeyValuePair<TKey,TValue>>.CopyTo(KeyValuePair<TKey,TValue>[] array, int index) { + CopyTo(array, index); + } + + void ICollection.CopyTo(Array array, int index) { + if (array == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (array.Rank != 1) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); + } + + if( array.GetLowerBound(0) != 0 ) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); + } + + if (index < 0 || index > array.Length) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (array.Length - index < Count) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + } + + KeyValuePair<TKey,TValue>[] pairs = array as KeyValuePair<TKey,TValue>[]; + if (pairs != null) { + CopyTo(pairs, index); + } + else if( array is DictionaryEntry[]) { + DictionaryEntry[] dictEntryArray = array as DictionaryEntry[]; + Entry[] entries = this.entries; + for (int i = 0; i < count; i++) { + if (entries[i].hashCode >= 0) { + dictEntryArray[index++] = new DictionaryEntry(entries[i].key, entries[i].value); + } + } + } + else { + object[] objects = array as object[]; + if (objects == null) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + } + + try { + int count = this.count; + Entry[] entries = this.entries; + for (int i = 0; i < count; i++) { + if (entries[i].hashCode >= 0) { + objects[index++] = new KeyValuePair<TKey,TValue>(entries[i].key, entries[i].value); + } + } + } + catch(ArrayTypeMismatchException) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + } + } + } + + IEnumerator IEnumerable.GetEnumerator() { + return new Enumerator(this, Enumerator.KeyValuePair); + } + + bool ICollection.IsSynchronized { + get { return false; } + } + + object ICollection.SyncRoot { + get { + if( _syncRoot == null) { + System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null); + } + return _syncRoot; + } + } + + bool IDictionary.IsFixedSize { + get { return false; } + } + + bool IDictionary.IsReadOnly { + get { return false; } + } + + ICollection IDictionary.Keys { + get { return (ICollection)Keys; } + } + + ICollection IDictionary.Values { + get { return (ICollection)Values; } + } + + object IDictionary.this[object key] { + get { + if( IsCompatibleKey(key)) { + int i = FindEntry((TKey)key); + if (i >= 0) { + return entries[i].value; + } + } + return null; + } + set { + if (key == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value); + + try { + TKey tempKey = (TKey)key; + try { + this[tempKey] = (TValue)value; + } + catch (InvalidCastException) { + ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue)); + } + } + catch (InvalidCastException) { + ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey)); + } + } + } + + private static bool IsCompatibleKey(object key) { + if( key == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + return (key is TKey); + } + + void IDictionary.Add(object key, object value) { + if (key == null) + { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + } + ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value); + + try { + TKey tempKey = (TKey)key; + + try { + Add(tempKey, (TValue)value); + } + catch (InvalidCastException) { + ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue)); + } + } + catch (InvalidCastException) { + ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey)); + } + } + + bool IDictionary.Contains(object key) { + if(IsCompatibleKey(key)) { + return ContainsKey((TKey)key); + } + + return false; + } + + IDictionaryEnumerator IDictionary.GetEnumerator() { + return new Enumerator(this, Enumerator.DictEntry); + } + + void IDictionary.Remove(object key) { + if(IsCompatibleKey(key)) { + Remove((TKey)key); + } + } + + [Serializable] + public struct Enumerator: IEnumerator<KeyValuePair<TKey,TValue>>, + IDictionaryEnumerator + { + private Dictionary<TKey,TValue> dictionary; + private int version; + private int index; + private KeyValuePair<TKey,TValue> current; + private int getEnumeratorRetType; // What should Enumerator.Current return? + + internal const int DictEntry = 1; + internal const int KeyValuePair = 2; + + internal Enumerator(Dictionary<TKey,TValue> dictionary, int getEnumeratorRetType) { + this.dictionary = dictionary; + version = dictionary.version; + index = 0; + this.getEnumeratorRetType = getEnumeratorRetType; + current = new KeyValuePair<TKey, TValue>(); + } + + public bool MoveNext() { + if (version != dictionary.version) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + } + + // Use unsigned comparison since we set index to dictionary.count+1 when the enumeration ends. + // dictionary.count+1 could be negative if dictionary.count is Int32.MaxValue + while ((uint)index < (uint)dictionary.count) { + if (dictionary.entries[index].hashCode >= 0) { + current = new KeyValuePair<TKey, TValue>(dictionary.entries[index].key, dictionary.entries[index].value); + index++; + return true; + } + index++; + } + + index = dictionary.count + 1; + current = new KeyValuePair<TKey, TValue>(); + return false; + } + + public KeyValuePair<TKey,TValue> Current { + get { return current; } + } + + public void Dispose() { + } + + object IEnumerator.Current { + get { + if( index == 0 || (index == dictionary.count + 1)) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + } + + if (getEnumeratorRetType == DictEntry) { + return new System.Collections.DictionaryEntry(current.Key, current.Value); + } else { + return new KeyValuePair<TKey, TValue>(current.Key, current.Value); + } + } + } + + void IEnumerator.Reset() { + if (version != dictionary.version) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + } + + index = 0; + current = new KeyValuePair<TKey, TValue>(); + } + + DictionaryEntry IDictionaryEnumerator.Entry { + get { + if( index == 0 || (index == dictionary.count + 1)) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + } + + return new DictionaryEntry(current.Key, current.Value); + } + } + + object IDictionaryEnumerator.Key { + get { + if( index == 0 || (index == dictionary.count + 1)) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + } + + return current.Key; + } + } + + object IDictionaryEnumerator.Value { + get { + if( index == 0 || (index == dictionary.count + 1)) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + } + + return current.Value; + } + } + } + + [DebuggerTypeProxy(typeof(Mscorlib_DictionaryKeyCollectionDebugView<,>))] + [DebuggerDisplay("Count = {Count}")] + [Serializable] + public sealed class KeyCollection: ICollection<TKey>, ICollection, IReadOnlyCollection<TKey> + { + private Dictionary<TKey,TValue> dictionary; + + public KeyCollection(Dictionary<TKey,TValue> dictionary) { + if (dictionary == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); + } + this.dictionary = dictionary; + } + + public Enumerator GetEnumerator() { + return new Enumerator(dictionary); + } + + public void CopyTo(TKey[] array, int index) { + if (array == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (index < 0 || index > array.Length) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (array.Length - index < dictionary.Count) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + } + + int count = dictionary.count; + Entry[] entries = dictionary.entries; + for (int i = 0; i < count; i++) { + if (entries[i].hashCode >= 0) array[index++] = entries[i].key; + } + } + + public int Count { + get { return dictionary.Count; } + } + + bool ICollection<TKey>.IsReadOnly { + get { return true; } + } + + void ICollection<TKey>.Add(TKey item){ + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); + } + + void ICollection<TKey>.Clear(){ + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); + } + + bool ICollection<TKey>.Contains(TKey item){ + return dictionary.ContainsKey(item); + } + + bool ICollection<TKey>.Remove(TKey item){ + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); + return false; + } + + IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator() { + return new Enumerator(dictionary); + } + + IEnumerator IEnumerable.GetEnumerator() { + return new Enumerator(dictionary); + } + + void ICollection.CopyTo(Array array, int index) { + if (array==null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (array.Rank != 1) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); + } + + if( array.GetLowerBound(0) != 0 ) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); + } + + if (index < 0 || index > array.Length) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (array.Length - index < dictionary.Count) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + } + + TKey[] keys = array as TKey[]; + if (keys != null) { + CopyTo(keys, index); + } + else { + object[] objects = array as object[]; + if (objects == null) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + } + + int count = dictionary.count; + Entry[] entries = dictionary.entries; + try { + for (int i = 0; i < count; i++) { + if (entries[i].hashCode >= 0) objects[index++] = entries[i].key; + } + } + catch(ArrayTypeMismatchException) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + } + } + } + + bool ICollection.IsSynchronized { + get { return false; } + } + + Object ICollection.SyncRoot { + get { return ((ICollection)dictionary).SyncRoot; } + } + + [Serializable] + public struct Enumerator : IEnumerator<TKey>, System.Collections.IEnumerator + { + private Dictionary<TKey, TValue> dictionary; + private int index; + private int version; + private TKey currentKey; + + internal Enumerator(Dictionary<TKey, TValue> dictionary) { + this.dictionary = dictionary; + version = dictionary.version; + index = 0; + currentKey = default(TKey); + } + + public void Dispose() { + } + + public bool MoveNext() { + if (version != dictionary.version) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + } + + while ((uint)index < (uint)dictionary.count) { + if (dictionary.entries[index].hashCode >= 0) { + currentKey = dictionary.entries[index].key; + index++; + return true; + } + index++; + } + + index = dictionary.count + 1; + currentKey = default(TKey); + return false; + } + + public TKey Current { + get { + return currentKey; + } + } + + Object System.Collections.IEnumerator.Current { + get { + if( index == 0 || (index == dictionary.count + 1)) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + } + + return currentKey; + } + } + + void System.Collections.IEnumerator.Reset() { + if (version != dictionary.version) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + } + + index = 0; + currentKey = default(TKey); + } + } + } + + [DebuggerTypeProxy(typeof(Mscorlib_DictionaryValueCollectionDebugView<,>))] + [DebuggerDisplay("Count = {Count}")] + [Serializable] + public sealed class ValueCollection: ICollection<TValue>, ICollection, IReadOnlyCollection<TValue> + { + private Dictionary<TKey,TValue> dictionary; + + public ValueCollection(Dictionary<TKey,TValue> dictionary) { + if (dictionary == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); + } + this.dictionary = dictionary; + } + + public Enumerator GetEnumerator() { + return new Enumerator(dictionary); + } + + public void CopyTo(TValue[] array, int index) { + if (array == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (index < 0 || index > array.Length) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (array.Length - index < dictionary.Count) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + } + + int count = dictionary.count; + Entry[] entries = dictionary.entries; + for (int i = 0; i < count; i++) { + if (entries[i].hashCode >= 0) array[index++] = entries[i].value; + } + } + + public int Count { + get { return dictionary.Count; } + } + + bool ICollection<TValue>.IsReadOnly { + get { return true; } + } + + void ICollection<TValue>.Add(TValue item){ + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); + } + + bool ICollection<TValue>.Remove(TValue item){ + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); + return false; + } + + void ICollection<TValue>.Clear(){ + ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); + } + + bool ICollection<TValue>.Contains(TValue item){ + return dictionary.ContainsValue(item); + } + + IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator() { + return new Enumerator(dictionary); + } + + IEnumerator IEnumerable.GetEnumerator() { + return new Enumerator(dictionary); + } + + void ICollection.CopyTo(Array array, int index) { + if (array == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); + } + + if (array.Rank != 1) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); + } + + if( array.GetLowerBound(0) != 0 ) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); + } + + if (index < 0 || index > array.Length) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (array.Length - index < dictionary.Count) + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); + + TValue[] values = array as TValue[]; + if (values != null) { + CopyTo(values, index); + } + else { + object[] objects = array as object[]; + if (objects == null) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + } + + int count = dictionary.count; + Entry[] entries = dictionary.entries; + try { + for (int i = 0; i < count; i++) { + if (entries[i].hashCode >= 0) objects[index++] = entries[i].value; + } + } + catch(ArrayTypeMismatchException) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + } + } + } + + bool ICollection.IsSynchronized { + get { return false; } + } + + Object ICollection.SyncRoot { + get { return ((ICollection)dictionary).SyncRoot; } + } + + [Serializable] + public struct Enumerator : IEnumerator<TValue>, System.Collections.IEnumerator + { + private Dictionary<TKey, TValue> dictionary; + private int index; + private int version; + private TValue currentValue; + + internal Enumerator(Dictionary<TKey, TValue> dictionary) { + this.dictionary = dictionary; + version = dictionary.version; + index = 0; + currentValue = default(TValue); + } + + public void Dispose() { + } + + public bool MoveNext() { + if (version != dictionary.version) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + } + + while ((uint)index < (uint)dictionary.count) { + if (dictionary.entries[index].hashCode >= 0) { + currentValue = dictionary.entries[index].value; + index++; + return true; + } + index++; + } + index = dictionary.count + 1; + currentValue = default(TValue); + return false; + } + + public TValue Current { + get { + return currentValue; + } + } + + Object System.Collections.IEnumerator.Current { + get { + if( index == 0 || (index == dictionary.count + 1)) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + } + + return currentValue; + } + } + + void System.Collections.IEnumerator.Reset() { + if (version != dictionary.version) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.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 new file mode 100644 index 0000000000..b845d64fed --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs @@ -0,0 +1,621 @@ +// 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. + +using System; +using System.Collections; +using System.Collections.Generic; +using System.Security; +using System.Runtime.Serialization; + +namespace System.Collections.Generic +{ + using System.Globalization; + using System.Runtime; + using System.Runtime.CompilerServices; + using System.Diagnostics.Contracts; + + [Serializable] + [TypeDependencyAttribute("System.Collections.Generic.ObjectEqualityComparer`1")] + public abstract class EqualityComparer<T> : IEqualityComparer, IEqualityComparer<T> + { + static readonly EqualityComparer<T> defaultComparer = CreateComparer(); + + public static EqualityComparer<T> Default { + get { + Contract.Ensures(Contract.Result<EqualityComparer<T>>() != null); + return defaultComparer; + } + } + + // + // 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); + + object result = null; + RuntimeType t = (RuntimeType)typeof(T); + + // Specialize type byte for performance reasons + if (t == typeof(byte)) { + result = new ByteEqualityComparer(); + } + // If T implements IEquatable<T> return a GenericEqualityComparer<T> + else if (typeof(IEquatable<T>).IsAssignableFrom(t)) + { + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericEqualityComparer<int>), t); + } + else if (default(T) == null) // Reference type/Nullable + { + // If T is a Nullable<U> where U implements IEquatable<U> return a NullableEqualityComparer<U> + if (t.IsGenericType && t.GetGenericTypeDefinition() == typeof(Nullable<>)) { + RuntimeType u = (RuntimeType)t.GetGenericArguments()[0]; + if (typeof(IEquatable<>).MakeGenericType(u).IsAssignableFrom(u)) { + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableEqualityComparer<int>), u); + } + } + } + // See the METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST and METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST_LONG cases in getILIntrinsicImplementation + else if (t.IsEnum) { + TypeCode underlyingTypeCode = Type.GetTypeCode(Enum.GetUnderlyingType(t)); + + // Depending on the enum type, we need to special case the comparers so that we avoid boxing + // Note: We have different comparers for Short and SByte because for those types we need to make sure we call GetHashCode on the actual underlying type as the + // implementation of GetHashCode is more complex than for the other types. + switch (underlyingTypeCode) { + case TypeCode.Int16: // short + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ShortEnumEqualityComparer<short>), t); + break; + case TypeCode.SByte: + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(SByteEnumEqualityComparer<sbyte>), t); + break; + case TypeCode.Int32: + case TypeCode.UInt32: + case TypeCode.Byte: + case TypeCode.UInt16: //ushort + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(EnumEqualityComparer<int>), t); + break; + case TypeCode.Int64: + case TypeCode.UInt64: + result = RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(LongEnumEqualityComparer<long>), t); + break; + } + } + + return result != null ? + (EqualityComparer<T>)result : + new ObjectEqualityComparer<T>(); // Fallback to ObjectEqualityComparer, which uses boxing + } + + [Pure] + public abstract bool Equals(T x, T y); + [Pure] + public abstract int GetHashCode(T obj); + + internal virtual int IndexOf(T[] array, T value, int startIndex, int count) { + int endIndex = startIndex + count; + for (int i = startIndex; i < endIndex; i++) { + if (Equals(array[i], value)) return i; + } + return -1; + } + + internal virtual int LastIndexOf(T[] array, T value, int startIndex, int count) { + int endIndex = startIndex - count + 1; + for (int i = startIndex; i >= endIndex; i--) { + if (Equals(array[i], value)) return i; + } + return -1; + } + + int IEqualityComparer.GetHashCode(object obj) { + if (obj == null) return 0; + if (obj is T) return GetHashCode((T)obj); + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArgumentForComparison); + return 0; + } + + bool IEqualityComparer.Equals(object x, object y) { + if (x == y) return true; + if (x == null || y == null) return false; + if ((x is T) && (y is T)) return Equals((T)x, (T)y); + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArgumentForComparison); + return false; + } + } + + // The methods in this class look identical to the inherited methods, but the calls + // to Equal bind to IEquatable<T>.Equals(T) instead of Object.Equals(Object) + [Serializable] + internal class GenericEqualityComparer<T>: EqualityComparer<T> where T: IEquatable<T> + { + [Pure] + public override bool Equals(T x, T y) { + if (x != null) { + if (y != null) return x.Equals(y); + return false; + } + if (y != null) return false; + return true; + } + + [Pure] + public override int GetHashCode(T obj) { + if (obj == null) return 0; + return obj.GetHashCode(); + } + + internal override int IndexOf(T[] array, T value, int startIndex, int count) { + int endIndex = startIndex + count; + if (value == null) { + for (int i = startIndex; i < endIndex; i++) { + if (array[i] == null) return i; + } + } + else { + for (int i = startIndex; i < endIndex; i++) { + if (array[i] != null && array[i].Equals(value)) return i; + } + } + return -1; + } + + internal override int LastIndexOf(T[] array, T value, int startIndex, int count) { + int endIndex = startIndex - count + 1; + if (value == null) { + for (int i = startIndex; i >= endIndex; i--) { + if (array[i] == null) return i; + } + } + else { + for (int i = startIndex; i >= endIndex; i--) { + if (array[i] != null && array[i].Equals(value)) return i; + } + } + return -1; + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj){ + GenericEqualityComparer<T> comparer = obj as GenericEqualityComparer<T>; + return comparer != null; + } + + public override int GetHashCode() { + return this.GetType().Name.GetHashCode(); + } + } + + [Serializable] + internal class NullableEqualityComparer<T> : EqualityComparer<Nullable<T>> where T : struct, IEquatable<T> + { + [Pure] + public override bool Equals(Nullable<T> x, Nullable<T> y) { + if (x.HasValue) { + if (y.HasValue) return x.value.Equals(y.value); + return false; + } + if (y.HasValue) return false; + return true; + } + + [Pure] + public override int GetHashCode(Nullable<T> obj) { + return obj.GetHashCode(); + } + + internal override int IndexOf(Nullable<T>[] array, Nullable<T> value, int startIndex, int count) { + int endIndex = startIndex + count; + if (!value.HasValue) { + for (int i = startIndex; i < endIndex; i++) { + if (!array[i].HasValue) return i; + } + } + else { + for (int i = startIndex; i < endIndex; i++) { + if (array[i].HasValue && array[i].value.Equals(value.value)) return i; + } + } + return -1; + } + + internal override int LastIndexOf(Nullable<T>[] array, Nullable<T> value, int startIndex, int count) { + int endIndex = startIndex - count + 1; + if (!value.HasValue) { + for (int i = startIndex; i >= endIndex; i--) { + if (!array[i].HasValue) return i; + } + } + else { + for (int i = startIndex; i >= endIndex; i--) { + if (array[i].HasValue && array[i].value.Equals(value.value)) return i; + } + } + return -1; + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj){ + NullableEqualityComparer<T> comparer = obj as NullableEqualityComparer<T>; + return comparer != null; + } + + public override int GetHashCode() { + return this.GetType().Name.GetHashCode(); + } + } + + [Serializable] + internal class ObjectEqualityComparer<T>: EqualityComparer<T> + { + [Pure] + public override bool Equals(T x, T y) { + if (x != null) { + if (y != null) return x.Equals(y); + return false; + } + if (y != null) return false; + return true; + } + + [Pure] + public override int GetHashCode(T obj) { + if (obj == null) return 0; + return obj.GetHashCode(); + } + + internal override int IndexOf(T[] array, T value, int startIndex, int count) { + int endIndex = startIndex + count; + if (value == null) { + for (int i = startIndex; i < endIndex; i++) { + if (array[i] == null) return i; + } + } + else { + for (int i = startIndex; i < endIndex; i++) { + if (array[i] != null && array[i].Equals(value)) return i; + } + } + return -1; + } + + internal override int LastIndexOf(T[] array, T value, int startIndex, int count) { + int endIndex = startIndex - count + 1; + if (value == null) { + for (int i = startIndex; i >= endIndex; i--) { + if (array[i] == null) return i; + } + } + else { + for (int i = startIndex; i >= endIndex; i--) { + if (array[i] != null && array[i].Equals(value)) return i; + } + } + return -1; + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj){ + ObjectEqualityComparer<T> comparer = obj as ObjectEqualityComparer<T>; + return comparer != null; + } + + public override int GetHashCode() { + return this.GetType().Name.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> + + internal class NonRandomizedStringEqualityComparer : GenericEqualityComparer<string> { + static IEqualityComparer<string> s_nonRandomizedComparer; + + internal static new IEqualityComparer<string> Default { + get { + if (s_nonRandomizedComparer == null) { + s_nonRandomizedComparer = new NonRandomizedStringEqualityComparer(); + } + return s_nonRandomizedComparer; + } + } + + [Pure] + public override int GetHashCode(string obj) { + if (obj == null) return 0; + 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> + { + [Pure] + public override bool Equals(byte x, byte y) { + return x == y; + } + + [Pure] + public override int GetHashCode(byte b) { + 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"); + if (startIndex < 0) + throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_Index")); + if (count < 0) + throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_Count")); + if (count > array.Length - startIndex) + throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); + Contract.EndContractBlock(); + if (count == 0) return -1; + fixed (byte* pbytes = array) { + return Buffer.IndexOfByte(pbytes, value, startIndex, count); + } + } + + internal override int LastIndexOf(byte[] array, byte value, int startIndex, int count) { + int endIndex = startIndex - count + 1; + for (int i = startIndex; i >= endIndex; i--) { + if (array[i] == value) return i; + } + return -1; + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj){ + ByteEqualityComparer comparer = obj as ByteEqualityComparer; + return comparer != null; + } + + public override int GetHashCode() { + return this.GetType().Name.GetHashCode(); + } + } + + [Serializable] + internal class EnumEqualityComparer<T> : EqualityComparer<T>, ISerializable where T : struct + { + [Pure] + public override bool Equals(T x, T y) { + int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(x); + int y_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(y); + return x_final == y_final; + } + + [Pure] + public override int GetHashCode(T obj) { + int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(obj); + return x_final.GetHashCode(); + } + + public EnumEqualityComparer() { } + + // 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) { + info.SetType(typeof(ObjectEqualityComparer<T>)); + } + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj){ + EnumEqualityComparer<T> comparer = obj as EnumEqualityComparer<T>; + return comparer != null; + } + + public override int GetHashCode() { + return this.GetType().Name.GetHashCode(); + } + } + + [Serializable] + internal sealed class SByteEnumEqualityComparer<T> : EnumEqualityComparer<T>, ISerializable where T : struct + { + public SByteEnumEqualityComparer() { } + + // This is used by the serialization engine. + public SByteEnumEqualityComparer(SerializationInfo information, StreamingContext context) { } + + [Pure] + public override int GetHashCode(T obj) { + int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(obj); + return ((sbyte)x_final).GetHashCode(); + } + } + + [Serializable] + internal sealed class ShortEnumEqualityComparer<T> : EnumEqualityComparer<T>, ISerializable where T : struct + { + public ShortEnumEqualityComparer() { } + + // This is used by the serialization engine. + public ShortEnumEqualityComparer(SerializationInfo information, StreamingContext context) { } + + [Pure] + public override int GetHashCode(T obj) { + int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(obj); + return ((short)x_final).GetHashCode(); + } + } + + [Serializable] + internal sealed class LongEnumEqualityComparer<T> : EqualityComparer<T>, ISerializable where T : struct + { + [Pure] + public override bool Equals(T x, T y) { + long x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCastLong(x); + long y_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCastLong(y); + return x_final == y_final; + } + + [Pure] + public override int GetHashCode(T obj) { + long x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCastLong(obj); + 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; + } + + public override int GetHashCode() { + return this.GetType().Name.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>)); + } + } + +#if FEATURE_RANDOMIZED_STRING_HASHING + // This type is not serializeable by design. It does not exist in previous versions and will be removed + // Once we move the framework to using secure hashing by default. + internal sealed class RandomizedStringEqualityComparer : IEqualityComparer<String>, IEqualityComparer, IWellKnownStringEqualityComparer + { + private long _entropy; + + public RandomizedStringEqualityComparer() { + _entropy = HashHelpers.GetEntropy(); + } + + public new bool Equals(object x, object y) { + if (x == y) return true; + if (x == null || y == null) return false; + if ((x is string) && (y is string)) return Equals((string)x, (string)y); + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArgumentForComparison); + return false; + } + + [Pure] + public bool Equals(string x, string y) { + if (x != null) { + if (y != null) return x.Equals(y); + return false; + } + if (y != null) return false; + return true; + } + + [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; + + string sObj = obj as string; + if(sObj != null) return String.InternalMarvin32HashString(sObj, sObj.Length, _entropy); + + return obj.GetHashCode(); + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj) { + RandomizedStringEqualityComparer comparer = obj as RandomizedStringEqualityComparer; + return (comparer != null) && (this._entropy == comparer._entropy); + } + + public override int GetHashCode() { + return (this.GetType().Name.GetHashCode() ^ ((int) (_entropy & 0x7FFFFFFF))); + } + + + IEqualityComparer IWellKnownStringEqualityComparer.GetRandomizedEqualityComparer() { + return new RandomizedStringEqualityComparer(); + } + + // We want to serialize the old comparer. + IEqualityComparer IWellKnownStringEqualityComparer.GetEqualityComparerForSerialization() { + return EqualityComparer<string>.Default; + } + } + + // This type is not serializeable by design. It does not exist in previous versions and will be removed + // Once we move the framework to using secure hashing by default. + internal sealed class RandomizedObjectEqualityComparer : IEqualityComparer, IWellKnownStringEqualityComparer + { + private long _entropy; + + public RandomizedObjectEqualityComparer() { + _entropy = HashHelpers.GetEntropy(); + } + + [Pure] + public new bool Equals(Object x, Object y) { + if (x != null) { + if (y != null) return x.Equals(y); + return false; + } + if (y != null) return false; + return true; + } + + [Pure] + [SecuritySafeCritical] + public int GetHashCode(Object obj) { + if(obj == null) return 0; + + string sObj = obj as string; + if(sObj != null) return String.InternalMarvin32HashString(sObj, sObj.Length, _entropy); + + return obj.GetHashCode(); + } + + // Equals method for the comparer itself. + public override bool Equals(Object obj){ + RandomizedObjectEqualityComparer comparer = obj as RandomizedObjectEqualityComparer; + return (comparer != null) && (this._entropy == comparer._entropy); + } + + public override int GetHashCode() { + return (this.GetType().Name.GetHashCode() ^ ((int) (_entropy & 0x7FFFFFFF))); + } + + IEqualityComparer IWellKnownStringEqualityComparer.GetRandomizedEqualityComparer() { + return new RandomizedObjectEqualityComparer(); + } + + // We want to serialize the old comparer, which in this case was null. + IEqualityComparer IWellKnownStringEqualityComparer.GetEqualityComparerForSerialization() { + return null; + } + } +#endif +} + diff --git a/src/mscorlib/src/System/Collections/Generic/ICollection.cs b/src/mscorlib/src/System/Collections/Generic/ICollection.cs new file mode 100644 index 0000000000..741e8cc79b --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/ICollection.cs @@ -0,0 +1,52 @@ +// 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. + +/*============================================================ +** +** Interface: ICollection +** +** +** +** +** Purpose: Base interface for all generic collections. +** +** +===========================================================*/ +namespace System.Collections.Generic { + using System; + using System.Runtime.CompilerServices; + using System.Diagnostics.Contracts; + + // Base interface for all collections, defining enumerators, size, and + // synchronization methods. + + // Note that T[] : IList<T>, and we want to ensure that if you use + // IList<YourValueType>, we ensure a YourValueType[] can be used + // without jitting. Hence the TypeDependencyAttribute on SZArrayHelper. + // This is a special workaround internally though - see VM\compile.cpp. + // The same attribute is on IEnumerable<T> and ICollection<T>. + [TypeDependencyAttribute("System.SZArrayHelper")] + public interface ICollection<T> : IEnumerable<T> + { + // Number of items in the collections. + int Count { get; } + + bool IsReadOnly { get; } + + void Add(T item); + + void Clear(); + + bool Contains(T item); + + // CopyTo copies a collection into an Array, starting at a particular + // index into the array. + // + void CopyTo(T[] array, int arrayIndex); + + //void CopyTo(int sourceIndex, T[] destinationArray, int destinationIndex, int count); + + bool Remove(T item); + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/IComparer.cs b/src/mscorlib/src/System/Collections/Generic/IComparer.cs new file mode 100644 index 0000000000..7b9e97ff0e --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/IComparer.cs @@ -0,0 +1,30 @@ +// 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. + +/*============================================================ +** +** Interface: IComparer +** +** +** +** +** Purpose: Interface for comparing two generic Objects. +** +** +===========================================================*/ +namespace System.Collections.Generic { + + using System; + // The generic IComparer interface implements a method that compares + // two objects. It is used in conjunction with the Sort and + // BinarySearch methods on the Array, List, and SortedList classes. + public interface IComparer<in T> + { + // Compares two objects. An implementation of this method must return a + // value less than zero if x is less than y, zero if x is equal to y, or a + // value greater than zero if x is greater than y. + // + int Compare(T x, T y); + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/IDictionary.cs b/src/mscorlib/src/System/Collections/Generic/IDictionary.cs new file mode 100644 index 0000000000..2a2da944d3 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/IDictionary.cs @@ -0,0 +1,58 @@ +// 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. + +/*============================================================ +** +** Interface: IDictionary +** +** +** +** +** Purpose: Base interface for all generic dictionaries. +** +** +===========================================================*/ +namespace System.Collections.Generic { + using System; + using System.Diagnostics.Contracts; + + // An IDictionary is a possibly unordered set of key-value pairs. + // Keys can be any non-null object. Values can be any object. + // You can look up a value in an IDictionary via the default indexed + // property, Items. + public interface IDictionary<TKey, TValue> : ICollection<KeyValuePair<TKey, TValue>> + { + // Interfaces are not serializable + // The Item property provides methods to read and edit entries + // in the Dictionary. + TValue this[TKey key] { + get; + set; + } + + // Returns a collections of the keys in this dictionary. + ICollection<TKey> Keys { + get; + } + + // Returns a collections of the values in this dictionary. + ICollection<TValue> Values { + get; + } + + // Returns whether this dictionary contains a particular key. + // + bool ContainsKey(TKey key); + + // Adds a key-value pair to the dictionary. + // + void Add(TKey key, TValue value); + + // Removes a particular key from the dictionary. + // + bool Remove(TKey key); + + bool TryGetValue(TKey key, out TValue value); + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/IEnumerable.cs b/src/mscorlib/src/System/Collections/Generic/IEnumerable.cs new file mode 100644 index 0000000000..67f35ce675 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/IEnumerable.cs @@ -0,0 +1,38 @@ +// 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. + +/*============================================================ +** +** Interface: IEnumerable +** +** +** +** +** Purpose: Interface for providing generic IEnumerators +** +** +===========================================================*/ +namespace System.Collections.Generic { + using System; + using System.Collections; + using System.Runtime.InteropServices; + using System.Runtime.CompilerServices; + using System.Diagnostics.Contracts; + + // Implement this interface if you need to support foreach semantics. + + // Note that T[] : IList<T>, and we want to ensure that if you use + // IList<YourValueType>, we ensure a YourValueType[] can be used + // without jitting. Hence the TypeDependencyAttribute on SZArrayHelper. + // This is a special workaround internally though - see VM\compile.cpp. + // The same attribute is on IList<T> and ICollection<T>. + [TypeDependencyAttribute("System.SZArrayHelper")] + public interface IEnumerable<out T> : IEnumerable + { + // Returns an IEnumerator for this enumerable Object. The enumerator provides + // a simple way to access all the contents of a collection. + /// <include file='doc\IEnumerable.uex' path='docs/doc[@for="IEnumerable.GetEnumerator"]/*' /> + new IEnumerator<T> GetEnumerator(); + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/IEnumerator.cs b/src/mscorlib/src/System/Collections/Generic/IEnumerator.cs new file mode 100644 index 0000000000..335616757b --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/IEnumerator.cs @@ -0,0 +1,35 @@ +// 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. + +/*============================================================ +** +** Interface: IEnumerator +** +** +** +** +** Purpose: Base interface for all generic enumerators. +** +** +===========================================================*/ +namespace System.Collections.Generic { + using System; + using System.Runtime.InteropServices; + + // Base interface for all generic enumerators, providing a simple approach + // to iterating over a collection. + public interface IEnumerator<out T> : IDisposable, IEnumerator + { + // Returns the current element of the enumeration. The returned value is + // undefined before the first call to MoveNext and following a + // call to MoveNext that returned false. Multiple calls to + // GetCurrent with no intervening calls to MoveNext + // will return the same object. + // + /// <include file='doc\IEnumerator.uex' path='docs/doc[@for="IEnumerator.Current"]/*' /> + new T Current { + get; + } + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/IEqualityComparer.cs b/src/mscorlib/src/System/Collections/Generic/IEqualityComparer.cs new file mode 100644 index 0000000000..b6ac3be006 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/IEqualityComparer.cs @@ -0,0 +1,19 @@ +// 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. + +// + +namespace System.Collections.Generic { + using System; + + // The generic IEqualityComparer interface implements methods to if check two objects are equal + // and generate Hashcode for an object. + // It is use in Dictionary class. + public interface IEqualityComparer<in T> + { + bool Equals(T x, T y); + int GetHashCode(T obj); + } +} + diff --git a/src/mscorlib/src/System/Collections/Generic/IList.cs b/src/mscorlib/src/System/Collections/Generic/IList.cs new file mode 100644 index 0000000000..75ca0a9b00 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/IList.cs @@ -0,0 +1,54 @@ +// 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. + +/*============================================================ +** +** Interface: IList +** +** +** +** +** Purpose: Base interface for all generic lists. +** +** +===========================================================*/ +namespace System.Collections.Generic { + + using System; + using System.Collections; + using System.Runtime.CompilerServices; + using System.Diagnostics.Contracts; + + // An IList is an ordered collection of objects. The exact ordering + // is up to the implementation of the list, ranging from a sorted + // order to insertion order. + + // Note that T[] : IList<T>, and we want to ensure that if you use + // IList<YourValueType>, we ensure a YourValueType[] can be used + // without jitting. Hence the TypeDependencyAttribute on SZArrayHelper. + // This is a special workaround internally though - see VM\compile.cpp. + // The same attribute is on IEnumerable<T> and ICollection<T>. + [TypeDependencyAttribute("System.SZArrayHelper")] + public interface IList<T> : ICollection<T> + { + // The Item property provides methods to read and edit entries in the List. + T this[int index] { + get; + set; + } + + // Returns the index of a particular item, if it is in the list. + // Returns -1 if the item isn't in the list. + int IndexOf(T item); + + // Inserts value into the list at position index. + // index must be non-negative and less than or equal to the + // number of elements in the list. If index equals the number + // of items in the list, then value is appended to the end. + void Insert(int index, T item); + + // Removes the item at position index. + void RemoveAt(int index); + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/IReadOnlyCollection.cs b/src/mscorlib/src/System/Collections/Generic/IReadOnlyCollection.cs new file mode 100644 index 0000000000..13bc718760 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/IReadOnlyCollection.cs @@ -0,0 +1,34 @@ +// 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. + +/*============================================================ +** +** Interface: IReadOnlyCollection<T> +** +** +** +** Purpose: Base interface for read-only generic lists. +** +===========================================================*/ +using System; +using System.Diagnostics.Contracts; +using System.Runtime.CompilerServices; + +namespace System.Collections.Generic +{ + + // Provides a read-only, covariant view of a generic list. + + // Note that T[] : IReadOnlyList<T>, and we want to ensure that if you use + // IList<YourValueType>, we ensure a YourValueType[] can be used + // without jitting. Hence the TypeDependencyAttribute on SZArrayHelper. + // This is a special workaround internally though - see VM\compile.cpp. + // The same attribute is on IList<T>, IEnumerable<T>, ICollection<T>, and IReadOnlyList<T>. + [TypeDependencyAttribute("System.SZArrayHelper")] + // If we ever implement more interfaces on IReadOnlyCollection, we should also update RuntimeTypeCache.PopulateInterfaces() in rttype.cs + public interface IReadOnlyCollection<out T> : IEnumerable<T> + { + int Count { get; } + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/IReadOnlyDictionary.cs b/src/mscorlib/src/System/Collections/Generic/IReadOnlyDictionary.cs new file mode 100644 index 0000000000..3603b9a4ea --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/IReadOnlyDictionary.cs @@ -0,0 +1,29 @@ +// 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. + +/*============================================================ +** +** Interface: IReadOnlyDictionary<TKey, TValue> +** +** +** +** Purpose: Base interface for read-only generic dictionaries. +** +===========================================================*/ +using System; +using System.Diagnostics.Contracts; + +namespace System.Collections.Generic +{ + // Provides a read-only view of a generic dictionary. + public interface IReadOnlyDictionary<TKey, TValue> : IReadOnlyCollection<KeyValuePair<TKey, TValue>> + { + bool ContainsKey(TKey key); + bool TryGetValue(TKey key, out TValue value); + + TValue this[TKey key] { get; } + IEnumerable<TKey> Keys { get; } + IEnumerable<TValue> Values { get; } + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/IReadOnlyList.cs b/src/mscorlib/src/System/Collections/Generic/IReadOnlyList.cs new file mode 100644 index 0000000000..77366f0b2f --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/IReadOnlyList.cs @@ -0,0 +1,34 @@ +// 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. + +/*============================================================ +** +** Interface: IReadOnlyList<T> +** +** +** +** Purpose: Base interface for read-only generic lists. +** +===========================================================*/ +using System; +using System.Diagnostics.Contracts; +using System.Runtime.CompilerServices; + +namespace System.Collections.Generic +{ + + // Provides a read-only, covariant view of a generic list. + + // Note that T[] : IReadOnlyList<T>, and we want to ensure that if you use + // IList<YourValueType>, we ensure a YourValueType[] can be used + // without jitting. Hence the TypeDependencyAttribute on SZArrayHelper. + // This is a special workaround internally though - see VM\compile.cpp. + // The same attribute is on IList<T>, IEnumerable<T>, ICollection<T> and IReadOnlyCollection<T>. + [TypeDependencyAttribute("System.SZArrayHelper")] + // If we ever implement more interfaces on IReadOnlyList, we should also update RuntimeTypeCache.PopulateInterfaces() in rttype.cs + public interface IReadOnlyList<out T> : IReadOnlyCollection<T> + { + T this[int index] { get; } + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/KeyNotFoundException.cs b/src/mscorlib/src/System/Collections/Generic/KeyNotFoundException.cs new file mode 100644 index 0000000000..ffcd0405fd --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/KeyNotFoundException.cs @@ -0,0 +1,45 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +/*============================================================================= +** +** +** +** +** +** Purpose: Exception class for Hashtable and Dictionary. +** +** +=============================================================================*/ + +namespace System.Collections.Generic { + + using System; + using System.Runtime.Remoting; + using System.Runtime.Serialization; + + [Serializable] + [System.Runtime.InteropServices.ComVisible(true)] + public class KeyNotFoundException : SystemException, ISerializable { + + public KeyNotFoundException () + : base(Environment.GetResourceString("Arg_KeyNotFound")) { + SetErrorCode(System.__HResults.COR_E_KEYNOTFOUND); + } + + public KeyNotFoundException(String message) + : base(message) { + SetErrorCode(System.__HResults.COR_E_KEYNOTFOUND); + } + + public KeyNotFoundException(String message, Exception innerException) + : base(message, innerException) { + SetErrorCode(System.__HResults.COR_E_KEYNOTFOUND); + } + + + protected KeyNotFoundException(SerializationInfo info, StreamingContext context) : base(info, context) { + } + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs b/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs new file mode 100644 index 0000000000..17e1c531f1 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs @@ -0,0 +1,56 @@ +// 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. + +/*============================================================ +** +** Interface: KeyValuePair +** +** +** +** +** Purpose: Generic key-value pair for dictionary enumerators. +** +** +===========================================================*/ +namespace System.Collections.Generic { + + using System; + using System.Text; + + // 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>. + [Serializable] + public struct KeyValuePair<TKey, TValue> { + private TKey key; + private TValue value; + + public KeyValuePair(TKey key, TValue value) { + this.key = key; + this.value = value; + } + + public TKey Key { + get { return key; } + } + + public TValue Value { + get { return value; } + } + + public override string ToString() { + StringBuilder s = StringBuilderCache.Acquire(); + s.Append('['); + if( Key != null) { + s.Append(Key.ToString()); + } + s.Append(", "); + if( Value != null) { + s.Append(Value.ToString()); + } + s.Append(']'); + return StringBuilderCache.GetStringAndRelease(s); + } + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/List.cs b/src/mscorlib/src/System/Collections/Generic/List.cs new file mode 100644 index 0000000000..ae3356d372 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/List.cs @@ -0,0 +1,1120 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +/*============================================================ +** +** +** +** +** Purpose: Implements a generic, dynamically sized list as an +** array. +** +** +===========================================================*/ +namespace System.Collections.Generic { + + using System; + using System.Runtime; + using System.Runtime.Versioning; + using System.Diagnostics; + using System.Diagnostics.Contracts; + using System.Collections.ObjectModel; + using System.Security.Permissions; + + // Implements a variable-size List that uses an array of objects to store the + // elements. A List has a capacity, which is the allocated length + // of the internal array. As elements are added to a List, the capacity + // of the List is automatically increased as required by reallocating the + // internal array. + // + [DebuggerTypeProxy(typeof(Mscorlib_CollectionDebugView<>))] + [DebuggerDisplay("Count = {Count}")] + [Serializable] + public class List<T> : IList<T>, System.Collections.IList, IReadOnlyList<T> + { + private const int _defaultCapacity = 4; + + private T[] _items; + [ContractPublicPropertyName("Count")] + private int _size; + private int _version; + [NonSerialized] + private Object _syncRoot; + + static readonly T[] _emptyArray = new T[0]; + + // Constructs a List. The list is initially empty and has a capacity + // of zero. Upon adding the first element to the list the capacity is + // increased to _defaultCapacity, and then increased in multiples of two + // as required. + public List() { + _items = _emptyArray; + } + + // Constructs a List with a given initial capacity. The list is + // initially empty, but will have room for the given number of elements + // before any reallocations are required. + // + public List(int capacity) { + if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + Contract.EndContractBlock(); + + if (capacity == 0) + _items = _emptyArray; + else + _items = new T[capacity]; + } + + // Constructs a List, copying the contents of the given collection. The + // size and capacity of the new list will both be equal to the size of the + // given collection. + // + public List(IEnumerable<T> collection) { + if (collection==null) + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); + Contract.EndContractBlock(); + + ICollection<T> c = collection as ICollection<T>; + if( c != null) { + int count = c.Count; + if (count == 0) + { + _items = _emptyArray; + } + else { + _items = new T[count]; + c.CopyTo(_items, 0); + _size = count; + } + } + 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); + } + } + } + } + + // Gets and sets the capacity of this list. The capacity is the size of + // the internal array used to hold items. When set, the internal + // array of the list is reallocated to the given capacity. + // + public int Capacity { + get { + Contract.Ensures(Contract.Result<int>() >= 0); + return _items.Length; + } + set { + if (value < _size) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity); + } + Contract.EndContractBlock(); + + if (value != _items.Length) { + if (value > 0) { + T[] newItems = new T[value]; + if (_size > 0) { + Array.Copy(_items, 0, newItems, 0, _size); + } + _items = newItems; + } + else { + _items = _emptyArray; + } + } + } + } + + // Read-only property describing how many elements are in the List. + public int Count { + get { + Contract.Ensures(Contract.Result<int>() >= 0); + return _size; + } + } + + bool System.Collections.IList.IsFixedSize { + get { return false; } + } + + + // Is this List read-only? + bool ICollection<T>.IsReadOnly { + get { return false; } + } + + bool System.Collections.IList.IsReadOnly { + get { return false; } + } + + // Is this List synchronized (thread-safe)? + bool System.Collections.ICollection.IsSynchronized { + get { return false; } + } + + // Synchronization root for this object. + Object System.Collections.ICollection.SyncRoot { + get { + if( _syncRoot == null) { + System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null); + } + return _syncRoot; + } + } + // Sets or Gets the element at the given index. + // + public T this[int index] { + get { + // Following trick can reduce the range check by one + if ((uint) index >= (uint)_size) { + ThrowHelper.ThrowArgumentOutOfRange_IndexException(); + } + Contract.EndContractBlock(); + return _items[index]; + } + + set { + if ((uint) index >= (uint)_size) { + ThrowHelper.ThrowArgumentOutOfRange_IndexException(); + } + Contract.EndContractBlock(); + _items[index] = value; + _version++; + } + } + + private static bool IsCompatibleObject(object value) { + // Non-null values are fine. Only accept nulls if T is a class or Nullable<U>. + // Note that default(T) is not equal to null for value types except when T is Nullable<U>. + return ((value is T) || (value == null && default(T) == null)); + } + + Object System.Collections.IList.this[int index] { + get { + return this[index]; + } + set { + ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(value, ExceptionArgument.value); + + try { + this[index] = (T)value; + } + catch (InvalidCastException) { + ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(T)); + } + } + } + + // Adds the given object to the end of this list. The size of the list is + // increased by one. If required, the capacity of the list is doubled + // before adding the new element. + // + public void Add(T item) { + if (_size == _items.Length) EnsureCapacity(_size + 1); + _items[_size++] = item; + _version++; + } + + int System.Collections.IList.Add(Object item) + { + ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(item, ExceptionArgument.item); + + try { + Add((T) item); + } + catch (InvalidCastException) { + ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T)); + } + + return Count - 1; + } + + + // Adds the elements of the given collection to the end of this list. If + // required, the capacity of the list is increased to twice the previous + // capacity or the new size, whichever is larger. + // + public void AddRange(IEnumerable<T> collection) { + Contract.Ensures(Count >= Contract.OldValue(Count)); + + InsertRange(_size, collection); + } + + public ReadOnlyCollection<T> AsReadOnly() { + Contract.Ensures(Contract.Result<ReadOnlyCollection<T>>() != null); + return new ReadOnlyCollection<T>(this); + } + + // Searches a section of the list for a given element using a binary search + // algorithm. Elements of the list are compared to the search value using + // the given IComparer interface. If comparer is null, elements of + // the list are compared to the search value using the IComparable + // interface, which in that case must be implemented by all elements of the + // list and the given search value. This method assumes that the given + // section of the list is already sorted; if this is not the case, the + // result will be incorrect. + // + // The method returns the index of the given value in the list. If the + // list does not contain the given value, the method returns a negative + // integer. The bitwise complement operator (~) can be applied to a + // negative result to produce the index of the first element (if any) that + // is larger than the given search value. This is also the index at which + // the search value should be inserted into the list in order for the list + // to remain sorted. + // + // The method uses the Array.BinarySearch method to perform the + // search. + // + public int BinarySearch(int index, int count, T item, IComparer<T> comparer) { + if (index < 0) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + if (count < 0) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + if (_size - index < count) + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); + Contract.Ensures(Contract.Result<int>() <= index + count); + Contract.EndContractBlock(); + + return Array.BinarySearch<T>(_items, index, count, item, comparer); + } + + public int BinarySearch(T item) + { + Contract.Ensures(Contract.Result<int>() <= Count); + return BinarySearch(0, Count, item, null); + } + + public int BinarySearch(T item, IComparer<T> comparer) + { + Contract.Ensures(Contract.Result<int>() <= Count); + return BinarySearch(0, Count, item, comparer); + } + + + // Clears the contents of List. + public void Clear() { + if (_size > 0) + { + Array.Clear(_items, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references. + _size = 0; + } + _version++; + } + + // Contains returns true if the specified element is in the List. + // It does a linear, O(n) search. Equality is determined by calling + // EqualityComparer<T>.Default.Equals(). + + public bool Contains(T item) + { + // PERF: IndexOf calls Array.IndexOf, which internally + // calls EqualityComparer<T>.Default.IndexOf, which + // is specialized for different types. This + // boosts performance since instead of making a + // virtual method call each iteration of the loop, + // via EqualityComparer<T>.Default.Equals, we + // only make one virtual call to EqualityComparer.IndexOf. + + return _size != 0 && IndexOf(item) != -1; + } + + bool System.Collections.IList.Contains(Object item) + { + if(IsCompatibleObject(item)) { + return Contains((T) item); + } + return false; + } + + public List<TOutput> ConvertAll<TOutput>(Converter<T,TOutput> converter) { + if( converter == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.converter); + } + + Contract.EndContractBlock(); + + List<TOutput> list = new List<TOutput>(_size); + for( int i = 0; i< _size; i++) { + list._items[i] = converter(_items[i]); + } + list._size = _size; + return list; + } + + // Copies this List into array, which must be of a + // compatible array type. + // + public void CopyTo(T[] array) { + CopyTo(array, 0); + } + + // Copies this List into array, which must be of a + // compatible array type. + // + void System.Collections.ICollection.CopyTo(Array array, int arrayIndex) { + if ((array != null) && (array.Rank != 1)) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); + } + Contract.EndContractBlock(); + + try { + // Array.Copy will check for NULL. + Array.Copy(_items, 0, array, arrayIndex, _size); + } + catch(ArrayTypeMismatchException){ + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidArrayType); + } + } + + // Copies a section of this list to the given array at the given index. + // + // The method uses the Array.Copy method to copy the elements. + // + public void CopyTo(int index, T[] array, int arrayIndex, int count) { + if (_size - index < count) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); + } + Contract.EndContractBlock(); + + // Delegate rest of error checking to Array.Copy. + Array.Copy(_items, index, array, arrayIndex, count); + } + + public void CopyTo(T[] array, int arrayIndex) { + // Delegate rest of error checking to Array.Copy. + Array.Copy(_items, 0, array, arrayIndex, _size); + } + + // 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 + // capacity is increased to twice the current capacity or to min, + // whichever is larger. + private void EnsureCapacity(int min) { + if (_items.Length < min) { + int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2; + // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow. + // Note that this check works even when _items.Length overflowed thanks to the (uint) cast + if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength; + if (newCapacity < min) newCapacity = min; + Capacity = newCapacity; + } + } + + public bool Exists(Predicate<T> match) { + return FindIndex(match) != -1; + } + + public T Find(Predicate<T> match) { + if( match == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match); + } + Contract.EndContractBlock(); + + for(int i = 0 ; i < _size; i++) { + if(match(_items[i])) { + return _items[i]; + } + } + return default(T); + } + + public List<T> FindAll(Predicate<T> match) { + if( match == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match); + } + Contract.EndContractBlock(); + + List<T> list = new List<T>(); + for(int i = 0 ; i < _size; i++) { + if(match(_items[i])) { + list.Add(_items[i]); + } + } + return list; + } + + public int FindIndex(Predicate<T> match) { + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(Contract.Result<int>() < Count); + return FindIndex(0, _size, match); + } + + public int FindIndex(int startIndex, Predicate<T> match) { + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(Contract.Result<int>() < startIndex + Count); + return FindIndex(startIndex, _size - startIndex, match); + } + + public int FindIndex(int startIndex, int count, Predicate<T> match) { + if( (uint)startIndex > (uint)_size ) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index); + } + + if (count < 0 || startIndex > _size - count) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count); + } + + if( match == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match); + } + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(Contract.Result<int>() < startIndex + count); + Contract.EndContractBlock(); + + int endIndex = startIndex + count; + for( int i = startIndex; i < endIndex; i++) { + if( match(_items[i])) return i; + } + return -1; + } + + public T FindLast(Predicate<T> match) { + if( match == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match); + } + Contract.EndContractBlock(); + + for(int i = _size - 1 ; i >= 0; i--) { + if(match(_items[i])) { + return _items[i]; + } + } + return default(T); + } + + public int FindLastIndex(Predicate<T> match) { + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(Contract.Result<int>() < Count); + return FindLastIndex(_size - 1, _size, match); + } + + public int FindLastIndex(int startIndex, Predicate<T> match) { + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(Contract.Result<int>() <= startIndex); + return FindLastIndex(startIndex, startIndex + 1, match); + } + + public int FindLastIndex(int startIndex, int count, Predicate<T> match) { + if( match == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match); + } + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(Contract.Result<int>() <= startIndex); + Contract.EndContractBlock(); + + if(_size == 0) { + // Special case for 0 length List + if( startIndex != -1) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index); + } + } + else { + // Make sure we're not out of range + if ( (uint)startIndex >= (uint)_size) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.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); + } + + int endIndex = startIndex - count; + for( int i = startIndex; i > endIndex; i--) { + if( match(_items[i])) { + return i; + } + } + return -1; + } + + public void ForEach(Action<T> action) { + if( action == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.action); + } + Contract.EndContractBlock(); + + int version = _version; + + for(int i = 0 ; i < _size; i++) { + if (version != _version && BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) { + break; + } + action(_items[i]); + } + + if (version != _version && BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + } + + // Returns an enumerator for this list with the given + // permission for removal of elements. If modifications made to the list + // while an enumeration is in progress, the MoveNext and + // GetObject methods of the enumerator will throw an exception. + // + public Enumerator GetEnumerator() { + return new Enumerator(this); + } + + /// <internalonly/> + IEnumerator<T> IEnumerable<T>.GetEnumerator() { + return new Enumerator(this); + } + + System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { + return new Enumerator(this); + } + + public List<T> GetRange(int index, int count) { + if (index < 0) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (count < 0) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (_size - index < count) { + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); + } + Contract.Ensures(Contract.Result<List<T>>() != null); + Contract.EndContractBlock(); + + List<T> list = new List<T>(count); + Array.Copy(_items, index, list._items, 0, count); + list._size = count; + return list; + } + + + // Returns the index of the first occurrence of a given value in a range of + // this list. The list is searched forwards from beginning to end. + // The elements of the list are compared to the given value using the + // Object.Equals method. + // + // This method uses the Array.IndexOf method to perform the + // search. + // + public int IndexOf(T item) { + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(Contract.Result<int>() < Count); + return Array.IndexOf(_items, item, 0, _size); + } + + int System.Collections.IList.IndexOf(Object item) + { + if(IsCompatibleObject(item)) { + return IndexOf((T)item); + } + return -1; + } + + // Returns the index of the first occurrence of a given value in a range of + // this list. The list is searched forwards, starting at index + // index and ending at count number of elements. The + // elements of the list are compared to the given value using the + // Object.Equals method. + // + // This method uses the Array.IndexOf method to perform the + // search. + // + public int IndexOf(T item, int index) { + if (index > _size) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(Contract.Result<int>() < Count); + Contract.EndContractBlock(); + return Array.IndexOf(_items, item, index, _size - index); + } + + // Returns the index of the first occurrence of a given value in a range of + // this list. The list is searched forwards, starting at index + // index and upto count number of elements. The + // elements of the list are compared to the given value using the + // Object.Equals method. + // + // This method uses the Array.IndexOf method to perform the + // search. + // + public int IndexOf(T item, int index, int count) { + if (index > _size) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); + + if (count <0 || index > _size - count) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count); + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(Contract.Result<int>() < Count); + Contract.EndContractBlock(); + + return Array.IndexOf(_items, item, index, count); + } + + // Inserts an element into this list at a given index. The size of the list + // is increased by one. If required, the capacity of the list is doubled + // before inserting the new element. + // + public void Insert(int index, T item) { + // Note that insertions at the end are legal. + if ((uint) index > (uint)_size) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert); + } + Contract.EndContractBlock(); + if (_size == _items.Length) EnsureCapacity(_size + 1); + if (index < _size) { + Array.Copy(_items, index, _items, index + 1, _size - index); + } + _items[index] = item; + _size++; + _version++; + } + + void System.Collections.IList.Insert(int index, Object item) + { + ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(item, ExceptionArgument.item); + + try { + Insert(index, (T) item); + } + catch (InvalidCastException) { + ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T)); + } + } + + // Inserts the elements of the given collection at a given index. If + // required, the capacity of the list is increased to twice the previous + // capacity or the new size, whichever is larger. Ranges may be added + // to the end of the list by setting index to the List's size. + // + public void InsertRange(int index, IEnumerable<T> collection) { + if (collection==null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); + } + + if ((uint)index > (uint)_size) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); + } + Contract.EndContractBlock(); + + ICollection<T> c = collection as ICollection<T>; + if( c != null ) { // if collection is ICollection<T> + int count = c.Count; + if (count > 0) { + EnsureCapacity(_size + count); + if (index < _size) { + Array.Copy(_items, index, _items, index + count, _size - index); + } + + // If we're inserting a List into itself, we want to be able to deal with that. + if (this == c) { + // Copy first part of _items to insert location + Array.Copy(_items, 0, _items, index, index); + // Copy last part of _items back to inserted location + Array.Copy(_items, index+count, _items, index*2, _size-index); + } + else { + T[] itemsToInsert = new T[count]; + c.CopyTo(itemsToInsert, 0); + itemsToInsert.CopyTo(_items, index); + } + _size += count; + } + } + else { + using(IEnumerator<T> en = collection.GetEnumerator()) { + while(en.MoveNext()) { + Insert(index++, en.Current); + } + } + } + _version++; + } + + // Returns the index of the last occurrence of a given value in a range of + // this list. The list is searched backwards, starting at the end + // and ending at the first element in the list. The elements of the list + // are compared to the given value using the Object.Equals method. + // + // This method uses the Array.LastIndexOf method to perform the + // search. + // + public int LastIndexOf(T item) + { + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(Contract.Result<int>() < Count); + if (_size == 0) { // Special case for empty list + return -1; + } + else { + return LastIndexOf(item, _size - 1, _size); + } + } + + // Returns the index of the last occurrence of a given value in a range of + // this list. The list is searched backwards, starting at index + // index and ending at the first element in the list. The + // elements of the list are compared to the given value using the + // Object.Equals method. + // + // This method uses the Array.LastIndexOf method to perform the + // search. + // + public int LastIndexOf(T item, int index) + { + if (index >= _size) + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(((Count == 0) && (Contract.Result<int>() == -1)) || ((Count > 0) && (Contract.Result<int>() <= index))); + Contract.EndContractBlock(); + return LastIndexOf(item, index, index + 1); + } + + // Returns the index of the last occurrence of a given value in a range of + // this list. The list is searched backwards, starting at index + // index and upto count elements. The elements of + // the list are compared to the given value using the Object.Equals + // method. + // + // This method uses the Array.LastIndexOf method to perform the + // search. + // + public int LastIndexOf(T item, int index, int count) { + if ((Count != 0) && (index < 0)) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if ((Count !=0) && (count < 0)) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + Contract.Ensures(Contract.Result<int>() >= -1); + Contract.Ensures(((Count == 0) && (Contract.Result<int>() == -1)) || ((Count > 0) && (Contract.Result<int>() <= index))); + Contract.EndContractBlock(); + + if (_size == 0) { // Special case for empty list + return -1; + } + + if (index >= _size) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection); + } + + if (count > index + 1) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection); + } + + return Array.LastIndexOf(_items, item, index, count); + } + + // Removes the element at the given index. The size of the list is + // decreased by one. + // + public bool Remove(T item) { + int index = IndexOf(item); + if (index >= 0) { + RemoveAt(index); + return true; + } + + return false; + } + + void System.Collections.IList.Remove(Object item) + { + if(IsCompatibleObject(item)) { + Remove((T) item); + } + } + + // This method removes all items which matches the predicate. + // The complexity is O(n). + public int RemoveAll(Predicate<T> match) { + if( match == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match); + } + Contract.Ensures(Contract.Result<int>() >= 0); + Contract.Ensures(Contract.Result<int>() <= Contract.OldValue(Count)); + Contract.EndContractBlock(); + + int freeIndex = 0; // the first free slot in items array + + // Find the first item which needs to be removed. + while( freeIndex < _size && !match(_items[freeIndex])) freeIndex++; + if( freeIndex >= _size) return 0; + + int current = freeIndex + 1; + while( current < _size) { + // Find the first item which needs to be kept. + while( current < _size && match(_items[current])) current++; + + if( current < _size) { + // copy item to the free slot. + _items[freeIndex++] = _items[current++]; + } + } + + Array.Clear(_items, freeIndex, _size - freeIndex); + int result = _size - freeIndex; + _size = freeIndex; + _version++; + return result; + } + + // Removes the element at the given index. The size of the list is + // decreased by one. + // + public void RemoveAt(int index) { + if ((uint)index >= (uint)_size) { + ThrowHelper.ThrowArgumentOutOfRange_IndexException(); + } + Contract.EndContractBlock(); + _size--; + if (index < _size) { + Array.Copy(_items, index + 1, _items, index, _size - index); + } + _items[_size] = default(T); + _version++; + } + + // Removes a range of elements from this list. + // + public void RemoveRange(int index, int count) { + if (index < 0) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (count < 0) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (_size - index < count) + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); + Contract.EndContractBlock(); + + if (count > 0) { + int i = _size; + _size -= count; + if (index < _size) { + Array.Copy(_items, index + count, _items, index, _size - index); + } + Array.Clear(_items, _size, count); + _version++; + } + } + + // Reverses the elements in this list. + public void Reverse() { + Reverse(0, Count); + } + + // Reverses the elements in a range of this list. Following a call to this + // method, an element in the range given by index and count + // which was previously located at index i will now be located at + // index index + (index + count - i - 1). + // + public void Reverse(int index, int count) { + if (index < 0) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (count < 0) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (_size - index < count) + 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--; + } + + _version++; + } + + // Sorts the elements in this list. Uses the default comparer and + // Array.Sort. + public void Sort() + { + Sort(0, Count, null); + } + + // Sorts the elements in this list. Uses Array.Sort with the + // provided comparer. + public void Sort(IComparer<T> comparer) + { + Sort(0, Count, comparer); + } + + // Sorts the elements in a section of this list. The sort compares the + // elements to each other using the given IComparer interface. If + // comparer is null, the elements are compared to each other using + // the IComparable interface, which in that case must be implemented by all + // elements of the list. + // + // This method uses the Array.Sort method to sort the elements. + // + public void Sort(int index, int count, IComparer<T> comparer) { + if (index < 0) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (count < 0) { + ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); + } + + if (_size - index < count) + ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); + Contract.EndContractBlock(); + + Array.Sort<T>(_items, index, count, comparer); + _version++; + } + + public void Sort(Comparison<T> comparison) { + if( comparison == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparison); + } + Contract.EndContractBlock(); + + if( _size > 0) { + IComparer<T> comparer = Comparer<T>.Create(comparison); + Array.Sort(_items, 0, _size, comparer); + } + } + + // ToArray returns an array containing the contents of the List. + // This requires copying the List, which is an O(n) operation. + public T[] ToArray() { + 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); + return array; + } + + // Sets the capacity of this list to the size of the list. This method can + // be used to minimize a list's memory overhead once it is known that no + // new elements will be added to the list. To completely clear a list and + // release all memory referenced by the list, execute the following + // statements: + // + // list.Clear(); + // list.TrimExcess(); + // + public void TrimExcess() { + int threshold = (int)(((double)_items.Length) * 0.9); + if( _size < threshold ) { + Capacity = _size; + } + } + + public bool TrueForAll(Predicate<T> match) { + if( match == null) { + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match); + } + Contract.EndContractBlock(); + + for(int i = 0 ; i < _size; i++) { + if( !match(_items[i])) { + return false; + } + } + return true; + } + + [Serializable] + public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator + { + private List<T> list; + private int index; + private int version; + private T current; + + internal Enumerator(List<T> list) { + this.list = list; + index = 0; + version = list._version; + current = default(T); + } + + public void Dispose() { + } + + public bool MoveNext() { + + List<T> localList = list; + + if (version == localList._version && ((uint)index < (uint)localList._size)) + { + current = localList._items[index]; + index++; + return true; + } + return MoveNextRare(); + } + + private bool MoveNextRare() + { + if (version != list._version) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + } + + index = list._size + 1; + current = default(T); + return false; + } + + public T Current { + get { + return current; + } + } + + Object System.Collections.IEnumerator.Current { + get { + if( index == 0 || index == list._size + 1) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen); + } + return Current; + } + } + + void System.Collections.IEnumerator.Reset() { + if (version != list._version) { + ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion); + } + + index = 0; + current = default(T); + } + + } + } +} + |