| /* |
| Copyright 2005-2010 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. |
| */ |
| |
| #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> |
| |
| #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].array > internal::vector_allocation_error_flag ) |
| ++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_neccessary(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. |
| inline static void publish_segment( segment_t& s, void* rhs ) { |
| // see also itt_store_pointer_with_release_v3() |
| ITT_NOTIFY( sync_releasing, &s.array ); |
| __TBB_store_with_release( s.array, rhs ); |
| } |
| |
| static size_type enable_segment(concurrent_vector_base_v3 &v, size_type k, size_type element_size); |
| |
| // 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); |
| |
| 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 arument |
| if( !__TBB_load_with_acquire(s.array) ) { // do not check for internal::vector_allocation_error_flag |
| if( owner ) { |
| enable_segment( v, index, element_size ); |
| } else { |
| ITT_NOTIFY(sync_prepare, &s.array); |
| spin_wait_while_eq( s.array, (void*)0 ); |
| ITT_NOTIFY(sync_acquired, &s.array); |
| } |
| } else { |
| ITT_NOTIFY(sync_acquired, &s.array); |
| } |
| if( s.array <= internal::vector_allocation_error_flag ) // check for internal::vector_allocation_error_flag |
| throw_exception(eid_bad_last_alloc); // throw custom exception, because it's hard to recover after internal::vector_allocation_error_flag correctly |
| 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) noexcept |
| : table(segments), first_block(fb), k(index), sz(0), start(s), finish(f), element_size(esize) {} |
| inline void first_segment() noexcept { |
| __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() noexcept { |
| finish -= sz; start = 0; // offsets from next segment |
| if( !k ) k = first_block; |
| else { ++k; sz <<= 1; } |
| } |
| template<typename F> |
| inline size_type apply(const F &func) { |
| first_segment(); |
| while( sz < finish ) { // work for more than one segment |
| func( table[k], static_cast<char*>(table[k].array)+element_size*start, sz-start ); |
| next_segment(); |
| } |
| func( table[k], static_cast<char*>(table[k].array)+element_size*start, finish-start ); |
| return k; |
| } |
| inline void *get_segment_ptr(size_type index, bool wait) { |
| segment_t &s = table[index]; |
| if( !__TBB_load_with_acquire(s.array) && wait ) { |
| ITT_NOTIFY(sync_prepare, &s.array); |
| spin_wait_while_eq( s.array, (void*)0 ); |
| ITT_NOTIFY(sync_acquired, &s.array); |
| } |
| return s.array; |
| } |
| ~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.array <= internal::vector_allocation_error_flag ) |
| 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.array > internal::vector_allocation_error_flag ) |
| 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 |
| // assigments 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].array) { |
| ITT_NOTIFY(sync_prepare, &v.my_storage[i].array); |
| atomic_backoff backoff; |
| do backoff.pause(); while( v.my_segment == v.my_storage && !v.my_storage[i].array ); |
| ITT_NOTIFY(sync_acquired, &v.my_storage[i].array); |
| } |
| if( v.my_segment != v.my_storage ) return; |
| |
| segment_t* s = (segment_t*)NFS_Allocate( pointers_per_long_table, sizeof(segment_t), NULL ); |
| // No need to check !s here, because NFS_Allocate throws exception if it cannot allocate the requested storage. |
| memset( s, 0, pointers_per_long_table*sizeof(segment_t) ); |
| for( segment_index_t i = 0; i < pointers_per_short_table; i++) |
| s[i] = v.my_storage[i]; |
| if( v.my_segment.compare_and_swap( s, v.my_storage ) != v.my_storage ) |
| NFS_Free( s ); |
| // 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) { |
| segment_t* s = v.my_segment; // TODO: optimize out as argument? Optimize accesses to my_first_block |
| __TBB_ASSERT( s[k].array <= internal::vector_allocation_error_flag, "concurrent operation during growth?" ); |
| if( !k ) { |
| assign_first_segment_if_neccessary(v, default_initial_segments-1); |
| __TBB_TRY { |
| publish_segment(s[0], allocate_segment(v, segment_size(v.my_first_block) ) ); |
| } __TBB_CATCH(...) { // intercept exception here, assign internal::vector_allocation_error_flag value, re-throw exception |
| publish_segment(s[0], internal::vector_allocation_error_flag); |
| __TBB_RETHROW(); |
| } |
| return 2; |
| } |
| size_type m = segment_size(k); |
| if( !v.my_first_block ) // push_back only |
| spin_wait_while_eq( v.my_first_block, segment_index_t(0) ); |
| if( k < v.my_first_block ) { |
| // s[0].array is changed only once ( 0 -> !0 ) and points to uninitialized memory |
| void *array0 = __TBB_load_with_acquire(s[0].array); |
| if( !array0 ) { |
| // sync_prepare called only if there is a wait |
| ITT_NOTIFY(sync_prepare, &s[0].array ); |
| spin_wait_while_eq( s[0].array, (void*)0 ); |
| array0 = __TBB_load_with_acquire(s[0].array); |
| } |
| ITT_NOTIFY(sync_acquired, &s[0].array); |
| if( array0 <= internal::vector_allocation_error_flag ) { // check for internal::vector_allocation_error_flag of initial segment |
| publish_segment(s[k], internal::vector_allocation_error_flag); // and assign internal::vector_allocation_error_flag here |
| throw_exception(eid_bad_last_alloc); // throw custom exception |
| } |
| publish_segment( s[k], |
| static_cast<void*>( static_cast<char*>(array0) + segment_base(k)*element_size ) |
| ); |
| } else { |
| __TBB_TRY { |
| publish_segment(s[k], allocate_segment(v, m)); |
| } __TBB_CATCH(...) { // intercept exception here, assign internal::vector_allocation_error_flag value, re-throw exception |
| publish_segment(s[k], internal::vector_allocation_error_flag); |
| __TBB_RETHROW(); |
| } |
| } |
| return m; |
| } |
| |
| 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_ptr(k_start++, true); // wait |
| if( k_start < first_block ) { |
| void *array0 = get_segment_ptr(0, start>0); // wait if necessary |
| if( array0 && !k_start ) ++k_start; |
| if( array0 <= internal::vector_allocation_error_flag ) |
| for(; k_start < first_block && k_start <= k_end; ++k_start ) |
| publish_segment(table[k_start], internal::vector_allocation_error_flag); |
| else for(; k_start < first_block && k_start <= k_end; ++k_start ) |
| publish_segment(table[k_start], static_cast<void*>( |
| static_cast<char*>(array0) + segment_base(k_start)*element_size) ); |
| } |
| for(; k_start <= k_end; ++k_start ) // not in first block |
| if( !__TBB_load_with_acquire(table[k_start].array) ) |
| publish_segment(table[k_start], internal::vector_allocation_error_flag); |
| // fill alocated items |
| first_segment(); |
| goto recover; |
| } |
| while( sz <= finish ) { // there is still work for at least one segment |
| next_segment(); |
| recover: |
| void *array = table[k].array; |
| if( array > internal::vector_allocation_error_flag ) |
| std::memset( static_cast<char*>(array)+element_size*start, 0, ((sz<finish?sz:finish) - start)*element_size ); |
| else __TBB_ASSERT( array == internal::vector_allocation_error_flag, NULL ); |
| } |
| } |
| |
| concurrent_vector_base_v3::~concurrent_vector_base_v3() { |
| segment_t* s = my_segment; |
| if( s != my_storage ) { |
| // Clear short segment. |
| for( segment_index_t i = 0; i < pointers_per_short_table; i++) |
| my_storage[i].array = NULL; |
| #if TBB_USE_DEBUG |
| for( segment_index_t i = 0; i < pointers_per_long_table; i++) |
| __TBB_ASSERT( my_segment[i].array <= internal::vector_allocation_error_flag, "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_neccessary(*this, segment_index_of(n-1)); |
| segment_index_t k = helper::find_segment_end(*this); |
| __TBB_TRY { |
| for( ; segment_base(k)<n; ++k ) { |
| helper::extend_table_if_necessary(*this, k, 0); |
| if(my_segment[k].array <= internal::vector_allocation_error_flag) |
| helper::enable_segment(*this, k, element_size); |
| } |
| } __TBB_CATCH(...) { |
| my_segment[k].array = NULL; |
| __TBB_RETHROW(); // repair and rethrow |
| } |
| } |
| |
| 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_neccessary(*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 == (segment_t*)src.my_storage && k >= pointers_per_short_table) |
| || src.my_segment[k].array <= internal::vector_allocation_error_flag ) { |
| 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].array, src.my_segment[k].array, 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].array <= internal::vector_allocation_error_flag) // check vector was broken before |
| throw_exception(eid_bad_last_alloc); // throw custom exception |
| // destructors are supposed to not throw any exceptions |
| destroy( (char*)my_segment[k].array+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_neccessary(*this, segment_index_of(n)); |
| size_type b; |
| for( segment_index_t k=0; (b=segment_base(k))<n; ++k ) { |
| if( (src.my_segment == (segment_t*)src.my_storage && k >= pointers_per_short_table) |
| || src.my_segment[k].array <= internal::vector_allocation_error_flag ) { // 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].array ) |
| helper::enable_segment(*this, k, element_size); |
| else if( my_segment[k].array <= internal::vector_allocation_error_flag ) |
| 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].array, src.my_segment[k].array, a ); |
| m -= a; |
| a *= element_size; |
| } |
| if( m>0 ) |
| copy( (char*)my_segment[k].array+a, (char*)src.my_segment[k].array+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 = __TBB_FetchAndIncrementWacquire(&my_early_size); |
| 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*)((char*)s.array+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.array) { |
| ITT_NOTIFY(sync_prepare, &s.array); |
| atomic_backoff backoff; |
| do backoff.pause(); |
| while( !__TBB_load_with_acquire(my_segment[i].array) ); // my_segment may change concurrently |
| ITT_NOTIFY(sync_acquired, &s.array); |
| } |
| if( my_segment[i].array <= internal::vector_allocation_error_flag ) |
| 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_neccessary(*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 ); |
| memset(&old, 0, sizeof(old)); |
| |
| if ( k != first_block && k ) // first segment optimization |
| { |
| // exception can occur here |
| void *seg = old.table[0] = helper::allocate_segment( *this, segment_size(k) ); |
| 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].array > internal::vector_allocation_error_flag, NULL); |
| void *s = static_cast<void*>( |
| static_cast<char*>(seg) + segment_base(i)*element_size ); |
| if(j + my_segment_size >= my_size) my_segment_size = my_size - j; |
| __TBB_TRY { // exception can occur here |
| copy( s, segment_table[i].array, my_segment_size ); |
| } __TBB_CATCH(...) { // destroy all the already copied items |
| helper for_each(reinterpret_cast<segment_t*>(&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 |
| memcpy(old.table, segment_table, k * sizeof(segment_t)); |
| for (segment_index_t i = 0; i < k; i++) { |
| segment_table[i].array = 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], 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; |
| memcpy(old.table+k_stop, segment_table+k_stop, (k_end-k_stop) * sizeof(segment_t)); |
| memset(segment_table+k_stop, 0, (k_end-k_stop) * sizeof(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, v_sz = v.my_early_size; |
| if(!my_sz && !v_sz) return; |
| size_type tmp = my_first_block; my_first_block = v.my_first_block; v.my_first_block = tmp; |
| bool my_short = (my_segment == my_storage), v_short = (v.my_segment == v.my_storage); |
| if ( my_short && v_short ) { // swap both tables |
| char tbl[pointers_per_short_table * sizeof(segment_t)]; |
| memcpy(tbl, my_storage, pointers_per_short_table * sizeof(segment_t)); |
| memcpy(my_storage, v.my_storage, pointers_per_short_table * sizeof(segment_t)); |
| memcpy(v.my_storage, tbl, pointers_per_short_table * sizeof(segment_t)); |
| } |
| else if ( my_short ) { // my -> v |
| memcpy(v.my_storage, my_storage, pointers_per_short_table * sizeof(segment_t)); |
| my_segment = v.my_segment; v.my_segment = v.my_storage; |
| } |
| else if ( v_short ) { // v -> my |
| memcpy(my_storage, v.my_storage, pointers_per_short_table * sizeof(segment_t)); |
| v.my_segment = my_segment; my_segment = my_storage; |
| } else { |
| segment_t *ptr = my_segment; my_segment = v.my_segment; v.my_segment = ptr; |
| } |
| my_early_size = v_sz; v.my_early_size = my_sz; |
| } |
| |
| } // namespace internal |
| |
| } // tbb |
