// Licensed to the .NET Foundation under one or more agreements. // The .NET Foundation licenses this file to you under the MIT license. using System.Collections; using System.Collections.Generic; using System.Collections.ObjectModel; using System.Diagnostics; using System.Diagnostics.CodeAnalysis; using System.Numerics; using System.Reflection; using System.Runtime; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using Internal.Runtime; namespace System { [Serializable] [TypeForwardedFrom("mscorlib, Version=4.0.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089")] public abstract partial class Array : ICloneable, IList, IStructuralComparable, IStructuralEquatable { // This is the threshold where Introspective sort switches to Insertion sort. // Empirically, 16 seems to speed up most cases without slowing down others, at least for integers. // Large value types may benefit from a smaller number. internal const int IntrosortSizeThreshold = 16; // 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); } return array.Length == 0 ? ReadOnlyCollection<T>.Empty : 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; // local copy if (larray == null) { array = new T[newSize]; return; } if (larray.Length != newSize) { // Due to array variance, it's possible that the incoming array is // actually of type U[], where U:T; or that an int[] <-> uint[] or // similar cast has occurred. In any case, since it's always legal // to reinterpret U as T in this scenario (but not necessarily the // other way around), we can use SpanHelpers.Memmove here. T[] newArray = new T[newSize]; Buffer.Memmove( ref MemoryMarshal.GetArrayDataReference(newArray), ref MemoryMarshal.GetArrayDataReference(larray), (uint)Math.Min(newSize, larray.Length)); array = newArray; } Debug.Assert(array != null); } [RequiresDynamicCode("The code for an array of the specified type might not be available.")] public static unsafe Array CreateInstance(Type elementType, int length) { ArgumentNullException.ThrowIfNull(elementType); ArgumentOutOfRangeException.ThrowIfNegative(length); RuntimeType? t = elementType.UnderlyingSystemType as RuntimeType; if (t == null) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.elementType); return InternalCreate(t, 1, &length, null); } [UnconditionalSuppressMessage("AotAnalysis", "IL3050:RequiresDynamicCode", Justification = "MDArrays of Rank != 1 can be created because they don't implement generic interfaces.")] public static unsafe Array CreateInstance(Type elementType, int length1, int length2) { ArgumentNullException.ThrowIfNull(elementType); ArgumentOutOfRangeException.ThrowIfNegative(length1); ArgumentOutOfRangeException.ThrowIfNegative(length2); RuntimeType? t = elementType.UnderlyingSystemType as RuntimeType; if (t == null) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.elementType); int* pLengths = stackalloc int[] { length1, length2 }; return InternalCreate(t, 2, pLengths, null); } [UnconditionalSuppressMessage("AotAnalysis", "IL3050:RequiresDynamicCode", Justification = "MDArrays of Rank != 1 can be created because they don't implement generic interfaces.")] public static unsafe Array CreateInstance(Type elementType, int length1, int length2, int length3) { ArgumentNullException.ThrowIfNull(elementType); ArgumentOutOfRangeException.ThrowIfNegative(length1); ArgumentOutOfRangeException.ThrowIfNegative(length2); ArgumentOutOfRangeException.ThrowIfNegative(length3); RuntimeType? t = elementType.UnderlyingSystemType as RuntimeType; if (t == null) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.elementType); int* pLengths = stackalloc int[] { length1, length2, length3 }; return InternalCreate(t, 3, pLengths, null); } [RequiresDynamicCode("The code for an array of the specified type might not be available.")] public static unsafe Array CreateInstance(Type elementType, params int[] lengths) { ArgumentNullException.ThrowIfNull(elementType); ArgumentNullException.ThrowIfNull(lengths); if (lengths.Length == 0) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NeedAtLeast1Rank); RuntimeType? t = elementType.UnderlyingSystemType as RuntimeType; if (t == null) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.elementType); // Check to make sure the lengths are all non-negative. Note that we check this here to give // a good exception message if they are not; however we check this again inside the execution // engine's low level allocation function after having made a copy of the array to prevent a // malicious caller from mutating the array after this check. for (int i = 0; i < lengths.Length; i++) if (lengths[i] < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.lengths, i, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); fixed (int* pLengths = &lengths[0]) return InternalCreate(t, lengths.Length, pLengths, null); } [RequiresDynamicCode("The code for an array of the specified type might not be available.")] public static unsafe Array CreateInstance(Type elementType, int[] lengths, int[] lowerBounds) { ArgumentNullException.ThrowIfNull(elementType); ArgumentNullException.ThrowIfNull(lengths); ArgumentNullException.ThrowIfNull(lowerBounds); if (lengths.Length != lowerBounds.Length) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RanksAndBounds); if (lengths.Length == 0) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NeedAtLeast1Rank); RuntimeType? t = elementType.UnderlyingSystemType as RuntimeType; if (t == null) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.elementType); // Check to make sure the lengths are all non-negative. Note that we check this here to give // a good exception message if they are not; however we check this again inside the execution // engine's low level allocation function after having made a copy of the array to prevent a // malicious caller from mutating the array after this check. for (int i = 0; i < lengths.Length; i++) if (lengths[i] < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.lengths, i, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); fixed (int* pLengths = &lengths[0]) fixed (int* pLowerBounds = &lowerBounds[0]) return InternalCreate(t, lengths.Length, pLengths, pLowerBounds); } [RequiresDynamicCode("The code for an array of the specified type might not be available.")] public static Array CreateInstance(Type elementType, params long[] lengths) { ArgumentNullException.ThrowIfNull(lengths); 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 CreateInstance(elementType, intLengths); } /// <summary> /// Creates a one-dimensional <see cref="Array"/> of the specified array type and length, with zero-based indexing. /// </summary> /// <param name="arrayType">The type of the array (not of the array element type).</param> /// <param name="length">The size of the <see cref="Array"/> to create.</param> /// <returns>A new one-dimensional <see cref="Array"/> of the specified <see cref="Type"/> with the specified length.</returns> /// <exception cref="ArgumentNullException"><paramref name="arrayType"/> is null.</exception> /// <exception cref="ArgumentOutOfRangeException"><paramref name="length"/> is negative.</exception> /// <exception cref="ArgumentException"><para><paramref name="arrayType"/> is not an array type.</para> /// <para>-or-</para> /// <para><paramref name="arrayType"/> is not one-dimensional array.</para> /// </exception> /// <remarks>When the array type is readily available, this method should be preferred over <see cref="CreateInstance(Type, int)"/>, as it has /// better performance and it is AOT-friendly.</remarks> public static unsafe Array CreateInstanceFromArrayType(Type arrayType, int length) { ArgumentNullException.ThrowIfNull(arrayType); ArgumentOutOfRangeException.ThrowIfNegative(length); RuntimeType? t = arrayType as RuntimeType; if (t == null) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.arrayType); if (!t.IsArray) ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_HasToBeArrayClass, ExceptionArgument.arrayType); if (t.GetArrayRank() != 1) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankMultiDimNotSupported, ExceptionArgument.arrayType); return InternalCreateFromArrayType(t, 1, &length, null); } /// <summary> /// Creates a multidimensional <see cref="Array"/> of the specified <see cref="Type"/> and dimension lengths, with zero-based indexing. /// </summary> /// <param name="arrayType">The type of the array (not of the array element type).</param> /// <param name="lengths">The dimension lengths, specified in an array of 32-bit integers.</param> /// <returns>A new multidimensional <see cref="Array"/> of the specified Type with the specified length for each dimension, using zero-based indexing.</returns> /// <exception cref="ArgumentNullException"><para><paramref name="arrayType"/> is null.</para> /// <para>-or-</para> /// <para><paramref name="lengths"/> is null.</para> /// </exception> /// <exception cref="ArgumentOutOfRangeException">Any value in <paramref name="lengths"/> is less than zero.</exception> /// <exception cref="ArgumentException"><para>The lengths array is empty.</para> /// <para>-or-</para> /// <para><paramref name="arrayType"/> is not an array type.</para> /// <para>-or-</para> /// <para><paramref name="arrayType"/> rank does not match <paramref name="lengths"/> length.</para> /// </exception> /// <remarks>When the array type is readily available, this method should be preferred over <see cref="CreateInstance(Type, int[])"/>, as it has /// better performance and it is AOT-friendly.</remarks> public static unsafe Array CreateInstanceFromArrayType(Type arrayType, params int[] lengths) { ArgumentNullException.ThrowIfNull(arrayType); ArgumentNullException.ThrowIfNull(lengths); RuntimeType? t = arrayType as RuntimeType; if (t == null) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.arrayType); if (!t.IsArray) ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_HasToBeArrayClass, ExceptionArgument.arrayType); if (t.GetArrayRank() != lengths.Length) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankIndices); // Check to make sure the lengths are all non-negative. Note that we check this here to give // a good exception message if they are not; however we check this again inside the execution // engine's low level allocation function after having made a copy of the array to prevent a // malicious caller from mutating the array after this check. for (int i = 0; i < lengths.Length; i++) if (lengths[i] < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.lengths, i, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); fixed (int* pLengths = &lengths[0]) return InternalCreateFromArrayType(t, lengths.Length, pLengths, null); } /// <summary> /// Creates a multidimensional <see cref="Array"/> of the specified <see cref="Type"/> and dimension lengths, with the specified lower bounds. /// </summary> /// <param name="arrayType">The type of the array (not of the array element type).</param> /// <param name="lengths">The dimension lengths, specified in an array of 32-bit integers.</param> /// <param name="lowerBounds">A one-dimensional array that contains the lower bound (starting index) of each dimension of the <see cref="Array"/> to create.</param> /// <returns>A new multidimensional <see cref="Array"/> of the specified <see cref="Type"/> with the specified length and lower bound for each dimension.</returns> /// <exception cref="ArgumentNullException"><para><paramref name="arrayType"/> is null.</para> /// <para>-or-</para> /// <para><paramref name="lengths"/> is null.</para> /// <para>-or-</para> /// <para><paramref name="lowerBounds"/> is null.</para> /// </exception> /// <exception cref="ArgumentException"><para>The <paramref name="lengths"/> and <paramref name="lowerBounds"/> arrays do not contain the same number of elements.</para> /// <para>-or-</para> /// <para>The lengths array is empty.</para> /// <para>-or-</para> /// <para><paramref name="arrayType"/> is not an array type.</para> /// <para>-or-</para> /// <para><paramref name="arrayType"/> rank does not match <paramref name="lengths"/> length.</para> /// </exception> /// <exception cref="ArgumentOutOfRangeException">Any value in <paramref name="lengths"/> is less than zero.</exception> /// <exception cref="PlatformNotSupportedException">Native AOT: any value in <paramref name="lowerBounds"/> is different than zero.</exception> /// <remarks>When the array type is readily available, this method should be preferred over <see cref="CreateInstance(Type, int[], int[])"/>, as it has /// better performance and it is AOT-friendly.</remarks> public static unsafe Array CreateInstanceFromArrayType(Type arrayType, int[] lengths, int[] lowerBounds) { ArgumentNullException.ThrowIfNull(arrayType); ArgumentNullException.ThrowIfNull(lengths); ArgumentNullException.ThrowIfNull(lowerBounds); if (lengths.Length != lowerBounds.Length) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RanksAndBounds); RuntimeType? t = arrayType as RuntimeType; if (t == null) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_MustBeType, ExceptionArgument.arrayType); if (!t.IsArray) ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_HasToBeArrayClass, ExceptionArgument.arrayType); if (t.GetArrayRank() != lengths.Length) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankIndices); if (lowerBounds[0] != 0 && t.IsSZArray) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_NonZeroLowerBound); // Check to make sure the lengths are all non-negative. Note that we check this here to give // a good exception message if they are not; however we check this again inside the execution // engine's low level allocation function after having made a copy of the array to prevent a // malicious caller from mutating the array after this check. for (int i = 0; i < lengths.Length; i++) if (lengths[i] < 0) ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.lengths, i, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum); fixed (int* pLengths = &lengths[0]) fixed (int* pLowerBounds = &lowerBounds[0]) return InternalCreateFromArrayType(t, lengths.Length, pLengths, pLowerBounds); } 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); } #if !MONO // implementation details of MethodTable // Provides a strong exception guarantee - either it succeeds, or // it throws an exception with no side effects. The arrays must be // compatible array types based on the array element type - this // method does not support casting, boxing, or primitive widening. // It will up-cast, assuming the array types are correct. public static void ConstrainedCopy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length) { Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length, reliable: true); } // Copies length elements from sourceArray, starting at index 0, to // destinationArray, starting at index 0. public static unsafe void Copy(Array sourceArray, Array destinationArray, int length) { if (sourceArray != null && destinationArray != null) { MethodTable* pMT = RuntimeHelpers.GetMethodTable(sourceArray); if (MethodTable.AreSameType(pMT, RuntimeHelpers.GetMethodTable(destinationArray)) && pMT->IsSzArray && (uint)length <= sourceArray.NativeLength && (uint)length <= destinationArray.NativeLength) { nuint byteCount = (uint)length * (nuint)pMT->ComponentSize; ref byte src = ref Unsafe.As<RawArrayData>(sourceArray).Data; ref byte dst = ref Unsafe.As<RawArrayData>(destinationArray).Data; if (pMT->ContainsGCPointers) Buffer.BulkMoveWithWriteBarrier(ref dst, ref src, byteCount); else SpanHelpers.Memmove(ref dst, ref src, byteCount); // GC.KeepAlive(sourceArray) not required. pMT kept alive via sourceArray return; } } // Less common CopyImpl(sourceArray, sourceArray?.GetLowerBound(0) ?? 0, destinationArray, destinationArray?.GetLowerBound(0) ?? 0, length, reliable: false); } // Copies length elements from sourceArray, starting at sourceIndex, to // destinationArray, starting at destinationIndex. public static void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length) { Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length, reliable: false); } private static unsafe void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, bool reliable) { if (sourceArray != null && destinationArray != null) { MethodTable* pMT = RuntimeHelpers.GetMethodTable(sourceArray); if (MethodTable.AreSameType(pMT, RuntimeHelpers.GetMethodTable(destinationArray)) && pMT->IsSzArray && length >= 0 && sourceIndex >= 0 && destinationIndex >= 0 && (uint)(sourceIndex + length) <= sourceArray.NativeLength && (uint)(destinationIndex + length) <= destinationArray.NativeLength) { nuint elementSize = (nuint)pMT->ComponentSize; nuint byteCount = (uint)length * elementSize; ref byte src = ref Unsafe.AddByteOffset(ref Unsafe.As<RawArrayData>(sourceArray).Data, (uint)sourceIndex * elementSize); ref byte dst = ref Unsafe.AddByteOffset(ref Unsafe.As<RawArrayData>(destinationArray).Data, (uint)destinationIndex * elementSize); if (pMT->ContainsGCPointers) Buffer.BulkMoveWithWriteBarrier(ref dst, ref src, byteCount); else SpanHelpers.Memmove(ref dst, ref src, byteCount); // GC.KeepAlive(sourceArray) not required. pMT kept alive via sourceArray return; } } // Less common CopyImpl(sourceArray, sourceIndex, destinationArray, destinationIndex, length, reliable); } // Reliability-wise, this method will either possibly corrupt your // instance, or if the reliable flag is true, it will either always // succeed or always throw an exception with no side effects. private static unsafe void CopyImpl(Array? sourceArray, int sourceIndex, Array? destinationArray, int destinationIndex, int length, bool reliable) { ArgumentNullException.ThrowIfNull(sourceArray); ArgumentNullException.ThrowIfNull(destinationArray); if (sourceArray.GetType() != destinationArray.GetType() && sourceArray.Rank != destinationArray.Rank) throw new RankException(SR.Rank_MustMatch); ArgumentOutOfRangeException.ThrowIfNegative(length); int srcLB = sourceArray.GetLowerBound(0); ArgumentOutOfRangeException.ThrowIfLessThan(sourceIndex, srcLB); sourceIndex -= srcLB; if ((sourceIndex < 0) || ((uint)(sourceIndex + length) > sourceArray.NativeLength)) throw new ArgumentException(SR.Arg_LongerThanSrcArray, nameof(sourceArray)); int dstLB = destinationArray.GetLowerBound(0); ArgumentOutOfRangeException.ThrowIfLessThan(destinationIndex, dstLB); destinationIndex -= dstLB; if ((destinationIndex < 0) || ((uint)(destinationIndex + length) > destinationArray.NativeLength)) throw new ArgumentException(SR.Arg_LongerThanDestArray, nameof(destinationArray)); ArrayAssignType assignType; if (sourceArray.GetType() == destinationArray.GetType() || (assignType = CanAssignArrayType(sourceArray, destinationArray)) == ArrayAssignType.SimpleCopy) { MethodTable* pMT = RuntimeHelpers.GetMethodTable(sourceArray); nuint elementSize = (nuint)pMT->ComponentSize; nuint byteCount = (uint)length * elementSize; ref byte src = ref Unsafe.AddByteOffset(ref MemoryMarshal.GetArrayDataReference(sourceArray), (uint)sourceIndex * elementSize); ref byte dst = ref Unsafe.AddByteOffset(ref MemoryMarshal.GetArrayDataReference(destinationArray), (uint)destinationIndex * elementSize); if (pMT->ContainsGCPointers) Buffer.BulkMoveWithWriteBarrier(ref dst, ref src, byteCount); else SpanHelpers.Memmove(ref dst, ref src, byteCount); // GC.KeepAlive(sourceArray) not required. pMT kept alive via sourceArray return; } // If we were called from Array.ConstrainedCopy, ensure that the array copy // is guaranteed to succeed. if (reliable) throw new ArrayTypeMismatchException(SR.ArrayTypeMismatch_ConstrainedCopy); // Rare CopySlow(sourceArray, sourceIndex, destinationArray, destinationIndex, length, assignType); } private static void CopySlow(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, ArrayAssignType assignType) { Debug.Assert(sourceArray.Rank == destinationArray.Rank); if (assignType == ArrayAssignType.WrongType) throw new ArrayTypeMismatchException(SR.ArrayTypeMismatch_CantAssignType); if (length > 0) { switch (assignType) { case ArrayAssignType.UnboxValueClass: CopyImplUnBoxEachElement(sourceArray, sourceIndex, destinationArray, destinationIndex, length); break; case ArrayAssignType.BoxValueClassOrPrimitive: CopyImplBoxEachElement(sourceArray, sourceIndex, destinationArray, destinationIndex, length); break; case ArrayAssignType.MustCast: CopyImplCastCheckEachElement(sourceArray, sourceIndex, destinationArray, destinationIndex, length); break; case ArrayAssignType.PrimitiveWiden: CopyImplPrimitiveWiden(sourceArray, sourceIndex, destinationArray, destinationIndex, length); break; default: Debug.Fail("Fell through switch in Array.Copy!"); break; } } } private enum ArrayAssignType { SimpleCopy, WrongType, MustCast, BoxValueClassOrPrimitive, UnboxValueClass, PrimitiveWiden, } // Array.CopyImpl case: Object[] or interface array to value-type array copy. private static unsafe void CopyImplUnBoxEachElement(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length) { MethodTable* pDestArrayMT = RuntimeHelpers.GetMethodTable(destinationArray); MethodTable* pDestMT = destinationArray.ElementMethodTable; Debug.Assert(!sourceArray.ElementMethodTable->IsValueType); Debug.Assert(pDestMT->IsValueType); nuint destSize = pDestArrayMT->ComponentSize; ref object? srcData = ref Unsafe.Add(ref Unsafe.As<byte, object?>(ref MemoryMarshal.GetArrayDataReference(sourceArray)), sourceIndex); ref byte destData = ref Unsafe.AddByteOffset(ref MemoryMarshal.GetArrayDataReference(destinationArray), (nuint)destinationIndex * destSize); for (int i = 0; i < length; i++) { object? obj = Unsafe.Add(ref srcData, i); // Now that we have retrieved the element, we are no longer subject to race // conditions from another array mutator. if (pDestMT->IsNullable) { #if NATIVEAOT RuntimeExports.RhUnboxNullable(ref destData, pDestMT, obj); #else CastHelpers.Unbox_Nullable(ref destData, pDestMT, obj); #endif } else if (obj is null || RuntimeHelpers.GetMethodTable(obj) != pDestMT) { throw new InvalidCastException(SR.InvalidCast_DownCastArrayElement); } else if (pDestMT->ContainsGCPointers) { Buffer.BulkMoveWithWriteBarrier(ref destData, ref obj.GetRawData(), destSize); } else { SpanHelpers.Memmove(ref destData, ref obj.GetRawData(), destSize); } destData = ref Unsafe.AddByteOffset(ref destData, destSize); } } // Array.CopyImpl case: Value-type array to Object[] or interface array copy. private static unsafe void CopyImplBoxEachElement(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length) { MethodTable* pSrcArrayMT = RuntimeHelpers.GetMethodTable(sourceArray); MethodTable* pSrcMT = sourceArray.ElementMethodTable; Debug.Assert(pSrcMT->IsValueType); Debug.Assert(!destinationArray.ElementMethodTable->IsValueType); nuint srcSize = pSrcArrayMT->ComponentSize; ref byte srcData = ref Unsafe.AddByteOffset(ref MemoryMarshal.GetArrayDataReference(sourceArray), (nuint)sourceIndex * srcSize); ref object? destData = ref Unsafe.Add(ref Unsafe.As<byte, object?>(ref MemoryMarshal.GetArrayDataReference(destinationArray)), destinationIndex); for (int i = 0; i < length; i++) { #if NATIVEAOT object? obj = RuntimeExports.RhBox(pSrcMT, ref srcData); #else object? obj = RuntimeHelpers.Box(pSrcMT, ref srcData); #endif Unsafe.Add(ref destData, i) = obj; srcData = ref Unsafe.AddByteOffset(ref srcData, srcSize); } } // Array.CopyImpl case: Casting copy from gc-ref array to gc-ref array. private static unsafe void CopyImplCastCheckEachElement(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length) { MethodTable* pDestMT = destinationArray.ElementMethodTable; Debug.Assert(!sourceArray.ElementMethodTable->IsValueType); Debug.Assert(!pDestMT->IsValueType); ref object? srcData = ref Unsafe.Add(ref Unsafe.As<byte, object?>(ref MemoryMarshal.GetArrayDataReference(sourceArray)), sourceIndex); ref object? destData = ref Unsafe.Add(ref Unsafe.As<byte, object?>(ref MemoryMarshal.GetArrayDataReference(destinationArray)), destinationIndex); for (int i = 0; i < length; i++) { object? obj = Unsafe.Add(ref srcData, i); // Now that we have grabbed obj, we are no longer subject to races from another // mutator thread. #if NATIVEAOT Unsafe.Add(ref destData, i) = TypeCast.CheckCastAny(pDestMT, obj); #else Unsafe.Add(ref destData, i) = CastHelpers.ChkCastAny(pDestMT, obj); #endif } } // Array.CopyImpl case: Primitive types that have a widening conversion private static unsafe void CopyImplPrimitiveWiden(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length) { Debug.Assert(sourceArray.ElementMethodTable->IsPrimitive); Debug.Assert(destinationArray.ElementMethodTable->IsPrimitive); // Get appropriate sizes, which requires method tables. #if NATIVEAOT EETypeElementType srcElType = sourceArray.ElementMethodTable->ElementType; EETypeElementType destElType = destinationArray.ElementMethodTable->ElementType; #else CorElementType srcElType = sourceArray.GetCorElementTypeOfElementType(); CorElementType destElType = destinationArray.GetCorElementTypeOfElementType(); #endif nuint srcElSize = RuntimeHelpers.GetMethodTable(sourceArray)->ComponentSize; nuint destElSize = RuntimeHelpers.GetMethodTable(destinationArray)->ComponentSize; ref byte srcData = ref Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(sourceArray), (nuint)sourceIndex * srcElSize); ref byte destData = ref Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(destinationArray), (nuint)destinationIndex * destElSize); for (int i = 0; i < length; i++) { InvokeUtils.PrimitiveWiden(ref srcData, ref destData, srcElType, destElType); srcData = ref Unsafe.AddByteOffset(ref srcData, srcElSize); destData = ref Unsafe.AddByteOffset(ref destData, destElSize); } } /// <summary> /// Clears the contents of an array. /// </summary> /// <param name="array">The array to clear.</param> /// <exception cref="ArgumentNullException"><paramref name="array"/> is null.</exception> public static unsafe void Clear(Array array) { if (array == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); MethodTable* pMT = RuntimeHelpers.GetMethodTable(array); nuint totalByteLength = pMT->ComponentSize * array.NativeLength; ref byte pStart = ref MemoryMarshal.GetArrayDataReference(array); if (!pMT->ContainsGCPointers) { SpanHelpers.ClearWithoutReferences(ref pStart, totalByteLength); } else { Debug.Assert(totalByteLength % (nuint)sizeof(IntPtr) == 0); SpanHelpers.ClearWithReferences(ref Unsafe.As<byte, IntPtr>(ref pStart), totalByteLength / (nuint)sizeof(IntPtr)); } // GC.KeepAlive(array) not required. pMT kept alive via `pStart` } // Sets length elements in array to 0 (or null for Object arrays), starting // at index. // public static unsafe void Clear(Array array, int index, int length) { if (array == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); ref byte p = ref Unsafe.As<RawArrayData>(array).Data; int lowerBound = 0; MethodTable* pMT = RuntimeHelpers.GetMethodTable(array); if (!pMT->IsSzArray) { int rank = pMT->MultiDimensionalArrayRank; lowerBound = Unsafe.Add(ref Unsafe.As<byte, int>(ref p), rank); p = ref Unsafe.Add(ref p, 2 * sizeof(int) * rank); // skip the bounds } int offset = index - lowerBound; if (index < lowerBound || offset < 0 || length < 0 || (uint)(offset + length) > array.NativeLength) ThrowHelper.ThrowIndexOutOfRangeException(); nuint elementSize = pMT->ComponentSize; ref byte ptr = ref Unsafe.AddByteOffset(ref p, (uint)offset * elementSize); nuint byteLength = (uint)length * elementSize; if (pMT->ContainsGCPointers) SpanHelpers.ClearWithReferences(ref Unsafe.As<byte, IntPtr>(ref ptr), byteLength / (uint)sizeof(IntPtr)); else SpanHelpers.ClearWithoutReferences(ref ptr, byteLength); // GC.KeepAlive(array) not required. pMT kept alive via `ptr` } private unsafe nint GetFlattenedIndex(int rawIndex) { // Checked by the caller Debug.Assert(Rank == 1); if (!RuntimeHelpers.GetMethodTable(this)->IsSzArray) { ref int bounds = ref this.GetMultiDimensionalArrayBounds(); rawIndex -= Unsafe.Add(ref bounds, 1); } if ((uint)rawIndex >= NativeLength) ThrowHelper.ThrowIndexOutOfRangeException(); return rawIndex; } internal unsafe nint GetFlattenedIndex(ReadOnlySpan<int> indices) { // Checked by the caller Debug.Assert(indices.Length == Rank); if (!RuntimeHelpers.GetMethodTable(this)->IsSzArray) { ref int bounds = ref this.GetMultiDimensionalArrayBounds(); nint flattenedIndex = 0; for (int i = 0; i < indices.Length; i++) { int index = indices[i] - Unsafe.Add(ref bounds, indices.Length + i); int length = Unsafe.Add(ref bounds, i); if ((uint)index >= (uint)length) ThrowHelper.ThrowIndexOutOfRangeException(); flattenedIndex = (length * flattenedIndex) + index; } Debug.Assert((nuint)flattenedIndex < NativeLength); return flattenedIndex; } else { int index = indices[0]; if ((uint)index >= NativeLength) ThrowHelper.ThrowIndexOutOfRangeException(); return index; } } [Intrinsic] public int GetLength(int dimension) { int rank = this.GetMultiDimensionalArrayRank(); if (rank == 0 && dimension == 0) return Length; if ((uint)dimension >= (uint)rank) throw new IndexOutOfRangeException(SR.IndexOutOfRange_ArrayRankIndex); return Unsafe.Add(ref this.GetMultiDimensionalArrayBounds(), dimension); } [Intrinsic] public int GetUpperBound(int dimension) { int rank = this.GetMultiDimensionalArrayRank(); if (rank == 0 && dimension == 0) return Length - 1; if ((uint)dimension >= (uint)rank) throw new IndexOutOfRangeException(SR.IndexOutOfRange_ArrayRankIndex); ref int bounds = ref this.GetMultiDimensionalArrayBounds(); return Unsafe.Add(ref bounds, dimension) + (SupportsNonZeroLowerBound ? Unsafe.Add(ref bounds, rank + dimension) : 0) - 1; } [Intrinsic] public int GetLowerBound(int dimension) { int rank = this.GetMultiDimensionalArrayRank(); if (rank == 0 && dimension == 0) return 0; if ((uint)dimension >= (uint)rank) throw new IndexOutOfRangeException(SR.IndexOutOfRange_ArrayRankIndex); if (SupportsNonZeroLowerBound) return Unsafe.Add(ref this.GetMultiDimensionalArrayBounds(), rank + dimension); else return 0; } #endif public object? GetValue(params int[] indices) { if (indices == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.indices); if (Rank != indices.Length) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankIndices); return InternalGetValue(GetFlattenedIndex(indices)); } public object? GetValue(int index) { if (Rank != 1) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need1DArray); return InternalGetValue(GetFlattenedIndex(index)); } public object? GetValue(int index1, int index2) { if (Rank != 2) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need2DArray); return InternalGetValue(GetFlattenedIndex([index1, index2])); } public object? GetValue(int index1, int index2, int index3) { if (Rank != 3) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need3DArray); return InternalGetValue(GetFlattenedIndex([index1, index2, index3])); } public void SetValue(object? value, int index) { if (Rank != 1) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need1DArray); InternalSetValue(value, GetFlattenedIndex(index)); } public void SetValue(object? value, int index1, int index2) { if (Rank != 2) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need2DArray); InternalSetValue(value, GetFlattenedIndex([index1, index2])); } public void SetValue(object? value, int index1, int index2, int index3) { if (Rank != 3) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_Need3DArray); InternalSetValue(value, GetFlattenedIndex([index1, index2, index3])); } public void SetValue(object? value, params int[] indices) { if (indices == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.indices); if (Rank != indices.Length) ThrowHelper.ThrowArgumentException(ExceptionResource.Arg_RankIndices); InternalSetValue(value, GetFlattenedIndex(indices)); } 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 IndexOf(this, value) >= this.GetLowerBound(0); } void IList.Clear() { Clear(this); } int IList.IndexOf(object? value) { return 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. // [Intrinsic] 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 (ReferenceEquals(this, other)) { return true; } if (other is not 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); HashCode hashCode = default; for (int i = (this.Length >= 8 ? this.Length - 8 : 0); i < this.Length; i++) { hashCode.Add(comparer.GetHashCode(GetValue(i)!)); } return hashCode.ToHashCode(); } // 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()) { 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_I: if (IntPtr.Size == 4) goto case CorElementType.ELEMENT_TYPE_I4; goto case CorElementType.ELEMENT_TYPE_I8; case CorElementType.ELEMENT_TYPE_U: if (IntPtr.Size == 4) goto case CorElementType.ELEMENT_TYPE_U4; goto case CorElementType.ELEMENT_TYPE_U8; 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(array, 0, array.Length, value, null); } public static int BinarySearch<T>(T[] array, T value, IComparer<T>? comparer) { if (array == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); return BinarySearch(array, 0, array.Length, value, comparer); } public static int BinarySearch<T>(T[] array, int index, int length, T value) { return BinarySearch(array, index, length, value, null); } public static int BinarySearch<T>(T[] array, int index, int length, T value, 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. 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, IDE0300 // this is the implementation of Array.Empty<T>() internal static readonly T[] Value = new T[0]; #pragma warning restore CA1825, IDE0300 } public static T[] Empty<T>() { return EmptyArray<T>.Value; } public static bool Exists<T>(T[] array, Predicate<T> match) { return FindIndex(array, match) != -1; } public static void Fill<T>(T[] array, T value) { if (array == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); } if (!typeof(T).IsValueType && array.GetType() != typeof(T[])) { for (int i = 0; i < array.Length; i++) { array[i] = value; } } else { new Span<T>(array).Fill(value); } } public static void Fill<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_IndexMustBeLessOrEqual(); } if ((uint)count > (uint)(array.Length - startIndex)) { ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count(); } if (!typeof(T).IsValueType && array.GetType() != typeof(T[])) { for (int i = startIndex; i < startIndex + count; i++) { array[i] = value; } } else { ref T first = ref Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(array), (nint)(uint)startIndex); new Span<T>(ref first, count).Fill(value); } } 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); } InlineArray4<T> stackAllocatedMatches = default; Span<T> span = stackAllocatedMatches; int foundCount = 0; T[]? values = null; foreach (T value in array) { if (match(value)) { if (foundCount >= span.Length) { values = new T[Math.Min((uint)span.Length * 2, (uint)array.Length)]; span.CopyTo(values); span = values; } span[foundCount++] = value; } } return values?.Length == foundCount ? values : span[..foundCount].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_IndexMustBeLessOrEqual(); } 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; } 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_IndexMustBeLess(); } } else { // Make sure we're not out of range if (startIndex < 0 || startIndex >= array.Length) { ThrowHelper.ThrowStartIndexArgumentOutOfRange_ArgumentOutOfRange_IndexMustBeLess(); } } // 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_IndexMustBeLessOrEqual(); 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: result = GenericIndexOf<int>(array, value, adjustedIndex, count); break; case CorElementType.ELEMENT_TYPE_I8: case CorElementType.ELEMENT_TYPE_U8: result = GenericIndexOf<long>(array, value, adjustedIndex, count); break; case CorElementType.ELEMENT_TYPE_I: case CorElementType.ELEMENT_TYPE_U: if (IntPtr.Size == 4) goto case CorElementType.ELEMENT_TYPE_I4; goto case CorElementType.ELEMENT_TYPE_I8; 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 unsafe 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_IndexMustBeLessOrEqual(); } if ((uint)count > (uint)(array.Length - startIndex)) { ThrowHelper.ThrowCountArgumentOutOfRange_ArgumentOutOfRange_Count(); } if (RuntimeHelpers.IsBitwiseEquatable<T>()) { if (sizeof(T) == sizeof(byte)) { int result = SpanHelpers.IndexOfValueType( ref Unsafe.Add(ref Unsafe.As<T, byte>(ref MemoryMarshal.GetArrayDataReference(array)), startIndex), Unsafe.BitCast<T, byte>(value), count); return (result >= 0 ? startIndex : 0) + result; } else if (sizeof(T) == sizeof(short)) { int result = SpanHelpers.IndexOfValueType( ref Unsafe.Add(ref Unsafe.As<T, short>(ref MemoryMarshal.GetArrayDataReference(array)), startIndex), Unsafe.BitCast<T, short>(value), count); return (result >= 0 ? startIndex : 0) + result; } else if (sizeof(T) == sizeof(int)) { int result = SpanHelpers.IndexOfValueType( ref Unsafe.Add(ref Unsafe.As<T, int>(ref MemoryMarshal.GetArrayDataReference(array)), startIndex), Unsafe.BitCast<T, int>(value), count); return (result >= 0 ? startIndex : 0) + result; } else if (sizeof(T) == sizeof(long)) { int result = SpanHelpers.IndexOfValueType( ref Unsafe.Add(ref Unsafe.As<T, long>(ref MemoryMarshal.GetArrayDataReference(array)), startIndex), Unsafe.BitCast<T, long>(value), count); return (result >= 0 ? startIndex : 0) + result; } } #if !NATIVEAOT 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_IndexMustBeLess(); 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: result = GenericLastIndexOf<int>(array, value, adjustedIndex, count); break; case CorElementType.ELEMENT_TYPE_I8: case CorElementType.ELEMENT_TYPE_U8: result = GenericLastIndexOf<long>(array, value, adjustedIndex, count); break; case CorElementType.ELEMENT_TYPE_I: case CorElementType.ELEMENT_TYPE_U: if (IntPtr.Size == 4) goto case CorElementType.ELEMENT_TYPE_I4; goto case CorElementType.ELEMENT_TYPE_I8; 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 unsafe 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_IndexMustBeLess(); } // 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_IndexMustBeLess(); } // 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 (sizeof(T) == sizeof(byte)) { int endIndex = startIndex - count + 1; int result = SpanHelpers.LastIndexOfValueType( ref Unsafe.Add(ref Unsafe.As<T, byte>(ref MemoryMarshal.GetArrayDataReference(array)), endIndex), Unsafe.BitCast<T, byte>(value), count); return (result >= 0 ? endIndex : 0) + result; } else if (sizeof(T) == sizeof(short)) { int endIndex = startIndex - count + 1; int result = SpanHelpers.LastIndexOfValueType( ref Unsafe.Add(ref Unsafe.As<T, short>(ref MemoryMarshal.GetArrayDataReference(array)), endIndex), Unsafe.BitCast<T, short>(value), count); return (result >= 0 ? endIndex : 0) + result; } else if (sizeof(T) == sizeof(int)) { int endIndex = startIndex - count + 1; int result = SpanHelpers.LastIndexOfValueType( ref Unsafe.Add(ref Unsafe.As<T, int>(ref MemoryMarshal.GetArrayDataReference(array)), endIndex), Unsafe.BitCast<T, int>(value), count); return (result >= 0 ? endIndex : 0) + result; } else if (sizeof(T) == sizeof(long)) { int endIndex = startIndex - count + 1; int result = SpanHelpers.LastIndexOfValueType( ref Unsafe.Add(ref Unsafe.As<T, long>(ref MemoryMarshal.GetArrayDataReference(array)), endIndex), Unsafe.BitCast<T, long>(value), count); return (result >= 0 ? endIndex : 0) + result; } } #if !NATIVEAOT 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: case CorElementType.ELEMENT_TYPE_R4: UnsafeArrayAsSpan<int>(array, adjustedIndex, length).Reverse(); return; case CorElementType.ELEMENT_TYPE_I8: case CorElementType.ELEMENT_TYPE_U8: case CorElementType.ELEMENT_TYPE_R8: UnsafeArrayAsSpan<long>(array, adjustedIndex, length).Reverse(); return; case CorElementType.ELEMENT_TYPE_I: case CorElementType.ELEMENT_TYPE_U: if (IntPtr.Size == 4) goto case CorElementType.ELEMENT_TYPE_I4; goto case CorElementType.ELEMENT_TYPE_I8; 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); if (array.Length > 1) SpanHelpers.Reverse(ref MemoryMarshal.GetArrayDataReference(array), (nuint)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; SpanHelpers.Reverse(ref Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(array), index), (nuint)length); } // 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_I: if (IntPtr.Size == 4) goto case CorElementType.ELEMENT_TYPE_I4; goto case CorElementType.ELEMENT_TYPE_I8; case CorElementType.ELEMENT_TYPE_U: if (IntPtr.Size == 4) goto case CorElementType.ELEMENT_TYPE_U4; goto case CorElementType.ELEMENT_TYPE_U8; case CorElementType.ELEMENT_TYPE_R4: GenericSort<float>(keys, items, adjustedIndex, length); return; case CorElementType.ELEMENT_TYPE_R8: GenericSort<double>(keys, items, adjustedIndex, length); return; } 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 MemoryMarshal.GetArrayDataReference(array), 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(keys, items, 0, keys.Length, null); } public static void Sort<T>(T[] array, int index, int length) { Sort(array, index, length, null); } public static void Sort<TKey, TValue>(TKey[] keys, TValue[]? items, int index, int length) { Sort(keys, items, index, length, null); } public static void Sort<T>(T[] array, IComparer<T>? comparer) { if (array == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); Sort(array, 0, array.Length, comparer); } public static void Sort<TKey, TValue>(TKey[] keys, TValue[]? items, IComparer<TKey>? comparer) { if (keys == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.keys); Sort(keys, items, 0, keys.Length, comparer); } public static void Sort<T>(T[] array, int index, int length, 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 MemoryMarshal.GetArrayDataReference(array), index), length); ArraySortHelper<T>.Default.Sort(span, comparer); } } public static void Sort<TKey, TValue>(TKey[] keys, TValue[]? items, int index, int length, 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(keys, index, length, comparer); return; } var spanKeys = new Span<TKey>(ref Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(keys), index), length); var spanItems = new Span<TValue>(ref Unsafe.Add(ref MemoryMarshal.GetArrayDataReference(items), 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 MemoryMarshal.GetArrayDataReference(array), 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; } /// <summary>Gets the maximum number of elements that may be contained in an array.</summary> /// <returns>The maximum count of elements allowed in any array.</returns> /// <remarks> /// <para>This property represents a runtime limitation, the maximum number of elements (not bytes) /// the runtime will allow in an array. There is no guarantee that an allocation under this length /// will succeed, but all attempts to allocate a larger array will fail.</para> /// <para>This property only applies to single-dimension, zero-bound (SZ) arrays. /// <see cref="Length"/> property may return larger value than this property for multi-dimensional arrays.</para> /// </remarks> public static int MaxLength => // Keep in sync with `inline SIZE_T MaxArrayLength()` from gchelpers and HashHelpers.MaxPrimeArrayLength. 0X7FFFFFC7; // 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 * (BitOperations.Log2((uint)length) + 1)); } catch (IndexOutOfRangeException) { ThrowHelper.ThrowArgumentException_BadComparer(comparer); } catch (Exception e) { ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e); } } // IntroSort is recursive; block it from being inlined into itself as // this is currenly not profitable. [MethodImpl(MethodImplOptions.NoInlining)] private void IntroSort(int lo, int hi, int depthLimit) { Debug.Assert(hi >= lo); Debug.Assert(depthLimit >= 0); while (hi > lo) { int partitionSize = hi - lo + 1; if (partitionSize <= IntrosortSizeThreshold) { Debug.Assert(partitionSize >= 2); 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) { Debug.Assert(hi - lo >= IntrosortSizeThreshold); // 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. if (left != hi - 1) { 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]; items?[lo + i - 1] = items[lo + child - 1]; i = child; } keys[lo + i - 1] = d; 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]; items?[j + 1] = items[j]; j--; } keys[j + 1] = t; 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 * (BitOperations.Log2((uint)length) + 1)); } catch (IndexOutOfRangeException) { ThrowHelper.ThrowArgumentException_BadComparer(comparer); } catch (Exception e) { ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e); } } // IntroSort is recursive; block it from being inlined into itself as // this is currenly not profitable. [MethodImpl(MethodImplOptions.NoInlining)] private void IntroSort(int lo, int hi, int depthLimit) { Debug.Assert(hi >= lo); Debug.Assert(depthLimit >= 0); while (hi > lo) { int partitionSize = hi - lo + 1; if (partitionSize <= IntrosortSizeThreshold) { Debug.Assert(partitionSize >= 2); 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) { Debug.Assert(hi - lo >= IntrosortSizeThreshold); // 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. if (left != hi - 1) { 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); items?.SetValue(items.GetValue(lo + child - 1), lo + i - 1); i = child; } keys.SetValue(d, lo + i - 1); 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); items?.SetValue(items.GetValue(j), j + 1); j--; } keys.SetValue(t, j + 1); 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 MemoryMarshal.GetArrayDataReference(array)), array.Length).Slice(adjustedIndex, length); public IEnumerator GetEnumerator() { return new ArrayEnumerator(this); } } } |