head	1.1;
branch	1.1.1;
access;
symbols
	netbsd-11-0-RC5:1.1.1.3
	netbsd-11-0-RC4:1.1.1.3
	netbsd-11-0-RC3:1.1.1.3
	netbsd-11-0-RC2:1.1.1.3
	netbsd-11-0-RC1:1.1.1.3
	gcc-14-3-0:1.1.1.4
	perseant-exfatfs-base-20250801:1.1.1.3
	netbsd-11:1.1.1.3.0.4
	netbsd-11-base:1.1.1.3
	gcc-12-5-0:1.1.1.3
	netbsd-10-1-RELEASE:1.1.1.2
	perseant-exfatfs-base-20240630:1.1.1.3
	gcc-12-4-0:1.1.1.3
	perseant-exfatfs:1.1.1.3.0.2
	perseant-exfatfs-base:1.1.1.3
	netbsd-10-0-RELEASE:1.1.1.2
	netbsd-10-0-RC6:1.1.1.2
	netbsd-10-0-RC5:1.1.1.2
	netbsd-10-0-RC4:1.1.1.2
	netbsd-10-0-RC3:1.1.1.2
	netbsd-10-0-RC2:1.1.1.2
	netbsd-10-0-RC1:1.1.1.2
	gcc-12-3-0:1.1.1.3
	gcc-10-5-0:1.1.1.2
	netbsd-10:1.1.1.2.0.6
	netbsd-10-base:1.1.1.2
	gcc-10-4-0:1.1.1.2
	cjep_sun2x-base1:1.1.1.2
	cjep_sun2x:1.1.1.2.0.4
	cjep_sun2x-base:1.1.1.2
	cjep_staticlib_x-base1:1.1.1.2
	cjep_staticlib_x:1.1.1.2.0.2
	cjep_staticlib_x-base:1.1.1.2
	gcc-10-3-0:1.1.1.2
	gcc-9-3-0:1.1.1.1
	FSF:1.1.1;
locks; strict;
comment	@ * @;


1.1
date	2020.09.05.07.52.10;	author mrg;	state Exp;
branches
	1.1.1.1;
next	;
commitid	ZRYA7IOuwfMjAPmC;

1.1.1.1
date	2020.09.05.07.52.10;	author mrg;	state Exp;
branches;
next	1.1.1.2;
commitid	ZRYA7IOuwfMjAPmC;

1.1.1.2
date	2021.04.10.22.10.04;	author mrg;	state Exp;
branches;
next	1.1.1.3;
commitid	eC4g0MRpqTvEkNOC;

1.1.1.3
date	2023.07.30.05.21.20;	author mrg;	state Exp;
branches;
next	1.1.1.4;
commitid	tk6nV4mbc9nVEMyE;

1.1.1.4
date	2025.09.13.23.45.48;	author mrg;	state Exp;
branches;
next	;
commitid	KwhwN4krNWa6XBaG;


desc
@@


1.1
log
@Initial revision
@
text
@// -*- C++ -*-
//===-- parallel_backend_tbb.h --------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#ifndef __PSTL_parallel_backend_tbb_H
#define __PSTL_parallel_backend_tbb_H

#include <algorithm>
#include <type_traits>

#include "parallel_backend_utils.h"

// Bring in minimal required subset of Intel TBB
#include <tbb/blocked_range.h>
#include <tbb/parallel_for.h>
#include <tbb/parallel_reduce.h>
#include <tbb/parallel_scan.h>
#include <tbb/parallel_invoke.h>
#include <tbb/task_arena.h>
#include <tbb/tbb_allocator.h>

#if TBB_INTERFACE_VERSION < 10000
#error Intel(R) Threading Building Blocks 2018 is required; older versions are not supported.
#endif

namespace __pstl
{
namespace __par_backend
{

//! Raw memory buffer with automatic freeing and no exceptions.
/** Some of our algorithms need to start with raw memory buffer,
not an initialize array, because initialization/destruction
would make the span be at least O(N). */
// tbb::allocator can improve performance in some cases.
template <typename _Tp>
class __buffer
{
    tbb::tbb_allocator<_Tp> _M_allocator;
    _Tp* _M_ptr;
    const std::size_t _M_buf_size;
    __buffer(const __buffer&) = delete;
    void
    operator=(const __buffer&) = delete;

  public:
    //! Try to obtain buffer of given size to store objects of _Tp type
    __buffer(std::size_t n) : _M_allocator(), _M_ptr(_M_allocator.allocate(n)), _M_buf_size(n) {}
    //! True if buffer was successfully obtained, zero otherwise.
    operator bool() const { return _M_ptr != NULL; }
    //! Return pointer to buffer, or  NULL if buffer could not be obtained.
    _Tp*
    get() const
    {
        return _M_ptr;
    }
    //! Destroy buffer
    ~__buffer() { _M_allocator.deallocate(_M_ptr, _M_buf_size); }
};

// Wrapper for tbb::task
inline void
__cancel_execution()
{
    tbb::task::self().group()->cancel_group_execution();
}

//------------------------------------------------------------------------
// parallel_for
//------------------------------------------------------------------------

template <class _Index, class _RealBody>
class __parallel_for_body
{
  public:
    __parallel_for_body(const _RealBody& __body) : _M_body(__body) {}
    __parallel_for_body(const __parallel_for_body& __body) : _M_body(__body._M_body) {}
    void
    operator()(const tbb::blocked_range<_Index>& __range) const
    {
        _M_body(__range.begin(), __range.end());
    }

  private:
    _RealBody _M_body;
};

//! Evaluation of brick f[i,j) for each subrange [i,j) of [first,last)
// wrapper over tbb::parallel_for
template <class _ExecutionPolicy, class _Index, class _Fp>
void
__parallel_for(_ExecutionPolicy&&, _Index __first, _Index __last, _Fp __f)
{
    tbb::this_task_arena::isolate([=]() {
        tbb::parallel_for(tbb::blocked_range<_Index>(__first, __last), __parallel_for_body<_Index, _Fp>(__f));
    });
}

//! Evaluation of brick f[i,j) for each subrange [i,j) of [first,last)
// wrapper over tbb::parallel_reduce
template <class _ExecutionPolicy, class _Value, class _Index, typename _RealBody, typename _Reduction>
_Value
__parallel_reduce(_ExecutionPolicy&&, _Index __first, _Index __last, const _Value& __identity,
                  const _RealBody& __real_body, const _Reduction& __reduction)
{
    return tbb::this_task_arena::isolate([__first, __last, &__identity, &__real_body, &__reduction]() -> _Value {
        return tbb::parallel_reduce(
            tbb::blocked_range<_Index>(__first, __last), __identity,
            [__real_body](const tbb::blocked_range<_Index>& __r, const _Value& __value) -> _Value {
                return __real_body(__r.begin(), __r.end(), __value);
            },
            __reduction);
    });
}

//------------------------------------------------------------------------
// parallel_transform_reduce
//
// Notation:
//      r(i,j,init) returns reduction of init with reduction over [i,j)
//      u(i) returns f(i,i+1,identity) for a hypothetical left identity element of r
//      c(x,y) combines values x and y that were the result of r or u
//------------------------------------------------------------------------

template <class _Index, class _Up, class _Tp, class _Cp, class _Rp>
struct __par_trans_red_body
{
    alignas(_Tp) char _M_sum_storage[sizeof(_Tp)]; // Holds generalized non-commutative sum when has_sum==true
    _Rp _M_brick_reduce;                           // Most likely to have non-empty layout
    _Up _M_u;
    _Cp _M_combine;
    bool _M_has_sum; // Put last to minimize size of class
    _Tp&
    sum()
    {
        __PSTL_ASSERT_MSG(_M_has_sum, "sum expected");
        return *(_Tp*)_M_sum_storage;
    }
    __par_trans_red_body(_Up __u, _Tp __init, _Cp __c, _Rp __r)
        : _M_brick_reduce(__r), _M_u(__u), _M_combine(__c), _M_has_sum(true)
    {
        new (_M_sum_storage) _Tp(__init);
    }

    __par_trans_red_body(__par_trans_red_body& __left, tbb::split)
        : _M_brick_reduce(__left._M_brick_reduce), _M_u(__left._M_u), _M_combine(__left._M_combine), _M_has_sum(false)
    {
    }

    ~__par_trans_red_body()
    {
        // 17.6.5.12 tells us to not worry about catching exceptions from destructors.
        if (_M_has_sum)
            sum().~_Tp();
    }

    void
    join(__par_trans_red_body& __rhs)
    {
        sum() = _M_combine(sum(), __rhs.sum());
    }

    void
    operator()(const tbb::blocked_range<_Index>& __range)
    {
        _Index __i = __range.begin();
        _Index __j = __range.end();
        if (!_M_has_sum)
        {
            __PSTL_ASSERT_MSG(__range.size() > 1, "there should be at least 2 elements");
            new (&_M_sum_storage)
                _Tp(_M_combine(_M_u(__i), _M_u(__i + 1))); // The condition i+1 < j is provided by the grain size of 3
            _M_has_sum = true;
            std::advance(__i, 2);
            if (__i == __j)
                return;
        }
        sum() = _M_brick_reduce(__i, __j, sum());
    }
};

template <class _ExecutionPolicy, class _Index, class _Up, class _Tp, class _Cp, class _Rp>
_Tp
__parallel_transform_reduce(_ExecutionPolicy&&, _Index __first, _Index __last, _Up __u, _Tp __init, _Cp __combine,
                            _Rp __brick_reduce)
{
    __par_backend::__par_trans_red_body<_Index, _Up, _Tp, _Cp, _Rp> __body(__u, __init, __combine, __brick_reduce);
    // The grain size of 3 is used in order to provide mininum 2 elements for each body
    tbb::this_task_arena::isolate(
        [__first, __last, &__body]() { tbb::parallel_reduce(tbb::blocked_range<_Index>(__first, __last, 3), __body); });
    return __body.sum();
}

//------------------------------------------------------------------------
// parallel_scan
//------------------------------------------------------------------------

template <class _Index, class _Up, class _Tp, class _Cp, class _Rp, class _Sp>
class __trans_scan_body
{
    alignas(_Tp) char _M_sum_storage[sizeof(_Tp)]; // Holds generalized non-commutative sum when has_sum==true
    _Rp _M_brick_reduce;                           // Most likely to have non-empty layout
    _Up _M_u;
    _Cp _M_combine;
    _Sp _M_scan;
    bool _M_has_sum; // Put last to minimize size of class
  public:
    __trans_scan_body(_Up __u, _Tp __init, _Cp __combine, _Rp __reduce, _Sp __scan)
        : _M_brick_reduce(__reduce), _M_u(__u), _M_combine(__combine), _M_scan(__scan), _M_has_sum(true)
    {
        new (_M_sum_storage) _Tp(__init);
    }

    __trans_scan_body(__trans_scan_body& __b, tbb::split)
        : _M_brick_reduce(__b._M_brick_reduce), _M_u(__b._M_u), _M_combine(__b._M_combine), _M_scan(__b._M_scan),
          _M_has_sum(false)
    {
    }

    ~__trans_scan_body()
    {
        // 17.6.5.12 tells us to not worry about catching exceptions from destructors.
        if (_M_has_sum)
            sum().~_Tp();
    }

    _Tp&
    sum() const
    {
        __PSTL_ASSERT_MSG(_M_has_sum, "sum expected");
        return *const_cast<_Tp*>(reinterpret_cast<_Tp const*>(_M_sum_storage));
    }

    void
    operator()(const tbb::blocked_range<_Index>& __range, tbb::pre_scan_tag)
    {
        _Index __i = __range.begin();
        _Index __j = __range.end();
        if (!_M_has_sum)
        {
            new (&_M_sum_storage) _Tp(_M_u(__i));
            _M_has_sum = true;
            ++__i;
            if (__i == __j)
                return;
        }
        sum() = _M_brick_reduce(__i, __j, sum());
    }

    void
    operator()(const tbb::blocked_range<_Index>& __range, tbb::final_scan_tag)
    {
        sum() = _M_scan(__range.begin(), __range.end(), sum());
    }

    void
    reverse_join(__trans_scan_body& __a)
    {
        if (_M_has_sum)
        {
            sum() = _M_combine(__a.sum(), sum());
        }
        else
        {
            new (&_M_sum_storage) _Tp(__a.sum());
            _M_has_sum = true;
        }
    }

    void
    assign(__trans_scan_body& __b)
    {
        sum() = __b.sum();
    }
};

template <typename _Index>
_Index
__split(_Index __m)
{
    _Index __k = 1;
    while (2 * __k < __m)
        __k *= 2;
    return __k;
}

//------------------------------------------------------------------------
// __parallel_strict_scan
//------------------------------------------------------------------------

template <typename _Index, typename _Tp, typename _Rp, typename _Cp>
void
__upsweep(_Index __i, _Index __m, _Index __tilesize, _Tp* __r, _Index __lastsize, _Rp __reduce, _Cp __combine)
{
    if (__m == 1)
        __r[0] = __reduce(__i * __tilesize, __lastsize);
    else
    {
        _Index __k = __split(__m);
        tbb::parallel_invoke(
	    [=] { __par_backend::__upsweep(__i, __k, __tilesize, __r, __tilesize, __reduce, __combine); },
            [=] { __par_backend::__upsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize, __reduce, __combine); });
        if (__m == 2 * __k)
            __r[__m - 1] = __combine(__r[__k - 1], __r[__m - 1]);
    }
}

template <typename _Index, typename _Tp, typename _Cp, typename _Sp>
void
__downsweep(_Index __i, _Index __m, _Index __tilesize, _Tp* __r, _Index __lastsize, _Tp __initial, _Cp __combine,
            _Sp __scan)
{
    if (__m == 1)
        __scan(__i * __tilesize, __lastsize, __initial);
    else
    {
        const _Index __k = __split(__m);
        tbb::parallel_invoke([=] { __par_backend::__downsweep(__i, __k, __tilesize, __r, __tilesize, __initial, __combine, __scan); },
                             // Assumes that __combine never throws.
                             //TODO: Consider adding a requirement for user functors to be constant.
                             [=, &__combine] {
                                 __par_backend::__downsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize,
                                             __combine(__initial, __r[__k - 1]), __combine, __scan);
                             });
    }
}

// Adapted from Intel(R) Cilk(TM) version from cilkpub.
// Let i:len denote a counted interval of length n starting at i.  s denotes a generalized-sum value.
// Expected actions of the functors are:
//     reduce(i,len) -> s  -- return reduction value of i:len.
//     combine(s1,s2) -> s -- return merged sum
//     apex(s) -- do any processing necessary between reduce and scan.
//     scan(i,len,initial) -- perform scan over i:len starting with initial.
// The initial range 0:n is partitioned into consecutive subranges.
// reduce and scan are each called exactly once per subrange.
// Thus callers can rely upon side effects in reduce.
// combine must not throw an exception.
// apex is called exactly once, after all calls to reduce and before all calls to scan.
// For example, it's useful for allocating a __buffer used by scan but whose size is the sum of all reduction values.
// T must have a trivial constructor and destructor.
template <class _ExecutionPolicy, typename _Index, typename _Tp, typename _Rp, typename _Cp, typename _Sp, typename _Ap>
void
__parallel_strict_scan(_ExecutionPolicy&&, _Index __n, _Tp __initial, _Rp __reduce, _Cp __combine, _Sp __scan,
                       _Ap __apex)
{
    tbb::this_task_arena::isolate([=, &__combine]() {
        if (__n > 1)
        {
            _Index __p = tbb::this_task_arena::max_concurrency();
            const _Index __slack = 4;
            _Index __tilesize = (__n - 1) / (__slack * __p) + 1;
            _Index __m = (__n - 1) / __tilesize;
            __buffer<_Tp> __buf(__m + 1);
            _Tp* __r = __buf.get();
            __par_backend::__upsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __reduce, __combine);

            // When __apex is a no-op and __combine has no side effects, a good optimizer
            // should be able to eliminate all code between here and __apex.
            // Alternatively, provide a default value for __apex that can be
            // recognized by metaprogramming that conditionlly executes the following.
            size_t __k = __m + 1;
            _Tp __t = __r[__k - 1];
            while ((__k &= __k - 1))
                __t = __combine(__r[__k - 1], __t);
            __apex(__combine(__initial, __t));
            __par_backend::__downsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __initial, __combine,
                        __scan);
            return;
        }
        // Fewer than 2 elements in sequence, or out of memory.  Handle has single block.
        _Tp __sum = __initial;
        if (__n)
            __sum = __combine(__sum, __reduce(_Index(0), __n));
        __apex(__sum);
        if (__n)
            __scan(_Index(0), __n, __initial);
    });
}

template <class _ExecutionPolicy, class _Index, class _Up, class _Tp, class _Cp, class _Rp, class _Sp>
_Tp
__parallel_transform_scan(_ExecutionPolicy&&, _Index __n, _Up __u, _Tp __init, _Cp __combine, _Rp __brick_reduce,
                          _Sp __scan)
{
    __trans_scan_body<_Index, _Up, _Tp, _Cp, _Rp, _Sp> __body(__u, __init, __combine, __brick_reduce, __scan);
    auto __range = tbb::blocked_range<_Index>(0, __n);
    tbb::this_task_arena::isolate([__range, &__body]() { tbb::parallel_scan(__range, __body); });
    return __body.sum();
}

//------------------------------------------------------------------------
// parallel_stable_sort
//------------------------------------------------------------------------

//------------------------------------------------------------------------
// stable_sort utilities
//
// These are used by parallel implementations but do not depend on them.
//------------------------------------------------------------------------

template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _RandomAccessIterator3,
          typename _Compare, typename _Cleanup, typename _LeafMerge>
class __merge_task : public tbb::task
{
    /*override*/ tbb::task*
    execute();
    _RandomAccessIterator1 _M_xs, _M_xe;
    _RandomAccessIterator2 _M_ys, _M_ye;
    _RandomAccessIterator3 _M_zs;
    _Compare _M_comp;
    _Cleanup _M_cleanup;
    _LeafMerge _M_leaf_merge;

  public:
    __merge_task(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys,
                 _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp, _Cleanup __cleanup,
                 _LeafMerge __leaf_merge)
        : _M_xs(__xs), _M_xe(__xe), _M_ys(__ys), _M_ye(__ye), _M_zs(__zs), _M_comp(__comp), _M_cleanup(__cleanup),
          _M_leaf_merge(__leaf_merge)
    {
    }
};

#define __PSTL_MERGE_CUT_OFF 2000

template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _RandomAccessIterator3,
          typename __M_Compare, typename _Cleanup, typename _LeafMerge>
tbb::task*
__merge_task<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3, __M_Compare, _Cleanup,
             _LeafMerge>::execute()
{
    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1;
    typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _DifferenceType2;
    typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType;
    const _SizeType __n = (_M_xe - _M_xs) + (_M_ye - _M_ys);
    const _SizeType __merge_cut_off = __PSTL_MERGE_CUT_OFF;
    if (__n <= __merge_cut_off)
    {
        _M_leaf_merge(_M_xs, _M_xe, _M_ys, _M_ye, _M_zs, _M_comp);

        //we clean the buffer one time on last step of the sort
        _M_cleanup(_M_xs, _M_xe);
        _M_cleanup(_M_ys, _M_ye);
        return nullptr;
    }
    else
    {
        _RandomAccessIterator1 __xm;
        _RandomAccessIterator2 __ym;
        if (_M_xe - _M_xs < _M_ye - _M_ys)
        {
            __ym = _M_ys + (_M_ye - _M_ys) / 2;
            __xm = std::upper_bound(_M_xs, _M_xe, *__ym, _M_comp);
        }
        else
        {
            __xm = _M_xs + (_M_xe - _M_xs) / 2;
            __ym = std::lower_bound(_M_ys, _M_ye, *__xm, _M_comp);
        }
        const _RandomAccessIterator3 __zm = _M_zs + ((__xm - _M_xs) + (__ym - _M_ys));
        tbb::task* __right = new (tbb::task::allocate_additional_child_of(*parent()))
            __merge_task(__xm, _M_xe, __ym, _M_ye, __zm, _M_comp, _M_cleanup, _M_leaf_merge);
        tbb::task::spawn(*__right);
        tbb::task::recycle_as_continuation();
        _M_xe = __xm;
        _M_ye = __ym;
    }
    return this;
}

template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _Compare, typename _LeafSort>
class __stable_sort_task : public tbb::task
{
  public:
    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1;
    typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _DifferenceType2;
    typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType;

  private:
    /*override*/ tbb::task*
    execute();
    _RandomAccessIterator1 _M_xs, _M_xe;
    _RandomAccessIterator2 _M_zs;
    _Compare _M_comp;
    _LeafSort _M_leaf_sort;
    int32_t _M_inplace;
    _SizeType _M_nsort;

  public:
    __stable_sort_task(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __zs,
                       int32_t __inplace, _Compare __comp, _LeafSort __leaf_sort, _SizeType __n)
        : _M_xs(__xs), _M_xe(__xe), _M_zs(__zs), _M_comp(__comp), _M_leaf_sort(__leaf_sort), _M_inplace(__inplace),
          _M_nsort(__n)
    {
    }
};

//! Binary operator that does nothing
struct __binary_no_op
{
    template <typename _T>
    void operator()(_T, _T)
    {
    }
};

#define __PSTL_STABLE_SORT_CUT_OFF 500

template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _Compare, typename _LeafSort>
tbb::task*
__stable_sort_task<_RandomAccessIterator1, _RandomAccessIterator2, _Compare, _LeafSort>::execute()
{
    const _SizeType __n = _M_xe - _M_xs;
    const _SizeType __nmerge = _M_nsort > 0 ? _M_nsort : __n;
    const _SizeType __sort_cut_off = __PSTL_STABLE_SORT_CUT_OFF;
    if (__n <= __sort_cut_off)
    {
        _M_leaf_sort(_M_xs, _M_xe, _M_comp);
        if (_M_inplace != 2)
            __par_backend::__init_buf(_M_xs, _M_xe, _M_zs, _M_inplace == 0);
        return NULL;
    }
    else
    {
        const _RandomAccessIterator1 __xm = _M_xs + __n / 2;
        const _RandomAccessIterator2 __zm = _M_zs + (__xm - _M_xs);
        const _RandomAccessIterator2 __ze = _M_zs + __n;
        task* __m;
        auto __move_values = [](_RandomAccessIterator2 __x, _RandomAccessIterator1 __z) { *__z = std::move(*__x); };
        auto __move_sequences = [](_RandomAccessIterator2 __first1, _RandomAccessIterator2 __last1,
                                   _RandomAccessIterator1 __first2) { return std::move(__first1, __last1, __first2); };
        if (_M_inplace == 2)
	    __m = new (tbb::task::allocate_continuation())
                __merge_task<_RandomAccessIterator2, _RandomAccessIterator2, _RandomAccessIterator1, _Compare,
                             __serial_destroy,
                             __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>>(
                    _M_zs, __zm, __zm, __ze, _M_xs, _M_comp, __serial_destroy(),
                    __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>(__nmerge, __move_values,
                                                                                             __move_sequences));
        else if (_M_inplace)
            __m = new (tbb::task::allocate_continuation())
                __merge_task<_RandomAccessIterator2, _RandomAccessIterator2, _RandomAccessIterator1, _Compare,
                             __par_backend::__binary_no_op, __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>>(
                    _M_zs, __zm, __zm, __ze, _M_xs, _M_comp, __par_backend::__binary_no_op(),
                    __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>(__nmerge, __move_values,
                                                                                             __move_sequences));
        else
        {
            auto __move_values = [](_RandomAccessIterator1 __x, _RandomAccessIterator2 __z) { *__z = std::move(*__x); };
            auto __move_sequences = [](_RandomAccessIterator1 __first1, _RandomAccessIterator1 __last1,
                                       _RandomAccessIterator2 __first2) {
                return std::move(__first1, __last1, __first2);
            };
            __m = new (tbb::task::allocate_continuation())
                __merge_task<_RandomAccessIterator1, _RandomAccessIterator1, _RandomAccessIterator2, _Compare,
                             __par_backend::__binary_no_op, __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>>(
                    _M_xs, __xm, __xm, _M_xe, _M_zs, _M_comp, __par_backend::__binary_no_op(),
                    __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>(__nmerge, __move_values,
                                                                                             __move_sequences));
        }
        __m->set_ref_count(2);
        task* __right = new (__m->allocate_child())
            __stable_sort_task(__xm, _M_xe, __zm, !_M_inplace, _M_comp, _M_leaf_sort, __nmerge);
	tbb::task::spawn(*__right);
	tbb::task::recycle_as_child_of(*__m);
        _M_xe = __xm;
        _M_inplace = !_M_inplace;
    }
    return this;
}

template <class _ExecutionPolicy, typename _RandomAccessIterator, typename _Compare, typename _LeafSort>
void
__parallel_stable_sort(_ExecutionPolicy&&, _RandomAccessIterator __xs, _RandomAccessIterator __xe, _Compare __comp,
                       _LeafSort __leaf_sort, std::size_t __nsort = 0)
{
    tbb::this_task_arena::isolate([=, &__nsort]() {
        //sorting based on task tree and parallel merge
        typedef typename std::iterator_traits<_RandomAccessIterator>::value_type _ValueType;
        typedef typename std::iterator_traits<_RandomAccessIterator>::difference_type _DifferenceType;
        const _DifferenceType __n = __xe - __xs;
        if (__nsort == 0)
            __nsort = __n;

        const _DifferenceType __sort_cut_off = __PSTL_STABLE_SORT_CUT_OFF;
        if (__n > __sort_cut_off)
        {
            __PSTL_ASSERT(__nsort > 0 && __nsort <= __n);
            __buffer<_ValueType> __buf(__n);
            using tbb::task;
            task::spawn_root_and_wait(*new (task::allocate_root())
                                          __stable_sort_task<_RandomAccessIterator, _ValueType*, _Compare, _LeafSort>(
                                              __xs, __xe, (_ValueType*)__buf.get(), 2, __comp, __leaf_sort, __nsort));
            return;
        }
        //serial sort
        __leaf_sort(__xs, __xe, __comp);
    });
}

//------------------------------------------------------------------------
// parallel_merge
//------------------------------------------------------------------------

template <class _ExecutionPolicy, typename _RandomAccessIterator1, typename _RandomAccessIterator2,
          typename _RandomAccessIterator3, typename _Compare, typename _LeafMerge>
void
__parallel_merge(_ExecutionPolicy&&, _RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe,
                 _RandomAccessIterator2 __ys, _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp,
                 _LeafMerge __leaf_merge)
{
    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1;
    typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _DifferenceType2;
    typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType;
    const _SizeType __n = (__xe - __xs) + (__ye - __ys);
    const _SizeType __merge_cut_off = __PSTL_MERGE_CUT_OFF;
    if (__n <= __merge_cut_off)
    {
        // Fall back on serial merge
        __leaf_merge(__xs, __xe, __ys, __ye, __zs, __comp);
    }
    else
    {
        tbb::this_task_arena::isolate([=]() {
            typedef __merge_task<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3, _Compare,
                                 __par_backend::__binary_no_op, _LeafMerge>
                _TaskType;
            tbb::task::spawn_root_and_wait(*new (tbb::task::allocate_root()) _TaskType(
                __xs, __xe, __ys, __ye, __zs, __comp, __par_backend::__binary_no_op(), __leaf_merge));
        });
    }
}

//------------------------------------------------------------------------
// parallel_invoke
//------------------------------------------------------------------------
template <class _ExecutionPolicy, typename _F1, typename _F2>
void
__parallel_invoke(_ExecutionPolicy&&, _F1&& __f1, _F2&& __f2)
{
    //TODO: a version of tbb::this_task_arena::isolate with variadic arguments pack should be added in the future
    tbb::this_task_arena::isolate([&]() { tbb::parallel_invoke(std::forward<_F1>(__f1), std::forward<_F2>(__f2)); });
}

} // namespace __par_backend
} // namespace __pstl

#endif /* __PSTL_parallel_backend_tbb_H */
@


1.1.1.1
log
@initial import of GCC 9.3.0.  changes include:

- live patching support
- shell completion help
- generally better diagnostic output (less verbose/more useful)
- diagnostics and optimisation choices can be emitted in json
- asan memory usage reduction
- many general, and specific to switch, inter-procedure,
  profile and link-time optimisations.  from the release notes:
  "Overall compile time of Firefox 66 and LibreOffice 6.2.3 on
  an 8-core machine was reduced by about 5% compared to GCC 8.3"
- OpenMP 5.0 support
- better spell-guesser
- partial experimental support for c2x and c++2a
- c++17 is no longer experimental
- arm AAPCS GCC 6-8 structure passing bug fixed, may cause
  incompatibility (restored compat with GCC 5 and earlier.)
- openrisc support
@
text
@@


1.1.1.2
log
@initial import of GCC 10.3.0.  main changes include:

caveats:
- ABI issue between c++14 and c++17 fixed
- profile mode is removed from libstdc++
- -fno-common is now the default

new features:
- new flags -fallocation-dce, -fprofile-partial-training,
  -fprofile-reproducible, -fprofile-prefix-path, and -fanalyzer
- many new compile and link time optimisations
- enhanced drive optimisations
- openacc 2.6 support
- openmp 5.0 features
- new warnings: -Wstring-compare and -Wzero-length-bounds
- extended warnings: -Warray-bounds, -Wformat-overflow,
  -Wrestrict, -Wreturn-local-addr, -Wstringop-overflow,
  -Warith-conversion, -Wmismatched-tags, and -Wredundant-tags
- some likely C2X features implemented
- more C++20 implemented
- many new arm & intel CPUs known

hundreds of reported bugs are fixed.  full list of changes
can be found at:

   https://gcc.gnu.org/gcc-10/changes.html
@
text
@d10 2
a11 2
#ifndef _PSTL_PARALLEL_BACKEND_TBB_H
#define _PSTL_PARALLEL_BACKEND_TBB_H
d28 1
a28 1
#    error Intel(R) Threading Building Blocks 2018 is required; older versions are not supported.
d141 1
a141 1
        _PSTL_ASSERT_MSG(_M_has_sum, "sum expected");
d175 1
a175 1
            _PSTL_ASSERT_MSG(__range.size() > 1, "there should be at least 2 elements");
d235 1
a235 1
        _PSTL_ASSERT_MSG(_M_has_sum, "sum expected");
d306 2
a307 4
            [=] { __par_backend::__upsweep(__i, __k, __tilesize, __r, __tilesize, __reduce, __combine); },
            [=] {
                __par_backend::__upsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize, __reduce, __combine);
            });
d323 7
a329 8
        tbb::parallel_invoke(
            [=] { __par_backend::__downsweep(__i, __k, __tilesize, __r, __tilesize, __initial, __combine, __scan); },
            // Assumes that __combine never throws.
            //TODO: Consider adding a requirement for user functors to be constant.
            [=, &__combine] {
                __par_backend::__downsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize,
                                           __combine(__initial, __r[__k - 1]), __combine, __scan);
            });
d361 1
a361 2
            __par_backend::__upsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __reduce,
                                     __combine);
d372 2
a373 2
            __par_backend::__downsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __initial,
                                       __combine, __scan);
d430 1
a430 1
#define _PSTL_MERGE_CUT_OFF 2000
d442 1
a442 1
    const _SizeType __merge_cut_off = _PSTL_MERGE_CUT_OFF;
d507 2
a508 2
    template <typename _Tp>
    void operator()(_Tp, _Tp)
d513 1
a513 1
#define _PSTL_STABLE_SORT_CUT_OFF 500
d521 1
a521 1
    const _SizeType __sort_cut_off = _PSTL_STABLE_SORT_CUT_OFF;
d539 1
a539 1
            __m = new (tbb::task::allocate_continuation())
d544 2
a545 2
                    __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>(
                        __nmerge, __move_values, __move_sequences));
d549 1
a549 2
                             __par_backend::__binary_no_op,
                             __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>>(
d551 2
a552 2
                    __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>(
                        __nmerge, __move_values, __move_sequences));
d562 1
a562 2
                             __par_backend::__binary_no_op,
                             __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>>(
d564 2
a565 2
                    __par_backend::__serial_move_merge<decltype(__move_values), decltype(__move_sequences)>(
                        __nmerge, __move_values, __move_sequences));
d570 2
a571 2
        tbb::task::spawn(*__right);
        tbb::task::recycle_as_child_of(*__m);
d591 1
a591 1
        const _DifferenceType __sort_cut_off = _PSTL_STABLE_SORT_CUT_OFF;
d594 1
a594 1
            _PSTL_ASSERT(__nsort > 0 && __nsort <= __n);
d622 1
a622 1
    const _SizeType __merge_cut_off = _PSTL_MERGE_CUT_OFF;
d654 1
a654 1
#endif /* _PSTL_PARALLEL_BACKEND_TBB_H */
@


1.1.1.3
log
@initial import of GCC 12.3.0.

major changes in GCC 11 included:

- The default mode for C++ is now -std=gnu++17 instead of -std=gnu++14.
- When building GCC itself, the host compiler must now support C++11,
  rather than C++98.
- Some short options of the gcov tool have been renamed: -i to -j and
  -j to -H.
- ThreadSanitizer improvements.
- Introduce Hardware-assisted AddressSanitizer support.
- For targets that produce DWARF debugging information GCC now defaults
  to DWARF version 5. This can produce up to 25% more compact debug
  information compared to earlier versions.
- Many optimisations.
- The existing malloc attribute has been extended so that it can be
  used to identify allocator/deallocator API pairs. A pair of new
  -Wmismatched-dealloc and -Wmismatched-new-delete warnings are added.
- Other new warnings:
  -Wsizeof-array-div, enabled by -Wall, warns about divisions of two
    sizeof operators when the first one is applied to an array and the
    divisor does not equal the size of the array element.
  -Wstringop-overread, enabled by default, warns about calls to string
    functions reading past the end of the arrays passed to them as
    arguments.
  -Wtsan, enabled by default, warns about unsupported features in
    ThreadSanitizer (currently std::atomic_thread_fence).
- Enchanced warnings:
  -Wfree-nonheap-object detects many more instances of calls to
    deallocation functions with pointers not returned from a dynamic
    memory allocation function.
  -Wmaybe-uninitialized diagnoses passing pointers or references to
    uninitialized memory to functions taking const-qualified arguments.
  -Wuninitialized detects reads from uninitialized dynamically
    allocated memory.
  -Warray-parameter warns about functions with inconsistent array forms.
  -Wvla-parameter warns about functions with inconsistent VLA forms.
- Several new features from the upcoming C2X revision of the ISO C
  standard are supported with -std=c2x and -std=gnu2x.
- Several C++20 features have been implemented.
- The C++ front end has experimental support for some of the upcoming
  C++23 draft.
- Several new C++ warnings.
- Enhanced Arm, AArch64, x86, and RISC-V CPU support.
- The implementation of how program state is tracked within
  -fanalyzer has been completely rewritten with many enhancements.

see https://gcc.gnu.org/gcc-11/changes.html for a full list.

major changes in GCC 12 include:

- An ABI incompatibility between C and C++ when passing or returning
  by value certain aggregates containing zero width bit-fields has
  been discovered on various targets. x86-64, ARM and AArch64
  will always ignore them (so there is a C ABI incompatibility
  between GCC 11 and earlier with GCC 12 or later), PowerPC64 ELFv2
  always take them into account (so there is a C++ ABI
  incompatibility, GCC 4.4 and earlier compatible with GCC 12 or
  later, incompatible with GCC 4.5 through GCC 11). RISC-V has
  changed the handling of these already starting with GCC 10. As
  the ABI requires, MIPS takes them into account handling function
  return values so there is a C++ ABI incompatibility with GCC 4.5
  through 11.
- STABS: Support for emitting the STABS debugging format is
  deprecated and will be removed in the next release. All ports now
  default to emit DWARF (version 2 or later) debugging info or are
  obsoleted.
- Vectorization is enabled at -O2 which is now equivalent to the
  original -O2 -ftree-vectorize -fvect-cost-model=very-cheap.
- GCC now supports the ShadowCallStack sanitizer.
- Support for __builtin_shufflevector compatible with the clang
  language extension was added.
- Support for attribute unavailable was added.
- Support for __builtin_dynamic_object_size compatible with the
  clang language extension was added.
- New warnings:
  -Wbidi-chars warns about potentially misleading UTF-8
    bidirectional control characters.
  -Warray-compare warns about comparisons between two operands of
    array type.
- Some new features from the upcoming C2X revision of the ISO C
  standard are supported with -std=c2x and -std=gnu2x.
- Several C++23 features have been implemented.
- Many C++ enhancements across warnings and -f options.

see https://gcc.gnu.org/gcc-12/changes.html for a full list.
@
text
@a25 1
#include <tbb/task.h>
d33 1
a33 1
namespace __tbb_backend
a69 1
#if TBB_INTERFACE_VERSION <= 12000
a70 3
#else
    tbb::task::current_context()->cancel_group_execution();
#endif
d192 1
a192 1
    __tbb_backend::__par_trans_red_body<_Index, _Up, _Tp, _Cp, _Rp> __body(__u, __init, __combine, __brick_reduce);
d306 1
a306 1
            [=] { __tbb_backend::__upsweep(__i, __k, __tilesize, __r, __tilesize, __reduce, __combine); },
d308 1
a308 1
                __tbb_backend::__upsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize, __reduce, __combine);
d326 1
a326 1
            [=] { __tbb_backend::__downsweep(__i, __k, __tilesize, __r, __tilesize, __initial, __combine, __scan); },
d330 1
a330 1
                __tbb_backend::__downsweep(__i + __k, __m - __k, __tilesize, __r + __k, __lastsize,
d364 1
a364 1
            __tbb_backend::__upsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __reduce,
d376 1
a376 1
            __tbb_backend::__downsweep(_Index(0), _Index(__m + 1), __tilesize, __r, __n - __m * __tilesize, __initial,
a409 1
#define _PSTL_MERGE_CUT_OFF 2000
d411 3
a413 7
template <typename _Func>
class __func_task;
template <typename _Func>
class __root_task;

#if TBB_INTERFACE_VERSION <= 12000
class __task : public tbb::task
d415 8
a422 59
  public:
    template <typename _Fn>
    __task*
    make_continuation(_Fn&& __f)
    {
        return new (allocate_continuation()) __func_task<typename std::decay<_Fn>::type>(std::forward<_Fn>(__f));
    }

    template <typename _Fn>
    __task*
    make_child_of(__task* parent, _Fn&& __f)
    {
        return new (parent->allocate_child()) __func_task<typename std::decay<_Fn>::type>(std::forward<_Fn>(__f));
    }

    template <typename _Fn>
    __task*
    make_additional_child_of(tbb::task* parent, _Fn&& __f)
    {
        return new (tbb::task::allocate_additional_child_of(*parent))
            __func_task<typename std::decay<_Fn>::type>(std::forward<_Fn>(__f));
    }

    inline void
    recycle_as_continuation()
    {
        tbb::task::recycle_as_continuation();
    }

    inline void
    recycle_as_child_of(__task* parent)
    {
        tbb::task::recycle_as_child_of(*parent);
    }

    inline void
    spawn(__task* __t)
    {
        tbb::task::spawn(*__t);
    }

    template <typename _Fn>
    static inline void
    spawn_root_and_wait(__root_task<_Fn>& __root)
    {
        tbb::task::spawn_root_and_wait(*__root._M_task);
    }
};

template <typename _Func>
class __func_task : public __task
{
    _Func _M_func;

    tbb::task*
    execute()
    {
        return _M_func(this);
    };
d425 5
a429 2
    template <typename _Fn>
    __func_task(_Fn&& __f) : _M_func{std::forward<_Fn>(__f)}
a431 6

    _Func&
    body()
    {
        return _M_func;
    }
d434 1
a434 4
template <typename _Func>
class __root_task
{
    tbb::task* _M_task;
d436 5
a440 210
  public:
    template <typename... Args>
    __root_task(Args&&... args)
        : _M_task{new (tbb::task::allocate_root()) __func_task<_Func>{_Func(std::forward<Args>(args)...)}}
    {
    }

    friend class __task;
    friend class __func_task<_Func>;
};

#else  // TBB_INTERFACE_VERSION <= 12000
class __task : public tbb::detail::d1::task
{
  protected:
    tbb::detail::d1::small_object_allocator _M_allocator{};
    tbb::detail::d1::execution_data* _M_execute_data{};
    __task* _M_parent{};
    std::atomic<int> _M_refcount{};
    bool _M_recycle{};

    template <typename _Fn>
    __task*
    allocate_func_task(_Fn&& __f)
    {
        _PSTL_ASSERT(_M_execute_data != nullptr);
        tbb::detail::d1::small_object_allocator __alloc{};
        auto __t =
            __alloc.new_object<__func_task<typename std::decay<_Fn>::type>>(*_M_execute_data, std::forward<_Fn>(__f));
        __t->_M_allocator = __alloc;
        return __t;
    }

  public:
    __task*
    parent()
    {
        return _M_parent;
    }

    void
    set_ref_count(int __n)
    {
        _M_refcount.store(__n, std::memory_order_release);
    }

    template <typename _Fn>
    __task*
    make_continuation(_Fn&& __f)
    {
        auto __t = allocate_func_task(std::forward<_Fn&&>(__f));
        __t->_M_parent = _M_parent;
        _M_parent = nullptr;
        return __t;
    }

    template <typename _Fn>
    __task*
    make_child_of(__task* __parent, _Fn&& __f)
    {
        auto __t = allocate_func_task(std::forward<_Fn&&>(__f));
        __t->_M_parent = __parent;
        return __t;
    }

    template <typename _Fn>
    __task*
    make_additional_child_of(__task* __parent, _Fn&& __f)
    {
        auto __t = make_child_of(__parent, std::forward<_Fn>(__f));
        _PSTL_ASSERT(__parent->_M_refcount.load(std::memory_order_relaxed) > 0);
        ++__parent->_M_refcount;
        return __t;
    }

    inline void
    recycle_as_continuation()
    {
        _M_recycle = true;
    }

    inline void
    recycle_as_child_of(__task* parent)
    {
        _M_recycle = true;
        _M_parent = parent;
    }

    inline void
    spawn(__task* __t)
    {
        _PSTL_ASSERT(_M_execute_data != nullptr);
        tbb::detail::d1::spawn(*__t, *_M_execute_data->context);
    }

    template <typename _Fn>
    static inline void
    spawn_root_and_wait(__root_task<_Fn>& __root)
    {
        tbb::detail::d1::execute_and_wait(*__root._M_func_task, __root._M_context, __root._M_wait_object,
                                          __root._M_context);
    }

    template <typename _Func>
    friend class __func_task;
};

template <typename _Func>
class __func_task : public __task
{
    _Func _M_func;

    __task*
    execute(tbb::detail::d1::execution_data& __ed) override
    {
        _M_execute_data = &__ed;
        _M_recycle = false;
        __task* __next = _M_func(this);
        return finalize(__next);
    };

    __task*
    cancel(tbb::detail::d1::execution_data& __ed) override
    {
        return finalize(nullptr);
    }

    __task*
    finalize(__task* __next)
    {
        bool __recycle = _M_recycle;
        _M_recycle = false;

        if (__recycle)
        {
            return __next;
        }

        auto __parent = _M_parent;
        auto __alloc = _M_allocator;
        auto __ed = _M_execute_data;

        this->~__func_task();

        _PSTL_ASSERT(__parent != nullptr);
        _PSTL_ASSERT(__parent->_M_refcount.load(std::memory_order_relaxed) > 0);
        if (--__parent->_M_refcount == 0)
        {
            _PSTL_ASSERT(__next == nullptr);
            __alloc.deallocate(this, *__ed);
            return __parent;
        }

        return __next;
    }

    friend class __root_task<_Func>;

  public:
    template <typename _Fn>
    __func_task(_Fn&& __f) : _M_func(std::forward<_Fn>(__f))
    {
    }

    _Func&
    body()
    {
        return _M_func;
    }
};

template <typename _Func>
class __root_task : public __task
{
    __task*
    execute(tbb::detail::d1::execution_data& __ed) override
    {
        _M_wait_object.release();
        return nullptr;
    };

    __task*
    cancel(tbb::detail::d1::execution_data& __ed) override
    {
        _M_wait_object.release();
        return nullptr;
    }

    __func_task<_Func>* _M_func_task{};
    tbb::detail::d1::wait_context _M_wait_object{0};
    tbb::task_group_context _M_context{};

  public:
    template <typename... Args>
    __root_task(Args&&... args) : _M_wait_object{1}
    {
        tbb::detail::d1::small_object_allocator __alloc{};
        _M_func_task = __alloc.new_object<__func_task<_Func>>(_Func(std::forward<Args>(args)...));
        _M_func_task->_M_allocator = __alloc;
        _M_func_task->_M_parent = this;
        _M_refcount.store(1, std::memory_order_relaxed);
    }

    friend class __task;
};
#endif // TBB_INTERFACE_VERSION <= 12000

template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _Compare, typename _Cleanup,
          typename _LeafMerge>
class __merge_func
d445 3
a447 21
    typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type _ValueType;

    _RandomAccessIterator1 _M_x_beg;
    _RandomAccessIterator2 _M_z_beg;

    _SizeType _M_xs, _M_xe;
    _SizeType _M_ys, _M_ye;
    _SizeType _M_zs;
    _Compare _M_comp;
    _LeafMerge _M_leaf_merge;
    _SizeType _M_nsort; //number of elements to be sorted for partial_sort alforithm

    static const _SizeType __merge_cut_off = _PSTL_MERGE_CUT_OFF;

    bool _root;   //means a task is merging root task
    bool _x_orig; //"true" means X(or left ) subrange is in the original container; false - in the buffer
    bool _y_orig; //"true" means Y(or right) subrange is in the original container; false - in the buffer
    bool _split; //"true" means a merge task is a split task for parallel merging, the execution logic differs

    bool
    is_partial() const
d449 1
a449 22
        return _M_nsort > 0;
    }

    struct __move_value
    {
        template <typename Iterator1, typename Iterator2>
        void
        operator()(Iterator1 __x, Iterator2 __z)
        {
            *__z = std::move(*__x);
        }
    };

    struct __move_value_construct
    {
        template <typename Iterator1, typename Iterator2>
        void
        operator()(Iterator1 __x, Iterator2 __z)
        {
            ::new (std::addressof(*__z)) _ValueType(std::move(*__x));
        }
    };
d451 3
a453 188
    struct __move_range
    {
        template <typename Iterator1, typename Iterator2>
        Iterator2
        operator()(Iterator1 __first1, Iterator1 __last1, Iterator2 __first2)
        {
            if (__last1 - __first1 < __merge_cut_off)
                return std::move(__first1, __last1, __first2);

            auto __n = __last1 - __first1;
            tbb::parallel_for(tbb::blocked_range<_SizeType>(0, __n, __merge_cut_off),
                              [__first1, __first2](const tbb::blocked_range<_SizeType>& __range) {
                                  std::move(__first1 + __range.begin(), __first1 + __range.end(),
                                            __first2 + __range.begin());
                              });
            return __first2 + __n;
        }
    };

    struct __move_range_construct
    {
        template <typename Iterator1, typename Iterator2>
        Iterator2
        operator()(Iterator1 __first1, Iterator1 __last1, Iterator2 __first2)
        {
            if (__last1 - __first1 < __merge_cut_off)
            {
                for (; __first1 != __last1; ++__first1, ++__first2)
                    __move_value_construct()(__first1, __first2);
                return __first2;
            }

            auto __n = __last1 - __first1;
            tbb::parallel_for(tbb::blocked_range<_SizeType>(0, __n, __merge_cut_off),
                              [__first1, __first2](const tbb::blocked_range<_SizeType>& __range) {
                                  for (auto i = __range.begin(); i != __range.end(); ++i)
                                      __move_value_construct()(__first1 + i, __first2 + i);
                              });
            return __first2 + __n;
        }
    };

    struct __cleanup_range
    {
        template <typename Iterator>
        void
        operator()(Iterator __first, Iterator __last)
        {
            if (__last - __first < __merge_cut_off)
                _Cleanup()(__first, __last);
            else
            {
                auto __n = __last - __first;
                tbb::parallel_for(tbb::blocked_range<_SizeType>(0, __n, __merge_cut_off),
                                  [__first](const tbb::blocked_range<_SizeType>& __range) {
                                      _Cleanup()(__first + __range.begin(), __first + __range.end());
                                  });
            }
        }
    };

  public:
    __merge_func(_SizeType __xs, _SizeType __xe, _SizeType __ys, _SizeType __ye, _SizeType __zs, _Compare __comp,
                 _Cleanup, _LeafMerge __leaf_merge, _SizeType __nsort, _RandomAccessIterator1 __x_beg,
                 _RandomAccessIterator2 __z_beg, bool __x_orig, bool __y_orig, bool __root)
        : _M_xs(__xs), _M_xe(__xe), _M_ys(__ys), _M_ye(__ye), _M_zs(__zs), _M_x_beg(__x_beg), _M_z_beg(__z_beg),
          _M_comp(__comp), _M_leaf_merge(__leaf_merge), _M_nsort(__nsort), _root(__root),
          _x_orig(__x_orig), _y_orig(__y_orig), _split(false)
    {
    }

    bool
    is_left(_SizeType __idx) const
    {
        return _M_xs == __idx;
    }

    template <typename IndexType>
    void
    set_odd(IndexType __idx, bool __on_off)
    {
        if (is_left(__idx))
            _x_orig = __on_off;
        else
            _y_orig = __on_off;
    }

    __task*
    operator()(__task* __self);

  private:
    __merge_func*
    parent_merge(__task* __self) const
    {
        return _root ? nullptr : &static_cast<__func_task<__merge_func>*>(__self->parent())->body();
    }
    bool
    x_less_y()
    {
        const auto __nx = (_M_xe - _M_xs);
        const auto __ny = (_M_ye - _M_ys);
        _PSTL_ASSERT(__nx > 0 && __ny > 0);

        _PSTL_ASSERT(_x_orig == _y_orig);
        _PSTL_ASSERT(!is_partial());

        if (_x_orig)
        {
            _PSTL_ASSERT(std::is_sorted(_M_x_beg + _M_xs, _M_x_beg + _M_xe, _M_comp));
            _PSTL_ASSERT(std::is_sorted(_M_x_beg + _M_ys, _M_x_beg + _M_ye, _M_comp));
            return !_M_comp(*(_M_x_beg + _M_ys), *(_M_x_beg + _M_xe - 1));
        }

        _PSTL_ASSERT(std::is_sorted(_M_z_beg + _M_xs, _M_z_beg + _M_xe, _M_comp));
        _PSTL_ASSERT(std::is_sorted(_M_z_beg + _M_ys, _M_z_beg + _M_ye, _M_comp));
        return !_M_comp(*(_M_z_beg + _M_zs + __nx), *(_M_z_beg + _M_zs + __nx - 1));
    }
    void
    move_x_range()
    {
        const auto __nx = (_M_xe - _M_xs);
        const auto __ny = (_M_ye - _M_ys);
        _PSTL_ASSERT(__nx > 0 && __ny > 0);

        if (_x_orig)
            __move_range_construct()(_M_x_beg + _M_xs, _M_x_beg + _M_xe, _M_z_beg + _M_zs);
        else
        {
            __move_range()(_M_z_beg + _M_zs, _M_z_beg + _M_zs + __nx, _M_x_beg + _M_xs);
            __cleanup_range()(_M_z_beg + _M_zs, _M_z_beg + _M_zs + __nx);
        }

        _x_orig = !_x_orig;
    }
    void
    move_y_range()
    {
        const auto __nx = (_M_xe - _M_xs);
        const auto __ny = (_M_ye - _M_ys);

        if (_y_orig)
            __move_range_construct()(_M_x_beg + _M_ys, _M_x_beg + _M_ye, _M_z_beg + _M_zs + __nx);
        else
        {
            __move_range()(_M_z_beg + _M_zs + __nx, _M_z_beg + _M_zs + __nx + __ny, _M_x_beg + _M_ys);
            __cleanup_range()(_M_z_beg + _M_zs + __nx, _M_z_beg + _M_zs + __nx + __ny);
        }

        _y_orig = !_y_orig;
    }
    __task*
    merge_ranges(__task* __self)
    {
        _PSTL_ASSERT(_x_orig == _y_orig); //two merged subrange must be lie into the same buffer

        const auto __nx = (_M_xe - _M_xs);
        const auto __ny = (_M_ye - _M_ys);
        const auto __n = __nx + __ny;

        // need to merge {x} and {y}
        if (__n > __merge_cut_off)
            return split_merging(__self);

        //merge to buffer
        if (_x_orig)
        {
            _M_leaf_merge(_M_x_beg + _M_xs, _M_x_beg + _M_xe, _M_x_beg + _M_ys, _M_x_beg + _M_ye, _M_z_beg + _M_zs,
                          _M_comp, __move_value_construct(), __move_value_construct(), __move_range_construct(),
                          __move_range_construct());
            _PSTL_ASSERT(parent_merge(__self)); //not root merging task
        }
        //merge to "origin"
        else
        {
            _PSTL_ASSERT(_x_orig == _y_orig);

            _PSTL_ASSERT(is_partial() || std::is_sorted(_M_z_beg + _M_xs, _M_z_beg + _M_xe, _M_comp));
            _PSTL_ASSERT(is_partial() || std::is_sorted(_M_z_beg + _M_ys, _M_z_beg + _M_ye, _M_comp));

            const auto __nx = (_M_xe - _M_xs);
            const auto __ny = (_M_ye - _M_ys);

            _M_leaf_merge(_M_z_beg + _M_xs, _M_z_beg + _M_xe, _M_z_beg + _M_ys, _M_z_beg + _M_ye, _M_x_beg + _M_zs,
                          _M_comp, __move_value(), __move_value(), __move_range(), __move_range());

            __cleanup_range()(_M_z_beg + _M_xs, _M_z_beg + _M_xe);
            __cleanup_range()(_M_z_beg + _M_ys, _M_z_beg + _M_ye);
        }
d456 1
a456 50

    __task*
    process_ranges(__task* __self)
    {
        _PSTL_ASSERT(_x_orig == _y_orig);
        _PSTL_ASSERT(!_split);

        auto p = parent_merge(__self);

        if (!p)
        { //root merging task

            //optimization, just for sort algorithm, //{x} <= {y}
            if (!is_partial() && x_less_y()) //we have a solution
            {
                if (!_x_orig)
                {                   //we have to move the solution to the origin
                    move_x_range(); //parallel moving
                    move_y_range(); //parallel moving
                }
                return nullptr;
            }
            //else: if we have data in the origin,
            //we have to move data to the buffer for final merging into the origin.
            if (_x_orig)
            {
                move_x_range(); //parallel moving
                move_y_range(); //parallel moving
            }
            // need to merge {x} and {y}.
            return merge_ranges(__self);
        }
        //else: not root merging task (parent_merge() == NULL)
        //optimization, just for sort algorithm, //{x} <= {y}
        if (!is_partial() && x_less_y())
        {
            const auto id_range = _M_zs;
            p->set_odd(id_range, _x_orig);
            return nullptr;
        }
        //else: we have to revert "_x(y)_orig" flag of the parent merging task
        const auto id_range = _M_zs;
        p->set_odd(id_range, !_x_orig);

        return merge_ranges(__self);
    }

    //splitting as merge task into 2 of the same level
    __task*
    split_merging(__task* __self)
d458 3
a460 7
        _PSTL_ASSERT(_x_orig == _y_orig);
        const auto __nx = (_M_xe - _M_xs);
        const auto __ny = (_M_ye - _M_ys);

        _SizeType __xm{};
        _SizeType __ym{};
        if (__nx < __ny)
d462 2
a463 6
            __ym = _M_ys + __ny / 2;

            if (_x_orig)
                __xm = std::upper_bound(_M_x_beg + _M_xs, _M_x_beg + _M_xe, *(_M_x_beg + __ym), _M_comp) - _M_x_beg;
            else
                __xm = std::upper_bound(_M_z_beg + _M_xs, _M_z_beg + _M_xe, *(_M_z_beg + __ym), _M_comp) - _M_z_beg;
d467 2
a468 6
            __xm = _M_xs + __nx / 2;

            if (_y_orig)
                __ym = std::lower_bound(_M_x_beg + _M_ys, _M_x_beg + _M_ye, *(_M_x_beg + __xm), _M_comp) - _M_x_beg;
            else
                __ym = std::lower_bound(_M_z_beg + _M_ys, _M_z_beg + _M_ye, *(_M_z_beg + __xm), _M_comp) - _M_z_beg;
d470 5
a474 9

        auto __zm = _M_zs + ((__xm - _M_xs) + (__ym - _M_ys));
        __merge_func __right_func(__xm, _M_xe, __ym, _M_ye, __zm, _M_comp, _Cleanup(), _M_leaf_merge, _M_nsort,
                                  _M_x_beg, _M_z_beg, _x_orig, _y_orig, _root);
        __right_func._split = true;
        auto __merge_task = __self->make_additional_child_of(__self->parent(), std::move(__right_func));
        __self->spawn(__merge_task);
        __self->recycle_as_continuation();

a476 44
        _split = true;

        return __self;
    }
};

template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename __M_Compare, typename _Cleanup,
          typename _LeafMerge>
__task*
__merge_func<_RandomAccessIterator1, _RandomAccessIterator2, __M_Compare, _Cleanup, _LeafMerge>::
operator()(__task* __self)
{
    //a. split merge task into 2 of the same level; the special logic,
    //without processing(process_ranges) adjacent sub-ranges x and y
    if (_split)
        return merge_ranges(__self);

    //b. General merging of adjacent sub-ranges x and y (with optimization in case of {x} <= {y} )

    //1. x and y are in the even buffer
    //2. x and y are in the odd buffer
    if (_x_orig == _y_orig)
        return process_ranges(__self);

    //3. x is in even buffer, y is in the odd buffer
    //4. x is in odd buffer, y is in the even buffer
    if (!parent_merge(__self))
    { //root merge task
        if (_x_orig)
            move_x_range();
        else
            move_y_range();
    }
    else
    {
        const _SizeType __nx = (_M_xe - _M_xs);
        const _SizeType __ny = (_M_ye - _M_ys);
        _PSTL_ASSERT(__nx > 0);
        _PSTL_ASSERT(__nx > 0);

        if (__nx < __ny)
            move_x_range();
        else
            move_y_range();
d478 1
a478 2

    return process_ranges(__self);
d482 1
a482 1
class __stable_sort_func
d490 4
a493 2
    _RandomAccessIterator1 _M_xs, _M_xe, _M_x_beg;
    _RandomAccessIterator2 _M_zs, _M_z_beg;
d496 2
a497 2
    bool _M_root;
    _SizeType _M_nsort; //zero or number of elements to be sorted for partial_sort alforithm
d500 4
a503 5
    __stable_sort_func(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __zs,
                       bool __root, _Compare __comp, _LeafSort __leaf_sort, _SizeType __nsort,
                       _RandomAccessIterator1 __x_beg, _RandomAccessIterator2 __z_beg)
        : _M_xs(__xs), _M_xe(__xe), _M_x_beg(__x_beg), _M_zs(__zs), _M_z_beg(__z_beg), _M_comp(__comp),
          _M_leaf_sort(__leaf_sort), _M_root(__root), _M_nsort(__nsort)
d506 1
d508 7
a514 2
    __task*
    operator()(__task* __self);
d520 2
a521 2
__task*
__stable_sort_func<_RandomAccessIterator1, _RandomAccessIterator2, _Compare, _LeafSort>::operator()(__task* __self)
a522 4
    typedef __merge_func<_RandomAccessIterator1, _RandomAccessIterator2, _Compare, __utils::__serial_destroy,
                         __utils::__serial_move_merge>
        _MergeTaskType;

d529 51
a579 2
        _PSTL_ASSERT(!_M_root);
        return nullptr;
d581 1
a581 18

    const _RandomAccessIterator1 __xm = _M_xs + __n / 2;
    const _RandomAccessIterator2 __zm = _M_zs + (__xm - _M_xs);
    const _RandomAccessIterator2 __ze = _M_zs + __n;
    _MergeTaskType __m(_MergeTaskType(_M_xs - _M_x_beg, __xm - _M_x_beg, __xm - _M_x_beg, _M_xe - _M_x_beg,
                                      _M_zs - _M_z_beg, _M_comp, __utils::__serial_destroy(),
                                      __utils::__serial_move_merge(__nmerge), _M_nsort, _M_x_beg, _M_z_beg,
                                      /*x_orig*/ true, /*y_orig*/ true, /*root*/ _M_root));
    auto __parent = __self->make_continuation(std::move(__m));
    __parent->set_ref_count(2);
    auto __right = __self->make_child_of(
        __parent, __stable_sort_func(__xm, _M_xe, __zm, false, _M_comp, _M_leaf_sort, _M_nsort, _M_x_beg, _M_z_beg));
    __self->spawn(__right);
    __self->recycle_as_child_of(__parent);
    _M_root = false;
    _M_xe = __xm;

    return __self;
d594 2
a595 2
        if (__nsort == __n)
            __nsort = 0; // 'partial_sort' becames 'sort'
d600 1
d602 4
a605 3
            __root_task<__stable_sort_func<_RandomAccessIterator, _ValueType*, _Compare, _LeafSort>> __root{
                __xs, __xe, __buf.get(), true, __comp, __leaf_sort, __nsort, __xs, __buf.get()};
            __task::spawn_root_and_wait(__root);
a615 62
template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _RandomAccessIterator3,
          typename _Compare, typename _LeafMerge>
class __merge_func_static
{
    _RandomAccessIterator1 _M_xs, _M_xe;
    _RandomAccessIterator2 _M_ys, _M_ye;
    _RandomAccessIterator3 _M_zs;
    _Compare _M_comp;
    _LeafMerge _M_leaf_merge;

  public:
    __merge_func_static(_RandomAccessIterator1 __xs, _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys,
                        _RandomAccessIterator2 __ye, _RandomAccessIterator3 __zs, _Compare __comp,
                        _LeafMerge __leaf_merge)
        : _M_xs(__xs), _M_xe(__xe), _M_ys(__ys), _M_ye(__ye), _M_zs(__zs), _M_comp(__comp), _M_leaf_merge(__leaf_merge)
    {
    }

    __task*
    operator()(__task* __self);
};

//TODO: consider usage of parallel_for with a custom blocked_range
template <typename _RandomAccessIterator1, typename _RandomAccessIterator2, typename _RandomAccessIterator3,
          typename __M_Compare, typename _LeafMerge>
__task*
__merge_func_static<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3, __M_Compare, _LeafMerge>::
operator()(__task* __self)
{
    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type _DifferenceType1;
    typedef typename std::iterator_traits<_RandomAccessIterator2>::difference_type _DifferenceType2;
    typedef typename std::common_type<_DifferenceType1, _DifferenceType2>::type _SizeType;
    const _SizeType __n = (_M_xe - _M_xs) + (_M_ye - _M_ys);
    const _SizeType __merge_cut_off = _PSTL_MERGE_CUT_OFF;
    if (__n <= __merge_cut_off)
    {
        _M_leaf_merge(_M_xs, _M_xe, _M_ys, _M_ye, _M_zs, _M_comp);
        return nullptr;
    }

    _RandomAccessIterator1 __xm;
    _RandomAccessIterator2 __ym;
    if (_M_xe - _M_xs < _M_ye - _M_ys)
    {
        __ym = _M_ys + (_M_ye - _M_ys) / 2;
        __xm = std::upper_bound(_M_xs, _M_xe, *__ym, _M_comp);
    }
    else
    {
        __xm = _M_xs + (_M_xe - _M_xs) / 2;
        __ym = std::lower_bound(_M_ys, _M_ye, *__xm, _M_comp);
    }
    const _RandomAccessIterator3 __zm = _M_zs + ((__xm - _M_xs) + (__ym - _M_ys));
    auto __right = __self->make_additional_child_of(
        __self->parent(), __merge_func_static(__xm, _M_xe, __ym, _M_ye, __zm, _M_comp, _M_leaf_merge));
    __self->spawn(__right);
    __self->recycle_as_continuation();
    _M_xe = __xm;
    _M_ye = __ym;

    return __self;
}
d637 2
a638 2
            typedef __merge_func_static<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3,
                                        _Compare, _LeafMerge>
d640 2
a641 2
            __root_task<_TaskType> __root{__xs, __xe, __ys, __ye, __zs, __comp, __leaf_merge};
            __task::spawn_root_and_wait(__root);
d657 1
a657 1
} // namespace __tbb_backend
@


1.1.1.4
log
@initial import of GCC 14.3.0.

major changes in GCC 13:
- improved sanitizer
- zstd debug info compression
- LTO improvements
- SARIF based diagnostic support
- new warnings: -Wxor-used-as-pow, -Wenum-int-mismatch, -Wself-move,
  -Wdangling-reference
- many new -Wanalyzer* specific warnings
- enhanced warnings: -Wpessimizing-move, -Wredundant-move
- new attributes to mark file descriptors, c++23 "assume"
- several C23 features added
- several C++23 features added
- many new features for Arm, x86, RISC-V

major changes in GCC 14:
- more strict C99 or newer support
- ia64* marked deprecated (but seemingly still in GCC 15.)
- several new hardening features
- support for "hardbool", which can have user supplied values of true/false
- explicit support for stack scrubbing upon function exit
- better auto-vectorisation support
- added clang-compatible __has_feature and __has_extension
- more C23, including -std=c23
- several C++26 features added
- better diagnostics in C++ templates
- new warnings: -Wnrvo, Welaborated-enum-base
- many new features for Arm, x86, RISC-V
- possible ABI breaking change for SPARC64 and small structures with arrays
  of floats.
@
text
@a17 5
#ifndef TBB_SUPPRESS_DEPRECATED_MESSAGES
# define TBB_SUPPRESS_DEPRECATED_MESSAGES 1
# define _GLIBCXX_UNDEF_SUPPRESS
#endif

a27 5
#ifdef _GLIBCXX_UNDEF_SUPPRESS
# undef TBB_SUPPRESS_DEPRECATED_MESSAGES
# undef _GLIBCXX_UNDEF_SUPPRESS
#endif

d102 1
a102 1
__parallel_for(__pstl::__internal::__tbb_backend_tag, _ExecutionPolicy&&, _Index __first, _Index __last, _Fp __f)
d113 2
a114 2
__parallel_reduce(__pstl::__internal::__tbb_backend_tag, _ExecutionPolicy&&, _Index __first, _Index __last,
                  const _Value& __identity, const _RealBody& __real_body, const _Reduction& __reduction)
d194 2
a195 2
__parallel_transform_reduce(__pstl::__internal::__tbb_backend_tag, _ExecutionPolicy&&, _Index __first, _Index __last,
                            _Up __u, _Tp __init, _Cp __combine, _Rp __brick_reduce)
d357 2
a358 2
__parallel_strict_scan(__pstl::__internal::__tbb_backend_tag, _ExecutionPolicy&&, _Index __n, _Tp __initial,
                       _Rp __reduce, _Cp __combine, _Sp __scan, _Ap __apex)
d397 2
a398 2
__parallel_transform_scan(__pstl::__internal::__tbb_backend_tag, _ExecutionPolicy&&, _Index __n, _Up __u, _Tp __init,
                          _Cp __combine, _Rp __brick_reduce, _Sp __scan)
d806 1
a806 1
        template <typename _Iterator>
d808 1
a808 1
        operator()(_Iterator __first, _Iterator __last)
d1157 2
a1158 2
__parallel_stable_sort(__pstl::__internal::__tbb_backend_tag, _ExecutionPolicy&&, _RandomAccessIterator __xs,
                       _RandomAccessIterator __xe, _Compare __comp, _LeafSort __leaf_sort, std::size_t __nsort = 0)
d1251 3
a1253 3
__parallel_merge(__pstl::__internal::__tbb_backend_tag, _ExecutionPolicy&&, _RandomAccessIterator1 __xs,
                 _RandomAccessIterator1 __xe, _RandomAccessIterator2 __ys, _RandomAccessIterator2 __ye,
                 _RandomAccessIterator3 __zs, _Compare __comp, _LeafMerge __leaf_merge)
d1282 1
a1282 1
__parallel_invoke(__pstl::__internal::__tbb_backend_tag, _ExecutionPolicy&&, _F1&& __f1, _F2&& __f2)
@