Index: gcc/libstdc++-v3/include/parallel/losertree.h |
diff --git a/gcc/libstdc++-v3/include/parallel/losertree.h b/gcc/libstdc++-v3/include/parallel/losertree.h |
deleted file mode 100644 |
index 6dbd59288641cbf748dcef970f7590f64931b0f3..0000000000000000000000000000000000000000 |
--- a/gcc/libstdc++-v3/include/parallel/losertree.h |
+++ /dev/null |
@@ -1,1021 +0,0 @@ |
-// -*- 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 */ |