--- /dev/null
+// -*- C++ -*-
+
+// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file parallel/losertree.h
+* @brief Many generic loser tree variants.
+* This file is a GNU parallel extension to the Standard C++ Library.
+*/
+
+// Written by Johannes Singler.
+
+#ifndef _GLIBCXX_PARALLEL_LOSERTREE_H
+#define _GLIBCXX_PARALLEL_LOSERTREE_H 1
+
+#include <functional>
+
+#include <bits/stl_algobase.h>
+#include <parallel/features.h>
+#include <parallel/base.h>
+
+namespace __gnu_parallel
+{
+
+/**
+ * @brief Guarded loser/tournament tree.
+ *
+ * The smallest element is at the top.
+ *
+ * Guarding is done explicitly through one flag sup per element,
+ * inf is not needed due to a better initialization routine. This
+ * is a well-performing variant.
+ *
+ * @param T the element type
+ * @param Comparator the comparator to use, defaults to std::less<T>
+ */
+template<typename T, typename Comparator>
+class LoserTreeBase
+{
+protected:
+ /** @brief Internal representation of a LoserTree element. */
+ struct Loser
+ {
+ /** @brief flag, true iff this is a "maximum" sentinel. */
+ bool sup;
+ /** @brief index of the source sequence. */
+ int source;
+ /** @brief key of the element in the LoserTree. */
+ T key;
+ };
+
+ unsigned int ik, k, offset;
+
+ /** log_2{k} */
+ unsigned int _M_log_k;
+
+ /** @brief LoserTree elements. */
+ Loser* losers;
+
+ /** @brief Comparator to use. */
+ Comparator comp;
+
+ /**
+ * @brief State flag that determines whether the LoserTree is empty.
+ *
+ * Only used for building the LoserTree.
+ */
+ bool first_insert;
+
+public:
+ /**
+ * @brief The constructor.
+ *
+ * @param _k The number of sequences to merge.
+ * @param _comp The comparator to use.
+ */
+ LoserTreeBase(unsigned int _k, Comparator _comp)
+ : comp(_comp)
+ {
+ ik = _k;
+
+ // Compute log_2{k} for the Loser Tree
+ _M_log_k = __log2(ik - 1) + 1;
+
+ // Next greater power of 2.
+ k = 1 << _M_log_k;
+ offset = k;
+
+ // Avoid default-constructing losers[].key
+ losers = static_cast<Loser*>(::operator new(2 * k * sizeof(Loser)));
+ for (unsigned int i = ik - 1; i < k; ++i)
+ losers[i + k].sup = true;
+
+ first_insert = true;
+ }
+
+ /**
+ * @brief The destructor.
+ */
+ ~LoserTreeBase()
+ { ::operator delete(losers); }
+
+ /**
+ * @brief Initializes the sequence "source" with the element "key".
+ *
+ * @param key the element to insert
+ * @param source index of the source sequence
+ * @param sup flag that determines whether the value to insert is an
+ * explicit supremum.
+ */
+ inline void
+ insert_start(const T& key, int source, bool sup)
+ {
+ unsigned int pos = k + source;
+
+ if(first_insert)
+ {
+ // Construct all keys, so we can easily deconstruct them.
+ for (unsigned int i = 0; i < (2 * k); ++i)
+ new(&(losers[i].key)) T(key);
+ first_insert = false;
+ }
+ else
+ new(&(losers[pos].key)) T(key);
+
+ losers[pos].sup = sup;
+ losers[pos].source = source;
+ }
+
+ /**
+ * @return the index of the sequence with the smallest element.
+ */
+ int get_min_source()
+ { return losers[0].source; }
+};
+
+/**
+ * @brief Stable LoserTree variant.
+ *
+ * Provides the stable implementations of insert_start, init_winner,
+ * init and delete_min_insert.
+ *
+ * Unstable variant is done using partial specialisation below.
+ */
+template<bool stable/* default == true */, typename T, typename Comparator>
+class LoserTree : public LoserTreeBase<T, Comparator>
+{
+ typedef LoserTreeBase<T, Comparator> Base;
+ using Base::k;
+ using Base::losers;
+ using Base::first_insert;
+
+public:
+ LoserTree(unsigned int _k, Comparator _comp)
+ : Base::LoserTreeBase(_k, _comp)
+ {}
+
+ unsigned int
+ init_winner(unsigned int root)
+ {
+ if (root >= k)
+ {
+ return root;
+ }
+ else
+ {
+ unsigned int left = init_winner (2 * root);
+ unsigned int right = init_winner (2 * root + 1);
+ if (losers[right].sup
+ || (!losers[left].sup
+ && !comp(losers[right].key, losers[left].key)))
+ {
+ // Left one is less or equal.
+ losers[root] = losers[right];
+ return left;
+ }
+ else
+ {
+ // Right one is less.
+ losers[root] = losers[left];
+ return right;
+ }
+ }
+ }
+
+ void init()
+ { losers[0] = losers[init_winner(1)]; }
+
+ /**
+ * @brief Delete the smallest element and insert a new element from
+ * the previously smallest element's sequence.
+ *
+ * This implementation is stable.
+ */
+ // Do not pass a const reference since key will be used as local variable.
+ void delete_min_insert(T key, bool sup)
+ {
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top!
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+
+ int source = losers[0].source;
+ for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ {
+ // The smaller one gets promoted, ties are broken by source.
+ if ((sup && (!losers[pos].sup || losers[pos].source < source))
+ || (!sup && !losers[pos].sup
+ && ((comp(losers[pos].key, key))
+ || (!comp(key, losers[pos].key)
+ && losers[pos].source < source))))
+ {
+ // The other one is smaller.
+ std::swap(losers[pos].sup, sup);
+ std::swap(losers[pos].source, source);
+ std::swap(losers[pos].key, key);
+ }
+ }
+
+ losers[0].sup = sup;
+ losers[0].source = source;
+ losers[0].key = key;
+ }
+};
+
+/**
+ * @brief Unstable LoserTree variant.
+ *
+ * Stability (non-stable here) is selected with partial specialization.
+ */
+template<typename T, typename Comparator>
+class LoserTree</* stable == */false, T, Comparator> :
+ public LoserTreeBase<T, Comparator>
+{
+ typedef LoserTreeBase<T, Comparator> Base;
+ using Base::_M_log_k;
+ using Base::k;
+ using Base::losers;
+ using Base::first_insert;
+
+public:
+ LoserTree(unsigned int _k, Comparator _comp)
+ : Base::LoserTreeBase(_k, _comp)
+ {}
+
+ /**
+ * Computes the winner of the competition at position "root".
+ *
+ * Called recursively (starting at 0) to build the initial tree.
+ *
+ * @param root index of the "game" to start.
+ */
+ unsigned int
+ init_winner (unsigned int root)
+ {
+ if (root >= k)
+ {
+ return root;
+ }
+ else
+ {
+ unsigned int left = init_winner (2 * root);
+ unsigned int right = init_winner (2 * root + 1);
+ if (losers[right].sup ||
+ (!losers[left].sup
+ && !comp(losers[right].key, losers[left].key)))
+ {
+ // Left one is less or equal.
+ losers[root] = losers[right];
+ return left;
+ }
+ else
+ {
+ // Right one is less.
+ losers[root] = losers[left];
+ return right;
+ }
+ }
+ }
+
+ inline void
+ init()
+ { losers[0] = losers[init_winner(1)]; }
+
+ /**
+ * Delete the key smallest element and insert the element key instead.
+ *
+ * @param key the key to insert
+ * @param sup true iff key is an explicitly marked supremum
+ */
+ // Do not pass a const reference since key will be used as local variable.
+ inline void
+ delete_min_insert(T key, bool sup)
+ {
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top!
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+
+ int source = losers[0].source;
+ for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ {
+ // The smaller one gets promoted.
+ if (sup || (!losers[pos].sup && comp(losers[pos].key, key)))
+ {
+ // The other one is smaller.
+ std::swap(losers[pos].sup, sup);
+ std::swap(losers[pos].source, source);
+ std::swap(losers[pos].key, key);
+ }
+ }
+
+ losers[0].sup = sup;
+ losers[0].source = source;
+ losers[0].key = key;
+ }
+};
+
+
+/**
+ * @brief Base class of Loser Tree implementation using pointers.
+ */
+template<typename T, typename Comparator>
+class LoserTreePointerBase
+{
+protected:
+ /** @brief Internal representation of LoserTree elements. */
+ struct Loser
+ {
+ bool sup;
+ int source;
+ const T* keyp;
+ };
+
+ unsigned int ik, k, offset;
+ Loser* losers;
+ Comparator comp;
+
+public:
+ LoserTreePointerBase(unsigned int _k, Comparator _comp = std::less<T>())
+ : comp(_comp)
+ {
+ ik = _k;
+
+ // Next greater power of 2.
+ k = 1 << (__log2(ik - 1) + 1);
+ offset = k;
+ losers = new Loser[k * 2];
+ for (unsigned int i = ik - 1; i < k; i++)
+ losers[i + k].sup = true;
+ }
+
+ ~LoserTreePointerBase()
+ { ::operator delete[](losers); }
+
+ int get_min_source()
+ { return losers[0].source; }
+
+ void insert_start(const T& key, int source, bool sup)
+ {
+ unsigned int pos = k + source;
+
+ losers[pos].sup = sup;
+ losers[pos].source = source;
+ losers[pos].keyp = &key;
+ }
+};
+
+/**
+ * @brief Stable LoserTree implementation.
+ *
+ * The unstable variant is implemented using partial instantiation below.
+ */
+template<bool stable/* default == true */, typename T, typename Comparator>
+class LoserTreePointer : public LoserTreePointerBase<T, Comparator>
+{
+ typedef LoserTreePointerBase<T, Comparator> Base;
+ using Base::k;
+ using Base::losers;
+
+public:
+ LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
+ : Base::LoserTreePointerBase(_k, _comp)
+ {}
+
+ unsigned int
+ init_winner(unsigned int root)
+ {
+ if (root >= k)
+ {
+ return root;
+ }
+ else
+ {
+ unsigned int left = init_winner (2 * root);
+ unsigned int right = init_winner (2 * root + 1);
+ if (losers[right].sup
+ || (!losers[left].sup && !comp(*losers[right].keyp,
+ *losers[left].keyp)))
+ {
+ // Left one is less or equal.
+ losers[root] = losers[right];
+ return left;
+ }
+ else
+ {
+ // Right one is less.
+ losers[root] = losers[left];
+ return right;
+ }
+ }
+ }
+
+ void init()
+ { losers[0] = losers[init_winner(1)]; }
+
+ void delete_min_insert(const T& key, bool sup)
+ {
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top!
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+
+ const T* keyp = &key;
+ int source = losers[0].source;
+ for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ {
+ // The smaller one gets promoted, ties are broken by source.
+ if ((sup && (!losers[pos].sup || losers[pos].source < source)) ||
+ (!sup && !losers[pos].sup &&
+ ((comp(*losers[pos].keyp, *keyp)) ||
+ (!comp(*keyp, *losers[pos].keyp)
+ && losers[pos].source < source))))
+ {
+ // The other one is smaller.
+ std::swap(losers[pos].sup, sup);
+ std::swap(losers[pos].source, source);
+ std::swap(losers[pos].keyp, keyp);
+ }
+ }
+
+ losers[0].sup = sup;
+ losers[0].source = source;
+ losers[0].keyp = keyp;
+ }
+};
+
+/**
+ * @brief Unstable LoserTree implementation.
+ *
+ * The stable variant is above.
+ */
+template<typename T, typename Comparator>
+class LoserTreePointer</* stable == */false, T, Comparator> :
+ public LoserTreePointerBase<T, Comparator>
+{
+ typedef LoserTreePointerBase<T, Comparator> Base;
+ using Base::k;
+ using Base::losers;
+
+public:
+ LoserTreePointer(unsigned int _k, Comparator _comp = std::less<T>())
+ : Base::LoserTreePointerBase(_k, _comp)
+ {}
+
+ unsigned int
+ init_winner(unsigned int root)
+ {
+ if (root >= k)
+ {
+ return root;
+ }
+ else
+ {
+ unsigned int left = init_winner (2 * root);
+ unsigned int right = init_winner (2 * root + 1);
+ if (losers[right].sup
+ || (!losers[left].sup
+ && !comp(*losers[right].keyp, *losers[left].keyp)))
+ {
+ // Left one is less or equal.
+ losers[root] = losers[right];
+ return left;
+ }
+ else
+ {
+ // Right one is less.
+ losers[root] = losers[left];
+ return right;
+ }
+ }
+ }
+
+ void init()
+ { losers[0] = losers[init_winner(1)]; }
+
+ void delete_min_insert(const T& key, bool sup)
+ {
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top!
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+
+ const T* keyp = &key;
+ int source = losers[0].source;
+ for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ {
+ // The smaller one gets promoted.
+ if (sup || (!losers[pos].sup && comp(*losers[pos].keyp, *keyp)))
+ {
+ // The other one is smaller.
+ std::swap(losers[pos].sup, sup);
+ std::swap(losers[pos].source, source);
+ std::swap(losers[pos].keyp, keyp);
+ }
+ }
+
+ losers[0].sup = sup;
+ losers[0].source = source;
+ losers[0].keyp = keyp;
+ }
+};
+
+/** @brief Base class for unguarded LoserTree implementation.
+ *
+ * The whole element is copied into the tree structure.
+ *
+ * No guarding is done, therefore not a single input sequence must
+ * run empty. Unused sequence heads are marked with a sentinel which
+ * is > all elements that are to be merged.
+ *
+ * This is a very fast variant.
+ */
+template<typename T, typename Comparator>
+class LoserTreeUnguardedBase
+{
+protected:
+ struct Loser
+ {
+ int source;
+ T key;
+ };
+
+ unsigned int ik, k, offset;
+ Loser* losers;
+ Comparator comp;
+
+public:
+ inline
+ LoserTreeUnguardedBase(unsigned int _k, const T _sentinel,
+ Comparator _comp = std::less<T>())
+ : comp(_comp)
+ {
+ ik = _k;
+
+ // Next greater power of 2.
+ k = 1 << (__log2(ik - 1) + 1);
+ offset = k;
+ // Avoid default-constructing losers[].key
+ losers = static_cast<Loser*>(::operator new(2 * k * sizeof(Loser)));
+
+ for (unsigned int i = k + ik - 1; i < (2 * k); ++i)
+ {
+ losers[i].key = _sentinel;
+ losers[i].source = -1;
+ }
+ }
+
+ inline ~LoserTreeUnguardedBase()
+ { ::operator delete(losers); }
+
+ inline int
+ get_min_source()
+ {
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top!
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+ return losers[0].source;
+ }
+
+ inline void
+ insert_start(const T& key, int source, bool)
+ {
+ unsigned int pos = k + source;
+
+ new(&(losers[pos].key)) T(key);
+ losers[pos].source = source;
+ }
+};
+
+/**
+ * @brief Stable implementation of unguarded LoserTree.
+ *
+ * Unstable variant is selected below with partial specialization.
+ */
+template<bool stable/* default == true */, typename T, typename Comparator>
+class LoserTreeUnguarded : public LoserTreeUnguardedBase<T, Comparator>
+{
+ typedef LoserTreeUnguardedBase<T, Comparator> Base;
+ using Base::k;
+ using Base::losers;
+
+public:
+ LoserTreeUnguarded(unsigned int _k, const T _sentinel,
+ Comparator _comp = std::less<T>())
+ : Base::LoserTreeUnguardedBase(_k, _sentinel, _comp)
+ {}
+
+ unsigned int
+ init_winner(unsigned int root)
+ {
+ if (root >= k)
+ {
+ return root;
+ }
+ else
+ {
+ unsigned int left = init_winner (2 * root);
+ unsigned int right = init_winner (2 * root + 1);
+ if (!comp(losers[right].key, losers[left].key))
+ {
+ // Left one is less or equal.
+ losers[root] = losers[right];
+ return left;
+ }
+ else
+ {
+ // Right one is less.
+ losers[root] = losers[left];
+ return right;
+ }
+ }
+ }
+
+ inline void
+ init()
+ {
+ losers[0] = losers[init_winner(1)];
+
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top at the beginning (0 sequences!)
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+ }
+
+ // Do not pass a const reference since key will be used as local variable.
+ inline void
+ delete_min_insert(T key, bool)
+ {
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top!
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+
+ int source = losers[0].source;
+ for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ {
+ // The smaller one gets promoted, ties are broken by source.
+ if (comp(losers[pos].key, key)
+ || (!comp(key, losers[pos].key) && losers[pos].source < source))
+ {
+ // The other one is smaller.
+ std::swap(losers[pos].source, source);
+ std::swap(losers[pos].key, key);
+ }
+ }
+
+ losers[0].source = source;
+ losers[0].key = key;
+ }
+};
+
+/**
+ * @brief Non-Stable implementation of unguarded LoserTree.
+ *
+ * Stable implementation is above.
+ */
+template<typename T, typename Comparator>
+class LoserTreeUnguarded</* stable == */false, T, Comparator> :
+ public LoserTreeUnguardedBase<T, Comparator>
+{
+ typedef LoserTreeUnguardedBase<T, Comparator> Base;
+ using Base::k;
+ using Base::losers;
+
+public:
+ LoserTreeUnguarded(unsigned int _k, const T _sentinel,
+ Comparator _comp = std::less<T>())
+ : Base::LoserTreeUnguardedBase(_k, _sentinel, _comp)
+ {}
+
+ unsigned int
+ init_winner (unsigned int root)
+ {
+ if (root >= k)
+ {
+ return root;
+ }
+ else
+ {
+ unsigned int left = init_winner (2 * root);
+ unsigned int right = init_winner (2 * root + 1);
+
+#if _GLIBCXX_ASSERTIONS
+ // If left one is sentinel then right one must be, too.
+ if (losers[left].source == -1)
+ _GLIBCXX_PARALLEL_ASSERT(losers[right].source == -1);
+#endif
+
+ if (!comp(losers[right].key, losers[left].key))
+ {
+ // Left one is less or equal.
+ losers[root] = losers[right];
+ return left;
+ }
+ else
+ {
+ // Right one is less.
+ losers[root] = losers[left];
+ return right;
+ }
+ }
+ }
+
+ inline void
+ init()
+ {
+ losers[0] = losers[init_winner(1)];
+
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top at the beginning (0 sequences!)
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+ }
+
+ // Do not pass a const reference since key will be used as local variable.
+ inline void
+ delete_min_insert(T key, bool)
+ {
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top!
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+
+ int source = losers[0].source;
+ for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ {
+ // The smaller one gets promoted.
+ if (comp(losers[pos].key, key))
+ {
+ // The other one is smaller.
+ std::swap(losers[pos].source, source);
+ std::swap(losers[pos].key, key);
+ }
+ }
+
+ losers[0].source = source;
+ losers[0].key = key;
+ }
+};
+
+/** @brief Unguarded loser tree, keeping only pointers to the
+* elements in the tree structure.
+*
+* No guarding is done, therefore not a single input sequence must
+* run empty. This is a very fast variant.
+*/
+template<typename T, typename Comparator>
+class LoserTreePointerUnguardedBase
+{
+protected:
+ struct Loser
+ {
+ int source;
+ const T* keyp;
+ };
+
+ unsigned int ik, k, offset;
+ Loser* losers;
+ Comparator comp;
+
+public:
+
+ inline
+ LoserTreePointerUnguardedBase(unsigned int _k, const T& _sentinel,
+ Comparator _comp = std::less<T>())
+ : comp(_comp)
+ {
+ ik = _k;
+
+ // Next greater power of 2.
+ k = 1 << (__log2(ik - 1) + 1);
+ offset = k;
+ // Avoid default-constructing losers[].key
+ losers = new Loser[2 * k];
+
+ for (unsigned int i = k + ik - 1; i < (2 * k); ++i)
+ {
+ losers[i].keyp = &_sentinel;
+ losers[i].source = -1;
+ }
+ }
+
+ inline ~LoserTreePointerUnguardedBase()
+ { delete[] losers; }
+
+ inline int
+ get_min_source()
+ {
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top!
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+ return losers[0].source;
+ }
+
+ inline void
+ insert_start(const T& key, int source, bool)
+ {
+ unsigned int pos = k + source;
+
+ losers[pos].keyp = &key;
+ losers[pos].source = source;
+ }
+};
+
+/**
+ * @brief Stable unguarded LoserTree variant storing pointers.
+ *
+ * Unstable variant is implemented below using partial specialization.
+ */
+template<bool stable/* default == true */, typename T, typename Comparator>
+class LoserTreePointerUnguarded :
+ public LoserTreePointerUnguardedBase<T, Comparator>
+{
+ typedef LoserTreePointerUnguardedBase<T, Comparator> Base;
+ using Base::k;
+ using Base::losers;
+
+public:
+ LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel,
+ Comparator _comp = std::less<T>())
+ : Base::LoserTreePointerUnguardedBase(_k, _sentinel, _comp)
+ {}
+
+ unsigned int
+ init_winner(unsigned int root)
+ {
+ if (root >= k)
+ {
+ return root;
+ }
+ else
+ {
+ unsigned int left = init_winner (2 * root);
+ unsigned int right = init_winner (2 * root + 1);
+ if (!comp(*losers[right].keyp, *losers[left].keyp))
+ {
+ // Left one is less or equal.
+ losers[root] = losers[right];
+ return left;
+ }
+ else
+ {
+ // Right one is less.
+ losers[root] = losers[left];
+ return right;
+ }
+ }
+ }
+
+ inline void
+ init()
+ {
+ losers[0] = losers[init_winner(1)];
+
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top at the beginning (0 sequences!)
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+ }
+
+ inline void
+ delete_min_insert(const T& key, bool sup)
+ {
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top!
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+
+ const T* keyp = &key;
+ int source = losers[0].source;
+ for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ {
+ // The smaller one gets promoted, ties are broken by source.
+ if (comp(*losers[pos].keyp, *keyp)
+ || (!comp(*keyp, *losers[pos].keyp) && losers[pos].source < source))
+ {
+ // The other one is smaller.
+ std::swap(losers[pos].source, source);
+ std::swap(losers[pos].keyp, keyp);
+ }
+ }
+
+ losers[0].source = source;
+ losers[0].keyp = keyp;
+ }
+};
+
+/**
+ * @brief Unstable unguarded LoserTree variant storing pointers.
+ *
+ * Stable variant is above.
+ */
+template<typename T, typename Comparator>
+class LoserTreePointerUnguarded</* stable == */false, T, Comparator> :
+ public LoserTreePointerUnguardedBase<T, Comparator>
+{
+ typedef LoserTreePointerUnguardedBase<T, Comparator> Base;
+ using Base::k;
+ using Base::losers;
+
+public:
+ LoserTreePointerUnguarded(unsigned int _k, const T& _sentinel,
+ Comparator _comp = std::less<T>())
+ : Base::LoserTreePointerUnguardedBase(_k, _sentinel, _comp)
+ {}
+
+ unsigned int
+ init_winner(unsigned int root)
+ {
+ if (root >= k)
+ {
+ return root;
+ }
+ else
+ {
+ unsigned int left = init_winner (2 * root);
+ unsigned int right = init_winner (2 * root + 1);
+
+#if _GLIBCXX_ASSERTIONS
+ // If left one is sentinel then right one must be, too.
+ if (losers[left].source == -1)
+ _GLIBCXX_PARALLEL_ASSERT(losers[right].source == -1);
+#endif
+
+ if (!comp(*losers[right].keyp, *losers[left].keyp))
+ {
+ // Left one is less or equal.
+ losers[root] = losers[right];
+ return left;
+ }
+ else
+ {
+ // Right one is less.
+ losers[root] = losers[left];
+ return right;
+ }
+ }
+ }
+
+ inline void
+ init()
+ {
+ losers[0] = losers[init_winner(1)];
+
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top at the beginning (0 sequences!)
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+ }
+
+ inline void
+ delete_min_insert(const T& key, bool sup)
+ {
+#if _GLIBCXX_ASSERTIONS
+ // no dummy sequence can ever be at the top!
+ _GLIBCXX_PARALLEL_ASSERT(losers[0].source != -1);
+#endif
+
+ const T* keyp = &key;
+ int source = losers[0].source;
+ for (unsigned int pos = (k + source) / 2; pos > 0; pos /= 2)
+ {
+ // The smaller one gets promoted.
+ if (comp(*(losers[pos].keyp), *keyp))
+ {
+ // The other one is smaller.
+ std::swap(losers[pos].source, source);
+ std::swap(losers[pos].keyp, keyp);
+ }
+ }
+
+ losers[0].source = source;
+ losers[0].keyp = keyp;
+ }
+};
+
+} // namespace __gnu_parallel
+
+#endif /* _GLIBCXX_PARALLEL_LOSERTREE_H */
projects / msp430-gcc.git / blobdiff