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

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