WebSVN – Kolibri OS – Blame – /contrib/sdk/sources/libstdc++-v3/include/parallel/multiway_merge.h

Rev	Author	Line No.	Line
5134	serge	1	// -- C++ --
		2
		3	// Copyright (C) 2007-2013 Free Software Foundation, Inc.
		4	//
		5	// This file is part of the GNU ISO C++ Library. This library is free
		6	// software; you can redistribute it and/or modify it under the terms
		7	// of the GNU General Public License as published by the Free Software
		8	// Foundation; either version 3, or (at your option) any later
		9	// version.
		10
		11	// This library is distributed in the hope that it will be useful, but
		12	// WITHOUT ANY WARRANTY; without even the implied warranty of
		13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
		14	// General Public License for more details.
		15
		16	// Under Section 7 of GPL version 3, you are granted additional
		17	// permissions described in the GCC Runtime Library Exception, version
		18	// 3.1, as published by the Free Software Foundation.
		19
		20	// You should have received a copy of the GNU General Public License and
		21	// a copy of the GCC Runtime Library Exception along with this program;
		22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
		23	// .
		24
		25	/** @file parallel/multiway_merge.h
		26	* @brief Implementation of sequential and parallel multiway merge.
		27	*
		28	* Explanations on the high-speed merging routines in the appendix of
		29	*
		30	* P. Sanders.
		31	* Fast priority queues for cached memory.
		32	* ACM Journal of Experimental Algorithmics, 5, 2000.
		33	*
		34	* This file is a GNU parallel extension to the Standard C++ Library.
		35	*/
		36
		37	// Written by Johannes Singler and Manuel Holtgrewe.
		38
		39	#ifndef _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
		40	#define _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H
		41
		42	#include
		43
		44	#include
		45	#include
		46	#include
		47	#include
		48	#include
		49	#if _GLIBCXX_ASSERTIONS
		50	#include
		51	#endif
		52
		53	/** @brief Length of a sequence described by a pair of iterators. */
		54	#define _GLIBCXX_PARALLEL_LENGTH(__s) ((__s).second - (__s).first)
		55
		56	namespace __gnu_parallel
		57	{
		58	template
		59	typename _DifferenceTp, typename _Compare>
		60	_OutputIterator
		61	__merge_advance(_RAIter1&, _RAIter1, _RAIter2&, _RAIter2,
		62	_OutputIterator, _DifferenceTp, _Compare);
		63
		64	/** @brief _Iterator wrapper supporting an implicit supremum at the end
		65	* of the sequence, dominating all comparisons.
		66	*
		67	* The implicit supremum comes with a performance cost.
		68	*
		69	* Deriving from _RAIter is not possible since
		70	* _RAIter need not be a class.
		71	*/
		72	template
		73	class _GuardedIterator
		74	{
		75	private:
		76	/** @brief Current iterator __position. */
		77	_RAIter _M_current;
		78
		79	/** @brief End iterator of the sequence. */
		80	_RAIter _M_end;
		81
		82	/** @brief _Compare. */
		83	_Compare& __comp;
		84
		85	public:
		86	/** @brief Constructor. Sets iterator to beginning of sequence.
		87	* @param __begin Begin iterator of sequence.
		88	* @param __end End iterator of sequence.
		89	* @param __comp Comparator provided for associated overloaded
		90	* compare operators. */
		91	_GuardedIterator(_RAIter __begin, _RAIter __end, _Compare& __comp)
		92	: _M_current(__begin), _M_end(__end), __comp(__comp)
		93	{ }
		94
		95	/** @brief Pre-increment operator.
		96	* @return This. */
		97	_GuardedIterator<_RAIter, _Compare>&
		98	operator++()
		99	{
		100	++_M_current;
		101	return *this;
		102	}
		103
		104	/** @brief Dereference operator.
		105	* @return Referenced element. */
		106	typename std::iterator_traits<_RAIter>::value_type&
		107	operator*()
		108	{ return *_M_current; }
		109
		110	/** @brief Convert to wrapped iterator.
		111	* @return Wrapped iterator. */
		112	operator _RAIter()
		113	{ return _M_current; }
		114
		115	/** @brief Compare two elements referenced by guarded iterators.
		116	* @param __bi1 First iterator.
		117	* @param __bi2 Second iterator.
		118	* @return @c true if less. */
		119	friend bool
		120	operator<(_GuardedIterator<_RAIter, _Compare>& __bi1,
		121	_GuardedIterator<_RAIter, _Compare>& __bi2)
		122	{
		123	if (__bi1._M_current == __bi1._M_end) // __bi1 is sup
		124	return __bi2._M_current == __bi2._M_end; // __bi2 is not sup
		125	if (__bi2._M_current == __bi2._M_end) // __bi2 is sup
		126	return true;
		127	return (__bi1.__comp)(__bi1, __bi2); // normal compare
		128	}
		129
		130	/** @brief Compare two elements referenced by guarded iterators.
		131	* @param __bi1 First iterator.
		132	* @param __bi2 Second iterator.
		133	* @return @c True if less equal. */
		134	friend bool
		135	operator<=(_GuardedIterator<_RAIter, _Compare>& __bi1,
		136	_GuardedIterator<_RAIter, _Compare>& __bi2)
		137	{
		138	if (__bi2._M_current == __bi2._M_end) // __bi1 is sup
		139	return __bi1._M_current != __bi1._M_end; // __bi2 is not sup
		140	if (__bi1._M_current == __bi1._M_end) // __bi2 is sup
		141	return false;
		142	return !(__bi1.__comp)(__bi2, __bi1); // normal compare
		143	}
		144	};
		145
		146	template
		147	class _UnguardedIterator
		148	{
		149	private:
		150	/** @brief Current iterator __position. */
		151	_RAIter _M_current;
		152	/** @brief _Compare. */
		153	_Compare& __comp;
		154
		155	public:
		156	/** @brief Constructor. Sets iterator to beginning of sequence.
		157	* @param __begin Begin iterator of sequence.
		158	* @param __end Unused, only for compatibility.
		159	* @param __comp Unused, only for compatibility. */
		160	_UnguardedIterator(_RAIter __begin,
		161	_RAIter /* __end */, _Compare& __comp)
		162	: _M_current(__begin), __comp(__comp)
		163	{ }
		164
		165	/** @brief Pre-increment operator.
		166	* @return This. */
		167	_UnguardedIterator<_RAIter, _Compare>&
		168	operator++()
		169	{
		170	++_M_current;
		171	return *this;
		172	}
		173
		174	/** @brief Dereference operator.
		175	* @return Referenced element. */
		176	typename std::iterator_traits<_RAIter>::value_type&
		177	operator*()
		178	{ return *_M_current; }
		179
		180	/** @brief Convert to wrapped iterator.
		181	* @return Wrapped iterator. */
		182	operator _RAIter()
		183	{ return _M_current; }
		184
		185	/** @brief Compare two elements referenced by unguarded iterators.
		186	* @param __bi1 First iterator.
		187	* @param __bi2 Second iterator.
		188	* @return @c true if less. */
		189	friend bool
		190	operator<(_UnguardedIterator<_RAIter, _Compare>& __bi1,
		191	_UnguardedIterator<_RAIter, _Compare>& __bi2)
		192	{
		193	// Normal compare.
		194	return (__bi1.__comp)(__bi1, __bi2);
		195	}
		196
		197	/** @brief Compare two elements referenced by unguarded iterators.
		198	* @param __bi1 First iterator.
		199	* @param __bi2 Second iterator.
		200	* @return @c True if less equal. */
		201	friend bool
		202	operator<=(_UnguardedIterator<_RAIter, _Compare>& __bi1,
		203	_UnguardedIterator<_RAIter, _Compare>& __bi2)
		204	{
		205	// Normal compare.
		206	return !(__bi1.__comp)(__bi2, __bi1);
		207	}
		208	};
		209
		210	/** @brief Highly efficient 3-way merging procedure.
		211	*
		212	* Merging is done with the algorithm implementation described by Peter
		213	* Sanders. Basically, the idea is to minimize the number of necessary
		214	* comparison after merging an element. The implementation trick
		215	* that makes this fast is that the order of the sequences is stored
		216	* in the instruction pointer (translated into labels in C++).
		217	*
		218	* This works well for merging up to 4 sequences.
		219	*
		220	* Note that making the merging stable does @a not come at a
		221	* performance hit.
		222	*
		223	* Whether the merging is done guarded or unguarded is selected by the
		224	* used iterator class.
		225	*
		226	* @param __seqs_begin Begin iterator of iterator pair input sequence.
		227	* @param __seqs_end End iterator of iterator pair input sequence.
		228	* @param __target Begin iterator of output sequence.
		229	* @param __comp Comparator.
		230	* @param __length Maximum length to merge, less equal than the
		231	* total number of elements available.
		232	*
		233	* @return End iterator of output sequence.
		234	*/
		235	template class iterator,
		236	typename _RAIterIterator,
		237	typename _RAIter3,
		238	typename _DifferenceTp,
		239	typename _Compare>
		240	_RAIter3
		241	multiway_merge_3_variant(_RAIterIterator __seqs_begin,
		242	_RAIterIterator __seqs_end,
		243	_RAIter3 __target,
		244	_DifferenceTp __length, _Compare __comp)
		245	{
		246	_GLIBCXX_CALL(__length);
		247
		248	typedef _DifferenceTp _DifferenceType;
		249
		250	typedef typename std::iterator_traits<_RAIterIterator>
		251	::value_type::first_type
		252	_RAIter1;
		253	typedef typename std::iterator_traits<_RAIter1>::value_type
		254	_ValueType;
		255
		256	if (__length == 0)
		257	return __target;
		258
		259	#if _GLIBCXX_ASSERTIONS
		260	_DifferenceTp __orig_length = __length;
		261	#endif
		262
		263	iterator<_RAIter1, _Compare>
		264	__seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
		265	__seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
		266	__seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp);
		267
		268	if (__seq0 <= __seq1)
		269	{
		270	if (__seq1 <= __seq2)
		271	goto __s012;
		272	else
		273	if (__seq2 < __seq0)
		274	goto __s201;
		275	else
		276	goto __s021;
		277	}
		278	else
		279	{
		280	if (__seq1 <= __seq2)
		281	{
		282	if (__seq0 <= __seq2)
		283	goto __s102;
		284	else
		285	goto __s120;
		286	}
		287	else
		288	goto __s210;
		289	}
		290	#define _GLIBCXX_PARALLEL_MERGE_3_CASE(__a, __b, __c, __c0, __c1) \
		291	__s ## __a ## __b ## __c : \
		292	__target = __seq ## __a; \
		293	++__target; \
		294	--__length; \
		295	++__seq ## __a; \
		296	if (__length == 0) goto __finish; \
		297	if (__seq ## __a __c0 __seq ## __b) goto __s ## __a ## __b ## __c; \
		298	if (__seq ## __a __c1 __seq ## __c) goto __s ## __b ## __a ## __c; \
		299	goto __s ## __b ## __c ## __a;
		300
		301	_GLIBCXX_PARALLEL_MERGE_3_CASE(0, 1, 2, <=, <=);
		302	_GLIBCXX_PARALLEL_MERGE_3_CASE(1, 2, 0, <=, < );
		303	_GLIBCXX_PARALLEL_MERGE_3_CASE(2, 0, 1, < , < );
		304	_GLIBCXX_PARALLEL_MERGE_3_CASE(1, 0, 2, < , <=);
		305	_GLIBCXX_PARALLEL_MERGE_3_CASE(0, 2, 1, <=, <=);
		306	_GLIBCXX_PARALLEL_MERGE_3_CASE(2, 1, 0, < , < );
		307
		308	#undef _GLIBCXX_PARALLEL_MERGE_3_CASE
		309
		310	__finish:
		311	;
		312
		313	#if _GLIBCXX_ASSERTIONS
		314	_GLIBCXX_PARALLEL_ASSERT(
		315	((_RAIter1)__seq0 - __seqs_begin[0].first) +
		316	((_RAIter1)__seq1 - __seqs_begin[1].first) +
		317	((_RAIter1)__seq2 - __seqs_begin[2].first)
		318	== __orig_length);
		319	#endif
		320
		321	__seqs_begin[0].first = __seq0;
		322	__seqs_begin[1].first = __seq1;
		323	__seqs_begin[2].first = __seq2;
		324
		325	return __target;
		326	}
		327
		328	/**
		329	* @brief Highly efficient 4-way merging procedure.
		330	*
		331	* Merging is done with the algorithm implementation described by Peter
		332	* Sanders. Basically, the idea is to minimize the number of necessary
		333	* comparison after merging an element. The implementation trick
		334	* that makes this fast is that the order of the sequences is stored
		335	* in the instruction pointer (translated into goto labels in C++).
		336	*
		337	* This works well for merging up to 4 sequences.
		338	*
		339	* Note that making the merging stable does @a not come at a
		340	* performance hit.
		341	*
		342	* Whether the merging is done guarded or unguarded is selected by the
		343	* used iterator class.
		344	*
		345	* @param __seqs_begin Begin iterator of iterator pair input sequence.
		346	* @param __seqs_end End iterator of iterator pair input sequence.
		347	* @param __target Begin iterator of output sequence.
		348	* @param __comp Comparator.
		349	* @param __length Maximum length to merge, less equal than the
		350	* total number of elements available.
		351	*
		352	* @return End iterator of output sequence.
		353	*/
		354	template class iterator,
		355	typename _RAIterIterator,
		356	typename _RAIter3,
		357	typename _DifferenceTp,
		358	typename _Compare>
		359	_RAIter3
		360	multiway_merge_4_variant(_RAIterIterator __seqs_begin,
		361	_RAIterIterator __seqs_end,
		362	_RAIter3 __target,
		363	_DifferenceTp __length, _Compare __comp)
		364	{
		365	_GLIBCXX_CALL(__length);
		366	typedef _DifferenceTp _DifferenceType;
		367
		368	typedef typename std::iterator_traits<_RAIterIterator>
		369	::value_type::first_type
		370	_RAIter1;
		371	typedef typename std::iterator_traits<_RAIter1>::value_type
		372	_ValueType;
		373
		374	iterator<_RAIter1, _Compare>
		375	__seq0(__seqs_begin[0].first, __seqs_begin[0].second, __comp),
		376	__seq1(__seqs_begin[1].first, __seqs_begin[1].second, __comp),
		377	__seq2(__seqs_begin[2].first, __seqs_begin[2].second, __comp),
		378	__seq3(__seqs_begin[3].first, __seqs_begin[3].second, __comp);
		379
		380	#define _GLIBCXX_PARALLEL_DECISION(__a, __b, __c, __d) { \
		381	if (__seq ## __d < __seq ## __a) \
		382	goto __s ## __d ## __a ## __b ## __c; \
		383	if (__seq ## __d < __seq ## __b) \
		384	goto __s ## __a ## __d ## __b ## __c; \
		385	if (__seq ## __d < __seq ## __c) \
		386	goto __s ## __a ## __b ## __d ## __c; \
		387	goto __s ## __a ## __b ## __c ## __d; }
		388
		389	if (__seq0 <= __seq1)
		390	{
		391	if (__seq1 <= __seq2)
		392	_GLIBCXX_PARALLEL_DECISION(0,1,2,3)
		393	else
		394	if (__seq2 < __seq0)
		395	_GLIBCXX_PARALLEL_DECISION(2,0,1,3)
		396	else
		397	_GLIBCXX_PARALLEL_DECISION(0,2,1,3)
		398	}
		399	else
		400	{
		401	if (__seq1 <= __seq2)
		402	{
		403	if (__seq0 <= __seq2)
		404	_GLIBCXX_PARALLEL_DECISION(1,0,2,3)
		405	else
		406	_GLIBCXX_PARALLEL_DECISION(1,2,0,3)
		407	}
		408	else
		409	_GLIBCXX_PARALLEL_DECISION(2,1,0,3)
		410	}
		411
		412	#define _GLIBCXX_PARALLEL_MERGE_4_CASE(__a, __b, __c, __d, \
		413	__c0, __c1, __c2) \
		414	__s ## __a ## __b ## __c ## __d: \
		415	if (__length == 0) goto __finish; \
		416	__target = __seq ## __a; \
		417	++__target; \
		418	--__length; \
		419	++__seq ## __a; \
		420	if (__seq ## __a __c0 __seq ## __b) \
		421	goto __s ## __a ## __b ## __c ## __d; \
		422	if (__seq ## __a __c1 __seq ## __c) \
		423	goto __s ## __b ## __a ## __c ## __d; \
		424	if (__seq ## __a __c2 __seq ## __d) \
		425	goto __s ## __b ## __c ## __a ## __d; \
		426	goto __s ## __b ## __c ## __d ## __a;
		427
		428	_GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 2, 3, <=, <=, <=);
		429	_GLIBCXX_PARALLEL_MERGE_4_CASE(0, 1, 3, 2, <=, <=, <=);
		430	_GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 1, 3, <=, <=, <=);
		431	_GLIBCXX_PARALLEL_MERGE_4_CASE(0, 2, 3, 1, <=, <=, <=);
		432	_GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 1, 2, <=, <=, <=);
		433	_GLIBCXX_PARALLEL_MERGE_4_CASE(0, 3, 2, 1, <=, <=, <=);
		434	_GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 2, 3, < , <=, <=);
		435	_GLIBCXX_PARALLEL_MERGE_4_CASE(1, 0, 3, 2, < , <=, <=);
		436	_GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 0, 3, <=, < , <=);
		437	_GLIBCXX_PARALLEL_MERGE_4_CASE(1, 2, 3, 0, <=, <=, < );
		438	_GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 0, 2, <=, < , <=);
		439	_GLIBCXX_PARALLEL_MERGE_4_CASE(1, 3, 2, 0, <=, <=, < );
		440	_GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 1, 3, < , < , <=);
		441	_GLIBCXX_PARALLEL_MERGE_4_CASE(2, 0, 3, 1, < , <=, < );
		442	_GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 0, 3, < , < , <=);
		443	_GLIBCXX_PARALLEL_MERGE_4_CASE(2, 1, 3, 0, < , <=, < );
		444	_GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 0, 1, <=, < , < );
		445	_GLIBCXX_PARALLEL_MERGE_4_CASE(2, 3, 1, 0, <=, < , < );
		446	_GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 1, 2, < , < , < );
		447	_GLIBCXX_PARALLEL_MERGE_4_CASE(3, 0, 2, 1, < , < , < );
		448	_GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 0, 2, < , < , < );
		449	_GLIBCXX_PARALLEL_MERGE_4_CASE(3, 1, 2, 0, < , < , < );
		450	_GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 0, 1, < , < , < );
		451	_GLIBCXX_PARALLEL_MERGE_4_CASE(3, 2, 1, 0, < , < , < );
		452
		453	#undef _GLIBCXX_PARALLEL_MERGE_4_CASE
		454	#undef _GLIBCXX_PARALLEL_DECISION
		455
		456	__finish:
		457	;
		458
		459	__seqs_begin[0].first = __seq0;
		460	__seqs_begin[1].first = __seq1;
		461	__seqs_begin[2].first = __seq2;
		462	__seqs_begin[3].first = __seq3;
		463
		464	return __target;
		465	}
		466
		467	/** @brief Multi-way merging procedure for a high branching factor,
		468	* guarded case.
		469	*
		470	* This merging variant uses a LoserTree class as selected by `_LT`.
		471	*
		472	* Stability is selected through the used LoserTree class `_LT`.
		473	*
		474	* At least one non-empty sequence is required.
		475	*
		476	* @param __seqs_begin Begin iterator of iterator pair input sequence.
		477	* @param __seqs_end End iterator of iterator pair input sequence.
		478	* @param __target Begin iterator of output sequence.
		479	* @param __comp Comparator.
		480	* @param __length Maximum length to merge, less equal than the
		481	* total number of elements available.
		482	*
		483	* @return End iterator of output sequence.
		484	*/
		485	template
		486	typename _RAIterIterator,
		487	typename _RAIter3,
		488	typename _DifferenceTp,
		489	typename _Compare>
		490	_RAIter3
		491	multiway_merge_loser_tree(_RAIterIterator __seqs_begin,
		492	_RAIterIterator __seqs_end,
		493	_RAIter3 __target,
		494	_DifferenceTp __length, _Compare __comp)
		495	{
		496	_GLIBCXX_CALL(__length)
		497
		498	typedef _DifferenceTp _DifferenceType;
		499	typedef typename std::iterator_traits<_RAIterIterator>
		500	::difference_type _SeqNumber;
		501	typedef typename std::iterator_traits<_RAIterIterator>
		502	::value_type::first_type
		503	_RAIter1;
		504	typedef typename std::iterator_traits<_RAIter1>::value_type
		505	_ValueType;
		506
		507	_SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
		508
		509	_LT __lt(__k, __comp);
		510
		511	// Default value for potentially non-default-constructible types.
		512	_ValueType* __arbitrary_element = 0;
		513
		514	for (_SeqNumber __t = 0; __t < __k; ++__t)
		515	{
		516	if(!__arbitrary_element
		517	&& _GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__t]) > 0)
		518	__arbitrary_element = &(*__seqs_begin[__t].first);
		519	}
		520
		521	for (_SeqNumber __t = 0; __t < __k; ++__t)
		522	{
		523	if (__seqs_begin[__t].first == __seqs_begin[__t].second)
		524	__lt.__insert_start(*__arbitrary_element, __t, true);
		525	else
		526	__lt.__insert_start(*__seqs_begin[__t].first, __t, false);
		527	}
		528
		529	__lt.__init();
		530
		531	_SeqNumber __source;
		532
		533	for (_DifferenceType __i = 0; __i < __length; ++__i)
		534	{
		535	//take out
		536	__source = __lt.__get_min_source();
		537
		538	(__target++) = (__seqs_begin[__source].first++);
		539
		540	// Feed.
		541	if (__seqs_begin[__source].first == __seqs_begin[__source].second)
		542	__lt.__delete_min_insert(*__arbitrary_element, true);
		543	else
		544	// Replace from same __source.
		545	__lt.__delete_min_insert(*__seqs_begin[__source].first, false);
		546	}
		547
		548	return __target;
		549	}
		550
		551	/** @brief Multi-way merging procedure for a high branching factor,
		552	* unguarded case.
		553	*
		554	* Merging is done using the LoserTree class `_LT`.
		555	*
		556	* Stability is selected by the used LoserTrees.
		557	*
		558	* @pre No input will run out of elements during the merge.
		559	*
		560	* @param __seqs_begin Begin iterator of iterator pair input sequence.
		561	* @param __seqs_end End iterator of iterator pair input sequence.
		562	* @param __target Begin iterator of output sequence.
		563	* @param __comp Comparator.
		564	* @param __length Maximum length to merge, less equal than the
		565	* total number of elements available.
		566	*
		567	* @return End iterator of output sequence.
		568	*/
		569	template
		570	typename _RAIterIterator,
		571	typename _RAIter3,
		572	typename _DifferenceTp, typename _Compare>
		573	_RAIter3
		574	multiway_merge_loser_tree_unguarded(_RAIterIterator __seqs_begin,
		575	_RAIterIterator __seqs_end,
		576	_RAIter3 __target,
		577	const typename std::iterator_traits
		578	_RAIterIterator>::value_type::first_type>::value_type&
		579	__sentinel,
		580	_DifferenceTp __length,
		581	_Compare __comp)
		582	{
		583	_GLIBCXX_CALL(__length)
		584	typedef _DifferenceTp _DifferenceType;
		585
		586	typedef typename std::iterator_traits<_RAIterIterator>
		587	::difference_type _SeqNumber;
		588	typedef typename std::iterator_traits<_RAIterIterator>
		589	::value_type::first_type
		590	_RAIter1;
		591	typedef typename std::iterator_traits<_RAIter1>::value_type
		592	_ValueType;
		593
		594	_SeqNumber __k = __seqs_end - __seqs_begin;
		595
		596	_LT __lt(__k, __sentinel, __comp);
		597
		598	for (_SeqNumber __t = 0; __t < __k; ++__t)
		599	{
		600	#if _GLIBCXX_ASSERTIONS
		601	_GLIBCXX_PARALLEL_ASSERT(__seqs_begin[__t].first
		602	!= __seqs_begin[__t].second);
		603	#endif
		604	__lt.__insert_start(*__seqs_begin[__t].first, __t, false);
		605	}
		606
		607	__lt.__init();
		608
		609	_SeqNumber __source;
		610
		611	#if _GLIBCXX_ASSERTIONS
		612	_DifferenceType __i = 0;
		613	#endif
		614
		615	_RAIter3 __target_end = __target + __length;
		616	while (__target < __target_end)
		617	{
		618	// Take out.
		619	__source = __lt.__get_min_source();
		620
		621	#if _GLIBCXX_ASSERTIONS
		622	_GLIBCXX_PARALLEL_ASSERT(0 <= __source && __source < __k);
		623	_GLIBCXX_PARALLEL_ASSERT(__i == 0
		624	\|\| !__comp((__seqs_begin[__source].first), (__target - 1)));
		625	#endif
		626
		627	// Feed.
		628	(__target++) = (__seqs_begin[__source].first++);
		629
		630	#if _GLIBCXX_ASSERTIONS
		631	++__i;
		632	#endif
		633	// Replace from same __source.
		634	__lt.__delete_min_insert(*__seqs_begin[__source].first, false);
		635	}
		636
		637	return __target;
		638	}
		639
		640
		641	/** @brief Multi-way merging procedure for a high branching factor,
		642	* requiring sentinels to exist.
		643	*
		644	* @tparam UnguardedLoserTree _Loser Tree variant to use for the unguarded
		645	* merging.
		646	*
		647	* @param __seqs_begin Begin iterator of iterator pair input sequence.
		648	* @param __seqs_end End iterator of iterator pair input sequence.
		649	* @param __target Begin iterator of output sequence.
		650	* @param __comp Comparator.
		651	* @param __length Maximum length to merge, less equal than the
		652	* total number of elements available.
		653	*
		654	* @return End iterator of output sequence.
		655	*/
		656	template
		657	typename _RAIterIterator,
		658	typename _RAIter3,
		659	typename _DifferenceTp,
		660	typename _Compare>
		661	_RAIter3
		662	multiway_merge_loser_tree_sentinel(_RAIterIterator __seqs_begin,
		663	_RAIterIterator __seqs_end,
		664	_RAIter3 __target,
		665	const typename std::iterator_traits
		666	_RAIterIterator>::value_type::first_type>::value_type&
		667	__sentinel,
		668	_DifferenceTp __length,
		669	_Compare __comp)
		670	{
		671	_GLIBCXX_CALL(__length)
		672
		673	typedef _DifferenceTp _DifferenceType;
		674	typedef std::iterator_traits<_RAIterIterator> _TraitsType;
		675	typedef typename std::iterator_traits<_RAIterIterator>
		676	::value_type::first_type
		677	_RAIter1;
		678	typedef typename std::iterator_traits<_RAIter1>::value_type
		679	_ValueType;
		680
		681	_RAIter3 __target_end;
		682
		683	for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
		684	// Move the sequence ends to the sentinel. This has the
		685	// effect that the sentinel appears to be within the sequence. Then,
		686	// we can use the unguarded variant if we merge out as many
		687	// non-sentinel elements as we have.
		688	++((*__s).second);
		689
		690	__target_end = multiway_merge_loser_tree_unguarded
		691	(__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
		692
		693	#if _GLIBCXX_ASSERTIONS
		694	_GLIBCXX_PARALLEL_ASSERT(__target_end == __target + __length);
		695	_GLIBCXX_PARALLEL_ASSERT(__is_sorted(__target, __target_end, __comp));
		696	#endif
		697
		698	// Restore the sequence ends so the sentinels are not contained in the
		699	// sequence any more (see comment in loop above).
		700	for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
		701	--((*__s).second);
		702
		703	return __target_end;
		704	}
		705
		706	/**
		707	* @brief Traits for determining whether the loser tree should
		708	* use pointers or copies.
		709	*
		710	* The field "_M_use_pointer" is used to determine whether to use pointers
		711	* in he loser trees or whether to copy the values into the loser tree.
		712	*
		713	* The default behavior is to use pointers if the data type is 4 times as
		714	* big as the pointer to it.
		715	*
		716	* Specialize for your data type to customize the behavior.
		717	*
		718	* Example:
		719	*
		720	* template<>
		721	* struct _LoserTreeTraits
		722	* { static const bool _M_use_pointer = false; };
		723	*
		724	* template<>
		725	* struct _LoserTreeTraits
		726	* { static const bool _M_use_pointer = true; };
		727	*
		728	* @param _Tp type to give the loser tree traits for.
		729	*/
		730	template
		731	struct _LoserTreeTraits
		732	{
		733	/**
		734	* @brief True iff to use pointers instead of values in loser trees.
		735	*
		736	* The default behavior is to use pointers if the data type is four
		737	* times as big as the pointer to it.
		738	*/
		739	static const bool _M_use_pointer = (sizeof(_Tp) > 4 * sizeof(_Tp*));
		740	};
		741
		742	/**
		743	* @brief Switch for 3-way merging with __sentinels turned off.
		744	*
		745	* Note that 3-way merging is always stable!
		746	*/
		747	template
		748	typename _RAIterIterator,
		749	typename _RAIter3,
		750	typename _DifferenceTp,
		751	typename _Compare>
		752	struct __multiway_merge_3_variant_sentinel_switch
		753	{
		754	_RAIter3
		755	operator()(_RAIterIterator __seqs_begin,
		756	_RAIterIterator __seqs_end,
		757	_RAIter3 __target,
		758	_DifferenceTp __length, _Compare __comp)
		759	{ return multiway_merge_3_variant<_GuardedIterator>
		760	(__seqs_begin, __seqs_end, __target, __length, __comp); }
		761	};
		762
		763	/**
		764	* @brief Switch for 3-way merging with __sentinels turned on.
		765	*
		766	* Note that 3-way merging is always stable!
		767	*/
		768	template
		769	typename _RAIter3,
		770	typename _DifferenceTp,
		771	typename _Compare>
		772	struct __multiway_merge_3_variant_sentinel_switch
		773	_RAIter3, _DifferenceTp,
		774	_Compare>
		775	{
		776	_RAIter3
		777	operator()(_RAIterIterator __seqs_begin,
		778	_RAIterIterator __seqs_end,
		779	_RAIter3 __target,
		780	_DifferenceTp __length, _Compare __comp)
		781	{ return multiway_merge_3_variant<_UnguardedIterator>
		782	(__seqs_begin, __seqs_end, __target, __length, __comp); }
		783	};
		784
		785	/**
		786	* @brief Switch for 4-way merging with __sentinels turned off.
		787	*
		788	* Note that 4-way merging is always stable!
		789	*/
		790	template
		791	typename _RAIterIterator,
		792	typename _RAIter3,
		793	typename _DifferenceTp,
		794	typename _Compare>
		795	struct __multiway_merge_4_variant_sentinel_switch
		796	{
		797	_RAIter3
		798	operator()(_RAIterIterator __seqs_begin,
		799	_RAIterIterator __seqs_end,
		800	_RAIter3 __target,
		801	_DifferenceTp __length, _Compare __comp)
		802	{ return multiway_merge_4_variant<_GuardedIterator>
		803	(__seqs_begin, __seqs_end, __target, __length, __comp); }
		804	};
		805
		806	/**
		807	* @brief Switch for 4-way merging with __sentinels turned on.
		808	*
		809	* Note that 4-way merging is always stable!
		810	*/
		811	template
		812	typename _RAIter3,
		813	typename _DifferenceTp,
		814	typename _Compare>
		815	struct __multiway_merge_4_variant_sentinel_switch
		816	_RAIter3, _DifferenceTp,
		817	_Compare>
		818	{
		819	_RAIter3
		820	operator()(_RAIterIterator __seqs_begin,
		821	_RAIterIterator __seqs_end,
		822	_RAIter3 __target,
		823	_DifferenceTp __length, _Compare __comp)
		824	{ return multiway_merge_4_variant<_UnguardedIterator>
		825	(__seqs_begin, __seqs_end, __target, __length, __comp); }
		826	};
		827
		828	/**
		829	* @brief Switch for k-way merging with __sentinels turned on.
		830	*/
		831	template
		832	bool __stable,
		833	typename _RAIterIterator,
		834	typename _RAIter3,
		835	typename _DifferenceTp,
		836	typename _Compare>
		837	struct __multiway_merge_k_variant_sentinel_switch
		838	{
		839	_RAIter3
		840	operator()(_RAIterIterator __seqs_begin,
		841	_RAIterIterator __seqs_end,
		842	_RAIter3 __target,
		843	const typename std::iterator_traits
		844	_RAIterIterator>::value_type::first_type>::value_type&
		845	__sentinel,
		846	_DifferenceTp __length, _Compare __comp)
		847	{
		848	typedef typename std::iterator_traits<_RAIterIterator>
		849	::value_type::first_type
		850	_RAIter1;
		851	typedef typename std::iterator_traits<_RAIter1>::value_type
		852	_ValueType;
		853
		854	return multiway_merge_loser_tree_sentinel<
		855	typename __gnu_cxx::__conditional_type<
		856	_LoserTreeTraits<_ValueType>::_M_use_pointer,
		857	_LoserTreePointerUnguarded<__stable, _ValueType, _Compare>,
		858	_LoserTreeUnguarded<__stable, _ValueType, _Compare>
		859	>::__type>
		860	(__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
		861	}
		862	};
		863
		864	/**
		865	* @brief Switch for k-way merging with __sentinels turned off.
		866	*/
		867	template
		868	typename _RAIterIterator,
		869	typename _RAIter3,
		870	typename _DifferenceTp,
		871	typename _Compare>
		872	struct __multiway_merge_k_variant_sentinel_switch
		873	_RAIterIterator,
		874	_RAIter3, _DifferenceTp,
		875	_Compare>
		876	{
		877	_RAIter3
		878	operator()(_RAIterIterator __seqs_begin,
		879	_RAIterIterator __seqs_end,
		880	_RAIter3 __target,
		881	const typename std::iterator_traits
		882	_RAIterIterator>::value_type::first_type>::value_type&
		883	__sentinel,
		884	_DifferenceTp __length, _Compare __comp)
		885	{
		886	typedef typename std::iterator_traits<_RAIterIterator>
		887	::value_type::first_type
		888	_RAIter1;
		889	typedef typename std::iterator_traits<_RAIter1>::value_type
		890	_ValueType;
		891
		892	return multiway_merge_loser_tree<
		893	typename __gnu_cxx::__conditional_type<
		894	_LoserTreeTraits<_ValueType>::_M_use_pointer,
		895	_LoserTreePointer<__stable, _ValueType, _Compare>,
		896	_LoserTree<__stable, _ValueType, _Compare>
		897	>::__type >(__seqs_begin, __seqs_end, __target, __length, __comp);
		898	}
		899	};
		900
		901	/** @brief Sequential multi-way merging switch.
		902	*
		903	* The _GLIBCXX_PARALLEL_DECISION is based on the branching factor and
		904	* runtime settings.
		905	* @param __seqs_begin Begin iterator of iterator pair input sequence.
		906	* @param __seqs_end End iterator of iterator pair input sequence.
		907	* @param __target Begin iterator of output sequence.
		908	* @param __comp Comparator.
		909	* @param __length Maximum length to merge, possibly larger than the
		910	* number of elements available.
		911	* @param __sentinel The sequences have __a __sentinel element.
		912	* @return End iterator of output sequence. */
		913	template
		914	bool __sentinels,
		915	typename _RAIterIterator,
		916	typename _RAIter3,
		917	typename _DifferenceTp,
		918	typename _Compare>
		919	_RAIter3
		920	__sequential_multiway_merge(_RAIterIterator __seqs_begin,
		921	_RAIterIterator __seqs_end,
		922	_RAIter3 __target,
		923	const typename std::iterator_traits
		924	_RAIterIterator>::value_type::first_type>::value_type&
		925	__sentinel,
		926	_DifferenceTp __length, _Compare __comp)
		927	{
		928	_GLIBCXX_CALL(__length)
		929
		930	typedef _DifferenceTp _DifferenceType;
		931	typedef typename std::iterator_traits<_RAIterIterator>
		932	::difference_type _SeqNumber;
		933	typedef typename std::iterator_traits<_RAIterIterator>
		934	::value_type::first_type
		935	_RAIter1;
		936	typedef typename std::iterator_traits<_RAIter1>::value_type
		937	_ValueType;
		938
		939	#if _GLIBCXX_ASSERTIONS
		940	for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
		941	{
		942	_GLIBCXX_PARALLEL_ASSERT(__is_sorted((*__s).first,
		943	(*__s).second, __comp));
		944	}
		945	#endif
		946
		947	_DifferenceTp __total_length = 0;
		948	for (_RAIterIterator __s = __seqs_begin; __s != __seqs_end; ++__s)
		949	__total_length += _GLIBCXX_PARALLEL_LENGTH(*__s);
		950
		951	__length = std::min<_DifferenceTp>(__length, __total_length);
		952
		953	if(__length == 0)
		954	return __target;
		955
		956	_RAIter3 __return_target = __target;
		957	_SeqNumber __k = static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
		958
		959	switch (__k)
		960	{
		961	case 0:
		962	break;
		963	case 1:
		964	__return_target = std::copy(__seqs_begin[0].first,
		965	__seqs_begin[0].first + __length,
		966	__target);
		967	__seqs_begin[0].first += __length;
		968	break;
		969	case 2:
		970	__return_target = __merge_advance(__seqs_begin[0].first,
		971	__seqs_begin[0].second,
		972	__seqs_begin[1].first,
		973	__seqs_begin[1].second,
		974	__target, __length, __comp);
		975	break;
		976	case 3:
		977	__return_target = __multiway_merge_3_variant_sentinel_switch
		978	<__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
		979	(__seqs_begin, __seqs_end, __target, __length, __comp);
		980	break;
		981	case 4:
		982	__return_target = __multiway_merge_4_variant_sentinel_switch
		983	<__sentinels, _RAIterIterator, _RAIter3, _DifferenceTp, _Compare>()
		984	(__seqs_begin, __seqs_end, __target, __length, __comp);
		985	break;
		986	default:
		987	__return_target = __multiway_merge_k_variant_sentinel_switch
		988	<__sentinels, __stable, _RAIterIterator, _RAIter3, _DifferenceTp,
		989	_Compare>()
		990	(__seqs_begin, __seqs_end, __target, __sentinel, __length, __comp);
		991	break;
		992	}
		993	#if _GLIBCXX_ASSERTIONS
		994	_GLIBCXX_PARALLEL_ASSERT(
		995	__is_sorted(__target, __target + __length, __comp));
		996	#endif
		997
		998	return __return_target;
		999	}
		1000
		1001	/**
		1002	* @brief Stable sorting functor.
		1003	*
		1004	* Used to reduce code instanciation in multiway_merge_sampling_splitting.
		1005	*/
		1006	template
		1007	struct _SamplingSorter
		1008	{
		1009	void
		1010	operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
		1011	{ __gnu_sequential::stable_sort(__first, __last, __comp); }
		1012	};
		1013
		1014	/**
		1015	* @brief Non-__stable sorting functor.
		1016	*
		1017	* Used to reduce code instantiation in multiway_merge_sampling_splitting.
		1018	*/
		1019	template
		1020	struct _SamplingSorter
		1021	{
		1022	void
		1023	operator()(_RAIter __first, _RAIter __last, _StrictWeakOrdering __comp)
		1024	{ __gnu_sequential::sort(__first, __last, __comp); }
		1025	};
		1026
		1027	/**
		1028	* @brief Sampling based splitting for parallel multiway-merge routine.
		1029	*/
		1030	template
		1031	typename _RAIterIterator,
		1032	typename _Compare,
		1033	typename _DifferenceType>
		1034	void
		1035	multiway_merge_sampling_splitting(_RAIterIterator __seqs_begin,
		1036	_RAIterIterator __seqs_end,
		1037	_DifferenceType __length,
		1038	_DifferenceType __total_length,
		1039	_Compare __comp,
		1040	std::vector > *__pieces)
		1041	{
		1042	typedef typename std::iterator_traits<_RAIterIterator>
		1043	::difference_type _SeqNumber;
		1044	typedef typename std::iterator_traits<_RAIterIterator>
		1045	::value_type::first_type
		1046	_RAIter1;
		1047	typedef typename std::iterator_traits<_RAIter1>::value_type
		1048	_ValueType;
		1049
		1050	// __k sequences.
		1051	const _SeqNumber __k
		1052	= static_cast<_SeqNumber>(__seqs_end - __seqs_begin);
		1053
		1054	const _ThreadIndex __num_threads = omp_get_num_threads();
		1055
		1056	const _DifferenceType __num_samples =
		1057	__gnu_parallel::_Settings::get().merge_oversampling * __num_threads;
		1058
		1059	_ValueType* __samples = static_cast<_ValueType*>
		1060	(::operator new(sizeof(_ValueType) * __k * __num_samples));
		1061	// Sample.
		1062	for (_SeqNumber __s = 0; __s < __k; ++__s)
		1063	for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
		1064	{
		1065	_DifferenceType sample_index = static_cast<_DifferenceType>
		1066	(_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__s])
		1067	* (double(__i + 1) / (__num_samples + 1))
		1068	* (double(__length) / __total_length));
		1069	new(&(__samples[__s * __num_samples + __i]))
		1070	_ValueType(__seqs_begin[__s].first[sample_index]);
		1071	}
		1072
		1073	// Sort stable or non-stable, depending on value of template parameter
		1074	// "__stable".
		1075	_SamplingSorter<__stable, _ValueType*, _Compare>()
		1076	(__samples, __samples + (__num_samples * __k), __comp);
		1077
		1078	for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
		1079	// For each slab / processor.
		1080	for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
		1081	{
		1082	// For each sequence.
		1083	if (__slab > 0)
		1084	__pieces[__slab][__seq].first = std::upper_bound
		1085	(__seqs_begin[__seq].first, __seqs_begin[__seq].second,
		1086	__samples[__num_samples * __k * __slab / __num_threads],
		1087	__comp)
		1088	- __seqs_begin[__seq].first;
		1089	else
		1090	// Absolute beginning.
		1091	__pieces[__slab][__seq].first = 0;
		1092	if ((__slab + 1) < __num_threads)
		1093	__pieces[__slab][__seq].second = std::upper_bound
		1094	(__seqs_begin[__seq].first, __seqs_begin[__seq].second,
		1095	__samples[__num_samples * __k * (__slab + 1) / __num_threads],
		1096	__comp)
		1097	- __seqs_begin[__seq].first;
		1098	else
		1099	// Absolute end.
		1100	__pieces[__slab][__seq].second =
		1101	_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
		1102	}
		1103
		1104	for (_SeqNumber __s = 0; __s < __k; ++__s)
		1105	for (_DifferenceType __i = 0; __i < __num_samples; ++__i)
		1106	__samples[__s * __num_samples + __i].~_ValueType();
		1107	::operator delete(__samples);
		1108	}
		1109
		1110	/**
		1111	* @brief Exact splitting for parallel multiway-merge routine.
		1112	*
		1113	* None of the passed sequences may be empty.
		1114	*/
		1115	template
		1116	typename _RAIterIterator,
		1117	typename _Compare,
		1118	typename _DifferenceType>
		1119	void
		1120	multiway_merge_exact_splitting(_RAIterIterator __seqs_begin,
		1121	_RAIterIterator __seqs_end,
		1122	_DifferenceType __length,
		1123	_DifferenceType __total_length,
		1124	_Compare __comp,
		1125	std::vector > *__pieces)
		1126	{
		1127	typedef typename std::iterator_traits<_RAIterIterator>
		1128	::difference_type _SeqNumber;
		1129	typedef typename std::iterator_traits<_RAIterIterator>
		1130	::value_type::first_type
		1131	_RAIter1;
		1132
		1133	const bool __tight = (__total_length == __length);
		1134
		1135	// __k sequences.
		1136	const _SeqNumber __k = __seqs_end - __seqs_begin;
		1137
		1138	const _ThreadIndex __num_threads = omp_get_num_threads();
		1139
		1140	// (Settings::multiway_merge_splitting
		1141	// == __gnu_parallel::_Settings::EXACT).
		1142	std::vector<_RAIter1>* __offsets =
		1143	new std::vector<_RAIter1>[__num_threads];
		1144	std::vector > __se(__k);
		1145
		1146	copy(__seqs_begin, __seqs_end, __se.begin());
		1147
		1148	_DifferenceType* __borders =
		1149	new _DifferenceType[__num_threads + 1];
		1150	__equally_split(__length, __num_threads, __borders);
		1151
		1152	for (_ThreadIndex __s = 0; __s < (__num_threads - 1); ++__s)
		1153	{
		1154	__offsets[__s].resize(__k);
		1155	multiseq_partition(__se.begin(), __se.end(), __borders[__s + 1],
		1156	__offsets[__s].begin(), __comp);
		1157
		1158	// Last one also needed and available.
		1159	if (!__tight)
		1160	{
		1161	__offsets[__num_threads - 1].resize(__k);
		1162	multiseq_partition(__se.begin(), __se.end(),
		1163	_DifferenceType(__length),
		1164	__offsets[__num_threads - 1].begin(),
		1165	__comp);
		1166	}
		1167	}
		1168	delete[] __borders;
		1169
		1170	for (_ThreadIndex __slab = 0; __slab < __num_threads; ++__slab)
		1171	{
		1172	// For each slab / processor.
		1173	for (_SeqNumber __seq = 0; __seq < __k; ++__seq)
		1174	{
		1175	// For each sequence.
		1176	if (__slab == 0)
		1177	{
		1178	// Absolute beginning.
		1179	__pieces[__slab][__seq].first = 0;
		1180	}
		1181	else
		1182	__pieces[__slab][__seq].first =
		1183	__pieces[__slab - 1][__seq].second;
		1184	if (!__tight \|\| __slab < (__num_threads - 1))
		1185	__pieces[__slab][__seq].second =
		1186	__offsets[__slab][__seq] - __seqs_begin[__seq].first;
		1187	else
		1188	{
		1189	// __slab == __num_threads - 1
		1190	__pieces[__slab][__seq].second =
		1191	_GLIBCXX_PARALLEL_LENGTH(__seqs_begin[__seq]);
		1192	}
		1193	}
		1194	}
		1195	delete[] __offsets;
		1196	}
		1197
		1198	/** @brief Parallel multi-way merge routine.
		1199	*
		1200	* The _GLIBCXX_PARALLEL_DECISION is based on the branching factor
		1201	* and runtime settings.
		1202	*
		1203	* Must not be called if the number of sequences is 1.
		1204	*
		1205	* @tparam _Splitter functor to split input (either __exact or sampling based)
		1206	* @tparam __stable Stable merging incurs a performance penalty.
		1207	* @tparam __sentinel Ignored.
		1208	*
		1209	* @param __seqs_begin Begin iterator of iterator pair input sequence.
		1210	* @param __seqs_end End iterator of iterator pair input sequence.
		1211	* @param __target Begin iterator of output sequence.
		1212	* @param __comp Comparator.
		1213	* @param __length Maximum length to merge, possibly larger than the
		1214	* number of elements available.
		1215	* @return End iterator of output sequence.
		1216	*/
		1217	template
		1218	bool __sentinels,
		1219	typename _RAIterIterator,
		1220	typename _RAIter3,
		1221	typename _DifferenceTp,
		1222	typename _Splitter,
		1223	typename _Compare>
		1224	_RAIter3
		1225	parallel_multiway_merge(_RAIterIterator __seqs_begin,
		1226	_RAIterIterator __seqs_end,
		1227	_RAIter3 __target,
		1228	_Splitter __splitter,
		1229	_DifferenceTp __length,
		1230	_Compare __comp,
		1231	_ThreadIndex __num_threads)
		1232	{
		1233	#if _GLIBCXX_ASSERTIONS
		1234	_GLIBCXX_PARALLEL_ASSERT(__seqs_end - __seqs_begin > 1);
		1235	#endif
		1236
		1237	_GLIBCXX_CALL(__length)
		1238
		1239	typedef _DifferenceTp _DifferenceType;
		1240	typedef typename std::iterator_traits<_RAIterIterator>
		1241	::difference_type _SeqNumber;
		1242	typedef typename std::iterator_traits<_RAIterIterator>
		1243	::value_type::first_type
		1244	_RAIter1;
		1245	typedef typename
		1246	std::iterator_traits<_RAIter1>::value_type _ValueType;
		1247
		1248	// Leave only non-empty sequences.
		1249	typedef std::pair<_RAIter1, _RAIter1> seq_type;
		1250	seq_type* __ne_seqs = new seq_type[__seqs_end - __seqs_begin];
		1251	_SeqNumber __k = 0;
		1252	_DifferenceType __total_length = 0;
		1253	for (_RAIterIterator __raii = __seqs_begin;
		1254	__raii != __seqs_end; ++__raii)
		1255	{
		1256	_DifferenceTp __seq_length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
		1257	if(__seq_length > 0)
		1258	{
		1259	__total_length += __seq_length;
		1260	__ne_seqs[__k++] = *__raii;
		1261	}
		1262	}
		1263
		1264	_GLIBCXX_CALL(__total_length)
		1265
		1266	__length = std::min<_DifferenceTp>(__length, __total_length);
		1267
		1268	if (__total_length == 0 \|\| __k == 0)
		1269	{
		1270	delete[] __ne_seqs;
		1271	return __target;
		1272	}
		1273
		1274	std::vector >* __pieces;
		1275
		1276	__num_threads = static_cast<_ThreadIndex>
		1277	(std::min<_DifferenceType>(__num_threads, __total_length));
		1278
		1279	# pragma omp parallel num_threads (__num_threads)
		1280	{
		1281	# pragma omp single
		1282	{
		1283	__num_threads = omp_get_num_threads();
		1284	// Thread __t will have to merge pieces[__iam][0..__k - 1]
		1285	__pieces = new std::vector<
		1286	std::pair<_DifferenceType, _DifferenceType> >[__num_threads];
		1287	for (_ThreadIndex __s = 0; __s < __num_threads; ++__s)
		1288	__pieces[__s].resize(__k);
		1289
		1290	_DifferenceType __num_samples =
		1291	__gnu_parallel::_Settings::get().merge_oversampling
		1292	* __num_threads;
		1293
		1294	__splitter(__ne_seqs, __ne_seqs + __k, __length, __total_length,
		1295	__comp, __pieces);
		1296	} //single
		1297
		1298	_ThreadIndex __iam = omp_get_thread_num();
		1299
		1300	_DifferenceType __target_position = 0;
		1301
		1302	for (_SeqNumber __c = 0; __c < __k; ++__c)
		1303	__target_position += __pieces[__iam][__c].first;
		1304
		1305	seq_type* __chunks = new seq_type[__k];
		1306
		1307	for (_SeqNumber __s = 0; __s < __k; ++__s)
		1308	__chunks[__s] = std::make_pair(__ne_seqs[__s].first
		1309	+ __pieces[__iam][__s].first,
		1310	__ne_seqs[__s].first
		1311	+ __pieces[__iam][__s].second);
		1312
		1313	if(__length > __target_position)
		1314	__sequential_multiway_merge<__stable, __sentinels>
		1315	(__chunks, __chunks + __k, __target + __target_position,
		1316	*(__seqs_begin->second), __length - __target_position, __comp);
		1317
		1318	delete[] __chunks;
		1319	} // parallel
		1320
		1321	#if _GLIBCXX_ASSERTIONS
		1322	_GLIBCXX_PARALLEL_ASSERT(
		1323	__is_sorted(__target, __target + __length, __comp));
		1324	#endif
		1325
		1326	__k = 0;
		1327	// Update ends of sequences.
		1328	for (_RAIterIterator __raii = __seqs_begin;
		1329	__raii != __seqs_end; ++__raii)
		1330	{
		1331	_DifferenceTp __length = _GLIBCXX_PARALLEL_LENGTH(*__raii);
		1332	if(__length > 0)
		1333	(*__raii).first += __pieces[__num_threads - 1][__k++].second;
		1334	}
		1335
		1336	delete[] __pieces;
		1337	delete[] __ne_seqs;
		1338
		1339	return __target + __length;
		1340	}
		1341
		1342	/**
		1343	* @brief Multiway Merge Frontend.
		1344	*
		1345	* Merge the sequences specified by seqs_begin and __seqs_end into
		1346	* __target. __seqs_begin and __seqs_end must point to a sequence of
		1347	* pairs. These pairs must contain an iterator to the beginning
		1348	* of a sequence in their first entry and an iterator the _M_end of
		1349	* the same sequence in their second entry.
		1350	*
		1351	* Ties are broken arbitrarily. See stable_multiway_merge for a variant
		1352	* that breaks ties by sequence number but is slower.
		1353	*
		1354	* The first entries of the pairs (i.e. the begin iterators) will be moved
		1355	* forward.
		1356	*
		1357	* The output sequence has to provide enough space for all elements
		1358	* that are written to it.
		1359	*
		1360	* This function will merge the input sequences:
		1361	*
		1362	* - not stable
		1363	* - parallel, depending on the input size and Settings
		1364	* - using sampling for splitting
		1365	* - not using sentinels
		1366	*
		1367	* Example:
		1368	*
		1369	*
		1370	* int sequences[10][10];
		1371	* for (int __i = 0; __i < 10; ++__i)
		1372	* for (int __j = 0; __i < 10; ++__j)
		1373	* sequences[__i][__j] = __j;
		1374	*
		1375	* int __out[33];
		1376	* std::vector > seqs;
		1377	* for (int __i = 0; __i < 10; ++__i)
		1378	* { seqs.push(std::make_pair(sequences[__i],
		1379	* sequences[__i] + 10)) }
		1380	*
		1381	* multiway_merge(seqs.begin(), seqs.end(), __target, std::less(), 33);
		1382	*
		1383	*
		1384	* @see stable_multiway_merge
		1385	*
		1386	* @pre All input sequences must be sorted.
		1387	* @pre Target must provide enough space to merge out length elements or
		1388	* the number of elements in all sequences, whichever is smaller.
		1389	*
		1390	* @post [__target, return __value) contains merged __elements from the
		1391	* input sequences.
		1392	* @post return __value - __target = min(__length, number of elements in all
		1393	* sequences).
		1394	*
		1395	* @tparam _RAIterPairIterator iterator over sequence
		1396	* of pairs of iterators
		1397	* @tparam _RAIterOut iterator over target sequence
		1398	* @tparam _DifferenceTp difference type for the sequence
		1399	* @tparam _Compare strict weak ordering type to compare elements
		1400	* in sequences
		1401	*
		1402	* @param __seqs_begin __begin of sequence __sequence
		1403	* @param __seqs_end _M_end of sequence __sequence
		1404	* @param __target target sequence to merge to.
		1405	* @param __comp strict weak ordering to use for element comparison.
		1406	* @param __length Maximum length to merge, possibly larger than the
		1407	* number of elements available.
		1408	*
		1409	* @return _M_end iterator of output sequence
		1410	*/
		1411	// multiway_merge
		1412	// public interface
		1413	template
		1414	typename _RAIterOut,
		1415	typename _DifferenceTp,
		1416	typename _Compare>
		1417	_RAIterOut
		1418	multiway_merge(_RAIterPairIterator __seqs_begin,
		1419	_RAIterPairIterator __seqs_end,
		1420	_RAIterOut __target,
		1421	_DifferenceTp __length, _Compare __comp,
		1422	__gnu_parallel::sequential_tag)
		1423	{
		1424	typedef _DifferenceTp _DifferenceType;
		1425	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1426
		1427	// catch special case: no sequences
		1428	if (__seqs_begin == __seqs_end)
		1429	return __target;
		1430
		1431	// Execute multiway merge sequentially.
		1432	return __sequential_multiway_merge
		1433
		1434	(__seqs_begin, __seqs_end, __target,
		1435	*(__seqs_begin->second), __length, __comp);
		1436	}
		1437
		1438	// public interface
		1439	template
		1440	typename _RAIterOut,
		1441	typename _DifferenceTp,
		1442	typename _Compare>
		1443	_RAIterOut
		1444	multiway_merge(_RAIterPairIterator __seqs_begin,
		1445	_RAIterPairIterator __seqs_end,
		1446	_RAIterOut __target,
		1447	_DifferenceTp __length, _Compare __comp,
		1448	__gnu_parallel::exact_tag __tag)
		1449	{
		1450	typedef _DifferenceTp _DifferenceType;
		1451	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1452
		1453	// catch special case: no sequences
		1454	if (__seqs_begin == __seqs_end)
		1455	return __target;
		1456
		1457	// Execute merge; maybe parallel, depending on the number of merged
		1458	// elements and the number of sequences and global thresholds in
		1459	// Settings.
		1460	if ((__seqs_end - __seqs_begin > 1)
		1461	&& _GLIBCXX_PARALLEL_CONDITION(
		1462	((__seqs_end - __seqs_begin) >=
		1463	__gnu_parallel::_Settings::get().multiway_merge_minimal_k)
		1464	&& ((_SequenceIndex)__length >=
		1465	__gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
		1466	return parallel_multiway_merge
		1467
		1468	(__seqs_begin, __seqs_end, __target,
		1469	multiway_merge_exact_splitting
		1470	typename std::iterator_traits<_RAIterPairIterator>
		1471	::value_type*, _Compare, _DifferenceTp>,
		1472	static_cast<_DifferenceType>(__length), __comp,
		1473	__tag.__get_num_threads());
		1474	else
		1475	return __sequential_multiway_merge
		1476
		1477	(__seqs_begin, __seqs_end, __target,
		1478	*(__seqs_begin->second), __length, __comp);
		1479	}
		1480
		1481	// public interface
		1482	template
		1483	typename _RAIterOut,
		1484	typename _DifferenceTp,
		1485	typename _Compare>
		1486	_RAIterOut
		1487	multiway_merge(_RAIterPairIterator __seqs_begin,
		1488	_RAIterPairIterator __seqs_end,
		1489	_RAIterOut __target,
		1490	_DifferenceTp __length, _Compare __comp,
		1491	__gnu_parallel::sampling_tag __tag)
		1492	{
		1493	typedef _DifferenceTp _DifferenceType;
		1494	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1495
		1496	// catch special case: no sequences
		1497	if (__seqs_begin == __seqs_end)
		1498	return __target;
		1499
		1500	// Execute merge; maybe parallel, depending on the number of merged
		1501	// elements and the number of sequences and global thresholds in
		1502	// Settings.
		1503	if ((__seqs_end - __seqs_begin > 1)
		1504	&& _GLIBCXX_PARALLEL_CONDITION(
		1505	((__seqs_end - __seqs_begin) >=
		1506	__gnu_parallel::_Settings::get().multiway_merge_minimal_k)
		1507	&& ((_SequenceIndex)__length >=
		1508	__gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
		1509	return parallel_multiway_merge
		1510
		1511	(__seqs_begin, __seqs_end, __target,
		1512	multiway_merge_exact_splitting
		1513	typename std::iterator_traits<_RAIterPairIterator>
		1514	::value_type*, _Compare, _DifferenceTp>,
		1515	static_cast<_DifferenceType>(__length), __comp,
		1516	__tag.__get_num_threads());
		1517	else
		1518	return __sequential_multiway_merge
		1519
		1520	(__seqs_begin, __seqs_end, __target,
		1521	*(__seqs_begin->second), __length, __comp);
		1522	}
		1523
		1524	// public interface
		1525	template
		1526	typename _RAIterOut,
		1527	typename _DifferenceTp,
		1528	typename _Compare>
		1529	_RAIterOut
		1530	multiway_merge(_RAIterPairIterator __seqs_begin,
		1531	_RAIterPairIterator __seqs_end,
		1532	_RAIterOut __target,
		1533	_DifferenceTp __length, _Compare __comp,
		1534	parallel_tag __tag = parallel_tag(0))
		1535	{ return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
		1536	__comp, exact_tag(__tag.__get_num_threads())); }
		1537
		1538	// public interface
		1539	template
		1540	typename _RAIterOut,
		1541	typename _DifferenceTp,
		1542	typename _Compare>
		1543	_RAIterOut
		1544	multiway_merge(_RAIterPairIterator __seqs_begin,
		1545	_RAIterPairIterator __seqs_end,
		1546	_RAIterOut __target,
		1547	_DifferenceTp __length, _Compare __comp,
		1548	default_parallel_tag __tag)
		1549	{ return multiway_merge(__seqs_begin, __seqs_end, __target, __length,
		1550	__comp, exact_tag(__tag.__get_num_threads())); }
		1551
		1552	// stable_multiway_merge
		1553	// public interface
		1554	template
		1555	typename _RAIterOut,
		1556	typename _DifferenceTp,
		1557	typename _Compare>
		1558	_RAIterOut
		1559	stable_multiway_merge(_RAIterPairIterator __seqs_begin,
		1560	_RAIterPairIterator __seqs_end,
		1561	_RAIterOut __target,
		1562	_DifferenceTp __length, _Compare __comp,
		1563	__gnu_parallel::sequential_tag)
		1564	{
		1565	typedef _DifferenceTp _DifferenceType;
		1566	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1567
		1568	// catch special case: no sequences
		1569	if (__seqs_begin == __seqs_end)
		1570	return __target;
		1571
		1572	// Execute multiway merge sequentially.
		1573	return __sequential_multiway_merge
		1574
		1575	(__seqs_begin, __seqs_end, __target,
		1576	*(__seqs_begin->second), __length, __comp);
		1577	}
		1578
		1579	// public interface
		1580	template
		1581	typename _RAIterOut,
		1582	typename _DifferenceTp,
		1583	typename _Compare>
		1584	_RAIterOut
		1585	stable_multiway_merge(_RAIterPairIterator __seqs_begin,
		1586	_RAIterPairIterator __seqs_end,
		1587	_RAIterOut __target,
		1588	_DifferenceTp __length, _Compare __comp,
		1589	__gnu_parallel::exact_tag __tag)
		1590	{
		1591	typedef _DifferenceTp _DifferenceType;
		1592	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1593
		1594	// catch special case: no sequences
		1595	if (__seqs_begin == __seqs_end)
		1596	return __target;
		1597
		1598	// Execute merge; maybe parallel, depending on the number of merged
		1599	// elements and the number of sequences and global thresholds in
		1600	// Settings.
		1601	if ((__seqs_end - __seqs_begin > 1)
		1602	&& _GLIBCXX_PARALLEL_CONDITION(
		1603	((__seqs_end - __seqs_begin) >=
		1604	__gnu_parallel::_Settings::get().multiway_merge_minimal_k)
		1605	&& ((_SequenceIndex)__length >=
		1606	__gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
		1607	return parallel_multiway_merge
		1608
		1609	(__seqs_begin, __seqs_end, __target,
		1610	multiway_merge_exact_splitting
		1611	typename std::iterator_traits<_RAIterPairIterator>
		1612	::value_type*, _Compare, _DifferenceTp>,
		1613	static_cast<_DifferenceType>(__length), __comp,
		1614	__tag.__get_num_threads());
		1615	else
		1616	return __sequential_multiway_merge
		1617
		1618	(__seqs_begin, __seqs_end, __target,
		1619	*(__seqs_begin->second), __length, __comp);
		1620	}
		1621
		1622	// public interface
		1623	template
		1624	typename _RAIterOut,
		1625	typename _DifferenceTp,
		1626	typename _Compare>
		1627	_RAIterOut
		1628	stable_multiway_merge(_RAIterPairIterator __seqs_begin,
		1629	_RAIterPairIterator __seqs_end,
		1630	_RAIterOut __target,
		1631	_DifferenceTp __length, _Compare __comp,
		1632	sampling_tag __tag)
		1633	{
		1634	typedef _DifferenceTp _DifferenceType;
		1635	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1636
		1637	// catch special case: no sequences
		1638	if (__seqs_begin == __seqs_end)
		1639	return __target;
		1640
		1641	// Execute merge; maybe parallel, depending on the number of merged
		1642	// elements and the number of sequences and global thresholds in
		1643	// Settings.
		1644	if ((__seqs_end - __seqs_begin > 1)
		1645	&& _GLIBCXX_PARALLEL_CONDITION(
		1646	((__seqs_end - __seqs_begin) >=
		1647	__gnu_parallel::_Settings::get().multiway_merge_minimal_k)
		1648	&& ((_SequenceIndex)__length >=
		1649	__gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
		1650	return parallel_multiway_merge
		1651
		1652	(__seqs_begin, __seqs_end, __target,
		1653	multiway_merge_sampling_splitting
		1654	typename std::iterator_traits<_RAIterPairIterator>
		1655	::value_type*, _Compare, _DifferenceTp>,
		1656	static_cast<_DifferenceType>(__length), __comp,
		1657	__tag.__get_num_threads());
		1658	else
		1659	return __sequential_multiway_merge
		1660
		1661	(__seqs_begin, __seqs_end, __target,
		1662	*(__seqs_begin->second), __length, __comp);
		1663	}
		1664
		1665	// public interface
		1666	template
		1667	typename _RAIterOut,
		1668	typename _DifferenceTp,
		1669	typename _Compare>
		1670	_RAIterOut
		1671	stable_multiway_merge(_RAIterPairIterator __seqs_begin,
		1672	_RAIterPairIterator __seqs_end,
		1673	_RAIterOut __target,
		1674	_DifferenceTp __length, _Compare __comp,
		1675	parallel_tag __tag = parallel_tag(0))
		1676	{
		1677	return stable_multiway_merge
		1678	(__seqs_begin, __seqs_end, __target, __length, __comp,
		1679	exact_tag(__tag.__get_num_threads()));
		1680	}
		1681
		1682	// public interface
		1683	template
		1684	typename _RAIterOut,
		1685	typename _DifferenceTp,
		1686	typename _Compare>
		1687	_RAIterOut
		1688	stable_multiway_merge(_RAIterPairIterator __seqs_begin,
		1689	_RAIterPairIterator __seqs_end,
		1690	_RAIterOut __target,
		1691	_DifferenceTp __length, _Compare __comp,
		1692	default_parallel_tag __tag)
		1693	{
		1694	return stable_multiway_merge
		1695	(__seqs_begin, __seqs_end, __target, __length, __comp,
		1696	exact_tag(__tag.__get_num_threads()));
		1697	}
		1698
		1699	/**
		1700	* @brief Multiway Merge Frontend.
		1701	*
		1702	* Merge the sequences specified by seqs_begin and __seqs_end into
		1703	* __target. __seqs_begin and __seqs_end must point to a sequence of
		1704	* pairs. These pairs must contain an iterator to the beginning
		1705	* of a sequence in their first entry and an iterator the _M_end of
		1706	* the same sequence in their second entry.
		1707	*
		1708	* Ties are broken arbitrarily. See stable_multiway_merge for a variant
		1709	* that breaks ties by sequence number but is slower.
		1710	*
		1711	* The first entries of the pairs (i.e. the begin iterators) will be moved
		1712	* forward accordingly.
		1713	*
		1714	* The output sequence has to provide enough space for all elements
		1715	* that are written to it.
		1716	*
		1717	* This function will merge the input sequences:
		1718	*
		1719	* - not stable
		1720	* - parallel, depending on the input size and Settings
		1721	* - using sampling for splitting
		1722	* - using sentinels
		1723	*
		1724	* You have to take care that the element the _M_end iterator points to is
		1725	* readable and contains a value that is greater than any other non-sentinel
		1726	* value in all sequences.
		1727	*
		1728	* Example:
		1729	*
		1730	*
		1731	* int sequences[10][11];
		1732	* for (int __i = 0; __i < 10; ++__i)
		1733	* for (int __j = 0; __i < 11; ++__j)
		1734	* sequences[__i][__j] = __j; // __last one is sentinel!
		1735	*
		1736	* int __out[33];
		1737	* std::vector > seqs;
		1738	* for (int __i = 0; __i < 10; ++__i)
		1739	* { seqs.push(std::make_pair(sequences[__i],
		1740	* sequences[__i] + 10)) }
		1741	*
		1742	* multiway_merge(seqs.begin(), seqs.end(), __target, std::less(), 33);
		1743	*
		1744	*
		1745	* @pre All input sequences must be sorted.
		1746	* @pre Target must provide enough space to merge out length elements or
		1747	* the number of elements in all sequences, whichever is smaller.
		1748	* @pre For each @c __i, @c __seqs_begin[__i].second must be the end
		1749	* marker of the sequence, but also reference the one more __sentinel
		1750	* element.
		1751	*
		1752	* @post [__target, return __value) contains merged __elements from the
		1753	* input sequences.
		1754	* @post return __value - __target = min(__length, number of elements in all
		1755	* sequences).
		1756	*
		1757	* @see stable_multiway_merge_sentinels
		1758	*
		1759	* @tparam _RAIterPairIterator iterator over sequence
		1760	* of pairs of iterators
		1761	* @tparam _RAIterOut iterator over target sequence
		1762	* @tparam _DifferenceTp difference type for the sequence
		1763	* @tparam _Compare strict weak ordering type to compare elements
		1764	* in sequences
		1765	*
		1766	* @param __seqs_begin __begin of sequence __sequence
		1767	* @param __seqs_end _M_end of sequence __sequence
		1768	* @param __target target sequence to merge to.
		1769	* @param __comp strict weak ordering to use for element comparison.
		1770	* @param __length Maximum length to merge, possibly larger than the
		1771	* number of elements available.
		1772	*
		1773	* @return _M_end iterator of output sequence
		1774	*/
		1775	// multiway_merge_sentinels
		1776	// public interface
		1777	template
		1778	typename _RAIterOut,
		1779	typename _DifferenceTp,
		1780	typename _Compare>
		1781	_RAIterOut
		1782	multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
		1783	_RAIterPairIterator __seqs_end,
		1784	_RAIterOut __target,
		1785	_DifferenceTp __length, _Compare __comp,
		1786	__gnu_parallel::sequential_tag)
		1787	{
		1788	typedef _DifferenceTp _DifferenceType;
		1789	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1790
		1791	// catch special case: no sequences
		1792	if (__seqs_begin == __seqs_end)
		1793	return __target;
		1794
		1795	// Execute multiway merge sequentially.
		1796	return __sequential_multiway_merge
		1797
		1798	(__seqs_begin, __seqs_end,
		1799	__target, *(__seqs_begin->second), __length, __comp);
		1800	}
		1801
		1802	// public interface
		1803	template
		1804	typename _RAIterOut,
		1805	typename _DifferenceTp,
		1806	typename _Compare>
		1807	_RAIterOut
		1808	multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
		1809	_RAIterPairIterator __seqs_end,
		1810	_RAIterOut __target,
		1811	_DifferenceTp __length, _Compare __comp,
		1812	__gnu_parallel::exact_tag __tag)
		1813	{
		1814	typedef _DifferenceTp _DifferenceType;
		1815	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1816
		1817	// catch special case: no sequences
		1818	if (__seqs_begin == __seqs_end)
		1819	return __target;
		1820
		1821	// Execute merge; maybe parallel, depending on the number of merged
		1822	// elements and the number of sequences and global thresholds in
		1823	// Settings.
		1824	if ((__seqs_end - __seqs_begin > 1)
		1825	&& _GLIBCXX_PARALLEL_CONDITION(
		1826	((__seqs_end - __seqs_begin) >=
		1827	__gnu_parallel::_Settings::get().multiway_merge_minimal_k)
		1828	&& ((_SequenceIndex)__length >=
		1829	__gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
		1830	return parallel_multiway_merge
		1831
		1832	(__seqs_begin, __seqs_end, __target,
		1833	multiway_merge_exact_splitting
		1834	typename std::iterator_traits<_RAIterPairIterator>
		1835	::value_type*, _Compare, _DifferenceTp>,
		1836	static_cast<_DifferenceType>(__length), __comp,
		1837	__tag.__get_num_threads());
		1838	else
		1839	return __sequential_multiway_merge
		1840
		1841	(__seqs_begin, __seqs_end, __target,
		1842	*(__seqs_begin->second), __length, __comp);
		1843	}
		1844
		1845	// public interface
		1846	template
		1847	typename _RAIterOut,
		1848	typename _DifferenceTp,
		1849	typename _Compare>
		1850	_RAIterOut
		1851	multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
		1852	_RAIterPairIterator __seqs_end,
		1853	_RAIterOut __target,
		1854	_DifferenceTp __length, _Compare __comp,
		1855	sampling_tag __tag)
		1856	{
		1857	typedef _DifferenceTp _DifferenceType;
		1858	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1859
		1860	// catch special case: no sequences
		1861	if (__seqs_begin == __seqs_end)
		1862	return __target;
		1863
		1864	// Execute merge; maybe parallel, depending on the number of merged
		1865	// elements and the number of sequences and global thresholds in
		1866	// Settings.
		1867	if ((__seqs_end - __seqs_begin > 1)
		1868	&& _GLIBCXX_PARALLEL_CONDITION(
		1869	((__seqs_end - __seqs_begin) >=
		1870	__gnu_parallel::_Settings::get().multiway_merge_minimal_k)
		1871	&& ((_SequenceIndex)__length >=
		1872	__gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
		1873	return parallel_multiway_merge
		1874
		1875	(__seqs_begin, __seqs_end, __target,
		1876	multiway_merge_sampling_splitting
		1877	typename std::iterator_traits<_RAIterPairIterator>
		1878	::value_type*, _Compare, _DifferenceTp>,
		1879	static_cast<_DifferenceType>(__length), __comp,
		1880	__tag.__get_num_threads());
		1881	else
		1882	return __sequential_multiway_merge
		1883	(
		1884	__seqs_begin, __seqs_end, __target,
		1885	*(__seqs_begin->second), __length, __comp);
		1886	}
		1887
		1888	// public interface
		1889	template
		1890	typename _RAIterOut,
		1891	typename _DifferenceTp,
		1892	typename _Compare>
		1893	_RAIterOut
		1894	multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
		1895	_RAIterPairIterator __seqs_end,
		1896	_RAIterOut __target,
		1897	_DifferenceTp __length, _Compare __comp,
		1898	parallel_tag __tag = parallel_tag(0))
		1899	{
		1900	return multiway_merge_sentinels
		1901	(__seqs_begin, __seqs_end, __target, __length, __comp,
		1902	exact_tag(__tag.__get_num_threads()));
		1903	}
		1904
		1905	// public interface
		1906	template
		1907	typename _RAIterOut,
		1908	typename _DifferenceTp,
		1909	typename _Compare>
		1910	_RAIterOut
		1911	multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
		1912	_RAIterPairIterator __seqs_end,
		1913	_RAIterOut __target,
		1914	_DifferenceTp __length, _Compare __comp,
		1915	default_parallel_tag __tag)
		1916	{
		1917	return multiway_merge_sentinels
		1918	(__seqs_begin, __seqs_end, __target, __length, __comp,
		1919	exact_tag(__tag.__get_num_threads()));
		1920	}
		1921
		1922	// stable_multiway_merge_sentinels
		1923	// public interface
		1924	template
		1925	typename _RAIterOut,
		1926	typename _DifferenceTp,
		1927	typename _Compare>
		1928	_RAIterOut
		1929	stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
		1930	_RAIterPairIterator __seqs_end,
		1931	_RAIterOut __target,
		1932	_DifferenceTp __length, _Compare __comp,
		1933	__gnu_parallel::sequential_tag)
		1934	{
		1935	typedef _DifferenceTp _DifferenceType;
		1936	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1937
		1938	// catch special case: no sequences
		1939	if (__seqs_begin == __seqs_end)
		1940	return __target;
		1941
		1942	// Execute multiway merge sequentially.
		1943	return __sequential_multiway_merge
		1944
		1945	(__seqs_begin, __seqs_end, __target,
		1946	*(__seqs_begin->second), __length, __comp);
		1947	}
		1948
		1949	// public interface
		1950	template
		1951	typename _RAIterOut,
		1952	typename _DifferenceTp,
		1953	typename _Compare>
		1954	_RAIterOut
		1955	stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
		1956	_RAIterPairIterator __seqs_end,
		1957	_RAIterOut __target,
		1958	_DifferenceTp __length, _Compare __comp,
		1959	__gnu_parallel::exact_tag __tag)
		1960	{
		1961	typedef _DifferenceTp _DifferenceType;
		1962	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		1963
		1964	// catch special case: no sequences
		1965	if (__seqs_begin == __seqs_end)
		1966	return __target;
		1967
		1968	// Execute merge; maybe parallel, depending on the number of merged
		1969	// elements and the number of sequences and global thresholds in
		1970	// Settings.
		1971	if ((__seqs_end - __seqs_begin > 1)
		1972	&& _GLIBCXX_PARALLEL_CONDITION(
		1973	((__seqs_end - __seqs_begin) >=
		1974	__gnu_parallel::_Settings::get().multiway_merge_minimal_k)
		1975	&& ((_SequenceIndex)__length >=
		1976	__gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
		1977	return parallel_multiway_merge
		1978
		1979	(__seqs_begin, __seqs_end, __target,
		1980	multiway_merge_exact_splitting
		1981	typename std::iterator_traits<_RAIterPairIterator>
		1982	::value_type*, _Compare, _DifferenceTp>,
		1983	static_cast<_DifferenceType>(__length), __comp,
		1984	__tag.__get_num_threads());
		1985	else
		1986	return __sequential_multiway_merge
		1987
		1988	(__seqs_begin, __seqs_end, __target,
		1989	*(__seqs_begin->second), __length, __comp);
		1990	}
		1991
		1992	// public interface
		1993	template
		1994	typename _RAIterOut,
		1995	typename _DifferenceTp,
		1996	typename _Compare>
		1997	_RAIterOut
		1998	stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
		1999	_RAIterPairIterator __seqs_end,
		2000	_RAIterOut __target,
		2001	_DifferenceTp __length,
		2002	_Compare __comp,
		2003	sampling_tag __tag)
		2004	{
		2005	typedef _DifferenceTp _DifferenceType;
		2006	_GLIBCXX_CALL(__seqs_end - __seqs_begin)
		2007
		2008	// catch special case: no sequences
		2009	if (__seqs_begin == __seqs_end)
		2010	return __target;
		2011
		2012	// Execute merge; maybe parallel, depending on the number of merged
		2013	// elements and the number of sequences and global thresholds in
		2014	// Settings.
		2015	if ((__seqs_end - __seqs_begin > 1)
		2016	&& _GLIBCXX_PARALLEL_CONDITION(
		2017	((__seqs_end - __seqs_begin) >=
		2018	__gnu_parallel::_Settings::get().multiway_merge_minimal_k)
		2019	&& ((_SequenceIndex)__length >=
		2020	__gnu_parallel::_Settings::get().multiway_merge_minimal_n)))
		2021	return parallel_multiway_merge
		2022
		2023	(__seqs_begin, __seqs_end, __target,
		2024	multiway_merge_sampling_splitting
		2025	typename std::iterator_traits<_RAIterPairIterator>
		2026	::value_type*, _Compare, _DifferenceTp>,
		2027	static_cast<_DifferenceType>(__length), __comp,
		2028	__tag.__get_num_threads());
		2029	else
		2030	return __sequential_multiway_merge
		2031
		2032	(__seqs_begin, __seqs_end, __target,
		2033	*(__seqs_begin->second), __length, __comp);
		2034	}
		2035
		2036	// public interface
		2037	template
		2038	typename _RAIterOut,
		2039	typename _DifferenceTp,
		2040	typename _Compare>
		2041	_RAIterOut
		2042	stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
		2043	_RAIterPairIterator __seqs_end,
		2044	_RAIterOut __target,
		2045	_DifferenceTp __length,
		2046	_Compare __comp,
		2047	parallel_tag __tag = parallel_tag(0))
		2048	{
		2049	return stable_multiway_merge_sentinels
		2050	(__seqs_begin, __seqs_end, __target, __length, __comp,
		2051	exact_tag(__tag.__get_num_threads()));
		2052	}
		2053
		2054	// public interface
		2055	template
		2056	typename _RAIterOut,
		2057	typename _DifferenceTp,
		2058	typename _Compare>
		2059	_RAIterOut
		2060	stable_multiway_merge_sentinels(_RAIterPairIterator __seqs_begin,
		2061	_RAIterPairIterator __seqs_end,
		2062	_RAIterOut __target,
		2063	_DifferenceTp __length, _Compare __comp,
		2064	default_parallel_tag __tag)
		2065	{
		2066	return stable_multiway_merge_sentinels
		2067	(__seqs_begin, __seqs_end, __target, __length, __comp,
		2068	exact_tag(__tag.__get_num_threads()));
		2069	}
		2070	}; // namespace __gnu_parallel
		2071
		2072	#endif /* _GLIBCXX_PARALLEL_MULTIWAY_MERGE_H */

Subversion Repositories Kolibri OS

(root)/contrib/sdk/sources/libstdc++-v3/include/parallel/multiway_merge.h – Rev 5136