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 4101141 : CONCAT3(GDKqsort_impl_, TPE, SUFF)(const struct qsort_t *restrict buf,
63 : char *restrict h, char *restrict t, size_t n)
64 : {
65 5186158 : size_t a, b, c, d;
66 5186158 : size_t r;
67 5186158 : bool swap_cnt;
68 : #ifdef INITIALIZER
69 : INITIALIZER;
70 : #endif
71 :
72 : loop:
73 5186158 : if (n < INSERTSORT) {
74 : /* insertion sort for very small chunks */
75 56510828 : for (b = 1; b < n; b++) {
76 461558747 : for (a = b; a > 0 && LT(a, a - 1, TPE, SUFF); a--) {
77 3580257621 : SWAP(a, a - 1, TPE);
78 : }
79 : }
80 : return;
81 : }
82 :
83 : /* determine pivot */
84 1137209 : 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 1137209 : a = 0;
92 1137209 : 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 1137209 : d = n >> 3;
100 1137209 : a = MED3(a, a + d, a + 2 * d, TPE, SUFF);
101 1137210 : b = MED3(b - d, b, b + d, TPE, SUFF);
102 1137209 : c = MED3(c - 2 * d, c - d, c, TPE, SUFF);
103 : }
104 1137209 : b = MED3(a, b, c, TPE, SUFF);
105 : }
106 : /* move pivot to start */
107 1137207 : if (b != 0)
108 8830138 : 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 133150537 : 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 456939418 : while (b <= c && LE(b, 0, TPE, SUFF)) {
123 322651928 : if (EQ(b, 0, TPE)) {
124 26618727 : swap_cnt = true;
125 235943695 : SWAP(a, b, TPE);
126 26618727 : a++;
127 : }
128 322651674 : b++;
129 : }
130 427909015 : while (b <= c && LE(0, c, TPE, SUFF)) {
131 293621357 : if (EQ(0, c, TPE)) {
132 4328458 : swap_cnt = true;
133 39439395 : SWAP(c, d, TPE);
134 4328458 : d--;
135 : }
136 293621350 : c--;
137 : }
138 134287747 : if (b > c)
139 : break;
140 1168640231 : SWAP(b, c, TPE);
141 133150537 : swap_cnt = true;
142 133150537 : b++;
143 133150537 : 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 1137210 : if (!swap_cnt && n < 1024) {
152 : /* switch to insertion sort, but only for small chunks */
153 17265444 : for (b = 1; b < n; b++) {
154 35180018 : for (a = b; a > 0 && LT(a, a - 1, TPE, SUFF); a--) {
155 68411298 : SWAP(a, a - 1, TPE);
156 : }
157 : }
158 : return;
159 : }
160 :
161 : /* move initial values equal to the pivot to the middle */
162 1104072 : r = MIN(a, b - a);
163 127110444 : multi_SWAP(0, b - r, r);
164 : /* move final values equal to the pivot to the middle */
165 1104072 : r = MIN(d - c, n - d - 1);
166 42374832 : 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 1104072 : if (b - a < d - c) {
177 513712 : if ((r = b - a) > 1) {
178 : /* sort values less than pivot */
179 501575 : CONCAT3(GDKqsort_impl_, TPE, SUFF)(buf, h, t, r);
180 : }
181 513711 : if ((r = d - c) > 1) {
182 : /* sort values greater than pivot
183 : * iterate rather than recurse */
184 512830 : h += (n - r) * buf->hs;
185 512830 : if (t && buf->ts)
186 493764 : t += (n - r) * buf->ts;
187 512830 : n = r;
188 512830 : goto loop;
189 : }
190 : } else {
191 590360 : if ((r = d - c) > 1) {
192 : /* sort values greater than pivot */
193 562728 : CONCAT3(GDKqsort_impl_, TPE, SUFF)(
194 562728 : buf, h + (n - r) * buf->hs,
195 528876 : t ? t + (n - r) * buf->ts : NULL, r);
196 : }
197 590365 : if ((r = b - a) > 1) {
198 : /* sort values less than pivot
199 : * iterate rather than recurse */
200 572187 : n = r;
201 572187 : goto loop;
202 : }
203 : }
204 : }
|
