3 // Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
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
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.
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.
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/>.
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.
30 // Written by Johannes Singler.
32 #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
33 #define _GLIBCXX_PARALLEL_LOSERTREE_H 1
35 #include <bits/stl_algobase.h>
36 #include <bits/stl_function.h>
37 #include <parallel/features.h>
38 #include <parallel/base.h>
40 namespace __gnu_parallel
43 * @brief Guarded loser/tournament tree.
45 * The smallest element is at the top.
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.
51 * @param _Tp the element type
52 * @param _Compare the comparator to use, defaults to std::less<_Tp>
54 template<typename _Tp, typename _Compare>
58 /** @brief Internal representation of a _LoserTree element. */
61 /** @brief flag, true iff this is a "maximum" __sentinel. */
63 /** @brief __index of the __source __sequence. */
65 /** @brief _M_key of the element in the _LoserTree. */
69 unsigned int _M_ik, _M_k, _M_offset;
72 unsigned int _M_log_k;
74 /** @brief _LoserTree __elements. */
77 /** @brief _Compare to use. */
81 * @brief State flag that determines whether the _LoserTree is empty.
83 * Only used for building the _LoserTree.
89 * @brief The constructor.
91 * @param __k The number of sequences to merge.
92 * @param __comp The comparator to use.
94 _LoserTreeBase(unsigned int __k, _Compare __comp)
99 // Compute log_2{_M_k} for the _Loser Tree
100 _M_log_k = __rd_log2(_M_ik - 1) + 1;
102 // Next greater power of 2.
103 _M_k = 1 << _M_log_k;
106 // Avoid default-constructing _M_losers[]._M_key
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;
116 * @brief The destructor.
120 for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
121 _M_losers[__i].~_Loser();
122 ::operator delete(_M_losers);
126 * @brief Initializes the sequence "_M_source" with the element "__key".
128 * @param __key the element to insert
129 * @param __source __index of the __source __sequence
130 * @param __sup flag that determines whether the value to insert is an
131 * explicit __supremum.
134 __insert_start(const _Tp& __key, int __source, bool __sup)
136 unsigned int __pos = _M_k + __source;
140 // Construct all keys, so we can easily destruct them.
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;
149 _M_losers[__pos]._M_source = __source;
153 * @return the index of the sequence with the smallest element.
155 int __get_min_source()
156 { return _M_losers[0]._M_source; }
160 * @brief Stable _LoserTree variant.
162 * Provides the stable implementations of insert_start, __init_winner,
163 * __init and __delete_min_insert.
165 * Unstable variant is done using partial specialisation below.
167 template<bool __stable/* default == true */, typename _Tp,
170 : public _LoserTreeBase<_Tp, _Compare>
172 typedef _LoserTreeBase<_Tp, _Compare> _Base;
174 using _Base::_M_losers;
175 using _Base::_M_first_insert;
178 _LoserTree(unsigned int __k, _Compare __comp)
179 : _Base::_LoserTreeBase(__k, __comp)
183 __init_winner(unsigned int __root)
189 unsigned int __left = __init_winner(2 * __root);
190 unsigned int __right = __init_winner(2 * __root + 1);
191 if (_M_losers[__right]._M_sup
192 || (!_M_losers[__left]._M_sup
193 && !_M_comp(_M_losers[__right]._M_key,
194 _M_losers[__left]._M_key)))
196 // Left one is less or equal.
197 _M_losers[__root] = _M_losers[__right];
202 // Right one is less.
203 _M_losers[__root] = _M_losers[__left];
210 { _M_losers[0] = _M_losers[__init_winner(1)]; }
213 * @brief Delete the smallest element and insert a new element from
214 * the previously smallest element's sequence.
216 * This implementation is stable.
218 // Do not pass a const reference since __key will be used as
221 __delete_min_insert(_Tp __key, bool __sup)
224 #if _GLIBCXX_ASSERTIONS
225 // no dummy sequence can ever be at the top!
226 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
229 int __source = _M_losers[0]._M_source;
230 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
233 // The smaller one gets promoted, ties are broken by _M_source.
234 if ((__sup && (!_M_losers[__pos]._M_sup
235 || _M_losers[__pos]._M_source < __source))
236 || (!__sup && !_M_losers[__pos]._M_sup
237 && ((_M_comp(_M_losers[__pos]._M_key, __key))
238 || (!_M_comp(__key, _M_losers[__pos]._M_key)
239 && _M_losers[__pos]._M_source < __source))))
241 // The other one is smaller.
242 std::swap(_M_losers[__pos]._M_sup, __sup);
243 std::swap(_M_losers[__pos]._M_source, __source);
244 swap(_M_losers[__pos]._M_key, __key);
248 _M_losers[0]._M_sup = __sup;
249 _M_losers[0]._M_source = __source;
250 _M_losers[0]._M_key = __key;
255 * @brief Unstable _LoserTree variant.
257 * Stability (non-stable here) is selected with partial specialization.
259 template<typename _Tp, typename _Compare>
260 class _LoserTree</* __stable == */false, _Tp, _Compare>
261 : public _LoserTreeBase<_Tp, _Compare>
263 typedef _LoserTreeBase<_Tp, _Compare> _Base;
264 using _Base::_M_log_k;
266 using _Base::_M_losers;
267 using _Base::_M_first_insert;
270 _LoserTree(unsigned int __k, _Compare __comp)
271 : _Base::_LoserTreeBase(__k, __comp)
275 * Computes the winner of the competition at position "__root".
277 * Called recursively (starting at 0) to build the initial tree.
279 * @param __root __index of the "game" to start.
282 __init_winner(unsigned int __root)
288 unsigned int __left = __init_winner(2 * __root);
289 unsigned int __right = __init_winner(2 * __root + 1);
290 if (_M_losers[__right]._M_sup
291 || (!_M_losers[__left]._M_sup
292 && !_M_comp(_M_losers[__right]._M_key,
293 _M_losers[__left]._M_key)))
295 // Left one is less or equal.
296 _M_losers[__root] = _M_losers[__right];
301 // Right one is less.
302 _M_losers[__root] = _M_losers[__left];
310 { _M_losers[0] = _M_losers[__init_winner(1)]; }
313 * Delete the _M_key smallest element and insert the element __key
316 * @param __key the _M_key to insert
317 * @param __sup true iff __key is an explicitly marked supremum
319 // Do not pass a const reference since __key will be used as local
322 __delete_min_insert(_Tp __key, bool __sup)
325 #if _GLIBCXX_ASSERTIONS
326 // no dummy sequence can ever be at the top!
327 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
330 int __source = _M_losers[0]._M_source;
331 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
334 // The smaller one gets promoted.
335 if (__sup || (!_M_losers[__pos]._M_sup
336 && _M_comp(_M_losers[__pos]._M_key, __key)))
338 // The other one is smaller.
339 std::swap(_M_losers[__pos]._M_sup, __sup);
340 std::swap(_M_losers[__pos]._M_source, __source);
341 swap(_M_losers[__pos]._M_key, __key);
345 _M_losers[0]._M_sup = __sup;
346 _M_losers[0]._M_source = __source;
347 _M_losers[0]._M_key = __key;
352 * @brief Base class of _Loser Tree implementation using pointers.
354 template<typename _Tp, typename _Compare>
355 class _LoserTreePointerBase
358 /** @brief Internal representation of _LoserTree __elements. */
366 unsigned int _M_ik, _M_k, _M_offset;
371 _LoserTreePointerBase(unsigned int __k,
372 _Compare __comp = std::less<_Tp>())
377 // Next greater power of 2.
378 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
380 _M_losers = new _Loser[_M_k * 2];
381 for (unsigned int __i = _M_ik - 1; __i < _M_k; __i++)
382 _M_losers[__i + _M_k]._M_sup = true;
385 ~_LoserTreePointerBase()
386 { delete[] _M_losers; }
388 int __get_min_source()
389 { return _M_losers[0]._M_source; }
391 void __insert_start(const _Tp& __key, int __source, bool __sup)
393 unsigned int __pos = _M_k + __source;
395 _M_losers[__pos]._M_sup = __sup;
396 _M_losers[__pos]._M_source = __source;
397 _M_losers[__pos]._M_keyp = &__key;
402 * @brief Stable _LoserTree implementation.
404 * The unstable variant is implemented using partial instantiation below.
406 template<bool __stable/* default == true */, typename _Tp, typename _Compare>
407 class _LoserTreePointer
408 : public _LoserTreePointerBase<_Tp, _Compare>
410 typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
412 using _Base::_M_losers;
415 _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
416 : _Base::_LoserTreePointerBase(__k, __comp)
420 __init_winner(unsigned int __root)
426 unsigned int __left = __init_winner(2 * __root);
427 unsigned int __right = __init_winner(2 * __root + 1);
428 if (_M_losers[__right]._M_sup
429 || (!_M_losers[__left]._M_sup
430 && !_M_comp(*_M_losers[__right]._M_keyp,
431 *_M_losers[__left]._M_keyp)))
433 // Left one is less or equal.
434 _M_losers[__root] = _M_losers[__right];
439 // Right one is less.
440 _M_losers[__root] = _M_losers[__left];
447 { _M_losers[0] = _M_losers[__init_winner(1)]; }
449 void __delete_min_insert(const _Tp& __key, bool __sup)
451 #if _GLIBCXX_ASSERTIONS
452 // no dummy sequence can ever be at the top!
453 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
456 const _Tp* __keyp = &__key;
457 int __source = _M_losers[0]._M_source;
458 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
461 // The smaller one gets promoted, ties are broken by __source.
462 if ((__sup && (!_M_losers[__pos]._M_sup
463 || _M_losers[__pos]._M_source < __source))
464 || (!__sup && !_M_losers[__pos]._M_sup &&
465 ((_M_comp(*_M_losers[__pos]._M_keyp, *__keyp))
466 || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
467 && _M_losers[__pos]._M_source < __source))))
469 // The other one is smaller.
470 std::swap(_M_losers[__pos]._M_sup, __sup);
471 std::swap(_M_losers[__pos]._M_source, __source);
472 std::swap(_M_losers[__pos]._M_keyp, __keyp);
476 _M_losers[0]._M_sup = __sup;
477 _M_losers[0]._M_source = __source;
478 _M_losers[0]._M_keyp = __keyp;
483 * @brief Unstable _LoserTree implementation.
485 * The stable variant is above.
487 template<typename _Tp, typename _Compare>
488 class _LoserTreePointer</* __stable == */false, _Tp, _Compare>
489 : public _LoserTreePointerBase<_Tp, _Compare>
491 typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
493 using _Base::_M_losers;
496 _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
497 : _Base::_LoserTreePointerBase(__k, __comp)
501 __init_winner(unsigned int __root)
507 unsigned int __left = __init_winner(2 * __root);
508 unsigned int __right = __init_winner(2 * __root + 1);
509 if (_M_losers[__right]._M_sup
510 || (!_M_losers[__left]._M_sup
511 && !_M_comp(*_M_losers[__right]._M_keyp,
512 *_M_losers[__left]._M_keyp)))
514 // Left one is less or equal.
515 _M_losers[__root] = _M_losers[__right];
520 // Right one is less.
521 _M_losers[__root] = _M_losers[__left];
528 { _M_losers[0] = _M_losers[__init_winner(1)]; }
530 void __delete_min_insert(const _Tp& __key, bool __sup)
532 #if _GLIBCXX_ASSERTIONS
533 // no dummy sequence can ever be at the top!
534 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
537 const _Tp* __keyp = &__key;
538 int __source = _M_losers[0]._M_source;
539 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
542 // The smaller one gets promoted.
543 if (__sup || (!_M_losers[__pos]._M_sup
544 && _M_comp(*_M_losers[__pos]._M_keyp, *__keyp)))
546 // The other one is smaller.
547 std::swap(_M_losers[__pos]._M_sup, __sup);
548 std::swap(_M_losers[__pos]._M_source, __source);
549 std::swap(_M_losers[__pos]._M_keyp, __keyp);
553 _M_losers[0]._M_sup = __sup;
554 _M_losers[0]._M_source = __source;
555 _M_losers[0]._M_keyp = __keyp;
559 /** @brief Base class for unguarded _LoserTree implementation.
561 * The whole element is copied into the tree structure.
563 * No guarding is done, therefore not a single input sequence must
564 * run empty. Unused __sequence heads are marked with a sentinel which
565 * is > all elements that are to be merged.
567 * This is a very fast variant.
569 template<typename _Tp, typename _Compare>
570 class _LoserTreeUnguardedBase
579 unsigned int _M_ik, _M_k, _M_offset;
584 _LoserTreeUnguardedBase(unsigned int __k, const _Tp& __sentinel,
585 _Compare __comp = std::less<_Tp>())
590 // Next greater power of 2.
591 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
593 // Avoid default-constructing _M_losers[]._M_key
594 _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
597 for (unsigned int __i = 0; __i < _M_k; ++__i)
599 ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel);
600 _M_losers[__i]._M_source = -1;
602 for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
604 ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel);
605 _M_losers[__i]._M_source = -1;
609 ~_LoserTreeUnguardedBase()
611 for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
612 _M_losers[__i].~_Loser();
613 ::operator delete(_M_losers);
619 #if _GLIBCXX_ASSERTIONS
620 // no dummy sequence can ever be at the top!
621 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
623 return _M_losers[0]._M_source;
627 __insert_start(const _Tp& __key, int __source, bool)
629 unsigned int __pos = _M_k + __source;
631 ::new(&(_M_losers[__pos]._M_key)) _Tp(__key);
632 _M_losers[__pos]._M_source = __source;
637 * @brief Stable implementation of unguarded _LoserTree.
639 * Unstable variant is selected below with partial specialization.
641 template<bool __stable/* default == true */, typename _Tp, typename _Compare>
642 class _LoserTreeUnguarded
643 : public _LoserTreeUnguardedBase<_Tp, _Compare>
645 typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
647 using _Base::_M_losers;
650 _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
651 _Compare __comp = std::less<_Tp>())
652 : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
656 __init_winner(unsigned int __root)
662 unsigned int __left = __init_winner(2 * __root);
663 unsigned int __right = __init_winner(2 * __root + 1);
664 if (!_M_comp(_M_losers[__right]._M_key,
665 _M_losers[__left]._M_key))
667 // Left one is less or equal.
668 _M_losers[__root] = _M_losers[__right];
673 // Right one is less.
674 _M_losers[__root] = _M_losers[__left];
683 _M_losers[0] = _M_losers[__init_winner(1)];
685 #if _GLIBCXX_ASSERTIONS
686 // no dummy sequence can ever be at the top at the beginning
688 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
692 // Do not pass a const reference since __key will be used as
695 __delete_min_insert(_Tp __key, bool)
698 #if _GLIBCXX_ASSERTIONS
699 // no dummy sequence can ever be at the top!
700 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
703 int __source = _M_losers[0]._M_source;
704 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
707 // The smaller one gets promoted, ties are broken by _M_source.
708 if (_M_comp(_M_losers[__pos]._M_key, __key)
709 || (!_M_comp(__key, _M_losers[__pos]._M_key)
710 && _M_losers[__pos]._M_source < __source))
712 // The other one is smaller.
713 std::swap(_M_losers[__pos]._M_source, __source);
714 swap(_M_losers[__pos]._M_key, __key);
718 _M_losers[0]._M_source = __source;
719 _M_losers[0]._M_key = __key;
724 * @brief Non-Stable implementation of unguarded _LoserTree.
726 * Stable implementation is above.
728 template<typename _Tp, typename _Compare>
729 class _LoserTreeUnguarded</* __stable == */false, _Tp, _Compare>
730 : public _LoserTreeUnguardedBase<_Tp, _Compare>
732 typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
734 using _Base::_M_losers;
737 _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
738 _Compare __comp = std::less<_Tp>())
739 : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
743 __init_winner(unsigned int __root)
749 unsigned int __left = __init_winner(2 * __root);
750 unsigned int __right = __init_winner(2 * __root + 1);
752 #if _GLIBCXX_ASSERTIONS
753 // If __left one is sentinel then __right one must be, too.
754 if (_M_losers[__left]._M_source == -1)
755 _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
758 if (!_M_comp(_M_losers[__right]._M_key,
759 _M_losers[__left]._M_key))
761 // Left one is less or equal.
762 _M_losers[__root] = _M_losers[__right];
767 // Right one is less.
768 _M_losers[__root] = _M_losers[__left];
777 _M_losers[0] = _M_losers[__init_winner(1)];
779 #if _GLIBCXX_ASSERTIONS
780 // no dummy sequence can ever be at the top at the beginning
782 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
786 // Do not pass a const reference since __key will be used as
789 __delete_min_insert(_Tp __key, bool)
792 #if _GLIBCXX_ASSERTIONS
793 // no dummy sequence can ever be at the top!
794 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
797 int __source = _M_losers[0]._M_source;
798 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
801 // The smaller one gets promoted.
802 if (_M_comp(_M_losers[__pos]._M_key, __key))
804 // The other one is smaller.
805 std::swap(_M_losers[__pos]._M_source, __source);
806 swap(_M_losers[__pos]._M_key, __key);
810 _M_losers[0]._M_source = __source;
811 _M_losers[0]._M_key = __key;
815 /** @brief Unguarded loser tree, keeping only pointers to the
816 * elements in the tree structure.
818 * No guarding is done, therefore not a single input sequence must
819 * run empty. This is a very fast variant.
821 template<typename _Tp, typename _Compare>
822 class _LoserTreePointerUnguardedBase
831 unsigned int _M_ik, _M_k, _M_offset;
837 _LoserTreePointerUnguardedBase(unsigned int __k, const _Tp& __sentinel,
838 _Compare __comp = std::less<_Tp>())
843 // Next greater power of 2.
844 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
846 // Avoid default-constructing _M_losers[]._M_key
847 _M_losers = new _Loser[2 * _M_k];
849 for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
851 _M_losers[__i]._M_keyp = &__sentinel;
852 _M_losers[__i]._M_source = -1;
856 ~_LoserTreePointerUnguardedBase()
857 { delete[] _M_losers; }
862 #if _GLIBCXX_ASSERTIONS
863 // no dummy sequence can ever be at the top!
864 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
866 return _M_losers[0]._M_source;
870 __insert_start(const _Tp& __key, int __source, bool)
872 unsigned int __pos = _M_k + __source;
874 _M_losers[__pos]._M_keyp = &__key;
875 _M_losers[__pos]._M_source = __source;
880 * @brief Stable unguarded _LoserTree variant storing pointers.
882 * Unstable variant is implemented below using partial specialization.
884 template<bool __stable/* default == true */, typename _Tp, typename _Compare>
885 class _LoserTreePointerUnguarded
886 : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
888 typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
890 using _Base::_M_losers;
893 _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
894 _Compare __comp = std::less<_Tp>())
895 : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
899 __init_winner(unsigned int __root)
905 unsigned int __left = __init_winner(2 * __root);
906 unsigned int __right = __init_winner(2 * __root + 1);
907 if (!_M_comp(*_M_losers[__right]._M_keyp,
908 *_M_losers[__left]._M_keyp))
910 // Left one is less or equal.
911 _M_losers[__root] = _M_losers[__right];
916 // Right one is less.
917 _M_losers[__root] = _M_losers[__left];
926 _M_losers[0] = _M_losers[__init_winner(1)];
928 #if _GLIBCXX_ASSERTIONS
929 // no dummy sequence can ever be at the top at the beginning
931 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
936 __delete_min_insert(const _Tp& __key, bool __sup)
938 #if _GLIBCXX_ASSERTIONS
939 // no dummy sequence can ever be at the top!
940 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
943 const _Tp* __keyp = &__key;
944 int __source = _M_losers[0]._M_source;
945 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
948 // The smaller one gets promoted, ties are broken by _M_source.
949 if (_M_comp(*_M_losers[__pos]._M_keyp, *__keyp)
950 || (!_M_comp(*__keyp, *_M_losers[__pos]._M_keyp)
951 && _M_losers[__pos]._M_source < __source))
953 // The other one is smaller.
954 std::swap(_M_losers[__pos]._M_source, __source);
955 std::swap(_M_losers[__pos]._M_keyp, __keyp);
959 _M_losers[0]._M_source = __source;
960 _M_losers[0]._M_keyp = __keyp;
965 * @brief Unstable unguarded _LoserTree variant storing pointers.
967 * Stable variant is above.
969 template<typename _Tp, typename _Compare>
970 class _LoserTreePointerUnguarded</* __stable == */false, _Tp, _Compare>
971 : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
973 typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
975 using _Base::_M_losers;
978 _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
979 _Compare __comp = std::less<_Tp>())
980 : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
984 __init_winner(unsigned int __root)
990 unsigned int __left = __init_winner(2 * __root);
991 unsigned int __right = __init_winner(2 * __root + 1);
993 #if _GLIBCXX_ASSERTIONS
994 // If __left one is sentinel then __right one must be, too.
995 if (_M_losers[__left]._M_source == -1)
996 _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
999 if (!_M_comp(*_M_losers[__right]._M_keyp,
1000 *_M_losers[__left]._M_keyp))
1002 // Left one is less or equal.
1003 _M_losers[__root] = _M_losers[__right];
1008 // Right one is less.
1009 _M_losers[__root] = _M_losers[__left];
1018 _M_losers[0] = _M_losers[__init_winner(1)];
1020 #if _GLIBCXX_ASSERTIONS
1021 // no dummy sequence can ever be at the top at the beginning
1023 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1028 __delete_min_insert(const _Tp& __key, bool __sup)
1030 #if _GLIBCXX_ASSERTIONS
1031 // no dummy sequence can ever be at the top!
1032 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1035 const _Tp* __keyp = &__key;
1036 int __source = _M_losers[0]._M_source;
1037 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
1040 // The smaller one gets promoted.
1041 if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp))
1043 // The other one is smaller.
1044 std::swap(_M_losers[__pos]._M_source, __source);
1045 std::swap(_M_losers[__pos]._M_keyp, __keyp);
1049 _M_losers[0]._M_source = __source;
1050 _M_losers[0]._M_keyp = __keyp;
1053 } // namespace __gnu_parallel
1055 #endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */