2 * Copyright (C) 2011-2016, Intel Corporation
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * * Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in
13 * the documentation and/or other materials provided with the
15 * * Neither the name of Intel Corporation nor the names of its
16 * contributors may be used to endorse or promote products derived
17 * from this software without specific prior written permission.
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
24 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
25 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
26 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
27 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY
29 * WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30 * POSSIBILITY OF SUCH DAMAGE.
32 * *********************************************************************
34 * PLEASE NOTE: This file is a downstream copy of a file mainitained in
35 * a repository at cilkplus.org. Changes made to this file that are not
36 * submitted through the contribution process detailed at
37 * http://www.cilkplus.org/submit-cilk-contribution will be lost the next
38 * time that a new version is released. Changes only submitted to the
39 * GNU compiler collection or posted to the git repository at
40 * https://bitbucket.org/intelcilkruntime/intel-cilk-runtime.git are
43 * We welcome your contributions to this open source project. Thank you
44 * for your assistance in helping us improve Cilk Plus.
51 * Purpose: hyperobject to provide different views of an object to each
55 #ifndef HOLDER_H_INCLUDED
56 #define HOLDER_H_INCLUDED
58 #include <cilk/reducer.h>
66 * Classes: holder<Type>
70 * This component provides a hyperobject that isolates a parallel uses of a
71 * common variable where it is not necessary to preserve changes from
72 * different parallel strands. In effect, a holder acts a bit like
73 * thread-local storage, but has qualities that work better with the
74 * fork-join structure of Intel(R) Cilk(TM) Plus. In particular, a holder has the
75 * following qualities:
77 * - The view of a holder before the first spawn within a function is the same
78 * as the view after each sync (as in the case of a reducer).
79 * - The view of a holder within the first spawned child of a function (or the
80 * first child spawned after a sync) is the same as the view on entry to the
82 * - The view of a holder before entering a _Cilk_for loop is the same as the
83 * view during the first iteration of the loop and the view at the end of
85 * - The view of a holder in the continuation of a spawn or in an arbitrary
86 * iteration of a _Cilk_for loop is *non-deterministic*. It is generally
87 * recommended that the holder be explicitly put into a known state in these
90 * A holder can be used as an alternative to parameter-passing. They are most
91 * useful for replacing non-local variables without massive refactoring. A
92 * holder takes advantage of the fact that, most of the time, a holder view
93 * does not change after a spawn or from one iteration of a parallel for loop
94 * to the next (i.e., stealing is the exception, not the rule). When the
95 * holder view is a large object that is expensive to construct, this
96 * optimization can save significant time versus creating a separate local
97 * object for each view. In addition, a holder using the "keep last" policy
98 * will have the same value after a sync as the serialization of the same
99 * program. The last quality will often allow the program to avoid
100 * recomputing a value.
104 * Function 'compute()' is a complex function that computes a value using a
105 * memoized algorithm, storing intermediate results in a hash table. Compute
106 * calls several other functions, each of which calls several other functions,
107 * all of which share a global hash table. In all, there are over a dozen
108 * functions with a total of about 60 references to the hash table.
110 * hash_table<int, X> memos;
112 * void h(const X& x); // Uses memos
114 * double compute(const X& x)
120 * g(i); // Uses memos
122 * std::for_each(c.begin(), c.end(), h); // Call h for each element of c
127 * const std::size_t ARRAY_SIZE = 1000000;
128 * extern X myArray[ARRAY_SIZE];
130 * for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
132 * compute(myArray[i]);
136 * We would like to replace the 'for' loop in 'main' with a 'cilk_for'.
137 * Although the hash table is cleared on entry to each call to 'compute()',
138 * and although the values stored in the hash table are no longer used after
139 * 'compute()' returns, the use of the hash table as a global variable
140 * prevents 'compute()' from being called safely in parallel. One way to do
141 * this would be to make 'memos' a private variable within the cilk_for loop
142 * and pass it down to the actual computation, so that each loop iteration has
143 * its own private copy:
145 * cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i)
147 * hash_table<int, X> memos;
148 * compute(myArray[i], memos);
151 * The problem with this approach is that it requires changing the signature
152 * of 'compute', 'h', 'g', and every one of the dozen or so functions that
153 * reference 'memos' as well as any function that calls those functions. This
154 * may break the abstraction of 'compute' and other functions, exposing an
155 * implementation detail that was not part of the interface. In addition, the
156 * function 'h' is called through a templated algorithm, 'for_each', which
157 * requires a fixed interface. Finally, there is constructor and destructor
158 * overhead for 'hash_table' each time through the loop.
160 * The alternative approach is to replace 'memos' with a holder. The holder
161 * would be available to all of the functions involved, but would not cause a
162 * race between parallel loop iterations. In order to make this work, each
163 * use of the 'memos' variable must be (mechanically) replaced by a use of the
166 * cilk::holder<hash_table<int, X> > memos_h;
168 * void h(const X& x); // Uses memos_h
170 * double compute(const X& x)
172 * memos_h().clear(); // operator() used to "dereference" the holder
174 * memos_h()[i] = x; // operator() used to "dereference" the holder
176 * g(i); // Uses memos_h
178 * std::for_each(c.begin(), c.end(), h); // Call h for each element of c
181 * Note that each reference to the holder must be modified with an empty pair
182 * of parenthesis. This syntax is needed because there is no facility in C++
183 * for a "smart reference" that would allow 'memos_h' to be a perfect
184 * replacement for 'memos'. One way that a user can avoid this syntax change
185 * is to wrap the holder in a class that has the same inteface as
186 * 'hash_table' but redirects all calls to the holder:
188 * template <typename K, typename V>
189 * class hash_table_holder
192 * cilk::holder<hash_table<K, V> > m_holder;
194 * void clear() { m_holder().clear(); }
195 * V& operator[](const K& x) { return m_holder()[x]; }
196 * std::size_t size() const { return m_holder().size(); }
200 * Using the above wrapper, the original code can be left unchanged except for
201 * replacing 'hash_table' with 'hash_table_holder' and replacing 'for' with
204 * hash_table_holder<int, X> memos;
206 * void h(const X& x); // Uses memos
208 * double compute(const X& x)
210 * memos.clear(); // Calls hash_table_holder::clear().
214 * The above changes have no benefit over the use of thread-local storage.
215 * What if one of the functions has a 'cilk_spawn', however?
223 * w = cilk_spawn compute_width(y); // May use 'memos'
224 * d = compute_depth(y); // Does not use 'memos'
226 * compute(y); // recursive call. Uses 'memos'.
230 * In the above example, the view of the holder within 'compute_width' is the
231 * same as the view on entry to 'h'. More importantly, the view of the holder
232 * within the recursive call to 'compute' is the same as the view on entry to
233 * 'h', even if a different worker is executing the recursive call. Thus, the
234 * holder view within a Intel Cilk Plus program has useful qualities not found in
235 * thread-local storage.
241 * After a sync, the value stored in a holder matches the most recent
242 * value stored into the holder by one of the starnds entering the sync.
243 * The holder policy used to instantiate the holder determines which of
244 * the entering strands determines the final value of the holder. A policy
245 * of 'holder_keep_indeterminate' (the default) is the most efficient, and
246 * results in an indeterminate value depending on the runtime schedule
247 * (see below for more specifics). An indeterminate value after a sync is
248 * often acceptable, especially if the value of the holder is not reused
249 * after the sync. All of the remaining policies retain the value of the
250 * last strand that would be executed in the serialization of the program.
251 * They differ in the mechanism used to move the value from one view to
252 * another. A policy of 'holder_keep_last_copy' moves values by
253 * copy-assignment. A policy of 'holder_keep_last_swap' moves values by
254 * calling 'swap'. A policy of 'holder_keep_last_move' is available only
255 * for compilers that support C++0x rvalue references and moves values by
256 * move-assignment. A policy of 'holder_keep_last' attempts to choose the
257 * most efficient mechanism: member-function 'swap' if the view type
258 * supports it, otherwise move-assignment if supported, otherwise
259 * copy-assignment. (The swap member function for a class that provides
260 * one is almost always as fast or faster than move-assignment or
263 * The behavior of 'holder_keep_indeterminate', while indeterminate, is
264 * not random and can be used for advanced programming or debugging. With
265 * a policy of 'holder_keep_intermediate', values are never copied or
266 * moved between views. The value of the view after a sync is the same as
267 * the value set in the last spawned child before a steal occurs or the
268 * last value set in the continuation if no steal occurs. Using this
269 * knowledge, a programmer can use a holder to detect the earliest steal
270 * in a piece of code. An indeterminate holder is also useful for keeping
271 * cached data similar to the way some applications might use thread-local
275 holder_keep_indeterminate
,
277 holder_keep_last_copy
,
278 holder_keep_last_swap
,
279 #ifdef __CILKRTS_RVALUE_REFERENCES
280 holder_keep_last_move
286 // Private special-case holder policy using the swap member-function
287 const holder_policy holder_keep_last_member_swap
=
288 (holder_policy
) (holder_keep_last_swap
| 0x10);
290 /* The constant, 'has_member_swap<T>::value', will be 'true' if 'T'
291 * has a non-static member function with prototype 'void swap(T&)'.
292 * The mechanism used to detect 'swap' is the most portable among
293 * present-day compilers, but is not the most robust. Specifically,
294 * the prototype for 'swap' must exactly match 'void swap(T&)'.
295 * Near-matches like a 'swap' function that returns 'int' instead of
296 * 'void' will not be detected. Detection will also fail if 'T'
297 * inherits 'swap' from a base class.
299 template <typename T
>
300 class has_member_swap
302 // This technique for detecting member functions was described by
303 // Rani Sharoni in comp.lang.c++.moderated:
304 // http://groups.google.com/group/comp.lang.c++.moderated/msg/2b06b2432fddfb60
306 // sizeof(notchar) is guaranteed larger than 1
307 struct notchar
{ char x
[2]; };
309 // Instantiationg Q<U, &U::swap> will fail unless U contains a
310 // non-static member with prototype 'void swap(U&)'.
311 template <class U
, void (U::*)(U
&)> struct Q
{ };
313 // First 'test' is preferred overload if U::swap exists with the
314 // correct prototype. Second 'test' is preferred overload
316 template <typename U
> static char test(Q
<U
,&U::swap
>*);
317 template <typename U
> static notchar
test(...);
320 /// 'value' will be true if T has a non-static member function
321 /// with prototype 'void swap(T&)'.
322 static const bool value
= (1 == sizeof(test
<T
>(0)));
325 template <typename T
> const bool has_member_swap
<T
>::value
;
328 * @brief Utility class for exception safety.
330 * The constuctor for this class takes a pointer and an allocator and
331 * holds on to them. The destructor deallocates the pointed-to
332 * object, without calling its destructor, typically to recover memory
333 * in case an exception is thrown. The release member clears the
334 * pointer so that the deallocation is prevented, i.e., when the
335 * exception danger has passed. The behavior of this class is similar
336 * to auto_ptr and unique_ptr.
338 template <typename Type
, typename Allocator
= std::allocator
<Type
> >
339 class auto_deallocator
345 auto_deallocator(const auto_deallocator
&);
346 auto_deallocator
& operator=(const auto_deallocator
&);
350 explicit auto_deallocator(Type
* p
, const Allocator
& a
= Allocator())
351 : m_alloc(a
), m_ptr(p
) { }
353 /// Destructor - free allocated resources
354 ~auto_deallocator() { if (m_ptr
) m_alloc
.deallocate(m_ptr
, 1); }
356 /// Remove reference to resource
357 void release() { m_ptr
= 0; }
361 * Pure-abstract base class to initialize holder views
363 template <typename Type
, typename Allocator
>
367 virtual ~init_base() { }
368 virtual init_base
* clone_self(Allocator
& a
) const = 0;
369 virtual void delete_self(Allocator
& a
) = 0;
370 virtual void construct_view(Type
* p
, Allocator
& a
) const = 0;
374 * Class to default-initialize a holder view
376 template <typename Type
, typename Allocator
>
377 class default_init
: public init_base
<Type
, Allocator
>
379 typedef init_base
<Type
, Allocator
> base
;
381 /// Private constructor (called from static make() function).
385 default_init(const default_init
&);
386 default_init
& operator=(const default_init
&);
389 // Static factory function
390 static default_init
* make(Allocator
& a
);
392 // Virtual function overrides
393 virtual ~default_init();
394 virtual base
* clone_self(Allocator
& a
) const;
395 virtual void delete_self(Allocator
& a
);
396 virtual void construct_view(Type
* p
, Allocator
& a
) const;
399 template <typename Type
, typename Allocator
>
400 default_init
<Type
, Allocator
>*
401 default_init
<Type
, Allocator
>::make(Allocator
&)
403 // Return a pointer to a singleton. All instances of this class
404 // are identical, so we need only one.
405 static default_init self
;
409 template <typename Type
, typename Allocator
>
410 default_init
<Type
, Allocator
>::~default_init()
414 template <typename Type
, typename Allocator
>
415 init_base
<Type
, Allocator
>*
416 default_init
<Type
, Allocator
>::clone_self(Allocator
& a
) const
421 template <typename Type
, typename Allocator
>
422 void default_init
<Type
, Allocator
>::delete_self(Allocator
&)
424 // Since make() returned a shared singleton, there is nothing to
428 template <typename Type
, typename Allocator
>
430 default_init
<Type
, Allocator
>::construct_view(Type
* p
,
433 ::new((void*) p
) Type();
434 // TBD: In a C++0x library, this should be rewritten
435 // std::allocator_traits<Allocator>::construct(a, p);
439 * Class to copy-construct a view from a stored exemplar.
441 template <typename Type
, typename Allocator
>
442 class exemplar_init
: public init_base
<Type
, Allocator
>
444 typedef init_base
<Type
, Allocator
> base
;
448 // Private constructors (called from make() functions).
449 exemplar_init(const Type
& val
, Allocator
& a
);
450 #ifdef __CILKRTS_RVALUE_REFERENCES
451 exemplar_init(Type
&& val
, Allocator
& a
);
455 exemplar_init(const exemplar_init
&);
456 exemplar_init
& operator=(const exemplar_init
&);
459 // Static factory functions
460 static exemplar_init
* make(const Type
& val
,
461 Allocator
& a
= Allocator());
462 #ifdef __CILKRTS_RVALUE_REFERENCES
463 static exemplar_init
* make(Type
&& val
,
464 Allocator
& a
= Allocator());
467 // Virtual function overrides
468 virtual ~exemplar_init();
469 virtual base
* clone_self(Allocator
& a
) const;
470 virtual void delete_self(Allocator
& a
);
471 virtual void construct_view(Type
* p
, Allocator
& a
) const;
474 template <typename Type
, typename Allocator
>
475 exemplar_init
<Type
, Allocator
>::exemplar_init(const Type
& val
,
478 m_exemplar
= a
.allocate(1);
479 auto_deallocator
<Type
, Allocator
> guard(m_exemplar
, a
);
480 a
.construct(m_exemplar
, val
);
484 #ifdef __CILKRTS_RVALUE_REFERENCES
485 template <typename Type
, typename Allocator
>
486 exemplar_init
<Type
, Allocator
>::exemplar_init(Type
&& val
,
489 m_exemplar
= a
.allocate(1);
490 auto_deallocator
<Type
, Allocator
> guard(m_exemplar
, a
);
491 a
.construct(m_exemplar
, std::forward
<Type
>(val
));
496 template <typename Type
, typename Allocator
>
497 exemplar_init
<Type
, Allocator
>*
498 exemplar_init
<Type
, Allocator
>::make(const Type
& val
,
501 typedef typename
Allocator::template rebind
<exemplar_init
>::other
503 self_alloc_t
alloc(a
);
505 exemplar_init
*self
= alloc
.allocate(1);
506 auto_deallocator
<exemplar_init
, self_alloc_t
> guard(self
, alloc
);
508 // Don't use allocator to construct self. Allocator should be
509 // used only on elements of type 'Type'.
510 ::new((void*) self
) exemplar_init(val
, a
);
517 #ifdef __CILKRTS_RVALUE_REFERENCES
518 template <typename Type
, typename Allocator
>
519 exemplar_init
<Type
, Allocator
>*
520 exemplar_init
<Type
, Allocator
>::make(Type
&& val
,
523 typedef typename
Allocator::template rebind
<exemplar_init
>::other
525 self_alloc_t
alloc(a
);
527 exemplar_init
*self
= alloc
.allocate(1);
528 auto_deallocator
<exemplar_init
, self_alloc_t
> guard(self
, alloc
);
530 // Don't use allocator to construct self. Allocator should be
531 // used only on elements of type 'Type'.
532 ::new((void*) self
) exemplar_init(std::forward
<Type
>(val
), a
);
540 template <typename Type
, typename Allocator
>
541 exemplar_init
<Type
, Allocator
>::~exemplar_init()
543 // Called only by delete_self, which deleted the exemplar using an
545 __CILKRTS_ASSERT(0 == m_exemplar
);
548 template <typename Type
, typename Allocator
>
549 init_base
<Type
, Allocator
>*
550 exemplar_init
<Type
, Allocator
>::clone_self(Allocator
& a
) const
552 return make(*m_exemplar
, a
);
555 template <typename Type
, typename Allocator
>
556 void exemplar_init
<Type
, Allocator
>::delete_self(Allocator
& a
)
558 typename
Allocator::template rebind
<exemplar_init
>::other
alloc(a
);
560 a
.destroy(m_exemplar
);
561 a
.deallocate(m_exemplar
, 1);
564 this->~exemplar_init();
565 alloc
.deallocate(this, 1);
568 template <typename Type
, typename Allocator
>
570 exemplar_init
<Type
, Allocator
>::construct_view(Type
* p
,
573 a
.construct(p
, *m_exemplar
);
574 // TBD: In a C++0x library, this should be rewritten
575 // std::allocator_traits<Allocator>::construct(a, p, *m_exemplar);
579 * Class to construct a view using a stored functor. The functor,
580 * 'f', must be be invokable using the expression 'Type x = f()'.
582 template <typename Func
, typename Allocator
>
584 public init_base
<typename
Allocator::value_type
, Allocator
>
586 typedef typename
Allocator::value_type value_type
;
587 typedef init_base
<value_type
, Allocator
> base
;
588 typedef typename
Allocator::template rebind
<Func
>::other f_alloc
;
592 /// Private constructors (called from make() functions
593 functor_init(const Func
& f
, Allocator
& a
);
594 #ifdef __CILKRTS_RVALUE_REFERENCES
595 functor_init(Func
&& f
, Allocator
& a
);
599 functor_init(const functor_init
&);
600 functor_init
& operator=(const functor_init
&);
603 // Static factory functions
604 static functor_init
* make(const Func
& val
,
605 Allocator
& a
= Allocator());
606 #ifdef __CILKRTS_RVALUE_REFERENCES
607 static functor_init
* make(Func
&& val
,
608 Allocator
& a
= Allocator());
611 // Virtual function overrides
612 virtual ~functor_init();
613 virtual base
* clone_self(Allocator
& a
) const;
614 virtual void delete_self(Allocator
& a
);
616 construct_view(value_type
* p
, Allocator
& a
) const;
619 /// Specialization to strip off reference from 'Func&'.
620 template <typename Func
, typename Allocator
>
621 struct functor_init
<Func
&, Allocator
>
622 : functor_init
<Func
, Allocator
> { };
624 /// Specialization to strip off reference and cvq from 'const Func&'.
625 template <typename Func
, typename Allocator
>
626 struct functor_init
<const Func
&, Allocator
>
627 : functor_init
<Func
, Allocator
> { };
629 template <typename Func
, typename Allocator
>
630 functor_init
<Func
, Allocator
>::functor_init(const Func
& f
,
635 m_functor
= alloc
.allocate(1);
636 auto_deallocator
<Func
, f_alloc
> guard(m_functor
, alloc
);
637 alloc
.construct(m_functor
, f
);
641 #ifdef __CILKRTS_RVALUE_REFERENCES
642 template <typename Func
, typename Allocator
>
643 functor_init
<Func
, Allocator
>::functor_init(Func
&& f
,
648 m_functor
= alloc
.allocate(1);
649 auto_deallocator
<Func
, f_alloc
> guard(m_functor
, alloc
);
650 alloc
.construct(m_functor
, std::forward
<Func
>(f
));
655 template <typename Func
, typename Allocator
>
656 functor_init
<Func
, Allocator
>*
657 functor_init
<Func
, Allocator
>::make(const Func
& f
, Allocator
& a
)
659 typedef typename
Allocator::template rebind
<functor_init
>::other
661 self_alloc_t
alloc(a
);
663 functor_init
*self
= alloc
.allocate(1);
664 auto_deallocator
<functor_init
, self_alloc_t
> guard(self
, alloc
);
666 // Don't use allocator to construct self. Allocator should be
667 // used only on elements of type 'Func'.
668 ::new((void*) self
) functor_init(f
, a
);
675 #ifdef __CILKRTS_RVALUE_REFERENCES
676 template <typename Func
, typename Allocator
>
677 functor_init
<Func
, Allocator
>*
678 functor_init
<Func
, Allocator
>::make(Func
&& f
, Allocator
& a
)
680 typedef typename
Allocator::template rebind
<functor_init
>::other
682 self_alloc_t
alloc(a
);
684 functor_init
*self
= alloc
.allocate(1);
685 auto_deallocator
<functor_init
, self_alloc_t
> guard(self
, alloc
);
687 // Don't use allocator to construct self. Allocator should be
688 // used only on elements of type 'Func'.
689 ::new((void*) self
) functor_init(std::forward
<Func
>(f
), a
);
697 template <typename Func
, typename Allocator
>
698 functor_init
<Func
, Allocator
>::~functor_init()
700 // Called only by delete_self, which deleted the functor using an
702 __CILKRTS_ASSERT(0 == m_functor
);
705 template <typename Func
, typename Allocator
>
706 init_base
<typename
Allocator::value_type
, Allocator
>*
707 functor_init
<Func
, Allocator
>::clone_self(Allocator
& a
) const
709 return make(*m_functor
, a
);
712 template <typename Func
, typename Allocator
>
714 void functor_init
<Func
, Allocator
>::delete_self(Allocator
& a
)
716 typename
Allocator::template rebind
<functor_init
>::other
alloc(a
);
719 fa
.destroy(m_functor
);
720 fa
.deallocate(m_functor
, 1);
723 this->~functor_init();
724 alloc
.deallocate(this, 1);
727 template <typename Func
, typename Allocator
>
728 void functor_init
<Func
, Allocator
>::construct_view(value_type
* p
,
731 a
.construct(p
, (*m_functor
)());
732 // In C++0x, the above should be written
733 // std::allocator_traits<Allocator>::construct(a, p, m_functor());
737 * Functor called to reduce a holder
739 template <typename Type
, holder_policy Policy
>
740 struct holder_reduce_functor
;
743 * Specialization to keep the left (first) value.
745 template <typename Type
>
746 struct holder_reduce_functor
<Type
, holder_keep_indeterminate
>
748 void operator()(Type
* left
, Type
* right
) const { }
752 * Specialization to copy-assign from the right (last) value.
754 template <typename Type
>
755 struct holder_reduce_functor
<Type
, holder_keep_last_copy
>
757 void operator()(Type
* left
, Type
* right
) const {
763 * Specialization to keep the right (last) value via swap.
765 template <typename Type
>
766 struct holder_reduce_functor
<Type
, holder_keep_last_swap
>
768 void operator()(Type
* left
, Type
* right
) const {
774 #ifdef __CILKRTS_RVALUE_REFERENCES
776 * Specialization to move-assign from the right (last) value.
778 template <typename Type
>
779 struct holder_reduce_functor
<Type
, holder_keep_last_move
>
781 void operator()(Type
* left
, Type
* right
) const {
782 *left
= std::move(*right
);
788 * Specialization to keep the right (last) value via the swap member
791 template <typename Type
>
792 struct holder_reduce_functor
<Type
, holder_keep_last_member_swap
>
794 void operator()(Type
* left
, Type
* right
) const {
800 * Specialization to keep the right (last) value by the most efficient
803 template <typename Type
>
804 struct holder_reduce_functor
<Type
, holder_keep_last
> :
805 holder_reduce_functor
<Type
,
807 (has_member_swap
<Type
>::value
?
808 holder_keep_last_member_swap
:
809 #ifdef __CILKRTS_RVALUE_REFERENCES
810 holder_keep_last_move
812 holder_keep_last_copy
817 } // end namespace internal
820 * Monoid for holders.
821 * Allocator type is required to be thread-safe.
823 template <typename Type
,
824 holder_policy Policy
= holder_keep_indeterminate
,
825 typename Allocator
= std::allocator
<Type
> >
826 class holder_monoid
: public monoid_base
<Type
>
828 // Allocator is mutable because the copy of the monoid inside the
829 // reducer is const (to avoid races on the shared state). However,
830 // the allocator is required to be thread-safe, so it is ok (and
831 // necessary) to modify.
832 mutable Allocator m_allocator
;
833 internal::init_base
<Type
, Allocator
> *m_initializer
;
836 /// This constructor uses default-initialization for both the leftmost
837 /// view and each identity view.
838 holder_monoid(const Allocator
& a
= Allocator())
841 internal::default_init
<Type
, Allocator
>::make(m_allocator
))
844 /// These constructors use 'val' as an exemplar to copy-construct both
845 /// the leftmost view and each identity view.
846 holder_monoid(const Type
& val
, const Allocator
& a
= Allocator())
848 , m_initializer(internal::exemplar_init
<Type
, Allocator
>::make(
849 val
, m_allocator
)) { }
850 /// This constructor uses 'f' as a functor to construct both
851 /// the leftmost view and each identity view.
852 template <typename Func
>
853 holder_monoid(const Func
& f
, const Allocator
& a
= Allocator())
856 internal::functor_init
<Func
, Allocator
>::make(f
,m_allocator
))
860 holder_monoid(const holder_monoid
& rhs
)
861 : m_allocator(rhs
.m_allocator
)
862 , m_initializer(rhs
.m_initializer
->clone_self(m_allocator
)) { }
864 /// "Extended" copy constructor with allocator
865 holder_monoid(const holder_monoid
& rhs
, const Allocator
& a
)
867 , m_initializer(rhs
.m_initializer
->clone_self(m_allocator
)) { }
869 #ifdef __CILKRTS_RVALUE_REFERENCES
871 holder_monoid(holder_monoid
&& rhs
)
872 : m_allocator(rhs
.m_allocator
)
873 , m_initializer(rhs
.m_initializer
) {
875 internal::default_init
<Type
, Allocator
>::make(m_allocator
);
878 /// "Extended" move constructor with allocator
879 holder_monoid(holder_monoid
&& rhs
, const Allocator
& a
)
882 if (a
!= rhs
.m_allocator
)
883 m_initializer
= rhs
.m_initializer
->clone_self(a
);
885 m_initializer
= rhs
.m_initializer
;
887 internal::default_init
<Type
, Allocator
>::make(m_allocator
);
892 ~holder_monoid() { m_initializer
->delete_self(m_allocator
); }
894 holder_monoid
& operator=(const holder_monoid
& rhs
) {
895 if (this == &rhs
) return *this;
896 m_initializer
->delete_self(m_allocator
);
897 m_initializer
= rhs
.m_initializer
->clone_self(m_allocator
);
900 #ifdef __CILKRTS_RVALUE_REFERENCES
901 holder_monoid
& operator=(holder_monoid
&& rhs
) {
902 if (m_allocator
!= rhs
.m_allocator
)
903 // Delegate to copy-assignment on unequal allocators
904 return operator=(static_cast<const holder_monoid
&>(rhs
));
905 std::swap(m_initializer
, rhs
.m_initializer
);
910 /// Constructs IDENTITY value into the uninitilized '*p'
911 void identity(Type
* p
) const
912 { m_initializer
->construct_view(p
, m_allocator
); }
914 /// Calls the destructor on the object pointed-to by 'p'
915 void destroy(Type
* p
) const
916 { m_allocator
.destroy(p
); }
918 /// Return a pointer to size bytes of raw memory
919 void* allocate(std::size_t s
) const {
920 __CILKRTS_ASSERT(sizeof(Type
) == s
);
921 return m_allocator
.allocate(1);
924 /// Deallocate the raw memory at p
925 void deallocate(void* p
) const {
926 m_allocator
.deallocate(static_cast<Type
*>(p
), sizeof(Type
));
929 void reduce(Type
* left
, Type
* right
) const {
930 internal::holder_reduce_functor
<Type
, Policy
>()(left
, right
);
933 void swap(holder_monoid
& other
) {
934 __CILKRTS_ASSERT(m_allocator
== other
.m_allocator
);
935 std::swap(m_initializer
, other
.m_initializer
);
938 Allocator
get_allocator() const {
943 // Namespace-scope swap
944 template <typename Type
, holder_policy Policy
, typename Allocator
>
945 inline void swap(holder_monoid
<Type
, Policy
, Allocator
>& a
,
946 holder_monoid
<Type
, Policy
, Allocator
>& b
)
952 * Hyperobject to provide different views of an object to each
955 template <typename Type
,
956 holder_policy Policy
= holder_keep_indeterminate
,
957 typename Allocator
= std::allocator
<Type
> >
958 class holder
: public reducer
<holder_monoid
<Type
, Policy
, Allocator
> >
960 typedef holder_monoid
<Type
, Policy
, Allocator
> monoid_type
;
961 typedef reducer
<monoid_type
> imp
;
963 // Return a value of Type constructed using the functor Func.
964 template <typename Func
>
965 Type
make_value(const Func
& f
) const {
968 char buf
[sizeof(Type
)];
973 obj(const Func
& f
) { f(static_cast<Type
*>(buf
)); }
974 ~obj() { static_cast<Type
*>(buf
)->~Type(); }
976 operator Type
&() { return *static_cast<Type
*>(buf
); }
983 /// Default constructor uses default-initialization for both the
984 /// leftmost view and each identity view.
985 holder(const Allocator
& alloc
= Allocator())
986 : imp(monoid_type(alloc
)) { }
988 /// Construct from an exemplar that is used to initialize both the
989 /// leftmost view and each identity view.
990 holder(const Type
& v
, const Allocator
& alloc
= Allocator())
991 // Alas, cannot use an rvalue reference for 'v' because it is used
992 // twice in the same expression for initializing imp.
993 : imp(monoid_type(v
, alloc
), v
) { }
995 /// Construct from a functor that is used to initialize both the
996 /// leftmost view and each identity view. The functor, 'f', must be be
997 /// invokable using the expression 'Type x = f()'.
998 template <typename Func
>
999 holder(const Func
& f
, const Allocator
& alloc
= Allocator())
1000 // Alas, cannot use an rvalue for 'f' because it is used twice in
1001 // the same expression for initializing imp.
1002 : imp(monoid_type(f
, alloc
), make_value(f
)) { }
1005 } // end namespace cilk
1008 # error Holders are currently available only for C++
1009 #endif /* __cplusplus */
1011 #endif /* HOLDER_H_INCLUDED */