http://stxxl.sourceforge.net
<beckmann@cs.uni-frankfurt.de>
<singler@kit.edu>
http://www.boost.org/LICENSE_1_0.txt
#ifndef STXXL_PARALLEL_HEADER
#define STXXL_PARALLEL_HEADER
#include <stxxl/bits/config.h>
#undef STXXL_PARALLEL
#undef STXXL_PARALLEL_MODE
#if defined(_GLIBCXX_PARALLEL) || defined (STXXL_PARALLEL_MODE_EXPLICIT)
#define STXXL_PARALLEL_MODE
#endif
#if defined(PARALLEL_MODE) && defined (__MCSTL__)
#error (_GLIBCXX_PARALLEL or STXXL_PARALLEL_MODE_EXPLICIT) and __MCSTL__ are defined
#endif
#if defined(STXXL_PARALLEL_MODE) || defined (__MCSTL__)
#define STXXL_PARALLEL 1
#else
#define STXXL_PARALLEL 0
#endif
#include <cassert>
#ifdef STXXL_PARALLEL_MODE
#include <omp.h>
#endif
#ifdef __MCSTL__
#include <mcstl.h>
#include <bits/mcstl_multiway_merge.h>
#include <stxxl/bits/compat/type_traits.h>
#endif
#if STXXL_PARALLEL
#include <algorithm>
#endif
#include <stxxl/bits/namespace.h>
#include <stxxl/bits/common/settings.h>
#include <stxxl/bits/verbose.h>
#if defined(_GLIBCXX_PARALLEL)
#define _STXXL_FORCE_SEQUENTIAL , __gnu_parallel::sequential_tag()
#elif defined(__MCSTL__)
#define _STXXL_FORCE_SEQUENTIAL , mcstl::sequential_tag()
#else
#define _STXXL_FORCE_SEQUENTIAL
#endif
#if 0
#define _STXXL_SORT_TRIGGER_FORCE_SEQUENTIAL _STXXL_FORCE_SEQUENTIAL
#else
#define _STXXL_SORT_TRIGGER_FORCE_SEQUENTIAL
#endif
#if !STXXL_PARALLEL
#undef STXXL_PARALLEL_MULTIWAY_MERGE
#define STXXL_PARALLEL_MULTIWAY_MERGE 0
#endif
#if defined(STXXL_PARALLEL_MODE) && ((__GNUC__ * 10000 + __GNUC_MINOR__ * 100) < 40400)
#undef STXXL_PARALLEL_MULTIWAY_MERGE
#define STXXL_PARALLEL_MULTIWAY_MERGE 0
#endif
#if !defined(STXXL_PARALLEL_MULTIWAY_MERGE)
#define STXXL_PARALLEL_MULTIWAY_MERGE 1
#endif
#if !defined(STXXL_NOT_CONSIDER_SORT_MEMORY_OVERHEAD)
#define STXXL_NOT_CONSIDER_SORT_MEMORY_OVERHEAD 0
#endif
#ifdef STXXL_PARALLEL_MODE_EXPLICIT
#include <parallel/algorithm>
#else
#include <algorithm>
#endif
__STXXL_BEGIN_NAMESPACE
inline unsigned sort_memory_usage_factor()
{
#if STXXL_PARALLEL && !STXXL_NOT_CONSIDER_SORT_MEMORY_OVERHEAD && defined(STXXL_PARALLEL_MODE)
return (__gnu_parallel::_Settings::get().sort_algorithm == __gnu_parallel::MWMS && omp_get_max_threads() > 1) ? 2 : 1;
#elif STXXL_PARALLEL && !STXXL_NOT_CONSIDER_SORT_MEMORY_OVERHEAD && defined(__MCSTL__)
return (mcstl::SETTINGS::sort_algorithm == mcstl::SETTINGS::MWMS && mcstl::SETTINGS::num_threads > 1) ? 2 : 1;
#else
return 1;
#endif
}
inline void check_sort_settings()
{
#if STXXL_PARALLEL && defined(STXXL_PARALLEL_MODE) && !defined(STXXL_NO_WARN_OMP_NESTED)
static bool did_warn = false;
if (!did_warn) {
if (__gnu_parallel::_Settings::get().sort_algorithm != __gnu_parallel::MWMS) {
if (omp_get_max_threads() <= 2) {
did_warn = true;
} else if (!omp_get_nested()) {
STXXL_ERRMSG("Inefficient settings detected. To get full potential from your CPU it is recommended to set OMP_NESTED=TRUE in the environment.");
did_warn = true;
}
}
}
#elif STXXL_PARALLEL && defined(__MCSTL__)
#else
#endif
}
inline bool do_parallel_merge()
{
#if STXXL_PARALLEL_MULTIWAY_MERGE && defined(STXXL_PARALLEL_MODE)
return !stxxl::SETTINGS::native_merge && omp_get_max_threads() >= 1;
#elif STXXL_PARALLEL_MULTIWAY_MERGE && defined(__MCSTL__)
return !stxxl::SETTINGS::native_merge && mcstl::SETTINGS::num_threads >= 1;
#else
return false;
#endif
}
namespace potentially_parallel
{
#ifdef STXXL_PARALLEL_MODE_EXPLICIT
using __gnu_parallel::sort;
using __gnu_parallel::random_shuffle;
#else
using std::sort;
using std::random_shuffle;
#endif
}
namespace parallel
{
#if STXXL_PARALLEL
@brief
@param
@param
@param
@param
@param
@return
template <typename RandomAccessIteratorPairIterator,
typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3
multiway_merge(RandomAccessIteratorPairIterator seqs_begin,
RandomAccessIteratorPairIterator seqs_end,
RandomAccessIterator3 target,
Comparator comp,
DiffType length)
{
#if defined(STXXL_PARALLEL_MODE) && ((__GNUC__ * 10000 + __GNUC_MINOR__ * 100) >= 40400)
return __gnu_parallel::multiway_merge(seqs_begin, seqs_end, target, length, comp);
#elif defined(STXXL_PARALLEL_MODE)
return __gnu_parallel::multiway_merge(seqs_begin, seqs_end, target, comp, length);
#elif defined(__MCSTL__)
typedef typename compat::make_signed<DiffType>::type difference_type;
return mcstl::multiway_merge(seqs_begin, seqs_end, target, comp, difference_type(length), false);
#else
#error "no implementation found for multiway_merge()"
#endif
}
@brief
@param
@param
@param
@param
@param
@return
@pre@c@c
template <typename RandomAccessIteratorPairIterator,
typename RandomAccessIterator3, typename DiffType, typename Comparator>
RandomAccessIterator3
multiway_merge_sentinel(RandomAccessIteratorPairIterator seqs_begin,
RandomAccessIteratorPairIterator seqs_end,
RandomAccessIterator3 target,
Comparator comp,
DiffType length)
{
#if defined(STXXL_PARALLEL_MODE) && ((__GNUC__ * 10000 + __GNUC_MINOR__ * 100) >= 40400)
return __gnu_parallel::multiway_merge_sentinels(seqs_begin, seqs_end, target, length, comp);
#elif defined(STXXL_PARALLEL_MODE)
return __gnu_parallel::multiway_merge_sentinels(seqs_begin, seqs_end, target, comp, length);
#elif defined(__MCSTL__)
typedef typename compat::make_signed<DiffType>::type difference_type;
return mcstl::multiway_merge_sentinel(seqs_begin, seqs_end, target, comp, difference_type(length), false);
#else
#error "no implementation found for multiway_merge_sentinel()"
#endif
}
#endif
}
__STXXL_END_NAMESPACE
#endif