1/*
2 * This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
5 *
6 * Copyright 1997 - July 2008 CWI, August 2008 - 2019 MonetDB B.V.
7 */
8
9/* This file is included multiple times. We expect the tokens SWAP,
10 * GDKqsort_impl, LE, LT, and EQ to be redefined each time. */
11
12/* This is an implementation of quicksort with a number of extra
13 * tweaks and optimizations. This function is an adaptation to fit
14 * into the MonetDB mould from the original version by Bentley &
15 * McIlroy from "Engineering a Sort Function". Hence the following
16 * copyright notice. Comments in the code are mine (Sjoerd
17 * Mullender). */
18
19/*
20 * Copyright (c) 1992, 1993
21 * The Regents of the University of California. All rights reserved.
22 *
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
25 * are met:
26 * 1. Redistributions of source code must retain the above copyright
27 * notice, this list of conditions and the following disclaimer.
28 * 2. Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in the
30 * documentation and/or other materials provided with the distribution.
31 * 3. All advertising materials mentioning features or use of this software
32 * must display the following acknowledgement:
33 * This product includes software developed by the University of
34 * California, Berkeley and its contributors.
35 * 4. Neither the name of the University nor the names of its contributors
36 * may be used to endorse or promote products derived from this software
37 * without specific prior written permission.
38 *
39 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
40 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
42 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
43 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
44 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
45 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
46 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
47 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
48 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
49 * SUCH DAMAGE.
50 */
51
52/* when to switch to insertion sort */
53#ifndef INSERTSORT
54#define INSERTSORT 60 /* the original algorithm used 7 */
55#endif
56
57static void
58CONCAT3(GDKqsort_impl_, TPE, SUFF)(const struct qsort_t *restrict buf,
59 char *restrict h, char *restrict t, size_t n)
60{
61 size_t a, b, c, d;
62 size_t r;
63 bool swap_cnt;
64#ifdef INITIALIZER
65 INITIALIZER;
66#endif
67
68 loop:
69 if (n < INSERTSORT) {
70 /* insertion sort for very small chunks */
71 for (b = 1; b < n; b++) {
72 for (a = b; a > 0 && LT(a, a - 1, TPE, SUFF); a--) {
73 SWAP(a, a - 1, TPE);
74 }
75 }
76 return;
77 }
78
79 /* determine pivot */
80 b = n >> 1; /* small arrays: middle element */
81#if INSERTSORT <= 7
82 if (n > 7)
83#endif
84 {
85 /* for larger arrays, take the middle value from the
86 * first, middle, and last */
87 a = 0;
88 c = n - 1;
89#if INSERTSORT <= 40
90 if (n > 40)
91#endif
92 {
93 /* for even larger arrays, take the middle
94 * value of three middle values */
95 d = n >> 3;
96 a = MED3(a, a + d, a + 2 * d, TPE, SUFF);
97 b = MED3(b - d, b, b + d, TPE, SUFF);
98 c = MED3(c - 2 * d, c - d, c, TPE, SUFF);
99 }
100 b = MED3(a, b, c, TPE, SUFF);
101 }
102 /* move pivot to start */
103 if (b != 0)
104 SWAP(0, b, TPE);
105
106 /* Bentley and McIlroy's implementation of Dijkstra's Dutch
107 * National Flag Problem */
108 a = b = 1;
109 c = d = n - 1;
110 swap_cnt = false;
111 for (;;) {
112 /* loop invariant:
113 * [0..a): values equal to pivot (cannot be empty)
114 * [a..b): values less than pivot (can be empty)
115 * [c+1..d+1): values greater than pivot (can be empty)
116 * [d+1..n): values equal to pivot (can be empty)
117 */
118 while (b <= c && LE(b, 0, TPE, SUFF)) {
119 if (EQ(b, 0, TPE)) {
120 swap_cnt = true;
121 SWAP(a, b, TPE);
122 a++;
123 }
124 b++;
125 }
126 while (b <= c && LE(0, c, TPE, SUFF)) {
127 if (EQ(0, c, TPE)) {
128 swap_cnt = true;
129 SWAP(c, d, TPE);
130 d--;
131 }
132 c--;
133 }
134 if (b > c)
135 break;
136 SWAP(b, c, TPE);
137 swap_cnt = true;
138 b++;
139 c--;
140 }
141 /* in addition to the loop invariant we have:
142 * b == c + 1
143 * i.e., there are b-a values less than the pivot and d-c
144 * values greater than the pivot
145 */
146
147 if (!swap_cnt && n < 1024) {
148 /* switch to insertion sort, but only for small chunks */
149 for (b = 1; b < n; b++) {
150 for (a = b; a > 0 && LT(a, a - 1, TPE, SUFF); a--) {
151 SWAP(a, a - 1, TPE);
152 }
153 }
154 return;
155 }
156
157 /* move initial values equal to the pivot to the middle */
158 r = MIN(a, b - a);
159 multi_SWAP(0, b - r, r);
160 /* move final values equal to the pivot to the middle */
161 r = MIN(d - c, n - d - 1);
162 multi_SWAP(b, n - r, r);
163 /* at this point we have:
164 * b == c + 1
165 * [0..b-a): values less than pivot (to be sorted)
166 * [b-a..n-(d-c)): values equal to pivot (in place)
167 * [n-(d-c)..n): values larger than pivot (to be sorted)
168 */
169
170 /* use recursion for smaller of the two subarrays, loop back
171 * to start for larger of the two */
172 if (b - a < d - c) {
173 if ((r = b - a) > 1) {
174 /* sort values less than pivot */
175 CONCAT3(GDKqsort_impl_, TPE, SUFF)(buf, h, t, r);
176 }
177 if ((r = d - c) > 1) {
178 /* sort values greater than pivot
179 * iterate rather than recurse */
180 h += (n - r) * buf->hs;
181 if (t && buf->ts)
182 t += (n - r) * buf->ts;
183 n = r;
184 goto loop;
185 }
186 } else {
187 if ((r = d - c) > 1) {
188 /* sort values greater than pivot */
189 CONCAT3(GDKqsort_impl_, TPE, SUFF)(
190 buf, h + (n - r) * buf->hs,
191 t ? t + (n - r) * buf->ts : NULL, r);
192 }
193 if ((r = b - a) > 1) {
194 /* sort values less than pivot
195 * iterate rather than recurse */
196 n = r;
197 goto loop;
198 }
199 }
200}
201