00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #ifndef __TBB_concurrent_vector_H
00022 #define __TBB_concurrent_vector_H
00023
00024 #include "tbb_stddef.h"
00025 #include "tbb_exception.h"
00026 #include "atomic.h"
00027 #include "cache_aligned_allocator.h"
00028 #include "blocked_range.h"
00029 #include "tbb_machine.h"
00030 #include <new>
00031
00032 #if !TBB_USE_EXCEPTIONS && _MSC_VER
00033
00034 #pragma warning (push)
00035 #pragma warning (disable: 4530)
00036 #endif
00037
00038 #include <algorithm>
00039 #include <iterator>
00040
00041 #if !TBB_USE_EXCEPTIONS && _MSC_VER
00042 #pragma warning (pop)
00043 #endif
00044
00045 #if _MSC_VER==1500 && !__INTEL_COMPILER
00046
00047 #pragma warning( push )
00048 #pragma warning( disable: 4985 )
00049 #endif
00050 #include <limits>
00051 #if _MSC_VER==1500 && !__INTEL_COMPILER
00052 #pragma warning( pop )
00053 #endif
00054
00055 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) && defined(_Wp64)
00056
00057 #pragma warning (push)
00058 #pragma warning (disable: 4267)
00059 #endif
00060
00061 namespace tbb {
00062
00063 template<typename T, class A = cache_aligned_allocator<T> >
00064 class concurrent_vector;
00065
00067 namespace internal {
00068
00070 static void *const vector_allocation_error_flag = reinterpret_cast<void*>(size_t(63));
00071
00073 void* __TBB_EXPORTED_FUNC itt_load_pointer_v3( const void* src );
00074
00076
00077 class concurrent_vector_base_v3 {
00078 protected:
00079
00080
00081 typedef size_t segment_index_t;
00082 typedef size_t size_type;
00083
00084
00085 enum {
00086
00087 default_initial_segments = 1,
00089 pointers_per_short_table = 3,
00090 pointers_per_long_table = sizeof(segment_index_t) * 8
00091 };
00092
00093
00094 struct segment_t {
00095 void* array;
00096 #if TBB_USE_ASSERT
00097 ~segment_t() {
00098 __TBB_ASSERT( array <= internal::vector_allocation_error_flag, "should have been freed by clear" );
00099 }
00100 #endif
00101 };
00102
00103
00104
00106 void* (*vector_allocator_ptr)(concurrent_vector_base_v3 &, size_t);
00107
00109 atomic<size_type> my_first_block;
00110
00112 atomic<size_type> my_early_size;
00113
00115 atomic<segment_t*> my_segment;
00116
00118 segment_t my_storage[pointers_per_short_table];
00119
00120
00121
00122 concurrent_vector_base_v3() {
00123 my_early_size = 0;
00124 my_first_block = 0;
00125 for( segment_index_t i = 0; i < pointers_per_short_table; i++)
00126 my_storage[i].array = NULL;
00127 my_segment = my_storage;
00128 }
00129 __TBB_EXPORTED_METHOD ~concurrent_vector_base_v3();
00130
00131 static segment_index_t segment_index_of( size_type index ) {
00132 return segment_index_t( __TBB_Log2( index|1 ) );
00133 }
00134
00135 static segment_index_t segment_base( segment_index_t k ) {
00136 return (segment_index_t(1)<<k & ~segment_index_t(1));
00137 }
00138
00139 static inline segment_index_t segment_base_index_of( segment_index_t &index ) {
00140 segment_index_t k = segment_index_of( index );
00141 index -= segment_base(k);
00142 return k;
00143 }
00144
00145 static size_type segment_size( segment_index_t k ) {
00146 return segment_index_t(1)<<k;
00147 }
00148
00150 typedef void (__TBB_EXPORTED_FUNC *internal_array_op1)(void* begin, size_type n );
00151
00153 typedef void (__TBB_EXPORTED_FUNC *internal_array_op2)(void* dst, const void* src, size_type n );
00154
00156 struct internal_segments_table {
00157 segment_index_t first_block;
00158 void* table[pointers_per_long_table];
00159 };
00160
00161 void __TBB_EXPORTED_METHOD internal_reserve( size_type n, size_type element_size, size_type max_size );
00162 size_type __TBB_EXPORTED_METHOD internal_capacity() const;
00163 void internal_grow( size_type start, size_type finish, size_type element_size, internal_array_op2 init, const void *src );
00164 size_type __TBB_EXPORTED_METHOD internal_grow_by( size_type delta, size_type element_size, internal_array_op2 init, const void *src );
00165 void* __TBB_EXPORTED_METHOD internal_push_back( size_type element_size, size_type& index );
00166 segment_index_t __TBB_EXPORTED_METHOD internal_clear( internal_array_op1 destroy );
00167 void* __TBB_EXPORTED_METHOD internal_compact( size_type element_size, void *table, internal_array_op1 destroy, internal_array_op2 copy );
00168 void __TBB_EXPORTED_METHOD internal_copy( const concurrent_vector_base_v3& src, size_type element_size, internal_array_op2 copy );
00169 void __TBB_EXPORTED_METHOD internal_assign( const concurrent_vector_base_v3& src, size_type element_size,
00170 internal_array_op1 destroy, internal_array_op2 assign, internal_array_op2 copy );
00172 void __TBB_EXPORTED_METHOD internal_throw_exception(size_type) const;
00173 void __TBB_EXPORTED_METHOD internal_swap(concurrent_vector_base_v3& v);
00174
00175 void __TBB_EXPORTED_METHOD internal_resize( size_type n, size_type element_size, size_type max_size, const void *src,
00176 internal_array_op1 destroy, internal_array_op2 init );
00177 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 );
00178
00180 void __TBB_EXPORTED_METHOD internal_grow_to_at_least( size_type new_size, size_type element_size, internal_array_op2 init, const void *src );
00181 private:
00183 class helper;
00184 friend class helper;
00185 };
00186
00187 typedef concurrent_vector_base_v3 concurrent_vector_base;
00188
00190
00192 template<typename Container, typename Value>
00193 class vector_iterator
00194 {
00196 Container* my_vector;
00197
00199 size_t my_index;
00200
00202
00203 mutable Value* my_item;
00204
00205 template<typename C, typename T>
00206 friend vector_iterator<C,T> operator+( ptrdiff_t offset, const vector_iterator<C,T>& v );
00207
00208 template<typename C, typename T, typename U>
00209 friend bool operator==( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
00210
00211 template<typename C, typename T, typename U>
00212 friend bool operator<( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
00213
00214 template<typename C, typename T, typename U>
00215 friend ptrdiff_t operator-( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
00216
00217 template<typename C, typename U>
00218 friend class internal::vector_iterator;
00219
00220 #if !defined(_MSC_VER) || defined(__INTEL_COMPILER)
00221 template<typename T, class A>
00222 friend class tbb::concurrent_vector;
00223 #else
00224 public:
00225 #endif
00226
00227 vector_iterator( const Container& vector, size_t index, void *ptr = 0 ) :
00228 my_vector(const_cast<Container*>(&vector)),
00229 my_index(index),
00230 my_item(static_cast<Value*>(ptr))
00231 {}
00232
00233 public:
00235 vector_iterator() : my_vector(NULL), my_index(~size_t(0)), my_item(NULL) {}
00236
00237 vector_iterator( const vector_iterator<Container,typename Container::value_type>& other ) :
00238 my_vector(other.my_vector),
00239 my_index(other.my_index),
00240 my_item(other.my_item)
00241 {}
00242
00243 vector_iterator operator+( ptrdiff_t offset ) const {
00244 return vector_iterator( *my_vector, my_index+offset );
00245 }
00246 vector_iterator &operator+=( ptrdiff_t offset ) {
00247 my_index+=offset;
00248 my_item = NULL;
00249 return *this;
00250 }
00251 vector_iterator operator-( ptrdiff_t offset ) const {
00252 return vector_iterator( *my_vector, my_index-offset );
00253 }
00254 vector_iterator &operator-=( ptrdiff_t offset ) {
00255 my_index-=offset;
00256 my_item = NULL;
00257 return *this;
00258 }
00259 Value& operator*() const {
00260 Value* item = my_item;
00261 if( !item ) {
00262 item = my_item = &my_vector->internal_subscript(my_index);
00263 }
00264 __TBB_ASSERT( item==&my_vector->internal_subscript(my_index), "corrupt cache" );
00265 return *item;
00266 }
00267 Value& operator[]( ptrdiff_t k ) const {
00268 return my_vector->internal_subscript(my_index+k);
00269 }
00270 Value* operator->() const {return &operator*();}
00271
00273 vector_iterator& operator++() {
00274 size_t k = ++my_index;
00275 if( my_item ) {
00276
00277 if( (k& (k-2))==0 ) {
00278
00279 my_item= NULL;
00280 } else {
00281 ++my_item;
00282 }
00283 }
00284 return *this;
00285 }
00286
00288 vector_iterator& operator--() {
00289 __TBB_ASSERT( my_index>0, "operator--() applied to iterator already at beginning of concurrent_vector" );
00290 size_t k = my_index--;
00291 if( my_item ) {
00292
00293 if( (k& (k-2))==0 ) {
00294
00295 my_item= NULL;
00296 } else {
00297 --my_item;
00298 }
00299 }
00300 return *this;
00301 }
00302
00304 vector_iterator operator++(int) {
00305 vector_iterator result = *this;
00306 operator++();
00307 return result;
00308 }
00309
00311 vector_iterator operator--(int) {
00312 vector_iterator result = *this;
00313 operator--();
00314 return result;
00315 }
00316
00317
00318
00319 typedef ptrdiff_t difference_type;
00320 typedef Value value_type;
00321 typedef Value* pointer;
00322 typedef Value& reference;
00323 typedef std::random_access_iterator_tag iterator_category;
00324 };
00325
00326 template<typename Container, typename T>
00327 vector_iterator<Container,T> operator+( ptrdiff_t offset, const vector_iterator<Container,T>& v ) {
00328 return vector_iterator<Container,T>( *v.my_vector, v.my_index+offset );
00329 }
00330
00331 template<typename Container, typename T, typename U>
00332 bool operator==( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00333 return i.my_index==j.my_index && i.my_vector == j.my_vector;
00334 }
00335
00336 template<typename Container, typename T, typename U>
00337 bool operator!=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00338 return !(i==j);
00339 }
00340
00341 template<typename Container, typename T, typename U>
00342 bool operator<( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00343 return i.my_index<j.my_index;
00344 }
00345
00346 template<typename Container, typename T, typename U>
00347 bool operator>( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00348 return j<i;
00349 }
00350
00351 template<typename Container, typename T, typename U>
00352 bool operator>=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00353 return !(i<j);
00354 }
00355
00356 template<typename Container, typename T, typename U>
00357 bool operator<=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00358 return !(j<i);
00359 }
00360
00361 template<typename Container, typename T, typename U>
00362 ptrdiff_t operator-( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00363 return ptrdiff_t(i.my_index)-ptrdiff_t(j.my_index);
00364 }
00365
00366 template<typename T, class A>
00367 class allocator_base {
00368 public:
00369 typedef typename A::template
00370 rebind<T>::other allocator_type;
00371 allocator_type my_allocator;
00372
00373 allocator_base(const allocator_type &a = allocator_type() ) : my_allocator(a) {}
00374 };
00375
00376 }
00378
00380
00441 template<typename T, class A>
00442 class concurrent_vector: protected internal::allocator_base<T, A>,
00443 private internal::concurrent_vector_base {
00444 private:
00445 template<typename I>
00446 class generic_range_type: public blocked_range<I> {
00447 public:
00448 typedef T value_type;
00449 typedef T& reference;
00450 typedef const T& const_reference;
00451 typedef I iterator;
00452 typedef ptrdiff_t difference_type;
00453 generic_range_type( I begin_, I end_, size_t grainsize_ = 1) : blocked_range<I>(begin_,end_,grainsize_) {}
00454 template<typename U>
00455 generic_range_type( const generic_range_type<U>& r) : blocked_range<I>(r.begin(),r.end(),r.grainsize()) {}
00456 generic_range_type( generic_range_type& r, split ) : blocked_range<I>(r,split()) {}
00457 };
00458
00459 template<typename C, typename U>
00460 friend class internal::vector_iterator;
00461 public:
00462
00463
00464
00465 typedef internal::concurrent_vector_base_v3::size_type size_type;
00466 typedef typename internal::allocator_base<T, A>::allocator_type allocator_type;
00467
00468 typedef T value_type;
00469 typedef ptrdiff_t difference_type;
00470 typedef T& reference;
00471 typedef const T& const_reference;
00472 typedef T *pointer;
00473 typedef const T *const_pointer;
00474
00475 typedef internal::vector_iterator<concurrent_vector,T> iterator;
00476 typedef internal::vector_iterator<concurrent_vector,const T> const_iterator;
00477
00478 #if !defined(_MSC_VER) || _CPPLIB_VER>=300
00479
00480 typedef std::reverse_iterator<iterator> reverse_iterator;
00481 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00482 #else
00483
00484 typedef std::reverse_iterator<iterator,T,T&,T*> reverse_iterator;
00485 typedef std::reverse_iterator<const_iterator,T,const T&,const T*> const_reverse_iterator;
00486 #endif
00487
00488
00489
00490
00491 typedef generic_range_type<iterator> range_type;
00492 typedef generic_range_type<const_iterator> const_range_type;
00493
00494
00495
00496
00497
00499 explicit concurrent_vector(const allocator_type &a = allocator_type())
00500 : internal::allocator_base<T, A>(a)
00501 {
00502 vector_allocator_ptr = &internal_allocator;
00503 }
00504
00506 concurrent_vector( const concurrent_vector& vector, const allocator_type& a = allocator_type() )
00507 : internal::allocator_base<T, A>(a)
00508 {
00509 vector_allocator_ptr = &internal_allocator;
00510 __TBB_TRY {
00511 internal_copy(vector, sizeof(T), ©_array);
00512 } __TBB_CATCH(...) {
00513 segment_t *table = my_segment;
00514 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00515 __TBB_RETHROW();
00516 }
00517 }
00518
00520 template<class M>
00521 concurrent_vector( const concurrent_vector<T, M>& vector, const allocator_type& a = allocator_type() )
00522 : internal::allocator_base<T, A>(a)
00523 {
00524 vector_allocator_ptr = &internal_allocator;
00525 __TBB_TRY {
00526 internal_copy(vector.internal_vector_base(), sizeof(T), ©_array);
00527 } __TBB_CATCH(...) {
00528 segment_t *table = my_segment;
00529 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00530 __TBB_RETHROW();
00531 }
00532 }
00533
00535 explicit concurrent_vector(size_type n)
00536 {
00537 vector_allocator_ptr = &internal_allocator;
00538 __TBB_TRY {
00539 internal_resize( n, sizeof(T), max_size(), NULL, &destroy_array, &initialize_array );
00540 } __TBB_CATCH(...) {
00541 segment_t *table = my_segment;
00542 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00543 __TBB_RETHROW();
00544 }
00545 }
00546
00548 concurrent_vector(size_type n, const_reference t, const allocator_type& a = allocator_type())
00549 : internal::allocator_base<T, A>(a)
00550 {
00551 vector_allocator_ptr = &internal_allocator;
00552 __TBB_TRY {
00553 internal_resize( n, sizeof(T), max_size(), static_cast<const void*>(&t), &destroy_array, &initialize_array_by );
00554 } __TBB_CATCH(...) {
00555 segment_t *table = my_segment;
00556 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00557 __TBB_RETHROW();
00558 }
00559 }
00560
00562 template<class I>
00563 concurrent_vector(I first, I last, const allocator_type &a = allocator_type())
00564 : internal::allocator_base<T, A>(a)
00565 {
00566 vector_allocator_ptr = &internal_allocator;
00567 __TBB_TRY {
00568 internal_assign_range(first, last, static_cast<is_integer_tag<std::numeric_limits<I>::is_integer> *>(0) );
00569 } __TBB_CATCH(...) {
00570 segment_t *table = my_segment;
00571 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00572 __TBB_RETHROW();
00573 }
00574 }
00575
00577 concurrent_vector& operator=( const concurrent_vector& vector ) {
00578 if( this != &vector )
00579 internal_assign(vector, sizeof(T), &destroy_array, &assign_array, ©_array);
00580 return *this;
00581 }
00582
00584 template<class M>
00585 concurrent_vector& operator=( const concurrent_vector<T, M>& vector ) {
00586 if( static_cast<void*>( this ) != static_cast<const void*>( &vector ) )
00587 internal_assign(vector.internal_vector_base(),
00588 sizeof(T), &destroy_array, &assign_array, ©_array);
00589 return *this;
00590 }
00591
00592
00593
00594
00596 #if TBB_DEPRECATED
00597
00598 size_type grow_by( size_type delta ) {
00599 return delta ? internal_grow_by( delta, sizeof(T), &initialize_array, NULL ) : my_early_size;
00600 }
00601 #else
00602
00603 iterator grow_by( size_type delta ) {
00604 return iterator(*this, delta ? internal_grow_by( delta, sizeof(T), &initialize_array, NULL ) : my_early_size);
00605 }
00606 #endif
00607
00609 #if TBB_DEPRECATED
00610
00611 size_type grow_by( size_type delta, const_reference t ) {
00612 return delta ? internal_grow_by( delta, sizeof(T), &initialize_array_by, static_cast<const void*>(&t) ) : my_early_size;
00613 }
00614 #else
00615
00616 iterator grow_by( size_type delta, const_reference t ) {
00617 return iterator(*this, delta ? internal_grow_by( delta, sizeof(T), &initialize_array_by, static_cast<const void*>(&t) ) : my_early_size);
00618 }
00619 #endif
00620
00622 #if TBB_DEPRECATED
00623
00625 void grow_to_at_least( size_type n ) {
00626 if( n ) internal_grow_to_at_least_with_result( n, sizeof(T), &initialize_array, NULL );
00627 };
00628 #else
00629
00633 iterator grow_to_at_least( size_type n ) {
00634 size_type m=0;
00635 if( n ) {
00636 m = internal_grow_to_at_least_with_result( n, sizeof(T), &initialize_array, NULL );
00637 if( m>n ) m=n;
00638 }
00639 return iterator(*this, m);
00640 };
00641 #endif
00642
00644 #if TBB_DEPRECATED
00645 size_type push_back( const_reference item )
00646 #else
00647
00648 iterator push_back( const_reference item )
00649 #endif
00650 {
00651 size_type k;
00652 void *ptr = internal_push_back(sizeof(T),k);
00653 internal_loop_guide loop(1, ptr);
00654 loop.init(&item);
00655 #if TBB_DEPRECATED
00656 return k;
00657 #else
00658 return iterator(*this, k, ptr);
00659 #endif
00660 }
00661
00663
00665 reference operator[]( size_type index ) {
00666 return internal_subscript(index);
00667 }
00668
00670 const_reference operator[]( size_type index ) const {
00671 return internal_subscript(index);
00672 }
00673
00675 reference at( size_type index ) {
00676 return internal_subscript_with_exceptions(index);
00677 }
00678
00680 const_reference at( size_type index ) const {
00681 return internal_subscript_with_exceptions(index);
00682 }
00683
00685 range_type range( size_t grainsize = 1) {
00686 return range_type( begin(), end(), grainsize );
00687 }
00688
00690 const_range_type range( size_t grainsize = 1 ) const {
00691 return const_range_type( begin(), end(), grainsize );
00692 }
00693
00694
00695
00697 size_type size() const {
00698 size_type sz = my_early_size, cp = internal_capacity();
00699 return cp < sz ? cp : sz;
00700 }
00701
00703 bool empty() const {return !my_early_size;}
00704
00706 size_type capacity() const {return internal_capacity();}
00707
00709
00711 void reserve( size_type n ) {
00712 if( n )
00713 internal_reserve(n, sizeof(T), max_size());
00714 }
00715
00717 void resize( size_type n ) {
00718 internal_resize( n, sizeof(T), max_size(), NULL, &destroy_array, &initialize_array );
00719 }
00720
00722 void resize( size_type n, const_reference t ) {
00723 internal_resize( n, sizeof(T), max_size(), static_cast<const void*>(&t), &destroy_array, &initialize_array_by );
00724 }
00725
00726 #if TBB_DEPRECATED
00728 void compact() {shrink_to_fit();}
00729 #endif
00730
00732 void shrink_to_fit();
00733
00735 size_type max_size() const {return (~size_type(0))/sizeof(T);}
00736
00737
00738
00739
00740
00742 iterator begin() {return iterator(*this,0);}
00744 iterator end() {return iterator(*this,size());}
00746 const_iterator begin() const {return const_iterator(*this,0);}
00748 const_iterator end() const {return const_iterator(*this,size());}
00750 const_iterator cbegin() const {return const_iterator(*this,0);}
00752 const_iterator cend() const {return const_iterator(*this,size());}
00754 reverse_iterator rbegin() {return reverse_iterator(end());}
00756 reverse_iterator rend() {return reverse_iterator(begin());}
00758 const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
00760 const_reverse_iterator rend() const {return const_reverse_iterator(begin());}
00762 const_reverse_iterator crbegin() const {return const_reverse_iterator(end());}
00764 const_reverse_iterator crend() const {return const_reverse_iterator(begin());}
00766 reference front() {
00767 __TBB_ASSERT( size()>0, NULL);
00768 return static_cast<T*>(my_segment[0].array)[0];
00769 }
00771 const_reference front() const {
00772 __TBB_ASSERT( size()>0, NULL);
00773 return static_cast<const T*>(my_segment[0].array)[0];
00774 }
00776 reference back() {
00777 __TBB_ASSERT( size()>0, NULL);
00778 return internal_subscript( size()-1 );
00779 }
00781 const_reference back() const {
00782 __TBB_ASSERT( size()>0, NULL);
00783 return internal_subscript( size()-1 );
00784 }
00786 allocator_type get_allocator() const { return this->my_allocator; }
00787
00789 void assign(size_type n, const_reference t) {
00790 clear();
00791 internal_resize( n, sizeof(T), max_size(), static_cast<const void*>(&t), &destroy_array, &initialize_array_by );
00792 }
00793
00795 template<class I>
00796 void assign(I first, I last) {
00797 clear(); internal_assign_range( first, last, static_cast<is_integer_tag<std::numeric_limits<I>::is_integer> *>(0) );
00798 }
00799
00801 void swap(concurrent_vector &vector) {
00802 if( this != &vector ) {
00803 concurrent_vector_base_v3::internal_swap(static_cast<concurrent_vector_base_v3&>(vector));
00804 std::swap(this->my_allocator, vector.my_allocator);
00805 }
00806 }
00807
00809
00810 void clear() {
00811 internal_clear(&destroy_array);
00812 }
00813
00815 ~concurrent_vector() {
00816 segment_t *table = my_segment;
00817 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00818
00819 }
00820
00821 const internal::concurrent_vector_base_v3 &internal_vector_base() const { return *this; }
00822 private:
00824 static void *internal_allocator(internal::concurrent_vector_base_v3 &vb, size_t k) {
00825 return static_cast<concurrent_vector<T, A>&>(vb).my_allocator.allocate(k);
00826 }
00828 void internal_free_segments(void *table[], segment_index_t k, segment_index_t first_block);
00829
00831 T& internal_subscript( size_type index ) const;
00832
00834 T& internal_subscript_with_exceptions( size_type index ) const;
00835
00837 void internal_assign_n(size_type n, const_pointer p) {
00838 internal_resize( n, sizeof(T), max_size(), static_cast<const void*>(p), &destroy_array, p? &initialize_array_by : &initialize_array );
00839 }
00840
00842 template<bool B> class is_integer_tag;
00843
00845 template<class I>
00846 void internal_assign_range(I first, I last, is_integer_tag<true> *) {
00847 internal_assign_n(static_cast<size_type>(first), &static_cast<T&>(last));
00848 }
00850 template<class I>
00851 void internal_assign_range(I first, I last, is_integer_tag<false> *) {
00852 internal_assign_iterators(first, last);
00853 }
00855 template<class I>
00856 void internal_assign_iterators(I first, I last);
00857
00859 static void __TBB_EXPORTED_FUNC initialize_array( void* begin, const void*, size_type n );
00860
00862 static void __TBB_EXPORTED_FUNC initialize_array_by( void* begin, const void* src, size_type n );
00863
00865 static void __TBB_EXPORTED_FUNC copy_array( void* dst, const void* src, size_type n );
00866
00868 static void __TBB_EXPORTED_FUNC assign_array( void* dst, const void* src, size_type n );
00869
00871 static void __TBB_EXPORTED_FUNC destroy_array( void* begin, size_type n );
00872
00874 class internal_loop_guide : internal::no_copy {
00875 public:
00876 const pointer array;
00877 const size_type n;
00878 size_type i;
00879 internal_loop_guide(size_type ntrials, void *ptr)
00880 : array(static_cast<pointer>(ptr)), n(ntrials), i(0) {}
00881 void init() { for(; i < n; ++i) new( &array[i] ) T(); }
00882 void init(const void *src) { for(; i < n; ++i) new( &array[i] ) T(*static_cast<const T*>(src)); }
00883 void copy(const void *src) { for(; i < n; ++i) new( &array[i] ) T(static_cast<const T*>(src)[i]); }
00884 void assign(const void *src) { for(; i < n; ++i) array[i] = static_cast<const T*>(src)[i]; }
00885 template<class I> void iterate(I &src) { for(; i < n; ++i, ++src) new( &array[i] ) T( *src ); }
00886 ~internal_loop_guide() {
00887 if(i < n)
00888 std::memset(array+i, 0, (n-i)*sizeof(value_type));
00889 }
00890 };
00891 };
00892
00893 template<typename T, class A>
00894 void concurrent_vector<T, A>::shrink_to_fit() {
00895 internal_segments_table old;
00896 __TBB_TRY {
00897 if( internal_compact( sizeof(T), &old, &destroy_array, ©_array ) )
00898 internal_free_segments( old.table, pointers_per_long_table, old.first_block );
00899 } __TBB_CATCH(...) {
00900 if( old.first_block )
00901 internal_free_segments( old.table, 1, old.first_block );
00902 __TBB_RETHROW();
00903 }
00904 }
00905
00906 template<typename T, class A>
00907 void concurrent_vector<T, A>::internal_free_segments(void *table[], segment_index_t k, segment_index_t first_block) {
00908
00909 while( k > first_block ) {
00910 --k;
00911 T* array = static_cast<T*>(table[k]);
00912 table[k] = NULL;
00913 if( array > internal::vector_allocation_error_flag )
00914 this->my_allocator.deallocate( array, segment_size(k) );
00915 }
00916 T* array = static_cast<T*>(table[0]);
00917 if( array > internal::vector_allocation_error_flag ) {
00918 __TBB_ASSERT( first_block > 0, NULL );
00919 while(k > 0) table[--k] = NULL;
00920 this->my_allocator.deallocate( array, segment_size(first_block) );
00921 }
00922 }
00923
00924 template<typename T, class A>
00925 T& concurrent_vector<T, A>::internal_subscript( size_type index ) const {
00926 __TBB_ASSERT( index < my_early_size, "index out of bounds" );
00927 size_type j = index;
00928 segment_index_t k = segment_base_index_of( j );
00929 __TBB_ASSERT( (segment_t*)my_segment != my_storage || k < pointers_per_short_table, "index is being allocated" );
00930
00931 #if TBB_USE_THREADING_TOOLS
00932 T* array = static_cast<T*>( tbb::internal::itt_load_pointer_v3(&my_segment[k].array));
00933 #else
00934 T* array = static_cast<T*>(my_segment[k].array);
00935 #endif
00936 __TBB_ASSERT( array != internal::vector_allocation_error_flag, "the instance is broken by bad allocation. Use at() instead" );
00937 __TBB_ASSERT( array, "index is being allocated" );
00938 return array[j];
00939 }
00940
00941 template<typename T, class A>
00942 T& concurrent_vector<T, A>::internal_subscript_with_exceptions( size_type index ) const {
00943 if( index >= my_early_size )
00944 internal::throw_exception(internal::eid_out_of_range);
00945 size_type j = index;
00946 segment_index_t k = segment_base_index_of( j );
00947 if( (segment_t*)my_segment == my_storage && k >= pointers_per_short_table )
00948 internal::throw_exception(internal::eid_segment_range_error);
00949 void *array = my_segment[k].array;
00950 if( array <= internal::vector_allocation_error_flag )
00951 internal::throw_exception(internal::eid_index_range_error);
00952 return static_cast<T*>(array)[j];
00953 }
00954
00955 template<typename T, class A> template<class I>
00956 void concurrent_vector<T, A>::internal_assign_iterators(I first, I last) {
00957 __TBB_ASSERT(my_early_size == 0, NULL);
00958 size_type n = std::distance(first, last);
00959 if( !n ) return;
00960 internal_reserve(n, sizeof(T), max_size());
00961 my_early_size = n;
00962 segment_index_t k = 0;
00963 size_type sz = segment_size( my_first_block );
00964 while( sz < n ) {
00965 internal_loop_guide loop(sz, my_segment[k].array);
00966 loop.iterate(first);
00967 n -= sz;
00968 if( !k ) k = my_first_block;
00969 else { ++k; sz <<= 1; }
00970 }
00971 internal_loop_guide loop(n, my_segment[k].array);
00972 loop.iterate(first);
00973 }
00974
00975 template<typename T, class A>
00976 void concurrent_vector<T, A>::initialize_array( void* begin, const void *, size_type n ) {
00977 internal_loop_guide loop(n, begin); loop.init();
00978 }
00979
00980 template<typename T, class A>
00981 void concurrent_vector<T, A>::initialize_array_by( void* begin, const void *src, size_type n ) {
00982 internal_loop_guide loop(n, begin); loop.init(src);
00983 }
00984
00985 template<typename T, class A>
00986 void concurrent_vector<T, A>::copy_array( void* dst, const void* src, size_type n ) {
00987 internal_loop_guide loop(n, dst); loop.copy(src);
00988 }
00989
00990 template<typename T, class A>
00991 void concurrent_vector<T, A>::assign_array( void* dst, const void* src, size_type n ) {
00992 internal_loop_guide loop(n, dst); loop.assign(src);
00993 }
00994
00995 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
00996
00997 #pragma warning (push)
00998 #pragma warning (disable: 4189)
00999 #endif
01000 template<typename T, class A>
01001 void concurrent_vector<T, A>::destroy_array( void* begin, size_type n ) {
01002 T* array = static_cast<T*>(begin);
01003 for( size_type j=n; j>0; --j )
01004 array[j-1].~T();
01005 }
01006 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
01007 #pragma warning (pop)
01008 #endif // warning 4189 is back
01009
01010
01011 template<typename T, class A1, class A2>
01012 inline bool operator==(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b) {
01013
01014 if(a.size() != b.size()) return false;
01015 typename concurrent_vector<T, A1>::const_iterator i(a.begin());
01016 typename concurrent_vector<T, A2>::const_iterator j(b.begin());
01017 for(; i != a.end(); ++i, ++j)
01018 if( !(*i == *j) ) return false;
01019 return true;
01020 }
01021
01022 template<typename T, class A1, class A2>
01023 inline bool operator!=(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
01024 { return !(a == b); }
01025
01026 template<typename T, class A1, class A2>
01027 inline bool operator<(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
01028 { return (std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end())); }
01029
01030 template<typename T, class A1, class A2>
01031 inline bool operator>(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
01032 { return b < a; }
01033
01034 template<typename T, class A1, class A2>
01035 inline bool operator<=(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
01036 { return !(b < a); }
01037
01038 template<typename T, class A1, class A2>
01039 inline bool operator>=(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
01040 { return !(a < b); }
01041
01042 template<typename T, class A>
01043 inline void swap(concurrent_vector<T, A> &a, concurrent_vector<T, A> &b)
01044 { a.swap( b ); }
01045
01046 }
01047
01048 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) && defined(_Wp64)
01049 #pragma warning (pop)
01050 #endif // warning 4267 is back
01051
01052 #endif