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 3584319 : CONCAT3(GDKqsort_impl_, TPE, SUFF)(const struct qsort_t *restrict buf,
63 : char *restrict h, char *restrict t, size_t n)
64 : {
65 4154864 : size_t a, b, c, d;
66 4154864 : size_t r;
67 4154864 : bool swap_cnt;
68 : #ifdef INITIALIZER
69 : INITIALIZER;
70 : #endif
71 :
72 : loop:
73 4154864 : if (n < INSERTSORT) {
74 : /* insertion sort for very small chunks */
75 37925571 : for (b = 1; b < n; b++) {
76 253932294 : for (a = b; a > 0 && LT(a, a - 1, TPE, SUFF); a--) {
77 1908969227 : SWAP(a, a - 1, TPE);
78 : }
79 : }
80 : return;
81 : }
82 :
83 : /* determine pivot */
84 616105 : 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 616105 : a = 0;
92 616105 : 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 616105 : d = n >> 3;
100 616105 : a = MED3(a, a + d, a + 2 * d, TPE, SUFF);
101 616082 : b = MED3(b - d, b, b + d, TPE, SUFF);
102 616081 : c = MED3(c - 2 * d, c - d, c, TPE, SUFF);
103 : }
104 616080 : b = MED3(a, b, c, TPE, SUFF);
105 : }
106 : /* move pivot to start */
107 616083 : if (b != 0)
108 4621259 : 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 75677615 : 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 257477012 : while (b <= c && LE(b, 0, TPE, SUFF)) {
123 181183258 : if (EQ(b, 0, TPE)) {
124 2402112 : swap_cnt = true;
125 22104529 : SWAP(a, b, TPE);
126 2402112 : a++;
127 : }
128 181183314 : b++;
129 : }
130 248575057 : while (b <= c && LE(0, c, TPE, SUFF)) {
131 172282116 : if (EQ(0, c, TPE)) {
132 685891 : swap_cnt = true;
133 6324870 : SWAP(c, d, TPE);
134 685891 : d--;
135 : }
136 172282107 : c--;
137 : }
138 76293700 : if (b > c)
139 : break;
140 662004916 : SWAP(b, c, TPE);
141 75677615 : swap_cnt = true;
142 75677615 : b++;
143 75677615 : 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 616085 : if (!swap_cnt && n < 1024) {
152 : /* switch to insertion sort, but only for small chunks */
153 16563676 : for (b = 1; b < n; b++) {
154 33621579 : for (a = b; a > 0 && LT(a, a - 1, TPE, SUFF); a--) {
155 73169965 : SWAP(a, a - 1, TPE);
156 : }
157 : }
158 : return;
159 : }
160 :
161 : /* move initial values equal to the pivot to the middle */
162 571465 : r = MIN(a, b - a);
163 10401220 : multi_SWAP(0, b - r, r);
164 : /* move final values equal to the pivot to the middle */
165 571465 : r = MIN(d - c, n - d - 1);
166 2235925 : 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 571465 : if (b - a < d - c) {
177 264316 : if ((r = b - a) > 1) {
178 : /* sort values less than pivot */
179 263909 : CONCAT3(GDKqsort_impl_, TPE, SUFF)(buf, h, t, r);
180 : }
181 264316 : if ((r = d - c) > 1) {
182 : /* sort values greater than pivot
183 : * iterate rather than recurse */
184 264313 : h += (n - r) * buf->hs;
185 264313 : if (t && buf->ts)
186 253240 : t += (n - r) * buf->ts;
187 264313 : n = r;
188 264313 : goto loop;
189 : }
190 : } else {
191 307149 : if ((r = d - c) > 1) {
192 : /* sort values greater than pivot */
193 305735 : CONCAT3(GDKqsort_impl_, TPE, SUFF)(
194 305735 : buf, h + (n - r) * buf->hs,
195 276997 : t ? t + (n - r) * buf->ts : NULL, r);
196 : }
197 307159 : if ((r = b - a) > 1) {
198 : /* sort values less than pivot
199 : * iterate rather than recurse */
200 306232 : n = r;
201 306232 : goto loop;
202 : }
203 : }
204 : }
|
