Index: gcc/libstdc++-v3/include/parallel/multiway_mergesort.h |
diff --git a/gcc/libstdc++-v3/include/parallel/multiway_mergesort.h b/gcc/libstdc++-v3/include/parallel/multiway_mergesort.h |
deleted file mode 100644 |
index 11dd885c8aeca42eeefc5aa171db4acfa22112ad..0000000000000000000000000000000000000000 |
--- a/gcc/libstdc++-v3/include/parallel/multiway_mergesort.h |
+++ /dev/null |
@@ -1,475 +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/multiway_mergesort.h |
- * @brief Parallel multiway merge sort. |
- * This file is a GNU parallel extension to the Standard C++ Library. |
- */ |
- |
-// Written by Johannes Singler. |
- |
-#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H |
-#define _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H 1 |
- |
-#include <vector> |
- |
-#include <parallel/basic_iterator.h> |
-#include <bits/stl_algo.h> |
-#include <parallel/parallel.h> |
-#include <parallel/multiway_merge.h> |
- |
-namespace __gnu_parallel |
-{ |
- |
-/** @brief Subsequence description. */ |
-template<typename _DifferenceTp> |
- struct Piece |
- { |
- typedef _DifferenceTp difference_type; |
- |
- /** @brief Begin of subsequence. */ |
- difference_type begin; |
- |
- /** @brief End of subsequence. */ |
- difference_type end; |
- }; |
- |
-/** @brief Data accessed by all threads. |
- * |
- * PMWMS = parallel multiway mergesort */ |
-template<typename RandomAccessIterator> |
- struct PMWMSSortingData |
- { |
- typedef std::iterator_traits<RandomAccessIterator> traits_type; |
- typedef typename traits_type::value_type value_type; |
- typedef typename traits_type::difference_type difference_type; |
- |
- /** @brief Number of threads involved. */ |
- thread_index_t num_threads; |
- |
- /** @brief Input begin. */ |
- RandomAccessIterator source; |
- |
- /** @brief Start indices, per thread. */ |
- difference_type* starts; |
- |
- /** @brief Storage in which to sort. */ |
- value_type** temporary; |
- |
- /** @brief Samples. */ |
- value_type* samples; |
- |
- /** @brief Offsets to add to the found positions. */ |
- difference_type* offsets; |
- |
- /** @brief Pieces of data to merge @c [thread][sequence] */ |
- std::vector<Piece<difference_type> >* pieces; |
-}; |
- |
-/** |
- * @brief Select samples from a sequence. |
- * @param sd Pointer to algorithm data. Result will be placed in |
- * @c sd->samples. |
- * @param num_samples Number of samples to select. |
- */ |
-template<typename RandomAccessIterator, typename _DifferenceTp> |
- void |
- determine_samples(PMWMSSortingData<RandomAccessIterator>* sd, |
- _DifferenceTp num_samples) |
- { |
- typedef std::iterator_traits<RandomAccessIterator> traits_type; |
- typedef typename traits_type::value_type value_type; |
- typedef _DifferenceTp difference_type; |
- |
- thread_index_t iam = omp_get_thread_num(); |
- |
- difference_type* es = new difference_type[num_samples + 2]; |
- |
- equally_split(sd->starts[iam + 1] - sd->starts[iam], |
- num_samples + 1, es); |
- |
- for (difference_type i = 0; i < num_samples; ++i) |
- ::new(&(sd->samples[iam * num_samples + i])) |
- value_type(sd->source[sd->starts[iam] + es[i + 1]]); |
- |
- delete[] es; |
- } |
- |
-/** @brief Split consistently. */ |
-template<bool exact, typename RandomAccessIterator, |
- typename Comparator, typename SortingPlacesIterator> |
- struct split_consistently |
- { |
- }; |
- |
-/** @brief Split by exact splitting. */ |
-template<typename RandomAccessIterator, typename Comparator, |
- typename SortingPlacesIterator> |
- struct split_consistently |
- <true, RandomAccessIterator, Comparator, SortingPlacesIterator> |
- { |
- void operator()( |
- const thread_index_t iam, |
- PMWMSSortingData<RandomAccessIterator>* sd, |
- Comparator& comp, |
- const typename |
- std::iterator_traits<RandomAccessIterator>::difference_type |
- num_samples) |
- const |
- { |
-# pragma omp barrier |
- |
- std::vector<std::pair<SortingPlacesIterator, SortingPlacesIterator> > |
- seqs(sd->num_threads); |
- for (thread_index_t s = 0; s < sd->num_threads; s++) |
- seqs[s] = std::make_pair(sd->temporary[s], |
- sd->temporary[s] |
- + (sd->starts[s + 1] - sd->starts[s])); |
- |
- std::vector<SortingPlacesIterator> offsets(sd->num_threads); |
- |
- // if not last thread |
- if (iam < sd->num_threads - 1) |
- multiseq_partition(seqs.begin(), seqs.end(), |
- sd->starts[iam + 1], offsets.begin(), comp); |
- |
- for (int seq = 0; seq < sd->num_threads; seq++) |
- { |
- // for each sequence |
- if (iam < (sd->num_threads - 1)) |
- sd->pieces[iam][seq].end = offsets[seq] - seqs[seq].first; |
- else |
- // very end of this sequence |
- sd->pieces[iam][seq].end = |
- sd->starts[seq + 1] - sd->starts[seq]; |
- } |
- |
-# pragma omp barrier |
- |
- for (thread_index_t seq = 0; seq < sd->num_threads; seq++) |
- { |
- // For each sequence. |
- if (iam > 0) |
- sd->pieces[iam][seq].begin = sd->pieces[iam - 1][seq].end; |
- else |
- // Absolute beginning. |
- sd->pieces[iam][seq].begin = 0; |
- } |
- } |
- }; |
- |
-/** @brief Split by sampling. */ |
-template<typename RandomAccessIterator, typename Comparator, |
- typename SortingPlacesIterator> |
- struct split_consistently<false, RandomAccessIterator, Comparator, |
- SortingPlacesIterator> |
- { |
- void operator()( |
- const thread_index_t iam, |
- PMWMSSortingData<RandomAccessIterator>* sd, |
- Comparator& comp, |
- const typename |
- std::iterator_traits<RandomAccessIterator>::difference_type |
- num_samples) |
- const |
- { |
- typedef std::iterator_traits<RandomAccessIterator> traits_type; |
- typedef typename traits_type::value_type value_type; |
- typedef typename traits_type::difference_type difference_type; |
- |
- determine_samples(sd, num_samples); |
- |
-# pragma omp barrier |
- |
-# pragma omp single |
- __gnu_sequential::sort(sd->samples, |
- sd->samples + (num_samples * sd->num_threads), |
- comp); |
- |
-# pragma omp barrier |
- |
- for (thread_index_t s = 0; s < sd->num_threads; ++s) |
- { |
- // For each sequence. |
- if (num_samples * iam > 0) |
- sd->pieces[iam][s].begin = |
- std::lower_bound(sd->temporary[s], |
- sd->temporary[s] |
- + (sd->starts[s + 1] - sd->starts[s]), |
- sd->samples[num_samples * iam], |
- comp) |
- - sd->temporary[s]; |
- else |
- // Absolute beginning. |
- sd->pieces[iam][s].begin = 0; |
- |
- if ((num_samples * (iam + 1)) < (num_samples * sd->num_threads)) |
- sd->pieces[iam][s].end = |
- std::lower_bound(sd->temporary[s], |
- sd->temporary[s] |
- + (sd->starts[s + 1] - sd->starts[s]), |
- sd->samples[num_samples * (iam + 1)], |
- comp) |
- - sd->temporary[s]; |
- else |
- // Absolute end. |
- sd->pieces[iam][s].end = sd->starts[s + 1] - sd->starts[s]; |
- } |
- } |
- }; |
- |
-template<bool stable, typename RandomAccessIterator, typename Comparator> |
- struct possibly_stable_sort |
- { |
- }; |
- |
-template<typename RandomAccessIterator, typename Comparator> |
- struct possibly_stable_sort<true, RandomAccessIterator, Comparator> |
- { |
- void operator()(const RandomAccessIterator& begin, |
- const RandomAccessIterator& end, Comparator& comp) const |
- { |
- __gnu_sequential::stable_sort(begin, end, comp); |
- } |
- }; |
- |
-template<typename RandomAccessIterator, typename Comparator> |
- struct possibly_stable_sort<false, RandomAccessIterator, Comparator> |
- { |
- void operator()(const RandomAccessIterator begin, |
- const RandomAccessIterator end, Comparator& comp) const |
- { |
- __gnu_sequential::sort(begin, end, comp); |
- } |
- }; |
- |
-template<bool stable, typename SeqRandomAccessIterator, |
- typename RandomAccessIterator, typename Comparator, |
- typename DiffType> |
- struct possibly_stable_multiway_merge |
- { |
- }; |
- |
-template<typename SeqRandomAccessIterator, typename RandomAccessIterator, |
- typename Comparator, typename DiffType> |
- struct possibly_stable_multiway_merge |
- <true, SeqRandomAccessIterator, RandomAccessIterator, Comparator, |
- DiffType> |
- { |
- void operator()(const SeqRandomAccessIterator& seqs_begin, |
- const SeqRandomAccessIterator& seqs_end, |
- const RandomAccessIterator& target, |
- Comparator& comp, |
- DiffType length_am) const |
- { |
- stable_multiway_merge(seqs_begin, seqs_end, target, length_am, comp, |
- sequential_tag()); |
- } |
- }; |
- |
-template<typename SeqRandomAccessIterator, typename RandomAccessIterator, |
- typename Comparator, typename DiffType> |
- struct possibly_stable_multiway_merge |
- <false, SeqRandomAccessIterator, RandomAccessIterator, Comparator, |
- DiffType> |
- { |
- void operator()(const SeqRandomAccessIterator& seqs_begin, |
- const SeqRandomAccessIterator& seqs_end, |
- const RandomAccessIterator& target, |
- Comparator& comp, |
- DiffType length_am) const |
- { |
- multiway_merge(seqs_begin, seqs_end, target, length_am, comp, |
- sequential_tag()); |
- } |
- }; |
- |
-/** @brief PMWMS code executed by each thread. |
- * @param sd Pointer to algorithm data. |
- * @param comp Comparator. |
- */ |
-template<bool stable, bool exact, typename RandomAccessIterator, |
- typename Comparator> |
- void |
- parallel_sort_mwms_pu(PMWMSSortingData<RandomAccessIterator>* sd, |
- Comparator& comp) |
- { |
- typedef std::iterator_traits<RandomAccessIterator> traits_type; |
- typedef typename traits_type::value_type value_type; |
- typedef typename traits_type::difference_type difference_type; |
- |
- thread_index_t iam = omp_get_thread_num(); |
- |
- // Length of this thread's chunk, before merging. |
- difference_type length_local = sd->starts[iam + 1] - sd->starts[iam]; |
- |
- // Sort in temporary storage, leave space for sentinel. |
- |
- typedef value_type* SortingPlacesIterator; |
- |
- sd->temporary[iam] = |
- static_cast<value_type*>( |
- ::operator new(sizeof(value_type) * (length_local + 1))); |
- |
- // Copy there. |
- std::uninitialized_copy(sd->source + sd->starts[iam], |
- sd->source + sd->starts[iam] + length_local, |
- sd->temporary[iam]); |
- |
- possibly_stable_sort<stable, SortingPlacesIterator, Comparator>() |
- (sd->temporary[iam], sd->temporary[iam] + length_local, comp); |
- |
- // Invariant: locally sorted subsequence in sd->temporary[iam], |
- // sd->temporary[iam] + length_local. |
- |
- // No barrier here: Synchronization is done by the splitting routine. |
- |
- difference_type num_samples = |
- _Settings::get().sort_mwms_oversampling * sd->num_threads - 1; |
- split_consistently |
- <exact, RandomAccessIterator, Comparator, SortingPlacesIterator>() |
- (iam, sd, comp, num_samples); |
- |
- // Offset from target begin, length after merging. |
- difference_type offset = 0, length_am = 0; |
- for (thread_index_t s = 0; s < sd->num_threads; s++) |
- { |
- length_am += sd->pieces[iam][s].end - sd->pieces[iam][s].begin; |
- offset += sd->pieces[iam][s].begin; |
- } |
- |
- typedef std::vector< |
- std::pair<SortingPlacesIterator, SortingPlacesIterator> > |
- seq_vector_type; |
- seq_vector_type seqs(sd->num_threads); |
- |
- for (int s = 0; s < sd->num_threads; ++s) |
- { |
- seqs[s] = |
- std::make_pair(sd->temporary[s] + sd->pieces[iam][s].begin, |
- sd->temporary[s] + sd->pieces[iam][s].end); |
- } |
- |
- possibly_stable_multiway_merge< |
- stable, |
- typename seq_vector_type::iterator, |
- RandomAccessIterator, |
- Comparator, difference_type>() |
- (seqs.begin(), seqs.end(), |
- sd->source + offset, comp, |
- length_am); |
- |
-# pragma omp barrier |
- |
- ::operator delete(sd->temporary[iam]); |
- } |
- |
-/** @brief PMWMS main call. |
- * @param begin Begin iterator of sequence. |
- * @param end End iterator of sequence. |
- * @param comp Comparator. |
- * @param n Length of sequence. |
- * @param num_threads Number of threads to use. |
- */ |
-template<bool stable, bool exact, typename RandomAccessIterator, |
- typename Comparator> |
- void |
- parallel_sort_mwms(RandomAccessIterator begin, RandomAccessIterator end, |
- Comparator comp, |
- thread_index_t num_threads) |
- { |
- _GLIBCXX_CALL(end - begin) |
- |
- typedef std::iterator_traits<RandomAccessIterator> traits_type; |
- typedef typename traits_type::value_type value_type; |
- typedef typename traits_type::difference_type difference_type; |
- |
- difference_type n = end - begin; |
- |
- if (n <= 1) |
- return; |
- |
- // at least one element per thread |
- if (num_threads > n) |
- num_threads = static_cast<thread_index_t>(n); |
- |
- // shared variables |
- PMWMSSortingData<RandomAccessIterator> sd; |
- difference_type* starts; |
- |
-# pragma omp parallel num_threads(num_threads) |
- { |
- num_threads = omp_get_num_threads(); //no more threads than requested |
- |
-# pragma omp single |
- { |
- sd.num_threads = num_threads; |
- sd.source = begin; |
- |
- sd.temporary = new value_type*[num_threads]; |
- |
- if (!exact) |
- { |
- difference_type size = |
- (_Settings::get().sort_mwms_oversampling * num_threads - 1) |
- * num_threads; |
- sd.samples = static_cast<value_type*>( |
- ::operator new(size * sizeof(value_type))); |
- } |
- else |
- sd.samples = NULL; |
- |
- sd.offsets = new difference_type[num_threads - 1]; |
- sd.pieces = new std::vector<Piece<difference_type> >[num_threads]; |
- for (int s = 0; s < num_threads; ++s) |
- sd.pieces[s].resize(num_threads); |
- starts = sd.starts = new difference_type[num_threads + 1]; |
- |
- difference_type chunk_length = n / num_threads; |
- difference_type split = n % num_threads; |
- difference_type pos = 0; |
- for (int i = 0; i < num_threads; ++i) |
- { |
- starts[i] = pos; |
- pos += (i < split) ? (chunk_length + 1) : chunk_length; |
- } |
- starts[num_threads] = pos; |
- } //single |
- |
- // Now sort in parallel. |
- parallel_sort_mwms_pu<stable, exact>(&sd, comp); |
- } //parallel |
- |
- delete[] starts; |
- delete[] sd.temporary; |
- |
- if (!exact) |
- ::operator delete(sd.samples); |
- |
- delete[] sd.offsets; |
- delete[] sd.pieces; |
- } |
-} //namespace __gnu_parallel |
- |
-#endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGESORT_H */ |