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