summaryrefslogtreecommitdiff
path: root/src/mscorlib/src/System/Collections/Generic
diff options
context:
space:
mode:
authorJiyoung Yun <jy910.yun@samsung.com>2016-11-23 19:09:09 +0900
committerJiyoung Yun <jy910.yun@samsung.com>2016-11-23 19:09:09 +0900
commit4b4aad7217d3292650e77eec2cf4c198ea9c3b4b (patch)
tree98110734c91668dfdbb126fcc0e15ddbd93738ca /src/mscorlib/src/System/Collections/Generic
parentfa45f57ed55137c75ac870356a1b8f76c84b229c (diff)
downloadcoreclr-4b4aad7217d3292650e77eec2cf4c198ea9c3b4b.tar.gz
coreclr-4b4aad7217d3292650e77eec2cf4c198ea9c3b4b.tar.bz2
coreclr-4b4aad7217d3292650e77eec2cf4c198ea9c3b4b.zip
Imported Upstream version 1.1.0upstream/1.1.0
Diffstat (limited to 'src/mscorlib/src/System/Collections/Generic')
-rw-r--r--src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs1558
-rw-r--r--src/mscorlib/src/System/Collections/Generic/Comparer.cs325
-rw-r--r--src/mscorlib/src/System/Collections/Generic/DebugView.cs129
-rw-r--r--src/mscorlib/src/System/Collections/Generic/Dictionary.cs1187
-rw-r--r--src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs621
-rw-r--r--src/mscorlib/src/System/Collections/Generic/ICollection.cs52
-rw-r--r--src/mscorlib/src/System/Collections/Generic/IComparer.cs30
-rw-r--r--src/mscorlib/src/System/Collections/Generic/IDictionary.cs58
-rw-r--r--src/mscorlib/src/System/Collections/Generic/IEnumerable.cs38
-rw-r--r--src/mscorlib/src/System/Collections/Generic/IEnumerator.cs35
-rw-r--r--src/mscorlib/src/System/Collections/Generic/IEqualityComparer.cs19
-rw-r--r--src/mscorlib/src/System/Collections/Generic/IList.cs54
-rw-r--r--src/mscorlib/src/System/Collections/Generic/IReadOnlyCollection.cs34
-rw-r--r--src/mscorlib/src/System/Collections/Generic/IReadOnlyDictionary.cs29
-rw-r--r--src/mscorlib/src/System/Collections/Generic/IReadOnlyList.cs34
-rw-r--r--src/mscorlib/src/System/Collections/Generic/KeyNotFoundException.cs45
-rw-r--r--src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs56
-rw-r--r--src/mscorlib/src/System/Collections/Generic/List.cs1120
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);
+ }
+
+ }
+ }
+}
+