visus
/
toolchain-gcc-arm-embedded
Watch 1
Star 0
Fork 0
Code Issues 0 Pull Requests 0 Releases 0 Wiki Activity
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.
2 Commits
1 Branch
Branch: main
Branches Tags
${ item.name }
Create branch ${ searchTerm }
from 'main'
${ noResults }
toolchain-gcc-arm-embedded/arm-none-eabi/include/c++/10.2.1/parallel/set_operations.h

530 lines
14KB
Raw Permalink Blame History 

  1. // -*- C++ -*-

  2. 

  3. // Copyright (C) 2007-2020 Free Software Foundation, Inc.

  4. //

  5. // This file is part of the GNU ISO C++ Library.  This library is free

  6. // software; you can redistribute it and/or modify it under the terms

  7. // of the GNU General Public License as published by the Free Software

  8. // Foundation; either version 3, or (at your option) any later

  9. // version.

  10. 

  11. // This library is distributed in the hope that it will be useful, but

  12. // WITHOUT ANY WARRANTY; without even the implied warranty of

  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

  14. // General Public License for more details.

  15. 

  16. // Under Section 7 of GPL version 3, you are granted additional

  17. // permissions described in the GCC Runtime Library Exception, version

  18. // 3.1, as published by the Free Software Foundation.

  19. 

  20. // You should have received a copy of the GNU General Public License and

  21. // a copy of the GCC Runtime Library Exception along with this program;

  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

  23. // <http://www.gnu.org/licenses/>.

  24. 

  25. /**

  26.  * @file parallel/set_operations.h

  27.  * @brief Parallel implementations of set operations for random-access

  28.  * iterators.

  29.  *  This file is a GNU parallel extension to the Standard C++ Library.

  30.  */

  31. 

  32. // Written by Marius Elvert and Felix Bondarenko.

  33. 

  34. #ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H

  35. #define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1

  36. 

  37. #include <omp.h>

  38. 

  39. #include <parallel/settings.h>

  40. #include <parallel/multiseq_selection.h>

  41. 

  42. namespace __gnu_parallel

  43. {

  44.   template<typename _IIter, typename _OutputIterator>

  45.     _OutputIterator

  46.     __copy_tail(std::pair<_IIter, _IIter> __b,

  47. 		std::pair<_IIter, _IIter> __e, _OutputIterator __r)

  48.     {

  49.       if (__b.first != __e.first)

  50. 	{

  51.           do

  52.             {

  53.               *__r++ = *__b.first++;

  54.             }

  55.           while (__b.first != __e.first);

  56. 	}

  57.       else

  58. 	{

  59.           while (__b.second != __e.second)

  60.             *__r++ = *__b.second++;

  61. 	}

  62.       return __r;

  63.     }

  64. 

  65.   template<typename _IIter,

  66.            typename _OutputIterator,

  67.            typename _Compare>

  68.     struct __symmetric_difference_func

  69.     {

  70.       typedef std::iterator_traits<_IIter> _TraitsType;

  71.       typedef typename _TraitsType::difference_type _DifferenceType;

  72.       typedef typename std::pair<_IIter, _IIter> _IteratorPair;

  73. 

  74.       __symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {}

  75. 

  76.       _Compare _M_comp;

  77. 

  78.       _OutputIterator

  79.       _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,

  80. 		_OutputIterator __r) const

  81.       {

  82. 	while (__a != __b && __c != __d)

  83.           {

  84.             if (_M_comp(*__a, *__c))

  85.               {

  86.         	*__r = *__a;

  87.         	++__a;

  88.         	++__r;

  89.               }

  90.             else if (_M_comp(*__c, *__a))

  91.               {

  92.         	*__r = *__c;

  93.         	++__c;

  94.         	++__r;

  95.               }

  96.             else

  97.               {

  98.         	++__a;

  99.         	++__c;

  100.               }

  101.           }

  102. 	return std::copy(__c, __d, std::copy(__a, __b, __r));

  103.       }

  104. 

  105.       _DifferenceType

  106.       __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const

  107.       {

  108. 	_DifferenceType __counter = 0;

  109. 

  110. 	while (__a != __b && __c != __d)

  111.           {

  112.             if (_M_comp(*__a, *__c))

  113.               {

  114.         	++__a;

  115.         	++__counter;

  116.               }

  117.             else if (_M_comp(*__c, *__a))

  118.               {

  119.         	++__c;

  120.         	++__counter;

  121.               }

  122.             else

  123.               {

  124.         	++__a;

  125.         	++__c;

  126.               }

  127.           }

  128. 

  129. 	return __counter + (__b - __a) + (__d - __c);

  130.       }

  131. 

  132.       _OutputIterator

  133.       __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const

  134.       { return std::copy(__c, __d, __out); }

  135. 

  136.       _OutputIterator

  137.       __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const

  138.       { return std::copy(__a, __b, __out); }

  139.     };

  140. 

  141. 

  142.   template<typename _IIter,

  143.            typename _OutputIterator,

  144.            typename _Compare>

  145.     struct __difference_func

  146.     {

  147.       typedef std::iterator_traits<_IIter> _TraitsType;

  148.       typedef typename _TraitsType::difference_type _DifferenceType;

  149.       typedef typename std::pair<_IIter, _IIter> _IteratorPair;

  150. 

  151.       __difference_func(_Compare __comp) : _M_comp(__comp) {}

  152. 

  153.       _Compare _M_comp;

  154. 

  155.       _OutputIterator

  156.       _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,

  157. 		_OutputIterator __r) const

  158.       {

  159. 	while (__a != __b && __c != __d)

  160.           {

  161.             if (_M_comp(*__a, *__c))

  162.               {

  163.         	*__r = *__a;

  164.         	++__a;

  165.         	++__r;

  166.               }

  167.             else if (_M_comp(*__c, *__a))

  168.               { ++__c; }

  169.             else

  170.               {

  171.         	++__a;

  172.         	++__c;

  173.               }

  174.           }

  175. 	return std::copy(__a, __b, __r);

  176.       }

  177. 

  178.       _DifferenceType

  179.       __count(_IIter __a, _IIter __b,

  180. 	      _IIter __c, _IIter __d) const

  181.       {

  182. 	_DifferenceType __counter = 0;

  183. 

  184. 	while (__a != __b && __c != __d)

  185.           {

  186.             if (_M_comp(*__a, *__c))

  187.               {

  188.         	++__a;

  189.         	++__counter;

  190.               }

  191.             else if (_M_comp(*__c, *__a))

  192.               { ++__c; }

  193.             else

  194.               { ++__a; ++__c; }

  195.           }

  196. 

  197. 	return __counter + (__b - __a);

  198.       }

  199. 

  200.       _OutputIterator

  201.       __first_empty(_IIter, _IIter, _OutputIterator __out) const

  202.       { return __out; }

  203. 

  204.       _OutputIterator

  205.       __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const

  206.       { return std::copy(__a, __b, __out); }

  207.     };

  208. 

  209. 

  210.   template<typename _IIter,

  211.            typename _OutputIterator,

  212.            typename _Compare>

  213.     struct __intersection_func

  214.     {

  215.       typedef std::iterator_traits<_IIter> _TraitsType;

  216.       typedef typename _TraitsType::difference_type _DifferenceType;

  217.       typedef typename std::pair<_IIter, _IIter> _IteratorPair;

  218. 

  219.       __intersection_func(_Compare __comp) : _M_comp(__comp) {}

  220. 

  221.       _Compare _M_comp;

  222. 

  223.       _OutputIterator

  224.       _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter __d,

  225. 		_OutputIterator __r) const

  226.       {

  227. 	while (__a != __b && __c != __d)

  228.           {

  229.             if (_M_comp(*__a, *__c))

  230.               { ++__a; }

  231.             else if (_M_comp(*__c, *__a))

  232.               { ++__c; }

  233.             else

  234.               {

  235.         	*__r = *__a;

  236.         	++__a;

  237.         	++__c;

  238.         	++__r;

  239.               }

  240.           }

  241. 

  242. 	return __r;

  243.       }

  244. 

  245.       _DifferenceType

  246.       __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const

  247.       {

  248. 	_DifferenceType __counter = 0;

  249. 

  250. 	while (__a != __b && __c != __d)

  251.           {

  252.             if (_M_comp(*__a, *__c))

  253.               { ++__a; }

  254.             else if (_M_comp(*__c, *__a))

  255.               { ++__c; }

  256.             else

  257.               {

  258.         	++__a;

  259.         	++__c;

  260.         	++__counter;

  261.               }

  262.           }

  263. 

  264. 	return __counter;

  265.       }

  266. 

  267.       _OutputIterator

  268.       __first_empty(_IIter, _IIter, _OutputIterator __out) const

  269.       { return __out; }

  270. 

  271.       _OutputIterator

  272.       __second_empty(_IIter, _IIter, _OutputIterator __out) const

  273.       { return __out; }

  274.     };

  275. 

  276.   template<class _IIter, class _OutputIterator, class _Compare>

  277.     struct __union_func

  278.     {

  279.       typedef typename std::iterator_traits<_IIter>::difference_type

  280.       _DifferenceType;

  281. 

  282.       __union_func(_Compare __comp) : _M_comp(__comp) {}

  283. 

  284.       _Compare _M_comp;

  285. 

  286.       _OutputIterator

  287.       _M_invoke(_IIter __a, const _IIter __b, _IIter __c,

  288. 		const _IIter __d, _OutputIterator __r) const

  289.       {

  290. 	while (__a != __b && __c != __d)

  291.           {

  292.             if (_M_comp(*__a, *__c))

  293.               {

  294.         	*__r = *__a;

  295.         	++__a;

  296.               }

  297.             else if (_M_comp(*__c, *__a))

  298.               {

  299.         	*__r = *__c;

  300.         	++__c;

  301.               }

  302.             else

  303.               {

  304.         	*__r = *__a;

  305.         	++__a;

  306.         	++__c;

  307.               }

  308.             ++__r;

  309.           }

  310. 	return std::copy(__c, __d, std::copy(__a, __b, __r));

  311.       }

  312. 

  313.       _DifferenceType

  314.       __count(_IIter __a, _IIter __b, _IIter __c, _IIter __d) const

  315.       {

  316. 	_DifferenceType __counter = 0;

  317. 

  318. 	while (__a != __b && __c != __d)

  319.           {

  320.             if (_M_comp(*__a, *__c))

  321.               { ++__a; }

  322.             else if (_M_comp(*__c, *__a))

  323.               { ++__c; }

  324.             else

  325.               {

  326.         	++__a;

  327.         	++__c;

  328.               }

  329.             ++__counter;

  330.           }

  331. 

  332. 	__counter += (__b - __a);

  333. 	__counter += (__d - __c);

  334. 	return __counter;

  335.       }

  336. 

  337.       _OutputIterator

  338.       __first_empty(_IIter __c, _IIter __d, _OutputIterator __out) const

  339.       { return std::copy(__c, __d, __out); }

  340. 

  341.       _OutputIterator

  342.       __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const

  343.       { return std::copy(__a, __b, __out); }

  344.     };

  345. 

  346.   template<typename _IIter,

  347.            typename _OutputIterator,

  348.            typename _Operation>

  349.     _OutputIterator

  350.     __parallel_set_operation(_IIter __begin1, _IIter __end1,

  351. 			     _IIter __begin2, _IIter __end2,

  352. 			     _OutputIterator __result, _Operation __op)

  353.     {

  354.       _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2))

  355. 

  356.       typedef std::iterator_traits<_IIter> _TraitsType;

  357.       typedef typename _TraitsType::difference_type _DifferenceType;

  358.       typedef typename std::pair<_IIter, _IIter> _IteratorPair;

  359. 

  360.       if (__begin1 == __end1)

  361. 	return __op.__first_empty(__begin2, __end2, __result);

  362. 

  363.       if (__begin2 == __end2)

  364. 	return __op.__second_empty(__begin1, __end1, __result);

  365. 

  366.       const _DifferenceType __size = (__end1 - __begin1) + (__end2 - __begin2);

  367. 

  368.       const _IteratorPair __sequence[2] = { std::make_pair(__begin1, __end1),

  369. 					    std::make_pair(__begin2, __end2) };

  370.       _OutputIterator __return_value = __result;

  371.       _DifferenceType *__borders;

  372.       _IteratorPair *__block_begins;

  373.       _DifferenceType* __lengths;

  374. 

  375.       _ThreadIndex __num_threads =

  376.           std::min<_DifferenceType>(__get_max_threads(),

  377.               std::min(__end1 - __begin1, __end2 - __begin2));

  378. 

  379. #     pragma omp parallel num_threads(__num_threads)

  380.       {

  381. #       pragma omp single

  382. 	{

  383. 	  __num_threads = omp_get_num_threads();

  384. 

  385. 	  __borders = new _DifferenceType[__num_threads + 2];

  386. 	  __equally_split(__size, __num_threads + 1, __borders);

  387. 	  __block_begins = new _IteratorPair[__num_threads + 1];

  388. 	  // Very __start.

  389. 	  __block_begins[0] = std::make_pair(__begin1, __begin2);

  390. 	  __lengths = new _DifferenceType[__num_threads];

  391. 	} //single

  392. 

  393. 	_ThreadIndex __iam = omp_get_thread_num();

  394. 

  395. 	// _Result from multiseq_partition.

  396. 	_IIter __offset[2];

  397. 	const _DifferenceType __rank = __borders[__iam + 1];

  398. 

  399. 	multiseq_partition(__sequence, __sequence + 2,

  400. 			   __rank, __offset, __op._M_comp);

  401. 

  402. 	// allowed to read?

  403. 	// together

  404. 	// *(__offset[ 0 ] - 1) == *__offset[ 1 ]

  405. 	if (__offset[ 0 ] != __begin1 && __offset[1] != __end2

  406. 	    && !__op._M_comp(*(__offset[0] - 1), *__offset[1])

  407. 	    && !__op._M_comp(*__offset[1], *(__offset[0] - 1)))

  408. 	  {

  409. 	    // Avoid split between globally equal elements: move one to

  410. 	    // front in first sequence.

  411.               --__offset[0];

  412. 	  }

  413. 

  414. 	_IteratorPair __block_end = __block_begins[__iam + 1] =

  415. 	  _IteratorPair(__offset[0], __offset[1]);

  416. 

  417. 	// Make sure all threads have their block_begin result written out.

  418. #       pragma omp barrier

  419. 

  420. 	_IteratorPair __block_begin = __block_begins[__iam];

  421. 

  422. 	// Begin working for the first block, while the others except

  423. 	// the last start to count.

  424. 	if (__iam == 0)

  425. 	  {

  426. 	    // The first thread can copy already.

  427. 	    __lengths[ __iam ] =

  428. 	      __op._M_invoke(__block_begin.first, __block_end.first,

  429. 			     __block_begin.second, __block_end.second,

  430. 			     __result) - __result;

  431. 	  }

  432. 	else

  433. 	  {

  434. 	    __lengths[ __iam ] =

  435. 	      __op.__count(__block_begin.first, __block_end.first,

  436. 			   __block_begin.second, __block_end.second);

  437. 	  }

  438. 

  439. 	// Make sure everyone wrote their lengths.

  440. #       pragma omp barrier

  441. 

  442. 	_OutputIterator __r = __result;

  443. 

  444. 	if (__iam == 0)

  445. 	  {

  446. 	    // Do the last block.

  447. 	    for (_ThreadIndex __i = 0; __i < __num_threads; ++__i)

  448. 	      __r += __lengths[__i];

  449. 

  450. 	    __block_begin = __block_begins[__num_threads];

  451. 

  452. 	    // Return the result iterator of the last block.

  453. 	    __return_value =

  454. 	      __op._M_invoke(__block_begin.first, __end1,

  455. 			     __block_begin.second, __end2, __r);

  456. 

  457. 	  }

  458.           else

  459.             {

  460.               for (_ThreadIndex __i = 0; __i < __iam; ++__i)

  461.         	__r += __lengths[ __i ];

  462. 

  463.               // Reset begins for copy pass.

  464.               __op._M_invoke(__block_begin.first, __block_end.first,

  465. 			     __block_begin.second, __block_end.second, __r);

  466.             }

  467. 	}

  468.       return __return_value;

  469.     }

  470. 

  471.   template<typename _IIter,

  472.            typename _OutputIterator,

  473.            typename _Compare>

  474.     inline _OutputIterator

  475.     __parallel_set_union(_IIter __begin1, _IIter __end1,

  476. 			 _IIter __begin2, _IIter __end2,

  477. 			 _OutputIterator __result, _Compare __comp)

  478.     {

  479.       return __parallel_set_operation(__begin1, __end1, __begin2, __end2,

  480. 				      __result,

  481. 				      __union_func< _IIter, _OutputIterator,

  482. 				      _Compare>(__comp));

  483.     }

  484. 

  485.   template<typename _IIter,

  486.            typename _OutputIterator,

  487.            typename _Compare>

  488.     inline _OutputIterator

  489.     __parallel_set_intersection(_IIter __begin1, _IIter __end1,

  490.                         	_IIter __begin2, _IIter __end2,

  491.                         	_OutputIterator __result, _Compare __comp)

  492.     {

  493.       return __parallel_set_operation(__begin1, __end1, __begin2, __end2,

  494. 				      __result,

  495. 				      __intersection_func<_IIter,

  496. 				      _OutputIterator, _Compare>(__comp));

  497.     }

  498. 

  499.   template<typename _IIter,

  500.            typename _OutputIterator,

  501.            typename _Compare>

  502.     inline _OutputIterator

  503.     __parallel_set_difference(_IIter __begin1, _IIter __end1,

  504.                               _IIter __begin2, _IIter __end2,

  505.                               _OutputIterator __result, _Compare __comp)

  506.     {

  507.       return __parallel_set_operation(__begin1, __end1, __begin2, __end2,

  508. 				      __result,

  509. 				      __difference_func<_IIter,

  510. 				      _OutputIterator, _Compare>(__comp));

  511.     }

  512. 

  513.   template<typename _IIter,

  514.            typename _OutputIterator,

  515.            typename _Compare>

  516.     inline _OutputIterator

  517.     __parallel_set_symmetric_difference(_IIter __begin1, _IIter __end1,

  518.                                 	_IIter __begin2, _IIter __end2,

  519.                                 	_OutputIterator __result,

  520.                                 	_Compare __comp)

  521.     {

  522.       return __parallel_set_operation(__begin1, __end1, __begin2, __end2,

  523. 				      __result,

  524. 				      __symmetric_difference_func<_IIter,

  525. 				      _OutputIterator, _Compare>(__comp));

  526.     }

  527. }

  528. 

  529. #endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */