summaryrefslogtreecommitdiff
path: root/src/classlibnative/bcltype/arrayhelpers.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/classlibnative/bcltype/arrayhelpers.h')
-rw-r--r--src/classlibnative/bcltype/arrayhelpers.h349
1 files changed, 349 insertions, 0 deletions
diff --git a/src/classlibnative/bcltype/arrayhelpers.h b/src/classlibnative/bcltype/arrayhelpers.h
new file mode 100644
index 0000000000..9329f1a2f5
--- /dev/null
+++ b/src/classlibnative/bcltype/arrayhelpers.h
@@ -0,0 +1,349 @@
+//
+// Copyright (c) Microsoft. All rights reserved.
+// Licensed under the MIT license. See LICENSE file in the project root for full license information.
+//
+//
+// File: ArrayHelpers.h
+//
+
+//
+// Helper methods for the Array class
+// Specifically, this contains indexing, sorting & searching templates.
+
+
+#ifndef _ARRAYHELPERS_H_
+#define _ARRAYHELPERS_H_
+
+#if defined(_MSC_VER) && defined(_TARGET_X86_) && !defined(FPO_ON)
+#pragma optimize("y", on) // Small critical routines, don't put in EBP frame
+#define FPO_ON 1
+#define COMARRAYHELPERS_TURNED_FPO_ON 1
+#endif
+
+#include "fcall.h"
+
+
+template <class KIND>
+class ArrayHelpers
+{
+public:
+ static int IndexOf(KIND array[], UINT32 index, UINT32 count, KIND value) {
+ LIMITED_METHOD_CONTRACT;
+
+ _ASSERTE(array != NULL && index >= 0 && count >= 0);
+ for(UINT32 i=index; i<index+count; i++)
+ if (array[i] == value)
+ return i;
+ return -1;
+ }
+
+ static int LastIndexOf(KIND array[], UINT32 index, UINT32 count, KIND value) {
+ LIMITED_METHOD_CONTRACT;
+
+ INT32 startIndex = (INT32)index;
+ INT32 n = (INT32)count;
+ _ASSERTE(array != NULL);
+ _ASSERTE(startIndex >= 0);
+ _ASSERTE(n >= 0);
+
+ // Note (startIndex- n) may be -1 when startIndex is 0 and n is 1.
+ _ASSERTE(startIndex >= n - 1);
+
+ // Prefast: caller asserts guarantee that startIndex - n won't underflow, but we need to spell
+ // this out for prefast.
+ PREFIX_ASSUME(startIndex >= startIndex - n);
+ INT32 endIndex = max(startIndex - n, -1);
+
+ for(INT32 i=startIndex; i> endIndex; i--)
+ if (array[i] == value)
+ return i;
+ return -1;
+ }
+
+ static int BinarySearchBitwiseEquals(KIND array[], int index, int length, KIND value) {
+ WRAPPER_NO_CONTRACT;
+
+ _ASSERTE(array != NULL);
+ _ASSERTE(length >= 0);
+ _ASSERTE(index >= 0);
+
+ int lo = index;
+
+ // Prefast: mscorlib.dll!System.Array.BinarySearch(Array,int,int,Object,IComparer)
+ // guarantees index and length are in the array bounds and do not overflow
+ PREFIX_ASSUME(index >= 0 && length >= 0 && INT32_MAX >= index + length - 1);
+ int hi = index + length - 1;
+
+ // Note: if length == 0, hi will be Int32.MinValue, and our comparison
+ // here between 0 & -1 will prevent us from breaking anything.
+ while (lo <= hi) {
+ int i = lo + ((hi - lo) >> 1);
+ if (array[i] < value) {
+ lo = i + 1;
+ }
+ else if (array[i] > value){
+ hi = i - 1;
+ }
+ else {
+ return i;
+ }
+ }
+ return ~lo;
+ }
+
+ inline static void SwapIfGreaterWithItems(KIND keys[], KIND items[], int a, int b) {
+ if (a != b) {
+ if (keys[a] > keys[b]) {
+ KIND key = keys[a];
+ keys[a] = keys[b];
+ keys[b] = key;
+ if (items != NULL) {
+ KIND item = items[a];
+ items[a] = items[b];
+ items[b] = item;
+ }
+ }
+ }
+ }
+
+ // For sorting, move all NaN instances to front of the input array
+ template <class REAL>
+ static unsigned int NaNPrepass(REAL keys[], REAL items[], unsigned int left, unsigned int right) {
+ for (unsigned int i = left; i <= right; i++) {
+ if (_isnan(keys[i])) {
+ REAL temp = keys[left];
+ keys[left] = keys[i];
+ keys[i] = temp;
+ if (items != NULL) {
+ temp = items[left];
+ items[left] = items[i];
+ items[i] = temp;
+ }
+ left++;
+ }
+ }
+ return left;
+ }
+
+ // Implementation of Introspection Sort
+ static void IntrospectiveSort(KIND keys[], KIND items[], int left, int right) {
+ WRAPPER_NO_CONTRACT;
+
+ // Make sure left != right in your own code.
+ _ASSERTE(keys != NULL && left < right);
+
+ int length = right - left + 1;
+
+ if (length < 2)
+ return;
+
+ IntroSort(keys, items, left, right, 2 * FloorLog2(length));
+ }
+
+ static const int introsortSizeThreshold = 16;
+
+ static int FloorLog2(int n)
+ {
+ int result = 0;
+ while (n >= 1)
+ {
+ result++;
+ n = n / 2;
+ }
+ return result;
+ }
+
+ static void IntroSort(KIND keys[], KIND items[], int lo, int hi, int depthLimit)
+ {
+ while (hi > lo)
+ {
+ int partitionSize = hi - lo + 1;
+ if(partitionSize <= introsortSizeThreshold)
+ {
+ if (partitionSize == 1)
+ {
+ return;
+ }
+ if (partitionSize == 2)
+ {
+ SwapIfGreaterWithItems(keys, items, lo, hi);
+ return;
+ }
+ if (partitionSize == 3)
+ {
+ SwapIfGreaterWithItems(keys, items, lo, hi-1);
+ SwapIfGreaterWithItems(keys, items, lo, hi);
+ SwapIfGreaterWithItems(keys, items, hi-1, hi);
+ return;
+ }
+
+ InsertionSort(keys, items, lo, hi);
+ return;
+ }
+
+ if (depthLimit == 0)
+ {
+ Heapsort(keys, items, lo, hi);
+ return;
+ }
+ depthLimit--;
+
+ int p = PickPivotAndPartition(keys, items, lo, hi);
+ IntroSort(keys, items, p + 1, hi, depthLimit);
+ hi = p - 1;
+ }
+ return;
+ }
+
+ static void Swap(KIND keys[], KIND items[], int i, int j)
+ {
+ KIND t = keys[i];
+ keys[i] = keys[j];
+ keys[j] = t;
+
+ if (items != NULL)
+ {
+ KIND item = items[i];
+ items[i] = items[j];
+ items[j] = item;
+ }
+ }
+
+ static int PickPivotAndPartition(KIND keys[], KIND items[], int lo, int hi)
+ {
+ // Compute median-of-three. But also partition them, since we've done the comparison.
+ int mid = lo + (hi - lo) / 2;
+
+ // Sort lo, mid and hi appropriately, then pick mid as the pivot.
+ SwapIfGreaterWithItems(keys, items, lo, mid);
+ SwapIfGreaterWithItems(keys, items, lo, hi);
+ SwapIfGreaterWithItems(keys, items, mid, hi);
+
+ KIND pivot = keys[mid];
+ Swap(keys, items, 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 (left < (hi - 1) && keys[++left] < pivot);
+ while (right > lo && pivot < keys[--right]);
+
+ if ((left >= right))
+ break;
+
+ Swap(keys, items, left, right);
+ }
+
+ // Put pivot in the right location.
+ Swap(keys, items, left, (hi - 1));
+ return left;
+ }
+
+ static void Heapsort(KIND keys[], KIND items[], int lo, int hi)
+ {
+ int n = hi - lo + 1;
+ for (int i = n / 2; i >= 1; i = i - 1)
+ {
+ DownHeap(keys, items, i, n, lo);
+ }
+ for (int i = n; i > 1; i = i - 1)
+ {
+ Swap(keys, items, lo, lo + i -1);
+ DownHeap(keys, items, 1, i - 1, lo);
+ }
+ }
+
+ static void DownHeap(KIND keys[], KIND items[], int i, int n, int lo)
+ {
+ KIND d = keys[lo + i - 1];
+ KIND di = (items != NULL) ? items[lo + i - 1] : NULL;
+ int child;
+
+ while (i <= n / 2)
+ {
+ child = 2 * i;
+ if (child < n && keys[lo + child - 1] < keys[lo + child])
+ {
+ child++;
+ }
+ if (!(d < keys[lo + child - 1]))
+ break;
+
+ keys[lo + i - 1] = keys[lo + child - 1];
+ if(items != NULL)
+ items[lo + i - 1] = items[ lo + child - 1];
+ i = child;
+ }
+ keys[lo + i - 1] = d;
+ if(items != NULL)
+ items[lo + i - 1] = di;
+ }
+
+ static void InsertionSort(KIND keys[], KIND items[], int lo, int hi)
+ {
+ int i, j;
+ KIND t, ti = NULL;
+ for (i = lo; i < hi; i++)
+ {
+ j = i;
+ t = keys[i + 1];
+ if(items != NULL)
+ ti = items[i + 1];
+ while (j >= lo && t < keys[j])
+ {
+ keys[j + 1] = keys[j];
+ if(items != NULL)
+ items[j + 1] = items[j];
+ j--;
+ }
+ keys[j + 1] = t;
+ if(items != NULL)
+ items[j + 1] = ti;
+ }
+ }
+
+ static void Reverse(KIND array[], UINT32 index, UINT32 count) {
+ LIMITED_METHOD_CONTRACT;
+
+ _ASSERTE(array != NULL);
+ if (count == 0) {
+ return;
+ }
+ UINT32 i = index;
+ UINT32 j = index + count - 1;
+ while(i < j) {
+ KIND temp = array[i];
+ array[i] = array[j];
+ array[j] = temp;
+ i++;
+ j--;
+ }
+ }
+};
+
+
+class ArrayHelper
+{
+public:
+ // These methods return TRUE or FALSE for success or failure, and the real
+ // result is an out param. They're helpers to make operations on SZ arrays of
+ // primitives significantly faster.
+ static FCDECL5(FC_BOOL_RET, TrySZIndexOf, ArrayBase * array, UINT32 index, UINT32 count, Object * value, INT32 * retVal);
+ static FCDECL5(FC_BOOL_RET, TrySZLastIndexOf, ArrayBase * array, UINT32 index, UINT32 count, Object * value, INT32 * retVal);
+ static FCDECL5(FC_BOOL_RET, TrySZBinarySearch, ArrayBase * array, UINT32 index, UINT32 count, Object * value, INT32 * retVal);
+
+ static FCDECL4(FC_BOOL_RET, TrySZSort, ArrayBase * keys, ArrayBase * items, UINT32 left, UINT32 right);
+ static FCDECL3(FC_BOOL_RET, TrySZReverse, ArrayBase * array, UINT32 index, UINT32 count);
+
+ // Helper methods
+ static INT32 IndexOfUINT8( UINT8* array, UINT32 index, UINT32 count, UINT8 value);
+};
+
+#if defined(COMARRAYHELPERS_TURNED_FPO_ON)
+#pragma optimize("", on) // Go back to command line default optimizations
+#undef COMARRAYHELPERS_TURNED_FPO_ON
+#undef FPO_ON
+#endif
+
+#endif // _ARRAYHELPERS_H_