[CRT] Reimplement qsort() using FreeBSD implementation.
authorPierre Schweitzer <pierre@reactos.org>
Sat, 2 Jun 2018 11:52:09 +0000 (13:52 +0200)
committerPierre Schweitzer <pierre@reactos.org>
Sat, 2 Jun 2018 11:56:42 +0000 (13:56 +0200)
Our implementation had a bug that could be triggered while
building our USBD library on ReactOS: the compare function
could be called with a NULL pointer instead of a valid value.

With this bug fixed (and the cmd hack in CORE-14648), ReactOS
can totally selfhost :-)! I was able to build LiveCD and BootCD
without any trouble, crash, deadlock or whatever.
(Next step: having a buildbot slave hosted on ReactOS ;-)).

Enjoy: https://twitter.com/HeisSpiter/status/1002880397103988737

CORE-14680

sdk/lib/crt/stdlib/qsort.c

index 62f3651..d6bca5f 100644 (file)
-/* Copyright (C) 1994 DJ Delorie, see COPYING.DJ for details */
-
-#include <stdlib.h>
-#include <search.h>
-
 /*-
- * Copyright (c) 1980, 1983 The Regents of the University of California.
- * All rights reserved.
+ * Copyright (c) 1992, 1993
+ *     The Regents of the University of California.  All rights reserved.
  *
- * Redistribution and use in source and binary forms are permitted
- * provided that: (1) source distributions retain this entire copyright
- * notice and comment, and (2) distributions including binaries display
- * the following acknowledgement:  ``This product includes software
- * developed by the University of California, Berkeley and its contributors''
- * in the documentation or other materials provided with the distribution
- * and in all advertising materials mentioning features or use of this
- * software. Neither the name of the University nor the names of its
- * contributors may be used to endorse or promote products derived
- * from this software without specific prior written permission.
- * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
- * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
- * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 4. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
  */
 
-/*
- * qsort.c:
- * Our own version of the system qsort routine which is faster by an average
- * of 25%, with lows and highs of 10% and 50%.
- * The THRESHold below is the insertion sort threshold, and has been adjusted
- * for records of size 48 bytes.
- * The MTHREShold is where we stop finding a better median.
- */
+#include <stdlib.h>
+#include <search.h>
 
-#define                THRESH          4               /* threshold for insertion */
-#define                MTHRESH         6               /* threshold for median */
+#define min(a, b)      (a) < (b) ? (a) : (b)
 
 /*
- * qst:
- * Do a quicksort
- * First, find the median element, and put that one in the first place as the
- * discriminator.  (This "median" is just the median of the first, last and
- * middle elements).  (Using this median instead of the first element is a big
- * win).  Then, the usual partitioning/swapping, followed by moving the
- * discriminator into the right place.  Then, figure out the sizes of the two
- * partions, do the smaller one recursively and the larger one via a repeat of
- * this code.  Stopping when there are less than THRESH elements in a partition
- * and cleaning up with an insertion sort (in our caller) is a huge win.
- * All data swaps are done in-line, which is space-losing but time-saving.
- * (And there are only three places where this is done).
+ * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
  */
+#define swapcode(TYPE, parmi, parmj, n) {              \
+       long i = (n) / sizeof (TYPE);                   \
+       register TYPE *pi = (TYPE *) (parmi);           \
+       register TYPE *pj = (TYPE *) (parmj);           \
+       do {                                            \
+               register TYPE   t = *pi;                \
+               *pi++ = *pj;                            \
+               *pj++ = t;                              \
+        } while (--i > 0);                             \
+}
 
-static void __cdecl
-qst(size_t size, int (__cdecl *compar)(const void*, const void*), char *base, char *max)
+#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
+       es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
+
+static __inline void
+swapfunc(char *a, char *b, int n, int swaptype)
 {
-  char c, *i, *j, *jj;
-  size_t ii;
-  char *mid, *tmp;
-  size_t lo, hi;
-  size_t thresh;
-  size_t mthresh;
+       if(swaptype <= 1)
+               swapcode(long, a, b, n)
+       else
+               swapcode(char, a, b, n)
+}
 
-  thresh = size * THRESH;
-  mthresh = size * MTHRESH;
+#define swap(a, b)                                     \
+       if (swaptype == 0) {                            \
+               long t = *(long *)(a);                  \
+               *(long *)(a) = *(long *)(b);            \
+               *(long *)(b) = t;                       \
+       } else                                          \
+               swapfunc(a, b, es, swaptype)
 
-  /*
-   * At the top here, lo is the number of characters of elements in the
-   * current partition.  (Which should be max - base).
-   * Find the median of the first, last, and middle element and make
-   * that the middle element.  Set j to largest of first and middle.
-   * If max is larger than that guy, then it's that guy, else compare
-   * max with loser of first and take larger.  Things are set up to
-   * prefer the middle, then the first in case of ties.
-   */
-  lo = max - base;             /* number of elements as chars */
-  do   {
-    mid = i = base + size * ((lo / size) >> 1);
-    if (lo >= mthresh)
-    {
-      j = (compar((jj = base), i) > 0 ? jj : i);
-      if (compar(j, (tmp = max - size)) > 0)
-      {
-       /* switch to first loser */
-       j = (j == jj ? i : jj);
-       if (compar(j, tmp) < 0)
-         j = tmp;
-      }
-      if (j != i)
-      {
-       ii = size;
-       do      {
-         c = *i;
-         *i++ = *j;
-         *j++ = c;
-       } while (--ii);
-      }
-    }
-    /*
-     * Semi-standard quicksort partitioning/swapping
-     */
-    for (i = base, j = max - size; ; )
-    {
-      while (i < mid && compar(i, mid) <= 0)
-       i += size;
-      while (j > mid)
-      {
-       if (compar(mid, j) <= 0)
-       {
-         j -= size;
-         continue;
-       }
-       tmp = i + size; /* value of i after swap */
-       if (i == mid)
-       {
-         /* j <-> mid, new mid is j */
-         mid = jj = j;
-       }
-       else
-       {
-         /* i <-> j */
-         jj = j;
-         j -= size;
-       }
-       goto swap;
-      }
-      if (i == mid)
-      {
-       break;
-      }
-      else
-      {
-       /* i <-> mid, new mid is i */
-       jj = mid;
-       tmp = mid = i;          /* value of i after swap */
-       j -= size;
-      }
-    swap:
-      ii = size;
-      do       {
-       c = *i;
-       *i++ = *jj;
-       *jj++ = c;
-      } while (--ii);
-      i = tmp;
-    }
-    /*
-     * Look at sizes of the two partitions, do the smaller
-     * one first by recursion, then do the larger one by
-     * making sure lo is its size, base and max are update
-     * correctly, and branching back.  But only repeat
-     * (recursively or by branching) if the partition is
-     * of at least size THRESH.
-     */
-    i = (j = mid) + size;
-    if ((lo = j - base) <= (hi = max - i))
-    {
-      if (lo >= thresh)
-       qst(size, compar, base, j);
-      base = i;
-      lo = hi;
-    }
-    else
-    {
-      if (hi >= thresh)
-       qst(size, compar, i, max);
-      max = j;
-    }
-  } while (lo >= thresh);
+#define vecswap(a, b, n)       if ((n) > 0) swapfunc(a, b, n, swaptype)
+
+#define        CMP(x, y) (cmp((x), (y)))
+
+static __inline char *
+med3(char *a, char *b, char *c, int (__cdecl *cmp)(const void*, const void*))
+{
+       return CMP(a, b) < 0 ?
+              (CMP(b, c) < 0 ? b : (CMP(a, c) < 0 ? c : a ))
+              :(CMP(b, c) > 0 ? b : (CMP(a, c) < 0 ? a : c ));
 }
 
 /*
@@ -177,67 +88,79 @@ qst(size_t size, int (__cdecl *compar)(const void*, const void*), char *base, ch
  */
 void
 __cdecl
-qsort(void *base0, size_t n, size_t size, int (__cdecl *compar)(const void*, const void*))
+qsort(void *a, size_t n, size_t es, int (__cdecl *cmp)(const void*, const void*))
 {
-  char *base = (char *)base0;
-  char c, *i, *j, *lo, *hi;
-  char *min, *max;
-  size_t thresh;
+       char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
+       int d, r, swaptype, swap_cnt;
 
-  if (n <= 1)
-    return;
+loop:  SWAPINIT(a, es);
+       swap_cnt = 0;
+       if (n < 7) {
+               for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+                       for (pl = pm; pl > (char *)a && CMP(pl - es, pl) > 0;
+                            pl -= es)
+                               swap(pl, pl - es);
+               return;
+       }
+       pm = (char *)a + (n / 2) * es;
+       if (n > 7) {
+               pl = a;
+               pn = (char *)a + (n - 1) * es;
+               if (n > 40) {
+                       d = (n / 8) * es;
+                       pl = med3(pl, pl + d, pl + 2 * d, cmp);
+                       pm = med3(pm - d, pm, pm + d, cmp);
+                       pn = med3(pn - 2 * d, pn - d, pn, cmp);
+               }
+               pm = med3(pl, pm, pn, cmp);
+       }
+       swap(a, pm);
+       pa = pb = (char *)a + es;
+
+       pc = pd = (char *)a + (n - 1) * es;
+       for (;;) {
+               while (pb <= pc && (r = CMP(pb, a)) <= 0) {
+                       if (r == 0) {
+                               swap_cnt = 1;
+                               swap(pa, pb);
+                               pa += es;
+                       }
+                       pb += es;
+               }
+               while (pb <= pc && (r = CMP(pc, a)) >= 0) {
+                       if (r == 0) {
+                               swap_cnt = 1;
+                               swap(pc, pd);
+                               pd -= es;
+                       }
+                       pc -= es;
+               }
+               if (pb > pc)
+                       break;
+               swap(pb, pc);
+               swap_cnt = 1;
+               pb += es;
+               pc -= es;
+       }
+       if (swap_cnt == 0) {  /* Switch to insertion sort */
+               for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+                       for (pl = pm; pl > (char *)a && CMP(pl - es, pl) > 0;
+                            pl -= es)
+                               swap(pl, pl - es);
+               return;
+       }
 
-  if (size == 0)
-    return;
-  thresh = size * THRESH;
-  max = base + n * size;
-  if (n >= THRESH)
-  {
-    qst(size, compar, base, max);
-    hi = base + thresh;
-  }
-  else
-  {
-    hi = max;
-  }
-  /*
-   * First put smallest element, which must be in the first THRESH, in
-   * the first position as a sentinel.  This is done just by searching
-   * the first THRESH elements (or the first n if n < THRESH), finding
-   * the min, and swapping it into the first position.
-   */
-  for (j = lo = base; (lo += size) < hi; )
-    if (compar(j, lo) > 0)
-      j = lo;
-  if (j != base)
-  {
-    /* swap j into place */
-    for (i = base, hi = base + size; i < hi; )
-    {
-      c = *j;
-      *j++ = *i;
-      *i++ = c;
-    }
-  }
-  /*
-   * With our sentinel in place, we now run the following hyper-fast
-   * insertion sort.  For each remaining element, min, from [1] to [n-1],
-   * set hi to the index of the element AFTER which this one goes.
-   * Then, do the standard insertion sort shift on a character at a time
-   * basis for each element in the frob.
-   */
-  for (min = base; (hi = min += size) < max; )
-  {
-    while (compar(hi -= size, min) > 0)
-      /* void */;
-    if ((hi += size) != min) {
-      for (lo = min + size; --lo >= min; )
-      {
-       c = *lo;
-       for (i = j = lo; (j -= size) >= hi; i = j)
-         *i = *j;
-       *i = c;
-      }
-    }
-  }
+       pn = (char *)a + n * es;
+       r = min(pa - (char *)a, pb - pa);
+       vecswap(a, pb - r, r);
+       r = min(pd - pc, pn - pd - es);
+       vecswap(pb, pn - r, r);
+       if ((r = pb - pa) > es)
+               qsort(a, r / es, es, cmp);
+       if ((r = pd - pc) > es) {
+               /* Iterate rather than recurse to save stack space */
+               a = pn - r;
+               n = r / es;
+               goto loop;
+       }
 }