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