1/* 2 * @copyright 3 * Copyright (C) 2011-2013, Intel Corporation 4 * All rights reserved. 5 * 6 * @copyright 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 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 16 * distribution. 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. 20 * 21 * @copyright 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. 34 * 35 */ 36 37/* 38 * holder.h 39 * 40 * Purpose: hyperobject to provide different views of an object to each 41 * parallel strand. 42 */ 43 44#ifndef HOLDER_H_INCLUDED 45#define HOLDER_H_INCLUDED 46 47#include <cilk/reducer.h> 48#include <memory> 49#include <utility> 50 51#ifdef __cplusplus 52 53/* C++ Interface 54 * 55 * Classes: holder<Type> 56 * 57 * Description: 58 * ============ 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 64 * qualities: 65 * 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 70 * function. 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 73 * the loop. 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 77 * situations. 78 * 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. 90 * 91 * Usage Example: 92 * ============== 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. 98 *.. 99 * hash_table<int, X> memos; 100 * 101 * void h(const X& x); // Uses memos 102 * 103 * double compute(const X& x) 104 * { 105 * memos.clear(); 106 * // ... 107 * memos[i] = x; 108 * ... 109 * g(i); // Uses memos 110 * // ... 111 * std::for_each(c.begin(), c.end(), h); // Call h for each element of c 112 * } 113 * 114 * int main() 115 * { 116 * const std::size_t ARRAY_SIZE = 1000000; 117 * extern X myArray[ARRAY_SIZE]; 118 * 119 * for (std::size_t i = 0; i < ARRAY_SIZE; ++i) 120 * { 121 * compute(myArray[i]); 122 * } 123 * } 124 *.. 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: 133 *.. 134 * cilk_for (std::size_t i = 0; i < ARRAY_SIZE; ++i) 135 * { 136 * hash_table<int, X> memos; 137 * compute(myArray[i], memos); 138 * } 139 *.. 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. 148 * 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 153 * holder: 154 *.. 155 * cilk::holder<hash_table<int, X> > memos_h; 156 * 157 * void h(const X& x); // Uses memos_h 158 * 159 * double compute(const X& x) 160 * { 161 * memos_h().clear(); // operator() used to "dereference" the holder 162 * // ... 163 * memos_h()[i] = x; // operator() used to "dereference" the holder 164 * ... 165 * g(i); // Uses memos_h 166 * // ... 167 * std::for_each(c.begin(), c.end(), h); // Call h for each element of c 168 * } 169 *.. 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: 176 *.. 177 * template <typename K, typename V> 178 * class hash_table_holder 179 * { 180 * private: 181 * cilk::holder<hash_table<K, V> > m_holder; 182 * public: 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(); } 186 * // etc. ... 187 * }; 188 *.. 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 191 * 'cilk_for': 192 *.. 193 * hash_table_holder<int, X> memos; 194 * 195 * void h(const X& x); // Uses memos 196 * 197 * double compute(const X& x) 198 * { 199 * memos.clear(); // Calls hash_table_holder::clear(). 200 * // ... 201 * } 202 *.. 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? 205 *.. 206 * void h(const X& x) 207 * { 208 * Y y = x.nested(); 209 * double d, w; 210 * if (y) 211 * { 212 * w = cilk_spawn compute_width(y); // May use 'memos' 213 * d = compute_depth(y); // Does not use 'memos' 214 * cilk_sync; 215 * compute(y); // recursive call. Uses 'memos'. 216 * } 217 * } 218 *.. 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. 225 */ 226 227namespace cilk { 228 229 /** 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 250 * copy-assignment.) 251 * 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 261 * storage. 262 */ 263 enum holder_policy { 264 holder_keep_indeterminate, 265 holder_keep_last, 266 holder_keep_last_copy, 267 holder_keep_last_swap, 268#ifdef __CILKRTS_RVALUE_REFERENCES 269 holder_keep_last_move 270#endif 271 }; 272 273 namespace internal { 274 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); 278 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. 287 */ 288 template <typename T> 289 class has_member_swap 290 { 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 294 295 // sizeof(notchar) is guaranteed larger than 1 296 struct notchar { char x[2]; }; 297 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 { }; 301 302 // First 'test' is preferred overload if U::swap exists with the 303 // correct prototype. Second 'test' is preferred overload 304 // otherwise. 305 template <typename U> static char test(Q<U,&U::swap>*); 306 template <typename U> static notchar test(...); 307 308 public: 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))); 312 }; 313 314 template <typename T> const bool has_member_swap<T>::value; 315 316 /** 317 * @brief Utility class for exception safety. 318 * 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. 326 */ 327 template <typename Type, typename Allocator = std::allocator<Type> > 328 class auto_deallocator 329 { 330 Allocator m_alloc; 331 Type* m_ptr; 332 333 // Non-copiable 334 auto_deallocator(const auto_deallocator&); 335 auto_deallocator& operator=(const auto_deallocator&); 336 337 public: 338 /// Constructor 339 explicit auto_deallocator(Type* p, const Allocator& a = Allocator()) 340 : m_alloc(a), m_ptr(p) { } 341 342 /// Destructor - free allocated resources 343 ~auto_deallocator() { if (m_ptr) m_alloc.deallocate(m_ptr, 1); } 344 345 /// Remove reference to resource 346 void release() { m_ptr = 0; } 347 }; 348 349 /** 350 * Pure-abstract base class to initialize holder views 351 */ 352 template <typename Type, typename Allocator> 353 class init_base 354 { 355 public: 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; 360 }; 361 362 /** 363 * Class to default-initialize a holder view 364 */ 365 template <typename Type, typename Allocator> 366 class default_init : public init_base<Type, Allocator> 367 { 368 typedef init_base<Type, Allocator> base; 369 370 /// Private constructor (called from static make() function). 371 default_init() { } 372 373 // Non-copiable 374 default_init(const default_init&); 375 default_init& operator=(const default_init&); 376 377 public: 378 // Static factory function 379 static default_init* make(Allocator& a); 380 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; 386 }; 387 388 template <typename Type, typename Allocator> 389 default_init<Type, Allocator>* 390 default_init<Type, Allocator>::make(Allocator&) 391 { 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; 395 return &self; 396 } 397 398 template <typename Type, typename Allocator> 399 default_init<Type, Allocator>::~default_init() 400 { 401 } 402 403 template <typename Type, typename Allocator> 404 init_base<Type, Allocator>* 405 default_init<Type, Allocator>::clone_self(Allocator& a) const 406 { 407 return make(a); 408 } 409 410 template <typename Type, typename Allocator> 411 void default_init<Type, Allocator>::delete_self(Allocator&) 412 { 413 // Since make() returned a shared singleton, there is nothing to 414 // delete here. 415 } 416 417 template <typename Type, typename Allocator> 418 void 419 default_init<Type, Allocator>::construct_view(Type* p, 420 Allocator&) const 421 { 422 ::new((void*) p) Type(); 423 // TBD: In a C++0x library, this should be rewritten 424 // std::allocator_traits<Allocator>::construct(a, p); 425 } 426 427 /** 428 * Class to copy-construct a view from a stored exemplar. 429 */ 430 template <typename Type, typename Allocator> 431 class exemplar_init : public init_base<Type, Allocator> 432 { 433 typedef init_base<Type, Allocator> base; 434 435 Type* m_exemplar; 436 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); 441#endif 442 443 // Non-copyiable 444 exemplar_init(const exemplar_init&); 445 exemplar_init& operator=(const exemplar_init&); 446 447 public: 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()); 454#endif 455 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; 461 }; 462 463 template <typename Type, typename Allocator> 464 exemplar_init<Type, Allocator>::exemplar_init(const Type& val, 465 Allocator& a) 466 { 467 m_exemplar = a.allocate(1); 468 auto_deallocator<Type, Allocator> guard(m_exemplar, a); 469 a.construct(m_exemplar, val); 470 guard.release(); 471 } 472 473#ifdef __CILKRTS_RVALUE_REFERENCES 474 template <typename Type, typename Allocator> 475 exemplar_init<Type, Allocator>::exemplar_init(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, std::forward<Type>(val)); 481 guard.release(); 482 } 483#endif 484 485 template <typename Type, typename Allocator> 486 exemplar_init<Type, Allocator>* 487 exemplar_init<Type, Allocator>::make(const Type& val, 488 Allocator& a) 489 { 490 typedef typename Allocator::template rebind<exemplar_init>::other 491 self_alloc_t; 492 self_alloc_t alloc(a); 493 494 exemplar_init *self = alloc.allocate(1); 495 auto_deallocator<exemplar_init, self_alloc_t> guard(self, alloc); 496 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); 500 501 guard.release(); 502 503 return self; 504 } 505 506#ifdef __CILKRTS_RVALUE_REFERENCES 507 template <typename Type, typename Allocator> 508 exemplar_init<Type, Allocator>* 509 exemplar_init<Type, Allocator>::make(Type&& val, 510 Allocator& a) 511 { 512 typedef typename Allocator::template rebind<exemplar_init>::other 513 self_alloc_t; 514 self_alloc_t alloc(a); 515 516 exemplar_init *self = alloc.allocate(1); 517 auto_deallocator<exemplar_init, self_alloc_t> guard(self, alloc); 518 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); 522 523 guard.release(); 524 525 return self; 526 } 527#endif 528 529 template <typename Type, typename Allocator> 530 exemplar_init<Type, Allocator>::~exemplar_init() 531 { 532 // Called only by delete_self, which deleted the exemplar using an 533 // allocator. 534 __CILKRTS_ASSERT(0 == m_exemplar); 535 } 536 537 template <typename Type, typename Allocator> 538 init_base<Type, Allocator>* 539 exemplar_init<Type, Allocator>::clone_self(Allocator& a) const 540 { 541 return make(*m_exemplar, a); 542 } 543 544 template <typename Type, typename Allocator> 545 void exemplar_init<Type, Allocator>::delete_self(Allocator& a) 546 { 547 typename Allocator::template rebind<exemplar_init>::other alloc(a); 548 549 a.destroy(m_exemplar); 550 a.deallocate(m_exemplar, 1); 551 m_exemplar = 0; 552 553 this->~exemplar_init(); 554 alloc.deallocate(this, 1); 555 } 556 557 template <typename Type, typename Allocator> 558 void 559 exemplar_init<Type, Allocator>::construct_view(Type* p, 560 Allocator& a) const 561 { 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); 565 } 566 567 /** 568 * Class to construct a view using a stored functor. The functor, 569 * 'f', must be be invokable using the expression 'Type x = f()'. 570 */ 571 template <typename Func, typename Allocator> 572 class functor_init : 573 public init_base<typename Allocator::value_type, Allocator> 574 { 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; 578 579 Func *m_functor; 580 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); 585#endif 586 587 // Non-copiable 588 functor_init(const functor_init&); 589 functor_init& operator=(const functor_init&); 590 591 public: 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()); 598#endif 599 600 // Virtual function overrides 601 virtual ~functor_init(); 602 virtual base* clone_self(Allocator& a) const; 603 virtual void delete_self(Allocator& a); 604 virtual void 605 construct_view(value_type* p, Allocator& a) const; 606 }; 607 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> { }; 612 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> { }; 617 618 template <typename Func, typename Allocator> 619 functor_init<Func, Allocator>::functor_init(const Func& f, 620 Allocator& a) 621 { 622 f_alloc alloc(a); 623 624 m_functor = alloc.allocate(1); 625 auto_deallocator<Func, f_alloc> guard(m_functor, alloc); 626 alloc.construct(m_functor, f); 627 guard.release(); 628 } 629 630#ifdef __CILKRTS_RVALUE_REFERENCES 631 template <typename Func, typename Allocator> 632 functor_init<Func, Allocator>::functor_init(Func&& f, 633 Allocator& a) 634 { 635 f_alloc alloc(a); 636 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)); 640 guard.release(); 641 } 642#endif 643 644 template <typename Func, typename Allocator> 645 functor_init<Func, Allocator>* 646 functor_init<Func, Allocator>::make(const Func& f, Allocator& a) 647 { 648 typedef typename Allocator::template rebind<functor_init>::other 649 self_alloc_t; 650 self_alloc_t alloc(a); 651 652 functor_init *self = alloc.allocate(1); 653 auto_deallocator<functor_init, self_alloc_t> guard(self, alloc); 654 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); 658 659 guard.release(); 660 661 return self; 662 } 663 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) 668 { 669 typedef typename Allocator::template rebind<functor_init>::other 670 self_alloc_t; 671 self_alloc_t alloc(a); 672 673 functor_init *self = alloc.allocate(1); 674 auto_deallocator<functor_init, self_alloc_t> guard(self, alloc); 675 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); 679 680 guard.release(); 681 682 return self; 683 } 684#endif 685 686 template <typename Func, typename Allocator> 687 functor_init<Func, Allocator>::~functor_init() 688 { 689 // Called only by delete_self, which deleted the functor using an 690 // allocator. 691 __CILKRTS_ASSERT(0 == m_functor); 692 } 693 694 template <typename Func, typename Allocator> 695 init_base<typename Allocator::value_type, Allocator>* 696 functor_init<Func, Allocator>::clone_self(Allocator& a) const 697 { 698 return make(*m_functor, a); 699 } 700 701 template <typename Func, typename Allocator> 702 inline 703 void functor_init<Func, Allocator>::delete_self(Allocator& a) 704 { 705 typename Allocator::template rebind<functor_init>::other alloc(a); 706 f_alloc fa(a); 707 708 fa.destroy(m_functor); 709 fa.deallocate(m_functor, 1); 710 m_functor = 0; 711 712 this->~functor_init(); 713 alloc.deallocate(this, 1); 714 } 715 716 template <typename Func, typename Allocator> 717 void functor_init<Func, Allocator>::construct_view(value_type* p, 718 Allocator& a) const 719 { 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()); 723 } 724 725 /** 726 * Functor called to reduce a holder 727 */ 728 template <typename Type, holder_policy Policy> 729 struct holder_reduce_functor; 730 731 /** 732 * Specialization to keep the left (first) value. 733 */ 734 template <typename Type> 735 struct holder_reduce_functor<Type, holder_keep_indeterminate> 736 { 737 void operator()(Type* left, Type* right) const { } 738 }; 739 740 /** 741 * Specialization to copy-assign from the right (last) value. 742 */ 743 template <typename Type> 744 struct holder_reduce_functor<Type, holder_keep_last_copy> 745 { 746 void operator()(Type* left, Type* right) const { 747 *left = *right; 748 } 749 }; 750 751 /* 752 * Specialization to keep the right (last) value via swap. 753 */ 754 template <typename Type> 755 struct holder_reduce_functor<Type, holder_keep_last_swap> 756 { 757 void operator()(Type* left, Type* right) const { 758 using std::swap; 759 swap(*left, *right); 760 } 761 }; 762 763#ifdef __CILKRTS_RVALUE_REFERENCES 764 /* 765 * Specialization to move-assign from the right (last) value. 766 */ 767 template <typename Type> 768 struct holder_reduce_functor<Type, holder_keep_last_move> 769 { 770 void operator()(Type* left, Type* right) const { 771 *left = std::move(*right); 772 } 773 }; 774#endif 775 776 /* 777 * Specialization to keep the right (last) value via the swap member 778 * function. 779 */ 780 template <typename Type> 781 struct holder_reduce_functor<Type, holder_keep_last_member_swap> 782 { 783 void operator()(Type* left, Type* right) const { 784 left->swap(*right); 785 } 786 }; 787 788 /* 789 * Specialization to keep the right (last) value by the most efficient 790 * means detectable. 791 */ 792 template <typename Type> 793 struct holder_reduce_functor<Type, holder_keep_last> : 794 holder_reduce_functor<Type, 795 (holder_policy) 796 (has_member_swap<Type>::value ? 797 holder_keep_last_member_swap : 798#ifdef __CILKRTS_RVALUE_REFERENCES 799 holder_keep_last_move 800#else 801 holder_keep_last_copy 802#endif 803 )> 804 { 805 }; 806 } // end namespace internal 807 808 /** 809 * Monoid for holders. 810 * Allocator type is required to be thread-safe. 811 */ 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> 816 { 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; 823 824 public: 825 /// This constructor uses default-initialization for both the leftmost 826 /// view and each identity view. 827 holder_monoid(const Allocator& a = Allocator()) 828 : m_allocator(a) 829 , m_initializer( 830 internal::default_init<Type, Allocator>::make(m_allocator)) 831 { } 832 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()) 836 : m_allocator(a) 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()) 843 : m_allocator(a) 844 , m_initializer( 845 internal::functor_init<Func, Allocator>::make(f,m_allocator)) 846 { } 847 848 /// Copy constructor 849 holder_monoid(const holder_monoid& rhs) 850 : m_allocator(rhs.m_allocator) 851 , m_initializer(rhs.m_initializer->clone_self(m_allocator)) { } 852 853 /// "Extended" copy constructor with allocator 854 holder_monoid(const holder_monoid& rhs, const Allocator& a) 855 : m_allocator(a) 856 , m_initializer(rhs.m_initializer->clone_self(m_allocator)) { } 857 858#ifdef __CILKRTS_RVALUE_REFERENCES 859 /// Move constructor 860 holder_monoid(holder_monoid&& rhs) 861 : m_allocator(rhs.m_allocator) 862 , m_initializer(rhs.m_initializer) { 863 rhs.m_initializer = 864 internal::default_init<Type, Allocator>::make(m_allocator); 865 } 866 867 /// "Extended" move constructor with allocator 868 holder_monoid(holder_monoid&& rhs, const Allocator& a) 869 : m_allocator(a) 870 , m_initializer(0) { 871 if (a != rhs.m_allocator) 872 m_initializer = rhs.m_initializer->clone_self(a); 873 else { 874 m_initializer = rhs.m_initializer; 875 rhs.m_initializer = 876 internal::default_init<Type, Allocator>::make(m_allocator); 877 } 878 } 879#endif 880 /// Destructor 881 ~holder_monoid() { m_initializer->delete_self(m_allocator); } 882 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); 887 } 888 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); 895 return *this; 896 } 897#endif 898 899 /// Constructs IDENTITY value into the uninitilized '*p' 900 void identity(Type* p) const 901 { m_initializer->construct_view(p, m_allocator); } 902 903 /// Calls the destructor on the object pointed-to by 'p' 904 void destroy(Type* p) const 905 { m_allocator.destroy(p); } 906 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); 911 } 912 913 /// Deallocate the raw memory at p 914 void deallocate(void* p) const { 915 m_allocator.deallocate(static_cast<Type*>(p), sizeof(Type)); 916 } 917 918 void reduce(Type* left, Type* right) const { 919 internal::holder_reduce_functor<Type, Policy>()(left, right); 920 } 921 922 void swap(holder_monoid& other) { 923 __CILKRTS_ASSERT(m_allocator == other.m_allocator); 924 std::swap(m_initializer, other.m_initializer); 925 } 926 927 Allocator get_allocator() const { 928 return m_allocator; 929 } 930 }; 931 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) 936 { 937 a.swap(b); 938 } 939 940 /** 941 * Hyperobject to provide different views of an object to each 942 * parallel strand. 943 */ 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> > 948 { 949 typedef holder_monoid<Type, Policy, Allocator> monoid_type; 950 typedef reducer<monoid_type> imp; 951 952 // Return a value of Type constructed using the functor Func. 953 template <typename Func> 954 Type make_value(const Func& f) const { 955 struct obj { 956 union { 957 char buf[sizeof(Type)]; 958 void* align1; 959 double align2; 960 }; 961 962 obj(const Func& f) { f(static_cast<Type*>(buf)); } 963 ~obj() { static_cast<Type*>(buf)->~Type(); } 964 965 operator Type&() { return *static_cast<Type*>(buf); } 966 }; 967 968 return obj(f); 969 } 970 971 public: 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)) { } 976 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) { } 983 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)) { } 992 }; 993 994} // end namespace cilk 995 996#else /* C */ 997# error Holders are currently available only for C++ 998#endif /* __cplusplus */ 999 1000#endif /* HOLDER_H_INCLUDED */ 1001