diff options
Diffstat (limited to 'src/classlibnative/bcltype/arrayhelpers.cpp')
-rw-r--r-- | src/classlibnative/bcltype/arrayhelpers.cpp | 427 |
1 files changed, 427 insertions, 0 deletions
diff --git a/src/classlibnative/bcltype/arrayhelpers.cpp b/src/classlibnative/bcltype/arrayhelpers.cpp new file mode 100644 index 0000000000..45e86d2b08 --- /dev/null +++ b/src/classlibnative/bcltype/arrayhelpers.cpp @@ -0,0 +1,427 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. +// +// File: ArrayHelpers.cpp +// + +// + +#include "common.h" + +#include <object.h> +#include "ceeload.h" + +#include "excep.h" +#include "frames.h" +#include "vars.hpp" +#include "classnames.h" +#include "arrayhelpers.h" +#include <memory.h> + +INT32 ArrayHelper::IndexOfUINT8( UINT8* array, UINT32 index, UINT32 count, UINT8 value) { + LIMITED_METHOD_CONTRACT; + UINT8 * pvalue = (UINT8 *)memchr(array + index, value, count); + if ( NULL == pvalue ) { + return -1; + } + else { + return static_cast<INT32>(pvalue - array); + } +} + + +// A fast IndexOf method for arrays of primitive types. Returns TRUE or FALSE +// if it succeeds, and stores result in retVal. +FCIMPL5(FC_BOOL_RET, ArrayHelper::TrySZIndexOf, ArrayBase * array, UINT32 index, UINT32 count, Object * value, INT32 * retVal) + FCALL_CONTRACT; + + VALIDATEOBJECT(array); + _ASSERTE(array != NULL); + + // <TODO>@TODO: Eventually, consider adding support for single dimension arrays with + // non-zero lower bounds. VB might care. </TODO> + if (array->GetRank() != 1 || array->GetLowerBoundsPtr()[0] != 0) + FC_RETURN_BOOL(FALSE); + + _ASSERTE(retVal != NULL); + _ASSERTE(index <= array->GetNumComponents()); + _ASSERTE(count <= array->GetNumComponents()); + _ASSERTE(array->GetNumComponents() >= index + count); + *retVal = 0xdeadbeef; // Initialize the return value. + // value can be NULL, but of course, will not be in primitive arrays. + + TypeHandle arrayTH = array->GetArrayElementTypeHandle(); + const CorElementType arrayElType = arrayTH.GetVerifierCorElementType(); + if (!CorTypeInfo::IsPrimitiveType_NoThrow(arrayElType)) + FC_RETURN_BOOL(FALSE); + // Handle special case of looking for a NULL object in a primitive array. + if (value == NULL) { + *retVal = -1; + FC_RETURN_BOOL(TRUE); + } + TypeHandle valueTH = value->GetTypeHandle(); + if (arrayTH != valueTH) + FC_RETURN_BOOL(FALSE); + + + switch(arrayElType) { + case ELEMENT_TYPE_I1: + case ELEMENT_TYPE_U1: + case ELEMENT_TYPE_BOOLEAN: + *retVal = IndexOfUINT8((U1*) array->GetDataPtr(), index, count, *(U1*)value->UnBox()); + break; + + case ELEMENT_TYPE_I2: + case ELEMENT_TYPE_U2: + case ELEMENT_TYPE_CHAR: + *retVal = ArrayHelpers<U2>::IndexOf((U2*) array->GetDataPtr(), index, count, *(U2*)value->UnBox()); + break; + + case ELEMENT_TYPE_I4: + case ELEMENT_TYPE_U4: + case ELEMENT_TYPE_R4: + IN_WIN32(case ELEMENT_TYPE_I:) + IN_WIN32(case ELEMENT_TYPE_U:) + *retVal = ArrayHelpers<U4>::IndexOf((U4*) array->GetDataPtr(), index, count, *(U4*)value->UnBox()); + break; + + case ELEMENT_TYPE_I8: + case ELEMENT_TYPE_U8: + case ELEMENT_TYPE_R8: + IN_WIN64(case ELEMENT_TYPE_I:) + IN_WIN64(case ELEMENT_TYPE_U:) + *retVal = ArrayHelpers<U8>::IndexOf((U8*) array->GetDataPtr(), index, count, *(U8*)value->UnBox()); + break; + + default: + _ASSERTE(!"Unrecognized primitive type in ArrayHelper::TrySZIndexOf"); + FC_RETURN_BOOL(FALSE); + } + FC_RETURN_BOOL(TRUE); +FCIMPLEND + +// A fast LastIndexOf method for arrays of primitive types. Returns TRUE or FALSE +// if it succeeds, and stores result in retVal. +FCIMPL5(FC_BOOL_RET, ArrayHelper::TrySZLastIndexOf, ArrayBase * array, UINT32 index, UINT32 count, Object * value, INT32 * retVal) +{ + FCALL_CONTRACT; + + VALIDATEOBJECT(array); + _ASSERTE(array != NULL); + + // <TODO>@TODO: Eventually, consider adding support for single dimension arrays with + // non-zero lower bounds. VB might care. </TODO> + if (array->GetRank() != 1 || array->GetLowerBoundsPtr()[0] != 0) + FC_RETURN_BOOL(FALSE); + + _ASSERTE(retVal != NULL); + *retVal = 0xdeadbeef; // Initialize the return value. + // value can be NULL, but of course, will not be in primitive arrays. + + TypeHandle arrayTH = array->GetArrayElementTypeHandle(); + const CorElementType arrayElType = arrayTH.GetVerifierCorElementType(); + if (!CorTypeInfo::IsPrimitiveType_NoThrow(arrayElType)) + FC_RETURN_BOOL(FALSE); + // Handle special case of looking for a NULL object in a primitive array. + // Also handle case where the array is of 0 length. + if (value == NULL || array->GetNumComponents() == 0) { + *retVal = -1; + FC_RETURN_BOOL(TRUE); + } + + _ASSERTE(index < array->GetNumComponents()); + _ASSERTE(count <= array->GetNumComponents()); + _ASSERTE(index + 1 >= count); + + TypeHandle valueTH = value->GetTypeHandle(); + if (arrayTH != valueTH) + FC_RETURN_BOOL(FALSE); + + + switch(arrayElType) { + case ELEMENT_TYPE_I1: + case ELEMENT_TYPE_U1: + case ELEMENT_TYPE_BOOLEAN: + *retVal = ArrayHelpers<U1>::LastIndexOf((U1*) array->GetDataPtr(), index, count, *(U1*)value->UnBox()); + break; + + case ELEMENT_TYPE_I2: + case ELEMENT_TYPE_U2: + case ELEMENT_TYPE_CHAR: + *retVal = ArrayHelpers<U2>::LastIndexOf((U2*) array->GetDataPtr(), index, count, *(U2*)value->UnBox()); + break; + + case ELEMENT_TYPE_I4: + case ELEMENT_TYPE_U4: + case ELEMENT_TYPE_R4: + IN_WIN32(case ELEMENT_TYPE_I:) + IN_WIN32(case ELEMENT_TYPE_U:) + *retVal = ArrayHelpers<U4>::LastIndexOf((U4*) array->GetDataPtr(), index, count, *(U4*)value->UnBox()); + break; + + case ELEMENT_TYPE_I8: + case ELEMENT_TYPE_U8: + case ELEMENT_TYPE_R8: + IN_WIN64(case ELEMENT_TYPE_I:) + IN_WIN64(case ELEMENT_TYPE_U:) + *retVal = ArrayHelpers<U8>::LastIndexOf((U8*) array->GetDataPtr(), index, count, *(U8*)value->UnBox()); + break; + + default: + _ASSERTE(!"Unrecognized primitive type in ArrayHelper::TrySZLastIndexOf"); + FC_RETURN_BOOL(FALSE); + } + FC_RETURN_BOOL(TRUE); +} +FCIMPLEND + + +FCIMPL5(FC_BOOL_RET, ArrayHelper::TrySZBinarySearch, ArrayBase * array, UINT32 index, UINT32 count, Object * value, INT32 * retVal) + FCALL_CONTRACT; + + VALIDATEOBJECT(array); + _ASSERTE(array != NULL); + + // <TODO>@TODO: Eventually, consider adding support for single dimension arrays with + // non-zero lower bounds. VB might care. </TODO> + if (array->GetRank() != 1 || array->GetLowerBoundsPtr()[0] != 0) + FC_RETURN_BOOL(FALSE); + + _ASSERTE(retVal != NULL); + _ASSERTE(index <= array->GetNumComponents()); + _ASSERTE(count <= array->GetNumComponents()); + _ASSERTE(array->GetNumComponents() >= index + count); + *retVal = 0xdeadbeef; // Initialize the return value. + // value can be NULL, but of course, will not be in primitive arrays. + TypeHandle arrayTH = array->GetArrayElementTypeHandle(); + const CorElementType arrayElType = arrayTH.GetVerifierCorElementType(); + if (!CorTypeInfo::IsPrimitiveType_NoThrow(arrayElType)) + FC_RETURN_BOOL(FALSE); + // Handle special case of looking for a NULL object in a primitive array. + if (value == NULL) { + *retVal = -1; + FC_RETURN_BOOL(TRUE); + } + + TypeHandle valueTH = value->GetTypeHandle(); + if (arrayTH != valueTH) + FC_RETURN_BOOL(FALSE); + + switch(arrayElType) { + case ELEMENT_TYPE_I1: + *retVal = ArrayHelpers<I1>::BinarySearchBitwiseEquals((I1*) array->GetDataPtr(), index, count, *(I1*)value->UnBox()); + break; + + case ELEMENT_TYPE_U1: + case ELEMENT_TYPE_BOOLEAN: + *retVal = ArrayHelpers<U1>::BinarySearchBitwiseEquals((U1*) array->GetDataPtr(), index, count, *(U1*)value->UnBox()); + break; + + case ELEMENT_TYPE_I2: + *retVal = ArrayHelpers<I2>::BinarySearchBitwiseEquals((I2*) array->GetDataPtr(), index, count, *(I2*)value->UnBox()); + break; + + case ELEMENT_TYPE_U2: + case ELEMENT_TYPE_CHAR: + *retVal = ArrayHelpers<U2>::BinarySearchBitwiseEquals((U2*) array->GetDataPtr(), index, count, *(U2*)value->UnBox()); + break; + + case ELEMENT_TYPE_I4: + *retVal = ArrayHelpers<I4>::BinarySearchBitwiseEquals((I4*) array->GetDataPtr(), index, count, *(I4*)value->UnBox()); + break; + + case ELEMENT_TYPE_U4: + *retVal = ArrayHelpers<U4>::BinarySearchBitwiseEquals((U4*) array->GetDataPtr(), index, count, *(U4*)value->UnBox()); + break; + + case ELEMENT_TYPE_R4: + *retVal = ArrayHelpers<R4>::BinarySearchBitwiseEquals((R4*) array->GetDataPtr(), index, count, *(R4*)value->UnBox()); + break; + + case ELEMENT_TYPE_I8: + *retVal = ArrayHelpers<I8>::BinarySearchBitwiseEquals((I8*) array->GetDataPtr(), index, count, *(I8*)value->UnBox()); + break; + + case ELEMENT_TYPE_U8: + *retVal = ArrayHelpers<U8>::BinarySearchBitwiseEquals((U8*) array->GetDataPtr(), index, count, *(U8*)value->UnBox()); + break; + + case ELEMENT_TYPE_R8: + *retVal = ArrayHelpers<R8>::BinarySearchBitwiseEquals((R8*) array->GetDataPtr(), index, count, *(R8*)value->UnBox()); + break; + + case ELEMENT_TYPE_I: + case ELEMENT_TYPE_U: + // In V1.0, IntPtr & UIntPtr are not fully supported types. They do + // not implement IComparable, so searching & sorting for them should + // fail. In V1.1 or V2.0, this should change. + FC_RETURN_BOOL(FALSE); + + default: + _ASSERTE(!"Unrecognized primitive type in ArrayHelper::TrySZBinarySearch"); + FC_RETURN_BOOL(FALSE); + } + FC_RETURN_BOOL(TRUE); +FCIMPLEND + +FCIMPL4(FC_BOOL_RET, ArrayHelper::TrySZSort, ArrayBase * keys, ArrayBase * items, UINT32 left, UINT32 right) + FCALL_CONTRACT; + + VALIDATEOBJECT(keys); + VALIDATEOBJECT(items); + _ASSERTE(keys != NULL); + + // <TODO>@TODO: Eventually, consider adding support for single dimension arrays with + // non-zero lower bounds. VB might care. </TODO> + if (keys->GetRank() != 1 || keys->GetLowerBoundsPtr()[0] != 0) + FC_RETURN_BOOL(FALSE); + + _ASSERTE(left <= right); + _ASSERTE(right < keys->GetNumComponents() || keys->GetNumComponents() == 0); + + TypeHandle keysTH = keys->GetArrayElementTypeHandle(); + const CorElementType keysElType = keysTH.GetVerifierCorElementType(); + if (!CorTypeInfo::IsPrimitiveType_NoThrow(keysElType)) + FC_RETURN_BOOL(FALSE); + if (items != NULL) { + TypeHandle itemsTH = items->GetArrayElementTypeHandle(); + if (keysTH != itemsTH) + FC_RETURN_BOOL(FALSE); // Can't currently handle sorting different types of arrays. + } + + // Handle special case of a 0 element range to sort. + // Consider both Sort(array, x, x) and Sort(zeroLen, 0, zeroLen.Length-1); + if (left == right || right == 0xffffffff) + FC_RETURN_BOOL(TRUE); + + switch(keysElType) { + case ELEMENT_TYPE_I1: + ArrayHelpers<I1>::IntrospectiveSort((I1*) keys->GetDataPtr(), (I1*) (items == NULL ? NULL : items->GetDataPtr()), left, right); + break; + + case ELEMENT_TYPE_U1: + case ELEMENT_TYPE_BOOLEAN: + ArrayHelpers<U1>::IntrospectiveSort((U1*) keys->GetDataPtr(), (U1*) (items == NULL ? NULL : items->GetDataPtr()), left, right); + break; + + case ELEMENT_TYPE_I2: + ArrayHelpers<I2>::IntrospectiveSort((I2*) keys->GetDataPtr(), (I2*) (items == NULL ? NULL : items->GetDataPtr()), left, right); + break; + + case ELEMENT_TYPE_U2: + case ELEMENT_TYPE_CHAR: + ArrayHelpers<U2>::IntrospectiveSort((U2*) keys->GetDataPtr(), (U2*) (items == NULL ? NULL : items->GetDataPtr()), left, right); + break; + + case ELEMENT_TYPE_I4: + ArrayHelpers<I4>::IntrospectiveSort((I4*) keys->GetDataPtr(), (I4*) (items == NULL ? NULL : items->GetDataPtr()), left, right); + break; + + case ELEMENT_TYPE_U4: + ArrayHelpers<U4>::IntrospectiveSort((U4*) keys->GetDataPtr(), (U4*) (items == NULL ? NULL : items->GetDataPtr()), left, right); + break; + + case ELEMENT_TYPE_R4: + { + R4 * R4Keys = (R4*) keys->GetDataPtr(); + R4 * R4Items = (R4*) (items == NULL ? NULL : items->GetDataPtr()); + + // Comparison to NaN is always false, so do a linear pass + // and swap all NaNs to the front of the array + left = ArrayHelpers<R4>::NaNPrepass(R4Keys, R4Items, left, right); + if(left != right) ArrayHelpers<R4>::IntrospectiveSort(R4Keys, R4Items, left, right); + break; + }; + + case ELEMENT_TYPE_I8: + ArrayHelpers<I8>::IntrospectiveSort((I8*) keys->GetDataPtr(), (I8*) (items == NULL ? NULL : items->GetDataPtr()), left, right); + break; + + case ELEMENT_TYPE_U8: + ArrayHelpers<U8>::IntrospectiveSort((U8*) keys->GetDataPtr(), (U8*) (items == NULL ? NULL : items->GetDataPtr()), left, right); + break; + + case ELEMENT_TYPE_R8: + { + R8 * R8Keys = (R8*) keys->GetDataPtr(); + R8 * R8Items = (R8*) (items == NULL ? NULL : items->GetDataPtr()); + + // Comparison to NaN is always false, so do a linear pass + // and swap all NaNs to the front of the array + left = ArrayHelpers<R8>::NaNPrepass(R8Keys, R8Items, left, right); + if(left != right) ArrayHelpers<R8>::IntrospectiveSort(R8Keys, R8Items, left, right); + break; + }; + + case ELEMENT_TYPE_I: + case ELEMENT_TYPE_U: + // In V1.0, IntPtr & UIntPtr are not fully supported types. They do + // not implement IComparable, so searching & sorting for them should + // fail. In V1.1 or V2.0, this should change. + FC_RETURN_BOOL(FALSE); + + default: + _ASSERTE(!"Unrecognized primitive type in ArrayHelper::TrySZSort"); + FC_RETURN_BOOL(FALSE); + } + FC_RETURN_BOOL(TRUE); +FCIMPLEND + +FCIMPL3(FC_BOOL_RET, ArrayHelper::TrySZReverse, ArrayBase * array, UINT32 index, UINT32 count) +{ + FCALL_CONTRACT; + + VALIDATEOBJECT(array); + _ASSERTE(array != NULL); + + // <TODO>@TODO: Eventually, consider adding support for single dimension arrays with + // non-zero lower bounds. VB might care. </TODO> + if (array->GetRank() != 1 || array->GetLowerBoundsPtr()[0] != 0) + FC_RETURN_BOOL(FALSE); + + _ASSERTE(index <= array->GetNumComponents()); + _ASSERTE(count <= array->GetNumComponents()); + _ASSERTE(array->GetNumComponents() >= index + count); + + TypeHandle arrayTH = array->GetArrayElementTypeHandle(); + const CorElementType arrayElType = arrayTH.GetVerifierCorElementType(); + if (!CorTypeInfo::IsPrimitiveType_NoThrow(arrayElType)) + FC_RETURN_BOOL(FALSE); + + switch(arrayElType) { + case ELEMENT_TYPE_I1: + case ELEMENT_TYPE_U1: + case ELEMENT_TYPE_BOOLEAN: + ArrayHelpers<U1>::Reverse((U1*) array->GetDataPtr(), index, count); + break; + + case ELEMENT_TYPE_I2: + case ELEMENT_TYPE_U2: + case ELEMENT_TYPE_CHAR: + ArrayHelpers<U2>::Reverse((U2*) array->GetDataPtr(), index, count); + break; + + case ELEMENT_TYPE_I4: + case ELEMENT_TYPE_U4: + case ELEMENT_TYPE_R4: + IN_WIN32(case ELEMENT_TYPE_I:) + IN_WIN32(case ELEMENT_TYPE_U:) + ArrayHelpers<U4>::Reverse((U4*) array->GetDataPtr(), index, count); + break; + + case ELEMENT_TYPE_I8: + case ELEMENT_TYPE_U8: + case ELEMENT_TYPE_R8: + IN_WIN64(case ELEMENT_TYPE_I:) + IN_WIN64(case ELEMENT_TYPE_U:) + ArrayHelpers<U8>::Reverse((U8*) array->GetDataPtr(), index, count); + break; + + default: + _ASSERTE(!"Unrecognized primitive type in ArrayHelper::TrySZReverse"); + FC_RETURN_BOOL(FALSE); + } + FC_RETURN_BOOL(TRUE); +} +FCIMPLEND |