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
37 #include <bits/stl_algobase.h>
38 #include <parallel/features.h>
39 #include <parallel/base.h>
41 namespace __gnu_parallel
45 * @brief Guarded loser/tournament tree.
47 * The smallest element is at the top.
49 * Guarding is done explicitly through one flag sup per element,
50 * inf is not needed due to a better initialization routine. This
51 * is a well-performing variant.
53 * @param T the element type
54 * @param Comparator the comparator to use, defaults to std::less<T>
56 template<typename T
, typename Comparator
>
60 /** @brief Internal representation of a LoserTree element. */
63 /** @brief flag, true iff this is a "maximum" sentinel. */
65 /** @brief index of the source sequence. */
67 /** @brief key of the element in the LoserTree. */
71 unsigned int ik
, k
, offset
;
74 unsigned int _M_log_k
;
76 /** @brief LoserTree elements. */
79 /** @brief Comparator to use. */
83 * @brief State flag that determines whether the LoserTree is empty.
85 * Only used for building the LoserTree.
91 * @brief The constructor.
93 * @param _k The number of sequences to merge.
94 * @param _comp The comparator to use.
96 LoserTreeBase(unsigned int _k
, Comparator _comp
)
101 // Compute log_2{k} for the Loser Tree
102 _M_log_k
= __log2(ik
- 1) + 1;
104 // Next greater power of 2.
108 // Avoid default-constructing losers[].key
109 losers
= static_cast<Loser
*>(::operator new(2 * k
* sizeof(Loser
)));
110 for (unsigned int i
= ik
- 1; i
< k
; ++i
)
111 losers
[i
+ k
].sup
= true;
117 * @brief The destructor.
120 { ::operator delete(losers
); }
123 * @brief Initializes the sequence "source" with the element "key".
125 * @param key the element to insert
126 * @param source index of the source sequence
127 * @param sup flag that determines whether the value to insert is an
131 insert_start(const T
& key
, int source
, bool sup
)
133 unsigned int pos
= k
+ source
;
137 // Construct all keys, so we can easily deconstruct them.
138 for (unsigned int i
= 0; i
< (2 * k
); ++i
)
139 new(&(losers
[i
].key
)) T(key
);
140 first_insert
= false;
143 new(&(losers
[pos
].key
)) T(key
);
145 losers
[pos
].sup
= sup
;
146 losers
[pos
].source
= source
;
150 * @return the index of the sequence with the smallest element.
153 { return losers
[0].source
; }
157 * @brief Stable LoserTree variant.
159 * Provides the stable implementations of insert_start, init_winner,
160 * init and delete_min_insert.
162 * Unstable variant is done using partial specialisation below.
164 template<bool stable
/* default == true */, typename T
, typename Comparator
>
165 class LoserTree
: public LoserTreeBase
<T
, Comparator
>
167 typedef LoserTreeBase
<T
, Comparator
> Base
;
170 using Base::first_insert
;
173 LoserTree(unsigned int _k
, Comparator _comp
)
174 : Base::LoserTreeBase(_k
, _comp
)
178 init_winner(unsigned int root
)
186 unsigned int left
= init_winner (2 * root
);
187 unsigned int right
= init_winner (2 * root
+ 1);
188 if (losers
[right
].sup
189 || (!losers
[left
].sup
190 && !comp(losers
[right
].key
, losers
[left
].key
)))
192 // Left one is less or equal.
193 losers
[root
] = losers
[right
];
198 // Right one is less.
199 losers
[root
] = losers
[left
];
206 { losers
[0] = 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 local variable.
215 void delete_min_insert(T key
, bool sup
)
217 #if _GLIBCXX_ASSERTIONS
218 // no dummy sequence can ever be at the top!
219 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
222 int source
= losers
[0].source
;
223 for (unsigned int pos
= (k
+ source
) / 2; pos
> 0; pos
/= 2)
225 // The smaller one gets promoted, ties are broken by source.
226 if ((sup
&& (!losers
[pos
].sup
|| losers
[pos
].source
< source
))
227 || (!sup
&& !losers
[pos
].sup
228 && ((comp(losers
[pos
].key
, key
))
229 || (!comp(key
, losers
[pos
].key
)
230 && losers
[pos
].source
< source
))))
232 // The other one is smaller.
233 std::swap(losers
[pos
].sup
, sup
);
234 std::swap(losers
[pos
].source
, source
);
235 std::swap(losers
[pos
].key
, key
);
240 losers
[0].source
= source
;
246 * @brief Unstable LoserTree variant.
248 * Stability (non-stable here) is selected with partial specialization.
250 template<typename T
, typename Comparator
>
251 class LoserTree
</* stable == */false, T
, Comparator
> :
252 public LoserTreeBase
<T
, Comparator
>
254 typedef LoserTreeBase
<T
, Comparator
> Base
;
255 using Base::_M_log_k
;
258 using Base::first_insert
;
261 LoserTree(unsigned int _k
, Comparator _comp
)
262 : Base::LoserTreeBase(_k
, _comp
)
266 * Computes the winner of the competition at position "root".
268 * Called recursively (starting at 0) to build the initial tree.
270 * @param root index of the "game" to start.
273 init_winner (unsigned int root
)
281 unsigned int left
= init_winner (2 * root
);
282 unsigned int right
= init_winner (2 * root
+ 1);
283 if (losers
[right
].sup
||
285 && !comp(losers
[right
].key
, losers
[left
].key
)))
287 // Left one is less or equal.
288 losers
[root
] = losers
[right
];
293 // Right one is less.
294 losers
[root
] = losers
[left
];
302 { losers
[0] = losers
[init_winner(1)]; }
305 * Delete the key smallest element and insert the element key instead.
307 * @param key the key to insert
308 * @param sup true iff key is an explicitly marked supremum
310 // Do not pass a const reference since key will be used as local variable.
312 delete_min_insert(T key
, bool sup
)
314 #if _GLIBCXX_ASSERTIONS
315 // no dummy sequence can ever be at the top!
316 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
319 int source
= losers
[0].source
;
320 for (unsigned int pos
= (k
+ source
) / 2; pos
> 0; pos
/= 2)
322 // The smaller one gets promoted.
323 if (sup
|| (!losers
[pos
].sup
&& comp(losers
[pos
].key
, key
)))
325 // The other one is smaller.
326 std::swap(losers
[pos
].sup
, sup
);
327 std::swap(losers
[pos
].source
, source
);
328 std::swap(losers
[pos
].key
, key
);
333 losers
[0].source
= source
;
340 * @brief Base class of Loser Tree implementation using pointers.
342 template<typename T
, typename Comparator
>
343 class LoserTreePointerBase
346 /** @brief Internal representation of LoserTree elements. */
354 unsigned int ik
, k
, offset
;
359 LoserTreePointerBase(unsigned int _k
, Comparator _comp
= std::less
<T
>())
364 // Next greater power of 2.
365 k
= 1 << (__log2(ik
- 1) + 1);
367 losers
= new Loser
[k
* 2];
368 for (unsigned int i
= ik
- 1; i
< k
; i
++)
369 losers
[i
+ k
].sup
= true;
372 ~LoserTreePointerBase()
373 { ::operator delete[](losers
); }
376 { return losers
[0].source
; }
378 void insert_start(const T
& key
, int source
, bool sup
)
380 unsigned int pos
= k
+ source
;
382 losers
[pos
].sup
= sup
;
383 losers
[pos
].source
= source
;
384 losers
[pos
].keyp
= &key
;
389 * @brief Stable LoserTree implementation.
391 * The unstable variant is implemented using partial instantiation below.
393 template<bool stable
/* default == true */, typename T
, typename Comparator
>
394 class LoserTreePointer
: public LoserTreePointerBase
<T
, Comparator
>
396 typedef LoserTreePointerBase
<T
, Comparator
> Base
;
401 LoserTreePointer(unsigned int _k
, Comparator _comp
= std::less
<T
>())
402 : Base::LoserTreePointerBase(_k
, _comp
)
406 init_winner(unsigned int root
)
414 unsigned int left
= init_winner (2 * root
);
415 unsigned int right
= init_winner (2 * root
+ 1);
416 if (losers
[right
].sup
417 || (!losers
[left
].sup
&& !comp(*losers
[right
].keyp
,
418 *losers
[left
].keyp
)))
420 // Left one is less or equal.
421 losers
[root
] = losers
[right
];
426 // Right one is less.
427 losers
[root
] = losers
[left
];
434 { losers
[0] = losers
[init_winner(1)]; }
436 void delete_min_insert(const T
& key
, bool sup
)
438 #if _GLIBCXX_ASSERTIONS
439 // no dummy sequence can ever be at the top!
440 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
443 const T
* keyp
= &key
;
444 int source
= losers
[0].source
;
445 for (unsigned int pos
= (k
+ source
) / 2; pos
> 0; pos
/= 2)
447 // The smaller one gets promoted, ties are broken by source.
448 if ((sup
&& (!losers
[pos
].sup
|| losers
[pos
].source
< source
)) ||
449 (!sup
&& !losers
[pos
].sup
&&
450 ((comp(*losers
[pos
].keyp
, *keyp
)) ||
451 (!comp(*keyp
, *losers
[pos
].keyp
)
452 && losers
[pos
].source
< source
))))
454 // The other one is smaller.
455 std::swap(losers
[pos
].sup
, sup
);
456 std::swap(losers
[pos
].source
, source
);
457 std::swap(losers
[pos
].keyp
, keyp
);
462 losers
[0].source
= source
;
463 losers
[0].keyp
= keyp
;
468 * @brief Unstable LoserTree implementation.
470 * The stable variant is above.
472 template<typename T
, typename Comparator
>
473 class LoserTreePointer
</* stable == */false, T
, Comparator
> :
474 public LoserTreePointerBase
<T
, Comparator
>
476 typedef LoserTreePointerBase
<T
, Comparator
> Base
;
481 LoserTreePointer(unsigned int _k
, Comparator _comp
= std::less
<T
>())
482 : Base::LoserTreePointerBase(_k
, _comp
)
486 init_winner(unsigned int root
)
494 unsigned int left
= init_winner (2 * root
);
495 unsigned int right
= init_winner (2 * root
+ 1);
496 if (losers
[right
].sup
497 || (!losers
[left
].sup
498 && !comp(*losers
[right
].keyp
, *losers
[left
].keyp
)))
500 // Left one is less or equal.
501 losers
[root
] = losers
[right
];
506 // Right one is less.
507 losers
[root
] = losers
[left
];
514 { losers
[0] = losers
[init_winner(1)]; }
516 void delete_min_insert(const T
& key
, bool sup
)
518 #if _GLIBCXX_ASSERTIONS
519 // no dummy sequence can ever be at the top!
520 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
523 const T
* keyp
= &key
;
524 int source
= losers
[0].source
;
525 for (unsigned int pos
= (k
+ source
) / 2; pos
> 0; pos
/= 2)
527 // The smaller one gets promoted.
528 if (sup
|| (!losers
[pos
].sup
&& comp(*losers
[pos
].keyp
, *keyp
)))
530 // The other one is smaller.
531 std::swap(losers
[pos
].sup
, sup
);
532 std::swap(losers
[pos
].source
, source
);
533 std::swap(losers
[pos
].keyp
, keyp
);
538 losers
[0].source
= source
;
539 losers
[0].keyp
= keyp
;
543 /** @brief Base class for unguarded LoserTree implementation.
545 * The whole element is copied into the tree structure.
547 * No guarding is done, therefore not a single input sequence must
548 * run empty. Unused sequence heads are marked with a sentinel which
549 * is > all elements that are to be merged.
551 * This is a very fast variant.
553 template<typename T
, typename Comparator
>
554 class LoserTreeUnguardedBase
563 unsigned int ik
, k
, offset
;
569 LoserTreeUnguardedBase(unsigned int _k
, const T _sentinel
,
570 Comparator _comp
= std::less
<T
>())
575 // Next greater power of 2.
576 k
= 1 << (__log2(ik
- 1) + 1);
578 // Avoid default-constructing losers[].key
579 losers
= static_cast<Loser
*>(::operator new(2 * k
* sizeof(Loser
)));
581 for (unsigned int i
= k
+ ik
- 1; i
< (2 * k
); ++i
)
583 losers
[i
].key
= _sentinel
;
584 losers
[i
].source
= -1;
588 inline ~LoserTreeUnguardedBase()
589 { ::operator delete(losers
); }
594 #if _GLIBCXX_ASSERTIONS
595 // no dummy sequence can ever be at the top!
596 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
598 return losers
[0].source
;
602 insert_start(const T
& key
, int source
, bool)
604 unsigned int pos
= k
+ source
;
606 new(&(losers
[pos
].key
)) T(key
);
607 losers
[pos
].source
= source
;
612 * @brief Stable implementation of unguarded LoserTree.
614 * Unstable variant is selected below with partial specialization.
616 template<bool stable
/* default == true */, typename T
, typename Comparator
>
617 class LoserTreeUnguarded
: public LoserTreeUnguardedBase
<T
, Comparator
>
619 typedef LoserTreeUnguardedBase
<T
, Comparator
> Base
;
624 LoserTreeUnguarded(unsigned int _k
, const T _sentinel
,
625 Comparator _comp
= std::less
<T
>())
626 : Base::LoserTreeUnguardedBase(_k
, _sentinel
, _comp
)
630 init_winner(unsigned int root
)
638 unsigned int left
= init_winner (2 * root
);
639 unsigned int right
= init_winner (2 * root
+ 1);
640 if (!comp(losers
[right
].key
, losers
[left
].key
))
642 // Left one is less or equal.
643 losers
[root
] = losers
[right
];
648 // Right one is less.
649 losers
[root
] = losers
[left
];
658 losers
[0] = losers
[init_winner(1)];
660 #if _GLIBCXX_ASSERTIONS
661 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
662 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
666 // Do not pass a const reference since key will be used as local variable.
668 delete_min_insert(T key
, bool)
670 #if _GLIBCXX_ASSERTIONS
671 // no dummy sequence can ever be at the top!
672 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
675 int source
= losers
[0].source
;
676 for (unsigned int pos
= (k
+ source
) / 2; pos
> 0; pos
/= 2)
678 // The smaller one gets promoted, ties are broken by source.
679 if (comp(losers
[pos
].key
, key
)
680 || (!comp(key
, losers
[pos
].key
) && losers
[pos
].source
< source
))
682 // The other one is smaller.
683 std::swap(losers
[pos
].source
, source
);
684 std::swap(losers
[pos
].key
, key
);
688 losers
[0].source
= source
;
694 * @brief Non-Stable implementation of unguarded LoserTree.
696 * Stable implementation is above.
698 template<typename T
, typename Comparator
>
699 class LoserTreeUnguarded
</* stable == */false, T
, Comparator
> :
700 public LoserTreeUnguardedBase
<T
, Comparator
>
702 typedef LoserTreeUnguardedBase
<T
, Comparator
> Base
;
707 LoserTreeUnguarded(unsigned int _k
, const T _sentinel
,
708 Comparator _comp
= std::less
<T
>())
709 : Base::LoserTreeUnguardedBase(_k
, _sentinel
, _comp
)
713 init_winner (unsigned int root
)
721 unsigned int left
= init_winner (2 * root
);
722 unsigned int right
= init_winner (2 * root
+ 1);
724 #if _GLIBCXX_ASSERTIONS
725 // If left one is sentinel then right one must be, too.
726 if (losers
[left
].source
== -1)
727 _GLIBCXX_PARALLEL_ASSERT(losers
[right
].source
== -1);
730 if (!comp(losers
[right
].key
, losers
[left
].key
))
732 // Left one is less or equal.
733 losers
[root
] = losers
[right
];
738 // Right one is less.
739 losers
[root
] = losers
[left
];
748 losers
[0] = losers
[init_winner(1)];
750 #if _GLIBCXX_ASSERTIONS
751 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
752 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
756 // Do not pass a const reference since key will be used as local variable.
758 delete_min_insert(T key
, bool)
760 #if _GLIBCXX_ASSERTIONS
761 // no dummy sequence can ever be at the top!
762 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
765 int source
= losers
[0].source
;
766 for (unsigned int pos
= (k
+ source
) / 2; pos
> 0; pos
/= 2)
768 // The smaller one gets promoted.
769 if (comp(losers
[pos
].key
, key
))
771 // The other one is smaller.
772 std::swap(losers
[pos
].source
, source
);
773 std::swap(losers
[pos
].key
, key
);
777 losers
[0].source
= source
;
782 /** @brief Unguarded loser tree, keeping only pointers to the
783 * elements in the tree structure.
785 * No guarding is done, therefore not a single input sequence must
786 * run empty. This is a very fast variant.
788 template<typename T
, typename Comparator
>
789 class LoserTreePointerUnguardedBase
798 unsigned int ik
, k
, offset
;
805 LoserTreePointerUnguardedBase(unsigned int _k
, const T
& _sentinel
,
806 Comparator _comp
= std::less
<T
>())
811 // Next greater power of 2.
812 k
= 1 << (__log2(ik
- 1) + 1);
814 // Avoid default-constructing losers[].key
815 losers
= new Loser
[2 * k
];
817 for (unsigned int i
= k
+ ik
- 1; i
< (2 * k
); ++i
)
819 losers
[i
].keyp
= &_sentinel
;
820 losers
[i
].source
= -1;
824 inline ~LoserTreePointerUnguardedBase()
830 #if _GLIBCXX_ASSERTIONS
831 // no dummy sequence can ever be at the top!
832 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
834 return losers
[0].source
;
838 insert_start(const T
& key
, int source
, bool)
840 unsigned int pos
= k
+ source
;
842 losers
[pos
].keyp
= &key
;
843 losers
[pos
].source
= source
;
848 * @brief Stable unguarded LoserTree variant storing pointers.
850 * Unstable variant is implemented below using partial specialization.
852 template<bool stable
/* default == true */, typename T
, typename Comparator
>
853 class LoserTreePointerUnguarded
:
854 public LoserTreePointerUnguardedBase
<T
, Comparator
>
856 typedef LoserTreePointerUnguardedBase
<T
, Comparator
> Base
;
861 LoserTreePointerUnguarded(unsigned int _k
, const T
& _sentinel
,
862 Comparator _comp
= std::less
<T
>())
863 : Base::LoserTreePointerUnguardedBase(_k
, _sentinel
, _comp
)
867 init_winner(unsigned int root
)
875 unsigned int left
= init_winner (2 * root
);
876 unsigned int right
= init_winner (2 * root
+ 1);
877 if (!comp(*losers
[right
].keyp
, *losers
[left
].keyp
))
879 // Left one is less or equal.
880 losers
[root
] = losers
[right
];
885 // Right one is less.
886 losers
[root
] = losers
[left
];
895 losers
[0] = losers
[init_winner(1)];
897 #if _GLIBCXX_ASSERTIONS
898 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
899 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
904 delete_min_insert(const T
& key
, bool sup
)
906 #if _GLIBCXX_ASSERTIONS
907 // no dummy sequence can ever be at the top!
908 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
911 const T
* keyp
= &key
;
912 int source
= losers
[0].source
;
913 for (unsigned int pos
= (k
+ source
) / 2; pos
> 0; pos
/= 2)
915 // The smaller one gets promoted, ties are broken by source.
916 if (comp(*losers
[pos
].keyp
, *keyp
)
917 || (!comp(*keyp
, *losers
[pos
].keyp
) && losers
[pos
].source
< source
))
919 // The other one is smaller.
920 std::swap(losers
[pos
].source
, source
);
921 std::swap(losers
[pos
].keyp
, keyp
);
925 losers
[0].source
= source
;
926 losers
[0].keyp
= keyp
;
931 * @brief Unstable unguarded LoserTree variant storing pointers.
933 * Stable variant is above.
935 template<typename T
, typename Comparator
>
936 class LoserTreePointerUnguarded
</* stable == */false, T
, Comparator
> :
937 public LoserTreePointerUnguardedBase
<T
, Comparator
>
939 typedef LoserTreePointerUnguardedBase
<T
, Comparator
> Base
;
944 LoserTreePointerUnguarded(unsigned int _k
, const T
& _sentinel
,
945 Comparator _comp
= std::less
<T
>())
946 : Base::LoserTreePointerUnguardedBase(_k
, _sentinel
, _comp
)
950 init_winner(unsigned int root
)
958 unsigned int left
= init_winner (2 * root
);
959 unsigned int right
= init_winner (2 * root
+ 1);
961 #if _GLIBCXX_ASSERTIONS
962 // If left one is sentinel then right one must be, too.
963 if (losers
[left
].source
== -1)
964 _GLIBCXX_PARALLEL_ASSERT(losers
[right
].source
== -1);
967 if (!comp(*losers
[right
].keyp
, *losers
[left
].keyp
))
969 // Left one is less or equal.
970 losers
[root
] = losers
[right
];
975 // Right one is less.
976 losers
[root
] = losers
[left
];
985 losers
[0] = losers
[init_winner(1)];
987 #if _GLIBCXX_ASSERTIONS
988 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
989 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
994 delete_min_insert(const T
& key
, bool sup
)
996 #if _GLIBCXX_ASSERTIONS
997 // no dummy sequence can ever be at the top!
998 _GLIBCXX_PARALLEL_ASSERT(losers
[0].source
!= -1);
1001 const T
* keyp
= &key
;
1002 int source
= losers
[0].source
;
1003 for (unsigned int pos
= (k
+ source
) / 2; pos
> 0; pos
/= 2)
1005 // The smaller one gets promoted.
1006 if (comp(*(losers
[pos
].keyp
), *keyp
))
1008 // The other one is smaller.
1009 std::swap(losers
[pos
].source
, source
);
1010 std::swap(losers
[pos
].keyp
, keyp
);
1014 losers
[0].source
= source
;
1015 losers
[0].keyp
= keyp
;
1019 } // namespace __gnu_parallel
1021 #endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */