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