17 #ifndef __TBB_enumerable_thread_specific_H
18 #define __TBB_enumerable_thread_specific_H
20 #define __TBB_enumerable_thread_specific_H_include_area
34 #if __TBB_PREVIEW_RESUMABLE_TASKS
44 #define __TBB_ETS_USE_CPP11 \
45 (__TBB_CPP11_RVALUE_REF_PRESENT && __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT \
46 && __TBB_CPP11_DECLTYPE_PRESENT && __TBB_CPP11_LAMBDAS_PRESENT)
54 #if __TBB_PREVIEW_RESUMABLE_TASKS
59 namespace interface6 {
62 template <
typename T,
typename Allocator, ets_key_usage_type ETS_key_type>
70 template <ets_key_usage_type ETS_key_type>
71 struct ets_key_selector {
73 static key_type current_key() {
78 #if __TBB_PREVIEW_RESUMABLE_TASKS
80 struct ets_key_selector<ets_suspend_aware> {
81 typedef task::suspend_point key_type;
82 static key_type current_key() {
83 return internal_current_suspend_point();
87 inline task::suspend_point atomic_compare_and_swap(task::suspend_point& location,
88 const task::suspend_point&
value,
const task::suspend_point& comparand) {
93 template<ets_key_usage_type ETS_key_type>
96 typedef typename ets_key_selector<ETS_key_type>::key_type key_type;
97 #if __TBB_PROTECTED_NESTED_CLASS_BROKEN
105 slot& at(
size_t k ) {
106 return ((slot*)(
void*)(
this+1))[k];
108 size_t size()
const {
return size_t(1)<<lg_size;}
109 size_t mask()
const {
return size()-1;}
110 size_t start(
size_t h )
const {
111 return h>>(8*
sizeof(size_t)-lg_size);
117 bool empty()
const {
return key == key_type();}
118 bool match( key_type k )
const {
return key == k;}
119 bool claim( key_type k ) {
121 return atomic_compare_and_swap(
key, k, key_type()) == key_type();
124 #if __TBB_PROTECTED_NESTED_CLASS_BROKEN
131 atomic<array*> my_root;
132 atomic<size_t> my_count;
133 virtual void* create_local() = 0;
134 virtual void* create_array(
size_t _size) = 0;
135 virtual void free_array(
void* ptr,
size_t _size) = 0;
136 array* allocate(
size_t lg_size ) {
137 size_t n = size_t(1)<<lg_size;
138 array* a =
static_cast<array*
>(create_array(
sizeof(array)+n*
sizeof(slot) ));
139 a->lg_size = lg_size;
140 std::memset( a+1, 0, n*
sizeof(slot) );
143 void free(array* a) {
144 size_t n = size_t(1)<<(a->lg_size);
145 free_array( (
void *)a,
size_t(
sizeof(array)+n*
sizeof(slot)) );
148 ets_base() {my_root=NULL; my_count=0;}
150 void* table_lookup(
bool& exists );
154 template <ets_key_usage_type E2>
155 void table_elementwise_copy(
const ets_base& other,
156 void*(*add_element)(ets_base<E2>&,
void*) ) {
159 if( !other.my_root )
return;
160 array* root = my_root = allocate(other.my_root->lg_size);
162 my_count = other.my_count;
163 size_t mask = root->mask();
164 for( array* r=other.my_root; r; r=r->next ) {
165 for(
size_t i=0; i<r->size(); ++i ) {
168 for(
size_t j = root->start(tbb::tbb_hash<key_type>()(s1.key)); ; j=(j+1)&
mask ) {
169 slot& s2 = root->at(j);
171 s2.ptr = add_element(
static_cast<ets_base<E2>&
>(*
this), s1.ptr);
175 else if( s2.match(s1.key) )
182 void table_swap( ets_base& other ) {
183 __TBB_ASSERT(
this!=&other,
"Don't swap an instance with itself");
184 tbb::internal::swap<relaxed>(my_root, other.my_root);
185 tbb::internal::swap<relaxed>(my_count, other.my_count);
189 template<ets_key_usage_type ETS_key_type>
190 ets_base<ETS_key_type>::~ets_base() {
194 template<ets_key_usage_type ETS_key_type>
195 void ets_base<ETS_key_type>::table_clear() {
196 while( array* r = my_root ) {
203 template<ets_key_usage_type ETS_key_type>
204 void* ets_base<ETS_key_type>::table_lookup(
bool& exists ) {
205 const key_type k = ets_key_selector<ETS_key_type>::current_key();
209 size_t h = tbb::tbb_hash<key_type>()(k);
210 for( array* r=my_root; r; r=r->next ) {
212 size_t mask=r->mask();
213 for(
size_t i = r->start(
h); ;i=(i+1)&
mask) {
215 if(
s.empty() )
break;
234 found = create_local();
236 size_t c = ++my_count;
239 if( !r || c>r->size()/2 ) {
240 size_t s = r ? r->lg_size : 2;
241 while( c>
size_t(1)<<(
s-1) ) ++
s;
242 array* a = allocate(
s);
246 array* new_r = my_root.compare_and_swap(a,r);
247 if( new_r==r )
break;
249 if( new_r->lg_size>=
s ) {
264 size_t mask = ir->mask();
265 for(
size_t i = ir->start(
h);;i=(i+1)&
mask) {
279 typedef ets_base<ets_no_key> super;
281 #if __TBB_WIN8UI_SUPPORT
282 typedef DWORD tls_key_t;
283 void create_key() { my_key = FlsAlloc(NULL); }
284 void destroy_key() { FlsFree(my_key); }
285 void set_tls(
void *
value) { FlsSetValue(my_key, (LPVOID)
value); }
286 void* get_tls() {
return (
void *)FlsGetValue(my_key); }
288 typedef DWORD tls_key_t;
289 void create_key() { my_key = TlsAlloc(); }
290 void destroy_key() { TlsFree(my_key); }
291 void set_tls(
void *
value) { TlsSetValue(my_key, (LPVOID)
value); }
292 void* get_tls() {
return (
void *)TlsGetValue(my_key); }
295 typedef pthread_key_t tls_key_t;
296 void create_key() { pthread_key_create(&my_key, NULL); }
297 void destroy_key() { pthread_key_delete(my_key); }
298 void set_tls(
void *
value )
const { pthread_setspecific(my_key,
value); }
299 void* get_tls()
const {
return pthread_getspecific(my_key); }
304 virtual
void free_array(
void* ptr,
size_t _size)
__TBB_override = 0;
306 ets_base() {create_key();}
307 ~ets_base() {destroy_key();}
308 void* table_lookup(
bool& exists ) {
309 void* found = get_tls();
313 found = super::table_lookup(exists);
321 super::table_clear();
323 void table_swap( ets_base& other ) {
325 __TBB_ASSERT(
this!=&other,
"Don't swap an instance with itself");
326 swap(my_key, other.my_key);
327 super::table_swap(other);
332 template<
typename Container,
typename Value >
333 class enumerable_thread_specific_iterator
334 #if defined(_WIN64) && defined(_MSC_VER)
336 : public std::iterator<std::random_access_iterator_tag,Value>
341 Container *my_container;
342 typename Container::size_type my_index;
343 mutable Value *my_value;
345 template<
typename C,
typename T>
346 friend enumerable_thread_specific_iterator<C,T>
347 operator+( ptrdiff_t offset,
const enumerable_thread_specific_iterator<C,T>& v );
349 template<
typename C,
typename T,
typename U>
350 friend bool operator==(
const enumerable_thread_specific_iterator<C,T>& i,
351 const enumerable_thread_specific_iterator<C,U>& j );
353 template<
typename C,
typename T,
typename U>
354 friend bool operator<(
const enumerable_thread_specific_iterator<C,T>& i,
355 const enumerable_thread_specific_iterator<C,U>& j );
357 template<
typename C,
typename T,
typename U>
358 friend ptrdiff_t
operator-(
const enumerable_thread_specific_iterator<C,T>& i,
359 const enumerable_thread_specific_iterator<C,U>& j );
361 template<
typename C,
typename U>
362 friend class enumerable_thread_specific_iterator;
366 enumerable_thread_specific_iterator(
const Container &container,
typename Container::size_type index ) :
367 my_container(&const_cast<Container &>(container)), my_index(index), my_value(NULL) {}
370 enumerable_thread_specific_iterator() : my_container(NULL), my_index(0), my_value(NULL) {}
373 enumerable_thread_specific_iterator(
const enumerable_thread_specific_iterator<Container, U>& other ) :
374 my_container( other.my_container ), my_index( other.my_index), my_value( const_cast<Value *>(other.my_value) ) {}
376 enumerable_thread_specific_iterator
operator+( ptrdiff_t offset )
const {
377 return enumerable_thread_specific_iterator(*my_container, my_index + offset);
380 enumerable_thread_specific_iterator &operator+=( ptrdiff_t offset ) {
386 enumerable_thread_specific_iterator
operator-( ptrdiff_t offset )
const {
387 return enumerable_thread_specific_iterator( *my_container, my_index-offset );
390 enumerable_thread_specific_iterator &operator-=( ptrdiff_t offset ) {
396 Value& operator*()
const {
397 Value*
value = my_value;
399 value = my_value = (*my_container)[my_index].value();
405 Value& operator[]( ptrdiff_t k )
const {
406 return (*my_container)[my_index + k].value;
409 Value* operator->()
const {
return &operator*();}
411 enumerable_thread_specific_iterator& operator++() {
417 enumerable_thread_specific_iterator& operator--() {
424 enumerable_thread_specific_iterator operator++(
int) {
425 enumerable_thread_specific_iterator result = *
this;
432 enumerable_thread_specific_iterator operator--(
int) {
433 enumerable_thread_specific_iterator result = *
this;
440 typedef ptrdiff_t difference_type;
441 typedef Value value_type;
442 typedef Value* pointer;
443 typedef Value& reference;
444 typedef std::random_access_iterator_tag iterator_category;
447 template<
typename Container,
typename T>
448 enumerable_thread_specific_iterator<Container,T>
449 operator+( ptrdiff_t offset,
const enumerable_thread_specific_iterator<Container,T>& v ) {
450 return enumerable_thread_specific_iterator<Container,T>( v.my_container, v.my_index + offset );
453 template<
typename Container,
typename T,
typename U>
454 bool operator==(
const enumerable_thread_specific_iterator<Container,T>& i,
455 const enumerable_thread_specific_iterator<Container,U>& j ) {
456 return i.my_index==j.my_index && i.my_container == j.my_container;
459 template<
typename Container,
typename T,
typename U>
460 bool operator!=(
const enumerable_thread_specific_iterator<Container,T>& i,
461 const enumerable_thread_specific_iterator<Container,U>& j ) {
465 template<
typename Container,
typename T,
typename U>
466 bool operator<(
const enumerable_thread_specific_iterator<Container,T>& i,
467 const enumerable_thread_specific_iterator<Container,U>& j ) {
468 return i.my_index<j.my_index;
471 template<
typename Container,
typename T,
typename U>
472 bool operator>(
const enumerable_thread_specific_iterator<Container,T>& i,
473 const enumerable_thread_specific_iterator<Container,U>& j ) {
477 template<
typename Container,
typename T,
typename U>
478 bool operator>=(
const enumerable_thread_specific_iterator<Container,T>& i,
479 const enumerable_thread_specific_iterator<Container,U>& j ) {
483 template<
typename Container,
typename T,
typename U>
484 bool operator<=(
const enumerable_thread_specific_iterator<Container,T>& i,
485 const enumerable_thread_specific_iterator<Container,U>& j ) {
489 template<
typename Container,
typename T,
typename U>
490 ptrdiff_t
operator-(
const enumerable_thread_specific_iterator<Container,T>& i,
491 const enumerable_thread_specific_iterator<Container,U>& j ) {
492 return i.my_index-j.my_index;
495 template<
typename SegmentedContainer,
typename Value >
496 class segmented_iterator
497 #if defined(_WIN64) && defined(_MSC_VER)
498 : public std::iterator<std::input_iterator_tag, Value>
501 template<
typename C,
typename T,
typename U>
502 friend bool operator==(
const segmented_iterator<C,T>& i,
const segmented_iterator<C,U>& j);
504 template<
typename C,
typename T,
typename U>
505 friend bool operator!=(
const segmented_iterator<C,T>& i,
const segmented_iterator<C,U>& j);
507 template<
typename C,
typename U>
508 friend class segmented_iterator;
512 segmented_iterator() {my_segcont = NULL;}
514 segmented_iterator(
const SegmentedContainer& _segmented_container ) :
515 my_segcont(const_cast<SegmentedContainer*>(&_segmented_container)),
516 outer_iter(my_segcont->
end()) { }
518 ~segmented_iterator() {}
520 typedef typename SegmentedContainer::iterator outer_iterator;
521 typedef typename SegmentedContainer::value_type InnerContainer;
522 typedef typename InnerContainer::iterator inner_iterator;
525 typedef ptrdiff_t difference_type;
526 typedef Value value_type;
527 typedef typename SegmentedContainer::size_type size_type;
528 typedef Value* pointer;
529 typedef Value& reference;
530 typedef std::input_iterator_tag iterator_category;
534 segmented_iterator(
const segmented_iterator<SegmentedContainer, U>& other) :
535 my_segcont(other.my_segcont),
536 outer_iter(other.outer_iter),
538 inner_iter(other.inner_iter)
543 segmented_iterator& operator=(
const segmented_iterator<SegmentedContainer, U>& other) {
545 my_segcont = other.my_segcont;
546 outer_iter = other.outer_iter;
547 if(outer_iter != my_segcont->end()) inner_iter = other.inner_iter;
555 segmented_iterator& operator=(
const outer_iterator& new_outer_iter) {
558 for(outer_iter = new_outer_iter ;outer_iter!=my_segcont->end(); ++outer_iter) {
559 if( !outer_iter->empty() ) {
560 inner_iter = outer_iter->begin();
568 segmented_iterator& operator++() {
574 segmented_iterator operator++(
int) {
575 segmented_iterator tmp = *
this;
580 bool operator==(
const outer_iterator& other_outer)
const {
582 return (outer_iter == other_outer &&
583 (outer_iter == my_segcont->end() || inner_iter == outer_iter->begin()));
586 bool operator!=(
const outer_iterator& other_outer)
const {
592 reference operator*()
const {
594 __TBB_ASSERT(outer_iter != my_segcont->end(),
"Dereferencing a pointer at end of container");
600 pointer operator->()
const {
return &operator*();}
603 SegmentedContainer* my_segcont;
604 outer_iterator outer_iter;
605 inner_iterator inner_iter;
612 while(inner_iter == outer_iter->end() && ++outer_iter != my_segcont->end()) {
613 inner_iter = outer_iter->begin();
618 template<
typename SegmentedContainer,
typename T,
typename U>
619 bool operator==(
const segmented_iterator<SegmentedContainer,T>& i,
620 const segmented_iterator<SegmentedContainer,U>& j ) {
621 if(i.my_segcont != j.my_segcont)
return false;
622 if(i.my_segcont == NULL)
return true;
623 if(i.outer_iter != j.outer_iter)
return false;
624 if(i.outer_iter == i.my_segcont->end())
return true;
625 return i.inner_iter == j.inner_iter;
629 template<
typename SegmentedContainer,
typename T,
typename U>
630 bool operator!=(
const segmented_iterator<SegmentedContainer,T>& i,
631 const segmented_iterator<SegmentedContainer,U>& j ) {
637 void construct(
void*where) {
new(where) T();}
638 construct_by_default(
int ) {}
644 void construct(
void*where) {
new(where) T(exemplar);}
645 construct_by_exemplar(
const T& t ) : exemplar(t) {}
646 #if __TBB_ETS_USE_CPP11
647 construct_by_exemplar( T&& t ) : exemplar(std::
move(t)) {}
651 template<
typename T,
typename Finit>
654 void construct(
void* where) {
new(where) T(f());}
655 construct_by_finit(
const Finit& f_ ) : f(f_) {}
656 #if __TBB_ETS_USE_CPP11
657 construct_by_finit( Finit&& f_ ) : f(std::
move(f_)) {}
661 #if __TBB_ETS_USE_CPP11
662 template<
typename T,
typename... P>
664 internal::stored_pack<P...> pack;
665 void construct(
void* where) {
667 new(where) T(args...);
670 construct_by_args( P&& ... args ) : pack(std::forward<P>(args)...) {}
677 class callback_base {
680 virtual callback_base* clone()
const = 0;
682 virtual void destroy() = 0;
684 virtual ~callback_base() { }
686 virtual void construct(
void* where) = 0;
689 template <
typename T,
typename Constructor>
690 class callback_leaf:
public callback_base<T>, Constructor {
691 #if __TBB_ETS_USE_CPP11
692 template<
typename... P> callback_leaf( P&& ... params ) : Constructor(std::forward<P>(params)...) {}
694 template<
typename X> callback_leaf(
const X& x ) : Constructor(x) {}
704 my_allocator_type().destroy(
this);
705 my_allocator_type().deallocate(
this,1);
709 Constructor::construct(where);
712 #if __TBB_ETS_USE_CPP11
713 template<
typename... P>
714 static callback_base<T>* make( P&& ... params ) {
715 void* where = my_allocator_type().allocate(1);
716 return new(where) callback_leaf( std::forward<P>(params)... );
720 static callback_base<T>* make(
const X& x ) {
721 void* where = my_allocator_type().allocate(1);
722 return new(where) callback_leaf(x);
738 tbb::aligned_space<U> my_space;
740 ets_element() { is_built =
false; }
741 U*
value() {
return my_space.begin(); }
742 U* value_committed() { is_built =
true;
return my_space.begin(); }
745 my_space.begin()->~U();
754 template<
typename T,
typename ETS>
struct is_compatible_ets {
static const bool value =
false; };
755 template<
typename T,
typename U,
typename A, ets_key_usage_type C>
758 #if __TBB_ETS_USE_CPP11
760 template <
typename T>
761 class is_callable_no_args {
766 template<
typename U>
static yes& decide( decltype(declval<U>()())* );
767 template<
typename U>
static no& decide(...);
769 static const bool value = (
sizeof(decide<T>(NULL)) ==
sizeof(yes));
796 template <
typename T,
797 typename Allocator=cache_aligned_allocator<T>,
799 class enumerable_thread_specific: internal::ets_base<ETS_key_type> {
831 my_construct_callback->construct(lref.value());
832 return lref.value_committed();
838 new(lref.value()) T(*
static_cast<T*
>(
p));
839 return lref.value_committed();
842 #if __TBB_ETS_USE_CPP11
843 static void* create_local_by_move( internal::ets_base<ETS_key_type>& base,
void*
p ) {
845 padded_element& lref = *ets.my_locals.grow_by(1);
846 new(lref.value()) T(
std::move(*
static_cast<T*
>(
p)));
847 return lref.value_committed();
855 size_t nelements = (_size +
sizeof(uintptr_t) -1) /
sizeof(uintptr_t);
860 size_t nelements = (_size +
sizeof(uintptr_t) -1) /
sizeof(uintptr_t);
877 typedef typename internal::enumerable_thread_specific_iterator< internal_collection_type, value_type >
iterator;
878 typedef typename internal::enumerable_thread_specific_iterator< internal_collection_type, const value_type >
const_iterator;
890 template <
typename Finit
891 #if __TBB_ETS_USE_CPP11
901 internal::callback_leaf<T,
internal::construct_by_exemplar<T> >::make( exemplar )
904 #if __TBB_ETS_USE_CPP11
910 template <
typename P1,
typename... P,
916 internal::callback_leaf<T,
internal::construct_by_args<T,P1,P...> >::make( std::forward<P1>(arg1), std::forward<P>(args)... )
922 if(my_construct_callback) my_construct_callback->destroy();
924 this->internal::ets_base<ETS_key_type>::table_clear();
930 return local(exists);
935 void* ptr = this->table_lookup(exists);
971 template<
typename A2, ets_key_usage_type C2>
973 #if __TBB_ETS_USE_CPP11 && TBB_USE_ASSERT
978 my_construct_callback = other.my_construct_callback->clone();
980 my_locals.
reserve(other.size());
981 this->table_elementwise_copy( other, create_local_by_copy );
987 swap(my_construct_callback, other.my_construct_callback);
990 swap(my_locals, other.my_locals);
991 this->internal::ets_base<ETS_key_type>::table_swap(other);
994 #if __TBB_ETS_USE_CPP11
995 template<
typename A2, ets_key_usage_type C2>
1001 my_construct_callback = other.my_construct_callback;
1002 other.my_construct_callback = NULL;
1004 my_locals.
reserve(other.size());
1005 this->table_elementwise_copy( other, create_local_by_move );
1012 :
internal::ets_base<ETS_key_type>()
1014 internal_copy(other);
1017 template<
typename Alloc, ets_key_usage_type Cachetype>
1020 internal_copy(other);
1023 #if __TBB_ETS_USE_CPP11
1026 internal_swap(other);
1029 template<
typename Alloc, ets_key_usage_type Cachetype>
1038 if(
this != &other ) {
1040 my_construct_callback->destroy();
1041 internal_copy( other );
1046 template<
typename Alloc, ets_key_usage_type Cachetype>
1049 __TBB_ASSERT(
static_cast<void*
>(
this)!=
static_cast<const void*
>(&other), NULL );
1051 my_construct_callback->destroy();
1052 internal_copy(other);
1056 #if __TBB_ETS_USE_CPP11
1059 if(
this != &other )
1060 internal_swap(other);
1064 template<
typename Alloc, ets_key_usage_type Cachetype>
1067 __TBB_ASSERT(
static_cast<void*
>(
this)!=
static_cast<const void*
>(&other), NULL );
1069 my_construct_callback->destroy();
1076 template <
typename combine_func_t>
1079 internal::ets_element<T> location;
1080 my_construct_callback->construct(location.value());
1081 return *location.value_committed();
1085 while(++ci !=
end())
1086 my_result = f_combine( my_result, *ci );
1091 template <
typename combine_func_t>
1100 template<
typename Container >
1118 typedef typename internal::segmented_iterator<Container, value_type>
iterator;
1119 typedef typename internal::segmented_iterator<Container, const value_type>
const_iterator;
1121 flattened2d(
const Container &c,
typename Container::const_iterator b,
typename Container::const_iterator e ) :
1122 my_container(const_cast<Container*>(&c)), my_begin(b), my_end(e) { }
1125 my_container(const_cast<Container*>(&c)), my_begin(c.
begin()), my_end(c.
end()) { }
1134 for(
typename Container::const_iterator i = my_begin; i != my_end; ++i) {
1135 tot_size += i->size();
1148 template <
typename Container>
1153 template <
typename Container>
1161 using interface6::internal::segmented_iterator;
1164 using interface6::enumerable_thread_specific;
1165 using interface6::flattened2d;
1171 #undef __TBB_enumerable_thread_specific_H_include_area