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