1 files changed, 124 insertions, 0 deletions
diff --git a/boost/sort/spreadsort/detail/spreadsort_common.hpp b/boost/sort/spreadsort/detail/spreadsort_common.hpp
new file mode 100644
index 0000000000..7b299ad5f3
--- /dev/null
+++ b/boost/sort/spreadsort/detail/spreadsort_common.hpp
@@ -0,0 +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