Permalink
Fetching contributors…
Cannot retrieve contributors at this time
289 lines (261 sloc) 7.5 KB
//-------------------------------------------------------------------------------------------------------
// Copyright (C) Microsoft. All rights reserved.
// Licensed under the MIT license. See LICENSE.txt file in the project root for full license information.
//-------------------------------------------------------------------------------------------------------
#pragma once
namespace JsUtil
{
// Sorting Networks - BEGIN
#define CCQ_SORT2(a, b) \
if (comparer(context, \
base + (b * size), \
base + (a * size)) < 0) \
{ \
CCQ_SWAP(base + (a * size), \
base + (b * size), size); \
}
#define CCQ_SORT3() \
CCQ_SORT2(0, 1) \
CCQ_SORT2(1, 2) \
CCQ_SORT2(0, 1)
#define CCQ_SORT4() \
CCQ_SORT2(0, 1) \
CCQ_SORT2(2, 3) \
CCQ_SORT2(0, 2) \
CCQ_SORT2(1, 3) \
CCQ_SORT2(1, 2)
#define CCQ_SORT5(a, b, c, d, e) \
CCQ_SORT2(a, b) \
CCQ_SORT2(d, e) \
CCQ_SORT2(c, e) \
CCQ_SORT2(c, d) \
CCQ_SORT2(a, d) \
CCQ_SORT2(a, c) \
CCQ_SORT2(b, e) \
CCQ_SORT2(b, d) \
CCQ_SORT2(b, c)
#define CCQ_SORT6() \
CCQ_SORT2(1, 2) \
CCQ_SORT2(0, 2) \
CCQ_SORT2(0, 1) \
CCQ_SORT2(4, 5) \
CCQ_SORT2(3, 5) \
CCQ_SORT2(3, 4) \
CCQ_SORT2(0, 3) \
CCQ_SORT2(1, 4) \
CCQ_SORT2(2, 5) \
CCQ_SORT2(2, 4) \
CCQ_SORT2(1, 3) \
CCQ_SORT2(2, 3)
#define CCQ_SORT7() \
CCQ_SORT2(1, 2) \
CCQ_SORT2(0, 2) \
CCQ_SORT2(0, 1) \
CCQ_SORT2(3, 4) \
CCQ_SORT2(5, 6) \
CCQ_SORT2(3, 5) \
CCQ_SORT2(4, 6) \
CCQ_SORT2(4, 5) \
CCQ_SORT2(0, 4) \
CCQ_SORT2(0, 3) \
CCQ_SORT2(1, 5) \
CCQ_SORT2(2, 6) \
CCQ_SORT2(2, 5) \
CCQ_SORT2(1, 3) \
CCQ_SORT2(2, 4) \
CCQ_SORT2(2, 3)
#define CCQ_SORT8() \
CCQ_SORT2(0, 1) \
CCQ_SORT2(2, 3) \
CCQ_SORT2(0, 2) \
CCQ_SORT2(1, 3) \
CCQ_SORT2(1, 2) \
CCQ_SORT2(4, 5) \
CCQ_SORT2(6, 7) \
CCQ_SORT2(4, 6) \
CCQ_SORT2(5, 7) \
CCQ_SORT2(5, 6) \
CCQ_SORT2(0, 4) \
CCQ_SORT2(1, 5) \
CCQ_SORT2(1, 4) \
CCQ_SORT2(2, 6) \
CCQ_SORT2(3, 7) \
CCQ_SORT2(3, 6) \
CCQ_SORT2(2, 4) \
CCQ_SORT2(3, 5) \
CCQ_SORT2(3, 4)
#define CCQ_SORT9() \
CCQ_SORT2(0, 1) \
CCQ_SORT2(3, 4) \
CCQ_SORT2(6, 7) \
CCQ_SORT2(1, 2) \
CCQ_SORT2(4, 5) \
CCQ_SORT2(7, 8) \
CCQ_SORT2(0, 1) \
CCQ_SORT2(3, 4) \
CCQ_SORT2(6, 7) \
CCQ_SORT2(0, 3) \
CCQ_SORT2(3, 6) \
CCQ_SORT2(0, 3) \
CCQ_SORT2(1, 4) \
CCQ_SORT2(4, 7) \
CCQ_SORT2(1, 4) \
CCQ_SORT2(2, 5) \
CCQ_SORT2(5, 8) \
CCQ_SORT2(2, 5) \
CCQ_SORT2(1, 3) \
CCQ_SORT2(5, 7) \
CCQ_SORT2(2, 6) \
CCQ_SORT2(4, 6) \
CCQ_SORT2(2, 4) \
CCQ_SORT2(2, 3) \
CCQ_SORT2(5, 6)
// Sorting Networks - END
union CC_QSORT_SWAP8
{
char chr[8]; // optimized for Js::Var
};
union CC_QSORT_SWAP4
{
char chr[4]; // optimized for TypedArray
};
union CC_QSORT_SWAP2
{
char chr[2]; // others
};
#define CC_QSORT_SWAP_LOOP(T, a, b, nsize) \
{ \
for (size_t i = 0; i < nsize; i++) \
{ \
T c = (a)[i]; \
(a)[i] = (b)[i]; \
(b)[i] = c; \
} \
}
template <class Policy, class T>
class QuickSortSwap
{
public:
static inline void swap(T* a, T* b, size_t size)
{
if (a == b) return;
size_t mod;
if (size >= 8)
{
mod = size & 7;
CC_QSORT_SWAP_LOOP(CC_QSORT_SWAP8, (CC_QSORT_SWAP8*) a, (CC_QSORT_SWAP8*) b, size / 8)
}
else if (size >= 4)
{
mod = size & 3;
CC_QSORT_SWAP_LOOP(CC_QSORT_SWAP4, (CC_QSORT_SWAP4*) a, (CC_QSORT_SWAP4*) b, size / 4)
}
else
{
mod = size & 1;
CC_QSORT_SWAP_LOOP(CC_QSORT_SWAP2, (CC_QSORT_SWAP2*) a, (CC_QSORT_SWAP2*) b, size / 2)
}
CC_QSORT_SWAP_LOOP(char, (char*) a, (char*) b, mod);
}
};
#ifdef RECYCLER_WRITE_BARRIER
template <class T>
class QuickSortSwap<_write_barrier_policy, T>
{
public:
static inline void swap(T* a, T* b, size_t _)
{
AssertMsg(_ == 1, "No byte to byte copies when a type has SWB is enabled. size should be 1!");
T temp = *a;
*a = *b;
*b = temp;
}
};
#endif
template <class Policy, class T, class Comparer>
class QuickSort
{
public:
#define CCQ_SWAP QuickSortSwap<Policy, T>::swap
static void Sort(T* base, size_t nmemb, size_t size, Comparer comparer, void* context)
{
if (!base)
{
return;
}
if (nmemb <= 9) // use sorting networks for members <= 2^3
{
switch(nmemb)
{
case 9:
CCQ_SORT9()
break;
case 8:
CCQ_SORT8()
break;
case 7:
CCQ_SORT7()
break;
case 6:
CCQ_SORT6()
break;
case 5:
CCQ_SORT5(0, 1, 2, 3, 4)
break;
case 4:
CCQ_SORT4()
break;
case 3:
CCQ_SORT3()
break;
case 2:
CCQ_SORT2(0, 1)
break;
default:
break; // nothing to sort
}
return;
}
CCQ_SORT5(0, (nmemb / 4), (nmemb / 2), ((3 * nmemb) / 4), (nmemb - 1));
// guess the median is in the middle now.
size_t pos = 0;
const size_t pivot = (nmemb - 1) * size;
// make last element the median(pivot)
CCQ_SWAP(base + pivot, base + ((nmemb / 2) * size), size);
// standard qsort pt. below
size_t i = 0;
for (; i < nmemb / 2 * size; i+= size)
{
// During the first half, count equal values as below the pivot
if (comparer(context, base + i, base + pivot) <= 0)
{
CCQ_SWAP(base + i, base + (pos * size), size);
pos++;
}
}
for (; i < pivot; i+= size)
{
// During the second half, count equal values as above the pivot
if (comparer(context, base + i, base + pivot) < 0)
{
CCQ_SWAP(base + i, base + (pos * size), size);
pos++;
}
}
// issue the last change
CCQ_SWAP(base + (pos * size), base + pivot, size);
Sort(base, pos++, size, comparer, context);
Sort(base + (pos * size), nmemb - pos, size, comparer, context);
}
#undef CCQ_SWAP
};
#undef CCQ_SORT2
#undef CCQ_SORT3
#undef CCQ_SORT4
#undef CCQ_SORT5
#undef CCQ_SORT6
#undef CCQ_SORT7
#undef CCQ_SORT8
#undef CCQ_SORT9
#undef CC_QSORT_SWAP_LOOP
}