libstdc++-v3/include/parallel/losertree.h

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