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