diff options
Diffstat (limited to 'src/mscorlib/src/System/Collections/Generic')
19 files changed, 1670 insertions, 1505 deletions
diff --git a/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs b/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs index 298ac3e177..e313cda0fb 100644 --- a/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs +++ b/src/mscorlib/src/System/Collections/Generic/ArraySortHelper.cs @@ -12,15 +12,16 @@ ** ** ===========================================================*/ + +using System; +using System.Globalization; +using System.Runtime.CompilerServices; +using System.Diagnostics; +using System.Diagnostics.Contracts; +using System.Runtime.Versioning; + namespace System.Collections.Generic { - using System; - using System.Globalization; - using System.Runtime.CompilerServices; - using System.Diagnostics; - using System.Diagnostics.Contracts; - using System.Runtime.Versioning; - #region ArraySortHelper for single arrays internal interface IArraySortHelper<TKey> @@ -36,8 +37,6 @@ namespace System.Collections.Generic // 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; @@ -49,18 +48,18 @@ namespace System.Collections.Generic return result; } - internal static void ThrowOrIgnoreBadComparer(Object comparer) { - throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", comparer)); + internal static void ThrowOrIgnoreBadComparer(Object comparer) + { + throw new ArgumentException(SR.Format(SR.Arg_BogusIComparer, comparer)); } - } - [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`1")] - internal class ArraySortHelper<T> + [TypeDependencyAttribute("System.Collections.Generic.GenericArraySortHelper`1")] + internal class ArraySortHelper<T> : IArraySortHelper<T> { - static volatile IArraySortHelper<T> defaultArraySortHelper; - + private static volatile IArraySortHelper<T> defaultArraySortHelper; + public static IArraySortHelper<T> Default { get @@ -71,8 +70,8 @@ namespace System.Collections.Generic return sorter; } - } - + } + private static IArraySortHelper<T> CreateArraySortHelper() { if (typeof(IComparable<T>).IsAssignableFrom(typeof(T))) @@ -81,7 +80,7 @@ namespace System.Collections.Generic } else { - defaultArraySortHelper = new ArraySortHelper<T>(); + defaultArraySortHelper = new ArraySortHelper<T>(); } return defaultArraySortHelper; } @@ -91,7 +90,7 @@ namespace System.Collections.Generic public void Sort(T[] keys, int index, int length, IComparer<T> comparer) { Debug.Assert(keys != null, "Check the arguments in the caller!"); - Debug.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); + Debug.Assert(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. @@ -110,7 +109,7 @@ namespace System.Collections.Generic } catch (Exception e) { - throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); } } @@ -127,7 +126,7 @@ namespace System.Collections.Generic } catch (Exception e) { - throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); } } @@ -150,7 +149,7 @@ namespace System.Collections.Generic } catch (Exception e) { - throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); } } @@ -241,9 +240,9 @@ namespace System.Collections.Generic } if (partitionSize == 3) { - SwapIfGreater(keys, comparer, lo, hi-1); + SwapIfGreater(keys, comparer, lo, hi - 1); SwapIfGreater(keys, comparer, lo, hi); - SwapIfGreater(keys, comparer, hi-1, hi); + SwapIfGreater(keys, comparer, hi - 1, hi); return; } @@ -375,7 +374,7 @@ namespace System.Collections.Generic 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) @@ -400,7 +399,7 @@ namespace System.Collections.Generic } catch (Exception e) { - throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); } } @@ -422,7 +421,7 @@ namespace System.Collections.Generic } catch (Exception e) { - throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); } } @@ -485,7 +484,7 @@ namespace System.Collections.Generic private static void Swap(T[] a, int i, int j) { - if(i!=j) + if (i != j) { T t = a[i]; a[i] = a[j]; @@ -529,9 +528,9 @@ namespace System.Collections.Generic } if (partitionSize == 3) { - SwapIfGreaterWithItems(keys, lo, hi-1); + SwapIfGreaterWithItems(keys, lo, hi - 1); SwapIfGreaterWithItems(keys, lo, hi); - SwapIfGreaterWithItems(keys, hi-1, hi); + SwapIfGreaterWithItems(keys, hi - 1, hi); return; } @@ -662,7 +661,7 @@ namespace System.Collections.Generic } } -#endregion + #endregion #region ArraySortHelper for paired key and value arrays @@ -675,7 +674,7 @@ namespace System.Collections.Generic internal class ArraySortHelper<TKey, TValue> : IArraySortHelper<TKey, TValue> { - static volatile IArraySortHelper<TKey, TValue> defaultArraySortHelper; + private static volatile IArraySortHelper<TKey, TValue> defaultArraySortHelper; public static IArraySortHelper<TKey, TValue> Default { @@ -724,7 +723,7 @@ namespace System.Collections.Generic } catch (Exception e) { - throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); } } @@ -755,12 +754,12 @@ namespace System.Collections.Generic private static void Swap(TKey[] keys, TValue[] values, int i, int j) { - if(i!=j) + if (i != j) { TKey k = keys[i]; keys[i] = keys[j]; keys[j] = k; - if(values != null) + if (values != null) { TValue v = values[i]; values[i] = values[j]; @@ -810,9 +809,9 @@ namespace System.Collections.Generic } if (partitionSize == 3) { - SwapIfGreaterWithItems(keys, values, comparer, lo, hi-1); + SwapIfGreaterWithItems(keys, values, comparer, lo, hi - 1); SwapIfGreaterWithItems(keys, values, comparer, lo, hi); - SwapIfGreaterWithItems(keys, values, comparer, hi-1, hi); + SwapIfGreaterWithItems(keys, values, comparer, hi - 1, hi); return; } @@ -913,12 +912,12 @@ namespace System.Collections.Generic if (!(comparer.Compare(d, keys[lo + child - 1]) < 0)) break; keys[lo + i - 1] = keys[lo + child - 1]; - if(values != null) + if (values != null) values[lo + i - 1] = values[lo + child - 1]; i = child; } keys[lo + i - 1] = d; - if(values != null) + if (values != null) values[lo + i - 1] = dValue; } @@ -942,12 +941,12 @@ namespace System.Collections.Generic while (j >= lo && comparer.Compare(t, keys[j]) < 0) { keys[j + 1] = keys[j]; - if(values != null) + if (values != null) values[j + 1] = values[j]; j--; } keys[j + 1] = t; - if(values != null) + if (values != null) values[j + 1] = tValue; } } @@ -960,8 +959,8 @@ namespace System.Collections.Generic public void Sort(TKey[] keys, TValue[] values, int index, int length, IComparer<TKey> comparer) { Debug.Assert(keys != null, "Check the arguments in the caller!"); - Debug.Assert( index >= 0 && length >= 0 && (keys.Length - index >= length), "Check the arguments in the caller!"); - + Debug.Assert(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 @@ -974,14 +973,14 @@ namespace System.Collections.Generic { ArraySortHelper<TKey, TValue>.IntrospectiveSort(keys, values, index, length, comparer); } - } + } catch (IndexOutOfRangeException) { IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer); } catch (Exception e) { - throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), e); + throw new InvalidOperationException(SR.InvalidOperation_IComparerFailed, e); } } @@ -1006,12 +1005,12 @@ namespace System.Collections.Generic private static void Swap(TKey[] keys, TValue[] values, int i, int j) { - if(i != j) + if (i != j) { TKey k = keys[i]; keys[i] = keys[j]; keys[j] = k; - if(values != null) + if (values != null) { TValue v = values[i]; values[i] = values[j]; @@ -1059,9 +1058,9 @@ namespace System.Collections.Generic } if (partitionSize == 3) { - SwapIfGreaterWithItems(keys, values, lo, hi-1); + SwapIfGreaterWithItems(keys, values, lo, hi - 1); SwapIfGreaterWithItems(keys, values, lo, hi); - SwapIfGreaterWithItems(keys, values, hi-1, hi); + SwapIfGreaterWithItems(keys, values, hi - 1, hi); return; } @@ -1106,10 +1105,10 @@ namespace System.Collections.Generic while (left < right) { - if(pivot == null) + if (pivot == null) { while (left < (hi - 1) && keys[++left] == null) ; - while (right > lo && keys[--right] != null); + while (right > lo && keys[--right] != null) ; } else { @@ -1167,12 +1166,12 @@ namespace System.Collections.Generic 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) + if (values != null) values[lo + i - 1] = values[lo + child - 1]; i = child; } keys[lo + i - 1] = d; - if(values != null) + if (values != null) values[lo + i - 1] = dValue; } @@ -1191,16 +1190,16 @@ namespace System.Collections.Generic { j = i; t = keys[i + 1]; - tValue = (values != null)? values[i + 1] : default(TValue); + 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) + if (values != null) values[j + 1] = values[j]; j--; } keys[j + 1] = t; - if(values != null) + if (values != null) values[j + 1] = tValue; } } diff --git a/src/mscorlib/src/System/Collections/Generic/Comparer.cs b/src/mscorlib/src/System/Collections/Generic/Comparer.cs index 056843a606..a9b4b3f0dd 100644 --- a/src/mscorlib/src/System/Collections/Generic/Comparer.cs +++ b/src/mscorlib/src/System/Collections/Generic/Comparer.cs @@ -15,19 +15,14 @@ using System.Security; using System.Runtime.Serialization; namespace System.Collections.Generic -{ +{ [Serializable] - [TypeDependencyAttribute("System.Collections.Generic.ObjectComparer`1")] + [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; - } - } + // To minimize generic instantiation overhead of creating the comparer per type, we keep the generic portion of the code as small + // as possible and define most of the creation logic in a non-generic class. + public static Comparer<T> Default { get; } = (Comparer<T>)ComparerHelpers.CreateDefaultComparer(typeof(T)); public static Comparer<T> Create(Comparison<T> comparison) { @@ -39,69 +34,10 @@ namespace System.Collections.Generic 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 - // - 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) { + 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); @@ -109,18 +45,20 @@ namespace System.Collections.Generic 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) { + { + public override int Compare(T x, T y) + { + if (x != null) + { if (y != null) return x.CompareTo(y); return 1; } @@ -139,8 +77,10 @@ namespace System.Collections.Generic [Serializable] internal sealed class NullableComparer<T> : Comparer<T?> where T : struct, IComparable<T> { - public override int Compare(T? x, T? y) { - if (x.HasValue) { + public override int Compare(T? x, T? y) + { + if (x.HasValue) + { if (y.HasValue) return x.value.CompareTo(y.value); return 1; } @@ -159,7 +99,8 @@ namespace System.Collections.Generic [Serializable] internal sealed class ObjectComparer<T> : Comparer<T> { - public override int Compare(T x, T y) { + public override int Compare(T x, T y) + { return System.Collections.Comparer.Default.Compare(x, y); } @@ -176,11 +117,13 @@ namespace System.Collections.Generic { private readonly Comparison<T> _comparison; - public ComparisonComparer(Comparison<T> comparison) { + public ComparisonComparer(Comparison<T> comparison) + { _comparison = comparison; } - public override int Compare(T x, T y) { + public override int Compare(T x, T y) + { return _comparison(x, y); } } @@ -196,12 +139,12 @@ namespace System.Collections.Generic { public Int32EnumComparer() { - Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + Debug.Assert(typeof(T).IsEnum); } - + // Used by the serialization engine. private Int32EnumComparer(SerializationInfo info, StreamingContext context) { } - + public override int Compare(T x, T y) { int ix = JitHelpers.UnsafeEnumCast(x); @@ -231,12 +174,12 @@ namespace System.Collections.Generic { public UInt32EnumComparer() { - Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + Debug.Assert(typeof(T).IsEnum); } - + // 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); @@ -262,9 +205,9 @@ namespace System.Collections.Generic { public Int64EnumComparer() { - Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + Debug.Assert(typeof(T).IsEnum); } - + public override int Compare(T x, T y) { long lx = JitHelpers.UnsafeEnumCastLong(x); @@ -290,12 +233,12 @@ namespace System.Collections.Generic { public UInt64EnumComparer() { - Debug.Assert(typeof(T).IsEnum, "This type is only intended to be used to compare enums!"); + Debug.Assert(typeof(T).IsEnum); } - + // 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); diff --git a/src/mscorlib/src/System/Collections/Generic/ComparerHelpers.cs b/src/mscorlib/src/System/Collections/Generic/ComparerHelpers.cs new file mode 100644 index 0000000000..3e428413d4 --- /dev/null +++ b/src/mscorlib/src/System/Collections/Generic/ComparerHelpers.cs @@ -0,0 +1,210 @@ +// 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.Diagnostics; +using static System.RuntimeTypeHandle; + +namespace System.Collections.Generic +{ + /// <summary> + /// Helper class for creating the default <see cref="Comparer{T}"/> and <see cref="EqualityComparer{T}"/>. + /// </summary> + /// <remarks> + /// This class is intentionally type-unsafe and non-generic to minimize the generic instantiation overhead of creating + /// the default comparer/equality comparer for a new type parameter. Efficiency of the methods in here does not matter too + /// much since they will only be run once per type parameter, but generic code involved in creating the comparers needs to be + /// kept to a minimum. + /// </remarks> + internal static class ComparerHelpers + { + /// <summary> + /// Creates the default <see cref="Comparer{T}"/>. + /// </summary> + /// <param name="type">The type to create the default comparer for.</param> + /// <remarks> + /// The logic in this method is replicated in vm/compile.cpp to ensure that NGen saves the right instantiations. + /// </remarks> + internal static object CreateDefaultComparer(Type type) + { + Debug.Assert(type != null && type is RuntimeType); + + object result = null; + var runtimeType = (RuntimeType)type; + + // If T implements IComparable<T> return a GenericComparer<T> + if (typeof(IComparable<>).MakeGenericType(type).IsAssignableFrom(type)) + { + result = CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericComparer<int>), runtimeType); + } + // Nullable does not implement IComparable<T?> directly because that would add an extra interface call per comparison. + // Instead, it relies on Comparer<T?>.Default to specialize for nullables and do the lifted comparisons if T implements IComparable. + else if (type.IsGenericType) + { + if (type.GetGenericTypeDefinition() == typeof(Nullable<>)) + { + result = TryCreateNullableComparer(runtimeType); + } + } + // The comparer for enums is specialized to avoid boxing. + else if (type.IsEnum) + { + result = TryCreateEnumComparer(runtimeType); + } + + return result ?? CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ObjectComparer<object>), runtimeType); + } + + /// <summary> + /// Creates the default <see cref="Comparer{T}"/> for a nullable type. + /// </summary> + /// <param name="nullableType">The nullable type to create the default comparer for.</param> + private static object TryCreateNullableComparer(RuntimeType nullableType) + { + Debug.Assert(nullableType != null); + Debug.Assert(nullableType.IsGenericType && nullableType.GetGenericTypeDefinition() == typeof(Nullable<>)); + + var embeddedType = (RuntimeType)nullableType.GetGenericArguments()[0]; + + if (typeof(IComparable<>).MakeGenericType(embeddedType).IsAssignableFrom(embeddedType)) + { + return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableComparer<int>), embeddedType); + } + + return null; + } + + /// <summary> + /// Creates the default <see cref="Comparer{T}"/> for an enum type. + /// </summary> + /// <param name="enumType">The enum type to create the default comparer for.</param> + private static object TryCreateEnumComparer(RuntimeType enumType) + { + Debug.Assert(enumType != null); + Debug.Assert(enumType.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(enumType)); + + // 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: + return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(Int32EnumComparer<int>), enumType); + case TypeCode.Byte: + case TypeCode.UInt16: + case TypeCode.UInt32: + return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(UInt32EnumComparer<uint>), enumType); + // 64-bit enums: Use `UnsafeEnumCastLong` + case TypeCode.Int64: + return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(Int64EnumComparer<long>), enumType); + case TypeCode.UInt64: + return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(UInt64EnumComparer<ulong>), enumType); + } + + return null; + } + + /// <summary> + /// Creates the default <see cref="EqualityComparer{T}"/>. + /// </summary> + /// <param name="type">The type to create the default equality comparer for.</param> + /// <remarks> + /// The logic in this method is replicated in vm/compile.cpp to ensure that NGen saves the right instantiations. + /// </remarks> + internal static object CreateDefaultEqualityComparer(Type type) + { + Debug.Assert(type != null && type is RuntimeType); + + object result = null; + var runtimeType = (RuntimeType)type; + + // Specialize for byte so Array.IndexOf is faster. + if (type == typeof(byte)) + { + result = new ByteEqualityComparer(); + } + // If T implements IEquatable<T> return a GenericEqualityComparer<T> + else if (typeof(IEquatable<>).MakeGenericType(type).IsAssignableFrom(type)) + { + result = CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericEqualityComparer<int>), runtimeType); + } + // Nullable does not implement IEquatable<T?> directly because that would add an extra interface call per comparison. + // Instead, it relies on EqualityComparer<T?>.Default to specialize for nullables and do the lifted comparisons if T implements IEquatable. + else if (type.IsGenericType) + { + if (type.GetGenericTypeDefinition() == typeof(Nullable<>)) + { + result = TryCreateNullableEqualityComparer(runtimeType); + } + } + // The equality comparer for enums is specialized to avoid boxing. + else if (type.IsEnum) + { + result = TryCreateEnumEqualityComparer(runtimeType); + } + + return result ?? CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ObjectEqualityComparer<object>), runtimeType); + } + + /// <summary> + /// Creates the default <see cref="EqualityComparer{T}"/> for a nullable type. + /// </summary> + /// <param name="nullableType">The nullable type to create the default equality comparer for.</param> + private static object TryCreateNullableEqualityComparer(RuntimeType nullableType) + { + Debug.Assert(nullableType != null); + Debug.Assert(nullableType.IsGenericType && nullableType.GetGenericTypeDefinition() == typeof(Nullable<>)); + + var embeddedType = (RuntimeType)nullableType.GetGenericArguments()[0]; + + if (typeof(IEquatable<>).MakeGenericType(embeddedType).IsAssignableFrom(embeddedType)) + { + return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableEqualityComparer<int>), embeddedType); + } + + return null; + } + + /// <summary> + /// Creates the default <see cref="EqualityComparer{T}"/> for an enum type. + /// </summary> + /// <param name="enumType">The enum type to create the default equality comparer for.</param> + private static object TryCreateEnumEqualityComparer(RuntimeType enumType) + { + Debug.Assert(enumType != null); + Debug.Assert(enumType.IsEnum); + + // See the METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST and METHOD__JIT_HELPERS__UNSAFE_ENUM_CAST_LONG cases in getILIntrinsicImplementation + // for how we cast the enum types to integral values in the comparer without boxing. + + TypeCode underlyingTypeCode = Type.GetTypeCode(Enum.GetUnderlyingType(enumType)); + + // 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, since for those types GetHashCode does not simply return the value. + // We need to preserve what they would return. + switch (underlyingTypeCode) + { + case TypeCode.Int16: + return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ShortEnumEqualityComparer<short>), enumType); + case TypeCode.SByte: + return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(SByteEnumEqualityComparer<sbyte>), enumType); + case TypeCode.Int32: + case TypeCode.UInt32: + case TypeCode.Byte: + case TypeCode.UInt16: + return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(EnumEqualityComparer<int>), enumType); + case TypeCode.Int64: + case TypeCode.UInt64: + return RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(LongEnumEqualityComparer<long>), enumType); + } + + return null; + } + } +} diff --git a/src/mscorlib/src/System/Collections/Generic/DebugView.cs b/src/mscorlib/src/System/Collections/Generic/DebugView.cs index 27c5011147..dc487c1411 100644 --- a/src/mscorlib/src/System/Collections/Generic/DebugView.cs +++ b/src/mscorlib/src/System/Collections/Generic/DebugView.cs @@ -13,116 +13,112 @@ ** =============================================================================*/ -namespace System.Collections.Generic { - using System; - using System.Collections.ObjectModel; - using System.Diagnostics; - using System.Diagnostics.Contracts; +using System; +using System.Collections.ObjectModel; +using System.Diagnostics; +using System.Diagnostics.Contracts; +namespace System.Collections.Generic +{ // // 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) { + 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; + this.collection = collection; } - + [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] - public T[] Items { - get { + 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) { + 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; + this.collection = collection; } - + [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] - public TKey[] Items { - get { + 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) { + 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; + this.collection = collection; } - + [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] - public TValue[] Items { - get { + 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; - internal sealed class Mscorlib_DictionaryDebugView<K, V> { - private IDictionary<K, V> dict; - - public Mscorlib_DictionaryDebugView(IDictionary<K, V> dictionary) { + public Mscorlib_DictionaryDebugView(IDictionary<K, V> dictionary) + { if (dictionary == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); - this.dict = dictionary; + dict = dictionary; } - + [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] - public KeyValuePair<K, V>[] Items { - get { + 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(nameof(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 index 7b60e31031..409b23b541 100644 --- a/src/mscorlib/src/System/Collections/Generic/Dictionary.cs +++ b/src/mscorlib/src/System/Collections/Generic/Dictionary.cs @@ -41,20 +41,43 @@ ** to serialization such that this code doesn't need to build in ** silverlight. ===========================================================*/ -namespace System.Collections.Generic { +namespace System.Collections.Generic +{ using System; using System.Collections; using System.Diagnostics; using System.Diagnostics.Contracts; using System.Runtime.Serialization; + /// <summary> + /// Used internally to control behavior of insertion into a <see cref="Dictionary{TKey, TValue}"/>. + /// </summary> + internal enum InsertionBehavior : byte + { + /// <summary> + /// The default insertion behavior. + /// </summary> + None = 0, + + /// <summary> + /// Specifies that an existing entry with the same key should be overwritten if encountered. + /// </summary> + OverwriteExisting = 1, + + /// <summary> + /// Specifies that if an existing entry with the same key is encountered, an exception should be thrown. + /// </summary> + ThrowOnExisting = 2 + } + [DebuggerTypeProxy(typeof(Mscorlib_DictionaryDebugView<,>))] [DebuggerDisplay("Count = {Count}")] [Serializable] - public class Dictionary<TKey,TValue>: IDictionary<TKey,TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback { - - private struct Entry { + 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 @@ -71,38 +94,40 @@ namespace System.Collections.Generic { 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() : this(0, null) { } - public Dictionary(int capacity): this(capacity, null) {} + public Dictionary(int capacity) : this(capacity, null) { } - public Dictionary(IEqualityComparer<TKey> comparer): this(0, comparer) {} + public Dictionary(IEqualityComparer<TKey> comparer) : this(0, comparer) { } - public Dictionary(int capacity, IEqualityComparer<TKey> 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 - if (HashHelpers.s_UseRandomizedStringHashing && comparer == EqualityComparer<string>.Default) + if (HashHelpers.s_UseRandomizedStringHashing && this.comparer == EqualityComparer<string>.Default) { - this.comparer = (IEqualityComparer<TKey>) NonRandomizedStringEqualityComparer.Default; + this.comparer = (IEqualityComparer<TKey>)NonRandomizedStringEqualityComparer.Default; } #endif // FEATURE_RANDOMIZED_STRING_HASHING } - 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) { + public Dictionary(IDictionary<TKey, TValue> dictionary) : this(dictionary, null) { } - if( 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); } @@ -110,138 +135,174 @@ namespace System.Collections.Generic { // 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; + 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) { + 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) { + foreach (KeyValuePair<TKey, TValue> pair in dictionary) + { Add(pair.Key, pair.Value); } } - public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection): - this(collection, null) { } + public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection) : + this(collection, null) + { } - public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer): + public Dictionary(IEnumerable<KeyValuePair<TKey, TValue>> collection, IEqualityComparer<TKey> comparer) : this((collection as ICollection<KeyValuePair<TKey, TValue>>)?.Count ?? 0, comparer) { - if (collection == null) { + if (collection == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); } - foreach (KeyValuePair<TKey, TValue> pair in collection) { + foreach (KeyValuePair<TKey, TValue> pair in collection) + { Add(pair.Key, pair.Value); } } - protected Dictionary(SerializationInfo info, StreamingContext context) { + 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 IEqualityComparer<TKey> Comparer + { + get + { + return comparer; + } } - - public int Count { + + public int Count + { get { return count - freeCount; } } - public KeyCollection Keys { - get { + 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); + 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); + IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys + { + get + { + if (keys == null) keys = new KeyCollection(this); return keys; } } - public ValueCollection Values { - get { + 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 { + ICollection<TValue> IDictionary<TKey, TValue>.Values + { + get + { if (values == null) values = new ValueCollection(this); return values; } } - IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values { - get { + IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values + { + get + { if (values == null) values = new ValueCollection(this); return values; } } - public TValue this[TKey key] { - get { + 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); + set + { + bool modified = TryInsert(key, value, InsertionBehavior.OverwriteExisting); + Debug.Assert(modified); } } - public void Add(TKey key, TValue value) { - Insert(key, value, true); + public void Add(TKey key, TValue value) + { + bool modified = TryInsert(key, value, InsertionBehavior.ThrowOnExisting); + Debug.Assert(modified); // If there was an existing key and the Add failed, an exception will already have been thrown. } - void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> keyValuePair) { + 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) { + 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)) { + 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) { + 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)) { + 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) { + public void Clear() + { + if (count > 0) + { for (int i = 0; i < buckets.Length; i++) buckets[i] = -1; Array.Clear(entries, 0, count); freeList = -1; @@ -251,90 +312,106 @@ namespace System.Collections.Generic { } } - public bool ContainsKey(TKey key) { + public bool ContainsKey(TKey key) + { return FindEntry(key) >= 0; } - public bool ContainsValue(TValue value) { - if (value == null) { - for (int i = 0; i < count; i++) { + 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 { + else + { EqualityComparer<TValue> c = EqualityComparer<TValue>.Default; - for (int i = 0; i < count; i++) { + 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) { + private void CopyTo(KeyValuePair<TKey, TValue>[] array, int index) + { + if (array == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } - - if (index < 0 || index > array.Length ) { + + if (index < 0 || index > array.Length) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } - if (array.Length - index < Count) { + 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); + 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() { + public Enumerator GetEnumerator() + { return new Enumerator(this, Enumerator.KeyValuePair); } - IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator() { + IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator() + { return new Enumerator(this, Enumerator.KeyValuePair); - } + } - public virtual void GetObjectData(SerializationInfo info, StreamingContext context) { - if (info==null) { + 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) { + 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) { + private int FindEntry(TKey key) + { + if (key == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } - if (buckets != null) { + if (buckets != null) + { int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; - for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) { + 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) { + 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; @@ -342,9 +419,10 @@ namespace System.Collections.Generic { freeList = -1; } - private void Insert(TKey key, TValue value, bool add) { - - if( key == null ) { + private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior) + { + if (key == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } @@ -356,27 +434,38 @@ namespace System.Collections.Generic { 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) { + for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) + { + if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) + { + if (behavior == InsertionBehavior.OverwriteExisting) + { + entries[i].value = value; + version++; + return true; + } + + if (behavior == InsertionBehavior.ThrowOnExisting) + { ThrowHelper.ThrowAddingDuplicateWithKeyArgumentException(key); } - entries[i].value = value; - version++; - return; - } + + return false; + } #if FEATURE_RANDOMIZED_STRING_HASHING collisionCount++; #endif } int index; - if (freeCount > 0) { + if (freeCount > 0) + { index = freeList; freeList = entries[index].next; freeCount--; } - else { + else + { if (count == entries.Length) { Resize(); @@ -399,52 +488,60 @@ namespace System.Collections.Generic { // 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) + if (collisionCount > HashHelpers.HashCollisionThreshold && comparer == NonRandomizedStringEqualityComparer.Default) { - comparer = (IEqualityComparer<TKey>) EqualityComparer<string>.Default; + comparer = (IEqualityComparer<TKey>)EqualityComparer<string>.Default; Resize(entries.Length, true); } #endif + return true; } - public virtual void OnDeserialization(Object sender) { + public virtual void OnDeserialization(Object sender) + { SerializationInfo siInfo; HashHelpers.SerializationInfoTable.TryGetValue(this, out siInfo); - - if (siInfo==null) { + + 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) { + 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>[]) + KeyValuePair<TKey, TValue>[] array = (KeyValuePair<TKey, TValue>[]) siInfo.GetValue(KeyValuePairsName, typeof(KeyValuePair<TKey, TValue>[])); - if (array==null) { + if (array == null) + { ThrowHelper.ThrowSerializationException(ExceptionResource.Serialization_MissingKeys); } - for (int i=0; i<array.Length; i++) { - if ( array[i].Key == null) { + 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); + Add(array[i].Key, array[i].Value); } } - else { + else + { buckets = null; } @@ -452,25 +549,32 @@ namespace System.Collections.Generic { HashHelpers.SerializationInfoTable.Remove(this); } - private void Resize() { + private void Resize() + { Resize(HashHelpers.ExpandPrime(count), false); } - private void Resize(int newSize, bool forceNewHashCodes) { + private void Resize(int newSize, bool forceNewHashCodes) + { Debug.Assert(newSize >= entries.Length); int[] newBuckets = new int[newSize]; for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1; Entry[] newEntries = new Entry[newSize]; Array.Copy(entries, 0, newEntries, 0, count); - if(forceNewHashCodes) { - for (int i = 0; i < count; i++) { - if(newEntries[i].hashCode != -1) { + 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) { + 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; @@ -480,21 +584,31 @@ namespace System.Collections.Generic { entries = newEntries; } - public bool Remove(TKey key) { - if(key == null) { + // The overload Remove(TKey key, out TValue value) is a copy of this method with one additional + // statement to copy the value for entry being removed into the output parameter. + // Code has been intentionally duplicated for performance reasons. + public bool Remove(TKey key) + { + if (key == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } - if (buckets != null) { + 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) { + 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 { + else + { entries[last].next = entries[i].next; } entries[i].hashCode = -1; @@ -511,9 +625,56 @@ namespace System.Collections.Generic { return false; } - public bool TryGetValue(TKey key, out TValue value) { + // This overload is a copy of the overload Remove(TKey key) with one additional + // statement to copy the value for entry being removed into the output parameter. + // Code has been intentionally duplicated for performance reasons. + public bool Remove(TKey key, out TValue value) + { + 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; + } + + value = entries[i].value; + + entries[i].hashCode = -1; + entries[i].next = freeList; + entries[i].key = default(TKey); + entries[i].value = default(TValue); + freeList = i; + freeCount++; + version++; + return true; + } + } + } + value = default(TValue); + return false; + } + + public bool TryGetValue(TKey key, out TValue value) + { int i = FindEntry(key); - if (i >= 0) { + if (i >= 0) + { value = entries[i].value; return true; } @@ -536,195 +697,246 @@ namespace System.Collections.Generic { return defaultValue; } - bool ICollection<KeyValuePair<TKey,TValue>>.IsReadOnly { + public bool TryAdd(TKey key, TValue value) => TryInsert(key, value, InsertionBehavior.None); + + bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly + { get { return false; } } - void ICollection<KeyValuePair<TKey,TValue>>.CopyTo(KeyValuePair<TKey,TValue>[] array, int index) { + 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) { + void ICollection.CopyTo(Array array, int index) + { + if (array == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } - - if (array.Rank != 1) { + + if (array.Rank != 1) + { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); } - if( array.GetLowerBound(0) != 0 ) { + if (array.GetLowerBound(0) != 0) + { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); } - - if (index < 0 || index > array.Length) { + + if (index < 0 || index > array.Length) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } - if (array.Length - index < Count) { + if (array.Length - index < Count) + { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); } - - KeyValuePair<TKey,TValue>[] pairs = array as KeyValuePair<TKey,TValue>[]; - if (pairs != null) { + + KeyValuePair<TKey, TValue>[] pairs = array as KeyValuePair<TKey, TValue>[]; + if (pairs != null) + { CopyTo(pairs, index); } - else if( array is DictionaryEntry[]) { + 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) { + for (int i = 0; i < count; i++) + { + if (entries[i].hashCode >= 0) + { dictEntryArray[index++] = new DictionaryEntry(entries[i].key, entries[i].value); } - } + } } - else { + else + { object[] objects = array as object[]; - if (objects == null) { + if (objects == null) + { ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } - try { + 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); + 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) { + catch (ArrayTypeMismatchException) + { ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } } } - IEnumerator IEnumerable.GetEnumerator() { + IEnumerator IEnumerable.GetEnumerator() + { return new Enumerator(this, Enumerator.KeyValuePair); } - - bool ICollection.IsSynchronized { + + bool ICollection.IsSynchronized + { get { return false; } } - object ICollection.SyncRoot { - get { - if( _syncRoot == null) { - System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null); + object ICollection.SyncRoot + { + get + { + if (_syncRoot == null) + { + System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null); } - return _syncRoot; + return _syncRoot; } } - bool IDictionary.IsFixedSize { + bool IDictionary.IsFixedSize + { get { return false; } } - bool IDictionary.IsReadOnly { + bool IDictionary.IsReadOnly + { get { return false; } } - ICollection IDictionary.Keys { + ICollection IDictionary.Keys + { get { return (ICollection)Keys; } } - - ICollection IDictionary.Values { + + ICollection IDictionary.Values + { get { return (ICollection)Values; } } - - object IDictionary.this[object key] { - get { - if( IsCompatibleKey(key)) { + + object IDictionary.this[object key] + { + get + { + if (IsCompatibleKey(key)) + { int i = FindEntry((TKey)key); - if (i >= 0) { - return entries[i].value; + if (i >= 0) + { + return entries[i].value; } } return null; } - set { + set + { if (key == null) { - ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value); - try { + try + { TKey tempKey = (TKey)key; - try { - this[tempKey] = (TValue)value; + try + { + this[tempKey] = (TValue)value; } - catch (InvalidCastException) { - ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue)); + catch (InvalidCastException) + { + ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue)); } } - catch (InvalidCastException) { + catch (InvalidCastException) + { ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey)); } } } - private static bool IsCompatibleKey(object key) { - if( key == null) { - ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); - } - return (key is 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) { + + void IDictionary.Add(object key, object value) + { if (key == null) { - ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); + ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key); } ThrowHelper.IfNullAndNullsAreIllegalThenThrow<TValue>(value, ExceptionArgument.value); - try { + try + { TKey tempKey = (TKey)key; - try { + try + { Add(tempKey, (TValue)value); } - catch (InvalidCastException) { - ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue)); + catch (InvalidCastException) + { + ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(TValue)); } } - catch (InvalidCastException) { + catch (InvalidCastException) + { ThrowHelper.ThrowWrongKeyTypeArgumentException(key, typeof(TKey)); } } - - bool IDictionary.Contains(object key) { - if(IsCompatibleKey(key)) { + + bool IDictionary.Contains(object key) + { + if (IsCompatibleKey(key)) + { return ContainsKey((TKey)key); } - + return false; } - - IDictionaryEnumerator IDictionary.GetEnumerator() { + + IDictionaryEnumerator IDictionary.GetEnumerator() + { return new Enumerator(this, Enumerator.DictEntry); } - - void IDictionary.Remove(object key) { - if(IsCompatibleKey(key)) { + + void IDictionary.Remove(object key) + { + if (IsCompatibleKey(key)) + { Remove((TKey)key); } } [Serializable] - public struct Enumerator: IEnumerator<KeyValuePair<TKey,TValue>>, + public struct Enumerator : IEnumerator<KeyValuePair<TKey, TValue>>, IDictionaryEnumerator { - private Dictionary<TKey,TValue> dictionary; + private Dictionary<TKey, TValue> dictionary; private int version; private int index; - private KeyValuePair<TKey,TValue> current; + 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) { + internal Enumerator(Dictionary<TKey, TValue> dictionary, int getEnumeratorRetType) + { this.dictionary = dictionary; version = dictionary.version; index = 0; @@ -732,15 +944,19 @@ namespace System.Collections.Generic { current = new KeyValuePair<TKey, TValue>(); } - public bool MoveNext() { - if (version != dictionary.version) { + public bool MoveNext() + { + if (version != dictionary.version) + { ThrowHelper.ThrowInvalidOperationException_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) { + 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; @@ -753,187 +969,236 @@ namespace System.Collections.Generic { return false; } - public KeyValuePair<TKey,TValue> Current { + public KeyValuePair<TKey, TValue> Current + { get { return current; } } - public void Dispose() { + public void Dispose() + { } - object IEnumerator.Current { - get { - if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); - } + object IEnumerator.Current + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } - if (getEnumeratorRetType == DictEntry) { + if (getEnumeratorRetType == DictEntry) + { return new System.Collections.DictionaryEntry(current.Key, current.Value); - } else { + } + else + { return new KeyValuePair<TKey, TValue>(current.Key, current.Value); } } } - void IEnumerator.Reset() { - if (version != dictionary.version) { + void IEnumerator.Reset() + { + if (version != dictionary.version) + { ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } index = 0; - current = new KeyValuePair<TKey, TValue>(); + current = new KeyValuePair<TKey, TValue>(); } - DictionaryEntry IDictionaryEnumerator.Entry { - get { - if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); - } - - return new DictionaryEntry(current.Key, current.Value); + DictionaryEntry IDictionaryEnumerator.Entry + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + + return new DictionaryEntry(current.Key, current.Value); } } - object IDictionaryEnumerator.Key { - get { - if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); - } - - return current.Key; + object IDictionaryEnumerator.Key + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + + return current.Key; } } - object IDictionaryEnumerator.Value { - get { - if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); - } - - return current.Value; + object IDictionaryEnumerator.Value + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + + return current.Value; } } } [DebuggerTypeProxy(typeof(Mscorlib_DictionaryKeyCollectionDebugView<,>))] - [DebuggerDisplay("Count = {Count}")] + [DebuggerDisplay("Count = {Count}")] [Serializable] - public sealed class KeyCollection: ICollection<TKey>, ICollection, IReadOnlyCollection<TKey> + public sealed class KeyCollection : ICollection<TKey>, ICollection, IReadOnlyCollection<TKey> { - private Dictionary<TKey,TValue> dictionary; + private Dictionary<TKey, TValue> dictionary; - public KeyCollection(Dictionary<TKey,TValue> dictionary) { - if (dictionary == null) { + public KeyCollection(Dictionary<TKey, TValue> dictionary) + { + if (dictionary == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); } this.dictionary = dictionary; } - public Enumerator GetEnumerator() { + public Enumerator GetEnumerator() + { return new Enumerator(dictionary); } - public void CopyTo(TKey[] array, int index) { - if (array == null) { + public void CopyTo(TKey[] array, int index) + { + if (array == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } - if (index < 0 || index > array.Length) { + if (index < 0 || index > array.Length) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } - if (array.Length - index < dictionary.Count) { + 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++) { + for (int i = 0; i < count; i++) + { if (entries[i].hashCode >= 0) array[index++] = entries[i].key; } } - public int Count { + public int Count + { get { return dictionary.Count; } } - bool ICollection<TKey>.IsReadOnly { + bool ICollection<TKey>.IsReadOnly + { get { return true; } } - void ICollection<TKey>.Add(TKey item){ + void ICollection<TKey>.Add(TKey item) + { ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); } - - void ICollection<TKey>.Clear(){ + + void ICollection<TKey>.Clear() + { ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); } - bool ICollection<TKey>.Contains(TKey item){ + bool ICollection<TKey>.Contains(TKey item) + { return dictionary.ContainsKey(item); } - bool ICollection<TKey>.Remove(TKey item){ + bool ICollection<TKey>.Remove(TKey item) + { ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_KeyCollectionSet); return false; } - - IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator() { + + IEnumerator<TKey> IEnumerable<TKey>.GetEnumerator() + { return new Enumerator(dictionary); } - IEnumerator IEnumerable.GetEnumerator() { - return new Enumerator(dictionary); + IEnumerator IEnumerable.GetEnumerator() + { + return new Enumerator(dictionary); } - void ICollection.CopyTo(Array array, int index) { - if (array==null) { + void ICollection.CopyTo(Array array, int index) + { + if (array == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } - if (array.Rank != 1) { + if (array.Rank != 1) + { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); } - if( array.GetLowerBound(0) != 0 ) { + if (array.GetLowerBound(0) != 0) + { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); } - if (index < 0 || index > array.Length) { + if (index < 0 || index > array.Length) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } - if (array.Length - index < dictionary.Count) { + if (array.Length - index < dictionary.Count) + { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); } - + TKey[] keys = array as TKey[]; - if (keys != null) { + if (keys != null) + { CopyTo(keys, index); } - else { + else + { object[] objects = array as object[]; - if (objects == null) { + if (objects == null) + { ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } - + int count = dictionary.count; Entry[] entries = dictionary.entries; - try { - for (int i = 0; i < count; i++) { + try + { + for (int i = 0; i < count; i++) + { if (entries[i].hashCode >= 0) objects[index++] = entries[i].key; } - } - catch(ArrayTypeMismatchException) { + } + catch (ArrayTypeMismatchException) + { ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } } } - bool ICollection.IsSynchronized { + bool ICollection.IsSynchronized + { get { return false; } } - Object ICollection.SyncRoot { + Object ICollection.SyncRoot + { get { return ((ICollection)dictionary).SyncRoot; } } @@ -944,24 +1209,30 @@ namespace System.Collections.Generic { private int index; private int version; private TKey currentKey; - - internal Enumerator(Dictionary<TKey, TValue> dictionary) { + + internal Enumerator(Dictionary<TKey, TValue> dictionary) + { this.dictionary = dictionary; version = dictionary.version; index = 0; - currentKey = default(TKey); + currentKey = default(TKey); } - public void Dispose() { + public void Dispose() + { } - public bool MoveNext() { - if (version != dictionary.version) { + public bool MoveNext() + { + if (version != dictionary.version) + { ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } - while ((uint)index < (uint)dictionary.count) { - if (dictionary.entries[index].hashCode >= 0) { + while ((uint)index < (uint)dictionary.count) + { + if (dictionary.entries[index].hashCode >= 0) + { currentKey = dictionary.entries[index].key; index++; return true; @@ -973,153 +1244,189 @@ namespace System.Collections.Generic { currentKey = default(TKey); return false; } - - public TKey Current { - get { + + public TKey Current + { + get + { return currentKey; } } - Object System.Collections.IEnumerator.Current { - get { - if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); - } - + Object System.Collections.IEnumerator.Current + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + return currentKey; } } - - void System.Collections.IEnumerator.Reset() { - if (version != dictionary.version) { - ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); + + void System.Collections.IEnumerator.Reset() + { + if (version != dictionary.version) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } - index = 0; + index = 0; currentKey = default(TKey); } - } + } } [DebuggerTypeProxy(typeof(Mscorlib_DictionaryValueCollectionDebugView<,>))] [DebuggerDisplay("Count = {Count}")] [Serializable] - public sealed class ValueCollection: ICollection<TValue>, ICollection, IReadOnlyCollection<TValue> + public sealed class ValueCollection : ICollection<TValue>, ICollection, IReadOnlyCollection<TValue> { - private Dictionary<TKey,TValue> dictionary; + private Dictionary<TKey, TValue> dictionary; - public ValueCollection(Dictionary<TKey,TValue> dictionary) { - if (dictionary == null) { + public ValueCollection(Dictionary<TKey, TValue> dictionary) + { + if (dictionary == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary); } this.dictionary = dictionary; } - public Enumerator GetEnumerator() { - return new Enumerator(dictionary); + public Enumerator GetEnumerator() + { + return new Enumerator(dictionary); } - public void CopyTo(TValue[] array, int index) { - if (array == null) { + public void CopyTo(TValue[] array, int index) + { + if (array == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } - if (index < 0 || index > array.Length) { + if (index < 0 || index > array.Length) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } - if (array.Length - index < dictionary.Count) { + 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++) { + for (int i = 0; i < count; i++) + { if (entries[i].hashCode >= 0) array[index++] = entries[i].value; } } - public int Count { + public int Count + { get { return dictionary.Count; } } - bool ICollection<TValue>.IsReadOnly { + bool ICollection<TValue>.IsReadOnly + { get { return true; } } - void ICollection<TValue>.Add(TValue item){ + void ICollection<TValue>.Add(TValue item) + { ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); } - bool ICollection<TValue>.Remove(TValue item){ + bool ICollection<TValue>.Remove(TValue item) + { ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); return false; } - void ICollection<TValue>.Clear(){ + void ICollection<TValue>.Clear() + { ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_ValueCollectionSet); } - bool ICollection<TValue>.Contains(TValue item){ + bool ICollection<TValue>.Contains(TValue item) + { return dictionary.ContainsValue(item); } - IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator() { + IEnumerator<TValue> IEnumerable<TValue>.GetEnumerator() + { return new Enumerator(dictionary); } - IEnumerator IEnumerable.GetEnumerator() { - return new Enumerator(dictionary); + IEnumerator IEnumerable.GetEnumerator() + { + return new Enumerator(dictionary); } - void ICollection.CopyTo(Array array, int index) { - if (array == null) { + void ICollection.CopyTo(Array array, int index) + { + if (array == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } - if (array.Rank != 1) { + if (array.Rank != 1) + { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); } - if( array.GetLowerBound(0) != 0 ) { + if (array.GetLowerBound(0) != 0) + { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); } - if (index < 0 || index > array.Length) { + if (index < 0 || index > array.Length) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } if (array.Length - index < dictionary.Count) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_ArrayPlusOffTooSmall); - + TValue[] values = array as TValue[]; - if (values != null) { + if (values != null) + { CopyTo(values, index); } - else { + else + { object[] objects = array as object[]; - if (objects == null) { + if (objects == null) + { ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } int count = dictionary.count; Entry[] entries = dictionary.entries; - try { - for (int i = 0; i < count; i++) { + try + { + for (int i = 0; i < count; i++) + { if (entries[i].hashCode >= 0) objects[index++] = entries[i].value; } } - catch(ArrayTypeMismatchException) { + catch (ArrayTypeMismatchException) + { ThrowHelper.ThrowArgumentException_Argument_InvalidArrayType(); } } } - bool ICollection.IsSynchronized { + bool ICollection.IsSynchronized + { get { return false; } } - Object ICollection.SyncRoot { + Object ICollection.SyncRoot + { get { return ((ICollection)dictionary).SyncRoot; } } @@ -1130,24 +1437,30 @@ namespace System.Collections.Generic { private int index; private int version; private TValue currentValue; - - internal Enumerator(Dictionary<TKey, TValue> dictionary) { + + internal Enumerator(Dictionary<TKey, TValue> dictionary) + { this.dictionary = dictionary; version = dictionary.version; index = 0; currentValue = default(TValue); } - public void Dispose() { + public void Dispose() + { } - public bool MoveNext() { - if (version != dictionary.version) { + public bool MoveNext() + { + if (version != dictionary.version) + { ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } - - while ((uint)index < (uint)dictionary.count) { - if (dictionary.entries[index].hashCode >= 0) { + + while ((uint)index < (uint)dictionary.count) + { + if (dictionary.entries[index].hashCode >= 0) + { currentValue = dictionary.entries[index].value; index++; return true; @@ -1158,28 +1471,35 @@ namespace System.Collections.Generic { currentValue = default(TValue); return false; } - - public TValue Current { - get { + + public TValue Current + { + get + { return currentValue; } } - Object System.Collections.IEnumerator.Current { - get { - if( index == 0 || (index == dictionary.count + 1)) { - ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); - } - + Object System.Collections.IEnumerator.Current + { + get + { + if (index == 0 || (index == dictionary.count + 1)) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + } + return currentValue; } } - - void System.Collections.IEnumerator.Reset() { - if (version != dictionary.version) { + + void System.Collections.IEnumerator.Reset() + { + if (version != dictionary.version) + { ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } - index = 0; + index = 0; currentValue = default(TValue); } } diff --git a/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs b/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs index 0f9259d2f3..0cd1bc1c12 100644 --- a/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs +++ b/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs @@ -7,117 +7,56 @@ using System.Collections; using System.Collections.Generic; using System.Security; +using System.Globalization; +using System.Runtime; +using System.Runtime.CompilerServices; +using System.Diagnostics.Contracts; + 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 - // - 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 - } + // To minimize generic instantiation overhead of creating the comparer per type, we keep the generic portion of the code as small + // as possible and define most of the creation logic in a non-generic class. + public static EqualityComparer<T> Default { get; } = (EqualityComparer<T>)ComparerHelpers.CreateDefaultEqualityComparer(typeof(T)); [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) { + internal virtual int IndexOf(T[] array, T value, int startIndex, int count) + { int endIndex = startIndex + count; - for (int i = startIndex; i < endIndex; i++) { + 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) { + internal virtual int LastIndexOf(T[] array, T value, int startIndex, int count) + { int endIndex = startIndex - count + 1; - for (int i = startIndex; i >= endIndex; i--) { + for (int i = startIndex; i >= endIndex; i--) + { if (Equals(array[i], value)) return i; } return -1; } - int IEqualityComparer.GetHashCode(object obj) { + 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; - } + return 0; + } - bool IEqualityComparer.Equals(object x, object y) { + 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); @@ -129,11 +68,13 @@ namespace System.Collections.Generic // 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> + internal class GenericEqualityComparer<T> : EqualityComparer<T> where T : IEquatable<T> { [Pure] - public override bool Equals(T x, T y) { - if (x != null) { + public override bool Equals(T x, T y) + { + if (x != null) + { if (y != null) return x.Equals(y); return false; } @@ -144,30 +85,40 @@ namespace System.Collections.Generic [Pure] public override int GetHashCode(T obj) => obj?.GetHashCode() ?? 0; - internal override int IndexOf(T[] array, T value, int startIndex, int count) { + 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 (value == null) + { + for (int i = startIndex; i < endIndex; i++) + { if (array[i] == null) return i; } } - else { - for (int i = startIndex; i < endIndex; 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) { + 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 (value == null) + { + for (int i = startIndex; i >= endIndex; i--) + { if (array[i] == null) return i; } } - else { - for (int i = startIndex; i >= endIndex; i--) { + else + { + for (int i = startIndex; i >= endIndex; i--) + { if (array[i] != null && array[i].Equals(value)) return i; } } @@ -188,8 +139,10 @@ namespace System.Collections.Generic internal sealed class NullableEqualityComparer<T> : EqualityComparer<T?> where T : struct, IEquatable<T> { [Pure] - public override bool Equals(T? x, T? y) { - if (x.HasValue) { + public override bool Equals(T? x, T? y) + { + if (x.HasValue) + { if (y.HasValue) return x.value.Equals(y.value); return false; } @@ -200,30 +153,40 @@ namespace System.Collections.Generic [Pure] public override int GetHashCode(T? obj) => obj.GetHashCode(); - internal override int IndexOf(T?[] array, T? value, int startIndex, int count) { + internal override int IndexOf(T?[] array, T? value, int startIndex, int count) + { int endIndex = startIndex + count; - if (!value.HasValue) { - for (int i = startIndex; i < endIndex; i++) { + if (!value.HasValue) + { + for (int i = startIndex; i < endIndex; i++) + { if (!array[i].HasValue) return i; } } - else { - for (int i = startIndex; i < endIndex; 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(T?[] array, T? value, int startIndex, int count) { + internal override int LastIndexOf(T?[] array, T? value, int startIndex, int count) + { int endIndex = startIndex - count + 1; - if (!value.HasValue) { - for (int i = startIndex; i >= endIndex; i--) { + if (!value.HasValue) + { + for (int i = startIndex; i >= endIndex; i--) + { if (!array[i].HasValue) return i; } } - else { - for (int i = startIndex; i >= endIndex; i--) { + else + { + for (int i = startIndex; i >= endIndex; i--) + { if (array[i].HasValue && array[i].value.Equals(value.value)) return i; } } @@ -239,11 +202,13 @@ namespace System.Collections.Generic } [Serializable] - internal sealed class ObjectEqualityComparer<T>: EqualityComparer<T> + internal sealed class ObjectEqualityComparer<T> : EqualityComparer<T> { [Pure] - public override bool Equals(T x, T y) { - if (x != null) { + public override bool Equals(T x, T y) + { + if (x != null) + { if (y != null) return x.Equals(y); return false; } @@ -254,30 +219,40 @@ namespace System.Collections.Generic [Pure] public override int GetHashCode(T obj) => obj?.GetHashCode() ?? 0; - internal override int IndexOf(T[] array, T value, int startIndex, int count) { + 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 (value == null) + { + for (int i = startIndex; i < endIndex; i++) + { if (array[i] == null) return i; } } - else { - for (int i = startIndex; i < endIndex; 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) { + 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 (value == null) + { + for (int i = startIndex; i >= endIndex; i--) + { if (array[i] == null) return i; } } - else { - for (int i = startIndex; i >= endIndex; i--) { + else + { + for (int i = startIndex; i >= endIndex; i--) + { if (array[i] != null && array[i].Equals(value)) return i; } } @@ -299,20 +274,25 @@ namespace System.Collections.Generic // keep the perofrmance not affected till we hit collision threshold and then we switch to the comparer which is using // randomized string hashing GenericEqualityComparer<string> [Serializable] - internal class NonRandomizedStringEqualityComparer : GenericEqualityComparer<string> { - static IEqualityComparer<string> s_nonRandomizedComparer; - - internal static new IEqualityComparer<string> Default { - get { - if (s_nonRandomizedComparer == null) { - s_nonRandomizedComparer = new NonRandomizedStringEqualityComparer(); - } - return s_nonRandomizedComparer; + internal class NonRandomizedStringEqualityComparer : GenericEqualityComparer<string> + { + private 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) { + public override int GetHashCode(string obj) + { if (obj == null) return 0; return obj.GetLegacyNonRandomizedHashCode(); } @@ -321,37 +301,43 @@ namespace System.Collections.Generic // 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 sealed class ByteEqualityComparer: EqualityComparer<byte> + internal sealed class ByteEqualityComparer : EqualityComparer<byte> { [Pure] - public override bool Equals(byte x, byte y) { + public override bool Equals(byte x, byte y) + { return x == y; } [Pure] - public override int GetHashCode(byte b) { + public override int GetHashCode(byte b) + { return b.GetHashCode(); } - internal unsafe override int IndexOf(byte[] array, byte value, int startIndex, int count) { - if (array==null) + internal unsafe override int IndexOf(byte[] array, byte value, int startIndex, int count) + { + if (array == null) throw new ArgumentNullException(nameof(array)); if (startIndex < 0) - throw new ArgumentOutOfRangeException(nameof(startIndex), Environment.GetResourceString("ArgumentOutOfRange_Index")); + throw new ArgumentOutOfRangeException(nameof(startIndex), SR.ArgumentOutOfRange_Index); if (count < 0) - throw new ArgumentOutOfRangeException(nameof(count), Environment.GetResourceString("ArgumentOutOfRange_Count")); + throw new ArgumentOutOfRangeException(nameof(count), SR.ArgumentOutOfRange_Count); if (count > array.Length - startIndex) - throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen")); + throw new ArgumentException(SR.Argument_InvalidOffLen); Contract.EndContractBlock(); if (count == 0) return -1; - fixed (byte* pbytes = array) { + fixed (byte* pbytes = array) + { return Buffer.IndexOfByte(pbytes, value, startIndex, count); } } - internal override int LastIndexOf(byte[] array, byte value, int startIndex, int 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--) { + for (int i = startIndex; i >= endIndex; i--) + { if (array[i] == value) return i; } return -1; @@ -362,21 +348,23 @@ namespace System.Collections.Generic obj != null && GetType() == obj.GetType(); public override int GetHashCode() => - GetType().GetHashCode(); + GetType().GetHashCode(); } [Serializable] internal class EnumEqualityComparer<T> : EqualityComparer<T> where T : struct { [Pure] - public override bool Equals(T x, T y) { + 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) { + public override int GetHashCode(T obj) + { int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(obj); return x_final.GetHashCode(); } @@ -421,7 +409,8 @@ namespace System.Collections.Generic public SByteEnumEqualityComparer() { } [Pure] - public override int GetHashCode(T obj) { + public override int GetHashCode(T obj) + { int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(obj); return ((sbyte)x_final).GetHashCode(); } @@ -433,7 +422,8 @@ namespace System.Collections.Generic public ShortEnumEqualityComparer() { } [Pure] - public override int GetHashCode(T obj) { + public override int GetHashCode(T obj) + { int x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCast(obj); return ((short)x_final).GetHashCode(); } @@ -443,14 +433,16 @@ namespace System.Collections.Generic internal sealed class LongEnumEqualityComparer<T> : EqualityComparer<T> where T : struct { [Pure] - public override bool Equals(T x, T y) { + 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) { + public override int GetHashCode(T obj) + { long x_final = System.Runtime.CompilerServices.JitHelpers.UnsafeEnumCastLong(obj); return x_final.GetHashCode(); } diff --git a/src/mscorlib/src/System/Collections/Generic/ICollection.cs b/src/mscorlib/src/System/Collections/Generic/ICollection.cs deleted file mode 100644 index 741e8cc79b..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/ICollection.cs +++ /dev/null @@ -1,52 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** 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 deleted file mode 100644 index 7b9e97ff0e..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/IComparer.cs +++ /dev/null @@ -1,30 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** 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 deleted file mode 100644 index 2a2da944d3..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/IDictionary.cs +++ /dev/null @@ -1,58 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** 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 deleted file mode 100644 index 67f35ce675..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/IEnumerable.cs +++ /dev/null @@ -1,38 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** 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 deleted file mode 100644 index 335616757b..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/IEnumerator.cs +++ /dev/null @@ -1,35 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** 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 deleted file mode 100644 index b6ac3be006..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/IEqualityComparer.cs +++ /dev/null @@ -1,19 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -// - -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 deleted file mode 100644 index 75ca0a9b00..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/IList.cs +++ /dev/null @@ -1,54 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** 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 deleted file mode 100644 index 13bc718760..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/IReadOnlyCollection.cs +++ /dev/null @@ -1,34 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** 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 deleted file mode 100644 index 3603b9a4ea..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/IReadOnlyDictionary.cs +++ /dev/null @@ -1,29 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** 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 deleted file mode 100644 index 77366f0b2f..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/IReadOnlyList.cs +++ /dev/null @@ -1,34 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** 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 deleted file mode 100644 index 1cd18cf808..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/KeyNotFoundException.cs +++ /dev/null @@ -1,44 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================================= -** -** -** -** -** -** Purpose: Exception class for Hashtable and Dictionary. -** -** -=============================================================================*/ - -namespace System.Collections.Generic { - - using System; - using System.Runtime.Remoting; - using System.Runtime.Serialization; - - [Serializable] - 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 deleted file mode 100644 index ba98adad7d..0000000000 --- a/src/mscorlib/src/System/Collections/Generic/KeyValuePair.cs +++ /dev/null @@ -1,74 +0,0 @@ -// Licensed to the .NET Foundation under one or more agreements. -// The .NET Foundation licenses this file to you under the MIT license. -// See the LICENSE file in the project root for more information. - -/*============================================================ -** -** Interface: KeyValuePair -** -** -** -** -** Purpose: Generic key-value pair for dictionary enumerators. -** -** -===========================================================*/ -namespace System.Collections.Generic { - - using System; - using System.ComponentModel; - using System.Text; - - // Provides the Create factory method for KeyValuePair<TKey, TValue>. - public static class KeyValuePair - { - // Creates a new KeyValuePair<TKey, TValue> from the given values. - public static KeyValuePair<TKey, TValue> Create<TKey, TValue>(TKey key, TValue value) - { - return new KeyValuePair<TKey, TValue>(key, value); - } - } - - // A KeyValuePair holds a key and a value from a dictionary. - // It is used by the IEnumerable<T> implementation for both IDictionary<TKey, TValue> - // and IReadOnlyDictionary<TKey, TValue>. - [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); - } - - [EditorBrowsable(EditorBrowsableState.Never)] - public void Deconstruct(out TKey key, out TValue value) - { - key = Key; - value = Value; - } - } -} diff --git a/src/mscorlib/src/System/Collections/Generic/List.cs b/src/mscorlib/src/System/Collections/Generic/List.cs index 362e26599d..67d1668aad 100644 --- a/src/mscorlib/src/System/Collections/Generic/List.cs +++ b/src/mscorlib/src/System/Collections/Generic/List.cs @@ -12,15 +12,15 @@ ** ** ===========================================================*/ -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; +using System.Diagnostics; +using System.Diagnostics.Contracts; +using System.Collections.ObjectModel; +using System.Runtime.CompilerServices; +namespace System.Collections.Generic +{ // 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 @@ -40,22 +40,24 @@ namespace System.Collections.Generic { private int _version; [NonSerialized] private Object _syncRoot; - - static readonly T[] _emptyArray = new T[0]; - + + private 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() { + 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) { + public List(int capacity) + { if (capacity < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); Contract.EndContractBlock(); @@ -64,116 +66,142 @@ namespace System.Collections.Generic { 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) + public List(IEnumerable<T> collection) + { + if (collection == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); Contract.EndContractBlock(); ICollection<T> c = collection as ICollection<T>; - if( c != null) { + if (c != null) + { int count = c.Count; if (count == 0) { _items = _emptyArray; } - else { + else + { _items = new T[count]; c.CopyTo(_items, 0); _size = count; } - } - else { + } + else + { _size = 0; _items = _emptyArray; AddEnumerable(collection); } } - + // 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 { + public int Capacity + { + get + { Contract.Ensures(Contract.Result<int>() >= 0); return _items.Length; } - set { - if (value < _size) { + set + { + if (value < _size) + { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity); } Contract.EndContractBlock(); - if (value != _items.Length) { - if (value > 0) { + if (value != _items.Length) + { + if (value > 0) + { T[] newItems = new T[value]; - if (_size > 0) { + if (_size > 0) + { Array.Copy(_items, 0, newItems, 0, _size); } _items = newItems; } - else { + else + { _items = _emptyArray; } } } } - + // Read-only property describing how many elements are in the List. - public int Count { - get { + public int Count + { + get + { Contract.Ensures(Contract.Result<int>() >= 0); - return _size; + return _size; } } - bool System.Collections.IList.IsFixedSize { + bool System.Collections.IList.IsFixedSize + { get { return false; } } - + // Is this List read-only? - bool ICollection<T>.IsReadOnly { + bool ICollection<T>.IsReadOnly + { get { return false; } } - bool System.Collections.IList.IsReadOnly { + bool System.Collections.IList.IsReadOnly + { get { return false; } } // Is this List synchronized (thread-safe)? - bool System.Collections.ICollection.IsSynchronized { + 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); + 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 { + public T this[int index] + { + get + { // Following trick can reduce the range check by one - if ((uint) index >= (uint)_size) { + if ((uint)index >= (uint)_size) + { ThrowHelper.ThrowArgumentOutOfRange_IndexException(); } Contract.EndContractBlock(); - return _items[index]; + return _items[index]; } - set { - if ((uint) index >= (uint)_size) { + set + { + if ((uint)index >= (uint)_size) + { ThrowHelper.ThrowArgumentOutOfRange_IndexException(); } Contract.EndContractBlock(); @@ -182,24 +210,30 @@ namespace System.Collections.Generic { } } - private static bool IsCompatibleObject(object value) { + 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 { + Object System.Collections.IList.this[int index] + { + get + { return this[index]; } - set { + set + { ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(value, ExceptionArgument.value); - try { - this[index] = (T)value; + try + { + this[index] = (T)value; } - catch (InvalidCastException) { - ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(T)); + catch (InvalidCastException) + { + ThrowHelper.ThrowWrongValueTypeArgumentException(value, typeof(T)); } } } @@ -207,22 +241,44 @@ namespace System.Collections.Generic { // 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; + [MethodImpl(MethodImplOptions.AggressiveInlining)] + public void Add(T item) + { + var array = _items; + var size = _size; _version++; + if ((uint)size < (uint)array.Length) + { + _size = size + 1; + array[size] = item; + } + else + { + AddWithResize(item); + } + } + + // Non-inline from List.Add to improve its code quality as uncommon path + [MethodImpl(MethodImplOptions.NoInlining)] + private void AddWithResize(T item) + { + var size = _size; + EnsureCapacity(size + 1); + _size = size + 1; + _items[size] = item; } int System.Collections.IList.Add(Object item) { ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(item, ExceptionArgument.item); - try { - Add((T) item); + try + { + Add((T)item); } - catch (InvalidCastException) { - ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T)); + catch (InvalidCastException) + { + ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T)); } return Count - 1; @@ -233,17 +289,19 @@ namespace System.Collections.Generic { // 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) { + public void AddRange(IEnumerable<T> collection) + { Contract.Ensures(Count >= Contract.OldValue(Count)); InsertRange(_size, collection); } - public ReadOnlyCollection<T> AsReadOnly() { + 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 @@ -264,7 +322,8 @@ namespace System.Collections.Generic { // The method uses the Array.BinarySearch method to perform the // search. // - public int BinarySearch(int index, int count, T item, IComparer<T> comparer) { + public int BinarySearch(int index, int count, T item, IComparer<T> comparer) + { if (index < 0) ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); if (count < 0) @@ -276,7 +335,7 @@ namespace System.Collections.Generic { return Array.BinarySearch<T>(_items, index, count, item, comparer); } - + public int BinarySearch(T item) { Contract.Ensures(Contract.Result<int>() <= Count); @@ -289,17 +348,27 @@ namespace System.Collections.Generic { return BinarySearch(0, Count, item, comparer); } - + // Clears the contents of List. - public void Clear() { - if (_size > 0) + public void Clear() + { + if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) { - Array.Clear(_items, 0, _size); // Don't need to doc this but we clear the elements so that the gc can reclaim the references. + int size = _size; _size = 0; + _version++; + if (size > 0) + { + Array.Clear(_items, 0, size); // Clear the elements so that the gc can reclaim the references. + } + } + else + { + _size = 0; + _version++; } - _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(). @@ -319,21 +388,25 @@ namespace System.Collections.Generic { bool System.Collections.IList.Contains(Object item) { - if(IsCompatibleObject(item)) { - return Contains((T) item); + if (IsCompatibleObject(item)) + { + return Contains((T)item); } return false; } - public List<TOutput> ConvertAll<TOutput>(Converter<T,TOutput> converter) { - if( converter == null) { + 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++) { + for (int i = 0; i < _size; i++) + { list._items[i] = converter(_items[i]); } list._size = _size; @@ -343,43 +416,51 @@ namespace System.Collections.Generic { // Copies this List into array, which must be of a // compatible array type. // - public void CopyTo(T[] array) { + 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)) { + void System.Collections.ICollection.CopyTo(Array array, int arrayIndex) + { + if ((array != null) && (array.Rank != 1)) + { ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported); } Contract.EndContractBlock(); - try { + try + { // Array.Copy will check for NULL. Array.Copy(_items, 0, array, arrayIndex, _size); } - catch(ArrayTypeMismatchException){ + catch (ArrayTypeMismatchException) + { ThrowHelper.ThrowArgumentException_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) { + 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) { + public void CopyTo(T[] array, int arrayIndex) + { // Delegate rest of error checking to Array.Copy. Array.Copy(_items, 0, array, arrayIndex, _size); } @@ -388,9 +469,11 @@ namespace System.Collections.Generic { // value. If the current capacity of the list is less than min, the // capacity is increased to twice the current capacity or to min, // whichever is larger. - private void EnsureCapacity(int min) { - if (_items.Length < min) { - int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2; + 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; @@ -398,62 +481,77 @@ namespace System.Collections.Generic { Capacity = newCapacity; } } - - public bool Exists(Predicate<T> match) { + + public bool Exists(Predicate<T> match) + { return FindIndex(match) != -1; } - public T Find(Predicate<T> match) { - if( match == null) { + 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])) { + 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) { + + 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<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) { + + 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) { + + 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.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index(); + + public int FindIndex(int startIndex, int count, Predicate<T> match) + { + if ((uint)startIndex > (uint)_size) + { + ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index(); } - if (count < 0 || startIndex > _size - count) { + if (count < 0 || startIndex > _size - count) + { ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count(); } - if( match == null) { + if (match == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match); } Contract.Ensures(Contract.Result<int>() >= -1); @@ -461,83 +559,103 @@ namespace System.Collections.Generic { Contract.EndContractBlock(); int endIndex = startIndex + count; - for( int i = startIndex; i < endIndex; i++) { - if( match(_items[i])) return i; + for (int i = startIndex; i < endIndex; i++) + { + if (match(_items[i])) return i; } return -1; } - - public T FindLast(Predicate<T> match) { - if( match == null) { + + 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])) { + for (int i = _size - 1; i >= 0; i--) + { + if (match(_items[i])) + { return _items[i]; } } return default(T); } - public int FindLastIndex(Predicate<T> match) { + 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) { + + 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) { + 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) { + if (_size == 0) + { // Special case for 0 length List - if( startIndex != -1) { + if (startIndex != -1) + { ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index(); } } - else { + else + { // Make sure we're not out of range - if ( (uint)startIndex >= (uint)_size) { + if ((uint)startIndex >= (uint)_size) + { ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index(); } } - + // 2nd have of this also catches when startIndex == MAXINT, so MAXINT - 0 + 1 == -1, which is < 0. - if (count < 0 || startIndex - count + 1 < 0) { + if (count < 0 || startIndex - count + 1 < 0) + { ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count(); } - + int endIndex = startIndex - count; - for( int i = startIndex; i > endIndex; i--) { - if( match(_items[i])) { + for (int i = startIndex; i > endIndex; i--) + { + if (match(_items[i])) + { return i; } } return -1; } - public void ForEach(Action<T> action) { - if( action == null) { + 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) { + for (int i = 0; i < _size; i++) + { + if (version != _version) + { break; } action(_items[i]); @@ -552,36 +670,42 @@ namespace System.Collections.Generic { // while an enumeration is in progress, the MoveNext and // GetObject methods of the enumerator will throw an exception. // - public Enumerator GetEnumerator() { + public Enumerator GetEnumerator() + { return new Enumerator(this); } - /// <internalonly/> - IEnumerator<T> IEnumerable<T>.GetEnumerator() { + IEnumerator<T> IEnumerable<T>.GetEnumerator() + { return new Enumerator(this); } - System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() { + System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() + { return new Enumerator(this); } - public List<T> GetRange(int index, int count) { - if (index < 0) { + public List<T> GetRange(int index, int count) + { + if (index < 0) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } - if (count < 0) { + if (count < 0) + { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); } - if (_size - index < count) { - ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); + 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); + Array.Copy(_items, index, list._items, 0, count); list._size = count; return list; } @@ -595,7 +719,8 @@ namespace System.Collections.Generic { // This method uses the Array.IndexOf method to perform the // search. // - public int IndexOf(T item) { + public int IndexOf(T item) + { Contract.Ensures(Contract.Result<int>() >= -1); Contract.Ensures(Contract.Result<int>() < Count); return Array.IndexOf(_items, item, 0, _size); @@ -603,7 +728,8 @@ namespace System.Collections.Generic { int System.Collections.IList.IndexOf(Object item) { - if(IsCompatibleObject(item)) { + if (IsCompatibleObject(item)) + { return IndexOf((T)item); } return -1; @@ -618,7 +744,8 @@ namespace System.Collections.Generic { // This method uses the Array.IndexOf method to perform the // search. // - public int IndexOf(T item, int index) { + public int IndexOf(T item, int index) + { if (index > _size) ThrowHelper.ThrowArgumentOutOfRange_IndexException(); Contract.Ensures(Contract.Result<int>() >= -1); @@ -636,46 +763,52 @@ namespace System.Collections.Generic { // This method uses the Array.IndexOf method to perform the // search. // - public int IndexOf(T item, int index, int count) { + public int IndexOf(T item, int index, int count) + { if (index > _size) ThrowHelper.ThrowArgumentOutOfRange_IndexException(); - if (count <0 || index > _size - count) ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count(); + if (count < 0 || index > _size - count) ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count(); Contract.Ensures(Contract.Result<int>() >= -1); Contract.Ensures(Contract.Result<int>() < Count); Contract.EndContractBlock(); 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) { + public void Insert(int index, T item) + { // Note that insertions at the end are legal. - if ((uint) index > (uint)_size) { + if ((uint)index > (uint)_size) + { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert); } Contract.EndContractBlock(); if (_size == _items.Length) EnsureCapacity(_size + 1); - if (index < _size) { + if (index < _size) + { Array.Copy(_items, index, _items, index + 1, _size - index); } _items[index] = item; - _size++; + _size++; _version++; } - + void System.Collections.IList.Insert(int index, Object item) { ThrowHelper.IfNullAndNullsAreIllegalThenThrow<T>(item, ExceptionArgument.item); - try { - Insert(index, (T) item); + try + { + Insert(index, (T)item); } - catch (InvalidCastException) { - ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T)); + catch (InvalidCastException) + { + ThrowHelper.ThrowWrongValueTypeArgumentException(item, typeof(T)); } } @@ -684,44 +817,55 @@ namespace System.Collections.Generic { // 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) { + public void InsertRange(int index, IEnumerable<T> collection) + { + if (collection == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); } - - if ((uint)index > (uint)_size) { + + if ((uint)index > (uint)_size) + { ThrowHelper.ThrowArgumentOutOfRange_IndexException(); } Contract.EndContractBlock(); ICollection<T> c = collection as ICollection<T>; - if( c != null ) { // if collection is ICollection<T> + if (c != null) + { // if collection is ICollection<T> int count = c.Count; - if (count > 0) { + if (count > 0) + { EnsureCapacity(_size + count); - if (index < _size) { + 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) { + 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); + Array.Copy(_items, index + count, _items, index * 2, _size - index); } - else { + else + { c.CopyTo(_items, index); } _size += count; - } + } } - else if (index < _size) { + else if (index < _size) + { // We're inserting a lazy enumerable. Call Insert on each of the constituent items. - using(IEnumerator<T> en = collection.GetEnumerator()) { - while(en.MoveNext()) { - Insert(index++, en.Current); - } + using (IEnumerator<T> en = collection.GetEnumerator()) + { + while (en.MoveNext()) + { + Insert(index++, en.Current); + } } } else @@ -729,9 +873,9 @@ namespace System.Collections.Generic { // We're adding a lazy enumerable because the index is at the end of this list. AddEnumerable(collection); } - _version++; + _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 @@ -744,10 +888,12 @@ namespace System.Collections.Generic { { Contract.Ensures(Contract.Result<int>() >= -1); Contract.Ensures(Contract.Result<int>() < Count); - if (_size == 0) { // Special case for empty list + if (_size == 0) + { // Special case for empty list return -1; } - else { + else + { return LastIndexOf(item, _size - 1, _size); } } @@ -780,39 +926,47 @@ namespace System.Collections.Generic { // 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)) { + public int LastIndexOf(T item, int index, int count) + { + if ((Count != 0) && (index < 0)) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } - if ((Count !=0) && (count < 0)) { + 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 + if (_size == 0) + { // Special case for empty list return -1; } - if (index >= _size) { + if (index >= _size) + { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_BiggerThanCollection); } - if (count > index + 1) { + 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) { + public bool Remove(T item) + { int index = IndexOf(item); - if (index >= 0) { + if (index >= 0) + { RemoveAt(index); return true; } @@ -822,39 +976,48 @@ namespace System.Collections.Generic { void System.Collections.IList.Remove(Object item) { - if(IsCompatibleObject(item)) { - Remove((T) 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) { + 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; - + while (freeIndex < _size && !match(_items[freeIndex])) freeIndex++; + if (freeIndex >= _size) return 0; + int current = freeIndex + 1; - while( current < _size) { + while (current < _size) + { // Find the first item which needs to be kept. - while( current < _size && match(_items[current])) current++; + while (current < _size && match(_items[current])) current++; - if( current < _size) { + if (current < _size) + { // copy item to the free slot. _items[freeIndex++] = _items[current++]; } - } - - Array.Clear(_items, freeIndex, _size - freeIndex); + } + + if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) + { + Array.Clear(_items, freeIndex, _size - freeIndex); // Clear the elements so that the gc can reclaim the references. + } + int result = _size - freeIndex; _size = freeIndex; _version++; @@ -864,61 +1027,80 @@ namespace System.Collections.Generic { // 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) { + public void RemoveAt(int index) + { + if ((uint)index >= (uint)_size) + { ThrowHelper.ThrowArgumentOutOfRange_IndexException(); } Contract.EndContractBlock(); _size--; - if (index < _size) { + if (index < _size) + { Array.Copy(_items, index + 1, _items, index, _size - index); } - _items[_size] = default(T); + if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) + { + _items[_size] = default(T); + } _version++; } - + // Removes a range of elements from this list. // - public void RemoveRange(int index, int count) { - if (index < 0) { + public void RemoveRange(int index, int count) + { + if (index < 0) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } - if (count < 0) { + if (count < 0) + { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); } - + if (_size - index < count) ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); Contract.EndContractBlock(); - - if (count > 0) { + + if (count > 0) + { int i = _size; _size -= count; - if (index < _size) { + if (index < _size) + { Array.Copy(_items, index + count, _items, index, _size - index); } - Array.Clear(_items, _size, count); + _version++; + if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) + { + Array.Clear(_items, _size, count); + } } } - + // Reverses the elements in this list. - public void Reverse() { + 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) { + public void Reverse(int index, int count) + { + if (index < 0) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } - - if (count < 0) { + + if (count < 0) + { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); } @@ -926,12 +1108,13 @@ namespace System.Collections.Generic { ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); Contract.EndContractBlock(); - if (count > 1) { + if (count > 1) + { Array.Reverse(_items, index, count); } _version++; } - + // Sorts the elements in this list. Uses the default comparer and // Array.Sort. public void Sort() @@ -954,32 +1137,39 @@ namespace System.Collections.Generic { // // This method uses the Array.Sort method to sort the elements. // - public void Sort(int index, int count, IComparer<T> comparer) { - if (index < 0) { + public void Sort(int index, int count, IComparer<T> comparer) + { + if (index < 0) + { ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException(); } - - if (count < 0) { + + if (count < 0) + { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); } - + if (_size - index < count) ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen); Contract.EndContractBlock(); - if (count > 1) { + if (count > 1) + { Array.Sort<T>(_items, index, count, comparer); } _version++; } - public void Sort(Comparison<T> comparison) { - if( comparison == null) { + public void Sort(Comparison<T> comparison) + { + if (comparison == null) + { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparison); } Contract.EndContractBlock(); - if (_size > 1) { + if (_size > 1) + { ArraySortHelper<T>.Sort(_items, 0, _size, comparison); } _version++; @@ -987,7 +1177,8 @@ namespace System.Collections.Generic { // ToArray returns an array containing the contents of the List. // This requires copying the List, which is an O(n) operation. - public T[] ToArray() { + public T[] ToArray() + { Contract.Ensures(Contract.Result<T[]>() != null); Contract.Ensures(Contract.Result<T[]>().Length == Count); @@ -1000,7 +1191,7 @@ namespace System.Collections.Generic { 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 @@ -1010,21 +1201,27 @@ namespace System.Collections.Generic { // list.Clear(); // list.TrimExcess(); // - public void TrimExcess() { - int threshold = (int)(((double)_items.Length) * 0.9); - if( _size < threshold ) { - Capacity = _size; + 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) { + 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])) { + for (int i = 0; i < _size; i++) + { + if (!match(_items[i])) + { return false; } } @@ -1064,23 +1261,25 @@ namespace System.Collections.Generic { private int version; private T current; - internal Enumerator(List<T> list) { + internal Enumerator(List<T> list) + { this.list = list; index = 0; version = list._version; current = default(T); } - public void Dispose() { + public void Dispose() + { } - public bool MoveNext() { - + public bool MoveNext() + { List<T> localList = list; - if (version == localList._version && ((uint)index < (uint)localList._size)) - { - current = localList._items[index]; + if (version == localList._version && ((uint)index < (uint)localList._size)) + { + current = localList._items[index]; index++; return true; } @@ -1088,40 +1287,47 @@ namespace System.Collections.Generic { } private bool MoveNextRare() - { - if (version != list._version) { + { + if (version != list._version) + { ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } index = list._size + 1; current = default(T); - return false; + return false; } - public T Current { - get { + public T Current + { + get + { return current; } } - Object System.Collections.IEnumerator.Current { - get { - if( index == 0 || index == list._size + 1) { - ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); + Object System.Collections.IEnumerator.Current + { + get + { + if (index == 0 || index == list._size + 1) + { + ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumOpCantHappen(); } return Current; } } - - void System.Collections.IEnumerator.Reset() { - if (version != list._version) { + + void System.Collections.IEnumerator.Reset() + { + if (version != list._version) + { ThrowHelper.ThrowInvalidOperationException_InvalidOperation_EnumFailedVersion(); } - + index = 0; current = default(T); } - } } } |