You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

2201 lines
78KB

  1. // -*- C++ -*-
  2. // Copyright (C) 2007-2020 Free Software Foundation, Inc.
  3. //
  4. // This file is part of the GNU ISO C++ Library. This library is free
  5. // software; you can redistribute it and/or modify it under the terms
  6. // of the GNU General Public License as published by the Free Software
  7. // Foundation; either version 3, or (at your option) any later
  8. // version.
  9. // This library is distributed in the hope that it will be useful, but
  10. // WITHOUT ANY WARRANTY; without even the implied warranty of
  11. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  12. // General Public License for more details.
  13. // Under Section 7 of GPL version 3, you are granted additional
  14. // permissions described in the GCC Runtime Library Exception, version
  15. // 3.1, as published by the Free Software Foundation.
  16. // You should have received a copy of the GNU General Public License and
  17. // a copy of the GCC Runtime Library Exception along with this program;
  18. // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
  19. // <http://www.gnu.org/licenses/>.
  20. /** @file parallel/algo.h
  21. * @brief Parallel STL function calls corresponding to the stl_algo.h header.
  22. *
  23. * The functions defined here mainly do case switches and
  24. * call the actual parallelized versions in other files.
  25. * Inlining policy: Functions that basically only contain one function call,
  26. * are declared inline.
  27. * This file is a GNU parallel extension to the Standard C++ Library.
  28. */
  29. // Written by Johannes Singler and Felix Putze.
  30. #ifndef _GLIBCXX_PARALLEL_ALGO_H
  31. #define _GLIBCXX_PARALLEL_ALGO_H 1
  32. #include <parallel/algorithmfwd.h>
  33. #include <bits/stl_algobase.h>
  34. #include <bits/stl_algo.h>
  35. #include <parallel/iterator.h>
  36. #include <parallel/base.h>
  37. #include <parallel/sort.h>
  38. #include <parallel/workstealing.h>
  39. #include <parallel/par_loop.h>
  40. #include <parallel/omp_loop.h>
  41. #include <parallel/omp_loop_static.h>
  42. #include <parallel/for_each_selectors.h>
  43. #include <parallel/for_each.h>
  44. #include <parallel/find.h>
  45. #include <parallel/find_selectors.h>
  46. #include <parallel/search.h>
  47. #include <parallel/random_shuffle.h>
  48. #include <parallel/partition.h>
  49. #include <parallel/merge.h>
  50. #include <parallel/unique_copy.h>
  51. #include <parallel/set_operations.h>
  52. namespace std _GLIBCXX_VISIBILITY(default)
  53. {
  54. namespace __parallel
  55. {
  56. // Sequential fallback
  57. template<typename _IIter, typename _Function>
  58. inline _Function
  59. for_each(_IIter __begin, _IIter __end, _Function __f,
  60. __gnu_parallel::sequential_tag)
  61. { return _GLIBCXX_STD_A::for_each(__begin, __end, __f); }
  62. // Sequential fallback for input iterator case
  63. template<typename _IIter, typename _Function, typename _IteratorTag>
  64. inline _Function
  65. __for_each_switch(_IIter __begin, _IIter __end, _Function __f,
  66. _IteratorTag)
  67. { return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag()); }
  68. // Parallel algorithm for random access iterators
  69. template<typename _RAIter, typename _Function>
  70. _Function
  71. __for_each_switch(_RAIter __begin, _RAIter __end,
  72. _Function __f, random_access_iterator_tag,
  73. __gnu_parallel::_Parallelism __parallelism_tag)
  74. {
  75. if (_GLIBCXX_PARALLEL_CONDITION(
  76. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  77. >= __gnu_parallel::_Settings::get().for_each_minimal_n
  78. && __gnu_parallel::__is_parallel(__parallelism_tag)))
  79. {
  80. bool __dummy;
  81. __gnu_parallel::__for_each_selector<_RAIter> __functionality;
  82. return __gnu_parallel::
  83. __for_each_template_random_access(
  84. __begin, __end, __f, __functionality,
  85. __gnu_parallel::_DummyReduct(), true, __dummy, -1,
  86. __parallelism_tag);
  87. }
  88. else
  89. return for_each(__begin, __end, __f, __gnu_parallel::sequential_tag());
  90. }
  91. // Public interface
  92. template<typename _Iterator, typename _Function>
  93. inline _Function
  94. for_each(_Iterator __begin, _Iterator __end, _Function __f,
  95. __gnu_parallel::_Parallelism __parallelism_tag)
  96. {
  97. return __for_each_switch(__begin, __end, __f,
  98. std::__iterator_category(__begin),
  99. __parallelism_tag);
  100. }
  101. template<typename _Iterator, typename _Function>
  102. inline _Function
  103. for_each(_Iterator __begin, _Iterator __end, _Function __f)
  104. {
  105. return __for_each_switch(__begin, __end, __f,
  106. std::__iterator_category(__begin));
  107. }
  108. // Sequential fallback
  109. template<typename _IIter, typename _Tp>
  110. inline _IIter
  111. find(_IIter __begin, _IIter __end, const _Tp& __val,
  112. __gnu_parallel::sequential_tag)
  113. { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
  114. // Sequential fallback for input iterator case
  115. template<typename _IIter, typename _Tp, typename _IteratorTag>
  116. inline _IIter
  117. __find_switch(_IIter __begin, _IIter __end, const _Tp& __val,
  118. _IteratorTag)
  119. { return _GLIBCXX_STD_A::find(__begin, __end, __val); }
  120. // Parallel find for random access iterators
  121. template<typename _RAIter, typename _Tp>
  122. _RAIter
  123. __find_switch(_RAIter __begin, _RAIter __end,
  124. const _Tp& __val, random_access_iterator_tag)
  125. {
  126. typedef iterator_traits<_RAIter> _TraitsType;
  127. typedef typename _TraitsType::value_type _ValueType;
  128. if (_GLIBCXX_PARALLEL_CONDITION(true))
  129. {
  130. __gnu_parallel::__binder2nd<__gnu_parallel::_EqualTo<_ValueType,
  131. const _Tp&>,
  132. _ValueType, const _Tp&, bool>
  133. __comp(__gnu_parallel::_EqualTo<_ValueType, const _Tp&>(), __val);
  134. return __gnu_parallel::__find_template(
  135. __begin, __end, __begin, __comp,
  136. __gnu_parallel::__find_if_selector()).first;
  137. }
  138. else
  139. return _GLIBCXX_STD_A::find(__begin, __end, __val);
  140. }
  141. // Public interface
  142. template<typename _IIter, typename _Tp>
  143. inline _IIter
  144. find(_IIter __begin, _IIter __end, const _Tp& __val)
  145. {
  146. return __find_switch(__begin, __end, __val,
  147. std::__iterator_category(__begin));
  148. }
  149. // Sequential fallback
  150. template<typename _IIter, typename _Predicate>
  151. inline _IIter
  152. find_if(_IIter __begin, _IIter __end, _Predicate __pred,
  153. __gnu_parallel::sequential_tag)
  154. { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
  155. // Sequential fallback for input iterator case
  156. template<typename _IIter, typename _Predicate, typename _IteratorTag>
  157. inline _IIter
  158. __find_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
  159. _IteratorTag)
  160. { return _GLIBCXX_STD_A::find_if(__begin, __end, __pred); }
  161. // Parallel find_if for random access iterators
  162. template<typename _RAIter, typename _Predicate>
  163. _RAIter
  164. __find_if_switch(_RAIter __begin, _RAIter __end,
  165. _Predicate __pred, random_access_iterator_tag)
  166. {
  167. if (_GLIBCXX_PARALLEL_CONDITION(true))
  168. return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
  169. __gnu_parallel::
  170. __find_if_selector()).first;
  171. else
  172. return _GLIBCXX_STD_A::find_if(__begin, __end, __pred);
  173. }
  174. // Public interface
  175. template<typename _IIter, typename _Predicate>
  176. inline _IIter
  177. find_if(_IIter __begin, _IIter __end, _Predicate __pred)
  178. {
  179. return __find_if_switch(__begin, __end, __pred,
  180. std::__iterator_category(__begin));
  181. }
  182. // Sequential fallback
  183. template<typename _IIter, typename _FIterator>
  184. inline _IIter
  185. find_first_of(_IIter __begin1, _IIter __end1,
  186. _FIterator __begin2, _FIterator __end2,
  187. __gnu_parallel::sequential_tag)
  188. {
  189. return _GLIBCXX_STD_A::find_first_of(__begin1, __end1, __begin2, __end2);
  190. }
  191. // Sequential fallback
  192. template<typename _IIter, typename _FIterator,
  193. typename _BinaryPredicate>
  194. inline _IIter
  195. find_first_of(_IIter __begin1, _IIter __end1,
  196. _FIterator __begin2, _FIterator __end2,
  197. _BinaryPredicate __comp, __gnu_parallel::sequential_tag)
  198. { return _GLIBCXX_STD_A::find_first_of(
  199. __begin1, __end1, __begin2, __end2, __comp); }
  200. // Sequential fallback for input iterator type
  201. template<typename _IIter, typename _FIterator,
  202. typename _IteratorTag1, typename _IteratorTag2>
  203. inline _IIter
  204. __find_first_of_switch(_IIter __begin1, _IIter __end1,
  205. _FIterator __begin2, _FIterator __end2,
  206. _IteratorTag1, _IteratorTag2)
  207. { return find_first_of(__begin1, __end1, __begin2, __end2,
  208. __gnu_parallel::sequential_tag()); }
  209. // Parallel algorithm for random access iterators
  210. template<typename _RAIter, typename _FIterator,
  211. typename _BinaryPredicate, typename _IteratorTag>
  212. inline _RAIter
  213. __find_first_of_switch(_RAIter __begin1,
  214. _RAIter __end1,
  215. _FIterator __begin2, _FIterator __end2,
  216. _BinaryPredicate __comp, random_access_iterator_tag,
  217. _IteratorTag)
  218. {
  219. return __gnu_parallel::
  220. __find_template(__begin1, __end1, __begin1, __comp,
  221. __gnu_parallel::__find_first_of_selector
  222. <_FIterator>(__begin2, __end2)).first;
  223. }
  224. // Sequential fallback for input iterator type
  225. template<typename _IIter, typename _FIterator,
  226. typename _BinaryPredicate, typename _IteratorTag1,
  227. typename _IteratorTag2>
  228. inline _IIter
  229. __find_first_of_switch(_IIter __begin1, _IIter __end1,
  230. _FIterator __begin2, _FIterator __end2,
  231. _BinaryPredicate __comp, _IteratorTag1, _IteratorTag2)
  232. { return find_first_of(__begin1, __end1, __begin2, __end2, __comp,
  233. __gnu_parallel::sequential_tag()); }
  234. // Public interface
  235. template<typename _IIter, typename _FIterator,
  236. typename _BinaryPredicate>
  237. inline _IIter
  238. find_first_of(_IIter __begin1, _IIter __end1,
  239. _FIterator __begin2, _FIterator __end2,
  240. _BinaryPredicate __comp)
  241. {
  242. return __find_first_of_switch(__begin1, __end1, __begin2, __end2, __comp,
  243. std::__iterator_category(__begin1),
  244. std::__iterator_category(__begin2));
  245. }
  246. // Public interface, insert default comparator
  247. template<typename _IIter, typename _FIterator>
  248. inline _IIter
  249. find_first_of(_IIter __begin1, _IIter __end1,
  250. _FIterator __begin2, _FIterator __end2)
  251. {
  252. typedef typename std::iterator_traits<_IIter>::value_type _IValueType;
  253. typedef typename std::iterator_traits<_FIterator>::value_type _FValueType;
  254. return __gnu_parallel::find_first_of(__begin1, __end1, __begin2, __end2,
  255. __gnu_parallel::_EqualTo<_IValueType, _FValueType>());
  256. }
  257. // Sequential fallback
  258. template<typename _IIter, typename _OutputIterator>
  259. inline _OutputIterator
  260. unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
  261. __gnu_parallel::sequential_tag)
  262. { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out); }
  263. // Sequential fallback
  264. template<typename _IIter, typename _OutputIterator,
  265. typename _Predicate>
  266. inline _OutputIterator
  267. unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
  268. _Predicate __pred, __gnu_parallel::sequential_tag)
  269. { return _GLIBCXX_STD_A::unique_copy(__begin1, __end1, __out, __pred); }
  270. // Sequential fallback for input iterator case
  271. template<typename _IIter, typename _OutputIterator,
  272. typename _Predicate, typename _IteratorTag1, typename _IteratorTag2>
  273. inline _OutputIterator
  274. __unique_copy_switch(_IIter __begin, _IIter __last,
  275. _OutputIterator __out, _Predicate __pred,
  276. _IteratorTag1, _IteratorTag2)
  277. { return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred); }
  278. // Parallel unique_copy for random access iterators
  279. template<typename _RAIter, typename _RandomAccessOutputIterator,
  280. typename _Predicate>
  281. _RandomAccessOutputIterator
  282. __unique_copy_switch(_RAIter __begin, _RAIter __last,
  283. _RandomAccessOutputIterator __out, _Predicate __pred,
  284. random_access_iterator_tag, random_access_iterator_tag)
  285. {
  286. if (_GLIBCXX_PARALLEL_CONDITION(
  287. static_cast<__gnu_parallel::_SequenceIndex>(__last - __begin)
  288. > __gnu_parallel::_Settings::get().unique_copy_minimal_n))
  289. return __gnu_parallel::__parallel_unique_copy(
  290. __begin, __last, __out, __pred);
  291. else
  292. return _GLIBCXX_STD_A::unique_copy(__begin, __last, __out, __pred);
  293. }
  294. // Public interface
  295. template<typename _IIter, typename _OutputIterator>
  296. inline _OutputIterator
  297. unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out)
  298. {
  299. typedef typename std::iterator_traits<_IIter>::value_type _ValueType;
  300. return __unique_copy_switch(
  301. __begin1, __end1, __out, equal_to<_ValueType>(),
  302. std::__iterator_category(__begin1),
  303. std::__iterator_category(__out));
  304. }
  305. // Public interface
  306. template<typename _IIter, typename _OutputIterator, typename _Predicate>
  307. inline _OutputIterator
  308. unique_copy(_IIter __begin1, _IIter __end1, _OutputIterator __out,
  309. _Predicate __pred)
  310. {
  311. return __unique_copy_switch(
  312. __begin1, __end1, __out, __pred,
  313. std::__iterator_category(__begin1),
  314. std::__iterator_category(__out));
  315. }
  316. // Sequential fallback
  317. template<typename _IIter1, typename _IIter2,
  318. typename _OutputIterator>
  319. inline _OutputIterator
  320. set_union(_IIter1 __begin1, _IIter1 __end1,
  321. _IIter2 __begin2, _IIter2 __end2,
  322. _OutputIterator __out, __gnu_parallel::sequential_tag)
  323. { return _GLIBCXX_STD_A::set_union(
  324. __begin1, __end1, __begin2, __end2, __out); }
  325. // Sequential fallback
  326. template<typename _IIter1, typename _IIter2,
  327. typename _OutputIterator, typename _Predicate>
  328. inline _OutputIterator
  329. set_union(_IIter1 __begin1, _IIter1 __end1,
  330. _IIter2 __begin2, _IIter2 __end2,
  331. _OutputIterator __out, _Predicate __pred,
  332. __gnu_parallel::sequential_tag)
  333. { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
  334. __begin2, __end2, __out, __pred); }
  335. // Sequential fallback for input iterator case
  336. template<typename _IIter1, typename _IIter2, typename _Predicate,
  337. typename _OutputIterator, typename _IteratorTag1,
  338. typename _IteratorTag2, typename _IteratorTag3>
  339. inline _OutputIterator
  340. __set_union_switch(
  341. _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
  342. _OutputIterator __result, _Predicate __pred,
  343. _IteratorTag1, _IteratorTag2, _IteratorTag3)
  344. { return _GLIBCXX_STD_A::set_union(__begin1, __end1,
  345. __begin2, __end2, __result, __pred); }
  346. // Parallel set_union for random access iterators
  347. template<typename _RAIter1, typename _RAIter2,
  348. typename _Output_RAIter, typename _Predicate>
  349. _Output_RAIter
  350. __set_union_switch(_RAIter1 __begin1, _RAIter1 __end1,
  351. _RAIter2 __begin2, _RAIter2 __end2,
  352. _Output_RAIter __result, _Predicate __pred,
  353. random_access_iterator_tag, random_access_iterator_tag,
  354. random_access_iterator_tag)
  355. {
  356. if (_GLIBCXX_PARALLEL_CONDITION(
  357. static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  358. >= __gnu_parallel::_Settings::get().set_union_minimal_n
  359. || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
  360. >= __gnu_parallel::_Settings::get().set_union_minimal_n))
  361. return __gnu_parallel::__parallel_set_union(
  362. __begin1, __end1, __begin2, __end2, __result, __pred);
  363. else
  364. return _GLIBCXX_STD_A::set_union(__begin1, __end1,
  365. __begin2, __end2, __result, __pred);
  366. }
  367. // Public interface
  368. template<typename _IIter1, typename _IIter2,
  369. typename _OutputIterator>
  370. inline _OutputIterator
  371. set_union(_IIter1 __begin1, _IIter1 __end1,
  372. _IIter2 __begin2, _IIter2 __end2, _OutputIterator __out)
  373. {
  374. typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
  375. typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
  376. return __set_union_switch(
  377. __begin1, __end1, __begin2, __end2, __out,
  378. __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
  379. std::__iterator_category(__begin1),
  380. std::__iterator_category(__begin2),
  381. std::__iterator_category(__out));
  382. }
  383. // Public interface
  384. template<typename _IIter1, typename _IIter2,
  385. typename _OutputIterator, typename _Predicate>
  386. inline _OutputIterator
  387. set_union(_IIter1 __begin1, _IIter1 __end1,
  388. _IIter2 __begin2, _IIter2 __end2,
  389. _OutputIterator __out, _Predicate __pred)
  390. {
  391. return __set_union_switch(
  392. __begin1, __end1, __begin2, __end2, __out, __pred,
  393. std::__iterator_category(__begin1),
  394. std::__iterator_category(__begin2),
  395. std::__iterator_category(__out));
  396. }
  397. // Sequential fallback.
  398. template<typename _IIter1, typename _IIter2,
  399. typename _OutputIterator>
  400. inline _OutputIterator
  401. set_intersection(_IIter1 __begin1, _IIter1 __end1,
  402. _IIter2 __begin2, _IIter2 __end2,
  403. _OutputIterator __out, __gnu_parallel::sequential_tag)
  404. { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1,
  405. __begin2, __end2, __out); }
  406. // Sequential fallback.
  407. template<typename _IIter1, typename _IIter2,
  408. typename _OutputIterator, typename _Predicate>
  409. inline _OutputIterator
  410. set_intersection(_IIter1 __begin1, _IIter1 __end1,
  411. _IIter2 __begin2, _IIter2 __end2,
  412. _OutputIterator __out, _Predicate __pred,
  413. __gnu_parallel::sequential_tag)
  414. { return _GLIBCXX_STD_A::set_intersection(
  415. __begin1, __end1, __begin2, __end2, __out, __pred); }
  416. // Sequential fallback for input iterator case
  417. template<typename _IIter1, typename _IIter2,
  418. typename _Predicate, typename _OutputIterator,
  419. typename _IteratorTag1, typename _IteratorTag2,
  420. typename _IteratorTag3>
  421. inline _OutputIterator
  422. __set_intersection_switch(_IIter1 __begin1, _IIter1 __end1,
  423. _IIter2 __begin2, _IIter2 __end2,
  424. _OutputIterator __result, _Predicate __pred,
  425. _IteratorTag1, _IteratorTag2, _IteratorTag3)
  426. { return _GLIBCXX_STD_A::set_intersection(__begin1, __end1, __begin2,
  427. __end2, __result, __pred); }
  428. // Parallel set_intersection for random access iterators
  429. template<typename _RAIter1, typename _RAIter2,
  430. typename _Output_RAIter, typename _Predicate>
  431. _Output_RAIter
  432. __set_intersection_switch(_RAIter1 __begin1,
  433. _RAIter1 __end1,
  434. _RAIter2 __begin2,
  435. _RAIter2 __end2,
  436. _Output_RAIter __result,
  437. _Predicate __pred,
  438. random_access_iterator_tag,
  439. random_access_iterator_tag,
  440. random_access_iterator_tag)
  441. {
  442. if (_GLIBCXX_PARALLEL_CONDITION(
  443. static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  444. >= __gnu_parallel::_Settings::get().set_union_minimal_n
  445. || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
  446. >= __gnu_parallel::_Settings::get().set_union_minimal_n))
  447. return __gnu_parallel::__parallel_set_intersection(
  448. __begin1, __end1, __begin2, __end2, __result, __pred);
  449. else
  450. return _GLIBCXX_STD_A::set_intersection(
  451. __begin1, __end1, __begin2, __end2, __result, __pred);
  452. }
  453. // Public interface
  454. template<typename _IIter1, typename _IIter2,
  455. typename _OutputIterator>
  456. inline _OutputIterator
  457. set_intersection(_IIter1 __begin1, _IIter1 __end1,
  458. _IIter2 __begin2, _IIter2 __end2,
  459. _OutputIterator __out)
  460. {
  461. typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
  462. typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
  463. return __set_intersection_switch(
  464. __begin1, __end1, __begin2, __end2, __out,
  465. __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
  466. std::__iterator_category(__begin1),
  467. std::__iterator_category(__begin2),
  468. std::__iterator_category(__out));
  469. }
  470. template<typename _IIter1, typename _IIter2,
  471. typename _OutputIterator, typename _Predicate>
  472. inline _OutputIterator
  473. set_intersection(_IIter1 __begin1, _IIter1 __end1,
  474. _IIter2 __begin2, _IIter2 __end2,
  475. _OutputIterator __out, _Predicate __pred)
  476. {
  477. return __set_intersection_switch(
  478. __begin1, __end1, __begin2, __end2, __out, __pred,
  479. std::__iterator_category(__begin1),
  480. std::__iterator_category(__begin2),
  481. std::__iterator_category(__out));
  482. }
  483. // Sequential fallback
  484. template<typename _IIter1, typename _IIter2,
  485. typename _OutputIterator>
  486. inline _OutputIterator
  487. set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
  488. _IIter2 __begin2, _IIter2 __end2,
  489. _OutputIterator __out,
  490. __gnu_parallel::sequential_tag)
  491. { return _GLIBCXX_STD_A::set_symmetric_difference(
  492. __begin1, __end1, __begin2, __end2, __out); }
  493. // Sequential fallback
  494. template<typename _IIter1, typename _IIter2,
  495. typename _OutputIterator, typename _Predicate>
  496. inline _OutputIterator
  497. set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
  498. _IIter2 __begin2, _IIter2 __end2,
  499. _OutputIterator __out, _Predicate __pred,
  500. __gnu_parallel::sequential_tag)
  501. { return _GLIBCXX_STD_A::set_symmetric_difference(
  502. __begin1, __end1, __begin2, __end2, __out, __pred); }
  503. // Sequential fallback for input iterator case
  504. template<typename _IIter1, typename _IIter2,
  505. typename _Predicate, typename _OutputIterator,
  506. typename _IteratorTag1, typename _IteratorTag2,
  507. typename _IteratorTag3>
  508. inline _OutputIterator
  509. __set_symmetric_difference_switch(
  510. _IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2, _IIter2 __end2,
  511. _OutputIterator __result, _Predicate __pred,
  512. _IteratorTag1, _IteratorTag2, _IteratorTag3)
  513. { return _GLIBCXX_STD_A::set_symmetric_difference(
  514. __begin1, __end1, __begin2, __end2, __result, __pred); }
  515. // Parallel set_symmetric_difference for random access iterators
  516. template<typename _RAIter1, typename _RAIter2,
  517. typename _Output_RAIter, typename _Predicate>
  518. _Output_RAIter
  519. __set_symmetric_difference_switch(_RAIter1 __begin1,
  520. _RAIter1 __end1,
  521. _RAIter2 __begin2,
  522. _RAIter2 __end2,
  523. _Output_RAIter __result,
  524. _Predicate __pred,
  525. random_access_iterator_tag,
  526. random_access_iterator_tag,
  527. random_access_iterator_tag)
  528. {
  529. if (_GLIBCXX_PARALLEL_CONDITION(
  530. static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  531. >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n
  532. || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
  533. >= __gnu_parallel::_Settings::get().set_symmetric_difference_minimal_n))
  534. return __gnu_parallel::__parallel_set_symmetric_difference(
  535. __begin1, __end1, __begin2, __end2, __result, __pred);
  536. else
  537. return _GLIBCXX_STD_A::set_symmetric_difference(
  538. __begin1, __end1, __begin2, __end2, __result, __pred);
  539. }
  540. // Public interface.
  541. template<typename _IIter1, typename _IIter2,
  542. typename _OutputIterator>
  543. inline _OutputIterator
  544. set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
  545. _IIter2 __begin2, _IIter2 __end2,
  546. _OutputIterator __out)
  547. {
  548. typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
  549. typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
  550. return __set_symmetric_difference_switch(
  551. __begin1, __end1, __begin2, __end2, __out,
  552. __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
  553. std::__iterator_category(__begin1),
  554. std::__iterator_category(__begin2),
  555. std::__iterator_category(__out));
  556. }
  557. // Public interface.
  558. template<typename _IIter1, typename _IIter2,
  559. typename _OutputIterator, typename _Predicate>
  560. inline _OutputIterator
  561. set_symmetric_difference(_IIter1 __begin1, _IIter1 __end1,
  562. _IIter2 __begin2, _IIter2 __end2,
  563. _OutputIterator __out, _Predicate __pred)
  564. {
  565. return __set_symmetric_difference_switch(
  566. __begin1, __end1, __begin2, __end2, __out, __pred,
  567. std::__iterator_category(__begin1),
  568. std::__iterator_category(__begin2),
  569. std::__iterator_category(__out));
  570. }
  571. // Sequential fallback.
  572. template<typename _IIter1, typename _IIter2,
  573. typename _OutputIterator>
  574. inline _OutputIterator
  575. set_difference(_IIter1 __begin1, _IIter1 __end1,
  576. _IIter2 __begin2, _IIter2 __end2,
  577. _OutputIterator __out, __gnu_parallel::sequential_tag)
  578. { return _GLIBCXX_STD_A::set_difference(
  579. __begin1,__end1, __begin2, __end2, __out); }
  580. // Sequential fallback.
  581. template<typename _IIter1, typename _IIter2,
  582. typename _OutputIterator, typename _Predicate>
  583. inline _OutputIterator
  584. set_difference(_IIter1 __begin1, _IIter1 __end1,
  585. _IIter2 __begin2, _IIter2 __end2,
  586. _OutputIterator __out, _Predicate __pred,
  587. __gnu_parallel::sequential_tag)
  588. { return _GLIBCXX_STD_A::set_difference(__begin1, __end1,
  589. __begin2, __end2, __out, __pred); }
  590. // Sequential fallback for input iterator case.
  591. template<typename _IIter1, typename _IIter2, typename _Predicate,
  592. typename _OutputIterator, typename _IteratorTag1,
  593. typename _IteratorTag2, typename _IteratorTag3>
  594. inline _OutputIterator
  595. __set_difference_switch(_IIter1 __begin1, _IIter1 __end1,
  596. _IIter2 __begin2, _IIter2 __end2,
  597. _OutputIterator __result, _Predicate __pred,
  598. _IteratorTag1, _IteratorTag2, _IteratorTag3)
  599. { return _GLIBCXX_STD_A::set_difference(
  600. __begin1, __end1, __begin2, __end2, __result, __pred); }
  601. // Parallel set_difference for random access iterators
  602. template<typename _RAIter1, typename _RAIter2,
  603. typename _Output_RAIter, typename _Predicate>
  604. _Output_RAIter
  605. __set_difference_switch(_RAIter1 __begin1,
  606. _RAIter1 __end1,
  607. _RAIter2 __begin2,
  608. _RAIter2 __end2,
  609. _Output_RAIter __result, _Predicate __pred,
  610. random_access_iterator_tag,
  611. random_access_iterator_tag,
  612. random_access_iterator_tag)
  613. {
  614. if (_GLIBCXX_PARALLEL_CONDITION(
  615. static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  616. >= __gnu_parallel::_Settings::get().set_difference_minimal_n
  617. || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
  618. >= __gnu_parallel::_Settings::get().set_difference_minimal_n))
  619. return __gnu_parallel::__parallel_set_difference(
  620. __begin1, __end1, __begin2, __end2, __result, __pred);
  621. else
  622. return _GLIBCXX_STD_A::set_difference(
  623. __begin1, __end1, __begin2, __end2, __result, __pred);
  624. }
  625. // Public interface
  626. template<typename _IIter1, typename _IIter2,
  627. typename _OutputIterator>
  628. inline _OutputIterator
  629. set_difference(_IIter1 __begin1, _IIter1 __end1,
  630. _IIter2 __begin2, _IIter2 __end2,
  631. _OutputIterator __out)
  632. {
  633. typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
  634. typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
  635. return __set_difference_switch(
  636. __begin1, __end1, __begin2, __end2, __out,
  637. __gnu_parallel::_Less<_ValueType1, _ValueType2>(),
  638. std::__iterator_category(__begin1),
  639. std::__iterator_category(__begin2),
  640. std::__iterator_category(__out));
  641. }
  642. // Public interface
  643. template<typename _IIter1, typename _IIter2,
  644. typename _OutputIterator, typename _Predicate>
  645. inline _OutputIterator
  646. set_difference(_IIter1 __begin1, _IIter1 __end1,
  647. _IIter2 __begin2, _IIter2 __end2,
  648. _OutputIterator __out, _Predicate __pred)
  649. {
  650. return __set_difference_switch(
  651. __begin1, __end1, __begin2, __end2, __out, __pred,
  652. std::__iterator_category(__begin1),
  653. std::__iterator_category(__begin2),
  654. std::__iterator_category(__out));
  655. }
  656. // Sequential fallback
  657. template<typename _FIterator>
  658. inline _FIterator
  659. adjacent_find(_FIterator __begin, _FIterator __end,
  660. __gnu_parallel::sequential_tag)
  661. { return _GLIBCXX_STD_A::adjacent_find(__begin, __end); }
  662. // Sequential fallback
  663. template<typename _FIterator, typename _BinaryPredicate>
  664. inline _FIterator
  665. adjacent_find(_FIterator __begin, _FIterator __end,
  666. _BinaryPredicate __binary_pred,
  667. __gnu_parallel::sequential_tag)
  668. { return _GLIBCXX_STD_A::adjacent_find(__begin, __end, __binary_pred); }
  669. // Parallel algorithm for random access iterators
  670. template<typename _RAIter>
  671. _RAIter
  672. __adjacent_find_switch(_RAIter __begin, _RAIter __end,
  673. random_access_iterator_tag)
  674. {
  675. typedef iterator_traits<_RAIter> _TraitsType;
  676. typedef typename _TraitsType::value_type _ValueType;
  677. if (_GLIBCXX_PARALLEL_CONDITION(true))
  678. {
  679. _RAIter __spot = __gnu_parallel::
  680. __find_template(
  681. __begin, __end - 1, __begin, equal_to<_ValueType>(),
  682. __gnu_parallel::__adjacent_find_selector())
  683. .first;
  684. if (__spot == (__end - 1))
  685. return __end;
  686. else
  687. return __spot;
  688. }
  689. else
  690. return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag());
  691. }
  692. // Sequential fallback for input iterator case
  693. template<typename _FIterator, typename _IteratorTag>
  694. inline _FIterator
  695. __adjacent_find_switch(_FIterator __begin, _FIterator __end,
  696. _IteratorTag)
  697. { return adjacent_find(__begin, __end, __gnu_parallel::sequential_tag()); }
  698. // Public interface
  699. template<typename _FIterator>
  700. inline _FIterator
  701. adjacent_find(_FIterator __begin, _FIterator __end)
  702. {
  703. return __adjacent_find_switch(__begin, __end,
  704. std::__iterator_category(__begin));
  705. }
  706. // Sequential fallback for input iterator case
  707. template<typename _FIterator, typename _BinaryPredicate,
  708. typename _IteratorTag>
  709. inline _FIterator
  710. __adjacent_find_switch(_FIterator __begin, _FIterator __end,
  711. _BinaryPredicate __pred, _IteratorTag)
  712. { return adjacent_find(__begin, __end, __pred,
  713. __gnu_parallel::sequential_tag()); }
  714. // Parallel algorithm for random access iterators
  715. template<typename _RAIter, typename _BinaryPredicate>
  716. _RAIter
  717. __adjacent_find_switch(_RAIter __begin, _RAIter __end,
  718. _BinaryPredicate __pred, random_access_iterator_tag)
  719. {
  720. if (_GLIBCXX_PARALLEL_CONDITION(true))
  721. return __gnu_parallel::__find_template(__begin, __end, __begin, __pred,
  722. __gnu_parallel::
  723. __adjacent_find_selector()).first;
  724. else
  725. return adjacent_find(__begin, __end, __pred,
  726. __gnu_parallel::sequential_tag());
  727. }
  728. // Public interface
  729. template<typename _FIterator, typename _BinaryPredicate>
  730. inline _FIterator
  731. adjacent_find(_FIterator __begin, _FIterator __end,
  732. _BinaryPredicate __pred)
  733. {
  734. return __adjacent_find_switch(__begin, __end, __pred,
  735. std::__iterator_category(__begin));
  736. }
  737. // Sequential fallback
  738. template<typename _IIter, typename _Tp>
  739. inline typename iterator_traits<_IIter>::difference_type
  740. count(_IIter __begin, _IIter __end, const _Tp& __value,
  741. __gnu_parallel::sequential_tag)
  742. { return _GLIBCXX_STD_A::count(__begin, __end, __value); }
  743. // Parallel code for random access iterators
  744. template<typename _RAIter, typename _Tp>
  745. typename iterator_traits<_RAIter>::difference_type
  746. __count_switch(_RAIter __begin, _RAIter __end,
  747. const _Tp& __value, random_access_iterator_tag,
  748. __gnu_parallel::_Parallelism __parallelism_tag)
  749. {
  750. typedef iterator_traits<_RAIter> _TraitsType;
  751. typedef typename _TraitsType::value_type _ValueType;
  752. typedef typename _TraitsType::difference_type _DifferenceType;
  753. typedef __gnu_parallel::_SequenceIndex _SequenceIndex;
  754. if (_GLIBCXX_PARALLEL_CONDITION(
  755. static_cast<_SequenceIndex>(__end - __begin)
  756. >= __gnu_parallel::_Settings::get().count_minimal_n
  757. && __gnu_parallel::__is_parallel(__parallelism_tag)))
  758. {
  759. __gnu_parallel::__count_selector<_RAIter, _DifferenceType>
  760. __functionality;
  761. _DifferenceType __res = 0;
  762. __gnu_parallel::
  763. __for_each_template_random_access(
  764. __begin, __end, __value, __functionality,
  765. std::plus<_SequenceIndex>(), __res, __res, -1,
  766. __parallelism_tag);
  767. return __res;
  768. }
  769. else
  770. return count(__begin, __end, __value,
  771. __gnu_parallel::sequential_tag());
  772. }
  773. // Sequential fallback for input iterator case.
  774. template<typename _IIter, typename _Tp, typename _IteratorTag>
  775. inline typename iterator_traits<_IIter>::difference_type
  776. __count_switch(_IIter __begin, _IIter __end, const _Tp& __value,
  777. _IteratorTag)
  778. { return count(__begin, __end, __value, __gnu_parallel::sequential_tag());
  779. }
  780. // Public interface.
  781. template<typename _IIter, typename _Tp>
  782. inline typename iterator_traits<_IIter>::difference_type
  783. count(_IIter __begin, _IIter __end, const _Tp& __value,
  784. __gnu_parallel::_Parallelism __parallelism_tag)
  785. {
  786. return __count_switch(__begin, __end, __value,
  787. std::__iterator_category(__begin),
  788. __parallelism_tag);
  789. }
  790. template<typename _IIter, typename _Tp>
  791. inline typename iterator_traits<_IIter>::difference_type
  792. count(_IIter __begin, _IIter __end, const _Tp& __value)
  793. {
  794. return __count_switch(__begin, __end, __value,
  795. std::__iterator_category(__begin));
  796. }
  797. // Sequential fallback.
  798. template<typename _IIter, typename _Predicate>
  799. inline typename iterator_traits<_IIter>::difference_type
  800. count_if(_IIter __begin, _IIter __end, _Predicate __pred,
  801. __gnu_parallel::sequential_tag)
  802. { return _GLIBCXX_STD_A::count_if(__begin, __end, __pred); }
  803. // Parallel count_if for random access iterators
  804. template<typename _RAIter, typename _Predicate>
  805. typename iterator_traits<_RAIter>::difference_type
  806. __count_if_switch(_RAIter __begin, _RAIter __end,
  807. _Predicate __pred, random_access_iterator_tag,
  808. __gnu_parallel::_Parallelism __parallelism_tag)
  809. {
  810. typedef iterator_traits<_RAIter> _TraitsType;
  811. typedef typename _TraitsType::value_type _ValueType;
  812. typedef typename _TraitsType::difference_type _DifferenceType;
  813. typedef __gnu_parallel::_SequenceIndex _SequenceIndex;
  814. if (_GLIBCXX_PARALLEL_CONDITION(
  815. static_cast<_SequenceIndex>(__end - __begin)
  816. >= __gnu_parallel::_Settings::get().count_minimal_n
  817. && __gnu_parallel::__is_parallel(__parallelism_tag)))
  818. {
  819. _DifferenceType __res = 0;
  820. __gnu_parallel::
  821. __count_if_selector<_RAIter, _DifferenceType>
  822. __functionality;
  823. __gnu_parallel::
  824. __for_each_template_random_access(
  825. __begin, __end, __pred, __functionality,
  826. std::plus<_SequenceIndex>(), __res, __res, -1,
  827. __parallelism_tag);
  828. return __res;
  829. }
  830. else
  831. return count_if(__begin, __end, __pred,
  832. __gnu_parallel::sequential_tag());
  833. }
  834. // Sequential fallback for input iterator case.
  835. template<typename _IIter, typename _Predicate, typename _IteratorTag>
  836. inline typename iterator_traits<_IIter>::difference_type
  837. __count_if_switch(_IIter __begin, _IIter __end, _Predicate __pred,
  838. _IteratorTag)
  839. { return count_if(__begin, __end, __pred,
  840. __gnu_parallel::sequential_tag()); }
  841. // Public interface.
  842. template<typename _IIter, typename _Predicate>
  843. inline typename iterator_traits<_IIter>::difference_type
  844. count_if(_IIter __begin, _IIter __end, _Predicate __pred,
  845. __gnu_parallel::_Parallelism __parallelism_tag)
  846. {
  847. return __count_if_switch(__begin, __end, __pred,
  848. std::__iterator_category(__begin),
  849. __parallelism_tag);
  850. }
  851. template<typename _IIter, typename _Predicate>
  852. inline typename iterator_traits<_IIter>::difference_type
  853. count_if(_IIter __begin, _IIter __end, _Predicate __pred)
  854. {
  855. return __count_if_switch(__begin, __end, __pred,
  856. std::__iterator_category(__begin));
  857. }
  858. // Sequential fallback.
  859. template<typename _FIterator1, typename _FIterator2>
  860. inline _FIterator1
  861. search(_FIterator1 __begin1, _FIterator1 __end1,
  862. _FIterator2 __begin2, _FIterator2 __end2,
  863. __gnu_parallel::sequential_tag)
  864. { return _GLIBCXX_STD_A::search(__begin1, __end1, __begin2, __end2); }
  865. // Parallel algorithm for random access iterator
  866. template<typename _RAIter1, typename _RAIter2>
  867. _RAIter1
  868. __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
  869. _RAIter2 __begin2, _RAIter2 __end2,
  870. random_access_iterator_tag, random_access_iterator_tag)
  871. {
  872. typedef typename std::iterator_traits<_RAIter1>::value_type _ValueType1;
  873. typedef typename std::iterator_traits<_RAIter2>::value_type _ValueType2;
  874. if (_GLIBCXX_PARALLEL_CONDITION(
  875. static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  876. >= __gnu_parallel::_Settings::get().search_minimal_n))
  877. return __gnu_parallel::
  878. __search_template(
  879. __begin1, __end1, __begin2, __end2,
  880. __gnu_parallel::_EqualTo<_ValueType1, _ValueType2>());
  881. else
  882. return search(__begin1, __end1, __begin2, __end2,
  883. __gnu_parallel::sequential_tag());
  884. }
  885. // Sequential fallback for input iterator case
  886. template<typename _FIterator1, typename _FIterator2,
  887. typename _IteratorTag1, typename _IteratorTag2>
  888. inline _FIterator1
  889. __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
  890. _FIterator2 __begin2, _FIterator2 __end2,
  891. _IteratorTag1, _IteratorTag2)
  892. { return search(__begin1, __end1, __begin2, __end2,
  893. __gnu_parallel::sequential_tag()); }
  894. // Public interface.
  895. template<typename _FIterator1, typename _FIterator2>
  896. inline _FIterator1
  897. search(_FIterator1 __begin1, _FIterator1 __end1,
  898. _FIterator2 __begin2, _FIterator2 __end2)
  899. {
  900. return __search_switch(__begin1, __end1, __begin2, __end2,
  901. std::__iterator_category(__begin1),
  902. std::__iterator_category(__begin2));
  903. }
  904. // Public interface.
  905. template<typename _FIterator1, typename _FIterator2,
  906. typename _BinaryPredicate>
  907. inline _FIterator1
  908. search(_FIterator1 __begin1, _FIterator1 __end1,
  909. _FIterator2 __begin2, _FIterator2 __end2,
  910. _BinaryPredicate __pred, __gnu_parallel::sequential_tag)
  911. { return _GLIBCXX_STD_A::search(
  912. __begin1, __end1, __begin2, __end2, __pred); }
  913. // Parallel algorithm for random access iterator.
  914. template<typename _RAIter1, typename _RAIter2,
  915. typename _BinaryPredicate>
  916. _RAIter1
  917. __search_switch(_RAIter1 __begin1, _RAIter1 __end1,
  918. _RAIter2 __begin2, _RAIter2 __end2,
  919. _BinaryPredicate __pred,
  920. random_access_iterator_tag, random_access_iterator_tag)
  921. {
  922. if (_GLIBCXX_PARALLEL_CONDITION(
  923. static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  924. >= __gnu_parallel::_Settings::get().search_minimal_n))
  925. return __gnu_parallel::__search_template(__begin1, __end1,
  926. __begin2, __end2, __pred);
  927. else
  928. return search(__begin1, __end1, __begin2, __end2, __pred,
  929. __gnu_parallel::sequential_tag());
  930. }
  931. // Sequential fallback for input iterator case
  932. template<typename _FIterator1, typename _FIterator2,
  933. typename _BinaryPredicate, typename _IteratorTag1,
  934. typename _IteratorTag2>
  935. inline _FIterator1
  936. __search_switch(_FIterator1 __begin1, _FIterator1 __end1,
  937. _FIterator2 __begin2, _FIterator2 __end2,
  938. _BinaryPredicate __pred, _IteratorTag1, _IteratorTag2)
  939. { return search(__begin1, __end1, __begin2, __end2, __pred,
  940. __gnu_parallel::sequential_tag()); }
  941. // Public interface
  942. template<typename _FIterator1, typename _FIterator2,
  943. typename _BinaryPredicate>
  944. inline _FIterator1
  945. search(_FIterator1 __begin1, _FIterator1 __end1,
  946. _FIterator2 __begin2, _FIterator2 __end2,
  947. _BinaryPredicate __pred)
  948. {
  949. return __search_switch(__begin1, __end1, __begin2, __end2, __pred,
  950. std::__iterator_category(__begin1),
  951. std::__iterator_category(__begin2));
  952. }
  953. // Sequential fallback
  954. template<typename _FIterator, typename _Integer, typename _Tp>
  955. inline _FIterator
  956. search_n(_FIterator __begin, _FIterator __end, _Integer __count,
  957. const _Tp& __val, __gnu_parallel::sequential_tag)
  958. { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val); }
  959. // Sequential fallback
  960. template<typename _FIterator, typename _Integer, typename _Tp,
  961. typename _BinaryPredicate>
  962. inline _FIterator
  963. search_n(_FIterator __begin, _FIterator __end, _Integer __count,
  964. const _Tp& __val, _BinaryPredicate __binary_pred,
  965. __gnu_parallel::sequential_tag)
  966. { return _GLIBCXX_STD_A::search_n(
  967. __begin, __end, __count, __val, __binary_pred); }
  968. // Public interface.
  969. template<typename _FIterator, typename _Integer, typename _Tp>
  970. inline _FIterator
  971. search_n(_FIterator __begin, _FIterator __end, _Integer __count,
  972. const _Tp& __val)
  973. {
  974. typedef typename iterator_traits<_FIterator>::value_type _ValueType;
  975. return __gnu_parallel::search_n(__begin, __end, __count, __val,
  976. __gnu_parallel::_EqualTo<_ValueType, _Tp>());
  977. }
  978. // Parallel algorithm for random access iterators.
  979. template<typename _RAIter, typename _Integer,
  980. typename _Tp, typename _BinaryPredicate>
  981. _RAIter
  982. __search_n_switch(_RAIter __begin, _RAIter __end, _Integer __count,
  983. const _Tp& __val, _BinaryPredicate __binary_pred,
  984. random_access_iterator_tag)
  985. {
  986. if (_GLIBCXX_PARALLEL_CONDITION(
  987. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  988. >= __gnu_parallel::_Settings::get().search_minimal_n))
  989. {
  990. __gnu_parallel::_PseudoSequence<_Tp, _Integer> __ps(__val, __count);
  991. return __gnu_parallel::__search_template(
  992. __begin, __end, __ps.begin(), __ps.end(), __binary_pred);
  993. }
  994. else
  995. return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
  996. __binary_pred);
  997. }
  998. // Sequential fallback for input iterator case.
  999. template<typename _FIterator, typename _Integer, typename _Tp,
  1000. typename _BinaryPredicate, typename _IteratorTag>
  1001. inline _FIterator
  1002. __search_n_switch(_FIterator __begin, _FIterator __end, _Integer __count,
  1003. const _Tp& __val, _BinaryPredicate __binary_pred,
  1004. _IteratorTag)
  1005. { return _GLIBCXX_STD_A::search_n(__begin, __end, __count, __val,
  1006. __binary_pred); }
  1007. // Public interface.
  1008. template<typename _FIterator, typename _Integer, typename _Tp,
  1009. typename _BinaryPredicate>
  1010. inline _FIterator
  1011. search_n(_FIterator __begin, _FIterator __end, _Integer __count,
  1012. const _Tp& __val, _BinaryPredicate __binary_pred)
  1013. {
  1014. return __search_n_switch(__begin, __end, __count, __val, __binary_pred,
  1015. std::__iterator_category(__begin));
  1016. }
  1017. // Sequential fallback.
  1018. template<typename _IIter, typename _OutputIterator,
  1019. typename _UnaryOperation>
  1020. inline _OutputIterator
  1021. transform(_IIter __begin, _IIter __end, _OutputIterator __result,
  1022. _UnaryOperation __unary_op, __gnu_parallel::sequential_tag)
  1023. { return _GLIBCXX_STD_A::transform(__begin, __end, __result, __unary_op); }
  1024. // Parallel unary transform for random access iterators.
  1025. template<typename _RAIter1, typename _RAIter2,
  1026. typename _UnaryOperation>
  1027. _RAIter2
  1028. __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
  1029. _RAIter2 __result, _UnaryOperation __unary_op,
  1030. random_access_iterator_tag, random_access_iterator_tag,
  1031. __gnu_parallel::_Parallelism __parallelism_tag)
  1032. {
  1033. if (_GLIBCXX_PARALLEL_CONDITION(
  1034. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1035. >= __gnu_parallel::_Settings::get().transform_minimal_n
  1036. && __gnu_parallel::__is_parallel(__parallelism_tag)))
  1037. {
  1038. bool __dummy = true;
  1039. typedef __gnu_parallel::_IteratorPair<_RAIter1,
  1040. _RAIter2, random_access_iterator_tag> _ItTrip;
  1041. _ItTrip __begin_pair(__begin, __result),
  1042. __end_pair(__end, __result + (__end - __begin));
  1043. __gnu_parallel::__transform1_selector<_ItTrip> __functionality;
  1044. __gnu_parallel::
  1045. __for_each_template_random_access(
  1046. __begin_pair, __end_pair, __unary_op, __functionality,
  1047. __gnu_parallel::_DummyReduct(),
  1048. __dummy, __dummy, -1, __parallelism_tag);
  1049. return __functionality._M_finish_iterator;
  1050. }
  1051. else
  1052. return transform(__begin, __end, __result, __unary_op,
  1053. __gnu_parallel::sequential_tag());
  1054. }
  1055. // Sequential fallback for input iterator case.
  1056. template<typename _RAIter1, typename _RAIter2,
  1057. typename _UnaryOperation, typename _IteratorTag1,
  1058. typename _IteratorTag2>
  1059. inline _RAIter2
  1060. __transform1_switch(_RAIter1 __begin, _RAIter1 __end,
  1061. _RAIter2 __result, _UnaryOperation __unary_op,
  1062. _IteratorTag1, _IteratorTag2)
  1063. { return transform(__begin, __end, __result, __unary_op,
  1064. __gnu_parallel::sequential_tag()); }
  1065. // Public interface.
  1066. template<typename _IIter, typename _OutputIterator,
  1067. typename _UnaryOperation>
  1068. inline _OutputIterator
  1069. transform(_IIter __begin, _IIter __end, _OutputIterator __result,
  1070. _UnaryOperation __unary_op,
  1071. __gnu_parallel::_Parallelism __parallelism_tag)
  1072. {
  1073. return __transform1_switch(__begin, __end, __result, __unary_op,
  1074. std::__iterator_category(__begin),
  1075. std::__iterator_category(__result),
  1076. __parallelism_tag);
  1077. }
  1078. template<typename _IIter, typename _OutputIterator,
  1079. typename _UnaryOperation>
  1080. inline _OutputIterator
  1081. transform(_IIter __begin, _IIter __end, _OutputIterator __result,
  1082. _UnaryOperation __unary_op)
  1083. {
  1084. return __transform1_switch(__begin, __end, __result, __unary_op,
  1085. std::__iterator_category(__begin),
  1086. std::__iterator_category(__result));
  1087. }
  1088. // Sequential fallback
  1089. template<typename _IIter1, typename _IIter2,
  1090. typename _OutputIterator, typename _BinaryOperation>
  1091. inline _OutputIterator
  1092. transform(_IIter1 __begin1, _IIter1 __end1,
  1093. _IIter2 __begin2, _OutputIterator __result,
  1094. _BinaryOperation __binary_op, __gnu_parallel::sequential_tag)
  1095. { return _GLIBCXX_STD_A::transform(__begin1, __end1,
  1096. __begin2, __result, __binary_op); }
  1097. // Parallel binary transform for random access iterators.
  1098. template<typename _RAIter1, typename _RAIter2,
  1099. typename _RAIter3, typename _BinaryOperation>
  1100. _RAIter3
  1101. __transform2_switch(_RAIter1 __begin1, _RAIter1 __end1,
  1102. _RAIter2 __begin2,
  1103. _RAIter3 __result, _BinaryOperation __binary_op,
  1104. random_access_iterator_tag, random_access_iterator_tag,
  1105. random_access_iterator_tag,
  1106. __gnu_parallel::_Parallelism __parallelism_tag)
  1107. {
  1108. if (_GLIBCXX_PARALLEL_CONDITION(
  1109. (__end1 - __begin1) >=
  1110. __gnu_parallel::_Settings::get().transform_minimal_n
  1111. && __gnu_parallel::__is_parallel(__parallelism_tag)))
  1112. {
  1113. bool __dummy = true;
  1114. typedef __gnu_parallel::_IteratorTriple<_RAIter1,
  1115. _RAIter2, _RAIter3,
  1116. random_access_iterator_tag> _ItTrip;
  1117. _ItTrip __begin_triple(__begin1, __begin2, __result),
  1118. __end_triple(__end1, __begin2 + (__end1 - __begin1),
  1119. __result + (__end1 - __begin1));
  1120. __gnu_parallel::__transform2_selector<_ItTrip> __functionality;
  1121. __gnu_parallel::
  1122. __for_each_template_random_access(__begin_triple, __end_triple,
  1123. __binary_op, __functionality,
  1124. __gnu_parallel::_DummyReduct(),
  1125. __dummy, __dummy, -1,
  1126. __parallelism_tag);
  1127. return __functionality._M_finish_iterator;
  1128. }
  1129. else
  1130. return transform(__begin1, __end1, __begin2, __result, __binary_op,
  1131. __gnu_parallel::sequential_tag());
  1132. }
  1133. // Sequential fallback for input iterator case.
  1134. template<typename _IIter1, typename _IIter2,
  1135. typename _OutputIterator, typename _BinaryOperation,
  1136. typename _Tag1, typename _Tag2, typename _Tag3>
  1137. inline _OutputIterator
  1138. __transform2_switch(_IIter1 __begin1, _IIter1 __end1,
  1139. _IIter2 __begin2, _OutputIterator __result,
  1140. _BinaryOperation __binary_op, _Tag1, _Tag2, _Tag3)
  1141. { return transform(__begin1, __end1, __begin2, __result, __binary_op,
  1142. __gnu_parallel::sequential_tag()); }
  1143. // Public interface.
  1144. template<typename _IIter1, typename _IIter2,
  1145. typename _OutputIterator, typename _BinaryOperation>
  1146. inline _OutputIterator
  1147. transform(_IIter1 __begin1, _IIter1 __end1,
  1148. _IIter2 __begin2, _OutputIterator __result,
  1149. _BinaryOperation __binary_op,
  1150. __gnu_parallel::_Parallelism __parallelism_tag)
  1151. {
  1152. return __transform2_switch(
  1153. __begin1, __end1, __begin2, __result, __binary_op,
  1154. std::__iterator_category(__begin1),
  1155. std::__iterator_category(__begin2),
  1156. std::__iterator_category(__result),
  1157. __parallelism_tag);
  1158. }
  1159. template<typename _IIter1, typename _IIter2,
  1160. typename _OutputIterator, typename _BinaryOperation>
  1161. inline _OutputIterator
  1162. transform(_IIter1 __begin1, _IIter1 __end1,
  1163. _IIter2 __begin2, _OutputIterator __result,
  1164. _BinaryOperation __binary_op)
  1165. {
  1166. return __transform2_switch(
  1167. __begin1, __end1, __begin2, __result, __binary_op,
  1168. std::__iterator_category(__begin1),
  1169. std::__iterator_category(__begin2),
  1170. std::__iterator_category(__result));
  1171. }
  1172. // Sequential fallback
  1173. template<typename _FIterator, typename _Tp>
  1174. inline void
  1175. replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
  1176. const _Tp& __new_value, __gnu_parallel::sequential_tag)
  1177. { _GLIBCXX_STD_A::replace(__begin, __end, __old_value, __new_value); }
  1178. // Sequential fallback for input iterator case
  1179. template<typename _FIterator, typename _Tp, typename _IteratorTag>
  1180. inline void
  1181. __replace_switch(_FIterator __begin, _FIterator __end,
  1182. const _Tp& __old_value, const _Tp& __new_value,
  1183. _IteratorTag)
  1184. { replace(__begin, __end, __old_value, __new_value,
  1185. __gnu_parallel::sequential_tag()); }
  1186. // Parallel replace for random access iterators
  1187. template<typename _RAIter, typename _Tp>
  1188. inline void
  1189. __replace_switch(_RAIter __begin, _RAIter __end,
  1190. const _Tp& __old_value, const _Tp& __new_value,
  1191. random_access_iterator_tag,
  1192. __gnu_parallel::_Parallelism __parallelism_tag)
  1193. {
  1194. // XXX parallel version is where?
  1195. replace(__begin, __end, __old_value, __new_value,
  1196. __gnu_parallel::sequential_tag());
  1197. }
  1198. // Public interface
  1199. template<typename _FIterator, typename _Tp>
  1200. inline void
  1201. replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
  1202. const _Tp& __new_value,
  1203. __gnu_parallel::_Parallelism __parallelism_tag)
  1204. {
  1205. __replace_switch(__begin, __end, __old_value, __new_value,
  1206. std::__iterator_category(__begin),
  1207. __parallelism_tag);
  1208. }
  1209. template<typename _FIterator, typename _Tp>
  1210. inline void
  1211. replace(_FIterator __begin, _FIterator __end, const _Tp& __old_value,
  1212. const _Tp& __new_value)
  1213. {
  1214. __replace_switch(__begin, __end, __old_value, __new_value,
  1215. std::__iterator_category(__begin));
  1216. }
  1217. // Sequential fallback
  1218. template<typename _FIterator, typename _Predicate, typename _Tp>
  1219. inline void
  1220. replace_if(_FIterator __begin, _FIterator __end, _Predicate __pred,
  1221. const _Tp& __new_value, __gnu_parallel::sequential_tag)
  1222. { _GLIBCXX_STD_A::replace_if(__begin, __end, __pred, __new_value); }
  1223. // Sequential fallback for input iterator case
  1224. template<typename _FIterator, typename _Predicate, typename _Tp,
  1225. typename _IteratorTag>
  1226. inline void
  1227. __replace_if_switch(_FIterator __begin, _FIterator __end,
  1228. _Predicate __pred, const _Tp& __new_value, _IteratorTag)
  1229. { replace_if(__begin, __end, __pred, __new_value,
  1230. __gnu_parallel::sequential_tag()); }
  1231. // Parallel algorithm for random access iterators.
  1232. template<typename _RAIter, typename _Predicate, typename _Tp>
  1233. void
  1234. __replace_if_switch(_RAIter __begin, _RAIter __end,
  1235. _Predicate __pred, const _Tp& __new_value,
  1236. random_access_iterator_tag,
  1237. __gnu_parallel::_Parallelism __parallelism_tag)
  1238. {
  1239. if (_GLIBCXX_PARALLEL_CONDITION(
  1240. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1241. >= __gnu_parallel::_Settings::get().replace_minimal_n
  1242. && __gnu_parallel::__is_parallel(__parallelism_tag)))
  1243. {
  1244. bool __dummy;
  1245. __gnu_parallel::
  1246. __replace_if_selector<_RAIter, _Predicate, _Tp>
  1247. __functionality(__new_value);
  1248. __gnu_parallel::
  1249. __for_each_template_random_access(
  1250. __begin, __end, __pred, __functionality,
  1251. __gnu_parallel::_DummyReduct(),
  1252. true, __dummy, -1, __parallelism_tag);
  1253. }
  1254. else
  1255. replace_if(__begin, __end, __pred, __new_value,
  1256. __gnu_parallel::sequential_tag());
  1257. }
  1258. // Public interface.
  1259. template<typename _FIterator, typename _Predicate, typename _Tp>
  1260. inline void
  1261. replace_if(_FIterator __begin, _FIterator __end,
  1262. _Predicate __pred, const _Tp& __new_value,
  1263. __gnu_parallel::_Parallelism __parallelism_tag)
  1264. {
  1265. __replace_if_switch(__begin, __end, __pred, __new_value,
  1266. std::__iterator_category(__begin),
  1267. __parallelism_tag);
  1268. }
  1269. template<typename _FIterator, typename _Predicate, typename _Tp>
  1270. inline void
  1271. replace_if(_FIterator __begin, _FIterator __end,
  1272. _Predicate __pred, const _Tp& __new_value)
  1273. {
  1274. __replace_if_switch(__begin, __end, __pred, __new_value,
  1275. std::__iterator_category(__begin));
  1276. }
  1277. // Sequential fallback
  1278. template<typename _FIterator, typename _Generator>
  1279. inline void
  1280. generate(_FIterator __begin, _FIterator __end, _Generator __gen,
  1281. __gnu_parallel::sequential_tag)
  1282. { _GLIBCXX_STD_A::generate(__begin, __end, __gen); }
  1283. // Sequential fallback for input iterator case.
  1284. template<typename _FIterator, typename _Generator, typename _IteratorTag>
  1285. inline void
  1286. __generate_switch(_FIterator __begin, _FIterator __end, _Generator __gen,
  1287. _IteratorTag)
  1288. { generate(__begin, __end, __gen, __gnu_parallel::sequential_tag()); }
  1289. // Parallel algorithm for random access iterators.
  1290. template<typename _RAIter, typename _Generator>
  1291. void
  1292. __generate_switch(_RAIter __begin, _RAIter __end,
  1293. _Generator __gen, random_access_iterator_tag,
  1294. __gnu_parallel::_Parallelism __parallelism_tag)
  1295. {
  1296. if (_GLIBCXX_PARALLEL_CONDITION(
  1297. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1298. >= __gnu_parallel::_Settings::get().generate_minimal_n
  1299. && __gnu_parallel::__is_parallel(__parallelism_tag)))
  1300. {
  1301. bool __dummy;
  1302. __gnu_parallel::__generate_selector<_RAIter>
  1303. __functionality;
  1304. __gnu_parallel::
  1305. __for_each_template_random_access(
  1306. __begin, __end, __gen, __functionality,
  1307. __gnu_parallel::_DummyReduct(),
  1308. true, __dummy, -1, __parallelism_tag);
  1309. }
  1310. else
  1311. generate(__begin, __end, __gen, __gnu_parallel::sequential_tag());
  1312. }
  1313. // Public interface.
  1314. template<typename _FIterator, typename _Generator>
  1315. inline void
  1316. generate(_FIterator __begin, _FIterator __end,
  1317. _Generator __gen, __gnu_parallel::_Parallelism __parallelism_tag)
  1318. {
  1319. __generate_switch(__begin, __end, __gen,
  1320. std::__iterator_category(__begin),
  1321. __parallelism_tag);
  1322. }
  1323. template<typename _FIterator, typename _Generator>
  1324. inline void
  1325. generate(_FIterator __begin, _FIterator __end, _Generator __gen)
  1326. {
  1327. __generate_switch(__begin, __end, __gen,
  1328. std::__iterator_category(__begin));
  1329. }
  1330. // Sequential fallback.
  1331. template<typename _OutputIterator, typename _Size, typename _Generator>
  1332. inline _OutputIterator
  1333. generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
  1334. __gnu_parallel::sequential_tag)
  1335. { return _GLIBCXX_STD_A::generate_n(__begin, __n, __gen); }
  1336. // Sequential fallback for input iterator case.
  1337. template<typename _OutputIterator, typename _Size, typename _Generator,
  1338. typename _IteratorTag>
  1339. inline _OutputIterator
  1340. __generate_n_switch(_OutputIterator __begin, _Size __n, _Generator __gen,
  1341. _IteratorTag)
  1342. { return generate_n(__begin, __n, __gen,
  1343. __gnu_parallel::sequential_tag()); }
  1344. // Parallel algorithm for random access iterators.
  1345. template<typename _RAIter, typename _Size, typename _Generator>
  1346. inline _RAIter
  1347. __generate_n_switch(_RAIter __begin, _Size __n, _Generator __gen,
  1348. random_access_iterator_tag,
  1349. __gnu_parallel::_Parallelism __parallelism_tag)
  1350. {
  1351. // XXX parallel version is where?
  1352. return generate_n(__begin, __n, __gen, __gnu_parallel::sequential_tag());
  1353. }
  1354. // Public interface.
  1355. template<typename _OutputIterator, typename _Size, typename _Generator>
  1356. inline _OutputIterator
  1357. generate_n(_OutputIterator __begin, _Size __n, _Generator __gen,
  1358. __gnu_parallel::_Parallelism __parallelism_tag)
  1359. {
  1360. return __generate_n_switch(__begin, __n, __gen,
  1361. std::__iterator_category(__begin),
  1362. __parallelism_tag);
  1363. }
  1364. template<typename _OutputIterator, typename _Size, typename _Generator>
  1365. inline _OutputIterator
  1366. generate_n(_OutputIterator __begin, _Size __n, _Generator __gen)
  1367. {
  1368. return __generate_n_switch(__begin, __n, __gen,
  1369. std::__iterator_category(__begin));
  1370. }
  1371. // Sequential fallback.
  1372. template<typename _RAIter>
  1373. inline void
  1374. random_shuffle(_RAIter __begin, _RAIter __end,
  1375. __gnu_parallel::sequential_tag)
  1376. { _GLIBCXX_STD_A::random_shuffle(__begin, __end); }
  1377. // Sequential fallback.
  1378. template<typename _RAIter, typename _RandomNumberGenerator>
  1379. inline void
  1380. random_shuffle(_RAIter __begin, _RAIter __end,
  1381. _RandomNumberGenerator& __rand,
  1382. __gnu_parallel::sequential_tag)
  1383. { _GLIBCXX_STD_A::random_shuffle(__begin, __end, __rand); }
  1384. /** @brief Functor wrapper for std::rand(). */
  1385. template<typename _MustBeInt = int>
  1386. struct _CRandNumber
  1387. {
  1388. int
  1389. operator()(int __limit)
  1390. { return rand() % __limit; }
  1391. };
  1392. // Fill in random number generator.
  1393. template<typename _RAIter>
  1394. inline void
  1395. random_shuffle(_RAIter __begin, _RAIter __end)
  1396. {
  1397. _CRandNumber<> __r;
  1398. // Parallelization still possible.
  1399. __gnu_parallel::random_shuffle(__begin, __end, __r);
  1400. }
  1401. // Parallel algorithm for random access iterators.
  1402. template<typename _RAIter, typename _RandomNumberGenerator>
  1403. void
  1404. random_shuffle(_RAIter __begin, _RAIter __end,
  1405. #if __cplusplus >= 201103L
  1406. _RandomNumberGenerator&& __rand)
  1407. #else
  1408. _RandomNumberGenerator& __rand)
  1409. #endif
  1410. {
  1411. if (__begin == __end)
  1412. return;
  1413. if (_GLIBCXX_PARALLEL_CONDITION(
  1414. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1415. >= __gnu_parallel::_Settings::get().random_shuffle_minimal_n))
  1416. __gnu_parallel::__parallel_random_shuffle(__begin, __end, __rand);
  1417. else
  1418. __gnu_parallel::__sequential_random_shuffle(__begin, __end, __rand);
  1419. }
  1420. // Sequential fallback.
  1421. template<typename _FIterator, typename _Predicate>
  1422. inline _FIterator
  1423. partition(_FIterator __begin, _FIterator __end,
  1424. _Predicate __pred, __gnu_parallel::sequential_tag)
  1425. { return _GLIBCXX_STD_A::partition(__begin, __end, __pred); }
  1426. // Sequential fallback for input iterator case.
  1427. template<typename _FIterator, typename _Predicate, typename _IteratorTag>
  1428. inline _FIterator
  1429. __partition_switch(_FIterator __begin, _FIterator __end,
  1430. _Predicate __pred, _IteratorTag)
  1431. { return partition(__begin, __end, __pred,
  1432. __gnu_parallel::sequential_tag()); }
  1433. // Parallel algorithm for random access iterators.
  1434. template<typename _RAIter, typename _Predicate>
  1435. _RAIter
  1436. __partition_switch(_RAIter __begin, _RAIter __end,
  1437. _Predicate __pred, random_access_iterator_tag)
  1438. {
  1439. if (_GLIBCXX_PARALLEL_CONDITION(
  1440. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1441. >= __gnu_parallel::_Settings::get().partition_minimal_n))
  1442. {
  1443. typedef typename std::iterator_traits<_RAIter>::
  1444. difference_type _DifferenceType;
  1445. _DifferenceType __middle = __gnu_parallel::
  1446. __parallel_partition(__begin, __end, __pred,
  1447. __gnu_parallel::__get_max_threads());
  1448. return __begin + __middle;
  1449. }
  1450. else
  1451. return partition(__begin, __end, __pred,
  1452. __gnu_parallel::sequential_tag());
  1453. }
  1454. // Public interface.
  1455. template<typename _FIterator, typename _Predicate>
  1456. inline _FIterator
  1457. partition(_FIterator __begin, _FIterator __end, _Predicate __pred)
  1458. {
  1459. return __partition_switch(__begin, __end, __pred,
  1460. std::__iterator_category(__begin));
  1461. }
  1462. // sort interface
  1463. // Sequential fallback
  1464. template<typename _RAIter>
  1465. inline void
  1466. sort(_RAIter __begin, _RAIter __end,
  1467. __gnu_parallel::sequential_tag)
  1468. { _GLIBCXX_STD_A::sort(__begin, __end); }
  1469. // Sequential fallback
  1470. template<typename _RAIter, typename _Compare>
  1471. inline void
  1472. sort(_RAIter __begin, _RAIter __end, _Compare __comp,
  1473. __gnu_parallel::sequential_tag)
  1474. { _GLIBCXX_STD_A::sort<_RAIter, _Compare>(__begin, __end,
  1475. __comp); }
  1476. // Public interface
  1477. template<typename _RAIter, typename _Compare,
  1478. typename _Parallelism>
  1479. void
  1480. sort(_RAIter __begin, _RAIter __end, _Compare __comp,
  1481. _Parallelism __parallelism)
  1482. {
  1483. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1484. if (__begin != __end)
  1485. {
  1486. if (_GLIBCXX_PARALLEL_CONDITION(
  1487. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
  1488. __gnu_parallel::_Settings::get().sort_minimal_n))
  1489. __gnu_parallel::__parallel_sort<false>(
  1490. __begin, __end, __comp, __parallelism);
  1491. else
  1492. sort(__begin, __end, __comp, __gnu_parallel::sequential_tag());
  1493. }
  1494. }
  1495. // Public interface, insert default comparator
  1496. template<typename _RAIter>
  1497. inline void
  1498. sort(_RAIter __begin, _RAIter __end)
  1499. {
  1500. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1501. sort(__begin, __end, std::less<_ValueType>(),
  1502. __gnu_parallel::default_parallel_tag());
  1503. }
  1504. // Public interface, insert default comparator
  1505. template<typename _RAIter>
  1506. inline void
  1507. sort(_RAIter __begin, _RAIter __end,
  1508. __gnu_parallel::default_parallel_tag __parallelism)
  1509. {
  1510. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1511. sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1512. }
  1513. // Public interface, insert default comparator
  1514. template<typename _RAIter>
  1515. inline void
  1516. sort(_RAIter __begin, _RAIter __end,
  1517. __gnu_parallel::parallel_tag __parallelism)
  1518. {
  1519. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1520. sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1521. }
  1522. // Public interface, insert default comparator
  1523. template<typename _RAIter>
  1524. inline void
  1525. sort(_RAIter __begin, _RAIter __end,
  1526. __gnu_parallel::multiway_mergesort_tag __parallelism)
  1527. {
  1528. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1529. sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1530. }
  1531. // Public interface, insert default comparator
  1532. template<typename _RAIter>
  1533. inline void
  1534. sort(_RAIter __begin, _RAIter __end,
  1535. __gnu_parallel::multiway_mergesort_sampling_tag __parallelism)
  1536. {
  1537. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1538. sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1539. }
  1540. // Public interface, insert default comparator
  1541. template<typename _RAIter>
  1542. inline void
  1543. sort(_RAIter __begin, _RAIter __end,
  1544. __gnu_parallel::multiway_mergesort_exact_tag __parallelism)
  1545. {
  1546. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1547. sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1548. }
  1549. // Public interface, insert default comparator
  1550. template<typename _RAIter>
  1551. inline void
  1552. sort(_RAIter __begin, _RAIter __end,
  1553. __gnu_parallel::quicksort_tag __parallelism)
  1554. {
  1555. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1556. sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1557. }
  1558. // Public interface, insert default comparator
  1559. template<typename _RAIter>
  1560. inline void
  1561. sort(_RAIter __begin, _RAIter __end,
  1562. __gnu_parallel::balanced_quicksort_tag __parallelism)
  1563. {
  1564. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1565. sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1566. }
  1567. // Public interface
  1568. template<typename _RAIter, typename _Compare>
  1569. void
  1570. sort(_RAIter __begin, _RAIter __end, _Compare __comp)
  1571. {
  1572. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1573. sort(__begin, __end, __comp, __gnu_parallel::default_parallel_tag());
  1574. }
  1575. // stable_sort interface
  1576. // Sequential fallback
  1577. template<typename _RAIter>
  1578. inline void
  1579. stable_sort(_RAIter __begin, _RAIter __end,
  1580. __gnu_parallel::sequential_tag)
  1581. { _GLIBCXX_STD_A::stable_sort(__begin, __end); }
  1582. // Sequential fallback
  1583. template<typename _RAIter, typename _Compare>
  1584. inline void
  1585. stable_sort(_RAIter __begin, _RAIter __end,
  1586. _Compare __comp, __gnu_parallel::sequential_tag)
  1587. { _GLIBCXX_STD_A::stable_sort<_RAIter, _Compare>(__begin, __end, __comp); }
  1588. // Public interface
  1589. template<typename _RAIter, typename _Compare,
  1590. typename _Parallelism>
  1591. void
  1592. stable_sort(_RAIter __begin, _RAIter __end,
  1593. _Compare __comp, _Parallelism __parallelism)
  1594. {
  1595. typedef iterator_traits<_RAIter> _TraitsType;
  1596. typedef typename _TraitsType::value_type _ValueType;
  1597. if (__begin != __end)
  1598. {
  1599. if (_GLIBCXX_PARALLEL_CONDITION(
  1600. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin) >=
  1601. __gnu_parallel::_Settings::get().sort_minimal_n))
  1602. __gnu_parallel::__parallel_sort<true>(__begin, __end,
  1603. __comp, __parallelism);
  1604. else
  1605. stable_sort(__begin, __end, __comp,
  1606. __gnu_parallel::sequential_tag());
  1607. }
  1608. }
  1609. // Public interface, insert default comparator
  1610. template<typename _RAIter>
  1611. inline void
  1612. stable_sort(_RAIter __begin, _RAIter __end)
  1613. {
  1614. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1615. stable_sort(__begin, __end, std::less<_ValueType>(),
  1616. __gnu_parallel::default_parallel_tag());
  1617. }
  1618. // Public interface, insert default comparator
  1619. template<typename _RAIter>
  1620. inline void
  1621. stable_sort(_RAIter __begin, _RAIter __end,
  1622. __gnu_parallel::default_parallel_tag __parallelism)
  1623. {
  1624. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1625. stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1626. }
  1627. // Public interface, insert default comparator
  1628. template<typename _RAIter>
  1629. inline void
  1630. stable_sort(_RAIter __begin, _RAIter __end,
  1631. __gnu_parallel::parallel_tag __parallelism)
  1632. {
  1633. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1634. stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1635. }
  1636. // Public interface, insert default comparator
  1637. template<typename _RAIter>
  1638. inline void
  1639. stable_sort(_RAIter __begin, _RAIter __end,
  1640. __gnu_parallel::multiway_mergesort_tag __parallelism)
  1641. {
  1642. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1643. stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1644. }
  1645. // Public interface, insert default comparator
  1646. template<typename _RAIter>
  1647. inline void
  1648. stable_sort(_RAIter __begin, _RAIter __end,
  1649. __gnu_parallel::quicksort_tag __parallelism)
  1650. {
  1651. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1652. stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1653. }
  1654. // Public interface, insert default comparator
  1655. template<typename _RAIter>
  1656. inline void
  1657. stable_sort(_RAIter __begin, _RAIter __end,
  1658. __gnu_parallel::balanced_quicksort_tag __parallelism)
  1659. {
  1660. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1661. stable_sort(__begin, __end, std::less<_ValueType>(), __parallelism);
  1662. }
  1663. // Public interface
  1664. template<typename _RAIter, typename _Compare>
  1665. void
  1666. stable_sort(_RAIter __begin, _RAIter __end, _Compare __comp)
  1667. {
  1668. stable_sort(
  1669. __begin, __end, __comp, __gnu_parallel::default_parallel_tag());
  1670. }
  1671. // Sequential fallback
  1672. template<typename _IIter1, typename _IIter2,
  1673. typename _OutputIterator>
  1674. inline _OutputIterator
  1675. merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  1676. _IIter2 __end2, _OutputIterator __result,
  1677. __gnu_parallel::sequential_tag)
  1678. { return _GLIBCXX_STD_A::merge(
  1679. __begin1, __end1, __begin2, __end2, __result); }
  1680. // Sequential fallback
  1681. template<typename _IIter1, typename _IIter2,
  1682. typename _OutputIterator, typename _Compare>
  1683. inline _OutputIterator
  1684. merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  1685. _IIter2 __end2, _OutputIterator __result, _Compare __comp,
  1686. __gnu_parallel::sequential_tag)
  1687. { return _GLIBCXX_STD_A::merge(
  1688. __begin1, __end1, __begin2, __end2, __result, __comp); }
  1689. // Sequential fallback for input iterator case
  1690. template<typename _IIter1, typename _IIter2, typename _OutputIterator,
  1691. typename _Compare, typename _IteratorTag1,
  1692. typename _IteratorTag2, typename _IteratorTag3>
  1693. inline _OutputIterator
  1694. __merge_switch(_IIter1 __begin1, _IIter1 __end1,
  1695. _IIter2 __begin2, _IIter2 __end2,
  1696. _OutputIterator __result, _Compare __comp,
  1697. _IteratorTag1, _IteratorTag2, _IteratorTag3)
  1698. { return _GLIBCXX_STD_A::merge(__begin1, __end1, __begin2, __end2,
  1699. __result, __comp); }
  1700. // Parallel algorithm for random access iterators
  1701. template<typename _IIter1, typename _IIter2,
  1702. typename _OutputIterator, typename _Compare>
  1703. _OutputIterator
  1704. __merge_switch(_IIter1 __begin1, _IIter1 __end1,
  1705. _IIter2 __begin2, _IIter2 __end2,
  1706. _OutputIterator __result, _Compare __comp,
  1707. random_access_iterator_tag, random_access_iterator_tag,
  1708. random_access_iterator_tag)
  1709. {
  1710. if (_GLIBCXX_PARALLEL_CONDITION(
  1711. (static_cast<__gnu_parallel::_SequenceIndex>(__end1 - __begin1)
  1712. >= __gnu_parallel::_Settings::get().merge_minimal_n
  1713. || static_cast<__gnu_parallel::_SequenceIndex>(__end2 - __begin2)
  1714. >= __gnu_parallel::_Settings::get().merge_minimal_n)))
  1715. return __gnu_parallel::__parallel_merge_advance(
  1716. __begin1, __end1, __begin2, __end2, __result,
  1717. (__end1 - __begin1) + (__end2 - __begin2), __comp);
  1718. else
  1719. return __gnu_parallel::__merge_advance(
  1720. __begin1, __end1, __begin2, __end2, __result,
  1721. (__end1 - __begin1) + (__end2 - __begin2), __comp);
  1722. }
  1723. // Public interface
  1724. template<typename _IIter1, typename _IIter2,
  1725. typename _OutputIterator, typename _Compare>
  1726. inline _OutputIterator
  1727. merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  1728. _IIter2 __end2, _OutputIterator __result, _Compare __comp)
  1729. {
  1730. return __merge_switch(
  1731. __begin1, __end1, __begin2, __end2, __result, __comp,
  1732. std::__iterator_category(__begin1),
  1733. std::__iterator_category(__begin2),
  1734. std::__iterator_category(__result));
  1735. }
  1736. // Public interface, insert default comparator
  1737. template<typename _IIter1, typename _IIter2,
  1738. typename _OutputIterator>
  1739. inline _OutputIterator
  1740. merge(_IIter1 __begin1, _IIter1 __end1, _IIter2 __begin2,
  1741. _IIter2 __end2, _OutputIterator __result)
  1742. {
  1743. typedef typename std::iterator_traits<_IIter1>::value_type _ValueType1;
  1744. typedef typename std::iterator_traits<_IIter2>::value_type _ValueType2;
  1745. return __gnu_parallel::merge(__begin1, __end1, __begin2, __end2,
  1746. __result, __gnu_parallel::_Less<_ValueType1, _ValueType2>());
  1747. }
  1748. // Sequential fallback
  1749. template<typename _RAIter>
  1750. inline void
  1751. nth_element(_RAIter __begin, _RAIter __nth,
  1752. _RAIter __end, __gnu_parallel::sequential_tag)
  1753. { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end); }
  1754. // Sequential fallback
  1755. template<typename _RAIter, typename _Compare>
  1756. inline void
  1757. nth_element(_RAIter __begin, _RAIter __nth,
  1758. _RAIter __end, _Compare __comp,
  1759. __gnu_parallel::sequential_tag)
  1760. { return _GLIBCXX_STD_A::nth_element(__begin, __nth, __end, __comp); }
  1761. // Public interface
  1762. template<typename _RAIter, typename _Compare>
  1763. inline void
  1764. nth_element(_RAIter __begin, _RAIter __nth,
  1765. _RAIter __end, _Compare __comp)
  1766. {
  1767. if (_GLIBCXX_PARALLEL_CONDITION(
  1768. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1769. >= __gnu_parallel::_Settings::get().nth_element_minimal_n))
  1770. __gnu_parallel::__parallel_nth_element(__begin, __nth, __end, __comp);
  1771. else
  1772. nth_element(__begin, __nth, __end, __comp,
  1773. __gnu_parallel::sequential_tag());
  1774. }
  1775. // Public interface, insert default comparator
  1776. template<typename _RAIter>
  1777. inline void
  1778. nth_element(_RAIter __begin, _RAIter __nth,
  1779. _RAIter __end)
  1780. {
  1781. typedef typename iterator_traits<_RAIter>::value_type _ValueType;
  1782. __gnu_parallel::nth_element(__begin, __nth, __end,
  1783. std::less<_ValueType>());
  1784. }
  1785. // Sequential fallback
  1786. template<typename _RAIter, typename _Compare>
  1787. inline void
  1788. partial_sort(_RAIter __begin, _RAIter __middle,
  1789. _RAIter __end, _Compare __comp,
  1790. __gnu_parallel::sequential_tag)
  1791. { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end, __comp); }
  1792. // Sequential fallback
  1793. template<typename _RAIter>
  1794. inline void
  1795. partial_sort(_RAIter __begin, _RAIter __middle,
  1796. _RAIter __end, __gnu_parallel::sequential_tag)
  1797. { _GLIBCXX_STD_A::partial_sort(__begin, __middle, __end); }
  1798. // Public interface, parallel algorithm for random access iterators
  1799. template<typename _RAIter, typename _Compare>
  1800. void
  1801. partial_sort(_RAIter __begin, _RAIter __middle,
  1802. _RAIter __end, _Compare __comp)
  1803. {
  1804. if (_GLIBCXX_PARALLEL_CONDITION(
  1805. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1806. >= __gnu_parallel::_Settings::get().partial_sort_minimal_n))
  1807. __gnu_parallel::
  1808. __parallel_partial_sort(__begin, __middle, __end, __comp);
  1809. else
  1810. partial_sort(__begin, __middle, __end, __comp,
  1811. __gnu_parallel::sequential_tag());
  1812. }
  1813. // Public interface, insert default comparator
  1814. template<typename _RAIter>
  1815. inline void
  1816. partial_sort(_RAIter __begin, _RAIter __middle,
  1817. _RAIter __end)
  1818. {
  1819. typedef iterator_traits<_RAIter> _TraitsType;
  1820. typedef typename _TraitsType::value_type _ValueType;
  1821. __gnu_parallel::partial_sort(__begin, __middle, __end,
  1822. std::less<_ValueType>());
  1823. }
  1824. // Sequential fallback
  1825. template<typename _FIterator>
  1826. inline _FIterator
  1827. max_element(_FIterator __begin, _FIterator __end,
  1828. __gnu_parallel::sequential_tag)
  1829. { return _GLIBCXX_STD_A::max_element(__begin, __end); }
  1830. // Sequential fallback
  1831. template<typename _FIterator, typename _Compare>
  1832. inline _FIterator
  1833. max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
  1834. __gnu_parallel::sequential_tag)
  1835. { return _GLIBCXX_STD_A::max_element(__begin, __end, __comp); }
  1836. // Sequential fallback for input iterator case
  1837. template<typename _FIterator, typename _Compare, typename _IteratorTag>
  1838. inline _FIterator
  1839. __max_element_switch(_FIterator __begin, _FIterator __end,
  1840. _Compare __comp, _IteratorTag)
  1841. { return max_element(__begin, __end, __comp,
  1842. __gnu_parallel::sequential_tag()); }
  1843. // Parallel algorithm for random access iterators
  1844. template<typename _RAIter, typename _Compare>
  1845. _RAIter
  1846. __max_element_switch(_RAIter __begin, _RAIter __end,
  1847. _Compare __comp, random_access_iterator_tag,
  1848. __gnu_parallel::_Parallelism __parallelism_tag)
  1849. {
  1850. if (_GLIBCXX_PARALLEL_CONDITION(
  1851. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1852. >= __gnu_parallel::_Settings::get().max_element_minimal_n
  1853. && __gnu_parallel::__is_parallel(__parallelism_tag)))
  1854. {
  1855. _RAIter __res(__begin);
  1856. __gnu_parallel::__identity_selector<_RAIter>
  1857. __functionality;
  1858. __gnu_parallel::
  1859. __for_each_template_random_access(
  1860. __begin, __end, __gnu_parallel::_Nothing(), __functionality,
  1861. __gnu_parallel::__max_element_reduct<_Compare, _RAIter>(__comp),
  1862. __res, __res, -1, __parallelism_tag);
  1863. return __res;
  1864. }
  1865. else
  1866. return max_element(__begin, __end, __comp,
  1867. __gnu_parallel::sequential_tag());
  1868. }
  1869. // Public interface, insert default comparator
  1870. template<typename _FIterator>
  1871. inline _FIterator
  1872. max_element(_FIterator __begin, _FIterator __end,
  1873. __gnu_parallel::_Parallelism __parallelism_tag)
  1874. {
  1875. typedef typename iterator_traits<_FIterator>::value_type _ValueType;
  1876. return max_element(__begin, __end, std::less<_ValueType>(),
  1877. __parallelism_tag);
  1878. }
  1879. template<typename _FIterator>
  1880. inline _FIterator
  1881. max_element(_FIterator __begin, _FIterator __end)
  1882. {
  1883. typedef typename iterator_traits<_FIterator>::value_type _ValueType;
  1884. return __gnu_parallel::max_element(__begin, __end,
  1885. std::less<_ValueType>());
  1886. }
  1887. // Public interface
  1888. template<typename _FIterator, typename _Compare>
  1889. inline _FIterator
  1890. max_element(_FIterator __begin, _FIterator __end, _Compare __comp,
  1891. __gnu_parallel::_Parallelism __parallelism_tag)
  1892. {
  1893. return __max_element_switch(__begin, __end, __comp,
  1894. std::__iterator_category(__begin),
  1895. __parallelism_tag);
  1896. }
  1897. template<typename _FIterator, typename _Compare>
  1898. inline _FIterator
  1899. max_element(_FIterator __begin, _FIterator __end, _Compare __comp)
  1900. {
  1901. return __max_element_switch(__begin, __end, __comp,
  1902. std::__iterator_category(__begin));
  1903. }
  1904. // Sequential fallback
  1905. template<typename _FIterator>
  1906. inline _FIterator
  1907. min_element(_FIterator __begin, _FIterator __end,
  1908. __gnu_parallel::sequential_tag)
  1909. { return _GLIBCXX_STD_A::min_element(__begin, __end); }
  1910. // Sequential fallback
  1911. template<typename _FIterator, typename _Compare>
  1912. inline _FIterator
  1913. min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
  1914. __gnu_parallel::sequential_tag)
  1915. { return _GLIBCXX_STD_A::min_element(__begin, __end, __comp); }
  1916. // Sequential fallback for input iterator case
  1917. template<typename _FIterator, typename _Compare, typename _IteratorTag>
  1918. inline _FIterator
  1919. __min_element_switch(_FIterator __begin, _FIterator __end,
  1920. _Compare __comp, _IteratorTag)
  1921. { return min_element(__begin, __end, __comp,
  1922. __gnu_parallel::sequential_tag()); }
  1923. // Parallel algorithm for random access iterators
  1924. template<typename _RAIter, typename _Compare>
  1925. _RAIter
  1926. __min_element_switch(_RAIter __begin, _RAIter __end,
  1927. _Compare __comp, random_access_iterator_tag,
  1928. __gnu_parallel::_Parallelism __parallelism_tag)
  1929. {
  1930. if (_GLIBCXX_PARALLEL_CONDITION(
  1931. static_cast<__gnu_parallel::_SequenceIndex>(__end - __begin)
  1932. >= __gnu_parallel::_Settings::get().min_element_minimal_n
  1933. && __gnu_parallel::__is_parallel(__parallelism_tag)))
  1934. {
  1935. _RAIter __res(__begin);
  1936. __gnu_parallel::__identity_selector<_RAIter>
  1937. __functionality;
  1938. __gnu_parallel::
  1939. __for_each_template_random_access(
  1940. __begin, __end, __gnu_parallel::_Nothing(), __functionality,
  1941. __gnu_parallel::__min_element_reduct<_Compare, _RAIter>(__comp),
  1942. __res, __res, -1, __parallelism_tag);
  1943. return __res;
  1944. }
  1945. else
  1946. return min_element(__begin, __end, __comp,
  1947. __gnu_parallel::sequential_tag());
  1948. }
  1949. // Public interface, insert default comparator
  1950. template<typename _FIterator>
  1951. inline _FIterator
  1952. min_element(_FIterator __begin, _FIterator __end,
  1953. __gnu_parallel::_Parallelism __parallelism_tag)
  1954. {
  1955. typedef typename iterator_traits<_FIterator>::value_type _ValueType;
  1956. return min_element(__begin, __end, std::less<_ValueType>(),
  1957. __parallelism_tag);
  1958. }
  1959. template<typename _FIterator>
  1960. inline _FIterator
  1961. min_element(_FIterator __begin, _FIterator __end)
  1962. {
  1963. typedef typename iterator_traits<_FIterator>::value_type _ValueType;
  1964. return __gnu_parallel::min_element(__begin, __end,
  1965. std::less<_ValueType>());
  1966. }
  1967. // Public interface
  1968. template<typename _FIterator, typename _Compare>
  1969. inline _FIterator
  1970. min_element(_FIterator __begin, _FIterator __end, _Compare __comp,
  1971. __gnu_parallel::_Parallelism __parallelism_tag)
  1972. {
  1973. return __min_element_switch(__begin, __end, __comp,
  1974. std::__iterator_category(__begin),
  1975. __parallelism_tag);
  1976. }
  1977. template<typename _FIterator, typename _Compare>
  1978. inline _FIterator
  1979. min_element(_FIterator __begin, _FIterator __end, _Compare __comp)
  1980. {
  1981. return __min_element_switch(__begin, __end, __comp,
  1982. std::__iterator_category(__begin));
  1983. }
  1984. #if __cplusplus >= 201703L
  1985. using _GLIBCXX_STD_A::for_each_n;
  1986. using _GLIBCXX_STD_A::sample;
  1987. #endif
  1988. } // end namespace
  1989. } // end namespace
  1990. #endif /* _GLIBCXX_PARALLEL_ALGO_H */