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;
235 inline LoserTree(unsigned int _k, Comparator _comp = std::less<T>())
240 // Next greater power of 2.
241 k = 1 << (log2(ik - 1) + 1);
243 losers = static_cast<Loser*>(::operator new(k * 2 * sizeof(Loser)));
244 for (unsigned int i = ik - 1; i < k; i++)
245 losers[i + k].sup = true;
253 { return losers[0].source; }
256 insert_start(const T& key, int source, bool sup)
258 unsigned int pos = k + source;
260 losers[pos].sup = sup;
261 losers[pos].source = source;
262 new(&(losers[pos].key)) T(key);
266 init_winner (unsigned int root)
274 unsigned int left = init_winner (2 * root);
275 unsigned int right = init_winner (2 * root + 1);
276 if (losers[right].sup ||
278 && !comp(losers[right].key, losers[left].key)))
280 // Left one is less or equal.
281 losers[root] = losers[right];
285 { // Right one is less.
286 losers[root] = losers[left];
294 { losers[0] = losers[init_winner(1)]; }
296 // Do not pass const reference since key will be used as local variable.
298 delete_min_insert(T key, bool sup)
300 int source = losers[0].source;
301 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
303 // The smaller one gets promoted.
304 if (sup || (!losers[pos].sup && comp(losers[pos].key, key)))
306 // The other one is smaller.
307 std::swap(losers[pos].sup, sup);
308 std::swap(losers[pos].source, source);
309 std::swap(losers[pos].key, key);
314 losers[0].source = source;
319 insert_start_stable(const T& key, int source, bool sup)
320 { return insert_start(key, source, sup); }
323 init_winner_stable (unsigned int root)
331 unsigned int left = init_winner (2 * root);
332 unsigned int right = init_winner (2 * root + 1);
333 if (losers[right].sup
334 || (!losers[left].sup
335 && !comp(losers[right].key, losers[left].key)))
337 // Left one is less or equal.
338 losers[root] = losers[right];
343 // Right one is less.
344 losers[root] = losers[left];
352 { losers[0] = losers[init_winner_stable(1)]; }
354 // Do not pass const reference since key will be used as local variable.
356 delete_min_insert_stable(T key, bool sup)
358 int source = losers[0].source;
359 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
361 // The smaller one gets promoted, ties are broken by source.
362 if ( (sup && (!losers[pos].sup || losers[pos].source < source))
363 || (!sup && !losers[pos].sup
364 && ((comp(losers[pos].key, key))
365 || (!comp(key, losers[pos].key)
366 && losers[pos].source < source))))
368 // The other one is smaller.
369 std::swap(losers[pos].sup, sup);
370 std::swap(losers[pos].source, source);
371 std::swap(losers[pos].key, key);
376 losers[0].source = source;
383 #if _GLIBCXX_LOSER_TREE_REFERENCE
385 /** @brief Guarded loser tree, either copying the whole element into
386 * the tree structure, or looking up the element via the index.
388 * Guarding is done explicitly through one flag sup per element,
389 * inf is not needed due to a better initialization routine. This
390 * is a well-performing variant.
392 template<typename T, typename Comparator = std::less<T> >
393 class LoserTreeReference
397 #define KEY(i) losers[i].key
398 #define KEY_SOURCE(i) key
400 #define KEY(i) keys[losers[i].source]
401 #define KEY_SOURCE(i) keys[i]
413 unsigned int ik, k, offset;
422 LoserTreeReference(unsigned int _k, Comparator _comp = std::less<T>())
427 // Next greater power of 2.
428 k = 1 << (log2(ik - 1) + 1);
430 losers = new Loser[k * 2];
434 for (unsigned int i = ik - 1; i < k; i++)
435 losers[i + k].sup = true;
438 inline ~LoserTreeReference()
448 { return losers[0].source; }
451 insert_start(T key, int source, bool sup)
453 unsigned int pos = k + source;
455 losers[pos].sup = sup;
456 losers[pos].source = source;
461 init_winner(unsigned int root)
469 unsigned int left = init_winner (2 * root);
470 unsigned int right = init_winner (2 * root + 1);
471 if ( losers[right].sup ||
472 (!losers[left].sup && !comp(KEY(right), KEY(left))))
474 // Left one is less or equal.
475 losers[root] = losers[right];
480 // Right one is less.
481 losers[root] = losers[left];
490 losers[0] = losers[init_winner(1)];
494 delete_min_insert(T key, bool sup)
496 int source = losers[0].source;
497 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
499 // The smaller one gets promoted.
500 if (sup || (!losers[pos].sup && comp(KEY(pos), KEY_SOURCE(source))))
502 // The other one is smaller.
503 std::swap(losers[pos].sup, sup);
504 std::swap(losers[pos].source, source);
506 std::swap(KEY(pos), KEY_SOURCE(source));
512 losers[0].source = source;
514 KEY(0) = KEY_SOURCE(source);
519 insert_start_stable(T key, int source, bool sup)
520 { return insert_start(key, source, sup); }
523 init_winner_stable(unsigned int root)
531 unsigned int left = init_winner (2 * root);
532 unsigned int right = init_winner (2 * root + 1);
533 if (losers[right].sup
534 || (!losers[left].sup && !comp(KEY(right), KEY(left))))
536 // Left one is less or equal.
537 losers[root] = losers[right];
542 // Right one is less.
543 losers[root] = losers[left];
551 { losers[0] = losers[init_winner_stable(1)]; }
554 delete_min_insert_stable(T key, bool sup)
556 int source = losers[0].source;
557 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
559 // The smaller one gets promoted, ties are broken by source.
560 if ( (sup && (!losers[pos].sup || losers[pos].source < source)) ||
561 (!sup && !losers[pos].sup &&
562 ((comp(KEY(pos), KEY_SOURCE(source))) ||
563 (!comp(KEY_SOURCE(source), KEY(pos))
564 && losers[pos].source < source))))
566 // The other one is smaller.
567 std::swap(losers[pos].sup, sup);
568 std::swap(losers[pos].source, source);
570 std::swap(KEY(pos), KEY_SOURCE(source));
576 losers[0].source = source;
578 KEY(0) = KEY_SOURCE(source);
587 #if _GLIBCXX_LOSER_TREE_POINTER
589 /** @brief Guarded loser tree, either copying the whole element into
590 the tree structure, or looking up the element via the index.
591 * Guarding is done explicitly through one flag sup per element,
592 * inf is not needed due to a better initialization routine.
593 * This is a well-performing variant.
595 template<typename T, typename Comparator = std::less<T> >
596 class LoserTreePointer
606 unsigned int ik, k, offset;
612 LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
617 // Next greater power of 2.
618 k = 1 << (log2(ik - 1) + 1);
620 losers = new Loser[k * 2];
621 for (unsigned int i = ik - 1; i < k; i++)
622 losers[i + k].sup = true;
625 inline ~LoserTreePointer()
630 { return losers[0].source; }
633 insert_start(const T& key, int source, bool sup)
635 unsigned int pos = k + source;
637 losers[pos].sup = sup;
638 losers[pos].source = source;
639 losers[pos].keyp = &key;
643 init_winner(unsigned int root)
651 unsigned int left = init_winner (2 * root);
652 unsigned int right = init_winner (2 * root + 1);
653 if (losers[right].sup
654 || (!losers[left].sup
655 && !comp(*losers[right].keyp, *losers[left].keyp)))
657 // Left one is less or equal.
658 losers[root] = losers[right];
663 // Right one is less.
664 losers[root] = losers[left];
672 { losers[0] = losers[init_winner(1)]; }
675 delete_min_insert(const T& key, bool sup)
677 const T* keyp = &key;
678 int source = losers[0].source;
679 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
681 // The smaller one gets promoted.
682 if (sup || (!losers[pos].sup && comp(*losers[pos].keyp, *keyp)))
684 // The other one is smaller.
685 std::swap(losers[pos].sup, sup);
686 std::swap(losers[pos].source, source);
687 std::swap(losers[pos].keyp, keyp);
692 losers[0].source = source;
693 losers[0].keyp = keyp;
697 insert_start_stable(const T& key, int source, bool sup)
698 { return insert_start(key, source, sup); }
701 init_winner_stable(unsigned int root)
709 unsigned int left = init_winner (2 * root);
710 unsigned int right = init_winner (2 * root + 1);
711 if (losers[right].sup
712 || (!losers[left].sup && !comp(*losers[right].keyp,
713 *losers[left].keyp)))
715 // Left one is less or equal.
716 losers[root] = losers[right];
721 // Right one is less.
722 losers[root] = losers[left];
730 { losers[0] = losers[init_winner_stable(1)]; }
733 delete_min_insert_stable(const T& key, bool sup)
735 const T* keyp = &key;
736 int source = losers[0].source;
737 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
739 // The smaller one gets promoted, ties are broken by source.
740 if ( (sup && (!losers[pos].sup || losers[pos].source < source)) ||
741 (!sup && !losers[pos].sup &&
742 ((comp(*losers[pos].keyp, *keyp)) ||
743 (!comp(*keyp, *losers[pos].keyp)
744 && losers[pos].source < source))))
746 // The other one is smaller.
747 std::swap(losers[pos].sup, sup);
748 std::swap(losers[pos].source, source);
749 std::swap(losers[pos].keyp, keyp);
754 losers[0].source = source;
755 losers[0].keyp = keyp;
761 #if _GLIBCXX_LOSER_TREE_UNGUARDED
763 /** @brief Unguarded loser tree, copying the whole element into the
766 * No guarding is done, therefore not a single input sequence must
767 * run empty. This is a very fast variant.
769 template<typename T, typename Comparator = std::less<T> >
770 class LoserTreeUnguarded
779 unsigned int ik, k, offset;
780 unsigned int* mapping;
785 map(unsigned int root, unsigned int begin, unsigned int end)
787 if (begin + 1 == end)
788 mapping[begin] = root;
791 // Next greater or equal power of 2.
792 unsigned int left = 1 << (log2(end - begin - 1));
793 map(root * 2, begin, begin + left);
794 map(root * 2 + 1, begin + left, end);
800 LoserTreeUnguarded(unsigned int _k, Comparator _comp = std::less<T>())
804 // Next greater or equal power of 2.
805 k = 1 << (log2(ik - 1) + 1);
807 losers = new Loser[k + ik];
808 mapping = new unsigned int[ik];
812 inline ~LoserTreeUnguarded()
820 { return losers[0].source; }
823 insert_start(const T& key, int source, bool)
825 unsigned int pos = mapping[source];
826 losers[pos].source = source;
827 losers[pos].key = key;
831 init_winner(unsigned int root, unsigned int begin, unsigned int end)
833 if (begin + 1 == end)
834 return mapping[begin];
837 // Next greater or equal power of 2.
838 unsigned int division = 1 << (log2(end - begin - 1));
839 unsigned int left = init_winner(2 * root, begin, begin + division);
841 init_winner(2 * root + 1, begin + division, end);
842 if (!comp(losers[right].key, losers[left].key))
844 // Left one is less or equal.
845 losers[root] = losers[right];
850 // Right one is less.
851 losers[root] = losers[left];
859 { losers[0] = losers[init_winner(1, 0, ik)]; }
861 // Do not pass const reference since key will be used as local variable.
863 delete_min_insert(const T& key, bool)
866 T& keyr = losers[0].key;
867 int& source = losers[0].source;
868 for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
870 // The smaller one gets promoted.
871 if (comp(losers[pos].key, keyr))
873 // The other one is smaller.
874 std::swap(losers[pos].source, source);
875 std::swap(losers[pos].key, keyr);
881 insert_start_stable(const T& key, int source, bool)
882 { return insert_start(key, source, false); }
889 delete_min_insert_stable(const T& key, bool)
892 T& keyr = losers[0].key;
893 int& source = losers[0].source;
894 for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
896 // The smaller one gets promoted, ties are broken by source.
897 if (comp(losers[pos].key, keyr)
898 || (!comp(keyr, losers[pos].key)
899 && losers[pos].source < source))
901 // The other one is smaller.
902 std::swap(losers[pos].source, source);
903 std::swap(losers[pos].key, keyr);
911 #if _GLIBCXX_LOSER_TREE_POINTER_UNGUARDED
913 /** @brief Unguarded loser tree, keeping only pointers to the
914 * elements in the tree structure.
916 * No guarding is done, therefore not a single input sequence must
917 * run empty. This is a very fast variant.
919 template<typename T, typename Comparator = std::less<T> >
920 class LoserTreePointerUnguarded
929 unsigned int ik, k, offset;
930 unsigned int* mapping;
934 void map(unsigned int root, unsigned int begin, unsigned int end)
936 if (begin + 1 == end)
937 mapping[begin] = root;
940 // Next greater or equal power of 2.
941 unsigned int left = 1 << (log2(end - begin - 1));
942 map(root * 2, begin, begin + left);
943 map(root * 2 + 1, begin + left, end);
949 LoserTreePointerUnguarded(unsigned int _k,
950 Comparator _comp = std::less<T>())
955 // Next greater power of 2.
956 k = 1 << (log2(ik - 1) + 1);
958 losers = new Loser[k + ik];
959 mapping = new unsigned int[ik];
963 inline ~LoserTreePointerUnguarded()
971 { return losers[0].source; }
974 insert_start(const T& key, int source, bool)
976 unsigned int pos = mapping[source];
977 losers[pos].source = source;
978 losers[pos].keyp = &key;
982 init_winner(unsigned int root, unsigned int begin, unsigned int end)
984 if (begin + 1 == end)
985 return mapping[begin];
988 // Next greater or equal power of 2.
989 unsigned int division = 1 << (log2(end - begin - 1));
990 unsigned int left = init_winner(2 * root, begin, begin + division);
992 = init_winner(2 * root + 1, begin + division, end);
993 if (!comp(*losers[right].keyp, *losers[left].keyp))
995 // Left one is less or equal.
996 losers[root] = losers[right];
1001 // Right one is less.
1002 losers[root] = losers[left];
1011 losers[0] = losers[init_winner(1, 0, ik)];
1015 delete_min_insert(const T& key, bool)
1017 const T* keyp = &key;
1018 int& source = losers[0].source;
1019 for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
1021 // The smaller one gets promoted.
1022 if (comp(*losers[pos].keyp, *keyp))
1024 // The other one is smaller.
1025 std::swap(losers[pos].source, source);
1026 std::swap(losers[pos].keyp, keyp);
1030 losers[0].keyp = keyp;
1034 insert_start_stable(const T& key, int source, bool)
1035 { return insert_start(key, source, false); }
1042 delete_min_insert_stable(const T& key, bool)
1044 int& source = losers[0].source;
1045 const T* keyp = &key;
1046 for (int pos = mapping[source] / 2; pos > 0; pos /= 2)
1048 // The smaller one gets promoted, ties are broken by source.
1049 if (comp(*losers[pos].keyp, *keyp)
1050 || (!comp(*keyp, *losers[pos].keyp)
1051 && losers[pos].source < source))
1053 // The other one is smaller.
1054 std::swap(losers[pos].source, source);
1055 std::swap(losers[pos].keyp, keyp);
1058 losers[0].keyp = keyp;
1063 template<typename _ValueTp, class Comparator>
1064 struct loser_tree_traits
1066 #if _GLIBCXX_LOSER_TREE
1067 typedef LoserTree<_ValueTp, Comparator> LT;
1069 # if _GLIBCXX_LOSER_TREE_POINTER
1070 typedef LoserTreePointer<_ValueTp, Comparator> LT;
1072 # error Must define some type in losertree.h.
1077 template<typename _ValueTp, class Comparator>
1078 struct loser_tree_unguarded_traits
1080 #if _GLIBCXX_LOSER_TREE_UNGUARDED
1081 typedef LoserTreeUnguarded<_ValueTp, Comparator> LT;
1083 # if _GLIBCXX_LOSER_TREE_POINTER_UNGUARDED
1084 typedef LoserTreePointerUnguarded<_ValueTp, Comparator> LT;
1086 # error Must define some unguarded type in losertree.h.