32 #pragma pack(push,_CRT_PACKING)
33 #pragma push_macro("new")
38 #define _TRACE_LEVEL_INFORMATION 4
52 class structured_task_group;
84 template<
typename _Function>
103 m_pFunction = reinterpret_cast <
TaskProc> (&::Concurrency::details::_UnrealizedChore::_InvokeBridge<task_handle>);
164 template <
class _Function>
284 template<
class _Function>
322 template<
class _Function>
387 template<
class _Function>
426 template<
class _Function>
572 template<
typename _Function>
573 void run(
const _Function& _Func)
613 template<
typename _Function>
652 template<
typename _Function>
695 template<
typename _Function>
756 template<
class _Function>
795 template<
class _Function>
864 template<
typename _Function>
907 template <
typename _Function1,
typename _Function2>
913 _Task_group.
run(_Task_handle1);
944 template <
typename _Function1,
typename _Function2>
984 template <
typename _Function1,
typename _Function2,
typename _Function3>
985 void parallel_invoke(
const _Function1& _Func1,
const _Function2& _Func2,
const _Function3& _Func3)
992 _Task_group.
run(_Task_handle1);
995 _Task_group.
run(_Task_handle2);
1039 template <
typename _Function1,
typename _Function2,
typename _Function3,
typename _Function4>
1040 void parallel_invoke(
const _Function1& _Func1,
const _Function2& _Func2,
const _Function3& _Func3,
const _Function4& _Func4)
1047 _Task_group.
run(_Task_handle1);
1050 _Task_group.
run(_Task_handle2);
1053 _Task_group.
run(_Task_handle3);
1103 template <
typename _Function1,
typename _Function2,
typename _Function3,
typename _Function4,
typename _Function5>
1104 void parallel_invoke(
const _Function1& _Func1,
const _Function2& _Func2,
const _Function3& _Func3,
const _Function4& _Func4,
const _Function5& _Func5)
1111 _Task_group.
run(_Task_handle1);
1114 _Task_group.
run(_Task_handle2);
1117 _Task_group.
run(_Task_handle3);
1120 _Task_group.
run(_Task_handle4);
1176 template <
typename _Function1,
typename _Function2,
typename _Function3,
typename _Function4,
typename _Function5,
1177 typename _Function6>
1178 void parallel_invoke(
const _Function1& _Func1,
const _Function2& _Func2,
const _Function3& _Func3,
const _Function4& _Func4,
const _Function5& _Func5,
1179 const _Function6& _Func6)
1186 _Task_group.
run(_Task_handle1);
1189 _Task_group.
run(_Task_handle2);
1192 _Task_group.
run(_Task_handle3);
1195 _Task_group.
run(_Task_handle4);
1198 _Task_group.
run(_Task_handle5);
1260 template <
typename _Function1,
typename _Function2,
typename _Function3,
typename _Function4,
typename _Function5,
1261 typename _Function6,
typename _Function7>
1262 void parallel_invoke(
const _Function1& _Func1,
const _Function2& _Func2,
const _Function3& _Func3,
const _Function4& _Func4,
const _Function5& _Func5,
1263 const _Function6& _Func6,
const _Function7& _Func7)
1270 _Task_group.
run(_Task_handle1);
1273 _Task_group.
run(_Task_handle2);
1276 _Task_group.
run(_Task_handle3);
1279 _Task_group.
run(_Task_handle4);
1282 _Task_group.
run(_Task_handle5);
1285 _Task_group.
run(_Task_handle6);
1353 template <
typename _Function1,
typename _Function2,
typename _Function3,
typename _Function4,
typename _Function5,
1354 typename _Function6,
typename _Function7,
typename _Function8>
1355 void parallel_invoke(
const _Function1& _Func1,
const _Function2& _Func2,
const _Function3& _Func3,
const _Function4& _Func4,
const _Function5& _Func5,
1356 const _Function6& _Func6,
const _Function7& _Func7,
const _Function8& _Func8)
1363 _Task_group.
run(_Task_handle1);
1366 _Task_group.
run(_Task_handle2);
1369 _Task_group.
run(_Task_handle3);
1372 _Task_group.
run(_Task_handle4);
1375 _Task_group.
run(_Task_handle5);
1378 _Task_group.
run(_Task_handle6);
1381 _Task_group.
run(_Task_handle7);
1455 template <
typename _Function1,
typename _Function2,
typename _Function3,
typename _Function4,
typename _Function5,
1456 typename _Function6,
typename _Function7,
typename _Function8,
typename _Function9>
1457 void parallel_invoke(
const _Function1& _Func1,
const _Function2& _Func2,
const _Function3& _Func3,
const _Function4& _Func4,
const _Function5& _Func5,
1458 const _Function6& _Func6,
const _Function7& _Func7,
const _Function8& _Func8,
const _Function9& _Func9)
1465 _Task_group.
run(_Task_handle1);
1468 _Task_group.
run(_Task_handle2);
1471 _Task_group.
run(_Task_handle3);
1474 _Task_group.
run(_Task_handle4);
1477 _Task_group.
run(_Task_handle5);
1480 _Task_group.
run(_Task_handle6);
1483 _Task_group.
run(_Task_handle7);
1486 _Task_group.
run(_Task_handle8);
1566 template <
typename _Function1,
typename _Function2,
typename _Function3,
typename _Function4,
typename _Function5,
1567 typename _Function6,
typename _Function7,
typename _Function8,
typename _Function9,
typename _Function10>
1568 void parallel_invoke(
const _Function1& _Func1,
const _Function2& _Func2,
const _Function3& _Func3,
const _Function4& _Func4,
const _Function5& _Func5,
1569 const _Function6& _Func6,
const _Function7& _Func7,
const _Function8& _Func8,
const _Function9& _Func9,
const _Function10& _Func10)
1576 _Task_group.
run(_Task_handle1);
1579 _Task_group.
run(_Task_handle2);
1582 _Task_group.
run(_Task_handle3);
1585 _Task_group.
run(_Task_handle4);
1588 _Task_group.
run(_Task_handle5);
1591 _Task_group.
run(_Task_handle6);
1594 _Task_group.
run(_Task_handle7);
1597 _Task_group.
run(_Task_handle8);
1600 _Task_group.
run(_Task_handle9);
1629 template<
class _Type>
1658 template<
class _Type>
1685 if (_Chunk_size == 0)
1687 throw std::invalid_argument(
"_Chunk_size");
1697 template<
class _Type>
1700 static_assert(
sizeof(_Type) <=
sizeof(_Size_type),
"Potential truncation of _Range_arg");
1701 _Size_type _Num_chunks = (
static_cast<_Size_type
>(_Range_arg) /
_M_chunk_size);
1703 if (_Num_chunks == 0)
1708 return static_cast<_Type
>(_Num_chunks);
1749 template<
class _Type>
1773 #pragma warning(push)
1774 #pragma warning(disable: 4180)
1776 #pragma warning(disable: 6263)
1780 template <
typename _Random_iterator,
typename _Index_type,
typename _Function,
bool _Is_iterator>
1784 static void __cdecl
_Invoke(
const _Random_iterator& _First, _Index_type& _Index,
const _Function& _Func)
1786 _Func(_First[_Index]);
1792 template <
typename _Random_iterator,
typename _Index_type,
typename _Function>
1796 static void __cdecl
_Invoke(
const _Random_iterator& _First, _Index_type& _Index,
const _Function& _Func)
1798 _Func(static_cast<_Random_iterator>(_First + _Index));
1804 template<
typename _Index_type>
1810 _Range(_Index_type _Current_iteration, _Index_type _Last_iteration) :
1824 if (_Remaining_iterations > 1)
1827 _M_last_iteration = _M_current_iteration + _Remaining_iterations / 2;
1834 _Helper_range->_M_current_iteration = _M_last_iteration;
1843 _Index_type _Current_iter = _M_current_iteration;
1845 _Helper_range->_M_current_iteration = _Current_iter + 1;
1846 _Helper_range->_M_last_iteration = _M_last_iteration;
1848 _M_last_iteration = _Current_iter + 1;
1854 return (_M_last_iteration - _M_current_iteration);
1895 template<typename _Index_type>
1900 _M_pHelper_range(
NULL), _M_pParent_worker(_PParent_worker), _M_pWorker_range(
NULL), _M_completion_count(0), _M_stop_iterating(0)
1908 if (_M_completion_count != _Tree_Complete)
1911 _Propagate_cancel();
1922 if (_M_completion_count)
1933 _Index_type _Cached_first_iteration = _Helper_range->_M_current_iteration;
1941 _M_pHelper_range = _Helper_range;
1947 while ((_Helper_range->_M_current_iteration == _Cached_first_iteration) && !_M_completion_count)
1949 if ((_M_pWorker_range !=
NULL) && _M_context._IsSynchronouslyBlocked())
1967 if ((_Worker_range !=
NULL) && _M_context._IsSynchronouslyBlocked()
1968 && (_Helper_range->_M_current_iteration == _Cached_first_iteration) && !_M_completion_count)
1972 _M_pHelper_range =
NULL;
1975 _CONCRT_ASSERT(_Helper_range->_M_current_iteration != _Cached_first_iteration);
1994 if (_Helper_range->_M_current_iteration == _Cached_first_iteration)
2015 _InterlockedExchangePointer(reinterpret_cast<void * volatile *>(&_M_pHelper_range),
NULL);
2028 _M_pWorker_range = _Worker_range;
2034 _M_pWorker_range =
NULL;
2035 _Wait_on_intrusive_steal();
2040 return (_M_pHelper_range !=
NULL);
2045 return (_M_completion_count != 0);
2053 _InterlockedExchange(&_M_completion_count, 1);
2059 _M_completion_count = _Tree_Complete;
2064 return _M_beacon._Is_signaled();
2069 return _M_beacon._Confirm_cancel();
2078 if (_M_stop_iterating != 0)
2082 while (_M_stop_iterating != 0)
2096 if (_M_pParent_worker !=
NULL)
2098 _M_pParent_worker->_NotifyCancel();
2103 static const long _Tree_Complete = 2;
2121 _Worker_proxy
const & operator=(_Worker_proxy
const&);
2133 template <
typename _Random_iterator,
typename _Index_type,
typename _Function,
typename _Partitioner,
bool _Is_iterator>
2137 _Parallel_chunk_helper(_Index_type,
const _Random_iterator& _First, _Index_type _First_iteration, _Index_type _Last_iteration,
const _Index_type& _Step,
2139 _M_first(_First), _M_first_iteration(_First_iteration), _M_last_iteration(_Last_iteration), _M_step(_Step), _M_function(_Func),
2140 _M_parent_worker(_Parent_data)
2148 _M_first(_First), _M_first_iteration(_Worker_range._M_current_iteration), _M_last_iteration(_Worker_range._M_last_iteration), _M_step(_Step), _M_function(_Func),
2149 _M_parent_worker(_Parent_data)
2167 if (_M_parent_worker !=
NULL && !_M_parent_worker->_Receive_range(&_Worker_range))
2174 _Index_type _Current_iteration = _Worker_range._M_current_iteration;
2175 _Index_type _Scaled_index = _Current_iteration * _M_step;
2198 _Helper_group.
run(_Helper_task);
2207 for (_Index_type _I = _Current_iteration; _I < _Worker_range._M_last_iteration; (_I++, _Worker_range._M_current_iteration =_I, _Scaled_index += _M_step))
2237 _Helper_group.
run(*_Helper_subtask);
2255 _Helper_group.
wait();
2276 template <
typename _Random_iterator,
typename _Index_type,
typename _Function,
typename _Partitioner,
bool _Is_iterator>
2281 _Index_type _Last_iteration,
const _Index_type& _Step,
const _Function& _Func,
const _Partitioner&) :
2282 _M_first(_First), _M_first_iteration(_First_iteration), _M_last_iteration(_Last_iteration), _M_step(_Step), _M_function(_Func)
2290 _Index_type _Scaled_index = _M_first_iteration * _M_step;
2292 for (_Index_type _I = _M_first_iteration; _I < _M_last_iteration; (_I++, _Scaled_index += _M_step))
2310 template <
typename _Random_iterator,
typename _Index_type,
typename _Function,
bool _Is_iterator>
2316 _Parallel_localized_chunk_helper(_Index_type _Chunk_index,
const _Random_iterator& _First, _Index_type _First_iteration, _Index_type _Last_iteration,
const _Index_type& _Step,
2318 _M_fixed_helper(_Chunk_index, _First, _First_iteration, _Last_iteration, _Step, _Func,
static_partitioner()),
2319 _M_chunk_location(_Part._Get_chunk_location(static_cast<unsigned
int>(_Chunk_index)))
2328 if (_M_chunk_location._Is_system())
2342 #pragma warning(pop)
2344 template <
typename _Worker_
class,
typename _Index_type,
typename Partitioner>
2350 _Task_group.
run(_Chunk_helpers[_I]);
2353 template <
typename _Worker_
class,
typename _Index_type>
2365 template <
typename _Worker_
class,
typename _Random_iterator,
typename _Index_type,
typename _Function,
typename _Partitioner>
2366 void _Parallel_chunk_impl(
const _Random_iterator& _First, _Index_type _Range_arg,
const _Index_type& _Step,
const _Function& _Func, _Partitioner&& _Part)
2371 _Index_type _Num_iterations = (_Step == 1) ? _Range_arg : (((_Range_arg - 1) / _Step) + 1);
2374 _Index_type _Num_chunks = _Part._Get_num_chunks(_Num_iterations);
2383 _Index_type _Iterations_per_chunk = _Num_iterations / _Num_chunks;
2384 _Index_type _Remaining_iterations = _Num_iterations % _Num_chunks;
2388 if (_Iterations_per_chunk == 0)
2390 _Num_chunks = _Remaining_iterations;
2393 _Index_type _Work_size = 0;
2394 _Index_type _Start_iteration = 0;
2398 for (_I = 0; _I < _Num_chunks - 1; _I++)
2400 if (_Remaining_iterations > 0)
2403 _Work_size = _Iterations_per_chunk + 1;
2404 _Remaining_iterations--;
2408 _Work_size = _Iterations_per_chunk;
2412 new(&_Chunk_helpers[_I])
task_handle<_Worker_class>(_Worker_class(_I, _First, _Start_iteration, _Start_iteration + _Work_size, _Step, _Func, std::forward<_Partitioner>(_Part)));
2419 _Start_iteration += _Work_size;
2423 _CONCRT_ASSERT((_Remaining_iterations == 0) || ((_Iterations_per_chunk == 0) && (_Remaining_iterations == 1)));
2424 _Work_size = _Num_iterations - _Start_iteration;
2427 new(&_Chunk_helpers[_I])
task_handle<_Worker_class>(_Worker_class(_I, _First, _Start_iteration, _Start_iteration + _Work_size, _Step, _Func, std::forward<_Partitioner>(_Part)));
2433 template <
typename _Worker_
class,
typename _Random_iterator,
typename _Index_type,
typename _Function>
2434 void _Parallel_chunk_impl(
const _Random_iterator& _First, _Index_type _Range_arg,
const _Index_type& _Step,
const _Function& _Func)
2436 _Parallel_chunk_impl<_Worker_class>(_First, _Range_arg, _Step, _Func,
auto_partitioner());
2440 template <
typename _Index_type,
typename _Diff_type,
typename _Function>
2444 _Parallel_chunk_impl<_Worker_class>(_First, _Range_arg, _Step, _Func, _Part);
2448 template <
typename _Index_type,
typename _Diff_type,
typename _Function>
2452 _Parallel_chunk_impl<_Worker_class>(_First, _Range_arg, _Step, _Func, _Part);
2456 template <
typename _Index_type,
typename _Diff_type,
typename _Function>
2460 _Parallel_chunk_impl<_Worker_class>(_First, _Range_arg, _Step, _Func, _Part);
2465 template <
typename _Index_type,
typename _Diff_type,
typename _Function>
2469 _Parallel_chunk_impl<_Worker_class>(_First, _Range_arg, _Step, _Func, _Part);
2472 template <
typename _Index_type,
typename _Function,
typename _Partitioner>
2478 throw std::invalid_argument(
"_Step");
2482 if (_First >= _Last)
2488 typedef typename std::conditional<std::is_same<_Index_type, int>::value,
unsigned int,
2489 typename std::conditional<std::is_same<_Index_type, long>::value,
unsigned long,
2490 typename std::conditional<std::is_same<_Index_type, long long>::value,
unsigned long long, decltype(_Last - _First)
2495 _Diff_type _Range_size = _Diff_type(_Last) - _Diff_type(_First);
2496 _Diff_type _Diff_step = _Step;
2498 if (_Range_size <= _Diff_step)
2504 _Parallel_for_partitioned_impl<_Index_type, _Diff_type, _Function>(_First, _Range_size, _Step, _Func, std::forward<_Partitioner>(_Part));
2508 template <
typename _Index_type,
typename _Function>
2554 template <
typename _Index_type,
typename _Function,
typename _Partitioner>
2555 void parallel_for(_Index_type _First, _Index_type
_Last, _Index_type _Step,
const _Function& _Func, _Partitioner&& _Part)
2590 template <
typename _Index_type,
typename _Function>
2629 template <
typename _Index_type,
typename _Function>
2632 parallel_for(_First, _Last, _Index_type(1), _Func, _Part);
2668 template <
typename _Index_type,
typename _Function>
2671 parallel_for(_First, _Last, _Index_type(1), _Func, _Part);
2707 template <
typename _Index_type,
typename _Function>
2710 parallel_for(_First, _Last, _Index_type(1), _Func, _Part);
2746 template <
typename _Index_type,
typename _Function>
2749 parallel_for(_First, _Last, _Index_type(1), _Func, _Part);
2762 #pragma warning(push)
2763 #pragma warning(disable: 4180)
2765 template <
typename _Forward_iterator,
typename _Function,
unsigned int _Chunk_size>
2769 typedef typename std::iterator_traits<_Forward_iterator>::value_type
_Value_type;
2770 static const unsigned int _Size = _Chunk_size;
2773 _M_function(_Func), _M_len(0)
2775 static_assert(std::is_lvalue_reference<decltype(*_First)>::value,
"lvalue required for forward iterator operator *");
2777 for (
unsigned int _Index=0; (_Index <
_Size) && (_First != _Last); _Index++)
2779 _M_element[_M_len++] = &(*_First++);
2787 [
this] (
unsigned int _Index)
2789 _M_function(*(_M_element[_Index]));
2797 typename std::iterator_traits<_Forward_iterator>::pointer _M_element[
_Size];
2803 #pragma warning(pop)
2807 template <
typename _Forward_iterator,
typename _Function>
2813 const unsigned int _Chunk_size = 1024;
2820 _Task_group.
run(_Functor);
2823 template <
typename _Forward_iterator,
typename _Function>
2829 if (_First != _Last)
2832 [&_First, &_Last, &_Func, &_Task_group]
2840 template <
typename _Forward_iterator,
typename _Function>
2845 if (_First != _Last)
2855 template <
typename _Random_iterator,
typename _Index_type,
typename _Function>
2860 _Parallel_chunk_impl<_Worker_class>(_First, _Range_arg, _Step, _Func, _Part);
2863 template <
typename _Random_iterator,
typename _Index_type,
typename _Function>
2868 _Parallel_chunk_impl<_Worker_class>(_First, _Range_arg, _Step, _Func, _Part);
2871 template <
typename _Random_iterator,
typename _Index_type,
typename _Function>
2876 _Parallel_chunk_impl<_Worker_class>(_First, _Range_arg, _Step, _Func, _Part);
2879 template <
typename _Random_iterator,
typename _Index_type,
typename _Function>
2884 _Parallel_chunk_impl<_Worker_class>(_First, _Range_arg, _Step, _Func, _Part);
2887 template <
typename _Random_iterator,
typename _Function,
typename _Partitioner>
2888 void _Parallel_for_each_impl(
const _Random_iterator& _First,
const _Random_iterator& _Last,
const _Function& _Func, _Partitioner&& _Part, std::random_access_iterator_tag)
2890 typedef typename std::iterator_traits<_Random_iterator>::difference_type _Index_type;
2893 if (_First >= _Last)
2898 _Index_type _Range_size = _Last - _First;
2900 if (_Range_size == 1)
2906 _Index_type _Step = 1;
2940 template <
typename _Iterator,
typename _Function>
2983 template <
typename _Iterator,
typename _Function,
typename _Partitioner>
2984 void parallel_for_each(_Iterator _First, _Iterator _Last,
const _Function& _Func, _Partitioner&& _Part)
2987 _Parallel_for_each_impl(_First, _Last, _Func, std::forward<_Partitioner>(_Part),
typename std::iterator_traits<_Iterator>::iterator_category());
2993 #pragma warning(push)
2994 #pragma warning(disable: 4180)
2997 template <
typename _Reduce_type,
typename _Sub_function,
typename _Combinable_type>
3009 _Sub_fun(_Sub_fun), _Combinable(_Comb), _Identity_value(_Identity)
3018 template<
typename _Ty,
typename _Sym_fun>
3037 _Item->
_Next = _Next;
3044 new(
reinterpret_cast<_Ty *
>(&
_Value)) _Ty(_Cur);
3058 return new(_Ret)
_Bucket(_Par);
3072 _M_root = _M_root->
_Next;
3073 reinterpret_cast<_Ty &
>(_Cur->
_Value).~_Ty();
3081 _Ty _Ret(reinterpret_cast<_Ty &>(_M_root->
_Value));
3083 _M_root = _M_root->
_Next;
3087 reinterpret_cast<_Ty &
>(_Cur->
_Value).~_Ty();
3090 _Ret = _M_fun(reinterpret_cast <_Ty &> (_Cur->
_Value), _Ret);
3091 _M_root = _M_root->
_Next;
3094 reinterpret_cast<_Ty &
>(_Cur->
_Value).~_Ty();
3165 template<
typename _Reduce_type,
typename _Forward_iterator,
typename _Range_reduce_fun,
typename _Sym_reduce_fun>
3167 const _Range_reduce_fun &_Range_fun,
const _Sym_reduce_fun &_Sym_fun)
3169 typedef typename std::iterator_traits<_Forward_iterator>::value_type _Value_type;
3171 static_assert(!std::is_same<
typename std::iterator_traits<_Forward_iterator>::iterator_category, std::input_iterator_tag>::value
3172 && !std::is_same<
typename std::iterator_traits<_Forward_iterator>::iterator_category, std::output_iterator_tag>::value,
3173 "iterator can not be input_iterator or output_iterator.");
3178 typename std::iterator_traits<_Forward_iterator>::iterator_category());
3228 template<
typename _Forward_iterator,
typename _Sym_reduce_fun>
3229 inline typename std::iterator_traits<_Forward_iterator>::value_type
parallel_reduce(_Forward_iterator _Begin, _Forward_iterator _End,
3230 const typename std::iterator_traits<_Forward_iterator>::value_type &
_Identity, _Sym_reduce_fun _Sym_fun)
3232 typedef typename std::remove_cv<typename std::iterator_traits<_Forward_iterator>::value_type>::type _Reduce_type;
3235 [_Sym_fun](_Forward_iterator _Begin, _Forward_iterator _End, _Reduce_type _Init)->_Reduce_type
3237 while (_Begin != _End)
3239 _Init = _Sym_fun(_Init, *_Begin++);
3286 template<
typename _Forward_iterator>
3288 _Forward_iterator _Begin, _Forward_iterator _End,
const typename std::iterator_traits<_Forward_iterator>::value_type &
_Identity)
3290 return parallel_reduce(_Begin, _End, _Identity, std::plus<
typename std::iterator_traits<_Forward_iterator>::value_type>());
3294 template <
typename _Forward_iterator,
typename _Function>
3295 typename _Function::_Reduce_type
_Parallel_reduce_impl(_Forward_iterator _First,
const _Forward_iterator& _Last,
const _Function& _Func,
3296 std::forward_iterator_tag)
3300 if (_First != _Last)
3305 return _Func._Combinable._Serial_combine_release();
3309 return _Func._Identity_value;
3314 template<
typename _Forward_iterator,
typename _Functor>
3320 _M_begin(_Begin), _M_end(_End), _M_fun(_Fun), _M_bucket(_M_fun._Combinable._Unsafe_push_back())
3324 void operator ()()
const
3326 _M_bucket->_Put(_M_fun._Sub_fun(_M_begin, _M_end, _M_fun._Identity_value));
3336 template <
typename _Worker,
typename _Random_iterator,
typename _Function>
3339 template <
typename _Random_iterator,
typename _Function>
3340 typename _Function::_Reduce_type
_Parallel_reduce_impl(_Random_iterator _First, _Random_iterator _Last,
const _Function& _Func,
3341 std::random_access_iterator_tag)
3346 if (_First >= _Last)
3348 return _Func._Identity_value;
3351 else if (_Last - _First <= 1)
3353 _Worker_class(_First, _Last, _Func)();
3354 return _Func._Combinable._Serial_combine_release();
3359 _Parallel_reduce_random_executor<_Worker_class>(_First,
_Last, _Func);
3360 return _Func._Combinable._Serial_combine_release();
3367 template <
typename _Worker,
typename _Random_iterator,
typename _Function>
3376 size_t _Begin_index = 0;
3377 size_t _Step =
_Size / _Cpu_num;
3378 size_t _NumRemaining =
_Size - _Step * _Cpu_num;
3380 for(
size_t _I = 0; _I < _Cpu_num - 1; _I++)
3382 size_t _Next = _Begin_index + _Step;
3396 _Tg.
run(_Tasks[_I]);
3397 _Begin_index = _Next;
3406 template <
typename _Forward_iterator,
typename _Function,
int _Default_worker_size,
int _Default_chunk_size>
3410 mutable std::auto_ptr<task_handle<_Worker_class>>
_Workers;
3417 while (_Worker_size < _Default_worker_size && _First != _Last)
3420 _Forward_iterator _Head = _First;
3423 for (
size_t _I = 0; _I < _Default_chunk_size && _First !=
_Last; ++_I, ++_First)
3434 _Workers(_Other._Workers), _Worker_size(_Other._Worker_size)
3438 void operator ()()
const
3441 for(
int _I = 0; _I < _Worker_size; _I++)
3443 _Tg.
run(_Workers.get()[_I]);
3452 for (
int _I = 0; _I < _Worker_size; _I++)
3454 _Workers.get()[_I].~task_handle<_Worker_class>();
3461 template <
typename _Forward_iterator,
typename _Function>
3464 const static int _Internal_worker_number = 1024, _Default_chunk_size = 512;
3473 while (_Index < _Internal_worker_number && _First != _Last)
3476 _Forward_iterator _Head = _First;
3479 for (
size_t _I = 0; _I < _Default_chunk_size && _First !=
_Last; ++_I, ++_First)
3487 _Worker_group.
run(_Workers[_Index]);
3492 while (_First != _Last)
3497 _Worker_group.
wait();
3500 #pragma warning(pop)
3505 #pragma warning(push)
3506 #pragma warning(disable: 4180)
3511 template<
typename _Any_input_traits,
typename _Any_output_traits>
3514 template<
typename _Input_iterator,
typename _Output_iterator,
typename _Unary_operator>
3526 template<
typename _Random_input_iterator,
typename _Random_output_iterator,
typename _Unary_operator,
typename _Partitioner>
3528 _Random_output_iterator& _Result,
const _Unary_operator& _Unary_op, _Partitioner&& _Part)
3533 [_Begin, &_Result, &_Unary_op](
size_t _Index)
3535 _Result[_Index] = _Unary_op(_Begin[_Index]);
3537 std::forward<_Partitioner>(_Part));
3538 _Result += _End - _Begin;
3543 template<
typename _Any_input_traits1,
typename _Any_input_traits2,
typename _Any_output_traits>
3547 template<
typename _Input_iterator1,
typename _Input_iterator2,
typename _Output_iterator,
typename _Binary_operator>
3549 _Output_iterator& _Result,
const _Binary_operator& _Binary_op,
const auto_partitioner&)
3560 template<
typename _Random_input_iterator1,
typename _Random_input_iterator2,
typename _Random_output_iterator,
typename _Binary_operator,
typename _Partitioner>
3562 _Random_input_iterator2 _Begin2, _Random_output_iterator& _Result,
const _Binary_operator& _Binary_op, _Partitioner&& _Part)
3564 if (_Begin1 < _End1)
3567 [_Begin1, _Begin2, &_Result, &_Binary_op](
size_t _Index)
3569 _Result[_Index] = _Binary_op(_Begin1[_Index], _Begin2[_Index]);
3571 std::forward<_Partitioner>(_Part));
3572 _Result += _End1 - _Begin1;
3580 template <
typename _Forward_iterator,
typename _Iterator_kind>
3585 typedef typename std::iterator_traits<_Forward_iterator>::value_type
value_type;
3589 static_assert(!std::is_same<_Iterator_kind, std::input_iterator_tag>::value
3590 && !std::is_same<_Iterator_kind, std::output_iterator_tag>::value,
3591 "iterator can not be input_iterator or output_iterator.");
3594 size_t _Populate(_Forward_iterator& _First, _Forward_iterator _Last)
3597 static_assert(std::is_lvalue_reference<decltype(*_First)>::value,
"lvalue required for forward iterator operator *");
3599 for (
size_t _Index=0; (_Index <
_Size) && (_First != _Last); _Index++)
3602 _M_element_array[_Length++] = &(*_First++);
3610 for (
size_t _Index=0; _Index < _Length; _Index++)
3612 _M_element_array[_Index] = &(*_First++);
3616 void _Store(
const value_type& _Elem,
size_t _Index)
const
3618 *(_M_element_array[_Index]) = _Elem;
3621 typename std::iterator_traits<_Forward_iterator>::reference
_Load(
size_t _Index)
const
3623 return *(_M_element_array[_Index]);
3627 typename std::iterator_traits<_Forward_iterator>::pointer _M_element_array[
_Size];
3630 template <
typename _Random_iterator>
3635 typedef typename std::iterator_traits<_Random_iterator>::value_type
value_type;
3641 size_t _Populate(_Random_iterator& _First, _Random_iterator _Last)
3643 typename std::iterator_traits<_Random_iterator>::difference_type _Range_size = _Last - _First;
3644 typename std::iterator_traits<_Random_iterator>::difference_type _Sized =
_Size;
3647 if (_Range_size > _Sized)
3654 _First += _Range_size;
3655 return static_cast<size_t>(_Range_size);
3665 void _Store(
const value_type& _Elem,
size_t _Index)
const
3667 _M_first[_Index] = _Elem;
3670 typename std::iterator_traits<_Random_iterator>::reference
_Load(
size_t _Index)
const
3673 return _M_first[_Index];
3680 template <
typename _Input_iterator1,
typename _Input_iterator2,
typename _Output_iterator,
typename _Binary_operator>
3685 _Output_iterator& _Result,
const _Binary_operator& _Binary_op) :
3686 _M_binary_op(_Binary_op), _M_len(0)
3688 _M_len = _M_input_helper1._Populate(_First1, _Last1);
3689 _M_input_helper2._Populate(_First2, _M_len);
3690 _M_output_helper._Populate(_Result, _M_len);
3697 [
this] (
size_t _Index)
3699 _M_output_helper._Store(_M_binary_op(_M_input_helper1._Load(_Index), _M_input_helper2._Load(_Index)), _Index);
3714 template <
typename _Input_iterator1,
typename _Input_iterator2,
typename _Output_iterator,
typename _Binary_operator>
3716 const _Binary_operator& _Binary_op,
task_group& _Tg)
3725 if (_First1 != _Last1)
3728 [=, &_Result, &_Binary_op, &_Tg]
3735 template <
typename _Input_iterator,
typename _Output_iterator,
typename _Unary_operator>
3740 _M_unary_op(_Unary_op), _M_len(0)
3742 _M_len = _M_input_helper._Populate(_First, _Last);
3743 _M_output_helper._Populate(_Result, _M_len);
3750 [
this] (
size_t _Index)
3752 _M_output_helper._Store(_M_unary_op(_M_input_helper._Load(_Index)), _Index);
3766 template <
typename _Input_iterator,
typename _Output_iterator,
typename _Unary_operator>
3768 const _Unary_operator& _Unary_op,
task_group& _Tg)
3777 if (_First != _Last)
3780 [=, &_Result, &_Unary_op, &_Tg]
3787 template <
typename _Input_iterator,
typename _Output_iterator,
typename _Unary_operator,
typename _Partitioner>
3788 _Output_iterator
_Parallel_transform_unary_impl(_Input_iterator _First, _Input_iterator _Last, _Output_iterator _Result,
const _Unary_operator& _Unary_op, _Partitioner&& _Part)
3790 typedef typename std::iterator_traits<_Input_iterator>::iterator_category _Input_iterator_type;
3791 typedef typename std::iterator_traits<_Output_iterator>::iterator_category _Output_iterator_type;
3793 if (_First != _Last)
3853 template <
typename _Input_iterator1,
typename _Output_iterator,
typename _Unary_operator>
3910 template <
typename _Input_iterator1,
typename _Output_iterator,
typename _Unary_operator>
3967 template <
typename _Input_iterator1,
typename _Output_iterator,
typename _Unary_operator>
4024 template <
typename _Input_iterator1,
typename _Output_iterator,
typename _Unary_operator>
4087 template <
typename _Input_iterator1,
typename _Input_iterator2,
typename _Output_iterator,
typename _Binary_operator,
typename _Partitioner>
4088 _Output_iterator
parallel_transform(_Input_iterator1 _First1, _Input_iterator1 _Last1, _Input_iterator2 _First2,
4089 _Output_iterator _Result,
const _Binary_operator& _Binary_op, _Partitioner&& _Part)
4091 typedef typename std::iterator_traits<_Input_iterator1>::iterator_category _Input_iterator_type1;
4092 typedef typename std::iterator_traits<_Input_iterator2>::iterator_category _Input_iterator_type2;
4093 typedef typename std::iterator_traits<_Output_iterator>::iterator_category _Output_iterator_type;
4095 if (_First1 != _Last1)
4152 template <
typename _Input_iterator1,
typename _Input_iterator2,
typename _Output_iterator,
typename _Binary_operator>
4153 _Output_iterator
parallel_transform(_Input_iterator1 _First1, _Input_iterator1 _Last1, _Input_iterator2 _First2,
4154 _Output_iterator _Result,
const _Binary_operator& _Binary_op)
4159 #pragma warning(pop)
4161 #pragma warning(push)
4163 #pragma warning(disable: 4316)
4179 template<
typename _Ty>
4186 #pragma warning(push)
4187 #pragma warning(disable: 4324)
4191 unsigned long _M_key;
4195 _Node(
unsigned long _Key, _Ty _InitialValue)
4196 : _M_key(_Key), _M_value(_InitialValue), _M_chain(
NULL)
4200 #pragma warning(pop)
4220 : _M_fnInitialize(_DefaultInit)
4243 template <
typename _Function>
4245 : _M_fnInitialize(_FnInitialize)
4265 : _M_size(_Copy._M_size), _M_fnInitialize(_Copy._M_fnInitialize)
4283 delete [] _M_buckets;
4298 delete [] _M_buckets;
4313 _Node* _ExistingNode = _FindLocalItem(_Key, &_Index);
4314 if (_ExistingNode ==
NULL)
4316 _ExistingNode = _AddLocalItem(_Key, _Index);
4320 return _ExistingNode->_M_value;
4340 _Node* _ExistingNode = _FindLocalItem(_Key, &_Index);
4341 if (_ExistingNode ==
NULL)
4344 _ExistingNode = _AddLocalItem(_Key, _Index);
4352 return _ExistingNode->_M_value;
4361 for (
size_t _Index = 0; _Index < _M_size; ++_Index)
4363 _Node* _CurrentNode = _M_buckets[_Index];
4364 while (_CurrentNode !=
NULL)
4366 _Node* _NextNode = _CurrentNode->_M_chain;
4367 delete _CurrentNode;
4368 _CurrentNode = _NextNode;
4371 memset((
void*)_M_buckets, 0, _M_size *
sizeof _M_buckets[0]);
4389 template<
typename _Function>
4392 _Node* _CurrentNode =
NULL;
4397 for (_Index = 0; _Index < _M_size; ++_Index)
4399 _CurrentNode = _M_buckets[_Index];
4400 if (_CurrentNode !=
NULL)
4407 if (_CurrentNode ==
NULL)
4409 return _M_fnInitialize();
4413 _Ty _Result = _CurrentNode->_M_value;
4414 for (_CurrentNode = _CurrentNode->_M_chain; _CurrentNode !=
NULL; _CurrentNode = _CurrentNode->_M_chain)
4416 _Result = _FnCombine(_Result, _CurrentNode->_M_value);
4421 for (++_Index; _Index < _M_size; ++_Index)
4423 for (_CurrentNode = _M_buckets[_Index]; _CurrentNode !=
NULL; _CurrentNode = _CurrentNode->_M_chain)
4425 _Result = _FnCombine(_Result, _CurrentNode->_M_value);
4445 template<
typename _Function>
4448 for (
size_t _Index = 0; _Index < _M_size; ++_Index)
4450 for (_Node* _CurrentNode = _M_buckets[_Index]; _CurrentNode !=
NULL; _CurrentNode = _CurrentNode->_M_chain)
4452 _FnCombine(_CurrentNode->_M_value);
4461 _M_buckets =
new _Node*[_M_size];
4462 memset((
void*)_M_buckets, 0, _M_size *
sizeof _M_buckets[0]);
4467 _M_buckets =
new _Node*[_M_size];
4468 for (
size_t _Index = 0; _Index < _M_size; ++_Index)
4470 _M_buckets[_Index] =
NULL;
4471 for (_Node* _CurrentNode = _Copy.
_M_buckets[_Index]; _CurrentNode !=
NULL; _CurrentNode = _CurrentNode->_M_chain)
4473 _Node* _NewNode =
new _Node(_CurrentNode->_M_key, _CurrentNode->_M_value);
4474 _NewNode->_M_chain = _M_buckets[_Index];
4475 _M_buckets[_Index] = _NewNode;
4484 *_PIndex = _Key % _M_size;
4487 _Node* _CurrentNode = _M_buckets[*_PIndex];
4488 while (_CurrentNode !=
NULL)
4490 if (_CurrentNode->_M_key == _Key)
4492 return _CurrentNode;
4495 _CurrentNode = _CurrentNode->_M_chain;
4503 _Node* _NewNode =
new _Node(_Key, _M_fnInitialize());
4507 _TopNode = _M_buckets[_Index];
4508 _NewNode->_M_chain = _TopNode;
4520 #pragma warning(pop) // C4316
4522 #pragma push_macro("_MAX_NUM_TASKS_PER_CORE")
4523 #pragma push_macro("_FINE_GRAIN_CHUNK_SIZE")
4524 #pragma push_macro("_SORT_MAX_RECURSION_DEPTH")
4541 #define _MAX_NUM_TASKS_PER_CORE 1024
4547 #define _FINE_GRAIN_CHUNK_SIZE 512
4550 #define _SORT_MAX_RECURSION_DEPTH 64
4552 template<
typename _Random_iterator,
typename _Function>
4553 inline size_t _Median_of_three(
const _Random_iterator &_Begin,
size_t _A,
size_t _B,
size_t _C,
const _Function &_Func,
bool &_Potentially_equal)
4555 _Potentially_equal =
false;
4556 if (_Func(_Begin[_A], _Begin[_B]))
4558 if (_Func(_Begin[_A], _Begin[_C]))
4560 return _Func(_Begin[_B], _Begin[_C]) ? _B : _C;
4569 if (_Func(_Begin[_B], _Begin[_C]))
4571 return _Func(_Begin[_A], _Begin[_C]) ? _A : _C;
4575 _Potentially_equal =
true;
4581 template<
typename _Random_iterator,
typename _Function>
4582 inline size_t _Median_of_nine(
const _Random_iterator &_Begin,
size_t _Size,
const _Function &_Func,
bool &_Potentially_equal)
4584 size_t _Offset = _Size / 8;
4585 size_t _A =
_Median_of_three(_Begin, 0, _Offset, _Offset * 2, _Func, _Potentially_equal),
4586 _B =
_Median_of_three(_Begin, _Offset * 3, _Offset * 4, _Offset * 5, _Func, _Potentially_equal),
4587 _C =
_Median_of_three(_Begin, _Offset * 6, _Offset * 7, _Size - 1, _Func, _Potentially_equal);
4590 if (_Potentially_equal)
4592 _Potentially_equal = !_Func(_Begin[_C], _Begin[_A]);
4599 template<
typename _Random_iterator,
typename _Function>
4600 inline size_t _Select_median_pivot(
const _Random_iterator &_Begin,
size_t _Size,
const _Function &_Func,
const size_t _Chunk_size,
bool &_Potentially_equal)
4603 if (_Chunk_size <
_FINE_GRAIN_CHUNK_SIZE && _Size <= std::max<size_t>(_Chunk_size * 4, static_cast<size_t>(15)))
4605 bool _Never_care_equal;
4606 return _Median_of_three(_Begin, 0, _Size / 2, _Size - 1, _Func, _Never_care_equal);
4616 template<
typename _Random_iterator,
typename _Random_buffer_iterator,
typename _Function>
4617 size_t _Search_mid_point(
const _Random_iterator &_Begin1,
size_t &_Len1,
const _Random_buffer_iterator &_Begin2,
size_t &_Len2,
const _Function &_Func)
4619 size_t _Len = (_Len1 + _Len2) / 2, _Index1 = 0, _Index2 = 0;
4621 while (_Index1 < _Len1 && _Index2 < _Len2)
4623 size_t _Mid1 = (_Index1 + _Len1) / 2, _Mid2 = (_Index2 + _Len2) / 2;
4624 if (_Func(_Begin1[_Mid1], _Begin2[_Mid2]))
4626 if (_Mid1 + _Mid2 < _Len)
4628 _Index1 = _Mid1 + 1;
4637 if (_Mid1 + _Mid2 < _Len)
4639 _Index2 = _Mid2 + 1;
4648 if (_Index1 == _Len1)
4650 _Len2 = _Len - _Len1;
4654 _Len1 = _Len - _Len2;
4661 template<
typename _Random_iterator,
typename _Random_buffer_iterator,
typename _Random_output_iterator,
typename _Function>
4662 void _Merge_chunks(_Random_iterator _Begin1,
const _Random_iterator &_End1, _Random_buffer_iterator _Begin2,
const _Random_buffer_iterator &_End2,
4663 _Random_output_iterator _Output,
const _Function &_Func)
4665 while (_Begin1 != _End1 && _Begin2 != _End2)
4667 if (_Func(*_Begin1, *_Begin2))
4677 if (_Begin1 != _End1)
4681 else if (_Begin2 != _End2)
4689 template<
typename _Random_iterator,
typename _Random_buffer_iterator,
typename _Random_output_iterator,
typename _Function>
4690 void _Parallel_merge(_Random_iterator _Begin1,
size_t _Len1, _Random_buffer_iterator _Begin2,
size_t _Len2, _Random_output_iterator _Output,
4691 const _Function &_Func,
size_t _Div_num)
4694 if (_Div_num <= 1 || (_Len1 <= 1 && _Len2 <= 1))
4696 _Merge_chunks(_Begin1, _Begin1 + _Len1, _Begin2, _Begin2 + _Len2, _Output, _Func);
4700 size_t _Mid_len1 = _Len1, _Mid_len2 = _Len2;
4706 _Parallel_merge(_Begin1, _Mid_len1, _Begin2, _Mid_len2, _Output, _Func, _Div_num / 2);
4710 _Parallel_merge(_Begin1 + _Mid_len1, _Len1 - _Mid_len1, _Begin2 + _Mid_len2, _Len2 - _Mid_len2, _Output + _Mid, _Func, _Div_num / 2);
4717 template<
typename _Ty,
typename _Function>
4720 return static_cast<size_t>(_Proj_func(_Val) >>
static_cast<int>(8 * _Radix) & 255);
4724 template<
typename _Random_iterator,
typename _Random_buffer_iterator,
typename _Function>
4725 void _Integer_radix_pass(
const _Random_iterator &_Begin,
size_t _Size,
const _Random_buffer_iterator &_Output,
size_t _Radix, _Function _Proj_func)
4732 size_t _Pos[256] = {0};
4734 for (
size_t _I = 0; _I <
_Size; _I++)
4736 ++_Pos[
_Radix_key(_Begin[_I], _Radix, _Proj_func)];
4739 for (
size_t _I = 1; _I < 256; _I++)
4741 _Pos[_I] += _Pos[_I - 1];
4745 for (
size_t _I = _Size - 1; _I != 0; _I--)
4754 template<
typename _Random_iterator,
typename _Random_buffer_iterator,
typename _Function>
4756 size_t _Radix, _Function _Proj_func,
size_t _Deep = 0)
4758 size_t _Cur_radix = 0;
4764 while (_Cur_radix < _Radix)
4770 if (_Cur_radix == _Radix)
4776 if (_Deep + _Radix + 1 & 1)
4791 template<
typename _Random_iterator,
typename _Random_buffer_iterator,
typename _Function>
4793 size_t _Radix, _Function _Proj_func,
const size_t _Chunk_size,
size_t _Deep = 0)
4796 if (_Size <= _Chunk_size || _Radix < 1)
4802 size_t _Buffer_size =
sizeof(
size_t) * 256 * _Threads_num;
4803 size_t _Step = _Size / _Threads_num;
4804 size_t _Remain = _Size % _Threads_num;
4809 memset(_Chunks, 0, _Buffer_size);
4856 size_t _Beg_index, _End_index;
4859 if (_Index < _Remain)
4861 _Beg_index = _Index * (_Step + 1);
4862 _End_index = _Beg_index + (_Step + 1);
4866 _Beg_index = _Remain * (_Step + 1) + (_Index - _Remain) * _Step;
4867 _End_index = _Beg_index + _Step;
4871 while (_Beg_index != _End_index)
4873 ++_Chunks[_Index][
_Radix_key(_Begin[_Beg_index++], _Radix, _Proj_func)];
4877 int _Index = -1,
_Count = 0;
4880 for (
int _I = 0; _I < 256; _I++)
4882 size_t _Last = _I ? _Chunks[_Threads_num - 1][_I - 1] : 0;
4883 _Chunks[0][_I] +=
_Last;
4885 for (
size_t _J = 1; _J < _Threads_num; _J++)
4887 _Chunks[_J][_I] += _Chunks[_J - 1][_I];
4892 if (_Chunks[_Threads_num - 1][_I] - _Last)
4905 size_t _Beg_index, _End_index;
4908 if (_Index < _Remain)
4910 _Beg_index = _Index * (_Step + 1);
4911 _End_index = _Beg_index + (_Step + 1);
4915 _Beg_index = _Remain * (_Step + 1) + (_Index - _Remain) * _Step;
4916 _End_index = _Beg_index + _Step;
4921 if (_Beg_index != _End_index--)
4923 while (_Beg_index != _End_index)
4925 _Output[--_Chunks[_Index][
_Radix_key(_Begin[_End_index], _Radix, _Proj_func)]] =
std::move(_Begin[_End_index]);
4928 _Output[--_Chunks[_Index][
_Radix_key(_Begin[_End_index], _Radix, _Proj_func)]] =
std::move(_Begin[_End_index]);
4935 if (_Index < 256 - 1)
4938 _Begin + _Chunks[0][_Index], _Radix - 1, _Proj_func, _Chunk_size, _Deep + 1);
4943 _Begin + _Chunks[0][_Index], _Radix - 1, _Proj_func, _Chunk_size, _Deep + 1);
4957 template<
typename _Random_iterator,
typename _Random_buffer_iterator,
typename _Function>
4959 _Function _Proj_func,
const size_t _Chunk_size)
4961 typedef typename std::iterator_traits<_Random_iterator>::value_type _Value_type;
4964 typedef typename std::remove_const<typename std::remove_reference<decltype(_Proj_func(*_Begin))>::type>::type _Integer_type;
4968 [=](_Random_iterator _Begin, _Random_iterator _End, _Integer_type _Init) -> _Integer_type
4970 while (_Begin != _End)
4972 _Integer_type _Ret = _Proj_func(*_Begin++);
4980 }, [](
const _Integer_type &_A,
const _Integer_type &_B) ->
const _Integer_type& {
return (_A < _B)? _B : _A;});
4984 while (_Max_val >>= 8)
4992 template<
typename _Random_iterator,
typename _Function>
4997 return std::sort(_Begin, _Begin + _Size, _Func);
5003 bool _Is_three_way_split =
false;
5004 size_t _Mid_index =
_Select_median_pivot(_Begin, _Size, _Func, _Chunk_size, _Is_three_way_split);
5011 size_t _I = 1, _J = _Size - 1;
5017 while (_Func(*_Begin, _Begin[_J]))
5022 while (_Func(_Begin[_I], *_Begin))
5032 if (_Func(_Begin[_K], *_Begin))
5041 while (_Func(*_Begin, _Begin[_K]))
5054 while (_Func(*_Begin, _Begin[_J]))
5060 while (_Func(_Begin[_I], *_Begin))
5081 volatile size_t _Next_div = _Div_num / 2;
5103 template<
typename _Random_iterator,
typename _Random_buffer_iterator,
typename _Function>
5105 int _Div_num,
const size_t _Chunk_size)
5107 static_assert(std::is_same<
typename std::iterator_traits<_Random_iterator>::value_type,
typename std::iterator_traits<_Random_buffer_iterator>::value_type>::value,
5108 "same value type expected");
5110 if (_Div_num <= 1 || _Size <= _Chunk_size)
5117 int _Left_div_turns = 0;
5118 while (_Div_num >>= 1)
5123 if (_Left_div_turns & 1)
5125 std::move(_Begin, _Begin + _Size, _Output);
5135 size_t _Mid = _Size / 2;
5138 auto _Handle =
make_task([&, _Chunk_size]
5148 if (_Is_buffer_swap)
5150 _Parallel_merge(_Output, _Mid, _Output + _Mid, _Size - _Mid, _Begin, _Func, _Div_num);
5154 _Parallel_merge(_Begin, _Mid, _Begin + _Mid, _Size - _Mid, _Output, _Func, _Div_num);
5157 return !_Is_buffer_swap;
5163 #pragma warning (push)
5164 #pragma warning (disable: 4127)
5167 template<
typename _Allocator>
5170 typename _Allocator::pointer _P = _Alloc.allocate(_N);
5174 if (!std::is_trivially_default_constructible<typename _Allocator::value_type>::value)
5176 for (
size_t _I = 0; _I < _N; _I++)
5179 typename _Allocator::value_type _T;
5180 _Alloc.construct(_P + _I, std::forward<typename _Allocator::value_type>(_T));
5188 template<
typename _Allocator>
5189 inline void _Destroy_buffer(
typename _Allocator::pointer _P,
size_t _N, _Allocator &_Alloc)
5193 if (!std::is_trivially_destructible<typename _Allocator::value_type>::value)
5195 for (
size_t _I = 0; _I < _N; _I++)
5197 _Alloc.destroy(_P + _I);
5201 _Alloc.deallocate(_P, _N);
5208 template<
typename _Allocator>
5235 #pragma warning (pop)
5270 template<
typename _Random_iterator,
typename _Function>
5271 inline void parallel_sort(
const _Random_iterator &_Begin,
const _Random_iterator &_End,
const _Function &_Func,
const size_t _Chunk_size = 2048)
5278 size_t _Size = _End - _Begin;
5281 if (_Size <= _Chunk_size || _Core_num < 2)
5311 template<
typename _Random_iterator>
5312 inline void parallel_sort(
const _Random_iterator &_Begin,
const _Random_iterator &_End)
5314 parallel_sort(_Begin, _End, std::less<
typename std::iterator_traits<_Random_iterator>::value_type>());
5360 template<
typename _Allocator,
typename _Random_iterator,
typename _Function>
5361 inline void parallel_buffered_sort(
const _Allocator& _Alloc,
const _Random_iterator &_Begin,
const _Random_iterator &_End,
const _Function &_Func,
const size_t _Chunk_size = 2048)
5368 size_t _Size = _End - _Begin;
5371 if (_Size <= _Chunk_size || _Core_num < 2)
5375 const static size_t _CORE_NUM_MASK = 0x55555555;
5416 _Func, _Core_num & _CORE_NUM_MASK | _Core_num << 1 & _CORE_NUM_MASK, _Chunk_size);
5461 template<
typename _Allocator,
typename _Random_iterator,
typename _Function>
5462 inline void parallel_buffered_sort(
const _Random_iterator &_Begin,
const _Random_iterator &_End,
const _Function &_Func,
const size_t _Chunk_size = 2048)
5465 return parallel_buffered_sort<_Allocator, _Random_iterator, _Function>(_Alloc, _Begin, _End, _Func, _Chunk_size);
5505 template<
typename _Random_iterator,
typename _Function>
5506 inline void parallel_buffered_sort(
const _Random_iterator &_Begin,
const _Random_iterator &_End,
const _Function &_Func,
const size_t _Chunk_size = 2048)
5508 parallel_buffered_sort<std::allocator<typename std::iterator_traits<_Random_iterator>::value_type>>(_Begin, _End, _Func, _Chunk_size);
5537 template<
typename _Random_iterator>
5540 parallel_buffered_sort<std::allocator<typename std::iterator_traits<_Random_iterator>::value_type>>(_Begin, _End,
5541 std::less<typename std::iterator_traits<_Random_iterator>::value_type>());
5573 template<
typename _Allocator,
typename _Random_iterator>
5576 parallel_buffered_sort<_Allocator>(_Begin, _End,
5577 std::less<typename std::iterator_traits<_Random_iterator>::value_type>());
5612 template<
typename _Allocator,
typename _Random_iterator>
5615 parallel_buffered_sort<_Allocator>(_Alloc, _Begin, _End, std::less<typename std::iterator_traits<_Random_iterator>::value_type>());
5618 #pragma warning(push)
5619 #pragma warning (disable: 4127)
5624 template <
typename _DataType>
5635 static_assert(std::is_integral<_DataType>::value,
5636 "Type should be integral to use default radix function. For more information on integral types, please refer to https://msdn.microsoft.com/en-us/library/bb983099.aspx.");
5637 static_assert((
sizeof(_DataType) <=
sizeof(
size_t)),
"Passed Type is bigger than size_t.");
5639 if (std::is_unsigned<_DataType>::value)
5648 return (((
SIZE_MAX/2) + 1) + static_cast<size_t>(_Val));
5652 #pragma warning (pop)
5679 template<
typename _Random_iterator>
5682 typedef typename std::iterator_traits<_Random_iterator>::value_type _DataType;
5686 parallel_radixsort<std::allocator<_DataType>>(_Begin, _End, _Proj_func, 256 * 256);
5720 template<
typename _Allocator,
typename _Random_iterator>
5721 inline void parallel_radixsort(
const _Allocator& _Alloc,
const _Random_iterator &_Begin,
const _Random_iterator &_End)
5723 typedef typename std::iterator_traits<_Random_iterator>::value_type _DataType;
5727 parallel_radixsort<_Allocator>(_Alloc, _Begin, _End, _Proj_func);
5758 template<
typename _Allocator,
typename _Random_iterator>
5762 return parallel_radixsort<_Allocator, _Random_iterator>(_Alloc, _Begin, _End);
5805 template<
typename _Allocator,
typename _Random_iterator,
typename _Function>
5806 inline void parallel_radixsort(
const _Allocator& _Alloc,
const _Random_iterator &_Begin,
const _Random_iterator &_End,
const _Function &_Proj_func,
const size_t _Chunk_size = 256 * 256)
5813 size_t _Size = _End - _Begin;
5866 template<
typename _Allocator,
typename _Random_iterator,
typename _Function>
5867 inline void parallel_radixsort(
const _Random_iterator &_Begin,
const _Random_iterator &_End,
const _Function &_Proj_func,
const size_t _Chunk_size = 256 * 256)
5870 return parallel_radixsort<_Allocator, _Random_iterator, _Function>(_Alloc, _Begin, _End, _Proj_func, _Chunk_size);
5907 template<
typename _Random_iterator,
typename _Function>
5908 inline void parallel_radixsort(
const _Random_iterator &_Begin,
const _Random_iterator &_End,
const _Function &_Proj_func,
const size_t _Chunk_size = 256 * 256)
5910 parallel_radixsort<std::allocator<typename std::iterator_traits<_Random_iterator>::value_type>>(
5911 _Begin, _End, _Proj_func, _Chunk_size);
5914 #pragma pop_macro("_SORT_MAX_RECURSION_DEPTH")
5915 #pragma pop_macro("_MAX_NUM_TASKS_PER_CORE")
5916 #pragma pop_macro("_FINE_GRAIN_CHUNK_SIZE")
5921 #pragma pop_macro("new")
void _Parallel_for_impl(_Index_type _First, _Index_type _Last, _Index_type _Step, const _Function &_Func, _Partitioner &&_Part)
Definition: ppl.h:2473
_Type _Get_num_chunks(_Type)
Definition: ppl.h:1750
volatile long _M_completion_count
Definition: ppl.h:2115
A cancellation beacon is a flag which can be polled in an inlinable fashion using the is_signaled met...
Definition: concrt.h:5299
void _Wait_on_intrusive_steal()
Definition: ppl.h:2075
void _Parallel_for_each_chunk(_Forward_iterator &_First, const _Forward_iterator &_Last, const _Function &_Func, task_group &_Task_group)
Definition: ppl.h:2808
_CONCRTIMP bool _IsCanceling()
Informs the caller whether or not the task collection is currently in the midst of cancellation...
void _Parallel_quicksort_impl(const _Random_iterator &_Begin, size_t _Size, const _Function &_Func, size_t _Div_num, const size_t _Chunk_size, int _Depth)
Definition: ppl.h:4993
_Iterator_helper()
Definition: ppl.h:3637
size_t _Select_median_pivot(const _Random_iterator &_Begin, size_t _Size, const _Function &_Func, const size_t _Chunk_size, bool &_Potentially_equal)
Definition: ppl.h:4600
std::function< _Ty()> _M_fnInitialize
Definition: ppl.h:4517
::Concurrency::details::_TaskCollection _M_task_collection
Definition: ppl.h:842
Definition: concrt.h:1100
#define NULL
Definition: vcruntime.h:236
static _CONCRTIMP void __cdecl _Yield()
_Ty & local()
Returns a reference to the thread-private sub-computation.
Definition: ppl.h:4309
void _Parallel_chunk_task_group_run(structured_task_group &_Task_group, task_handle< _Worker_class > *_Chunk_helpers, const Partitioner &, _Index_type _I)
Definition: ppl.h:2345
static void __cdecl _Invoke(const _Random_iterator &_First, _Index_type &_Index, const _Function &_Func)
Definition: ppl.h:1784
An event type that marks the beginning of a start/end event pair.
Definition: concrt.h:5465
void _Parallel_integer_sort_asc(const _Random_iterator &_Begin, size_t _Size, const _Random_buffer_iterator &_Output, _Function _Proj_func, const size_t _Chunk_size)
Definition: ppl.h:4958
const _Sub_function & _Sub_fun
Definition: ppl.h:3000
bool _Send_range(_Range< _Index_type > *_Worker_range)
Definition: ppl.h:2003
size_t _M_size
Definition: ppl.h:4516
_Parallel_fixed_chunk_helper< _Random_iterator, _Index_type, _Function, static_partitioner, _Is_iterator > _Base
Definition: ppl.h:2314
The combinable object is intended to provide thread-private copies of data, to perform lock-free t...
Definition: ppl.h:4180
Structured task collections represent groups of work which follow a strictly LIFO ordered paradigm qu...
Definition: concrt.h:4495
unchecked_array_iterator< _Iterator > make_unchecked_array_iterator(_Iterator _Ptr)
Definition: iterator:725
volatile _Index_type _M_current
Definition: ppl.h:1889
~combinable()
Destroys a combinable object.
Definition: ppl.h:4295
size_t _M_number
Definition: ppl.h:3050
void _Populate(_Forward_iterator &_First, size_t _Length)
Definition: ppl.h:3608
unsigned int _M_len
Definition: ppl.h:2798
_Bucket * _M_root
Definition: ppl.h:3051
unsigned int _Count
Definition: xcomplex:668
#define _TRACE_LEVEL_INFORMATION
Definition: ppl.h:38
void _NotifyCancel()
Definition: ppl.h:2089
_Worker_proxy * _M_pParent_worker
Definition: ppl.h:2109
Implements busy wait with no backoff
Definition: concrt.h:578
TaskProc m_pFunction
Definition: concrt.h:4191
void run_with_cancellation_token(const _Function &_Func, cancellation_token _Ct)
Executes a function object immediately and synchronously in the context of a given cancellation token...
Definition: ppl.h:865
#define _CONCRT_ASSERT(x)
Definition: concrt.h:123
location & _M_chunk_location
Definition: ppl.h:2337
_CONCRTIMP void __cdecl _Trace_ppl_function(const GUID &_Guid, unsigned char _Level, ConcRT_EventType _Type)
_Parallel_chunk_helper(_Index_type, const _Random_iterator &_First, _Index_type _First_iteration, _Index_type _Last_iteration, const _Index_type &_Step, const _Function &_Func, const _Partitioner &, _Worker_proxy< _Index_type > *const _Parent_data=NULL)
Definition: ppl.h:2137
combinable(const combinable &_Copy)
Constructs a new combinable object.
Definition: ppl.h:4264
_Index_type _Number_of_iterations() const
Definition: ppl.h:1852
task_group_status run_and_wait(const _Function &_Func)
Schedules a task to be run inline on the calling context with the assistance of the structured_task_g...
Definition: ppl.h:427
location * _M_pChunk_locations
Definition: ppl.h:1766
~_Worker_proxy()
Definition: ppl.h:1905
void _Integer_radix_pass(const _Random_iterator &_Begin, size_t _Size, const _Random_buffer_iterator &_Output, size_t _Radix, _Function _Proj_func)
Definition: ppl.h:4725
task_handle< _Function > make_task(const _Function &_Func)
A factory method for creating a task_handle object.
Definition: ppl.h:165
std::iterator_traits< _Forward_iterator >::value_type parallel_reduce(_Forward_iterator _Begin, _Forward_iterator _End, const typename std::iterator_traits< _Forward_iterator >::value_type &_Identity)
Computes the sum of all elements in a specified range by computing successive partial sums...
Definition: ppl.h:3287
static cancellation_token none()
Returns a cancellation token which can never be subject to cancellation.
Definition: pplcancellation_token.h:628
_Node * _FindLocalItem(unsigned long _Key, size_t *_PIndex)
Definition: ppl.h:4480
_CONCRTIMP const GUID PPLParallelForEventGuid
A category GUID describing ETW events fired by the Concurrency Runtime that are directly related to u...
_CONCRTIMP void _Cancel()
Cancels work on the task collection.
std::iterator_traits< _Random_iterator >::reference _Load(size_t _Index) const
Definition: ppl.h:3670
void(__cdecl * TaskProc)(void *)
Concurrency::details contains definitions of support routines in the public namespaces and one or mor...
Definition: concrt.h:251
_CONCRTIMP bool __cdecl is_current_task_group_canceling()
Returns an indication of whether the task group which is currently executing inline on the current co...
_Bucket * _Next
Definition: ppl.h:3027
void * align(size_t _Bound, size_t _Size, void *&_Ptr, size_t &_Space) _NOEXCEPT
Definition: memory:1985
void operator()() const
Definition: ppl.h:2325
_CONCRTIMP const GUID PPLParallelInvokeEventGuid
A category GUID describing ETW events fired by the Concurrency Runtime that are directly related to u...
_CONCRTIMP void _Schedule(_UnrealizedChore *_PChore, location *_PLocation)
Schedules a chore that can potentially run in parallel. The chore is pushed onto the associated works...
_Combinable_type & _Combinable
Definition: ppl.h:3003
void _Parallel_merge(_Random_iterator _Begin1, size_t _Len1, _Random_buffer_iterator _Begin2, size_t _Len2, _Random_output_iterator _Output, const _Function &_Func, size_t _Div_num)
Definition: ppl.h:4690
_In_ int _Val
Definition: vcruntime_string.h:62
void combine_each(_Function _FnCombine) const
Computes a final value from the set of thread-local sub-computations by calling the supplied combine ...
Definition: ppl.h:4446
_Parallel_chunk_helper(const _Random_iterator &_First, const _Index_type &_Step, const _Function &_Func, const _Range< _Index_type > &_Worker_range, _Worker_proxy< _Index_type > *const _Parent_data=NULL)
Definition: ppl.h:2146
void _IncrementConstructedElemsCount()
Definition: concrt.h:1072
location & _Get_chunk_location(unsigned int _ChunkIndex)
Definition: ppl.h:1744
_Functor::_Bucket_type *const _M_bucket
Definition: ppl.h:3332
_Bucket(_Bucket *_N)
Definition: ppl.h:3029
void operator()() const
Definition: ppl.h:2287
_CONCRTIMP void *__cdecl Alloc(size_t _NumBytes)
Allocates a block of memory of the size specified from the Concurrency Runtime Caching Suballocator...
__declspec(align(64)) struct _Node
Definition: ppl.h:4188
const _Function & _M_function
Definition: ppl.h:2266
_Output_iterator parallel_transform(_Input_iterator1 _First1, _Input_iterator1 _Last1, _Output_iterator _Result, const _Unary_operator&_Unary_op, const auto_partitioner &_Part=auto_partitioner())
Applies a specified function object to each element in a source range, or to a pair of elements from ...
Definition: ppl.h:3854
The Concurrency namespace provides classes and functions that provide access to the Concurrency Runti...
Definition: agents.h:43
void _Parallel_for_each_forward_impl(_Forward_iterator &_First, const _Forward_iterator &_Last, const _Function &_Func, task_group &_Task_group)
Definition: ppl.h:2824
void _Parallel_integer_radix_sort(const _Random_iterator &_Begin, size_t _Size, const _Random_buffer_iterator &_Output, size_t _Radix, _Function _Proj_func, const size_t _Chunk_size, size_t _Deep=0)
Definition: ppl.h:4792
std::iterator_traits< _Forward_iterator >::value_type _Value_type
Definition: ppl.h:2769
void _Integer_radix_sort(const _Random_iterator &_Begin, size_t _Size, const _Random_buffer_iterator &_Output, size_t _Radix, _Function _Proj_func, size_t _Deep=0)
Definition: ppl.h:4755
void _Disable_intrusive_steal()
Definition: ppl.h:2032
~task_handle()
Destroys the task_handle object.
Definition: ppl.h:110
_Random_iterator _M_first
Definition: ppl.h:3677
void interruption_point()
Creates an interruption point for cancellation. If a cancellation is in progress in the context where...
Definition: ppl.h:880
_CONCRTIMP void _Cancel()
Cancels work on the task collection.
__declspec(property(get=_Get_current_iteration, put=_Set_current_iteration)) _Index_type _M_current_iteration
_ElemType * _InitOnRawMalloca(void *_MallocaRet)
Definition: concrt.h:1062
void clear()
Clears any intermediate computational results from a previous usage.
Definition: ppl.h:4359
void _Construct(_Ty1 *_Ptr, _Ty2 &&_Val)
Definition: xmemory0:138
void parallel_invoke(const _Function1 &_Func1, const _Function2 &_Func2)
Executes the function objects supplied as parameters in parallel, and blocks until they have finished...
Definition: ppl.h:945
task_handle const & operator=(task_handle const &)
_Allocator _M_alloc
Definition: ppl.h:5230
_Parallel_reduce_fixed_worker(_Forward_iterator _Begin, _Forward_iterator _End, const _Functor &_Fun)
Definition: ppl.h:3319
std::auto_ptr< task_handle< _Worker_class > > _Workers
Definition: ppl.h:3410
task_group()
Constructs a new task_group object.
Definition: ppl.h:504
_CONCRTIMP const GUID PPLParallelForeachEventGuid
A category GUID describing ETW events fired by the Concurrency Runtime that are directly related to u...
_OutIt _Move_no_deprecate(_InIt _First, _InIt _Last, _OutIt _Dest)
Definition: xutility:2623
void operator()() const
Definition: ppl.h:2159
_CONCRTIMP void _CheckTaskCollection()
void _Set_last_iteration(const _Index_type _I)
Definition: ppl.h:1878
_TaskCollectionStatus _Wait()
Waits for all chores running in the _StructuredTaskCollection to finish (normally or abnormally)...
Definition: concrt.h:4604
static _CONCRTIMP _Context __cdecl _CurrentContext()
The static_partitioner class represents a static partitioning of the range iterated over by parallel_...
Definition: ppl.h:1641
The simple_partitioner class represents a static partitioning of the range iterated over by parallel_...
Definition: ppl.h:1670
structured_task_group()
Constructs a new structured_task_group object.
Definition: ppl.h:219
size_t _M_size
Definition: ppl.h:5229
void _Set_tree_done()
Definition: ppl.h:2056
void _Set_current_iteration(const _Index_type _I)
Definition: ppl.h:1864
_TaskCollectionStatus _Wait()
Waits for all chores running in the _TaskCollection to finish (normally or abnormally). This method encapsulates all the running tasks in an exception handling block, and will re-throw any exceptions that occur in any of it tasks (if those exceptions occur on another thread, they are marshaled from that thread to the thread where the _TaskCollection was created, and re-thrown). After this function returns, the _TaskCollection cannot be used for scheduling further work.
Definition: concrt.h:4809
size_t _Search_mid_point(const _Random_iterator &_Begin1, size_t &_Len1, const _Random_buffer_iterator &_Begin2, size_t &_Len2, const _Function &_Func)
Definition: ppl.h:4617
::Concurrency::details::_Cancellation_beacon _M_beacon
Definition: ppl.h:2112
bool _Parallel_buffered_sort_impl(const _Random_iterator &_Begin, size_t _Size, _Random_buffer_iterator _Output, const _Function &_Func, int _Div_num, const size_t _Chunk_size)
Definition: ppl.h:5104
volatile _Index_type _M_last
Definition: ppl.h:1890
_Bucket * _Unsafe_push_back()
Definition: ppl.h:3101
_Parallel_for_each_helper(_Forward_iterator &_First, const _Forward_iterator &_Last, const _Function &_Func)
Definition: ppl.h:2772
bool _SpinOnce()
Spins for one time quantum,until a maximum spin is reached.
Definition: concrt.h:626
~task_group()
Destroys a task_group object. You are expected to call the either the wait or run_and_wait method on ...
Definition: ppl.h:536
void _Parallel_for_partitioned_impl(_Index_type _First, _Diff_type _Range_arg, _Diff_type _Step, const _Function &_Func, const auto_partitioner &_Part)
Definition: ppl.h:2441
const _Index_type _M_first_iteration
Definition: ppl.h:2304
_Worker_proxy(_Worker_proxy *_PParent_worker=NULL)
Definition: ppl.h:1899
_Ty _Serial_combine_release()
Definition: ppl.h:3079
void _InitCopy(const combinable &_Copy)
Definition: ppl.h:4465
_Range(_Index_type _Current_iteration, _Index_type _Last_iteration)
Definition: ppl.h:1810
void run(const _Function &_Func)
Schedules a task on the task_group object. If a task_handle object is passed as a parameter to run...
Definition: ppl.h:573
~structured_task_group()
Destroys a structured_task_group object. You are expected to call either the wait or run_and_wait met...
Definition: ppl.h:252
void run(task_handle< _Function > &_Task_handle)
Schedules a task on the structured_task_group object. The caller manages the lifetime of the task_han...
Definition: ppl.h:285
void _Parallel_chunk_impl(const _Random_iterator &_First, _Index_type _Range_arg, const _Index_type &_Step, const _Function &_Func, _Partitioner &&_Part)
Definition: ppl.h:2366
task_group_status run_and_wait(task_handle< _Function > &_Task_handle)
Schedules a task to be run inline on the calling context with the assistance of the structured_task_g...
Definition: ppl.h:388
void _Put(const _Ty &_Cur)
Definition: ppl.h:3042
bool _Is_done()
Definition: ppl.h:2043
_Ty & local(bool &_Exists)
Returns a reference to the thread-private sub-computation.
Definition: ppl.h:4336
void run(task_handle< _Function > &_Task_handle, location &_Placement)
Schedules a task on the task_group object. If a task_handle object is passed as a parameter to run...
Definition: ppl.h:696
std::iterator_traits< _Forward_iterator >::value_type value_type
Definition: ppl.h:3585
int _Worker_size
Definition: ppl.h:3411
unsigned int size_t
Definition: sourceannotations.h:19
_Reduce_type parallel_reduce(_Forward_iterator _Begin, _Forward_iterator _End, const _Reduce_type &_Identity, const _Range_reduce_fun &_Range_fun, const _Sym_reduce_fun &_Sym_fun)
Computes the sum of all elements in a specified range by computing successive partial sums...
Definition: ppl.h:3166
void _Parallel_reduce_random_executor(_Random_iterator _Begin, _Random_iterator _End, const _Function &_Fun)
Definition: ppl.h:3368
_CONCRTIMP void __cdecl Free(_Pre_maybenull_ _Post_invalid_ void *_PAllocation)
Releases a block of memory previously allocated by the Alloc method to the Concurrency Runtime Cachin...
void _Parallel_for_each_partitioned_impl(const _Random_iterator &_First, _Index_type _Range_arg, _Index_type _Step, const _Function &_Func, const auto_partitioner &_Part)
Definition: ppl.h:2856
const _Random_iterator & _M_first
Definition: ppl.h:2300
void parallel_buffered_sort(const _Allocator &_Alloc, const _Random_iterator &_Begin, const _Random_iterator &_End, const _Function &_Func, const size_t _Chunk_size=2048)
Arranges the elements in a specified range into a nondescending order, or according to an ordering cr...
Definition: ppl.h:5361
~auto_partitioner()
Destroys a auto_partitioner object.
Definition: ppl.h:1627
const _Index_type & _M_step
Definition: ppl.h:2301
_Bucket * _Construct(_Bucket *_Par=0)
Definition: ppl.h:3055
size_t _GetAllocationSize() const
Definition: concrt.h:1104
The auto_partitioner class represents the default method parallel_for, parallel_for_each and parallel...
Definition: ppl.h:1614
_CONCRTIMP _TaskCollectionStatus __stdcall _RunAndWait(_UnrealizedChore *_PChore=NULL)
A cancellation friendly wrapper with which to execute _PChore and then waits for all chores running i...
void parallel_sort(const _Random_iterator &_Begin, const _Random_iterator &_End, const _Function &_Func, const size_t _Chunk_size=2048)
Arranges the elements in a specified range into a nondescending order, or according to an ordering cr...
Definition: ppl.h:5271
affinity_partitioner()
Constructs an affinity_partitioner object.
Definition: ppl.h:1731
void parallel_for_each(const extent< _Rank > &_Compute_domain, const _Kernel_type &_Kernel)
Invokes a parallel computation of a kernel function over a compute domain on an accelerator_view. The accelerator_view is determined from the arrays and/or array_views captured by the kernel function, or if no accelerator_view can be derived, the default is chosen.
Definition: amp.h:7020
void parallel_for(_Index_type _First, _Index_type _Last, _Index_type _Step, const _Function &_Func, _Partitioner &&_Part)
parallel_for iterates over a range of indices and executes a user-supplied function at each iteration...
Definition: ppl.h:2555
~_AllocatedBufferHolder()
Definition: ppl.h:5218
void _Enable_intrusive_steal(_Range< _Index_type > *_Worker_range)
Definition: ppl.h:2026
void swap(array< _Ty, _Size > &_Left, array< _Ty, _Size > &_Right) _NOEXCEPT_OP(_NOEXCEPT_OP(_Left.swap(_Right)))
Definition: array:433
auto_partitioner()
Constructs a auto_partitioner object.
Definition: ppl.h:1621
#define _FINE_GRAIN_CHUNK_SIZE
Definition: ppl.h:4547
void _Store(const value_type &_Elem, size_t _Index) const
Definition: ppl.h:3665
#define _SORT_MAX_RECURSION_DEPTH
Definition: ppl.h:4550
An event type that marks the beginning of a start/end event pair.
Definition: concrt.h:5460
void _Propagate_cancel()
Definition: ppl.h:2094
void _Parallel_for_each_impl(_Forward_iterator _First, const _Forward_iterator &_Last, const _Function &_Func, const auto_partitioner &, std::forward_iterator_tag)
Definition: ppl.h:2841
_Node *volatile * _M_buckets
Definition: ppl.h:4515
structured_task_group(cancellation_token _CancellationToken)
Constructs a new structured_task_group object.
Definition: ppl.h:236
task_group_status run_and_wait(const _Function &_Func)
Schedules a task to be run inline on the calling context with the assistance of the task_group object...
Definition: ppl.h:796
_CONCRTIMP bool _IsCanceling()
Informs the caller whether or not the task collection is currently in the midst of a cancellation...
_Base _M_fixed_helper
Definition: ppl.h:2338
bool _GetRuntimeOwnsLifetime() const
Definition: concrt.h:4232
_Parallel_reduce_forward_executor_helper(const _Parallel_reduce_forward_executor_helper &_Other)
Definition: ppl.h:3433
_Allocator::pointer _M_buffer
Definition: ppl.h:5231
size_t _Median_of_nine(const _Random_iterator &_Begin, size_t _Size, const _Function &_Func, bool &_Potentially_equal)
Definition: ppl.h:4582
static _Ty _DefaultInit()
Definition: ppl.h:4202
void parallel_radixsort(const _Random_iterator &_Begin, const _Random_iterator &_End)
Arranges elements in a specified range into an non descending order using a radix sorting algorithm...
Definition: ppl.h:5680
_CONCRTIMP void _Schedule(_UnrealizedChore *_PChore, location *_PLocation)
Schedules a chore that can potentially run in parallel. The chore is pushed onto the associated works...
#define false
Definition: stdbool.h:16
_Allocator::pointer _Construct_buffer(size_t _N, _Allocator &_Alloc)
Definition: ppl.h:5168
Definition: concrt.h:4197
::Concurrency::details::_TaskCollectionBase * _OwningCollection() const
Definition: concrt.h:4218
const _Index_type _M_last_iteration
Definition: ppl.h:2269
unsigned long long _Size_type
Definition: ppl.h:1673
The structured_task_group class represents a highly structured collection of parallel work...
Definition: ppl.h:205
combinable & operator=(const combinable &_Copy)
Assigns to a combinable object from another combinable object.
Definition: ppl.h:4280
void * _InterlockedCompareExchangePointer(void *volatile *, void *, void *)
const _Functor & _M_fun
Definition: ppl.h:3330
combinable(_Function _FnInitialize)
Constructs a new combinable object.
Definition: ppl.h:4244
const _Reduce_type & _Identity_value
Definition: ppl.h:3001
task_group_status wait()
Waits until all work on the structured_task_group has completed or is canceled.
Definition: ppl.h:349
void _SetRuntimeOwnsLifetime(bool _FValue)
Definition: concrt.h:4225
_Range< _Index_type > *volatile _M_pWorker_range
Definition: ppl.h:2118
void _Parallel_invoke_impl(const _Function1 &_Func1, const _Function2 &_Func2)
Definition: ppl.h:908
_Parallel_localized_chunk_helper(_Index_type _Chunk_index, const _Random_iterator &_First, _Index_type _First_iteration, _Index_type _Last_iteration, const _Index_type &_Step, const _Function &_Func, affinity_partitioner &_Part)
Definition: ppl.h:2316
Task collections represent groups of work which step outside the strict structuring of the _Structure...
Definition: concrt.h:4702
_Function _M_function
Definition: ppl.h:137
~simple_partitioner()
Destroys a simple_partitioner object.
Definition: ppl.h:1695
_Size_type _M_chunk_size
Definition: ppl.h:1713
size_t _Radix_key(const _Ty &_Val, size_t _Radix, _Function _Proj_func)
Definition: ppl.h:4718
The task_group class represents a collection of parallel work which can be waited on or canceled...
Definition: ppl.h:490
_CONCRTIMP _TaskCollectionStatus __stdcall _RunAndWait(_UnrealizedChore *_PChore=NULL)
A cancellation friendly wrapper with which to execute _PChore and then waits for all chores running i...
An abstraction of a physical location on hardware.
Definition: concrt.h:1825
const _Forward_iterator _M_end
Definition: ppl.h:3331
void run(const _Function &_Func, location &_Placement)
Schedules a task on the task_group object. If a task_handle object is passed as a parameter to run...
Definition: ppl.h:614
void _Insert(_Bucket *_Item)
Definition: ppl.h:3034
static _CONCRTIMP location __cdecl current()
Returns a location object representing the most specific place the calling thread is executing...
task_group(cancellation_token _CancellationToken)
Constructs a new task_group object.
Definition: ppl.h:520
bool is_canceling()
Informs the caller whether or not the task group is currently in the midst of a cancellation. This does not necessarily indicate that the cancel method was called on the structured_task_group object (although such certainly qualifies this method to return true). It may be the case that the structured_task_group object is executing inline and a task group further up in the work tree was canceled. In cases such as these where the runtime can determine ahead of time that cancellation will flow through this structured_task_group object, true will be returned as well.
Definition: ppl.h:463
size_t _Populate(_Random_iterator &_First, _Random_iterator _Last)
Definition: ppl.h:3641
unsigned int _M_num_chunks
Definition: ppl.h:1763
void operator()() const
The function call operator that the runtime invokes to perform the work of the task handle...
Definition: ppl.h:126
void _Store(const value_type &_Elem, size_t _Index) const
Definition: ppl.h:3616
void _Send_range(_Range< _Index_type > *_Helper_range)
Definition: ppl.h:1818
_Type _Get_num_chunks(_Type) const
Definition: ppl.h:1630
std::iterator_traits< _Forward_iterator >::reference _Load(size_t _Index) const
Definition: ppl.h:3621
#define _MAX_NUM_TASKS_PER_CORE
Definition: ppl.h:4541
void cancel()
Makes a best effort attempt to cancel the sub-tree of work rooted at this task group. Every task scheduled on the task group will get canceled transitively if possible.
Definition: ppl.h:812
_ElemType * _AddRawMallocaNode(void *_MallocaRet)
Definition: concrt.h:1124
void _Set_done()
Definition: ppl.h:2048
bool _Receive_range(_Range< _Index_type > *_Helper_range)
Definition: ppl.h:1919
bool _Verify_beacon_cancellation()
Definition: ppl.h:2067
~_Parallel_reduce_forward_executor_helper()
Definition: ppl.h:3448
void _Steal_range(_Range< _Index_type > *_Helper_range)
Definition: ppl.h:1838
task_group_status
Describes the execution status of a task_group or structured_task_group object. A value of this type ...
Definition: pplinterface.h:102
void _Destroy_buffer(typename _Allocator::pointer _P, size_t _N, _Allocator &_Alloc)
Definition: ppl.h:5189
_Reduce_type _Reduce_type
Definition: ppl.h:3005
size_t _Median_of_three(const _Random_iterator &_Begin, size_t _A, size_t _B, size_t _C, const _Function &_Func, bool &_Potentially_equal)
Definition: ppl.h:4553
_Allocator::pointer _Get_buffer()
Definition: ppl.h:5223
_Parallel_reduce_forward_executor_helper(_Forward_iterator &_First, _Forward_iterator _Last, const _Function &_Func)
Definition: ppl.h:3413
void run(task_handle< _Function > &_Task_handle)
Schedules a task on the task_group object. If a task_handle object is passed as a parameter to run...
Definition: ppl.h:653
void operator()() const
Definition: ppl.h:2783
task_group_status run_and_wait(task_handle< _Function > &_Task_handle)
Schedules a task to be run inline on the calling context with the assistance of the task_group object...
Definition: ppl.h:757
simple_partitioner(_Size_type _Chunk_size)
Constructs a simple_partitioner object.
Definition: ppl.h:1683
_Order_combinable(const _Sym_fun &_Fun)
Definition: ppl.h:3061
_Type _Get_num_chunks(_Type) const
Definition: ppl.h:1659
bool _Is_helper_registered()
Definition: ppl.h:2038
long __cdecl _InterlockedDecrement(long volatile *)
const _Sym_fun & _M_fun
Definition: ppl.h:3049
static_partitioner()
Constructs a static_partitioner object.
Definition: ppl.h:1648
#define _CONCRTIMP
Definition: crtdefs.h:48
_CONCRTIMP size_t __cdecl _GetCombinableSize()
constexpr remove_reference< _Ty >::type && move(_Ty &&_Arg) _NOEXCEPT
Definition: type_traits:1290
const _Index_type _M_last_iteration
Definition: ppl.h:2305
_Worker_proxy< _Index_type > *const _M_parent_worker
Definition: ppl.h:2271
static _CONCRTIMP unsigned int __cdecl _GetNumberOfVirtualProcessors()
void _Merge_chunks(_Random_iterator _Begin1, const _Random_iterator &_End1, _Random_buffer_iterator _Begin2, const _Random_buffer_iterator &_End2, _Random_output_iterator _Output, const _Function &_Func)
Definition: ppl.h:4662
::Concurrency::details::_Context _M_context
Definition: ppl.h:2113
std::iterator_traits< _Random_iterator >::value_type value_type
Definition: ppl.h:3635
void _Populate(_Random_iterator &_First, size_t _Length)
Definition: ppl.h:3659
The affinity_partitioner class is similar to the static_partitioner class, but it improves cache affi...
Definition: ppl.h:1723
void _Parallel_for_impl(_Index_type _First, _Index_type _Last, _Index_type _Step, const _Function &_Func)
Definition: ppl.h:2509
char _Value[(sizeof(_Ty)/sizeof(char))]
Definition: ppl.h:3026
_AllocatedBufferHolder(size_t _Size, const _Allocator &_Alloc)
Definition: ppl.h:5212
const _Index_type _M_first_iteration
Definition: ppl.h:2268
_Ty combine(_Function _FnCombine) const
Computes a final value from the set of thread-local sub-computations by calling the supplied combine ...
Definition: ppl.h:4390
void cancel()
Makes a best effort attempt to cancel the sub-tree of work rooted at this task group. Every task scheduled on the task group will get canceled transitively if possible.
Definition: ppl.h:444
~static_partitioner()
Destroys a static_partitioner object.
Definition: ppl.h:1656
static void __cdecl _Invoke(const _Random_iterator &_First, _Index_type &_Index, const _Function &_Func)
Definition: ppl.h:1796
_Type _Get_num_chunks(_Type _Range_arg) const
Definition: ppl.h:1698
Definition: concrt.h:1044
void _InitNew()
Definition: ppl.h:4458
long __cdecl _InterlockedIncrement(long volatile *)
_Parallel_fixed_chunk_helper(_Index_type, const _Random_iterator &_First, _Index_type _First_iteration, _Index_type _Last_iteration, const _Index_type &_Step, const _Function &_Func, const _Partitioner &)
Definition: ppl.h:2280
void _Parallel_transform_binary_impl2(_Input_iterator1 _First1, _Input_iterator1 _Last1, _Input_iterator2 _First2, _Output_iterator &_Result, const _Binary_operator&_Binary_op, task_group &_Tg)
Definition: ppl.h:3715
bool _Is_beacon_signaled()
Definition: ppl.h:2062
size_t _Populate(_Forward_iterator &_First, _Forward_iterator _Last)
Definition: ppl.h:3594
_Iterator_helper()
Definition: ppl.h:3587
_Combinable_type::_Bucket _Bucket_type
Definition: ppl.h:3006
_Parallel_reduce_fixed_worker< _Forward_iterator, _Function > _Worker_class
Definition: ppl.h:3409
const _Function & _M_function
Definition: ppl.h:2302
#define SIZE_MAX
Definition: limits.h:76
size_t operator()(const _DataType &_Val) const
Definition: ppl.h:5627
The task_handle class represents an individual parallel work item. It encapsulates the instructions a...
Definition: ppl.h:85
_Index_type _Get_current_iteration() const
Definition: ppl.h:1858
_Reduce_functor_helper(const _Reduce_type &_Identity, const _Sub_function &_Sub_fun, _Combinable_type &&_Comb)
Definition: ppl.h:3008
Definition: xtr1common:326
_In_ int _Value
Definition: setjmp.h:173
const _Function & _M_function
Definition: ppl.h:2796
~affinity_partitioner()
Destroys an affinity_partitioner object.
Definition: ppl.h:1739
_FwdIt _Last
Definition: algorithm:1936
void run(task_handle< _Function > &_Task_handle, location &_Placement)
Schedules a task on the structured_task_group object. The caller manages the lifetime of the task_han...
Definition: ppl.h:323
combinable()
Constructs a new combinable object.
Definition: ppl.h:4219
_Function::_Reduce_type _Parallel_reduce_impl(_Forward_iterator _First, const _Forward_iterator &_Last, const _Function &_Func, std::forward_iterator_tag)
Definition: ppl.h:3295
_Range< _Index_type > *volatile _M_pHelper_range
Definition: ppl.h:2106
_Index_type _Get_last_iteration() const
Definition: ppl.h:1872
_Size
Definition: vcruntime_string.h:36
const _Random_iterator & _M_first
Definition: ppl.h:2264
const _Index_type & _M_step
Definition: ppl.h:2265
void sort(_RanIt _First, _RanIt _Last, _Pr _Pred)
Definition: algorithm:2781
::Concurrency::details::_StructuredTaskCollection _M_task_collection
Definition: ppl.h:474
~_Order_combinable()
Definition: ppl.h:3067
void _Parallel_transform_unary_impl2(_Input_iterator _First, _Input_iterator _Last, _Output_iterator &_Result, const _Unary_operator&_Unary_op, task_group &_Tg)
Definition: ppl.h:3767
void parallel_for(_Index_type _First, _Index_type _Last, const _Function &_Func, affinity_partitioner &_Part)
parallel_for iterates over a range of indices and executes a user-supplied function at each iteration...
Definition: ppl.h:2747
_Node * _AddLocalItem(unsigned long _Key, size_t _Index)
Definition: ppl.h:4501
void _Parallel_reduce_forward_executor(_Forward_iterator _First, _Forward_iterator _Last, const _Function &_Func, task_group &_Task_group)
Definition: ppl.h:3462
volatile long _M_stop_iterating
Definition: ppl.h:2119
bool is_canceling()
Informs the caller whether or not the task group is currently in the midst of a cancellation. This does not necessarily indicate that the cancel method was called on the task_group object (although such certainly qualifies this method to return true). It may be the case that the task_group object is executing inline and a task group further up in the work tree was canceled. In cases such as these where the runtime can determine ahead of time that cancellation will flow through this task_group object, true will be returned as well.
Definition: ppl.h:831
_Output_iterator _Parallel_transform_unary_impl(_Input_iterator _First, _Input_iterator _Last, _Output_iterator _Result, const _Unary_operator&_Unary_op, _Partitioner &&_Part)
Definition: ppl.h:3788
The cancellation_token class represents the ability to determine whether some operation has been requ...
Definition: pplcancellation_token.h:616
static _ChoreType * _InternalAlloc(const _Function &_Func)
Definition: concrt.h:4239
task_group_status wait()
Waits until all work on the task_group object has either completed or been canceled.
Definition: ppl.h:719
task_handle(const _Function &_Func)
Constructs a new task_handle object. The work of the task is performed by invoking the function speci...
Definition: ppl.h:101