← Back to branch summary

~ubuntu-branches/ubuntu/hardy/postgresql-8.4/hardy-backports

« back to all changes in this revision

Viewing changes to src/port/qsort.c

  • Committer: Bazaar Package Importer
  • Author(s): Martin Pitt
  • Date: 2009-03-20 12:00:13 UTC
  • Revision ID: james.westby@ubuntu.com-20090320120013-hogj7egc5mjncc5g
Tags: upstream-8.4~0cvs20090328
Import upstream version 8.4~0cvs20090328

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/port/qsort.c
 
1
/*
 
2
 *      qsort.c: standard quicksort algorithm
 
3
 *
 
4
 *      Modifications from vanilla NetBSD source:
 
5
 *        Add do ... while() macro fix
 
6
 *        Remove __inline, _DIAGASSERTs, __P
 
7
 *        Remove ill-considered "swap_cnt" switch to insertion sort,
 
8
 *        in favor of a simple check for presorted input.
 
9
 *
 
10
 *      CAUTION: if you change this file, see also qsort_arg.c
 
11
 *
 
12
 *      $PostgreSQL$
 
13
 */
 
14
 
 
15
/*      $NetBSD$        */
 
16
 
 
17
/*-
 
18
 * Copyright (c) 1992, 1993
 
19
 *      The Regents of the University of California.  All rights reserved.
 
20
 *
 
21
 * Redistribution and use in source and binary forms, with or without
 
22
 * modification, are permitted provided that the following conditions
 
23
 * are met:
 
24
 * 1. Redistributions of source code must retain the above copyright
 
25
 *        notice, this list of conditions and the following disclaimer.
 
26
 * 2. Redistributions in binary form must reproduce the above copyright
 
27
 *        notice, this list of conditions and the following disclaimer in the
 
28
 *        documentation and/or other materials provided with the distribution.
 
29
 * 3. Neither the name of the University nor the names of its contributors
 
30
 *        may be used to endorse or promote products derived from this software
 
31
 *        without specific prior written permission.
 
32
 *
 
33
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 
34
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
35
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
36
 * ARE DISCLAIMED.      IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 
37
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 
38
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 
39
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
40
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 
41
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 
42
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 
43
 * SUCH DAMAGE.
 
44
 */
 
45
 
 
46
#include "c.h"
 
47
 
 
48
 
 
49
static char *med3(char *a, char *b, char *c,
 
50
         int (*cmp) (const void *, const void *));
 
51
static void swapfunc(char *, char *, size_t, int);
 
52
 
 
53
/*
 
54
 * Qsort routine based on J. L. Bentley and M. D. McIlroy,
 
55
 * "Engineering a sort function",
 
56
 * Software--Practice and Experience 23 (1993) 1249-1265.
 
57
 * We have modified their original by adding a check for already-sorted input,
 
58
 * which seems to be a win per discussions on pgsql-hackers around 2006-03-21.
 
59
 */
 
60
#define swapcode(TYPE, parmi, parmj, n) \
 
61
do {            \
 
62
        size_t i = (n) / sizeof (TYPE);                 \
 
63
        TYPE *pi = (TYPE *)(void *)(parmi);                     \
 
64
        TYPE *pj = (TYPE *)(void *)(parmj);                     \
 
65
        do {                                            \
 
66
                TYPE    t = *pi;                        \
 
67
                *pi++ = *pj;                            \
 
68
                *pj++ = t;                              \
 
69
                } while (--i > 0);                              \
 
70
} while (0)
 
71
 
 
72
#define SWAPINIT(a, es) swaptype = ((char *)(a) - (char *)0) % sizeof(long) || \
 
73
        (es) % sizeof(long) ? 2 : (es) == sizeof(long)? 0 : 1;
 
74
 
 
75
static void
 
76
swapfunc(char *a, char *b, size_t n, int swaptype)
 
77
{
 
78
        if (swaptype <= 1)
 
79
                swapcode(long, a, b, n);
 
80
        else
 
81
                swapcode(char, a, b, n);
 
82
}
 
83
 
 
84
#define swap(a, b)                                              \
 
85
        if (swaptype == 0) {                                    \
 
86
                long t = *(long *)(void *)(a);                  \
 
87
                *(long *)(void *)(a) = *(long *)(void *)(b);    \
 
88
                *(long *)(void *)(b) = t;                       \
 
89
        } else                                                  \
 
90
                swapfunc(a, b, es, swaptype)
 
91
 
 
92
#define vecswap(a, b, n) if ((n) > 0) swapfunc((a), (b), (size_t)(n), swaptype)
 
93
 
 
94
static char *
 
95
med3(char *a, char *b, char *c, int (*cmp) (const void *, const void *))
 
96
{
 
97
        return cmp(a, b) < 0 ?
 
98
                (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a))
 
99
                : (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c));
 
100
}
 
101
 
 
102
void
 
103
pg_qsort(void *a, size_t n, size_t es, int (*cmp) (const void *, const void *))
 
104
{
 
105
        char       *pa,
 
106
                           *pb,
 
107
                           *pc,
 
108
                           *pd,
 
109
                           *pl,
 
110
                           *pm,
 
111
                           *pn;
 
112
        int                     d,
 
113
                                r,
 
114
                                swaptype,
 
115
                                presorted;
 
116
 
 
117
loop:SWAPINIT(a, es);
 
118
        if (n < 7)
 
119
        {
 
120
                for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
 
121
                        for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
 
122
                                 pl -= es)
 
123
                                swap(pl, pl - es);
 
124
                return;
 
125
        }
 
126
        presorted = 1;
 
127
        for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
 
128
        {
 
129
                if (cmp(pm - es, pm) > 0)
 
130
                {
 
131
                        presorted = 0;
 
132
                        break;
 
133
                }
 
134
        }
 
135
        if (presorted)
 
136
                return;
 
137
        pm = (char *) a + (n / 2) * es;
 
138
        if (n > 7)
 
139
        {
 
140
                pl = (char *) a;
 
141
                pn = (char *) a + (n - 1) * es;
 
142
                if (n > 40)
 
143
                {
 
144
                        d = (n / 8) * es;
 
145
                        pl = med3(pl, pl + d, pl + 2 * d, cmp);
 
146
                        pm = med3(pm - d, pm, pm + d, cmp);
 
147
                        pn = med3(pn - 2 * d, pn - d, pn, cmp);
 
148
                }
 
149
                pm = med3(pl, pm, pn, cmp);
 
150
        }
 
151
        swap(a, pm);
 
152
        pa = pb = (char *) a + es;
 
153
        pc = pd = (char *) a + (n - 1) * es;
 
154
        for (;;)
 
155
        {
 
156
                while (pb <= pc && (r = cmp(pb, a)) <= 0)
 
157
                {
 
158
                        if (r == 0)
 
159
                        {
 
160
                                swap(pa, pb);
 
161
                                pa += es;
 
162
                        }
 
163
                        pb += es;
 
164
                }
 
165
                while (pb <= pc && (r = cmp(pc, a)) >= 0)
 
166
                {
 
167
                        if (r == 0)
 
168
                        {
 
169
                                swap(pc, pd);
 
170
                                pd -= es;
 
171
                        }
 
172
                        pc -= es;
 
173
                }
 
174
                if (pb > pc)
 
175
                        break;
 
176
                swap(pb, pc);
 
177
                pb += es;
 
178
                pc -= es;
 
179
        }
 
180
        pn = (char *) a + n * es;
 
181
        r = Min(pa - (char *) a, pb - pa);
 
182
        vecswap(a, pb - r, r);
 
183
        r = Min(pd - pc, pn - pd - es);
 
184
        vecswap(pb, pn - r, r);
 
185
        if ((r = pb - pa) > es)
 
186
                qsort(a, r / es, es, cmp);
 
187
        if ((r = pd - pc) > es)
 
188
        {
 
189
                /* Iterate rather than recurse to save stack space */
 
190
                a = pn - r;
 
191
                n = r / es;
 
192
                goto loop;
 
193
        }
 
194
/*              qsort(pn - r, r / es, es, cmp);*/
 
195
}