ceph/src/boost/boost/sort/spinsort/spinsort.hpp

   1 //----------------------------------------------------------------------------
   2 /// @file spinsort.hpp
   3 /// @brief Spin Sort algorithm
   4 ///
   5 /// @author Copyright (c) 2016 Francisco José Tapia (fjtapia@gmail.com )\n
   6 ///         Distributed under the Boost Software License, Version 1.0.\n
   7 ///         ( See accompanying file LICENSE_1_0.txt or copy at
   8 ///           http://www.boost.org/LICENSE_1_0.txt  )
   9 /// @version 0.1
  10 ///
  11 /// @remarks
  12 //-----------------------------------------------------------------------------
  13 #ifndef __BOOST_SORT_PARALLEL_ALGORITHM_SPIN_SORT_HPP
  14 #define __BOOST_SORT_PARALLEL_ALGORITHM_SPIN_SORT_HPP
  15
  16 //#include <boost/sort/spinsort/util/indirect.hpp>
  17 #include <boost/sort/insert_sort/insert_sort.hpp>
  18 #include <boost/sort/common/util/traits.hpp>
  19 #include <boost/sort/common/util/algorithm.hpp>
  20 #include <boost/sort/common/range.hpp>
  21 #include <boost/sort/common/indirect.hpp>
  22 #include <cstdlib>
  23 #include <functional>
  24 #include <iterator>
  25 #include <memory>
  26 #include <type_traits>
  27 #include <vector>
  28 #include <cstddef>
  29
  30 namespace boost
  31 {
  32 namespace sort
  33 {
  34 namespace spin_detail
  35 {
  36
  37 //----------------------------------------------------------------------------
  38 //                USING SENTENCES
  39 //----------------------------------------------------------------------------
  40 namespace bsc = boost::sort::common;
  41 using bsc::range;
  42 using bsc::util::nbits64;
  43 using bsc::util::compare_iter;
  44 using bsc::util::value_iter;
  45 using boost::sort::insert_sort;
  46
  47 //
  48 //############################################################################
  49 //                                                                          ##
  50 //          D E F I N I T I O N S    O F    F U N C T I O N S               ##
  51 //                                                                          ##
  52 //############################################################################
  53 //
  54 template <class Iter1_t, class Iter2_t, typename Compare>
  55 static void insert_partial_sort (Iter1_t first, Iter1_t mid,
  56                                  Iter1_t last, Compare comp,
  57                                  const range<Iter2_t> &rng_aux);
  58
  59 template<class Iter1_t, class Iter2_t, class Compare>
  60 static bool check_stable_sort (const range<Iter1_t> &rng_data,
  61                                const range<Iter2_t> &rng_aux, Compare comp);
  62
  63 template<class Iter1_t, class Iter2_t, class Compare>
  64 static void range_sort (const range<Iter1_t> &range1,
  65                         const range<Iter2_t> &range2, Compare comp,
  66                         uint32_t level);
  67
  68 template<class Iter1_t, class Iter2_t, class Compare>
  69 static void sort_range_sort (const range<Iter1_t> &rng_data,
  70                              const range<Iter2_t> &rng_aux, Compare comp);
  71
  72 //
  73 //-----------------------------------------------------------------------------
  74 //  function : insert_partial_sort
  75 /// @brief : Insertion sort of elements sorted
  76 /// @param first: iterator to the first element of the range
  77 /// @param mid : last pointer of the sorted data, and first pointer to the
  78 ///               elements to insert
  79 /// @param last : iterator to the next element of the last in the range
  80 /// @param comp :
  81 /// @comments : the two ranges are sorted
  82 //-----------------------------------------------------------------------------
  83 template<class Iter1_t, class Iter2_t, typename Compare>
  84 static void insert_partial_sort (Iter1_t first, Iter1_t mid, Iter1_t last,
  85                                  Compare comp, const range<Iter2_t> &rng_aux)
  86 {
  87     //------------------------------------------------------------------------
  88     //                 metaprogram
  89     //------------------------------------------------------------------------
  90     typedef value_iter<Iter1_t> value_t;
  91     typedef value_iter<Iter2_t> value2_t;
  92     static_assert (std::is_same<value_t, value2_t>::value,
  93                     "Incompatible iterators\n");
  94
  95     //--------------------------------------------------------------------
  96     //                   program
  97     //--------------------------------------------------------------------
  98     assert(size_t(last - mid) <= rng_aux.size());
  99
 100     if (mid == last) return;
 101     //insertionsort ( mid, last, comp);
 102     if (first == mid) return;
 103
 104     //------------------------------------------------------------------------
 105     // creation of the vector of elements to insert and their position in the
 106     // sorted part
 107     // the data are inserted in rng_aux
 108     //-----------------------------------------------------------------------
 109     std::vector<Iter1_t> viter;
 110     Iter2_t beta = rng_aux.first, data = rng_aux.first;
 111
 112     for (Iter1_t alpha = mid; alpha != last; ++alpha)
 113         *(beta++) = std::move(*alpha);
 114
 115     size_t ndata = last - mid;
 116
 117     Iter1_t linf = first, lsup = mid;
 118     for (uint32_t i = 0; i < ndata; ++i)
 119     {
 120         Iter1_t it1 = std::upper_bound(linf, lsup, *(data + i), comp);
 121         viter.push_back(it1);
 122         linf = it1;
 123     };
 124
 125     // moving the elements
 126     viter.push_back(mid);
 127     for (uint32_t i = viter.size() - 1; i != 0; --i)
 128     {
 129         Iter1_t src = viter[i], limit = viter[i - 1];
 130         Iter1_t dest = src + (i);
 131         while (src != limit) *(--dest) = std::move(*(--src));
 132         *(viter[i - 1] + (i - 1)) = std::move(*(data + (i - 1)));
 133     };
 134 }
 135 ;
 136 //-----------------------------------------------------------------------------
 137 //  function : check_stable_sort
 138 /// @brief check if the elements between first and last are osted or reverse
 139 ///        sorted. If the number of elements not sorted is small, insert in
 140 ///        the sorted part
 141 /// @param range_input : range with the elements to sort
 142 /// @param range_buffer : range with the elements sorted
 143 /// @param comp : object for to compare two elements
 144 /// @param level : when is 1, sort with the insertionsort algorithm
 145 ///                if not make a recursive call splitting the ranges
 146 //
 147 /// @comments : if the number of levels is odd, the data are in the first
 148 /// parameter of range_sort, and the results appear in the second parameter
 149 /// If the number of levels is even, the data are in the second
 150 /// parameter of range_sort, and the results are in the same parameter
 151 //-----------------------------------------------------------------------------
 152 template<class Iter1_t, class Iter2_t, class Compare>
 153 static bool check_stable_sort(const range<Iter1_t> &rng_data,
 154                               const range<Iter2_t> &rng_aux, Compare comp)
 155 {
 156     //------------------------------------------------------------------------
 157     //              metaprogramming
 158     //------------------------------------------------------------------------
 159     typedef value_iter<Iter1_t> value_t;
 160     typedef value_iter<Iter2_t> value2_t;
 161     static_assert (std::is_same<value_t, value2_t>::value,
 162                     "Incompatible iterators\n");
 163
 164     //------------------------------------------------------------------------
 165     //                    program
 166     //------------------------------------------------------------------------
 167     // the maximun number of elements not ordered, for to be inserted in the
 168     // sorted part
 169     //const ptrdiff_t  min_insert_partial_sort = 32 ;
 170     const size_t ndata = rng_data.size();
 171     if (ndata < 32)
 172     {
 173         insert_sort(rng_data.first, rng_data.last, comp);
 174         return true;
 175     };
 176     const size_t min_insert_partial_sort =
 177                     ((ndata >> 3) < 33) ? 32 : (ndata >> 3);
 178     if (ndata < 2) return true;
 179
 180     // check if sorted
 181     bool sw = true;
 182     Iter1_t it2 = rng_data.first + 1;
 183     for (Iter1_t it1 = rng_data.first;
 184                     it2 != rng_data.last and (sw = not comp(*it2, *it1)); it1 =
 185                                     it2++)
 186         ;
 187     if (sw) return true;
 188
 189     // insert the elements between it1 and last
 190     if (size_t(rng_data.last - it2) < min_insert_partial_sort)
 191     {
 192         sort_range_sort(range<Iter1_t>(it2, rng_data.last), rng_aux, comp);
 193         insert_partial_sort(rng_data.first, it2, rng_data.last, comp, rng_aux);
 194         return true;
 195     };
 196
 197     // check if reverse sorted
 198     if ((it2 != (rng_data.first + 1))) return false;
 199     sw = true;
 200     for (Iter1_t it1 = rng_data.first;
 201                     it2 != rng_data.last and (sw = comp(*it2, *it1)); it1 =
 202                                     it2++)
 203         ;
 204     if (size_t(rng_data.last - it2) >= min_insert_partial_sort) return false;
 205
 206     // reverse the elements between first and it1
 207     size_t nreverse = it2 - rng_data.first;
 208     Iter1_t alpha(rng_data.first), beta(it2 - 1), mid(
 209                     rng_data.first + (nreverse >> 1));
 210     while (alpha != mid)
 211         std::swap(*(alpha++), *(beta--));
 212
 213     // insert the elements between it1 and last
 214     if (it2 != rng_data.last)
 215     {
 216         sort_range_sort(range<Iter1_t>(it2, rng_data.last), rng_aux, comp);
 217         insert_partial_sort(rng_data.first, it2, rng_data.last, comp, rng_aux);
 218     };
 219     return true;
 220 }
 221 ;
 222 //-----------------------------------------------------------------------------
 223 //  function : range_sort
 224 /// @brief this function divide r_input in two parts, sort it,and merge moving
 225 ///        the elements to range_buf
 226 /// @param range_input : range with the elements to sort
 227 /// @param range_buffer : range with the elements sorted
 228 /// @param comp : object for to compare two elements
 229 /// @param level : when is 1, sort with the insertionsort algorithm
 230 ///                if not make a recursive call splitting the ranges
 231 //
 232 /// @comments : if the number of levels is odd, the data are in the first
 233 /// parameter of range_sort, and the results appear in the second parameter
 234 /// If the number of levels is even, the data are in the second
 235 /// parameter of range_sort, and the results are in the same parameter
 236 /// The two ranges must have the same size
 237 //-----------------------------------------------------------------------------
 238 template<class Iter1_t, class Iter2_t, class Compare>
 239 static void range_sort(const range<Iter1_t> &range1,
 240                        const range<Iter2_t> &range2, Compare comp,
 241                        uint32_t level)
 242 {
 243     //-----------------------------------------------------------------------
 244     //                  metaprogram
 245     //-----------------------------------------------------------------------
 246     typedef value_iter<Iter1_t> value_t;
 247     typedef value_iter<Iter2_t> value2_t;
 248     static_assert (std::is_same<value_t, value2_t>::value,
 249                     "Incompatible iterators\n");
 250
 251     //-----------------------------------------------------------------------
 252     //                  program
 253     //-----------------------------------------------------------------------
 254     typedef range<Iter1_t> range_it1;
 255     typedef range<Iter2_t> range_it2;
 256     assert(range1.size() == range2.size() and level != 0);
 257
 258     //------------------- check if sort --------------------------------------
 259     if (range1.size() > 1024)
 260     {
 261         if ((level & 1) == 0)
 262         {
 263             if (check_stable_sort(range2, range1, comp)) return;
 264         }
 265         else
 266         {
 267             if (check_stable_sort(range1, range2, comp))
 268             {
 269                 move_forward(range2, range1);
 270                 return;
 271             };
 272         };
 273     };
 274
 275     //------------------- normal process -----------------------------------
 276     size_t nelem1 = (range1.size() + 1) >> 1;
 277     range_it1 range_input1(range1.first, range1.first + nelem1),
 278                            range_input2(range1.first + nelem1, range1.last);
 279
 280     if (level < 2)
 281     {
 282         insert_sort(range_input1.first, range_input1.last, comp);
 283         insert_sort(range_input2.first, range_input2.last, comp);
 284     }
 285     else
 286     {
 287         range_sort (range_it2(range2.first, range2.first + nelem1),
 288                     range_input1, comp, level - 1);
 289
 290         range_sort (range_it2(range2.first + nelem1, range2.last),
 291                     range_input2, comp, level - 1);
 292     };
 293
 294     merge(range2, range_input1, range_input2, comp);
 295 }
 296 ;
 297 //-----------------------------------------------------------------------------
 298 //  function : sort_range_sort
 299 /// @brief this sort elements using the range_sort function and receiving a
 300 ///        buffer of initialized memory
 301 /// @param rng_data : range with the elements to sort
 302 /// @param rng_aux : range of at least the same memory than rng_data used as
 303 ///                  auxiliary memory in the sorting
 304 /// @param comp : object for to compare two elements
 305 //-----------------------------------------------------------------------------
 306 template<class Iter1_t, class Iter2_t, class Compare>
 307 static void sort_range_sort(const range<Iter1_t> &rng_data,
 308                             const range<Iter2_t> &rng_aux, Compare comp)
 309 {
 310     //-----------------------------------------------------------------------
 311     //                  metaprogram
 312     //-----------------------------------------------------------------------
 313     typedef value_iter<Iter1_t> value_t;
 314     typedef value_iter<Iter2_t> value2_t;
 315     static_assert (std::is_same<value_t, value2_t>::value,
 316                     "Incompatible iterators\n");
 317
 318     //------------------------------------------------------------------------
 319     //                    program
 320     //------------------------------------------------------------------------
 321     // minimal number of element before to jump to insertionsort
 322     static const uint32_t sort_min = 32;
 323     if (rng_data.size() <= sort_min)
 324     {
 325         insert_sort(rng_data.first, rng_data.last, comp);
 326         return;
 327     };
 328
 329 #ifdef __BS_DEBUG
 330     assert (rng_aux.size () >= rng_data.size ());
 331 #endif
 332
 333     range<Iter2_t> rng_buffer(rng_aux.first, rng_aux.first + rng_data.size());
 334     uint32_t nlevel =
 335                     nbits64(((rng_data.size() + sort_min - 1) / sort_min) - 1);
 336     //assert (nlevel != 0);
 337
 338     if ((nlevel & 1) == 0)
 339     {
 340         range_sort(rng_buffer, rng_data, comp, nlevel);
 341     }
 342     else
 343     {
 344         range_sort(rng_data, rng_buffer, comp, nlevel);
 345         move_forward(rng_data, rng_buffer);
 346     };
 347 }
 348 ;
 349 //
 350 //############################################################################
 351 //                                                                          ##
 352 //                              S T R U C T                                 ##
 353 //                                                                          ##
 354 //                           S P I N _ S O R T                              ##
 355 //                                                                          ##
 356 //############################################################################
 357 //---------------------------------------------------------------------------
 358 /// @struct spin_sort
 359 /// @brief  This class implement s stable sort algorithm with 1 thread, with
 360 ///         an auxiliary memory of N/2 elements
 361 //----------------------------------------------------------------------------
 362 template<class Iter_t, typename Compare = compare_iter<Iter_t>>
 363 class spinsort
 364 {
 365     //------------------------------------------------------------------------
 366     //               DEFINITIONS AND CONSTANTS
 367     //------------------------------------------------------------------------
 368     typedef value_iter<Iter_t> value_t;
 369     typedef range<Iter_t> range_it;
 370     typedef range<value_t *> range_buf;
 371     // When the number of elements to sort is smaller than Sort_min, are sorted
 372     // by the insertion sort algorithm
 373     static const uint32_t Sort_min = 36;
 374
 375     //------------------------------------------------------------------------
 376     //                      VARIABLES
 377     //------------------------------------------------------------------------
 378     // Pointer to the auxiliary memory
 379     value_t *ptr;
 380
 381     // Number of elements in the auxiliary memory
 382     size_t nptr;
 383
 384     // construct indicate if the auxiliary memory in initialized, and owner
 385     // indicate if the auxiliary memory had been created inside the object or
 386     // had
 387     // been received as a parameter
 388     bool construct = false, owner = false;
 389
 390     //------------------------------------------------------------------------
 391     //                   PRIVATE FUNCTIONS
 392     //-------------------------------------------------------------------------
 393     spinsort (Iter_t first, Iter_t last, Compare comp, value_t *paux,
 394                size_t naux);
 395
 396 public:
 397     //------------------------------------------------------------------------
 398     //                   PUBLIC FUNCTIONS
 399     //-------------------------------------------------------------------------
 400     spinsort(Iter_t first, Iter_t last, Compare comp = Compare())
 401     : spinsort(first, last, comp, nullptr, 0) { };
 402
 403     spinsort(Iter_t first, Iter_t last, Compare comp, range_buf range_aux)
 404     : spinsort(first, last, comp, range_aux.first, range_aux.size()) { };
 405     //
 406     //-----------------------------------------------------------------------
 407     //  function :~spinsort
 408     /// @brief destructor of the struct. Destroy the elements if construct is
 409     /// true,
 410     ///        and return the memory if owner is true
 411     //-----------------------------------------------------------------------
 412     ~spinsort(void)
 413     {
 414         if (construct)
 415         {
 416             destroy(range<value_t *>(ptr, ptr + nptr));
 417             construct = false;
 418         };
 419         if (owner and ptr != nullptr) std::return_temporary_buffer(ptr);
 420     };
 421 };
 422 //----------------------------------------------------------------------------
 423 //        End of class spinsort
 424 //----------------------------------------------------------------------------
 425 //
 426 //-------------------------------------------------------------------------
 427 //  function : spinsort
 428 /// @brief constructor of the struct
 429 //
 430 /// @param first : iterator to the first element of the range to sort
 431 /// @param last : iterator after the last element to the range to sort
 432 /// @param comp : object for to compare two elements pointed by Iter_t
 433 ///               iterators
 434 /// @param paux : pointer to the auxiliary memory provided. If nullptr, the
 435 ///               memory is created inside the class
 436 /// @param naux : number of elements pointed by paux
 437 //------------------------------------------------------------------------
 438 template <class Iter_t, typename Compare>
 439 spinsort <Iter_t, Compare>
 440 ::spinsort (Iter_t first, Iter_t last, Compare comp, value_t *paux, size_t naux)
 441 : ptr(paux), nptr(naux), construct(false), owner(false)
 442 {
 443     range<Iter_t> range_input(first, last);
 444     assert(range_input.valid());
 445
 446     size_t nelem = range_input.size();
 447     owner = construct = false;
 448
 449     nptr = (nelem + 1) >> 1;
 450     size_t nelem_1 = nptr;
 451     size_t nelem_2 = nelem - nelem_1;
 452
 453     if (nelem <= (Sort_min << 1))
 454     {
 455         insert_sort(range_input.first, range_input.last, comp);
 456         return;
 457     };
 458
 459     //------------------- check if sort ---------------------------------
 460     bool sw = true;
 461     for (Iter_t it1 = first, it2 = first + 1; it2 != last
 462          and (sw = not comp(*it2, *it1)); it1 = it2++) ;
 463     if (sw) return;
 464
 465     //------------------- check if reverse sort -------------------------
 466     sw = true;
 467     for (Iter_t it1 = first, it2 = first + 1;
 468          it2 != last and (sw = comp(*it2, *it1)); it1 = it2++);
 469     if (sw)
 470     {
 471         size_t nelem2 = nelem >> 1;
 472         Iter_t it1 = first, it2 = last - 1;
 473         for (size_t i = 0; i < nelem2; ++i)
 474             std::swap(*(it1++), *(it2--));
 475         return;
 476     };
 477
 478     if (ptr == nullptr)
 479     {
 480         ptr = std::get_temporary_buffer<value_t>(nptr).first;
 481         if (ptr == nullptr) throw std::bad_alloc();
 482         owner = true;
 483     };
 484     range_buf range_aux(ptr, (ptr + nptr));
 485
 486     //---------------------------------------------------------------------
 487     //                  Process
 488     //---------------------------------------------------------------------
 489     uint32_t nlevel = nbits64(((nelem + Sort_min - 1) / Sort_min) - 1) - 1;
 490     assert(nlevel != 0);
 491
 492     if ((nlevel & 1) == 1)
 493     {
 494         //----------------------------------------------------------------
 495         // if the number of levels is odd, the data are in the first
 496         // parameter of range_sort, and the results appear in the second
 497         // parameter
 498         //----------------------------------------------------------------
 499         range_it range_1(first, first + nelem_2), range_2(first + nelem_2,
 500                         last);
 501         range_aux = move_construct(range_aux, range_2);
 502         construct = true;
 503
 504         range_sort(range_aux, range_2, comp, nlevel);
 505         range_buf rng_bx(range_aux.first, range_aux.first + nelem_2);
 506
 507         range_sort(range_1, rng_bx, comp, nlevel);
 508         merge_half(range_input, rng_bx, range_2, comp);
 509     }
 510     else
 511     {
 512         //----------------------------------------------------------------
 513         // If the number of levels is even, the data are in the second
 514         // parameter of range_sort, and the results are in the same
 515         //  parameter
 516         //----------------------------------------------------------------
 517         range_it range_1(first, first + nelem_1), range_2(first + nelem_1,
 518                         last);
 519         range_aux = move_construct(range_aux, range_1);
 520         construct = true;
 521
 522         range_sort(range_1, range_aux, comp, nlevel);
 523
 524         range_1.last = range_1.first + range_2.size();
 525         range_sort(range_1, range_2, comp, nlevel);
 526         merge_half(range_input, range_aux, range_2, comp);
 527     };
 528 };
 529
 530 //****************************************************************************
 531 };//    End namepspace spin_detail
 532 //****************************************************************************
 533 //
 534 namespace bsc = boost::sort::common;
 535 //-----------------------------------------------------------------------------
 536 //  function : spinsort
 537 /// @brief this function implement a single thread stable sort
 538 ///
 539 /// @param first : iterator to the first element of the range to sort
 540 /// @param last : iterator after the last element to the range to sort
 541 /// @param comp : object for to compare two elements pointed by Iter_t
 542 ///               iterators
 543 //-----------------------------------------------------------------------------
 544 template <class Iter_t, class Compare = compare_iter<Iter_t>>
 545 inline void spinsort (Iter_t first, Iter_t last, Compare comp = Compare())
 546 {
 547     spin_detail::spinsort <Iter_t, Compare> (first, last, comp);
 548 };
 549
 550 template <class Iter_t, class Compare = compare_iter<Iter_t>>
 551 inline void indirect_spinsort (Iter_t first, Iter_t last,
 552                                Compare comp = Compare())
 553 {
 554     typedef typename std::vector<Iter_t>::iterator itx_iter;
 555     typedef common::less_ptr_no_null <Iter_t, Compare> itx_comp;
 556     common::indirect_sort (spinsort<itx_iter, itx_comp>, first, last, comp);
 557 };
 558
 559 //****************************************************************************
 560 };//    End namespace sort
 561 };//    End namepspace boost
 562 //****************************************************************************
 563 //
 564 #endif