diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/parallel/losertree.h')
| -rw-r--r-- | gcc-4.4.3/libstdc++-v3/include/parallel/losertree.h | 1021 |
1 files changed, 1021 insertions, 0 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/parallel/losertree.h b/gcc-4.4.3/libstdc++-v3/include/parallel/losertree.h new file mode 100644 index 000000000..6dbd59288 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/parallel/losertree.h @@ -0,0 +1,1021 @@ +// -*- 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 */ |