summaryrefslogtreecommitdiff
path: root/src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs
diff options
context:
space:
mode:
Diffstat (limited to 'src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs')
-rw-r--r--src/mscorlib/src/System/Collections/Generic/EqualityComparer.cs290
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 0f9259d..0cd1bc1 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();
}