ceph/src/boost/boost/move/algo/detail/merge.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2015-2016.
   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/move for documentation.
   9 //
  10 //////////////////////////////////////////////////////////////////////////////
  11 #ifndef BOOST_MOVE_MERGE_HPP
  12 #define BOOST_MOVE_MERGE_HPP
  13
  14 #include <boost/move/algo/move.hpp>
  15 #include <boost/move/adl_move_swap.hpp>
  16 #include <boost/move/algo/detail/basic_op.hpp>
  17 #include <boost/move/detail/iterator_traits.hpp>
  18 #include <boost/move/detail/destruct_n.hpp>
  19 #include <boost/move/algo/predicate.hpp>
  20 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
  21 #include <boost/assert.hpp>
  22 #include <cstddef>
  23
  24 namespace boost {
  25 namespace movelib {
  26
  27 template<class T, class RandRawIt = T*, class SizeType = typename iterator_traits<RandRawIt>::size_type>
  28 class adaptive_xbuf
  29 {
  30    adaptive_xbuf(const adaptive_xbuf &);
  31    adaptive_xbuf & operator=(const adaptive_xbuf &);
  32
  33    #if !defined(UINTPTR_MAX)
  34    typedef std::size_t uintptr_t;
  35    #endif
  36
  37    public:
  38    typedef RandRawIt iterator;
  39    typedef SizeType  size_type;
  40
  41    adaptive_xbuf()
  42       : m_ptr(), m_size(0), m_capacity(0)
  43    {}
  44
  45    adaptive_xbuf(RandRawIt raw_memory, size_type capacity)
  46       : m_ptr(raw_memory), m_size(0), m_capacity(capacity)
  47    {}
  48
  49    template<class RandIt>
  50    void move_assign(RandIt first, size_type n)
  51    {
  52       if(n <= m_size){
  53          boost::move(first, first+n, m_ptr);
  54          size_type size = m_size;
  55          while(size-- != n){
  56             m_ptr[size].~T();
  57          }
  58          m_size = n;
  59       }
  60       else{
  61          RandRawIt result = boost::move(first, first+m_size, m_ptr);
  62          boost::uninitialized_move(first+m_size, first+n, result);
  63          m_size = n;
  64       }
  65    }
  66
  67    template<class RandIt>
  68    void push_back(RandIt first, size_type n)
  69    {
  70       BOOST_ASSERT(m_capacity - m_size >= n);
  71       boost::uninitialized_move(first, first+n, m_ptr+m_size);
  72       m_size += n;
  73    }
  74
  75    template<class RandIt>
  76    iterator add(RandIt it)
  77    {
  78       BOOST_ASSERT(m_size < m_capacity);
  79       RandRawIt p_ret = m_ptr + m_size;
  80       ::new(&*p_ret) T(::boost::move(*it));
  81       ++m_size;
  82       return p_ret;
  83    }
  84
  85    template<class RandIt>
  86    void insert(iterator pos, RandIt it)
  87    {
  88       if(pos == (m_ptr + m_size)){
  89          this->add(it);
  90       }
  91       else{
  92          this->add(m_ptr+m_size-1);
  93          //m_size updated
  94          boost::move_backward(pos, m_ptr+m_size-2, m_ptr+m_size-1);
  95          *pos = boost::move(*it);
  96       }
  97    }
  98
  99    void set_size(size_type size)
 100    {
 101       m_size = size;
 102    }
 103
 104    void shrink_to_fit(size_type const size)
 105    {
 106       if(m_size > size){
 107          for(size_type szt_i = size; szt_i != m_size; ++szt_i){
 108             m_ptr[szt_i].~T();
 109          }
 110          m_size = size;
 111       }
 112    }
 113
 114    void initialize_until(size_type const size, T &t)
 115    {
 116       BOOST_ASSERT(m_size < m_capacity);
 117       if(m_size < size){
 118          BOOST_TRY
 119          {
 120             ::new((void*)&m_ptr[m_size]) T(::boost::move(t));
 121             ++m_size;
 122             for(; m_size != size; ++m_size){
 123                ::new((void*)&m_ptr[m_size]) T(::boost::move(m_ptr[m_size-1]));
 124             }
 125             t = ::boost::move(m_ptr[m_size-1]);
 126          }
 127          BOOST_CATCH(...)
 128          {
 129             while(m_size)
 130             {
 131                --m_size;
 132                m_ptr[m_size].~T();
 133             }
 134          }
 135          BOOST_CATCH_END
 136       }
 137    }
 138
 139    private:
 140    template<class RIt>
 141    static bool is_raw_ptr(RIt)
 142    {
 143       return false;
 144    }
 145
 146    static bool is_raw_ptr(T*)
 147    {
 148       return true;
 149    }
 150
 151    public:
 152    template<class U>
 153    bool supports_aligned_trailing(size_type size, size_type trail_count) const
 154    {
 155       if(this->is_raw_ptr(this->data()) && m_capacity){
 156          uintptr_t u_addr_sz = uintptr_t(&*(this->data()+size));
 157          uintptr_t u_addr_cp = uintptr_t(&*(this->data()+this->capacity()));
 158          u_addr_sz = ((u_addr_sz + sizeof(U)-1)/sizeof(U))*sizeof(U);
 159          return (u_addr_cp >= u_addr_sz) && ((u_addr_cp - u_addr_sz)/sizeof(U) >= trail_count);
 160       }
 161       return false;
 162    }
 163
 164    template<class U>
 165    U *aligned_trailing() const
 166    {
 167       return this->aligned_trailing<U>(this->size());
 168    }
 169
 170    template<class U>
 171    U *aligned_trailing(size_type pos) const
 172    {
 173       uintptr_t u_addr = uintptr_t(&*(this->data()+pos));
 174       u_addr = ((u_addr + sizeof(U)-1)/sizeof(U))*sizeof(U);
 175       return (U*)u_addr;
 176    }
 177
 178    ~adaptive_xbuf()
 179    {
 180       this->clear();
 181    }
 182
 183    size_type capacity() const
 184    {  return m_capacity;   }
 185
 186    iterator data() const
 187    {  return m_ptr;   }
 188
 189    iterator begin() const
 190    {  return m_ptr;   }
 191
 192    iterator end() const
 193    {  return m_ptr+m_size;   }
 194
 195    size_type size() const
 196    {  return m_size;   }
 197
 198    bool empty() const
 199    {  return !m_size;   }
 200
 201    void clear()
 202    {
 203       this->shrink_to_fit(0u);
 204    }
 205
 206    private:
 207    RandRawIt m_ptr;
 208    size_type m_size;
 209    size_type m_capacity;
 210 };
 211
 212 template<class Iterator, class SizeType, class Op>
 213 class range_xbuf
 214 {
 215    range_xbuf(const range_xbuf &);
 216    range_xbuf & operator=(const range_xbuf &);
 217
 218    public:
 219    typedef SizeType size_type;
 220    typedef Iterator iterator;
 221
 222    range_xbuf(Iterator first, Iterator last)
 223       : m_first(first), m_last(first), m_cap(last)
 224    {}
 225
 226    template<class RandIt>
 227    void move_assign(RandIt first, size_type n)
 228    {
 229       BOOST_ASSERT(size_type(n) <= size_type(m_cap-m_first));
 230       m_last = Op()(forward_t(), first, first+n, m_first);
 231    }
 232
 233    ~range_xbuf()
 234    {}
 235
 236    size_type capacity() const
 237    {  return m_cap-m_first;   }
 238
 239    Iterator data() const
 240    {  return m_first;   }
 241
 242    Iterator end() const
 243    {  return m_last;   }
 244
 245    size_type size() const
 246    {  return m_last-m_first;   }
 247
 248    bool empty() const
 249    {  return m_first == m_last;   }
 250
 251    void clear()
 252    {
 253       m_last = m_first;
 254    }
 255
 256    template<class RandIt>
 257    iterator add(RandIt it)
 258    {
 259       Iterator pos(m_last);
 260       *pos = boost::move(*it);
 261       ++m_last;
 262       return pos;
 263    }
 264
 265    void set_size(size_type size)
 266    {
 267       m_last  = m_first;
 268       m_last += size;
 269    }
 270
 271    private:
 272    Iterator const m_first;
 273    Iterator m_last;
 274    Iterator const m_cap;
 275 };
 276
 277
 278
 279 // @cond
 280
 281 /*
 282 template<typename Unsigned>
 283 inline Unsigned gcd(Unsigned x, Unsigned y)
 284 {
 285    if(0 == ((x &(x-1)) | (y & (y-1)))){
 286       return x < y ? x : y;
 287    }
 288    else{
 289       do
 290       {
 291          Unsigned t = x % y;
 292          x = y;
 293          y = t;
 294       } while (y);
 295       return x;
 296    }
 297 }
 298 */
 299
 300 //Modified version from "An Optimal In-Place Array Rotation Algorithm", Ching-Kuang Shene
 301 template<typename Unsigned>
 302 Unsigned gcd(Unsigned x, Unsigned y)
 303 {
 304    if(0 == ((x &(x-1)) | (y & (y-1)))){
 305       return x < y ? x : y;
 306    }
 307    else{
 308       Unsigned z = 1;
 309       while((!(x&1)) & (!(y&1))){
 310          z <<=1, x>>=1, y>>=1;
 311       }
 312       while(x && y){
 313          if(!(x&1))
 314             x >>=1;
 315          else if(!(y&1))
 316             y >>=1;
 317          else if(x >=y)
 318             x = (x-y) >> 1;
 319          else
 320             y = (y-x) >> 1;
 321       }
 322       return z*(x+y);
 323    }
 324 }
 325
 326 template<typename RandIt>
 327 RandIt rotate_gcd(RandIt first, RandIt middle, RandIt last)
 328 {
 329    typedef typename iterator_traits<RandIt>::size_type size_type;
 330    typedef typename iterator_traits<RandIt>::value_type value_type;
 331
 332    if(first == middle)
 333       return last;
 334    if(middle == last)
 335       return first;
 336    const size_type middle_pos = size_type(middle - first);
 337    RandIt ret = last - middle_pos;
 338    if (middle == ret){
 339       boost::adl_move_swap_ranges(first, middle, middle);
 340    }
 341    else{
 342       const size_type length = size_type(last - first);
 343       for( RandIt it_i(first), it_gcd(it_i + gcd(length, middle_pos))
 344          ; it_i != it_gcd
 345          ; ++it_i){
 346          value_type temp(boost::move(*it_i));
 347          RandIt it_j = it_i;
 348          RandIt it_k = it_j+middle_pos;
 349          do{
 350             *it_j = boost::move(*it_k);
 351             it_j = it_k;
 352             size_type const left = size_type(last - it_j);
 353             it_k = left > middle_pos ? it_j + middle_pos : first + (middle_pos - left);
 354          } while(it_k != it_i);
 355          *it_j = boost::move(temp);
 356       }
 357    }
 358    return ret;
 359 }
 360
 361 template <class RandIt, class T, class Compare>
 362 RandIt lower_bound
 363    (RandIt first, const RandIt last, const T& key, Compare comp)
 364 {
 365    typedef typename iterator_traits
 366       <RandIt>::size_type size_type;
 367    size_type len = size_type(last - first);
 368    RandIt middle;
 369
 370    while (len) {
 371       size_type step = len >> 1;
 372       middle = first;
 373       middle += step;
 374
 375       if (comp(*middle, key)) {
 376          first = ++middle;
 377          len -= step + 1;
 378       }
 379       else{
 380          len = step;
 381       }
 382    }
 383    return first;
 384 }
 385
 386 template <class RandIt, class T, class Compare>
 387 RandIt upper_bound
 388    (RandIt first, const RandIt last, const T& key, Compare comp)
 389 {
 390    typedef typename iterator_traits
 391       <RandIt>::size_type size_type;
 392    size_type len = size_type(last - first);
 393    RandIt middle;
 394
 395    while (len) {
 396       size_type step = len >> 1;
 397       middle = first;
 398       middle += step;
 399
 400       if (!comp(key, *middle)) {
 401          first = ++middle;
 402          len -= step + 1;
 403       }
 404       else{
 405          len = step;
 406       }
 407    }
 408    return first;
 409 }
 410
 411
 412 template<class RandIt, class Compare, class Op>
 413 void op_merge_left( RandIt buf_first
 414                     , RandIt first1
 415                     , RandIt const last1
 416                     , RandIt const last2
 417                     , Compare comp
 418                     , Op op)
 419 {
 420    for(RandIt first2=last1; first2 != last2; ++buf_first){
 421       if(first1 == last1){
 422          op(forward_t(), first2, last2, buf_first);
 423          return;
 424       }
 425       else if(comp(*first2, *first1)){
 426          op(first2, buf_first);
 427          ++first2;
 428       }
 429       else{
 430          op(first1, buf_first);
 431          ++first1;
 432       }
 433    }
 434    if(buf_first != first1){//In case all remaining elements are in the same place
 435                            //(e.g. buffer is exactly the size of the second half
 436                            //and all elements from the second half are less)
 437       op(forward_t(), first1, last1, buf_first);
 438    }
 439 }
 440
 441 // [buf_first, first1) -> buffer
 442 // [first1, last1) merge [last1,last2) -> [buf_first,buf_first+(last2-first1))
 443 // Elements from buffer are moved to [last2 - (first1-buf_first), last2)
 444 // Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs
 445 template<class RandIt, class Compare>
 446 void merge_left
 447    (RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp)
 448 {
 449    op_merge_left(buf_first, first1, last1, last2, comp, move_op());
 450 }
 451
 452 // [buf_first, first1) -> buffer
 453 // [first1, last1) merge [last1,last2) -> [buf_first,buf_first+(last2-first1))
 454 // Elements from buffer are swapped to [last2 - (first1-buf_first), last2)
 455 // Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs
 456 template<class RandIt, class Compare>
 457 void swap_merge_left
 458    (RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp)
 459 {
 460    op_merge_left(buf_first, first1, last1, last2, comp, swap_op());
 461 }
 462
 463 template<class RandIt, class Compare, class Op>
 464 void op_merge_right
 465    (RandIt const first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp, Op op)
 466 {
 467    RandIt const first2 = last1;
 468    while(first1 != last1){
 469       if(last2 == first2){
 470          op(backward_t(), first1, last1, buf_last);
 471          return;
 472       }
 473       --last2;
 474       --last1;
 475       --buf_last;
 476       if(comp(*last2, *last1)){
 477          op(last1, buf_last);
 478          ++last2;
 479       }
 480       else{
 481          op(last2, buf_last);
 482          ++last1;
 483       }
 484    }
 485    if(last2 != buf_last){  //In case all remaining elements are in the same place
 486                            //(e.g. buffer is exactly the size of the first half
 487                            //and all elements from the second half are less)
 488       op(backward_t(), first2, last2, buf_last);
 489    }
 490 }
 491
 492 // [last2, buf_last) - buffer
 493 // [first1, last1) merge [last1,last2) -> [first1+(buf_last-last2), buf_last)
 494 // Note: distance[last2, buf_last) >= distance[first1, last1), so no overlapping occurs
 495 template<class RandIt, class Compare>
 496 void merge_right
 497    (RandIt first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp)
 498 {
 499    op_merge_right(first1, last1, last2, buf_last, comp, move_op());
 500 }
 501
 502 // [last2, buf_last) - buffer
 503 // [first1, last1) merge [last1,last2) -> [first1+(buf_last-last2), buf_last)
 504 // Note: distance[last2, buf_last) >= distance[first1, last1), so no overlapping occurs
 505 template<class RandIt, class Compare>
 506 void swap_merge_right
 507    (RandIt first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp)
 508 {
 509    op_merge_right(first1, last1, last2, buf_last, comp, swap_op());
 510 }
 511
 512 ///////////////////////////////////////////////////////////////////////////////
 513 //
 514 //                            BUFFERED MERGE
 515 //
 516 ///////////////////////////////////////////////////////////////////////////////
 517 template<class RandIt, class Compare, class Op, class Buf>
 518 void op_buffered_merge
 519       ( RandIt first, RandIt const middle, RandIt last
 520       , Compare comp, Op op
 521       , Buf &xbuf)
 522 {
 523    if(first != middle && middle != last && comp(*middle, middle[-1])){
 524       typedef typename iterator_traits<RandIt>::size_type   size_type;
 525       size_type const len1 = size_type(middle-first);
 526       size_type const len2 = size_type(last-middle);
 527       if(len1 <= len2){
 528          first = boost::movelib::upper_bound(first, middle, *middle, comp);
 529          xbuf.move_assign(first, size_type(middle-first));
 530          op_merge_with_right_placed
 531             (xbuf.data(), xbuf.end(), first, middle, last, comp, op);
 532       }
 533       else{
 534          last = boost::movelib::lower_bound(middle, last, middle[-1], comp);
 535          xbuf.move_assign(middle, size_type(last-middle));
 536          op_merge_with_left_placed
 537             (first, middle, last, xbuf.data(), xbuf.end(), comp, op);
 538       }
 539    }
 540 }
 541
 542 template<class RandIt, class Compare, class XBuf>
 543 void buffered_merge
 544       ( RandIt first, RandIt const middle, RandIt last
 545       , Compare comp
 546       , XBuf &xbuf)
 547 {
 548    op_buffered_merge(first, middle, last, comp, move_op(), xbuf);
 549 }
 550
 551 //Complexity: min(len1,len2)^2 + max(len1,len2)
 552 template<class RandIt, class Compare>
 553 void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp)
 554 {
 555    if((middle - first) < (last - middle)){
 556       while(first != middle){
 557          RandIt const old_last1 = middle;
 558          middle = boost::movelib::lower_bound(middle, last, *first, comp);
 559          first = rotate_gcd(first, old_last1, middle);
 560          if(middle == last){
 561             break;
 562          }
 563          do{
 564             ++first;
 565          } while(first != middle && !comp(*middle, *first));
 566       }
 567    }
 568    else{
 569       while(middle != last){
 570          RandIt p = boost::movelib::upper_bound(first, middle, last[-1], comp);
 571          last = rotate_gcd(p, middle, last);
 572          middle = p;
 573          if(middle == first){
 574             break;
 575          }
 576          --p;
 577          do{
 578             --last;
 579          } while(middle != last && !comp(last[-1], *p));
 580       }
 581    }
 582 }
 583
 584 static const std::size_t MergeBufferlessONLogNRotationThreshold = 16u;
 585
 586 template <class RandIt, class Compare>
 587 void merge_bufferless_ONlogN_recursive
 588    ( RandIt first, RandIt middle, RandIt last
 589    , typename iterator_traits<RandIt>::size_type len1
 590    , typename iterator_traits<RandIt>::size_type len2
 591    , Compare comp)
 592 {
 593    typedef typename iterator_traits<RandIt>::size_type size_type;
 594
 595    while(1) {
 596       //trivial cases
 597       if (!len2) {
 598          return;
 599       }
 600       else if (!len1) {
 601          return;
 602       }
 603       else if (size_type(len1 | len2) == 1u) {
 604          if (comp(*middle, *first))
 605             adl_move_swap(*first, *middle);
 606          return;
 607       }
 608       else if(size_type(len1+len2) < MergeBufferlessONLogNRotationThreshold){
 609          merge_bufferless_ON2(first, middle, last, comp);
 610          return;
 611       }
 612
 613       RandIt first_cut = first;
 614       RandIt second_cut = middle;
 615       size_type len11 = 0;
 616       size_type len22 = 0;
 617       if (len1 > len2) {
 618          len11 = len1 / 2;
 619          first_cut +=  len11;
 620          second_cut = boost::movelib::lower_bound(middle, last, *first_cut, comp);
 621          len22 = size_type(second_cut - middle);
 622       }
 623       else {
 624          len22 = len2 / 2;
 625          second_cut += len22;
 626          first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp);
 627          len11 = size_type(first_cut - first);
 628       }
 629       RandIt new_middle = rotate_gcd(first_cut, middle, second_cut);
 630
 631       //Avoid one recursive call doing a manual tail call elimination on the biggest range
 632       const size_type len_internal = len11+len22;
 633       if( len_internal < (len1 + len2 - len_internal) ) {
 634          merge_bufferless_ONlogN_recursive(first, first_cut,  new_middle, len11, len22,        comp);
 635          first = new_middle;
 636          middle = second_cut;
 637          len1 -= len11;
 638          len2 -= len22;
 639       }
 640       else {
 641          merge_bufferless_ONlogN_recursive(new_middle, second_cut, last, len1 - len11, len2 - len22, comp);
 642          middle = first_cut;
 643          last = new_middle;
 644          len1 = len11;
 645          len2 = len22;
 646       }
 647    }
 648 }
 649
 650
 651 //Complexity: NlogN
 652 template<class RandIt, class Compare>
 653 void merge_bufferless_ONlogN(RandIt first, RandIt middle, RandIt last, Compare comp)
 654 {
 655    typedef typename iterator_traits<RandIt>::size_type size_type;
 656    merge_bufferless_ONlogN_recursive
 657       (first, middle, last, size_type(middle - first), size_type(last - middle), comp);
 658 }
 659
 660 template<class RandIt, class Compare>
 661 void merge_bufferless(RandIt first, RandIt middle, RandIt last, Compare comp)
 662 {
 663    #define BOOST_ADAPTIVE_MERGE_NLOGN_MERGE
 664    #ifdef BOOST_ADAPTIVE_MERGE_NLOGN_MERGE
 665    merge_bufferless_ONlogN(first, middle, last, comp);
 666    #else
 667    merge_bufferless_ON2(first, middle, last, comp);
 668    #endif   //BOOST_ADAPTIVE_MERGE_NLOGN_MERGE
 669 }
 670
 671 // [r_first, r_last) are already in the right part of the destination range.
 672 template <class Compare, class InputIterator, class InputOutIterator, class Op>
 673 void op_merge_with_right_placed
 674    ( InputIterator first, InputIterator last
 675    , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
 676    , Compare comp, Op op)
 677 {
 678    BOOST_ASSERT((last - first) == (r_first - dest_first));
 679    while ( first != last ) {
 680       if (r_first == r_last) {
 681          InputOutIterator end = op(forward_t(), first, last, dest_first);
 682          BOOST_ASSERT(end == r_last);
 683          (void)end;
 684          return;
 685       }
 686       else if (comp(*r_first, *first)) {
 687          op(r_first, dest_first);
 688          ++r_first;
 689       }
 690       else {
 691          op(first, dest_first);
 692          ++first;
 693       }
 694       ++dest_first;
 695    }
 696    // Remaining [r_first, r_last) already in the correct place
 697 }
 698
 699 template <class Compare, class InputIterator, class InputOutIterator>
 700 void swap_merge_with_right_placed
 701    ( InputIterator first, InputIterator last
 702    , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
 703    , Compare comp)
 704 {
 705    op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, swap_op());
 706 }
 707
 708 // [first, last) are already in the right part of the destination range.
 709 template <class Compare, class Op, class BidirIterator, class BidirOutIterator>
 710 void op_merge_with_left_placed
 711    ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last
 712    , BidirIterator const r_first, BidirIterator r_last
 713    , Compare comp, Op op)
 714 {
 715    BOOST_ASSERT((dest_last - last) == (r_last - r_first));
 716    while( r_first != r_last ) {
 717       if(first == last) {
 718          BidirOutIterator res = op(backward_t(), r_first, r_last, dest_last);
 719          BOOST_ASSERT(last == res);
 720          (void)res;
 721          return;
 722       }
 723       --r_last;
 724       --last;
 725       if(comp(*r_last, *last)){
 726          ++r_last;
 727          --dest_last;
 728          op(last, dest_last);
 729       }
 730       else{
 731          ++last;
 732          --dest_last;
 733          op(r_last, dest_last);
 734       }
 735    }
 736    // Remaining [first, last) already in the correct place
 737 }
 738
 739 // @endcond
 740
 741 // [first, last) are already in the right part of the destination range.
 742 template <class Compare, class BidirIterator, class BidirOutIterator>
 743 void merge_with_left_placed
 744    ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last
 745    , BidirIterator const r_first, BidirIterator r_last
 746    , Compare comp)
 747 {
 748    op_merge_with_left_placed(first, last, dest_last, r_first, r_last, comp, move_op());
 749 }
 750
 751 // [r_first, r_last) are already in the right part of the destination range.
 752 template <class Compare, class InputIterator, class InputOutIterator>
 753 void merge_with_right_placed
 754    ( InputIterator first, InputIterator last
 755    , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
 756    , Compare comp)
 757 {
 758    op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, move_op());
 759 }
 760
 761 // [r_first, r_last) are already in the right part of the destination range.
 762 // [dest_first, r_first) is uninitialized memory
 763 template <class Compare, class InputIterator, class InputOutIterator>
 764 void uninitialized_merge_with_right_placed
 765    ( InputIterator first, InputIterator last
 766    , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
 767    , Compare comp)
 768 {
 769    BOOST_ASSERT((last - first) == (r_first - dest_first));
 770    typedef typename iterator_traits<InputOutIterator>::value_type value_type;
 771    InputOutIterator const original_r_first = r_first;
 772
 773    destruct_n<value_type, InputOutIterator> d(dest_first);
 774
 775    while ( first != last && dest_first != original_r_first ) {
 776       if (r_first == r_last) {
 777          for(; dest_first != original_r_first; ++dest_first, ++first){
 778             ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first));
 779             d.incr();
 780          }
 781          d.release();
 782          InputOutIterator end = ::boost::move(first, last, original_r_first);
 783          BOOST_ASSERT(end == r_last);
 784          (void)end;
 785          return;
 786       }
 787       else if (comp(*r_first, *first)) {
 788          ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*r_first));
 789          d.incr();
 790          ++r_first;
 791       }
 792       else {
 793          ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first));
 794          d.incr();
 795          ++first;
 796       }
 797       ++dest_first;
 798    }
 799    d.release();
 800    merge_with_right_placed(first, last, original_r_first, r_first, r_last, comp);
 801 }
 802
 803 /*
 804 // [r_first, r_last) are already in the right part of the destination range.
 805 // [dest_first, r_first) is uninitialized memory
 806 template <class Compare, class BidirOutIterator, class BidirIterator>
 807 void uninitialized_merge_with_left_placed
 808    ( BidirOutIterator dest_first, BidirOutIterator r_first, BidirOutIterator r_last
 809    , BidirIterator first, BidirIterator last
 810    , Compare comp)
 811 {
 812    BOOST_ASSERT((last - first) == (r_last - r_first));
 813    typedef typename iterator_traits<BidirOutIterator>::value_type value_type;
 814    BidirOutIterator const original_r_last = r_last;
 815
 816    destruct_n<value_type> d(&*dest_last);
 817
 818    while ( first != last && dest_first != original_r_first ) {
 819       if (r_first == r_last) {
 820          for(; dest_first != original_r_first; ++dest_first, ++first){
 821             ::new(&*dest_first) value_type(::boost::move(*first));
 822             d.incr();
 823          }
 824          d.release();
 825          BidirOutIterator end = ::boost::move(first, last, original_r_first);
 826          BOOST_ASSERT(end == r_last);
 827          (void)end;
 828          return;
 829       }
 830       else if (comp(*r_first, *first)) {
 831          ::new(&*dest_first) value_type(::boost::move(*r_first));
 832          d.incr();
 833          ++r_first;
 834       }
 835       else {
 836          ::new(&*dest_first) value_type(::boost::move(*first));
 837          d.incr();
 838          ++first;
 839       }
 840       ++dest_first;
 841    }
 842    d.release();
 843    merge_with_right_placed(first, last, original_r_first, r_first, r_last, comp);
 844 }
 845 */
 846
 847
 848 /// This is a helper function for the merge routines.
 849 template<typename BidirectionalIterator1, typename BidirectionalIterator2>
 850    BidirectionalIterator1
 851    rotate_adaptive(BidirectionalIterator1 first,
 852       BidirectionalIterator1 middle,
 853       BidirectionalIterator1 last,
 854       typename iterator_traits<BidirectionalIterator1>::size_type len1,
 855       typename iterator_traits<BidirectionalIterator1>::size_type len2,
 856       BidirectionalIterator2 buffer,
 857       typename iterator_traits<BidirectionalIterator1>::size_type buffer_size)
 858 {
 859    if (len1 > len2 && len2 <= buffer_size)
 860    {
 861       if(len2) //Protect against self-move ranges
 862       {
 863          BidirectionalIterator2 buffer_end = boost::move(middle, last, buffer);
 864          boost::move_backward(first, middle, last);
 865          return boost::move(buffer, buffer_end, first);
 866       }
 867       else
 868          return first;
 869    }
 870    else if (len1 <= buffer_size)
 871    {
 872       if(len1) //Protect against self-move ranges
 873       {
 874          BidirectionalIterator2 buffer_end = boost::move(first, middle, buffer);
 875          BidirectionalIterator1 ret = boost::move(middle, last, first);
 876          boost::move(buffer, buffer_end, ret);
 877          return ret;
 878       }
 879       else
 880          return last;
 881    }
 882    else
 883       return rotate_gcd(first, middle, last);
 884 }
 885
 886 template<typename BidirectionalIterator,
 887    typename Pointer, typename Compare>
 888    void merge_adaptive_ONlogN_recursive
 889    (BidirectionalIterator first,
 890       BidirectionalIterator middle,
 891       BidirectionalIterator last,
 892       typename iterator_traits<BidirectionalIterator>::size_type len1,
 893       typename iterator_traits<BidirectionalIterator>::size_type len2,
 894       Pointer buffer,
 895       typename iterator_traits<BidirectionalIterator>::size_type buffer_size,
 896       Compare comp)
 897 {
 898    typedef typename iterator_traits<BidirectionalIterator>::size_type size_type;
 899    //trivial cases
 900    if (!len2 || !len1) {
 901       return;
 902    }
 903    else if (len1 <= buffer_size || len2 <= buffer_size)
 904    {
 905       range_xbuf<Pointer, size_type, move_op> rxbuf(buffer, buffer + buffer_size);
 906       buffered_merge(first, middle, last, comp, rxbuf);
 907    }
 908    else if (size_type(len1 + len2) == 2u) {
 909       if (comp(*middle, *first))
 910          adl_move_swap(*first, *middle);
 911       return;
 912    }
 913    else if (size_type(len1 + len2) < MergeBufferlessONLogNRotationThreshold) {
 914       merge_bufferless_ON2(first, middle, last, comp);
 915       return;
 916    }
 917    BidirectionalIterator first_cut = first;
 918    BidirectionalIterator second_cut = middle;
 919    size_type len11 = 0;
 920    size_type len22 = 0;
 921    if (len1 > len2)  //(len1 < len2)
 922    {
 923       len11 = len1 / 2;
 924       first_cut += len11;
 925       second_cut = boost::movelib::lower_bound(middle, last, *first_cut, comp);
 926       len22 = second_cut - middle;
 927    }
 928    else
 929    {
 930       len22 = len2 / 2;
 931       second_cut += len22;
 932       first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp);
 933       len11 = first_cut - first;
 934    }
 935
 936    BidirectionalIterator new_middle
 937       = rotate_adaptive(first_cut, middle, second_cut,
 938          size_type(len1 - len11), len22, buffer,
 939          buffer_size);
 940    merge_adaptive_ONlogN_recursive(first, first_cut, new_middle, len11,
 941       len22, buffer, buffer_size, comp);
 942    merge_adaptive_ONlogN_recursive(new_middle, second_cut, last,
 943       len1 - len11, len2 - len22, buffer, buffer_size, comp);
 944 }
 945
 946
 947 template<typename BidirectionalIterator, typename Compare, typename RandRawIt>
 948 void merge_adaptive_ONlogN(BidirectionalIterator first,
 949                                      BidirectionalIterator middle,
 950                                      BidirectionalIterator last,
 951                                      Compare comp,
 952                            RandRawIt uninitialized,
 953                            typename iterator_traits<BidirectionalIterator>::size_type uninitialized_len)
 954 {
 955    typedef typename iterator_traits<BidirectionalIterator>::value_type  value_type;
 956    typedef typename iterator_traits<BidirectionalIterator>::size_type   size_type;
 957
 958    if (first == middle || middle == last)
 959       return;
 960
 961    if(uninitialized_len)
 962    {
 963       const size_type len1 = size_type(middle - first);
 964       const size_type len2 = size_type(last - middle);
 965
 966       ::boost::movelib::adaptive_xbuf<value_type, RandRawIt> xbuf(uninitialized, uninitialized_len);
 967       xbuf.initialize_until(uninitialized_len, *first);
 968            merge_adaptive_ONlogN_recursive(first, middle, last, len1, len2, xbuf.begin(), uninitialized_len, comp);
 969    }
 970    else
 971    {
 972       merge_bufferless(first, middle, last, comp);
 973    }
 974 }
 975
 976
 977 }  //namespace movelib {
 978 }  //namespace boost {
 979
 980 #endif   //#define BOOST_MOVE_MERGE_HPP