| // -*- 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 */ |