The C and C++ Include Header Files

/usr/include/c++/11/parallel/set_operations.h


$ cat -n /usr/include/c++/11/parallel/set_operations.h

     1	// -*- C++ -*-
     2	
     3	// Copyright (C) 2007-2021 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 */