JezK
Edit File: holder.h
/* * @copyright * Copyright (C) 2011-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. * */ /* * holder.h * * Purpose: hyperobject to provide different views of an object to each * parallel strand. */ #ifndef HOLDER_H_INCLUDED #define HOLDER_H_INCLUDED #include <cilk/reducer.h> #include <memory> #include <utility> #ifdef __cplusplus /* C++ Interface * * Classes: holder<Type> * * Description: * ============ * This component provides a hyperobject that isolates a parallel uses of a * common variable where it is not necessary to preserve changes from * different parallel strands. In effect, a holder acts a bit like * thread-local storage, but has qualities that work better with the * fork-join structure of Cilk. In particular, a holder has the following * qualities: * * - The view of a holder before the first spawn within a function is the same * as the view after each sync (as in the case of a reducer). * - The view of a holder within the first spawned child of a function (or the * first child spawned after a sync) is the same as the view on entry to the * function. * - The view of a holder before entering a _Cilk_for loop is the same as the * view during the first iteration of the loop and the view at the end of * the loop. * - The view of a holder in the continuation of a spawn or in an arbitrary * iteration of a _Cilk_for loop is *non-deterministic*. It is generally * recommended that the holder be explicitly put into a known state in these * situations. * * A holder can be used as an alternative to parameter-passing. They are most * useful for replacing non-local variables without massive refactoring. A * holder takes advantage of the fact that, most of the time, a holder view * does not change after a spawn or from one iteration of a parallel for loop * to the next (i.e., stealing is the exception, not the rule). When the * holder view is a large object that is expensive to construct, this * optimization can save significant time versus creating a separate local * object for each view. In addition, a holder using the "keep last" policy * will have the same value after a sync as the serialization of the same * program. The last quality will often allow the program to avoid * recomputing a value. * * Usage Example: * ============== * Function 'compute()' is a complex function that computes a value using a * memoized algorithm, storing intermediate results in a hash table. Compute * calls several other functions, each of which calls several other functions, * all of which share a global hash table. In all, there are over a dozen * functions with a total of about 60 references to the hash table. *.. * hash_table<int, X> memos; * * void h(const X& x); // Uses memos * * double compute(const X& x) * { * memos.clear(); * // ... * memos[i] = x; * ... * g(i); // Uses memos * // ... * std::for_each(c.begin(), c.end(), h); // Call h for each element of c * } * * int main() * { * const std::size_t ARRAY_SIZE = 1000000; * extern X myArray[ARRAY_SIZE]; * * for (std::size_t i = 0; i < ARRAY_SIZE; ++i) * { * compute(myArray[i]); * } * } *.. * We would like to replace the 'for' loop in 'main' with a 'cilk_for'. * Although the hash table is cleared on entry to each call to 'compute()', * and although the values stored in the hash table are no longer used after * 'compute()' returns, the use of the hash table as a global variable * prevents 'compute()' from being called safely in parallel. One way to do * this would be to make 'memos' a private variable within the cilk_for loop * and pass it down to the actual computation, so that each loop iteration has * its own private copy: *.. * cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i) * { * hash_table<int, X> memos; * compute(myArray[i], memos); * } *.. * The problem with this approach is that it requires changing the signature * of 'compute', 'h', 'g', and every one of the dozen or so functions that * reference 'memos' as well as any function that calls those functions. This * may break the abstraction of 'compute' and other functions, exposing an * implementation detail that was not part of the interface. In addition, the * function 'h' is called through a templated algorithm, 'for_each', which * requires a fixed interface. Finally, there is constructor and destructor * overhead for 'hash_table' each time through the loop. * * The alternative approach is to replace 'memos' with a holder. The holder * would be available to all of the functions involved, but would not cause a * race between parallel loop iterations. In order to make this work, each * use of the 'memos' variable must be (mechanically) replaced by a use of the * holder: *.. * cilk::holder<hash_table<int, X> > memos_h; * * void h(const X& x); // Uses memos_h * * double compute(const X& x) * { * memos_h().clear(); // operator() used to "dereference" the holder * // ... * memos_h()[i] = x; // operator() used to "dereference" the holder * ... * g(i); // Uses memos_h * // ... * std::for_each(c.begin(), c.end(), h); // Call h for each element of c * } *.. * Note that each reference to the holder must be modified with an empty pair * of parenthesis. This syntax is needed because there is no facility in C++ * for a "smart reference" that would allow 'memos_h' to be a perfect * replacement for 'memos'. One way that a user can avoid this syntax change * is to wrap the holder in a class that has the same inteface as * 'hash_table' but redirects all calls to the holder: *.. * template <typename K, typename V> * class hash_table_holder * { * private: * cilk::holder<hash_table<K, V> > m_holder; * public: * void clear() { m_holder().clear(); } * V& operator[](const K& x) { return m_holder()[x]; } * std::size_t size() const { return m_holder().size(); } * // etc. ... * }; *.. * Using the above wrapper, the original code can be left unchanged except for * replacing 'hash_table' with 'hash_table_holder' and replacing 'for' with * 'cilk_for': *.. * hash_table_holder<int, X> memos; * * void h(const X& x); // Uses memos * * double compute(const X& x) * { * memos.clear(); // Calls hash_table_holder::clear(). * // ... * } *.. * The above changes have no benefit over the use of thread-local storage. * What if one of the functions has a 'cilk_spawn', however? *.. * void h(const X& x) * { * Y y = x.nested(); * double d, w; * if (y) * { * w = cilk_spawn compute_width(y); // May use 'memos' * d = compute_depth(y); // Does not use 'memos' * cilk_sync; * compute(y); // recursive call. Uses 'memos'. * } * } *.. * In the above example, the view of the holder within 'compute_width' is the * same as the view on entry to 'h'. More importantly, the view of the holder * within the recursive call to 'compute' is the same as the view on entry to * 'h', even if a different worker is executing the recursive call. Thus, the * holder view within a Cilk program has useful qualities not found in * thread-local storage. */ namespace cilk { /** * After a sync, the value stored in a holder matches the most recent * value stored into the holder by one of the starnds entering the sync. * The holder policy used to instantiate the holder determines which of * the entering strands determines the final value of the holder. A policy * of 'holder_keep_indeterminate' (the default) is the most efficient, and * results in an indeterminate value depending on the runtime schedule * (see below for more specifics). An indeterminate value after a sync is * often acceptable, especially if the value of the holder is not reused * after the sync. All of the remaining policies retain the value of the * last strand that would be executed in the serialization of the program. * They differ in the mechanism used to move the value from one view to * another. A policy of 'holder_keep_last_copy' moves values by * copy-assignment. A policy of 'holder_keep_last_swap' moves values by * calling 'swap'. A policy of 'holder_keep_last_move' is available only * for compilers that support C++0x rvalue references and moves values by * move-assignment. A policy of 'holder_keep_last' attempts to choose the * most efficient mechanism: member-function 'swap' if the view type * supports it, otherwise move-assignment if supported, otherwise * copy-assignment. (The swap member function for a class that provides * one is almost always as fast or faster than move-assignment or * copy-assignment.) * * The behavior of 'holder_keep_indeterminate', while indeterminate, is * not random and can be used for advanced programming or debugging. With * a policy of 'holder_keep_intermediate', values are never copied or * moved between views. The value of the view after a sync is the same as * the value set in the last spawned child before a steal occurs or the * last value set in the continuation if no steal occurs. Using this * knowledge, a programmer can use a holder to detect the earliest steal * in a piece of code. An indeterminate holder is also useful for keeping * cached data similar to the way some applications might use thread-local * storage. */ enum holder_policy { holder_keep_indeterminate, holder_keep_last, holder_keep_last_copy, holder_keep_last_swap, #ifdef __CILKRTS_RVALUE_REFERENCES holder_keep_last_move #endif }; namespace internal { // Private special-case holder policy using the swap member-function const holder_policy holder_keep_last_member_swap = (holder_policy) (holder_keep_last_swap | 0x10); /* The constant, 'has_member_swap<T>::value', will be 'true' if 'T' * has a non-static member function with prototype 'void swap(T&)'. * The mechanism used to detect 'swap' is the most portable among * present-day compilers, but is not the most robust. Specifically, * the prototype for 'swap' must exactly match 'void swap(T&)'. * Near-matches like a 'swap' function that returns 'int' instead of * 'void' will not be detected. Detection will also fail if 'T' * inherits 'swap' from a base class. */ template <typename T> class has_member_swap { // This technique for detecting member functions was described by // Rani Sharoni in comp.lang.c++.moderated: // http://groups.google.com/group/comp.lang.c++.moderated/msg/2b06b2432fddfb60 // sizeof(notchar) is guaranteed larger than 1 struct notchar { char x[2]; }; // Instantiationg Q<U, &U::swap> will fail unless U contains a // non-static member with prototype 'void swap(U&)'. template <class U, void (U::*)(U&)> struct Q { }; // First 'test' is preferred overload if U::swap exists with the // correct prototype. Second 'test' is preferred overload // otherwise. template <typename U> static char test(Q<U,&U::swap>*); template <typename U> static notchar test(...); public: /// 'value' will be true if T has a non-static member function /// with prototype 'void swap(T&)'. static const bool value = (1 == sizeof(test<T>(0))); }; template <typename T> const bool has_member_swap<T>::value; /** * @brief Utility class for exception safety. * * The constuctor for this class takes a pointer and an allocator and * holds on to them. The destructor deallocates the pointed-to * object, without calling its destructor, typically to recover memory * in case an exception is thrown. The release member clears the * pointer so that the deallocation is prevented, i.e., when the * exception danger has passed. The behavior of this class is similar * to auto_ptr and unique_ptr. */ template <typename Type, typename Allocator = std::allocator<Type> > class auto_deallocator { Allocator m_alloc; Type* m_ptr; // Non-copiable auto_deallocator(const auto_deallocator&); auto_deallocator& operator=(const auto_deallocator&); public: /// Constructor explicit auto_deallocator(Type* p, const Allocator& a = Allocator()) : m_alloc(a), m_ptr(p) { } /// Destructor - free allocated resources ~auto_deallocator() { if (m_ptr) m_alloc.deallocate(m_ptr, 1); } /// Remove reference to resource void release() { m_ptr = 0; } }; /** * Pure-abstract base class to initialize holder views */ template <typename Type, typename Allocator> class init_base { public: virtual ~init_base() { } virtual init_base* clone_self(Allocator& a) const = 0; virtual void delete_self(Allocator& a) = 0; virtual void construct_view(Type* p, Allocator& a) const = 0; }; /** * Class to default-initialize a holder view */ template <typename Type, typename Allocator> class default_init : public init_base<Type, Allocator> { typedef init_base<Type, Allocator> base; /// Private constructor (called from static make() function). default_init() { } // Non-copiable default_init(const default_init&); default_init& operator=(const default_init&); public: // Static factory function static default_init* make(Allocator& a); // Virtual function overrides virtual ~default_init(); virtual base* clone_self(Allocator& a) const; virtual void delete_self(Allocator& a); virtual void construct_view(Type* p, Allocator& a) const; }; template <typename Type, typename Allocator> default_init<Type, Allocator>* default_init<Type, Allocator>::make(Allocator&) { // Return a pointer to a singleton. All instances of this class // are identical, so we need only one. static default_init self; return &self; } template <typename Type, typename Allocator> default_init<Type, Allocator>::~default_init() { } template <typename Type, typename Allocator> init_base<Type, Allocator>* default_init<Type, Allocator>::clone_self(Allocator& a) const { return make(a); } template <typename Type, typename Allocator> void default_init<Type, Allocator>::delete_self(Allocator&) { // Since make() returned a shared singleton, there is nothing to // delete here. } template <typename Type, typename Allocator> void default_init<Type, Allocator>::construct_view(Type* p, Allocator&) const { ::new((void*) p) Type(); // TBD: In a C++0x library, this should be rewritten // std::allocator_traits<Allocator>::construct(a, p); } /** * Class to copy-construct a view from a stored exemplar. */ template <typename Type, typename Allocator> class exemplar_init : public init_base<Type, Allocator> { typedef init_base<Type, Allocator> base; Type* m_exemplar; // Private constructors (called from make() functions). exemplar_init(const Type& val, Allocator& a); #ifdef __CILKRTS_RVALUE_REFERENCES exemplar_init(Type&& val, Allocator& a); #endif // Non-copyiable exemplar_init(const exemplar_init&); exemplar_init& operator=(const exemplar_init&); public: // Static factory functions static exemplar_init* make(const Type& val, Allocator& a = Allocator()); #ifdef __CILKRTS_RVALUE_REFERENCES static exemplar_init* make(Type&& val, Allocator& a = Allocator()); #endif // Virtual function overrides virtual ~exemplar_init(); virtual base* clone_self(Allocator& a) const; virtual void delete_self(Allocator& a); virtual void construct_view(Type* p, Allocator& a) const; }; template <typename Type, typename Allocator> exemplar_init<Type, Allocator>::exemplar_init(const Type& val, Allocator& a) { m_exemplar = a.allocate(1); auto_deallocator<Type, Allocator> guard(m_exemplar, a); a.construct(m_exemplar, val); guard.release(); } #ifdef __CILKRTS_RVALUE_REFERENCES template <typename Type, typename Allocator> exemplar_init<Type, Allocator>::exemplar_init(Type&& val, Allocator& a) { m_exemplar = a.allocate(1); auto_deallocator<Type, Allocator> guard(m_exemplar, a); a.construct(m_exemplar, std::forward<Type>(val)); guard.release(); } #endif template <typename Type, typename Allocator> exemplar_init<Type, Allocator>* exemplar_init<Type, Allocator>::make(const Type& val, Allocator& a) { typedef typename Allocator::template rebind<exemplar_init>::other self_alloc_t; self_alloc_t alloc(a); exemplar_init *self = alloc.allocate(1); auto_deallocator<exemplar_init, self_alloc_t> guard(self, alloc); // Don't use allocator to construct self. Allocator should be // used only on elements of type 'Type'. ::new((void*) self) exemplar_init(val, a); guard.release(); return self; } #ifdef __CILKRTS_RVALUE_REFERENCES template <typename Type, typename Allocator> exemplar_init<Type, Allocator>* exemplar_init<Type, Allocator>::make(Type&& val, Allocator& a) { typedef typename Allocator::template rebind<exemplar_init>::other self_alloc_t; self_alloc_t alloc(a); exemplar_init *self = alloc.allocate(1); auto_deallocator<exemplar_init, self_alloc_t> guard(self, alloc); // Don't use allocator to construct self. Allocator should be // used only on elements of type 'Type'. ::new((void*) self) exemplar_init(std::forward<Type>(val), a); guard.release(); return self; } #endif template <typename Type, typename Allocator> exemplar_init<Type, Allocator>::~exemplar_init() { // Called only by delete_self, which deleted the exemplar using an // allocator. __CILKRTS_ASSERT(0 == m_exemplar); } template <typename Type, typename Allocator> init_base<Type, Allocator>* exemplar_init<Type, Allocator>::clone_self(Allocator& a) const { return make(*m_exemplar, a); } template <typename Type, typename Allocator> void exemplar_init<Type, Allocator>::delete_self(Allocator& a) { typename Allocator::template rebind<exemplar_init>::other alloc(a); a.destroy(m_exemplar); a.deallocate(m_exemplar, 1); m_exemplar = 0; this->~exemplar_init(); alloc.deallocate(this, 1); } template <typename Type, typename Allocator> void exemplar_init<Type, Allocator>::construct_view(Type* p, Allocator& a) const { a.construct(p, *m_exemplar); // TBD: In a C++0x library, this should be rewritten // std::allocator_traits<Allocator>::construct(a, p, *m_exemplar); } /** * Class to construct a view using a stored functor. The functor, * 'f', must be be invokable using the expression 'Type x = f()'. */ template <typename Func, typename Allocator> class functor_init : public init_base<typename Allocator::value_type, Allocator> { typedef typename Allocator::value_type value_type; typedef init_base<value_type, Allocator> base; typedef typename Allocator::template rebind<Func>::other f_alloc; Func *m_functor; /// Private constructors (called from make() functions functor_init(const Func& f, Allocator& a); #ifdef __CILKRTS_RVALUE_REFERENCES functor_init(Func&& f, Allocator& a); #endif // Non-copiable functor_init(const functor_init&); functor_init& operator=(const functor_init&); public: // Static factory functions static functor_init* make(const Func& val, Allocator& a = Allocator()); #ifdef __CILKRTS_RVALUE_REFERENCES static functor_init* make(Func&& val, Allocator& a = Allocator()); #endif // Virtual function overrides virtual ~functor_init(); virtual base* clone_self(Allocator& a) const; virtual void delete_self(Allocator& a); virtual void construct_view(value_type* p, Allocator& a) const; }; /// Specialization to strip off reference from 'Func&'. template <typename Func, typename Allocator> struct functor_init<Func&, Allocator> : functor_init<Func, Allocator> { }; /// Specialization to strip off reference and cvq from 'const Func&'. template <typename Func, typename Allocator> struct functor_init<const Func&, Allocator> : functor_init<Func, Allocator> { }; template <typename Func, typename Allocator> functor_init<Func, Allocator>::functor_init(const Func& f, Allocator& a) { f_alloc alloc(a); m_functor = alloc.allocate(1); auto_deallocator<Func, f_alloc> guard(m_functor, alloc); alloc.construct(m_functor, f); guard.release(); } #ifdef __CILKRTS_RVALUE_REFERENCES template <typename Func, typename Allocator> functor_init<Func, Allocator>::functor_init(Func&& f, Allocator& a) { f_alloc alloc(a); m_functor = alloc.allocate(1); auto_deallocator<Func, f_alloc> guard(m_functor, alloc); alloc.construct(m_functor, std::forward<Func>(f)); guard.release(); } #endif template <typename Func, typename Allocator> functor_init<Func, Allocator>* functor_init<Func, Allocator>::make(const Func& f, Allocator& a) { typedef typename Allocator::template rebind<functor_init>::other self_alloc_t; self_alloc_t alloc(a); functor_init *self = alloc.allocate(1); auto_deallocator<functor_init, self_alloc_t> guard(self, alloc); // Don't use allocator to construct self. Allocator should be // used only on elements of type 'Func'. ::new((void*) self) functor_init(f, a); guard.release(); return self; } #ifdef __CILKRTS_RVALUE_REFERENCES template <typename Func, typename Allocator> functor_init<Func, Allocator>* functor_init<Func, Allocator>::make(Func&& f, Allocator& a) { typedef typename Allocator::template rebind<functor_init>::other self_alloc_t; self_alloc_t alloc(a); functor_init *self = alloc.allocate(1); auto_deallocator<functor_init, self_alloc_t> guard(self, alloc); // Don't use allocator to construct self. Allocator should be // used only on elements of type 'Func'. ::new((void*) self) functor_init(std::forward<Func>(f), a); guard.release(); return self; } #endif template <typename Func, typename Allocator> functor_init<Func, Allocator>::~functor_init() { // Called only by delete_self, which deleted the functor using an // allocator. __CILKRTS_ASSERT(0 == m_functor); } template <typename Func, typename Allocator> init_base<typename Allocator::value_type, Allocator>* functor_init<Func, Allocator>::clone_self(Allocator& a) const { return make(*m_functor, a); } template <typename Func, typename Allocator> inline void functor_init<Func, Allocator>::delete_self(Allocator& a) { typename Allocator::template rebind<functor_init>::other alloc(a); f_alloc fa(a); fa.destroy(m_functor); fa.deallocate(m_functor, 1); m_functor = 0; this->~functor_init(); alloc.deallocate(this, 1); } template <typename Func, typename Allocator> void functor_init<Func, Allocator>::construct_view(value_type* p, Allocator& a) const { a.construct(p, (*m_functor)()); // In C++0x, the above should be written // std::allocator_traits<Allocator>::construct(a, p, m_functor()); } /** * Functor called to reduce a holder */ template <typename Type, holder_policy Policy> struct holder_reduce_functor; /** * Specialization to keep the left (first) value. */ template <typename Type> struct holder_reduce_functor<Type, holder_keep_indeterminate> { void operator()(Type* left, Type* right) const { } }; /** * Specialization to copy-assign from the right (last) value. */ template <typename Type> struct holder_reduce_functor<Type, holder_keep_last_copy> { void operator()(Type* left, Type* right) const { *left = *right; } }; /* * Specialization to keep the right (last) value via swap. */ template <typename Type> struct holder_reduce_functor<Type, holder_keep_last_swap> { void operator()(Type* left, Type* right) const { using std::swap; swap(*left, *right); } }; #ifdef __CILKRTS_RVALUE_REFERENCES /* * Specialization to move-assign from the right (last) value. */ template <typename Type> struct holder_reduce_functor<Type, holder_keep_last_move> { void operator()(Type* left, Type* right) const { *left = std::move(*right); } }; #endif /* * Specialization to keep the right (last) value via the swap member * function. */ template <typename Type> struct holder_reduce_functor<Type, holder_keep_last_member_swap> { void operator()(Type* left, Type* right) const { left->swap(*right); } }; /* * Specialization to keep the right (last) value by the most efficient * means detectable. */ template <typename Type> struct holder_reduce_functor<Type, holder_keep_last> : holder_reduce_functor<Type, (holder_policy) (has_member_swap<Type>::value ? holder_keep_last_member_swap : #ifdef __CILKRTS_RVALUE_REFERENCES holder_keep_last_move #else holder_keep_last_copy #endif )> { }; } // end namespace internal /** * Monoid for holders. * Allocator type is required to be thread-safe. */ template <typename Type, holder_policy Policy = holder_keep_indeterminate, typename Allocator = std::allocator<Type> > class holder_monoid : public monoid_base<Type> { // Allocator is mutable because the copy of the monoid inside the // reducer is const (to avoid races on the shared state). However, // the allocator is required to be thread-safe, so it is ok (and // necessary) to modify. mutable Allocator m_allocator; internal::init_base<Type, Allocator> *m_initializer; public: /// This constructor uses default-initialization for both the leftmost /// view and each identity view. holder_monoid(const Allocator& a = Allocator()) : m_allocator(a) , m_initializer( internal::default_init<Type, Allocator>::make(m_allocator)) { } /// These constructors use 'val' as an exemplar to copy-construct both /// the leftmost view and each identity view. holder_monoid(const Type& val, const Allocator& a = Allocator()) : m_allocator(a) , m_initializer(internal::exemplar_init<Type, Allocator>::make( val, m_allocator)) { } /// This constructor uses 'f' as a functor to construct both /// the leftmost view and each identity view. template <typename Func> holder_monoid(const Func& f, const Allocator& a = Allocator()) : m_allocator(a) , m_initializer( internal::functor_init<Func, Allocator>::make(f,m_allocator)) { } /// Copy constructor holder_monoid(const holder_monoid& rhs) : m_allocator(rhs.m_allocator) , m_initializer(rhs.m_initializer->clone_self(m_allocator)) { } /// "Extended" copy constructor with allocator holder_monoid(const holder_monoid& rhs, const Allocator& a) : m_allocator(a) , m_initializer(rhs.m_initializer->clone_self(m_allocator)) { } #ifdef __CILKRTS_RVALUE_REFERENCES /// Move constructor holder_monoid(holder_monoid&& rhs) : m_allocator(rhs.m_allocator) , m_initializer(rhs.m_initializer) { rhs.m_initializer = internal::default_init<Type, Allocator>::make(m_allocator); } /// "Extended" move constructor with allocator holder_monoid(holder_monoid&& rhs, const Allocator& a) : m_allocator(a) , m_initializer(0) { if (a != rhs.m_allocator) m_initializer = rhs.m_initializer->clone_self(a); else { m_initializer = rhs.m_initializer; rhs.m_initializer = internal::default_init<Type, Allocator>::make(m_allocator); } } #endif /// Destructor ~holder_monoid() { m_initializer->delete_self(m_allocator); } holder_monoid& operator=(const holder_monoid& rhs) { if (this == &rhs) return *this; m_initializer->delete_self(m_allocator); m_initializer = rhs.m_initializer->clone_self(m_allocator); } #ifdef __CILKRTS_RVALUE_REFERENCES holder_monoid& operator=(holder_monoid&& rhs) { if (m_allocator != rhs.m_allocator) // Delegate to copy-assignment on unequal allocators return operator=(static_cast<const holder_monoid&>(rhs)); std::swap(m_initializer, rhs.m_initializer); return *this; } #endif /// Constructs IDENTITY value into the uninitilized '*p' void identity(Type* p) const { m_initializer->construct_view(p, m_allocator); } /// Calls the destructor on the object pointed-to by 'p' void destroy(Type* p) const { m_allocator.destroy(p); } /// Return a pointer to size bytes of raw memory void* allocate(std::size_t s) const { __CILKRTS_ASSERT(sizeof(Type) == s); return m_allocator.allocate(1); } /// Deallocate the raw memory at p void deallocate(void* p) const { m_allocator.deallocate(static_cast<Type*>(p), sizeof(Type)); } void reduce(Type* left, Type* right) const { internal::holder_reduce_functor<Type, Policy>()(left, right); } void swap(holder_monoid& other) { __CILKRTS_ASSERT(m_allocator == other.m_allocator); std::swap(m_initializer, other.m_initializer); } Allocator get_allocator() const { return m_allocator; } }; // Namespace-scope swap template <typename Type, holder_policy Policy, typename Allocator> inline void swap(holder_monoid<Type, Policy, Allocator>& a, holder_monoid<Type, Policy, Allocator>& b) { a.swap(b); } /** * Hyperobject to provide different views of an object to each * parallel strand. */ template <typename Type, holder_policy Policy = holder_keep_indeterminate, typename Allocator = std::allocator<Type> > class holder : public reducer<holder_monoid<Type, Policy, Allocator> > { typedef holder_monoid<Type, Policy, Allocator> monoid_type; typedef reducer<monoid_type> imp; // Return a value of Type constructed using the functor Func. template <typename Func> Type make_value(const Func& f) const { struct obj { union { char buf[sizeof(Type)]; void* align1; double align2; }; obj(const Func& f) { f(static_cast<Type*>(buf)); } ~obj() { static_cast<Type*>(buf)->~Type(); } operator Type&() { return *static_cast<Type*>(buf); } }; return obj(f); } public: /// Default constructor uses default-initialization for both the /// leftmost view and each identity view. holder(const Allocator& alloc = Allocator()) : imp(monoid_type(alloc)) { } /// Construct from an exemplar that is used to initialize both the /// leftmost view and each identity view. holder(const Type& v, const Allocator& alloc = Allocator()) // Alas, cannot use an rvalue reference for 'v' because it is used // twice in the same expression for initializing imp. : imp(monoid_type(v, alloc), v) { } /// Construct from a functor that is used to initialize both the /// leftmost view and each identity view. The functor, 'f', must be be /// invokable using the expression 'Type x = f()'. template <typename Func> holder(const Func& f, const Allocator& alloc = Allocator()) // Alas, cannot use an rvalue for 'f' because it is used twice in // the same expression for initializing imp. : imp(monoid_type(f, alloc), make_value(f)) { } }; } // end namespace cilk #else /* C */ # error Holders are currently available only for C++ #endif /* __cplusplus */ #endif /* HOLDER_H_INCLUDED */