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 using std::swap;
00220 #if _GLIBCXX_ASSERTIONS
00221
00222 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00223 #endif
00224
00225 int __source = _M_losers[0]._M_source;
00226 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00227 __pos /= 2)
00228 {
00229
00230 if ((__sup && (!_M_losers[__pos]._M_sup
00231 || _M_losers[__pos]._M_source < __source))
00232 || (!__sup && !_M_losers[__pos]._M_sup
00233 && ((_M_comp(_M_losers[__pos]._M_key, __key))
00234 || (!_M_comp(__key, _M_losers[__pos]._M_key)
00235 && _M_losers[__pos]._M_source < __source))))
00236 {
00237
00238 std::swap(_M_losers[__pos]._M_sup, __sup);
00239 std::swap(_M_losers[__pos]._M_source, __source);
00240 swap(_M_losers[__pos]._M_key, __key);
00241 }
00242 }
00243
00244 _M_losers[0]._M_sup = __sup;
00245 _M_losers[0]._M_source = __source;
00246 _M_losers[0]._M_key = __key;
00247 }
00248 };
00249
00250
00251
00252
00253
00254
00255 template<typename _Tp, typename _Compare>
00256 class _LoserTree<false, _Tp, _Compare>
00257 : public _LoserTreeBase<_Tp, _Compare>
00258 {
00259 typedef _LoserTreeBase<_Tp, _Compare> _Base;
00260 using _Base::_M_log_k;
00261 using _Base::_M_k;
00262 using _Base::_M_losers;
00263 using _Base::_M_first_insert;
00264
00265 public:
00266 _LoserTree(unsigned int __k, _Compare __comp)
00267 : _Base::_LoserTreeBase(__k, __comp)
00268 { }
00269
00270
00271
00272
00273
00274
00275
00276
00277 unsigned int
00278 __init_winner(unsigned int __root)
00279 {
00280 if (__root >= _M_k)
00281 return __root;
00282 else
00283 {
00284 unsigned int __left = __init_winner(2 * __root);
00285 unsigned int __right = __init_winner(2 * __root + 1);
00286 if (_M_losers[__right]._M_sup
00287 || (!_M_losers[__left]._M_sup
00288 && !_M_comp(_M_losers[__right]._M_key,
00289 _M_losers[__left]._M_key)))
00290 {
00291
00292 _M_losers[__root] = _M_losers[__right];
00293 return __left;
00294 }
00295 else
00296 {
00297
00298 _M_losers[__root] = _M_losers[__left];
00299 return __right;
00300 }
00301 }
00302 }
00303
00304 void
00305 __init()
00306 { _M_losers[0] = _M_losers[__init_winner(1)]; }
00307
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317 void
00318 __delete_min_insert(_Tp __key, bool __sup)
00319 {
00320 using std::swap;
00321 #if _GLIBCXX_ASSERTIONS
00322
00323 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00324 #endif
00325
00326 int __source = _M_losers[0]._M_source;
00327 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00328 __pos /= 2)
00329 {
00330
00331 if (__sup || (!_M_losers[__pos]._M_sup
00332 && _M_comp(_M_losers[__pos]._M_key, __key)))
00333 {
00334
00335 std::swap(_M_losers[__pos]._M_sup, __sup);
00336 std::swap(_M_losers[__pos]._M_source, __source);
00337 swap(_M_losers[__pos]._M_key, __key);
00338 }
00339 }
00340
00341 _M_losers[0]._M_sup = __sup;
00342 _M_losers[0]._M_source = __source;
00343 _M_losers[0]._M_key = __key;
00344 }
00345 };
00346
00347
00348
00349
00350 template<typename _Tp, typename _Compare>
00351 class _LoserTreePointerBase
00352 {
00353 protected:
00354
00355 struct _Loser
00356 {
00357 bool _M_sup;
00358 int _M_source;
00359 const _Tp* _M_keyp;
00360 };
00361
00362 unsigned int _M_ik, _M_k, _M_offset;
00363 _Loser* _M_losers;
00364 _Compare _M_comp;
00365
00366 public:
00367 _LoserTreePointerBase(unsigned int __k,
00368 _Compare __comp = std::less<_Tp>())
00369 : _M_comp(__comp)
00370 {
00371 _M_ik = __k;
00372
00373
00374 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
00375 _M_offset = _M_k;
00376 _M_losers = new _Loser[_M_k * 2];
00377 for (unsigned int __i = _M_ik - 1; __i < _M_k; __i++)
00378 _M_losers[__i + _M_k]._M_sup = true;
00379 }
00380
00381 ~_LoserTreePointerBase()
00382 { ::operator delete[](_M_losers); }
00383
00384 int __get_min_source()
00385 { return _M_losers[0]._M_source; }
00386
00387 void __insert_start(const _Tp& __key, int __source, bool __sup)
00388 {
00389 unsigned int __pos = _M_k + __source;
00390
00391 _M_losers[__pos]._M_sup = __sup;
00392 _M_losers[__pos]._M_source = __source;
00393 _M_losers[__pos]._M_keyp = &__key;
00394 }
00395 };
00396
00397
00398
00399
00400
00401
00402 template<bool __stable, typename _Tp, typename _Compare>
00403 class _LoserTreePointer
00404 : public _LoserTreePointerBase<_Tp, _Compare>
00405 {
00406 typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
00407 using _Base::_M_k;
00408 using _Base::_M_losers;
00409
00410 public:
00411 _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
00412 : _Base::_LoserTreePointerBase(__k, __comp)
00413 { }
00414
00415 unsigned int
00416 __init_winner(unsigned int __root)
00417 {
00418 if (__root >= _M_k)
00419 return __root;
00420 else
00421 {
00422 unsigned int __left = __init_winner(2 * __root);
00423 unsigned int __right = __init_winner(2 * __root + 1);
00424 if (_M_losers[__right]._M_sup
00425 || (!_M_losers[__left]._M_sup
00426 && !_M_comp(*_M_losers[__right]._M_keyp,
00427 *_M_losers[__left]._M_keyp)))
00428 {
00429
00430 _M_losers[__root] = _M_losers[__right];
00431 return __left;
00432 }
00433 else
00434 {
00435
00436 _M_losers[__root] = _M_losers[__left];
00437 return __right;
00438 }
00439 }
00440 }
00441
00442 void __init()
00443 { _M_losers[0] = _M_losers[__init_winner(1)]; }
00444
00445 void __delete_min_insert(const _Tp& __key, bool __sup)
00446 {
00447 #if _GLIBCXX_ASSERTIONS
00448
00449 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00450 #endif
00451
00452 const _Tp* __keyp = &__key;
00453 int __source = _M_losers[0]._M_source;
00454 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00455 __pos /= 2)
00456 {
00457
00458 if ((__sup && (!_M_losers[__pos]._M_sup
00459 || _M_losers[__pos]._M_source < __source))
00460 || (!__sup && !_M_losers[__pos]._M_sup &&
00461 ((_M_comp(*_M_losers[__pos]._M_keyp, *__keyp))
00462 || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
00463 && _M_losers[__pos]._M_source < __source))))
00464 {
00465
00466 std::swap(_M_losers[__pos]._M_sup, __sup);
00467 std::swap(_M_losers[__pos]._M_source, __source);
00468 std::swap(_M_losers[__pos]._M_keyp, __keyp);
00469 }
00470 }
00471
00472 _M_losers[0]._M_sup = __sup;
00473 _M_losers[0]._M_source = __source;
00474 _M_losers[0]._M_keyp = __keyp;
00475 }
00476 };
00477
00478
00479
00480
00481
00482
00483 template<typename _Tp, typename _Compare>
00484 class _LoserTreePointer<false, _Tp, _Compare>
00485 : public _LoserTreePointerBase<_Tp, _Compare>
00486 {
00487 typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
00488 using _Base::_M_k;
00489 using _Base::_M_losers;
00490
00491 public:
00492 _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
00493 : _Base::_LoserTreePointerBase(__k, __comp)
00494 { }
00495
00496 unsigned int
00497 __init_winner(unsigned int __root)
00498 {
00499 if (__root >= _M_k)
00500 return __root;
00501 else
00502 {
00503 unsigned int __left = __init_winner(2 * __root);
00504 unsigned int __right = __init_winner(2 * __root + 1);
00505 if (_M_losers[__right]._M_sup
00506 || (!_M_losers[__left]._M_sup
00507 && !_M_comp(*_M_losers[__right]._M_keyp,
00508 *_M_losers[__left]._M_keyp)))
00509 {
00510
00511 _M_losers[__root] = _M_losers[__right];
00512 return __left;
00513 }
00514 else
00515 {
00516
00517 _M_losers[__root] = _M_losers[__left];
00518 return __right;
00519 }
00520 }
00521 }
00522
00523 void __init()
00524 { _M_losers[0] = _M_losers[__init_winner(1)]; }
00525
00526 void __delete_min_insert(const _Tp& __key, bool __sup)
00527 {
00528 #if _GLIBCXX_ASSERTIONS
00529
00530 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00531 #endif
00532
00533 const _Tp* __keyp = &__key;
00534 int __source = _M_losers[0]._M_source;
00535 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00536 __pos /= 2)
00537 {
00538
00539 if (__sup || (!_M_losers[__pos]._M_sup
00540 && _M_comp(*_M_losers[__pos]._M_keyp, *__keyp)))
00541 {
00542
00543 std::swap(_M_losers[__pos]._M_sup, __sup);
00544 std::swap(_M_losers[__pos]._M_source, __source);
00545 std::swap(_M_losers[__pos]._M_keyp, __keyp);
00546 }
00547 }
00548
00549 _M_losers[0]._M_sup = __sup;
00550 _M_losers[0]._M_source = __source;
00551 _M_losers[0]._M_keyp = __keyp;
00552 }
00553 };
00554
00555
00556
00557
00558
00559
00560
00561
00562
00563
00564
00565 template<typename _Tp, typename _Compare>
00566 class _LoserTreeUnguardedBase
00567 {
00568 protected:
00569 struct _Loser
00570 {
00571 int _M_source;
00572 _Tp _M_key;
00573 };
00574
00575 unsigned int _M_ik, _M_k, _M_offset;
00576 _Loser* _M_losers;
00577 _Compare _M_comp;
00578
00579 public:
00580 _LoserTreeUnguardedBase(unsigned int __k, const _Tp __sentinel,
00581 _Compare __comp = std::less<_Tp>())
00582 : _M_comp(__comp)
00583 {
00584 _M_ik = __k;
00585
00586
00587 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
00588 _M_offset = _M_k;
00589
00590 _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
00591 * sizeof(_Loser)));
00592
00593 for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
00594 {
00595 _M_losers[__i]._M_key = __sentinel;
00596 _M_losers[__i]._M_source = -1;
00597 }
00598 }
00599
00600 ~_LoserTreeUnguardedBase()
00601 { ::operator delete(_M_losers); }
00602
00603 int
00604 __get_min_source()
00605 {
00606 #if _GLIBCXX_ASSERTIONS
00607
00608 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00609 #endif
00610 return _M_losers[0]._M_source;
00611 }
00612
00613 void
00614 __insert_start(const _Tp& __key, int __source, bool)
00615 {
00616 unsigned int __pos = _M_k + __source;
00617
00618 new(&(_M_losers[__pos]._M_key)) _Tp(__key);
00619 _M_losers[__pos]._M_source = __source;
00620 }
00621 };
00622
00623
00624
00625
00626
00627
00628 template<bool __stable, typename _Tp, typename _Compare>
00629 class _LoserTreeUnguarded
00630 : public _LoserTreeUnguardedBase<_Tp, _Compare>
00631 {
00632 typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
00633 using _Base::_M_k;
00634 using _Base::_M_losers;
00635
00636 public:
00637 _LoserTreeUnguarded(unsigned int __k, const _Tp __sentinel,
00638 _Compare __comp = std::less<_Tp>())
00639 : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
00640 { }
00641
00642 unsigned int
00643 __init_winner(unsigned int __root)
00644 {
00645 if (__root >= _M_k)
00646 return __root;
00647 else
00648 {
00649 unsigned int __left = __init_winner(2 * __root);
00650 unsigned int __right = __init_winner(2 * __root + 1);
00651 if (!_M_comp(_M_losers[__right]._M_key,
00652 _M_losers[__left]._M_key))
00653 {
00654
00655 _M_losers[__root] = _M_losers[__right];
00656 return __left;
00657 }
00658 else
00659 {
00660
00661 _M_losers[__root] = _M_losers[__left];
00662 return __right;
00663 }
00664 }
00665 }
00666
00667 void
00668 __init()
00669 {
00670 _M_losers[0] = _M_losers[__init_winner(1)];
00671
00672 #if _GLIBCXX_ASSERTIONS
00673
00674
00675 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00676 #endif
00677 }
00678
00679
00680
00681 void
00682 __delete_min_insert(_Tp __key, bool)
00683 {
00684 using std::swap;
00685 #if _GLIBCXX_ASSERTIONS
00686
00687 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00688 #endif
00689
00690 int __source = _M_losers[0]._M_source;
00691 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00692 __pos /= 2)
00693 {
00694
00695 if (_M_comp(_M_losers[__pos]._M_key, __key)
00696 || (!_M_comp(__key, _M_losers[__pos]._M_key)
00697 && _M_losers[__pos]._M_source < __source))
00698 {
00699
00700 std::swap(_M_losers[__pos]._M_source, __source);
00701 swap(_M_losers[__pos]._M_key, __key);
00702 }
00703 }
00704
00705 _M_losers[0]._M_source = __source;
00706 _M_losers[0]._M_key = __key;
00707 }
00708 };
00709
00710
00711
00712
00713
00714
00715 template<typename _Tp, typename _Compare>
00716 class _LoserTreeUnguarded<false, _Tp, _Compare>
00717 : public _LoserTreeUnguardedBase<_Tp, _Compare>
00718 {
00719 typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
00720 using _Base::_M_k;
00721 using _Base::_M_losers;
00722
00723 public:
00724 _LoserTreeUnguarded(unsigned int __k, const _Tp __sentinel,
00725 _Compare __comp = std::less<_Tp>())
00726 : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
00727 { }
00728
00729 unsigned int
00730 __init_winner(unsigned int __root)
00731 {
00732 if (__root >= _M_k)
00733 return __root;
00734 else
00735 {
00736 unsigned int __left = __init_winner(2 * __root);
00737 unsigned int __right = __init_winner(2 * __root + 1);
00738
00739 #if _GLIBCXX_ASSERTIONS
00740
00741 if (_M_losers[__left]._M_source == -1)
00742 _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
00743 #endif
00744
00745 if (!_M_comp(_M_losers[__right]._M_key,
00746 _M_losers[__left]._M_key))
00747 {
00748
00749 _M_losers[__root] = _M_losers[__right];
00750 return __left;
00751 }
00752 else
00753 {
00754
00755 _M_losers[__root] = _M_losers[__left];
00756 return __right;
00757 }
00758 }
00759 }
00760
00761 void
00762 __init()
00763 {
00764 _M_losers[0] = _M_losers[__init_winner(1)];
00765
00766 #if _GLIBCXX_ASSERTIONS
00767
00768
00769 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00770 #endif
00771 }
00772
00773
00774
00775 void
00776 __delete_min_insert(_Tp __key, bool)
00777 {
00778 using std::swap;
00779 #if _GLIBCXX_ASSERTIONS
00780
00781 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00782 #endif
00783
00784 int __source = _M_losers[0]._M_source;
00785 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00786 __pos /= 2)
00787 {
00788
00789 if (_M_comp(_M_losers[__pos]._M_key, __key))
00790 {
00791
00792 std::swap(_M_losers[__pos]._M_source, __source);
00793 swap(_M_losers[__pos]._M_key, __key);
00794 }
00795 }
00796
00797 _M_losers[0]._M_source = __source;
00798 _M_losers[0]._M_key = __key;
00799 }
00800 };
00801
00802
00803
00804
00805
00806
00807
00808 template<typename _Tp, typename _Compare>
00809 class _LoserTreePointerUnguardedBase
00810 {
00811 protected:
00812 struct _Loser
00813 {
00814 int _M_source;
00815 const _Tp* _M_keyp;
00816 };
00817
00818 unsigned int _M_ik, _M_k, _M_offset;
00819 _Loser* _M_losers;
00820 _Compare _M_comp;
00821
00822 public:
00823
00824 _LoserTreePointerUnguardedBase(unsigned int __k, const _Tp& __sentinel,
00825 _Compare __comp = std::less<_Tp>())
00826 : _M_comp(__comp)
00827 {
00828 _M_ik = __k;
00829
00830
00831 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
00832 _M_offset = _M_k;
00833
00834 _M_losers = new _Loser[2 * _M_k];
00835
00836 for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
00837 {
00838 _M_losers[__i]._M_keyp = &__sentinel;
00839 _M_losers[__i]._M_source = -1;
00840 }
00841 }
00842
00843 ~_LoserTreePointerUnguardedBase()
00844 { delete[] _M_losers; }
00845
00846 int
00847 __get_min_source()
00848 {
00849 #if _GLIBCXX_ASSERTIONS
00850
00851 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00852 #endif
00853 return _M_losers[0]._M_source;
00854 }
00855
00856 void
00857 __insert_start(const _Tp& __key, int __source, bool)
00858 {
00859 unsigned int __pos = _M_k + __source;
00860
00861 _M_losers[__pos]._M_keyp = &__key;
00862 _M_losers[__pos]._M_source = __source;
00863 }
00864 };
00865
00866
00867
00868
00869
00870
00871 template<bool __stable, typename _Tp, typename _Compare>
00872 class _LoserTreePointerUnguarded
00873 : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
00874 {
00875 typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
00876 using _Base::_M_k;
00877 using _Base::_M_losers;
00878
00879 public:
00880 _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
00881 _Compare __comp = std::less<_Tp>())
00882 : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
00883 { }
00884
00885 unsigned int
00886 __init_winner(unsigned int __root)
00887 {
00888 if (__root >= _M_k)
00889 return __root;
00890 else
00891 {
00892 unsigned int __left = __init_winner(2 * __root);
00893 unsigned int __right = __init_winner(2 * __root + 1);
00894 if (!_M_comp(*_M_losers[__right]._M_keyp,
00895 *_M_losers[__left]._M_keyp))
00896 {
00897
00898 _M_losers[__root] = _M_losers[__right];
00899 return __left;
00900 }
00901 else
00902 {
00903
00904 _M_losers[__root] = _M_losers[__left];
00905 return __right;
00906 }
00907 }
00908 }
00909
00910 void
00911 __init()
00912 {
00913 _M_losers[0] = _M_losers[__init_winner(1)];
00914
00915 #if _GLIBCXX_ASSERTIONS
00916
00917
00918 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00919 #endif
00920 }
00921
00922 void
00923 __delete_min_insert(const _Tp& __key, bool __sup)
00924 {
00925 #if _GLIBCXX_ASSERTIONS
00926
00927 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
00928 #endif
00929
00930 const _Tp* __keyp = &__key;
00931 int __source = _M_losers[0]._M_source;
00932 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
00933 __pos /= 2)
00934 {
00935
00936 if (_M_comp(*_M_losers[__pos]._M_keyp, *__keyp)
00937 || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
00938 && _M_losers[__pos]._M_source < __source))
00939 {
00940
00941 std::swap(_M_losers[__pos]._M_source, __source);
00942 std::swap(_M_losers[__pos]._M_keyp, __keyp);
00943 }
00944 }
00945
00946 _M_losers[0]._M_source = __source;
00947 _M_losers[0]._M_keyp = __keyp;
00948 }
00949 };
00950
00951
00952
00953
00954
00955
00956 template<typename _Tp, typename _Compare>
00957 class _LoserTreePointerUnguarded<false, _Tp, _Compare>
00958 : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
00959 {
00960 typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
00961 using _Base::_M_k;
00962 using _Base::_M_losers;
00963
00964 public:
00965 _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
00966 _Compare __comp = std::less<_Tp>())
00967 : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
00968 { }
00969
00970 unsigned int
00971 __init_winner(unsigned int __root)
00972 {
00973 if (__root >= _M_k)
00974 return __root;
00975 else
00976 {
00977 unsigned int __left = __init_winner(2 * __root);
00978 unsigned int __right = __init_winner(2 * __root + 1);
00979
00980 #if _GLIBCXX_ASSERTIONS
00981
00982 if (_M_losers[__left]._M_source == -1)
00983 _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
00984 #endif
00985
00986 if (!_M_comp(*_M_losers[__right]._M_keyp,
00987 *_M_losers[__left]._M_keyp))
00988 {
00989
00990 _M_losers[__root] = _M_losers[__right];
00991 return __left;
00992 }
00993 else
00994 {
00995
00996 _M_losers[__root] = _M_losers[__left];
00997 return __right;
00998 }
00999 }
01000 }
01001
01002 void
01003 __init()
01004 {
01005 _M_losers[0] = _M_losers[__init_winner(1)];
01006
01007 #if _GLIBCXX_ASSERTIONS
01008
01009
01010 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
01011 #endif
01012 }
01013
01014 void
01015 __delete_min_insert(const _Tp& __key, bool __sup)
01016 {
01017 #if _GLIBCXX_ASSERTIONS
01018
01019 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
01020 #endif
01021
01022 const _Tp* __keyp = &__key;
01023 int __source = _M_losers[0]._M_source;
01024 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
01025 __pos /= 2)
01026 {
01027
01028 if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp))
01029 {
01030
01031 std::swap(_M_losers[__pos]._M_source, __source);
01032 std::swap(_M_losers[__pos]._M_keyp, __keyp);
01033 }
01034 }
01035
01036 _M_losers[0]._M_source = __source;
01037 _M_losers[0]._M_keyp = __keyp;
01038 }
01039 };
01040 }
01041
01042 #endif