git.sesse.net Git - casparcg/blob - tbb30_20100406oss/include/tbb/enumerable_thread_specific.h

   1 /*
   2     Copyright 2005-2010 Intel Corporation.  All Rights Reserved.
   3
   4     This file is part of Threading Building Blocks.
   5
   6     Threading Building Blocks is free software; you can redistribute it
   7     and/or modify it under the terms of the GNU General Public License
   8     version 2 as published by the Free Software Foundation.
   9
  10     Threading Building Blocks is distributed in the hope that it will be
  11     useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  12     of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with Threading Building Blocks; if not, write to the Free Software
  17     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18
  19     As a special exception, you may use this file as part of a free software
  20     library without restriction.  Specifically, if other files instantiate
  21     templates or use macros or inline functions from this file, or you compile
  22     this file and link it with other files to produce an executable, this
  23     file does not by itself cause the resulting executable to be covered by
  24     the GNU General Public License.  This exception does not however
  25     invalidate any other reasons why the executable file might be covered by
  26     the GNU General Public License.
  27 */
  28
  29 #ifndef __TBB_enumerable_thread_specific_H
  30 #define __TBB_enumerable_thread_specific_H
  31
  32 #include "concurrent_vector.h"
  33 #include "tbb_thread.h"
  34 #include "cache_aligned_allocator.h"
  35 #if __SUNPRO_CC
  36 #include <string.h>  // for memcpy
  37 #endif
  38
  39 #if _WIN32||_WIN64
  40 #include <windows.h>
  41 #else
  42 #include <pthread.h>
  43 #endif
  44
  45 namespace tbb {
  46
  47 //! enum for selecting between single key and key-per-instance versions
  48 enum ets_key_usage_type { ets_key_per_instance, ets_no_key };
  49
  50 namespace interface5 {
  51
  52     //! @cond
  53     namespace internal {
  54
  55         template<ets_key_usage_type ETS_key_type>
  56         class ets_base: tbb::internal::no_copy {
  57         protected:
  58 #if _WIN32||_WIN64
  59             typedef DWORD key_type;
  60 #else
  61             typedef pthread_t key_type;
  62 #endif
  63 #if __TBB_GCC_3_3_PROTECTED_BROKEN
  64         public:
  65 #endif
  66             struct slot;
  67
  68             struct array {
  69                 array* next;
  70                 size_t lg_size;
  71                 slot& at( size_t k ) {
  72                     return ((slot*)(void*)(this+1))[k];
  73                 }
  74                 size_t size() const {return (size_t)1<<lg_size;}
  75                 size_t mask() const {return size()-1;}
  76                 size_t start( size_t h ) const {
  77                     return h>>(8*sizeof(size_t)-lg_size);
  78                 }
  79             };
  80             struct slot {
  81                 key_type key;
  82                 void* ptr;
  83                 bool empty() const {return !key;}
  84                 bool match( key_type k ) const {return key==k;}
  85                 bool claim( key_type k ) {
  86                     __TBB_ASSERT(sizeof(tbb::atomic<key_type>)==sizeof(key_type), NULL);
  87                     __TBB_ASSERT(sizeof(void*)==sizeof(tbb::atomic<key_type>*), NULL);
  88                     union { void* space; tbb::atomic<key_type>* key_atomic; } helper;
  89                     helper.space = &key;
  90                     return helper.key_atomic->compare_and_swap(k,0)==0;
  91                 }
  92             };
  93 #if __TBB_GCC_3_3_PROTECTED_BROKEN
  94         protected:
  95 #endif
  96
  97             static key_type key_of_current_thread() {
  98                tbb::tbb_thread::id id = tbb::this_tbb_thread::get_id();
  99                key_type k;
 100                memcpy( &k, &id, sizeof(k) );
 101                return k;
 102             }
 103
 104             //! Root of linked list of arrays of decreasing size.
 105             /** NULL if and only if my_count==0.
 106                 Each array in the list is half the size of its predecessor. */
 107             atomic<array*> my_root;
 108             atomic<size_t> my_count;
 109             virtual void* create_local() = 0;
 110             virtual void* create_array(size_t _size) = 0;  // _size in bytes
 111             virtual void free_array(void* ptr, size_t _size) = 0; // _size in bytes
 112             array* allocate( size_t lg_size ) {
 113                 size_t n = 1<<lg_size;
 114                 array* a = static_cast<array*>(create_array( sizeof(array)+n*sizeof(slot) ));
 115                 a->lg_size = lg_size;
 116                 std::memset( a+1, 0, n*sizeof(slot) );
 117                 return a;
 118             }
 119             void free(array* a) {
 120                 size_t n = 1<<(a->lg_size);
 121                 free_array( (void *)a, size_t(sizeof(array)+n*sizeof(slot)) );
 122             }
 123             static size_t hash( key_type k ) {
 124                 // Multiplicative hashing.  Client should use *upper* bits.
 125                 // casts required for Mac gcc4.* compiler
 126 #if __TBB_WORDSIZE == 4
 127                 return uintptr_t(k)*0x9E3779B9;
 128 #else
 129                 return uintptr_t(k)*0x9E3779B97F4A7C15;
 130 #endif
 131             }
 132
 133             ets_base() {my_root=NULL; my_count=0;}
 134             virtual ~ets_base();  // g++ complains if this is not virtual...
 135             void* table_lookup( bool& exists );
 136             void table_clear();
 137             slot& table_find( key_type k ) {
 138                 size_t h = hash(k);
 139                 array* r = my_root;
 140                 size_t mask = r->mask();
 141                 for(size_t i = r->start(h);;i=(i+1)&mask) {
 142                     slot& s = r->at(i);
 143                     if( s.empty() || s.match(k) )
 144                         return s;
 145                 }
 146             }
 147             void table_reserve_for_copy( const ets_base& other ) {
 148                 __TBB_ASSERT(!my_root,NULL);
 149                 __TBB_ASSERT(!my_count,NULL);
 150                 if( other.my_root ) {
 151                     array* a = allocate(other.my_root->lg_size);
 152                     a->next = NULL;
 153                     my_root = a;
 154                     my_count = other.my_count;
 155                 }
 156             }
 157         };
 158
 159         template<ets_key_usage_type ETS_key_type>
 160         ets_base<ETS_key_type>::~ets_base() {
 161             __TBB_ASSERT(!my_root, NULL);
 162         }
 163
 164         template<ets_key_usage_type ETS_key_type>
 165         void ets_base<ETS_key_type>::table_clear() {
 166             while( array* r = my_root ) {
 167                 my_root = r->next;
 168                 free(r);
 169             }
 170             my_count = 0;
 171         }
 172
 173         template<ets_key_usage_type ETS_key_type>
 174         void* ets_base<ETS_key_type>::table_lookup( bool& exists ) {
 175             const key_type k = key_of_current_thread();
 176
 177             __TBB_ASSERT(k!=0,NULL);
 178             void* found;
 179             size_t h = hash(k);
 180             for( array* r=my_root; r; r=r->next ) {
 181                 size_t mask=r->mask();
 182                 for(size_t i = r->start(h); ;i=(i+1)&mask) {
 183                     slot& s = r->at(i);
 184                     if( s.empty() ) break;
 185                     if( s.match(k) ) {
 186                         if( r==my_root ) {
 187                             // Success at top level
 188                             exists = true;
 189                             return s.ptr;
 190                         } else {
 191                             // Success at some other level.  Need to insert at top level.
 192                             exists = true;
 193                             found = s.ptr;
 194                             goto insert;
 195                         }
 196                     }
 197                 }
 198             }
 199             // Key does not yet exist
 200             exists = false;
 201             found = create_local();
 202             {
 203                 size_t c = ++my_count;
 204                 array* r = my_root;
 205                 if( !r || c>r->size()/2 ) {
 206                     size_t s = r ? r->lg_size : 2;
 207                     while( c>size_t(1)<<(s-1) ) ++s;
 208                     array* a = allocate(s);
 209                     for(;;) {
 210                         a->next = my_root;
 211                         array* new_r = my_root.compare_and_swap(a,r);
 212                         if( new_r==r ) break;
 213                         if( new_r->lg_size>=s ) {
 214                             // Another thread inserted an equal or  bigger array, so our array is superfluous.
 215                             free(a);
 216                             break;
 217                         }
 218                         r = new_r;
 219                     }
 220                 }
 221             }
 222         insert:
 223             // Guaranteed to be room for it, and it is not present, so search for empty slot and grab it.
 224             array* ir = my_root;
 225             size_t mask = ir->mask();
 226             for(size_t i = ir->start(h);;i=(i+1)&mask) {
 227                 slot& s = ir->at(i);
 228                 if( s.empty() ) {
 229                     if( s.claim(k) ) {
 230                         s.ptr = found;
 231                         return found;
 232                     }
 233                 }
 234             }
 235         };
 236
 237         //! Specialization that exploits native TLS
 238         template <>
 239         class ets_base<ets_key_per_instance>: protected ets_base<ets_no_key> {
 240             typedef ets_base<ets_no_key> super;
 241 #if _WIN32||_WIN64
 242             typedef DWORD tls_key_t;
 243             void create_key() { my_key = TlsAlloc(); }
 244             void destroy_key() { TlsFree(my_key); }
 245             void set_tls(void * value) { TlsSetValue(my_key, (LPVOID)value); }
 246             void* get_tls() { return (void *)TlsGetValue(my_key); }
 247 #else
 248             typedef pthread_key_t tls_key_t;
 249             void create_key() { pthread_key_create(&my_key, NULL); }
 250             void destroy_key() { pthread_key_delete(my_key); }
 251             void set_tls( void * value ) const { pthread_setspecific(my_key, value); }
 252             void* get_tls() const { return pthread_getspecific(my_key); }
 253 #endif
 254             tls_key_t my_key;
 255             virtual void* create_local() = 0;
 256             virtual void* create_array(size_t _size) = 0;  // _size in bytes
 257             virtual void free_array(void* ptr, size_t _size) = 0; // size in bytes
 258         public:
 259             ets_base() {create_key();}
 260             ~ets_base() {destroy_key();}
 261             void* table_lookup( bool& exists ) {
 262                 void* found = get_tls();
 263                 if( found ) {
 264                     exists=true;
 265                 } else {
 266                     found = super::table_lookup(exists);
 267                     set_tls(found);
 268                 }
 269                 return found;
 270             }
 271             void table_clear() {
 272                 destroy_key();
 273                 create_key();
 274                 super::table_clear();
 275             }
 276         };
 277
 278         //! Random access iterator for traversing the thread local copies.
 279         template< typename Container, typename Value >
 280         class enumerable_thread_specific_iterator
 281 #if defined(_WIN64) && defined(_MSC_VER)
 282             // Ensure that Microsoft's internal template function _Val_type works correctly.
 283             : public std::iterator<std::random_access_iterator_tag,Value>
 284 #endif /* defined(_WIN64) && defined(_MSC_VER) */
 285         {
 286             //! current position in the concurrent_vector
 287
 288             Container *my_container;
 289             typename Container::size_type my_index;
 290             mutable Value *my_value;
 291
 292             template<typename C, typename T>
 293             friend enumerable_thread_specific_iterator<C,T> operator+( ptrdiff_t offset,
 294                                                                        const enumerable_thread_specific_iterator<C,T>& v );
 295
 296             template<typename C, typename T, typename U>
 297             friend bool operator==( const enumerable_thread_specific_iterator<C,T>& i,
 298                                     const enumerable_thread_specific_iterator<C,U>& j );
 299
 300             template<typename C, typename T, typename U>
 301             friend bool operator<( const enumerable_thread_specific_iterator<C,T>& i,
 302                                    const enumerable_thread_specific_iterator<C,U>& j );
 303
 304             template<typename C, typename T, typename U>
 305             friend ptrdiff_t operator-( const enumerable_thread_specific_iterator<C,T>& i, const enumerable_thread_specific_iterator<C,U>& j );
 306
 307             template<typename C, typename U>
 308             friend class enumerable_thread_specific_iterator;
 309
 310             public:
 311
 312             enumerable_thread_specific_iterator( const Container &container, typename Container::size_type index ) :
 313                 my_container(&const_cast<Container &>(container)), my_index(index), my_value(NULL) {}
 314
 315             //! Default constructor
 316             enumerable_thread_specific_iterator() : my_container(NULL), my_index(0), my_value(NULL) {}
 317
 318             template<typename U>
 319             enumerable_thread_specific_iterator( const enumerable_thread_specific_iterator<Container, U>& other ) :
 320                     my_container( other.my_container ), my_index( other.my_index), my_value( const_cast<Value *>(other.my_value) ) {}
 321
 322             enumerable_thread_specific_iterator operator+( ptrdiff_t offset ) const {
 323                 return enumerable_thread_specific_iterator(*my_container, my_index + offset);
 324             }
 325
 326             enumerable_thread_specific_iterator &operator+=( ptrdiff_t offset ) {
 327                 my_index += offset;
 328                 my_value = NULL;
 329                 return *this;
 330             }
 331
 332             enumerable_thread_specific_iterator operator-( ptrdiff_t offset ) const {
 333                 return enumerable_thread_specific_iterator( *my_container, my_index-offset );
 334             }
 335
 336             enumerable_thread_specific_iterator &operator-=( ptrdiff_t offset ) {
 337                 my_index -= offset;
 338                 my_value = NULL;
 339                 return *this;
 340             }
 341
 342             Value& operator*() const {
 343                 Value* value = my_value;
 344                 if( !value ) {
 345                     value = my_value = reinterpret_cast<Value *>(&(*my_container)[my_index].value);
 346                 }
 347                 __TBB_ASSERT( value==reinterpret_cast<Value *>(&(*my_container)[my_index].value), "corrupt cache" );
 348                 return *value;
 349             }
 350
 351             Value& operator[]( ptrdiff_t k ) const {
 352                return (*my_container)[my_index + k].value;
 353             }
 354
 355             Value* operator->() const {return &operator*();}
 356
 357             enumerable_thread_specific_iterator& operator++() {
 358                 ++my_index;
 359                 my_value = NULL;
 360                 return *this;
 361             }
 362
 363             enumerable_thread_specific_iterator& operator--() {
 364                 --my_index;
 365                 my_value = NULL;
 366                 return *this;
 367             }
 368
 369             //! Post increment
 370             enumerable_thread_specific_iterator operator++(int) {
 371                 enumerable_thread_specific_iterator result = *this;
 372                 ++my_index;
 373                 my_value = NULL;
 374                 return result;
 375             }
 376
 377             //! Post decrement
 378             enumerable_thread_specific_iterator operator--(int) {
 379                 enumerable_thread_specific_iterator result = *this;
 380                 --my_index;
 381                 my_value = NULL;
 382                 return result;
 383             }
 384
 385             // STL support
 386             typedef ptrdiff_t difference_type;
 387             typedef Value value_type;
 388             typedef Value* pointer;
 389             typedef Value& reference;
 390             typedef std::random_access_iterator_tag iterator_category;
 391         };
 392
 393         template<typename Container, typename T>
 394         enumerable_thread_specific_iterator<Container,T> operator+( ptrdiff_t offset,
 395                                                                     const enumerable_thread_specific_iterator<Container,T>& v ) {
 396             return enumerable_thread_specific_iterator<Container,T>( v.my_container, v.my_index + offset );
 397         }
 398
 399         template<typename Container, typename T, typename U>
 400         bool operator==( const enumerable_thread_specific_iterator<Container,T>& i,
 401                          const enumerable_thread_specific_iterator<Container,U>& j ) {
 402             return i.my_index==j.my_index && i.my_container == j.my_container;
 403         }
 404
 405         template<typename Container, typename T, typename U>
 406         bool operator!=( const enumerable_thread_specific_iterator<Container,T>& i,
 407                          const enumerable_thread_specific_iterator<Container,U>& j ) {
 408             return !(i==j);
 409         }
 410
 411         template<typename Container, typename T, typename U>
 412         bool operator<( const enumerable_thread_specific_iterator<Container,T>& i,
 413                         const enumerable_thread_specific_iterator<Container,U>& j ) {
 414             return i.my_index<j.my_index;
 415         }
 416
 417         template<typename Container, typename T, typename U>
 418         bool operator>( const enumerable_thread_specific_iterator<Container,T>& i,
 419                         const enumerable_thread_specific_iterator<Container,U>& j ) {
 420             return j<i;
 421         }
 422
 423         template<typename Container, typename T, typename U>
 424         bool operator>=( const enumerable_thread_specific_iterator<Container,T>& i,
 425                          const enumerable_thread_specific_iterator<Container,U>& j ) {
 426             return !(i<j);
 427         }
 428
 429         template<typename Container, typename T, typename U>
 430         bool operator<=( const enumerable_thread_specific_iterator<Container,T>& i,
 431                          const enumerable_thread_specific_iterator<Container,U>& j ) {
 432             return !(j<i);
 433         }
 434
 435         template<typename Container, typename T, typename U>
 436         ptrdiff_t operator-( const enumerable_thread_specific_iterator<Container,T>& i,
 437                              const enumerable_thread_specific_iterator<Container,U>& j ) {
 438             return i.my_index-j.my_index;
 439         }
 440
 441     template<typename SegmentedContainer, typename Value >
 442         class segmented_iterator
 443 #if defined(_WIN64) && defined(_MSC_VER)
 444         : public std::iterator<std::input_iterator_tag, Value>
 445 #endif
 446         {
 447             template<typename C, typename T, typename U>
 448             friend bool operator==(const segmented_iterator<C,T>& i, const segmented_iterator<C,U>& j);
 449
 450             template<typename C, typename T, typename U>
 451             friend bool operator!=(const segmented_iterator<C,T>& i, const segmented_iterator<C,U>& j);
 452
 453             template<typename C, typename U>
 454             friend class segmented_iterator;
 455
 456             public:
 457
 458                 segmented_iterator() {my_segcont = NULL;}
 459
 460                 segmented_iterator( const SegmentedContainer& _segmented_container ) :
 461                     my_segcont(const_cast<SegmentedContainer*>(&_segmented_container)),
 462                     outer_iter(my_segcont->end()) { }
 463
 464                 ~segmented_iterator() {}
 465
 466                 typedef typename SegmentedContainer::iterator outer_iterator;
 467                 typedef typename SegmentedContainer::value_type InnerContainer;
 468                 typedef typename InnerContainer::iterator inner_iterator;
 469
 470                 // STL support
 471                 typedef ptrdiff_t difference_type;
 472                 typedef Value value_type;
 473                 typedef typename SegmentedContainer::size_type size_type;
 474                 typedef Value* pointer;
 475                 typedef Value& reference;
 476                 typedef std::input_iterator_tag iterator_category;
 477
 478                 // Copy Constructor
 479                 template<typename U>
 480                 segmented_iterator(const segmented_iterator<SegmentedContainer, U>& other) :
 481                     my_segcont(other.my_segcont),
 482                     outer_iter(other.outer_iter),
 483                     // can we assign a default-constructed iterator to inner if we're at the end?
 484                     inner_iter(other.inner_iter)
 485                 {}
 486
 487                 // assignment
 488                 template<typename U>
 489                 segmented_iterator& operator=( const segmented_iterator<SegmentedContainer, U>& other) {
 490                     if(this != &other) {
 491                         my_segcont = other.my_segcont;
 492                         outer_iter = other.outer_iter;
 493                         if(outer_iter != my_segcont->end()) inner_iter = other.inner_iter;
 494                     }
 495                     return *this;
 496                 }
 497
 498                 // allow assignment of outer iterator to segmented iterator.  Once it is
 499                 // assigned, move forward until a non-empty inner container is found or
 500                 // the end of the outer container is reached.
 501                 segmented_iterator& operator=(const outer_iterator& new_outer_iter) {
 502                     __TBB_ASSERT(my_segcont != NULL, NULL);
 503                     // check that this iterator points to something inside the segmented container
 504                     for(outer_iter = new_outer_iter ;outer_iter!=my_segcont->end(); ++outer_iter) {
 505                         if( !outer_iter->empty() ) {
 506                             inner_iter = outer_iter->begin();
 507                             break;
 508                         }
 509                     }
 510                     return *this;
 511                 }
 512
 513                 // pre-increment
 514                 segmented_iterator& operator++() {
 515                     advance_me();
 516                     return *this;
 517                 }
 518
 519                 // post-increment
 520                 segmented_iterator operator++(int) {
 521                     segmented_iterator tmp = *this;
 522                     operator++();
 523                     return tmp;
 524                 }
 525
 526                 bool operator==(const outer_iterator& other_outer) const {
 527                     __TBB_ASSERT(my_segcont != NULL, NULL);
 528                     return (outer_iter == other_outer &&
 529                             (outer_iter == my_segcont->end() || inner_iter == outer_iter->begin()));
 530                 }
 531
 532                 bool operator!=(const outer_iterator& other_outer) const {
 533                     return !operator==(other_outer);
 534
 535                 }
 536
 537                 // (i)* RHS
 538                 reference operator*() const {
 539                     __TBB_ASSERT(my_segcont != NULL, NULL);
 540                     __TBB_ASSERT(outer_iter != my_segcont->end(), "Dereferencing a pointer at end of container");
 541                     __TBB_ASSERT(inner_iter != outer_iter->end(), NULL); // should never happen
 542                     return *inner_iter;
 543                 }
 544
 545                 // i->
 546                 pointer operator->() const { return &operator*();}
 547
 548             private:
 549                 SegmentedContainer*             my_segcont;
 550                 outer_iterator outer_iter;
 551                 inner_iterator inner_iter;
 552
 553                 void advance_me() {
 554                     __TBB_ASSERT(my_segcont != NULL, NULL);
 555                     __TBB_ASSERT(outer_iter != my_segcont->end(), NULL); // not true if there are no inner containers
 556                     __TBB_ASSERT(inner_iter != outer_iter->end(), NULL); // not true if the inner containers are all empty.
 557                     ++inner_iter;
 558                     while(inner_iter == outer_iter->end() && ++outer_iter != my_segcont->end()) {
 559                         inner_iter = outer_iter->begin();
 560                     }
 561                 }
 562         };    // segmented_iterator
 563
 564         template<typename SegmentedContainer, typename T, typename U>
 565         bool operator==( const segmented_iterator<SegmentedContainer,T>& i,
 566                          const segmented_iterator<SegmentedContainer,U>& j ) {
 567             if(i.my_segcont != j.my_segcont) return false;
 568             if(i.my_segcont == NULL) return true;
 569             if(i.outer_iter != j.outer_iter) return false;
 570             if(i.outer_iter == i.my_segcont->end()) return true;
 571             return i.inner_iter == j.inner_iter;
 572         }
 573
 574         // !=
 575         template<typename SegmentedContainer, typename T, typename U>
 576         bool operator!=( const segmented_iterator<SegmentedContainer,T>& i,
 577                          const segmented_iterator<SegmentedContainer,U>& j ) {
 578             return !(i==j);
 579         }
 580
 581         // storage for initialization function pointer
 582         template<typename T>
 583         struct callback_base {
 584             virtual T apply( ) = 0;
 585             virtual void destroy( ) = 0;
 586             // need to be able to create copies of callback_base for copy constructor
 587             virtual callback_base* make_copy() = 0;
 588             // need virtual destructor to satisfy GCC compiler warning
 589             virtual ~callback_base() { }
 590         };
 591
 592         template <typename T, typename Functor>
 593         struct callback_leaf : public callback_base<T>, public tbb::internal::no_copy {
 594             typedef Functor my_callback_type;
 595             typedef callback_leaf<T,Functor> my_type;
 596             typedef my_type* callback_pointer;
 597             typedef typename tbb::tbb_allocator<my_type> my_allocator_type;
 598             Functor f;
 599             callback_leaf( const Functor& f_) : f(f_) {
 600             }
 601
 602             static callback_pointer new_callback(const Functor& f_ ) {
 603                 void* new_void = my_allocator_type().allocate(1);
 604                 callback_pointer new_cb = new (new_void) callback_leaf<T,Functor>(f_); // placement new
 605                 return new_cb;
 606             }
 607
 608             /* override */ callback_pointer make_copy() {
 609                 return new_callback( f );
 610             }
 611
 612              /* override */ void destroy( ) {
 613                  callback_pointer my_ptr = this;
 614                  my_allocator_type().destroy(my_ptr);
 615                  my_allocator_type().deallocate(my_ptr,1);
 616              }
 617             /* override */ T apply() { return f(); }  // does copy construction of returned value.
 618         };
 619
 620
 621         //! Template for adding padding in order to avoid false sharing
 622         /** ModularSize should be sizeof(U) modulo the cache line size.
 623             All maintenance of the space will be done explicitly on push_back,
 624             and all thread local copies must be destroyed before the concurrent
 625             vector is deleted.
 626         */
 627         template<typename U, size_t ModularSize>
 628         struct ets_element {
 629             char value[sizeof(U) + tbb::internal::NFS_MaxLineSize-ModularSize];
 630             void unconstruct() {
 631                 // "reinterpret_cast<U*>(&value)->~U();" causes type-punning warning with gcc 4.4,
 632                 // "U* u = reinterpret_cast<U*>(&value); u->~U();" causes unused variable warning with VS2010.
 633                 // Thus another "casting via union" hack.
 634                 __TBB_ASSERT(sizeof(void*)==sizeof(U*),NULL);
 635                 union { void* space; U* val; } helper;
 636                 helper.space = &value;
 637                 helper.val->~U();
 638             }
 639         };
 640
 641         //! Partial specialization for case where no padding is needed.
 642         template<typename U>
 643         struct ets_element<U,0> {
 644             char value[sizeof(U)];
 645             void unconstruct() { // Same implementation as in general case
 646                 __TBB_ASSERT(sizeof(void*)==sizeof(U*),NULL);
 647                 union { void* space; U* val; } helper;
 648                 helper.space = &value;
 649                 helper.val->~U();
 650             }
 651         };
 652
 653     } // namespace internal
 654     //! @endcond
 655
 656     //! The enumerable_thread_specific container
 657     /** enumerable_thread_specific has the following properties:
 658         - thread-local copies are lazily created, with default, exemplar or function initialization.
 659         - thread-local copies do not move (during lifetime, and excepting clear()) so the address of a copy is invariant.
 660         - the contained objects need not have operator=() defined if combine is not used.
 661         - enumerable_thread_specific containers may be copy-constructed or assigned.
 662         - thread-local copies can be managed by hash-table, or can be accessed via TLS storage for speed.
 663         - outside of parallel contexts, the contents of all thread-local copies are accessible by iterator or using combine or combine_each methods
 664
 665     @par Segmented iterator
 666         When the thread-local objects are containers with input_iterators defined, a segmented iterator may
 667         be used to iterate over all the elements of all thread-local copies.
 668
 669     @par combine and combine_each
 670         - Both methods are defined for enumerable_thread_specific.
 671         - combine() requires the the type T have operator=() defined.
 672         - neither method modifies the contents of the object (though there is no guarantee that the applied methods do not modify the object.)
 673         - Both are evaluated in serial context (the methods are assumed to be non-benign.)
 674
 675     @ingroup containers */
 676     template <typename T,
 677               typename Allocator=cache_aligned_allocator<T>,
 678               ets_key_usage_type ETS_key_type=ets_no_key >
 679     class enumerable_thread_specific: internal::ets_base<ETS_key_type> {
 680
 681         template<typename U, typename A, ets_key_usage_type C> friend class enumerable_thread_specific;
 682
 683         typedef internal::ets_element<T,sizeof(T)%tbb::internal::NFS_MaxLineSize> padded_element;
 684
 685         //! A generic range, used to create range objects from the iterators
 686         template<typename I>
 687         class generic_range_type: public blocked_range<I> {
 688         public:
 689             typedef T value_type;
 690             typedef T& reference;
 691             typedef const T& const_reference;
 692             typedef I iterator;
 693             typedef ptrdiff_t difference_type;
 694             generic_range_type( I begin_, I end_, size_t grainsize_ = 1) : blocked_range<I>(begin_,end_,grainsize_) {}
 695             template<typename U>
 696             generic_range_type( const generic_range_type<U>& r) : blocked_range<I>(r.begin(),r.end(),r.grainsize()) {}
 697             generic_range_type( generic_range_type& r, split ) : blocked_range<I>(r,split()) {}
 698         };
 699
 700         typedef typename Allocator::template rebind< padded_element >::other padded_allocator_type;
 701         typedef tbb::concurrent_vector< padded_element, padded_allocator_type > internal_collection_type;
 702
 703         internal::callback_base<T> *my_finit_callback;
 704
 705         // need to use a pointed-to exemplar because T may not be assignable.
 706         // using tbb_allocator instead of padded_element_allocator because we may be
 707         // copying an exemplar from one instantiation of ETS to another with a different
 708         // allocator.
 709         typedef typename tbb::tbb_allocator<padded_element > exemplar_allocator_type;
 710         static padded_element * create_exemplar(const T& my_value) {
 711             padded_element *new_exemplar = reinterpret_cast<padded_element *>(exemplar_allocator_type().allocate(1));
 712             new(new_exemplar->value) T(my_value);
 713             return new_exemplar;
 714         }
 715
 716         static padded_element *create_exemplar( ) {
 717             padded_element *new_exemplar = reinterpret_cast<padded_element *>(exemplar_allocator_type().allocate(1));
 718             new(new_exemplar->value) T( );
 719             return new_exemplar;
 720         }
 721
 722         static void free_exemplar(padded_element *my_ptr) {
 723             my_ptr->unconstruct();
 724             exemplar_allocator_type().destroy(my_ptr);
 725             exemplar_allocator_type().deallocate(my_ptr,1);
 726         }
 727
 728         padded_element* my_exemplar_ptr;
 729
 730         internal_collection_type my_locals;
 731
 732         /*override*/ void* create_local() {
 733 #if TBB_DEPRECATED
 734             void* lref = &my_locals[my_locals.push_back(padded_element())];
 735 #else
 736             void* lref = &*my_locals.push_back(padded_element());
 737 #endif
 738             if(my_finit_callback) {
 739                 new(lref) T(my_finit_callback->apply());
 740             } else if(my_exemplar_ptr) {
 741                 pointer t_exemp = reinterpret_cast<T *>(&(my_exemplar_ptr->value));
 742                 new(lref) T(*t_exemp);
 743             } else {
 744                 new(lref) T();
 745             }
 746             return lref;
 747         }
 748
 749         void unconstruct_locals() {
 750             for(typename internal_collection_type::iterator cvi = my_locals.begin(); cvi != my_locals.end(); ++cvi) {
 751                 cvi->unconstruct();
 752             }
 753         }
 754
 755         typedef typename Allocator::template rebind< uintptr_t >::other array_allocator_type;
 756
 757         // _size is in bytes
 758         /*override*/ void* create_array(size_t _size) {
 759             size_t nelements = (_size + sizeof(uintptr_t) -1) / sizeof(uintptr_t);
 760             return array_allocator_type().allocate(nelements);
 761         }
 762
 763         /*override*/ void free_array( void* _ptr, size_t _size) {
 764             size_t nelements = (_size + sizeof(uintptr_t) -1) / sizeof(uintptr_t);
 765             array_allocator_type().deallocate( reinterpret_cast<uintptr_t *>(_ptr),nelements);
 766         }
 767
 768     public:
 769
 770         //! Basic types
 771         typedef Allocator allocator_type;
 772         typedef T value_type;
 773         typedef T& reference;
 774         typedef const T& const_reference;
 775         typedef T* pointer;
 776         typedef const T* const_pointer;
 777         typedef typename internal_collection_type::size_type size_type;
 778         typedef typename internal_collection_type::difference_type difference_type;
 779
 780         // Iterator types
 781         typedef typename internal::enumerable_thread_specific_iterator< internal_collection_type, value_type > iterator;
 782         typedef typename internal::enumerable_thread_specific_iterator< internal_collection_type, const value_type > const_iterator;
 783
 784         // Parallel range types
 785         typedef generic_range_type< iterator > range_type;
 786         typedef generic_range_type< const_iterator > const_range_type;
 787
 788         //! Default constructor, which leads to default construction of local copies
 789         enumerable_thread_specific() : my_finit_callback(0) {
 790             my_exemplar_ptr = 0;
 791         }
 792
 793         //! construction with initializer method
 794         // Finit should be a function taking 0 parameters and returning a T
 795         template <typename Finit>
 796         enumerable_thread_specific( Finit _finit )
 797         {
 798             my_finit_callback = internal::callback_leaf<T,Finit>::new_callback( _finit );
 799             my_exemplar_ptr = 0; // don't need exemplar if function is provided
 800         }
 801
 802         //! Constuction with exemplar, which leads to copy construction of local copies
 803         enumerable_thread_specific(const T &_exemplar) : my_finit_callback(0) {
 804             my_exemplar_ptr = create_exemplar(_exemplar);
 805         }
 806
 807         //! Destructor
 808         ~enumerable_thread_specific() {
 809             if(my_finit_callback) {
 810                 my_finit_callback->destroy();
 811             }
 812             if(my_exemplar_ptr) {
 813                 free_exemplar(my_exemplar_ptr);
 814             }
 815             this->clear();  // deallocation before the derived class is finished destructing
 816             // So free(array *) is still accessible
 817         }
 818
 819         //! returns reference to local, discarding exists
 820         reference local() {
 821             bool exists;
 822             return local(exists);
 823         }
 824
 825         //! Returns reference to calling thread's local copy, creating one if necessary
 826         reference local(bool& exists)  {
 827             __TBB_ASSERT(ETS_key_type==ets_no_key,"ets_key_per_instance not yet implemented");
 828             void* ptr = this->table_lookup(exists);
 829             return *(T*)ptr;
 830         }
 831
 832         //! Get the number of local copies
 833         size_type size() const { return my_locals.size(); }
 834
 835         //! true if there have been no local copies created
 836         bool empty() const { return my_locals.empty(); }
 837
 838         //! begin iterator
 839         iterator begin() { return iterator( my_locals, 0 ); }
 840         //! end iterator
 841         iterator end() { return iterator(my_locals, my_locals.size() ); }
 842
 843         //! begin const iterator
 844         const_iterator begin() const { return const_iterator(my_locals, 0); }
 845
 846         //! end const iterator
 847         const_iterator end() const { return const_iterator(my_locals, my_locals.size()); }
 848
 849         //! Get range for parallel algorithms
 850         range_type range( size_t grainsize=1 ) { return range_type( begin(), end(), grainsize ); }
 851
 852         //! Get const range for parallel algorithms
 853         const_range_type range( size_t grainsize=1 ) const { return const_range_type( begin(), end(), grainsize ); }
 854
 855         //! Destroys local copies
 856         void clear() {
 857             unconstruct_locals();
 858             my_locals.clear();
 859             this->table_clear();
 860             // callback is not destroyed
 861             // exemplar is not destroyed
 862         }
 863
 864     private:
 865
 866         template<typename U, typename A2, ets_key_usage_type C2>
 867         void internal_copy( const enumerable_thread_specific<U, A2, C2>& other);
 868
 869     public:
 870
 871         template<typename U, typename Alloc, ets_key_usage_type Cachetype>
 872         enumerable_thread_specific( const enumerable_thread_specific<U, Alloc, Cachetype>& other ) : internal::ets_base<ETS_key_type> ()
 873         {
 874             internal_copy(other);
 875         }
 876
 877         enumerable_thread_specific( const enumerable_thread_specific& other ) : internal::ets_base<ETS_key_type> ()
 878         {
 879             internal_copy(other);
 880         }
 881
 882     private:
 883
 884         template<typename U, typename A2, ets_key_usage_type C2>
 885         enumerable_thread_specific &
 886         internal_assign(const enumerable_thread_specific<U, A2, C2>& other) {
 887             if(static_cast<void *>( this ) != static_cast<const void *>( &other )) {
 888                 this->clear();
 889                 if(my_finit_callback) {
 890                     my_finit_callback->destroy();
 891                     my_finit_callback = 0;
 892                 }
 893                 if(my_exemplar_ptr) {
 894                     free_exemplar(my_exemplar_ptr);
 895                     my_exemplar_ptr = 0;
 896                 }
 897                 internal_copy( other );
 898             }
 899             return *this;
 900         }
 901
 902     public:
 903
 904         // assignment
 905         enumerable_thread_specific& operator=(const enumerable_thread_specific& other) {
 906             return internal_assign(other);
 907         }
 908
 909         template<typename U, typename Alloc, ets_key_usage_type Cachetype>
 910         enumerable_thread_specific& operator=(const enumerable_thread_specific<U, Alloc, Cachetype>& other)
 911         {
 912             return internal_assign(other);
 913         }
 914
 915         // combine_func_t has signature T(T,T) or T(const T&, const T&)
 916         template <typename combine_func_t>
 917         T combine(combine_func_t f_combine) {
 918             if(begin() == end()) {
 919                 if(my_finit_callback) {
 920                     return my_finit_callback->apply();
 921                 }
 922                 pointer local_ref = reinterpret_cast<T*>((my_exemplar_ptr->value));
 923                 return T(*local_ref);
 924             }
 925             const_iterator ci = begin();
 926             T my_result = *ci;
 927             while(++ci != end())
 928                 my_result = f_combine( my_result, *ci );
 929             return my_result;
 930         }
 931
 932         // combine_func_t has signature void(T) or void(const T&)
 933         template <typename combine_func_t>
 934         void combine_each(combine_func_t f_combine) {
 935             for(const_iterator ci = begin(); ci != end(); ++ci) {
 936                 f_combine( *ci );
 937             }
 938         }
 939
 940     }; // enumerable_thread_specific
 941
 942
 943     template <typename T, typename Allocator, ets_key_usage_type ETS_key_type>
 944     template<typename U, typename A2, ets_key_usage_type C2>
 945     void enumerable_thread_specific<T,Allocator,ETS_key_type>::internal_copy( const enumerable_thread_specific<U, A2, C2>& other) {
 946         typedef internal::ets_base<ets_no_key> base;
 947         __TBB_ASSERT(my_locals.size()==0,NULL);
 948         this->table_reserve_for_copy( other );
 949         for( base::array* r=other.my_root; r; r=r->next ) {
 950             for( size_t i=0; i<r->size(); ++i ) {
 951                 base::slot& s1 = r->at(i);
 952                 if( !s1.empty() ) {
 953                     base::slot& s2 = this->table_find(s1.key);
 954                     if( s2.empty() ) {
 955 #if TBB_DEPRECATED
 956                         void* lref = &my_locals[my_locals.push_back(padded_element())];
 957 #else
 958                         void* lref = &*my_locals.push_back(padded_element());
 959 #endif
 960                         s2.ptr = new(lref) T(*(U*)s1.ptr);
 961                         s2.key = s1.key;
 962                     } else {
 963                         // Skip the duplicate
 964                     }
 965                 }
 966             }
 967         }
 968         if(other.my_finit_callback) {
 969             my_finit_callback = other.my_finit_callback->make_copy();
 970         } else {
 971             my_finit_callback = 0;
 972         }
 973         if(other.my_exemplar_ptr) {
 974             pointer local_ref = reinterpret_cast<U*>(other.my_exemplar_ptr->value);
 975             my_exemplar_ptr = create_exemplar(*local_ref);
 976         } else {
 977             my_exemplar_ptr = 0;
 978         }
 979     }
 980
 981     template< typename Container >
 982     class flattened2d {
 983
 984         // This intermediate typedef is to address issues with VC7.1 compilers
 985         typedef typename Container::value_type conval_type;
 986
 987     public:
 988
 989         //! Basic types
 990         typedef typename conval_type::size_type size_type;
 991         typedef typename conval_type::difference_type difference_type;
 992         typedef typename conval_type::allocator_type allocator_type;
 993         typedef typename conval_type::value_type value_type;
 994         typedef typename conval_type::reference reference;
 995         typedef typename conval_type::const_reference const_reference;
 996         typedef typename conval_type::pointer pointer;
 997         typedef typename conval_type::const_pointer const_pointer;
 998
 999         typedef typename internal::segmented_iterator<Container, value_type> iterator;
1000         typedef typename internal::segmented_iterator<Container, const value_type> const_iterator;
1001
1002         flattened2d( const Container &c, typename Container::const_iterator b, typename Container::const_iterator e ) :
1003             my_container(const_cast<Container*>(&c)), my_begin(b), my_end(e) { }
1004
1005         flattened2d( const Container &c ) :
1006             my_container(const_cast<Container*>(&c)), my_begin(c.begin()), my_end(c.end()) { }
1007
1008         iterator begin() { return iterator(*my_container) = my_begin; }
1009         iterator end() { return iterator(*my_container) = my_end; }
1010         const_iterator begin() const { return const_iterator(*my_container) = my_begin; }
1011         const_iterator end() const { return const_iterator(*my_container) = my_end; }
1012
1013         size_type size() const {
1014             size_type tot_size = 0;
1015             for(typename Container::const_iterator i = my_begin; i != my_end; ++i) {
1016                 tot_size += i->size();
1017             }
1018             return tot_size;
1019         }
1020
1021     private:
1022
1023         Container *my_container;
1024         typename Container::const_iterator my_begin;
1025         typename Container::const_iterator my_end;
1026
1027     };
1028
1029     template <typename Container>
1030     flattened2d<Container> flatten2d(const Container &c, const typename Container::const_iterator b, const typename Container::const_iterator e) {
1031         return flattened2d<Container>(c, b, e);
1032     }
1033
1034     template <typename Container>
1035     flattened2d<Container> flatten2d(const Container &c) {
1036         return flattened2d<Container>(c);
1037     }
1038
1039 } // interface5
1040
1041 namespace internal {
1042 using interface5::internal::segmented_iterator;
1043 }
1044
1045 using interface5::enumerable_thread_specific;
1046 using interface5::flattened2d;
1047 using interface5::flatten2d;
1048
1049 } // namespace tbb
1050
1051 #endif