aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/Makefile.global.in4
-rw-r--r--src/backend/utils/sort/tuplesort.c73
-rw-r--r--src/include/port.h11
-rw-r--r--src/port/qsort.c6
-rw-r--r--src/port/qsort_arg.c201
5 files changed, 247 insertions, 48 deletions
diff --git a/src/Makefile.global.in b/src/Makefile.global.in
index 60493a8e4bf..4e55fe9bfdc 100644
--- a/src/Makefile.global.in
+++ b/src/Makefile.global.in
@@ -1,5 +1,5 @@
# -*-makefile-*-
-# $PostgreSQL: pgsql/src/Makefile.global.in,v 1.230 2006/09/19 15:36:07 tgl Exp $
+# $PostgreSQL: pgsql/src/Makefile.global.in,v 1.231 2006/10/03 22:18:22 tgl Exp $
#------------------------------------------------------------------------------
# All PostgreSQL makefiles include this file and use the variables it sets,
@@ -413,7 +413,7 @@ endif
#
# substitute implementations of C library routines (see src/port/)
-LIBOBJS = @LIBOBJS@ copydir.o dirmod.o exec.o noblock.o path.o pipe.o pgsleep.o pgstrcasecmp.o sprompt.o thread.o
+LIBOBJS = @LIBOBJS@ copydir.o dirmod.o exec.o noblock.o path.o pipe.o pgsleep.o pgstrcasecmp.o qsort.o qsort_arg.o sprompt.o thread.o
LIBS := -lpgport $(LIBS)
# add location of libpgport.a to LDFLAGS
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 7d503f244fb..08e63e0756d 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -91,7 +91,7 @@
* Portions Copyright (c) 1994, Regents of the University of California
*
* IDENTIFICATION
- * $PostgreSQL: pgsql/src/backend/utils/sort/tuplesort.c,v 1.68 2006/07/14 14:52:25 momjian Exp $
+ * $PostgreSQL: pgsql/src/backend/utils/sort/tuplesort.c,v 1.69 2006/10/03 22:18:23 tgl Exp $
*
*-------------------------------------------------------------------------
*/
@@ -201,11 +201,11 @@ struct Tuplesortstate
* They are set up by the tuplesort_begin_xxx routines.
*
* Function to compare two tuples; result is per qsort() convention, ie:
- *
- * <0, 0, >0 according as a<b, a=b, a>b.
+ * <0, 0, >0 according as a<b, a=b, a>b. The API must match
+ * qsort_arg_comparator.
*/
- int (*comparetup) (Tuplesortstate *state,
- const SortTuple *a, const SortTuple *b);
+ int (*comparetup) (const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state);
/*
* Function to copy a supplied input tuple into palloc'd space and set up
@@ -345,7 +345,7 @@ struct Tuplesortstate
#endif
};
-#define COMPARETUP(state,a,b) ((*(state)->comparetup) (state, a, b))
+#define COMPARETUP(state,a,b) ((*(state)->comparetup) (a, b, state))
#define COPYTUP(state,stup,tup) ((*(state)->copytup) (state, stup, tup))
#define WRITETUP(state,tape,stup) ((*(state)->writetup) (state, tape, stup))
#define READTUP(state,stup,tape,len) ((*(state)->readtup) (state, stup, tape, len))
@@ -410,37 +410,28 @@ static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple,
static void tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex);
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK);
static void markrunend(Tuplesortstate *state, int tapenum);
-static int qsort_comparetup(const void *a, const void *b);
-static int comparetup_heap(Tuplesortstate *state,
- const SortTuple *a, const SortTuple *b);
+static int comparetup_heap(const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state);
static void copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup);
static void writetup_heap(Tuplesortstate *state, int tapenum,
SortTuple *stup);
static void readtup_heap(Tuplesortstate *state, SortTuple *stup,
int tapenum, unsigned int len);
-static int comparetup_index(Tuplesortstate *state,
- const SortTuple *a, const SortTuple *b);
+static int comparetup_index(const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state);
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup);
static void writetup_index(Tuplesortstate *state, int tapenum,
SortTuple *stup);
static void readtup_index(Tuplesortstate *state, SortTuple *stup,
int tapenum, unsigned int len);
-static int comparetup_datum(Tuplesortstate *state,
- const SortTuple *a, const SortTuple *b);
+static int comparetup_datum(const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state);
static void copytup_datum(Tuplesortstate *state, SortTuple *stup, void *tup);
static void writetup_datum(Tuplesortstate *state, int tapenum,
SortTuple *stup);
static void readtup_datum(Tuplesortstate *state, SortTuple *stup,
int tapenum, unsigned int len);
-/*
- * Since qsort(3) will not pass any context info to qsort_comparetup(),
- * we have to use this ugly static variable. It is set to point to the
- * active Tuplesortstate object just before calling qsort. It should
- * not be used directly by anything except qsort_comparetup().
- */
-static Tuplesortstate *qsort_tuplesortstate;
-
/*
* tuplesort_begin_xxx
@@ -930,11 +921,11 @@ tuplesort_performsort(Tuplesortstate *state)
* amount of memory. Just qsort 'em and we're done.
*/
if (state->memtupcount > 1)
- {
- qsort_tuplesortstate = state;
- qsort((void *) state->memtuples, state->memtupcount,
- sizeof(SortTuple), qsort_comparetup);
- }
+ qsort_arg((void *) state->memtuples,
+ state->memtupcount,
+ sizeof(SortTuple),
+ (qsort_arg_comparator) state->comparetup,
+ (void *) state);
state->current = 0;
state->eof_reached = false;
state->markpos_offset = 0;
@@ -1587,7 +1578,6 @@ mergeonerun(Tuplesortstate *state)
*/
while (state->memtupcount > 0)
{
- CHECK_FOR_INTERRUPTS();
/* write the tuple to destTape */
priorAvail = state->availMem;
srcTape = state->memtuples[0].tupindex;
@@ -2092,20 +2082,6 @@ markrunend(Tuplesortstate *state, int tapenum)
/*
- * qsort interface
- */
-
-static int
-qsort_comparetup(const void *a, const void *b)
-{
- /* The passed pointers are pointers to SortTuple ... */
- return COMPARETUP(qsort_tuplesortstate,
- (const SortTuple *) a,
- (const SortTuple *) b);
-}
-
-
-/*
* This routine selects an appropriate sorting function to implement
* a sort operator as efficiently as possible. The straightforward
* method is to use the operator's implementation proc --- ie, "<"
@@ -2319,7 +2295,7 @@ ApplySortFunction(FmgrInfo *sortFunction, SortFunctionKind kind,
*/
static int
-comparetup_heap(Tuplesortstate *state, const SortTuple *a, const SortTuple *b)
+comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
{
ScanKey scanKey = state->scanKeys;
HeapTupleData ltup;
@@ -2328,6 +2304,9 @@ comparetup_heap(Tuplesortstate *state, const SortTuple *a, const SortTuple *b)
int nkey;
int32 compare;
+ /* Allow interrupting long sorts */
+ CHECK_FOR_INTERRUPTS();
+
/* Compare the leading sort key */
compare = inlineApplySortFunction(&scanKey->sk_func,
state->sortFnKinds[0],
@@ -2449,7 +2428,7 @@ readtup_heap(Tuplesortstate *state, SortTuple *stup,
*/
static int
-comparetup_index(Tuplesortstate *state, const SortTuple *a, const SortTuple *b)
+comparetup_index(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
{
/*
* This is similar to _bt_tuplecompare(), but we have already done the
@@ -2466,6 +2445,9 @@ comparetup_index(Tuplesortstate *state, const SortTuple *a, const SortTuple *b)
int nkey;
int32 compare;
+ /* Allow interrupting long sorts */
+ CHECK_FOR_INTERRUPTS();
+
/* Compare the leading sort key */
compare = inlineApplySortFunction(&scanKey->sk_func,
SORTFUNC_CMP,
@@ -2622,8 +2604,11 @@ readtup_index(Tuplesortstate *state, SortTuple *stup,
*/
static int
-comparetup_datum(Tuplesortstate *state, const SortTuple *a, const SortTuple *b)
+comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
{
+ /* Allow interrupting long sorts */
+ CHECK_FOR_INTERRUPTS();
+
return inlineApplySortFunction(&state->sortOpFn, state->sortFnKind,
a->datum1, a->isnull1,
b->datum1, b->isnull1);
diff --git a/src/include/port.h b/src/include/port.h
index eb8b0318159..cf3694f4f52 100644
--- a/src/include/port.h
+++ b/src/include/port.h
@@ -6,10 +6,12 @@
* Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
- * $PostgreSQL: pgsql/src/include/port.h,v 1.102 2006/10/02 00:06:18 tgl Exp $
+ * $PostgreSQL: pgsql/src/include/port.h,v 1.103 2006/10/03 22:18:23 tgl Exp $
*
*-------------------------------------------------------------------------
*/
+#ifndef PG_PORT_H
+#define PG_PORT_H
#include <ctype.h>
#include <netdb.h>
@@ -361,3 +363,10 @@ extern int pqGethostbyname(const char *name,
char *buffer, size_t buflen,
struct hostent ** result,
int *herrno);
+
+typedef int (*qsort_arg_comparator) (const void *a, const void *b, void *arg);
+
+extern void qsort_arg(void *base, size_t nel, size_t elsize,
+ qsort_arg_comparator cmp, void *arg);
+
+#endif /* PG_PORT_H */
diff --git a/src/port/qsort.c b/src/port/qsort.c
index a7aa8cea2a9..3f3e7787e9f 100644
--- a/src/port/qsort.c
+++ b/src/port/qsort.c
@@ -1,11 +1,15 @@
/*
+ * 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.
*
- * $PostgreSQL: pgsql/src/port/qsort.c,v 1.9 2006/03/21 19:49:15 tgl Exp $
+ * 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.13 2003/08/07 16:43:42 agc Exp $ */
diff --git a/src/port/qsort_arg.c b/src/port/qsort_arg.c
new file mode 100644
index 00000000000..ac7b149b5ff
--- /dev/null
+++ b/src/port/qsort_arg.c
@@ -0,0 +1,201 @@
+/*
+ * qsort_arg.c: qsort with a passthrough "void *" argument
+ *
+ * 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.c
+ *
+ * $PostgreSQL: pgsql/src/port/qsort_arg.c,v 1.1 2006/10/03 22:18:23 tgl Exp $
+ */
+
+/* $NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $ */
+
+/*-
+ * Copyright (c) 1992, 1993
+ * The Regents of the University of California. All rights reserved.
+ *
+ * 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.
+ * 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.
+ *
+ * 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.
+ */
+
+#include "c.h"
+
+
+static char *med3(char *a, char *b, char *c,
+ qsort_arg_comparator cmp, void *arg);
+static void swapfunc(char *, char *, size_t, int);
+
+#define min(a, b) ((a) < (b) ? (a) : (b))
+
+/*
+ * 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 { \
+ size_t i = (n) / sizeof (TYPE); \
+ TYPE *pi = (TYPE *)(void *)(parmi); \
+ TYPE *pj = (TYPE *)(void *)(parmj); \
+ do { \
+ TYPE t = *pi; \
+ *pi++ = *pj; \
+ *pj++ = t; \
+ } 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;
+
+static void
+swapfunc(a, b, n, swaptype)
+char *a,
+ *b;
+size_t n;
+int swaptype;
+{
+ if (swaptype <= 1)
+ swapcode(long, a, b, n);
+ else
+ swapcode(char, a, b, n);
+}
+
+#define swap(a, b) \
+ if (swaptype == 0) { \
+ long t = *(long *)(void *)(a); \
+ *(long *)(void *)(a) = *(long *)(void *)(b); \
+ *(long *)(void *)(b) = t; \
+ } else \
+ swapfunc(a, b, es, swaptype)
+
+#define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n), swaptype)
+
+static char *
+med3(char *a, char *b, char *c, qsort_arg_comparator cmp, void *arg)
+{
+ return cmp(a, b, arg) < 0 ?
+ (cmp(b, c, arg) < 0 ? b : (cmp(a, c, arg) < 0 ? c : a))
+ : (cmp(b, c, arg) > 0 ? b : (cmp(a, c, arg) < 0 ? a : c));
+}
+
+void
+qsort_arg(void *a, size_t n, size_t es, qsort_arg_comparator cmp, void *arg)
+{
+ char *pa,
+ *pb,
+ *pc,
+ *pd,
+ *pl,
+ *pm,
+ *pn;
+ int d,
+ r,
+ swaptype,
+ presorted;
+
+loop:SWAPINIT(a, es);
+ 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, arg) > 0;
+ pl -= 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, arg) > 0)
+ {
+ presorted = 0;
+ break;
+ }
+ }
+ if (presorted)
+ return;
+ pm = (char *) a + (n / 2) * es;
+ if (n > 7)
+ {
+ pl = (char *) a;
+ pn = (char *) a + (n - 1) * es;
+ if (n > 40)
+ {
+ d = (n / 8) * es;
+ pl = med3(pl, pl + d, pl + 2 * d, cmp, arg);
+ pm = med3(pm - d, pm, pm + d, cmp, arg);
+ pn = med3(pn - 2 * d, pn - d, pn, cmp, arg);
+ }
+ pm = med3(pl, pm, pn, cmp, arg);
+ }
+ swap(a, pm);
+ pa = pb = (char *) a + es;
+ pc = pd = (char *) a + (n - 1) * es;
+ for (;;)
+ {
+ while (pb <= pc && (r = cmp(pb, a, arg)) <= 0)
+ {
+ if (r == 0)
+ {
+ swap(pa, pb);
+ pa += es;
+ }
+ pb += es;
+ }
+ while (pb <= pc && (r = cmp(pc, a, arg)) >= 0)
+ {
+ if (r == 0)
+ {
+ swap(pc, pd);
+ pd -= es;
+ }
+ pc -= es;
+ }
+ if (pb > pc)
+ break;
+ swap(pb, pc);
+ pb += es;
+ pc -= es;
+ }
+ 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_arg(a, r / es, es, cmp, arg);
+ if ((r = pd - pc) > es)
+ {
+ /* Iterate rather than recurse to save stack space */
+ a = pn - r;
+ n = r / es;
+ goto loop;
+ }
+/* qsort_arg(pn - r, r / es, es, cmp, arg);*/
+}
generated by cgit v1.2.3 (git 2.25.1) at 2025-05-21 12:38:05 +0000