3 // Copyright (C) 2007, 2008, 2009 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.
119 { ::operator delete(_M_losers
); }
122 * @brief Initializes the sequence "_M_source" with the element "__key".
124 * @param __key the element to insert
125 * @param __source __index of the __source __sequence
126 * @param __sup flag that determines whether the value to insert is an
127 * explicit __supremum.
130 __insert_start(const _Tp
& __key
, int __source
, bool __sup
)
132 unsigned int __pos
= _M_k
+ __source
;
136 // Construct all keys, so we can easily deconstruct them.
137 for (unsigned int __i
= 0; __i
< (2 * _M_k
); ++__i
)
138 new(&(_M_losers
[__i
]._M_key
)) _Tp(__key
);
139 _M_first_insert
= false;
142 new(&(_M_losers
[__pos
]._M_key
)) _Tp(__key
);
144 _M_losers
[__pos
]._M_sup
= __sup
;
145 _M_losers
[__pos
]._M_source
= __source
;
149 * @return the index of the sequence with the smallest element.
151 int __get_min_source()
152 { return _M_losers
[0]._M_source
; }
156 * @brief Stable _LoserTree variant.
158 * Provides the stable implementations of insert_start, __init_winner,
159 * __init and __delete_min_insert.
161 * Unstable variant is done using partial specialisation below.
163 template<bool __stable
/* default == true */, typename _Tp
,
166 : public _LoserTreeBase
<_Tp
, _Compare
>
168 typedef _LoserTreeBase
<_Tp
, _Compare
> _Base
;
170 using _Base::_M_losers
;
171 using _Base::_M_first_insert
;
174 _LoserTree(unsigned int __k
, _Compare __comp
)
175 : _Base::_LoserTreeBase(__k
, __comp
)
179 __init_winner(unsigned int __root
)
185 unsigned int __left
= __init_winner(2 * __root
);
186 unsigned int __right
= __init_winner(2 * __root
+ 1);
187 if (_M_losers
[__right
]._M_sup
188 || (!_M_losers
[__left
]._M_sup
189 && !_M_comp(_M_losers
[__right
]._M_key
,
190 _M_losers
[__left
]._M_key
)))
192 // Left one is less or equal.
193 _M_losers
[__root
] = _M_losers
[__right
];
198 // Right one is less.
199 _M_losers
[__root
] = _M_losers
[__left
];
206 { _M_losers
[0] = _M_losers
[__init_winner(1)]; }
209 * @brief Delete the smallest element and insert a new element from
210 * the previously smallest element's sequence.
212 * This implementation is stable.
214 // Do not pass a const reference since __key will be used as
217 __delete_min_insert(_Tp __key
, bool __sup
)
219 #if _GLIBCXX_ASSERTIONS
220 // no dummy sequence can ever be at the top!
221 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
224 int __source
= _M_losers
[0]._M_source
;
225 for (unsigned int __pos
= (_M_k
+ __source
) / 2; __pos
> 0;
228 // The smaller one gets promoted, ties are broken by _M_source.
229 if ((__sup
&& (!_M_losers
[__pos
]._M_sup
230 || _M_losers
[__pos
]._M_source
< __source
))
231 || (!__sup
&& !_M_losers
[__pos
]._M_sup
232 && ((_M_comp(_M_losers
[__pos
]._M_key
, __key
))
233 || (!_M_comp(__key
, _M_losers
[__pos
]._M_key
)
234 && _M_losers
[__pos
]._M_source
< __source
))))
236 // The other one is smaller.
237 std::swap(_M_losers
[__pos
]._M_sup
, __sup
);
238 std::swap(_M_losers
[__pos
]._M_source
, __source
);
239 std::swap(_M_losers
[__pos
]._M_key
, __key
);
243 _M_losers
[0]._M_sup
= __sup
;
244 _M_losers
[0]._M_source
= __source
;
245 _M_losers
[0]._M_key
= __key
;
250 * @brief Unstable _LoserTree variant.
252 * Stability (non-stable here) is selected with partial specialization.
254 template<typename _Tp
, typename _Compare
>
255 class _LoserTree
</* __stable == */false, _Tp
, _Compare
>
256 : public _LoserTreeBase
<_Tp
, _Compare
>
258 typedef _LoserTreeBase
<_Tp
, _Compare
> _Base
;
259 using _Base::_M_log_k
;
261 using _Base::_M_losers
;
262 using _Base::_M_first_insert
;
265 _LoserTree(unsigned int __k
, _Compare __comp
)
266 : _Base::_LoserTreeBase(__k
, __comp
)
270 * Computes the winner of the competition at position "__root".
272 * Called recursively (starting at 0) to build the initial tree.
274 * @param __root __index of the "game" to start.
277 __init_winner(unsigned int __root
)
283 unsigned int __left
= __init_winner(2 * __root
);
284 unsigned int __right
= __init_winner(2 * __root
+ 1);
285 if (_M_losers
[__right
]._M_sup
286 || (!_M_losers
[__left
]._M_sup
287 && !_M_comp(_M_losers
[__right
]._M_key
,
288 _M_losers
[__left
]._M_key
)))
290 // Left one is less or equal.
291 _M_losers
[__root
] = _M_losers
[__right
];
296 // Right one is less.
297 _M_losers
[__root
] = _M_losers
[__left
];
305 { _M_losers
[0] = _M_losers
[__init_winner(1)]; }
308 * Delete the _M_key smallest element and insert the element __key
311 * @param __key the _M_key to insert
312 * @param __sup true iff __key is an explicitly marked supremum
314 // Do not pass a const reference since __key will be used as local
317 __delete_min_insert(_Tp __key
, bool __sup
)
319 #if _GLIBCXX_ASSERTIONS
320 // no dummy sequence can ever be at the top!
321 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
324 int __source
= _M_losers
[0]._M_source
;
325 for (unsigned int __pos
= (_M_k
+ __source
) / 2; __pos
> 0;
328 // The smaller one gets promoted.
329 if (__sup
|| (!_M_losers
[__pos
]._M_sup
330 && _M_comp(_M_losers
[__pos
]._M_key
, __key
)))
332 // The other one is smaller.
333 std::swap(_M_losers
[__pos
]._M_sup
, __sup
);
334 std::swap(_M_losers
[__pos
]._M_source
, __source
);
335 std::swap(_M_losers
[__pos
]._M_key
, __key
);
339 _M_losers
[0]._M_sup
= __sup
;
340 _M_losers
[0]._M_source
= __source
;
341 _M_losers
[0]._M_key
= __key
;
346 * @brief Base class of _Loser Tree implementation using pointers.
348 template<typename _Tp
, typename _Compare
>
349 class _LoserTreePointerBase
352 /** @brief Internal representation of _LoserTree __elements. */
360 unsigned int _M_ik
, _M_k
, _M_offset
;
365 _LoserTreePointerBase(unsigned int __k
,
366 _Compare __comp
= std::less
<_Tp
>())
371 // Next greater power of 2.
372 _M_k
= 1 << (__rd_log2(_M_ik
- 1) + 1);
374 _M_losers
= new _Loser
[_M_k
* 2];
375 for (unsigned int __i
= _M_ik
- 1; __i
< _M_k
; __i
++)
376 _M_losers
[__i
+ _M_k
]._M_sup
= true;
379 ~_LoserTreePointerBase()
380 { ::operator delete[](_M_losers
); }
382 int __get_min_source()
383 { return _M_losers
[0]._M_source
; }
385 void __insert_start(const _Tp
& __key
, int __source
, bool __sup
)
387 unsigned int __pos
= _M_k
+ __source
;
389 _M_losers
[__pos
]._M_sup
= __sup
;
390 _M_losers
[__pos
]._M_source
= __source
;
391 _M_losers
[__pos
]._M_keyp
= &__key
;
396 * @brief Stable _LoserTree implementation.
398 * The unstable variant is implemented using partial instantiation below.
400 template<bool __stable
/* default == true */, typename _Tp
, typename _Compare
>
401 class _LoserTreePointer
402 : public _LoserTreePointerBase
<_Tp
, _Compare
>
404 typedef _LoserTreePointerBase
<_Tp
, _Compare
> _Base
;
406 using _Base::_M_losers
;
409 _LoserTreePointer(unsigned int __k
, _Compare __comp
= std::less
<_Tp
>())
410 : _Base::_LoserTreePointerBase(__k
, __comp
)
414 __init_winner(unsigned int __root
)
420 unsigned int __left
= __init_winner(2 * __root
);
421 unsigned int __right
= __init_winner(2 * __root
+ 1);
422 if (_M_losers
[__right
]._M_sup
423 || (!_M_losers
[__left
]._M_sup
424 && !_M_comp(*_M_losers
[__right
]._M_keyp
,
425 *_M_losers
[__left
]._M_keyp
)))
427 // Left one is less or equal.
428 _M_losers
[__root
] = _M_losers
[__right
];
433 // Right one is less.
434 _M_losers
[__root
] = _M_losers
[__left
];
441 { _M_losers
[0] = _M_losers
[__init_winner(1)]; }
443 void __delete_min_insert(const _Tp
& __key
, bool __sup
)
445 #if _GLIBCXX_ASSERTIONS
446 // no dummy sequence can ever be at the top!
447 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
450 const _Tp
* __keyp
= &__key
;
451 int __source
= _M_losers
[0]._M_source
;
452 for (unsigned int __pos
= (_M_k
+ __source
) / 2; __pos
> 0;
455 // The smaller one gets promoted, ties are broken by __source.
456 if ((__sup
&& (!_M_losers
[__pos
]._M_sup
457 || _M_losers
[__pos
]._M_source
< __source
))
458 || (!__sup
&& !_M_losers
[__pos
]._M_sup
&&
459 ((_M_comp(*_M_losers
[__pos
]._M_keyp
, *__keyp
))
460 || (!_M_comp(*__keyp
, *_M_losers
[__pos
]._M_keyp
)
461 && _M_losers
[__pos
]._M_source
< __source
))))
463 // The other one is smaller.
464 std::swap(_M_losers
[__pos
]._M_sup
, __sup
);
465 std::swap(_M_losers
[__pos
]._M_source
, __source
);
466 std::swap(_M_losers
[__pos
]._M_keyp
, __keyp
);
470 _M_losers
[0]._M_sup
= __sup
;
471 _M_losers
[0]._M_source
= __source
;
472 _M_losers
[0]._M_keyp
= __keyp
;
477 * @brief Unstable _LoserTree implementation.
479 * The stable variant is above.
481 template<typename _Tp
, typename _Compare
>
482 class _LoserTreePointer
</* __stable == */false, _Tp
, _Compare
>
483 : public _LoserTreePointerBase
<_Tp
, _Compare
>
485 typedef _LoserTreePointerBase
<_Tp
, _Compare
> _Base
;
487 using _Base::_M_losers
;
490 _LoserTreePointer(unsigned int __k
, _Compare __comp
= std::less
<_Tp
>())
491 : _Base::_LoserTreePointerBase(__k
, __comp
)
495 __init_winner(unsigned int __root
)
501 unsigned int __left
= __init_winner(2 * __root
);
502 unsigned int __right
= __init_winner(2 * __root
+ 1);
503 if (_M_losers
[__right
]._M_sup
504 || (!_M_losers
[__left
]._M_sup
505 && !_M_comp(*_M_losers
[__right
]._M_keyp
,
506 *_M_losers
[__left
]._M_keyp
)))
508 // Left one is less or equal.
509 _M_losers
[__root
] = _M_losers
[__right
];
514 // Right one is less.
515 _M_losers
[__root
] = _M_losers
[__left
];
522 { _M_losers
[0] = _M_losers
[__init_winner(1)]; }
524 void __delete_min_insert(const _Tp
& __key
, bool __sup
)
526 #if _GLIBCXX_ASSERTIONS
527 // no dummy sequence can ever be at the top!
528 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
531 const _Tp
* __keyp
= &__key
;
532 int __source
= _M_losers
[0]._M_source
;
533 for (unsigned int __pos
= (_M_k
+ __source
) / 2; __pos
> 0;
536 // The smaller one gets promoted.
537 if (__sup
|| (!_M_losers
[__pos
]._M_sup
538 && _M_comp(*_M_losers
[__pos
]._M_keyp
, *__keyp
)))
540 // The other one is smaller.
541 std::swap(_M_losers
[__pos
]._M_sup
, __sup
);
542 std::swap(_M_losers
[__pos
]._M_source
, __source
);
543 std::swap(_M_losers
[__pos
]._M_keyp
, __keyp
);
547 _M_losers
[0]._M_sup
= __sup
;
548 _M_losers
[0]._M_source
= __source
;
549 _M_losers
[0]._M_keyp
= __keyp
;
553 /** @brief Base class for unguarded _LoserTree implementation.
555 * The whole element is copied into the tree structure.
557 * No guarding is done, therefore not a single input sequence must
558 * run empty. Unused __sequence heads are marked with a sentinel which
559 * is > all elements that are to be merged.
561 * This is a very fast variant.
563 template<typename _Tp
, typename _Compare
>
564 class _LoserTreeUnguardedBase
573 unsigned int _M_ik
, _M_k
, _M_offset
;
578 _LoserTreeUnguardedBase(unsigned int __k
, const _Tp __sentinel
,
579 _Compare __comp
= std::less
<_Tp
>())
584 // Next greater power of 2.
585 _M_k
= 1 << (__rd_log2(_M_ik
- 1) + 1);
587 // Avoid default-constructing _M_losers[]._M_key
588 _M_losers
= static_cast<_Loser
*>(::operator new(2 * _M_k
591 for (unsigned int __i
= _M_k
+ _M_ik
- 1; __i
< (2 * _M_k
); ++__i
)
593 _M_losers
[__i
]._M_key
= __sentinel
;
594 _M_losers
[__i
]._M_source
= -1;
598 ~_LoserTreeUnguardedBase()
599 { ::operator delete(_M_losers
); }
604 #if _GLIBCXX_ASSERTIONS
605 // no dummy sequence can ever be at the top!
606 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
608 return _M_losers
[0]._M_source
;
612 __insert_start(const _Tp
& __key
, int __source
, bool)
614 unsigned int __pos
= _M_k
+ __source
;
616 new(&(_M_losers
[__pos
]._M_key
)) _Tp(__key
);
617 _M_losers
[__pos
]._M_source
= __source
;
622 * @brief Stable implementation of unguarded _LoserTree.
624 * Unstable variant is selected below with partial specialization.
626 template<bool __stable
/* default == true */, typename _Tp
, typename _Compare
>
627 class _LoserTreeUnguarded
628 : public _LoserTreeUnguardedBase
<_Tp
, _Compare
>
630 typedef _LoserTreeUnguardedBase
<_Tp
, _Compare
> _Base
;
632 using _Base::_M_losers
;
635 _LoserTreeUnguarded(unsigned int __k
, const _Tp __sentinel
,
636 _Compare __comp
= std::less
<_Tp
>())
637 : _Base::_LoserTreeUnguardedBase(__k
, __sentinel
, __comp
)
641 __init_winner(unsigned int __root
)
647 unsigned int __left
= __init_winner(2 * __root
);
648 unsigned int __right
= __init_winner(2 * __root
+ 1);
649 if (!_M_comp(_M_losers
[__right
]._M_key
,
650 _M_losers
[__left
]._M_key
))
652 // Left one is less or equal.
653 _M_losers
[__root
] = _M_losers
[__right
];
658 // Right one is less.
659 _M_losers
[__root
] = _M_losers
[__left
];
668 _M_losers
[0] = _M_losers
[__init_winner(1)];
670 #if _GLIBCXX_ASSERTIONS
671 // no dummy sequence can ever be at the top at the beginning
673 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
677 // Do not pass a const reference since __key will be used as
680 __delete_min_insert(_Tp __key
, bool)
682 #if _GLIBCXX_ASSERTIONS
683 // no dummy sequence can ever be at the top!
684 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
687 int __source
= _M_losers
[0]._M_source
;
688 for (unsigned int __pos
= (_M_k
+ __source
) / 2; __pos
> 0;
691 // The smaller one gets promoted, ties are broken by _M_source.
692 if (_M_comp(_M_losers
[__pos
]._M_key
, __key
)
693 || (!_M_comp(__key
, _M_losers
[__pos
]._M_key
)
694 && _M_losers
[__pos
]._M_source
< __source
))
696 // The other one is smaller.
697 std::swap(_M_losers
[__pos
]._M_source
, __source
);
698 std::swap(_M_losers
[__pos
]._M_key
, __key
);
702 _M_losers
[0]._M_source
= __source
;
703 _M_losers
[0]._M_key
= __key
;
708 * @brief Non-Stable implementation of unguarded _LoserTree.
710 * Stable implementation is above.
712 template<typename _Tp
, typename _Compare
>
713 class _LoserTreeUnguarded
</* __stable == */false, _Tp
, _Compare
>
714 : public _LoserTreeUnguardedBase
<_Tp
, _Compare
>
716 typedef _LoserTreeUnguardedBase
<_Tp
, _Compare
> _Base
;
718 using _Base::_M_losers
;
721 _LoserTreeUnguarded(unsigned int __k
, const _Tp __sentinel
,
722 _Compare __comp
= std::less
<_Tp
>())
723 : _Base::_LoserTreeUnguardedBase(__k
, __sentinel
, __comp
)
727 __init_winner(unsigned int __root
)
733 unsigned int __left
= __init_winner(2 * __root
);
734 unsigned int __right
= __init_winner(2 * __root
+ 1);
736 #if _GLIBCXX_ASSERTIONS
737 // If __left one is sentinel then __right one must be, too.
738 if (_M_losers
[__left
]._M_source
== -1)
739 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[__right
]._M_source
== -1);
742 if (!_M_comp(_M_losers
[__right
]._M_key
,
743 _M_losers
[__left
]._M_key
))
745 // Left one is less or equal.
746 _M_losers
[__root
] = _M_losers
[__right
];
751 // Right one is less.
752 _M_losers
[__root
] = _M_losers
[__left
];
761 _M_losers
[0] = _M_losers
[__init_winner(1)];
763 #if _GLIBCXX_ASSERTIONS
764 // no dummy sequence can ever be at the top at the beginning
766 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
770 // Do not pass a const reference since __key will be used as
773 __delete_min_insert(_Tp __key
, bool)
775 #if _GLIBCXX_ASSERTIONS
776 // no dummy sequence can ever be at the top!
777 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
780 int __source
= _M_losers
[0]._M_source
;
781 for (unsigned int __pos
= (_M_k
+ __source
) / 2; __pos
> 0;
784 // The smaller one gets promoted.
785 if (_M_comp(_M_losers
[__pos
]._M_key
, __key
))
787 // The other one is smaller.
788 std::swap(_M_losers
[__pos
]._M_source
, __source
);
789 std::swap(_M_losers
[__pos
]._M_key
, __key
);
793 _M_losers
[0]._M_source
= __source
;
794 _M_losers
[0]._M_key
= __key
;
798 /** @brief Unguarded loser tree, keeping only pointers to the
799 * elements in the tree structure.
801 * No guarding is done, therefore not a single input sequence must
802 * run empty. This is a very fast variant.
804 template<typename _Tp
, typename _Compare
>
805 class _LoserTreePointerUnguardedBase
814 unsigned int _M_ik
, _M_k
, _M_offset
;
820 _LoserTreePointerUnguardedBase(unsigned int __k
, const _Tp
& __sentinel
,
821 _Compare __comp
= std::less
<_Tp
>())
826 // Next greater power of 2.
827 _M_k
= 1 << (__rd_log2(_M_ik
- 1) + 1);
829 // Avoid default-constructing _M_losers[]._M_key
830 _M_losers
= new _Loser
[2 * _M_k
];
832 for (unsigned int __i
= _M_k
+ _M_ik
- 1; __i
< (2 * _M_k
); ++__i
)
834 _M_losers
[__i
]._M_keyp
= &__sentinel
;
835 _M_losers
[__i
]._M_source
= -1;
839 ~_LoserTreePointerUnguardedBase()
840 { delete[] _M_losers
; }
845 #if _GLIBCXX_ASSERTIONS
846 // no dummy sequence can ever be at the top!
847 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
849 return _M_losers
[0]._M_source
;
853 __insert_start(const _Tp
& __key
, int __source
, bool)
855 unsigned int __pos
= _M_k
+ __source
;
857 _M_losers
[__pos
]._M_keyp
= &__key
;
858 _M_losers
[__pos
]._M_source
= __source
;
863 * @brief Stable unguarded _LoserTree variant storing pointers.
865 * Unstable variant is implemented below using partial specialization.
867 template<bool __stable
/* default == true */, typename _Tp
, typename _Compare
>
868 class _LoserTreePointerUnguarded
869 : public _LoserTreePointerUnguardedBase
<_Tp
, _Compare
>
871 typedef _LoserTreePointerUnguardedBase
<_Tp
, _Compare
> _Base
;
873 using _Base::_M_losers
;
876 _LoserTreePointerUnguarded(unsigned int __k
, const _Tp
& __sentinel
,
877 _Compare __comp
= std::less
<_Tp
>())
878 : _Base::_LoserTreePointerUnguardedBase(__k
, __sentinel
, __comp
)
882 __init_winner(unsigned int __root
)
888 unsigned int __left
= __init_winner(2 * __root
);
889 unsigned int __right
= __init_winner(2 * __root
+ 1);
890 if (!_M_comp(*_M_losers
[__right
]._M_keyp
,
891 *_M_losers
[__left
]._M_keyp
))
893 // Left one is less or equal.
894 _M_losers
[__root
] = _M_losers
[__right
];
899 // Right one is less.
900 _M_losers
[__root
] = _M_losers
[__left
];
909 _M_losers
[0] = _M_losers
[__init_winner(1)];
911 #if _GLIBCXX_ASSERTIONS
912 // no dummy sequence can ever be at the top at the beginning
914 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
919 __delete_min_insert(const _Tp
& __key
, bool __sup
)
921 #if _GLIBCXX_ASSERTIONS
922 // no dummy sequence can ever be at the top!
923 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
926 const _Tp
* __keyp
= &__key
;
927 int __source
= _M_losers
[0]._M_source
;
928 for (unsigned int __pos
= (_M_k
+ __source
) / 2; __pos
> 0;
931 // The smaller one gets promoted, ties are broken by _M_source.
932 if (_M_comp(*_M_losers
[__pos
]._M_keyp
, *__keyp
)
933 || (!_M_comp(*__keyp
, *_M_losers
[__pos
]._M_keyp
)
934 && _M_losers
[__pos
]._M_source
< __source
))
936 // The other one is smaller.
937 std::swap(_M_losers
[__pos
]._M_source
, __source
);
938 std::swap(_M_losers
[__pos
]._M_keyp
, __keyp
);
942 _M_losers
[0]._M_source
= __source
;
943 _M_losers
[0]._M_keyp
= __keyp
;
948 * @brief Unstable unguarded _LoserTree variant storing pointers.
950 * Stable variant is above.
952 template<typename _Tp
, typename _Compare
>
953 class _LoserTreePointerUnguarded
</* __stable == */false, _Tp
, _Compare
>
954 : public _LoserTreePointerUnguardedBase
<_Tp
, _Compare
>
956 typedef _LoserTreePointerUnguardedBase
<_Tp
, _Compare
> _Base
;
958 using _Base::_M_losers
;
961 _LoserTreePointerUnguarded(unsigned int __k
, const _Tp
& __sentinel
,
962 _Compare __comp
= std::less
<_Tp
>())
963 : _Base::_LoserTreePointerUnguardedBase(__k
, __sentinel
, __comp
)
967 __init_winner(unsigned int __root
)
973 unsigned int __left
= __init_winner(2 * __root
);
974 unsigned int __right
= __init_winner(2 * __root
+ 1);
976 #if _GLIBCXX_ASSERTIONS
977 // If __left one is sentinel then __right one must be, too.
978 if (_M_losers
[__left
]._M_source
== -1)
979 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[__right
]._M_source
== -1);
982 if (!_M_comp(*_M_losers
[__right
]._M_keyp
,
983 *_M_losers
[__left
]._M_keyp
))
985 // Left one is less or equal.
986 _M_losers
[__root
] = _M_losers
[__right
];
991 // Right one is less.
992 _M_losers
[__root
] = _M_losers
[__left
];
1001 _M_losers
[0] = _M_losers
[__init_winner(1)];
1003 #if _GLIBCXX_ASSERTIONS
1004 // no dummy sequence can ever be at the top at the beginning
1006 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
1011 __delete_min_insert(const _Tp
& __key
, bool __sup
)
1013 #if _GLIBCXX_ASSERTIONS
1014 // no dummy sequence can ever be at the top!
1015 _GLIBCXX_PARALLEL_ASSERT(_M_losers
[0]._M_source
!= -1);
1018 const _Tp
* __keyp
= &__key
;
1019 int __source
= _M_losers
[0]._M_source
;
1020 for (unsigned int __pos
= (_M_k
+ __source
) / 2; __pos
> 0;
1023 // The smaller one gets promoted.
1024 if (_M_comp(*(_M_losers
[__pos
]._M_keyp
), *__keyp
))
1026 // The other one is smaller.
1027 std::swap(_M_losers
[__pos
]._M_source
, __source
);
1028 std::swap(_M_losers
[__pos
]._M_keyp
, __keyp
);
1032 _M_losers
[0]._M_source
= __source
;
1033 _M_losers
[0]._M_keyp
= __keyp
;
1036 } // namespace __gnu_parallel
1038 #endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */