ceph/src/boost/libs/sort/include/boost/sort/spreadsort/detail/integer_sort.hpp

   1 // Details for templated Spreadsort-based integer_sort.
   2
   3 //          Copyright Steven J. Ross 2001 - 2014.
   4 // Distributed under the Boost Software License, Version 1.0.
   5 //    (See accompanying file LICENSE_1_0.txt or copy at
   6 //          http://www.boost.org/LICENSE_1_0.txt)
   7
   8 // See http://www.boost.org/libs/sort for library home page.
   9
  10 /*
  11 Some improvements suggested by:
  12 Phil Endecott and Frank Gennari
  13 */
  14
  15 #ifndef BOOST_SORT_SPREADSORT_DETAIL_INTEGER_SORT_HPP
  16 #define BOOST_SORT_SPREADSORT_DETAIL_INTEGER_SORT_HPP
  17 #include <algorithm>
  18 #include <vector>
  19 #include <limits>
  20 #include <functional>
  21 #include <boost/static_assert.hpp>
  22 #include <boost/serialization/static_warning.hpp>
  23 #include <boost/utility/enable_if.hpp>
  24 #include <boost/sort/spreadsort/detail/constants.hpp>
  25 #include <boost/sort/spreadsort/detail/spreadsort_common.hpp>
  26 #include <boost/cstdint.hpp>
  27
  28 namespace boost {
  29 namespace sort {
  30 namespace spreadsort {
  31   namespace detail {
  32     // Return true if the list is sorted.  Otherwise, find the minimum and
  33     // maximum using <.
  34     template <class RandomAccessIter>
  35     inline bool
  36     is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
  37                                RandomAccessIter & max, RandomAccessIter & min)
  38     {
  39       min = max = current;
  40       //This assumes we have more than 1 element based on prior checks.
  41       while (!(*(current + 1) < *current)) {
  42         //If everything is in sorted order, return
  43         if (++current == last - 1)
  44           return true;
  45       }
  46
  47       //The maximum is the last sorted element
  48       max = current;
  49       //Start from the first unsorted element
  50       while (++current < last) {
  51         if (*max < *current)
  52           max = current;
  53         else if (*current < *min)
  54           min = current;
  55       }
  56       return false;
  57     }
  58
  59     // Return true if the list is sorted.  Otherwise, find the minimum and
  60     // maximum.
  61     // Use a user-defined comparison operator
  62     template <class RandomAccessIter, class Compare>
  63     inline bool
  64     is_sorted_or_find_extremes(RandomAccessIter current, RandomAccessIter last,
  65                 RandomAccessIter & max, RandomAccessIter & min, Compare comp)
  66     {
  67       min = max = current;
  68       while (!comp(*(current + 1), *current)) {
  69         //If everything is in sorted order, return
  70         if (++current == last - 1)
  71           return true;
  72       }
  73
  74       //The maximum is the last sorted element
  75       max = current;
  76       while (++current < last) {
  77         if (comp(*max, *current))
  78           max = current;
  79         else if (comp(*current, *min))
  80           min = current;
  81       }
  82       return false;
  83     }
  84
  85     //Gets a non-negative right bit shift to operate as a logarithmic divisor
  86     template<unsigned log_mean_bin_size>
  87     inline int
  88     get_log_divisor(size_t count, int log_range)
  89     {
  90       int log_divisor;
  91       //If we can finish in one iteration without exceeding either
  92       //(2 to the max_finishing_splits) or n bins, do so
  93       if ((log_divisor = log_range - rough_log_2_size(count)) <= 0 &&
  94          log_range <= max_finishing_splits)
  95         log_divisor = 0;
  96       else {
  97         //otherwise divide the data into an optimized number of pieces
  98         log_divisor += log_mean_bin_size;
  99         //Cannot exceed max_splits or cache misses slow down bin lookups
 100         if ((log_range - log_divisor) > max_splits)
 101           log_divisor = log_range - max_splits;
 102       }
 103       return log_divisor;
 104     }
 105
 106     //Implementation for recursive integer sorting
 107     template <class RandomAccessIter, class Div_type, class Size_type>
 108     inline void
 109     spreadsort_rec(RandomAccessIter first, RandomAccessIter last,
 110               std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
 111               , size_t *bin_sizes)
 112     {
 113       //This step is roughly 10% of runtime, but it helps avoid worst-case
 114       //behavior and improve behavior with real data
 115       //If you know the maximum and minimum ahead of time, you can pass those
 116       //values in and skip this step for the first iteration
 117       RandomAccessIter max, min;
 118       if (is_sorted_or_find_extremes(first, last, max, min))
 119         return;
 120       RandomAccessIter * target_bin;
 121       unsigned log_divisor = get_log_divisor<int_log_mean_bin_size>(
 122           last - first, rough_log_2_size(Size_type((*max >> 0) - (*min >> 0))));
 123       Div_type div_min = *min >> log_divisor;
 124       Div_type div_max = *max >> log_divisor;
 125       unsigned bin_count = unsigned(div_max - div_min) + 1;
 126       unsigned cache_end;
 127       RandomAccessIter * bins =
 128         size_bins(bin_sizes, bin_cache, cache_offset, cache_end, bin_count);
 129
 130       //Calculating the size of each bin; this takes roughly 10% of runtime
 131       for (RandomAccessIter current = first; current != last;)
 132         bin_sizes[size_t((*(current++) >> log_divisor) - div_min)]++;
 133       //Assign the bin positions
 134       bins[0] = first;
 135       for (unsigned u = 0; u < bin_count - 1; u++)
 136         bins[u + 1] = bins[u] + bin_sizes[u];
 137
 138       RandomAccessIter nextbinstart = first;
 139       //Swap into place
 140       //This dominates runtime, mostly in the swap and bin lookups
 141       for (unsigned u = 0; u < bin_count - 1; ++u) {
 142         RandomAccessIter * local_bin = bins + u;
 143         nextbinstart += bin_sizes[u];
 144         //Iterating over each element in this bin
 145         for (RandomAccessIter current = *local_bin; current < nextbinstart;
 146             ++current) {
 147           //Swapping elements in current into place until the correct
 148           //element has been swapped in
 149           for (target_bin = (bins + ((*current >> log_divisor) - div_min));
 150               target_bin != local_bin;
 151             target_bin = bins + ((*current >> log_divisor) - div_min)) {
 152             //3-way swap; this is about 1% faster than a 2-way swap
 153             //The main advantage is less copies are involved per item
 154             //put in the correct place
 155             typename std::iterator_traits<RandomAccessIter>::value_type tmp;
 156             RandomAccessIter b = (*target_bin)++;
 157             RandomAccessIter * b_bin = bins + ((*b >> log_divisor) - div_min);
 158             if (b_bin != local_bin) {
 159               RandomAccessIter c = (*b_bin)++;
 160               tmp = *c;
 161               *c = *b;
 162             }
 163             else
 164               tmp = *b;
 165             *b = *current;
 166             *current = tmp;
 167           }
 168         }
 169         *local_bin = nextbinstart;
 170       }
 171       bins[bin_count - 1] = last;
 172
 173       //If we've bucketsorted, the array is sorted and we should skip recursion
 174       if (!log_divisor)
 175         return;
 176       //log_divisor is the remaining range; calculating the comparison threshold
 177       size_t max_count =
 178         get_min_count<int_log_mean_bin_size, int_log_min_split_count,
 179                       int_log_finishing_count>(log_divisor);
 180
 181       //Recursing
 182       RandomAccessIter lastPos = first;
 183       for (unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u],
 184           ++u) {
 185         Size_type count = bin_cache[u] - lastPos;
 186         //don't sort unless there are at least two items to Compare
 187         if (count < 2)
 188           continue;
 189         //using std::sort if its worst-case is better
 190         if (count < max_count)
 191           std::sort(lastPos, bin_cache[u]);
 192         else
 193           spreadsort_rec<RandomAccessIter, Div_type, Size_type>(lastPos,
 194                                                                  bin_cache[u],
 195                                                                  bin_cache,
 196                                                                  cache_end,
 197                                                                  bin_sizes);
 198       }
 199     }
 200
 201     //Generic bitshift-based 3-way swapping code
 202     template <class RandomAccessIter, class Div_type, class Right_shift>
 203     inline void inner_swap_loop(RandomAccessIter * bins,
 204       const RandomAccessIter & next_bin_start, unsigned ii, Right_shift &rshift
 205       , const unsigned log_divisor, const Div_type div_min)
 206     {
 207       RandomAccessIter * local_bin = bins + ii;
 208       for (RandomAccessIter current = *local_bin; current < next_bin_start;
 209           ++current) {
 210         for (RandomAccessIter * target_bin =
 211             (bins + (rshift(*current, log_divisor) - div_min));
 212             target_bin != local_bin;
 213             target_bin = bins + (rshift(*current, log_divisor) - div_min)) {
 214           typename std::iterator_traits<RandomAccessIter>::value_type tmp;
 215           RandomAccessIter b = (*target_bin)++;
 216           RandomAccessIter * b_bin =
 217             bins + (rshift(*b, log_divisor) - div_min);
 218           //Three-way swap; if the item to be swapped doesn't belong
 219           //in the current bin, swap it to where it belongs
 220           if (b_bin != local_bin) {
 221             RandomAccessIter c = (*b_bin)++;
 222             tmp = *c;
 223             *c = *b;
 224           }
 225           //Note: we could increment current once the swap is done in this case
 226           //but that seems to impair performance
 227           else
 228             tmp = *b;
 229           *b = *current;
 230           *current = tmp;
 231         }
 232       }
 233       *local_bin = next_bin_start;
 234     }
 235
 236     //Standard swapping wrapper for ascending values
 237     template <class RandomAccessIter, class Div_type, class Right_shift>
 238     inline void swap_loop(RandomAccessIter * bins,
 239              RandomAccessIter & next_bin_start, unsigned ii, Right_shift &rshift
 240              , const size_t *bin_sizes
 241              , const unsigned log_divisor, const Div_type div_min)
 242     {
 243       next_bin_start += bin_sizes[ii];
 244       inner_swap_loop<RandomAccessIter, Div_type, Right_shift>(bins,
 245                               next_bin_start, ii, rshift, log_divisor, div_min);
 246     }
 247
 248     //Functor implementation for recursive sorting
 249     template <class RandomAccessIter, class Div_type, class Right_shift,
 250               class Compare, class Size_type, unsigned log_mean_bin_size,
 251                 unsigned log_min_split_count, unsigned log_finishing_count>
 252     inline void
 253     spreadsort_rec(RandomAccessIter first, RandomAccessIter last,
 254           std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
 255           , size_t *bin_sizes, Right_shift rshift, Compare comp)
 256     {
 257       RandomAccessIter max, min;
 258       if (is_sorted_or_find_extremes(first, last, max, min, comp))
 259         return;
 260       unsigned log_divisor = get_log_divisor<log_mean_bin_size>(last - first,
 261             rough_log_2_size(Size_type(rshift(*max, 0) - rshift(*min, 0))));
 262       Div_type div_min = rshift(*min, log_divisor);
 263       Div_type div_max = rshift(*max, log_divisor);
 264       unsigned bin_count = unsigned(div_max - div_min) + 1;
 265       unsigned cache_end;
 266       RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
 267                                           cache_end, bin_count);
 268
 269       //Calculating the size of each bin
 270       for (RandomAccessIter current = first; current != last;)
 271         bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++;
 272       bins[0] = first;
 273       for (unsigned u = 0; u < bin_count - 1; u++)
 274         bins[u + 1] = bins[u] + bin_sizes[u];
 275
 276       //Swap into place
 277       RandomAccessIter next_bin_start = first;
 278       for (unsigned u = 0; u < bin_count - 1; ++u)
 279         swap_loop<RandomAccessIter, Div_type, Right_shift>(bins, next_bin_start,
 280                                   u, rshift, bin_sizes, log_divisor, div_min);
 281       bins[bin_count - 1] = last;
 282
 283       //If we've bucketsorted, the array is sorted
 284       if (!log_divisor)
 285         return;
 286
 287       //Recursing
 288       size_t max_count = get_min_count<log_mean_bin_size, log_min_split_count,
 289                           log_finishing_count>(log_divisor);
 290       RandomAccessIter lastPos = first;
 291       for (unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u],
 292           ++u) {
 293         size_t count = bin_cache[u] - lastPos;
 294         if (count < 2)
 295           continue;
 296         if (count < max_count)
 297           std::sort(lastPos, bin_cache[u], comp);
 298         else
 299           spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
 300         Size_type, log_mean_bin_size, log_min_split_count, log_finishing_count>
 301       (lastPos, bin_cache[u], bin_cache, cache_end, bin_sizes, rshift, comp);
 302       }
 303     }
 304
 305     //Functor implementation for recursive sorting with only Shift overridden
 306     template <class RandomAccessIter, class Div_type, class Right_shift,
 307               class Size_type, unsigned log_mean_bin_size,
 308               unsigned log_min_split_count, unsigned log_finishing_count>
 309     inline void
 310     spreadsort_rec(RandomAccessIter first, RandomAccessIter last,
 311               std::vector<RandomAccessIter> &bin_cache, unsigned cache_offset
 312               , size_t *bin_sizes, Right_shift rshift)
 313     {
 314       RandomAccessIter max, min;
 315       if (is_sorted_or_find_extremes(first, last, max, min))
 316         return;
 317       unsigned log_divisor = get_log_divisor<log_mean_bin_size>(last - first,
 318             rough_log_2_size(Size_type(rshift(*max, 0) - rshift(*min, 0))));
 319       Div_type div_min = rshift(*min, log_divisor);
 320       Div_type div_max = rshift(*max, log_divisor);
 321       unsigned bin_count = unsigned(div_max - div_min) + 1;
 322       unsigned cache_end;
 323       RandomAccessIter * bins = size_bins(bin_sizes, bin_cache, cache_offset,
 324                                           cache_end, bin_count);
 325
 326       //Calculating the size of each bin
 327       for (RandomAccessIter current = first; current != last;)
 328         bin_sizes[unsigned(rshift(*(current++), log_divisor) - div_min)]++;
 329       bins[0] = first;
 330       for (unsigned u = 0; u < bin_count - 1; u++)
 331         bins[u + 1] = bins[u] + bin_sizes[u];
 332
 333       //Swap into place
 334       RandomAccessIter nextbinstart = first;
 335       for (unsigned ii = 0; ii < bin_count - 1; ++ii)
 336         swap_loop<RandomAccessIter, Div_type, Right_shift>(bins, nextbinstart,
 337                                 ii, rshift, bin_sizes, log_divisor, div_min);
 338       bins[bin_count - 1] = last;
 339
 340       //If we've bucketsorted, the array is sorted
 341       if (!log_divisor)
 342         return;
 343
 344       //Recursing
 345       size_t max_count = get_min_count<log_mean_bin_size, log_min_split_count,
 346                           log_finishing_count>(log_divisor);
 347       RandomAccessIter lastPos = first;
 348       for (unsigned u = cache_offset; u < cache_end; lastPos = bin_cache[u],
 349           ++u) {
 350         size_t count = bin_cache[u] - lastPos;
 351         if (count < 2)
 352           continue;
 353         if (count < max_count)
 354           std::sort(lastPos, bin_cache[u]);
 355         else
 356           spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Size_type,
 357           log_mean_bin_size, log_min_split_count, log_finishing_count>(lastPos,
 358                       bin_cache[u], bin_cache, cache_end, bin_sizes, rshift);
 359       }
 360     }
 361
 362     //Holds the bin vector and makes the initial recursive call
 363     template <class RandomAccessIter, class Div_type>
 364     //Only use spreadsort if the integer can fit in a size_t
 365     inline typename boost::enable_if_c< sizeof(Div_type) <= sizeof(size_t),
 366                                                             void >::type
 367     integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type)
 368     {
 369       size_t bin_sizes[1 << max_finishing_splits];
 370       std::vector<RandomAccessIter> bin_cache;
 371       spreadsort_rec<RandomAccessIter, Div_type, size_t>(first, last,
 372           bin_cache, 0, bin_sizes);
 373     }
 374
 375     //Holds the bin vector and makes the initial recursive call
 376     template <class RandomAccessIter, class Div_type>
 377     //Only use spreadsort if the integer can fit in a uintmax_t
 378     inline typename boost::enable_if_c< (sizeof(Div_type) > sizeof(size_t))
 379       && sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type
 380     integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type)
 381     {
 382       size_t bin_sizes[1 << max_finishing_splits];
 383       std::vector<RandomAccessIter> bin_cache;
 384       spreadsort_rec<RandomAccessIter, Div_type, boost::uintmax_t>(first,
 385           last, bin_cache, 0, bin_sizes);
 386     }
 387
 388     template <class RandomAccessIter, class Div_type>
 389     inline typename boost::disable_if_c< sizeof(Div_type) <= sizeof(size_t)
 390       || sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type
 391     //defaulting to std::sort when integer_sort won't work
 392     integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type)
 393     {
 394       //Warning that we're using std::sort, even though integer_sort was called
 395       BOOST_STATIC_WARNING( sizeof(Div_type) <= sizeof(size_t) );
 396       std::sort(first, last);
 397     }
 398
 399
 400     //Same for the full functor version
 401     template <class RandomAccessIter, class Div_type, class Right_shift,
 402               class Compare>
 403     //Only use spreadsort if the integer can fit in a size_t
 404     inline typename boost::enable_if_c< sizeof(Div_type) <= sizeof(size_t),
 405                                  void >::type
 406     integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 407                 Right_shift shift, Compare comp)
 408     {
 409       size_t bin_sizes[1 << max_finishing_splits];
 410       std::vector<RandomAccessIter> bin_cache;
 411       spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
 412           size_t, int_log_mean_bin_size, int_log_min_split_count,
 413                         int_log_finishing_count>
 414           (first, last, bin_cache, 0, bin_sizes, shift, comp);
 415     }
 416
 417     template <class RandomAccessIter, class Div_type, class Right_shift,
 418               class Compare>
 419     //Only use spreadsort if the integer can fit in a uintmax_t
 420     inline typename boost::enable_if_c< (sizeof(Div_type) > sizeof(size_t))
 421       && sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type
 422     integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 423                 Right_shift shift, Compare comp)
 424     {
 425       size_t bin_sizes[1 << max_finishing_splits];
 426       std::vector<RandomAccessIter> bin_cache;
 427       spreadsort_rec<RandomAccessIter, Div_type, Right_shift, Compare,
 428                         boost::uintmax_t, int_log_mean_bin_size,
 429                         int_log_min_split_count, int_log_finishing_count>
 430           (first, last, bin_cache, 0, bin_sizes, shift, comp);
 431     }
 432
 433     template <class RandomAccessIter, class Div_type, class Right_shift,
 434               class Compare>
 435     inline typename boost::disable_if_c< sizeof(Div_type) <= sizeof(size_t)
 436       || sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type
 437     //defaulting to std::sort when integer_sort won't work
 438     integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 439                 Right_shift shift, Compare comp)
 440     {
 441       //Warning that we're using std::sort, even though integer_sort was called
 442       BOOST_STATIC_WARNING( sizeof(Div_type) <= sizeof(size_t) );
 443       std::sort(first, last, comp);
 444     }
 445
 446
 447     //Same for the right shift version
 448     template <class RandomAccessIter, class Div_type, class Right_shift>
 449     //Only use spreadsort if the integer can fit in a size_t
 450     inline typename boost::enable_if_c< sizeof(Div_type) <= sizeof(size_t),
 451                                  void >::type
 452     integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 453                 Right_shift shift)
 454     {
 455       size_t bin_sizes[1 << max_finishing_splits];
 456       std::vector<RandomAccessIter> bin_cache;
 457       spreadsort_rec<RandomAccessIter, Div_type, Right_shift, size_t,
 458           int_log_mean_bin_size, int_log_min_split_count,
 459                         int_log_finishing_count>
 460           (first, last, bin_cache, 0, bin_sizes, shift);
 461     }
 462
 463     template <class RandomAccessIter, class Div_type, class Right_shift>
 464     //Only use spreadsort if the integer can fit in a uintmax_t
 465     inline typename boost::enable_if_c< (sizeof(Div_type) > sizeof(size_t))
 466       && sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type
 467     integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 468                 Right_shift shift)
 469     {
 470       size_t bin_sizes[1 << max_finishing_splits];
 471       std::vector<RandomAccessIter> bin_cache;
 472       spreadsort_rec<RandomAccessIter, Div_type, Right_shift,
 473                         boost::uintmax_t, int_log_mean_bin_size,
 474                         int_log_min_split_count, int_log_finishing_count>
 475           (first, last, bin_cache, 0, bin_sizes, shift);
 476     }
 477
 478     template <class RandomAccessIter, class Div_type, class Right_shift>
 479     inline typename boost::disable_if_c< sizeof(Div_type) <= sizeof(size_t)
 480       || sizeof(Div_type) <= sizeof(boost::uintmax_t), void >::type
 481     //defaulting to std::sort when integer_sort won't work
 482     integer_sort(RandomAccessIter first, RandomAccessIter last, Div_type,
 483                 Right_shift shift)
 484     {
 485       //Warning that we're using std::sort, even though integer_sort was called
 486       BOOST_STATIC_WARNING( sizeof(Div_type) <= sizeof(size_t) );
 487       std::sort(first, last);
 488     }
 489   }
 490 }
 491 }
 492 }
 493
 494 #endif