summaryrefslogtreecommitdiff
path: root/boost/sort/spreadsort/detail/spreadsort_common.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/sort/spreadsort/detail/spreadsort_common.hpp')
-rw-r--r--boost/sort/spreadsort/detail/spreadsort_common.hpp248
1 files changed, 124 insertions, 124 deletions
diff --git a/boost/sort/spreadsort/detail/spreadsort_common.hpp b/boost/sort/spreadsort/detail/spreadsort_common.hpp
index 7b299ad5f3..7917fddae0 100644
--- a/boost/sort/spreadsort/detail/spreadsort_common.hpp
+++ b/boost/sort/spreadsort/detail/spreadsort_common.hpp
@@ -1,124 +1,124 @@
-// Contains get_min_count, the core optimization of the spreadsort algorithm.
-// Also has other helper functions commonly useful across variants.
-
-// Copyright Steven J. Ross 2001 - 2014.
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-// See http://www.boost.org/libs/sort for library home page.
-
-/*
-Some improvements suggested by:
-Phil Endecott and Frank Gennari
-*/
-
-#ifndef BOOST_SORT_SPREADSORT_DETAIL_SPREAD_SORT_COMMON_HPP
-#define BOOST_SORT_SPREADSORT_DETAIL_SPREAD_SORT_COMMON_HPP
-#include <algorithm>
-#include <vector>
-#include <cstring>
-#include <limits>
-#include <functional>
-#include <boost/static_assert.hpp>
-#include <boost/serialization/static_warning.hpp>
-#include <boost/sort/spreadsort/detail/constants.hpp>
-#include <boost/cstdint.hpp>
-
-namespace boost {
-namespace sort {
-namespace spreadsort {
- namespace detail {
- //This only works on unsigned data types
- template <typename T>
- inline unsigned
- rough_log_2_size(const T& input)
- {
- unsigned result = 0;
- //The && is necessary on some compilers to avoid infinite loops
- //it doesn't significantly impair performance
- while ((input >> result) && (result < (8*sizeof(T)))) ++result;
- return result;
- }
-
- //Gets the minimum size to call spreadsort on to control worst-case runtime.
- //This is called for a set of bins, instead of bin-by-bin, to minimize
- //runtime overhead.
- //This could be replaced by a lookup table of sizeof(Div_type)*8 but this
- //function is more general.
- template<unsigned log_mean_bin_size,
- unsigned log_min_split_count, unsigned log_finishing_count>
- inline size_t
- get_min_count(unsigned log_range)
- {
- const size_t typed_one = 1;
- const unsigned min_size = log_mean_bin_size + log_min_split_count;
- //Assuring that constants have valid settings
- BOOST_STATIC_ASSERT(log_min_split_count <= max_splits &&
- log_min_split_count > 0);
- BOOST_STATIC_ASSERT(max_splits > 1 &&
- max_splits < (8 * sizeof(unsigned)));
- BOOST_STATIC_ASSERT(max_finishing_splits >= max_splits &&
- max_finishing_splits < (8 * sizeof(unsigned)));
- BOOST_STATIC_ASSERT(log_mean_bin_size >= 0);
- BOOST_STATIC_ASSERT(log_finishing_count >= 0);
- //if we can complete in one iteration, do so
- //This first check allows the compiler to optimize never-executed code out
- if (log_finishing_count < min_size) {
- if (log_range <= min_size && log_range <= max_splits) {
- //Return no smaller than a certain minimum limit
- if (log_range <= log_finishing_count)
- return typed_one << log_finishing_count;
- return typed_one << log_range;
- }
- }
- const unsigned base_iterations = max_splits - log_min_split_count;
- //sum of n to n + x = ((x + 1) * (n + (n + x)))/2 + log_mean_bin_size
- const unsigned base_range =
- ((base_iterations + 1) * (max_splits + log_min_split_count))/2
- + log_mean_bin_size;
- //Calculating the required number of iterations, and returning
- //1 << (iteration_count + min_size)
- if (log_range < base_range) {
- unsigned result = log_min_split_count;
- for (unsigned offset = min_size; offset < log_range;
- offset += ++result);
- //Preventing overflow; this situation shouldn't occur
- if ((result + log_mean_bin_size) >= (8 * sizeof(size_t)))
- return typed_one << ((8 * sizeof(size_t)) - 1);
- return typed_one << (result + log_mean_bin_size);
- }
- //A quick division can calculate the worst-case runtime for larger ranges
- unsigned remainder = log_range - base_range;
- //the max_splits - 1 is used to calculate the ceiling of the division
- unsigned bit_length = ((((max_splits - 1) + remainder)/max_splits)
- + base_iterations + min_size);
- //Preventing overflow; this situation shouldn't occur
- if (bit_length >= (8 * sizeof(size_t)))
- return typed_one << ((8 * sizeof(size_t)) - 1);
- //n(log_range)/max_splits + C, optimizing worst-case performance
- return typed_one << bit_length;
- }
-
- // Resizes the bin cache and bin sizes, and initializes each bin size to 0.
- // This generates the memory overhead to use in radix sorting.
- template <class RandomAccessIter>
- inline RandomAccessIter *
- size_bins(size_t *bin_sizes, std::vector<RandomAccessIter>
- &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
- {
- // Clear the bin sizes
- for (size_t u = 0; u < bin_count; u++)
- bin_sizes[u] = 0;
- //Make sure there is space for the bins
- cache_end = cache_offset + bin_count;
- if (cache_end > bin_cache.size())
- bin_cache.resize(cache_end);
- return &(bin_cache[cache_offset]);
- }
- }
-}
-}
-}
-
-#endif
+// Contains get_min_count, the core optimization of the spreadsort algorithm.
+// Also has other helper functions commonly useful across variants.
+
+// Copyright Steven J. Ross 2001 - 2014.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/libs/sort for library home page.
+
+/*
+Some improvements suggested by:
+Phil Endecott and Frank Gennari
+*/
+
+#ifndef BOOST_SORT_SPREADSORT_DETAIL_SPREAD_SORT_COMMON_HPP
+#define BOOST_SORT_SPREADSORT_DETAIL_SPREAD_SORT_COMMON_HPP
+#include <algorithm>
+#include <vector>
+#include <cstring>
+#include <limits>
+#include <functional>
+#include <boost/static_assert.hpp>
+#include <boost/serialization/static_warning.hpp>
+#include <boost/sort/spreadsort/detail/constants.hpp>
+#include <boost/cstdint.hpp>
+
+namespace boost {
+namespace sort {
+namespace spreadsort {
+ namespace detail {
+ //This only works on unsigned data types
+ template <typename T>
+ inline unsigned
+ rough_log_2_size(const T& input)
+ {
+ unsigned result = 0;
+ //The && is necessary on some compilers to avoid infinite loops
+ //it doesn't significantly impair performance
+ while ((input >> result) && (result < (8*sizeof(T)))) ++result;
+ return result;
+ }
+
+ //Gets the minimum size to call spreadsort on to control worst-case runtime.
+ //This is called for a set of bins, instead of bin-by-bin, to minimize
+ //runtime overhead.
+ //This could be replaced by a lookup table of sizeof(Div_type)*8 but this
+ //function is more general.
+ template<unsigned log_mean_bin_size,
+ unsigned log_min_split_count, unsigned log_finishing_count>
+ inline size_t
+ get_min_count(unsigned log_range)
+ {
+ const size_t typed_one = 1;
+ const unsigned min_size = log_mean_bin_size + log_min_split_count;
+ //Assuring that constants have valid settings
+ BOOST_STATIC_ASSERT(log_min_split_count <= max_splits &&
+ log_min_split_count > 0);
+ BOOST_STATIC_ASSERT(max_splits > 1 &&
+ max_splits < (8 * sizeof(unsigned)));
+ BOOST_STATIC_ASSERT(max_finishing_splits >= max_splits &&
+ max_finishing_splits < (8 * sizeof(unsigned)));
+ BOOST_STATIC_ASSERT(log_mean_bin_size >= 0);
+ BOOST_STATIC_ASSERT(log_finishing_count >= 0);
+ //if we can complete in one iteration, do so
+ //This first check allows the compiler to optimize never-executed code out
+ if (log_finishing_count < min_size) {
+ if (log_range <= min_size && log_range <= max_splits) {
+ //Return no smaller than a certain minimum limit
+ if (log_range <= log_finishing_count)
+ return typed_one << log_finishing_count;
+ return typed_one << log_range;
+ }
+ }
+ const unsigned base_iterations = max_splits - log_min_split_count;
+ //sum of n to n + x = ((x + 1) * (n + (n + x)))/2 + log_mean_bin_size
+ const unsigned base_range =
+ ((base_iterations + 1) * (max_splits + log_min_split_count))/2
+ + log_mean_bin_size;
+ //Calculating the required number of iterations, and returning
+ //1 << (iteration_count + min_size)
+ if (log_range < base_range) {
+ unsigned result = log_min_split_count;
+ for (unsigned offset = min_size; offset < log_range;
+ offset += ++result);
+ //Preventing overflow; this situation shouldn't occur
+ if ((result + log_mean_bin_size) >= (8 * sizeof(size_t)))
+ return typed_one << ((8 * sizeof(size_t)) - 1);
+ return typed_one << (result + log_mean_bin_size);
+ }
+ //A quick division can calculate the worst-case runtime for larger ranges
+ unsigned remainder = log_range - base_range;
+ //the max_splits - 1 is used to calculate the ceiling of the division
+ unsigned bit_length = ((((max_splits - 1) + remainder)/max_splits)
+ + base_iterations + min_size);
+ //Preventing overflow; this situation shouldn't occur
+ if (bit_length >= (8 * sizeof(size_t)))
+ return typed_one << ((8 * sizeof(size_t)) - 1);
+ //n(log_range)/max_splits + C, optimizing worst-case performance
+ return typed_one << bit_length;
+ }
+
+ // Resizes the bin cache and bin sizes, and initializes each bin size to 0.
+ // This generates the memory overhead to use in radix sorting.
+ template <class RandomAccessIter>
+ inline RandomAccessIter *
+ size_bins(size_t *bin_sizes, std::vector<RandomAccessIter>
+ &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
+ {
+ // Clear the bin sizes
+ for (size_t u = 0; u < bin_count; u++)
+ bin_sizes[u] = 0;
+ //Make sure there is space for the bins
+ cache_end = cache_offset + bin_count;
+ if (cache_end > bin_cache.size())
+ bin_cache.resize(cache_end);
+ return &(bin_cache[cache_offset]);
+ }
+ }
+}
+}
+}
+
+#endif