qsort.cpp File Reference

#include <corecrt_internal.h>
#include <search.h>

Include dependency graph for qsort.cpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#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))
#define	__fileDECL   __cdecl
#define	__COMPARE(context, p1, p2)   comp(p1, p2)
#define	__SHORTSORT(lo, hi, width, comp, context)   shortsort(lo, hi, width, comp);
#define	_QSORT_SWAP_DEFINED
#define	CUTOFF   8
#define	STKSIZ   (8 * sizeof(void*) - 2)

Functions
static _CRT_SECURITYSAFECRITICAL_ATTRIBUTE void __fileDECL	swap (_Inout_updates_(width) char *a, _Inout_updates_(width) char *b, size_t width)
static _CRT_SECURITYSAFECRITICAL_ATTRIBUTE 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 *))
_CRT_SECURITYSAFECRITICAL_ATTRIBUTE void __fileDECL	qsort (void *const base, size_t const num, size_t const width, int(__fileDECL *const comp)(void const *, void const *))

Macro Definition Documentation

__COMPARE

#define __COMPARE	(		context,
			p1,
			p2
	)		comp(p1, p2)

Definition at line 40 of file qsort.cpp.

__fileDECL

#define __fileDECL   __cdecl

Definition at line 31 of file qsort.cpp.

__SHORTSORT

#define __SHORTSORT	(		lo,
			hi,
			width,
			comp,
			context
	)		shortsort(lo, hi, width, comp);

Definition at line 41 of file qsort.cpp.

_QSORT_SWAP_DEFINED

#define _QSORT_SWAP_DEFINED

Definition at line 48 of file qsort.cpp.

BEGIN_PRAGMA_OPTIMIZE_DISABLE

#define BEGIN_PRAGMA_OPTIMIZE_DISABLE	(		flags,
			bug,
			reason
	)		__pragma(optimize(flags, off))

Definition at line 14 of file qsort.cpp.

BEGIN_PRAGMA_OPTIMIZE_ENABLE

#define BEGIN_PRAGMA_OPTIMIZE_ENABLE	(		flags,
			bug,
			reason
	)		__pragma(optimize(flags, on))

Definition at line 16 of file qsort.cpp.

CUTOFF

#define CUTOFF   8

Definition at line 131 of file qsort.cpp.

END_PRAGMA_OPTIMIZE

#define END_PRAGMA_OPTIMIZE

(

)

__pragma(optimize("", on))

Definition at line 18 of file qsort.cpp.

STKSIZ

#define STKSIZ   (8 * sizeof(void*) - 2)

Definition at line 138 of file qsort.cpp.

Function Documentation

qsort()

_CRT_SECURITYSAFECRITICAL_ATTRIBUTE void __fileDECL qsort	(	void *const	base,
		size_t const	num,
		size_t const	width,
		int(__fileDECL *const comp)(void const *, void const *)
	)

Definition at line 164 of file qsort.cpp.

{
    _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;
    }
}

shortsort()

static _CRT_SECURITYSAFECRITICAL_ATTRIBUTE 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 *)    )

static

Definition at line 83 of file qsort.cpp.

{
    // 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
}

swap()

static _CRT_SECURITYSAFECRITICAL_ATTRIBUTE void __fileDECL swap ( _Inout_updates_(width) char *  a, _Inout_updates_(width) char *  b, size_t  width  )

static

Definition at line 50 of file qsort.cpp.

{
    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;
        }
    }
}