Switch over to using our own qsort() all the time, as has been proposed

[postgresql] / src / port / qsort.c

diff --git a/src/port/qsort.c b/src/port/qsort.c
index 5562f603aa4c083486839e876b55a40d1ccfae36..3f3e7787e9fd2566ef4487af7bac8e939dc34dee 100644 (file)
--- a/src/port/qsort.c
+++ b/src/port/qsort.c
@@ -1,10 +1,18 @@
 /*
- *  Copied from NetBSD CVS, 2002-07-19, bjm
- *  Add do ... while() macro fix
- *  Remove __inline, _DIAGASSERTs
+ *     qsort.c: standard quicksort algorithm
+ *
+ *     Modifications from vanilla NetBSD source:
+ *       Add do ... while() macro fix
+ *       Remove __inline, _DIAGASSERTs, __P
+ *       Remove ill-considered "swap_cnt" switch to insertion sort,
+ *       in favor of a simple check for presorted input.
+ *
+ *     CAUTION: if you change this file, see also qsort_arg.c
+ *
+ *     $PostgreSQL: pgsql/src/port/qsort.c,v 1.10 2006/10/03 22:18:23 tgl Exp $
  */
 
-/*     $NetBSD: qsort.c,v 1.12 1999/09/20 04:39:40 lukem Exp $ */
+/*     $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $   */
 
 /*-
  * Copyright (c) 1992, 1993
@@ -18,11 +26,7 @@
  * 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.
- * 3. All advertising materials mentioning features or use of this software
- *       must display the following acknowledgement:
- *     This product includes software developed by the University of
- *     California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
+ * 3. 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.
  *
@@ -39,21 +43,21 @@
  * SUCH DAMAGE.
  */
 
-#include <sys/cdefs.h>
-#include <sys/types.h>
+#include "c.h"
 
-#include <assert.h>
-#include <errno.h>
-#include <stdlib.h>
 
-static char *med3 __P((char *, char *, char *,
-        int (*) (const void *, const void *)));
-static void swapfunc __P((char *, char *, size_t, int));
+static char *med3(char *, char *, char *,
+        int (*) (const void *, const void *));
+static void swapfunc(char *, char *, size_t, int);
 
-#define min(a, b)      (a) < (b) ? a : b
+#define min(a, b)      ((a) < (b) ? (a) : (b))
 
 /*
- * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function".
+ * Qsort routine based on J. L. Bentley and M. D. McIlroy,
+ * "Engineering a sort function",
+ * Software--Practice and Experience 23 (1993) 1249-1265.
+ * We have modified their original by adding a check for already-sorted input,
+ * which seems to be a win per discussions on pgsql-hackers around 2006-03-21.
  */
 #define swapcode(TYPE, parmi, parmj, n) \
 do {           \
@@ -67,8 +71,8 @@ do {          \
                } while (--i > 0);                              \
 } while (0)
 
-#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
-       es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;
+#define SWAPINIT(a, es) swaptype = ((char *)(a) - (char *)0) % sizeof(long) || \
+       (es) % sizeof(long) ? 2 : (es) == sizeof(long)? 0 : 1;
 
 static void
 swapfunc(a, b, n, swaptype)
@@ -98,7 +102,7 @@ med3(a, b, c, cmp)
 char      *a,
                   *b,
                   *c;
-int                    (*cmp) __P((const void *, const void *));
+int                    (*cmp) (const void *, const void *);
 {
        return cmp(a, b) < 0 ?
                (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a))
@@ -110,7 +114,7 @@ qsort(a, n, es, cmp)
 void      *a;
 size_t         n,
                        es;
-int                    (*cmp) __P((const void *, const void *));
+int                    (*cmp) (const void *, const void *);
 {
        char       *pa,
                           *pb,
@@ -122,10 +126,9 @@ int                        (*cmp) __P((const void *, const void *));
        int                     d,
                                r,
                                swaptype,
-                               swap_cnt;
+                               presorted;
 
 loop:SWAPINIT(a, es);
-       swap_cnt = 0;
        if (n < 7)
        {
                for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
@@ -134,6 +137,17 @@ loop:SWAPINIT(a, es);
                                swap(pl, pl - es);
                return;
        }
+       presorted = 1;
+       for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
+       {
+               if (cmp(pm - es, pm) > 0)
+               {
+                       presorted = 0;
+                       break;
+               }
+       }
+       if (presorted)
+               return;
        pm = (char *) a + (n / 2) * es;
        if (n > 7)
        {
@@ -150,7 +164,6 @@ loop:SWAPINIT(a, es);
        }
        swap(a, pm);
        pa = pb = (char *) a + es;
-
        pc = pd = (char *) a + (n - 1) * es;
        for (;;)
        {
@@ -158,7 +171,6 @@ loop:SWAPINIT(a, es);
                {
                        if (r == 0)
                        {
-                               swap_cnt = 1;
                                swap(pa, pb);
                                pa += es;
                        }
@@ -168,7 +180,6 @@ loop:SWAPINIT(a, es);
                {
                        if (r == 0)
                        {
-                               swap_cnt = 1;
                                swap(pc, pd);
                                pd -= es;
                        }
@@ -177,19 +188,9 @@ loop:SWAPINIT(a, 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;
-       }
-
        pn = (char *) a + n * es;
        r = min(pa - (char *) a, pb - pa);
        vecswap(a, pb - r, r);