32 #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H 33 #define _GLIBCXX_PARALLEL_LOSERTREE_H 1 54 template<
typename _Tp,
typename _Compare>
69 unsigned int _M_ik, _M_k, _M_offset;
107 _M_losers =
static_cast<_Loser*
>(::operator
new(2 * _M_k
109 for (
unsigned int __i = _M_ik - 1; __i < _M_k; ++__i)
110 _M_losers[__i + _M_k].
_M_sup =
true;
112 _M_first_insert =
true;
120 for (
unsigned int __i = 0; __i < (2 * _M_k); ++__i)
136 unsigned int __pos = _M_k + __source;
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;
146 _M_losers[__pos].
_M_key = __key;
148 _M_losers[__pos].
_M_sup = __sup;
167 template<
bool __stable,
typename _Tp,
174 using _Base::_M_comp;
175 using _Base::_M_losers;
176 using _Base::_M_first_insert;
180 : _Base::_LoserTreeBase(__k, __comp)
184 __init_winner(
unsigned int __root)
190 unsigned int __left = __init_winner(2 * __root);
191 unsigned int __right = __init_winner(2 * __root + 1);
225 #if _GLIBCXX_PARALLEL_ASSERTIONS 231 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
260 template<
typename _Tp,
typename _Compare>
265 using _Base::_M_log_k;
267 using _Base::_M_comp;
268 using _Base::_M_losers;
269 using _Base::_M_first_insert;
273 : _Base::_LoserTreeBase(__k, __comp)
290 unsigned int __left = __init_winner(2 * __root);
291 unsigned int __right = __init_winner(2 * __root + 1);
327 #if _GLIBCXX_PARALLEL_ASSERTIONS 333 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
356 template<
typename _Tp,
typename _Compare>
368 unsigned int _M_ik, _M_k, _M_offset;
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;
391 {
return _M_losers[0]._M_source; }
395 unsigned int __pos = _M_k + __source;
397 _M_losers[__pos]._M_sup = __sup;
398 _M_losers[__pos]._M_source = __source;
399 _M_losers[__pos]._M_keyp = &__key;
408 template<
bool __stable,
typename _Tp,
typename _Compare>
414 using _Base::_M_comp;
415 using _Base::_M_losers;
419 : _Base::_LoserTreePointerBase(__k, __comp)
423 __init_winner(
unsigned int __root)
429 unsigned int __left = __init_winner(2 * __root);
430 unsigned int __right = __init_winner(2 * __root + 1);
452 void __delete_min_insert(
const _Tp& __key,
bool __sup)
454 #if _GLIBCXX_PARALLEL_ASSERTIONS 459 const _Tp* __keyp = &__key;
461 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
475 std::swap(
_M_losers[__pos]._M_keyp, __keyp);
490 template<
typename _Tp,
typename _Compare>
496 using _Base::_M_comp;
497 using _Base::_M_losers;
501 : _Base::_LoserTreePointerBase(__k, __comp)
505 __init_winner(
unsigned int __root)
511 unsigned int __left = __init_winner(2 * __root);
512 unsigned int __right = __init_winner(2 * __root + 1);
534 void __delete_min_insert(
const _Tp& __key,
bool __sup)
536 #if _GLIBCXX_PARALLEL_ASSERTIONS 541 const _Tp* __keyp = &__key;
543 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
553 std::swap(
_M_losers[__pos]._M_keyp, __keyp);
573 template<
typename _Tp,
typename _Compare>
583 unsigned int _M_ik, _M_k, _M_offset;
598 _M_losers =
static_cast<_Loser*
>(::operator
new(2 * _M_k
601 for (
unsigned int __i = 0; __i < _M_k; ++__i)
603 ::new(&(_M_losers[__i].
_M_key)) _Tp(__sentinel);
604 _M_losers[__i]._M_source = -1;
606 for (
unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
608 ::new(&(_M_losers[__i].
_M_key)) _Tp(__sentinel);
609 _M_losers[__i]._M_source = -1;
615 for (
unsigned int __i = 0; __i < (2 * _M_k); ++__i)
616 _M_losers[__i].~_Loser();
623 #if _GLIBCXX_PARALLEL_ASSERTIONS 625 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0].
_M_source != -1);
627 return _M_losers[0]._M_source;
633 unsigned int __pos = _M_k + __source;
635 ::new(&(_M_losers[__pos].
_M_key)) _Tp(__key);
636 _M_losers[__pos]._M_source = __source;
645 template<
bool __stable,
typename _Tp,
typename _Compare>
651 using _Base::_M_comp;
652 using _Base::_M_losers;
657 : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
661 __init_winner(
unsigned int __root)
667 unsigned int __left = __init_winner(2 * __root);
668 unsigned int __right = __init_winner(2 * __root + 1);
690 #if _GLIBCXX_PARALLEL_ASSERTIONS 700 __delete_min_insert(_Tp __key,
bool)
703 #if _GLIBCXX_PARALLEL_ASSERTIONS 709 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
733 template<
typename _Tp,
typename _Compare>
739 using _Base::_M_comp;
740 using _Base::_M_losers;
745 : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
749 __init_winner(
unsigned int __root)
755 unsigned int __left = __init_winner(2 * __root);
756 unsigned int __right = __init_winner(2 * __root + 1);
758 #if _GLIBCXX_PARALLEL_ASSERTIONS 785 #if _GLIBCXX_PARALLEL_ASSERTIONS 795 __delete_min_insert(_Tp __key,
bool)
798 #if _GLIBCXX_PARALLEL_ASSERTIONS 804 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
827 template<
typename _Tp,
typename _Compare>
837 unsigned int _M_ik, _M_k, _M_offset;
853 _M_losers =
new _Loser[2 * _M_k];
855 for (
unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
857 _M_losers[__i]._M_keyp = &__sentinel;
858 _M_losers[__i]._M_source = -1;
868 #if _GLIBCXX_PARALLEL_ASSERTIONS 870 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0].
_M_source != -1);
872 return _M_losers[0]._M_source;
878 unsigned int __pos = _M_k + __source;
880 _M_losers[__pos]._M_keyp = &__key;
881 _M_losers[__pos]._M_source = __source;
890 template<
bool __stable,
typename _Tp,
typename _Compare>
896 using _Base::_M_comp;
897 using _Base::_M_losers;
902 : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
906 __init_winner(
unsigned int __root)
912 unsigned int __left = __init_winner(2 * __root);
913 unsigned int __right = __init_winner(2 * __root + 1);
935 #if _GLIBCXX_PARALLEL_ASSERTIONS 943 __delete_min_insert(
const _Tp& __key,
bool __sup)
945 #if _GLIBCXX_PARALLEL_ASSERTIONS 950 const _Tp* __keyp = &__key;
952 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
962 std::swap(
_M_losers[__pos]._M_keyp, __keyp);
976 template<
typename _Tp,
typename _Compare>
982 using _Base::_M_comp;
983 using _Base::_M_losers;
988 : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
992 __init_winner(
unsigned int __root)
998 unsigned int __left = __init_winner(2 * __root);
999 unsigned int __right = __init_winner(2 * __root + 1);
1001 #if _GLIBCXX_PARALLEL_ASSERTIONS 1028 #if _GLIBCXX_PARALLEL_ASSERTIONS 1036 __delete_min_insert(
const _Tp& __key,
bool __sup)
1038 #if _GLIBCXX_PARALLEL_ASSERTIONS 1043 const _Tp* __keyp = &__key;
1045 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
1053 std::swap(
_M_losers[__pos]._M_keyp, __keyp);
Guarded loser/tournament tree.
Stable unguarded _LoserTree variant storing pointers.
Base class for unguarded _LoserTree implementation.
Internal representation of _LoserTree __elements.
_Tp _M_key
_M_key of the element in the _LoserTree.
void __insert_start(const _Tp &__key, int __source, bool __sup)
Initializes the sequence "_M_source" with the element "__key".
Stable implementation of unguarded _LoserTree.
_Compare _M_comp
_Compare to use.
_Loser * _M_losers
_LoserTree __elements.
~_LoserTreeBase()
The destructor.
int _M_source
__index of the __source __sequence.
_Size __rd_log2(_Size __n)
Calculates the rounded-down logarithm of __n for base 2.
bool _M_first_insert
State flag that determines whether the _LoserTree is empty.
Sequential helper functions. This file is a GNU parallel extension to the Standard C++ Library...
void __delete_min_insert(_Tp __key, bool __sup)
_LoserTreeBase(unsigned int __k, _Compare __comp)
The constructor.
Defines on whether to include algorithm variants.
Stable _LoserTree variant.
void __delete_min_insert(_Tp __key, bool __sup)
Delete the smallest element and insert a new element from the previously smallest element's sequence...
GNU parallel code for public use.
One of the comparison functors.
Unguarded loser tree, keeping only pointers to the elements in the tree structure.
unsigned int __init_winner(unsigned int __root)
bool _M_sup
flag, true iff this is a "maximum" __sentinel.
Base class of _Loser Tree implementation using pointers.
Internal representation of a _LoserTree element.
Stable _LoserTree implementation.