Loading

Paste #pxwjx24zl

  1. //
  2. // qsort.cpp
  3. //
  4. //      Copyright (c) Microsoft Corporation. All rights reserved.
  5. //
  6. // Defines qsort(), a routine for sorting arrays.
  7. //
  8. #include <corecrt_internal.h>
  9. #include <search.h>
  10.  
  11.  
  12.  
  13. // Always compile this module for speed, not size
  14. #pragma optimize("t", on)
  15.  
  16.  
  17.  
  18. #ifdef _M_CEE
  19.     #define __fileDECL __clrcall
  20. #else
  21.     #define __fileDECL __cdecl
  22. #endif
  23.  
  24.  
  25.  
  26. #ifdef __USE_CONTEXT
  27.     #define __COMPARE(context, p1, p2)                comp(context, p1, p2)
  28.     #define __SHORTSORT(lo, hi, width, comp, context) shortsort_s(lo, hi, width, comp, context);
  29. #else
  30.     #define __COMPARE(context, p1, p2)                comp(p1, p2)
  31.     #define __SHORTSORT(lo, hi, width, comp, context) shortsort(lo, hi, width, comp);
  32. #endif
  33.  
  34.  
  35.  
  36. // Swaps the objects of size 'width' that are pointed to by 'a' and 'b'
  37. #ifndef _QSORT_SWAP_DEFINED
  38. #define _QSORT_SWAP_DEFINED
  39. _CRT_SECURITYSAFECRITICAL_ATTRIBUTE
  40. static void __fileDECL swap(_Inout_updates_(width) char* a, _Inout_updates_(width) char* b, size_t width)
  41. {
  42.     if (a != b)
  43.     {
  44.         // Do the swap one character at a time to avoid potential alignment
  45.         // problems:
  46.         while (width--)
  47.         {
  48.             char const tmp = *a;
  49.             *a++ = *b;
  50.             *b++ = tmp;
  51.         }
  52.     }
  53. }
  54. #endif // _QSORT_SWAP_DEFINED
  55.  
  56.  
  57.  
  58. // An insertion sort for sorting short arrays.  Sorts the sub-array of elements
  59. // between lo and hi (inclusive).  Assumes lo < hi.  lo and hi are pointers to
  60. // the first and last elements in the range to be sorted (note:  hi does not
  61. // point one-past-the-end).  The comp is a comparer with the same behavior as
  62. // specified for qsort.
  63. _CRT_SECURITYSAFECRITICAL_ATTRIBUTE
  64. #ifdef __USE_CONTEXT
  65. static void __fileDECL shortsort_s(
  66.     _Inout_updates_(hi - lo + 1) char*        lo,
  67.     _Inout_updates_(width)       char*        hi,
  68.     size_t const width,
  69.     int (__fileDECL* comp)(void*, void const*, void const*),
  70.     void*  const context
  71.     )
  72. #else // __USE_CONTEXT
  73. static void __fileDECL shortsort(
  74.     _Inout_updates_(hi - lo + 1) char*        lo,
  75.     _Inout_updates_(width)       char*        hi,
  76.     size_t const width,
  77.     int (__fileDECL* comp)(void const*, void const*)
  78.     )
  79. #endif // __USE_CONTEXT
  80. {
  81.     // Note: in assertions below, i and j are alway inside original bound of
  82.     // array to sort.
  83.  
  84.     // Reentrancy diligence: Save (and unset) global-state mode to the stack before making callout to 'compare'
  85.     __crt_state_management::scoped_global_state_reset saved_state;
  86.  
  87.     while (hi > lo)
  88.     {
  89.         // A[i] <= A[j] for i <= j, j > hi
  90.         char* max = lo;
  91.         for (char* p = lo+width; p <= hi; p += width)
  92.         {
  93.             // A[i] <= A[max] for lo <= i < p
  94.             if (__COMPARE(context, p, max) > 0)
  95.             {
  96.                 max = p;
  97.             }
  98.             // A[i] <= A[max] for lo <= i <= p
  99.         }
  100.  
  101.         // A[i] <= A[max] for lo <= i <= hi
  102.  
  103.         swap(max, hi, width);
  104.  
  105.         // A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi
  106.  
  107.         hi -= width;
  108.  
  109.         // A[i] <= A[j] for i <= j, j > hi, loop top condition established
  110.     }
  111.  
  112.     // A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
  113.     // so array is sorted
  114. }
  115.  
  116.  
  117.  
  118. // This macro defines the cutoff between using QuickSort and insertion sort for
  119. // arrays; arrays with lengths shorter or equal to the below value use insertion
  120. // sort.
  121. #define CUTOFF 8 // Testing shows that this is a good value.
  122.  
  123. // Note:  The theoretical number of stack entries required is no more than 1 +
  124. // log2(num).  But we switch to insertion sort for CUTOFF elements or less, so
  125. // we really only need 1 + log2(num) - log(CUTOFF) stack entries.  For a CUTOFF
  126. // of 8, that means we need no more than 30 stack entries for 32-bit platforms
  127. // and 62 for 64-bit platforms.
  128. #define STKSIZ (8 * sizeof(void*) - 2)
  129.  
  130.  
  131.  
  132. // QuickSort function for sorting arrays.  The array is sorted in place.
  133. // Parameters:
  134. //  * base:  Pointer to the initial element of the array
  135. //  * num:   Number of elements in the array
  136. //  * width: Width of each element in the array, in bytes
  137. //  * comp:  Pointer to a function returning analog of strcmp for strings, but
  138. //           supplied by the caller for comparing the array elements.  It
  139. //           accepts two pointers to elements; returns negative if 1 < 2;
  140. //           zero if 1 == 2, and positive if 1 > 2.
  141. #ifndef _M_CEE
  142. extern "C"
  143. #endif
  144. _CRT_SECURITYSAFECRITICAL_ATTRIBUTE
  145. #ifdef __USE_CONTEXT
  146. void __fileDECL qsort_s(
  147.     void*  const base,
  148.     size_t const num,
  149.     size_t const width,
  150.     int (__fileDECL* const comp)(void*, void const*, void const*),
  151.     void*  const context
  152.     )
  153. #else // __USE_CONTEXT
  154. void __fileDECL qsort(
  155.     void*  const base,
  156.     size_t const num,
  157.     size_t const width,
  158.     int (__fileDECL* const comp)(void const*, void const*)
  159.     )
  160. #endif // __USE_CONTEXT
  161. {
  162.     _VALIDATE_RETURN_VOID(base != nullptr || num == 0, EINVAL);
  163.     _VALIDATE_RETURN_VOID(width > 0, EINVAL);
  164.     _VALIDATE_RETURN_VOID(comp != nullptr, EINVAL);
  165.  
  166.     // A stack for saving the sub-arrays yet to be processed:
  167.     char* lostk[STKSIZ];
  168.     char* histk[STKSIZ];
  169.     int stkptr = 0;
  170.  
  171.     if (num < 2)
  172.         return; // Nothing to do:
  173.  
  174.     // The ends of the sub-array currently being sorted (note that 'hi' points
  175.     // to the last element, not one-past-the-end):
  176.     char* lo = static_cast<char*>(base);
  177.     char* hi = static_cast<char*>(base) + width * (num-1);
  178.  
  179.     // This entry point is for pseudo-recursion calling: setting
  180.     // lo and hi and jumping to here is like recursion, but stkptr is
  181.     // preserved, locals aren't, so we preserve stuff on the stack.
  182. recurse:
  183.  
  184.     // The number of elements in the sub-array currently being sorted:
  185.     size_t const size = (hi - lo) / width + 1;
  186.  
  187.     // Below a certain size, it is faster to use a O(n^2) sorting method:
  188.     if (size <= CUTOFF)
  189.     {
  190.         __SHORTSORT(lo, hi, width, comp, context);
  191.     }
  192.     else
  193.     {
  194.         // First we pick a partitioning element.  The efficiency of the
  195.         // algorithm demands that we find one that is approximately the median
  196.         // of the values, but also that we select one fast.  We choose the
  197.         // median of the first, middle, and last elements, to avoid bad
  198.         // performance in the face of already sorted data, or data that is made
  199.         // up of multiple sorted runs appended together.  Testing shows that a
  200.         // median-of-three algorithm provides better performance than simply
  201.         // picking the middle element for the latter case.
  202.  
  203.         // Find the middle element:
  204.         char* mid = lo + (size / 2) * width;
  205.  
  206.         // Sort the first, middle, last elements into order:
  207.         if (__COMPARE(context, lo, mid) > 0)
  208.             swap(lo, mid, width);
  209.  
  210.         if (__COMPARE(context, lo, hi) > 0)
  211.             swap(lo, hi, width);
  212.  
  213.         if (__COMPARE(context, mid, hi) > 0)
  214.             swap(mid, hi, width);
  215.  
  216.         // We now wish to partition the array into three pieces, one consisting
  217.         // of elements <= partition element, one of elements equal to the
  218.         // partition element, and one of elements > than it.  This is done
  219.         // below; comments indicate conditions established at every step.
  220.  
  221.         char* loguy = lo;
  222.         char* higuy = hi;
  223.  
  224.         // Note that higuy decreases and loguy increases on every iteration,
  225.         // so loop must terminate.
  226.         for (;;)
  227.         {
  228.             // lo <= loguy < hi, lo < higuy <= hi,
  229.             // A[i] <= A[mid] for lo <= i <= loguy,
  230.             // A[i] > A[mid] for higuy <= i < hi,
  231.             // A[hi] >= A[mid]
  232.  
  233.             // The doubled loop is to avoid calling comp(mid,mid), since some
  234.             // existing comparison funcs don't work when passed the same
  235.             // value for both pointers.
  236.  
  237.             if (mid > loguy)
  238.             {
  239.                 do
  240.                 {
  241.                     loguy += width;
  242.                 }
  243.                 while (loguy < mid && __COMPARE(context, loguy, mid) <= 0);
  244.             }
  245.             if (mid <= loguy)
  246.             {
  247.                 do
  248.                 {
  249.                     loguy += width;
  250.                 }
  251.                 while (loguy <= hi && __COMPARE(context, loguy, mid) <= 0);
  252.             }
  253.  
  254.             // lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy,
  255.             // either loguy > hi or A[loguy] > A[mid]
  256.  
  257.             do
  258.             {
  259.                 higuy -= width;
  260.             }
  261.             while (higuy > mid && __COMPARE(context, higuy, mid) > 0);
  262.  
  263.             // lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi,
  264.             // either higuy == lo or A[higuy] <= A[mid]
  265.  
  266.             if (higuy < loguy)
  267.                 break;
  268.  
  269.             // if loguy > hi or higuy == lo, then we would have exited, so
  270.             // A[loguy] > A[mid], A[higuy] <= A[mid],
  271.             // loguy <= hi, higuy > lo
  272.  
  273.             swap(loguy, higuy, width);
  274.  
  275.             // If the partition element was moved, follow it.  Only need
  276.             // to check for mid == higuy, since before the swap,
  277.             // A[loguy] > A[mid] implies loguy != mid.
  278.  
  279.             if (mid == higuy)
  280.                 mid = loguy;
  281.  
  282.             // A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top
  283.             // of loop is re-established
  284.         }
  285.  
  286.         //     A[i] <= A[mid] for lo <= i < loguy,
  287.         //     A[i] > A[mid] for higuy < i < hi,
  288.         //     A[hi] >= A[mid]
  289.         //     higuy < loguy
  290.         // implying:
  291.         //     higuy == loguy-1
  292.         //     or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid]
  293.  
  294.         // Find adjacent elements equal to the partition element.  The
  295.         // doubled loop is to avoid calling comp(mid,mid), since some
  296.         // existing comparison funcs don't work when passed the same value
  297.         // for both pointers.
  298.  
  299.         higuy += width;
  300.         if (mid < higuy)
  301.         {
  302.             do
  303.             {
  304.                 higuy -= width;
  305.             }
  306.             while (higuy > mid && __COMPARE(context, higuy, mid) == 0);
  307.         }
  308.         if (mid >= higuy)
  309.         {
  310.             do
  311.             {
  312.                 higuy -= width;
  313.             }
  314.             while (higuy > lo && __COMPARE(context, higuy, mid) == 0);
  315.         }
  316.  
  317.         // OK, now we have the following:
  318.         //    higuy < loguy
  319.         //    lo <= higuy <= hi
  320.         //    A[i]  <= A[mid] for lo <= i <= higuy
  321.         //    A[i]  == A[mid] for higuy < i < loguy
  322.         //    A[i]  >  A[mid] for loguy <= i < hi
  323.         //    A[hi] >= A[mid] */
  324.  
  325.         // We've finished the partition, now we want to sort the subarrays
  326.         // [lo, higuy] and [loguy, hi].
  327.         // We do the smaller one first to minimize stack usage.
  328.         // We only sort arrays of length 2 or more.
  329.  
  330.         if (higuy - lo >= hi - loguy)
  331.         {
  332.             if (lo < higuy)
  333.             {
  334.                 // Save the big recursion for later:
  335.                 lostk[stkptr] = lo;
  336.                 histk[stkptr] = higuy;
  337.                 ++stkptr;
  338.             }
  339.  
  340.             if (loguy < hi)
  341.             {
  342.                 // Do the small recursion:
  343.                 lo = loguy;
  344.                 goto recurse;
  345.             }
  346.         }
  347.         else
  348.         {
  349.             if (loguy < hi)
  350.             {
  351.                 // Save the big recursion for later:
  352.                 lostk[stkptr] = loguy;
  353.                 histk[stkptr] = hi;
  354.                 ++stkptr;
  355.             }
  356.  
  357.             if (lo < higuy)
  358.             {
  359.                 // Do the small recursion:
  360.                 hi = higuy;
  361.                 goto recurse;
  362.             }
  363.         }
  364.     }
  365.  
  366.     // We have sorted the array, except for any pending sorts on the stack.
  367.     // Check if there are any, and sort them:
  368.     --stkptr;
  369.     if (stkptr >= 0)
  370.     {
  371.         // Pop sub-array from the stack:
  372.         lo = lostk[stkptr];
  373.         hi = histk[stkptr];
  374.         goto recurse;
  375.     }
  376.     else
  377.     {
  378.         // Otherwise, all sub-arrays have been sorted:
  379.         return;
  380.     }
  381. }
  382.  
  383. #undef __COMPARE
  384. #undef __SHORTSORT

Comments