concurrent_vector.cpp
Go to the documentation of this file.
/*
Copyright (c) 2005-2020 Intel Corporation
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
#if (_MSC_VER)
//MSVC 10 "deprecated" application of some std:: algorithms to raw pointers as not safe.
//The reason is that destination is not checked against bounds/having enough place.
#define _SCL_SECURE_NO_WARNINGS
#endif
#include "tbb/concurrent_vector.h"
#include "tbb/cache_aligned_allocator.h"
#include "tbb/tbb_exception.h"
#include "tbb_misc.h"
#include "itt_notify.h"
#include <cstring>
#include <memory> //for uninitialized_fill_n
#if defined(_MSC_VER) && defined(_Wp64)
// Workaround for overzealous compiler warnings in /Wp64 mode
#pragma warning (disable: 4267)
#endif
namespace tbb {
namespace internal {
class concurrent_vector_base_v3::helper :no_assign {
public:
static const size_type page_size = 4096;
inline static bool incompact_predicate(size_type size) { // assert size != 0, see source/test/test_vector_layout.cpp
return size < page_size || ((size-1)%page_size < page_size/2 && size < page_size * 128); // for more details
}
inline static size_type find_segment_end(const concurrent_vector_base_v3 &v) {
segment_t *s = v.my_segment;
segment_index_t u = s==v.my_storage? pointers_per_short_table : pointers_per_long_table;
segment_index_t k = 0;
while( k < u && (s[k].load<relaxed>()==segment_allocated() ))
++k;
return k;
}
// TODO: optimize accesses to my_first_block
inline static void assign_first_segment_if_necessary(concurrent_vector_base_v3 &v, segment_index_t k) {
if( !v.my_first_block ) {
/* There was a suggestion to set first segment according to incompact_predicate:
while( k && !helper::incompact_predicate(segment_size( k ) * element_size) )
--k; // while previous vector size is compact, decrement
// reasons to not do it:
// * constructor(n) is not ready to accept fragmented segments
// * backward compatibility due to that constructor
// * current version gives additional guarantee and faster init.
// * two calls to reserve() will give the same effect.
*/
v.my_first_block.compare_and_swap(k+1, 0); // store number of segments
}
}
inline static void *allocate_segment(concurrent_vector_base_v3 &v, size_type n) {
void *ptr = v.vector_allocator_ptr(v, n);
if(!ptr) throw_exception(eid_bad_alloc); // check for bad allocation, throw exception
return ptr;
}
template<typename argument_type>
inline static void publish_segment( segment_t& s, argument_type rhs ) {
// see also itt_store_pointer_with_release_v3()
ITT_NOTIFY( sync_releasing, &s );
s.store<release>(rhs);
}
static size_type enable_segment(concurrent_vector_base_v3 &v, size_type k, size_type element_size, bool mark_as_not_used_on_failure = false);
// TODO: rename as get_segments_table() and return segment pointer
inline static void extend_table_if_necessary(concurrent_vector_base_v3 &v, size_type k, size_type start ) {
if(k >= pointers_per_short_table && v.my_segment == v.my_storage)
extend_segment_table(v, start );
}
static void extend_segment_table(concurrent_vector_base_v3 &v, size_type start);
struct segment_not_used_predicate: no_assign {
segment_t &s;
segment_not_used_predicate(segment_t &segment) : s(segment) {}
bool operator()() const { return s.load<relaxed>() == segment_not_used ();}
};
inline static segment_t& acquire_segment(concurrent_vector_base_v3 &v, size_type index, size_type element_size, bool owner) {
segment_t &s = v.my_segment[index]; // TODO: pass v.my_segment as argument
if( s.load<acquire>() == segment_not_used() ) { // do not check for segment_allocation_failed state
if( owner ) {
enable_segment( v, index, element_size );
} else {
ITT_NOTIFY(sync_prepare, &s);
spin_wait_while(segment_not_used_predicate(s));
ITT_NOTIFY(sync_acquired, &s);
}
} else {
ITT_NOTIFY(sync_acquired, &s);
}
enforce_segment_allocated(s.load<relaxed>()); //it's hard to recover correctly after segment_allocation_failed state
return s;
}
segment_t *table;// TODO: review all segment_index_t as just short type
size_type first_block, k, sz, start, finish, element_size;
helper(segment_t *segments, size_type fb, size_type esize, size_type index, size_type s, size_type f) throw()
: table(segments), first_block(fb), k(index), sz(0), start(s), finish(f), element_size(esize) {}
inline void first_segment() throw() {
__TBB_ASSERT( start <= finish, NULL );
__TBB_ASSERT( first_block || !finish, NULL );
if( k < first_block ) k = 0; // process solid segment at a time
size_type base = segment_base( k );
__TBB_ASSERT( base <= start, NULL );
finish -= base; start -= base; // rebase as offsets from segment k
sz = k ? base : segment_size( first_block ); // sz==base for k>0
}
inline void next_segment() throw() {
finish -= sz; start = 0; // offsets from next segment
if( !k ) k = first_block;
else { ++k; sz = segment_size( k ); }
}
template<typename F>
inline size_type apply(const F &func) {
first_segment();
while( sz < finish ) { // work for more than one segment
//TODO: remove extra load() of table[k] inside func
func( table[k], table[k].load<relaxed>().pointer<char>() + element_size*start, sz - start );
next_segment();
}
func( table[k], table[k].load<relaxed>().pointer<char>() + element_size*start, finish - start );
return k;
}
inline segment_value_t get_segment_value(size_type index, bool wait) {
segment_t &s = table[index];
if( wait && (s.load<acquire>() == segment_not_used()) ) {
ITT_NOTIFY(sync_prepare, &s);
spin_wait_while(segment_not_used_predicate(s));
ITT_NOTIFY(sync_acquired, &s);
}
return s.load<relaxed>();
}
~helper() {
if( sz >= finish ) return; // the work is done correctly
cleanup();
}
void cleanup();
struct init_body {
internal_array_op2 func;
const void *arg;
init_body(internal_array_op2 init, const void *src) : func(init), arg(src) {}
void operator()(segment_t &, void *begin, size_type n) const {
func( begin, arg, n );
}
};
struct safe_init_body {
internal_array_op2 func;
const void *arg;
safe_init_body(internal_array_op2 init, const void *src) : func(init), arg(src) {}
void operator()(segment_t &s, void *begin, size_type n) const {
enforce_segment_allocated(s.load<relaxed>());
func( begin, arg, n );
}
};
struct destroy_body {
internal_array_op1 func;
destroy_body(internal_array_op1 destroy) : func(destroy) {}
void operator()(segment_t &s, void *begin, size_type n) const {
if(s.load<relaxed>() == segment_allocated())
func( begin, n );
}
};
}; // class helper
void concurrent_vector_base_v3::helper::extend_segment_table(concurrent_vector_base_v3 &v, concurrent_vector_base_v3::size_type start) {
if( start > segment_size(pointers_per_short_table) ) start = segment_size(pointers_per_short_table);
// If other threads are trying to set pointers in the short segment, wait for them to finish their
// assignments before we copy the short segment to the long segment. Note: grow_to_at_least depends on it
for( segment_index_t i = 0; segment_base(i) < start && v.my_segment == v.my_storage; i++ ){
if(v.my_storage[i].load<relaxed>() == segment_not_used()) {
ITT_NOTIFY(sync_prepare, &v.my_storage[i]);
atomic_backoff backoff(true);
while( v.my_segment == v.my_storage && (v.my_storage[i].load<relaxed>() == segment_not_used()) )
backoff.pause();
ITT_NOTIFY(sync_acquired, &v.my_storage[i]);
}
}
if( v.my_segment != v.my_storage ) return;
segment_t* new_segment_table = (segment_t*)NFS_Allocate( pointers_per_long_table, sizeof(segment_t), NULL );
__TBB_ASSERT(new_segment_table, "NFS_Allocate should throws exception if it cannot allocate the requested storage, and not returns zero pointer" );
std::uninitialized_fill_n(new_segment_table,size_t(pointers_per_long_table),segment_t()); //init newly allocated table
//TODO: replace with static assert
__TBB_STATIC_ASSERT(pointers_per_long_table >= pointers_per_short_table, "size of the big table should be not lesser than of the small one, as we copy values to it" );
std::copy(v.my_storage, v.my_storage+pointers_per_short_table, new_segment_table);//copy values from old table, here operator= of segment_t is used
if( v.my_segment.compare_and_swap( new_segment_table, v.my_storage ) != v.my_storage )
NFS_Free( new_segment_table );
// else TODO: add ITT_NOTIFY signals for v.my_segment?
}
concurrent_vector_base_v3::size_type concurrent_vector_base_v3::helper::enable_segment(concurrent_vector_base_v3 &v, concurrent_vector_base_v3::size_type k, concurrent_vector_base_v3::size_type element_size,
bool mark_as_not_used_on_failure ) {
struct segment_scope_guard : no_copy{
segment_t* my_segment_ptr;
bool my_mark_as_not_used;
segment_scope_guard(segment_t& segment, bool mark_as_not_used) : my_segment_ptr(&segment), my_mark_as_not_used(mark_as_not_used){}
void dismiss(){ my_segment_ptr = 0;}
~segment_scope_guard(){
if (my_segment_ptr){
if (!my_mark_as_not_used){
publish_segment(*my_segment_ptr, segment_allocation_failed());
}else{
publish_segment(*my_segment_ptr, segment_not_used());
}
}
}
};
segment_t* s = v.my_segment; // TODO: optimize out as argument? Optimize accesses to my_first_block
__TBB_ASSERT(s[k].load<relaxed>() != segment_allocated(), "concurrent operation during growth?");
size_type size_of_enabled_segment = segment_size(k);
size_type size_to_allocate = size_of_enabled_segment;
if( !k ) {
assign_first_segment_if_necessary(v, default_initial_segments-1);
size_of_enabled_segment = 2 ;
size_to_allocate = segment_size(v.my_first_block);
} else {
spin_wait_while_eq( v.my_first_block, segment_index_t(0) );
}
if( k && (k < v.my_first_block)){ //no need to allocate anything
// s[0].array is changed only once ( 0 -> !0 ) and points to uninitialized memory
segment_value_t array0 = s[0].load<acquire>();
if(array0 == segment_not_used()){
// sync_prepare called only if there is a wait
ITT_NOTIFY(sync_prepare, &s[0]);
spin_wait_while( segment_not_used_predicate(s[0]));
array0 = s[0].load<acquire>();
}
ITT_NOTIFY(sync_acquired, &s[0]);
segment_scope_guard k_segment_guard(s[k], false);
enforce_segment_allocated(array0); // initial segment should be allocated
k_segment_guard.dismiss();
publish_segment( s[k],
static_cast<void*>(array0.pointer<char>() + segment_base(k)*element_size )
);
} else {
segment_scope_guard k_segment_guard(s[k], mark_as_not_used_on_failure);
publish_segment(s[k], allocate_segment(v, size_to_allocate));
k_segment_guard.dismiss();
}
return size_of_enabled_segment;
}
void concurrent_vector_base_v3::helper::cleanup() {
if( !sz ) { // allocation failed, restore the table
segment_index_t k_start = k, k_end = segment_index_of(finish-1);
if( segment_base( k_start ) < start )
get_segment_value(k_start++, true); // wait
if( k_start < first_block ) {
segment_value_t segment0 = get_segment_value(0, start>0); // wait if necessary
if((segment0 != segment_not_used()) && !k_start ) ++k_start;
if(segment0 != segment_allocated())
for(; k_start < first_block && k_start <= k_end; ++k_start )
publish_segment(table[k_start], segment_allocation_failed());
else for(; k_start < first_block && k_start <= k_end; ++k_start )
publish_segment(table[k_start], static_cast<void*>(
(segment0.pointer<char>()) + segment_base(k_start)*element_size) );
}
for(; k_start <= k_end; ++k_start ) // not in first block
if(table[k_start].load<acquire>() == segment_not_used())
publish_segment(table[k_start], segment_allocation_failed());
// fill allocated items
first_segment();
goto recover;
}
while( sz <= finish ) { // there is still work for at least one segment
next_segment();
recover:
segment_value_t array = table[k].load<relaxed>();
if(array == segment_allocated())
std::memset( (array.pointer<char>()) + element_size*start, 0, ((sz<finish?sz:finish) - start)*element_size );
else __TBB_ASSERT( array == segment_allocation_failed(), NULL );
}
}
concurrent_vector_base_v3::~concurrent_vector_base_v3() {
segment_t* s = my_segment;
if( s != my_storage ) {
#if TBB_USE_ASSERT
//to please assert in segment_t destructor
std::fill_n(my_storage,size_t(pointers_per_short_table),segment_t());
#endif /* TBB_USE_ASSERT */
#if TBB_USE_DEBUG
for( segment_index_t i = 0; i < pointers_per_long_table; i++)
__TBB_ASSERT( my_segment[i].load<relaxed>() != segment_allocated(), "Segment should have been freed. Please recompile with new TBB before using exceptions.");
#endif
my_segment = my_storage;
NFS_Free( s );
}
}
concurrent_vector_base_v3::size_type concurrent_vector_base_v3::internal_capacity() const {
return segment_base( helper::find_segment_end(*this) );
}
void concurrent_vector_base_v3::internal_throw_exception(size_type t) const {
exception_id ids[] = { eid_out_of_range, eid_segment_range_error, eid_index_range_error };
__TBB_ASSERT(t < sizeof(ids) / sizeof(exception_id), NULL);
throw_exception(ids[t]);
}
void concurrent_vector_base_v3::internal_reserve( size_type n, size_type element_size, size_type max_size ) {
if( n>max_size )
throw_exception(eid_reservation_length_error);
__TBB_ASSERT( n, NULL );
helper::assign_first_segment_if_necessary(*this, segment_index_of(n-1));
segment_index_t k = helper::find_segment_end(*this);
for( ; segment_base(k)<n; ++k ) {
helper::extend_table_if_necessary(*this, k, 0);
if(my_segment[k].load<relaxed>() != segment_allocated())
helper::enable_segment(*this, k, element_size, true ); //in case of failure mark segments as not used
}
}
//TODO: Looks like atomic loads can be done relaxed here, as the only place this method is called from
//is the constructor, which does not require synchronization (for more details see comment in the
// concurrent_vector_base constructor).
void concurrent_vector_base_v3::internal_copy( const concurrent_vector_base_v3& src, size_type element_size, internal_array_op2 copy ) {
size_type n = src.my_early_size;
__TBB_ASSERT( my_segment == my_storage, NULL);
if( n ) {
helper::assign_first_segment_if_necessary(*this, segment_index_of(n-1));
size_type b;
for( segment_index_t k=0; (b=segment_base(k))<n; ++k ) {
if( (src.my_segment.load<acquire>() == src.my_storage && k >= pointers_per_short_table)
|| (src.my_segment[k].load<relaxed>() != segment_allocated())) {
my_early_size = b; break;
}
helper::extend_table_if_necessary(*this, k, 0);
size_type m = helper::enable_segment(*this, k, element_size);
if( m > n-b ) m = n-b;
my_early_size = b+m;
copy( my_segment[k].load<relaxed>().pointer<void>(), src.my_segment[k].load<relaxed>().pointer<void>(), m );
}
}
}
void concurrent_vector_base_v3::internal_assign( const concurrent_vector_base_v3& src, size_type element_size, internal_array_op1 destroy, internal_array_op2 assign, internal_array_op2 copy ) {
size_type n = src.my_early_size;
while( my_early_size>n ) { // TODO: improve
segment_index_t k = segment_index_of( my_early_size-1 );
size_type b=segment_base(k);
size_type new_end = b>=n ? b : n;
__TBB_ASSERT( my_early_size>new_end, NULL );
enforce_segment_allocated(my_segment[k].load<relaxed>()); //if vector was broken before
// destructors are supposed to not throw any exceptions
destroy( my_segment[k].load<relaxed>().pointer<char>() + element_size*(new_end-b), my_early_size-new_end );
my_early_size = new_end;
}
size_type dst_initialized_size = my_early_size;
my_early_size = n;
helper::assign_first_segment_if_necessary(*this, segment_index_of(n));
size_type b;
for( segment_index_t k=0; (b=segment_base(k))<n; ++k ) {
if( (src.my_segment.load<acquire>() == src.my_storage && k >= pointers_per_short_table)
|| src.my_segment[k].load<relaxed>() != segment_allocated() ) { // if source is damaged
my_early_size = b; break; // TODO: it may cause undestructed items
}
helper::extend_table_if_necessary(*this, k, 0);
if( my_segment[k].load<relaxed>() == segment_not_used())
helper::enable_segment(*this, k, element_size);
else
enforce_segment_allocated(my_segment[k].load<relaxed>());
size_type m = k? segment_size(k) : 2;
if( m > n-b ) m = n-b;
size_type a = 0;
if( dst_initialized_size>b ) {
a = dst_initialized_size-b;
if( a>m ) a = m;
assign( my_segment[k].load<relaxed>().pointer<void>(), src.my_segment[k].load<relaxed>().pointer<void>(), a );
m -= a;
a *= element_size;
}
if( m>0 )
copy( my_segment[k].load<relaxed>().pointer<char>() + a, src.my_segment[k].load<relaxed>().pointer<char>() + a, m );
}
__TBB_ASSERT( src.my_early_size==n, "detected use of concurrent_vector::operator= with right side that was concurrently modified" );
}
void* concurrent_vector_base_v3::internal_push_back( size_type element_size, size_type& index ) {
__TBB_ASSERT( sizeof(my_early_size)==sizeof(uintptr_t), NULL );
size_type tmp = my_early_size.fetch_and_increment<acquire>();
index = tmp;
segment_index_t k_old = segment_index_of( tmp );
size_type base = segment_base(k_old);
helper::extend_table_if_necessary(*this, k_old, tmp);
segment_t& s = helper::acquire_segment(*this, k_old, element_size, base==tmp);
size_type j_begin = tmp-base;
return (void*)(s.load<relaxed>().pointer<char>() + element_size*j_begin);
}
void concurrent_vector_base_v3::internal_grow_to_at_least( size_type new_size, size_type element_size, internal_array_op2 init, const void *src ) {
internal_grow_to_at_least_with_result( new_size, element_size, init, src );
}
concurrent_vector_base_v3::size_type concurrent_vector_base_v3::internal_grow_to_at_least_with_result( size_type new_size, size_type element_size, internal_array_op2 init, const void *src ) {
size_type e = my_early_size;
while( e<new_size ) {
size_type f = my_early_size.compare_and_swap(new_size,e);
if( f==e ) {
internal_grow( e, new_size, element_size, init, src );
break;
}
e = f;
}
// Check/wait for segments allocation completes
segment_index_t i, k_old = segment_index_of( new_size-1 );
if( k_old >= pointers_per_short_table && my_segment == my_storage ) {
spin_wait_while_eq( my_segment, my_storage );
}
for( i = 0; i <= k_old; ++i ) {
segment_t &s = my_segment[i];
if(s.load<relaxed>() == segment_not_used()) {
ITT_NOTIFY(sync_prepare, &s);
atomic_backoff backoff(true);
while( my_segment[i].load<acquire>() == segment_not_used() ) // my_segment may change concurrently
backoff.pause();
ITT_NOTIFY(sync_acquired, &s);
}
enforce_segment_allocated(my_segment[i].load<relaxed>());
}
#if TBB_USE_DEBUG
size_type capacity = internal_capacity();
__TBB_ASSERT( capacity >= new_size, NULL);
#endif
return e;
}
concurrent_vector_base_v3::size_type concurrent_vector_base_v3::internal_grow_by( size_type delta, size_type element_size, internal_array_op2 init, const void *src ) {
size_type result = my_early_size.fetch_and_add(delta);
internal_grow( result, result+delta, element_size, init, src );
return result;
}
void concurrent_vector_base_v3::internal_grow( const size_type start, size_type finish, size_type element_size, internal_array_op2 init, const void *src ) {
__TBB_ASSERT( start<finish, "start must be less than finish" );
segment_index_t k_start = segment_index_of(start), k_end = segment_index_of(finish-1);
helper::assign_first_segment_if_necessary(*this, k_end);
helper::extend_table_if_necessary(*this, k_end, start);
helper range(my_segment, my_first_block, element_size, k_start, start, finish);
for(; k_end > k_start && k_end >= range.first_block; --k_end ) // allocate segments in reverse order
helper::acquire_segment(*this, k_end, element_size, true/*for k_end>k_start*/);
for(; k_start <= k_end; ++k_start ) // but allocate first block in straight order
helper::acquire_segment(*this, k_start, element_size, segment_base( k_start ) >= start );
range.apply( helper::init_body(init, src) );
}
void concurrent_vector_base_v3::internal_resize( size_type n, size_type element_size, size_type max_size, const void *src,
internal_array_op1 destroy, internal_array_op2 init ) {
size_type j = my_early_size;
if( n > j ) { // construct items
internal_reserve(n, element_size, max_size);
my_early_size = n;
helper for_each(my_segment, my_first_block, element_size, segment_index_of(j), j, n);
for_each.apply( helper::safe_init_body(init, src) );
} else {
my_early_size = n;
helper for_each(my_segment, my_first_block, element_size, segment_index_of(n), n, j);
for_each.apply( helper::destroy_body(destroy) );
}
}
concurrent_vector_base_v3::segment_index_t concurrent_vector_base_v3::internal_clear( internal_array_op1 destroy ) {
__TBB_ASSERT( my_segment, NULL );
size_type j = my_early_size;
my_early_size = 0;
helper for_each(my_segment, my_first_block, 0, 0, 0, j); // element_size is safe to be zero if 'start' is zero
j = for_each.apply( helper::destroy_body(destroy) );
size_type i = helper::find_segment_end(*this);
return j < i? i : j+1;
}
void *concurrent_vector_base_v3::internal_compact( size_type element_size, void *table, internal_array_op1 destroy, internal_array_op2 copy )
{
const size_type my_size = my_early_size;
const segment_index_t k_end = helper::find_segment_end(*this); // allocated segments
const segment_index_t k_stop = my_size? segment_index_of(my_size-1) + 1 : 0; // number of segments to store existing items: 0=>0; 1,2=>1; 3,4=>2; [5-8]=>3;..
const segment_index_t first_block = my_first_block; // number of merged segments, getting values from atomics
segment_index_t k = first_block;
if(k_stop < first_block)
k = k_stop;
else
while (k < k_stop && helper::incompact_predicate(segment_size( k ) * element_size) ) k++;
if(k_stop == k_end && k == first_block)
return NULL;
segment_t *const segment_table = my_segment;
internal_segments_table &old = *static_cast<internal_segments_table*>( table );
//this call is left here for sake of backward compatibility, and as a placeholder for table initialization
std::fill_n(old.table,sizeof(old.table)/sizeof(old.table[0]),segment_t());
old.first_block=0;
if ( k != first_block && k ) // first segment optimization
{
// exception can occur here
void *seg = helper::allocate_segment(*this, segment_size(k));
old.table[0].store<relaxed>(seg);
old.first_block = k; // fill info for freeing new segment if exception occurs
// copy items to the new segment
size_type my_segment_size = segment_size( first_block );
for (segment_index_t i = 0, j = 0; i < k && j < my_size; j = my_segment_size) {
__TBB_ASSERT( segment_table[i].load<relaxed>() == segment_allocated(), NULL);
void *s = static_cast<void*>(
static_cast<char*>(seg) + segment_base(i)*element_size );
//TODO: refactor to use std::min
if(j + my_segment_size >= my_size) my_segment_size = my_size - j;
__TBB_TRY { // exception can occur here
copy( s, segment_table[i].load<relaxed>().pointer<void>(), my_segment_size );
} __TBB_CATCH(...) { // destroy all the already copied items
helper for_each(&old.table[0], old.first_block, element_size,
0, 0, segment_base(i)+ my_segment_size);
for_each.apply( helper::destroy_body(destroy) );
__TBB_RETHROW();
}
my_segment_size = i? segment_size( ++i ) : segment_size( i = first_block );
}
// commit the changes
std::copy(segment_table,segment_table + k,old.table);
for (segment_index_t i = 0; i < k; i++) {
segment_table[i].store<relaxed>(static_cast<void*>(
static_cast<char*>(seg) + segment_base(i)*element_size ));
}
old.first_block = first_block; my_first_block = k; // now, first_block != my_first_block
// destroy original copies
my_segment_size = segment_size( first_block ); // old.first_block actually
for (segment_index_t i = 0, j = 0; i < k && j < my_size; j = my_segment_size) {
if(j + my_segment_size >= my_size) my_segment_size = my_size - j;
// destructors are supposed to not throw any exceptions
destroy( old.table[i].load<relaxed>().pointer<void>(), my_segment_size );
my_segment_size = i? segment_size( ++i ) : segment_size( i = first_block );
}
}
// free unnecessary segments allocated by reserve() call
if ( k_stop < k_end ) {
old.first_block = first_block;
std::copy(segment_table+k_stop, segment_table+k_end, old.table+k_stop );
std::fill_n(segment_table+k_stop, (k_end-k_stop), segment_t());
if( !k ) my_first_block = 0;
}
return table;
}
void concurrent_vector_base_v3::internal_swap(concurrent_vector_base_v3& v)
{
size_type my_sz = my_early_size.load<acquire>();
size_type v_sz = v.my_early_size.load<relaxed>();
if(!my_sz && !v_sz) return;
bool my_was_short = (my_segment.load<relaxed>() == my_storage);
bool v_was_short = (v.my_segment.load<relaxed>() == v.my_storage);
//In C++11, this would be: swap(my_storage, v.my_storage);
for (int i=0; i < pointers_per_short_table; ++i){
swap(my_storage[i], v.my_storage[i]);
}
tbb::internal::swap<relaxed>(my_first_block, v.my_first_block);
tbb::internal::swap<relaxed>(my_segment, v.my_segment);
if (my_was_short){
v.my_segment.store<relaxed>(v.my_storage);
}
if(v_was_short){
my_segment.store<relaxed>(my_storage);
}
my_early_size.store<relaxed>(v_sz);
v.my_early_size.store<release>(my_sz);
}
} // namespace internal
} // tbb
tbb::internal::concurrent_vector_base_v3::helper::extend_table_if_necessary
static void extend_table_if_necessary(concurrent_vector_base_v3 &v, size_type k, size_type start)
Definition: concurrent_vector.cpp:92
tbb::acquire
Acquire.
Definition: atomic.h:57
tbb::internal::concurrent_vector_base_v3::helper::next_segment
void next_segment()
Definition: concurrent_vector.cpp:135
internal
Definition: _flow_graph_async_msg_impl.h:24
tbb::relaxed
No ordering.
Definition: atomic.h:61
tbb::internal::concurrent_vector_base_v3::helper::segment_not_used_predicate::segment_not_used_predicate
segment_not_used_predicate(segment_t &segment)
Definition: concurrent_vector.cpp:101
tbb::internal::spin_wait_while
void spin_wait_while(predicate_type condition)
Definition: tbb_machine.h:408
tbb::internal::eid_index_range_error
Definition: tbb_exception.h:73
tbb::internal::concurrent_vector_base_v3::helper::start
size_type start
Definition: concurrent_vector.cpp:123
tbb::internal::concurrent_vector_base_v3::helper::init_body::init_body
init_body(internal_array_op2 init, const void *src)
Definition: concurrent_vector.cpp:172
tbb::internal::concurrent_vector_base_v3::segment_base
static segment_index_t segment_base(segment_index_t k)
Definition: concurrent_vector.h:218
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
tbb::internal::concurrent_vector_base_v3::internal_grow
void internal_grow(size_type start, size_type finish, size_type element_size, internal_array_op2 init, const void *src)
Definition: concurrent_vector.cpp:473
tbb::internal::no_copy
Base class for types that should not be copied or assigned.
Definition: tbb_stddef.h:330
tbb::internal::concurrent_vector_base_v3::helper::destroy_body::destroy_body
destroy_body(internal_array_op1 destroy)
Definition: concurrent_vector.cpp:188
tbb::internal::concurrent_vector_base_v3::helper::finish
size_type finish
Definition: concurrent_vector.cpp:123
ITT_NOTIFY
#define ITT_NOTIFY(name, obj)
Definition: itt_notify.h:112
tbb::internal::concurrent_vector_base_v3::internal_segments_table::table
segment_t table[pointers_per_long_table]
Definition: concurrent_vector.h:251
tbb::internal::concurrent_vector_base_v3::helper::safe_init_body
Definition: concurrent_vector.cpp:177
tbb::internal::atomic_backoff
Class that implements exponential backoff.
Definition: tbb_machine.h:348
tbb::internal::throw_exception
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
Definition: tbb_exception.h:105
tbb::internal::concurrent_vector_base_v3::internal_array_op1
void(__TBB_EXPORTED_FUNC * internal_array_op1)(void *begin, size_type n)
An operation on an n-element array starting at begin.
Definition: concurrent_vector.h:243
tbb::internal::concurrent_vector_base_v3::helper
Definition: concurrent_vector.cpp:40
tbb::internal::eid_segment_range_error
Definition: tbb_exception.h:72
tbb::internal::concurrent_vector_base_v3::internal_assign
void __TBB_EXPORTED_METHOD internal_assign(const concurrent_vector_base_v3 &src, size_type element_size, internal_array_op1 destroy, internal_array_op2 assign, internal_array_op2 copy)
Definition: concurrent_vector.cpp:376
tbb::internal::concurrent_vector_base_v3::helper::helper
helper(segment_t *segments, size_type fb, size_type esize, size_type index, size_type s, size_type f)
Definition: concurrent_vector.cpp:124
tbb::internal::concurrent_vector_base_v3::segment_t::load
segment_value_t load() const
Definition: concurrent_vector.h:147
tbb::internal::concurrent_vector_base_v3::segment_allocation_failed
Definition: concurrent_vector.h:101
tbb::internal::concurrent_vector_base_v3::swap
friend void swap(segment_t &, segment_t &) __TBB_NOEXCEPT(true)
Definition: concurrent_vector.h:284
cache_aligned_allocator.h
tbb::internal::concurrent_vector_base_v3
Base class of concurrent vector implementation.
Definition: concurrent_vector.h:83
tbb::internal::concurrent_vector_base_v3::helper::init_body::func
internal_array_op2 func
Definition: concurrent_vector.cpp:170
tbb::internal::concurrent_vector_base_v3::my_segment
atomic< segment_t * > my_segment
Pointer to the segments table.
Definition: concurrent_vector.h:187
tbb
The graph class.
Definition: serial/tbb/parallel_for.h:46
tbb::internal::concurrent_vector_base_v3::helper::destroy_body::func
internal_array_op1 func
Definition: concurrent_vector.cpp:187
tbb::internal::concurrent_vector_base_v3::helper::get_segment_value
segment_value_t get_segment_value(size_type index, bool wait)
Definition: concurrent_vector.cpp:151
tbb::internal::concurrent_vector_base_v3::helper::segment_not_used_predicate::s
segment_t & s
Definition: concurrent_vector.cpp:100
tbb::internal::concurrent_vector_base_v3::helper::destroy_body::operator()
void operator()(segment_t &s, void *begin, size_type n) const
Definition: concurrent_vector.cpp:189
tbb::internal::concurrent_vector_base_v3::helper::extend_segment_table
static void extend_segment_table(concurrent_vector_base_v3 &v, size_type start)
Definition: concurrent_vector.cpp:196
begin
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp begin
Definition: ittnotify_static.h:182
tbb::internal::concurrent_vector_base_v3::helper::k
size_type k
Definition: concurrent_vector.cpp:123
tbb::internal::concurrent_vector_base_v3::helper::sz
size_type sz
Definition: concurrent_vector.cpp:123
tbb::internal::concurrent_vector_base_v3::internal_segments_table
Internal structure for compact()
Definition: concurrent_vector.h:249
tbb::internal::concurrent_vector_base_v3::helper::enable_segment
static size_type enable_segment(concurrent_vector_base_v3 &v, size_type k, size_type element_size, bool mark_as_not_used_on_failure=false)
Definition: concurrent_vector.cpp:222
tbb::internal::spin_wait_while_eq
void spin_wait_while_eq(const volatile T &location, U value)
Spin WHILE the value of the variable is equal to a given value.
Definition: tbb_machine.h:394
tbb::internal::concurrent_vector_base_v3::size_type
size_t size_type
Definition: concurrent_vector.h:88
tbb::internal::eid_out_of_range
Definition: tbb_exception.h:71
tbb::internal::concurrent_vector_base_v3::internal_grow_to_at_least_with_result
size_type __TBB_EXPORTED_METHOD internal_grow_to_at_least_with_result(size_type new_size, size_type element_size, internal_array_op2 init, const void *src)
Definition: concurrent_vector.cpp:434
size
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t size
Definition: ittnotify_static.h:109
tbb::internal::concurrent_vector_base_v3::helper::assign_first_segment_if_necessary
static void assign_first_segment_if_necessary(concurrent_vector_base_v3 &v, segment_index_t k)
assign first segment size. k - is index of last segment to be allocated, not a count of segments
Definition: concurrent_vector.cpp:60
tbb::internal::concurrent_vector_base_v3::internal_segments_table::first_block
segment_index_t first_block
Definition: concurrent_vector.h:250
tbb::internal::concurrent_vector_base_v3::pointers_per_short_table
Number of slots for segment pointers inside the class.
Definition: concurrent_vector.h:95
tbb::internal::concurrent_vector_base_v3::segment_index_of
static segment_index_t segment_index_of(size_type index)
Definition: concurrent_vector.h:214
tbb::internal::concurrent_vector_base_v3::internal_resize
void __TBB_EXPORTED_METHOD internal_resize(size_type n, size_type element_size, size_type max_size, const void *src, internal_array_op1 destroy, internal_array_op2 init)
Definition: concurrent_vector.cpp:486
tbb::internal::concurrent_vector_base_v3::helper::safe_init_body::safe_init_body
safe_init_body(internal_array_op2 init, const void *src)
Definition: concurrent_vector.cpp:180
itt_notify.h
tbb::internal::atomic_backoff::pause
void pause()
Pause for a while.
Definition: tbb_machine.h:363
tbb::internal::exception_id
exception_id
Definition: tbb_exception.h:67
tbb::internal::concurrent_vector_base_v3::segment_value_t::pointer
T * pointer() const
Definition: concurrent_vector.h:118
tbb::internal::concurrent_vector_base_v3::helper::init_body::operator()
void operator()(segment_t &, void *begin, size_type n) const
Definition: concurrent_vector.cpp:173
new_size
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t new_size
Definition: ittnotify_static.h:163
tbb::internal::concurrent_vector_base_v3::segment_t::store
void store(segment_not_used)
Definition: concurrent_vector.h:150
tbb::internal::concurrent_vector_base_v3::segment_size
static size_type segment_size(segment_index_t k)
Definition: concurrent_vector.h:228
tbb::internal::concurrent_vector_base_v3::helper::init_body
TODO: turn into lambda functions when available.
Definition: concurrent_vector.cpp:169
tbb::internal::concurrent_vector_base_v3::helper::allocate_segment
static void * allocate_segment(concurrent_vector_base_v3 &v, size_type n)
Definition: concurrent_vector.cpp:75
tbb::internal::concurrent_vector_base_v3::helper::segment_not_used_predicate::operator()
bool operator()() const
Definition: concurrent_vector.cpp:102
tbb::internal::concurrent_vector_base_v3::segment_allocated
Definition: concurrent_vector.h:100
tbb::internal::concurrent_vector_base_v3::internal_grow_to_at_least
void __TBB_EXPORTED_METHOD internal_grow_to_at_least(size_type new_size, size_type element_size, internal_array_op2 init, const void *src)
Deprecated entry point for backwards compatibility to TBB 2.1.
Definition: concurrent_vector.cpp:430
tbb::internal::concurrent_vector_base_v3::helper::first_block
size_type first_block
Definition: concurrent_vector.cpp:123
__TBB_STATIC_ASSERT
#define __TBB_STATIC_ASSERT(condition, msg)
Definition: tbb_stddef.h:553
tbb::internal::concurrent_vector_base_v3::default_initial_segments
Definition: concurrent_vector.h:93
tbb_exception.h
tbb::internal::concurrent_vector_base_v3::vector_allocator_ptr
void *(* vector_allocator_ptr)(concurrent_vector_base_v3 &, size_t)
allocator function pointer
Definition: concurrent_vector.h:178
tbb::internal::concurrent_vector_base_v3::internal_throw_exception
void __TBB_EXPORTED_METHOD internal_throw_exception(size_type) const
Obsolete.
Definition: concurrent_vector.cpp:333
tbb::internal::concurrent_vector_base_v3::enforce_segment_allocated
friend void enforce_segment_allocated(segment_value_t const &s, internal::exception_id exception=eid_bad_last_alloc)
Definition: concurrent_vector.h:121
tbb::internal::concurrent_vector_base_v3::segment_index_t
size_t segment_index_t
Definition: concurrent_vector.h:87
tbb::internal::concurrent_vector_base_v3::helper::destroy_body
Definition: concurrent_vector.cpp:186
tbb::internal::concurrent_vector_base_v3::helper::cleanup
void cleanup()
Out of line code to assists destructor in infrequent cases.
Definition: concurrent_vector.cpp:281
tbb::internal::concurrent_vector_base_v3::helper::segment_not_used_predicate
Definition: concurrent_vector.cpp:99
tbb::internal::concurrent_vector_base_v3::internal_compact
void *__TBB_EXPORTED_METHOD internal_compact(size_type element_size, void *table, internal_array_op1 destroy, internal_array_op2 copy)
Definition: concurrent_vector.cpp:511
tbb::internal::concurrent_vector_base_v3::segment_value_t
Definition: concurrent_vector.h:104
tbb::internal::concurrent_vector_base_v3::segment_not_used
Definition: concurrent_vector.h:99
tbb::internal::concurrent_vector_base_v3::my_storage
segment_t my_storage[pointers_per_short_table]
embedded storage of segment pointers
Definition: concurrent_vector.h:190
tbb_misc.h
__TBB_TRY
#define __TBB_TRY
Definition: tbb_stddef.h:283
s
void const char const char int ITT_FORMAT __itt_group_sync s
Definition: ittnotify_static.h:91
tbb::internal::concurrent_vector_base_v3::helper::page_size
static const size_type page_size
memory page size
Definition: concurrent_vector.cpp:43
tbb::internal::concurrent_vector_base_v3::internal_push_back
void *__TBB_EXPORTED_METHOD internal_push_back(size_type element_size, size_type &index)
Definition: concurrent_vector.cpp:418
tbb::internal::concurrent_vector_base_v3::my_first_block
atomic< size_type > my_first_block
count of segments in the first block
Definition: concurrent_vector.h:181
tbb::internal::concurrent_vector_base_v3::helper::~helper
~helper()
Definition: concurrent_vector.cpp:160
tbb::internal::concurrent_vector_base_v3::~concurrent_vector_base_v3
__TBB_EXPORTED_METHOD ~concurrent_vector_base_v3()
Definition: concurrent_vector.cpp:313
tbb::internal::no_assign
Base class for types that should not be assigned.
Definition: tbb_stddef.h:322
concurrent_vector.h
tbb::internal::eid_bad_alloc
Definition: tbb_exception.h:68
tbb::internal::concurrent_vector_base_v3::helper::apply
size_type apply(const F &func)
Definition: concurrent_vector.cpp:141
tbb::internal::concurrent_vector_base_v3::helper::acquire_segment
static segment_t & acquire_segment(concurrent_vector_base_v3 &v, size_type index, size_type element_size, bool owner)
Definition: concurrent_vector.cpp:104
tbb::internal::concurrent_vector_base_v3::helper::safe_init_body::arg
const void * arg
Definition: concurrent_vector.cpp:179
tbb::internal::concurrent_vector_base_v3::internal_clear
segment_index_t __TBB_EXPORTED_METHOD internal_clear(internal_array_op1 destroy)
Definition: concurrent_vector.cpp:501
tbb::internal::eid_reservation_length_error
Definition: tbb_exception.h:83
tbb::internal::concurrent_vector_base_v3::my_early_size
atomic< size_type > my_early_size
Requested size of vector.
Definition: concurrent_vector.h:184
tbb::internal::concurrent_vector_base_v3::internal_array_op2
void(__TBB_EXPORTED_FUNC * internal_array_op2)(void *dst, const void *src, size_type n)
An operation on n-element destination array and n-element source array.
Definition: concurrent_vector.h:246
tbb::internal::concurrent_vector_base_v3::helper::safe_init_body::func
internal_array_op2 func
Definition: concurrent_vector.cpp:178
tbb::internal::concurrent_vector_base_v3::helper::table
segment_t * table
Definition: concurrent_vector.cpp:122
sync_releasing
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p sync_releasing
Definition: ittnotify_static.h:104
tbb::internal::concurrent_vector_base_v3::pointers_per_long_table
Definition: concurrent_vector.h:96
tbb::internal::concurrent_vector_base_v3::internal_copy
void __TBB_EXPORTED_METHOD internal_copy(const concurrent_vector_base_v3 &src, size_type element_size, internal_array_op2 copy)
Definition: concurrent_vector.cpp:356
__TBB_CATCH
#define __TBB_CATCH(e)
Definition: tbb_stddef.h:284
tbb::internal::concurrent_vector_base_v3::internal_grow_by
size_type __TBB_EXPORTED_METHOD internal_grow_by(size_type delta, size_type element_size, internal_array_op2 init, const void *src)
Definition: concurrent_vector.cpp:467
tbb::internal::NFS_Free
void __TBB_EXPORTED_FUNC NFS_Free(void *)
Free memory allocated by NFS_Allocate.
Definition: cache_aligned_allocator.cpp:198
tbb::internal::concurrent_vector_base_v3::internal_swap
void __TBB_EXPORTED_METHOD internal_swap(concurrent_vector_base_v3 &v)
Definition: concurrent_vector.cpp:582
tbb::internal::concurrent_vector_base_v3::segment_t
Definition: concurrent_vector.h:128
tbb::internal::concurrent_vector_base_v3::helper::incompact_predicate
static bool incompact_predicate(size_type size)
Definition: concurrent_vector.cpp:45
tbb::internal::concurrent_vector_base_v3::helper::find_segment_end
static size_type find_segment_end(const concurrent_vector_base_v3 &v)
Definition: concurrent_vector.cpp:49
tbb::internal::concurrent_vector_base_v3::helper::publish_segment
static void publish_segment(segment_t &s, argument_type rhs)
Publish segment so other threads can see it.
Definition: concurrent_vector.cpp:83
tbb::release
Release.
Definition: atomic.h:59
tbb::internal::concurrent_vector_base_v3::helper::init_body::arg
const void * arg
Definition: concurrent_vector.cpp:171
tbb::internal::concurrent_vector_base_v3::helper::element_size
size_type element_size
Definition: concurrent_vector.cpp:123
tbb::internal::concurrent_vector_base_v3::internal_reserve
void __TBB_EXPORTED_METHOD internal_reserve(size_type n, size_type element_size, size_type max_size)
Definition: concurrent_vector.cpp:339
__TBB_RETHROW
#define __TBB_RETHROW()
Definition: tbb_stddef.h:286
tbb::internal::NFS_Allocate
void *__TBB_EXPORTED_FUNC NFS_Allocate(size_t n_element, size_t element_size, void *hint)
Allocate memory on cache/sector line boundary.
Definition: cache_aligned_allocator.cpp:176
tbb::internal::concurrent_vector_base_v3::helper::first_segment
void first_segment()
Definition: concurrent_vector.cpp:126
tbb::internal::concurrent_vector_base_v3::helper::safe_init_body::operator()
void operator()(segment_t &s, void *begin, size_type n) const
Definition: concurrent_vector.cpp:181
tbb::internal::concurrent_vector_base_v3::internal_capacity
size_type __TBB_EXPORTED_METHOD internal_capacity() const
Definition: concurrent_vector.cpp:329

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.