]>
Commit | Line | Data |
---|---|---|
4710dd51 | 1 | /* |
0657c20f | 2 | * Copyright (C) 2011-2016, Intel Corporation |
4710dd51 | 3 | * All rights reserved. |
4 | * | |
4710dd51 | 5 | * Redistribution and use in source and binary forms, with or without |
6 | * modification, are permitted provided that the following conditions | |
7 | * are met: | |
8 | * | |
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 | |
14 | * distribution. | |
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. | |
18 | * | |
4710dd51 | 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. | |
0657c20f | 31 | * |
32 | * ********************************************************************* | |
33 | * | |
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 | |
41 | * not tracked. | |
42 | * | |
43 | * We welcome your contributions to this open source project. Thank you | |
44 | * for your assistance in helping us improve Cilk Plus. | |
4710dd51 | 45 | * |
46 | */ | |
47 | ||
48 | /* | |
49 | * holder.h | |
50 | * | |
51 | * Purpose: hyperobject to provide different views of an object to each | |
52 | * parallel strand. | |
53 | */ | |
54 | ||
55 | #ifndef HOLDER_H_INCLUDED | |
56 | #define HOLDER_H_INCLUDED | |
57 | ||
58 | #include <cilk/reducer.h> | |
59 | #include <memory> | |
60 | #include <utility> | |
61 | ||
62 | #ifdef __cplusplus | |
63 | ||
64 | /* C++ Interface | |
65 | * | |
66 | * Classes: holder<Type> | |
67 | * | |
68 | * Description: | |
69 | * ============ | |
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 | |
0657c20f | 74 | * fork-join structure of Intel(R) Cilk(TM) Plus. In particular, a holder has the |
75 | * following qualities: | |
4710dd51 | 76 | * |
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 | |
81 | * function. | |
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 | |
84 | * the loop. | |
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 | |
88 | * situations. | |
89 | * | |
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. | |
101 | * | |
102 | * Usage Example: | |
103 | * ============== | |
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. | |
109 | *.. | |
110 | * hash_table<int, X> memos; | |
111 | * | |
112 | * void h(const X& x); // Uses memos | |
113 | * | |
114 | * double compute(const X& x) | |
115 | * { | |
116 | * memos.clear(); | |
117 | * // ... | |
118 | * memos[i] = x; | |
119 | * ... | |
120 | * g(i); // Uses memos | |
121 | * // ... | |
122 | * std::for_each(c.begin(), c.end(), h); // Call h for each element of c | |
123 | * } | |
124 | * | |
125 | * int main() | |
126 | * { | |
127 | * const std::size_t ARRAY_SIZE = 1000000; | |
128 | * extern X myArray[ARRAY_SIZE]; | |
129 | * | |
130 | * for (std::size_t i = 0; i < ARRAY_SIZE; ++i) | |
131 | * { | |
132 | * compute(myArray[i]); | |
133 | * } | |
134 | * } | |
135 | *.. | |
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: | |
144 | *.. | |
145 | * cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i) | |
146 | * { | |
147 | * hash_table<int, X> memos; | |
148 | * compute(myArray[i], memos); | |
149 | * } | |
150 | *.. | |
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. | |
159 | * | |
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 | |
164 | * holder: | |
165 | *.. | |
166 | * cilk::holder<hash_table<int, X> > memos_h; | |
167 | * | |
168 | * void h(const X& x); // Uses memos_h | |
169 | * | |
170 | * double compute(const X& x) | |
171 | * { | |
172 | * memos_h().clear(); // operator() used to "dereference" the holder | |
173 | * // ... | |
174 | * memos_h()[i] = x; // operator() used to "dereference" the holder | |
175 | * ... | |
176 | * g(i); // Uses memos_h | |
177 | * // ... | |
178 | * std::for_each(c.begin(), c.end(), h); // Call h for each element of c | |
179 | * } | |
180 | *.. | |
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: | |
187 | *.. | |
188 | * template <typename K, typename V> | |
189 | * class hash_table_holder | |
190 | * { | |
191 | * private: | |
192 | * cilk::holder<hash_table<K, V> > m_holder; | |
193 | * public: | |
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(); } | |
197 | * // etc. ... | |
198 | * }; | |
199 | *.. | |
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 | |
202 | * 'cilk_for': | |
203 | *.. | |
204 | * hash_table_holder<int, X> memos; | |
205 | * | |
206 | * void h(const X& x); // Uses memos | |
207 | * | |
208 | * double compute(const X& x) | |
209 | * { | |
210 | * memos.clear(); // Calls hash_table_holder::clear(). | |
211 | * // ... | |
212 | * } | |
213 | *.. | |
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? | |
216 | *.. | |
217 | * void h(const X& x) | |
218 | * { | |
219 | * Y y = x.nested(); | |
220 | * double d, w; | |
221 | * if (y) | |
222 | * { | |
223 | * w = cilk_spawn compute_width(y); // May use 'memos' | |
224 | * d = compute_depth(y); // Does not use 'memos' | |
225 | * cilk_sync; | |
226 | * compute(y); // recursive call. Uses 'memos'. | |
227 | * } | |
228 | * } | |
229 | *.. | |
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 | |
0657c20f | 234 | * holder view within a Intel Cilk Plus program has useful qualities not found in |
4710dd51 | 235 | * thread-local storage. |
236 | */ | |
237 | ||
238 | namespace cilk { | |
239 | ||
240 | /** | |
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 | |
261 | * copy-assignment.) | |
262 | * | |
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 | |
272 | * storage. | |
273 | */ | |
274 | enum holder_policy { | |
275 | holder_keep_indeterminate, | |
276 | holder_keep_last, | |
277 | holder_keep_last_copy, | |
278 | holder_keep_last_swap, | |
279 | #ifdef __CILKRTS_RVALUE_REFERENCES | |
280 | holder_keep_last_move | |
281 | #endif | |
282 | }; | |
283 | ||
284 | namespace internal { | |
285 | ||
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); | |
289 | ||
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. | |
298 | */ | |
299 | template <typename T> | |
300 | class has_member_swap | |
301 | { | |
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 | |
305 | ||
306 | // sizeof(notchar) is guaranteed larger than 1 | |
307 | struct notchar { char x[2]; }; | |
308 | ||
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 { }; | |
312 | ||
313 | // First 'test' is preferred overload if U::swap exists with the | |
314 | // correct prototype. Second 'test' is preferred overload | |
315 | // otherwise. | |
316 | template <typename U> static char test(Q<U,&U::swap>*); | |
317 | template <typename U> static notchar test(...); | |
318 | ||
319 | public: | |
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))); | |
323 | }; | |
324 | ||
325 | template <typename T> const bool has_member_swap<T>::value; | |
326 | ||
327 | /** | |
328 | * @brief Utility class for exception safety. | |
329 | * | |
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. | |
337 | */ | |
338 | template <typename Type, typename Allocator = std::allocator<Type> > | |
339 | class auto_deallocator | |
340 | { | |
341 | Allocator m_alloc; | |
342 | Type* m_ptr; | |
343 | ||
344 | // Non-copiable | |
345 | auto_deallocator(const auto_deallocator&); | |
346 | auto_deallocator& operator=(const auto_deallocator&); | |
347 | ||
348 | public: | |
349 | /// Constructor | |
350 | explicit auto_deallocator(Type* p, const Allocator& a = Allocator()) | |
351 | : m_alloc(a), m_ptr(p) { } | |
352 | ||
353 | /// Destructor - free allocated resources | |
354 | ~auto_deallocator() { if (m_ptr) m_alloc.deallocate(m_ptr, 1); } | |
355 | ||
356 | /// Remove reference to resource | |
357 | void release() { m_ptr = 0; } | |
358 | }; | |
359 | ||
360 | /** | |
361 | * Pure-abstract base class to initialize holder views | |
362 | */ | |
363 | template <typename Type, typename Allocator> | |
364 | class init_base | |
365 | { | |
366 | public: | |
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; | |
371 | }; | |
372 | ||
373 | /** | |
374 | * Class to default-initialize a holder view | |
375 | */ | |
376 | template <typename Type, typename Allocator> | |
377 | class default_init : public init_base<Type, Allocator> | |
378 | { | |
379 | typedef init_base<Type, Allocator> base; | |
380 | ||
381 | /// Private constructor (called from static make() function). | |
382 | default_init() { } | |
383 | ||
384 | // Non-copiable | |
385 | default_init(const default_init&); | |
386 | default_init& operator=(const default_init&); | |
387 | ||
388 | public: | |
389 | // Static factory function | |
390 | static default_init* make(Allocator& a); | |
391 | ||
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; | |
397 | }; | |
398 | ||
399 | template <typename Type, typename Allocator> | |
400 | default_init<Type, Allocator>* | |
401 | default_init<Type, Allocator>::make(Allocator&) | |
402 | { | |
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; | |
406 | return &self; | |
407 | } | |
408 | ||
409 | template <typename Type, typename Allocator> | |
410 | default_init<Type, Allocator>::~default_init() | |
411 | { | |
412 | } | |
413 | ||
414 | template <typename Type, typename Allocator> | |
415 | init_base<Type, Allocator>* | |
416 | default_init<Type, Allocator>::clone_self(Allocator& a) const | |
417 | { | |
418 | return make(a); | |
419 | } | |
420 | ||
421 | template <typename Type, typename Allocator> | |
422 | void default_init<Type, Allocator>::delete_self(Allocator&) | |
423 | { | |
424 | // Since make() returned a shared singleton, there is nothing to | |
425 | // delete here. | |
426 | } | |
427 | ||
428 | template <typename Type, typename Allocator> | |
429 | void | |
430 | default_init<Type, Allocator>::construct_view(Type* p, | |
431 | Allocator&) const | |
432 | { | |
433 | ::new((void*) p) Type(); | |
434 | // TBD: In a C++0x library, this should be rewritten | |
435 | // std::allocator_traits<Allocator>::construct(a, p); | |
436 | } | |
437 | ||
438 | /** | |
439 | * Class to copy-construct a view from a stored exemplar. | |
440 | */ | |
441 | template <typename Type, typename Allocator> | |
442 | class exemplar_init : public init_base<Type, Allocator> | |
443 | { | |
444 | typedef init_base<Type, Allocator> base; | |
445 | ||
446 | Type* m_exemplar; | |
447 | ||
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); | |
452 | #endif | |
453 | ||
454 | // Non-copyiable | |
455 | exemplar_init(const exemplar_init&); | |
456 | exemplar_init& operator=(const exemplar_init&); | |
457 | ||
458 | public: | |
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()); | |
465 | #endif | |
466 | ||
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; | |
472 | }; | |
473 | ||
474 | template <typename Type, typename Allocator> | |
475 | exemplar_init<Type, Allocator>::exemplar_init(const Type& val, | |
476 | Allocator& a) | |
477 | { | |
478 | m_exemplar = a.allocate(1); | |
479 | auto_deallocator<Type, Allocator> guard(m_exemplar, a); | |
480 | a.construct(m_exemplar, val); | |
481 | guard.release(); | |
482 | } | |
483 | ||
484 | #ifdef __CILKRTS_RVALUE_REFERENCES | |
485 | template <typename Type, typename Allocator> | |
486 | exemplar_init<Type, Allocator>::exemplar_init(Type&& val, | |
487 | Allocator& a) | |
488 | { | |
489 | m_exemplar = a.allocate(1); | |
490 | auto_deallocator<Type, Allocator> guard(m_exemplar, a); | |
491 | a.construct(m_exemplar, std::forward<Type>(val)); | |
492 | guard.release(); | |
493 | } | |
494 | #endif | |
495 | ||
496 | template <typename Type, typename Allocator> | |
497 | exemplar_init<Type, Allocator>* | |
498 | exemplar_init<Type, Allocator>::make(const Type& val, | |
499 | Allocator& a) | |
500 | { | |
501 | typedef typename Allocator::template rebind<exemplar_init>::other | |
502 | self_alloc_t; | |
503 | self_alloc_t alloc(a); | |
504 | ||
505 | exemplar_init *self = alloc.allocate(1); | |
506 | auto_deallocator<exemplar_init, self_alloc_t> guard(self, alloc); | |
507 | ||
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); | |
511 | ||
512 | guard.release(); | |
513 | ||
514 | return self; | |
515 | } | |
516 | ||
517 | #ifdef __CILKRTS_RVALUE_REFERENCES | |
518 | template <typename Type, typename Allocator> | |
519 | exemplar_init<Type, Allocator>* | |
520 | exemplar_init<Type, Allocator>::make(Type&& val, | |
521 | Allocator& a) | |
522 | { | |
523 | typedef typename Allocator::template rebind<exemplar_init>::other | |
524 | self_alloc_t; | |
525 | self_alloc_t alloc(a); | |
526 | ||
527 | exemplar_init *self = alloc.allocate(1); | |
528 | auto_deallocator<exemplar_init, self_alloc_t> guard(self, alloc); | |
529 | ||
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); | |
533 | ||
534 | guard.release(); | |
535 | ||
536 | return self; | |
537 | } | |
538 | #endif | |
539 | ||
540 | template <typename Type, typename Allocator> | |
541 | exemplar_init<Type, Allocator>::~exemplar_init() | |
542 | { | |
543 | // Called only by delete_self, which deleted the exemplar using an | |
544 | // allocator. | |
545 | __CILKRTS_ASSERT(0 == m_exemplar); | |
546 | } | |
547 | ||
548 | template <typename Type, typename Allocator> | |
549 | init_base<Type, Allocator>* | |
550 | exemplar_init<Type, Allocator>::clone_self(Allocator& a) const | |
551 | { | |
552 | return make(*m_exemplar, a); | |
553 | } | |
554 | ||
555 | template <typename Type, typename Allocator> | |
556 | void exemplar_init<Type, Allocator>::delete_self(Allocator& a) | |
557 | { | |
558 | typename Allocator::template rebind<exemplar_init>::other alloc(a); | |
559 | ||
560 | a.destroy(m_exemplar); | |
561 | a.deallocate(m_exemplar, 1); | |
562 | m_exemplar = 0; | |
563 | ||
564 | this->~exemplar_init(); | |
565 | alloc.deallocate(this, 1); | |
566 | } | |
567 | ||
568 | template <typename Type, typename Allocator> | |
569 | void | |
570 | exemplar_init<Type, Allocator>::construct_view(Type* p, | |
571 | Allocator& a) const | |
572 | { | |
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); | |
576 | } | |
577 | ||
578 | /** | |
579 | * Class to construct a view using a stored functor. The functor, | |
580 | * 'f', must be be invokable using the expression 'Type x = f()'. | |
581 | */ | |
582 | template <typename Func, typename Allocator> | |
583 | class functor_init : | |
584 | public init_base<typename Allocator::value_type, Allocator> | |
585 | { | |
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; | |
589 | ||
590 | Func *m_functor; | |
591 | ||
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); | |
596 | #endif | |
597 | ||
598 | // Non-copiable | |
599 | functor_init(const functor_init&); | |
600 | functor_init& operator=(const functor_init&); | |
601 | ||
602 | public: | |
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()); | |
609 | #endif | |
610 | ||
611 | // Virtual function overrides | |
612 | virtual ~functor_init(); | |
613 | virtual base* clone_self(Allocator& a) const; | |
614 | virtual void delete_self(Allocator& a); | |
615 | virtual void | |
616 | construct_view(value_type* p, Allocator& a) const; | |
617 | }; | |
618 | ||
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> { }; | |
623 | ||
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> { }; | |
628 | ||
629 | template <typename Func, typename Allocator> | |
630 | functor_init<Func, Allocator>::functor_init(const Func& f, | |
631 | Allocator& a) | |
632 | { | |
633 | f_alloc alloc(a); | |
634 | ||
635 | m_functor = alloc.allocate(1); | |
636 | auto_deallocator<Func, f_alloc> guard(m_functor, alloc); | |
637 | alloc.construct(m_functor, f); | |
638 | guard.release(); | |
639 | } | |
640 | ||
641 | #ifdef __CILKRTS_RVALUE_REFERENCES | |
642 | template <typename Func, typename Allocator> | |
643 | functor_init<Func, Allocator>::functor_init(Func&& f, | |
644 | Allocator& a) | |
645 | { | |
646 | f_alloc alloc(a); | |
647 | ||
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)); | |
651 | guard.release(); | |
652 | } | |
653 | #endif | |
654 | ||
655 | template <typename Func, typename Allocator> | |
656 | functor_init<Func, Allocator>* | |
657 | functor_init<Func, Allocator>::make(const Func& f, Allocator& a) | |
658 | { | |
659 | typedef typename Allocator::template rebind<functor_init>::other | |
660 | self_alloc_t; | |
661 | self_alloc_t alloc(a); | |
662 | ||
663 | functor_init *self = alloc.allocate(1); | |
664 | auto_deallocator<functor_init, self_alloc_t> guard(self, alloc); | |
665 | ||
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); | |
669 | ||
670 | guard.release(); | |
671 | ||
672 | return self; | |
673 | } | |
674 | ||
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) | |
679 | { | |
680 | typedef typename Allocator::template rebind<functor_init>::other | |
681 | self_alloc_t; | |
682 | self_alloc_t alloc(a); | |
683 | ||
684 | functor_init *self = alloc.allocate(1); | |
685 | auto_deallocator<functor_init, self_alloc_t> guard(self, alloc); | |
686 | ||
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); | |
690 | ||
691 | guard.release(); | |
692 | ||
693 | return self; | |
694 | } | |
695 | #endif | |
696 | ||
697 | template <typename Func, typename Allocator> | |
698 | functor_init<Func, Allocator>::~functor_init() | |
699 | { | |
700 | // Called only by delete_self, which deleted the functor using an | |
701 | // allocator. | |
702 | __CILKRTS_ASSERT(0 == m_functor); | |
703 | } | |
704 | ||
705 | template <typename Func, typename Allocator> | |
706 | init_base<typename Allocator::value_type, Allocator>* | |
707 | functor_init<Func, Allocator>::clone_self(Allocator& a) const | |
708 | { | |
709 | return make(*m_functor, a); | |
710 | } | |
711 | ||
712 | template <typename Func, typename Allocator> | |
713 | inline | |
714 | void functor_init<Func, Allocator>::delete_self(Allocator& a) | |
715 | { | |
716 | typename Allocator::template rebind<functor_init>::other alloc(a); | |
717 | f_alloc fa(a); | |
718 | ||
719 | fa.destroy(m_functor); | |
720 | fa.deallocate(m_functor, 1); | |
721 | m_functor = 0; | |
722 | ||
723 | this->~functor_init(); | |
724 | alloc.deallocate(this, 1); | |
725 | } | |
726 | ||
727 | template <typename Func, typename Allocator> | |
728 | void functor_init<Func, Allocator>::construct_view(value_type* p, | |
729 | Allocator& a) const | |
730 | { | |
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()); | |
734 | } | |
735 | ||
736 | /** | |
737 | * Functor called to reduce a holder | |
738 | */ | |
739 | template <typename Type, holder_policy Policy> | |
740 | struct holder_reduce_functor; | |
741 | ||
742 | /** | |
743 | * Specialization to keep the left (first) value. | |
744 | */ | |
745 | template <typename Type> | |
746 | struct holder_reduce_functor<Type, holder_keep_indeterminate> | |
747 | { | |
748 | void operator()(Type* left, Type* right) const { } | |
749 | }; | |
750 | ||
751 | /** | |
752 | * Specialization to copy-assign from the right (last) value. | |
753 | */ | |
754 | template <typename Type> | |
755 | struct holder_reduce_functor<Type, holder_keep_last_copy> | |
756 | { | |
757 | void operator()(Type* left, Type* right) const { | |
758 | *left = *right; | |
759 | } | |
760 | }; | |
761 | ||
762 | /* | |
763 | * Specialization to keep the right (last) value via swap. | |
764 | */ | |
765 | template <typename Type> | |
766 | struct holder_reduce_functor<Type, holder_keep_last_swap> | |
767 | { | |
768 | void operator()(Type* left, Type* right) const { | |
769 | using std::swap; | |
770 | swap(*left, *right); | |
771 | } | |
772 | }; | |
773 | ||
774 | #ifdef __CILKRTS_RVALUE_REFERENCES | |
775 | /* | |
776 | * Specialization to move-assign from the right (last) value. | |
777 | */ | |
778 | template <typename Type> | |
779 | struct holder_reduce_functor<Type, holder_keep_last_move> | |
780 | { | |
781 | void operator()(Type* left, Type* right) const { | |
782 | *left = std::move(*right); | |
783 | } | |
784 | }; | |
785 | #endif | |
786 | ||
787 | /* | |
788 | * Specialization to keep the right (last) value via the swap member | |
789 | * function. | |
790 | */ | |
791 | template <typename Type> | |
792 | struct holder_reduce_functor<Type, holder_keep_last_member_swap> | |
793 | { | |
794 | void operator()(Type* left, Type* right) const { | |
795 | left->swap(*right); | |
796 | } | |
797 | }; | |
798 | ||
799 | /* | |
800 | * Specialization to keep the right (last) value by the most efficient | |
801 | * means detectable. | |
802 | */ | |
803 | template <typename Type> | |
804 | struct holder_reduce_functor<Type, holder_keep_last> : | |
805 | holder_reduce_functor<Type, | |
806 | (holder_policy) | |
807 | (has_member_swap<Type>::value ? | |
808 | holder_keep_last_member_swap : | |
809 | #ifdef __CILKRTS_RVALUE_REFERENCES | |
810 | holder_keep_last_move | |
811 | #else | |
812 | holder_keep_last_copy | |
813 | #endif | |
814 | )> | |
815 | { | |
816 | }; | |
817 | } // end namespace internal | |
818 | ||
819 | /** | |
820 | * Monoid for holders. | |
821 | * Allocator type is required to be thread-safe. | |
822 | */ | |
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> | |
827 | { | |
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; | |
834 | ||
835 | public: | |
836 | /// This constructor uses default-initialization for both the leftmost | |
837 | /// view and each identity view. | |
838 | holder_monoid(const Allocator& a = Allocator()) | |
839 | : m_allocator(a) | |
840 | , m_initializer( | |
841 | internal::default_init<Type, Allocator>::make(m_allocator)) | |
842 | { } | |
843 | ||
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()) | |
847 | : m_allocator(a) | |
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()) | |
854 | : m_allocator(a) | |
855 | , m_initializer( | |
856 | internal::functor_init<Func, Allocator>::make(f,m_allocator)) | |
857 | { } | |
858 | ||
859 | /// Copy constructor | |
860 | holder_monoid(const holder_monoid& rhs) | |
861 | : m_allocator(rhs.m_allocator) | |
862 | , m_initializer(rhs.m_initializer->clone_self(m_allocator)) { } | |
863 | ||
864 | /// "Extended" copy constructor with allocator | |
865 | holder_monoid(const holder_monoid& rhs, const Allocator& a) | |
866 | : m_allocator(a) | |
867 | , m_initializer(rhs.m_initializer->clone_self(m_allocator)) { } | |
868 | ||
869 | #ifdef __CILKRTS_RVALUE_REFERENCES | |
870 | /// Move constructor | |
871 | holder_monoid(holder_monoid&& rhs) | |
872 | : m_allocator(rhs.m_allocator) | |
873 | , m_initializer(rhs.m_initializer) { | |
874 | rhs.m_initializer = | |
875 | internal::default_init<Type, Allocator>::make(m_allocator); | |
876 | } | |
877 | ||
878 | /// "Extended" move constructor with allocator | |
879 | holder_monoid(holder_monoid&& rhs, const Allocator& a) | |
880 | : m_allocator(a) | |
881 | , m_initializer(0) { | |
882 | if (a != rhs.m_allocator) | |
883 | m_initializer = rhs.m_initializer->clone_self(a); | |
884 | else { | |
885 | m_initializer = rhs.m_initializer; | |
886 | rhs.m_initializer = | |
887 | internal::default_init<Type, Allocator>::make(m_allocator); | |
888 | } | |
889 | } | |
890 | #endif | |
891 | /// Destructor | |
892 | ~holder_monoid() { m_initializer->delete_self(m_allocator); } | |
893 | ||
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); | |
898 | } | |
899 | ||
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); | |
906 | return *this; | |
907 | } | |
908 | #endif | |
909 | ||
910 | /// Constructs IDENTITY value into the uninitilized '*p' | |
911 | void identity(Type* p) const | |
912 | { m_initializer->construct_view(p, m_allocator); } | |
913 | ||
914 | /// Calls the destructor on the object pointed-to by 'p' | |
915 | void destroy(Type* p) const | |
916 | { m_allocator.destroy(p); } | |
917 | ||
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); | |
922 | } | |
923 | ||
924 | /// Deallocate the raw memory at p | |
925 | void deallocate(void* p) const { | |
926 | m_allocator.deallocate(static_cast<Type*>(p), sizeof(Type)); | |
927 | } | |
928 | ||
929 | void reduce(Type* left, Type* right) const { | |
930 | internal::holder_reduce_functor<Type, Policy>()(left, right); | |
931 | } | |
932 | ||
933 | void swap(holder_monoid& other) { | |
934 | __CILKRTS_ASSERT(m_allocator == other.m_allocator); | |
935 | std::swap(m_initializer, other.m_initializer); | |
936 | } | |
937 | ||
938 | Allocator get_allocator() const { | |
939 | return m_allocator; | |
940 | } | |
941 | }; | |
942 | ||
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) | |
947 | { | |
948 | a.swap(b); | |
949 | } | |
950 | ||
951 | /** | |
952 | * Hyperobject to provide different views of an object to each | |
953 | * parallel strand. | |
954 | */ | |
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> > | |
959 | { | |
960 | typedef holder_monoid<Type, Policy, Allocator> monoid_type; | |
961 | typedef reducer<monoid_type> imp; | |
962 | ||
963 | // Return a value of Type constructed using the functor Func. | |
964 | template <typename Func> | |
965 | Type make_value(const Func& f) const { | |
966 | struct obj { | |
967 | union { | |
968 | char buf[sizeof(Type)]; | |
969 | void* align1; | |
970 | double align2; | |
971 | }; | |
972 | ||
973 | obj(const Func& f) { f(static_cast<Type*>(buf)); } | |
974 | ~obj() { static_cast<Type*>(buf)->~Type(); } | |
975 | ||
976 | operator Type&() { return *static_cast<Type*>(buf); } | |
977 | }; | |
978 | ||
979 | return obj(f); | |
980 | } | |
981 | ||
982 | public: | |
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)) { } | |
987 | ||
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) { } | |
994 | ||
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)) { } | |
1003 | }; | |
1004 | ||
1005 | } // end namespace cilk | |
1006 | ||
1007 | #else /* C */ | |
1008 | # error Holders are currently available only for C++ | |
1009 | #endif /* __cplusplus */ | |
1010 | ||
1011 | #endif /* HOLDER_H_INCLUDED */ |