3 // Copyright (C) 2007 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 2, 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 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 /** @file parallel/losertree.h
32 * @brief Many generic loser tree variants.
33 * This file is a GNU parallel extension to the Standard C++ Library.
36 // Written by Johannes Singler.
38 #ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
39 #define _GLIBCXX_PARALLEL_LOSERTREE_H 1
43 #include <bits/stl_algobase.h>
44 #include <parallel/features.h>
45 #include <parallel/base.h>
47 namespace __gnu_parallel
50 #if _GLIBCXX_LOSER_TREE_EXPLICIT
52 /** @brief Guarded loser tree, copying the whole element into the
55 * Guarding is done explicitly through two flags per element, inf
56 * and sup This is a quite slow variant.
58 template<typename T, typename Comparator = std::less<T> >
59 class LoserTreeExplicit
64 // The relevant element.
67 // Is this an infimum or supremum element?
70 // Number of the sequence the element comes from.
74 unsigned int size, offset;
80 LoserTreeExplicit(unsigned int _size, Comparator _comp = std::less<T>())
85 losers = new Loser[size];
86 for (unsigned int l = 0; l < size; l++)
88 //losers[l].key = ... stays unset
90 losers[l].sup = false;
91 //losers[l].source = -1; //sentinel
95 inline ~LoserTreeExplicit()
100 { return losers[0].source; }
103 insert_start(T key, int source, bool sup)
106 for (unsigned int pos = (offset + source) / 2; pos > 0; pos /= 2)
108 if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup
109 && comp(losers[pos].key, key)) || losers[pos].inf || sup)
111 // The other one is smaller.
112 std::swap(losers[pos].key, key);
113 std::swap(losers[pos].inf, inf);
114 std::swap(losers[pos].sup, sup);
115 std::swap(losers[pos].source, source);
122 losers[0].source = source;
129 delete_min_insert(T key, bool sup)
132 int source = losers[0].source;
133 for (unsigned int pos = (offset + source) / 2; pos > 0; pos /= 2)
135 // The smaller one gets promoted.
136 if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup
137 && comp(losers[pos].key, key))
138 || losers[pos].inf || sup)
140 // The other one is smaller.
141 std::swap(losers[pos].key, key);
142 std::swap(losers[pos].inf, inf);
143 std::swap(losers[pos].sup, sup);
144 std::swap(losers[pos].source, source);
151 losers[0].source = source;
155 insert_start_stable(T key, int source, bool sup)
158 for (unsigned int pos = (offset + source) / 2; pos > 0; pos /= 2)
160 if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup &&
161 ((comp(losers[pos].key, key)) ||
162 (!comp(key, losers[pos].key) && losers[pos].source < source)))
163 || losers[pos].inf || sup)
166 std::swap(losers[pos].key, key);
167 std::swap(losers[pos].inf, inf);
168 std::swap(losers[pos].sup, sup);
169 std::swap(losers[pos].source, source);
176 losers[0].source = source;
183 delete_min_insert_stable(T key, bool sup)
186 int source = losers[0].source;
187 for (unsigned int pos = (offset + source) / 2; pos > 0; pos /= 2)
189 if ((!inf && !losers[pos].inf && !sup && !losers[pos].sup
190 && ((comp(losers[pos].key, key)) ||
191 (!comp(key, losers[pos].key) && losers[pos].source < source)))
192 || losers[pos].inf || sup)
194 std::swap(losers[pos].key, key);
195 std::swap(losers[pos].inf, inf);
196 std::swap(losers[pos].sup, sup);
197 std::swap(losers[pos].source, source);
204 losers[0].source = source;
210 #if _GLIBCXX_LOSER_TREE
212 /** @brief Guarded loser tree, either copying the whole element into
213 * the tree structure, or looking up the element via the index.
215 * Guarding is done explicitly through one flag sup per element,
216 * inf is not needed due to a better initialization routine. This
217 * is a well-performing variant.
219 template<typename T, typename Comparator = std::less<T> >
230 unsigned int ik, k, offset;
236 inline LoserTree(unsigned int _k, Comparator _comp = std::less<T>())
241 // Next greater power of 2.
242 k = 1 << (log2(ik - 1) + 1);
244 // Avoid default-constructing losers[].key
245 losers = static_cast<Loser*>(::operator new(2 * k * sizeof(Loser)));
246 for (unsigned int i = ik - 1; i < k; ++i)
247 losers[i + k].sup = true;
257 { return losers[0].source; }
260 insert_start(const T& key, int source, bool sup)
262 unsigned int pos = k + source;
266 // Construct all keys, so we can easily deconstruct them.
267 for (unsigned int i = 0; i < (2 * k); ++i)
268 new(&(losers[i].key)) T(key);
269 first_insert = false;
272 new(&(losers[pos].key)) T(key);
274 losers[pos].sup = sup;
275 losers[pos].source = source;
279 init_winner (unsigned int root)
287 unsigned int left = init_winner (2 * root);
288 unsigned int right = init_winner (2 * root + 1);
289 if (losers[right].sup ||
291 && !comp(losers[right].key, losers[left].key)))
293 // Left one is less or equal.
294 losers[root] = losers[right];
299 // Right one is less.
300 losers[root] = losers[left];
308 { losers[0] = losers[init_winner(1)]; }
310 // Do not pass const reference since key will be used as local variable.
312 delete_min_insert(T key, bool sup)
314 int source = losers[0].source;
315 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
317 // The smaller one gets promoted.
318 if (sup || (!losers[pos].sup && comp(losers[pos].key, key)))
320 // The other one is smaller.
321 std::swap(losers[pos].sup, sup);
322 std::swap(losers[pos].source, source);
323 std::swap(losers[pos].key, key);
328 losers[0].source = source;
333 insert_start_stable(const T& key, int source, bool sup)
334 { return insert_start(key, source, sup); }
337 init_winner_stable (unsigned int root)
345 unsigned int left = init_winner (2 * root);
346 unsigned int right = init_winner (2 * root + 1);
347 if (losers[right].sup
348 || (!losers[left].sup
349 && !comp(losers[right].key, losers[left].key)))
351 // Left one is less or equal.
352 losers[root] = losers[right];
357 // Right one is less.
358 losers[root] = losers[left];
366 { losers[0] = losers[init_winner_stable(1)]; }
368 // Do not pass const reference since key will be used as local variable.
370 delete_min_insert_stable(T key, bool sup)
372 int source = losers[0].source;
373 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
375 // The smaller one gets promoted, ties are broken by source.
376 if ( (sup && (!losers[pos].sup || losers[pos].source < source))
377 || (!sup && !losers[pos].sup
378 && ((comp(losers[pos].key, key))
379 || (!comp(key, losers[pos].key)
380 && losers[pos].source < source))))
382 // The other one is smaller.
383 std::swap(losers[pos].sup, sup);
384 std::swap(losers[pos].source, source);
385 std::swap(losers[pos].key, key);
390 losers[0].source = source;
397 #if _GLIBCXX_LOSER_TREE_REFERENCE
399 /** @brief Guarded loser tree, either copying the whole element into
400 * the tree structure, or looking up the element via the index.
402 * Guarding is done explicitly through one flag sup per element,
403 * inf is not needed due to a better initialization routine. This
404 * is a well-performing variant.
406 template<typename T, typename Comparator = std::less<T> >
407 class LoserTreeReference
411 #define KEY(i) losers[i].key
412 #define KEY_SOURCE(i) key
414 #define KEY(i) keys[losers[i].source]
415 #define KEY_SOURCE(i) keys[i]
427 unsigned int ik, k, offset;
436 LoserTreeReference(unsigned int _k, Comparator _comp = std::less<T>())
441 // Next greater power of 2.
442 k = 1 << (log2(ik - 1) + 1);
444 losers = new Loser[k * 2];
448 for (unsigned int i = ik - 1; i < k; i++)
449 losers[i + k].sup = true;
452 inline ~LoserTreeReference()
462 { return losers[0].source; }
465 insert_start(T key, int source, bool sup)
467 unsigned int pos = k + source;
469 losers[pos].sup = sup;
470 losers[pos].source = source;
475 init_winner(unsigned int root)
483 unsigned int left = init_winner (2 * root);
484 unsigned int right = init_winner (2 * root + 1);
485 if ( losers[right].sup ||
486 (!losers[left].sup && !comp(KEY(right), KEY(left))))
488 // Left one is less or equal.
489 losers[root] = losers[right];
494 // Right one is less.
495 losers[root] = losers[left];
504 losers[0] = losers[init_winner(1)];
508 delete_min_insert(T key, bool sup)
510 int source = losers[0].source;
511 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
513 // The smaller one gets promoted.
514 if (sup || (!losers[pos].sup && comp(KEY(pos), KEY_SOURCE(source))))
516 // The other one is smaller.
517 std::swap(losers[pos].sup, sup);
518 std::swap(losers[pos].source, source);
520 std::swap(KEY(pos), KEY_SOURCE(source));
526 losers[0].source = source;
528 KEY(0) = KEY_SOURCE(source);
533 insert_start_stable(T key, int source, bool sup)
534 { return insert_start(key, source, sup); }
537 init_winner_stable(unsigned int root)
545 unsigned int left = init_winner (2 * root);
546 unsigned int right = init_winner (2 * root + 1);
547 if (losers[right].sup
548 || (!losers[left].sup && !comp(KEY(right), KEY(left))))
550 // Left one is less or equal.
551 losers[root] = losers[right];
556 // Right one is less.
557 losers[root] = losers[left];
565 { losers[0] = losers[init_winner_stable(1)]; }
568 delete_min_insert_stable(T key, bool sup)
570 int source = losers[0].source;
571 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
573 // The smaller one gets promoted, ties are broken by source.
574 if ( (sup && (!losers[pos].sup || losers[pos].source < source)) ||
575 (!sup && !losers[pos].sup &&
576 ((comp(KEY(pos), KEY_SOURCE(source))) ||
577 (!comp(KEY_SOURCE(source), KEY(pos))
578 && losers[pos].source < source))))
580 // The other one is smaller.
581 std::swap(losers[pos].sup, sup);
582 std::swap(losers[pos].source, source);
584 std::swap(KEY(pos), KEY_SOURCE(source));
590 losers[0].source = source;
592 KEY(0) = KEY_SOURCE(source);
601 #if _GLIBCXX_LOSER_TREE_POINTER
603 /** @brief Guarded loser tree, either copying the whole element into
604 the tree structure, or looking up the element via the index.
605 * Guarding is done explicitly through one flag sup per element,
606 * inf is not needed due to a better initialization routine.
607 * This is a well-performing variant.
609 template<typename T, typename Comparator = std::less<T> >
610 class LoserTreePointer
620 unsigned int ik, k, offset;
626 LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
631 // Next greater power of 2.
632 k = 1 << (log2(ik - 1) + 1);
634 losers = new Loser[k * 2];
635 for (unsigned int i = ik - 1; i < k; i++)
636 losers[i + k].sup = true;
639 inline ~LoserTreePointer()
644 { return losers[0].source; }
647 insert_start(const T& key, int source, bool sup)
649 unsigned int pos = k + source;
651 losers[pos].sup = sup;
652 losers[pos].source = source;
653 losers[pos].keyp = &key;
657 init_winner(unsigned int root)
665 unsigned int left = init_winner (2 * root);
666 unsigned int right = init_winner (2 * root + 1);
667 if (losers[right].sup
668 || (!losers[left].sup
669 && !comp(*losers[right].keyp, *losers[left].keyp)))
671 // Left one is less or equal.
672 losers[root] = losers[right];
677 // Right one is less.
678 losers[root] = losers[left];
686 { losers[0] = losers[init_winner(1)]; }
689 delete_min_insert(const T& key, bool sup)
691 const T* keyp = &key;
692 int source = losers[0].source;
693 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
695 // The smaller one gets promoted.
696 if (sup || (!losers[pos].sup && comp(*losers[pos].keyp, *keyp)))
698 // The other one is smaller.
699 std::swap(losers[pos].sup, sup);
700 std::swap(losers[pos].source, source);
701 std::swap(losers[pos].keyp, keyp);
706 losers[0].source = source;
707 losers[0].keyp = keyp;
711 insert_start_stable(const T& key, int source, bool sup)
712 { return insert_start(key, source, sup); }
715 init_winner_stable(unsigned int root)
723 unsigned int left = init_winner (2 * root);
724 unsigned int right = init_winner (2 * root + 1);
725 if (losers[right].sup
726 || (!losers[left].sup && !comp(*losers[right].keyp,
727 *losers[left].keyp)))
729 // Left one is less or equal.
730 losers[root] = losers[right];
735 // Right one is less.
736 losers[root] = losers[left];
744 { losers[0] = losers[init_winner_stable(1)]; }
747 delete_min_insert_stable(const T& key, bool sup)
749 const T* keyp = &key;
750 int source = losers[0].source;
751 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
753 // The smaller one gets promoted, ties are broken by source.
754 if ( (sup && (!losers[pos].sup || losers[pos].source < source)) ||
755 (!sup && !losers[pos].sup &&
756 ((comp(*losers[pos].keyp, *keyp)) ||
757 (!comp(*keyp, *losers[pos].keyp)
758 && losers[pos].source < source))))
760 // The other one is smaller.
761 std::swap(losers[pos].sup, sup);
762 std::swap(losers[pos].source, source);
763 std::swap(losers[pos].keyp, keyp);
768 losers[0].source = source;
769 losers[0].keyp = keyp;
775 #if _GLIBCXX_LOSER_TREE_UNGUARDED
777 /** @brief Unguarded loser tree, copying the whole element into the
780 * No guarding is done, therefore not a single input sequence must
781 * run empty. This is a very fast variant.
783 template<typename T, typename Comparator = std::less<T> >
784 class LoserTreeUnguarded
793 unsigned int ik, k, offset;
794 unsigned int* mapping;
799 map(unsigned int root, unsigned int begin, unsigned int end)
801 if (begin + 1 == end)
802 mapping[begin] = root;
805 // Next greater or equal power of 2.
806 unsigned int left = 1 << (log2(end - begin - 1));
807 map(root * 2, begin, begin + left);
808 map(root * 2 + 1, begin + left, end);
814 LoserTreeUnguarded(unsigned int _k, Comparator _comp = std::less<T>())
818 // Next greater or equal power of 2.
819 k = 1 << (log2(ik - 1) + 1);
821 losers = new Loser[k + ik];
822 mapping = new unsigned int[ik];
826 inline ~LoserTreeUnguarded()
834 { return losers[0].source; }
837 insert_start(const T& key, int source, bool)
839 unsigned int pos = mapping[source];
840 losers[pos].source = source;
841 losers[pos].key = key;
845 init_winner(unsigned int root, unsigned int begin, unsigned int end)
847 if (begin + 1 == end)
848 return mapping[begin];
851 // Next greater or equal power of 2.
852 unsigned int division = 1 << (log2(end - begin - 1));
853 unsigned int left = init_winner(2 * root, begin, begin + division);
855 init_winner(2 * root + 1, begin + division, end);
856 if (!comp(losers[right].key, losers[left].key))
858 // Left one is less or equal.
859 losers[root] = losers[right];
864 // Right one is less.
865 losers[root] = losers[left];
873 { losers[0] = losers[init_winner(1, 0, ik)]; }
875 // Do not pass const reference since key will be used as local variable.
877 delete_min_insert(const T& key, bool)
880 T& keyr = losers[0].key;
881 int& source = losers[0].source;
882 for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
884 // The smaller one gets promoted.
885 if (comp(losers[pos].key, keyr))
887 // The other one is smaller.
888 std::swap(losers[pos].source, source);
889 std::swap(losers[pos].key, keyr);
895 insert_start_stable(const T& key, int source, bool)
896 { return insert_start(key, source, false); }
903 delete_min_insert_stable(const T& key, bool)
906 T& keyr = losers[0].key;
907 int& source = losers[0].source;
908 for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
910 // The smaller one gets promoted, ties are broken by source.
911 if (comp(losers[pos].key, keyr)
912 || (!comp(keyr, losers[pos].key)
913 && losers[pos].source < source))
915 // The other one is smaller.
916 std::swap(losers[pos].source, source);
917 std::swap(losers[pos].key, keyr);
925 #if _GLIBCXX_LOSER_TREE_POINTER_UNGUARDED
927 /** @brief Unguarded loser tree, keeping only pointers to the
928 * elements in the tree structure.
930 * No guarding is done, therefore not a single input sequence must
931 * run empty. This is a very fast variant.
933 template<typename T, typename Comparator = std::less<T> >
934 class LoserTreePointerUnguarded
943 unsigned int ik, k, offset;
944 unsigned int* mapping;
948 void map(unsigned int root, unsigned int begin, unsigned int end)
950 if (begin + 1 == end)
951 mapping[begin] = root;
954 // Next greater or equal power of 2.
955 unsigned int left = 1 << (log2(end - begin - 1));
956 map(root * 2, begin, begin + left);
957 map(root * 2 + 1, begin + left, end);
963 LoserTreePointerUnguarded(unsigned int _k,
964 Comparator _comp = std::less<T>())
969 // Next greater power of 2.
970 k = 1 << (log2(ik - 1) + 1);
972 losers = new Loser[k + ik];
973 mapping = new unsigned int[ik];
977 inline ~LoserTreePointerUnguarded()
985 { return losers[0].source; }
988 insert_start(const T& key, int source, bool)
990 unsigned int pos = mapping[source];
991 losers[pos].source = source;
992 losers[pos].keyp = &key;
996 init_winner(unsigned int root, unsigned int begin, unsigned int end)
998 if (begin + 1 == end)
999 return mapping[begin];
1002 // Next greater or equal power of 2.
1003 unsigned int division = 1 << (log2(end - begin - 1));
1004 unsigned int left = init_winner(2 * root, begin, begin + division);
1006 = init_winner(2 * root + 1, begin + division, end);
1007 if (!comp(*losers[right].keyp, *losers[left].keyp))
1009 // Left one is less or equal.
1010 losers[root] = losers[right];
1015 // Right one is less.
1016 losers[root] = losers[left];
1025 losers[0] = losers[init_winner(1, 0, ik)];
1029 delete_min_insert(const T& key, bool)
1031 const T* keyp = &key;
1032 int& source = losers[0].source;
1033 for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
1035 // The smaller one gets promoted.
1036 if (comp(*losers[pos].keyp, *keyp))
1038 // The other one is smaller.
1039 std::swap(losers[pos].source, source);
1040 std::swap(losers[pos].keyp, keyp);
1044 losers[0].keyp = keyp;
1048 insert_start_stable(const T& key, int source, bool)
1049 { return insert_start(key, source, false); }
1056 delete_min_insert_stable(const T& key, bool)
1058 int& source = losers[0].source;
1059 const T* keyp = &key;
1060 for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
1062 // The smaller one gets promoted, ties are broken by source.
1063 if (comp(*losers[pos].keyp, *keyp)
1064 || (!comp(*keyp, *losers[pos].keyp)
1065 && losers[pos].source < source))
1067 // The other one is smaller.
1068 std::swap(losers[pos].source, source);
1069 std::swap(losers[pos].keyp, keyp);
1072 losers[0].keyp = keyp;
1077 template<typename _ValueTp, class Comparator>
1078 struct loser_tree_traits
1080 #if _GLIBCXX_LOSER_TREE
1081 typedef LoserTree<_ValueTp, Comparator> LT;
1083 # if _GLIBCXX_LOSER_TREE_POINTER
1084 typedef LoserTreePointer<_ValueTp, Comparator> LT;
1086 # error Must define some type in losertree.h.
1091 template<typename _ValueTp, class Comparator>
1092 struct loser_tree_unguarded_traits
1094 #if _GLIBCXX_LOSER_TREE_UNGUARDED
1095 typedef LoserTreeUnguarded<_ValueTp, Comparator> LT;
1097 # if _GLIBCXX_LOSER_TREE_POINTER_UNGUARDED
1098 typedef LoserTreePointerUnguarded<_ValueTp, Comparator> LT;
1100 # error Must define some unguarded type in losertree.h.