Install gcc-4.3.3-tdm-1-g++.tar.gz
[msysgit.git] / mingw / lib / gcc / mingw32 / 4.3.3 / include / c++ / parallel / losertree.h
blob9c49f487eb2a222d8a54bd021258f84e3280d882
1 // -*- C++ -*-
3 // Copyright (C) 2007, 2008 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 2, or (at your option) any later
9 // version.
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
29 // Public License.
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
41 #include <functional>
43 #include <bits/stl_algobase.h>
44 #include <parallel/features.h>
45 #include <parallel/base.h>
47 namespace __gnu_parallel
50 /**
51 * @brief Guarded loser/tournament tree.
53 * The smallest element is at the top.
55 * Guarding is done explicitly through one flag sup per element,
56 * inf is not needed due to a better initialization routine. This
57 * is a well-performing variant.
59 * @param T the element type
60 * @param Comparator the comparator to use, defaults to std::less<T>
62 template<typename T, typename Comparator>
63 class LoserTreeBase
65 protected:
66 /** @brief Internal representation of a LoserTree element. */
67 struct Loser
69 /** @brief flag, true iff this is a "maximum" sentinel. */
70 bool sup;
71 /** @brief index of the source sequence. */
72 int source;
73 /** @brief key of the element in the LoserTree. */
74 T key;
77 unsigned int ik, k, offset;
79 /** log_2{k} */
80 unsigned int _M_log_k;
82 /** @brief LoserTree elements. */
83 Loser* losers;
85 /** @brief Comparator to use. */
86 Comparator comp;
88 /**
89 * @brief State flag that determines whether the LoserTree is empty.
91 * Only used for building the LoserTree.
93 bool first_insert;
95 public:
96 /**
97 * @brief The constructor.
99 * @param _k The number of sequences to merge.
100 * @param _comp The comparator to use.
102 LoserTreeBase(unsigned int _k, Comparator _comp)
103 : comp(_comp)
105 ik = _k;
107 // Compute log_2{k} for the Loser Tree
108 _M_log_k = log2(ik - 1) + 1;
110 // Next greater power of 2.
111 k = 1 << _M_log_k;
112 offset = k;
114 // Avoid default-constructing losers[].key
115 losers = static_cast<Loser*>(::operator new(2 * k * sizeof(Loser)));
116 for (unsigned int i = ik - 1; i < k; ++i)
117 losers[i + k].sup = true;
119 first_insert = true;
123 * @brief The destructor.
125 ~LoserTreeBase()
126 { ::operator delete(losers); }
129 * @brief Initializes the sequence "source" with the element "key".
131 * @param key the element to insert
132 * @param source index of the source sequence
133 * @param sup flag that determines whether the value to insert is an
134 * explicit supremum.
136 inline void
137 insert_start(const T& key, int source, bool sup)
139 unsigned int pos = k + source;
141 if(first_insert)
143 // Construct all keys, so we can easily deconstruct them.
144 for (unsigned int i = 0; i < (2 * k); ++i)
145 new(&(losers[i].key)) T(key);
146 first_insert = false;
148 else
149 new(&(losers[pos].key)) T(key);
151 losers[pos].sup = sup;
152 losers[pos].source = source;
156 * @return the index of the sequence with the smallest element.
158 int get_min_source()
159 { return losers[0].source; }
163 * @brief Stable LoserTree variant.
165 * Provides the stable implementations of insert_start, init_winner,
166 * init and delete_min_insert.
168 * Unstable variant is done using partial specialisation below.
170 template<bool stable/* default == true */, typename T, typename Comparator>
171 class LoserTree : public LoserTreeBase<T, Comparator>
173 typedef LoserTreeBase<T, Comparator> Base;
174 using Base::k;
175 using Base::losers;
176 using Base::first_insert;
178 public:
179 LoserTree(unsigned int _k, Comparator _comp)
180 : Base::LoserTreeBase(_k, _comp)
183 unsigned int
184 init_winner(unsigned int root)
186 if (root >= k)
188 return root;
190 else
192 unsigned int left = init_winner (2 * root);
193 unsigned int right = init_winner (2 * root + 1);
194 if (losers[right].sup
195 || (!losers[left].sup
196 && !comp(losers[right].key, losers[left].key)))
198 // Left one is less or equal.
199 losers[root] = losers[right];
200 return left;
202 else
204 // Right one is less.
205 losers[root] = losers[left];
206 return right;
211 void init()
212 { losers[0] = losers[init_winner(1)]; }
215 * @brief Delete the smallest element and insert a new element from
216 * the previously smallest element's sequence.
218 * This implementation is stable.
220 // Do not pass a const reference since key will be used as local variable.
221 void delete_min_insert(T key, bool sup)
223 #if _GLIBCXX_ASSERTIONS
224 // no dummy sequence can ever be at the top!
225 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
226 #endif
228 int source = losers[0].source;
229 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
231 // The smaller one gets promoted, ties are broken by source.
232 if ((sup && (!losers[pos].sup || losers[pos].source < source))
233 || (!sup && !losers[pos].sup
234 && ((comp(losers[pos].key, key))
235 || (!comp(key, losers[pos].key)
236 && losers[pos].source < source))))
238 // The other one is smaller.
239 std::swap(losers[pos].sup, sup);
240 std::swap(losers[pos].source, source);
241 std::swap(losers[pos].key, key);
245 losers[0].sup = sup;
246 losers[0].source = source;
247 losers[0].key = key;
252 * @brief Unstable LoserTree variant.
254 * Stability (non-stable here) is selected with partial specialization.
256 template<typename T, typename Comparator>
257 class LoserTree</* stable == */false, T, Comparator> :
258 public LoserTreeBase<T, Comparator>
260 typedef LoserTreeBase<T, Comparator> Base;
261 using Base::_M_log_k;
262 using Base::k;
263 using Base::losers;
264 using Base::first_insert;
266 public:
267 LoserTree(unsigned int _k, Comparator _comp)
268 : Base::LoserTreeBase(_k, _comp)
272 * Computes the winner of the competition at position "root".
274 * Called recursively (starting at 0) to build the initial tree.
276 * @param root index of the "game" to start.
278 unsigned int
279 init_winner (unsigned int root)
281 if (root >= k)
283 return root;
285 else
287 unsigned int left = init_winner (2 * root);
288 unsigned int right = init_winner (2 * root + 1);
289 if (losers[right].sup ||
290 (!losers[left].sup
291 && !comp(losers[right].key, losers[left].key)))
293 // Left one is less or equal.
294 losers[root] = losers[right];
295 return left;
297 else
299 // Right one is less.
300 losers[root] = losers[left];
301 return right;
306 inline void
307 init()
308 { losers[0] = losers[init_winner(1)]; }
311 * Delete the key smallest element and insert the element key instead.
313 * @param key the key to insert
314 * @param sup true iff key is an explicitly marked supremum
316 // Do not pass a const reference since key will be used as local variable.
317 inline void
318 delete_min_insert(T key, bool sup)
320 #if _GLIBCXX_ASSERTIONS
321 // no dummy sequence can ever be at the top!
322 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
323 #endif
325 int source = losers[0].source;
326 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
328 // The smaller one gets promoted.
329 if (sup || (!losers[pos].sup && comp(losers[pos].key, key)))
331 // The other one is smaller.
332 std::swap(losers[pos].sup, sup);
333 std::swap(losers[pos].source, source);
334 std::swap(losers[pos].key, key);
338 losers[0].sup = sup;
339 losers[0].source = source;
340 losers[0].key = key;
346 * @brief Base class of Loser Tree implementation using pointers.
348 template<typename T, typename Comparator>
349 class LoserTreePointerBase
351 protected:
352 /** @brief Internal representation of LoserTree elements. */
353 struct Loser
355 bool sup;
356 int source;
357 const T* keyp;
360 unsigned int ik, k, offset;
361 Loser* losers;
362 Comparator comp;
364 public:
365 LoserTreePointerBase(unsigned int _k, Comparator _comp = std::less<T>())
366 : comp(_comp)
368 ik = _k;
370 // Next greater power of 2.
371 k = 1 << (log2(ik - 1) + 1);
372 offset = k;
373 losers = new Loser[k * 2];
374 for (unsigned int i = ik - 1; i < k; i++)
375 losers[i + k].sup = true;
378 ~LoserTreePointerBase()
379 { ::operator delete[](losers); }
381 int get_min_source()
382 { return losers[0].source; }
384 void insert_start(const T& key, int source, bool sup)
386 unsigned int pos = k + source;
388 losers[pos].sup = sup;
389 losers[pos].source = source;
390 losers[pos].keyp = &key;
395 * @brief Stable LoserTree implementation.
397 * The unstable variant is implemented using partial instantiation below.
399 template<bool stable/* default == true */, typename T, typename Comparator>
400 class LoserTreePointer : public LoserTreePointerBase<T, Comparator>
402 typedef LoserTreePointerBase<T, Comparator> Base;
403 using Base::k;
404 using Base::losers;
406 public:
407 LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
408 : Base::LoserTreePointerBase(_k, _comp)
411 unsigned int
412 init_winner(unsigned int root)
414 if (root >= k)
416 return root;
418 else
420 unsigned int left = init_winner (2 * root);
421 unsigned int right = init_winner (2 * root + 1);
422 if (losers[right].sup
423 || (!losers[left].sup && !comp(*losers[right].keyp,
424 *losers[left].keyp)))
426 // Left one is less or equal.
427 losers[root] = losers[right];
428 return left;
430 else
432 // Right one is less.
433 losers[root] = losers[left];
434 return right;
439 void init()
440 { losers[0] = losers[init_winner(1)]; }
442 void delete_min_insert(const T& key, bool sup)
444 #if _GLIBCXX_ASSERTIONS
445 // no dummy sequence can ever be at the top!
446 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
447 #endif
449 const T* keyp = &key;
450 int source = losers[0].source;
451 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
453 // The smaller one gets promoted, ties are broken by source.
454 if ((sup && (!losers[pos].sup || losers[pos].source < source)) ||
455 (!sup && !losers[pos].sup &&
456 ((comp(*losers[pos].keyp, *keyp)) ||
457 (!comp(*keyp, *losers[pos].keyp)
458 && losers[pos].source < source))))
460 // The other one is smaller.
461 std::swap(losers[pos].sup, sup);
462 std::swap(losers[pos].source, source);
463 std::swap(losers[pos].keyp, keyp);
467 losers[0].sup = sup;
468 losers[0].source = source;
469 losers[0].keyp = keyp;
474 * @brief Unstable LoserTree implementation.
476 * The stable variant is above.
478 template<typename T, typename Comparator>
479 class LoserTreePointer</* stable == */false, T, Comparator> :
480 public LoserTreePointerBase<T, Comparator>
482 typedef LoserTreePointerBase<T, Comparator> Base;
483 using Base::k;
484 using Base::losers;
486 public:
487 LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
488 : Base::LoserTreePointerBase(_k, _comp)
491 unsigned int
492 init_winner(unsigned int root)
494 if (root >= k)
496 return root;
498 else
500 unsigned int left = init_winner (2 * root);
501 unsigned int right = init_winner (2 * root + 1);
502 if (losers[right].sup
503 || (!losers[left].sup
504 && !comp(*losers[right].keyp, *losers[left].keyp)))
506 // Left one is less or equal.
507 losers[root] = losers[right];
508 return left;
510 else
512 // Right one is less.
513 losers[root] = losers[left];
514 return right;
519 void init()
520 { losers[0] = losers[init_winner(1)]; }
522 void delete_min_insert(const T& key, bool sup)
524 #if _GLIBCXX_ASSERTIONS
525 // no dummy sequence can ever be at the top!
526 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
527 #endif
529 const T* keyp = &key;
530 int source = losers[0].source;
531 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
533 // The smaller one gets promoted.
534 if (sup || (!losers[pos].sup && comp(*losers[pos].keyp, *keyp)))
536 // The other one is smaller.
537 std::swap(losers[pos].sup, sup);
538 std::swap(losers[pos].source, source);
539 std::swap(losers[pos].keyp, keyp);
543 losers[0].sup = sup;
544 losers[0].source = source;
545 losers[0].keyp = keyp;
549 /** @brief Base class for unguarded LoserTree implementation.
551 * The whole element is copied into the tree structure.
553 * No guarding is done, therefore not a single input sequence must
554 * run empty. Unused sequence heads are marked with a sentinel which
555 * is &gt; all elements that are to be merged.
557 * This is a very fast variant.
559 template<typename T, typename Comparator>
560 class LoserTreeUnguardedBase
562 protected:
563 struct Loser
565 int source;
566 T key;
569 unsigned int ik, k, offset;
570 Loser* losers;
571 Comparator comp;
573 public:
574 inline
575 LoserTreeUnguardedBase(unsigned int _k, const T _sentinel,
576 Comparator _comp = std::less<T>())
577 : comp(_comp)
579 ik = _k;
581 // Next greater power of 2.
582 k = 1 << (log2(ik - 1) + 1);
583 offset = k;
584 // Avoid default-constructing losers[].key
585 losers = static_cast<Loser*>(::operator new(2 * k * sizeof(Loser)));
587 for (unsigned int i = k + ik - 1; i < (2 * k); ++i)
589 losers[i].key = _sentinel;
590 losers[i].source = -1;
594 inline ~LoserTreeUnguardedBase()
595 { ::operator delete(losers); }
597 inline int
598 get_min_source()
600 #if _GLIBCXX_ASSERTIONS
601 // no dummy sequence can ever be at the top!
602 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
603 #endif
604 return losers[0].source;
607 inline void
608 insert_start(const T& key, int source, bool)
610 unsigned int pos = k + source;
612 new(&(losers[pos].key)) T(key);
613 losers[pos].source = source;
618 * @brief Stable implementation of unguarded LoserTree.
620 * Unstable variant is selected below with partial specialization.
622 template<bool stable/* default == true */, typename T, typename Comparator>
623 class LoserTreeUnguarded : public LoserTreeUnguardedBase<T, Comparator>
625 typedef LoserTreeUnguardedBase<T, Comparator> Base;
626 using Base::k;
627 using Base::losers;
629 public:
630 LoserTreeUnguarded(unsigned int _k, const T _sentinel,
631 Comparator _comp = std::less<T>())
632 : Base::LoserTreeUnguardedBase(_k, _sentinel, _comp)
635 unsigned int
636 init_winner(unsigned int root)
638 if (root >= k)
640 return root;
642 else
644 unsigned int left = init_winner (2 * root);
645 unsigned int right = init_winner (2 * root + 1);
646 if (!comp(losers[right].key, losers[left].key))
648 // Left one is less or equal.
649 losers[root] = losers[right];
650 return left;
652 else
654 // Right one is less.
655 losers[root] = losers[left];
656 return right;
661 inline void
662 init()
664 losers[0] = losers[init_winner(1)];
666 #if _GLIBCXX_ASSERTIONS
667 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
668 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
669 #endif
672 // Do not pass a const reference since key will be used as local variable.
673 inline void
674 delete_min_insert(T key, bool)
676 #if _GLIBCXX_ASSERTIONS
677 // no dummy sequence can ever be at the top!
678 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
679 #endif
681 int source = losers[0].source;
682 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
684 // The smaller one gets promoted, ties are broken by source.
685 if (comp(losers[pos].key, key)
686 || (!comp(key, losers[pos].key) && losers[pos].source < source))
688 // The other one is smaller.
689 std::swap(losers[pos].source, source);
690 std::swap(losers[pos].key, key);
694 losers[0].source = source;
695 losers[0].key = key;
700 * @brief Non-Stable implementation of unguarded LoserTree.
702 * Stable implementation is above.
704 template<typename T, typename Comparator>
705 class LoserTreeUnguarded</* stable == */false, T, Comparator> :
706 public LoserTreeUnguardedBase<T, Comparator>
708 typedef LoserTreeUnguardedBase<T, Comparator> Base;
709 using Base::k;
710 using Base::losers;
712 public:
713 LoserTreeUnguarded(unsigned int _k, const T _sentinel,
714 Comparator _comp = std::less<T>())
715 : Base::LoserTreeUnguardedBase(_k, _sentinel, _comp)
718 unsigned int
719 init_winner (unsigned int root)
721 if (root >= k)
723 return root;
725 else
727 unsigned int left = init_winner (2 * root);
728 unsigned int right = init_winner (2 * root + 1);
730 #if _GLIBCXX_ASSERTIONS
731 // If left one is sentinel then right one must be, too.
732 if (losers[left].source == -1)
733 _GLIBCXX_PARALLEL_ASSERT(losers[right].source == -1);
734 #endif
736 if (!comp(losers[right].key, losers[left].key))
738 // Left one is less or equal.
739 losers[root] = losers[right];
740 return left;
742 else
744 // Right one is less.
745 losers[root] = losers[left];
746 return right;
751 inline void
752 init()
754 losers[0] = losers[init_winner(1)];
756 #if _GLIBCXX_ASSERTIONS
757 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
758 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
759 #endif
762 // Do not pass a const reference since key will be used as local variable.
763 inline void
764 delete_min_insert(T key, bool)
766 #if _GLIBCXX_ASSERTIONS
767 // no dummy sequence can ever be at the top!
768 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
769 #endif
771 int source = losers[0].source;
772 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
774 // The smaller one gets promoted.
775 if (comp(losers[pos].key, key))
777 // The other one is smaller.
778 std::swap(losers[pos].source, source);
779 std::swap(losers[pos].key, key);
783 losers[0].source = source;
784 losers[0].key = key;
788 /** @brief Unguarded loser tree, keeping only pointers to the
789 * elements in the tree structure.
791 * No guarding is done, therefore not a single input sequence must
792 * run empty. This is a very fast variant.
794 template<typename T, typename Comparator>
795 class LoserTreePointerUnguardedBase
797 protected:
798 struct Loser
800 int source;
801 const T* keyp;
804 unsigned int ik, k, offset;
805 Loser* losers;
806 Comparator comp;
808 public:
810 inline
811 LoserTreePointerUnguardedBase(unsigned int _k, const T& _sentinel,
812 Comparator _comp = std::less<T>())
813 : comp(_comp)
815 ik = _k;
817 // Next greater power of 2.
818 k = 1 << (log2(ik - 1) + 1);
819 offset = k;
820 // Avoid default-constructing losers[].key
821 losers = new Loser[2 * k];
823 for (unsigned int i = k + ik - 1; i < (2 * k); ++i)
825 losers[i].keyp = &_sentinel;
826 losers[i].source = -1;
830 inline ~LoserTreePointerUnguardedBase()
831 { delete[] losers; }
833 inline int
834 get_min_source()
836 #if _GLIBCXX_ASSERTIONS
837 // no dummy sequence can ever be at the top!
838 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
839 #endif
840 return losers[0].source;
843 inline void
844 insert_start(const T& key, int source, bool)
846 unsigned int pos = k + source;
848 losers[pos].keyp = &key;
849 losers[pos].source = source;
854 * @brief Stable unguarded LoserTree variant storing pointers.
856 * Unstable variant is implemented below using partial specialization.
858 template<bool stable/* default == true */, typename T, typename Comparator>
859 class LoserTreePointerUnguarded :
860 public LoserTreePointerUnguardedBase<T, Comparator>
862 typedef LoserTreePointerUnguardedBase<T, Comparator> Base;
863 using Base::k;
864 using Base::losers;
866 public:
867 LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel,
868 Comparator _comp = std::less<T>())
869 : Base::LoserTreePointerUnguardedBase(_k, _sentinel, _comp)
872 unsigned int
873 init_winner(unsigned int root)
875 if (root >= k)
877 return root;
879 else
881 unsigned int left = init_winner (2 * root);
882 unsigned int right = init_winner (2 * root + 1);
883 if (!comp(*losers[right].keyp, *losers[left].keyp))
885 // Left one is less or equal.
886 losers[root] = losers[right];
887 return left;
889 else
891 // Right one is less.
892 losers[root] = losers[left];
893 return right;
898 inline void
899 init()
901 losers[0] = losers[init_winner(1)];
903 #if _GLIBCXX_ASSERTIONS
904 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
905 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
906 #endif
909 inline void
910 delete_min_insert(const T& key, bool sup)
912 #if _GLIBCXX_ASSERTIONS
913 // no dummy sequence can ever be at the top!
914 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
915 #endif
917 const T* keyp = &key;
918 int source = losers[0].source;
919 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
921 // The smaller one gets promoted, ties are broken by source.
922 if (comp(*losers[pos].keyp, *keyp)
923 || (!comp(*keyp, *losers[pos].keyp) && losers[pos].source < source))
925 // The other one is smaller.
926 std::swap(losers[pos].source, source);
927 std::swap(losers[pos].keyp, keyp);
931 losers[0].source = source;
932 losers[0].keyp = keyp;
937 * @brief Unstable unguarded LoserTree variant storing pointers.
939 * Stable variant is above.
941 template<typename T, typename Comparator>
942 class LoserTreePointerUnguarded</* stable == */false, T, Comparator> :
943 public LoserTreePointerUnguardedBase<T, Comparator>
945 typedef LoserTreePointerUnguardedBase<T, Comparator> Base;
946 using Base::k;
947 using Base::losers;
949 public:
950 LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel,
951 Comparator _comp = std::less<T>())
952 : Base::LoserTreePointerUnguardedBase(_k, _sentinel, _comp)
955 unsigned int
956 init_winner(unsigned int root)
958 if (root >= k)
960 return root;
962 else
964 unsigned int left = init_winner (2 * root);
965 unsigned int right = init_winner (2 * root + 1);
967 #if _GLIBCXX_ASSERTIONS
968 // If left one is sentinel then right one must be, too.
969 if (losers[left].source == -1)
970 _GLIBCXX_PARALLEL_ASSERT(losers[right].source == -1);
971 #endif
973 if (!comp(*losers[right].keyp, *losers[left].keyp))
975 // Left one is less or equal.
976 losers[root] = losers[right];
977 return left;
979 else
981 // Right one is less.
982 losers[root] = losers[left];
983 return right;
988 inline void
989 init()
991 losers[0] = losers[init_winner(1)];
993 #if _GLIBCXX_ASSERTIONS
994 // no dummy sequence can ever be at the top at the beginning (0 sequences!)
995 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
996 #endif
999 inline void
1000 delete_min_insert(const T& key, bool sup)
1002 #if _GLIBCXX_ASSERTIONS
1003 // no dummy sequence can ever be at the top!
1004 _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
1005 #endif
1007 const T* keyp = &key;
1008 int source = losers[0].source;
1009 for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
1011 // The smaller one gets promoted.
1012 if (comp(*(losers[pos].keyp), *keyp))
1014 // The other one is smaller.
1015 std::swap(losers[pos].source, source);
1016 std::swap(losers[pos].keyp, keyp);
1020 losers[0].source = source;
1021 losers[0].keyp = keyp;
1025 } // namespace __gnu_parallel
1027 #endif