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