1 // -*- C++ -*-
2
3 // Copyright (C) 2007-2023 Free Software Foundation, Inc.
4 //
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
9 // version.
10
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.
15
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.
19
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/>.
24
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.
28 */
29
30 // Written by Johannes Singler.
31
32 #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
33 #define _GLIBCXX_PARALLEL_LOSERTREE_H 1
34
35 #include <bits/stl_algobase.h>
36 #include <bits/stl_function.h>
37 #include <parallel/features.h>
38 #include <parallel/base.h>
39
40 namespace __gnu_parallel
41 {
42 /**
43 * @brief Guarded loser/tournament tree.
44 *
45 * The smallest element is at the top.
46 *
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.
50 *
51 * @param _Tp the element type
52 * @param _Compare the comparator to use, defaults to std::less<_Tp>
53 */
54 template<typename _Tp, typename _Compare>
55 class _LoserTreeBase
56 {
57 protected:
58 /** @brief Internal representation of a _LoserTree element. */
59 struct _Loser
60 {
61 /** @brief flag, true iff this is a "maximum" __sentinel. */
62 bool _M_sup;
63 /** @brief __index of the __source __sequence. */
64 int _M_source;
65 /** @brief _M_key of the element in the _LoserTree. */
66 _Tp _M_key;
67 };
68
69 unsigned int _M_ik, _M_k, _M_offset;
70
71 /** log_2{_M_k} */
72 unsigned int _M_log_k;
73
74 /** @brief _LoserTree __elements. */
75 _Loser* _M_losers;
76
77 /** @brief _Compare to use. */
78 _Compare _M_comp;
79
80 /**
81 * @brief State flag that determines whether the _LoserTree is empty.
82 *
83 * Only used for building the _LoserTree.
84 */
85 bool _M_first_insert;
86
87 public:
88 /**
89 * @brief The constructor.
90 *
91 * @param __k The number of sequences to merge.
92 * @param __comp The comparator to use.
93 */
94 _LoserTreeBase(unsigned int __k, _Compare __comp)
95 : _M_comp(__comp)
96 {
97 _M_ik = __k;
98
99 // Compute log_2{_M_k} for the _Loser Tree
100 _M_log_k = __rd_log2(_M_ik - 1) + 1;
101
102 // Next greater power of 2.
103 _M_k = 1 << _M_log_k;
104 _M_offset = _M_k;
105
106 // Avoid default-constructing _M_losers[]._M_key
107 _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
108 * sizeof(_Loser)));
109 for (unsigned int __i = _M_ik - 1; __i < _M_k; ++__i)
110 _M_losers[__i + _M_k]._M_sup = true;
111
112 _M_first_insert = true;
113 }
114
115 /**
116 * @brief The destructor.
117 */
118 ~_LoserTreeBase()
119 {
120 for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
121 _M_losers[__i].~_Loser();
122 ::operator delete(_M_losers);
123 }
124
125 /**
126 * @brief Initializes the sequence "_M_source" with the element "__key".
127 *
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.
132 */
133 void
134 __insert_start(const _Tp& __key, int __source, bool __sup)
135 {
136 unsigned int __pos = _M_k + __source;
137
138 if (_M_first_insert)
139 {
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;
144 }
145 else
146 _M_losers[__pos]._M_key = __key;
147
148 _M_losers[__pos]._M_sup = __sup;
149 _M_losers[__pos]._M_source = __source;
150 }
151
152 /**
153 * @return the index of the sequence with the smallest element.
154 */
155 int __get_min_source()
156 { return _M_losers[0]._M_source; }
157 };
158
159 /**
160 * @brief Stable _LoserTree variant.
161 *
162 * Provides the stable implementations of insert_start, __init_winner,
163 * __init and __delete_min_insert.
164 *
165 * Unstable variant is done using partial specialisation below.
166 */
167 template<bool __stable/* default == true */, typename _Tp,
168 typename _Compare>
169 class _LoserTree
170 : public _LoserTreeBase<_Tp, _Compare>
171 {
172 typedef _LoserTreeBase<_Tp, _Compare> _Base;
173 using _Base::_M_k;
174 using _Base::_M_comp;
175 using _Base::_M_losers;
176 using _Base::_M_first_insert;
177
178 public:
179 _LoserTree(unsigned int __k, _Compare __comp)
180 : _Base::_LoserTreeBase(__k, __comp)
181 { }
182
183 unsigned int
184 __init_winner(unsigned int __root)
185 {
186 if (__root >= _M_k)
187 return __root;
188 else
189 {
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)))
196 {
197 // Left one is less or equal.
198 _M_losers[__root] = _M_losers[__right];
199 return __left;
200 }
201 else
202 {
203 // Right one is less.
204 _M_losers[__root] = _M_losers[__left];
205 return __right;
206 }
207 }
208 }
209
210 void __init()
211 { _M_losers[0] = _M_losers[__init_winner(1)]; }
212
213 /**
214 * @brief Delete the smallest element and insert a new element from
215 * the previously smallest element's sequence.
216 *
217 * This implementation is stable.
218 */
219 // Do not pass a const reference since __key will be used as
220 // local variable.
221 void
222 __delete_min_insert(_Tp __key, bool __sup)
223 {
224 using std::swap;
225 #if _GLIBCXX_PARALLEL_ASSERTIONS
226 // no dummy sequence can ever be at the top!
227 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
228 #endif
229
230 int __source = _M_losers[0]._M_source;
231 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
232 __pos /= 2)
233 {
234 // The smaller one gets promoted, ties are broken by _M_source.
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))))
241 {
242 // The other one is smaller.
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);
246 }
247 }
248
249 _M_losers[0]._M_sup = __sup;
250 _M_losers[0]._M_source = __source;
251 _M_losers[0]._M_key = __key;
252 }
253 };
254
255 /**
256 * @brief Unstable _LoserTree variant.
257 *
258 * Stability (non-stable here) is selected with partial specialization.
259 */
260 template<typename _Tp, typename _Compare>
261 class _LoserTree</* __stable == */false, _Tp, _Compare>
262 : public _LoserTreeBase<_Tp, _Compare>
263 {
264 typedef _LoserTreeBase<_Tp, _Compare> _Base;
265 using _Base::_M_log_k;
266 using _Base::_M_k;
267 using _Base::_M_comp;
268 using _Base::_M_losers;
269 using _Base::_M_first_insert;
270
271 public:
272 _LoserTree(unsigned int __k, _Compare __comp)
273 : _Base::_LoserTreeBase(__k, __comp)
274 { }
275
276 /**
277 * Computes the winner of the competition at position "__root".
278 *
279 * Called recursively (starting at 0) to build the initial tree.
280 *
281 * @param __root __index of the "game" to start.
282 */
283 unsigned int
284 __init_winner(unsigned int __root)
285 {
286 if (__root >= _M_k)
287 return __root;
288 else
289 {
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)))
296 {
297 // Left one is less or equal.
298 _M_losers[__root] = _M_losers[__right];
299 return __left;
300 }
301 else
302 {
303 // Right one is less.
304 _M_losers[__root] = _M_losers[__left];
305 return __right;
306 }
307 }
308 }
309
310 void
311 __init()
312 { _M_losers[0] = _M_losers[__init_winner(1)]; }
313
314 /**
315 * Delete the _M_key smallest element and insert the element __key
316 * instead.
317 *
318 * @param __key the _M_key to insert
319 * @param __sup true iff __key is an explicitly marked supremum
320 */
321 // Do not pass a const reference since __key will be used as local
322 // variable.
323 void
324 __delete_min_insert(_Tp __key, bool __sup)
325 {
326 using std::swap;
327 #if _GLIBCXX_PARALLEL_ASSERTIONS
328 // no dummy sequence can ever be at the top!
329 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
330 #endif
331
332 int __source = _M_losers[0]._M_source;
333 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
334 __pos /= 2)
335 {
336 // The smaller one gets promoted.
337 if (__sup || (!_M_losers[__pos]._M_sup
338 && _M_comp(_M_losers[__pos]._M_key, __key)))
339 {
340 // The other one is smaller.
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);
344 }
345 }
346
347 _M_losers[0]._M_sup = __sup;
348 _M_losers[0]._M_source = __source;
349 _M_losers[0]._M_key = __key;
350 }
351 };
352
353 /**
354 * @brief Base class of _Loser Tree implementation using pointers.
355 */
356 template<typename _Tp, typename _Compare>
357 class _LoserTreePointerBase
358 {
359 protected:
360 /** @brief Internal representation of _LoserTree __elements. */
361 struct _Loser
362 {
363 bool _M_sup;
364 int _M_source;
365 const _Tp* _M_keyp;
366 };
367
368 unsigned int _M_ik, _M_k, _M_offset;
369 _Loser* _M_losers;
370 _Compare _M_comp;
371
372 public:
373 _LoserTreePointerBase(unsigned int __k,
374 _Compare __comp = std::less<_Tp>())
375 : _M_comp(__comp)
376 {
377 _M_ik = __k;
378
379 // Next greater power of 2.
380 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
381 _M_offset = _M_k;
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;
385 }
386
387 ~_LoserTreePointerBase()
388 { delete[] _M_losers; }
389
390 int __get_min_source()
391 { return _M_losers[0]._M_source; }
392
393 void __insert_start(const _Tp& __key, int __source, bool __sup)
394 {
395 unsigned int __pos = _M_k + __source;
396
397 _M_losers[__pos]._M_sup = __sup;
398 _M_losers[__pos]._M_source = __source;
399 _M_losers[__pos]._M_keyp = &__key;
400 }
401 };
402
403 /**
404 * @brief Stable _LoserTree implementation.
405 *
406 * The unstable variant is implemented using partial instantiation below.
407 */
408 template<bool __stable/* default == true */, typename _Tp, typename _Compare>
409 class _LoserTreePointer
410 : public _LoserTreePointerBase<_Tp, _Compare>
411 {
412 typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
413 using _Base::_M_k;
414 using _Base::_M_comp;
415 using _Base::_M_losers;
416
417 public:
418 _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
419 : _Base::_LoserTreePointerBase(__k, __comp)
420 { }
421
422 unsigned int
423 __init_winner(unsigned int __root)
424 {
425 if (__root >= _M_k)
426 return __root;
427 else
428 {
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)))
435 {
436 // Left one is less or equal.
437 _M_losers[__root] = _M_losers[__right];
438 return __left;
439 }
440 else
441 {
442 // Right one is less.
443 _M_losers[__root] = _M_losers[__left];
444 return __right;
445 }
446 }
447 }
448
449 void __init()
450 { _M_losers[0] = _M_losers[__init_winner(1)]; }
451
452 void __delete_min_insert(const _Tp& __key, bool __sup)
453 {
454 #if _GLIBCXX_PARALLEL_ASSERTIONS
455 // no dummy sequence can ever be at the top!
456 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
457 #endif
458
459 const _Tp* __keyp = &__key;
460 int __source = _M_losers[0]._M_source;
461 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
462 __pos /= 2)
463 {
464 // The smaller one gets promoted, ties are broken by __source.
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))))
471 {
472 // The other one is smaller.
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);
476 }
477 }
478
479 _M_losers[0]._M_sup = __sup;
480 _M_losers[0]._M_source = __source;
481 _M_losers[0]._M_keyp = __keyp;
482 }
483 };
484
485 /**
486 * @brief Unstable _LoserTree implementation.
487 *
488 * The stable variant is above.
489 */
490 template<typename _Tp, typename _Compare>
491 class _LoserTreePointer</* __stable == */false, _Tp, _Compare>
492 : public _LoserTreePointerBase<_Tp, _Compare>
493 {
494 typedef _LoserTreePointerBase<_Tp, _Compare> _Base;
495 using _Base::_M_k;
496 using _Base::_M_comp;
497 using _Base::_M_losers;
498
499 public:
500 _LoserTreePointer(unsigned int __k, _Compare __comp = std::less<_Tp>())
501 : _Base::_LoserTreePointerBase(__k, __comp)
502 { }
503
504 unsigned int
505 __init_winner(unsigned int __root)
506 {
507 if (__root >= _M_k)
508 return __root;
509 else
510 {
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)))
517 {
518 // Left one is less or equal.
519 _M_losers[__root] = _M_losers[__right];
520 return __left;
521 }
522 else
523 {
524 // Right one is less.
525 _M_losers[__root] = _M_losers[__left];
526 return __right;
527 }
528 }
529 }
530
531 void __init()
532 { _M_losers[0] = _M_losers[__init_winner(1)]; }
533
534 void __delete_min_insert(const _Tp& __key, bool __sup)
535 {
536 #if _GLIBCXX_PARALLEL_ASSERTIONS
537 // no dummy sequence can ever be at the top!
538 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
539 #endif
540
541 const _Tp* __keyp = &__key;
542 int __source = _M_losers[0]._M_source;
543 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
544 __pos /= 2)
545 {
546 // The smaller one gets promoted.
547 if (__sup || (!_M_losers[__pos]._M_sup
548 && _M_comp(*_M_losers[__pos]._M_keyp, *__keyp)))
549 {
550 // The other one is smaller.
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);
554 }
555 }
556
557 _M_losers[0]._M_sup = __sup;
558 _M_losers[0]._M_source = __source;
559 _M_losers[0]._M_keyp = __keyp;
560 }
561 };
562
563 /** @brief Base class for unguarded _LoserTree implementation.
564 *
565 * The whole element is copied into the tree structure.
566 *
567 * No guarding is done, therefore not a single input sequence must
568 * run empty. Unused __sequence heads are marked with a sentinel which
569 * is > all elements that are to be merged.
570 *
571 * This is a very fast variant.
572 */
573 template<typename _Tp, typename _Compare>
574 class _LoserTreeUnguardedBase
575 {
576 protected:
577 struct _Loser
578 {
579 int _M_source;
580 _Tp _M_key;
581 };
582
583 unsigned int _M_ik, _M_k, _M_offset;
584 _Loser* _M_losers;
585 _Compare _M_comp;
586
587 public:
588 _LoserTreeUnguardedBase(unsigned int __k, const _Tp& __sentinel,
589 _Compare __comp = std::less<_Tp>())
590 : _M_comp(__comp)
591 {
592 _M_ik = __k;
593
594 // Next greater power of 2.
595 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
596 _M_offset = _M_k;
597 // Avoid default-constructing _M_losers[]._M_key
598 _M_losers = static_cast<_Loser*>(::operator new(2 * _M_k
599 * sizeof(_Loser)));
600
601 for (unsigned int __i = 0; __i < _M_k; ++__i)
602 {
603 ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel);
604 _M_losers[__i]._M_source = -1;
605 }
606 for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
607 {
608 ::new(&(_M_losers[__i]._M_key)) _Tp(__sentinel);
609 _M_losers[__i]._M_source = -1;
610 }
611 }
612
613 ~_LoserTreeUnguardedBase()
614 {
615 for (unsigned int __i = 0; __i < (2 * _M_k); ++__i)
616 _M_losers[__i].~_Loser();
617 ::operator delete(_M_losers);
618 }
619
620 int
621 __get_min_source()
622 {
623 #if _GLIBCXX_PARALLEL_ASSERTIONS
624 // no dummy sequence can ever be at the top!
625 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
626 #endif
627 return _M_losers[0]._M_source;
628 }
629
630 void
631 __insert_start(const _Tp& __key, int __source, bool)
632 {
633 unsigned int __pos = _M_k + __source;
634
635 ::new(&(_M_losers[__pos]._M_key)) _Tp(__key);
636 _M_losers[__pos]._M_source = __source;
637 }
638 };
639
640 /**
641 * @brief Stable implementation of unguarded _LoserTree.
642 *
643 * Unstable variant is selected below with partial specialization.
644 */
645 template<bool __stable/* default == true */, typename _Tp, typename _Compare>
646 class _LoserTreeUnguarded
647 : public _LoserTreeUnguardedBase<_Tp, _Compare>
648 {
649 typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
650 using _Base::_M_k;
651 using _Base::_M_comp;
652 using _Base::_M_losers;
653
654 public:
655 _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
656 _Compare __comp = std::less<_Tp>())
657 : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
658 { }
659
660 unsigned int
661 __init_winner(unsigned int __root)
662 {
663 if (__root >= _M_k)
664 return __root;
665 else
666 {
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))
671 {
672 // Left one is less or equal.
673 _M_losers[__root] = _M_losers[__right];
674 return __left;
675 }
676 else
677 {
678 // Right one is less.
679 _M_losers[__root] = _M_losers[__left];
680 return __right;
681 }
682 }
683 }
684
685 void
686 __init()
687 {
688 _M_losers[0] = _M_losers[__init_winner(1)];
689
690 #if _GLIBCXX_PARALLEL_ASSERTIONS
691 // no dummy sequence can ever be at the top at the beginning
692 // (0 sequences!)
693 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
694 #endif
695 }
696
697 // Do not pass a const reference since __key will be used as
698 // local variable.
699 void
700 __delete_min_insert(_Tp __key, bool)
701 {
702 using std::swap;
703 #if _GLIBCXX_PARALLEL_ASSERTIONS
704 // no dummy sequence can ever be at the top!
705 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
706 #endif
707
708 int __source = _M_losers[0]._M_source;
709 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
710 __pos /= 2)
711 {
712 // The smaller one gets promoted, ties are broken by _M_source.
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))
716 {
717 // The other one is smaller.
718 std::swap(_M_losers[__pos]._M_source, __source);
719 swap(_M_losers[__pos]._M_key, __key);
720 }
721 }
722
723 _M_losers[0]._M_source = __source;
724 _M_losers[0]._M_key = __key;
725 }
726 };
727
728 /**
729 * @brief Non-Stable implementation of unguarded _LoserTree.
730 *
731 * Stable implementation is above.
732 */
733 template<typename _Tp, typename _Compare>
734 class _LoserTreeUnguarded</* __stable == */false, _Tp, _Compare>
735 : public _LoserTreeUnguardedBase<_Tp, _Compare>
736 {
737 typedef _LoserTreeUnguardedBase<_Tp, _Compare> _Base;
738 using _Base::_M_k;
739 using _Base::_M_comp;
740 using _Base::_M_losers;
741
742 public:
743 _LoserTreeUnguarded(unsigned int __k, const _Tp& __sentinel,
744 _Compare __comp = std::less<_Tp>())
745 : _Base::_LoserTreeUnguardedBase(__k, __sentinel, __comp)
746 { }
747
748 unsigned int
749 __init_winner(unsigned int __root)
750 {
751 if (__root >= _M_k)
752 return __root;
753 else
754 {
755 unsigned int __left = __init_winner(2 * __root);
756 unsigned int __right = __init_winner(2 * __root + 1);
757
758 #if _GLIBCXX_PARALLEL_ASSERTIONS
759 // If __left one is sentinel then __right one must be, too.
760 if (_M_losers[__left]._M_source == -1)
761 _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
762 #endif
763
764 if (!_M_comp(_M_losers[__right]._M_key,
765 _M_losers[__left]._M_key))
766 {
767 // Left one is less or equal.
768 _M_losers[__root] = _M_losers[__right];
769 return __left;
770 }
771 else
772 {
773 // Right one is less.
774 _M_losers[__root] = _M_losers[__left];
775 return __right;
776 }
777 }
778 }
779
780 void
781 __init()
782 {
783 _M_losers[0] = _M_losers[__init_winner(1)];
784
785 #if _GLIBCXX_PARALLEL_ASSERTIONS
786 // no dummy sequence can ever be at the top at the beginning
787 // (0 sequences!)
788 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
789 #endif
790 }
791
792 // Do not pass a const reference since __key will be used as
793 // local variable.
794 void
795 __delete_min_insert(_Tp __key, bool)
796 {
797 using std::swap;
798 #if _GLIBCXX_PARALLEL_ASSERTIONS
799 // no dummy sequence can ever be at the top!
800 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
801 #endif
802
803 int __source = _M_losers[0]._M_source;
804 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
805 __pos /= 2)
806 {
807 // The smaller one gets promoted.
808 if (_M_comp(_M_losers[__pos]._M_key, __key))
809 {
810 // The other one is smaller.
811 std::swap(_M_losers[__pos]._M_source, __source);
812 swap(_M_losers[__pos]._M_key, __key);
813 }
814 }
815
816 _M_losers[0]._M_source = __source;
817 _M_losers[0]._M_key = __key;
818 }
819 };
820
821 /** @brief Unguarded loser tree, keeping only pointers to the
822 * elements in the tree structure.
823 *
824 * No guarding is done, therefore not a single input sequence must
825 * run empty. This is a very fast variant.
826 */
827 template<typename _Tp, typename _Compare>
828 class _LoserTreePointerUnguardedBase
829 {
830 protected:
831 struct _Loser
832 {
833 int _M_source;
834 const _Tp* _M_keyp;
835 };
836
837 unsigned int _M_ik, _M_k, _M_offset;
838 _Loser* _M_losers;
839 _Compare _M_comp;
840
841 public:
842
843 _LoserTreePointerUnguardedBase(unsigned int __k, const _Tp& __sentinel,
844 _Compare __comp = std::less<_Tp>())
845 : _M_comp(__comp)
846 {
847 _M_ik = __k;
848
849 // Next greater power of 2.
850 _M_k = 1 << (__rd_log2(_M_ik - 1) + 1);
851 _M_offset = _M_k;
852 // Avoid default-constructing _M_losers[]._M_key
853 _M_losers = new _Loser[2 * _M_k];
854
855 for (unsigned int __i = _M_k + _M_ik - 1; __i < (2 * _M_k); ++__i)
856 {
857 _M_losers[__i]._M_keyp = &__sentinel;
858 _M_losers[__i]._M_source = -1;
859 }
860 }
861
862 ~_LoserTreePointerUnguardedBase()
863 { delete[] _M_losers; }
864
865 int
866 __get_min_source()
867 {
868 #if _GLIBCXX_PARALLEL_ASSERTIONS
869 // no dummy sequence can ever be at the top!
870 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
871 #endif
872 return _M_losers[0]._M_source;
873 }
874
875 void
876 __insert_start(const _Tp& __key, int __source, bool)
877 {
878 unsigned int __pos = _M_k + __source;
879
880 _M_losers[__pos]._M_keyp = &__key;
881 _M_losers[__pos]._M_source = __source;
882 }
883 };
884
885 /**
886 * @brief Stable unguarded _LoserTree variant storing pointers.
887 *
888 * Unstable variant is implemented below using partial specialization.
889 */
890 template<bool __stable/* default == true */, typename _Tp, typename _Compare>
891 class _LoserTreePointerUnguarded
892 : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
893 {
894 typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
895 using _Base::_M_k;
896 using _Base::_M_comp;
897 using _Base::_M_losers;
898
899 public:
900 _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
901 _Compare __comp = std::less<_Tp>())
902 : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
903 { }
904
905 unsigned int
906 __init_winner(unsigned int __root)
907 {
908 if (__root >= _M_k)
909 return __root;
910 else
911 {
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))
916 {
917 // Left one is less or equal.
918 _M_losers[__root] = _M_losers[__right];
919 return __left;
920 }
921 else
922 {
923 // Right one is less.
924 _M_losers[__root] = _M_losers[__left];
925 return __right;
926 }
927 }
928 }
929
930 void
931 __init()
932 {
933 _M_losers[0] = _M_losers[__init_winner(1)];
934
935 #if _GLIBCXX_PARALLEL_ASSERTIONS
936 // no dummy sequence can ever be at the top at the beginning
937 // (0 sequences!)
938 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
939 #endif
940 }
941
942 void
943 __delete_min_insert(const _Tp& __key, bool __sup)
944 {
945 #if _GLIBCXX_PARALLEL_ASSERTIONS
946 // no dummy sequence can ever be at the top!
947 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
948 #endif
949
950 const _Tp* __keyp = &__key;
951 int __source = _M_losers[0]._M_source;
952 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
953 __pos /= 2)
954 {
955 // The smaller one gets promoted, ties are broken by _M_source.
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))
959 {
960 // The other one is smaller.
961 std::swap(_M_losers[__pos]._M_source, __source);
962 std::swap(_M_losers[__pos]._M_keyp, __keyp);
963 }
964 }
965
966 _M_losers[0]._M_source = __source;
967 _M_losers[0]._M_keyp = __keyp;
968 }
969 };
970
971 /**
972 * @brief Unstable unguarded _LoserTree variant storing pointers.
973 *
974 * Stable variant is above.
975 */
976 template<typename _Tp, typename _Compare>
977 class _LoserTreePointerUnguarded</* __stable == */false, _Tp, _Compare>
978 : public _LoserTreePointerUnguardedBase<_Tp, _Compare>
979 {
980 typedef _LoserTreePointerUnguardedBase<_Tp, _Compare> _Base;
981 using _Base::_M_k;
982 using _Base::_M_comp;
983 using _Base::_M_losers;
984
985 public:
986 _LoserTreePointerUnguarded(unsigned int __k, const _Tp& __sentinel,
987 _Compare __comp = std::less<_Tp>())
988 : _Base::_LoserTreePointerUnguardedBase(__k, __sentinel, __comp)
989 { }
990
991 unsigned int
992 __init_winner(unsigned int __root)
993 {
994 if (__root >= _M_k)
995 return __root;
996 else
997 {
998 unsigned int __left = __init_winner(2 * __root);
999 unsigned int __right = __init_winner(2 * __root + 1);
1000
1001 #if _GLIBCXX_PARALLEL_ASSERTIONS
1002 // If __left one is sentinel then __right one must be, too.
1003 if (_M_losers[__left]._M_source == -1)
1004 _GLIBCXX_PARALLEL_ASSERT(_M_losers[__right]._M_source == -1);
1005 #endif
1006
1007 if (!_M_comp(*_M_losers[__right]._M_keyp,
1008 *_M_losers[__left]._M_keyp))
1009 {
1010 // Left one is less or equal.
1011 _M_losers[__root] = _M_losers[__right];
1012 return __left;
1013 }
1014 else
1015 {
1016 // Right one is less.
1017 _M_losers[__root] = _M_losers[__left];
1018 return __right;
1019 }
1020 }
1021 }
1022
1023 void
1024 __init()
1025 {
1026 _M_losers[0] = _M_losers[__init_winner(1)];
1027
1028 #if _GLIBCXX_PARALLEL_ASSERTIONS
1029 // no dummy sequence can ever be at the top at the beginning
1030 // (0 sequences!)
1031 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1032 #endif
1033 }
1034
1035 void
1036 __delete_min_insert(const _Tp& __key, bool __sup)
1037 {
1038 #if _GLIBCXX_PARALLEL_ASSERTIONS
1039 // no dummy sequence can ever be at the top!
1040 _GLIBCXX_PARALLEL_ASSERT(_M_losers[0]._M_source != -1);
1041 #endif
1042
1043 const _Tp* __keyp = &__key;
1044 int __source = _M_losers[0]._M_source;
1045 for (unsigned int __pos = (_M_k + __source) / 2; __pos > 0;
1046 __pos /= 2)
1047 {
1048 // The smaller one gets promoted.
1049 if (_M_comp(*(_M_losers[__pos]._M_keyp), *__keyp))
1050 {
1051 // The other one is smaller.
1052 std::swap(_M_losers[__pos]._M_source, __source);
1053 std::swap(_M_losers[__pos]._M_keyp, __keyp);
1054 }
1055 }
1056
1057 _M_losers[0]._M_source = __source;
1058 _M_losers[0]._M_keyp = __keyp;
1059 }
1060 };
1061 } // namespace __gnu_parallel
1062
1063 #endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */