contrib/gcc-4.7/libstdc++-v3/include/parallel/losertree.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file parallel/losertree.h
  26 *  @brief Many generic loser tree variants.
  27 *  This file is a GNU parallel extension to the Standard C++ Library.
  28 */
  29
  30 // Written by Johannes Singler.
  31
  32 #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
  33 #define _GLIBCXX_PARALLEL_LOSERTREE_H 1
  34
  35 #include <bits/stl_algobase.h>
  36 #include <bits/stl_function.h>
  37 #include <parallel/features.h>
  38 #include <parallel/base.h>
  39
  40 namespace __gnu_parallel
  41 {
  42   /**
  43    * @brief Guarded loser/tournament tree.
  44    *
  45    * The smallest element is at the top.
  46    *
  47    * Guarding is done explicitly through one flag _M_sup per element,
  48    * inf is not needed due to a better initialization routine.  This
  49    * is a well-performing variant.
  50    *
  51    * @param _Tp the element type
  52    * @param _Compare the comparator to use, defaults to std::less<_Tp>
  53    */
  54   template<typename _Tp, typename _Compare>
  55     class _LoserTreeBase
  56     {
  57     protected:
  58       /** @brief Internal representation of a _LoserTree element. */
  59       struct _Loser
  60       {
  61         /** @brief flag, true iff this is a "maximum" __sentinel. */
  62         bool _M_sup;
  63         /** @brief __index of the __source __sequence. */
  64         int _M_source;
  65         /** @brief _M_key of the element in the _LoserTree. */
  66         _Tp _M_key;
  67       };
  68
  69       unsigned int _M_ik, _M_k, _M_offset;
  70
  71       /** log_2{_M_k} */
  72       unsigned int _M_log_k;
  73
  74       /** @brief _LoserTree __elements. */
  75       _Loser* _M_losers;
  76
  77       /** @brief _Compare to use. */
  78       _Compare _M_comp;
  79
  80       /**
  81        * @brief State flag that determines whether the _LoserTree is empty.
  82        *
  83        * Only used for building the _LoserTree.
  84        */
  85       bool _M_first_insert;
  86
  87     public:
  88       /**
  89        * @brief The constructor.
  90        *
  91        * @param __k The number of sequences to merge.
  92        * @param __comp The comparator to use.
  93        */
  94       _LoserTreeBase(unsigned int __k, _Compare __comp)
  95       : _M_comp(__comp)
  96       {
  97         _M_ik = __k;
  98
  99         // Compute log_2{_M_k} for the _Loser Tree
 100         _M_log_k = __rd_log2(_M_ik - 1) + 1;
 101
 102         // Next greater power of 2.
 103         _M_k = 1 << _M_log_k;
 104         _M_offset = _M_k;
 105
 106         // Avoid default-constructing _M_losers[]._M_key
 107         _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
 108                                                         * sizeof(_Loser)));
 109         for (unsigned int __i = _M_ik - 1; __i < _M_k; ++__i)
 110           _M_losers[__i + _M_k]._M_sup = true;
 111
 112         _M_first_insert = true;
 113       }
 114
 115       /**
 116        * @brief The destructor.
 117        */
 118       ~_LoserTreeBase()
 119       {
 120         for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
 121           _M_losers[__i].~_Loser();
 122         ::operator delete(_M_losers);
 123       }
 124
 125       /**
 126        * @brief Initializes the sequence "_M_source" with the element "__key".
 127        *
 128        * @param __key the element to insert
 129        * @param __source __index of the __source __sequence
 130        * @param __sup flag that determines whether the value to insert is an
 131        *   explicit __supremum.
 132        */
 133       void
 134       __insert_start(const _Tp& __key, int __source, bool __sup)
 135       {
 136         unsigned int __pos = _M_k + __source;
 137
 138         if (_M_first_insert)
 139           {
 140             // Construct all keys, so we can easily destruct them.
 141             for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
 142               ::new(&(_M_losers[__i]._M_key)) _Tp(__key);
 143             _M_first_insert = false;
 144           }
 145         else
 146           _M_losers[__pos]._M_key = __key;
 147
 148         _M_losers[__pos]._M_sup = __sup;
 149         _M_losers[__pos]._M_source = __source;
 150       }
 151
 152       /**
 153        * @return the index of the sequence with the smallest element.
 154        */
 155       int __get_min_source()
 156       { return _M_losers[0]._M_source; }
 157     };
 158
 159     /**
 160      * @brief Stable _LoserTree variant.
 161      *
 162      * Provides the stable implementations of insert_start, __init_winner,
 163      * __init and __delete_min_insert.
 164      *
 165      * Unstable variant is done using partial specialisation below.
 166      */
 167   template<bool __stable/* default == true */, typename _Tp,
 168            typename _Compare>
 169     class _LoserTree
 170     : public _LoserTreeBase<_Tp, _Compare>
 171     {
 172       typedef _LoserTreeBase<_Tp, _Compare> _Base;
 173       using _Base::_M_k;
 174       using _Base::_M_comp;
 175       using _Base::_M_losers;
 176       using _Base::_M_first_insert;
 177
 178     public:
 179       _LoserTree(unsigned int __k, _Compare __comp)
 180       : _Base::_LoserTreeBase(__k, __comp)
 181       { }
 182
 183       unsigned int
 184       __init_winner(unsigned int __root)
 185       {
 186         if (__root >= _M_k)
 187           return __root;
 188         else
 189           {
 190             unsigned int __left = __init_winner(2 * __root);
 191             unsigned int __right = __init_winner(2 * __root + 1);
 192             if (_M_losers[__right]._M_sup
 193                 || (!_M_losers[__left]._M_sup
 194                     && !_M_comp(_M_losers[__right]._M_key,
 195                                 _M_losers[__left]._M_key)))
 196               {
 197                 // Left one is less or equal.
 198                 _M_losers[__root] = _M_losers[__right];
 199                 return __left;
 200               }
 201             else
 202               {
 203                 // Right one is less.
 204                 _M_losers[__root] = _M_losers[__left];
 205                 return __right;
 206               }
 207           }
 208       }
 209
 210       void __init()
 211       { _M_losers[0] = _M_losers[__init_winner(1)]; }
 212
 213       /**
 214        * @brief Delete the smallest element and insert a new element from
 215        *   the previously smallest element's sequence.
 216        *
 217        * This implementation is stable.
 218        */
 219       // Do not pass a const reference since __key will be used as
 220       // local variable.
 221       void
 222       __delete_min_insert(_Tp __key, bool __sup)
 223       {
 224         using std::swap;
 225 #if _GLIBCXX_ASSERTIONS
 226         // no dummy sequence can ever be at the top!
 227         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 228 #endif
 229
 230         int __source = _M_losers[0]._M_source;
 231         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
 232              __pos /= 2)
 233           {
 234             // The smaller one gets promoted, ties are broken by _M_source.
 235             if ((__sup && (!_M_losers[__pos]._M_sup
 236                            || _M_losers[__pos]._M_source < __source))
 237                 || (!__sup && !_M_losers[__pos]._M_sup
 238                     && ((_M_comp(_M_losers[__pos]._M_key, __key))
 239                         || (!_M_comp(__key, _M_losers[__pos]._M_key)
 240                             && _M_losers[__pos]._M_source < __source))))
 241               {
 242                 // The other one is smaller.
 243                 std::swap(_M_losers[__pos]._M_sup, __sup);
 244                 std::swap(_M_losers[__pos]._M_source, __source);
 245                 swap(_M_losers[__pos]._M_key, __key);
 246               }
 247           }
 248
 249         _M_losers[0]._M_sup = __sup;
 250         _M_losers[0]._M_source = __source;
 251         _M_losers[0]._M_key = __key;
 252       }
 253     };
 254
 255     /**
 256      * @brief Unstable _LoserTree variant.
 257      *
 258      * Stability (non-stable here) is selected with partial specialization.
 259      */
 260   template<typename _Tp, typename _Compare>
 261     class _LoserTree</* __stable == */false, _Tp, _Compare>
 262     : public _LoserTreeBase<_Tp, _Compare>
 263     {
 264       typedef _LoserTreeBase<_Tp, _Compare> _Base;
 265       using _Base::_M_log_k;
 266       using _Base::_M_k;
 267       using _Base::_M_comp;
 268       using _Base::_M_losers;
 269       using _Base::_M_first_insert;
 270
 271     public:
 272       _LoserTree(unsigned int __k, _Compare __comp)
 273       : _Base::_LoserTreeBase(__k, __comp)
 274       { }
 275
 276       /**
 277        * Computes the winner of the competition at position "__root".
 278        *
 279        * Called recursively (starting at 0) to build the initial tree.
 280        *
 281        * @param __root __index of the "game" to start.
 282        */
 283       unsigned int
 284       __init_winner(unsigned int __root)
 285       {
 286         if (__root >= _M_k)
 287           return __root;
 288         else
 289           {
 290             unsigned int __left = __init_winner(2 * __root);
 291             unsigned int __right = __init_winner(2 * __root + 1);
 292             if (_M_losers[__right]._M_sup
 293                 || (!_M_losers[__left]._M_sup
 294                     && !_M_comp(_M_losers[__right]._M_key,
 295                                 _M_losers[__left]._M_key)))
 296               {
 297                 // Left one is less or equal.
 298                 _M_losers[__root] = _M_losers[__right];
 299                 return __left;
 300               }
 301             else
 302               {
 303                 // Right one is less.
 304                 _M_losers[__root] = _M_losers[__left];
 305                 return __right;
 306               }
 307           }
 308       }
 309
 310       void
 311       __init()
 312       { _M_losers[0] = _M_losers[__init_winner(1)]; }
 313
 314       /**
 315        * Delete the _M_key smallest element and insert the element __key
 316        * instead.
 317        *
 318        * @param __key the _M_key to insert
 319        * @param __sup true iff __key is an explicitly marked supremum
 320        */
 321       // Do not pass a const reference since __key will be used as local
 322       // variable.
 323       void
 324       __delete_min_insert(_Tp __key, bool __sup)
 325       {
 326         using std::swap;
 327 #if _GLIBCXX_ASSERTIONS
 328         // no dummy sequence can ever be at the top!
 329         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 330 #endif
 331
 332         int __source = _M_losers[0]._M_source;
 333         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
 334              __pos /= 2)
 335           {
 336             // The smaller one gets promoted.
 337             if (__sup || (!_M_losers[__pos]._M_sup
 338                           && _M_comp(_M_losers[__pos]._M_key, __key)))
 339               {
 340                 // The other one is smaller.
 341                 std::swap(_M_losers[__pos]._M_sup, __sup);
 342                 std::swap(_M_losers[__pos]._M_source, __source);
 343                 swap(_M_losers[__pos]._M_key, __key);
 344               }
 345           }
 346
 347         _M_losers[0]._M_sup = __sup;
 348         _M_losers[0]._M_source = __source;
 349         _M_losers[0]._M_key = __key;
 350       }
 351     };
 352
 353   /**
 354    * @brief Base class of _Loser Tree implementation using pointers.
 355    */
 356   template<typename _Tp, typename _Compare>
 357     class _LoserTreePointerBase
 358     {
 359     protected:
 360       /** @brief Internal representation of _LoserTree __elements. */
 361       struct _Loser
 362       {
 363         bool _M_sup;
 364         int _M_source;
 365         const _Tp* _M_keyp;
 366       };
 367
 368       unsigned int _M_ik, _M_k, _M_offset;
 369       _Loser* _M_losers;
 370       _Compare _M_comp;
 371
 372     public:
 373       _LoserTreePointerBase(unsigned int __k,
 374                             _Compare __comp = std::less<_Tp>())
 375       : _M_comp(__comp)
 376       {
 377         _M_ik = __k;
 378
 379         // Next greater power of 2.
 380         _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
 381         _M_offset = _M_k;
 382         _M_losers = new _Loser[_M_k * 2];
 383         for (unsigned int __i = _M_ik - 1; __i < _M_k; __i++)
 384           _M_losers[__i + _M_k]._M_sup = true;
 385       }
 386
 387       ~_LoserTreePointerBase()
 388       { delete[] _M_losers; }
 389
 390       int __get_min_source()
 391       { return _M_losers[0]._M_source; }
 392
 393       void __insert_start(const _Tp& __key, int __source, bool __sup)
 394       {
 395         unsigned int __pos = _M_k + __source;
 396
 397         _M_losers[__pos]._M_sup = __sup;
 398         _M_losers[__pos]._M_source = __source;
 399         _M_losers[__pos]._M_keyp = &__key;
 400       }
 401     };
 402
 403   /**
 404    * @brief Stable _LoserTree implementation.
 405    *
 406    * The unstable variant is implemented using partial instantiation below.
 407    */
 408   template<bool __stable/* default == true */, typename _Tp, typename _Compare>
 409     class _LoserTreePointer
 410     : public _LoserTreePointerBase<_Tp, _Compare>
 411     {
 412       typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
 413       using _Base::_M_k;
 414       using _Base::_M_comp;
 415       using _Base::_M_losers;
 416
 417     public:
 418       _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
 419       : _Base::_LoserTreePointerBase(__k, __comp)
 420       { }
 421
 422       unsigned int
 423       __init_winner(unsigned int __root)
 424       {
 425         if (__root >= _M_k)
 426           return __root;
 427         else
 428           {
 429             unsigned int __left = __init_winner(2 * __root);
 430             unsigned int __right = __init_winner(2 * __root + 1);
 431             if (_M_losers[__right]._M_sup
 432                 || (!_M_losers[__left]._M_sup
 433                     && !_M_comp(*_M_losers[__right]._M_keyp,
 434                                 *_M_losers[__left]._M_keyp)))
 435               {
 436                 // Left one is less or equal.
 437                 _M_losers[__root] = _M_losers[__right];
 438                 return __left;
 439               }
 440             else
 441               {
 442                 // Right one is less.
 443                 _M_losers[__root] = _M_losers[__left];
 444                 return __right;
 445               }
 446           }
 447       }
 448
 449       void __init()
 450       { _M_losers[0] = _M_losers[__init_winner(1)]; }
 451
 452       void __delete_min_insert(const _Tp& __key, bool __sup)
 453       {
 454 #if _GLIBCXX_ASSERTIONS
 455         // no dummy sequence can ever be at the top!
 456         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 457 #endif
 458
 459         const _Tp* __keyp = &__key;
 460         int __source = _M_losers[0]._M_source;
 461         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
 462              __pos /= 2)
 463           {
 464             // The smaller one gets promoted, ties are broken by __source.
 465             if ((__sup && (!_M_losers[__pos]._M_sup
 466                            || _M_losers[__pos]._M_source < __source))
 467                 || (!__sup && !_M_losers[__pos]._M_sup &&
 468                     ((_M_comp(*_M_losers[__pos]._M_keyp, *__keyp))
 469                      || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
 470                          && _M_losers[__pos]._M_source < __source))))
 471               {
 472                 // The other one is smaller.
 473                 std::swap(_M_losers[__pos]._M_sup, __sup);
 474                 std::swap(_M_losers[__pos]._M_source, __source);
 475                 std::swap(_M_losers[__pos]._M_keyp, __keyp);
 476               }
 477           }
 478
 479         _M_losers[0]._M_sup = __sup;
 480         _M_losers[0]._M_source = __source;
 481         _M_losers[0]._M_keyp = __keyp;
 482       }
 483     };
 484
 485   /**
 486    * @brief Unstable _LoserTree implementation.
 487    *
 488    * The stable variant is above.
 489    */
 490   template<typename _Tp, typename _Compare>
 491     class _LoserTreePointer</* __stable == */false, _Tp, _Compare>
 492     : public _LoserTreePointerBase<_Tp, _Compare>
 493     {
 494       typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
 495       using _Base::_M_k;
 496       using _Base::_M_comp;
 497       using _Base::_M_losers;
 498
 499     public:
 500       _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
 501       : _Base::_LoserTreePointerBase(__k, __comp)
 502       { }
 503
 504       unsigned int
 505       __init_winner(unsigned int __root)
 506       {
 507         if (__root >= _M_k)
 508           return __root;
 509         else
 510           {
 511             unsigned int __left = __init_winner(2 * __root);
 512             unsigned int __right = __init_winner(2 * __root + 1);
 513             if (_M_losers[__right]._M_sup
 514                 || (!_M_losers[__left]._M_sup
 515                     && !_M_comp(*_M_losers[__right]._M_keyp,
 516                                 *_M_losers[__left]._M_keyp)))
 517               {
 518                 // Left one is less or equal.
 519                 _M_losers[__root] = _M_losers[__right];
 520                 return __left;
 521               }
 522             else
 523               {
 524                 // Right one is less.
 525                 _M_losers[__root] = _M_losers[__left];
 526                 return __right;
 527               }
 528           }
 529       }
 530
 531       void __init()
 532       { _M_losers[0] = _M_losers[__init_winner(1)]; }
 533
 534       void __delete_min_insert(const _Tp& __key, bool __sup)
 535       {
 536 #if _GLIBCXX_ASSERTIONS
 537         // no dummy sequence can ever be at the top!
 538         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 539 #endif
 540
 541         const _Tp* __keyp = &__key;
 542         int __source = _M_losers[0]._M_source;
 543         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
 544              __pos /= 2)
 545           {
 546             // The smaller one gets promoted.
 547             if (__sup || (!_M_losers[__pos]._M_sup
 548                           && _M_comp(*_M_losers[__pos]._M_keyp, *__keyp)))
 549               {
 550                 // The other one is smaller.
 551                 std::swap(_M_losers[__pos]._M_sup, __sup);
 552                 std::swap(_M_losers[__pos]._M_source, __source);
 553                 std::swap(_M_losers[__pos]._M_keyp, __keyp);
 554               }
 555           }
 556
 557         _M_losers[0]._M_sup = __sup;
 558         _M_losers[0]._M_source = __source;
 559         _M_losers[0]._M_keyp = __keyp;
 560       }
 561     };
 562
 563   /** @brief Base class for unguarded _LoserTree implementation.
 564    *
 565    * The whole element is copied into the tree structure.
 566    *
 567    * No guarding is done, therefore not a single input sequence must
 568    * run empty.  Unused __sequence heads are marked with a sentinel which
 569    * is &gt; all elements that are to be merged.
 570    *
 571    * This is a very fast variant.
 572    */
 573   template<typename _Tp, typename _Compare>
 574     class _LoserTreeUnguardedBase
 575     {
 576     protected:
 577       struct _Loser
 578       {
 579         int _M_source;
 580         _Tp _M_key;
 581       };
 582
 583       unsigned int _M_ik, _M_k, _M_offset;
 584       _Loser* _M_losers;
 585       _Compare _M_comp;
 586
 587     public:
 588       _LoserTreeUnguardedBase(unsigned int __k, const _Tp& __sentinel,
 589                               _Compare __comp = std::less<_Tp>())
 590       : _M_comp(__comp)
 591       {
 592         _M_ik = __k;
 593
 594         // Next greater power of 2.
 595         _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
 596         _M_offset = _M_k;
 597         // Avoid default-constructing _M_losers[]._M_key
 598         _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
 599                                                         * sizeof(_Loser)));
 600
 601         for (unsigned int __i = 0; __i < _M_k; ++__i)
 602           {
 603             ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel);
 604             _M_losers[__i]._M_source = -1;
 605           }
 606         for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
 607           {
 608             ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel);
 609             _M_losers[__i]._M_source = -1;
 610           }
 611       }
 612
 613       ~_LoserTreeUnguardedBase()
 614       {
 615         for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
 616           _M_losers[__i].~_Loser();
 617         ::operator delete(_M_losers);
 618       }
 619
 620       int
 621       __get_min_source()
 622       {
 623 #if _GLIBCXX_ASSERTIONS
 624         // no dummy sequence can ever be at the top!
 625         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 626 #endif
 627         return _M_losers[0]._M_source;
 628       }
 629
 630       void
 631       __insert_start(const _Tp& __key, int __source, bool)
 632       {
 633         unsigned int __pos = _M_k + __source;
 634
 635         ::new(&(_M_losers[__pos]._M_key)) _Tp(__key);
 636         _M_losers[__pos]._M_source = __source;
 637       }
 638     };
 639
 640   /**
 641    * @brief Stable implementation of unguarded _LoserTree.
 642    *
 643    * Unstable variant is selected below with partial specialization.
 644    */
 645   template<bool __stable/* default == true */, typename _Tp, typename _Compare>
 646     class _LoserTreeUnguarded
 647     : public _LoserTreeUnguardedBase<_Tp, _Compare>
 648     {
 649       typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
 650       using _Base::_M_k;
 651       using _Base::_M_comp;
 652       using _Base::_M_losers;
 653
 654   public:
 655       _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
 656                           _Compare __comp = std::less<_Tp>())
 657       : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
 658       { }
 659
 660       unsigned int
 661       __init_winner(unsigned int __root)
 662       {
 663         if (__root >= _M_k)
 664           return __root;
 665         else
 666           {
 667             unsigned int __left = __init_winner(2 * __root);
 668             unsigned int __right = __init_winner(2 * __root + 1);
 669             if (!_M_comp(_M_losers[__right]._M_key,
 670                          _M_losers[__left]._M_key))
 671               {
 672                 // Left one is less or equal.
 673                 _M_losers[__root] = _M_losers[__right];
 674                 return __left;
 675               }
 676             else
 677               {
 678                 // Right one is less.
 679                 _M_losers[__root] = _M_losers[__left];
 680                 return __right;
 681               }
 682           }
 683       }
 684
 685       void
 686       __init()
 687       {
 688         _M_losers[0] = _M_losers[__init_winner(1)];
 689
 690 #if _GLIBCXX_ASSERTIONS
 691         // no dummy sequence can ever be at the top at the beginning
 692         // (0 sequences!)
 693         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 694 #endif
 695       }
 696
 697       // Do not pass a const reference since __key will be used as
 698       // local variable.
 699       void
 700       __delete_min_insert(_Tp __key, bool)
 701       {
 702         using std::swap;
 703 #if _GLIBCXX_ASSERTIONS
 704         // no dummy sequence can ever be at the top!
 705         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 706 #endif
 707
 708         int __source = _M_losers[0]._M_source;
 709         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
 710              __pos /= 2)
 711           {
 712             // The smaller one gets promoted, ties are broken by _M_source.
 713             if (_M_comp(_M_losers[__pos]._M_key, __key)
 714                 || (!_M_comp(__key, _M_losers[__pos]._M_key)
 715                     && _M_losers[__pos]._M_source < __source))
 716               {
 717                 // The other one is smaller.
 718                 std::swap(_M_losers[__pos]._M_source, __source);
 719                 swap(_M_losers[__pos]._M_key, __key);
 720               }
 721           }
 722
 723         _M_losers[0]._M_source = __source;
 724         _M_losers[0]._M_key = __key;
 725       }
 726     };
 727
 728   /**
 729    * @brief Non-Stable implementation of unguarded _LoserTree.
 730    *
 731    * Stable implementation is above.
 732    */
 733   template<typename _Tp, typename _Compare>
 734     class _LoserTreeUnguarded</* __stable == */false, _Tp, _Compare>
 735     : public _LoserTreeUnguardedBase<_Tp, _Compare>
 736     {
 737       typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
 738       using _Base::_M_k;
 739       using _Base::_M_comp;
 740       using _Base::_M_losers;
 741
 742     public:
 743       _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
 744                           _Compare __comp = std::less<_Tp>())
 745       : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
 746       { }
 747
 748       unsigned int
 749       __init_winner(unsigned int __root)
 750       {
 751         if (__root >= _M_k)
 752           return __root;
 753         else
 754           {
 755             unsigned int __left = __init_winner(2 * __root);
 756             unsigned int __right = __init_winner(2 * __root + 1);
 757
 758 #if _GLIBCXX_ASSERTIONS
 759             // If __left one is sentinel then __right one must be, too.
 760             if (_M_losers[__left]._M_source == -1)
 761               _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
 762 #endif
 763
 764             if (!_M_comp(_M_losers[__right]._M_key,
 765                          _M_losers[__left]._M_key))
 766               {
 767                 // Left one is less or equal.
 768                 _M_losers[__root] = _M_losers[__right];
 769                 return __left;
 770               }
 771             else
 772               {
 773                 // Right one is less.
 774                 _M_losers[__root] = _M_losers[__left];
 775                 return __right;
 776               }
 777           }
 778       }
 779
 780       void
 781       __init()
 782       {
 783         _M_losers[0] = _M_losers[__init_winner(1)];
 784
 785 #if _GLIBCXX_ASSERTIONS
 786         // no dummy sequence can ever be at the top at the beginning
 787         // (0 sequences!)
 788         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 789 #endif
 790       }
 791
 792       // Do not pass a const reference since __key will be used as
 793       // local variable.
 794       void
 795       __delete_min_insert(_Tp __key, bool)
 796       {
 797         using std::swap;
 798 #if _GLIBCXX_ASSERTIONS
 799         // no dummy sequence can ever be at the top!
 800         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 801 #endif
 802
 803         int __source = _M_losers[0]._M_source;
 804         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
 805              __pos /= 2)
 806           {
 807             // The smaller one gets promoted.
 808             if (_M_comp(_M_losers[__pos]._M_key, __key))
 809               {
 810                 // The other one is smaller.
 811                 std::swap(_M_losers[__pos]._M_source, __source);
 812                 swap(_M_losers[__pos]._M_key, __key);
 813               }
 814           }
 815
 816         _M_losers[0]._M_source = __source;
 817         _M_losers[0]._M_key = __key;
 818       }
 819     };
 820
 821   /** @brief Unguarded loser tree, keeping only pointers to the
 822   * elements in the tree structure.
 823   *
 824   *  No guarding is done, therefore not a single input sequence must
 825   *  run empty.  This is a very fast variant.
 826   */
 827   template<typename _Tp, typename _Compare>
 828     class _LoserTreePointerUnguardedBase
 829     {
 830     protected:
 831       struct _Loser
 832       {
 833         int _M_source;
 834         const _Tp* _M_keyp;
 835       };
 836
 837       unsigned int _M_ik, _M_k, _M_offset;
 838       _Loser* _M_losers;
 839       _Compare _M_comp;
 840
 841     public:
 842
 843       _LoserTreePointerUnguardedBase(unsigned int __k, const _Tp& __sentinel,
 844                                      _Compare __comp = std::less<_Tp>())
 845       : _M_comp(__comp)
 846       {
 847         _M_ik = __k;
 848
 849         // Next greater power of 2.
 850         _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
 851         _M_offset = _M_k;
 852         // Avoid default-constructing _M_losers[]._M_key
 853         _M_losers = new _Loser[2 * _M_k];
 854
 855         for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
 856           {
 857             _M_losers[__i]._M_keyp = &__sentinel;
 858             _M_losers[__i]._M_source = -1;
 859           }
 860       }
 861
 862       ~_LoserTreePointerUnguardedBase()
 863       { delete[] _M_losers; }
 864
 865       int
 866       __get_min_source()
 867       {
 868 #if _GLIBCXX_ASSERTIONS
 869         // no dummy sequence can ever be at the top!
 870         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 871 #endif
 872         return _M_losers[0]._M_source;
 873       }
 874
 875       void
 876       __insert_start(const _Tp& __key, int __source, bool)
 877       {
 878         unsigned int __pos = _M_k + __source;
 879
 880         _M_losers[__pos]._M_keyp = &__key;
 881         _M_losers[__pos]._M_source = __source;
 882       }
 883     };
 884
 885   /**
 886    * @brief Stable unguarded _LoserTree variant storing pointers.
 887    *
 888    * Unstable variant is implemented below using partial specialization.
 889    */
 890   template<bool __stable/* default == true */, typename _Tp, typename _Compare>
 891     class _LoserTreePointerUnguarded
 892     : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
 893     {
 894       typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
 895       using _Base::_M_k;
 896       using _Base::_M_comp;
 897       using _Base::_M_losers;
 898
 899     public:
 900       _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
 901                                  _Compare __comp = std::less<_Tp>())
 902       : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
 903       { }
 904
 905       unsigned int
 906       __init_winner(unsigned int __root)
 907       {
 908         if (__root >= _M_k)
 909           return __root;
 910         else
 911           {
 912             unsigned int __left = __init_winner(2 * __root);
 913             unsigned int __right = __init_winner(2 * __root + 1);
 914             if (!_M_comp(*_M_losers[__right]._M_keyp,
 915                          *_M_losers[__left]._M_keyp))
 916               {
 917                 // Left one is less or equal.
 918                 _M_losers[__root] = _M_losers[__right];
 919                 return __left;
 920               }
 921             else
 922               {
 923                 // Right one is less.
 924                 _M_losers[__root] = _M_losers[__left];
 925                 return __right;
 926               }
 927           }
 928       }
 929
 930       void
 931       __init()
 932       {
 933         _M_losers[0] = _M_losers[__init_winner(1)];
 934
 935 #if _GLIBCXX_ASSERTIONS
 936         // no dummy sequence can ever be at the top at the beginning
 937         // (0 sequences!)
 938         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 939 #endif
 940       }
 941
 942       void
 943       __delete_min_insert(const _Tp& __key, bool __sup)
 944       {
 945 #if _GLIBCXX_ASSERTIONS
 946         // no dummy sequence can ever be at the top!
 947         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
 948 #endif
 949
 950         const _Tp* __keyp = &__key;
 951         int __source = _M_losers[0]._M_source;
 952         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
 953              __pos /= 2)
 954           {
 955             // The smaller one gets promoted, ties are broken by _M_source.
 956             if (_M_comp(*_M_losers[__pos]._M_keyp, *__keyp)
 957                 || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
 958                     && _M_losers[__pos]._M_source < __source))
 959               {
 960                 // The other one is smaller.
 961                 std::swap(_M_losers[__pos]._M_source, __source);
 962                 std::swap(_M_losers[__pos]._M_keyp, __keyp);
 963               }
 964           }
 965
 966         _M_losers[0]._M_source = __source;
 967         _M_losers[0]._M_keyp = __keyp;
 968       }
 969     };
 970
 971   /**
 972    * @brief Unstable unguarded _LoserTree variant storing pointers.
 973    *
 974    * Stable variant is above.
 975    */
 976   template<typename _Tp, typename _Compare>
 977     class _LoserTreePointerUnguarded</* __stable == */false, _Tp, _Compare>
 978     : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
 979     {
 980       typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
 981       using _Base::_M_k;
 982       using _Base::_M_comp;
 983       using _Base::_M_losers;
 984
 985   public:
 986       _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
 987                                  _Compare __comp = std::less<_Tp>())
 988       : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
 989       { }
 990
 991       unsigned int
 992       __init_winner(unsigned int __root)
 993       {
 994         if (__root >= _M_k)
 995           return __root;
 996         else
 997           {
 998             unsigned int __left = __init_winner(2 * __root);
 999             unsigned int __right = __init_winner(2 * __root + 1);
1000
1001 #if _GLIBCXX_ASSERTIONS
1002             // If __left one is sentinel then __right one must be, too.
1003             if (_M_losers[__left]._M_source == -1)
1004               _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
1005 #endif
1006
1007             if (!_M_comp(*_M_losers[__right]._M_keyp,
1008                          *_M_losers[__left]._M_keyp))
1009               {
1010                 // Left one is less or equal.
1011                 _M_losers[__root] = _M_losers[__right];
1012                 return __left;
1013               }
1014             else
1015               {
1016                 // Right one is less.
1017                 _M_losers[__root] = _M_losers[__left];
1018                 return __right;
1019               }
1020           }
1021       }
1022
1023       void
1024       __init()
1025       {
1026         _M_losers[0] = _M_losers[__init_winner(1)];
1027
1028 #if _GLIBCXX_ASSERTIONS
1029         // no dummy sequence can ever be at the top at the beginning
1030         // (0 sequences!)
1031         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1032 #endif
1033       }
1034
1035       void
1036       __delete_min_insert(const _Tp& __key, bool __sup)
1037       {
1038 #if _GLIBCXX_ASSERTIONS
1039         // no dummy sequence can ever be at the top!
1040         _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1041 #endif
1042
1043         const _Tp* __keyp = &__key;
1044         int __source = _M_losers[0]._M_source;
1045         for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
1046              __pos /= 2)
1047           {
1048             // The smaller one gets promoted.
1049             if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp))
1050               {
1051                 // The other one is smaller.
1052                 std::swap(_M_losers[__pos]._M_source, __source);
1053                 std::swap(_M_losers[__pos]._M_keyp, __keyp);
1054               }
1055           }
1056
1057         _M_losers[0]._M_source = __source;
1058         _M_losers[0]._M_keyp = __keyp;
1059       }
1060     };
1061 } // namespace __gnu_parallel
1062
1063 #endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */