Something went wrong. Try again.
Reactos
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397//// qsort.cpp//// Copyright (c) Microsoft Corporation. All rights reserved.//// Defines qsort(), a routine for sorting arrays.//#include <corecrt_internal.h>#include <search.h>
/* Temporarily define optimization macros (to be removed by the build team: RsmqblCompiler alias) */#if !defined(BEGIN_PRAGMA_OPTIMIZE_DISABLE)#define BEGIN_PRAGMA_OPTIMIZE_DISABLE(flags, bug, reason) \ __pragma(optimize(flags, off))#define BEGIN_PRAGMA_OPTIMIZE_ENABLE(flags, bug, reason) \ __pragma(optimize(flags, on))#define END_PRAGMA_OPTIMIZE() \ __pragma(optimize("", on))#endif
// Always compile this module for speed, not sizeBEGIN_PRAGMA_OPTIMIZE_ENABLE("t", MSFT:4499497, "This file is performance-critical and should always be optimized for speed")
#ifdef _M_CEE #define __fileDECL __clrcall#else #define __fileDECL __cdecl#endif
#ifdef __USE_CONTEXT #define __COMPARE(context, p1, p2) comp(context, p1, p2) #define __SHORTSORT(lo, hi, width, comp, context) shortsort_s(lo, hi, width, comp, context);#else #define __COMPARE(context, p1, p2) comp(p1, p2) #define __SHORTSORT(lo, hi, width, comp, context) shortsort(lo, hi, width, comp);#endif
// Swaps the objects of size 'width' that are pointed to by 'a' and 'b'#ifndef _QSORT_SWAP_DEFINED#define _QSORT_SWAP_DEFINED_CRT_SECURITYSAFECRITICAL_ATTRIBUTEstatic void __fileDECL swap(_Inout_updates_(width) char* a, _Inout_updates_(width) char* b, size_t width){ if (a != b) { // Do the swap one character at a time to avoid potential alignment // problems: while (width--) { char const tmp = *a; *a++ = *b; *b++ = tmp; } }}#endif // _QSORT_SWAP_DEFINED
// An insertion sort for sorting short arrays. Sorts the sub-array of elements// between lo and hi (inclusive). Assumes lo < hi. lo and hi are pointers to// the first and last elements in the range to be sorted (note: hi does not// point one-past-the-end). The comp is a comparer with the same behavior as// specified for qsort._CRT_SECURITYSAFECRITICAL_ATTRIBUTE#ifdef __USE_CONTEXTstatic void __fileDECL shortsort_s( _Inout_updates_(hi - lo + 1) char* lo, _Inout_updates_(width) char* hi, size_t const width, int (__fileDECL* comp)(void*, void const*, void const*), void* const context )#else // __USE_CONTEXTstatic void __fileDECL shortsort( _Inout_updates_(hi - lo + 1) char* lo, _Inout_updates_(width) char* hi, size_t const width, int (__fileDECL* comp)(void const*, void const*) )#endif // __USE_CONTEXT{ // Note: in assertions below, i and j are alway inside original bound of // array to sort.
// Reentrancy diligence: Save (and unset) global-state mode to the stack before making callout to 'compare' __crt_state_management::scoped_global_state_reset saved_state;
while (hi > lo) { // A[i] <= A[j] for i <= j, j > hi char* max = lo; for (char* p = lo+width; p <= hi; p += width) { // A[i] <= A[max] for lo <= i < p if (__COMPARE(context, p, max) > 0) { max = p; } // A[i] <= A[max] for lo <= i <= p }
// A[i] <= A[max] for lo <= i <= hi
swap(max, hi, width);
// A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi
hi -= width;
// A[i] <= A[j] for i <= j, j > hi, loop top condition established }
// A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j, // so array is sorted}
// This macro defines the cutoff between using QuickSort and insertion sort for// arrays; arrays with lengths shorter or equal to the below value use insertion// sort.#define CUTOFF 8 // Testing shows that this is a good value.
// Note: The theoretical number of stack entries required is no more than 1 +// log2(num). But we switch to insertion sort for CUTOFF elements or less, so// we really only need 1 + log2(num) - log(CUTOFF) stack entries. For a CUTOFF// of 8, that means we need no more than 30 stack entries for 32-bit platforms// and 62 for 64-bit platforms.#define STKSIZ (8 * sizeof(void*) - 2)
// QuickSort function for sorting arrays. The array is sorted in place.// Parameters:// * base: Pointer to the initial element of the array// * num: Number of elements in the array// * width: Width of each element in the array, in bytes// * comp: Pointer to a function returning analog of strcmp for strings, but// supplied by the caller for comparing the array elements. It// accepts two pointers to elements; returns negative if 1 < 2;// zero if 1 == 2, and positive if 1 > 2.#ifndef _M_CEEextern "C"#endif_CRT_SECURITYSAFECRITICAL_ATTRIBUTE#ifdef __USE_CONTEXTvoid __fileDECL qsort_s( void* const base, size_t const num, size_t const width, int (__fileDECL* const comp)(void*, void const*, void const*), void* const context )#else // __USE_CONTEXTvoid __fileDECL qsort( void* const base, size_t const num, size_t const width, int (__fileDECL* const comp)(void const*, void const*) )#endif // __USE_CONTEXT{ _VALIDATE_RETURN_VOID(base != nullptr || num == 0, EINVAL); _VALIDATE_RETURN_VOID(width > 0, EINVAL); _VALIDATE_RETURN_VOID(comp != nullptr, EINVAL);
// A stack for saving the sub-arrays yet to be processed: char* lostk[STKSIZ]; char* histk[STKSIZ]; int stkptr = 0;
if (num < 2) return; // Nothing to do:
// The ends of the sub-array currently being sorted (note that 'hi' points // to the last element, not one-past-the-end): char* lo = static_cast<char*>(base); char* hi = static_cast<char*>(base) + width * (num-1);
// This entry point is for pseudo-recursion calling: setting // lo and hi and jumping to here is like recursion, but stkptr is // preserved, locals aren't, so we preserve stuff on the stack.recurse:
// The number of elements in the sub-array currently being sorted: size_t const size = (hi - lo) / width + 1;
// Below a certain size, it is faster to use a O(n^2) sorting method: if (size <= CUTOFF) { __SHORTSORT(lo, hi, width, comp, context); } else { // First we pick a partitioning element. The efficiency of the // algorithm demands that we find one that is approximately the median // of the values, but also that we select one fast. We choose the // median of the first, middle, and last elements, to avoid bad // performance in the face of already sorted data, or data that is made // up of multiple sorted runs appended together. Testing shows that a // median-of-three algorithm provides better performance than simply // picking the middle element for the latter case.
// Find the middle element: char* mid = lo + (size / 2) * width;
// Sort the first, middle, last elements into order: if (__COMPARE(context, lo, mid) > 0) swap(lo, mid, width);
if (__COMPARE(context, lo, hi) > 0) swap(lo, hi, width);
if (__COMPARE(context, mid, hi) > 0) swap(mid, hi, width);
// We now wish to partition the array into three pieces, one consisting // of elements <= partition element, one of elements equal to the // partition element, and one of elements > than it. This is done // below; comments indicate conditions established at every step.
char* loguy = lo; char* higuy = hi;
// Note that higuy decreases and loguy increases on every iteration, // so loop must terminate. for (;;) { // lo <= loguy < hi, lo < higuy <= hi, // A[i] <= A[mid] for lo <= i <= loguy, // A[i] > A[mid] for higuy <= i < hi, // A[hi] >= A[mid]
// The doubled loop is to avoid calling comp(mid,mid), since some // existing comparison funcs don't work when passed the same // value for both pointers.
if (mid > loguy) { do { loguy += width; } while (loguy < mid && __COMPARE(context, loguy, mid) <= 0); } if (mid <= loguy) { do { loguy += width; } while (loguy <= hi && __COMPARE(context, loguy, mid) <= 0); }
// lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy, // either loguy > hi or A[loguy] > A[mid]
do { higuy -= width; } while (higuy > mid && __COMPARE(context, higuy, mid) > 0);
// lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi, // either higuy == lo or A[higuy] <= A[mid]
if (higuy < loguy) break;
// if loguy > hi or higuy == lo, then we would have exited, so // A[loguy] > A[mid], A[higuy] <= A[mid], // loguy <= hi, higuy > lo
swap(loguy, higuy, width);
// If the partition element was moved, follow it. Only need // to check for mid == higuy, since before the swap, // A[loguy] > A[mid] implies loguy != mid.
if (mid == higuy) mid = loguy;
// A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top // of loop is re-established }
// A[i] <= A[mid] for lo <= i < loguy, // A[i] > A[mid] for higuy < i < hi, // A[hi] >= A[mid] // higuy < loguy // implying: // higuy == loguy-1 // or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid]
// Find adjacent elements equal to the partition element. The // doubled loop is to avoid calling comp(mid,mid), since some // existing comparison funcs don't work when passed the same value // for both pointers.
higuy += width; if (mid < higuy) { do { higuy -= width; } while (higuy > mid && __COMPARE(context, higuy, mid) == 0); } if (mid >= higuy) { do { higuy -= width; } while (higuy > lo && __COMPARE(context, higuy, mid) == 0); }
// OK, now we have the following: // higuy < loguy // lo <= higuy <= hi // A[i] <= A[mid] for lo <= i <= higuy // A[i] == A[mid] for higuy < i < loguy // A[i] > A[mid] for loguy <= i < hi // A[hi] >= A[mid] */
// We've finished the partition, now we want to sort the subarrays // [lo, higuy] and [loguy, hi]. // We do the smaller one first to minimize stack usage. // We only sort arrays of length 2 or more.
if (higuy - lo >= hi - loguy) { if (lo < higuy) { // Save the big recursion for later: lostk[stkptr] = lo; histk[stkptr] = higuy; ++stkptr; }
if (loguy < hi) { // Do the small recursion: lo = loguy; goto recurse; } } else { if (loguy < hi) { // Save the big recursion for later: lostk[stkptr] = loguy; histk[stkptr] = hi; ++stkptr; }
if (lo < higuy) { // Do the small recursion: hi = higuy; goto recurse; } } }
// We have sorted the array, except for any pending sorts on the stack. // Check if there are any, and sort them: --stkptr; if (stkptr >= 0) { // Pop sub-array from the stack: lo = lostk[stkptr]; hi = histk[stkptr]; goto recurse; } else { // Otherwise, all sub-arrays have been sorted: return; }}
#undef __COMPARE#undef __SHORTSORT
END_PRAGMA_OPTIMIZE()