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
  23 namespace boost {
  24 namespace movelib {
  25
  26 // @cond
  27
  28 /*
  29 template<typename Unsigned>
  30 inline Unsigned gcd(Unsigned x, Unsigned y)
  31 {
  32    if(0 == ((x &(x-1)) | (y & (y-1)))){
  33       return x < y ? x : y;
  34    }
  35    else{
  36       do
  37       {
  38          Unsigned t = x % y;
  39          x = y;
  40          y = t;
  41       } while (y);
  42       return x;
  43    }
  44 }
  45 */
  46
  47 //Modified version from "An Optimal In-Place Array Rotation Algorithm", Ching-Kuang Shene
  48 template<typename Unsigned>
  49 Unsigned gcd(Unsigned x, Unsigned y)
  50 {
  51    if(0 == ((x &(x-1)) | (y & (y-1)))){
  52       return x < y ? x : y;
  53    }
  54    else{
  55       Unsigned z = 1;
  56       while((!(x&1)) & (!(y&1))){
  57          z <<=1, x>>=1, y>>=1;
  58       }
  59       while(x && y){
  60          if(!(x&1))
  61             x >>=1;
  62          else if(!(y&1))
  63             y >>=1;
  64          else if(x >=y)
  65             x = (x-y) >> 1;
  66          else
  67             y = (y-x) >> 1;
  68       }
  69       return z*(x+y);
  70    }
  71 }
  72
  73 template<typename RandIt>
  74 RandIt rotate_gcd(RandIt first, RandIt middle, RandIt last)
  75 {
  76    typedef typename iterator_traits<RandIt>::size_type size_type;
  77    typedef typename iterator_traits<RandIt>::value_type value_type;
  78
  79    if(first == middle)
  80       return last;
  81    if(middle == last)
  82       return first;
  83    const size_type middle_pos = size_type(middle - first);
  84    RandIt ret = last - middle_pos;
  85    if (middle == ret){
  86       boost::adl_move_swap_ranges(first, middle, middle);
  87    }
  88    else{
  89       const size_type length = size_type(last - first);
  90       for( RandIt it_i(first), it_gcd(it_i + gcd(length, middle_pos))
  91          ; it_i != it_gcd
  92          ; ++it_i){
  93          value_type temp(boost::move(*it_i));
  94          RandIt it_j = it_i;
  95          RandIt it_k = it_j+middle_pos;
  96          do{
  97             *it_j = boost::move(*it_k);
  98             it_j = it_k;
  99             size_type const left = size_type(last - it_j);
 100             it_k = left > middle_pos ? it_j + middle_pos : first + (middle_pos - left);
 101          } while(it_k != it_i);
 102          *it_j = boost::move(temp);
 103       }
 104    }
 105    return ret;
 106 }
 107
 108 template <class RandIt, class T, class Compare>
 109 RandIt lower_bound
 110    (RandIt first, const RandIt last, const T& key, Compare comp)
 111 {
 112    typedef typename iterator_traits
 113       <RandIt>::size_type size_type;
 114    size_type len = size_type(last - first);
 115    RandIt middle;
 116
 117    while (len) {
 118       size_type step = len >> 1;
 119       middle = first;
 120       middle += step;
 121
 122       if (comp(*middle, key)) {
 123          first = ++middle;
 124          len -= step + 1;
 125       }
 126       else{
 127          len = step;
 128       }
 129    }
 130    return first;
 131 }
 132
 133 template <class RandIt, class T, class Compare>
 134 RandIt upper_bound
 135    (RandIt first, const RandIt last, const T& key, Compare comp)
 136 {
 137    typedef typename iterator_traits
 138       <RandIt>::size_type size_type;
 139    size_type len = size_type(last - first);
 140    RandIt middle;
 141
 142    while (len) {
 143       size_type step = len >> 1;
 144       middle = first;
 145       middle += step;
 146
 147       if (!comp(key, *middle)) {
 148          first = ++middle;
 149          len -= step + 1;
 150       }
 151       else{
 152          len = step;
 153       }
 154    }
 155    return first;
 156 }
 157
 158
 159 template<class RandIt, class Compare, class Op>
 160 void op_merge_left( RandIt buf_first
 161                     , RandIt first1
 162                     , RandIt const last1
 163                     , RandIt const last2
 164                     , Compare comp
 165                     , Op op)
 166 {
 167    for(RandIt first2=last1; first2 != last2; ++buf_first){
 168       if(first1 == last1){
 169          op(forward_t(), first2, last2, buf_first);
 170          return;
 171       }
 172       else if(comp(*first2, *first1)){
 173          op(first2, buf_first);
 174          ++first2;
 175       }
 176       else{
 177          op(first1, buf_first);
 178          ++first1;
 179       }
 180    }
 181    if(buf_first != first1){//In case all remaining elements are in the same place
 182                            //(e.g. buffer is exactly the size of the second half
 183                            //and all elements from the second half are less)
 184       op(forward_t(), first1, last1, buf_first);
 185    }
 186 }
 187
 188 // [buf_first, first1) -> buffer
 189 // [first1, last1) merge [last1,last2) -> [buf_first,buf_first+(last2-first1))
 190 // Elements from buffer are moved to [last2 - (first1-buf_first), last2)
 191 // Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs
 192 template<class RandIt, class Compare>
 193 void merge_left
 194    (RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp)
 195 {
 196    op_merge_left(buf_first, first1, last1, last2, comp, move_op());
 197 }
 198
 199 // [buf_first, first1) -> buffer
 200 // [first1, last1) merge [last1,last2) -> [buf_first,buf_first+(last2-first1))
 201 // Elements from buffer are swapped to [last2 - (first1-buf_first), last2)
 202 // Note: distance(buf_first, first1) >= distance(last1, last2), so no overlapping occurs
 203 template<class RandIt, class Compare>
 204 void swap_merge_left
 205    (RandIt buf_first, RandIt first1, RandIt const last1, RandIt const last2, Compare comp)
 206 {
 207    op_merge_left(buf_first, first1, last1, last2, comp, swap_op());
 208 }
 209
 210 template<class RandIt, class Compare, class Op>
 211 void op_merge_right
 212    (RandIt const first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp, Op op)
 213 {
 214    RandIt const first2 = last1;
 215    while(first1 != last1){
 216       if(last2 == first2){
 217          op(backward_t(), first1, last1, buf_last);
 218          return;
 219       }
 220       --last2;
 221       --last1;
 222       --buf_last;
 223       if(comp(*last2, *last1)){
 224          op(last1, buf_last);
 225          ++last2;
 226       }
 227       else{
 228          op(last2, buf_last);
 229          ++last1;
 230       }
 231    }
 232    if(last2 != buf_last){  //In case all remaining elements are in the same place
 233                            //(e.g. buffer is exactly the size of the first half
 234                            //and all elements from the second half are less)
 235       op(backward_t(), first2, last2, buf_last);
 236    }
 237 }
 238
 239 // [last2, buf_last) - buffer
 240 // [first1, last1) merge [last1,last2) -> [first1+(buf_last-last2), buf_last)
 241 // Note: distance[last2, buf_last) >= distance[first1, last1), so no overlapping occurs
 242 template<class RandIt, class Compare>
 243 void merge_right
 244    (RandIt first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp)
 245 {
 246    op_merge_right(first1, last1, last2, buf_last, comp, move_op());
 247 }
 248
 249 // [last2, buf_last) - buffer
 250 // [first1, last1) merge [last1,last2) -> [first1+(buf_last-last2), buf_last)
 251 // Note: distance[last2, buf_last) >= distance[first1, last1), so no overlapping occurs
 252 template<class RandIt, class Compare>
 253 void swap_merge_right
 254    (RandIt first1, RandIt last1, RandIt last2, RandIt buf_last, Compare comp)
 255 {
 256    op_merge_right(first1, last1, last2, buf_last, comp, swap_op());
 257 }
 258
 259 template <class BidirIt, class Distance, class Compare>
 260 void merge_bufferless_ONlogN_recursive
 261    (BidirIt first, BidirIt middle, BidirIt last, Distance len1, Distance len2, Compare comp)
 262 {
 263    typedef typename iterator_traits<BidirIt>::size_type size_type;
 264    while(1) {
 265       //#define MERGE_BUFFERLESS_RECURSIVE_OPT
 266       #ifndef MERGE_BUFFERLESS_RECURSIVE_OPT
 267       if (len2  == 0) {
 268          return;
 269       }
 270
 271       if (!len1) {
 272          return;
 273       }
 274
 275       if ((len1 | len2) == 1) {
 276          if (comp(*middle, *first))
 277             adl_move_swap(*first, *middle);
 278          return;
 279       }
 280       #else
 281       if (len2  == 0) {
 282          return;
 283       }
 284
 285       if (!len1) {
 286          return;
 287       }
 288       BidirIt middle_prev = middle; --middle_prev;
 289       if(!comp(*middle, *middle_prev))
 290          return;
 291
 292       while(true) {
 293          if (comp(*middle, *first))
 294             break;
 295          ++first;
 296          if(--len1 == 1)
 297             break;
 298       }
 299
 300       if (len1 == 1 && len2 == 1) {
 301          //comp(*middle, *first) == true already tested in the loop
 302          adl_move_swap(*first, *middle);
 303          return;
 304       }
 305       #endif
 306
 307       BidirIt first_cut = first;
 308       BidirIt second_cut = middle;
 309       Distance len11 = 0;
 310       Distance len22 = 0;
 311       if (len1 > len2) {
 312          len11 = len1 / 2;
 313          first_cut +=  len11;
 314          second_cut = boost::movelib::lower_bound(middle, last, *first_cut, comp);
 315          len22 = size_type(second_cut - middle);
 316       }
 317       else {
 318          len22 = len2 / 2;
 319          second_cut += len22;
 320          first_cut = boost::movelib::upper_bound(first, middle, *second_cut, comp);
 321          len11 = size_type(first_cut - first);
 322       }
 323       BidirIt new_middle = rotate_gcd(first_cut, middle, second_cut);
 324
 325       //Avoid one recursive call doing a manual tail call elimination on the biggest range
 326       const Distance len_internal = len11+len22;
 327       if( len_internal < (len1 + len2 - len_internal) ) {
 328          merge_bufferless_ONlogN_recursive(first,      first_cut,  new_middle, len11,        len22,        comp);
 329          //merge_bufferless_recursive(new_middle, second_cut, last,       len1 - len11, len2 - len22, comp);
 330          first = new_middle;
 331          middle = second_cut;
 332          len1 -= len11;
 333          len2 -= len22;
 334       }
 335       else {
 336          //merge_bufferless_recursive(first,      first_cut,  new_middle, len11,        len22,        comp);
 337          merge_bufferless_ONlogN_recursive(new_middle, second_cut, last,       len1 - len11, len2 - len22, comp);
 338          middle = first_cut;
 339          last = new_middle;
 340          len1 = len11;
 341          len2 = len22;
 342       }
 343    }
 344 }
 345
 346 //Complexity: NlogN
 347 template<class BidirIt, class Compare>
 348 void merge_bufferless_ONlogN(BidirIt first, BidirIt middle, BidirIt last, Compare comp)
 349 {
 350    merge_bufferless_ONlogN_recursive
 351       (first, middle, last, middle - first, last - middle, comp);
 352 }
 353
 354 //Complexity: min(len1,len2)^2 + max(len1,len2)
 355 template<class RandIt, class Compare>
 356 void merge_bufferless_ON2(RandIt first, RandIt middle, RandIt last, Compare comp)
 357 {
 358    if((middle - first) < (last - middle)){
 359       while(first != middle){
 360          RandIt const old_last1 = middle;
 361          middle = boost::movelib::lower_bound(middle, last, *first, comp);
 362          first = rotate_gcd(first, old_last1, middle);
 363          if(middle == last){
 364             break;
 365          }
 366          do{
 367             ++first;
 368          } while(first != middle && !comp(*middle, *first));
 369       }
 370    }
 371    else{
 372       while(middle != last){
 373          RandIt p = boost::movelib::upper_bound(first, middle, last[-1], comp);
 374          last = rotate_gcd(p, middle, last);
 375          middle = p;
 376          if(middle == first){
 377             break;
 378          }
 379          --p;
 380          do{
 381             --last;
 382          } while(middle != last && !comp(last[-1], *p));
 383       }
 384    }
 385 }
 386
 387 template<class RandIt, class Compare>
 388 void merge_bufferless(RandIt first, RandIt middle, RandIt last, Compare comp)
 389 {
 390    //#define BOOST_ADAPTIVE_MERGE_NLOGN_MERGE
 391    #ifdef BOOST_ADAPTIVE_MERGE_NLOGN_MERGE
 392    merge_bufferless_ONlogN(first, middle, last, comp);
 393    #else
 394    merge_bufferless_ON2(first, middle, last, comp);
 395    #endif   //BOOST_ADAPTIVE_MERGE_NLOGN_MERGE
 396 }
 397
 398 // [r_first, r_last) are already in the right part of the destination range.
 399 template <class Compare, class InputIterator, class InputOutIterator, class Op>
 400 void op_merge_with_right_placed
 401    ( InputIterator first, InputIterator last
 402    , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
 403    , Compare comp, Op op)
 404 {
 405    BOOST_ASSERT((last - first) == (r_first - dest_first));
 406    while ( first != last ) {
 407       if (r_first == r_last) {
 408          InputOutIterator end = op(forward_t(), first, last, dest_first);
 409          BOOST_ASSERT(end == r_last);
 410          (void)end;
 411          return;
 412       }
 413       else if (comp(*r_first, *first)) {
 414          op(r_first, dest_first);
 415          ++r_first;
 416       }
 417       else {
 418          op(first, dest_first);
 419          ++first;
 420       }
 421       ++dest_first;
 422    }
 423    // Remaining [r_first, r_last) already in the correct place
 424 }
 425
 426 template <class Compare, class InputIterator, class InputOutIterator>
 427 void swap_merge_with_right_placed
 428    ( InputIterator first, InputIterator last
 429    , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
 430    , Compare comp)
 431 {
 432    op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, swap_op());
 433 }
 434
 435 // [first, last) are already in the right part of the destination range.
 436 template <class Compare, class Op, class BidirIterator, class BidirOutIterator>
 437 void op_merge_with_left_placed
 438    ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last
 439    , BidirIterator const r_first, BidirIterator r_last
 440    , Compare comp, Op op)
 441 {
 442    BOOST_ASSERT((dest_last - last) == (r_last - r_first));
 443    while( r_first != r_last ) {
 444       if(first == last) {
 445          BidirOutIterator res = op(backward_t(), r_first, r_last, dest_last);
 446          BOOST_ASSERT(last == res);
 447          (void)res;
 448          return;
 449       }
 450       --r_last;
 451       --last;
 452       if(comp(*r_last, *last)){
 453          ++r_last;
 454          --dest_last;
 455          op(last, dest_last);
 456       }
 457       else{
 458          ++last;
 459          --dest_last;
 460          op(r_last, dest_last);
 461       }
 462    }
 463    // Remaining [first, last) already in the correct place
 464 }
 465
 466 // @endcond
 467
 468 // [irst, last) are already in the right part of the destination range.
 469 template <class Compare, class BidirIterator, class BidirOutIterator>
 470 void merge_with_left_placed
 471    ( BidirOutIterator const first, BidirOutIterator last, BidirOutIterator dest_last
 472    , BidirIterator const r_first, BidirIterator r_last
 473    , Compare comp)
 474 {
 475    op_merge_with_left_placed(first, last, dest_last, r_first, r_last, comp, move_op());
 476 }
 477
 478 // [r_first, r_last) are already in the right part of the destination range.
 479 template <class Compare, class InputIterator, class InputOutIterator>
 480 void merge_with_right_placed
 481    ( InputIterator first, InputIterator last
 482    , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
 483    , Compare comp)
 484 {
 485    op_merge_with_right_placed(first, last, dest_first, r_first, r_last, comp, move_op());
 486 }
 487
 488 // [r_first, r_last) are already in the right part of the destination range.
 489 // [dest_first, r_first) is uninitialized memory
 490 template <class Compare, class InputIterator, class InputOutIterator>
 491 void uninitialized_merge_with_right_placed
 492    ( InputIterator first, InputIterator last
 493    , InputOutIterator dest_first, InputOutIterator r_first, InputOutIterator r_last
 494    , Compare comp)
 495 {
 496    BOOST_ASSERT((last - first) == (r_first - dest_first));
 497    typedef typename iterator_traits<InputOutIterator>::value_type value_type;
 498    InputOutIterator const original_r_first = r_first;
 499
 500    destruct_n<value_type, InputOutIterator> d(dest_first);
 501
 502    while ( first != last && dest_first != original_r_first ) {
 503       if (r_first == r_last) {
 504          for(; dest_first != original_r_first; ++dest_first, ++first){
 505             ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first));
 506             d.incr();
 507          }
 508          d.release();
 509          InputOutIterator end = ::boost::move(first, last, original_r_first);
 510          BOOST_ASSERT(end == r_last);
 511          (void)end;
 512          return;
 513       }
 514       else if (comp(*r_first, *first)) {
 515          ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*r_first));
 516          d.incr();
 517          ++r_first;
 518       }
 519       else {
 520          ::new((iterator_to_raw_pointer)(dest_first)) value_type(::boost::move(*first));
 521          d.incr();
 522          ++first;
 523       }
 524       ++dest_first;
 525    }
 526    d.release();
 527    merge_with_right_placed(first, last, original_r_first, r_first, r_last, comp);
 528 }
 529
 530 /*
 531 // [r_first, r_last) are already in the right part of the destination range.
 532 // [dest_first, r_first) is uninitialized memory
 533 template <class Compare, class BidirOutIterator, class BidirIterator>
 534 void uninitialized_merge_with_left_placed
 535    ( BidirOutIterator dest_first, BidirOutIterator r_first, BidirOutIterator r_last
 536    , BidirIterator first, BidirIterator last
 537    , Compare comp)
 538 {
 539    BOOST_ASSERT((last - first) == (r_last - r_first));
 540    typedef typename iterator_traits<BidirOutIterator>::value_type value_type;
 541    BidirOutIterator const original_r_last = r_last;
 542
 543    destruct_n<value_type> d(&*dest_last);
 544
 545    while ( first != last && dest_first != original_r_first ) {
 546       if (r_first == r_last) {
 547          for(; dest_first != original_r_first; ++dest_first, ++first){
 548             ::new(&*dest_first) value_type(::boost::move(*first));
 549             d.incr();
 550          }
 551          d.release();
 552          BidirOutIterator end = ::boost::move(first, last, original_r_first);
 553          BOOST_ASSERT(end == r_last);
 554          (void)end;
 555          return;
 556       }
 557       else if (comp(*r_first, *first)) {
 558          ::new(&*dest_first) value_type(::boost::move(*r_first));
 559          d.incr();
 560          ++r_first;
 561       }
 562       else {
 563          ::new(&*dest_first) value_type(::boost::move(*first));
 564          d.incr();
 565          ++first;
 566       }
 567       ++dest_first;
 568    }
 569    d.release();
 570    merge_with_right_placed(first, last, original_r_first, r_first, r_last, comp);
 571 }
 572 */
 573
 574 }  //namespace movelib {
 575 }  //namespace boost {
 576
 577 #endif   //#define BOOST_MOVE_MERGE_HPP