00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032 #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
00033 #define _GLIBCXX_PARALLEL_LOSERTREE_H 1
00034
00035 #include <bits/stl_algobase.h>
00036 #include <bits/stl_function.h>
00037 #include <parallel/features.h>
00038 #include <parallel/base.h>
00039
00040 namespace __gnu_parallel
00041 {
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054 template<typename _Tp, typename _Compare>
00055 class _LoserTreeBase
00056 {
00057 protected:
00058
00059 struct _Loser
00060 {
00061
00062 bool _M_sup;
00063
00064 int _M_source;
00065
00066 _Tp _M_key;
00067 };
00068
00069 unsigned int _M_ik, _M_k, _M_offset;
00070
00071
00072 unsigned int _M_log_k;
00073
00074
00075 _Loser* _M_losers;
00076
00077
00078 _Compare _M_comp;
00079
00080
00081
00082
00083
00084
00085 bool _M_first_insert;
00086
00087 public:
00088
00089
00090
00091
00092
00093
00094 _LoserTreeBase(unsigned int __k, _Compare __comp)
00095 : _M_comp(__comp)
00096 {
00097 _M_ik = __k;
00098
00099
00100 _M_log_k = __rd_log2(_M_ik - 1) + 1;
00101
00102
00103 _M_k = 1 << _M_log_k;
00104 _M_offset = _M_k;
00105
00106
00107 _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
00108 * sizeof(_Loser)));
00109 for (unsigned int __i = _M_ik - 1; __i < _M_k; ++__i)
00110 _M_losers[__i + _M_k]._M_sup = true;
00111
00112 _M_first_insert = true;
00113 }
00114
00115
00116
00117
00118 ~_LoserTreeBase()
00119 { ::operator delete(_M_losers); }
00120
00121
00122
00123
00124
00125
00126
00127
00128
00129 void
00130 __insert_start(const _Tp& __key, int __source, bool __sup)
00131 {
00132 unsigned int __pos = _M_k + __source;
00133
00134 if(_M_first_insert)
00135 {
00136
00137 for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
00138 new(&(_M_losers[__i]._M_key)) _Tp(__key);
00139 _M_first_insert = false;
00140 }
00141 else
00142 new(&(_M_losers[__pos]._M_key)) _Tp(__key);
00143
00144 _M_losers[__pos]._M_sup = __sup;
00145 _M_losers[__pos]._M_source = __source;
00146 }
00147
00148
00149
00150
00151 int __get_min_source()
00152 { return _M_losers[0]._M_source; }
00153 };
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163 template<bool __stable, typename _Tp,
00164 typename _Compare>
00165 class _LoserTree
00166 : public _LoserTreeBase<_Tp, _Compare>
00167 {
00168 typedef _LoserTreeBase<_Tp, _Compare> _Base;
00169 using _Base::_M_k;
00170 using _Base::_M_losers;
00171 using _Base::_M_first_insert;
00172
00173 public:
00174 _LoserTree(unsigned int __k, _Compare __comp)
00175 : _Base::_LoserTreeBase(__k, __comp)
00176 { }
00177
00178 unsigned int
00179 __init_winner(unsigned int __root)
00180 {
00181 if (__root >= _M_k)
00182 return __root;
00183 else
00184 {
00185 unsigned int __left = __init_winner(2 * __root);
00186 unsigned int __right = __init_winner(2 * __root + 1);
00187 if (_M_losers[__right]._M_sup
00188 || (!_M_losers[__left]._M_sup
00189 && !_M_comp(_M_losers[__right]._M_key,
00190 _M_losers[__left]._M_key)))
00191 {
00192
00193 _M_losers[__root] = _M_losers[__right];
00194 return __left;
00195 }
00196 else
00197 {
00198
00199 _M_losers[__root] = _M_losers[__left];
00200 return __right;
00201 }
00202 }
00203 }
00204
00205 void __init()
00206 { _M_losers[0] = _M_losers[__init_winner(1)]; }
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216 void
00217 __delete_min_insert(_Tp __key, bool __sup)
00218 {
00219 #if _GLIBCXX_ASSERTIONS
00220
00221 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00222 #endif
00223
00224 int __source = _M_losers[0]._M_source;
00225 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00226 __pos /= 2)
00227 {
00228
00229 if ((__sup && (!_M_losers[__pos]._M_sup
00230 || _M_losers[__pos]._M_source < __source))
00231 || (!__sup && !_M_losers[__pos]._M_sup
00232 && ((_M_comp(_M_losers[__pos]._M_key, __key))
00233 || (!_M_comp(__key, _M_losers[__pos]._M_key)
00234 && _M_losers[__pos]._M_source < __source))))
00235 {
00236
00237 std::swap(_M_losers[__pos]._M_sup, __sup);
00238 std::swap(_M_losers[__pos]._M_source, __source);
00239 std::swap(_M_losers[__pos]._M_key, __key);
00240 }
00241 }
00242
00243 _M_losers[0]._M_sup = __sup;
00244 _M_losers[0]._M_source = __source;
00245 _M_losers[0]._M_key = __key;
00246 }
00247 };
00248
00249
00250
00251
00252
00253
00254 template<typename _Tp, typename _Compare>
00255 class _LoserTree<false, _Tp, _Compare>
00256 : public _LoserTreeBase<_Tp, _Compare>
00257 {
00258 typedef _LoserTreeBase<_Tp, _Compare> _Base;
00259 using _Base::_M_log_k;
00260 using _Base::_M_k;
00261 using _Base::_M_losers;
00262 using _Base::_M_first_insert;
00263
00264 public:
00265 _LoserTree(unsigned int __k, _Compare __comp)
00266 : _Base::_LoserTreeBase(__k, __comp)
00267 { }
00268
00269
00270
00271
00272
00273
00274
00275
00276 unsigned int
00277 __init_winner(unsigned int __root)
00278 {
00279 if (__root >= _M_k)
00280 return __root;
00281 else
00282 {
00283 unsigned int __left = __init_winner(2 * __root);
00284 unsigned int __right = __init_winner(2 * __root + 1);
00285 if (_M_losers[__right]._M_sup
00286 || (!_M_losers[__left]._M_sup
00287 && !_M_comp(_M_losers[__right]._M_key,
00288 _M_losers[__left]._M_key)))
00289 {
00290
00291 _M_losers[__root] = _M_losers[__right];
00292 return __left;
00293 }
00294 else
00295 {
00296
00297 _M_losers[__root] = _M_losers[__left];
00298 return __right;
00299 }
00300 }
00301 }
00302
00303 void
00304 __init()
00305 { _M_losers[0] = _M_losers[__init_winner(1)]; }
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315
00316 void
00317 __delete_min_insert(_Tp __key, bool __sup)
00318 {
00319 #if _GLIBCXX_ASSERTIONS
00320
00321 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00322 #endif
00323
00324 int __source = _M_losers[0]._M_source;
00325 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00326 __pos /= 2)
00327 {
00328
00329 if (__sup || (!_M_losers[__pos]._M_sup
00330 && _M_comp(_M_losers[__pos]._M_key, __key)))
00331 {
00332
00333 std::swap(_M_losers[__pos]._M_sup, __sup);
00334 std::swap(_M_losers[__pos]._M_source, __source);
00335 std::swap(_M_losers[__pos]._M_key, __key);
00336 }
00337 }
00338
00339 _M_losers[0]._M_sup = __sup;
00340 _M_losers[0]._M_source = __source;
00341 _M_losers[0]._M_key = __key;
00342 }
00343 };
00344
00345
00346
00347
00348 template<typename _Tp, typename _Compare>
00349 class _LoserTreePointerBase
00350 {
00351 protected:
00352
00353 struct _Loser
00354 {
00355 bool _M_sup;
00356 int _M_source;
00357 const _Tp* _M_keyp;
00358 };
00359
00360 unsigned int _M_ik, _M_k, _M_offset;
00361 _Loser* _M_losers;
00362 _Compare _M_comp;
00363
00364 public:
00365 _LoserTreePointerBase(unsigned int __k,
00366 _Compare __comp = std::less<_Tp>())
00367 : _M_comp(__comp)
00368 {
00369 _M_ik = __k;
00370
00371
00372 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
00373 _M_offset = _M_k;
00374 _M_losers = new _Loser[_M_k * 2];
00375 for (unsigned int __i = _M_ik - 1; __i < _M_k; __i++)
00376 _M_losers[__i + _M_k]._M_sup = true;
00377 }
00378
00379 ~_LoserTreePointerBase()
00380 { ::operator delete[](_M_losers); }
00381
00382 int __get_min_source()
00383 { return _M_losers[0]._M_source; }
00384
00385 void __insert_start(const _Tp& __key, int __source, bool __sup)
00386 {
00387 unsigned int __pos = _M_k + __source;
00388
00389 _M_losers[__pos]._M_sup = __sup;
00390 _M_losers[__pos]._M_source = __source;
00391 _M_losers[__pos]._M_keyp = &__key;
00392 }
00393 };
00394
00395
00396
00397
00398
00399
00400 template<bool __stable, typename _Tp, typename _Compare>
00401 class _LoserTreePointer
00402 : public _LoserTreePointerBase<_Tp, _Compare>
00403 {
00404 typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
00405 using _Base::_M_k;
00406 using _Base::_M_losers;
00407
00408 public:
00409 _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
00410 : _Base::_LoserTreePointerBase(__k, __comp)
00411 { }
00412
00413 unsigned int
00414 __init_winner(unsigned int __root)
00415 {
00416 if (__root >= _M_k)
00417 return __root;
00418 else
00419 {
00420 unsigned int __left = __init_winner(2 * __root);
00421 unsigned int __right = __init_winner(2 * __root + 1);
00422 if (_M_losers[__right]._M_sup
00423 || (!_M_losers[__left]._M_sup
00424 && !_M_comp(*_M_losers[__right]._M_keyp,
00425 *_M_losers[__left]._M_keyp)))
00426 {
00427
00428 _M_losers[__root] = _M_losers[__right];
00429 return __left;
00430 }
00431 else
00432 {
00433
00434 _M_losers[__root] = _M_losers[__left];
00435 return __right;
00436 }
00437 }
00438 }
00439
00440 void __init()
00441 { _M_losers[0] = _M_losers[__init_winner(1)]; }
00442
00443 void __delete_min_insert(const _Tp& __key, bool __sup)
00444 {
00445 #if _GLIBCXX_ASSERTIONS
00446
00447 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00448 #endif
00449
00450 const _Tp* __keyp = &__key;
00451 int __source = _M_losers[0]._M_source;
00452 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00453 __pos /= 2)
00454 {
00455
00456 if ((__sup && (!_M_losers[__pos]._M_sup
00457 || _M_losers[__pos]._M_source < __source))
00458 || (!__sup && !_M_losers[__pos]._M_sup &&
00459 ((_M_comp(*_M_losers[__pos]._M_keyp, *__keyp))
00460 || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
00461 && _M_losers[__pos]._M_source < __source))))
00462 {
00463
00464 std::swap(_M_losers[__pos]._M_sup, __sup);
00465 std::swap(_M_losers[__pos]._M_source, __source);
00466 std::swap(_M_losers[__pos]._M_keyp, __keyp);
00467 }
00468 }
00469
00470 _M_losers[0]._M_sup = __sup;
00471 _M_losers[0]._M_source = __source;
00472 _M_losers[0]._M_keyp = __keyp;
00473 }
00474 };
00475
00476
00477
00478
00479
00480
00481 template<typename _Tp, typename _Compare>
00482 class _LoserTreePointer<false, _Tp, _Compare>
00483 : public _LoserTreePointerBase<_Tp, _Compare>
00484 {
00485 typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
00486 using _Base::_M_k;
00487 using _Base::_M_losers;
00488
00489 public:
00490 _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
00491 : _Base::_LoserTreePointerBase(__k, __comp)
00492 { }
00493
00494 unsigned int
00495 __init_winner(unsigned int __root)
00496 {
00497 if (__root >= _M_k)
00498 return __root;
00499 else
00500 {
00501 unsigned int __left = __init_winner(2 * __root);
00502 unsigned int __right = __init_winner(2 * __root + 1);
00503 if (_M_losers[__right]._M_sup
00504 || (!_M_losers[__left]._M_sup
00505 && !_M_comp(*_M_losers[__right]._M_keyp,
00506 *_M_losers[__left]._M_keyp)))
00507 {
00508
00509 _M_losers[__root] = _M_losers[__right];
00510 return __left;
00511 }
00512 else
00513 {
00514
00515 _M_losers[__root] = _M_losers[__left];
00516 return __right;
00517 }
00518 }
00519 }
00520
00521 void __init()
00522 { _M_losers[0] = _M_losers[__init_winner(1)]; }
00523
00524 void __delete_min_insert(const _Tp& __key, bool __sup)
00525 {
00526 #if _GLIBCXX_ASSERTIONS
00527
00528 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00529 #endif
00530
00531 const _Tp* __keyp = &__key;
00532 int __source = _M_losers[0]._M_source;
00533 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00534 __pos /= 2)
00535 {
00536
00537 if (__sup || (!_M_losers[__pos]._M_sup
00538 && _M_comp(*_M_losers[__pos]._M_keyp, *__keyp)))
00539 {
00540
00541 std::swap(_M_losers[__pos]._M_sup, __sup);
00542 std::swap(_M_losers[__pos]._M_source, __source);
00543 std::swap(_M_losers[__pos]._M_keyp, __keyp);
00544 }
00545 }
00546
00547 _M_losers[0]._M_sup = __sup;
00548 _M_losers[0]._M_source = __source;
00549 _M_losers[0]._M_keyp = __keyp;
00550 }
00551 };
00552
00553
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563 template<typename _Tp, typename _Compare>
00564 class _LoserTreeUnguardedBase
00565 {
00566 protected:
00567 struct _Loser
00568 {
00569 int _M_source;
00570 _Tp _M_key;
00571 };
00572
00573 unsigned int _M_ik, _M_k, _M_offset;
00574 _Loser* _M_losers;
00575 _Compare _M_comp;
00576
00577 public:
00578 _LoserTreeUnguardedBase(unsigned int __k, const _Tp __sentinel,
00579 _Compare __comp = std::less<_Tp>())
00580 : _M_comp(__comp)
00581 {
00582 _M_ik = __k;
00583
00584
00585 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
00586 _M_offset = _M_k;
00587
00588 _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
00589 * sizeof(_Loser)));
00590
00591 for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
00592 {
00593 _M_losers[__i]._M_key = __sentinel;
00594 _M_losers[__i]._M_source = -1;
00595 }
00596 }
00597
00598 ~_LoserTreeUnguardedBase()
00599 { ::operator delete(_M_losers); }
00600
00601 int
00602 __get_min_source()
00603 {
00604 #if _GLIBCXX_ASSERTIONS
00605
00606 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00607 #endif
00608 return _M_losers[0]._M_source;
00609 }
00610
00611 void
00612 __insert_start(const _Tp& __key, int __source, bool)
00613 {
00614 unsigned int __pos = _M_k + __source;
00615
00616 new(&(_M_losers[__pos]._M_key)) _Tp(__key);
00617 _M_losers[__pos]._M_source = __source;
00618 }
00619 };
00620
00621
00622
00623
00624
00625
00626 template<bool __stable, typename _Tp, typename _Compare>
00627 class _LoserTreeUnguarded
00628 : public _LoserTreeUnguardedBase<_Tp, _Compare>
00629 {
00630 typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
00631 using _Base::_M_k;
00632 using _Base::_M_losers;
00633
00634 public:
00635 _LoserTreeUnguarded(unsigned int __k, const _Tp __sentinel,
00636 _Compare __comp = std::less<_Tp>())
00637 : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
00638 { }
00639
00640 unsigned int
00641 __init_winner(unsigned int __root)
00642 {
00643 if (__root >= _M_k)
00644 return __root;
00645 else
00646 {
00647 unsigned int __left = __init_winner(2 * __root);
00648 unsigned int __right = __init_winner(2 * __root + 1);
00649 if (!_M_comp(_M_losers[__right]._M_key,
00650 _M_losers[__left]._M_key))
00651 {
00652
00653 _M_losers[__root] = _M_losers[__right];
00654 return __left;
00655 }
00656 else
00657 {
00658
00659 _M_losers[__root] = _M_losers[__left];
00660 return __right;
00661 }
00662 }
00663 }
00664
00665 void
00666 __init()
00667 {
00668 _M_losers[0] = _M_losers[__init_winner(1)];
00669
00670 #if _GLIBCXX_ASSERTIONS
00671
00672
00673 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00674 #endif
00675 }
00676
00677
00678
00679 void
00680 __delete_min_insert(_Tp __key, bool)
00681 {
00682 #if _GLIBCXX_ASSERTIONS
00683
00684 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00685 #endif
00686
00687 int __source = _M_losers[0]._M_source;
00688 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00689 __pos /= 2)
00690 {
00691
00692 if (_M_comp(_M_losers[__pos]._M_key, __key)
00693 || (!_M_comp(__key, _M_losers[__pos]._M_key)
00694 && _M_losers[__pos]._M_source < __source))
00695 {
00696
00697 std::swap(_M_losers[__pos]._M_source, __source);
00698 std::swap(_M_losers[__pos]._M_key, __key);
00699 }
00700 }
00701
00702 _M_losers[0]._M_source = __source;
00703 _M_losers[0]._M_key = __key;
00704 }
00705 };
00706
00707
00708
00709
00710
00711
00712 template<typename _Tp, typename _Compare>
00713 class _LoserTreeUnguarded<false, _Tp, _Compare>
00714 : public _LoserTreeUnguardedBase<_Tp, _Compare>
00715 {
00716 typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
00717 using _Base::_M_k;
00718 using _Base::_M_losers;
00719
00720 public:
00721 _LoserTreeUnguarded(unsigned int __k, const _Tp __sentinel,
00722 _Compare __comp = std::less<_Tp>())
00723 : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
00724 { }
00725
00726 unsigned int
00727 __init_winner(unsigned int __root)
00728 {
00729 if (__root >= _M_k)
00730 return __root;
00731 else
00732 {
00733 unsigned int __left = __init_winner(2 * __root);
00734 unsigned int __right = __init_winner(2 * __root + 1);
00735
00736 #if _GLIBCXX_ASSERTIONS
00737
00738 if (_M_losers[__left]._M_source == -1)
00739 _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
00740 #endif
00741
00742 if (!_M_comp(_M_losers[__right]._M_key,
00743 _M_losers[__left]._M_key))
00744 {
00745
00746 _M_losers[__root] = _M_losers[__right];
00747 return __left;
00748 }
00749 else
00750 {
00751
00752 _M_losers[__root] = _M_losers[__left];
00753 return __right;
00754 }
00755 }
00756 }
00757
00758 void
00759 __init()
00760 {
00761 _M_losers[0] = _M_losers[__init_winner(1)];
00762
00763 #if _GLIBCXX_ASSERTIONS
00764
00765
00766 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00767 #endif
00768 }
00769
00770
00771
00772 void
00773 __delete_min_insert(_Tp __key, bool)
00774 {
00775 #if _GLIBCXX_ASSERTIONS
00776
00777 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00778 #endif
00779
00780 int __source = _M_losers[0]._M_source;
00781 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00782 __pos /= 2)
00783 {
00784
00785 if (_M_comp(_M_losers[__pos]._M_key, __key))
00786 {
00787
00788 std::swap(_M_losers[__pos]._M_source, __source);
00789 std::swap(_M_losers[__pos]._M_key, __key);
00790 }
00791 }
00792
00793 _M_losers[0]._M_source = __source;
00794 _M_losers[0]._M_key = __key;
00795 }
00796 };
00797
00798
00799
00800
00801
00802
00803
00804 template<typename _Tp, typename _Compare>
00805 class _LoserTreePointerUnguardedBase
00806 {
00807 protected:
00808 struct _Loser
00809 {
00810 int _M_source;
00811 const _Tp* _M_keyp;
00812 };
00813
00814 unsigned int _M_ik, _M_k, _M_offset;
00815 _Loser* _M_losers;
00816 _Compare _M_comp;
00817
00818 public:
00819
00820 _LoserTreePointerUnguardedBase(unsigned int __k, const _Tp& __sentinel,
00821 _Compare __comp = std::less<_Tp>())
00822 : _M_comp(__comp)
00823 {
00824 _M_ik = __k;
00825
00826
00827 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
00828 _M_offset = _M_k;
00829
00830 _M_losers = new _Loser[2 * _M_k];
00831
00832 for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
00833 {
00834 _M_losers[__i]._M_keyp = &__sentinel;
00835 _M_losers[__i]._M_source = -1;
00836 }
00837 }
00838
00839 ~_LoserTreePointerUnguardedBase()
00840 { delete[] _M_losers; }
00841
00842 int
00843 __get_min_source()
00844 {
00845 #if _GLIBCXX_ASSERTIONS
00846
00847 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00848 #endif
00849 return _M_losers[0]._M_source;
00850 }
00851
00852 void
00853 __insert_start(const _Tp& __key, int __source, bool)
00854 {
00855 unsigned int __pos = _M_k + __source;
00856
00857 _M_losers[__pos]._M_keyp = &__key;
00858 _M_losers[__pos]._M_source = __source;
00859 }
00860 };
00861
00862
00863
00864
00865
00866
00867 template<bool __stable, typename _Tp, typename _Compare>
00868 class _LoserTreePointerUnguarded
00869 : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
00870 {
00871 typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
00872 using _Base::_M_k;
00873 using _Base::_M_losers;
00874
00875 public:
00876 _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
00877 _Compare __comp = std::less<_Tp>())
00878 : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
00879 { }
00880
00881 unsigned int
00882 __init_winner(unsigned int __root)
00883 {
00884 if (__root >= _M_k)
00885 return __root;
00886 else
00887 {
00888 unsigned int __left = __init_winner(2 * __root);
00889 unsigned int __right = __init_winner(2 * __root + 1);
00890 if (!_M_comp(*_M_losers[__right]._M_keyp,
00891 *_M_losers[__left]._M_keyp))
00892 {
00893
00894 _M_losers[__root] = _M_losers[__right];
00895 return __left;
00896 }
00897 else
00898 {
00899
00900 _M_losers[__root] = _M_losers[__left];
00901 return __right;
00902 }
00903 }
00904 }
00905
00906 void
00907 __init()
00908 {
00909 _M_losers[0] = _M_losers[__init_winner(1)];
00910
00911 #if _GLIBCXX_ASSERTIONS
00912
00913
00914 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00915 #endif
00916 }
00917
00918 void
00919 __delete_min_insert(const _Tp& __key, bool __sup)
00920 {
00921 #if _GLIBCXX_ASSERTIONS
00922
00923 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00924 #endif
00925
00926 const _Tp* __keyp = &__key;
00927 int __source = _M_losers[0]._M_source;
00928 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00929 __pos /= 2)
00930 {
00931
00932 if (_M_comp(*_M_losers[__pos]._M_keyp, *__keyp)
00933 || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
00934 && _M_losers[__pos]._M_source < __source))
00935 {
00936
00937 std::swap(_M_losers[__pos]._M_source, __source);
00938 std::swap(_M_losers[__pos]._M_keyp, __keyp);
00939 }
00940 }
00941
00942 _M_losers[0]._M_source = __source;
00943 _M_losers[0]._M_keyp = __keyp;
00944 }
00945 };
00946
00947
00948
00949
00950
00951
00952 template<typename _Tp, typename _Compare>
00953 class _LoserTreePointerUnguarded<false, _Tp, _Compare>
00954 : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
00955 {
00956 typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
00957 using _Base::_M_k;
00958 using _Base::_M_losers;
00959
00960 public:
00961 _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
00962 _Compare __comp = std::less<_Tp>())
00963 : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
00964 { }
00965
00966 unsigned int
00967 __init_winner(unsigned int __root)
00968 {
00969 if (__root >= _M_k)
00970 return __root;
00971 else
00972 {
00973 unsigned int __left = __init_winner(2 * __root);
00974 unsigned int __right = __init_winner(2 * __root + 1);
00975
00976 #if _GLIBCXX_ASSERTIONS
00977
00978 if (_M_losers[__left]._M_source == -1)
00979 _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
00980 #endif
00981
00982 if (!_M_comp(*_M_losers[__right]._M_keyp,
00983 *_M_losers[__left]._M_keyp))
00984 {
00985
00986 _M_losers[__root] = _M_losers[__right];
00987 return __left;
00988 }
00989 else
00990 {
00991
00992 _M_losers[__root] = _M_losers[__left];
00993 return __right;
00994 }
00995 }
00996 }
00997
00998 void
00999 __init()
01000 {
01001 _M_losers[0] = _M_losers[__init_winner(1)];
01002
01003 #if _GLIBCXX_ASSERTIONS
01004
01005
01006 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
01007 #endif
01008 }
01009
01010 void
01011 __delete_min_insert(const _Tp& __key, bool __sup)
01012 {
01013 #if _GLIBCXX_ASSERTIONS
01014
01015 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
01016 #endif
01017
01018 const _Tp* __keyp = &__key;
01019 int __source = _M_losers[0]._M_source;
01020 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
01021 __pos /= 2)
01022 {
01023
01024 if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp))
01025 {
01026
01027 std::swap(_M_losers[__pos]._M_source, __source);
01028 std::swap(_M_losers[__pos]._M_keyp, __keyp);
01029 }
01030 }
01031
01032 _M_losers[0]._M_source = __source;
01033 _M_losers[0]._M_keyp = __keyp;
01034 }
01035 };
01036 }
01037
01038 #endif