spreadsort/detail/spreadsort_common.hpp

0001 // Contains get_min_count, the core optimization of the spreadsort algorithm.
0002 // Also has other helper functions commonly useful across variants.
0003
0004 //          Copyright Steven J. Ross 2001 - 2014.
0005 // Distributed under the Boost Software License, Version 1.0.
0006 //    (See accompanying file LICENSE_1_0.txt or copy at
0007 //          http://www.boost.org/LICENSE_1_0.txt)
0008
0009 // See http://www.boost.org/libs/sort for library home page.
0010
0011 /*
0012 Some improvements suggested by:
0013 Phil Endecott and Frank Gennari
0014 */
0015
0016 #ifndef BOOST_SORT_SPREADSORT_DETAIL_SPREAD_SORT_COMMON_HPP
0017 #define BOOST_SORT_SPREADSORT_DETAIL_SPREAD_SORT_COMMON_HPP
0018 #include <algorithm>
0019 #include <vector>
0020 #include <cstring>
0021 #include <limits>
0022 #include <functional>
0023 #include <boost/static_assert.hpp>
0024 #include <boost/sort/pdqsort/pdqsort.hpp>
0025 #include <boost/sort/spreadsort/detail/constants.hpp>
0026 #include <boost/cstdint.hpp>
0027
0028 namespace boost {
0029 namespace sort {
0030 namespace spreadsort {
0031  namespace detail {
0032     //This only works on unsigned data types
0033     template <typename T>
0034     inline unsigned
0035     rough_log_2_size(const T& input)
0036     {
0037       unsigned result = 0;
0038       //The && is necessary on some compilers to avoid infinite loops
0039       //it doesn't significantly impair performance
0040       while ((result < (8*sizeof(T))) && (input >> result)) ++result;
0041       return result;
0042     }
0043
0044     //Gets the minimum size to call spreadsort on to control worst-case runtime.
0045     //This is called for a set of bins, instead of bin-by-bin, to minimize
0046     //runtime overhead.
0047     //This could be replaced by a lookup table of sizeof(Div_type)*8 but this
0048     //function is more general.
0049     template<unsigned log_mean_bin_size,
0050       unsigned log_min_split_count, unsigned log_finishing_count>
0051     inline size_t
0052     get_min_count(unsigned log_range)
0053     {
0054       const size_t typed_one = 1;
0055       const unsigned min_size = log_mean_bin_size + log_min_split_count;
0056       //Assuring that constants have valid settings
0057       BOOST_STATIC_ASSERT(log_min_split_count <= max_splits &&
0058                           log_min_split_count > 0);
0059       BOOST_STATIC_ASSERT(max_splits > 1 &&
0060                           max_splits < (8 * sizeof(unsigned)));
0061       BOOST_STATIC_ASSERT(max_finishing_splits >= max_splits &&
0062                           max_finishing_splits < (8 * sizeof(unsigned)));
0063       BOOST_STATIC_ASSERT(log_mean_bin_size >= 0);
0064       BOOST_STATIC_ASSERT(log_finishing_count >= 0);
0065       //if we can complete in one iteration, do so
0066       //This first check allows the compiler to optimize never-executed code out
0067       if (log_finishing_count < min_size) {
0068         if (log_range <= min_size && log_range <= max_splits) {
0069           //Return no smaller than a certain minimum limit
0070           if (log_range <= log_finishing_count)
0071             return typed_one << log_finishing_count;
0072           return typed_one << log_range;
0073         }
0074       }
0075       const unsigned base_iterations = max_splits - log_min_split_count;
0076       //sum of n to n + x = ((x + 1) * (n + (n + x)))/2 + log_mean_bin_size
0077       const unsigned base_range =
0078           ((base_iterations + 1) * (max_splits + log_min_split_count))/2
0079           + log_mean_bin_size;
0080       //Calculating the required number of iterations, and returning
0081       //1 << (iteration_count + min_size)
0082       if (log_range < base_range) {
0083         unsigned result = log_min_split_count;
0084         for (unsigned offset = min_size; offset < log_range;
0085           offset += ++result);
0086         //Preventing overflow; this situation shouldn't occur
0087         if ((result + log_mean_bin_size) >= (8 * sizeof(size_t)))
0088           return typed_one << ((8 * sizeof(size_t)) - 1);
0089         return typed_one << (result + log_mean_bin_size);
0090       }
0091       //A quick division can calculate the worst-case runtime for larger ranges
0092       unsigned remainder = log_range - base_range;
0093       //the max_splits - 1 is used to calculate the ceiling of the division
0094       unsigned bit_length = ((((max_splits - 1) + remainder)/max_splits)
0095         + base_iterations + min_size);
0096       //Preventing overflow; this situation shouldn't occur
0097       if (bit_length >= (8 * sizeof(size_t)))
0098         return typed_one << ((8 * sizeof(size_t)) - 1);
0099       //n(log_range)/max_splits + C, optimizing worst-case performance
0100       return typed_one << bit_length;
0101     }
0102
0103     // Resizes the bin cache and bin sizes, and initializes each bin size to 0.
0104     // This generates the memory overhead to use in radix sorting.
0105     template <class RandomAccessIter>
0106     inline RandomAccessIter *
0107     size_bins(size_t *bin_sizes, std::vector<RandomAccessIter>
0108   &bin_cache, unsigned cache_offset, unsigned &cache_end, unsigned bin_count)
0109     {
0110       // Clear the bin sizes
0111       for (size_t u = 0; u < bin_count; u++)
0112         bin_sizes[u] = 0;
0113       //Make sure there is space for the bins
0114       cache_end = cache_offset + bin_count;
0115       if (cache_end > bin_cache.size())
0116         bin_cache.resize(cache_end);
0117       return &(bin_cache[cache_offset]);
0118     }
0119   }
0120 }
0121 }
0122 }
0123
0124 #endif