cfglayout.c (fixup_reorder_chain): Accept conditional jumps without a fallthrough...

[thirdparty/gcc.git] / libstdc++-v3 / include / parallel / set_operations.h

// -*- 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 _IIter, typename _OutputIterator>
  _OutputIterator
  copy_tail(std::pair<_IIter, _IIter> __b,
            std::pair<_IIter, _IIter> __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 _IIter,
	 typename _OutputIterator,
	 typename _Compare>
  struct symmetric_difference_func
  {
    typedef std::iterator_traits<_IIter> _TraitsType;
    typedef typename _TraitsType::difference_type _DifferenceType;
    typedef typename std::pair<_IIter, _IIter> _IteratorPair;

    symmetric_difference_func(_Compare __comp) : _M_comp(__comp) {}

    _Compare _M_comp;

    _OutputIterator
    _M_invoke(_IIter __a, _IIter __b,
	   _IIter __c, _IIter d,
	   _OutputIterator __r) const
    {
      while (__a != __b && __c != d)
        {
          if (_M_comp(*__a, *__c))
            {
              *__r = *__a;
              ++__a;
              ++__r;
            }
          else if (_M_comp(*__c, *__a))
            {
              *__r = *__c;
              ++__c;
              ++__r;
            }
          else
            {
              ++__a;
              ++__c;
            }
        }
      return std::copy(__c, d, std::copy(__a, __b, __r));
    }

    _DifferenceType
    __count(_IIter __a, _IIter __b,
	  _IIter __c, _IIter d) const
    {
      _DifferenceType __counter = 0;

      while (__a != __b && __c != d)
        {
          if (_M_comp(*__a, *__c))
            {
              ++__a;
              ++__counter;
            }
          else if (_M_comp(*__c, *__a))
            {
              ++__c;
              ++__counter;
            }
          else
            {
              ++__a;
              ++__c;
            }
        }

      return __counter + (__b - __a) + (d - __c);
    }

    _OutputIterator
    __first_empty(_IIter __c, _IIter d, _OutputIterator __out) const
    { return std::copy(__c, d, __out); }

    _OutputIterator
    __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
    { return std::copy(__a, __b, __out); }
  };


template<typename _IIter,
	 typename _OutputIterator,
	 typename _Compare>
  struct __difference_func
  {
    typedef std::iterator_traits<_IIter> _TraitsType;
    typedef typename _TraitsType::difference_type _DifferenceType;
    typedef typename std::pair<_IIter, _IIter> _IteratorPair;

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

    _Compare _M_comp;

    _OutputIterator
    _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter d,
          _OutputIterator __r) const
    {
      while (__a != __b && __c != d)
        {
          if (_M_comp(*__a, *__c))
            {
              *__r = *__a;
              ++__a;
              ++__r;
            }
          else if (_M_comp(*__c, *__a))
            { ++__c; }
          else
            {
              ++__a;
              ++__c;
            }
        }
      return std::copy(__a, __b, __r);
    }

    _DifferenceType
    __count(_IIter __a, _IIter __b,
	  _IIter __c, _IIter d) const
    {
      _DifferenceType __counter = 0;

      while (__a != __b && __c != d)
        {
          if (_M_comp(*__a, *__c))
            {
              ++__a;
              ++__counter;
            }
          else if (_M_comp(*__c, *__a))
            { ++__c; }
          else
            { ++__a; ++__c; }
        }

      return __counter + (__b - __a);
    }

    inline _OutputIterator
    __first_empty(_IIter __c, _IIter d, _OutputIterator __out) const
    { return __out; }

    inline _OutputIterator
    __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
    { return std::copy(__a, __b, __out); }
  };


template<typename _IIter,
	 typename _OutputIterator,
	 typename _Compare>
  struct __intersection_func
  {
    typedef std::iterator_traits<_IIter> _TraitsType;
    typedef typename _TraitsType::difference_type _DifferenceType;
    typedef typename std::pair<_IIter, _IIter> _IteratorPair;

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

    _Compare _M_comp;

    _OutputIterator
    _M_invoke(_IIter __a, _IIter __b, _IIter __c, _IIter d,
          _OutputIterator __r) const
    {
      while (__a != __b && __c != d)
        {
          if (_M_comp(*__a, *__c))
            { ++__a; }
          else if (_M_comp(*__c, *__a))
            { ++__c; }
          else
            {
              *__r = *__a;
              ++__a;
              ++__c;
              ++__r;
            }
        }

      return __r;
    }

    _DifferenceType
    __count(_IIter __a, _IIter __b,
	  _IIter __c, _IIter d) const
    {
      _DifferenceType __counter = 0;

      while (__a != __b && __c != d)
        {
          if (_M_comp(*__a, *__c))
            { ++__a; }
          else if (_M_comp(*__c, *__a))
            { ++__c; }
          else
            {
              ++__a;
              ++__c;
              ++__counter;
            }
        }

      return __counter;
    }

    inline _OutputIterator
    __first_empty(_IIter __c, _IIter d, _OutputIterator __out) const
    { return __out; }

    inline _OutputIterator
    __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
    { return __out; }
  };

template<class _IIter, class _OutputIterator, class _Compare>
  struct __union_func
  {
    typedef typename std::iterator_traits<_IIter>::difference_type
    _DifferenceType;

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

    _Compare _M_comp;

    _OutputIterator
    _M_invoke(_IIter __a, const _IIter __b, _IIter __c,
          const _IIter d, _OutputIterator __r) const
    {
      while (__a != __b && __c != d)
        {
          if (_M_comp(*__a, *__c))
            {
              *__r = *__a;
              ++__a;
            }
          else if (_M_comp(*__c, *__a))
            {
              *__r = *__c;
              ++__c;
            }
          else
            {
              *__r = *__a;
              ++__a;
              ++__c;
            }
          ++__r;
        }
      return std::copy(__c, d, std::copy(__a, __b, __r));
    }

    _DifferenceType
    __count(_IIter __a, _IIter __b,
	  _IIter __c, _IIter d) const
    {
      _DifferenceType __counter = 0;

      while (__a != __b && __c != d)
        {
          if (_M_comp(*__a, *__c))
            { ++__a; }
          else if (_M_comp(*__c, *__a))
            { ++__c; }
          else
            {
              ++__a;
              ++__c;
            }
          ++__counter;
        }

      __counter += (__b - __a);
      __counter += (d - __c);
      return __counter;
    }

    inline _OutputIterator
    __first_empty(_IIter __c, _IIter d, _OutputIterator __out) const
    { return std::copy(__c, d, __out); }

    inline _OutputIterator
    __second_empty(_IIter __a, _IIter __b, _OutputIterator __out) const
    { return std::copy(__a, __b, __out); }
  };

template<typename _IIter,
	 typename _OutputIterator,
	 typename Operation>
  _OutputIterator
  __parallel_set_operation(_IIter __begin1, _IIter __end1,
                         _IIter __begin2, _IIter __end2,
                         _OutputIterator __result, Operation __op)
  {
    _GLIBCXX_CALL((__end1 - __begin1) + (__end2 - __begin2))

    typedef std::iterator_traits<_IIter> _TraitsType;
    typedef typename _TraitsType::difference_type _DifferenceType;
    typedef typename std::pair<_IIter, _IIter> _IteratorPair;

    if (__begin1 == __end1)
      return __op.__first_empty(__begin2, __end2, __result);

    if (__begin2 == __end2)
      return __op.__second_empty(__begin1, __end1, __result);

    const _DifferenceType size = (__end1 - __begin1) + (__end2 - __begin2);

    const _IteratorPair __sequence[ 2 ] =
        { std::make_pair(__begin1, __end1), std::make_pair(__begin2, __end2) } ;
    _OutputIterator return_value = __result;
    _DifferenceType *__borders;
    _IteratorPair *__block_begins;
    _DifferenceType* __lengths;

    _ThreadIndex __num_threads =
        std::min<_DifferenceType>(__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 _DifferenceType[__num_threads + 2];
            equally_split(size, __num_threads + 1, __borders);
            __block_begins = new _IteratorPair[__num_threads + 1];
            // Very __start.
            __block_begins[0] = std::make_pair(__begin1, __begin2);
            __lengths = new _DifferenceType[__num_threads];
          } //single

        _ThreadIndex __iam = omp_get_thread_num();

        // _Result from multiseq_partition.
        _IIter __offset[2];
        const _DifferenceType __rank = __borders[__iam + 1];

        multiseq_partition(__sequence, __sequence + 2, __rank, __offset, __op._M_comp);

        // allowed to read?
        // together
        // *(__offset[ 0 ] - 1) == *__offset[ 1 ]
        if (__offset[ 0 ] != __begin1 && __offset[ 1 ] != __end2
            && !__op._M_comp(*(__offset[ 0 ] - 1), *__offset[ 1 ])
            && !__op._M_comp(*__offset[ 1 ], *(__offset[ 0 ] - 1)))
          {
            // Avoid split between globally equal elements: move one to
            // front in first sequence.
            --__offset[ 0 ];
          }

        _IteratorPair block_end = __block_begins[ __iam + 1 ] =
            _IteratorPair(__offset[ 0 ], __offset[ 1 ]);

        // Make sure all threads have their block_begin result written out.
#       pragma omp barrier

        _IteratorPair __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._M_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._M_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._M_invoke(__block_begin.first, block_end.first,
                  __block_begin.second, block_end.second, __r);
          }
      }
    return return_value;
  }


template<typename _IIter,
	 typename _OutputIterator,
	 typename _Compare>
  inline _OutputIterator
  __parallel_set_union(_IIter __begin1, _IIter __end1,
                     _IIter __begin2, _IIter __end2,
                     _OutputIterator __result, _Compare _M_comp)
  {
    return __parallel_set_operation(__begin1, __end1, __begin2, __end2, __result,
        __union_func< _IIter, _OutputIterator, _Compare>(_M_comp));
  }

template<typename _IIter,
	 typename _OutputIterator,
	 typename _Compare>
  inline _OutputIterator
  __parallel_set_intersection(_IIter __begin1, _IIter __end1,
                            _IIter __begin2, _IIter __end2,
                            _OutputIterator __result, _Compare _M_comp)
  {
    return __parallel_set_operation(__begin1, __end1, __begin2, __end2, __result,
        __intersection_func<_IIter, _OutputIterator, _Compare>(_M_comp));
  }

template<typename _IIter,
	 typename _OutputIterator,
	 typename _Compare>
  inline _OutputIterator
  __parallel_set_difference(_IIter __begin1, _IIter __end1,
                          _IIter __begin2, _IIter __end2,
                          _OutputIterator __result, _Compare _M_comp)
  {
    return __parallel_set_operation(__begin1, __end1, __begin2, __end2, __result,
        __difference_func<_IIter, _OutputIterator, _Compare>(_M_comp));
  }

template<typename _IIter,
	 typename _OutputIterator,
	 typename _Compare>
  inline _OutputIterator
  __parallel_set_symmetric_difference(_IIter __begin1, _IIter __end1,
                                    _IIter __begin2, _IIter __end2,
                                    _OutputIterator __result, _Compare _M_comp)
  {
    return __parallel_set_operation(__begin1, __end1, __begin2, __end2, __result,
        symmetric_difference_func<_IIter, _OutputIterator, _Compare>
            (_M_comp));
  }

}

#endif /* _GLIBCXX_PARALLEL_SET_OPERATIONS_H */