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