// Wrapper of C-language FILE struct -*- C++ -*- // Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // 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. // // ISO C++ 14882: 27.8 File-based streams // /** @file basic_file.h * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ #ifndef _GLIBCXX_BASIC_FILE_STDIO_H #define _GLIBCXX_BASIC_FILE_STDIO_H 1 #pragma GCC system_header #include #include // for __c_lock and __c_file #include _GLIBCXX_BEGIN_NAMESPACE(std) // Generic declaration. template class __basic_file; // Specialization. template<> class __basic_file { // Underlying data source/sink. __c_file* _M_cfile; // True iff we opened _M_cfile, and thus must close it ourselves. bool _M_cfile_created; public: __basic_file(__c_lock* __lock = 0); __basic_file* open(const char* __name, ios_base::openmode __mode, int __prot = 0664); __basic_file* sys_open(__c_file* __file, ios_base::openmode); __basic_file* sys_open(int __fd, ios_base::openmode __mode); __basic_file* close(); bool is_open() const; int fd(); __c_file* file(); ~__basic_file(); streamsize xsputn(const char* __s, streamsize __n); streamsize xsputn_2(const char* __s1, streamsize __n1, const char* __s2, streamsize __n2); streamsize xsgetn(char* __s, streamsize __n); streamoff seekoff(streamoff __off, ios_base::seekdir __way); int sync(); streamsize showmanyc(); }; _GLIBCXX_END_NAMESPACE #endif // std::messages implementation details, generic version -*- C++ -*- // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // 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 messages_members.h * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ // // ISO C++ 14882: 22.2.7.1.2 messages virtual functions // // Written by Benjamin Kosnik _GLIBCXX_BEGIN_NAMESPACE(std) // Non-virtual member functions. template messages<_CharT>::messages(size_t __refs) : facet(__refs) { _M_c_locale_messages = _S_get_c_locale(); } template messages<_CharT>::messages(__c_locale, const char*, size_t __refs) : facet(__refs) { _M_c_locale_messages = _S_get_c_locale(); } template typename messages<_CharT>::catalog messages<_CharT>::open(const basic_string& __s, const locale& __loc, const char*) const { return this->do_open(__s, __loc); } // Virtual member functions. template messages<_CharT>::~messages() { _S_destroy_c_locale(_M_c_locale_messages); } template typename messages<_CharT>::catalog messages<_CharT>::do_open(const basic_string&, const locale&) const { return 0; } template typename messages<_CharT>::string_type messages<_CharT>::do_get(catalog, int, int, const string_type& __dfault) const { return __dfault; } template void messages<_CharT>::do_close(catalog) const { } // messages_byname template messages_byname<_CharT>::messages_byname(const char* __s, size_t __refs) : messages<_CharT>(__refs) { if (__builtin_strcmp(__s, "C") != 0 && __builtin_strcmp(__s, "POSIX") != 0) { this->_S_destroy_c_locale(this->_M_c_locale_messages); this->_S_create_c_locale(this->_M_c_locale_messages, __s); } } _GLIBCXX_END_NAMESPACE // Control various target specific ABI tweaks. Generic version. // Copyright (C) 2004, 2006, 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // 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 cxxabi_tweaks.h * The header provides an CPU-variable interface to the C++ ABI. */ #ifndef _CXXABI_TWEAKS_H #define _CXXABI_TWEAKS_H 1 #ifdef __cplusplus namespace __cxxabiv1 { extern "C" { #endif // The generic ABI uses the first byte of a 64-bit guard variable. #define _GLIBCXX_GUARD_TEST(x) (*(char *) (x) != 0) #define _GLIBCXX_GUARD_SET(x) *(char *) (x) = 1 #define _GLIBCXX_GUARD_BIT __guard_test_bit (0, 1) #define _GLIBCXX_GUARD_PENDING_BIT __guard_test_bit (1, 1) #define _GLIBCXX_GUARD_WAITING_BIT __guard_test_bit (2, 1) __extension__ typedef int __guard __attribute__((mode (__DI__))); // __cxa_vec_ctor has void return type. typedef void __cxa_vec_ctor_return_type; #define _GLIBCXX_CXA_VEC_CTOR_RETURN(x) return // Constructors and destructors do not return a value. typedef void __cxa_cdtor_return_type; #ifdef __cplusplus } } // namespace __cxxabiv1 #endif #endif // Low-level type for atomic operations -*- C++ -*- // Copyright (C) 2004 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // 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 atomic_word.h * This file is a GNU extension to the Standard C++ Library. */ #ifndef _GLIBCXX_ATOMIC_WORD_H #define _GLIBCXX_ATOMIC_WORD_H 1 typedef int _Atomic_word; // Define these two macros using the appropriate memory barrier for the target. // The commented out versions below are the defaults. // See ia64/atomic_word.h for an alternative approach. // This one prevents loads from being hoisted across the barrier; // in other words, this is a Load-Load acquire barrier. // This is necessary iff TARGET_RELAXED_ORDERING is defined in tm.h. // #define _GLIBCXX_READ_MEM_BARRIER __asm __volatile ("":::"memory") // This one prevents stores from being sunk across the barrier; in other // words, a Store-Store release barrier. // #define _GLIBCXX_WRITE_MEM_BARRIER __asm __volatile ("":::"memory") #endif Q . ..R omp_loop.hSsearch.hTfind_selectors.hU numericfwd.hVmultiway_merge.hWalgo.hX partial_sum.hYmerge.hZ checkers.h[ compiletime_settings.h\algorithmfwd.h]basic_iterator.h^multiseq_selection.h_find.h`compatibility.haworkstealing.hbequally_split.hc partition.hd settings.he algorithmfqueue.hgnumerichset_operations.hirandom_shuffle.hj features.hkbalanced_quicksort.hl unique_copy.hmtypes.hn iterator.ho par_loop.hplist_partition.hqbase.hromp_loop_static.hs for_each.ht parallel.hu losertree.hvmultiway_mergesort.hwfor_each_selectors.hx quicksort.hysort.hzrandom_number.h{ algobase.h|\tags.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/omp_loop.h * @brief Parallelization of embarrassingly parallel execution by * means of an OpenMP for loop. * This file is a GNU parallel extension to the Standard C++ Library. */ // Written by Felix Putze. #ifndef _GLIBCXX_PARALLEL_OMP_LOOP_H #define _GLIBCXX_PARALLEL_OMP_LOOP_H 1 #include #include #include #include namespace __gnu_parallel { /** @brief Embarrassingly parallel algorithm for random access * iterators, using an OpenMP for loop. * * @param begin Begin iterator of element sequence. * @param end End iterator of element sequence. * @param o User-supplied functor (comparator, predicate, adding * functor, etc.). * @param f Functor to "process" an element with op (depends on * desired functionality, e. g. for std::for_each(), ...). * @param r Functor to "add" a single result to the already * processed elements (depends on functionality). * @param base Base value for reduction. * @param output Pointer to position where final result is written to * @param bound Maximum number of elements processed (e. g. for * std::count_n()). * @return User-supplied functor (that may contain a part of the result). */ template Op for_each_template_random_access_omp_loop(RandomAccessIterator begin, RandomAccessIterator end, Op o, Fu& f, Red r, Result base, Result& output, typename std::iterator_traits :: difference_type bound) { typedef typename std::iterator_traits::difference_type difference_type; difference_type length = end - begin; thread_index_t num_threads = __gnu_parallel::min(get_max_threads(), length); Result *thread_results; # pragma omp parallel num_threads(num_threads) { # pragma omp single { num_threads = omp_get_num_threads(); thread_results = new Result[num_threads]; for (thread_index_t i = 0; i < num_threads; ++i) thread_results[i] = Result(); } thread_index_t iam = omp_get_thread_num(); # pragma omp for schedule(dynamic, _Settings::get().workstealing_chunk_size) for (difference_type pos = 0; pos < length; ++pos) thread_results[iam] = r(thread_results[iam], f(o, begin+pos)); } //parallel for (thread_index_t i = 0; i < num_threads; ++i) output = r(output, thread_results[i]); delete [] thread_results; // Points to last element processed (needed as return value for // some algorithms like transform). f.finish_iterator = begin + length; return o; } } // end namespace #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/search.h * @brief Parallel implementation base for std::search() and * std::search_n(). * This file is a GNU parallel extension to the Standard C++ Library. */ // Written by Felix Putze. #ifndef _GLIBCXX_PARALLEL_SEARCH_H #define _GLIBCXX_PARALLEL_SEARCH_H 1 #include #include #include namespace __gnu_parallel { /** * @brief Precalculate advances for Knuth-Morris-Pratt algorithm. * @param elements Begin iterator of sequence to search for. * @param length Length of sequence to search for. * @param advances Returned offsets. */ template void calc_borders(RandomAccessIterator elements, _DifferenceTp length, _DifferenceTp* off) { typedef _DifferenceTp difference_type; off[0] = -1; if (length > 1) off[1] = 0; difference_type k = 0; for (difference_type j = 2; j <= length; j++) { while ((k >= 0) && !(elements[k] == elements[j-1])) k = off[k]; off[j] = ++k; } } // Generic parallel find algorithm (requires random access iterator). /** @brief Parallel std::search. * @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 pred Find predicate. * @return Place of finding in first sequences. */ template _RandomAccessIterator1 search_template(_RandomAccessIterator1 begin1, _RandomAccessIterator1 end1, _RandomAccessIterator2 begin2, _RandomAccessIterator2 end2, Pred pred) { typedef std::iterator_traits<_RandomAccessIterator1> traits_type; typedef typename traits_type::difference_type difference_type; _GLIBCXX_CALL((end1 - begin1) + (end2 - begin2)); difference_type pattern_length = end2 - begin2; // Pattern too short. if(pattern_length <= 0) return end1; // Last point to start search. difference_type input_length = (end1 - begin1) - pattern_length; // Where is first occurrence of pattern? defaults to end. difference_type result = (end1 - begin1); difference_type *splitters; // Pattern too long. if (input_length < 0) return end1; omp_lock_t result_lock; omp_init_lock(&result_lock); thread_index_t num_threads = std::max(1, std::min(input_length, get_max_threads())); difference_type advances[pattern_length]; calc_borders(begin2, pattern_length, advances); # pragma omp parallel num_threads(num_threads) { # pragma omp single { num_threads = omp_get_num_threads(); splitters = new difference_type[num_threads + 1]; equally_split(input_length, num_threads, splitters); } thread_index_t iam = omp_get_thread_num(); difference_type start = splitters[iam], stop = splitters[iam + 1]; difference_type pos_in_pattern = 0; bool found_pattern = false; while (start <= stop && !found_pattern) { // Get new value of result. #pragma omp flush(result) // No chance for this thread to find first occurrence. if (result < start) break; while (pred(begin1[start + pos_in_pattern], begin2[pos_in_pattern])) { ++pos_in_pattern; if (pos_in_pattern == pattern_length) { // Found new candidate for result. omp_set_lock(&result_lock); result = std::min(result, start); omp_unset_lock(&result_lock); found_pattern = true; break; } } // Make safe jump. start += (pos_in_pattern - advances[pos_in_pattern]); pos_in_pattern = (advances[pos_in_pattern] < 0) ? 0 : advances[pos_in_pattern]; } } //parallel omp_destroy_lock(&result_lock); delete[] splitters; // Return iterator on found element. return (begin1 + result); } } // end namespace #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/find_selectors.h * @brief Function objects representing different tasks to be plugged * into the parallel find algorithm. * This file is a GNU parallel extension to the Standard C++ Library. */ // Written by Felix Putze. #ifndef _GLIBCXX_PARALLEL_FIND_FUNCTIONS_H #define _GLIBCXX_PARALLEL_FIND_FUNCTIONS_H 1 #include #include #include namespace __gnu_parallel { /** @brief Base class of all __gnu_parallel::find_template selectors. */ struct generic_find_selector { }; /** * @brief Test predicate on a single element, used for std::find() * and std::find_if (). */ struct find_if_selector : public generic_find_selector { /** @brief Test on one position. * @param i1 Iterator on first sequence. * @param i2 Iterator on second sequence (unused). * @param pred Find predicate. */ template bool operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred) { return pred(*i1); } /** @brief Corresponding sequential algorithm on a sequence. * @param begin1 Begin iterator of first sequence. * @param end1 End iterator of first sequence. * @param begin2 Begin iterator of second sequence. * @param pred Find predicate. */ template std::pair sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred) { return std::make_pair(find_if(begin1, end1, pred, sequential_tag()), begin2); } }; /** @brief Test predicate on two adjacent elements. */ struct adjacent_find_selector : public generic_find_selector { /** @brief Test on one position. * @param i1 Iterator on first sequence. * @param i2 Iterator on second sequence (unused). * @param pred Find predicate. */ template bool operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred) { // Passed end iterator is one short. return pred(*i1, *(i1 + 1)); } /** @brief Corresponding sequential algorithm on a sequence. * @param begin1 Begin iterator of first sequence. * @param end1 End iterator of first sequence. * @param begin2 Begin iterator of second sequence. * @param pred Find predicate. */ template std::pair sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred) { // Passed end iterator is one short. RandomAccessIterator1 spot = adjacent_find(begin1, end1 + 1, pred, sequential_tag()); if (spot == (end1 + 1)) spot = end1; return std::make_pair(spot, begin2); } }; /** @brief Test inverted predicate on a single element. */ struct mismatch_selector : public generic_find_selector { /** * @brief Test on one position. * @param i1 Iterator on first sequence. * @param i2 Iterator on second sequence (unused). * @param pred Find predicate. */ template bool operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred) { return !pred(*i1, *i2); } /** * @brief Corresponding sequential algorithm on a sequence. * @param begin1 Begin iterator of first sequence. * @param end1 End iterator of first sequence. * @param begin2 Begin iterator of second sequence. * @param pred Find predicate. */ template std::pair sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred) { return mismatch(begin1, end1, begin2, pred, sequential_tag()); } }; /** @brief Test predicate on several elements. */ template struct find_first_of_selector : public generic_find_selector { ForwardIterator begin; ForwardIterator end; explicit find_first_of_selector(ForwardIterator begin, ForwardIterator end) : begin(begin), end(end) { } /** @brief Test on one position. * @param i1 Iterator on first sequence. * @param i2 Iterator on second sequence (unused). * @param pred Find predicate. */ template bool operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred) { for (ForwardIterator pos_in_candidates = begin; pos_in_candidates != end; ++pos_in_candidates) if (pred(*i1, *pos_in_candidates)) return true; return false; } /** @brief Corresponding sequential algorithm on a sequence. * @param begin1 Begin iterator of first sequence. * @param end1 End iterator of first sequence. * @param begin2 Begin iterator of second sequence. * @param pred Find predicate. */ template std::pair sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred) { return std::make_pair(find_first_of(begin1, end1, begin, end, pred, sequential_tag()), begin2); } }; } #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/numericfwd.h * This file is a GNU parallel extension to the Standard C++ Library. */ #ifndef _GLIBCXX_PARALLEL_NUMERICFWD_H #define _GLIBCXX_PARALLEL_NUMERICFWD_H 1 #pragma GCC system_header #include #include namespace std { namespace __parallel { template _Tp accumulate(_IIter, _IIter, _Tp); template _Tp accumulate(_IIter, _IIter, _Tp, __gnu_parallel::sequential_tag); template _Tp accumulate(_IIter, _IIter, _Tp, __gnu_parallel::_Parallelism); template _Tp accumulate_switch(_IIter, _IIter, _Tp, _Tag); template _Tp accumulate(_IIter, _IIter, _Tp, _BinaryOper); template _Tp accumulate(_IIter, _IIter, _Tp, _BinaryOper, __gnu_parallel::sequential_tag); template _Tp accumulate(_IIter, _IIter, _Tp, _BinaryOper, __gnu_parallel::_Parallelism); template _Tp accumulate_switch(_IIter, _IIter, _Tp, _BinaryOper, _Tag); template _Tp accumulate_switch(_RAIter, _RAIter, _Tp, _BinaryOper, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_unbalanced); template _OIter adjacent_difference(_IIter, _IIter, _OIter); template _OIter adjacent_difference(_IIter, _IIter, _OIter, _BinaryOper); template _OIter adjacent_difference(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag); template _OIter adjacent_difference(_IIter, _IIter, _OIter, _BinaryOper, __gnu_parallel::sequential_tag); template _OIter adjacent_difference(_IIter, _IIter, _OIter, __gnu_parallel::_Parallelism); template _OIter adjacent_difference(_IIter, _IIter, _OIter, _BinaryOper, __gnu_parallel::_Parallelism); template _OIter adjacent_difference_switch(_IIter, _IIter, _OIter, _BinaryOper, _Tag1, _Tag2); template _OIter adjacent_difference_switch(_IIter, _IIter, _OIter, _BinaryOper, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::_Parallelism parallelism = __gnu_parallel::parallel_unbalanced); template _Tp inner_product(_IIter1, _IIter1, _IIter2, _Tp); template _Tp inner_product(_IIter1, _IIter1, _IIter2, _Tp, __gnu_parallel::sequential_tag); template _Tp inner_product(_IIter1, _IIter1, _IIter2, _Tp, __gnu_parallel::_Parallelism); template _Tp inner_product(_IIter1, _IIter1, _IIter2, _Tp, _BinaryFunction1, _BinaryFunction2); template _Tp inner_product(_IIter1, _IIter1, _IIter2, _Tp, _BinaryFunction1, _BinaryFunction2, __gnu_parallel::sequential_tag); template _Tp inner_product(_IIter1, _IIter1, _IIter2, _Tp, BinaryFunction1, BinaryFunction2, __gnu_parallel::_Parallelism); template _Tp inner_product_switch(_RAIter1, _RAIter1, _RAIter2, _Tp, BinaryFunction1, BinaryFunction2, random_access_iterator_tag, random_access_iterator_tag, __gnu_parallel::_Parallelism = __gnu_parallel::parallel_unbalanced); template _Tp inner_product_switch(_IIter1, _IIter1, _IIter2, _Tp, _BinaryFunction1, _BinaryFunction2, _Tag1, _Tag2); template _OIter partial_sum(_IIter, _IIter, _OIter, __gnu_parallel::sequential_tag); template _OIter partial_sum(_IIter, _IIter, _OIter, _BinaryOper, __gnu_parallel::sequential_tag); template _OIter partial_sum(_IIter, _IIter, _OIter result); template _OIter partial_sum(_IIter, _IIter, _OIter, _BinaryOper); template _OIter partial_sum_switch(_IIter, _IIter, _OIter, _BinaryOper, _Tag1, _Tag2); template _OIter partial_sum_switch(_IIter, _IIter, _OIter, _BinaryOper, random_access_iterator_tag, random_access_iterator_tag); } // end namespace } // end namespace #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/multiway_merge.h * @brief Implementation of sequential and parallel multiway merge. * * Explanations on the high-speed merging routines in the appendix of * * P. Sanders. * Fast priority queues for cached memory. * ACM Journal of Experimental Algorithmics, 5, 2000. * * This file is a GNU parallel extension to the Standard C++ Library. */ // Written by Johannes Singler and Manuel Holtgrewe. #ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H #define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H #include #include #include #include #include #if _GLIBCXX_ASSERTIONS #include #endif /** @brief Length of a sequence described by a pair of iterators. */ #define _GLIBCXX_PARALLEL_LENGTH(s) ((s).second - (s).first) namespace __gnu_parallel { // Announce guarded and unguarded iterator. template class guarded_iterator; // Making the arguments const references seems to dangerous, // the user-defined comparator might not be const. template inline bool operator<(guarded_iterator& bi1, guarded_iterator& bi2); template inline bool operator<=(guarded_iterator& bi1, guarded_iterator& bi2); /** @brief Iterator wrapper supporting an implicit supremum at the end * of the sequence, dominating all comparisons. * * The implicit supremum comes with a performance cost. * * Deriving from RandomAccessIterator is not possible since * RandomAccessIterator need not be a class. */ template class guarded_iterator { private: /** @brief Current iterator position. */ RandomAccessIterator current; /** @brief End iterator of the sequence. */ RandomAccessIterator end; /** @brief Comparator. */ Comparator& comp; public: /** @brief Constructor. Sets iterator to beginning of sequence. * @param begin Begin iterator of sequence. * @param end End iterator of sequence. * @param comp Comparator provided for associated overloaded * compare operators. */ guarded_iterator(RandomAccessIterator begin, RandomAccessIterator end, Comparator& comp) : current(begin), end(end), comp(comp) { } /** @brief Pre-increment operator. * @return This. */ guarded_iterator& operator++() { ++current; return *this; } /** @brief Dereference operator. * @return Referenced element. */ typename std::iterator_traits::value_type& operator*() { return *current; } /** @brief Convert to wrapped iterator. * @return Wrapped iterator. */ operator RandomAccessIterator() { return current; } friend bool operator< ( guarded_iterator& bi1, guarded_iterator& bi2); friend bool operator<= ( guarded_iterator& bi1, guarded_iterator& bi2); }; /** @brief Compare two elements referenced by guarded iterators. * @param bi1 First iterator. * @param bi2 Second iterator. * @return @c True if less. */ template inline bool operator<(guarded_iterator& bi1, guarded_iterator& bi2) { if (bi1.current == bi1.end) //bi1 is sup return bi2.current == bi2.end; //bi2 is not sup if (bi2.current == bi2.end) //bi2 is sup return true; return (bi1.comp)(*bi1, *bi2); //normal compare } /** @brief Compare two elements referenced by guarded iterators. * @param bi1 First iterator. * @param bi2 Second iterator. * @return @c True if less equal. */ template inline bool operator<=(guarded_iterator& bi1, guarded_iterator& bi2) { if (bi2.current == bi2.end) //bi1 is sup return bi1.current != bi1.end; //bi2 is not sup if (bi1.current == bi1.end) //bi2 is sup return false; return !(bi1.comp)(*bi2, *bi1); //normal compare } template class unguarded_iterator; template inline bool operator<(unguarded_iterator& bi1, unguarded_iterator& bi2); template inline bool operator<=(unguarded_iterator& bi1, unguarded_iterator& bi2); template class unguarded_iterator { private: /** @brief Current iterator position. */ RandomAccessIterator current; /** @brief Comparator. */ mutable Comparator& comp; public: /** @brief Constructor. Sets iterator to beginning of sequence. * @param begin Begin iterator of sequence. * @param end Unused, only for compatibility. * @param comp Unused, only for compatibility. */ unguarded_iterator(RandomAccessIterator begin, RandomAccessIterator end, Comparator& comp) : current(begin), comp(comp) { } /** @brief Pre-increment operator. * @return This. */ unguarded_iterator& operator++() { ++current; return *this; } /** @brief Dereference operator. * @return Referenced element. */ typename std::iterator_traits::value_type& operator*() { return *current; } /** @brief Convert to wrapped iterator. * @return Wrapped iterator. */ operator RandomAccessIterator() { return current; } friend bool operator< ( unguarded_iterator& bi1, unguarded_iterator& bi2); friend bool operator<= ( unguarded_iterator& bi1, unguarded_iterator& bi2); }; /** @brief Compare two elements referenced by unguarded iterators. * @param bi1 First iterator. * @param bi2 Second iterator. * @return @c True if less. */ template inline bool operator<(unguarded_iterator& bi1, unguarded_iterator& bi2) { // Normal compare. return (bi1.comp)(*bi1, *bi2); } /** @brief Compare two elements referenced by unguarded iterators. * @param bi1 First iterator. * @param bi2 Second iterator. * @return @c True if less equal. */ template inline bool operator<=(unguarded_iterator& bi1, unguarded_iterator& bi2) { // Normal compare. return !(bi1.comp)(*bi2, *bi1); } /** @brief Highly efficient 3-way merging procedure. * * Merging is done with the algorithm implementation described by Peter * Sanders. Basically, the idea is to minimize the number of necessary * comparison after merging out an element. The implementation trick * that makes this fast is that the order of the sequences is stored * in the instruction pointer (translated into labels in C++). * * This works well for merging up to 4 sequences. * * Note that making the merging stable does not come at a * performance hit. * * Whether the merging is done guarded or unguarded is selected by the * used iterator class. * * @param seqs_begin Begin iterator of iterator pair input sequence. * @param seqs_end End iterator of iterator pair input sequence. * @param target Begin iterator out output sequence. * @param comp Comparator. * @param length Maximum length to merge, less equal than the * total number of elements available. * * @return End iterator of output sequence. */ template class iterator, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 multiway_merge_3_variant( RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length) { _GLIBCXX_CALL(length); typedef _DifferenceTp difference_type; typedef typename std::iterator_traits ::value_type::first_type RandomAccessIterator1; typedef typename std::iterator_traits::value_type value_type; if (length == 0) return target; #if _GLIBCXX_ASSERTIONS _DifferenceTp orig_length = length; #endif iterator seq0(seqs_begin[0].first, seqs_begin[0].second, comp), seq1(seqs_begin[1].first, seqs_begin[1].second, comp), seq2(seqs_begin[2].first, seqs_begin[2].second, comp); if (seq0 <= seq1) { if (seq1 <= seq2) goto s012; else if (seq2 < seq0) goto s201; else goto s021; } else { if (seq1 <= seq2) { if (seq0 <= seq2) goto s102; else goto s120; } else goto s210; } #define _GLIBCXX_PARALLEL_MERGE_3_CASE(a,b,c,c0,c1) \ s ## a ## b ## c : \ *target = *seq ## a; \ ++target; \ --length; \ ++seq ## a; \ if (length == 0) goto finish; \ if (seq ## a c0 seq ## b) goto s ## a ## b ## c; \ if (seq ## a c1 seq ## c) goto s ## b ## a ## c; \ goto s ## b ## c ## a; _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=); _GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < ); _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < ); _GLIBCXX_PARALLEL_MERGE·#¸#¹#º#»#¼#½#¾#¿#À#Á#Â#Ã#Ä#Å#Æ#Ç#È#É#Ê#Ë#Ì#Í#Î#Ï#Ð#Ñ#Ò#Ó#Ô#Õ#Ö#×#Ø#Ù#Ú#Û#Ü#Ý#Þ#ß#à#á#â#ã#ä#å#æ#ç#è#é#ê#ë#ì#í#_3_CASE(1, 0, 2, < , <=); _GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=); _GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < ); #undef _GLIBCXX_PARALLEL_MERGE_3_CASE finish: ; #if _GLIBCXX_ASSERTIONS _GLIBCXX_PARALLEL_ASSERT( ((RandomAccessIterator1)seq0 - seqs_begin[0].first) + ((RandomAccessIterator1)seq1 - seqs_begin[1].first) + ((RandomAccessIterator1)seq2 - seqs_begin[2].first) == orig_length); #endif seqs_begin[0].first = seq0; seqs_begin[1].first = seq1; seqs_begin[2].first = seq2; return target; } /** * @brief Highly efficient 4-way merging procedure. * * Merging is done with the algorithm implementation described by Peter * Sanders. Basically, the idea is to minimize the number of necessary * comparison after merging out an element. The implementation trick * that makes this fast is that the order of the sequences is stored * in the instruction pointer (translated into goto labels in C++). * * This works well for merging up to 4 sequences. * * Note that making the merging stable does not come at a * performance hit. * * Whether the merging is done guarded or unguarded is selected by the * used iterator class. * * @param seqs_begin Begin iterator of iterator pair input sequence. * @param seqs_end End iterator of iterator pair input sequence. * @param target Begin iterator out output sequence. * @param comp Comparator. * @param length Maximum length to merge, less equal than the * total number of elements available. * * @return End iterator of output sequence. */ template class iterator, typename RandomAccessIteratorIterator, typename RandomAccessIterator3, typename _DifferenceTp, typename Comparator> RandomAccessIterator3 multiway_merge_4_variant(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length) { _GLIBCXX_CALL(length); typedef _DifferenceTp difference_type; typedef typename std::iterator_traits ::value_type::first_type RandomAccessIterator1; typedef typename std::iterator_traits::value_type value_type; iterator seq0(seqs_begin[0].first, seqs_begin[0].second, comp), seq1(seqs_begin[1].first, seqs_begin[1].second, comp), seq2(seqs_begin[2].first, seqs_begin[2].second, comp), seq3(seqs_begin[3].first, seqs_begin[3].second, comp); #define _GLIBCXX_PARALLEL_DECISION(a,b,c,d) { \ if (seq ## d < seq ## a) goto s ## d ## a ## b ## c; \ if (seq ## d < seq ## b) goto s ## a ## d ## b ## c; \ if (seq ## d < seq ## c) goto s ## a ## b ## d ## c; \ goto s ## a ## b ## c ## d; } if (seq0 <= seq1) { if (seq1 <= seq2) _GLIBCXX_PARALLEL_DECISION(0,1,2,3) else if (seq2 < seq0) _GLIBCXX_PARALLEL_DECISION(2,0,1,3) else _GLIBCXX_PARALLEL_DECISION(0,2,1,3) } else { if (seq1 <= seq2) { if (seq0 <= seq2) _GLIBCXX_PARALLEL_DECISION(1,0,2,3) else _GLIBCXX_PARALLEL_DECISION(1,2,0,3) } else _GLIBCXX_PARALLEL_DECISION(2,1,0,3) } #define _GLIBCXX_PARALLEL_MERGE_4_CASE(a,b,c,d,c0,c1,c2) \ s ## a ## b ## c ## d: \ if (length == 0) goto finish; \ *target = *seq ## a; \ ++target; \ --length; \ ++seq ## a; \ if (seq ## a c0 seq ## b) goto s ## a ## b ## c ## d; \ if (seq ## a c1 seq ## c) goto s ## b ## a ## c ## d; \ if (seq ## a c2 seq ## d) goto s ## b ## c ## a ## d; \ goto s ## b ## c ## d ## a; _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=); _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < ); _GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < ); #undef _GLIBCXX_PARALLEL_MERGE_4_CASE #undef _GLIBCXX_PARALLEL_DECISION finish: ; seqs_begin[0].first = seq0; seqs_begin[1].first = seq1; seqs_begin[2].first = seq2; seqs_begin[3].first = seq3; return target; } /** @brief Multi-way merging procedure for a high branching factor, * guarded case. * * This merging variant uses a LoserTree class as selected by LT. * * Stability is selected through the used LoserTree class LT. * * At least one non-empty sequence is required. * * @param seqs_begin Begin iterator of iterator pair input sequence. * @param seqs_end End iterator of iterator pair input sequence. * @param target Begin iterator out output sequence. * @param comp Comparator. * @param length Maximum length to merge, less equal than the * total number of elements available. * * @return End iterator of output sequence. */ template RandomAccessIterator3 multiway_merge_loser_tree(RandomAccessIteratorIterator seqs_begin, RandomAccessIteratorIterator seqs_end, RandomAccessIterator3 target, Comparator comp, _DifferenceTp length) { _GLIBCXX_CALL(length) typedef _DifferenceTp difference_type; typedef typename std::iterator_traits ::value_type::first_type RandomAccessIterator1; typedef typename std::iterator_traits::value_type value_type; int k = static_cast(seqs_end - seqs_begin); LT lt(k, comp); // Default value for potentially non-default-constructible types. value_type* arbitrary_element = NULL; for (int t = 0; t < k; ++t) { if(arbitrary_element == NULL && _GLIBCXX_PARALLEL_LENGTH(seqs_begin[t]) > 0) arbitrary_element = &(*seqs_begin[t].first); } for (int t = 0; t < k; ++t) { if (seqs_begin[t].first == seqs_begin[t].second) lt.insert_start(*arbitrary_element, t, true); else lt.insert_start(*seqs_begin[t].first, t, false); } lt.init(); int source; for (difference_type i = 0; i < length; ++i) { //take out source = lt.get_min_source(); *(target++) = *(seqs_begin[source].first++); // Feed. if (seqs_begin[source].first == seqs_begin[source].second) lt.delete_min_insert(*arbitrary_element, true); else // Replace from same source. lt.delete_min_insert(*seqs_begin[source].first, false); } return target; } /** @brief Multi-way merging procedure for a high branching factor, * unguarded case. * * Merging is done using the LoserTree class LT. * * Stability is selected by the used LoserTrees. * * @pre No input will run out of elements during the merge. * * @param seqs_begin Begin iterator of iterator pair input sequence. * @param seqs_end End iterator of iterator pair input sequence. * @param target Begin iterator out output sequence. * @param comp Comparator. * @param length Maximum length to merge, less equal than the * total number of elements available. * * @return End iterator of output sequence. */ template