Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | Download | RSS feed

  1. static void shortsort(char *lo, char *hi, unsigned width,
  2.                 int (*comp)(const void *, const void *));
  3.  
  4. static void swap(char *p, char *q, unsigned width);
  5.  
  6. /* this parameter defines the cutoff between using quick sort and
  7.    insertion sort for arrays; arrays with lengths shorter or equal to the
  8.    below value use insertion sort */
  9.  
  10. #define CUTOFF 8            /* testing shows that this is good value */
  11.  
  12. #define STKSIZ (8*sizeof(void*) - 2)
  13.  
  14. /***
  15. *qsort(base, num, wid, comp) - quicksort function for sorting arrays
  16. *
  17. *Purpose:
  18. *   quicksort the array of elements
  19. *   side effects:  sorts in place
  20. *   maximum array size is number of elements times size of elements,
  21. *   but is limited by the virtual address space of the processor
  22. *
  23. *Entry:
  24. *   char *base = pointer to base of array
  25. *   unsigned num  = number of elements in the array
  26. *   unsigned width = width in bytes of each array element
  27. *   int (*comp)() = pointer to function returning analog of strcmp for
  28. *           strings, but supplied by user for comparing the array elements.
  29. *           it accepts 2 pointers to elements.
  30. *           Returns neg if 1<2, 0 if 1=2, pos if 1>2.
  31. *
  32. *Exit:
  33. *   returns void
  34. *
  35. *******************************************************************************/
  36.  
  37. void qsort (
  38.     void *base,
  39.     unsigned num,
  40.     unsigned width,
  41.     int (*comp)(const void *, const void *)
  42.     )
  43. {
  44.     /* Note: the number of stack entries required is no more than
  45.        1 + log2(num), so 30 is sufficient for any array */
  46.     char *lo, *hi;              /* ends of sub-array currently sorting */
  47.     char *mid;                  /* points to middle of subarray */
  48.     char *loguy, *higuy;        /* traveling pointers for partition step */
  49.     unsigned size;              /* size of the sub-array */
  50.     char *lostk[STKSIZ], *histk[STKSIZ];
  51.     int stkptr;                 /* stack for saving sub-array to be processed */
  52.  
  53.     if (num < 2)
  54.         return;                 /* nothing to do */
  55.  
  56.     stkptr = 0;                 /* initialize stack */
  57.  
  58.     lo = (char *)base;
  59.     hi = (char *)base + width * (num-1);        /* initialize limits */
  60.  
  61.     /* this entry point is for pseudo-recursion calling: setting
  62.        lo and hi and jumping to here is like recursion, but stkptr is
  63.        preserved, locals aren't, so we preserve stuff on the stack */
  64. recurse:
  65.  
  66.     size = (hi - lo) / width + 1;        /* number of el's to sort */
  67.  
  68.     /* below a certain size, it is faster to use a O(n^2) sorting method */
  69.     if (size <= CUTOFF) {
  70.         shortsort(lo, hi, width, comp);
  71.     }
  72.     else {
  73.         /* First we pick a partitioning element.  The efficiency of the
  74.            algorithm demands that we find one that is approximately the median
  75.            of the values, but also that we select one fast.  We choose the
  76.            median of the first, middle, and last elements, to avoid bad
  77.            performance in the face of already sorted data, or data that is made
  78.            up of multiple sorted runs appended together.  Testing shows that a
  79.            median-of-three algorithm provides better performance than simply
  80.            picking the middle element for the latter case. */
  81.  
  82.         mid = lo + (size / 2) * width;      /* find middle element */
  83.  
  84.         /* Sort the first, middle, last elements into order */
  85.         if (comp(lo, mid) > 0) {
  86.             swap(lo, mid, width);
  87.         }
  88.         if (comp(lo, hi) > 0) {
  89.             swap(lo, hi, width);
  90.         }
  91.         if (comp(mid, hi) > 0) {
  92.             swap(mid, hi, width);
  93.         }
  94.  
  95.         /* We now wish to partition the array into three pieces, one consisting
  96.            of elements <= partition element, one of elements equal to the
  97.            partition element, and one of elements > than it.  This is done
  98.            below; comments indicate conditions established at every step. */
  99.  
  100.         loguy = lo;
  101.         higuy = hi;
  102.  
  103.         /* Note that higuy decreases and loguy increases on every iteration,
  104.            so loop must terminate. */
  105.         for (;;) {
  106.             /* lo <= loguy < hi, lo < higuy <= hi,
  107.                A[i] <= A[mid] for lo <= i <= loguy,
  108.                A[i] > A[mid] for higuy <= i < hi,
  109.                A[hi] >= A[mid] */
  110.  
  111.             /* The doubled loop is to avoid calling comp(mid,mid), since some
  112.                existing comparison funcs don't work when passed the same
  113.                value for both pointers. */
  114.  
  115.             if (mid > loguy) {
  116.                 do  {
  117.                     loguy += width;
  118.                 } while (loguy < mid && comp(loguy, mid) <= 0);
  119.             }
  120.             if (mid <= loguy) {
  121.                 do  {
  122.                     loguy += width;
  123.                 } while (loguy <= hi && comp(loguy, mid) <= 0);
  124.             }
  125.  
  126.             /* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy,
  127.                either loguy > hi or A[loguy] > A[mid] */
  128.  
  129.             do  {
  130.                 higuy -= width;
  131.             } while (higuy > mid && comp(higuy, mid) > 0);
  132.  
  133.             /* lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi,
  134.                either higuy == lo or A[higuy] <= A[mid] */
  135.  
  136.             if (higuy < loguy)
  137.                 break;
  138.  
  139.             /* if loguy > hi or higuy == lo, then we would have exited, so
  140.                A[loguy] > A[mid], A[higuy] <= A[mid],
  141.                loguy <= hi, higuy > lo */
  142.  
  143.             swap(loguy, higuy, width);
  144.  
  145.             /* If the partition element was moved, follow it.  Only need
  146.                to check for mid == higuy, since before the swap,
  147.                A[loguy] > A[mid] implies loguy != mid. */
  148.  
  149.             if (mid == higuy)
  150.                 mid = loguy;
  151.  
  152.             /* A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top
  153.                of loop is re-established */
  154.         }
  155.  
  156.         /*     A[i] <= A[mid] for lo <= i < loguy,
  157.                A[i] > A[mid] for higuy < i < hi,
  158.                A[hi] >= A[mid]
  159.                higuy < loguy
  160.            implying:
  161.                higuy == loguy-1
  162.                or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid] */
  163.  
  164.         /* Find adjacent elements equal to the partition element.  The
  165.            doubled loop is to avoid calling comp(mid,mid), since some
  166.            existing comparison funcs don't work when passed the same value
  167.            for both pointers. */
  168.  
  169.         higuy += width;
  170.         if (mid < higuy) {
  171.             do  {
  172.                 higuy -= width;
  173.             } while (higuy > mid && comp(higuy, mid) == 0);
  174.         }
  175.         if (mid >= higuy) {
  176.             do  {
  177.                 higuy -= width;
  178.             } while (higuy > lo && comp(higuy, mid) == 0);
  179.         }
  180.  
  181.         /* OK, now we have the following:
  182.               higuy < loguy
  183.               lo <= higuy <= hi
  184.               A[i]  <= A[mid] for lo <= i <= higuy
  185.               A[i]  == A[mid] for higuy < i < loguy
  186.               A[i]  >  A[mid] for loguy <= i < hi
  187.               A[hi] >= A[mid] */
  188.  
  189.         /* We've finished the partition, now we want to sort the subarrays
  190.            [lo, higuy] and [loguy, hi].
  191.            We do the smaller one first to minimize stack usage.
  192.            We only sort arrays of length 2 or more.*/
  193.  
  194.         if ( higuy - lo >= hi - loguy ) {
  195.             if (lo < higuy) {
  196.                 lostk[stkptr] = lo;
  197.                 histk[stkptr] = higuy;
  198.                 ++stkptr;
  199.             }                           /* save big recursion for later */
  200.  
  201.             if (loguy < hi) {
  202.                 lo = loguy;
  203.                 goto recurse;           /* do small recursion */
  204.             }
  205.         }
  206.         else {
  207.             if (loguy < hi) {
  208.                 lostk[stkptr] = loguy;
  209.                 histk[stkptr] = hi;
  210.                 ++stkptr;               /* save big recursion for later */
  211.             }
  212.  
  213.             if (lo < higuy) {
  214.                 hi = higuy;
  215.                 goto recurse;           /* do small recursion */
  216.             }
  217.         }
  218.     }
  219.  
  220.     /* We have sorted the array, except for any pending sorts on the stack.
  221.        Check if there are any, and do them. */
  222.  
  223.     --stkptr;
  224.     if (stkptr >= 0) {
  225.         lo = lostk[stkptr];
  226.         hi = histk[stkptr];
  227.         goto recurse;           /* pop subarray from stack */
  228.     }
  229.     else
  230.         return;                 /* all subarrays done */
  231. }
  232.  
  233.  
  234. /***
  235. *shortsort(hi, lo, width, comp) - insertion sort for sorting short arrays
  236. *shortsort_s(hi, lo, width, comp, context) - insertion sort for sorting short arrays
  237. *
  238. *Purpose:
  239. *       sorts the sub-array of elements between lo and hi (inclusive)
  240. *       side effects:  sorts in place
  241. *       assumes that lo < hi
  242. *
  243. *Entry:
  244. *       char *lo = pointer to low element to sort
  245. *       char *hi = pointer to high element to sort
  246. *       unsigned width = width in bytes of each array element
  247. *       int (*comp)() = pointer to function returning analog of strcmp for
  248. *               strings, but supplied by user for comparing the array elements.
  249. *               it accepts 2 pointers to elements, together with a pointer to a context
  250. *               (if present). Returns neg if 1<2, 0 if 1=2, pos if 1>2.
  251. *       void *context - pointer to the context in which the function is
  252. *               called. This context is passed to the comparison function.
  253. *
  254. *Exit:
  255. *       returns void
  256. *
  257. *Exceptions:
  258. *
  259. *******************************************************************************/
  260.  
  261. static void shortsort (
  262.     char *lo,
  263.     char *hi,
  264.     unsigned width,
  265.     int (*comp)(const void *, const void *)
  266.     )
  267. {
  268.     char *p, *max;
  269.  
  270.     /* Note: in assertions below, i and j are alway inside original bound of
  271.        array to sort. */
  272.  
  273.     while (hi > lo) {
  274.         /* A[i] <= A[j] for i <= j, j > hi */
  275.         max = lo;
  276.         for (p = lo+width; p <= hi; p += width) {
  277.             /* A[i] <= A[max] for lo <= i < p */
  278.             if (comp(p, max) > 0) {
  279.                 max = p;
  280.             }
  281.             /* A[i] <= A[max] for lo <= i <= p */
  282.         }
  283.  
  284.         /* A[i] <= A[max] for lo <= i <= hi */
  285.  
  286.         swap(max, hi, width);
  287.  
  288.         /* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */
  289.  
  290.         hi -= width;
  291.  
  292.         /* A[i] <= A[j] for i <= j, j > hi, loop top condition established */
  293.     }
  294.     /* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
  295.        so array is sorted */
  296. }
  297.  
  298. /***
  299. *swap(a, b, width) - swap two elements
  300. *
  301. *Purpose:
  302. *       swaps the two array elements of size width
  303. *
  304. *Entry:
  305. *       char *a, *b = pointer to two elements to swap
  306. *       unsigned width = width in bytes of each array element
  307. *
  308. *Exit:
  309. *       returns void
  310. *
  311. *Exceptions:
  312. *
  313. *******************************************************************************/
  314.  
  315. static void swap (
  316.     char *a,
  317.     char *b,
  318.     unsigned width
  319.     )
  320. {
  321.     char tmp;
  322.  
  323.     if ( a != b )
  324.         /* Do the swap one character at a time to avoid potential alignment
  325.            problems. */
  326.         while ( width-- ) {
  327.             tmp = *a;
  328.             *a++ = *b;
  329.             *b++ = tmp;
  330.         }
  331. }
  332.