Files
Filip Navara bd278dd00d Mirror changes from mono/corefx,coreclr (#17777)
* Rewrite the rest of the array non-generic fast paths in C# (#27703)

* Rewrite the rest of the array non-generic fast paths in C#

* Add missing resource string

* Use CorElementType and handle native ints to match the unmanaged implementation

* Avoid try pattern for Sort and Reverse

* Match the native implementation more closely

Signed-off-by: dotnet-bot <[email protected]>

* Rewrite Enum.CompareTo in C# (dotnet/coreclr#27792)

* Rewrite Enum.CompareTo in C#

* Handle floating point too for match the existing native implementation

Signed-off-by: dotnet-bot <[email protected]>

* Remove unused argument from GetRegionDisplayName (dotnet/coreclr#27806)

* Remove unused argument from GetRegionDisplayName

* Address race conditions in CultureData

While most of the race conditions in this file are benign, in these cases, a thread could end up returning an intermediate value due to multiple potential writes to the same field.

Signed-off-by: dotnet-bot <[email protected]>

* Fix StyleCop rule SA1129 ("Do not use default value type constructor") (#27716)

Will enable the rule in corefx once these changes have propagated.

Signed-off-by: dotnet-bot <[email protected]>

* Remove non-shared Enum.CompareTo/InternalCompareTo implementation, add new Array icalls used by shared code
2019-11-12 18:46:00 +01:00

2270 lines
88 KiB
C#

// 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.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Diagnostics.CodeAnalysis;
using System.Reflection;
using System.Runtime.CompilerServices;
using Internal.Runtime.CompilerServices;
namespace System
{
[Serializable]
[System.Runtime.CompilerServices.TypeForwardedFrom("mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")]
public abstract partial class Array : ICloneable, IList, IStructuralComparable, IStructuralEquatable
{
// We impose limits on maximum array length in each dimension to allow efficient
// implementation of advanced range check elimination in future.
// Keep in sync with vm\gcscan.cpp and HashHelpers.MaxPrimeArrayLength.
// The constants are defined in this method: inline SIZE_T MaxArrayLength(SIZE_T componentSize) from gcscan
// We have different max sizes for arrays with elements of size 1 for backwards compatibility
internal const int MaxArrayLength = 0X7FEFFFFF;
internal const int MaxByteArrayLength = 0x7FFFFFC7;
// This ctor exists solely to prevent C# from generating a protected .ctor that violates the surface area.
private protected Array() { }
public static ReadOnlyCollection<T> AsReadOnly<T>(T[] array)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
// T[] implements IList<T>.
return new ReadOnlyCollection<T>(array);
}
public static void Resize<T>([NotNull] ref T[]? array, int newSize)
{
if (newSize < 0)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.newSize, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
T[]? larray = array;
if (larray == null)
{
array = new T[newSize];
return;
}
if (larray.Length != newSize)
{
T[] newArray = new T[newSize];
Copy(larray, 0, newArray, 0, larray.Length > newSize ? newSize : larray.Length);
array = newArray;
}
}
public static Array CreateInstance(Type elementType, params long[] lengths)
{
if (lengths == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.lengths);
}
if (lengths.Length == 0)
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NeedAtLeast1Rank);
int[] intLengths = new int[lengths.Length];
for (int i = 0; i < lengths.Length; ++i)
{
long len = lengths[i];
int ilen = (int)len;
if (len != ilen)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.len, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
intLengths[i] = ilen;
}
return Array.CreateInstance(elementType, intLengths);
}
public static void Copy(Array sourceArray, Array destinationArray, long length)
{
int ilength = (int)length;
if (length != ilength)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
Copy(sourceArray, destinationArray, ilength);
}
public static void Copy(Array sourceArray, long sourceIndex, Array destinationArray, long destinationIndex, long length)
{
int isourceIndex = (int)sourceIndex;
int idestinationIndex = (int)destinationIndex;
int ilength = (int)length;
if (sourceIndex != isourceIndex)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.sourceIndex, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
if (destinationIndex != idestinationIndex)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.destinationIndex, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
if (length != ilength)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.length, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
Copy(sourceArray, isourceIndex, destinationArray, idestinationIndex, ilength);
}
public object? GetValue(long index)
{
int iindex = (int)index;
if (index != iindex)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
return this.GetValue(iindex);
}
public object? GetValue(long index1, long index2)
{
int iindex1 = (int)index1;
int iindex2 = (int)index2;
if (index1 != iindex1)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index1, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
if (index2 != iindex2)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index2, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
return this.GetValue(iindex1, iindex2);
}
public object? GetValue(long index1, long index2, long index3)
{
int iindex1 = (int)index1;
int iindex2 = (int)index2;
int iindex3 = (int)index3;
if (index1 != iindex1)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index1, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
if (index2 != iindex2)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index2, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
if (index3 != iindex3)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index3, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
return this.GetValue(iindex1, iindex2, iindex3);
}
public object? GetValue(params long[] indices)
{
if (indices == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.indices);
if (Rank != indices.Length)
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankIndices);
int[] intIndices = new int[indices.Length];
for (int i = 0; i < indices.Length; ++i)
{
long index = indices[i];
int iindex = (int)index;
if (index != iindex)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
intIndices[i] = iindex;
}
return this.GetValue(intIndices);
}
public void SetValue(object? value, long index)
{
int iindex = (int)index;
if (index != iindex)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
this.SetValue(value, iindex);
}
public void SetValue(object? value, long index1, long index2)
{
int iindex1 = (int)index1;
int iindex2 = (int)index2;
if (index1 != iindex1)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index1, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
if (index2 != iindex2)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index2, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
this.SetValue(value, iindex1, iindex2);
}
public void SetValue(object? value, long index1, long index2, long index3)
{
int iindex1 = (int)index1;
int iindex2 = (int)index2;
int iindex3 = (int)index3;
if (index1 != iindex1)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index1, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
if (index2 != iindex2)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index2, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
if (index3 != iindex3)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index3, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
this.SetValue(value, iindex1, iindex2, iindex3);
}
public void SetValue(object? value, params long[] indices)
{
if (indices == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.indices);
if (Rank != indices.Length)
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankIndices);
int[] intIndices = new int[indices.Length];
for (int i = 0; i < indices.Length; ++i)
{
long index = indices[i];
int iindex = (int)index;
if (index != iindex)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
intIndices[i] = iindex;
}
this.SetValue(value, intIndices);
}
private static int GetMedian(int low, int hi)
{
// Note both may be negative, if we are dealing with arrays w/ negative lower bounds.
Debug.Assert(low <= hi);
Debug.Assert(hi - low >= 0, "Length overflow!");
return low + ((hi - low) >> 1);
}
public long GetLongLength(int dimension)
{
// This method should throw an IndexOufOfRangeException for compat if dimension < 0 or >= Rank
return GetLength(dimension);
}
// Number of elements in the Array.
int ICollection.Count => Length;
// Returns an object appropriate for synchronizing access to this
// Array.
public object SyncRoot => this;
// Is this Array read-only?
public bool IsReadOnly => false;
public bool IsFixedSize => true;
// Is this Array synchronized (i.e., thread-safe)? If you want a synchronized
// collection, you can use SyncRoot as an object to synchronize your
// collection with. You could also call GetSynchronized()
// to get a synchronized wrapper around the Array.
public bool IsSynchronized => false;
object? IList.this[int index]
{
get => GetValue(index);
set => SetValue(value, index);
}
int IList.Add(object? value)
{
ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
return default;
}
bool IList.Contains(object? value)
{
return Array.IndexOf(this, value) >= this.GetLowerBound(0);
}
void IList.Clear()
{
Array.Clear(this, this.GetLowerBound(0), this.Length);
}
int IList.IndexOf(object? value)
{
return Array.IndexOf(this, value);
}
void IList.Insert(int index, object? value)
{
ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
}
void IList.Remove(object? value)
{
ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
}
void IList.RemoveAt(int index)
{
ThrowHelper.ThrowNotSupportedException(ExceptionResource.NotSupported_FixedSizeCollection);
}
// Make a new array which is a shallow copy of the original array.
//
public object Clone()
{
return MemberwiseClone();
}
int IStructuralComparable.CompareTo(object? other, IComparer comparer)
{
if (other == null)
{
return 1;
}
Array? o = other as Array;
if (o == null || this.Length != o.Length)
{
ThrowHelper.ThrowArgumentException(ExceptionResource.ArgumentException_OtherNotArrayOfCorrectLength, ExceptionArgument.other);
}
int i = 0;
int c = 0;
while (i < o.Length && c == 0)
{
object? left = GetValue(i);
object? right = o.GetValue(i);
c = comparer.Compare(left, right);
i++;
}
return c;
}
bool IStructuralEquatable.Equals(object? other, IEqualityComparer comparer)
{
if (other == null)
{
return false;
}
if (object.ReferenceEquals(this, other))
{
return true;
}
if (!(other is Array o) || o.Length != this.Length)
{
return false;
}
int i = 0;
while (i < o.Length)
{
object? left = GetValue(i);
object? right = o.GetValue(i);
if (!comparer.Equals(left, right))
{
return false;
}
i++;
}
return true;
}
int IStructuralEquatable.GetHashCode(IEqualityComparer comparer)
{
if (comparer == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparer);
int ret = 0;
for (int i = (this.Length >= 8 ? this.Length - 8 : 0); i < this.Length; i++)
{
ret = HashCode.Combine(ret, comparer.GetHashCode(GetValue(i)!));
}
return ret;
}
// Searches an array for a given element using a binary search algorithm.
// Elements of the array are compared to the search value using the
// IComparable interface, which must be implemented by all elements
// of the array and the given search value. This method assumes that the
// array is already sorted according to the IComparable interface;
// if this is not the case, the result will be incorrect.
//
// The method returns the index of the given value in the array. If the
// array does not contain the given value, the method returns a negative
// integer. The bitwise complement operator (~) can be applied to a
// negative result to produce the index of the first element (if any) that
// is larger than the given search value.
//
public static int BinarySearch(Array array, object? value)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
return BinarySearch(array, array.GetLowerBound(0), array.Length, value, null);
}
// Searches a section of an array for a given element using a binary search
// algorithm. Elements of the array are compared to the search value using
// the IComparable interface, which must be implemented by all
// elements of the array and the given search value. This method assumes
// that the array is already sorted according to the IComparable
// interface; if this is not the case, the result will be incorrect.
//
// The method returns the index of the given value in the array. If the
// array does not contain the given value, the method returns a negative
// integer. The bitwise complement operator (~) can be applied to a
// negative result to produce the index of the first element (if any) that
// is larger than the given search value.
//
public static int BinarySearch(Array array, int index, int length, object? value)
{
return BinarySearch(array, index, length, value, null);
}
// Searches an array for a given element using a binary search algorithm.
// Elements of the array are compared to the search value using the given
// IComparer interface. If comparer is null, elements of the
// array are compared to the search value using the IComparable
// interface, which in that case must be implemented by all elements of the
// array and the given search value. This method assumes that the array is
// already sorted; if this is not the case, the result will be incorrect.
//
// The method returns the index of the given value in the array. If the
// array does not contain the given value, the method returns a negative
// integer. The bitwise complement operator (~) can be applied to a
// negative result to produce the index of the first element (if any) that
// is larger than the given search value.
//
public static int BinarySearch(Array array, object? value, IComparer? comparer)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
return BinarySearch(array, array.GetLowerBound(0), array.Length, value, comparer);
}
// Searches a section of an array for a given element using a binary search
// algorithm. Elements of the array are compared to the search value using
// the given IComparer interface. If comparer is null,
// elements of the array are compared to the search value using the
// IComparable interface, which in that case must be implemented by
// all elements of the array and the given search value. This method
// assumes that the array is already sorted; if this is not the case, the
// result will be incorrect.
//
// The method returns the index of the given value in the array. If the
// array does not contain the given value, the method returns a negative
// integer. The bitwise complement operator (~) can be applied to a
// negative result to produce the index of the first element (if any) that
// is larger than the given search value.
//
public static int BinarySearch(Array array, int index, int length, object? value, IComparer? comparer)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
int lb = array.GetLowerBound(0);
if (index < lb)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (length < 0)
ThrowHelper.ThrowLengthArgumentOutOfRange_ArgumentOutOfRange_NeedNonNegNum();
if (array.Length - (index - lb) < length)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
if (array.Rank != 1)
ThrowHelper.ThrowRankException(ExceptionResource.Rank_MultiDimNotSupported);
comparer ??= Comparer.Default;
int lo = index;
int hi = index + length - 1;
if (array is object[] objArray)
{
while (lo <= hi)
{
// i might overflow if lo and hi are both large positive numbers.
int i = GetMedian(lo, hi);
int c;
try
{
c = comparer.Compare(objArray[i], value);
}
catch (Exception e)
{
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
return default;
}
if (c == 0) return i;
if (c < 0)
{
lo = i + 1;
}
else
{
hi = i - 1;
}
}
return ~lo;
}
if (comparer == Comparer.Default)
{
CorElementType et = array.GetCorElementTypeOfElementType();
if (et.IsPrimitiveType()
// IntPtr/UIntPtr does not implement IComparable
&& (et != CorElementType.ELEMENT_TYPE_I) && (et != CorElementType.ELEMENT_TYPE_U))
{
if (value == null)
return ~index;
if (array.IsValueOfElementType(value))
{
int adjustedIndex = index - lb;
int result = -1;
switch (et)
{
case CorElementType.ELEMENT_TYPE_I1:
result = GenericBinarySearch<sbyte>(array, adjustedIndex, length, value);
break;
case CorElementType.ELEMENT_TYPE_U1:
case CorElementType.ELEMENT_TYPE_BOOLEAN:
result = GenericBinarySearch<byte>(array, adjustedIndex, length, value);
break;
case CorElementType.ELEMENT_TYPE_I2:
result = GenericBinarySearch<short>(array, adjustedIndex, length, value);
break;
case CorElementType.ELEMENT_TYPE_U2:
case CorElementType.ELEMENT_TYPE_CHAR:
result = GenericBinarySearch<ushort>(array, adjustedIndex, length, value);
break;
case CorElementType.ELEMENT_TYPE_I4:
result = GenericBinarySearch<int>(array, adjustedIndex, length, value);
break;
case CorElementType.ELEMENT_TYPE_U4:
result = GenericBinarySearch<uint>(array, adjustedIndex, length, value);
break;
case CorElementType.ELEMENT_TYPE_I8:
result = GenericBinarySearch<long>(array, adjustedIndex, length, value);
break;
case CorElementType.ELEMENT_TYPE_U8:
result = GenericBinarySearch<ulong>(array, adjustedIndex, length, value);
break;
case CorElementType.ELEMENT_TYPE_R4:
result = GenericBinarySearch<float>(array, adjustedIndex, length, value);
break;
case CorElementType.ELEMENT_TYPE_R8:
result = GenericBinarySearch<double>(array, adjustedIndex, length, value);
break;
default:
Debug.Fail("All primitive types should be handled above");
break;
}
return (result >= 0) ? (index + result) : ~(index + ~result);
static int GenericBinarySearch<T>(Array array, int adjustedIndex, int length, object value) where T: struct, IComparable<T>
=> UnsafeArrayAsSpan<T>(array, adjustedIndex, length).BinarySearch(Unsafe.As<byte, T>(ref value.GetRawData()));
}
}
}
while (lo <= hi)
{
int i = GetMedian(lo, hi);
int c;
try
{
c = comparer.Compare(array.GetValue(i), value);
}
catch (Exception e)
{
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
return default;
}
if (c == 0) return i;
if (c < 0)
{
lo = i + 1;
}
else
{
hi = i - 1;
}
}
return ~lo;
}
public static int BinarySearch<T>(T[] array, T value)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
return BinarySearch<T>(array, 0, array.Length, value, null);
}
public static int BinarySearch<T>(T[] array, T value, System.Collections.Generic.IComparer<T>? comparer)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
return BinarySearch<T>(array, 0, array.Length, value, comparer);
}
public static int BinarySearch<T>(T[] array, int index, int length, T value)
{
return BinarySearch<T>(array, index, length, value, null);
}
public static int BinarySearch<T>(T[] array, int index, int length, T value, System.Collections.Generic.IComparer<T>? comparer)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
if (index < 0)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (length < 0)
ThrowHelper.ThrowLengthArgumentOutOfRange_ArgumentOutOfRange_NeedNonNegNum();
if (array.Length - index < length)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
return ArraySortHelper<T>.Default.BinarySearch(array, index, length, value, comparer);
}
public static TOutput[] ConvertAll<TInput, TOutput>(TInput[] array, Converter<TInput, TOutput> converter)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (converter == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.converter);
}
TOutput[] newArray = new TOutput[array.Length];
for (int i = 0; i < array.Length; i++)
{
newArray[i] = converter(array[i]);
}
return newArray;
}
// CopyTo copies a collection into an Array, starting at a particular
// index into the array.
//
// This method is to support the ICollection interface, and calls
// Array.Copy internally. If you aren't using ICollection explicitly,
// call Array.Copy to avoid an extra indirection.
//
public void CopyTo(Array array, int index)
{
if (array != null && array.Rank != 1)
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported);
// Note: Array.Copy throws a RankException and we want a consistent ArgumentException for all the IList CopyTo methods.
Array.Copy(this, GetLowerBound(0), array!, index, Length);
}
public void CopyTo(Array array, long index)
{
int iindex = (int)index;
if (index != iindex)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_HugeArrayNotSupported);
this.CopyTo(array, iindex);
}
private static class EmptyArray<T>
{
#pragma warning disable CA1825 // this is the implementation of Array.Empty<T>()
internal static readonly T[] Value = new T[0];
#pragma warning restore CA1825
}
public static T[] Empty<T>()
{
return EmptyArray<T>.Value;
}
public static bool Exists<T>(T[] array, Predicate<T> match)
{
return Array.FindIndex(array, match) != -1;
}
public static void Fill<T>(T[] array, T value)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
for (int i = 0; i < array.Length; i++)
{
array[i] = value;
}
}
public static void Fill<T>(T[] array, T value, int startIndex, int count)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (startIndex < 0 || startIndex > array.Length)
{
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
}
if (count < 0 || startIndex > array.Length - count)
{
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
}
for (int i = startIndex; i < startIndex + count; i++)
{
array[i] = value;
}
}
[return: MaybeNull]
public static T Find<T>(T[] array, Predicate<T> match)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
for (int i = 0; i < array.Length; i++)
{
if (match(array[i]))
{
return array[i];
}
}
return default!;
}
public static T[] FindAll<T>(T[] array, Predicate<T> match)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
List<T> list = new List<T>();
for (int i = 0; i < array.Length; i++)
{
if (match(array[i]))
{
list.Add(array[i]);
}
}
return list.ToArray();
}
public static int FindIndex<T>(T[] array, Predicate<T> match)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
return FindIndex(array, 0, array.Length, match);
}
public static int FindIndex<T>(T[] array, int startIndex, Predicate<T> match)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
return FindIndex(array, startIndex, array.Length - startIndex, match);
}
public static int FindIndex<T>(T[] array, int startIndex, int count, Predicate<T> match)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (startIndex < 0 || startIndex > array.Length)
{
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
}
if (count < 0 || startIndex > array.Length - count)
{
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
}
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
int endIndex = startIndex + count;
for (int i = startIndex; i < endIndex; i++)
{
if (match(array[i]))
return i;
}
return -1;
}
[return: MaybeNull]
public static T FindLast<T>(T[] array, Predicate<T> match)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
for (int i = array.Length - 1; i >= 0; i--)
{
if (match(array[i]))
{
return array[i];
}
}
return default!;
}
public static int FindLastIndex<T>(T[] array, Predicate<T> match)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
return FindLastIndex(array, array.Length - 1, array.Length, match);
}
public static int FindLastIndex<T>(T[] array, int startIndex, Predicate<T> match)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
return FindLastIndex(array, startIndex, startIndex + 1, match);
}
public static int FindLastIndex<T>(T[] array, int startIndex, int count, Predicate<T> match)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
if (array.Length == 0)
{
// Special case for 0 length List
if (startIndex != -1)
{
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
}
}
else
{
// Make sure we're not out of range
if (startIndex < 0 || startIndex >= array.Length)
{
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)
{
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
}
int endIndex = startIndex - count;
for (int i = startIndex; i > endIndex; i--)
{
if (match(array[i]))
{
return i;
}
}
return -1;
}
public static void ForEach<T>(T[] array, Action<T> action)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (action == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.action);
}
for (int i = 0; i < array.Length; i++)
{
action(array[i]);
}
}
// Returns the index of the first occurrence of a given value in an array.
// The array is searched forwards, and the elements of the array are
// compared to the given value using the Object.Equals method.
//
public static int IndexOf(Array array, object? value)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
return IndexOf(array, value, array.GetLowerBound(0), array.Length);
}
// Returns the index of the first occurrence of a given value in a range of
// an array. The array is searched forwards, starting at index
// startIndex and ending at the last element of the array. The
// elements of the array are compared to the given value using the
// Object.Equals method.
//
public static int IndexOf(Array array, object? value, int startIndex)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
int lb = array.GetLowerBound(0);
return IndexOf(array, value, startIndex, array.Length - startIndex + lb);
}
// Returns the index of the first occurrence of a given value in a range of
// an array. The array is searched forwards, starting at index
// startIndex and upto count elements. The
// elements of the array are compared to the given value using the
// Object.Equals method.
//
public static int IndexOf(Array array, object? value, int startIndex, int count)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
if (array.Rank != 1)
ThrowHelper.ThrowRankException(ExceptionResource.Rank_MultiDimNotSupported);
int lb = array.GetLowerBound(0);
if (startIndex < lb || startIndex > array.Length + lb)
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
if (count < 0 || count > array.Length - startIndex + lb)
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
int endIndex = startIndex + count;
if (array is object[] objArray)
{
if (value == null)
{
for (int i = startIndex; i < endIndex; i++)
{
if (objArray[i] == null)
return i;
}
}
else
{
for (int i = startIndex; i < endIndex; i++)
{
object obj = objArray[i];
if (obj != null && obj.Equals(value))
return i;
}
}
return -1;
}
CorElementType et = array.GetCorElementTypeOfElementType();
if (et.IsPrimitiveType())
{
if (value == null)
return lb - 1;
if (array.IsValueOfElementType(value))
{
int adjustedIndex = startIndex - lb;
int result = -1;
switch (et)
{
case CorElementType.ELEMENT_TYPE_I1:
case CorElementType.ELEMENT_TYPE_U1:
case CorElementType.ELEMENT_TYPE_BOOLEAN:
result = GenericIndexOf<byte>(array, value, adjustedIndex, count);
break;
case CorElementType.ELEMENT_TYPE_I2:
case CorElementType.ELEMENT_TYPE_U2:
case CorElementType.ELEMENT_TYPE_CHAR:
result = GenericIndexOf<char>(array, value, adjustedIndex, count);
break;
case CorElementType.ELEMENT_TYPE_I4:
case CorElementType.ELEMENT_TYPE_U4:
#if !BIT64
case CorElementType.ELEMENT_TYPE_I:
case CorElementType.ELEMENT_TYPE_U:
#endif
result = GenericIndexOf<int>(array, value, adjustedIndex, count);
break;
case CorElementType.ELEMENT_TYPE_I8:
case CorElementType.ELEMENT_TYPE_U8:
#if BIT64
case CorElementType.ELEMENT_TYPE_I:
case CorElementType.ELEMENT_TYPE_U:
#endif
result = GenericIndexOf<long>(array, value, adjustedIndex, count);
break;
case CorElementType.ELEMENT_TYPE_R4:
result = GenericIndexOf<float>(array, value, adjustedIndex, count);
break;
case CorElementType.ELEMENT_TYPE_R8:
result = GenericIndexOf<double>(array, value, adjustedIndex, count);
break;
default:
Debug.Fail("All primitive types should be handled above");
break;
}
return (result >= 0 ? startIndex : lb) + result;
static int GenericIndexOf<T>(Array array, object value, int adjustedIndex, int length) where T : struct, IEquatable<T>
=> UnsafeArrayAsSpan<T>(array, adjustedIndex, length).IndexOf(Unsafe.As<byte, T>(ref value.GetRawData()));
}
}
for (int i = startIndex; i < endIndex; i++)
{
object? obj = array.GetValue(i);
if (obj == null)
{
if (value == null)
return i;
}
else
{
if (obj.Equals(value))
return i;
}
}
// Return one less than the lower bound of the array. This way,
// for arrays with a lower bound of -1 we will not return -1 when the
// item was not found. And for SZArrays (the vast majority), -1 still
// works for them.
return lb - 1;
}
public static int IndexOf<T>(T[] array, T value)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
return IndexOf(array, value, 0, array.Length);
}
public static int IndexOf<T>(T[] array, T value, int startIndex)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
return IndexOf(array, value, startIndex, array.Length - startIndex);
}
public static int IndexOf<T>(T[] array, T value, int startIndex, int count)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if ((uint)startIndex > (uint)array.Length)
{
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
}
if ((uint)count > (uint)(array.Length - startIndex))
{
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
}
if (RuntimeHelpers.IsBitwiseEquatable<T>())
{
if (Unsafe.SizeOf<T>() == sizeof(byte))
{
int result = SpanHelpers.IndexOf(
ref Unsafe.Add(ref array.GetRawSzArrayData(), startIndex),
Unsafe.As<T, byte>(ref value),
count);
return (result >= 0 ? startIndex : 0) + result;
}
else if (Unsafe.SizeOf<T>() == sizeof(char))
{
int result = SpanHelpers.IndexOf(
ref Unsafe.Add(ref Unsafe.As<byte, char>(ref array.GetRawSzArrayData()), startIndex),
Unsafe.As<T, char>(ref value),
count);
return (result >= 0 ? startIndex : 0) + result;
}
else if (Unsafe.SizeOf<T>() == sizeof(int))
{
int result = SpanHelpers.IndexOf(
ref Unsafe.Add(ref Unsafe.As<byte, int>(ref array.GetRawSzArrayData()), startIndex),
Unsafe.As<T, int>(ref value),
count);
return (result >= 0 ? startIndex : 0) + result;
}
else if (Unsafe.SizeOf<T>() == sizeof(long))
{
int result = SpanHelpers.IndexOf(
ref Unsafe.Add(ref Unsafe.As<byte, long>(ref array.GetRawSzArrayData()), startIndex),
Unsafe.As<T, long>(ref value),
count);
return (result >= 0 ? startIndex : 0) + result;
}
}
#if !CORERT
return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count);
#else
return IndexOfImpl(array, value, startIndex, count);
#endif
}
// Returns the index of the last occurrence of a given value in an array.
// The array is searched backwards, and the elements of the array are
// compared to the given value using the Object.Equals method.
//
public static int LastIndexOf(Array array, object? value)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
int lb = array.GetLowerBound(0);
return LastIndexOf(array, value, array.Length - 1 + lb, array.Length);
}
// Returns the index of the last occurrence of a given value in a range of
// an array. The array is searched backwards, starting at index
// startIndex and ending at index 0. The elements of the array are
// compared to the given value using the Object.Equals method.
//
public static int LastIndexOf(Array array, object? value, int startIndex)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
int lb = array.GetLowerBound(0);
return LastIndexOf(array, value, startIndex, startIndex + 1 - lb);
}
// Returns the index of the last occurrence of a given value in a range of
// an array. The array is searched backwards, starting at index
// startIndex and counting uptocount elements. The elements of
// the array are compared to the given value using the Object.Equals
// method.
//
public static int LastIndexOf(Array array, object? value, int startIndex, int count)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
int lb = array.GetLowerBound(0);
if (array.Length == 0)
{
return lb - 1;
}
if (startIndex < lb || startIndex >= array.Length + lb)
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
if (count < 0)
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
if (count > startIndex - lb + 1)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.endIndex, ExceptionResource.ArgumentOutOfRange_EndIndexStartIndex);
if (array.Rank != 1)
ThrowHelper.ThrowRankException(ExceptionResource.Rank_MultiDimNotSupported);
int endIndex = startIndex - count + 1;
if (array is object[] objArray)
{
if (value == null)
{
for (int i = startIndex; i >= endIndex; i--)
{
if (objArray[i] == null)
return i;
}
}
else
{
for (int i = startIndex; i >= endIndex; i--)
{
object obj = objArray[i];
if (obj != null && obj.Equals(value))
return i;
}
}
return -1;
}
CorElementType et = array.GetCorElementTypeOfElementType();
if (et.IsPrimitiveType())
{
if (value == null)
return lb - 1;
if (array.IsValueOfElementType(value))
{
int adjustedIndex = endIndex - lb;
int result = -1;
switch (et)
{
case CorElementType.ELEMENT_TYPE_I1:
case CorElementType.ELEMENT_TYPE_U1:
case CorElementType.ELEMENT_TYPE_BOOLEAN:
result = GenericLastIndexOf<byte>(array, value, adjustedIndex, count);
break;
case CorElementType.ELEMENT_TYPE_I2:
case CorElementType.ELEMENT_TYPE_U2:
case CorElementType.ELEMENT_TYPE_CHAR:
result = GenericLastIndexOf<char>(array, value, adjustedIndex, count);
break;
case CorElementType.ELEMENT_TYPE_I4:
case CorElementType.ELEMENT_TYPE_U4:
#if !BIT64
case CorElementType.ELEMENT_TYPE_I:
case CorElementType.ELEMENT_TYPE_U:
#endif
result = GenericLastIndexOf<int>(array, value, adjustedIndex, count);
break;
case CorElementType.ELEMENT_TYPE_I8:
case CorElementType.ELEMENT_TYPE_U8:
#if BIT64
case CorElementType.ELEMENT_TYPE_I:
case CorElementType.ELEMENT_TYPE_U:
#endif
result = GenericLastIndexOf<long>(array, value, adjustedIndex, count);
break;
case CorElementType.ELEMENT_TYPE_R4:
result = GenericLastIndexOf<float>(array, value, adjustedIndex, count);
break;
case CorElementType.ELEMENT_TYPE_R8:
result = GenericLastIndexOf<double>(array, value, adjustedIndex, count);
break;
default:
Debug.Fail("All primitive types should be handled above");
break;
}
return (result >= 0 ? endIndex : lb) + result;
static int GenericLastIndexOf<T>(Array array, object value, int adjustedIndex, int length) where T : struct, IEquatable<T>
=> UnsafeArrayAsSpan<T>(array, adjustedIndex, length).LastIndexOf(Unsafe.As<byte, T>(ref value.GetRawData()));
}
}
for (int i = startIndex; i >= endIndex; i--)
{
object? obj = array.GetValue(i);
if (obj == null)
{
if (value == null)
return i;
}
else
{
if (obj.Equals(value))
return i;
}
}
return lb - 1; // Return lb-1 for arrays with negative lower bounds.
}
public static int LastIndexOf<T>(T[] array, T value)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
return LastIndexOf(array, value, array.Length - 1, array.Length);
}
public static int LastIndexOf<T>(T[] array, T value, int startIndex)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
// if array is empty and startIndex is 0, we need to pass 0 as count
return LastIndexOf(array, value, startIndex, (array.Length == 0) ? 0 : (startIndex + 1));
}
public static int LastIndexOf<T>(T[] array, T value, int startIndex, int count)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (array.Length == 0)
{
//
// Special case for 0 length List
// accept -1 and 0 as valid startIndex for compablility reason.
//
if (startIndex != -1 && startIndex != 0)
{
ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_Index();
}
// only 0 is a valid value for count if array is empty
if (count != 0)
{
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
}
return -1;
}
// Make sure we're not out of range
if ((uint)startIndex >= (uint)array.Length)
{
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)
{
ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count();
}
if (RuntimeHelpers.IsBitwiseEquatable<T>())
{
if (Unsafe.SizeOf<T>() == sizeof(byte))
{
int endIndex = startIndex - count + 1;
int result = SpanHelpers.LastIndexOf(
ref Unsafe.Add(ref array.GetRawSzArrayData(), endIndex),
Unsafe.As<T, byte>(ref value),
count);
return (result >= 0 ? endIndex : 0) + result;
}
else if (Unsafe.SizeOf<T>() == sizeof(char))
{
int endIndex = startIndex - count + 1;
int result = SpanHelpers.LastIndexOf(
ref Unsafe.Add(ref Unsafe.As<byte, char>(ref array.GetRawSzArrayData()), endIndex),
Unsafe.As<T, char>(ref value),
count);
return (result >= 0 ? endIndex : 0) + result;
}
else if (Unsafe.SizeOf<T>() == sizeof(int))
{
int endIndex = startIndex - count + 1;
int result = SpanHelpers.LastIndexOf(
ref Unsafe.Add(ref Unsafe.As<byte, int>(ref array.GetRawSzArrayData()), endIndex),
Unsafe.As<T, int>(ref value),
count);
return (result >= 0 ? endIndex : 0) + result;
}
else if (Unsafe.SizeOf<T>() == sizeof(long))
{
int endIndex = startIndex - count + 1;
int result = SpanHelpers.LastIndexOf(
ref Unsafe.Add(ref Unsafe.As<byte, long>(ref array.GetRawSzArrayData()), endIndex),
Unsafe.As<T, long>(ref value),
count);
return (result >= 0 ? endIndex : 0) + result;
}
}
#if !CORERT
return EqualityComparer<T>.Default.LastIndexOf(array, value, startIndex, count);
#else
return LastIndexOfImpl(array, value, startIndex, count);
#endif
}
// Reverses all elements of the given array. Following a call to this
// method, an element previously located at index i will now be
// located at index length - i - 1, where length is the
// length of the array.
//
public static void Reverse(Array array)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
Reverse(array, array.GetLowerBound(0), array.Length);
}
// Reverses the elements in a range of an array. 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).
// Reliability note: This may fail because it may have to box objects.
//
public static void Reverse(Array array, int index, int length)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
int lowerBound = array.GetLowerBound(0);
if (index < lowerBound)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (length < 0)
ThrowHelper.ThrowLengthArgumentOutOfRange_ArgumentOutOfRange_NeedNonNegNum();
if (array.Length - (index - lowerBound) < length)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
if (array.Rank != 1)
ThrowHelper.ThrowRankException(ExceptionResource.Rank_MultiDimNotSupported);
if (length <= 1)
return;
int adjustedIndex = index - lowerBound;
switch (array.GetCorElementTypeOfElementType())
{
case CorElementType.ELEMENT_TYPE_I1:
case CorElementType.ELEMENT_TYPE_U1:
case CorElementType.ELEMENT_TYPE_BOOLEAN:
UnsafeArrayAsSpan<byte>(array, adjustedIndex, length).Reverse();
return;
case CorElementType.ELEMENT_TYPE_I2:
case CorElementType.ELEMENT_TYPE_U2:
case CorElementType.ELEMENT_TYPE_CHAR:
UnsafeArrayAsSpan<short>(array, adjustedIndex, length).Reverse();
return;
case CorElementType.ELEMENT_TYPE_I4:
case CorElementType.ELEMENT_TYPE_U4:
#if !BIT64
case CorElementType.ELEMENT_TYPE_I:
case CorElementType.ELEMENT_TYPE_U:
#endif
case CorElementType.ELEMENT_TYPE_R4:
UnsafeArrayAsSpan<int>(array, adjustedIndex, length).Reverse();
return;
case CorElementType.ELEMENT_TYPE_I8:
case CorElementType.ELEMENT_TYPE_U8:
#if BIT64
case CorElementType.ELEMENT_TYPE_I:
case CorElementType.ELEMENT_TYPE_U:
#endif
case CorElementType.ELEMENT_TYPE_R8:
UnsafeArrayAsSpan<long>(array, adjustedIndex, length).Reverse();
return;
case CorElementType.ELEMENT_TYPE_OBJECT:
case CorElementType.ELEMENT_TYPE_ARRAY:
case CorElementType.ELEMENT_TYPE_SZARRAY:
UnsafeArrayAsSpan<object>(array, adjustedIndex, length).Reverse();
return;
}
int i = index;
int j = index + length - 1;
while (i < j)
{
object? temp = array.GetValue(i);
array.SetValue(array.GetValue(j), i);
array.SetValue(temp, j);
i++;
j--;
}
}
public static void Reverse<T>(T[] array)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
Reverse(array, 0, array.Length);
}
public static void Reverse<T>(T[] array, int index, int length)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
if (index < 0)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (length < 0)
ThrowHelper.ThrowLengthArgumentOutOfRange_ArgumentOutOfRange_NeedNonNegNum();
if (array.Length - index < length)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
if (length <= 1)
return;
ref T first = ref Unsafe.Add(ref Unsafe.As<byte, T>(ref array.GetRawSzArrayData()), index);
ref T last = ref Unsafe.Add(ref Unsafe.Add(ref first, length), -1);
do
{
T temp = first;
first = last;
last = temp;
first = ref Unsafe.Add(ref first, 1);
last = ref Unsafe.Add(ref last, -1);
} while (Unsafe.IsAddressLessThan(ref first, ref last));
}
// Sorts the elements of an array. The sort compares the elements to each
// other using the IComparable interface, which must be implemented
// by all elements of the array.
//
public static void Sort(Array array)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
Sort(array, null, array.GetLowerBound(0), array.Length, null);
}
// Sorts the elements of two arrays based on the keys in the first array.
// Elements in the keys array specify the sort keys for
// corresponding elements in the items array. The sort compares the
// keys to each other using the IComparable interface, which must be
// implemented by all elements of the keys array.
//
public static void Sort(Array keys, Array? items)
{
if (keys == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
Sort(keys, items, keys.GetLowerBound(0), keys.Length, null);
}
// Sorts the elements in a section of an array. The sort compares the
// elements to each other using the IComparable interface, which
// must be implemented by all elements in the given section of the array.
//
public static void Sort(Array array, int index, int length)
{
Sort(array, null, index, length, null);
}
// Sorts the elements in a section of two arrays based on the keys in the
// first array. Elements in the keys array specify the sort keys for
// corresponding elements in the items array. The sort compares the
// keys to each other using the IComparable interface, which must be
// implemented by all elements of the keys array.
//
public static void Sort(Array keys, Array? items, int index, int length)
{
Sort(keys, items, index, length, null);
}
// Sorts the elements of an array. The sort compares the elements to each
// other using the given IComparer interface. If comparer is
// null, the elements are compared to each other using the
// IComparable interface, which in that case must be implemented by
// all elements of the array.
//
public static void Sort(Array array, IComparer? comparer)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
Sort(array, null, array.GetLowerBound(0), array.Length, comparer);
}
// Sorts the elements of two arrays based on the keys in the first array.
// Elements in the keys array specify the sort keys for
// corresponding elements in the items array. The sort compares the
// keys to each other using the given IComparer interface. If
// comparer is null, the elements are compared to each other using
// the IComparable interface, which in that case must be implemented
// by all elements of the keys array.
//
public static void Sort(Array keys, Array? items, IComparer? comparer)
{
if (keys == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
Sort(keys, items, keys.GetLowerBound(0), keys.Length, comparer);
}
// Sorts the elements in a section of an array. The sort compares the
// elements to each other using the given IComparer interface. If
// comparer is null, the elements are compared to each other using
// the IComparable interface, which in that case must be implemented
// by all elements in the given section of the array.
//
public static void Sort(Array array, int index, int length, IComparer? comparer)
{
Sort(array, null, index, length, comparer);
}
// Sorts the elements in a section of two arrays based on the keys in the
// first array. Elements in the keys array specify the sort keys for
// corresponding elements in the items array. The sort compares the
// keys to each other using the given IComparer interface. If
// comparer is null, the elements are compared to each other using
// the IComparable interface, which in that case must be implemented
// by all elements of the given section of the keys array.
//
public static void Sort(Array keys, Array? items, int index, int length, IComparer? comparer)
{
if (keys == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
if (keys.Rank != 1 || (items != null && items.Rank != 1))
ThrowHelper.ThrowRankException(ExceptionResource.Rank_MultiDimNotSupported);
int keysLowerBound = keys.GetLowerBound(0);
if (items != null && keysLowerBound != items.GetLowerBound(0))
ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_LowerBoundsMustMatch);
if (index < keysLowerBound)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (length < 0)
ThrowHelper.ThrowLengthArgumentOutOfRange_ArgumentOutOfRange_NeedNonNegNum();
if (keys.Length - (index - keysLowerBound) < length || (items != null && (index - keysLowerBound) > items.Length - length))
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
if (length <= 1)
return;
comparer ??= Comparer.Default;
if (keys is object[] objKeys)
{
object[]? objItems = items as object[];
if (items == null || objItems != null)
{
new SorterObjectArray(objKeys, objItems, comparer).Sort(index, length);
return;
}
}
if (comparer == Comparer.Default)
{
CorElementType et = keys.GetCorElementTypeOfElementType();
if (items == null || items.GetCorElementTypeOfElementType() == et)
{
int adjustedIndex = index - keysLowerBound;
switch (et)
{
case CorElementType.ELEMENT_TYPE_I1:
GenericSort<sbyte>(keys, items, adjustedIndex, length);
return;
case CorElementType.ELEMENT_TYPE_U1:
case CorElementType.ELEMENT_TYPE_BOOLEAN:
GenericSort<byte>(keys, items, adjustedIndex, length);
return;
case CorElementType.ELEMENT_TYPE_I2:
GenericSort<short>(keys, items, adjustedIndex, length);
return;
case CorElementType.ELEMENT_TYPE_U2:
case CorElementType.ELEMENT_TYPE_CHAR:
GenericSort<ushort>(keys, items, adjustedIndex, length);
return;
case CorElementType.ELEMENT_TYPE_I4:
GenericSort<int>(keys, items, adjustedIndex, length);
return;
case CorElementType.ELEMENT_TYPE_U4:
GenericSort<uint>(keys, items, adjustedIndex, length);
return;
case CorElementType.ELEMENT_TYPE_I8:
GenericSort<long>(keys, items, adjustedIndex, length);
return;
case CorElementType.ELEMENT_TYPE_U8:
GenericSort<ulong>(keys, items, adjustedIndex, length);
return;
case CorElementType.ELEMENT_TYPE_R4:
GenericSort<float>(keys, items, adjustedIndex, length);
return;
case CorElementType.ELEMENT_TYPE_R8:
GenericSort<double>(keys, items, adjustedIndex, length);
return;
case CorElementType.ELEMENT_TYPE_I:
case CorElementType.ELEMENT_TYPE_U:
// IntPtr/UIntPtr does not implement IComparable
break;
}
static void GenericSort<T>(Array keys, Array? items, int adjustedIndex, int length) where T: struct
{
Span<T> keysSpan = UnsafeArrayAsSpan<T>(keys, adjustedIndex, length);
if (items != null)
{
keysSpan.Sort<T, T>(UnsafeArrayAsSpan<T>(items, adjustedIndex, length));
}
else
{
keysSpan.Sort<T>();
}
}
}
}
new SorterGenericArray(keys, items, comparer).Sort(index, length);
}
public static void Sort<T>(T[] array)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
if (array.Length > 1)
{
var span = new Span<T>(ref Unsafe.As<byte, T>(ref array.GetRawSzArrayData()), array.Length);
ArraySortHelper<T>.Default.Sort(span, null);
}
}
public static void Sort<TKey, TValue>(TKey[] keys, TValue[]? items)
{
if (keys == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
Sort<TKey, TValue>(keys, items, 0, keys.Length, null);
}
public static void Sort<T>(T[] array, int index, int length)
{
Sort<T>(array, index, length, null);
}
public static void Sort<TKey, TValue>(TKey[] keys, TValue[]? items, int index, int length)
{
Sort<TKey, TValue>(keys, items, index, length, null);
}
public static void Sort<T>(T[] array, System.Collections.Generic.IComparer<T>? comparer)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
Sort<T>(array, 0, array.Length, comparer);
}
public static void Sort<TKey, TValue>(TKey[] keys, TValue[]? items, System.Collections.Generic.IComparer<TKey>? comparer)
{
if (keys == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
Sort<TKey, TValue>(keys, items, 0, keys.Length, comparer);
}
public static void Sort<T>(T[] array, int index, int length, System.Collections.Generic.IComparer<T>? comparer)
{
if (array == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
if (index < 0)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (length < 0)
ThrowHelper.ThrowLengthArgumentOutOfRange_ArgumentOutOfRange_NeedNonNegNum();
if (array.Length - index < length)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
if (length > 1)
{
var span = new Span<T>(ref Unsafe.Add(ref Unsafe.As<byte, T>(ref array.GetRawSzArrayData()), index), length);
ArraySortHelper<T>.Default.Sort(span, comparer);
}
}
public static void Sort<TKey, TValue>(TKey[] keys, TValue[]? items, int index, int length, System.Collections.Generic.IComparer<TKey>? comparer)
{
if (keys == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys);
if (index < 0)
ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
if (length < 0)
ThrowHelper.ThrowLengthArgumentOutOfRange_ArgumentOutOfRange_NeedNonNegNum();
if (keys.Length - index < length || (items != null && index > items.Length - length))
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
if (length > 1)
{
if (items == null)
{
Sort<TKey>(keys, index, length, comparer);
return;
}
var spanKeys = new Span<TKey>(ref Unsafe.Add(ref Unsafe.As<byte, TKey>(ref keys.GetRawSzArrayData()), index), length);
var spanItems = new Span<TValue>(ref Unsafe.Add(ref Unsafe.As<byte, TValue>(ref items.GetRawSzArrayData()), index), length);
ArraySortHelper<TKey, TValue>.Default.Sort(spanKeys, spanItems, comparer);
}
}
public static void Sort<T>(T[] array, Comparison<T> comparison)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (comparison == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.comparison);
}
var span = new Span<T>(ref Unsafe.As<byte, T>(ref array.GetRawSzArrayData()), array.Length);
ArraySortHelper<T>.Sort(span, comparison);
}
public static bool TrueForAll<T>(T[] array, Predicate<T> match)
{
if (array == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);
}
if (match == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
for (int i = 0; i < array.Length; i++)
{
if (!match(array[i]))
{
return false;
}
}
return true;
}
// Private value type used by the Sort methods.
private readonly struct SorterObjectArray
{
private readonly object[] keys;
private readonly object?[]? items;
private readonly IComparer comparer;
internal SorterObjectArray(object[] keys, object?[]? items, IComparer comparer)
{
this.keys = keys;
this.items = items;
this.comparer = comparer;
}
internal void SwapIfGreater(int a, int b)
{
if (a != b)
{
if (comparer.Compare(keys[a], keys[b]) > 0)
{
object temp = keys[a];
keys[a] = keys[b];
keys[b] = temp;
if (items != null)
{
object? item = items[a];
items[a] = items[b];
items[b] = item;
}
}
}
}
private void Swap(int i, int j)
{
object t = keys[i];
keys[i] = keys[j];
keys[j] = t;
if (items != null)
{
object? item = items[i];
items[i] = items[j];
items[j] = item;
}
}
internal void Sort(int left, int length)
{
IntrospectiveSort(left, length);
}
private void IntrospectiveSort(int left, int length)
{
if (length < 2)
return;
try
{
IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(length));
}
catch (IndexOutOfRangeException)
{
IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
}
catch (Exception e)
{
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
}
}
private void IntroSort(int lo, int hi, int depthLimit)
{
while (hi > lo)
{
int partitionSize = hi - lo + 1;
if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
{
if (partitionSize == 1)
{
return;
}
if (partitionSize == 2)
{
SwapIfGreater(lo, hi);
return;
}
if (partitionSize == 3)
{
SwapIfGreater(lo, hi - 1);
SwapIfGreater(lo, hi);
SwapIfGreater(hi - 1, hi);
return;
}
InsertionSort(lo, hi);
return;
}
if (depthLimit == 0)
{
Heapsort(lo, hi);
return;
}
depthLimit--;
int p = PickPivotAndPartition(lo, hi);
IntroSort(p + 1, hi, depthLimit);
hi = p - 1;
}
}
private int PickPivotAndPartition(int lo, int hi)
{
// Compute median-of-three. But also partition them, since we've done the comparison.
int mid = lo + (hi - lo) / 2;
// Sort lo, mid and hi appropriately, then pick mid as the pivot.
SwapIfGreater(lo, mid);
SwapIfGreater(lo, hi);
SwapIfGreater(mid, hi);
object pivot = keys[mid];
Swap(mid, hi - 1);
int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
while (left < right)
{
while (comparer.Compare(keys[++left], pivot) < 0) ;
while (comparer.Compare(pivot, keys[--right]) < 0) ;
if (left >= right)
break;
Swap(left, right);
}
// Put pivot in the right location.
Swap(left, hi - 1);
return left;
}
private void Heapsort(int lo, int hi)
{
int n = hi - lo + 1;
for (int i = n / 2; i >= 1; i--)
{
DownHeap(i, n, lo);
}
for (int i = n; i > 1; i--)
{
Swap(lo, lo + i - 1);
DownHeap(1, i - 1, lo);
}
}
private void DownHeap(int i, int n, int lo)
{
object d = keys[lo + i - 1];
object? dt = items?[lo + i - 1];
int child;
while (i <= n / 2)
{
child = 2 * i;
if (child < n && comparer.Compare(keys[lo + child - 1], keys[lo + child]) < 0)
{
child++;
}
if (!(comparer.Compare(d, keys[lo + child - 1]) < 0))
break;
keys[lo + i - 1] = keys[lo + child - 1];
if (items != null)
items[lo + i - 1] = items[lo + child - 1];
i = child;
}
keys[lo + i - 1] = d;
if (items != null)
items[lo + i - 1] = dt;
}
private void InsertionSort(int lo, int hi)
{
int i, j;
object t;
object? ti;
for (i = lo; i < hi; i++)
{
j = i;
t = keys[i + 1];
ti = items?[i + 1];
while (j >= lo && comparer.Compare(t, keys[j]) < 0)
{
keys[j + 1] = keys[j];
if (items != null)
items[j + 1] = items[j];
j--;
}
keys[j + 1] = t;
if (items != null)
items[j + 1] = ti;
}
}
}
// Private value used by the Sort methods for instances of Array.
// This is slower than the one for Object[], since we can't use the JIT helpers
// to access the elements. We must use GetValue & SetValue.
private readonly struct SorterGenericArray
{
private readonly Array keys;
private readonly Array? items;
private readonly IComparer comparer;
internal SorterGenericArray(Array keys, Array? items, IComparer comparer)
{
this.keys = keys;
this.items = items;
this.comparer = comparer;
}
internal void SwapIfGreater(int a, int b)
{
if (a != b)
{
if (comparer.Compare(keys.GetValue(a), keys.GetValue(b)) > 0)
{
object? key = keys.GetValue(a);
keys.SetValue(keys.GetValue(b), a);
keys.SetValue(key, b);
if (items != null)
{
object? item = items.GetValue(a);
items.SetValue(items.GetValue(b), a);
items.SetValue(item, b);
}
}
}
}
private void Swap(int i, int j)
{
object? t1 = keys.GetValue(i);
keys.SetValue(keys.GetValue(j), i);
keys.SetValue(t1, j);
if (items != null)
{
object? t2 = items.GetValue(i);
items.SetValue(items.GetValue(j), i);
items.SetValue(t2, j);
}
}
internal void Sort(int left, int length)
{
IntrospectiveSort(left, length);
}
private void IntrospectiveSort(int left, int length)
{
if (length < 2)
return;
try
{
IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2PlusOne(length));
}
catch (IndexOutOfRangeException)
{
IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(comparer);
}
catch (Exception e)
{
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
}
}
private void IntroSort(int lo, int hi, int depthLimit)
{
while (hi > lo)
{
int partitionSize = hi - lo + 1;
if (partitionSize <= IntrospectiveSortUtilities.IntrosortSizeThreshold)
{
if (partitionSize == 1)
{
return;
}
if (partitionSize == 2)
{
SwapIfGreater(lo, hi);
return;
}
if (partitionSize == 3)
{
SwapIfGreater(lo, hi - 1);
SwapIfGreater(lo, hi);
SwapIfGreater(hi - 1, hi);
return;
}
InsertionSort(lo, hi);
return;
}
if (depthLimit == 0)
{
Heapsort(lo, hi);
return;
}
depthLimit--;
int p = PickPivotAndPartition(lo, hi);
IntroSort(p + 1, hi, depthLimit);
hi = p - 1;
}
}
private int PickPivotAndPartition(int lo, int hi)
{
// Compute median-of-three. But also partition them, since we've done the comparison.
int mid = lo + (hi - lo) / 2;
SwapIfGreater(lo, mid);
SwapIfGreater(lo, hi);
SwapIfGreater(mid, hi);
object? pivot = keys.GetValue(mid);
Swap(mid, hi - 1);
int left = lo, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below.
while (left < right)
{
while (comparer.Compare(keys.GetValue(++left), pivot) < 0) ;
while (comparer.Compare(pivot, keys.GetValue(--right)) < 0) ;
if (left >= right)
break;
Swap(left, right);
}
// Put pivot in the right location.
Swap(left, hi - 1);
return left;
}
private void Heapsort(int lo, int hi)
{
int n = hi - lo + 1;
for (int i = n / 2; i >= 1; i--)
{
DownHeap(i, n, lo);
}
for (int i = n; i > 1; i--)
{
Swap(lo, lo + i - 1);
DownHeap(1, i - 1, lo);
}
}
private void DownHeap(int i, int n, int lo)
{
object? d = keys.GetValue(lo + i - 1);
object? dt = items?.GetValue(lo + i - 1);
int child;
while (i <= n / 2)
{
child = 2 * i;
if (child < n && comparer.Compare(keys.GetValue(lo + child - 1), keys.GetValue(lo + child)) < 0)
{
child++;
}
if (!(comparer.Compare(d, keys.GetValue(lo + child - 1)) < 0))
break;
keys.SetValue(keys.GetValue(lo + child - 1), lo + i - 1);
if (items != null)
items.SetValue(items.GetValue(lo + child - 1), lo + i - 1);
i = child;
}
keys.SetValue(d, lo + i - 1);
if (items != null)
items.SetValue(dt, lo + i - 1);
}
private void InsertionSort(int lo, int hi)
{
int i, j;
object? t;
object? dt;
for (i = lo; i < hi; i++)
{
j = i;
t = keys.GetValue(i + 1);
dt = items?.GetValue(i + 1);
while (j >= lo && comparer.Compare(t, keys.GetValue(j)) < 0)
{
keys.SetValue(keys.GetValue(j), j + 1);
if (items != null)
items.SetValue(items.GetValue(j), j + 1);
j--;
}
keys.SetValue(t, j + 1);
if (items != null)
items.SetValue(dt, j + 1);
}
}
}
private static Span<T> UnsafeArrayAsSpan<T>(Array array, int adjustedIndex, int length) =>
new Span<T>(ref Unsafe.As<byte, T>(ref array.GetRawArrayData()), array.Length).Slice(adjustedIndex, length);
#if !CORERT
public IEnumerator GetEnumerator()
{
int lowerBound = GetLowerBound(0);
if (Rank == 1 && lowerBound == 0)
return new SZArrayEnumerator(this);
else
return new ArrayEnumerator(this, lowerBound, Length);
}
#endif // !CORERT
}
}