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