1 | /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*- */ |
2 | // vim: ft=cpp:expandtab:ts=8:sw=4:softtabstop=4: |
3 | #ident "$Id$" |
4 | /*====== |
5 | This file is part of PerconaFT. |
6 | |
7 | |
8 | Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved. |
9 | |
10 | PerconaFT is free software: you can redistribute it and/or modify |
11 | it under the terms of the GNU General Public License, version 2, |
12 | as published by the Free Software Foundation. |
13 | |
14 | PerconaFT is distributed in the hope that it will be useful, |
15 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
16 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
17 | GNU General Public License for more details. |
18 | |
19 | You should have received a copy of the GNU General Public License |
20 | along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. |
21 | |
22 | ---------------------------------------- |
23 | |
24 | PerconaFT is free software: you can redistribute it and/or modify |
25 | it under the terms of the GNU Affero General Public License, version 3, |
26 | as published by the Free Software Foundation. |
27 | |
28 | PerconaFT is distributed in the hope that it will be useful, |
29 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
30 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
31 | GNU Affero General Public License for more details. |
32 | |
33 | You should have received a copy of the GNU Affero General Public License |
34 | along with PerconaFT. If not, see <http://www.gnu.org/licenses/>. |
35 | ======= */ |
36 | |
37 | #ident "Copyright (c) 2006, 2015, Percona and/or its affiliates. All rights reserved." |
38 | |
39 | #pragma once |
40 | |
41 | #include <string.h> |
42 | #include <memory.h> |
43 | |
44 | namespace toku { |
45 | |
46 | template<typename sortdata_t, typename sortextra_t, int (*cmp)(sortextra_t &, const sortdata_t &, const sortdata_t &)> |
47 | struct sort { |
48 | |
49 | static const int single_threaded_threshold = 10000; |
50 | |
51 | /** |
52 | * Effect: Sort n elements of type sortdata_t in the array a. |
53 | * Elements are compared by the template parameter cmp, using |
54 | * the context in extra. |
55 | */ |
56 | static int |
57 | mergesort_r(sortdata_t *a, const int n, sortextra_t &) |
58 | { |
59 | sortdata_t *as[2] = { a, nullptr }; |
60 | if (n >= single_threaded_threshold) { |
61 | XMALLOC_N(n, as[1]); |
62 | } |
63 | int which = mergesort_internal(as, 0, n, extra); |
64 | if (which == 1) { |
65 | memcpy(a, as[1], n * (sizeof a[0])); |
66 | } |
67 | if (n >= single_threaded_threshold) { |
68 | toku_free(as[1]); |
69 | } |
70 | return 0; |
71 | } |
72 | |
73 | private: |
74 | |
75 | // Sorts the data in as[which]. Returns dest such that as[dest] |
76 | // contains the sorted data (might be which or 1-which). |
77 | static int |
78 | mergesort_internal(sortdata_t *as[2], const int which, const int n, sortextra_t &) |
79 | { |
80 | if (n <= 1) { return which; } |
81 | if (n < single_threaded_threshold) { |
82 | quicksort_r(as[which], n, extra); |
83 | return which; |
84 | } |
85 | const int mid = n / 2; |
86 | sortdata_t *right_as[2] = { &(as[0])[mid], &(as[1])[mid] }; |
87 | const int r1 = mergesort_internal(as, which, mid, extra); |
88 | const int r2 = mergesort_internal(right_as, which, n - mid, extra); |
89 | if (r1 != r2) { |
90 | // move everything to the same place (r2) |
91 | memcpy(as[r2], as[r1], mid * (sizeof as[r2][0])); |
92 | } |
93 | // now as[r2] has both sorted arrays |
94 | const int dest = 1 - r2; |
95 | merge(&(as[dest])[0], &(as[1-dest])[0], mid, &(as[1-dest])[mid], n - mid, extra); |
96 | return dest; |
97 | } |
98 | |
99 | static void |
100 | merge_c(sortdata_t *dest, const sortdata_t *a, const int an, const sortdata_t *b, const int bn, sortextra_t &) |
101 | { |
102 | int ai, bi, i; |
103 | for (ai = 0, bi = 0, i = 0; ai < an && bi < bn; ++i) { |
104 | if (cmp(extra, a[ai], b[bi]) < 0) { |
105 | dest[i] = a[ai]; |
106 | ai++; |
107 | } else { |
108 | dest[i] = b[bi]; |
109 | bi++; |
110 | } |
111 | } |
112 | if (ai < an) { |
113 | memcpy(&dest[i], &a[ai], (an - ai) * (sizeof dest[0])); |
114 | } else if (bi < bn) { |
115 | memcpy(&dest[i], &b[bi], (bn - bi) * (sizeof dest[0])); |
116 | } |
117 | } |
118 | |
119 | static int |
120 | binsearch(const sortdata_t &key, const sortdata_t *a, const int n, const int abefore, sortextra_t &) |
121 | { |
122 | if (n == 0) { |
123 | return abefore; |
124 | } |
125 | const int mid = n / 2; |
126 | const sortdata_t *akey = &a[mid]; |
127 | int c = cmp(extra, key, *akey); |
128 | if (c < 0) { |
129 | if (n == 1) { |
130 | return abefore; |
131 | } else { |
132 | return binsearch(key, a, mid, abefore, extra); |
133 | } |
134 | } else if (c > 0) { |
135 | if (n == 1) { |
136 | return abefore + 1; |
137 | } else { |
138 | return binsearch(key, akey, n - mid, abefore + mid, extra); |
139 | } |
140 | } else { |
141 | return abefore + mid; |
142 | } |
143 | } |
144 | |
145 | static void |
146 | merge(sortdata_t *dest, const sortdata_t *a_, const int an_, const sortdata_t *b_, const int bn_, sortextra_t &) |
147 | { |
148 | if (an_ + bn_ < single_threaded_threshold) { |
149 | merge_c(dest, a_, an_, b_, bn_, extra); |
150 | } else { |
151 | const bool swapargs = an_ < bn_; |
152 | const sortdata_t *a = swapargs ? b_ : a_; |
153 | const sortdata_t *b = swapargs ? a_ : b_; |
154 | const int an = swapargs ? bn_ : an_; |
155 | const int bn = swapargs ? an_ : bn_; |
156 | |
157 | const int a2 = an / 2; |
158 | const sortdata_t *akey = &a[a2]; |
159 | const int b2 = binsearch(*akey, b, bn, 0, extra); |
160 | merge(dest, a, a2, b, b2, extra); |
161 | merge(&dest[a2 + b2], akey, an - a2, &b[b2], bn - b2, extra); |
162 | } |
163 | } |
164 | |
165 | static void |
166 | quicksort_r(sortdata_t *a, const int n, sortextra_t &) |
167 | { |
168 | if (n > 1) { |
169 | const int lo = 0; |
170 | int pivot = n / 2; |
171 | const int hi = n - 1; |
172 | if (cmp(extra, a[lo], a[pivot]) > 0) { |
173 | const sortdata_t tmp = a[lo]; a[lo] = a[pivot]; a[pivot] = tmp; |
174 | } |
175 | if (cmp(extra, a[pivot], a[hi]) > 0) { |
176 | const sortdata_t tmp = a[pivot]; a[pivot] = a[hi]; a[hi] = tmp; |
177 | if (cmp(extra, a[lo], a[pivot]) > 0) { |
178 | const sortdata_t tmp2 = a[lo]; a[lo] = a[pivot]; a[pivot] = tmp2; |
179 | } |
180 | } |
181 | int li = lo + 1, ri = hi - 1; |
182 | while (li <= ri) { |
183 | while (cmp(extra, a[li], a[pivot]) < 0) { |
184 | li++; |
185 | } |
186 | while (cmp(extra, a[pivot], a[ri]) < 0) { |
187 | ri--; |
188 | } |
189 | if (li < ri) { |
190 | sortdata_t tmp = a[li]; a[li] = a[ri]; a[ri] = tmp; |
191 | // fix up pivot if we moved it |
192 | if (pivot == li) { pivot = ri; } |
193 | else if (pivot == ri) { pivot = li; } |
194 | li++; |
195 | ri--; |
196 | } else if (li == ri) { |
197 | li++; |
198 | ri--; |
199 | } |
200 | } |
201 | |
202 | quicksort_r(&a[lo], ri + 1, extra); |
203 | quicksort_r(&a[li], hi - li + 1, extra); |
204 | } |
205 | } |
206 | }; |
207 | |
208 | }; |
209 | |