daily pastebin goal
49%
SHARE
TWEET

Untitled

a guest Sep 4th, 2010 125 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2. *qsort.c - quicksort algorithm; qsort() library function for sorting arrays
  3. *
  4. *   Copyright (c) Microsoft Corporation. All rights reserved.
  5. *
  6. *Purpose:
  7. *   To implement the qsort() routine for sorting arrays.
  8. *
  9. *******************************************************************************/
  10.  
  11. #include <stdlib.h>
  12. #include <search.h>
  13. #include <internal.h>
  14.  
  15. /* Always compile this module for speed, not size */
  16. #pragma optimize("t", on)
  17.  
  18. #if defined (_M_CEE)
  19. #define __fileDECL  __clrcall
  20. #else  /* defined (_M_CEE) */
  21. #define __fileDECL  __cdecl
  22. #endif  /* defined (_M_CEE) */
  23.  
  24. /* when building Managed Run time dll, we should be defining __cdecl
  25.  * to __clrcall. Also note that when compiling for MRT, we are compiling
  26.  * as C++ file.
  27.  */
  28.  
  29. /* prototypes for local routines */
  30. #ifdef __USE_CONTEXT
  31. static void __fileDECL shortsort_s(char *lo, char *hi, size_t width,
  32.                 int (__fileDECL *comp)(void *, const void *, const void *), void *);
  33. #define swap swap_c
  34. #else  /* __USE_CONTEXT */
  35. static void __fileDECL shortsort(char *lo, char *hi, size_t width,
  36.                 int (__fileDECL *comp)(const void *, const void *));
  37. #endif  /* __USE_CONTEXT */
  38.  
  39. static void __fileDECL swap(char *p, char *q, size_t width);
  40.  
  41. /* this parameter defines the cutoff between using quick sort and
  42.    insertion sort for arrays; arrays with lengths shorter or equal to the
  43.    below value use insertion sort */
  44.  
  45. #define CUTOFF 8            /* testing shows that this is good value */
  46.  
  47. /* Note: the theoretical number of stack entries required is
  48.    no more than 1 + log2(num).  But we switch to insertion
  49.    sort for CUTOFF elements or less, so we really only need
  50.    1 + log2(num) - log2(CUTOFF) stack entries.  For a CUTOFF
  51.    of 8, that means we need no more than 30 stack entries for
  52.    32 bit platforms, and 62 for 64-bit platforms. */
  53. #define STKSIZ (8*sizeof(void*) - 2)
  54.  
  55. /***
  56. *qsort(base, num, wid, comp) - quicksort function for sorting arrays
  57. *
  58. *Purpose:
  59. *   quicksort the array of elements
  60. *   side effects:  sorts in place
  61. *   maximum array size is number of elements times size of elements,
  62. *   but is limited by the virtual address space of the processor
  63. *
  64. *Entry:
  65. *   char *base = pointer to base of array
  66. *   size_t num  = number of elements in the array
  67. *   size_t width = width in bytes of each array element
  68. *   int (*comp)() = pointer to function returning analog of strcmp for
  69. *           strings, but supplied by user for comparing the array elements.
  70. *           it accepts 2 pointers to elements.
  71. *           Returns neg if 1<2, 0 if 1=2, pos if 1>2.
  72. *
  73. *Exit:
  74. *   returns void
  75. *
  76. *Exceptions:
  77. *   Input parameters are validated. Refer to the validation section of the function.
  78. *
  79. *******************************************************************************/
  80.  
  81. #ifdef __USE_CONTEXT
  82. #define __COMPARE(context, p1, p2) comp(context, p1, p2)
  83. #define __SHORTSORT(lo, hi, width, comp, context) shortsort_s(lo, hi, width, comp, context);
  84. #else  /* __USE_CONTEXT */
  85. #define __COMPARE(context, p1, p2) comp(p1, p2)
  86. #define __SHORTSORT(lo, hi, width, comp, context) shortsort(lo, hi, width, comp);
  87. #endif  /* __USE_CONTEXT */
  88.  
  89. #ifdef __USE_CONTEXT
  90. void __fileDECL qsort_s (
  91.     void *base,
  92.     size_t num,
  93.     size_t width,
  94.     int (__fileDECL *comp)(void *, const void *, const void *),
  95.     void *context
  96.     )
  97. #else  /* __USE_CONTEXT */
  98. void __fileDECL qsort (
  99.     void *base,
  100.     size_t num,
  101.     size_t width,
  102.     int (__fileDECL *comp)(const void *, const void *)
  103.     )
  104. #endif  /* __USE_CONTEXT */
  105. {
  106.     char *lo, *hi;              /* ends of sub-array currently sorting */
  107.     char *mid;                  /* points to middle of subarray */
  108.     char *loguy, *higuy;        /* traveling pointers for partition step */
  109.     size_t size;                /* size of the sub-array */
  110.     char *lostk[STKSIZ], *histk[STKSIZ];
  111.     int stkptr;                 /* stack for saving sub-array to be processed */
  112.  
  113.     /* validation section */
  114.     _VALIDATE_RETURN_VOID(base != NULL || num == 0, EINVAL);
  115.     _VALIDATE_RETURN_VOID(width > 0, EINVAL);
  116.     _VALIDATE_RETURN_VOID(comp != NULL, EINVAL);
  117.  
  118.     if (num < 2)
  119.         return;                 /* nothing to do */
  120.  
  121.     stkptr = 0;                 /* initialize stack */
  122.  
  123.     lo = (char *)base;
  124.     hi = (char *)base + width * (num-1);        /* initialize limits */
  125.  
  126.     /* this entry point is for pseudo-recursion calling: setting
  127.        lo and hi and jumping to here is like recursion, but stkptr is
  128.        preserved, locals aren't, so we preserve stuff on the stack */
  129. recurse:
  130.  
  131.     size = (hi - lo) / width + 1;        /* number of el's to sort */
  132.  
  133.     /* below a certain size, it is faster to use a O(n^2) sorting method */
  134.     if (size <= CUTOFF) {
  135.         __SHORTSORT(lo, hi, width, comp, context);
  136.     }
  137.     else {
  138.         /* First we pick a partitioning element.  The efficiency of the
  139.            algorithm demands that we find one that is approximately the median
  140.            of the values, but also that we select one fast.  We choose the
  141.            median of the first, middle, and last elements, to avoid bad
  142.            performance in the face of already sorted data, or data that is made
  143.            up of multiple sorted runs appended together.  Testing shows that a
  144.            median-of-three algorithm provides better performance than simply
  145.            picking the middle element for the latter case. */
  146.  
  147.         mid = lo + (size / 2) * width;      /* find middle element */
  148.  
  149.         /* Sort the first, middle, last elements into order */
  150.         if (__COMPARE(context, lo, mid) > 0) {
  151.             swap(lo, mid, width);
  152.         }
  153.         if (__COMPARE(context, lo, hi) > 0) {
  154.             swap(lo, hi, width);
  155.         }
  156.         if (__COMPARE(context, mid, hi) > 0) {
  157.             swap(mid, hi, width);
  158.         }
  159.  
  160.         /* We now wish to partition the array into three pieces, one consisting
  161.            of elements <= partition element, one of elements equal to the
  162.            partition element, and one of elements > than it.  This is done
  163.            below; comments indicate conditions established at every step. */
  164.  
  165.         loguy = lo;
  166.         higuy = hi;
  167.  
  168.         /* Note that higuy decreases and loguy increases on every iteration,
  169.            so loop must terminate. */
  170.         for (;;) {
  171.             /* lo <= loguy < hi, lo < higuy <= hi,
  172.                A[i] <= A[mid] for lo <= i <= loguy,
  173.                A[i] > A[mid] for higuy <= i < hi,
  174.                A[hi] >= A[mid] */
  175.  
  176.             /* The doubled loop is to avoid calling comp(mid,mid), since some
  177.                existing comparison funcs don't work when passed the same
  178.                value for both pointers. */
  179.  
  180.             if (mid > loguy) {
  181.                 do  {
  182.                     loguy += width;
  183.                 } while (loguy < mid && __COMPARE(context, loguy, mid) <= 0);
  184.             }
  185.             if (mid <= loguy) {
  186.                 do  {
  187.                     loguy += width;
  188.                 } while (loguy <= hi && __COMPARE(context, loguy, mid) <= 0);
  189.             }
  190.  
  191.             /* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy,
  192.                either loguy > hi or A[loguy] > A[mid] */
  193.  
  194.             do  {
  195.                 higuy -= width;
  196.             } while (higuy > mid && __COMPARE(context, higuy, mid) > 0);
  197.  
  198.             /* lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi,
  199.                either higuy == lo or A[higuy] <= A[mid] */
  200.  
  201.             if (higuy < loguy)
  202.                 break;
  203.  
  204.             /* if loguy > hi or higuy == lo, then we would have exited, so
  205.                A[loguy] > A[mid], A[higuy] <= A[mid],
  206.                loguy <= hi, higuy > lo */
  207.  
  208.             swap(loguy, higuy, width);
  209.  
  210.             /* If the partition element was moved, follow it.  Only need
  211.                to check for mid == higuy, since before the swap,
  212.                A[loguy] > A[mid] implies loguy != mid. */
  213.  
  214.             if (mid == higuy)
  215.                 mid = loguy;
  216.  
  217.             /* A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top
  218.                of loop is re-established */
  219.         }
  220.  
  221.         /*     A[i] <= A[mid] for lo <= i < loguy,
  222.                A[i] > A[mid] for higuy < i < hi,
  223.                A[hi] >= A[mid]
  224.                higuy < loguy
  225.            implying:
  226.                higuy == loguy-1
  227.                or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid] */
  228.  
  229.         /* Find adjacent elements equal to the partition element.  The
  230.            doubled loop is to avoid calling comp(mid,mid), since some
  231.            existing comparison funcs don't work when passed the same value
  232.            for both pointers. */
  233.  
  234.         higuy += width;
  235.         if (mid < higuy) {
  236.             do  {
  237.                 higuy -= width;
  238.             } while (higuy > mid && __COMPARE(context, higuy, mid) == 0);
  239.         }
  240.         if (mid >= higuy) {
  241.             do  {
  242.                 higuy -= width;
  243.             } while (higuy > lo && __COMPARE(context, higuy, mid) == 0);
  244.         }
  245.  
  246.         /* OK, now we have the following:
  247.               higuy < loguy
  248.               lo <= higuy <= hi
  249.               A[i]  <= A[mid] for lo <= i <= higuy
  250.               A[i]  == A[mid] for higuy < i < loguy
  251.               A[i]  >  A[mid] for loguy <= i < hi
  252.               A[hi] >= A[mid] */
  253.  
  254.         /* We've finished the partition, now we want to sort the subarrays
  255.            [lo, higuy] and [loguy, hi].
  256.            We do the smaller one first to minimize stack usage.
  257.            We only sort arrays of length 2 or more.*/
  258.  
  259.         if ( higuy - lo >= hi - loguy ) {
  260.             if (lo < higuy) {
  261.                 lostk[stkptr] = lo;
  262.                 histk[stkptr] = higuy;
  263.                 ++stkptr;
  264.             }                           /* save big recursion for later */
  265.  
  266.             if (loguy < hi) {
  267.                 lo = loguy;
  268.                 goto recurse;           /* do small recursion */
  269.             }
  270.         }
  271.         else {
  272.             if (loguy < hi) {
  273.                 lostk[stkptr] = loguy;
  274.                 histk[stkptr] = hi;
  275.                 ++stkptr;               /* save big recursion for later */
  276.             }
  277.  
  278.             if (lo < higuy) {
  279.                 hi = higuy;
  280.                 goto recurse;           /* do small recursion */
  281.             }
  282.         }
  283.     }
  284.  
  285.     /* We have sorted the array, except for any pending sorts on the stack.
  286.        Check if there are any, and do them. */
  287.  
  288.     --stkptr;
  289.     if (stkptr >= 0) {
  290.         lo = lostk[stkptr];
  291.         hi = histk[stkptr];
  292.         goto recurse;           /* pop subarray from stack */
  293.     }
  294.     else
  295.         return;                 /* all subarrays done */
  296. }
  297.  
  298.  
  299. /***
  300. *shortsort(hi, lo, width, comp) - insertion sort for sorting short arrays
  301. *shortsort_s(hi, lo, width, comp, context) - insertion sort for sorting short arrays
  302. *
  303. *Purpose:
  304. *       sorts the sub-array of elements between lo and hi (inclusive)
  305. *       side effects:  sorts in place
  306. *       assumes that lo < hi
  307. *
  308. *Entry:
  309. *       char *lo = pointer to low element to sort
  310. *       char *hi = pointer to high element to sort
  311. *       size_t width = width in bytes of each array element
  312. *       int (*comp)() = pointer to function returning analog of strcmp for
  313. *               strings, but supplied by user for comparing the array elements.
  314. *               it accepts 2 pointers to elements, together with a pointer to a context
  315. *               (if present). Returns neg if 1<2, 0 if 1=2, pos if 1>2.
  316. *       void *context - pointer to the context in which the function is
  317. *               called. This context is passed to the comparison function.
  318. *
  319. *Exit:
  320. *       returns void
  321. *
  322. *Exceptions:
  323. *
  324. *******************************************************************************/
  325.  
  326. #ifdef __USE_CONTEXT
  327. static void __fileDECL shortsort_s (
  328.     char *lo,
  329.     char *hi,
  330.     size_t width,
  331.     int (__fileDECL *comp)(void *, const void *, const void *),
  332.     void * context
  333.     )
  334. #else  /* __USE_CONTEXT */
  335. static void __fileDECL shortsort (
  336.     char *lo,
  337.     char *hi,
  338.     size_t width,
  339.     int (__fileDECL *comp)(const void *, const void *)
  340.     )
  341. #endif  /* __USE_CONTEXT */
  342. {
  343.     char *p, *max;
  344.  
  345.     /* Note: in assertions below, i and j are alway inside original bound of
  346.        array to sort. */
  347.  
  348.     while (hi > lo) {
  349.         /* A[i] <= A[j] for i <= j, j > hi */
  350.         max = lo;
  351.         for (p = lo+width; p <= hi; p += width) {
  352.             /* A[i] <= A[max] for lo <= i < p */
  353.             if (__COMPARE(context, p, max) > 0) {
  354.                 max = p;
  355.             }
  356.             /* A[i] <= A[max] for lo <= i <= p */
  357.         }
  358.  
  359.         /* A[i] <= A[max] for lo <= i <= hi */
  360.  
  361.         swap(max, hi, width);
  362.  
  363.         /* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */
  364.  
  365.         hi -= width;
  366.  
  367.         /* A[i] <= A[j] for i <= j, j > hi, loop top condition established */
  368.     }
  369.     /* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
  370.        so array is sorted */
  371. }
  372.  
  373. /***
  374. *swap(a, b, width) - swap two elements
  375. *
  376. *Purpose:
  377. *       swaps the two array elements of size width
  378. *
  379. *Entry:
  380. *       char *a, *b = pointer to two elements to swap
  381. *       size_t width = width in bytes of each array element
  382. *
  383. *Exit:
  384. *       returns void
  385. *
  386. *Exceptions:
  387. *
  388. *******************************************************************************/
  389.  
  390. static void __fileDECL swap (
  391.     char *a,
  392.     char *b,
  393.     size_t width
  394.     )
  395. {
  396.     char tmp;
  397.  
  398.     if ( a != b )
  399.         /* Do the swap one character at a time to avoid potential alignment
  400.            problems. */
  401.         while ( width-- ) {
  402.             tmp = *a;
  403.             *a++ = *b;
  404.             *b++ = tmp;
  405.         }
  406. }
  407.  
  408. #undef __fileDECL
  409. #undef __COMPARE
  410. #undef __SHORTSORT
  411. #undef swap
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top