omp, iterator_category(), parallelism_tag); } template inline ForwardIterator max_element(ForwardIterator begin, ForwardIterator end, Comparator comp) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return max_element_switch(begin, end, comp, iterator_category()); } // Sequential fallback template inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::min_element(begin, end); } // Sequential fallback template inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::sequential_tag) { return _GLIBCXX_STD_P::min_element(begin, end, comp); } // Sequential fallback for input iterator case template inline ForwardIterator min_element_switch(ForwardIterator begin, ForwardIterator end, Comparator comp, IteratorTag) { return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); } // Parallel algorithm for random access iterators template RandomAccessIterator min_element_switch(RandomAccessIterator begin, RandomAccessIterator end, Comparator comp, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism_tag = __gnu_parallel::parallel_balanced) { if (_GLIBCXX_PARALLEL_CONDITION( static_cast<__gnu_parallel::sequence_index_t>(end - begin) >= __gnu_parallel::_Settings::get().min_element_minimal_n && __gnu_parallel::is_parallel(parallelism_tag))) { RandomAccessIterator res(begin); __gnu_parallel::identity_selector functionality; __gnu_parallel:: for_each_template_random_access(begin, end, __gnu_parallel::nothing(), functionality, __gnu_parallel:: min_element_reduct(comp), res, res, -1, parallelism_tag); return res; } else return min_element(begin, end, comp, __gnu_parallel::sequential_tag()); } // Public interface, insert default comparator template inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, __gnu_parallel::_Parallelism parallelism_tag) { typedef typename iterator_traits::value_type value_type; return min_element(begin, end, std::less(), parallelism_tag); } template inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end) { typedef typename iterator_traits::value_type value_type; return min_element(begin, end, std::less()); } // Public interface template inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, Comparator comp, __gnu_parallel::_Parallelism parallelism_tag) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return min_element_switch(begin, end, comp, iterator_category(), parallelism_tag); } template inline ForwardIterator min_element(ForwardIterator begin, ForwardIterator end, Comparator comp) { typedef iterator_traits traits_type; typedef typename traits_type::iterator_category iterator_category; return min_element_switch(begin, end, comp, iterator_category()); } } // end namespace } // end namespace #endif /* _GLIBCXX_ALGORITHM_H */ // -*- C++ -*- // Copyright (C) 2007, 2008 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. /** @file parallel/partial_sum.h * @brief Parallel implementation of std::partial_sum(), i. e. prefix * sums. * This file is a GNU parallel extension to the Standard C++ Library. */ // Written by Johannes Singler. #ifndef _GLIBCXX_PARALLEL_PARTIAL_SUM_H #define _GLIBCXX_PARALLEL_PARTIAL_SUM_H 1 #include #include #include #include #include namespace __gnu_parallel { // Problem: there is no 0-element given. /** @brief Base case prefix sum routine. * @param begin Begin iterator of input sequence. * @param end End iterator of input sequence. * @param result Begin iterator of output sequence. * @param bin_op Associative binary function. * @param value Start value. Must be passed since the neutral * element is unknown in general. * @return End iterator of output sequence. */ template OutputIterator parallel_partial_sum_basecase(InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename std::iterator_traits ::value_type value) { if (begin == end) return result; while (begin != end) { value = bin_op(value, *begin); *result = value; ++result; ++begin; } return result; } /** @brief Parallel partial sum implementation, two-phase approach, no recursion. * @param begin Begin iterator of input sequence. * @param end End iterator of input sequence. * @param result Begin iterator of output sequence. * @param bin_op Associative binary function. * @param n Length of sequence. * @param num_threads Number of threads to use. * @return End iterator of output sequence. */ template OutputIterator parallel_partial_sum_linear(InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op, typename std::iterator_traits ::difference_type n) { typedef std::iterator_traits traits_type; typedef typename traits_type::value_type value_type; typedef typename traits_type::difference_type difference_type; if (begin == end) return result; thread_index_t num_threads = std::min(get_max_threads(), n - 1); if (num_threads < 2) { *result = *begin; return parallel_partial_sum_basecase( begin + 1, end, result + 1, bin_op, *begin); } difference_type* borders; value_type* sums; const _Settings& __s = _Settings::get(); # pragma omp parallel num_threads(num_threads) { # pragma omp single { num_threads = omp_get_num_threads(); borders = new difference_type[num_threads + 2]; if (__s.partial_sum_dilation == 1.0f) equally_split(n, num_threads + 1, borders); else { difference_type chunk_length = ((double)n / ((double)num_threads + __s.partial_sum_dilation)), borderstart = n - num_threads * chunk_length; borders[0] = 0; for (int i = 1; i < (num_threads + 1); ++i) { borders[i] = borderstart; borderstart += chunk_length; } borders[num_threads + 1] = n; } sums = static_cast(::operator new(sizeof(value_type) * num_threads)); OutputIterator target_end; } //single thread_index_t iam = omp_get_thread_num(); if (iam == 0) { *result = *begin; parallel_partial_sum_basecase(begin + 1, begin + borders[1], result + 1, bin_op, *begin); ::new(&(sums[iam])) value_type(*(result + borders[1] - 1)); } else { ::new(&(sums[iam])) value_type(std::accumulate(begin + borders[iam] + 1, begin + borders[iam + 1], *(begin + borders[iam]), bin_op, __gnu_parallel::sequential_tag())); } # pragma omp barrier # pragma omp single parallel_partial_sum_basecase( sums + 1, sums + num_threads, sums + 1, bin_op, sums[0]); # pragma omp barrier // Still same team. parallel_partial_sum_basecase(begin + borders[iam + 1], begin + borders[iam + 2], result + borders[iam + 1], bin_op, sums[iam]); } //parallel ::operator delete(sums); delete[] borders; return result + n; } /** @brief Parallel partial sum front-end. * @param begin Begin iterator of input sequence. * @param end End iterator of input sequence. * @param result Begin iterator of output sequence. * @param bin_op Associative binary function. * @return End iterator of output sequence. */ template OutputIterator parallel_partial_sum(InputIterator begin, InputIterator end, OutputIterator result, BinaryOperation bin_op) { _GLIBCXX_CALL(begin - end) typedef std::iterator_traits traits_type; typedef typename traits_type::value_type value_type; typedef typename traits_type::difference_type difference_type; difference_type n = end - begin; switch (_Settings::get().partial_sum_algorithm) { case LINEAR: // Need an initial offset. return parallel_partial_sum_linear(begin, end, result, bin_op, n); default: // Partial_sum algorithm not implemented. _GLIBCXX_PARALLEL_ASSERT(0); return result + n; } } } #endif // -*- C++ -*- // Copyright (C) 2007, 2008 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. /** @file parallel/merge.h * @brief Parallel implementation of std::merge(). * This file is a GNU parallel extension to the Standard C++ Library. */ // Written by Johannes Singler. #ifndef _GLIBCXX_PARALLEL_MERGE_H #define _GLIBCXX_PARALLEL_MERGE_H 1 #include #include namespace __gnu_parallel { /** @brief Merge routine being able to merge only the @c max_length * smallest elements. * * The @c begin iterators are advanced accordingly, they might not * reach @c end, in contrast to the usual variant. * @param begin1 Begin iterator of first sequence. * @param end1 End iterator of first sequence. * @param begin2 Begin iterator of second sequence. * @param end2 End iterator of second sequence. * @param target Target begin iterator. * @param max_length Maximum number of elements to merge. * @param comp Comparator. * @return Output end iterator. */ template OutputIterator merge_advance_usual(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp) { typedef _DifferenceTp difference_type; while (begin1 != end1 && begin2 != end2 && max_length > 0) { // array1[i1] < array0[i0] if (comp(*begin2, *begin1)) *target++ = *begin2++; else *target++ = *begin1++; --max_length; } if (begin1 != end1) { target = std::copy(begin1, begin1 + max_length, target); begin1 += max_length; } else { target = std::copy(begin2, begin2 + max_length, target); begin2 += max_length; } return target; } /** @brief Merge routine being able to merge only the @c max_length * smallest elements. * * The @c begin iterators are advanced accordingly, they might not * reach @c end, in contrast to the usual variant. * Specially designed code should allow the compiler to generate * conditional moves instead of branches. * @param begin1 Begin iterator of first sequence. * @param end1 End iterator of first sequence. * @param begin2 Begin iterator of second sequence. * @param end2 End iterator of second sequence. * @param target Target begin iterator. * @param max_length Maximum number of elements to merge. * @param comp Comparator. * @return Output end iterator. */ template OutputIterator merge_advance_movc(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp) { typedef _DifferenceTp difference_type; typedef typename std::iterator_traits::value_type value_type1; typedef typename std::iterator_traits::value_type value_type2; #if _GLIBCXX_ASSERTIONS _GLIBCXX_PARALLEL_ASSERT(max_length >= 0); #endif while (begin1 != end1 && begin2 != end2 && max_length > 0) { RandomAccessIterator1 next1 = begin1 + 1; RandomAccessIterator2 next2 = begin2 + 1; value_type1 element1 = *begin1; value_type2 element2 = *begin2; if (comp(element2, element1)) { element1 = element2; begin2 = next2; } else begin1 = next1; *target = element1; ++target; --max_length; } if (begin1 != end1) { target = std::copy(begin1, begin1 + max_length, target); begin1 += max_length; } else { target = std::copy(begin2, begin2 + max_length, target); begin2 += max_length; } return target; } /** @brief Merge routine being able to merge only the @c max_length * smallest elements. * * The @c begin iterators are advanced accordingly, they might not * reach @c end, in contrast to the usual variant. * Static switch on whether to use the conditional-move variant. * @param begin1 Begin iterator of first sequence. * @param end1 End iterator of first sequence. * @param begin2 Begin iterator of second sequence. * @param end2 End iterator of second sequence. * @param target Target begin iterator. * @param max_length Maximum number of elements to merge. * @param comp Comparator. * @return Output end iterator. */ template inline OutputIterator merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, RandomAccessIterator2 end2, OutputIterator target, _DifferenceTp max_length, Comparator comp) { _GLIBCXX_CALL(max_length) return merge_advance_movc(begin1, end1, begin2, end2, target, max_length, comp); } /** @brief Merge routine fallback to sequential in case the iterators of the two input sequences are of different type. * @param begin1 Begin iterator of first sequence. * @param end1 End iterator of first sequence. * @param begin2 Begin iterator of second sequence. * @param end2 End iterator of second sequence. * @param target Target begin iterator. * @param max_length Maximum number of elements to merge. * @param comp Comparator. * @return Output end iterator. */ template inline RandomAccessIterator3 parallel_merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator2& begin2, // different iterators, parallel implementation // not available RandomAccessIterator2 end2, RandomAccessIterator3 target, typename std::iterator_traits:: difference_type max_length, Comparator comp) { return merge_advance(begin1, end1, begin2, end2, target, max_length, comp); } /** @brief Parallel merge routine being able to merge only the @c * max_length smallest elements. * * The @c begin iterators are advanced accordingly, they might not * reach @c end, in contrast to the usual variant. * The functionality is projected onto parallel_multiway_merge. * @param begin1 Begin iterator of first sequence. * @param end1 End iterator of first sequence. * @param begin2 Begin iterator of second sequence. * @param end2 End iterator of second sequence. * @param target Target begin iterator. * @param max_length Maximum number of elements to merge. * @param comp Comparator. * @return Output end iterator. */ template inline RandomAccessIterator3 parallel_merge_advance(RandomAccessIterator1& begin1, RandomAccessIterator1 end1, RandomAccessIterator1& begin2, RandomAccessIterator1 end2, RandomAccessIterator3 target, typename std::iterator_traits:: difference_type max_length, Comparator comp) { typedef typename std::iterator_traits::value_type value_type; typedef typename std::iterator_traits:: difference_type difference_type1 /* == difference_type2 */; typedef typename std::iterator_traits:: difference_type difference_type3; typedef typename std::pair iterator_pair; std::pair seqs[2] = { std::make_pair(begin1, end1), std::make_pair(begin2, end2) }; RandomAccessIterator3 target_end = parallel_multiway_merge < /* stable = */ true, /* sentinels = */ false>( seqs, seqs + 2, target, comp, multiway_merge_exact_splitting < /* stable = */ true, iterator_pair*, Comparator, difference_type1>, max_length); return target_end; } } //namespace __gnu_parallel #endif // -*- C++ -*- // Copyright (C) 2007, 2008 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. /** @file parallel/checkers.h * @brief Routines for checking the correctness of algorithm results. * This file is a GNU parallel extension to the Standard C++ Library. */ // Written by Johannes Singler. #ifndef _GLIBCXX_PARALLEL_CHECKERS #define _GLIBCXX_PARALLEL_CHECKERS 1 #include #include #include namespace __gnu_parallel { /** * @brief Check whether @c [begin, @c end) is sorted according to @c comp. * @param begin Begin iterator of sequence. * @param end End iterator of sequence. * @param comp Comparator. * @return @c true if sorted, @c false otherwise. */ // XXX Comparator default template argument template bool is_sorted(InputIterator begin, InputIterator end, Comparator comp = std::less:: value_type>()) { if (begin == end) return true; InputIterator current(begin), recent(begin); unsigned long long position = 1; for (current++; current != end; current++) { if (comp(*current, *recent)) { printf("is_sorted: check failed before position %i.\n", position); return false; } recent = current; position++; } return true; } /** * @brief Check whether @c [begin, @c end) is sorted according to @c comp. * Prints the position in case an unordered pair is found. * @param begin Begin iterator of sequence. * @param end End iterator of sequence. * @param first_failure The first failure is returned in this variable. * @param comp Comparator. * @return @c true if sorted, @c false otherwise. */ // XXX Comparator default template argument template bool is_sorted_failure(InputIterator begin, InputIterator end, InputIterator& first_failure, Comparator comp = std::less:: value_type>()) { if (begin == end) return true; InputIterator current(begin), recent(begin); unsigned long long position = 1; for (current++; current != end; current++) { if (comp(*current, *recent)) { first_failure = current; printf("is_sorted: check failed before position %lld.\n", position); return false; } recent = current; position++; } first_failure = end; return true; } /** * @brief Check whether @c [begin, @c end) is sorted according to @c comp. * Prints all unordered pair, including the surrounding two elements. * @param begin Begin iterator of sequence. * @param end End iterator of sequence. * @param comp Comparator. * @return @c true if sorted, @c false otherwise. */ template bool // XXX Comparator default template argument is_sorted_print_failures(InputIterator begin, InputIterator end, Comparator comp = std::less::value_type>()) { if (begin == end) return true; InputIterator recent(begin); bool ok = true; for (InputIterator pos(begin + 1); pos != end; pos++) { if (comp(*pos, *recent)) { printf("%ld: %d %d %d %d\n", pos - begin, *(pos - 2), *(pos- 1), *pos, *(pos + 1)); ok = false; } recent = pos; } return ok; } } #endif // -*- C++ -*- // Copyright (C) 2007 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. /** @file parallel/compiletime_settings.h * @brief Defines on options concerning debugging and performance, at * compile-time. * This file is a GNU parallel extension to the Standard C++ Library. */ // Written by Johannes Singler. #include /** @brief Determine verbosity level of the parallel mode. * Level 1 prints a message each time a parallel-mode function is entered. */ #define _GLIBCXX_VERBOSE_LEVEL 0 /** @def _GLIBCXX_CALL * @brief Macro to produce log message when entering a function. * @param n Input size. * @see _GLIBCXX_VERBOSE_LEVEL */ #if (_GLIBCXX_VERBOSE_LEVEL == 0) #define _GLIBCXX_CALL(n) #endif #if (_GLIBCXX_VERBOSE_LEVEL == 1) #define _GLIBCXX_CALL(n) \ printf(" %s:\niam = %d, n = %ld, num_threads = %d\n", \ __PRETTY_FUNCTION__, omp_get_thread_num(), (n), get_max_threads()); #endif #ifndef _GLIBCXX_SCALE_DOWN_FPU /** @brief Use floating-point scaling instead of modulo for mapping * random numbers to a range. This can be faster on certain CPUs. */ #define _GLIBCXX_SCALE_DOWN_FPU 0 #endif #ifndef _GLIBCXX_ASSERTIONS /** @brief Switch on many _GLIBCXX_PARALLEL_ASSERTions in parallel code. * Should be switched on only locally. */ #define _GLIBCXX_ASSERTIONS 0 #endif #ifndef _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1 /** @brief Switch on many _GLIBCXX_PARALLEL_ASSERTions in parallel code. * Consider the size of the L1 cache for * __gnu_parallel::parallel_random_shuffle(). */ #define _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_L1 0 #endif #ifndef _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB /** @brief Switch on many _GLIBCXX_PARALLEL_ASSERTions in parallel code. * Consider the size of the TLB for * __gnu_parallel::parallel_random_shuffle(). */ #define _GLIBCXX_RANDOM_SHUFFLE_CONSIDER_TLB 0 #endif // parallel extensions -*- C++ -*- // Copyright (C) 2007, 2008 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. /** @file parallel/algorithmfwd.h * This file is a GNU parallel extension to the Standard C++ Library. */ #ifndef _GLIBCXX_PARALLEL_ALGORITHMFWD_H #define _GLIBCXX_PARALLEL_ALGORITHMFWD_H 1 #pragma GCC system_header #include #include namespace std { namespace __parallel { template _FIter adjacent_find(_FIter, _FIter); template _FIter adjacent_find(_FIter, _FIter, __gnu_parallel::sequential_tag); template _FIter adjacent_find_switch(_FIter, _FIter, _IterTag); template _RAIter adjacent_find_switch(_RAIter, _RAIter, random_access_iterator_tag); template _FIter adjacent_find(_FIter, _FIter, _BiPredicate); template _FIter adjacent_find(_FIter, _FIter, _BiPredicate, __gnu_parallel::sequential_tag); template _FIter adjacent_find_switch(_FIter, _FIter, _BiPredicate, _IterTag); template _RAIter adjacent_find_switch(_RAIter, _RAIter, _BiPredicate, random_access_iterator_tag); template typename iterator_traits<_IIter>::difference_type count(_IIter, _IIter, const _Tp&); template typename iterator_traits<_IIter>::difference_type count(_IIter, _IIter, const _Tp&, __gnu_parallel::sequential_tag); template typename iterator_traits<_IIter>::difference_type count(_IIter, _IIter, const _Tp&, __gnu_parallel::_Parallelism); template typename iterator_traits<_IIter>::difference_type count_switch(_IIter, _IIter, const _Tp&, _IterTag); template typename iterator_traits<_RAIter>::difference_type count_switch(_RAIter, _RAIter, const _Tp&, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_unbalanced); template typename iterator_traits<_IIter>::difference_type count_if(_IIter, _IIter, _Predicate); template typename iterator_traits<_IIter>::difference_type count_if(_IIter, _IIter, _Predicate, __gnu_parallel::sequential_tag); template typename iterator_traits<_IIter>::difference_type count_if(_IIter, _IIter, _Predicate, __gnu_parallel::_Parallelism); template typename iterator_traits<_IIter>::difference_type count_if_switch(_IIter, _IIter, _Predicate, _IterTag); template typename iterator_traits<_RAIter>::difference_type count_if_switch(_RAIter, _RAIter, _Predicate, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_unbalanced); // algobase.h template bool equal(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag); template bool equal(_IIter1, _IIter1, _IIter2, Predicate, __gnu_parallel::sequential_tag); template bool equal(_IIter1, _IIter1, _IIter2); template bool equal(_IIter1, _IIter1, _IIter2, Predicate); template _IIter find(_IIter, _IIter, const _Tp&, __gnu_parallel::sequential_tag); template _IIter find(_IIter, _IIter, const _Tp& val); template _IIter find_switch(_IIter, _IIter, const _Tp&, _IterTag); template _RAIter find_switch(_RAIter, _RAIter, const _Tp&, random_access_iterator_tag); template _IIter find_if(_IIter, _IIter, _Predicate, __gnu_parallel::sequential_tag); template _IIter find_if(_IIter, _IIter, _Predicate); template _IIter find_if_switch(_IIter, _IIter, _Predicate, _IterTag); template _RAIter find_if_switch(_RAIter, _RAIter, _Predicate, random_access_iterator_tag); template _IIter find_first_of(_IIter, _IIter, _FIter, _FIter, __gnu_parallel::sequential_tag); template _IIter find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate, __gnu_parallel::sequential_tag); template _IIter find_first_of(_IIter, _IIter, _FIter, _FIter, _BiPredicate); template _IIter find_first_of(_IIter, _IIter, _FIter, _FIter); template _IIter find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _IterTag1, _IterTag2); template _RAIter find_first_of_switch(_RAIter, _RAIter, _FIter, _FIter, _BiPredicate, random_access_iterator_tag, _IterTag); template _IIter find_first_of_switch(_IIter, _IIter, _FIter, _FIter, _BiPredicate, _IterTag1, _IterTag2); template _Function for_each(_IIter, _IIter, _Function); template _Function for_each(_IIter, _IIter, _Function, __gnu_parallel::sequential_tag); template _Function for_each(_Iterator, _Iterator, _Function, __gnu_parallel::_Parallelism); template _Function for_each_switch(_IIter, _IIter, _Function, _IterTag); template _Function for_each_switch(_RAIter, _RAIter, _Function, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_balanced); template void generate(_FIter, _FIter, _Generator); template void generate(_FIter, _FIter, _Generator, __gnu_parallel::sequential_tag); template void generate(_FIter, _FIter, _Generator, __gnu_parallel::_Parallelism); template void generate_switch(_FIter, _FIter, _Generator, _IterTag); template void generate_switch(_RAIter, _RAIter, _Generator, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_balanced); template _OIter generate_n(_OIter, _Size, _Generator); template _OIter generate_n(_OIter, _Size, _Generator, __gnu_parallel::sequential_tag); template _OIter generate_n(_OIter, _Size, _Generator, __gnu_parallel::_Parallelism); template _OIter generate_n_switch(_OIter, _Size, _Generator, _IterTag); template _RAIter generate_n_switch(_RAIter, _Size, _Generator, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_balanced); template bool lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, __gnu_parallel::sequential_tag); template bool lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Predicate, __gnu_parallel::sequential_tag); template bool lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2); template bool lexicographical_compare(_IIter1, _IIter1, _IIter2, _IIter2, _Predicate); template bool lexicographical_compare_switch(_IIter1, _IIter1, _IIter2, _IIter2, _Predicate, _IterTag1, _IterTag2); template bool lexicographical_compare_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _Predicate, random_access_iterator_tag, random_access_iterator_tag); // algo.h template pair<_IIter1, _IIter2> mismatch(_IIter1, _IIter1, _IIter2, __gnu_parallel::sequential_tag); template pair<_IIter1, _IIter2> mismatch(_IIter1, _IIter1, _IIter2, _Predicate, __gnu_parallel::sequential_tag); template pair<_IIter1, _IIter2> mismatch(_IIter1, _IIter1, _IIter2); template pair<_IIter1, _IIter2> mismatch(_IIter1, _IIter1, _IIter2, _Predicate); template pair<_IIter1, _IIter2> mismatch_switch(_IIter1, _IIter1, _IIter2, _Predicate, _IterTag1, _IterTag2); template pair<_RAIter1, _RAIter2> mismatch_switch(_RAIter1, _RAIter1, _RAIter2, _Predicate, random_access_iterator_tag, random_access_iterator_tag); template _FIter1 search(_FIter1, _FIter1, _FIter2, _FIter2, __gnu_parallel::sequential_tag); template _FIter1 search(_FIter1, _FIter1, _FIter2, _FIter2); template _FIter1 search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate, __gnu_parallel::sequential_tag); template _FIter1 search(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate); template _RAIter1 search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, random_access_iterator_tag, random_access_iterator_tag); template _FIter1 search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _IterTag1, _IterTag2); template _RAIter1 search_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _BiPredicate, random_access_iterator_tag, random_access_iterator_tag); template _FIter1 search_switch(_FIter1, _FIter1, _FIter2, _FIter2, _BiPredicate, _IterTag1, _IterTag2); template _FIter search_n(_FIter, _FIter, _Integer, const _Tp&, __gnu_parallel::sequential_tag); template _FIter search_n(_FIter, _FIter, _Integer, const _Tp&, _BiPredicate, __gnu_parallel::sequential_tag); template _FIter search_n(_FIter, _FIter, _Integer, const _Tp&); template _FIter search_n(_FIter, _FIter, _Integer, const _Tp&, _BiPredicate); template _RAIter search_n_switch(_RAIter, _RAIter, _Integer, const _Tp&, _BiPredicate, random_access_iterator_tag); template _FIter search_n_switch(_FIter, _FIter, _Integer, const _Tp&, _BiPredicate, _IterTag); template _OIter transform(_IIter, _IIter, _OIter, UnaryOperation); template _OIter transform(_IIter, _IIter, _OIter, UnaryOperation, __gnu_parallel::sequential_tag); template _OIter transform(_IIter, _IIter, _OIter, UnaryOperation, __gnu_parallel::_Parallelism); template _OIter transform1_switch(_IIter, _IIter, _OIter, UnaryOperation, _IterTag1, _IterTag2); template _RAOIter transform1_switch(_RAIIter, _RAIIter, _RAOIter, UnaryOperation, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_balanced); template _OIter transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation); template _OIter transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation, __gnu_parallel::sequential_tag); template _OIter transform(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation, __gnu_parallel::_Parallelism); template _RAIter3 transform2_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter3, _BiOperation, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_balanced); template _OIter transform2_switch(_IIter1, _IIter1, _IIter2, _OIter, _BiOperation, _Tag1, _Tag2, _Tag3); template void replace(_FIter, _FIter, const _Tp&, const _Tp&); template void replace(_FIter, _FIter, const _Tp&, const _Tp&, __gnu_parallel::sequential_tag); template void replace(_FIter, _FIter, const _Tp&, const _Tp&, __gnu_parallel::_Parallelism); template void replace_switch(_FIter, _FIter, const _Tp&, const _Tp&, _IterTag); template void replace_switch(_RAIter, _RAIter, const _Tp&, const _Tp&, random_access_iterator_tag, __gnu_parallel::_Parallelism); template void replace_if(_FIter, _FIter, _Predicate, const _Tp&); template void replace_if(_FIter, _FIter, _Predicate, const _Tp&, __gnu_parallel::sequential_tag); template void replace_if(_FIter, _FIter, _Predicate, const _Tp&, __gnu_parallel::_Parallelism); template void replace_if_switch(_FIter, _FIter, _Predicate, const _Tp&, _IterTag); template void replace_if_switch(_RAIter, _RAIter, _Predicate, const _Tp&, random_access_iterator_tag, __gnu_parallel::_Parallelism); template _FIter max_element(_FIter, _FIter); template _FIter max_element(_FIter, _FIter, __gnu_parallel::sequential_tag); template _FIter max_element(_FIter, _FIter, __gnu_parallel::_Parallelism); template _FIter max_element(_FIter, _FIter, _Compare); template _FIter max_element(_FIter, _FIter, _Compare, __gnu_parallel::sequential_tag); template _FIter max_element(_FIter, _FIter, _Compare, __gnu_parallel::_Parallelism); template _FIter max_element_switch(_FIter, _FIter, _Compare, _IterTag); template _RAIter max_element_switch(_RAIter, _RAIter, _Compare, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_balanced); template _OIter merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag); template _OIter merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare, __gnu_parallel::sequential_tag); template _OIter merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare); template _OIter merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); template _OIter merge_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare, _IterTag1, _IterTag2, _IterTag3); template _OIter merge_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag); template _FIter min_element(_FIter, _FIter); template _FIter min_element(_FIter, _FIter, __gnu_parallel::sequential_tag); template _FIter min_element(_FIter, _FIter, __gnu_parallel::_Parallelism parallelism_tag); template _FIter min_element(_FIter, _FIter, _Compare); template _FIter min_element(_FIter, _FIter, _Compare, __gnu_parallel::sequential_tag); template _FIter min_element(_FIter, _FIter, _Compare, __gnu_parallel::_Parallelism); template _FIter min_element_switch(_FIter, _FIter, _Compare, _IterTag); template _RAIter min_element_switch(_RAIter, _RAIter, _Compare, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_balanced); template void nth_element(_RAIter, _RAIter, _RAIter, __gnu_parallel::sequential_tag); template void nth_element(_RAIter, _RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag); template void nth_element(_RAIter, _RAIter, _RAIter, _Compare); template void nth_element(_RAIter, _RAIter, _RAIter); template void partial_sort(_RAIter, _RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag); template void partial_sort(_RAIter, _RAIter, _RAIter, __gnu_parallel::sequential_tag); template void partial_sort(_RAIter, _RAIter, _RAIter, _Compare); template void partial_sort(_RAIter, _RAIter, _RAIter); template _FIter partition(_FIter, _FIter, Predicate, __gnu_parallel::sequential_tag); template _FIter partition(_FIter, _FIter, Predicate); template _FIter partition_switch(_FIter, _FIter, Predicate, _IterTag); template _RAIter partition_switch(_RAIter, _RAIter, Predicate, random_access_iterator_tag); template void random_shuffle(_RAIter, _RAIter, __gnu_parallel::sequential_tag); template void random_shuffle(_RAIter, _RAIter, _RandomNumberGenerator&, __gnu_parallel::sequential_tag); template void random_shuffle(_RAIter, _RAIter); template void random_shuffle(_RAIter, _RAIter, _RandomNumberGenerator&); template _OIter set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag); template _OIter set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, Predicate, __gnu_parallel::sequential_tag); template _OIter set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); template _OIter set_union(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate); template _OIter set_union_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate, _IterTag1, _IterTag2, _IterTag3); template _Output_RAIter set_union_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _Output_RAIter, _Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag); template _OIter set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag); template _OIter set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate, __gnu_parallel::sequential_tag); template _OIter set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); template _OIter set_intersection(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate); template _OIter set_intersection_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate, _IterTag1, _IterTag2, _IterTag3); template _Output_RAIter set_intersection_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _Output_RAIter, _Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag); template _OIter set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag); template _OIter set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate, __gnu_parallel::sequential_tag); template _OIter set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); template _OIter set_symmetric_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate); template _OIter set_symmetric_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate, _IterTag1, _IterTag2, _IterTag3); template _Output_RAIter set_symmetric_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _Output_RAIter, _Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag); template _OIter set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, __gnu_parallel::sequential_tag); template _OIter set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate, __gnu_parallel::sequential_tag); template _OIter set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter); template _OIter set_difference(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate); template _OIter set_difference_switch(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Predicate, _IterTag1, _IterTag2, _IterTag3); template _Output_RAIter set_difference_switch(_RAIter1, _RAIter1, _RAIter2, _RAIter2, _Output_RAIter, _Predicate, random_access_iterator_tag, random_access_iterator_tag, random_access_iterator_tag); template void sort(_RAIter, _RAIter, __gnu_parallel::sequential_tag); template void sort(_RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag); template void sort(_RAIter, _RAIter); template void sort(_RAIter, _RAIter, _Compare); template void stable_sort(_RAIter, _RAIter, __gnu_parallel::sequential_tag); template void stable_sort(_RAIter, _RAIter, _Compare, __gnu_parallel::sequential_tag); template void stable_sort(_RAIter, _RAIter); template void stable_sort(_RAIter, _RAIter, _Compare); template _OIter unique_copy(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag); template _OIter unique_copy(_IIter, _IIter, _OIter, _Predicate, __gnu_parallel::sequential_tag); template _OIter unique_copy(_IIter, _IIter, _OIter); template _OIter unique_copy(_IIter, _IIter, _OIter, _Predicate); template _OIter unique_copy_switch(_IIter, _IIter, _OIter, _Predicate, _IterTag1, _IterTag2); template _RandomAccess_OIter unique_copy_switch(_RAIter, _RAIter, _RandomAccess_OIter, _Predicate, random_access_iterator_tag, random_access_iterator_tag); } // end namespace __parallel } // end namespace std #endif // -*- C++ -*- // Copyright (C) 2007 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 2, 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. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. /** @file parallel/basic_iterator.h * @brief Includes the original header files concerned with iterators * except for stream iterators. * This file is a GNU parallel extension to the Standard C++ Library. */ // Written by Johannes Singler. #ifndef _GLIBCXX_PARALLEL_BASIC_ITERATOR_H #define _GLIBCXX_PARALLEL_BASIC_ITERATOR_H 1 #include #include #include #include #include #endif /* _GLIBCXX_BASIC_ITERATOR_H */