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  *	  Take care to recurse on the smaller partition, to bound stack usage.
10  *
11  *	CAUTION: if you change this file, see also qsort_arg.c, gen_qsort_tuple.pl
12  *
13  *	src/port/qsort.c
14  */
15 
16 /*	$NetBSD: qsort.c,v 1.13 2003/08/07 16:43:42 agc Exp $	*/
17 
18 /*-
19  * Copyright (c) 1992, 1993
20  *	The Regents of the University of California.  All rights reserved.
21  *
22  * Redistribution and use in source and binary forms, with or without
23  * modification, are permitted provided that the following conditions
24  * are met:
25  * 1. Redistributions of source code must retain the above copyright
26  *	  notice, this list of conditions and the following disclaimer.
27  * 2. Redistributions in binary form must reproduce the above copyright
28  *	  notice, this list of conditions and the following disclaimer in the
29  *	  documentation and/or other materials provided with the distribution.
30  * 3. Neither the name of the University nor the names of its contributors
31  *	  may be used to endorse or promote products derived from this software
32  *	  without specific prior written permission.
33  *
34  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44  * SUCH DAMAGE.
45  */
46 
47 #include "c.h"
48 
49 
50 static char *med3(char *a, char *b, char *c,
51 				  int (*cmp) (const void *, const void *));
52 static void swapfunc(char *, char *, size_t, int);
53 
54 /*
55  * Qsort routine based on J. L. Bentley and M. D. McIlroy,
56  * "Engineering a sort function",
57  * Software--Practice and Experience 23 (1993) 1249-1265.
58  *
59  * We have modified their original by adding a check for already-sorted input,
60  * which seems to be a win per discussions on pgsql-hackers around 2006-03-21.
61  *
62  * Also, we recurse on the smaller partition and iterate on the larger one,
63  * which ensures we cannot recurse more than log(N) levels (since the
64  * partition recursed to is surely no more than half of the input).  Bentley
65  * and McIlroy explicitly rejected doing this on the grounds that it's "not
66  * worth the effort", but we have seen crashes in the field due to stack
67  * overrun, so that judgment seems wrong.
68  */
69 
70 #define swapcode(TYPE, parmi, parmj, n) \
71 do {		\
72 	size_t i = (n) / sizeof (TYPE);			\
73 	TYPE *pi = (TYPE *)(void *)(parmi);			\
74 	TYPE *pj = (TYPE *)(void *)(parmj);			\
75 	do {						\
76 		TYPE	t = *pi;			\
77 		*pi++ = *pj;				\
78 		*pj++ = t;				\
79 		} while (--i > 0);				\
80 } while (0)
81 
82 #define SWAPINIT(a, es) swaptype = ((char *)(a) - (char *)0) % sizeof(long) || \
83 	(es) % sizeof(long) ? 2 : (es) == sizeof(long)? 0 : 1
84 
85 static void
swapfunc(char * a,char * b,size_t n,int swaptype)86 swapfunc(char *a, char *b, size_t n, int swaptype)
87 {
88 	if (swaptype <= 1)
89 		swapcode(long, a, b, n);
90 	else
91 		swapcode(char, a, b, n);
92 }
93 
94 #define swap(a, b)						\
95 	if (swaptype == 0) {					\
96 		long t = *(long *)(void *)(a);			\
97 		*(long *)(void *)(a) = *(long *)(void *)(b);	\
98 		*(long *)(void *)(b) = t;			\
99 	} else							\
100 		swapfunc(a, b, es, swaptype)
101 
102 #define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
103 
104 static char *
med3(char * a,char * b,char * c,int (* cmp)(const void *,const void *))105 med3(char *a, char *b, char *c, int (*cmp) (const void *, const void *))
106 {
107 	return cmp(a, b) < 0 ?
108 		(cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a))
109 		: (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c));
110 }
111 
112 void
pg_qsort(void * a,size_t n,size_t es,int (* cmp)(const void *,const void *))113 pg_qsort(void *a, size_t n, size_t es, int (*cmp) (const void *, const void *))
114 {
115 	char	   *pa,
116 			   *pb,
117 			   *pc,
118 			   *pd,
119 			   *pl,
120 			   *pm,
121 			   *pn;
122 	size_t		d1,
123 				d2;
124 	int			r,
125 				swaptype,
126 				presorted;
127 
128 loop:SWAPINIT(a, es);
129 	if (n < 7)
130 	{
131 		for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
132 			for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
133 				 pl -= es)
134 				swap(pl, pl - es);
135 		return;
136 	}
137 	presorted = 1;
138 	for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
139 	{
140 		if (cmp(pm - es, pm) > 0)
141 		{
142 			presorted = 0;
143 			break;
144 		}
145 	}
146 	if (presorted)
147 		return;
148 	pm = (char *) a + (n / 2) * es;
149 	if (n > 7)
150 	{
151 		pl = (char *) a;
152 		pn = (char *) a + (n - 1) * es;
153 		if (n > 40)
154 		{
155 			size_t		d = (n / 8) * es;
156 
157 			pl = med3(pl, pl + d, pl + 2 * d, cmp);
158 			pm = med3(pm - d, pm, pm + d, cmp);
159 			pn = med3(pn - 2 * d, pn - d, pn, cmp);
160 		}
161 		pm = med3(pl, pm, pn, cmp);
162 	}
163 	swap(a, pm);
164 	pa = pb = (char *) a + es;
165 	pc = pd = (char *) a + (n - 1) * es;
166 	for (;;)
167 	{
168 		while (pb <= pc && (r = cmp(pb, a)) <= 0)
169 		{
170 			if (r == 0)
171 			{
172 				swap(pa, pb);
173 				pa += es;
174 			}
175 			pb += es;
176 		}
177 		while (pb <= pc && (r = cmp(pc, a)) >= 0)
178 		{
179 			if (r == 0)
180 			{
181 				swap(pc, pd);
182 				pd -= es;
183 			}
184 			pc -= es;
185 		}
186 		if (pb > pc)
187 			break;
188 		swap(pb, pc);
189 		pb += es;
190 		pc -= es;
191 	}
192 	pn = (char *) a + n * es;
193 	d1 = Min(pa - (char *) a, pb - pa);
194 	vecswap(a, pb - d1, d1);
195 	d1 = Min(pd - pc, pn - pd - es);
196 	vecswap(pb, pn - d1, d1);
197 	d1 = pb - pa;
198 	d2 = pd - pc;
199 	if (d1 <= d2)
200 	{
201 		/* Recurse on left partition, then iterate on right partition */
202 		if (d1 > es)
203 			pg_qsort(a, d1 / es, es, cmp);
204 		if (d2 > es)
205 		{
206 			/* Iterate rather than recurse to save stack space */
207 			/* pg_qsort(pn - d2, d2 / es, es, cmp); */
208 			a = pn - d2;
209 			n = d2 / es;
210 			goto loop;
211 		}
212 	}
213 	else
214 	{
215 		/* Recurse on right partition, then iterate on left partition */
216 		if (d2 > es)
217 			pg_qsort(pn - d2, d2 / es, es, cmp);
218 		if (d1 > es)
219 		{
220 			/* Iterate rather than recurse to save stack space */
221 			/* pg_qsort(a, d1 / es, es, cmp); */
222 			n = d1 / es;
223 			goto loop;
224 		}
225 	}
226 }
227 
228 /*
229  * qsort comparator wrapper for strcmp.
230  */
231 int
pg_qsort_strcmp(const void * a,const void * b)232 pg_qsort_strcmp(const void *a, const void *b)
233 {
234 	return strcmp(*(const char *const *) a, *(const char *const *) b);
235 }
236