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/*======
5This file is part of PerconaFT.
6
7
8Copyright (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
44namespace 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 &extra)
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 &extra)
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 &extra)
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 &extra)
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 &extra)
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 &extra)
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