// -*- C++ -*-
// Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
/**
* @file parallel/set_operations.h
* @brief Parallel implementations of set operations for random-access
* iterators.
* This file is a GNU parallel extension to the Standard C++ Library.
*/
// Written by Marius Elvert and Felix Bondarenko.
#ifndef _GLIBCXX_PARALLEL_SET_OPERATIONS_H
#define _GLIBCXX_PARALLEL_SET_OPERATIONS_H 1
#include <omp.h>
#include <parallel/settings.h>
#include <parallel/multiseq_selection.h>
namespace __gnu_parallel
{
template<typename InputIterator, typename OutputIterator>
OutputIterator
copy_tail(std::pair<InputIterator, InputIterator> b,
std::pair<InputIterator, InputIterator> e, OutputIterator r)
{
if (b.first != e.first)
{
do
{
*r++ = *b.first++;
}
while (b.first != e.first);
}
else
{
while (b.second != e.second)
*r++ = *b.second++;
}
return r;
}
template<typename InputIterator,
typename OutputIterator,
typename Comparator>
struct symmetric_difference_func
{
typedef std::iterator_traits<InputIterator> traits_type;
typedef typename traits_type::difference_type difference_type;
typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
symmetric_difference_func(Comparator c) : comp(c) {}
Comparator comp;
OutputIterator
invoke(InputIterator a, InputIterator b,
InputIterator c, InputIterator d,
OutputIterator r) const
{
while (a != b && c != d)
{
if (comp(*a, *c))
{
*r = *a;
++a;
++r;
}
else if (comp(*c, *a))
{
*r = *c;
++c;
++r;
}
else
{
++a;
++c;
}
}
return std::copy(c, d, std::copy(a, b, r));
}
difference_type
count(InputIterator a, InputIterator b,
InputIterator c, InputIterator d) const
{
difference_type counter = 0;
while (a != b && c != d)
{
if (comp(*a, *c))
{
++a;
++counter;
}
else if (comp(*c, *a))
{
++c;
++counter;
}
else
{
++a;
++c;
}
}
return counter + (b - a) + (d - c);
}
OutputIterator
first_empty(InputIterator c, InputIterator d, OutputIterator out) const
{ return std::copy(c, d, out); }
OutputIterator
second_empty(InputIterator a, InputIterator b, OutputIterator out) const
{ return std::copy(a, b, out); }
};
template<typename InputIterator,
typename OutputIterator,
typename Comparator>
struct difference_func
{
typedef std::iterator_traits<InputIterator> traits_type;
typedef typename traits_type::difference_type difference_type;
typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
difference_func(Comparator c) : comp(c) {}
Comparator comp;
OutputIterator
invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
OutputIterator r) const
{
while (a != b && c != d)
{
if (comp(*a, *c))
{
*r = *a;
++a;
++r;
}
else if (comp(*c, *a))
{ ++c; }
else
{
++a;
++c;
}
}
return std::copy(a, b, r);
}
difference_type
count(InputIterator a, InputIterator b,
InputIterator c, InputIterator d) const
{
difference_type counter = 0;
while (a != b && c != d)
{
if (comp(*a, *c))
{
++a;
++counter;
}
else if (comp(*c, *a))
{ ++c; }
else
{ ++a; ++c; }
}
return counter + (b - a);
}
inline OutputIterator
first_empty(InputIterator c, InputIterator d, OutputIterator out) const
{ return out; }
inline OutputIterator
second_empty(InputIterator a, InputIterator b, OutputIterator out) const
{ return std::copy(a, b, out); }
};
template<typename InputIterator,
typename OutputIterator,
typename Comparator>
struct intersection_func
{
typedef std::iterator_traits<InputIterator> traits_type;
typedef typename traits_type::difference_type difference_type;
typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
intersection_func(Comparator c) : comp(c) {}
Comparator comp;
OutputIterator
invoke(InputIterator a, InputIterator b, InputIterator c, InputIterator d,
OutputIterator r) const
{
while (a != b && c != d)
{
if (comp(*a, *c))
{ ++a; }
else if (comp(*c, *a))
{ ++c; }
else
{
*r = *a;
++a;
++c;
++r;
}
}
return r;
}
difference_type
count(InputIterator a, InputIterator b,
InputIterator c, InputIterator d) const
{
difference_type counter = 0;
while (a != b && c != d)
{
if (comp(*a, *c))
{ ++a; }
else if (comp(*c, *a))
{ ++c; }
else
{
++a;
++c;
++counter;
}
}
return counter;
}
inline OutputIterator
first_empty(InputIterator c, InputIterator d, OutputIterator out) const
{ return out; }
inline OutputIterator
second_empty(InputIterator a, InputIterator b, OutputIterator out) const
{ return out; }
};
template<class InputIterator, class OutputIterator, class Comparator>
struct union_func
{
typedef typename std::iterator_traits<InputIterator>::difference_type
difference_type;
union_func(Comparator c) : comp(c) {}
Comparator comp;
OutputIterator
invoke(InputIterator a, const InputIterator b, InputIterator c,
const InputIterator d, OutputIterator r) const
{
while (a != b && c != d)
{
if (comp(*a, *c))
{
*r = *a;
++a;
}
else if (comp(*c, *a))
{
*r = *c;
++c;
}
else
{
*r = *a;
++a;
++c;
}
++r;
}
return std::copy(c, d, std::copy(a, b, r));
}
difference_type
count(InputIterator a, InputIterator b,
InputIterator c, InputIterator d) const
{
difference_type counter = 0;
while (a != b && c != d)
{
if (comp(*a, *c))
{ ++a; }
else if (comp(*c, *a))
{ ++c; }
else
{
++a;
++c;
}
++counter;
}
counter += (b - a);
counter += (d - c);
return counter;
}
inline OutputIterator
first_empty(InputIterator c, InputIterator d, OutputIterator out) const
{ return std::copy(c, d, out); }
inline OutputIterator
second_empty(InputIterator a, InputIterator b, OutputIterator out) const
{ return std::copy(a, b, out); }
};
template<typename InputIterator,
typename OutputIterator,
typename Operation>
OutputIterator
parallel_set_operation(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator result, Operation op)
{
_GLIBCXX_CALL((end1 - begin1) + (end2 - begin2))
typedef std::iterator_traits<InputIterator> traits_type;
typedef typename traits_type::difference_type difference_type;
typedef typename std::pair<InputIterator, InputIterator> iterator_pair;
if (begin1 == end1)
return op.first_empty(begin2, end2, result);
if (begin2 == end2)
return op.second_empty(begin1, end1, result);
const difference_type size = (end1 - begin1) + (end2 - begin2);
const iterator_pair sequence[ 2 ] =
{ std::make_pair(begin1, end1), std::make_pair(begin2, end2) } ;
OutputIterator return_value = result;
difference_type *borders;
iterator_pair *block_begins;
difference_type* lengths;
thread_index_t num_threads =
std::min<difference_type>(get_max_threads(),
std::min(end1 - begin1, end2 - begin2));
# pragma omp parallel num_threads(num_threads)
{
# pragma omp single
{
num_threads = omp_get_num_threads();
borders = new difference_type[num_threads + 2];
equally_split(size, num_threads + 1, borders);
block_begins = new iterator_pair[num_threads + 1];
// Very start.
block_begins[0] = std::make_pair(begin1, begin2);
lengths = new difference_type[num_threads];
} //single
thread_index_t iam = omp_get_thread_num();
// Result from multiseq_partition.
InputIterator offset[2];
const difference_type rank = borders[iam + 1];
multiseq_partition(sequence, sequence + 2, rank, offset, op.comp);
// allowed to read?
// together
// *(offset[ 0 ] - 1) == *offset[ 1 ]
if (offset[ 0 ] != begin1 && offset[ 1 ] != end2
&& !op.comp(*(offset[ 0 ] - 1), *offset[ 1 ])
&& !op.comp(*offset[ 1 ], *(offset[ 0 ] - 1)))
{
// Avoid split between globally equal elements: move one to
// front in first sequence.
--offset[ 0 ];
}
iterator_pair block_end = block_begins[ iam + 1 ] =
iterator_pair(offset[ 0 ], offset[ 1 ]);
// Make sure all threads have their block_begin result written out.
# pragma omp barrier
iterator_pair block_begin = block_begins[ iam ];
// Begin working for the first block, while the others except
// the last start to count.
if (iam == 0)
{
// The first thread can copy already.
lengths[ iam ] = op.invoke(block_begin.first, block_end.first,
block_begin.second, block_end.second,
result)
- result;
}
else
{
lengths[ iam ] = op.count(block_begin.first, block_end.first,
block_begin.second, block_end.second);
}
// Make sure everyone wrote their lengths.
# pragma omp barrier
OutputIterator r = result;
if (iam == 0)
{
// Do the last block.
for (int i = 0; i < num_threads; ++i)
r += lengths[i];
block_begin = block_begins[num_threads];
// Return the result iterator of the last block.
return_value = op.invoke(
block_begin.first, end1, block_begin.second, end2, r);
}
else
{
for (int i = 0; i < iam; ++i)
r += lengths[ i ];
// Reset begins for copy pass.
op.invoke(block_begin.first, block_end.first,
block_begin.second, block_end.second, r);
}
}
return return_value;
}
template<typename InputIterator,
typename OutputIterator,
typename Comparator>
inline OutputIterator
parallel_set_union(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator result, Comparator comp)
{
return parallel_set_operation(begin1, end1, begin2, end2, result,
union_func< InputIterator, OutputIterator, Comparator>(comp));
}
template<typename InputIterator,
typename OutputIterator,
typename Comparator>
inline OutputIterator
parallel_set_intersection(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator result, Comparator comp)
{
return parallel_set_operation(begin1, end1, begin2, end2, result,
intersection_func<InputIterator, OutputIterator, Comparator>(comp));
}
template<typename InputIterator,
typename OutputIterator,
typename Comparator>
inline OutputIterator
parallel_set_difference(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator result, Comparator comp)
{
return parallel_set_operation(begin1, end1, begin2, end2, result,
difference_func<InputIterator, OutputIterator, Comparator>(comp));
}
template<typename InputIterator,
typename OutputIterator,
typename Comparator>
inline OutputIterator
parallel_set_symmetric_difference(InputIterator begin1, InputIterator end1,
InputIterator begin2, InputIterator end2,
OutputIterator result, Comparator comp)
{
return parallel_set_operation(begin1, end1, begin2, end2, result,
symmetric_difference_func<InputIterator, OutputIterator, Comparator>
(comp));
}
}
#endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */