Viewing file: set_operations.h (14.13 KB) -rw-r--r-- Select action/file-type: (+) | (+) | (+) | Code (+) | Session (+) | (+) | SDB (+) | (+) | (+) | (+) | (+) | (+) |
// -*- 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 */
|