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 */