diff options
Diffstat (limited to 'src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs')
| -rw-r--r-- | src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs | 290 |
1 files changed, 141 insertions, 149 deletions
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(); } |