111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2007-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the terms 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the GNU General Public License as published by the Free Software 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Foundation; either version 3, or (at your option) any later 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, but 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** @file parallel/merge.h 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Parallel implementation of std::merge(). 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This file is a GNU parallel extension to the Standard C++ Library. 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Written by Johannes Singler. 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef _GLIBCXX_PARALLEL_MERGE_H 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define _GLIBCXX_PARALLEL_MERGE_H 1 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <parallel/basic_iterator.h> 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <bits/stl_algo.h> 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_parallel 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Merge routine being able to merge only the @c __max_length 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * smallest elements. 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * The @c __begin iterators are advanced accordingly, they might not 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * reach @c __end, in contrast to the usual variant. 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end2 End iterator of second sequence. 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __target Target begin iterator. 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __max_length Maximum number of elements to merge. 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __comp Comparator. 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @return Output end iterator. */ 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _OutputIterator, typename _DifferenceTp, 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Compare> 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _OutputIterator 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __merge_advance_usual(_RAIter1& __begin1, _RAIter1 __end1, 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2& __begin2, _RAIter2 __end2, 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _OutputIterator __target, 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceTp __max_length, _Compare __comp) 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _DifferenceTp _DifferenceType; 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0) 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // array1[__i1] < array0[i0] 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__comp(*__begin2, *__begin1)) 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert *__target++ = *__begin2++; 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert *__target++ = *__begin1++; 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert --__max_length; 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__begin1 != __end1) 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __target = std::copy(__begin1, __begin1 + __max_length, __target); 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin1 += __max_length; 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __target = std::copy(__begin2, __begin2 + __max_length, __target); 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin2 += __max_length; 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __target; 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Merge routine being able to merge only the @c __max_length 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * smallest elements. 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * The @c __begin iterators are advanced accordingly, they might not 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * reach @c __end, in contrast to the usual variant. 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Specially designed code should allow the compiler to generate 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * conditional moves instead of branches. 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end2 End iterator of second sequence. 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __target Target begin iterator. 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __max_length Maximum number of elements to merge. 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __comp Comparator. 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @return Output end iterator. */ 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _OutputIterator, typename _DifferenceTp, 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Compare> 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _OutputIterator 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __merge_advance_movc(_RAIter1& __begin1, _RAIter1 __end1, 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2& __begin2, _RAIter2 __end2, 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _OutputIterator __target, 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _DifferenceTp __max_length, _Compare __comp) 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _DifferenceTp _DifferenceType; 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_RAIter1>::value_type 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ValueType1; 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_RAIter2>::value_type 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ValueType2; 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if _GLIBCXX_ASSERTIONS 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_PARALLEL_ASSERT(__max_length >= 0); 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__begin1 != __end1 && __begin2 != __end2 && __max_length > 0) 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter1 __next1 = __begin1 + 1; 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __next2 = __begin2 + 1; 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ValueType1 __element1 = *__begin1; 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _ValueType2 __element2 = *__begin2; 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__comp(__element2, __element1)) 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __element1 = __element2; 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin2 = __next2; 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin1 = __next1; 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert *__target = __element1; 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__target; 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert --__max_length; 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__begin1 != __end1) 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __target = std::copy(__begin1, __begin1 + __max_length, __target); 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin1 += __max_length; 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __target = std::copy(__begin2, __begin2 + __max_length, __target); 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __begin2 += __max_length; 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __target; 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Merge routine being able to merge only the @c __max_length 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * smallest elements. 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * The @c __begin iterators are advanced accordingly, they might not 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * reach @c __end, in contrast to the usual variant. 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Static switch on whether to use the conditional-move variant. 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end2 End iterator of second sequence. 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __target Target begin iterator. 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __max_length Maximum number of elements to merge. 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __comp Comparator. 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @return Output end iterator. */ 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _OutputIterator, typename _DifferenceTp, 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Compare> 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline _OutputIterator 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __merge_advance(_RAIter1& __begin1, _RAIter1 __end1, 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2& __begin2, _RAIter2 __end2, 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _OutputIterator __target, _DifferenceTp __max_length, 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Compare __comp) 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_CALL(__max_length) 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __merge_advance_movc(__begin1, __end1, __begin2, __end2, 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __target, __max_length, __comp); 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Merge routine fallback to sequential in case the 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert iterators of the two input sequences are of different type. 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end2 End iterator of second sequence. 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __target Target begin iterator. 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __max_length Maximum number of elements to merge. 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __comp Comparator. 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @return Output end iterator. */ 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter2, 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _RAIter3, typename _Compare> 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline _RAIter3 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __parallel_merge_advance(_RAIter1& __begin1, _RAIter1 __end1, 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2& __begin2, 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // different iterators, parallel implementation 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // not available 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter2 __end2, _RAIter3 __target, typename 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::iterator_traits<_RAIter1>:: 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert difference_type __max_length, _Compare __comp) 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return __merge_advance(__begin1, __end1, __begin2, __end2, __target, 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __max_length, __comp); } 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** @brief Parallel merge routine being able to merge only the @c 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * __max_length smallest elements. 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * The @c __begin iterators are advanced accordingly, they might not 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * reach @c __end, in contrast to the usual variant. 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * The functionality is projected onto parallel_multiway_merge. 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin1 Begin iterator of first sequence. 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end1 End iterator of first sequence. 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __begin2 Begin iterator of second sequence. 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __end2 End iterator of second sequence. 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __target Target begin iterator. 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __max_length Maximum number of elements to merge. 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @param __comp Comparator. 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @return Output end iterator. 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename _RAIter1, typename _RAIter3, 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Compare> 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline _RAIter3 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __parallel_merge_advance(_RAIter1& __begin1, _RAIter1 __end1, 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter1& __begin2, _RAIter1 __end2, 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter3 __target, typename 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::iterator_traits<_RAIter1>:: 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert difference_type __max_length, _Compare __comp) 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::iterator_traits<_RAIter1>::value_type _ValueType; 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_RAIter1>:: 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert difference_type _DifferenceType1 /* == difference_type2 */; 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::iterator_traits<_RAIter3>:: 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert difference_type _DifferenceType3; 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename std::pair<_RAIter1, _RAIter1> 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _IteratorPair; 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _IteratorPair __seqs[2] = { std::make_pair(__begin1, __end1), 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::make_pair(__begin2, __end2) }; 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RAIter3 __target_end = parallel_multiway_merge 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert < /* __stable = */ true, /* __sentinels = */ false> 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (__seqs, __seqs + 2, __target, multiway_merge_exact_splitting 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert < /* __stable = */ true, _IteratorPair*, 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Compare, _DifferenceType1>, __max_length, __comp, 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert omp_get_max_threads()); 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __target_end; 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} //namespace __gnu_parallel 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* _GLIBCXX_PARALLEL_MERGE_H */ 252