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;
109 for (
unsigned int __i = _M_ik - 1; __i < _M_k; ++__i)
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);
167 template<
bool __stable,
typename _Tp,
184 __init_winner(
unsigned int __root)
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)))
198 _M_losers[__root] = _M_losers[__right];
204 _M_losers[__root] = _M_losers[__left];
211 { _M_losers[0] = _M_losers[__init_winner(1)]; }
225 #if _GLIBCXX_PARALLEL_ASSERTIONS 227 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
230 int __source = _M_losers[0]._M_source;
231 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
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))))
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);
249 _M_losers[0]._M_sup = __sup;
250 _M_losers[0]._M_source = __source;
251 _M_losers[0]._M_key = __key;
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);
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)))
298 _M_losers[__root] = _M_losers[__right];
304 _M_losers[__root] = _M_losers[__left];
312 { _M_losers[0] = _M_losers[__init_winner(1)]; }
327 #if _GLIBCXX_PARALLEL_ASSERTIONS 329 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
332 int __source = _M_losers[0]._M_source;
333 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
337 if (__sup || (!_M_losers[__pos]._M_sup
338 && _M_comp(_M_losers[__pos]._M_key, __key)))
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);
347 _M_losers[0]._M_sup = __sup;
348 _M_losers[0]._M_source = __source;
349 _M_losers[0]._M_key = __key;
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;
388 {
delete[] _M_losers; }
390 int __get_min_source()
391 {
return _M_losers[0]._M_source; }
393 void __insert_start(
const _Tp& __key,
int __source,
bool __sup)
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);
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)))
437 _M_losers[__root] = _M_losers[__right];
443 _M_losers[__root] = _M_losers[__left];
450 { _M_losers[0] = _M_losers[__init_winner(1)]; }
452 void __delete_min_insert(
const _Tp& __key,
bool __sup)
454 #if _GLIBCXX_PARALLEL_ASSERTIONS 456 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
459 const _Tp* __keyp = &__key;
460 int __source = _M_losers[0]._M_source;
461 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
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))))
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);
479 _M_losers[0]._M_sup = __sup;
480 _M_losers[0]._M_source = __source;
481 _M_losers[0]._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);
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)))
519 _M_losers[__root] = _M_losers[__right];
525 _M_losers[__root] = _M_losers[__left];
532 { _M_losers[0] = _M_losers[__init_winner(1)]; }
534 void __delete_min_insert(
const _Tp& __key,
bool __sup)
536 #if _GLIBCXX_PARALLEL_ASSERTIONS 538 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
541 const _Tp* __keyp = &__key;
542 int __source = _M_losers[0]._M_source;
543 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
547 if (__sup || (!_M_losers[__pos]._M_sup
548 && _M_comp(*_M_losers[__pos]._M_keyp, *__keyp)))
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);
557 _M_losers[0]._M_sup = __sup;
558 _M_losers[0]._M_source = __source;
559 _M_losers[0]._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();
617 ::operator
delete(_M_losers);
623 #if _GLIBCXX_PARALLEL_ASSERTIONS 625 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
627 return _M_losers[0]._M_source;
631 __insert_start(
const _Tp& __key,
int __source,
bool)
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);
669 if (!_M_comp(_M_losers[__right]._M_key,
670 _M_losers[__left]._M_key))
673 _M_losers[__root] = _M_losers[__right];
679 _M_losers[__root] = _M_losers[__left];
688 _M_losers[0] = _M_losers[__init_winner(1)];
690 #if _GLIBCXX_PARALLEL_ASSERTIONS 693 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
700 __delete_min_insert(_Tp __key,
bool)
703 #if _GLIBCXX_PARALLEL_ASSERTIONS 705 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
708 int __source = _M_losers[0]._M_source;
709 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
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))
718 std::swap(_M_losers[__pos]._M_source, __source);
719 swap(_M_losers[__pos]._M_key, __key);
723 _M_losers[0]._M_source = __source;
724 _M_losers[0]._M_key = __key;
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 760 if (_M_losers[__left]._M_source == -1)
761 _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
764 if (!_M_comp(_M_losers[__right]._M_key,
765 _M_losers[__left]._M_key))
768 _M_losers[__root] = _M_losers[__right];
774 _M_losers[__root] = _M_losers[__left];
783 _M_losers[0] = _M_losers[__init_winner(1)];
785 #if _GLIBCXX_PARALLEL_ASSERTIONS 788 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
795 __delete_min_insert(_Tp __key,
bool)
798 #if _GLIBCXX_PARALLEL_ASSERTIONS 800 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
803 int __source = _M_losers[0]._M_source;
804 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
808 if (_M_comp(_M_losers[__pos]._M_key, __key))
811 std::swap(_M_losers[__pos]._M_source, __source);
812 swap(_M_losers[__pos]._M_key, __key);
816 _M_losers[0]._M_source = __source;
817 _M_losers[0]._M_key = __key;
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;
863 {
delete[] _M_losers; }
868 #if _GLIBCXX_PARALLEL_ASSERTIONS 870 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
872 return _M_losers[0]._M_source;
876 __insert_start(
const _Tp& __key,
int __source,
bool)
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);
914 if (!_M_comp(*_M_losers[__right]._M_keyp,
915 *_M_losers[__left]._M_keyp))
918 _M_losers[__root] = _M_losers[__right];
924 _M_losers[__root] = _M_losers[__left];
933 _M_losers[0] = _M_losers[__init_winner(1)];
935 #if _GLIBCXX_PARALLEL_ASSERTIONS 938 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
943 __delete_min_insert(
const _Tp& __key,
bool __sup)
945 #if _GLIBCXX_PARALLEL_ASSERTIONS 947 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
950 const _Tp* __keyp = &__key;
951 int __source = _M_losers[0]._M_source;
952 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
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))
961 std::swap(_M_losers[__pos]._M_source, __source);
962 std::swap(_M_losers[__pos]._M_keyp, __keyp);
966 _M_losers[0]._M_source = __source;
967 _M_losers[0]._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 1003 if (_M_losers[__left]._M_source == -1)
1004 _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
1007 if (!_M_comp(*_M_losers[__right]._M_keyp,
1008 *_M_losers[__left]._M_keyp))
1011 _M_losers[__root] = _M_losers[__right];
1017 _M_losers[__root] = _M_losers[__left];
1026 _M_losers[0] = _M_losers[__init_winner(1)];
1028 #if _GLIBCXX_PARALLEL_ASSERTIONS 1031 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1036 __delete_min_insert(
const _Tp& __key,
bool __sup)
1038 #if _GLIBCXX_PARALLEL_ASSERTIONS 1040 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1043 const _Tp* __keyp = &__key;
1044 int __source = _M_losers[0]._M_source;
1045 for (
unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
1049 if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp))
1052 std::swap(_M_losers[__pos]._M_source, __source);
1053 std::swap(_M_losers[__pos]._M_keyp, __keyp);
1057 _M_losers[0]._M_source = __source;
1058 _M_losers[0]._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.