You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
632 lines
30 KiB
C++
632 lines
30 KiB
C++
/*
|
|
Copyright 2005-2014 Intel Corporation. All Rights Reserved.
|
|
|
|
This file is part of Threading Building Blocks. Threading Building Blocks is free software;
|
|
you can redistribute it and/or modify it under the terms of the GNU General Public License
|
|
version 2 as published by the Free Software Foundation. Threading Building Blocks is
|
|
distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
|
|
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
|
|
See the GNU General Public License for more details. You should have received a copy of
|
|
the GNU General Public License along with Threading Building Blocks; if not, write to the
|
|
Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
|
|
|
|
As a special exception, you may use this file as part of a free software library without
|
|
restriction. Specifically, if other files instantiate templates or use macros or inline
|
|
functions from this file, or you compile this file and link it with other files to produce
|
|
an executable, this file does not by itself cause the resulting executable to be covered
|
|
by the GNU General Public License. This exception does not however invalidate any other
|
|
reasons why the executable file might be covered by the GNU General Public 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"
|
|
|
|
#if !TBB_USE_EXCEPTIONS && _MSC_VER
|
|
// Suppress "C++ exception handler used, but unwind semantics are not enabled" warning in STL headers
|
|
#pragma warning (push)
|
|
#pragma warning (disable: 4530)
|
|
#endif
|
|
|
|
#include <cstring>
|
|
#include <memory> //for uninitialized_fill_n
|
|
|
|
#if !TBB_USE_EXCEPTIONS && _MSC_VER
|
|
#pragma warning (pop)
|
|
#endif
|
|
|
|
#if defined(_MSC_VER) && defined(_Wp64)
|
|
// Workaround for overzealous compiler warnings in /Wp64 mode
|
|
#pragma warning (disable: 4267)
|
|
#endif
|
|
|
|
using namespace std;
|
|
|
|
namespace tbb {
|
|
|
|
namespace internal {
|
|
class concurrent_vector_base_v3::helper :no_assign {
|
|
public:
|
|
//! memory page size
|
|
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
|
|
//! assign first segment size. k - is index of last segment to be allocated, not a count of segments
|
|
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;
|
|
}
|
|
|
|
//! Publish segment so other threads can see it.
|
|
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);
|
|
}
|
|
if(s.load<relaxed>() != segment_allocated())
|
|
throw_exception(eid_bad_last_alloc); // throw custom exception, because it's hard to recover correctly after segment_allocation_failed state
|
|
return s;
|
|
}
|
|
|
|
///// non-static fields of helper for exception-safe iteration across segments
|
|
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();
|
|
}
|
|
|
|
//! Out of line code to assists destructor in infrequent cases.
|
|
void cleanup();
|
|
|
|
/// TODO: turn into lambda functions when available
|
|
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 {
|
|
if(s.load<relaxed>() != segment_allocated())
|
|
throw_exception(eid_bad_last_alloc); // throw custom exception
|
|
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 );
|
|
}
|
|
};
|
|
};
|
|
|
|
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]);
|
|
if(array0 != segment_allocated()) { // check for segment_allocation_failed state of initial segment
|
|
publish_segment(s[k], segment_allocation_failed()); // and assign segment_allocation_failed state here
|
|
throw_exception(eid_bad_last_alloc); // throw custom exception
|
|
}
|
|
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 {
|
|
switch(t) {
|
|
case 0: throw_exception(eid_out_of_range);
|
|
case 1: throw_exception(eid_segment_range_error);
|
|
case 2: throw_exception(eid_index_range_error);
|
|
}
|
|
}
|
|
|
|
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 );
|
|
if( my_segment[k].load<relaxed>() != segment_allocated()) // check vector was broken before
|
|
throw_exception(eid_bad_last_alloc); // throw custom exception
|
|
// 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 if( my_segment[k].load<relaxed>() != segment_allocated() )
|
|
throw_exception(eid_bad_last_alloc); // throw custom exception
|
|
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);
|
|
}
|
|
if( my_segment[i].load<relaxed>() != segment_allocated() )
|
|
throw_exception(eid_bad_last_alloc);
|
|
}
|
|
#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
|