diff options
Diffstat (limited to 'libcilkrts/include/cilk/reducer.h')
| -rw-r--r-- | libcilkrts/include/cilk/reducer.h | 1154 |
1 files changed, 628 insertions, 526 deletions
diff --git a/libcilkrts/include/cilk/reducer.h b/libcilkrts/include/cilk/reducer.h index a22651e1e6f..09c2e196903 100644 --- a/libcilkrts/include/cilk/reducer.h +++ b/libcilkrts/include/cilk/reducer.h @@ -1,10 +1,8 @@ /* reducer.h -*- C++ -*- * - * @copyright - * Copyright (C) 2009-2013, Intel Corporation + * Copyright (C) 2009-2016, Intel Corporation * All rights reserved. * - * @copyright * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: @@ -19,7 +17,6 @@ * contributors may be used to endorse or promote products derived * from this software without specific prior written permission. * - * @copyright * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR @@ -32,11 +29,25 @@ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. + * + * ********************************************************************* + * + * PLEASE NOTE: This file is a downstream copy of a file mainitained in + * a repository at cilkplus.org. Changes made to this file that are not + * submitted through the contribution process detailed at + * http://www.cilkplus.org/submit-cilk-contribution will be lost the next + * time that a new version is released. Changes only submitted to the + * GNU compiler collection or posted to the git repository at + * https://bitbucket.org/intelcilkruntime/intel-cilk-runtime.git are + * not tracked. + * + * We welcome your contributions to this open source project. Thank you + * for your assistance in helping us improve Cilk Plus. */ - + /** @file reducer.h * - * @brief Defines foundation classes for creating Cilk reducers. + * @brief Defines foundation classes for creating Intel(R) Cilk(TM) Plus reducers. * * @ingroup Reducers * @@ -44,7 +55,7 @@ * * @defgroup Reducers Reducers */ - + #ifndef REDUCER_H_INCLUDED #define REDUCER_H_INCLUDED @@ -59,12 +70,96 @@ namespace cilk { +/** Class for provisionally constructed objects. + * + * The monoid_base<T,V>::construct() functions manually construct both a + * monoid and a view. If one of these is constructed successfully, and the + * construction of the other (or some other initialization) fails, then the + * first one must be destroyed to avoid a memory leak. Because the + * construction is explicit, the destruction must be explicit, too. + * + * A provisional_guard object wraps a pointer to a newly constructed + * object. A call to its confirm() function confirms that the object is + * really going to be used. If the guard is destroyed without being + * confirmed, then the pointed-to object is destroyed (but not + * deallocated). + * + * Expected usage: + * + * provisional_guard<T1> x1_provisional( new (x1) T1 ); + * … more initialization … + * x1_provisional.confirm(); + * + * or + * + * provisional_guard<T1> x1_provisional( new (x1) T1 ); + * x1_provisional.confirm_if( new (x2) T2 ); + * + * If an exception is thrown in the "more initialization" code in the + * first example, or in the `T2` constructor in the second example, then + * `x1_provisional` will not be confirmed, so when its destructor is + * called during exception unwinding, the `T1` object that was constructed + * in `x1` will be destroyed. + * + * **NOTE**: Do *not* be tempted to chain a `provisional_guard` + * constructor with `confirm_if` as in this example: + * + * // BAD IDEA + * provisional_guard<T1>( new (x1) T1 ).confirm_if( new (x2) T2 ); + * + * The code above is problematic because the evaluation of the T2 + * constructor is unsequenced with respect to the call to the + * `provisional_guard` constructor (and with respect the T1 constructor). + * Thus, the compiler may choose to evaluate `new (x2) T2` before + * constructing the guard and leak the T1 object if the `T2` constructor + * throws. + * + * @tparam Type The type of the provisionally constructed object. + */ +template <typename Type> +class provisional_guard { + Type* m_ptr; + +public: + + /** Constructor. Creates a guard for a provisionally constructed object. + * + * @param ptr A pointer to the provisionally constructed object. + */ + provisional_guard(Type* ptr) : m_ptr(ptr) {} + + /** Destructor. Destroy the object pointed to by the contained pointer + * if it has not been confirmed. + */ + ~provisional_guard() { if (m_ptr) m_ptr->~Type(); } + + /** Confirm the provisional construction. Do *not* delete the contained + * pointer when the guard is destroyed. + */ + void confirm() { m_ptr = 0; } + + /** Confirm provisional construction if argument is non-null. Note that + * if an exception is thrown during evaluation of the argument + * expression, then this function will not be called, and the + * provisional object will not be confirmed. This allows the usage: + * + * x1_provisional.confirm_if( new (x2) T2() ); + * + * @param cond An arbitrary pointer. The provisional object will be + * confirmed if @a cond is not null. + * + * @returns The value of the @a cond argument. + */ + template <typename Cond> + Cond* confirm_if(Cond* cond) { if (cond) m_ptr = 0; return cond; } +}; + /** Base class for defining monoids. * * The monoid_base class template is useful for creating classes that model * the monoid concept. It provides the core type and memory management * functionality. A subclass of monoid_base need only declare and implement - * the `identity` and `reduce` functions. + * the `identity` and `reduce` functions. * * The monoid_base class also manages the integration between the monoid, the * reducer class that is based on it, and an optional view class which wraps @@ -79,149 +174,51 @@ namespace cilk { template <typename Value, typename View = Value> class monoid_base { -protected: - - /** Class for provisionally constructed objects. - * - * The monoid_base::construct() functions manually construct both a monoid - * and a view. If one of these is constructed successfully, and the - * construction of the other (or some other initialization) fails, then - * the first one must be destroyed to avoid a memory leak. Because the - * construction is explicit, the destruction must be explicit, too. - * - * A provisional_guard object wraps a pointer to a newly constructed - * object. A call to its confirm() function confirms that the object is - * really going to be used. If the guard is destroyed without being - * confirmed, then the pointed-to object is destroyed (but not - * deallocated). - * - * Expected usage: - * - * provisional_guard<T1> x1_provisional( new (x1) T1() ); - * … more initialization … - * x1_provisional.confirm(); - * - * or - * - * provisional_guard<T1> x1_provisional( new (x1) T1() ); - * x1_provisional.confirm_if( new (x2) T2() ); - * - * If an exception is thrown in the “more initialization” code in the - * first example, or in the `T2` constructor in the second example, then - * `x1_provisional` will not be confirmed, so when its destructor is - * called during exception unwinding, the `T1` object that was constructed - * in `x1` will be destroyed. - * - * @see provisional() - * - * @tparam Type The type of the provisionally constructed object. - */ - template <typename Type> - class provisional_guard { - Type* m_ptr; - - public: - - /** Constructor. Creates a guard for a provisionally constructed object. - * - * @param ptr A pointer to the provisionally constructed object. - */ - provisional_guard(Type* ptr) : m_ptr(ptr) {} - - /** Destructor. Destroy the object pointed to by the contained pointer - * if it has not been confirmed. - */ - ~provisional_guard() { if (m_ptr) m_ptr->~Type(); } - - /** Confirm the provisional construction. Do *not* delete the contained - * pointer when the guard is destroyed. - */ - void confirm() { m_ptr = 0; } - - /** Confirm provisional construction if argument is non-null. Note that - * if an exception is thrown during evaluation of the argument - * expression, then this function will not be called, and the - * provisional object will not be confirmed. This allows the usage: - * - * x1_provisional.confirm_if( new (x2) T2() ); - * - * @param cond An arbitrary pointer. The provisional object will be - * confirmed if @a cond is not null. - * - * @returns The value of the @a cond argument. - */ - template <typename Cond> - Cond* confirm_if(Cond* cond) { if (cond) m_ptr = 0; return cond; } - }; - - - /** Create a provisional_guard object. This function allows simpler code - * when the only use of a provisional_guard is in a - * provisional_guard::confirm_if() call immediately following its - * creation. Instead of - * - * provisional_guard<T>guard( new (ptr_to_T) T() ); - * guard.confirm_if( new (ptr_to_U) U() ); - * - * you can just write - * - * provisional( new (ptr_to_T) T() ).confirm_if( new (ptr_to_U) U() ); - * - * @tparam Type The type of the provisionally constructed object. - * - * @param ptr A pointer to a provisionally constructed object. - * - * @returns A @ref provisional_guard object that guards the - * provisionally constructed object pointed to by @a ptr. - */ - template <typename Type> - static provisional_guard<Type> provisional(Type* ptr) - { return provisional_guard<Type>(ptr); } public: /** Value type of the monoid. */ typedef Value value_type; - + /** View type of the monoid. Defaults to be the same as the value type. * @see monoid_with_view */ typedef View view_type; - - enum { + + enum { /** Should reducers created with this monoid be aligned? * * @details - * “Aligned” means that the view is allocated at a cache-line aligned + * "Aligned" means that the view is allocated at a cache-line aligned * offset in the reducer, and the reducer must be cache-line aligned. - * “Unaligned” means that the reducer as a whole is just naturally - * aligned, but it contains a large enough block of uninitialized + * "Unaligned" means that the reducer as a whole is just naturally + * aligned, but it contains a large enough block of uninitialized * storage for a cache-line aligned view to be allocated in it at * reducer construction time. * - * Since the standard heap allocator (new reducer) does not allocate + * Since the standard heap allocator (new reducer) does not allocate * cache-line aligned storage, only unaligned reducers can be safely * allocated on the heap. - * + * * Default is false (unaligned) unless overridden in a subclass. * * @since 1.02 - * (In Cilk library versions 1.0 and 1.01, the default was true. - * In Cilk library versions prior to 1.0, reducers were always aligned, - * and this data member did not exist.) + * (In Intel Cilk Plus library versions 1.0 and 1.01, the default was true. + * In Intel Cilk Plus library versions prior to 1.0, reducers were always + * aligned, and this data member did not exist.) */ - align_reducer = false + align_reducer = false }; - - /** Destroy a view. Destroys (without deallocating) the @a View object + + /** Destroys a view. Destroys (without deallocating) the @a View object * pointed to by @a p. * * @param p The address of the @a View object to be destroyed. */ void destroy(view_type* p) const { p->~view_type(); } - /** Allocate raw memory. Allocate @a s bytes of memory with no + /** Allocates raw memory. Allocate @a s bytes of memory with no * initialization. * * @param s The number of bytes of memory to allocate. @@ -229,7 +226,7 @@ public: */ void* allocate(size_t s) const { return operator new(s); } - /** Deallocate raw memory. Deallocates the memory pointed to by @a p + /** Deallocates raw memory pointed to by @a p * without doing any destruction. * * @param p Pointer to the memory to be deallocated. @@ -239,10 +236,10 @@ public: */ void deallocate(void* p) const { operator delete(p); } - /** Create the identity value. Constructs (without allocating) a @a View + /** Creates the identity value. Constructs (without allocating) a @a View * object representing the default value of the @a Value type. * - * @param p A pointer to a block of raw memory large enough to hold a + * @param p A pointer to a block of raw memory large enough to hold a * @a View object. * * @post The memory pointed to by @a p contains a @a View object that @@ -255,128 +252,165 @@ public: * this default definition. */ void identity(View* p) const { new ((void*) p) View(); } - - - /** @name Construct the monoid and the view with arbitrary arguments. + + + /** @name Constructs the monoid and the view with arbitrary arguments. * * A @ref reducer object contains monoid and view data members, which are * declared as raw storage (byte arrays), so that they are not implicitly * constructed when the reducer is constructed. Instead, a reducer - * constructor calls one of the monoid class’s static construct() + * constructor calls one of the monoid class's static construct() * functions with the addresses of the monoid and the view, and the * construct() function uses placement `new` to construct them. - * * This allows the monoid to determine the order in which the monoid and * view are constructed, and to make one of them dependent on the other. * - * Any arguments to the reducer constructor are just passed on as + * Any arguments to the reducer constructor are just passed on as * additional arguments to the construct() function (after the monoid - * and view addresses). + * and view addresses are set). * - * Any monoid whose needs are satisfied by the suite of construct() + * A monoid whose needs are satisfied by the suite of construct() * functions below, such as @ref monoid_with_view, can just inherit them * from monoid_base. Other monoids will need to provide their own versions * to override the monoid_base functions. */ //@{ - - /** Default-construct the monoid, and pass zero to five const reference - * arguments to the view constructor. + + /** Default-constructs the monoid, identity-constructs the view. + * + * @param monoid Address of uninitialized monoid object. + * @param view Address of uninitialized initial view object. */ //@{ - template <typename Monoid> static void construct(Monoid* monoid, View* view) - { provisional( new ((void*)monoid) Monoid() ).confirm_if( - (monoid->identity(view), view) ); } + { + provisional_guard<Monoid> guard( new((void*) monoid) Monoid() ); + monoid->identity(view); + guard.confirm(); + } + //@} + + /** Default-constructs the monoid, and passes one to five const reference + * arguments to the view constructor. + */ + //@{ template <typename Monoid, typename T1> static void construct(Monoid* monoid, View* view, const T1& x1) - { provisional( new ((void*)monoid) Monoid() ).confirm_if( - new ((void*)view) View(x1) ); } + { + provisional_guard<Monoid> guard( new((void*) monoid) Monoid() ); + guard.confirm_if( new((void*) view) View(x1) ); + } template <typename Monoid, typename T1, typename T2> - static void construct(Monoid* monoid, View* view, + static void construct(Monoid* monoid, View* view, const T1& x1, const T2& x2) - { provisional( new ((void*)monoid) Monoid() ).confirm_if( - new ((void*)view) View(x1, x2) ); } + { + provisional_guard<Monoid> guard( new((void*) monoid) Monoid() ); + guard.confirm_if( new((void*) view) View(x1, x2) ); + } template <typename Monoid, typename T1, typename T2, typename T3> - static void construct(Monoid* monoid, View* view, + static void construct(Monoid* monoid, View* view, const T1& x1, const T2& x2, const T3& x3) - { provisional( new ((void*)monoid) Monoid() ).confirm_if( - new ((void*)view) View(x1, x2, x3) ); } + { + provisional_guard<Monoid> guard( new((void*) monoid) Monoid() ); + guard.confirm_if( new((void*) view) View(x1, x2, x3) ); + } - template <typename Monoid, typename T1, typename T2, typename T3, + template <typename Monoid, typename T1, typename T2, typename T3, typename T4> - static void construct(Monoid* monoid, View* view, - const T1& x1, const T2& x2, const T3& x3, + static void construct(Monoid* monoid, View* view, + const T1& x1, const T2& x2, const T3& x3, const T4& x4) - { provisional( new ((void*)monoid) Monoid() ).confirm_if( - new ((void*)view) View(x1, x2, x3, x4) ); } + { + provisional_guard<Monoid> guard( new((void*) monoid) Monoid() ); + guard.confirm_if( new((void*) view) View(x1, x2, x3, x4) ); + } - template <typename Monoid, typename T1, typename T2, typename T3, + template <typename Monoid, typename T1, typename T2, typename T3, typename T4, typename T5> - static void construct(Monoid* monoid, View* view, - const T1& x1, const T2& x2, const T3& x3, + static void construct(Monoid* monoid, View* view, + const T1& x1, const T2& x2, const T3& x3, const T4& x4, const T5& x5) - { provisional( new ((void*)monoid) Monoid() ).confirm_if( - new ((void*)view) View(x1, x2, x3, x4, x5) ); } - + { + provisional_guard<Monoid> guard( new((void*) monoid) Monoid() ); + guard.confirm_if( new((void*) view) View(x1, x2, x3, x4, x5) ); + } + //@} - - /** Default-construct the monoid, and pass one non-const reference argument - * to the view constructor. + + /** Default-constructs the monoid, and passes one non-const reference + * argument to the view constructor. */ //@{ template <typename Monoid, typename T1> static void construct(Monoid* monoid, View* view, T1& x1) - { provisional( new ((void*)monoid) Monoid() ).confirm_if( - new ((void*)view) View(x1) ); } + { + provisional_guard<Monoid> guard( new((void*) monoid) Monoid() ); + guard.confirm_if( new((void*) view) View(x1) ); + } //@} - /** Copy-construct the monoid, and pass zero to four const reference - * arguments to the view constructor. + /** Copy-constructs the monoid, and identity-constructs the view + * constructor. + * + * @param monoid Address of uninitialized monoid object. + * @param view Address of uninitialized initial view object. + * @param m Object to be copied into `*monoid` */ //@{ - template <typename Monoid> static void construct(Monoid* monoid, View* view, const Monoid& m) - { provisional( new ((void*)monoid) Monoid(m) ).confirm_if( - new ((void*)view) View() ); } + { + provisional_guard<Monoid> guard( new((void*) monoid) Monoid(m) ); + monoid->identity(view); + guard.confirm(); + } + //@} + + /** Copy-constructs the monoid, and passes one to four const reference + * arguments to the view constructor. + */ + //@{ template <typename Monoid, typename T1> - static void construct(Monoid* monoid, View* view, const Monoid& m, + static void construct(Monoid* monoid, View* view, const Monoid& m, const T1& x1) - { provisional( new ((void*)monoid) Monoid(m) ).confirm_if( - new ((void*)view) View(x1) ); } - + { + provisional_guard<Monoid> guard( new((void*) monoid) Monoid(m) ); + guard.confirm_if( new((void*) view) View(x1) ); + } + template <typename Monoid, typename T1, typename T2> - static void construct(Monoid* monoid, View* view, const Monoid& m, + static void construct(Monoid* monoid, View* view, const Monoid& m, const T1& x1, const T2& x2) - { provisional( new ((void*)monoid) Monoid(m) ).confirm_if( - new ((void*)view) View(x1, x2) ); } - + { + provisional_guard<Monoid> guard( new((void*) monoid) Monoid(m) ); + guard.confirm_if( new((void*) view) View(x1, x2) ); + } + template <typename Monoid, typename T1, typename T2, typename T3> - static void construct(Monoid* monoid, View* view, const Monoid& m, + static void construct(Monoid* monoid, View* view, const Monoid& m, const T1& x1, const T2& x2, const T3& x3) { - provisional( new ((void*)monoid) Monoid(m) ).confirm_if( - new ((void*)view) View(x1, x2, x3) ); + provisional_guard<Monoid> guard( new((void*) monoid) Monoid(m) ); + guard.confirm_if( new((void*) view) View(x1, x2, x3) ); } - - template <typename Monoid, typename T1, typename T2, typename T3, + + template <typename Monoid, typename T1, typename T2, typename T3, typename T4> - static void construct(Monoid* monoid, View* view, const Monoid& m, - const T1& x1, const T2& x2, const T3& x3, + static void construct(Monoid* monoid, View* view, const Monoid& m, + const T1& x1, const T2& x2, const T3& x3, const T4& x4) { - provisional( new ((void*)monoid) Monoid(m) ).confirm_if( - new ((void*)view) View(x1, x2, x3, x4) ); + provisional_guard<Monoid> guard( new((void*) monoid) Monoid(m) ); + guard.confirm_if( new((void*) view) View(x1, x2, x3, x4) ); } - + //@} - + //@} }; @@ -385,8 +419,8 @@ public: * from its view. * * A simple implementation of the monoid-view-reducer architecture would - * distribute knowledge about the type and operations for the reduction - * between the monoid and the view — the identity and reduction operations are + * distribute knowledge about the type and operations for the reduction + * between the monoid and the view - the identity and reduction operations are * specified in the monoid, the reduction operations are implemented in the * view, and the value type is specified in both the monoid and the view. * This is inelegant. @@ -396,10 +430,11 @@ public: * customization of the monoid_with_view class itself is needed beyond * instantiating it with an appropriate view class. (Customized subclasses of * monoid_with_view may be needed for other reasons, such as to keep some - * state for the reducer.) All of the Cilk predefined reducers use + * state for the reducer.) All of the Intel Cilk Plus predefined reducers use * monoid_with_view or one of its subclasses. - * - * The view class `View` of a monoid_with_view must provide the following public definitions: + * + * The view class `View` of a monoid_with_view must provide the following + * public definitions: * * Definition | Meaning * ---------------------------------|-------- @@ -420,20 +455,20 @@ public: /** Should reducers created with this monoid be aligned? */ enum { align_reducer = Align }; - + /** Create the identity value. * - * Implements the monoid `identity` operation by using the @a View class’s + * Implements the monoid `identity` operation by using the @a View class's * default constructor. * - * @param p A pointer to a block of raw memory large enough to hold a + * @param p A pointer to a block of raw memory large enough to hold a * @p View object. */ - void identity(View* p) const { new ((void*)p) View(); } - + void identity(View* p) const { new((void*) p) View(); } + /** Reduce the values of two views. * - * Implements the monoid `reduce` operation by calling the left view’s + * Implements the monoid `reduce` operation by calling the left view's * `%reduce()` function with the right view as an operand. * * @param left The left operand of the reduce operation. @@ -452,7 +487,7 @@ public: * required by a @ref monoid_with_view (but not the identity constructor and * reduce operation, which are inherently specific to a particular kind of * reduction). It also defines the value access functions which will be called - * by the corresponding @ref reducer functions. (It uses copy semantics for + * by the corresponding @ref reducer functions. (It uses copy semantics for * the view_move_in() and view_move_out() functions, which is appropriate * for simple scalar types, but not necessarily for more complex types like * STL containers. @@ -469,15 +504,15 @@ public: /** Value type definition required by @ref monoid_with_view. */ typedef Type value_type; - + /** Default constructor. */ - scalar_view() : m_value() {} - + scalar_view() : m_value() {} + /** Value constructor. */ scalar_view(const Type& v) : m_value(v) {} - + /** @name Value functions required by the reducer class. * * Note that the move in/out functions use simple assignment semantics. @@ -499,12 +534,16 @@ public: /** Get the value of the view. */ Type const& view_get_value() const { return m_value; } - + + /** Type returned by view_get_value. + */ + typedef Type const& return_type_for_get_value; + /** Get a reference to the value contained in the view. For legacy * reducer support only. */ Type & view_get_reference() { return m_value; } - + /** Get a reference to the value contained in the view. For legacy * reducer support only. */ @@ -517,18 +556,18 @@ public: * * Some types allow their values to be _moved_ as an alternative to copying. * Moving a value may be much faster than copying it, but may leave the value - * of the move’s source undefined. Consider the `swap` operation provided by + * of the move's source undefined. Consider the `swap` operation provided by * many STL container classes: * * list<T> x, y; * x = y; // Copy * x.swap(y); // Move * - * The assignment _copies_ the value of `y` into `x` in time linear in the + * The assignment _copies_ the value of `y` into `x` in time linear in the * size of `y`, leaving `y` unchanged. The `swap` _moves_ the value of `y` * into `x` in constant time, but it also moves the value of `x` into `y`, * potentially leaving `y` undefined. - * + * * A move_in_wrapper simply wraps a pointer to an object. It is created by a * call to cilk::move_in(). Passing a move_in_wrapper to a view constructor * (actually, passing it to a reducer constructor, which passes it to the @@ -538,18 +577,18 @@ public: * * A view class exercises this option by defining a _move-in constructor_, * i.e., a constructor with a move_in_wrapper parameter. The constructor calls - * the wrapper’s `value()` function to get a reference to its pointed-to + * the wrapper's `value()` function to get a reference to its pointed-to * value, and can then use that reference in a move operation. * * A move_in_wrapper also has an implicit conversion to its pointed-to value, - * so if a view class does not define a move-in constructor, its ordinary + * so if a view class does not define a move-in constructor, its ordinary * value constructor will be called with the wrapped value. For example, an * @ref ReducersAdd "op_add" view does not have a move-in constructor, so * * int x; * reducer< op_add<int> > xr(move_in(x)); * - * will simply call the `op_add_view(const int &)` constructor. But an + * will simply call the `op_add_view(const int &)` constructor. But an * @ref ReducersList "op_list_append" view does have a move-in constructor, * so * @@ -573,19 +612,19 @@ class move_in_wrapper { Type *m_pointer; public: - + /** Constructor that captures the address of its argument. This is almost * always called from the @ref move_in function. */ explicit move_in_wrapper(Type& ref) : m_pointer(&ref) { } - + /** Implicit conversion to the wrapped value. This allows a move_in_wrapper * to be used where a value of the wrapped type is expected, in which case * the wrapper is completely transparent. */ operator Type&() const { return *m_pointer; } - - /** Get a reference to the pointed-to value. This has the same effect as + + /** Get a reference to the pointed-to value. This has the same effect as * the implicit conversion, but makes the intent clearer in a move-in * constructor. */ @@ -594,7 +633,7 @@ public: /** Function to create a move_in_wrapper for a value. * - * @tparam Type The type of the argument, which will be the `type` of the + * @tparam Type The type of the argument, which will be the `type` of the * created wrapper. * * @see move_in_wrapper @@ -608,9 +647,9 @@ move_in_wrapper<Type> move_in(Type& ref) /** @copydoc move_in(Type&) * * @note Applying a function that is explicitly specified as modifying its - * argument to a const argument is obviously an irrational thing to + * argument to a const argument is obviously an irrational thing to * do. This move_in() variant is just provided to allow calling a - * move-in constructor with a function return value, which the + * move-in constructor with a function return value, which the * language treats as a const. Using it for any other purpose will * probably end in tears. */ @@ -622,37 +661,37 @@ move_in_wrapper<Type> move_in(const Type& ref) /** Wrapper class to allow implicit downcasts to reducer subclasses. * - * The Cilk library contains a collection of reducer wrapper classes which - * were created before the `cilk::reducer<Monoid>` style was developed. For + * The Intel Cilk Plus library contains a collection of reducer wrapper classes which + * were created before the `cilk::reducer<Monoid>` style was developed. For * example, `cilk::reducer_opadd<Type>` provided essentially the same - * functionality that is now provided by - * `cilk::reducer< cilk::op_add<Type> >`. These legacy reducer classes are - * deprecated, but still supported, and they have been reimplemented as + * functionality that is now provided by + * `cilk::reducer< cilk::op_add<Type> >`. These legacy reducer classes are + * deprecated, but still supported, and they have been reimplemented as * subclasses of the corresponding `cilk::reducer` classes. For example: * * template <class T> * reducer_opadd<T> : public reducer< op_add<T> > { ... }; * - * This reimplementation allows transparent conversion between legacy and - * new reducers. That is, a `reducer<op_add>*` or `reducer<op_add>&` can be - * used anywhere that a `reducer_opadd*` or `reducer_opadd&` is expected, - * and vice versa. + * This reimplementation allows transparent conversion between legacy and + * new reducers. That is, a `reducer<op_add>*` or `reducer<op_add>&` can be + * used anywhere that a `reducer_opadd*` or `reducer_opadd&` is expected, + * and vice versa. * - * The conversion from the legacy reducer to the new reducer is just an - * up-cast, which is provided for free by C++. The conversion from the new - * reducer to the legacy reducer is a down-cast, though, which requires an + * The conversion from the legacy reducer to the new reducer is just an + * up-cast, which is provided for free by C++. The conversion from the new + * reducer to the legacy reducer is a down-cast, though, which requires an * explicit conversion member function in the `reducer` class. The challenge * is to define a function in the reducer template class which will convert - * each cilk::reducer specialization to the corresponding legacy reducer, + * each cilk::reducer specialization to the corresponding legacy reducer, * if there is one. * * The trick is in the legacy_reducer_downcast template class, which provides * a mapping from `cilk::reducer` specializations to legacy reducer classes. - * `reducer<Monoid>` has a conversion function to convert itself to + * `reducer<Monoid>` has a conversion function to convert itself to * `legacy_reducer_downcast< reducer<Monoid> >::%type`. By default, * `legacy_reducer_downcast<Reducer>::%type` is just a trivial subclass of * `Reducer`, which is uninteresting, but a reducer with a legacy counterpart - * will have a specialization of `legacy_reducer_downcast` whose `type` is + * will have a specialization of `legacy_reducer_downcast` whose `type` is * the corresponding legacy reducer. For example: * * template <typename Type> @@ -662,16 +701,17 @@ move_in_wrapper<Type> move_in(const Type& ref) * }; * * - * @tparam Reducer The new-style reducer class whose corresponding legacy reducer class - * is `type`, if there is such a legacy reducer class. + * @tparam Reducer The new-style reducer class whose corresponding legacy + * reducer class is `type`, if there is such a legacy reducer + * class. */ template <typename Reducer> struct legacy_reducer_downcast { /** The related legacy reducer class. * - * By default, this is just a trivial subclass of Reducer, but it can be - * overridden in the specialization of legacy_reducer_downcast for + * By default, this is just a trivial subclass of Reducer, but it can be + * overridden in the specialization of legacy_reducer_downcast for * a reducer that has a corresponding legacy reducers. */ struct type : Reducer { }; @@ -684,21 +724,51 @@ namespace internal { template <typename Value, typename View> struct reducer_set_get { - static View theView; // Declared but not defined - - // sizeof(notchar) is guaranteed larger than 1 + // sizeof(notchar) != sizeof(char) struct notchar { char x[2]; }; - // check_for_ref returns char if 'get_value' returns by value and notchar - // if 'get_value' returns by reference. - static char check_for_ref(Value, ...); - static notchar check_for_ref(Value&, int); + // `does_view_define_return_type_for_get_value(View*)` returns `char` if + // `View` defines `return_type_for_get_value`, and `notchar` if it doesn't. + + template <typename T> + struct using_type {}; + + template <typename T> + static char does_view_define_return_type_for_get_value( + using_type<typename T::return_type_for_get_value>*); - enum { GET_VALUE_BY_VALUE = - (1 == sizeof(check_for_ref(theView.view_get_value(), 0))) } ; + template <typename T> + static notchar does_view_define_return_type_for_get_value(...); - typedef typename condition<GET_VALUE_BY_VALUE, - Value, const Value&>::type get_value_type; + // `VIEW_DOES_DEFINE_RETURN_TYPE_FOR_GET_VALUE` is true if `View` defines + // `return_type_for_get_value`. + + enum { VIEW_DOES_DEFINE_RETURN_TYPE_FOR_GET_VALUE = + sizeof( does_view_define_return_type_for_get_value<View>(0) ) + == sizeof(char) } ; + + // `return_type_for_get_value` is `View::return_type_for_get_value` + // if it is defined, and just `Value` otherwise. + + template <typename InnerView, bool ViewDoesDefineReturnTypeForGetValue> + struct return_type_for_view_get_value { + typedef Value type; + }; + + template <typename InnerView> + struct return_type_for_view_get_value<InnerView, true> { + typedef typename InnerView::return_type_for_get_value type; + }; + +public: + + typedef + typename + return_type_for_view_get_value< + View, + VIEW_DOES_DEFINE_RETURN_TYPE_FOR_GET_VALUE + >::type + return_type_for_get_value; static void move_in(View& view, Value& v) { view.view_move_in(v); } static void move_out(View& view, Value& v) { view.view_move_out(v); } @@ -706,21 +776,23 @@ struct reducer_set_get static void set_value(View& view, const Value& v) { view.view_set_value(v); } - static get_value_type get_value(const View& view) + static return_type_for_get_value get_value(const View& view) { return view.view_get_value(); } }; template <typename Value> struct reducer_set_get<Value, Value> { - typedef const Value& get_value_type; + typedef const Value& return_type_for_get_value; static void move_in(Value& view, Value& v) { view = v; } static void move_out(Value& view, Value& v) { v = view; } - static void set_value(Value& view, const Value& v) { view = v; } + static void set_value(Value& view, const Value& v) + { view = v; } - static get_value_type get_value(const Value& view) { return view; } + static return_type_for_get_value get_value(const Value& view) + { return view; } }; /// @endcond @@ -728,7 +800,7 @@ struct reducer_set_get<Value, Value> /** Base class defining the data layout that is common to all reducers. */ -template <typename Monoid> +template <typename Monoid> class reducer_base { typedef typename Monoid::view_type view_type; @@ -746,20 +818,20 @@ class reducer_base { // Used for sanity checking at destruction. // void* m_initialThis; - + // The leftmost view comes next. It is defined in the derived // reducer_content class. - + /** @name C-callable wrappers for the C++-coded monoid dispatch functions. */ //@{ - + static void reduce_wrapper(void* r, void* lhs, void* rhs); static void identity_wrapper(void* r, void* view); static void destroy_wrapper(void* r, void* view); static void* allocate_wrapper(void* r, __STDNS size_t bytes); static void deallocate_wrapper(void* r, void* view); - + //@} protected: @@ -768,7 +840,7 @@ protected: * * @param leftmost The address of the leftmost view in the reducer. */ - reducer_base(char* leftmost) + reducer_base(char* leftmost) { static const cilk_c_monoid c_monoid_initializer = { (cilk_c_reducer_reduce_fn_t) &reduce_wrapper, @@ -783,10 +855,10 @@ protected: m_base.__view_offset = (char*)leftmost - (char*)this; m_base.__view_size = sizeof(view_type); m_initialThis = this; - + __cilkrts_hyper_create(&m_base); } - + /** Destructor. */ __CILKRTS_STRAND_STALE(~reducer_base()) @@ -794,7 +866,7 @@ protected: // Make sure we haven't been memcopy'd or corrupted __CILKRTS_ASSERT( this == m_initialThis || - // Allow for a layout bug that may put the initialThis field one + // Allow for a layout bug that may put the initialThis field one // word later in 1.0 reducers than in 0.9 and 1.1 reducers. this == *(&m_initialThis + 1) ); @@ -803,63 +875,63 @@ protected: /** Monoid data member. * - * @return A pointer to the reducer’s monoid data member. + * @return A pointer to the reducer's monoid data member. */ Monoid* monoid_ptr() { return &m_monoid.object(); } /** Leftmost view data member. * - * @return A pointer to the reducer’s leftmost view data member. + * @return A pointer to the reducer's leftmost view data member. * - * @note This function returns the address of the *leftmost* view, - * which is unique for the lifetime of the reducer. It is - * intended to be used in constructors and destructors. - * Use the reducer::view() function to access the per-strand + * @note This function returns the address of the *leftmost* view, + * which is unique for the lifetime of the reducer. It is + * intended to be used in constructors and destructors. + * Use the reducer::view() function to access the per-strand * view instance. */ - view_type* leftmost_ptr() + view_type* leftmost_ptr() { char* view_addr = (char*)this + m_base.__view_offset; return reinterpret_cast<view_type*>(view_addr); } - + public: /** @name Access the current view. * - * These functions return a reference to the instance of the reducer’s + * These functions return a reference to the instance of the reducer's * view that was created for the current strand of a parallel computation - * (and create it if it doesn’t already exist). Note the difference from + * (and create it if it doesn't already exist). Note the difference from * the (private) leftmost_ptr() function, which returns a pointer to the * _leftmost_ view, which is the same in all strands. */ //@{ - + /** Per-strand view instance. * * @return A reference to the per-strand view instance. */ - view_type& view() + view_type& view() { - return *static_cast<view_type *>(__cilkrts_hyper_lookup(&m_base)); + return *static_cast<view_type *>(__cilkrts_hyper_lookup(&m_base)); } - + /** @copydoc view() */ - const view_type& view() const - { - return const_cast<reducer_base*>(this)->view(); + const view_type& view() const + { + return const_cast<reducer_base*>(this)->view(); } - + //@} - + /** Initial view pointer field. * * @internal * * @return a reference to the m_initialThis field. * - * @note This function is provided for “white-box” testing of the + * @note This function is provided for "white-box" testing of the * reducer layout code. There is never any reason for user code * to call it. */ @@ -905,7 +977,7 @@ void reducer_base<Monoid>::deallocate_wrapper(void* r, void* view) /** Base class defining the data members of a reducer. * - * @tparam Aligned The `m_view` data member, and therefore the entire + * @tparam Aligned The `m_view` data member, and therefore the entire * structure, are cache-line aligned if this parameter * is `true'. */ @@ -918,12 +990,12 @@ template <typename Monoid> class reducer_content<Monoid, true> : public reducer_base<Monoid> { typedef typename Monoid::view_type view_type; - + // The leftmost view is defined as raw bytes. It will be constructed - // by the monoid `construct` function. It is cache-aligned, which + // by the monoid `construct` function. It is cache-aligned, which // will push it into a new cache line. Furthermore, its alignment causes - // the reducer as a whole to be cache-aligned, which makes the reducer - // size a multiple of a cache line. Since there is nothing in the reducer + // the reducer as a whole to be cache-aligned, which makes the reducer + // size a multiple of a cache line. Since there is nothing in the reducer // after the view, all this means that the leftmost view gets one or more // cache lines all to itself, which prevents false sharing. // @@ -936,7 +1008,7 @@ class reducer_content<Monoid, true> : public reducer_base<Monoid> */ bool reducer_is_cache_aligned() const { return 0 == ((std::size_t) this & (__CILKRTS_CACHE_LINE__ - 1)); } - + protected: /** Constructor. @@ -945,14 +1017,15 @@ protected: { #ifndef CILK_IGNORE_REDUCER_ALIGNMENT assert(reducer_is_cache_aligned() && - "Reducer should be cache aligned. Please see comments following this assertion for explanation and fixes."); + "Reducer should be cache aligned. Please see comments following " + "this assertion for explanation and fixes."); #endif /* "REDUCER SHOULD BE CACHE ALIGNED" ASSERTION. * - * This Reducer class instantiation specifies cache-line alignment of the + * This Reducer class instantiation specifies cache-line alignment of the * leftmost view field (and, implicitly, of the reducer itself). You got * this assertion because a reducer with this class was allocated at a - * non-cache-aligned address, probably because it was allocated on the + * non-cache-aligned address, probably because it was allocated on the * heap with `new`. This can be a problem for two reasons: * * 1. If the leftmost view is not on a cache line by itself, there might @@ -974,14 +1047,14 @@ protected: * * There are three ways that you can fix this assertion failure. * - * A. Rewrite your code to use the new-style `reducer< op_XXX<Type> >` + * A. Rewrite your code to use the new-style `reducer< op_XXX<Type> >` * instead of the legacy `reducer_XXX<type>`. The new-style reducers * are not declared to be cache-aligned, and will work properly if * they are not cache-aligned. * * B. If you must allocate an old-style reducer or a structure containing * a reducer on the heap, figure out how to align it correctly. The - * suggested fix is to use `cilk::aligned_new()` and + * suggested fix is to use `cilk::aligned_new()` and * `cilk::aligned_delete()` instead of `new` and `delete`, as follows: * * Type* ptr = cilk::aligned_new<Type>(constructor-arguments); @@ -1003,7 +1076,7 @@ class reducer_content<Monoid, false> : public reducer_base<Monoid> // Reserve space for the leftmost view. The view will be allocated at an // aligned offset in this space at runtime, to guarantee that the view - // will get one or more cache lines all to itself, to prevent false + // will get one or more cache lines all to itself, to prevent false // sharing. // // The number of bytes to reserve is determined as follows: @@ -1026,10 +1099,10 @@ class reducer_content<Monoid, false> : public reducer_base<Monoid> protected: /** Constructor. Find the first cache-aligned position in the reserved - * area, and pass it to the base constructor as the leftmost view + * area, and pass it to the base constructor as the leftmost view * address. */ - reducer_content() : + reducer_content() : reducer_base<Monoid>( (char*)( ((std::size_t)&m_leftmost + __CILKRTS_CACHE_LINE__ - 1) & ~ (__CILKRTS_CACHE_LINE__ - 1) ) ) @@ -1056,8 +1129,9 @@ namespace stub { * A reducer is instantiated on a Monoid. The Monoid provides the value * type, associative reduce function, and identity for the reducer. * - * @tparam Monoid The monoid class that the reducer is instantiated on. It must model - * the @ref reducers_monoid_concept "monoid concept". + * @tparam Monoid The monoid class that the reducer is instantiated on. It + * must model the @ref reducers_monoid_concept "monoid + * concept". * * @see @ref pagereducers */ @@ -1068,33 +1142,33 @@ class reducer : public internal::reducer_content<Monoid> using base::monoid_ptr; using base::leftmost_ptr; public: - typedef Monoid monoid_type; ///< The monoid type. - typedef typename Monoid::value_type value_type; ///< The value type. - typedef typename Monoid::view_type view_type; ///< The view type. + typedef Monoid monoid_type; ///< The monoid type. + typedef typename Monoid::value_type value_type; ///< The value type. + typedef typename Monoid::view_type view_type; ///< The view type. private: typedef internal::reducer_set_get<value_type, view_type> set_get; - + reducer(const reducer&); ///< Disallow copying. reducer& operator=(const reducer&); ///< Disallow assignment. public: - + /** @name Constructors * - * All reducer constructors call the static `construct()` function of the monoid class to - * construct the reducer's monoid and leftmost view. + * All reducer constructors call the static `construct()` function of the + * monoid class to construct the reducer's monoid and leftmost view. * - * The reducer constructor arguments are simply passed through to the construct() function. - * Thus, the constructor parameters accepted by a particular reducer class are determined - * by its monoid class. + * The reducer constructor arguments are simply passed through to the + * construct() function. Thus, the constructor parameters accepted by a + * particular reducer class are determined by its monoid class. */ //@{ /** 0 – 6 const reference parameters. */ //@{ - + reducer() { monoid_type::construct(monoid_ptr(), leftmost_ptr()); @@ -1125,19 +1199,24 @@ class reducer : public internal::reducer_content<Monoid> } template <typename T1, typename T2, typename T3, typename T4, typename T5> - reducer(const T1& x1, const T2& x2, const T3& x3, const T4& x4, const T5& x5) + reducer(const T1& x1, const T2& x2, const T3& x3, const T4& x4, + const T5& x5) { - monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2, x3, x4, x5); + monoid_type::construct(monoid_ptr(), leftmost_ptr(), + x1, x2, x3, x4, x5); } - template <typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> - reducer(const T1& x1, const T2& x2, const T3& x3, const T4& x4, const T5& x5, const T6& x6) + template <typename T1, typename T2, typename T3, typename T4, + typename T5, typename T6> + reducer(const T1& x1, const T2& x2, const T3& x3, const T4& x4, + const T5& x5, const T6& x6) { - monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2, x3, x4, x5, x6); + monoid_type::construct(monoid_ptr(), leftmost_ptr(), + x1, x2, x3, x4, x5, x6); } - + //@} - + /** 1 non-const reference parameter. */ //@{ @@ -1147,7 +1226,7 @@ class reducer : public internal::reducer_content<Monoid> { monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1); } - + //@} /** Destructor. @@ -1164,29 +1243,29 @@ class reducer : public internal::reducer_content<Monoid> * @return A reference to the monoid object belonging to this reducer. */ Monoid& monoid() { return *monoid_ptr(); } - - const Monoid& monoid() const + + const Monoid& monoid() const { return const_cast<reducer*>(this)->monoid(); } //@} //@{ /** Access the current view. * - * Return a reference to the instance of the reducer’s view that was + * Return a reference to the instance of the reducer's view that was * created for the current strand of a parallel computation (and create - * it if it doesn’t already exist). + * it if it doesn't already exist). */ view_type& view() { return base::view(); } const view_type& view() const { return base::view(); } //@} - + /** @name Dereference the reducer to get the view. * - * “Dereferencing” a reducer yields the view for the current strand. The + * "Dereferencing" a reducer yields the view for the current strand. The * view, in turn, acts as a proxy for its contained value, exposing only - * those operations which are consistent with the reducer’s monoid. Thus, - * all modifications of the reducer’s accumulator variable are written as + * those operations which are consistent with the reducer's monoid. Thus, + * all modifications of the reducer's accumulator variable are written as * * *reducer OP ... * @@ -1194,7 +1273,7 @@ class reducer : public internal::reducer_content<Monoid> * * reducer->func(...) * - * (The permitted operations on a reducer’s accumulator are listed in the + * (The permitted operations on a reducer's accumulator are listed in the * documentation for that particular kind of reducer.) * * @note `*r` is a synonym for `r.view()`. Recommended style is to use @@ -1204,7 +1283,7 @@ class reducer : public internal::reducer_content<Monoid> * call attention to the view itself. */ //@{ - + //@{ /** Dereference operator. * @@ -1222,12 +1301,12 @@ class reducer : public internal::reducer_content<Monoid> view_type* operator->() { return &view(); } view_type const* operator->() const { return &view(); } //@} - + //@{ /** Deprecated view access. * - * `r()` is a synonym for `*r` which was used with early versions of Cilk - * reducers. `*r` is now the preferred usage. + * `r()` is a synonym for `*r` which was used with early versions of + * Intel Cilk Plus reducers. `*r` is now the preferred usage. * * @deprecated Use operator*() instead of operator()(). * @@ -1236,9 +1315,9 @@ class reducer : public internal::reducer_content<Monoid> view_type& operator()() { return view(); } view_type const& operator()() const { return view(); } //@} - + //@} - + /** @name Set and get the value. * * These functions are used to set an initial value for the reducer before @@ -1247,25 +1326,25 @@ class reducer : public internal::reducer_content<Monoid> * * @note These functions are completely different from the view * operations that are made available via operator*() and - * operator->(), which are used to _modify_ the reducer’s value + * operator->(), which are used to _modify_ the reducer's value * _during_ the reduction. * - * @warning These functions _can_ be called at any time, and in + * @warning These functions _can_ be called at any time, and in * general, they will refer to the value contained in the view * for the current strand. However, using them other than to - * set the reduction’s initial value or get its final value + * set the reduction's initial value or get its final value * will almost always result in undefined behavior. */ //@{ /** Move a value into the reducer. * - * This function is used to set the initial value of the reducer’s + * This function is used to set the initial value of the reducer's * accumulator variable by either copying or _moving_ the value of @a obj * into it. Moving a value can often be performed in constant time, even * for large container objects, but has the side effect of leaving the - * value of @a obj undefined. (See the description of the - * @ref move_in_wrapper class for a discussion of moving values.) + * value of @a obj undefined. (See the description of the + * @ref move_in_wrapper class for a discussion of moving values.) * * @par Usage * A move_in() call to initialize a reducer is often paired with a @@ -1278,14 +1357,14 @@ class reducer : public internal::reducer_content<Monoid> * * @par Assumptions * - You cannot assume either that this will function will copy its - * value or that it will move it. - * - You must assume that the value of @a obj will be undefined - * after the call to move_in(). + * value or that it will move it. + * - You must assume that the value of @a obj will be undefined + * after the call to move_in(). * - You can assume that move_in() will be at least as efficient as * set_value(), and you should therefore prefer move_in() unless * you need the value of @a obj to be unchanged after the call. * (But you should usually prefer the move-in constructor over a - * move_in() call — see the note below.) + * move_in() call - see the note below.) * * @note The behavior of a default constructor followed by move-in * initialization: @@ -1296,14 +1375,14 @@ class reducer : public internal::reducer_content<Monoid> * @note is not necessarily the same as a move-in constructor: * * reducer<Type> xr(move_in(x)); - * - * @note In particular, when @a Type is a container type with a + * + * @note In particular, when @a Type is a container type with a * non-empty allocator, the move-in constructor will create the * accumulator variable with the same allocator as the input * argument @a x, while the default constructor will create the * accumulator variable with a default allocator. The mismatch of - * allocators in the latter case means that the input argument - * @a x may have to be copied in linear time instead of being + * allocators in the latter case means that the input argument + * @a x may have to be copied in linear time instead of being * moved in constant time. * * @note Best practice is to prefer the move-in constructor over the @@ -1326,13 +1405,13 @@ class reducer : public internal::reducer_content<Monoid> /** Move the value out of the reducer. * - * This function is used to retrieve the final value of the reducer’s + * This function is used to retrieve the final value of the reducer's * accumulator variable by either copying or _moving_ the value of @a obj * into it. Moving a value can often be performed in constant time, even * for large container objects, but has the side effect of leaving the - * value of the reducer’s accumulator variable undefined. (See the - * description of the @ref move_in_wrapper class for a discussion of - * moving values.) + * value of the reducer's accumulator variable undefined. (See the + * description of the @ref move_in_wrapper class for a discussion of + * moving values.) * * @par Usage * A move_in() call to initialize a reducer is often paired with a @@ -1345,15 +1424,15 @@ class reducer : public internal::reducer_content<Monoid> * * @par Assumptions * - You cannot assume either that this will function will copy its - * value or that it will move it. - * - You must assume that the value of the reducer’s accumulator + * value or that it will move it. + * - You must assume that the value of the reducer's accumulator * variable will be undefined after the call to move_out(). * - You can assume that move_out() will be at least as efficient as * get_value(), and you should therefore prefer move_out() unless * you need the accumulator variable to be preserved after the * call. * - * @warning Calling this function other than to retrieve the final + * @warning Calling this function other than to retrieve the final * value of a reduction will almost always result in undefined * behavior. * @@ -1368,7 +1447,7 @@ class reducer : public internal::reducer_content<Monoid> /** Set the value of the reducer. * - * This function sets the initial value of the reducer’s accumulator + * This function sets the initial value of the reducer's accumulator * variable to the value of @a obj. * * @note The behavior of a default constructor followed by @@ -1380,8 +1459,8 @@ class reducer : public internal::reducer_content<Monoid> * @note is not necessarily the same as a value constructor: * * reducer<Type> xr(x); - * - * @note In particular, when @a Type is a container type with a + * + * @note In particular, when @a Type is a container type with a * non-empty allocator, the value constructor will create the * accumulator variable with the same allocator as the input * argument @a x, while the default constructor will create the @@ -1391,7 +1470,7 @@ class reducer : public internal::reducer_content<Monoid> * for a reduction will almost always result in undefined * behavior. * - * @param obj The object containing the value that will be copied into + * @param obj The object containing the value that will be copied into * the reducer. * * @post The reducer contains a copy of the value in @a obj. @@ -1402,10 +1481,10 @@ class reducer : public internal::reducer_content<Monoid> /** Get the value of the reducer. * - * This function gets the final value of the reducer’s accumulator + * This function gets the final value of the reducer's accumulator * variable. * - * @warning Calling this function other than to retrieve the final + * @warning Calling this function other than to retrieve the final * value of a reduction will almost always result in undefined * behavior. * @@ -1413,9 +1492,9 @@ class reducer : public internal::reducer_content<Monoid> * * @see move_out() */ - typename set_get::get_value_type get_value() const + typename set_get::return_type_for_get_value get_value() const { return set_get::get_value(view()); } - + //@} /** Implicit downcast to legacy reducer wrapper, if any. @@ -1452,137 +1531,148 @@ using stub::reducer; /** @page page_reducers_in_c Creating and Using Reducers in C * * @tableofcontents - * - * The Cilk runtime supports reducers written in C as well as in C++. The basic logic is the - * same, but the implementation details are very different. The C++ reducer implementation uses - * templates heavily to create very generic components. The C reducer implementation uses - * macros, which are a much blunter instrument. The most immediate consequence is that the - * monoid/view/reducer architecture is mostly implicit rather than explicit in C reducers. - * + * + * The Intel Cilk Plus runtime supports reducers written in C as well as in C++. The + * basic logic is the same, but the implementation details are very + * different. The C++ reducer implementation uses templates heavily to create + * very generic components. The C reducer implementation uses macros, which + * are a much blunter instrument. The most immediate consequence is that the + * monoid/view/reducer architecture is mostly implicit rather than explicit + * in C reducers. + * * @section reducers_c_overview Overview of Using Reducers in C - * + * * The basic usage pattern for C reducers is: - * + * * 1. Create and initialize a reducer object. - * 2. Tell the Cilk runtime about the reducer. + * 2. Tell the Intel Cilk Plus runtime about the reducer. * 3. Update the value contained in the reducer in a parallel computation. - * 4. Tell the Cilk runtime that you are done with the reducer. + * 4. Tell the Intel Cilk Plus runtime that you are done with the reducer. * 5. Retrieve the value from the reducer. - * + * * @subsection reducers_c_creation Creating and Initializing a C Reducer - * + * * The basic pattern for creating and initializing a reducer object in C is - * + * * CILK_C_DECLARE_REDUCER(value-type) reducer-name = * CILK_C_INIT_REDUCER(value-type, * reduce-function, * identity-function, * destroy-function, * initial-value); - * - * This is simply an initialized definition of a variable named _reducer-name_. The - * @ref CILK_C_DECLARE_REDUCER macro expands to an anonymous `struct` declaration for a reducer - * object containing a view of type _value-type_, and the @ref CILK_C_INIT_REDUCER macro - * expands to a struct initializer. - * + * + * This is simply an initialized definition of a variable named + * _reducer-name_. The @ref CILK_C_DECLARE_REDUCER macro expands to an + * anonymous `struct` declaration for a reducer object containing a view of + * type _value-type_, and the @ref CILK_C_INIT_REDUCER macro expands to a + * struct initializer. + * * @subsection reducers_c_reduce_func Reduce Functions - * - * The reduce function for a reducer is called when a parallel execution strand terminates, to - * combine the values computed by the terminating strand and the strand to its left. It takes - * three arguments: - * - * - `void* reducer` — the address of the reducer. - * - `void* left` — the address of the value for the left strand. - * - `void* right` — the address of the value for the right (terminating) strand. - * - * It must apply the reducer’s reduction operation to the `left` and `right` values, leaving - * the result in the `left` value. The `right` value is undefined after the reduce function - * call. - * + * + * The reduce function for a reducer is called when a parallel execution + * strand terminates, to combine the values computed by the terminating + * strand and the strand to its left. It takes three arguments: + * + * - `void* reducer` - the address of the reducer. + * - `void* left` - the address of the value for the left strand. + * - `void* right` - the address of the value for the right (terminating) + * strand. + * + * It must apply the reducer's reduction operation to the `left` and `right` + * values, leaving the result in the `left` value. The `right` value is + * undefined after the reduce function call. + * * @subsection reducers_c_identity_func Identity Functions - * - * The identity function for a reducer is called when a parallel execution strand begins, to - * initialize its value to the reducer’s identity value. It takes two arguments: - * - * - `void* reducer` — the address of the reducer. - * - `void* v` — the address of a freshly allocated block of memory of size + * + * The identity function for a reducer is called when a parallel execution + * strand begins, to initialize its value to the reducer's identity value. It + * takes two arguments: + * + * - `void* reducer` - the address of the reducer. + * - `void* v` - the address of a freshly allocated block of memory of size * `sizeof(value-type)`. - * - * It must initialize the memory pointed to by `v` so that it contains the reducer’s identity - * value. - * + * + * It must initialize the memory pointed to by `v` so that it contains the + * reducer's identity value. + * * @subsection reducers_c_destroy_func Destroy Functions - * - * The destroy function for a reducer is called when a parallel execution strand terminates, to - * do any necessary cleanup before its value is deallocated. It takes two arguments: - * - * - `void* reducer` — the address of the reducer. - * - `void* p` — the address of the value for the terminating strand. - * - * It must release any resources belonging to the value pointed to by `p`, to avoid a resource - * leak when the memory containing the value is deallocated. - * - * The runtime function `__cilkrts_hyperobject_noop_destroy` can be used for the destructor - * function if the reducer’s values do not need any cleanup. - * - * @subsection reducers_c_register Tell the Cilk Runtime About the Reducer - * - * Call the @ref CILK_C_REGISTER_REDUCER macro to register the reducer with the Cilk runtime: - * + * + * The destroy function for a reducer is called when a parallel execution + * strand terminates, to do any necessary cleanup before its value is + * deallocated. It takes two arguments: + * + * - `void* reducer` - the address of the reducer. + * - `void* p` - the address of the value for the terminating strand. + * + * It must release any resources belonging to the value pointed to by `p`, to + * avoid a resource leak when the memory containing the value is deallocated. + * + * The runtime function `__cilkrts_hyperobject_noop_destroy` can be used for + * the destructor function if the reducer's values do not need any cleanup. + * + * @subsection reducers_c_register Tell the Intel Cilk Plus Runtime About the + * Reducer + * + * Call the @ref CILK_C_REGISTER_REDUCER macro to register the reducer with + * the Intel Cilk Plus runtime: + * * CILK_C_REGISTER_REDUCER(reducer-name); - * - * The runtime will manage reducer values for all registered reducers when parallel execution - * strands begin and end. - * + * + * The runtime will manage reducer values for all registered reducers when + * parallel execution strands begin and end. + * * @subsection reducers_c_update Update the Value Contained in the Reducer - * - * The @ref REDUCER_VIEW macro returns a reference to the reducer’s value for the current - * parallel strand: - * + * + * The @ref REDUCER_VIEW macro returns a reference to the reducer's value for + * the current parallel strand: + * * REDUCER_VIEW(reducer-name) = REDUCER_VIEW(reducer-name) OP x; - * - * C++ reducer views restrict access to the wrapped value so that it can only be modified in - * ways consistent with the reducer’s operation. No such protection is provided for C reducers. - * It is - * entirely the responsibility of the user to avoid modifying the value in any - * inappropriate way. - * - * @subsection c_reducers_unregister Tell the Cilk Runtime That You Are Done with the Reducer - * - * When the parallel computation is complete, call the @ref CILK_C_UNREGISTER_REDUCER macro to - * unregister the reducer with the Cilk runtime: - * + * + * C++ reducer views restrict access to the wrapped value so that it can only + * be modified in ways consistent with the reducer's operation. No such + * protection is provided for C reducers. It is entirely the responsibility + * of the user to avoid modifying the value in any inappropriate way. + * + * @subsection c_reducers_unregister Tell the Intel Cilk Plus Runtime That You Are + * Done with the Reducer + * + * When the parallel computation is complete, call the @ref + * CILK_C_UNREGISTER_REDUCER macro to unregister the reducer with the + * Intel Cilk Plus runtime: + * * CILK_C_UNREGISTER_REDUCER(reducer-name); - * + * * The runtime will stop managing reducer values for the reducer. - * + * * @subsection c_reducers_retrieve Retrieve the Value from the Reducer - * - * When the parallel computation is complete, use the @ref REDUCER_VIEW macro to retrieve the - * final value computed by the reducer. - * - * @subsection reducers_c_example_custom Example — Creating and Using a Custom C Reducer - * + * + * When the parallel computation is complete, use the @ref REDUCER_VIEW macro + * to retrieve the final value computed by the reducer. + * + * @subsection reducers_c_example_custom Example - Creating and Using a + * Custom C Reducer + * * The `IntList` type represents a simple list of integers. - * + * * struct _intListNode { * int value; * _intListNode* next; * } IntListNode; * typedef struct { IntListNode* head; IntListNode* tail; } IntList; - * + * * // Initialize a list to be empty * void IntList_init(IntList* list) { list->head = list->tail = 0; } - * + * * // Append an integer to the list - * void IntList_append(IntList* list, int x) - * { + * void IntList_append(IntList* list, int x) + * { * IntListNode* node = (IntListNode*) malloc(sizeof(IntListNode)); * if (list->tail) list->tail->next = node; else list->head = node; * list->tail = node; * } - * - * // Append the right list to the left list, and leave the right list empty + * + * // Append the right list to the left list, and leave the right list + * // empty * void IntList_concat(IntList* left, IntList* right) * { * if (left->head) { @@ -1594,19 +1684,20 @@ using stub::reducer; * } * IntList_init(*right); * } - * - * This code creates a reducer that supports creating an `IntList` by appending values to it. - * + * + * This code creates a reducer that supports creating an `IntList` by + * appending values to it. + * * void identity_IntList(void* reducer, void* list) * { * IntList_init((IntList*)list); * } - * + * * void reduce_IntList(void* reducer, void* left, void* right) * { * IntList_concat((IntList*)left, (IntList*)right); * } - * + * * CILK_C_DECLARE_REDUCER(IntList) my_list_int_reducer = * CILK_C_INIT_REDUCER(IntList, * reduce_int_list, @@ -1620,28 +1711,29 @@ using stub::reducer; * IntList_append(&REDUCER_VIEW(my_int_list_reducer), a[i]); * } * CILK_C_UNREGISTER_REDUCER(my_int_list_reducer); - * + * * IntList result = REDUCER_VIEW(my_int_list_reducer); * * @section reducers_c_predefined Predefined C Reducers * - * Some of the predefined reducer classes in the Cilk library come with a set of predefined - * macros to provide the same capabilities in C. In general, two macros are provided for each - * predefined reducer family: + * Some of the predefined reducer classes in the Intel Cilk Plus library come with + * a set of predefined macros to provide the same capabilities in C. + * In general, two macros are provided for each predefined reducer family: * - * - `CILK_C_REDUCER_operation(reducer-name, type-name, initial-value)` — Declares a - * reducer object named _reducer-name_ with initial value _initial-value_ to perform - * a reduction using the _operation_ on values of the type specified by _type-name_. - * This is the equivalent of the general code described in @ref reducers_c_creation : + * - `CILK_C_REDUCER_operation(reducer-name, type-name, initial-value)` - + * Declares a reducer object named _reducer-name_ with initial value + * _initial-value_ to perform a reduction using the _operation_ on values + * of the type specified by _type-name_. This is the equivalent of the + * general code described in @ref reducers_c_creation : * * CILK_C_DECLARE_REDUCER(type) reducer-name = * CILK_C_INIT_REDUCER(type, ..., initial-value); * - * where _type_ is the C type corresponding to _type_name_. See @ref reducers_c_type_names - * below for the _type-names_ that you can use. + * where _type_ is the C type corresponding to _type_name_. See @ref + * reducers_c_type_names below for the _type-names_ that you can use. * - * - `CILK_C_REDUCER_operation_TYPE(type-name)` — Expands to the `typedef` name for the type - * of the reducer object declared by + * - `CILK_C_REDUCER_operation_TYPE(type-name)` - Expands to the `typedef` + * name for the type of the reducer object declared by * `CILK_C_REDUCER_operation(reducer-name, type-name, initial-value)`. * * See @ref reducers_c_example_predefined. @@ -1651,22 +1743,23 @@ using stub::reducer; * | Operation | Name | Documentation | * |-------------------|---------------|-------------------------------| * | addition | `OPADD` | @ref ReducersAdd | - * | bitwise and | `OPAND` | @ref ReducersAnd | - * | bitwise or | `OPOR` | @ref ReducersOr | - * | bitwise xor | `OPXOR` | @ref ReducersXor | + * | bitwise AND | `OPAND` | @ref ReducersAnd | + * | bitwise OR | `OPOR` | @ref ReducersOr | + * | bitwise XOR | `OPXOR` | @ref ReducersXor | * | multiplication | `OPMUL` | @ref ReducersMul | * | minimum | `MIN` | @ref ReducersMinMax | * | minimum & index | `MIN_INDEX` | @ref ReducersMinMax | - * | maximum | `MIN` | @ref ReducersMinMax | - * | maximum & index | `MIN_INDEX` | @ref ReducersMinMax | - * + * | maximum | `MAX` | @ref ReducersMinMax | + * | maximum & index | `MAX_INDEX` | @ref ReducersMinMax | + * * @subsection reducers_c_type_names Numeric Type Names - * - * The type and function names created by the C reducer definition macros incorporate both the - * reducer kind (`opadd`, `opxor`, etc.) and the value type of the reducer (`int`, `double`, - * etc.). The value type is represented by a _numeric type name_ string. The types supported - * in C reducers, and their corresponding numeric type names, are given in the following table: - * + * + * The type and function names created by the C reducer definition macros + * incorporate both the reducer kind (`opadd`, `opxor`, etc.) and the value + * type of the reducer (`int`, `double`, etc.). The value type is represented + * by a _numeric type name_ string. The types supported in C reducers, and + * their corresponding numeric type names, are given in the following table: + * * | Type | Numeric Type Name | * |-----------------------|-------------------------------| * | `char` | `char` | @@ -1685,8 +1778,9 @@ using stub::reducer; * | `float` | `float` | * | `double` | `double` | * | `long double` | `longdouble` | - * - * @subsection reducers_c_example_predefined Example — Using a Predefined C Reducer + * + * @subsection reducers_c_example_predefined Example - Using a Predefined C + * Reducer * * To compute the sum of all the values in an array of `unsigned int`: * @@ -1699,7 +1793,7 @@ using stub::reducer; * printf("The sum is %u\n", REDUCER_VIEW(sum)); */ - + /** @name C language reducer macros * * These macros are used to declare and work with reducers in C code. @@ -1712,7 +1806,8 @@ using stub::reducer; /** @name Compound identifier macros. * - * These macros are used to construct an identifier by concatenating two or three identifiers. + * These macros are used to construct an identifier by concatenating two or + * three identifiers. */ //@{ @@ -1730,7 +1825,7 @@ using stub::reducer; //@} -/** Compiler-specific keyword for the “type of” operator. +/** Compiler-specific keyword for the "type of" operator. */ #if defined(__GNUC__) && !defined(__INTEL_COMPILER) # define _Typeof __typeof__ @@ -1738,15 +1833,16 @@ using stub::reducer; /** @name Predefined reducer function declaration macros. * - * These macros are used to create the function headers for the identity, reduction, - * and destructor functions for a builtin reducer family. The macro can be followed by - * a semicolon to create a declaration, or by a brace-enclosed body to create a definition. + * These macros are used to create the function headers for the identity, + * reduction, and destructor functions for a builtin reducer family. The + * macro can be followed by a semicolon to create a declaration, or by a + * brace-enclosed body to create a definition. */ //@{ /** Create an identity function header. * - * @note The name of the function’s value pointer parameter will always be `v`. + * @note The name of the function's value pointer parameter will always be `v`. * * @param name The reducer family name. * @param tn The type name. @@ -1758,8 +1854,9 @@ using stub::reducer; * * @param name The reducer family name. * @param tn The type name. - * @param l The name to use for the function’s left value pointer parameter. - * @param r The name to use for the function’s right value pointer parameter. + * @param l The name to use for the function's left value pointer parameter. + * @param r The name to use for the function's right value pointer + * parameter. */ #define __CILKRTS_DECLARE_REDUCER_REDUCE(name,tn,l,r) CILK_EXPORT \ void __CILKRTS_MKIDENT3(name,_reduce_,tn)(void* key, void* l, void* r) @@ -1768,7 +1865,7 @@ using stub::reducer; * * @param name The reducer family name. * @param tn The type name. - * @param p The name to use for the function’s value pointer parameter. + * @param p The name to use for the function's value pointer parameter. */ #define __CILKRTS_DECLARE_REDUCER_DESTROY(name,tn,p) CILK_EXPORT \ void __CILKRTS_MKIDENT3(name,_destroy_,tn)(void* key, void* p) @@ -1784,8 +1881,8 @@ using stub::reducer; /** Declaration of a C reducer structure type. * - * This macro expands into an anonymous structure declaration for a C reducer structure - * which contains a @a Type value. For example: + * This macro expands into an anonymous structure declaration for a C reducer + * structure which contains a @a Type value. For example: * * CILK_C_DECLARE_REDUCER(int) my_add_int_reducer = * CILK_C_INIT_REDUCER(int, …); @@ -1801,27 +1898,30 @@ using stub::reducer; /** Initializer for a C reducer structure. * - * This macro expands into a brace-enclosed structure initializer for a C reducer structure - * that was declared with `CILK_C_DECLARE_REDUCER(Type)`. For example: + * This macro expands into a brace-enclosed structure initializer for a C + * reducer structure that was declared with + * `CILK_C_DECLARE_REDUCER(Type)`. For example: * * CILK_C_DECLARE_REDUCER(int) my_add_int_reducer = - * CILK_C_INIT_REDUCER(int, - * add_int_reduce, - * add_int_identity, + * CILK_C_INIT_REDUCER(int, + * add_int_reduce, + * add_int_identity, * __cilkrts_hyperobject_noop_destroy, * 0); * - * @param Type The type of the value contained in the reducer object. Must be the same as - * the @a Type argument of the CILK_C_DECLARE_REDUCER macro call that created - * the reducer. - * @param Reduce The address of the @ref reducers_c_reduce_func "reduce function" for the + * @param Type The type of the value contained in the reducer object. Must + * be the same as the @a Type argument of the + * CILK_C_DECLARE_REDUCER macro call that created the * reducer. - * @param Identity The address of the @ref reducers_c_identity_func "identity function" for - * the reducer. - * @param Destroy The address of the @ref reducers_c_destroy_func "destroy function" for the - * reducer. - * @param ... The initial value for the reducer. (A single expression if @a Type is a - * scalar type; a list of values if @a Type is a struct or array type.) + * @param Reduce The address of the @ref reducers_c_reduce_func + * "reduce function" for the reducer. + * @param Identity The address of the @ref reducers_c_identity_func + * "identity function" for the reducer. + * @param Destroy The address of the @ref reducers_c_destroy_func + * "destroy function" for the reducer. + * @param ... The initial value for the reducer. (A single expression if + * @a Type is a scalar type; a list of values if @a Type is a + * struct or array type.) * * @see @ref reducers_c_creation */ @@ -1840,10 +1940,10 @@ using stub::reducer; , __VA_ARGS__ \ } -/** Register a reducer with the Cilk runtime. +/** Register a reducer with the Intel Cilk Plus runtime. * - * The runtime will manage reducer values for all registered reducers when parallel execution - * strands begin and end. For example: + * The runtime will manage reducer values for all registered reducers when + * parallel execution strands begin and end. For example: * * CILK_C_REGISTER_REDUCER(my_add_int_reducer); * cilk_for (int i = 0; i != n; ++i) { @@ -1857,10 +1957,10 @@ using stub::reducer; #define CILK_C_REGISTER_REDUCER(Expr) \ __cilkrts_hyper_create(&(Expr).__cilkrts_hyperbase) -/** Unregister a reducer with the Cilk runtime. +/** Unregister a reducer with the Intel Cilk Plus runtime. * - * The runtime will stop managing reducer values for a reducer after it is unregistered. For - * example: + * The runtime will stop managing reducer values for a reducer after it is + * unregistered. For example: * * cilk_for (int i = 0; i != n; ++i) { * … @@ -1876,17 +1976,19 @@ using stub::reducer; /** Get the current view for a reducer. * - * The `REDUCER_VIEW(reducer-name)` returns a reference to the reducer’s value for the - * current parallel strand. This can be used to initialize thevalue of the reducer before it - * is used, to modify the value of the reducer on the current parallel strand, or to retrieve - * the final value of the reducer at the end of the parallel computation. + * The `REDUCER_VIEW(reducer-name)` returns a reference to the reducer's + * value for the current parallel strand. This can be used to initialize the + * value of the reducer before it is used, to modify the value of the reducer + * on the current parallel strand, or to retrieve the final value of the + * reducer at the end of the parallel computation. * * REDUCER_VIEW(my_add_int_reducer) = REDUCER_VIEW(my_add_int_reducer) + x; * - * @note C++ reducer views restrict access to the wrapped value so that it can only be - * modified in ways consistent with the reducer’s operation. No such protection is provided - * for C reducers. It is entirely the responsibility of the user to refrain from modifying the - * value in any inappropriate way. + * @note C++ reducer views restrict access to the wrapped value so that it + * can only be modified in ways consistent with the reducer's operation. No + * such protection is provided for C reducers. It is entirely the + * responsibility of the user to refrain from modifying the value in any + * inappropriate way. * * @param Expr The reducer whose value is to be returned. * |