diff options
Diffstat (limited to 'storage/tokudb/PerconaFT/util/sort.h')
| -rw-r--r-- | storage/tokudb/PerconaFT/util/sort.h | 208 |
1 files changed, 208 insertions, 0 deletions
diff --git a/storage/tokudb/PerconaFT/util/sort.h b/storage/tokudb/PerconaFT/util/sort.h new file mode 100644 index 00000000000..0f0bb7ee940 --- /dev/null +++ b/storage/tokudb/PerconaFT/util/sort.h @@ -0,0 +1,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); + } + } + }; + +}; |