← Back to branch summary

~vcs-imports/mammoth-replicator/trunk

« back to all changes in this revision

Viewing changes to src/port/qsort.c

  • Committer: alvherre
  • Date: 2005-12-16 21:24:52 UTC
  • Revision ID: svn-v4:db760fc0-0f08-0410-9d63-cc6633f64896:trunk:1
Initial import of the REL8_0_3 sources from the Pgsql CVS repository.

Show diffs side-by-side

added added

removed removed

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