3 * Copyright (C) 2011-2013, Intel Corporation
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
25 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
26 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
29 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
30 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
32 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33 * POSSIBILITY OF SUCH DAMAGE.
40 * Purpose: hyperobject to provide different views of an object to each
44 #ifndef HOLDER_H_INCLUDED
45 #define HOLDER_H_INCLUDED
47 #include <cilk/reducer.h>
55 * Classes: holder<Type>
59 * This component provides a hyperobject that isolates a parallel uses of a
60 * common variable where it is not necessary to preserve changes from
61 * different parallel strands. In effect, a holder acts a bit like
62 * thread-local storage, but has qualities that work better with the
63 * fork-join structure of Cilk. In particular, a holder has the following
66 * - The view of a holder before the first spawn within a function is the same
67 * as the view after each sync (as in the case of a reducer).
68 * - The view of a holder within the first spawned child of a function (or the
69 * first child spawned after a sync) is the same as the view on entry to the
71 * - The view of a holder before entering a _Cilk_for loop is the same as the
72 * view during the first iteration of the loop and the view at the end of
74 * - The view of a holder in the continuation of a spawn or in an arbitrary
75 * iteration of a _Cilk_for loop is *non-deterministic*. It is generally
76 * recommended that the holder be explicitly put into a known state in these
79 * A holder can be used as an alternative to parameter-passing. They are most
80 * useful for replacing non-local variables without massive refactoring. A
81 * holder takes advantage of the fact that, most of the time, a holder view
82 * does not change after a spawn or from one iteration of a parallel for loop
83 * to the next (i.e., stealing is the exception, not the rule). When the
84 * holder view is a large object that is expensive to construct, this
85 * optimization can save significant time versus creating a separate local
86 * object for each view. In addition, a holder using the "keep last" policy
87 * will have the same value after a sync as the serialization of the same
88 * program. The last quality will often allow the program to avoid
89 * recomputing a value.
93 * Function 'compute()' is a complex function that computes a value using a
94 * memoized algorithm, storing intermediate results in a hash table. Compute
95 * calls several other functions, each of which calls several other functions,
96 * all of which share a global hash table. In all, there are over a dozen
97 * functions with a total of about 60 references to the hash table.
99 * hash_table<int, X> memos;
101 * void h(const X& x); // Uses memos
103 * double compute(const X& x)
109 * g(i); // Uses memos
111 * std::for_each(c.begin(), c.end(), h); // Call h for each element of c
116 * const std::size_t ARRAY_SIZE = 1000000;
117 * extern X myArray[ARRAY_SIZE];
119 * for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
121 * compute(myArray[i]);
125 * We would like to replace the 'for' loop in 'main' with a 'cilk_for'.
126 * Although the hash table is cleared on entry to each call to 'compute()',
127 * and although the values stored in the hash table are no longer used after
128 * 'compute()' returns, the use of the hash table as a global variable
129 * prevents 'compute()' from being called safely in parallel. One way to do
130 * this would be to make 'memos' a private variable within the cilk_for loop
131 * and pass it down to the actual computation, so that each loop iteration has
132 * its own private copy:
134 * cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
136 * hash_table<int, X> memos;
137 * compute(myArray[i], memos);
140 * The problem with this approach is that it requires changing the signature
141 * of 'compute', 'h', 'g', and every one of the dozen or so functions that
142 * reference 'memos' as well as any function that calls those functions. This
143 * may break the abstraction of 'compute' and other functions, exposing an
144 * implementation detail that was not part of the interface. In addition, the
145 * function 'h' is called through a templated algorithm, 'for_each', which
146 * requires a fixed interface. Finally, there is constructor and destructor
147 * overhead for 'hash_table' each time through the loop.
149 * The alternative approach is to replace 'memos' with a holder. The holder
150 * would be available to all of the functions involved, but would not cause a
151 * race between parallel loop iterations. In order to make this work, each
152 * use of the 'memos' variable must be (mechanically) replaced by a use of the
155 * cilk::holder<hash_table<int, X> > memos_h;
157 * void h(const X& x); // Uses memos_h
159 * double compute(const X& x)
161 * memos_h().clear(); // operator() used to "dereference" the holder
163 * memos_h()[i] = x; // operator() used to "dereference" the holder
165 * g(i); // Uses memos_h
167 * std::for_each(c.begin(), c.end(), h); // Call h for each element of c
170 * Note that each reference to the holder must be modified with an empty pair
171 * of parenthesis. This syntax is needed because there is no facility in C++
172 * for a "smart reference" that would allow 'memos_h' to be a perfect
173 * replacement for 'memos'. One way that a user can avoid this syntax change
174 * is to wrap the holder in a class that has the same inteface as
175 * 'hash_table' but redirects all calls to the holder:
177 * template <typename K, typename V>
178 * class hash_table_holder
181 * cilk::holder<hash_table<K, V> > m_holder;
183 * void clear() { m_holder().clear(); }
184 * V& operator[](const K& x) { return m_holder()[x]; }
185 * std::size_t size() const { return m_holder().size(); }
189 * Using the above wrapper, the original code can be left unchanged except for
190 * replacing 'hash_table' with 'hash_table_holder' and replacing 'for' with
193 * hash_table_holder<int, X> memos;
195 * void h(const X& x); // Uses memos
197 * double compute(const X& x)
199 * memos.clear(); // Calls hash_table_holder::clear().
203 * The above changes have no benefit over the use of thread-local storage.
204 * What if one of the functions has a 'cilk_spawn', however?
212 * w = cilk_spawn compute_width(y); // May use 'memos'
213 * d = compute_depth(y); // Does not use 'memos'
215 * compute(y); // recursive call. Uses 'memos'.
219 * In the above example, the view of the holder within 'compute_width' is the
220 * same as the view on entry to 'h'. More importantly, the view of the holder
221 * within the recursive call to 'compute' is the same as the view on entry to
222 * 'h', even if a different worker is executing the recursive call. Thus, the
223 * holder view within a Cilk program has useful qualities not found in
224 * thread-local storage.
230 * After a sync, the value stored in a holder matches the most recent
231 * value stored into the holder by one of the starnds entering the sync.
232 * The holder policy used to instantiate the holder determines which of
233 * the entering strands determines the final value of the holder. A policy
234 * of 'holder_keep_indeterminate' (the default) is the most efficient, and
235 * results in an indeterminate value depending on the runtime schedule
236 * (see below for more specifics). An indeterminate value after a sync is
237 * often acceptable, especially if the value of the holder is not reused
238 * after the sync. All of the remaining policies retain the value of the
239 * last strand that would be executed in the serialization of the program.
240 * They differ in the mechanism used to move the value from one view to
241 * another. A policy of 'holder_keep_last_copy' moves values by
242 * copy-assignment. A policy of 'holder_keep_last_swap' moves values by
243 * calling 'swap'. A policy of 'holder_keep_last_move' is available only
244 * for compilers that support C++0x rvalue references and moves values by
245 * move-assignment. A policy of 'holder_keep_last' attempts to choose the
246 * most efficient mechanism: member-function 'swap' if the view type
247 * supports it, otherwise move-assignment if supported, otherwise
248 * copy-assignment. (The swap member function for a class that provides
249 * one is almost always as fast or faster than move-assignment or
252 * The behavior of 'holder_keep_indeterminate', while indeterminate, is
253 * not random and can be used for advanced programming or debugging. With
254 * a policy of 'holder_keep_intermediate', values are never copied or
255 * moved between views. The value of the view after a sync is the same as
256 * the value set in the last spawned child before a steal occurs or the
257 * last value set in the continuation if no steal occurs. Using this
258 * knowledge, a programmer can use a holder to detect the earliest steal
259 * in a piece of code. An indeterminate holder is also useful for keeping
260 * cached data similar to the way some applications might use thread-local
264 holder_keep_indeterminate
,
266 holder_keep_last_copy
,
267 holder_keep_last_swap
,
268 #ifdef __CILKRTS_RVALUE_REFERENCES
269 holder_keep_last_move
275 // Private special-case holder policy using the swap member-function
276 const holder_policy holder_keep_last_member_swap
=
277 (holder_policy
) (holder_keep_last_swap
| 0x10);
279 /* The constant, 'has_member_swap<T>::value', will be 'true' if 'T'
280 * has a non-static member function with prototype 'void swap(T&)'.
281 * The mechanism used to detect 'swap' is the most portable among
282 * present-day compilers, but is not the most robust. Specifically,
283 * the prototype for 'swap' must exactly match 'void swap(T&)'.
284 * Near-matches like a 'swap' function that returns 'int' instead of
285 * 'void' will not be detected. Detection will also fail if 'T'
286 * inherits 'swap' from a base class.
288 template <typename T
>
289 class has_member_swap
291 // This technique for detecting member functions was described by
292 // Rani Sharoni in comp.lang.c++.moderated:
293 // http://groups.google.com/group/comp.lang.c++.moderated/msg/2b06b2432fddfb60
295 // sizeof(notchar) is guaranteed larger than 1
296 struct notchar
{ char x
[2]; };
298 // Instantiationg Q<U, &U::swap> will fail unless U contains a
299 // non-static member with prototype 'void swap(U&)'.
300 template <class U
, void (U::*)(U
&)> struct Q
{ };
302 // First 'test' is preferred overload if U::swap exists with the
303 // correct prototype. Second 'test' is preferred overload
305 template <typename U
> static char test(Q
<U
,&U::swap
>*);
306 template <typename U
> static notchar
test(...);
309 /// 'value' will be true if T has a non-static member function
310 /// with prototype 'void swap(T&)'.
311 static const bool value
= (1 == sizeof(test
<T
>(0)));
314 template <typename T
> const bool has_member_swap
<T
>::value
;
317 * @brief Utility class for exception safety.
319 * The constuctor for this class takes a pointer and an allocator and
320 * holds on to them. The destructor deallocates the pointed-to
321 * object, without calling its destructor, typically to recover memory
322 * in case an exception is thrown. The release member clears the
323 * pointer so that the deallocation is prevented, i.e., when the
324 * exception danger has passed. The behavior of this class is similar
325 * to auto_ptr and unique_ptr.
327 template <typename Type
, typename Allocator
= std::allocator
<Type
> >
328 class auto_deallocator
334 auto_deallocator(const auto_deallocator
&);
335 auto_deallocator
& operator=(const auto_deallocator
&);
339 explicit auto_deallocator(Type
* p
, const Allocator
& a
= Allocator())
340 : m_alloc(a
), m_ptr(p
) { }
342 /// Destructor - free allocated resources
343 ~auto_deallocator() { if (m_ptr
) m_alloc
.deallocate(m_ptr
, 1); }
345 /// Remove reference to resource
346 void release() { m_ptr
= 0; }
350 * Pure-abstract base class to initialize holder views
352 template <typename Type
, typename Allocator
>
356 virtual ~init_base() { }
357 virtual init_base
* clone_self(Allocator
& a
) const = 0;
358 virtual void delete_self(Allocator
& a
) = 0;
359 virtual void construct_view(Type
* p
, Allocator
& a
) const = 0;
363 * Class to default-initialize a holder view
365 template <typename Type
, typename Allocator
>
366 class default_init
: public init_base
<Type
, Allocator
>
368 typedef init_base
<Type
, Allocator
> base
;
370 /// Private constructor (called from static make() function).
374 default_init(const default_init
&);
375 default_init
& operator=(const default_init
&);
378 // Static factory function
379 static default_init
* make(Allocator
& a
);
381 // Virtual function overrides
382 virtual ~default_init();
383 virtual base
* clone_self(Allocator
& a
) const;
384 virtual void delete_self(Allocator
& a
);
385 virtual void construct_view(Type
* p
, Allocator
& a
) const;
388 template <typename Type
, typename Allocator
>
389 default_init
<Type
, Allocator
>*
390 default_init
<Type
, Allocator
>::make(Allocator
&)
392 // Return a pointer to a singleton. All instances of this class
393 // are identical, so we need only one.
394 static default_init self
;
398 template <typename Type
, typename Allocator
>
399 default_init
<Type
, Allocator
>::~default_init()
403 template <typename Type
, typename Allocator
>
404 init_base
<Type
, Allocator
>*
405 default_init
<Type
, Allocator
>::clone_self(Allocator
& a
) const
410 template <typename Type
, typename Allocator
>
411 void default_init
<Type
, Allocator
>::delete_self(Allocator
&)
413 // Since make() returned a shared singleton, there is nothing to
417 template <typename Type
, typename Allocator
>
419 default_init
<Type
, Allocator
>::construct_view(Type
* p
,
422 ::new((void*) p
) Type();
423 // TBD: In a C++0x library, this should be rewritten
424 // std::allocator_traits<Allocator>::construct(a, p);
428 * Class to copy-construct a view from a stored exemplar.
430 template <typename Type
, typename Allocator
>
431 class exemplar_init
: public init_base
<Type
, Allocator
>
433 typedef init_base
<Type
, Allocator
> base
;
437 // Private constructors (called from make() functions).
438 exemplar_init(const Type
& val
, Allocator
& a
);
439 #ifdef __CILKRTS_RVALUE_REFERENCES
440 exemplar_init(Type
&& val
, Allocator
& a
);
444 exemplar_init(const exemplar_init
&);
445 exemplar_init
& operator=(const exemplar_init
&);
448 // Static factory functions
449 static exemplar_init
* make(const Type
& val
,
450 Allocator
& a
= Allocator());
451 #ifdef __CILKRTS_RVALUE_REFERENCES
452 static exemplar_init
* make(Type
&& val
,
453 Allocator
& a
= Allocator());
456 // Virtual function overrides
457 virtual ~exemplar_init();
458 virtual base
* clone_self(Allocator
& a
) const;
459 virtual void delete_self(Allocator
& a
);
460 virtual void construct_view(Type
* p
, Allocator
& a
) const;
463 template <typename Type
, typename Allocator
>
464 exemplar_init
<Type
, Allocator
>::exemplar_init(const Type
& val
,
467 m_exemplar
= a
.allocate(1);
468 auto_deallocator
<Type
, Allocator
> guard(m_exemplar
, a
);
469 a
.construct(m_exemplar
, val
);
473 #ifdef __CILKRTS_RVALUE_REFERENCES
474 template <typename Type
, typename Allocator
>
475 exemplar_init
<Type
, Allocator
>::exemplar_init(Type
&& val
,
478 m_exemplar
= a
.allocate(1);
479 auto_deallocator
<Type
, Allocator
> guard(m_exemplar
, a
);
480 a
.construct(m_exemplar
, std::forward
<Type
>(val
));
485 template <typename Type
, typename Allocator
>
486 exemplar_init
<Type
, Allocator
>*
487 exemplar_init
<Type
, Allocator
>::make(const Type
& val
,
490 typedef typename
Allocator::template rebind
<exemplar_init
>::other
492 self_alloc_t
alloc(a
);
494 exemplar_init
*self
= alloc
.allocate(1);
495 auto_deallocator
<exemplar_init
, self_alloc_t
> guard(self
, alloc
);
497 // Don't use allocator to construct self. Allocator should be
498 // used only on elements of type 'Type'.
499 ::new((void*) self
) exemplar_init(val
, a
);
506 #ifdef __CILKRTS_RVALUE_REFERENCES
507 template <typename Type
, typename Allocator
>
508 exemplar_init
<Type
, Allocator
>*
509 exemplar_init
<Type
, Allocator
>::make(Type
&& val
,
512 typedef typename
Allocator::template rebind
<exemplar_init
>::other
514 self_alloc_t
alloc(a
);
516 exemplar_init
*self
= alloc
.allocate(1);
517 auto_deallocator
<exemplar_init
, self_alloc_t
> guard(self
, alloc
);
519 // Don't use allocator to construct self. Allocator should be
520 // used only on elements of type 'Type'.
521 ::new((void*) self
) exemplar_init(std::forward
<Type
>(val
), a
);
529 template <typename Type
, typename Allocator
>
530 exemplar_init
<Type
, Allocator
>::~exemplar_init()
532 // Called only by delete_self, which deleted the exemplar using an
534 __CILKRTS_ASSERT(0 == m_exemplar
);
537 template <typename Type
, typename Allocator
>
538 init_base
<Type
, Allocator
>*
539 exemplar_init
<Type
, Allocator
>::clone_self(Allocator
& a
) const
541 return make(*m_exemplar
, a
);
544 template <typename Type
, typename Allocator
>
545 void exemplar_init
<Type
, Allocator
>::delete_self(Allocator
& a
)
547 typename
Allocator::template rebind
<exemplar_init
>::other
alloc(a
);
549 a
.destroy(m_exemplar
);
550 a
.deallocate(m_exemplar
, 1);
553 this->~exemplar_init();
554 alloc
.deallocate(this, 1);
557 template <typename Type
, typename Allocator
>
559 exemplar_init
<Type
, Allocator
>::construct_view(Type
* p
,
562 a
.construct(p
, *m_exemplar
);
563 // TBD: In a C++0x library, this should be rewritten
564 // std::allocator_traits<Allocator>::construct(a, p, *m_exemplar);
568 * Class to construct a view using a stored functor. The functor,
569 * 'f', must be be invokable using the expression 'Type x = f()'.
571 template <typename Func
, typename Allocator
>
573 public init_base
<typename
Allocator::value_type
, Allocator
>
575 typedef typename
Allocator::value_type value_type
;
576 typedef init_base
<value_type
, Allocator
> base
;
577 typedef typename
Allocator::template rebind
<Func
>::other f_alloc
;
581 /// Private constructors (called from make() functions
582 functor_init(const Func
& f
, Allocator
& a
);
583 #ifdef __CILKRTS_RVALUE_REFERENCES
584 functor_init(Func
&& f
, Allocator
& a
);
588 functor_init(const functor_init
&);
589 functor_init
& operator=(const functor_init
&);
592 // Static factory functions
593 static functor_init
* make(const Func
& val
,
594 Allocator
& a
= Allocator());
595 #ifdef __CILKRTS_RVALUE_REFERENCES
596 static functor_init
* make(Func
&& val
,
597 Allocator
& a
= Allocator());
600 // Virtual function overrides
601 virtual ~functor_init();
602 virtual base
* clone_self(Allocator
& a
) const;
603 virtual void delete_self(Allocator
& a
);
605 construct_view(value_type
* p
, Allocator
& a
) const;
608 /// Specialization to strip off reference from 'Func&'.
609 template <typename Func
, typename Allocator
>
610 struct functor_init
<Func
&, Allocator
>
611 : functor_init
<Func
, Allocator
> { };
613 /// Specialization to strip off reference and cvq from 'const Func&'.
614 template <typename Func
, typename Allocator
>
615 struct functor_init
<const Func
&, Allocator
>
616 : functor_init
<Func
, Allocator
> { };
618 template <typename Func
, typename Allocator
>
619 functor_init
<Func
, Allocator
>::functor_init(const Func
& f
,
624 m_functor
= alloc
.allocate(1);
625 auto_deallocator
<Func
, f_alloc
> guard(m_functor
, alloc
);
626 alloc
.construct(m_functor
, f
);
630 #ifdef __CILKRTS_RVALUE_REFERENCES
631 template <typename Func
, typename Allocator
>
632 functor_init
<Func
, Allocator
>::functor_init(Func
&& f
,
637 m_functor
= alloc
.allocate(1);
638 auto_deallocator
<Func
, f_alloc
> guard(m_functor
, alloc
);
639 alloc
.construct(m_functor
, std::forward
<Func
>(f
));
644 template <typename Func
, typename Allocator
>
645 functor_init
<Func
, Allocator
>*
646 functor_init
<Func
, Allocator
>::make(const Func
& f
, Allocator
& a
)
648 typedef typename
Allocator::template rebind
<functor_init
>::other
650 self_alloc_t
alloc(a
);
652 functor_init
*self
= alloc
.allocate(1);
653 auto_deallocator
<functor_init
, self_alloc_t
> guard(self
, alloc
);
655 // Don't use allocator to construct self. Allocator should be
656 // used only on elements of type 'Func'.
657 ::new((void*) self
) functor_init(f
, a
);
664 #ifdef __CILKRTS_RVALUE_REFERENCES
665 template <typename Func
, typename Allocator
>
666 functor_init
<Func
, Allocator
>*
667 functor_init
<Func
, Allocator
>::make(Func
&& f
, Allocator
& a
)
669 typedef typename
Allocator::template rebind
<functor_init
>::other
671 self_alloc_t
alloc(a
);
673 functor_init
*self
= alloc
.allocate(1);
674 auto_deallocator
<functor_init
, self_alloc_t
> guard(self
, alloc
);
676 // Don't use allocator to construct self. Allocator should be
677 // used only on elements of type 'Func'.
678 ::new((void*) self
) functor_init(std::forward
<Func
>(f
), a
);
686 template <typename Func
, typename Allocator
>
687 functor_init
<Func
, Allocator
>::~functor_init()
689 // Called only by delete_self, which deleted the functor using an
691 __CILKRTS_ASSERT(0 == m_functor
);
694 template <typename Func
, typename Allocator
>
695 init_base
<typename
Allocator::value_type
, Allocator
>*
696 functor_init
<Func
, Allocator
>::clone_self(Allocator
& a
) const
698 return make(*m_functor
, a
);
701 template <typename Func
, typename Allocator
>
703 void functor_init
<Func
, Allocator
>::delete_self(Allocator
& a
)
705 typename
Allocator::template rebind
<functor_init
>::other
alloc(a
);
708 fa
.destroy(m_functor
);
709 fa
.deallocate(m_functor
, 1);
712 this->~functor_init();
713 alloc
.deallocate(this, 1);
716 template <typename Func
, typename Allocator
>
717 void functor_init
<Func
, Allocator
>::construct_view(value_type
* p
,
720 a
.construct(p
, (*m_functor
)());
721 // In C++0x, the above should be written
722 // std::allocator_traits<Allocator>::construct(a, p, m_functor());
726 * Functor called to reduce a holder
728 template <typename Type
, holder_policy Policy
>
729 struct holder_reduce_functor
;
732 * Specialization to keep the left (first) value.
734 template <typename Type
>
735 struct holder_reduce_functor
<Type
, holder_keep_indeterminate
>
737 void operator()(Type
* left
, Type
* right
) const { }
741 * Specialization to copy-assign from the right (last) value.
743 template <typename Type
>
744 struct holder_reduce_functor
<Type
, holder_keep_last_copy
>
746 void operator()(Type
* left
, Type
* right
) const {
752 * Specialization to keep the right (last) value via swap.
754 template <typename Type
>
755 struct holder_reduce_functor
<Type
, holder_keep_last_swap
>
757 void operator()(Type
* left
, Type
* right
) const {
763 #ifdef __CILKRTS_RVALUE_REFERENCES
765 * Specialization to move-assign from the right (last) value.
767 template <typename Type
>
768 struct holder_reduce_functor
<Type
, holder_keep_last_move
>
770 void operator()(Type
* left
, Type
* right
) const {
771 *left
= std::move(*right
);
777 * Specialization to keep the right (last) value via the swap member
780 template <typename Type
>
781 struct holder_reduce_functor
<Type
, holder_keep_last_member_swap
>
783 void operator()(Type
* left
, Type
* right
) const {
789 * Specialization to keep the right (last) value by the most efficient
792 template <typename Type
>
793 struct holder_reduce_functor
<Type
, holder_keep_last
> :
794 holder_reduce_functor
<Type
,
796 (has_member_swap
<Type
>::value
?
797 holder_keep_last_member_swap
:
798 #ifdef __CILKRTS_RVALUE_REFERENCES
799 holder_keep_last_move
801 holder_keep_last_copy
806 } // end namespace internal
809 * Monoid for holders.
810 * Allocator type is required to be thread-safe.
812 template <typename Type
,
813 holder_policy Policy
= holder_keep_indeterminate
,
814 typename Allocator
= std::allocator
<Type
> >
815 class holder_monoid
: public monoid_base
<Type
>
817 // Allocator is mutable because the copy of the monoid inside the
818 // reducer is const (to avoid races on the shared state). However,
819 // the allocator is required to be thread-safe, so it is ok (and
820 // necessary) to modify.
821 mutable Allocator m_allocator
;
822 internal::init_base
<Type
, Allocator
> *m_initializer
;
825 /// This constructor uses default-initialization for both the leftmost
826 /// view and each identity view.
827 holder_monoid(const Allocator
& a
= Allocator())
830 internal::default_init
<Type
, Allocator
>::make(m_allocator
))
833 /// These constructors use 'val' as an exemplar to copy-construct both
834 /// the leftmost view and each identity view.
835 holder_monoid(const Type
& val
, const Allocator
& a
= Allocator())
837 , m_initializer(internal::exemplar_init
<Type
, Allocator
>::make(
838 val
, m_allocator
)) { }
839 /// This constructor uses 'f' as a functor to construct both
840 /// the leftmost view and each identity view.
841 template <typename Func
>
842 holder_monoid(const Func
& f
, const Allocator
& a
= Allocator())
845 internal::functor_init
<Func
, Allocator
>::make(f
,m_allocator
))
849 holder_monoid(const holder_monoid
& rhs
)
850 : m_allocator(rhs
.m_allocator
)
851 , m_initializer(rhs
.m_initializer
->clone_self(m_allocator
)) { }
853 /// "Extended" copy constructor with allocator
854 holder_monoid(const holder_monoid
& rhs
, const Allocator
& a
)
856 , m_initializer(rhs
.m_initializer
->clone_self(m_allocator
)) { }
858 #ifdef __CILKRTS_RVALUE_REFERENCES
860 holder_monoid(holder_monoid
&& rhs
)
861 : m_allocator(rhs
.m_allocator
)
862 , m_initializer(rhs
.m_initializer
) {
864 internal::default_init
<Type
, Allocator
>::make(m_allocator
);
867 /// "Extended" move constructor with allocator
868 holder_monoid(holder_monoid
&& rhs
, const Allocator
& a
)
871 if (a
!= rhs
.m_allocator
)
872 m_initializer
= rhs
.m_initializer
->clone_self(a
);
874 m_initializer
= rhs
.m_initializer
;
876 internal::default_init
<Type
, Allocator
>::make(m_allocator
);
881 ~holder_monoid() { m_initializer
->delete_self(m_allocator
); }
883 holder_monoid
& operator=(const holder_monoid
& rhs
) {
884 if (this == &rhs
) return *this;
885 m_initializer
->delete_self(m_allocator
);
886 m_initializer
= rhs
.m_initializer
->clone_self(m_allocator
);
889 #ifdef __CILKRTS_RVALUE_REFERENCES
890 holder_monoid
& operator=(holder_monoid
&& rhs
) {
891 if (m_allocator
!= rhs
.m_allocator
)
892 // Delegate to copy-assignment on unequal allocators
893 return operator=(static_cast<const holder_monoid
&>(rhs
));
894 std::swap(m_initializer
, rhs
.m_initializer
);
899 /// Constructs IDENTITY value into the uninitilized '*p'
900 void identity(Type
* p
) const
901 { m_initializer
->construct_view(p
, m_allocator
); }
903 /// Calls the destructor on the object pointed-to by 'p'
904 void destroy(Type
* p
) const
905 { m_allocator
.destroy(p
); }
907 /// Return a pointer to size bytes of raw memory
908 void* allocate(std::size_t s
) const {
909 __CILKRTS_ASSERT(sizeof(Type
) == s
);
910 return m_allocator
.allocate(1);
913 /// Deallocate the raw memory at p
914 void deallocate(void* p
) const {
915 m_allocator
.deallocate(static_cast<Type
*>(p
), sizeof(Type
));
918 void reduce(Type
* left
, Type
* right
) const {
919 internal::holder_reduce_functor
<Type
, Policy
>()(left
, right
);
922 void swap(holder_monoid
& other
) {
923 __CILKRTS_ASSERT(m_allocator
== other
.m_allocator
);
924 std::swap(m_initializer
, other
.m_initializer
);
927 Allocator
get_allocator() const {
932 // Namespace-scope swap
933 template <typename Type
, holder_policy Policy
, typename Allocator
>
934 inline void swap(holder_monoid
<Type
, Policy
, Allocator
>& a
,
935 holder_monoid
<Type
, Policy
, Allocator
>& b
)
941 * Hyperobject to provide different views of an object to each
944 template <typename Type
,
945 holder_policy Policy
= holder_keep_indeterminate
,
946 typename Allocator
= std::allocator
<Type
> >
947 class holder
: public reducer
<holder_monoid
<Type
, Policy
, Allocator
> >
949 typedef holder_monoid
<Type
, Policy
, Allocator
> monoid_type
;
950 typedef reducer
<monoid_type
> imp
;
952 // Return a value of Type constructed using the functor Func.
953 template <typename Func
>
954 Type
make_value(const Func
& f
) const {
957 char buf
[sizeof(Type
)];
962 obj(const Func
& f
) { f(static_cast<Type
*>(buf
)); }
963 ~obj() { static_cast<Type
*>(buf
)->~Type(); }
965 operator Type
&() { return *static_cast<Type
*>(buf
); }
972 /// Default constructor uses default-initialization for both the
973 /// leftmost view and each identity view.
974 holder(const Allocator
& alloc
= Allocator())
975 : imp(monoid_type(alloc
)) { }
977 /// Construct from an exemplar that is used to initialize both the
978 /// leftmost view and each identity view.
979 holder(const Type
& v
, const Allocator
& alloc
= Allocator())
980 // Alas, cannot use an rvalue reference for 'v' because it is used
981 // twice in the same expression for initializing imp.
982 : imp(monoid_type(v
, alloc
), v
) { }
984 /// Construct from a functor that is used to initialize both the
985 /// leftmost view and each identity view. The functor, 'f', must be be
986 /// invokable using the expression 'Type x = f()'.
987 template <typename Func
>
988 holder(const Func
& f
, const Allocator
& alloc
= Allocator())
989 // Alas, cannot use an rvalue for 'f' because it is used twice in
990 // the same expression for initializing imp.
991 : imp(monoid_type(f
, alloc
), make_value(f
)) { }
994 } // end namespace cilk
997 # error Holders are currently available only for C++
998 #endif /* __cplusplus */
1000 #endif /* HOLDER_H_INCLUDED */