path: root/libcilkrts/include/cilk/reducer.h

/*  reducer.h                  -*- C++ -*-
 *
 *  @copyright
 *  Copyright (C) 2009-2013, 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:
 *  
 *    * Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *    * Redistributions in binary form must reproduce the above copyright
 *      notice, this list of conditions and the following disclaimer in
 *      the documentation and/or other materials provided with the
 *      distribution.
 *    * Neither the name of Intel Corporation nor the names of its
 *      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
 *  A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 *  HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 *  INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 *  BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
 *  OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
 *  AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 *  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.
 */
 
/** @file reducer.h
 *
 *  @brief Defines foundation classes for creating Cilk reducers.
 *
 *  @ingroup Reducers
 *
 *  @see @ref pagereducers
 *
 *  @defgroup Reducers Reducers
 */
 
#ifndef REDUCER_H_INCLUDED
#define REDUCER_H_INCLUDED

#include "cilk/hyperobject_base.h"
#include "cilk/metaprogramming.h"

#ifdef __cplusplus

//===================== C++ interfaces ===================================

#include <new>

namespace cilk {

/** 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 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
 *  value objects and restricts access to their operations.
 *
 *  @tparam Value   The value type for the monoid.
 *  @tparam View    An optional view class that serves as a proxy for the value
 *                  type.
 *
 *  @see monoid_with_view
 */
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 { 
        /** Should reducers created with this monoid be aligned?
         *
         *  @details
         *  “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 
         *  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 
         *  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.)
         */
        align_reducer = false 
    };
    
    /** Destroy 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
     *  initialization.
     *
     *  @param s    The number of bytes of memory to allocate.
     *  @return     An untyped pointer to the allocated memory.
     */
    void* allocate(size_t s) const { return operator new(s); }

    /** Deallocate raw memory. Deallocates the memory pointed to by @a p 
     *  without doing any destruction.
     *
     *  @param p    Pointer to the memory to be deallocated.
     *
     *  @pre        @a p points to a block of memory that was allocated by a
     *              call to allocate().
     */
    void deallocate(void* p) const { operator delete(p); }

    /** Create 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 
     *              @a View object.
     *
     *  @post       The memory pointed to by @a p contains a @a View object that
     *              represents the default value of the @a View type.
     *
     *  @deprecated This function constructs the @a View object with its default
     *              constructor, which will often, but not always, yield the
     *              appropriate identity value. Monoid classes should declare
     *              their identity function explicitly, rather than relying on
     *              this default definition.
     */
    void identity(View* p) const { new ((void*) p) View(); }
    
    
    /** @name Construct 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() 
     *  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 
     *  additional arguments to the construct() function (after the monoid
     *  and view addresses).
     *
     *  Any 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.
     */
    //@{
    
    template <typename Monoid>
    static void construct(Monoid* monoid, View* view)
        { provisional( new ((void*)monoid) Monoid() ).confirm_if( 
            (monoid->identity(view), view) ); }

    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) ); }

    template <typename Monoid, typename T1, typename T2>
    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) ); }

    template <typename Monoid, typename T1, typename T2, typename T3>
    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) ); }

    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, 
                            const T4& x4)
        { provisional( new ((void*)monoid) Monoid() ).confirm_if( 
            new ((void*)view) View(x1, x2, x3, x4) ); }

    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, 
                            const T4& x4, const T5& x5)
        { provisional( new ((void*)monoid) Monoid() ).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.
     */
    //@{
    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) ); }
    //@}

    /** Copy-construct the monoid, and pass zero to four const reference
     *  arguments to the view constructor.
     */
    //@{

    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() ); }

    template <typename Monoid, typename T1>
    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) ); }
        
    template <typename Monoid, typename T1, typename T2>
    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) ); }
        
    template <typename Monoid, typename T1, typename T2, typename T3>
    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) );
    }
        
    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, 
                            const T4& x4)
    {
        provisional( new ((void*)monoid) Monoid(m) ).confirm_if(
            new ((void*)view) View(x1, x2, x3, x4) );
    }
        
    //@}
    
    //@}
};


/** Monoid class that gets its value type and identity and reduce operations
 *  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
 *  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.
 *
 *  monoid_with_view is a subclass of @ref monoid_base that gets its value type
 *  and its identity and reduction operations from its view class. No
 *  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
 *  monoid_with_view or one of its subclasses.
 *  
 *  The view class `View` of a monoid_with_view must provide the following public definitions:
 *
 *  Definition                       | Meaning
 *  ---------------------------------|--------
 *  `value_type`                     | a typedef of the value type for the reduction
 *  `View()`                         | a default constructor which constructs the identity value for the reduction
 *  `void reduce(const View* other)` | a member function which applies the reduction operation to the values of `this` view and the `other` view, leaving the result as the value of `this` view, and leaving the value of the `other` view undefined (but valid)
 *
 *  @tparam View    The view class for the monoid.
 *  @tparam Align   If true, reducers instantiated on this monoid will be
 *                  cache-aligned. By default, library reducers (unlike legacy
 *                  library reducer _wrappers_) are aligned only as required by
 *                  contents.
 */
template <class View, bool Align = false>
class monoid_with_view : public monoid_base<typename View::value_type, View>
{
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
     *  default constructor.
     *
     *  @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(); }
    
    /** Reduce the values of two views.
     *
     *  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.
     *  @param  right   The right operand of the reduce operation.
     *  @post           The left view contains the result of the reduce
     *                  operation, and the right view is undefined.
     */
    void reduce(View* left, View* right) const { left->reduce(right); }
};


/** Base class for simple views with (usually) scalar values.
 *
 *  The scalar_view class is intended as a base class which provides about half
 *  of the required definitions for simple views. It defines the `value_type`
 *  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 
 *  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.
 *
 *  @tparam Type    The type of value wrapped by the view.
 */
template <typename Type>
class scalar_view
{
protected:
    Type m_value;       ///< The wrapped accumulator variable.

public:
    /** Value type definition required by @ref monoid_with_view.
     */
    typedef Type value_type;
    
    /** Default constructor.
     */
    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.
     */
    //@{

    /** Set the value of the view.
     */
    void view_move_in(Type& v) { m_value = v; }

    /** Get the value of the view.
     */
    void view_move_out(Type& v) { v = m_value; }

    /** Set the value of the view.
     */
    void view_set_value(const Type& v) { m_value = v; }

    /** Get the value of the view.
     */
    Type const& view_get_value() const { return m_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.
     */
    Type const& view_get_reference() const { return m_value; }
    //@}
};


/** Wrapper class for move-in construction.
 *
 *  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
 *  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 
 *  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
 *  monoid `construct()` function, which passes it to the view constructor)
 *  allows, but does not require, the value pointed to by the wrapper to be
 *  moved into the view instead of copied.
 *
 *  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 
 *  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 
 *  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 
 *  @ref ReducersList "op_list_append" view does have a move-in  constructor,
 *  so
 *
 *      list<int> x;
 *      reducer< op_list_append<int> > xr(move_in(x));
 *
 *  will call the `op_list_append_view(move_in_wrapper<int>)` constructor,
 *  which can `swap` the value of `x` into the view.
 *
 *  @note   Remember that passing the value of a variable to a reducer
 *          constructor using a move_in_wrapper leaves the variable undefined.
 *          You cannot assume that the constructor either will or will not copy
 *          or move the value.
 *
 *  @tparam Type    The type of the wrapped value.
 *
 *  @see cilk::move_in()
 */
template <typename Type>
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 
     *  the implicit conversion, but makes the intent clearer in a move-in
     *  constructor.
     */
    Type& value() const { return *m_pointer; }
};

/** Function to create a move_in_wrapper for a value.
 *
 *  @tparam Type    The type of the argument, which will be the `type` of the 
 *                  created wrapper.
 *
 *  @see move_in_wrapper
 */
template <typename Type>
inline
move_in_wrapper<Type> move_in(Type& ref)
    { return move_in_wrapper<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 
 *          do. This move_in() variant is just provided to allow calling a
 *          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.
 */
template <typename Type>
inline
move_in_wrapper<Type> move_in(const Type& ref)
    { return move_in_wrapper<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 
 *  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 
 *  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. 
 *
 *  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, 
 *  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 
 *  `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 
 *  the corresponding legacy reducer. For example:
 *
 *      template <typename Type>
 *      struct legacy_reducer_downcast< reducer< op_add<Type> > >
 *      {
 *          typedef reducer_opadd<Type> type;
 *      };
 *
 *
 *  @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 
     *  a reducer that has a corresponding legacy reducers.
     */
    struct type : Reducer { };
};


namespace internal {
/// @cond internal

template <typename Value, typename View>
struct reducer_set_get
{
    static View theView;  // Declared but not defined

    // sizeof(notchar) is guaranteed larger than 1
    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);

    enum { GET_VALUE_BY_VALUE =
           (1 == sizeof(check_for_ref(theView.view_get_value(), 0))) } ;

    typedef typename condition<GET_VALUE_BY_VALUE,
                               Value, const Value&>::type get_value_type;

    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); }

    static void set_value(View& view, const Value& v)
        { view.view_set_value(v); }

    static get_value_type 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;

    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 get_value_type get_value(const Value& view) { return view; }
};

/// @endcond


/** Base class defining the data layout that is common to all reducers.
 */
template <typename Monoid> 
class reducer_base {
    typedef typename Monoid::view_type view_type;

    // This makes the reducer a hyper-object. (Partially initialized in
    // the derived reducer_content class.)
    //
    __cilkrts_hyperobject_base      m_base;

    // The monoid is allocated here as raw bytes, and is constructed explicitly
    // by a call to the monoid_type::construct() function in the constructor of
    // the `reducer` subclass.
    //
    storage_for_object<Monoid>      m_monoid;

    // 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:

    /** Constructor.
     *
     *  @param  leftmost    The address of the leftmost view in the reducer.
     */
    reducer_base(char* leftmost) 
    {
        static const cilk_c_monoid c_monoid_initializer = {
            (cilk_c_reducer_reduce_fn_t)     &reduce_wrapper,
            (cilk_c_reducer_identity_fn_t)   &identity_wrapper,
            (cilk_c_reducer_destroy_fn_t)    &destroy_wrapper,
            (cilk_c_reducer_allocate_fn_t)   &allocate_wrapper,
            (cilk_c_reducer_deallocate_fn_t) &deallocate_wrapper
        };

        m_base.__c_monoid = c_monoid_initializer;
        m_base.__flags = 0;
        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())
    {
        // 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 
            // word later in 1.0 reducers than in 0.9  and 1.1 reducers.
            this == *(&m_initialThis + 1)
        );
        __cilkrts_hyper_destroy(&m_base);
    }

    /** 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.
     *
     *  @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() 
    {
        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 
     *  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
     *  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() 
    {
        return *static_cast<view_type *>(__cilkrts_hyper_lookup(&m_base)); 
    }
    
    /** @copydoc 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
     *          reducer layout code. There is never any reason for user code
     *          to call it.
     */
    const void* const & initial_this() const { return m_initialThis; }
};

template <typename Monoid>
void reducer_base<Monoid>::reduce_wrapper(void* r, void* lhs, void* rhs)
{
    Monoid* monoid = static_cast<reducer_base*>(r)->monoid_ptr();
    monoid->reduce(static_cast<view_type*>(lhs),
                         static_cast<view_type*>(rhs));
}

template <typename Monoid>
void reducer_base<Monoid>::identity_wrapper(void* r, void* view)
{
    Monoid* monoid = static_cast<reducer_base*>(r)->monoid_ptr();
    monoid->identity(static_cast<view_type*>(view));
}

template <typename Monoid>
void reducer_base<Monoid>::destroy_wrapper(void* r, void* view)
{
    Monoid* monoid = static_cast<reducer_base*>(r)->monoid_ptr();
    monoid->destroy(static_cast<view_type*>(view));
}

template <typename Monoid>
void* reducer_base<Monoid>::allocate_wrapper(void* r, __STDNS size_t bytes)
{
    Monoid* monoid = static_cast<reducer_base*>(r)->monoid_ptr();
    return monoid->allocate(bytes);
}

template <typename Monoid>
void reducer_base<Monoid>::deallocate_wrapper(void* r, void* view)
{
    Monoid* monoid = static_cast<reducer_base*>(r)->monoid_ptr();
    monoid->deallocate(static_cast<view_type*>(view));
}


/** Base class defining the data members of a reducer.
 *
 *  @tparam Aligned The `m_view` data member, and therefore the entire 
 *                  structure, are cache-line aligned if this parameter
 *                  is `true'.
 */
template <typename Monoid, bool Aligned = Monoid::align_reducer>
class reducer_content;

/** Base class defining the data members of an aligned reducer.
 */
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 
    // 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 
    // after the view, all this means that the leftmost view gets one or more
    // cache lines all to itself, which prevents false sharing.
    //
    __CILKRTS_CACHE_ALIGN
    char m_leftmost[sizeof(view_type)];

    /** Test if the reducer is cache-line-aligned.
     *
     *  Used in assertions.
     */
    bool reducer_is_cache_aligned() const
        { return 0 == ((std::size_t) this & (__CILKRTS_CACHE_LINE__ - 1)); }
        
protected:

    /** Constructor.
     */
    reducer_content() : reducer_base<Monoid>((char*)&m_leftmost)
    {
#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.");
#endif
    /*  "REDUCER SHOULD BE CACHE ALIGNED" ASSERTION.
     *
     *  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 
     *  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
     *      be a slowdown resulting from accesses to the same cache line from
     *      different threads.
     *
     *  2.  The compiler thinks that reducer is cache-line aligned, but it
     *      really isn't. If the reducer is contained in a structure, then the
     *      compiler will believe that the containing structure, and other
     *      fields contained in it, are also more aligned than they really
     *      are. In particular, if the structure contains a numeric array that
     *      is used in a vectorizable loop, then the compiler might generate
     *      invalid vector instructions, resulting in a runtime error.
     *
     *  The compiler will always allocate reducer variables, and structure
     *  variables containing reducers, with their required alignment.
     *  Reducers, and structures containing a reducer, which are allocated
     *  on the heap with `new` will _not_ be properly aligned.
     *
     *  There are three ways that you can fix this assertion failure.
     *
     *  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 
     *      `cilk::aligned_delete()` instead of `new` and `delete`, as follows:
     *
     *          Type* ptr = cilk::aligned_new<Type>(constructor-arguments);
     *          cilk::aligned_delete(ptr);
     *
     *  C.  Define the macro CILK_IGNORE_REDUCER_ALIGNMENT, which will suppress
     *      the assertion check. Do this only if you are comfortable that
     *      problem (2) above will not occur.
     */
    }
};

/** Base class defining the data members of an unaligned reducer.
 */
template <typename Monoid>
class reducer_content<Monoid, false> : public reducer_base<Monoid>
{
    typedef typename Monoid::view_type view_type;      ///< The view type.

    // 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 
    // sharing.
    //
    // The number of bytes to reserve is determined as follows:
    // * Start with the view size.
    // * Round up to a multiple of the cache line size, to get the total size
    //   of the cache lines that will be dedicated to the view.
    // * Add (cache line size - 1) filler bytes to guarantee that the reserved
    //   area will contain a cache-aligned block of the required cache lines,
    //   no matter where the reserved area starts.
    //
    char m_leftmost[
        // View size rounded up to multiple cache lines
        (   (sizeof(view_type) + __CILKRTS_CACHE_LINE__ - 1)
            & ~ (__CILKRTS_CACHE_LINE__ - 1)
        )
        // plus filler to allow alignment.
        + __CILKRTS_CACHE_LINE__ - 1
        ];

protected:

    /** Constructor. Find the first cache-aligned position in the reserved
     *  area, and pass it to the base constructor as the leftmost view 
     *  address.
     */
    reducer_content() : 
        reducer_base<Monoid>(
            (char*)( ((std::size_t)&m_leftmost + __CILKRTS_CACHE_LINE__ - 1)
                     & ~ (__CILKRTS_CACHE_LINE__ - 1) ) )
    {}
};


} // namespace internal


// The __cilkrts_hyperobject_ functions are defined differently depending on
// whether a file is compiled with or without the CILK_STUB option. Therefore,
// reducers compiled in the two modes should be link-time incompatible, so that
// object files compiled with stubbed reducers won't be linked into an
// unstubbed program, or vice versa. We achieve this by putting the reducer
// class definition into the cilk::stub namespace in a stubbed compilation.

#ifdef CILK_STUB
namespace stub {
#endif

/** Reducer class.
 *
 *  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".
 *
 *  @see @ref pagereducers
 */
template <class Monoid>
class reducer : public internal::reducer_content<Monoid>
{
    typedef internal::reducer_content<Monoid> base;
    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.

  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. 
     *
     *  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());
    }

    template <typename T1>
    reducer(const T1& x1)
    {
        monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1);
    }

    template <typename T1, typename T2>
    reducer(const T1& x1, const T2& x2)
    {
        monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2);
    }

    template <typename T1, typename T2, typename T3>
    reducer(const T1& x1, const T2& x2, const T3& x3)
    {
        monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2, x3);
    }

    template <typename T1, typename T2, typename T3, typename T4>
    reducer(const T1& x1, const T2& x2, const T3& x3, const T4& x4)
    {
        monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2, x3, x4);
    }

    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)
    {
        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)
    {
        monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1, x2, x3, x4, x5, x6);
    }
    
    //@}
    
    /** 1 non-const reference parameter.
     */
    //@{

    template <typename T1>
    reducer(T1& x1)
    {
        monoid_type::construct(monoid_ptr(), leftmost_ptr(), x1);
    }
    
    //@}

    /** Destructor.
     */
    __CILKRTS_STRAND_STALE(~reducer())
    {
        leftmost_ptr()->~view_type();
        monoid_ptr()->~monoid_type();
    }

    //@{
    /** Get the monoid.
     *
     *  @return A reference to the monoid object belonging to this reducer.
     */
    Monoid& monoid() { return *monoid_ptr(); }
    
    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 
     *  created for the current strand of a parallel computation (and create
     *  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
     *  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
     *
     *      *reducer OP ...
     *
     *  or
     *
     *      reducer->func(...)
     *
     *  (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
     *          `*r` (or `r->`) in the common case where code is simply
     *          updating the accumulator variable wrapped in the view, and to
     *          use `r.view()` in the unusual case where it is desirable to
     *          call attention to the view itself.
     */
    //@{
    
    //@{
    /** Dereference operator.
     *
     *  @return A reference to the per-strand view instance.
     */
    view_type&       operator*()       { return view(); }
    view_type const& operator*() const { return view(); }
    //@}

    //@{
    /** Pointer operator.
     *
     *  @return A pointer to the per-strand view instance.
     */
    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.
     *
     *  @deprecated Use operator*() instead of operator()().
     *
     *  @return A reference to the per-strand view instance.
     */
    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
     *  starting the reduction, or to get the final value after the reduction
     *  is complete.
     *
     *  @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
     *          _during_ the reduction.
     *
     *  @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
     *              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
     *  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.) 
     *
     *  @par    Usage
     *          A move_in() call to initialize a reducer is often paired with a
     *          move_out() call to get its final value:
     *
     *              reducer<Type> xr;
     *              xr.move_in(x);
     *              … do the reduction …
     *              xr.move_out(x);
     *
     *  @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(). 
     *      -   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.)
     *
     *  @note   The behavior of a default constructor followed by move-in
     *          initialization:
     *
     *              reducer<Type> xr;
     *              xr.move_in(x);
     *
     *  @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 
     *          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 
     *          moved in constant time.
     *
     *  @note   Best practice is to prefer the move-in constructor over the
     *          move-in function unless the move-in function is required for
     *          some specific reason.
     *
     *  @warning    Calling this function other than to set the initial value
     *              for a reduction will almost always result in undefined
     *              behavior.
     *
     *  @param  obj The object containing the value that will be moved into the
     *              reducer.
     *
     *  @post   The reducer contains the value that was initially in @a obj.
     *  @post   The value of @a obj is undefined.
     *
     *  @see set_value()
     */
    void move_in(value_type& obj) { set_get::move_in(view(), obj);}

    /** Move the value out of the reducer.
     *
     *  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.) 
     *
     *  @par    Usage
     *          A move_in() call to initialize a reducer is often paired with a
     *          move_out() call to get its final value:
     *
     *              reducer<Type> xr;
     *              xr.move_in(x);
     *              … do the reduction …
     *              xr.move_out(x);
     *
     *  @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
     *          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 
     *              value of a reduction will almost always result in undefined
     *              behavior.
     *
     *  @param  obj The object that the value of the reducer will be moved into.
     *
     *  @post   @a obj contains the value that was initially in the reducer.
     *  @post   The value of the reducer is undefined.
     *
     *  @see get_value()
     */
    void move_out(value_type& obj) { set_get::move_out(view(), obj); }

    /** Set the value of the reducer.
     *
     *  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
     *          initialization:
     *
     *      reducer<Type> xr;
     *      xr.set_value(x);
     *
     *  @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 
     *          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
     *          accumulator variable with a default allocator.
     *
     *  @warning    Calling this function other than to set the initial value
     *              for a reduction will almost always result in undefined
     *              behavior.
     *
     *  @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.
     *
     *  @see move_in()
     */
    void set_value(const value_type& obj) { set_get::set_value(view(), obj); }

    /** Get the value of the reducer.
     *
     *  This function gets the final value of the reducer’s accumulator
     *  variable.
     *
     *  @warning    Calling this function other than to retrieve the final 
     *              value of a reduction will almost always result in undefined
     *              behavior.
     *
     *  @return     A reference to the value contained in the reducer.
     *
     *  @see move_out()
     */
    typename set_get::get_value_type get_value() const 
        { return set_get::get_value(view()); }
    
    //@}

    /** Implicit downcast to legacy reducer wrapper, if any.
     *
     *  @see legacy_reducer_downcast
     */
    operator typename legacy_reducer_downcast<reducer>::type& ()
    {
        typedef typename legacy_reducer_downcast<reducer>::type downcast_type;
        return *reinterpret_cast<downcast_type*>(this);
    }


    /** Implicit downcast to legacy reducer wrapper, if any.
     *
     *  @see legacy_reducer_downcast
     */
    operator const typename legacy_reducer_downcast<reducer>::type& () const
    {
        typedef typename legacy_reducer_downcast<reducer>::type downcast_type;
        return *reinterpret_cast<const downcast_type*>(this);
    }
};

#ifdef CILK_STUB
} // namespace stub
using stub::reducer;
#endif

} // end namespace cilk

#endif /* __cplusplus */

/** @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.
 *  
 *  @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.
 *  3.  Update the value contained in the reducer in a parallel computation.
 *  4.  Tell the Cilk 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.
 *  
 *  @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.
 *  
 *  @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
 *      `sizeof(value-type)`.
 *  
 *  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:
 *  
 *      CILK_C_REGISTER_REDUCER(reducer-name);
 *  
 *  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:
 *  
 *      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:
 *  
 *      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
 *  
 *  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) 
 *      { 
 *          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
 *      void IntList_concat(IntList* left, IntList* right)
 *      {
 *          if (left->head) {
 *              left->tail->next = right->head;
 *              if (right->tail) left->tail = right->tail;
 *          }
 *          else {
 *              *left = *right;
 *          }
 *          IntList_init(*right);
 *      }
 *      
 *  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,
 *                              identity_int_list,
 *                              __cilkrts_hyperobject_noop_destroy);
 *                              // Initial value omitted //
 *      ListInt_init(&REDUCER_VIEW(my_int_list_reducer));
 *
 *      CILK_C_REGISTER_REDUCER(my_int_list_reducer);
 *      cilk_for (int i = 0; i != n; ++i) {
 *          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:
 *
 *  -   `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.
 *
 *  -   `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.
 *
 *  The predefined C reducers are:
 *
 *  |   Operation       |   Name        |   Documentation               |
 *  |-------------------|---------------|-------------------------------|
 *  |   addition        |   `OPADD`     |   @ref ReducersAdd            |
 *  |   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         |
 *      
 *  @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:
 *  
 *  |   Type                |   Numeric Type Name           |
 *  |-----------------------|-------------------------------|
 *  |  `char`               |  `char`                       |
 *  |  `unsigned char`      |  `uchar`                      |
 *  |  `signed char`        |  `schar`                      |
 *  |  `wchar_t`            |  `wchar_t`                    |
 *  |  `short`              |  `short`                      |
 *  |  `unsigned short`     |  `ushort`                     |
 *  |  `int`                |  `int`                        |
 *  |  `unsigned int`       |  `uint`                       |
 *  |  `unsigned int`       |  `unsigned` (alternate name)  |
 *  |  `long`               |  `long`                       |
 *  |  `unsigned long`      |  `ulong`                      |
 *  |  `long long`          |  `longlong`                   |
 *  |  `unsigned long long` |  `ulonglong`                  |
 *  |  `float`              |  `float`                      |
 *  |  `double`             |  `double`                     |
 *  |  `long double`        |  `longdouble`                 |
 *  
 *  @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`:
 *
 *      CILK_C_REDUCER_OPADD(sum, uint, 0);
 *      CILK_C_REGISTER_REDUCER(sum);
 *      cilk_for(int i = 0; i != n; ++i) {
 *          REDUCER_VIEW(sum) += a[i];
 *      }
 *      CILK_C_UNREGISTER_REDUCER(sum);
 *      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.
 *
 *  @see @ref page_reducers_in_c
 */
 //@{

/// @cond internal

/** @name Compound identifier macros.
 *
 *  These macros are used to construct an identifier by concatenating two or three identifiers.
 */
//@{

/** Expand to an identifier formed by concatenating two identifiers.
 */
#define __CILKRTS_MKIDENT(a,b) __CILKRTS_MKIDENT_IMP(a,b,)

/** Expand to an identifier formed by concatenating three identifiers.
 */
#define __CILKRTS_MKIDENT3(a,b,c) __CILKRTS_MKIDENT_IMP(a,b,c)

/** Helper macro to do the concatenation.
 */
#define __CILKRTS_MKIDENT_IMP(a,b,c) a ## b ## c

//@}

/** Compiler-specific keyword for the “type of” operator.
 */
#if defined(__GNUC__) && !defined(__INTEL_COMPILER)
# define _Typeof __typeof__
#endif

/** @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.
 */
//@{

/** Create an identity function header.
 *
 *  @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.
 */
#define __CILKRTS_DECLARE_REDUCER_IDENTITY(name,tn)  CILK_EXPORT         \
    void __CILKRTS_MKIDENT3(name,_identity_,tn)(void* key, void* v)

/** Create a reduction function header.
 *
 *  @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.
 */
#define __CILKRTS_DECLARE_REDUCER_REDUCE(name,tn,l,r) CILK_EXPORT        \
    void __CILKRTS_MKIDENT3(name,_reduce_,tn)(void* key, void* l, void* r)

/** Create a destructor function header.
 *
 *  @param name The reducer family name.
 *  @param tn   The type name.
 *  @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)

//@}

/// @endcond


/***************************************************************************
 *              Real implementation
 ***************************************************************************/

/** 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:
 *
 *      CILK_C_DECLARE_REDUCER(int) my_add_int_reducer =
 *          CILK_C_INIT_REDUCER(int, …);
 *
 *  @param Type The type of the value contained in the reducer object.
 *
 *  @see @ref reducers_c_creation
 */
#define CILK_C_DECLARE_REDUCER(Type) struct {                      \
        __cilkrts_hyperobject_base   __cilkrts_hyperbase;          \
        __CILKRTS_CACHE_ALIGN Type   value;                        \
    }

/** 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:
 *
 *      CILK_C_DECLARE_REDUCER(int) my_add_int_reducer =
 *          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
 *                  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
 */

#define CILK_C_INIT_REDUCER(Type, Reduce, Identity, Destroy, ...)       \
    {   {   {   Reduce                                                  \
            ,   Identity                                                \
            ,   Destroy                                                 \
            ,   __cilkrts_hyperobject_alloc                             \
            ,   __cilkrts_hyperobject_dealloc                           \
            }                                                           \
        ,   0                                                           \
        ,   __CILKRTS_CACHE_LINE__                                      \
        ,   sizeof(Type)                                                \
        }                                                               \
    ,   __VA_ARGS__                                                     \
    }

/** Register a reducer with the Cilk runtime.
 *
 *  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) {
 *          …
 *      }
 *
 *  @param Expr The reducer to be registered.
 *
 *  @see @ref page_reducers_in_c
 */
#define CILK_C_REGISTER_REDUCER(Expr) \
    __cilkrts_hyper_create(&(Expr).__cilkrts_hyperbase)

/** Unregister a reducer with the Cilk runtime.
 *
 *  The runtime will stop managing reducer values for a reducer after it is unregistered. For
 *  example:
 *
 *      cilk_for (int i = 0; i != n; ++i) {
 *          …
 *      }
 *      CILK_C_UNREGISTER_REDUCER(my_add_int_reducer);
 *
 *  @param Expr The reducer to be unregistered.
 *
 *  @see @ref page_reducers_in_c
 */
#define CILK_C_UNREGISTER_REDUCER(Expr) \
    __cilkrts_hyper_destroy(&(Expr).__cilkrts_hyperbase)

/** 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.
 *
 *      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.
 *
 *  @param Expr The reducer whose value is to be returned.
 *
 *  @see @ref page_reducers_in_c
 */
#define REDUCER_VIEW(Expr) (*(_Typeof((Expr).value)*)               \
    __cilkrts_hyper_lookup(&(Expr).__cilkrts_hyperbase))

//@} C language reducer macros

#endif // CILK_REDUCER_H_INCLUDED