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 "tbb_profiling.h"
00031 #include <new>
00032 #include <cstring>
00033
00034 #if !TBB_USE_EXCEPTIONS && _MSC_VER
00035
00036 #pragma warning (push)
00037 #pragma warning (disable: 4530)
00038 #endif
00039
00040 #include <algorithm>
00041 #include <iterator>
00042
00043 #if !TBB_USE_EXCEPTIONS && _MSC_VER
00044 #pragma warning (pop)
00045 #endif
00046
00047 #if _MSC_VER==1500 && !__INTEL_COMPILER
00048
00049 #pragma warning( push )
00050 #pragma warning( disable: 4985 )
00051 #endif
00052 #include <limits>
00053 #if _MSC_VER==1500 && !__INTEL_COMPILER
00054 #pragma warning( pop )
00055 #endif
00056
00057 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) && defined(_Wp64)
00058
00059 #pragma warning (push)
00060 #pragma warning (disable: 4267)
00061 #endif
00062
00063 namespace tbb {
00064
00065 template<typename T, class A = cache_aligned_allocator<T> >
00066 class concurrent_vector;
00067
00069 namespace internal {
00070
00072 static void *const vector_allocation_error_flag = reinterpret_cast<void*>(size_t(63));
00073
00075
00076 class concurrent_vector_base_v3 {
00077 protected:
00078
00079
00080 typedef size_t segment_index_t;
00081 typedef size_t size_type;
00082
00083
00084 enum {
00085
00086 default_initial_segments = 1,
00088 pointers_per_short_table = 3,
00089 pointers_per_long_table = sizeof(segment_index_t) * 8
00090 };
00091
00092
00093 struct segment_t {
00094 void* array;
00095 #if TBB_USE_ASSERT
00096 ~segment_t() {
00097 __TBB_ASSERT( array <= internal::vector_allocation_error_flag, "should have been freed by clear" );
00098 }
00099 #endif
00100 };
00101
00102
00103
00105 void* (*vector_allocator_ptr)(concurrent_vector_base_v3 &, size_t);
00106
00108 atomic<size_type> my_first_block;
00109
00111 atomic<size_type> my_early_size;
00112
00114 atomic<segment_t*> my_segment;
00115
00117 segment_t my_storage[pointers_per_short_table];
00118
00119
00120
00121 concurrent_vector_base_v3() {
00122 my_early_size = 0;
00123 my_first_block = 0;
00124 for( segment_index_t i = 0; i < pointers_per_short_table; i++)
00125 my_storage[i].array = NULL;
00126 my_segment = my_storage;
00127 }
00128 __TBB_EXPORTED_METHOD ~concurrent_vector_base_v3();
00129
00130 static segment_index_t segment_index_of( size_type index ) {
00131 return segment_index_t( __TBB_Log2( index|1 ) );
00132 }
00133
00134 static segment_index_t segment_base( segment_index_t k ) {
00135 return (segment_index_t(1)<<k & ~segment_index_t(1));
00136 }
00137
00138 static inline segment_index_t segment_base_index_of( segment_index_t &index ) {
00139 segment_index_t k = segment_index_of( index );
00140 index -= segment_base(k);
00141 return k;
00142 }
00143
00144 static size_type segment_size( segment_index_t k ) {
00145 return segment_index_t(1)<<k;
00146 }
00147
00149 typedef void (__TBB_EXPORTED_FUNC *internal_array_op1)(void* begin, size_type n );
00150
00152 typedef void (__TBB_EXPORTED_FUNC *internal_array_op2)(void* dst, const void* src, size_type n );
00153
00155 struct internal_segments_table {
00156 segment_index_t first_block;
00157 void* table[pointers_per_long_table];
00158 };
00159
00160 void __TBB_EXPORTED_METHOD internal_reserve( size_type n, size_type element_size, size_type max_size );
00161 size_type __TBB_EXPORTED_METHOD internal_capacity() const;
00162 void internal_grow( size_type start, size_type finish, size_type element_size, internal_array_op2 init, const void *src );
00163 size_type __TBB_EXPORTED_METHOD internal_grow_by( size_type delta, size_type element_size, internal_array_op2 init, const void *src );
00164 void* __TBB_EXPORTED_METHOD internal_push_back( size_type element_size, size_type& index );
00165 segment_index_t __TBB_EXPORTED_METHOD internal_clear( internal_array_op1 destroy );
00166 void* __TBB_EXPORTED_METHOD internal_compact( size_type element_size, void *table, internal_array_op1 destroy, internal_array_op2 copy );
00167 void __TBB_EXPORTED_METHOD internal_copy( const concurrent_vector_base_v3& src, size_type element_size, internal_array_op2 copy );
00168 void __TBB_EXPORTED_METHOD internal_assign( const concurrent_vector_base_v3& src, size_type element_size,
00169 internal_array_op1 destroy, internal_array_op2 assign, internal_array_op2 copy );
00171 void __TBB_EXPORTED_METHOD internal_throw_exception(size_type) const;
00172 void __TBB_EXPORTED_METHOD internal_swap(concurrent_vector_base_v3& v);
00173
00174 void __TBB_EXPORTED_METHOD internal_resize( size_type n, size_type element_size, size_type max_size, const void *src,
00175 internal_array_op1 destroy, internal_array_op2 init );
00176 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 );
00177
00179 void __TBB_EXPORTED_METHOD internal_grow_to_at_least( size_type new_size, size_type element_size, internal_array_op2 init, const void *src );
00180 private:
00182 class helper;
00183 friend class helper;
00184 };
00185
00186 typedef concurrent_vector_base_v3 concurrent_vector_base;
00187
00189
00191 template<typename Container, typename Value>
00192 class vector_iterator
00193 {
00195 Container* my_vector;
00196
00198 size_t my_index;
00199
00201
00202 mutable Value* my_item;
00203
00204 template<typename C, typename T>
00205 friend vector_iterator<C,T> operator+( ptrdiff_t offset, const vector_iterator<C,T>& v );
00206
00207 template<typename C, typename T, typename U>
00208 friend bool operator==( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
00209
00210 template<typename C, typename T, typename U>
00211 friend bool operator<( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
00212
00213 template<typename C, typename T, typename U>
00214 friend ptrdiff_t operator-( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
00215
00216 template<typename C, typename U>
00217 friend class internal::vector_iterator;
00218
00219 #if !defined(_MSC_VER) || defined(__INTEL_COMPILER)
00220 template<typename T, class A>
00221 friend class tbb::concurrent_vector;
00222 #else
00223 public:
00224 #endif
00225
00226 vector_iterator( const Container& vector, size_t index, void *ptr = 0 ) :
00227 my_vector(const_cast<Container*>(&vector)),
00228 my_index(index),
00229 my_item(static_cast<Value*>(ptr))
00230 {}
00231
00232 public:
00234 vector_iterator() : my_vector(NULL), my_index(~size_t(0)), my_item(NULL) {}
00235
00236 vector_iterator( const vector_iterator<Container,typename Container::value_type>& other ) :
00237 my_vector(other.my_vector),
00238 my_index(other.my_index),
00239 my_item(other.my_item)
00240 {}
00241
00242 vector_iterator operator+( ptrdiff_t offset ) const {
00243 return vector_iterator( *my_vector, my_index+offset );
00244 }
00245 vector_iterator &operator+=( ptrdiff_t offset ) {
00246 my_index+=offset;
00247 my_item = NULL;
00248 return *this;
00249 }
00250 vector_iterator operator-( ptrdiff_t offset ) const {
00251 return vector_iterator( *my_vector, my_index-offset );
00252 }
00253 vector_iterator &operator-=( ptrdiff_t offset ) {
00254 my_index-=offset;
00255 my_item = NULL;
00256 return *this;
00257 }
00258 Value& operator*() const {
00259 Value* item = my_item;
00260 if( !item ) {
00261 item = my_item = &my_vector->internal_subscript(my_index);
00262 }
00263 __TBB_ASSERT( item==&my_vector->internal_subscript(my_index), "corrupt cache" );
00264 return *item;
00265 }
00266 Value& operator[]( ptrdiff_t k ) const {
00267 return my_vector->internal_subscript(my_index+k);
00268 }
00269 Value* operator->() const {return &operator*();}
00270
00272 vector_iterator& operator++() {
00273 size_t k = ++my_index;
00274 if( my_item ) {
00275
00276 if( (k& (k-2))==0 ) {
00277
00278 my_item= NULL;
00279 } else {
00280 ++my_item;
00281 }
00282 }
00283 return *this;
00284 }
00285
00287 vector_iterator& operator--() {
00288 __TBB_ASSERT( my_index>0, "operator--() applied to iterator already at beginning of concurrent_vector" );
00289 size_t k = my_index--;
00290 if( my_item ) {
00291
00292 if( (k& (k-2))==0 ) {
00293
00294 my_item= NULL;
00295 } else {
00296 --my_item;
00297 }
00298 }
00299 return *this;
00300 }
00301
00303 vector_iterator operator++(int) {
00304 vector_iterator result = *this;
00305 operator++();
00306 return result;
00307 }
00308
00310 vector_iterator operator--(int) {
00311 vector_iterator result = *this;
00312 operator--();
00313 return result;
00314 }
00315
00316
00317
00318 typedef ptrdiff_t difference_type;
00319 typedef Value value_type;
00320 typedef Value* pointer;
00321 typedef Value& reference;
00322 typedef std::random_access_iterator_tag iterator_category;
00323 };
00324
00325 template<typename Container, typename T>
00326 vector_iterator<Container,T> operator+( ptrdiff_t offset, const vector_iterator<Container,T>& v ) {
00327 return vector_iterator<Container,T>( *v.my_vector, v.my_index+offset );
00328 }
00329
00330 template<typename Container, typename T, typename U>
00331 bool operator==( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00332 return i.my_index==j.my_index && i.my_vector == j.my_vector;
00333 }
00334
00335 template<typename Container, typename T, typename U>
00336 bool operator!=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00337 return !(i==j);
00338 }
00339
00340 template<typename Container, typename T, typename U>
00341 bool operator<( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00342 return i.my_index<j.my_index;
00343 }
00344
00345 template<typename Container, typename T, typename U>
00346 bool operator>( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00347 return j<i;
00348 }
00349
00350 template<typename Container, typename T, typename U>
00351 bool operator>=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00352 return !(i<j);
00353 }
00354
00355 template<typename Container, typename T, typename U>
00356 bool operator<=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00357 return !(j<i);
00358 }
00359
00360 template<typename Container, typename T, typename U>
00361 ptrdiff_t operator-( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
00362 return ptrdiff_t(i.my_index)-ptrdiff_t(j.my_index);
00363 }
00364
00365 template<typename T, class A>
00366 class allocator_base {
00367 public:
00368 typedef typename A::template
00369 rebind<T>::other allocator_type;
00370 allocator_type my_allocator;
00371
00372 allocator_base(const allocator_type &a = allocator_type() ) : my_allocator(a) {}
00373 };
00374
00375 }
00377
00379
00440 template<typename T, class A>
00441 class concurrent_vector: protected internal::allocator_base<T, A>,
00442 private internal::concurrent_vector_base {
00443 private:
00444 template<typename I>
00445 class generic_range_type: public blocked_range<I> {
00446 public:
00447 typedef T value_type;
00448 typedef T& reference;
00449 typedef const T& const_reference;
00450 typedef I iterator;
00451 typedef ptrdiff_t difference_type;
00452 generic_range_type( I begin_, I end_, size_t grainsize_ = 1) : blocked_range<I>(begin_,end_,grainsize_) {}
00453 template<typename U>
00454 generic_range_type( const generic_range_type<U>& r) : blocked_range<I>(r.begin(),r.end(),r.grainsize()) {}
00455 generic_range_type( generic_range_type& r, split ) : blocked_range<I>(r,split()) {}
00456 };
00457
00458 template<typename C, typename U>
00459 friend class internal::vector_iterator;
00460 public:
00461
00462
00463
00464 typedef internal::concurrent_vector_base_v3::size_type size_type;
00465 typedef typename internal::allocator_base<T, A>::allocator_type allocator_type;
00466
00467 typedef T value_type;
00468 typedef ptrdiff_t difference_type;
00469 typedef T& reference;
00470 typedef const T& const_reference;
00471 typedef T *pointer;
00472 typedef const T *const_pointer;
00473
00474 typedef internal::vector_iterator<concurrent_vector,T> iterator;
00475 typedef internal::vector_iterator<concurrent_vector,const T> const_iterator;
00476
00477 #if !defined(_MSC_VER) || _CPPLIB_VER>=300
00478
00479 typedef std::reverse_iterator<iterator> reverse_iterator;
00480 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00481 #else
00482
00483 typedef std::reverse_iterator<iterator,T,T&,T*> reverse_iterator;
00484 typedef std::reverse_iterator<const_iterator,T,const T&,const T*> const_reverse_iterator;
00485 #endif
00486
00487
00488
00489
00490 typedef generic_range_type<iterator> range_type;
00491 typedef generic_range_type<const_iterator> const_range_type;
00492
00493
00494
00495
00496
00498 explicit concurrent_vector(const allocator_type &a = allocator_type())
00499 : internal::allocator_base<T, A>(a), internal::concurrent_vector_base()
00500 {
00501 vector_allocator_ptr = &internal_allocator;
00502 }
00503
00505 concurrent_vector( const concurrent_vector& vector, const allocator_type& a = allocator_type() )
00506 : internal::allocator_base<T, A>(a), internal::concurrent_vector_base()
00507 {
00508 vector_allocator_ptr = &internal_allocator;
00509 __TBB_TRY {
00510 internal_copy(vector, sizeof(T), ©_array);
00511 } __TBB_CATCH(...) {
00512 segment_t *table = my_segment;
00513 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00514 __TBB_RETHROW();
00515 }
00516 }
00517
00519 template<class M>
00520 concurrent_vector( const concurrent_vector<T, M>& vector, const allocator_type& a = allocator_type() )
00521 : internal::allocator_base<T, A>(a), internal::concurrent_vector_base()
00522 {
00523 vector_allocator_ptr = &internal_allocator;
00524 __TBB_TRY {
00525 internal_copy(vector.internal_vector_base(), sizeof(T), ©_array);
00526 } __TBB_CATCH(...) {
00527 segment_t *table = my_segment;
00528 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00529 __TBB_RETHROW();
00530 }
00531 }
00532
00534 explicit concurrent_vector(size_type n)
00535 {
00536 vector_allocator_ptr = &internal_allocator;
00537 __TBB_TRY {
00538 internal_resize( n, sizeof(T), max_size(), NULL, &destroy_array, &initialize_array );
00539 } __TBB_CATCH(...) {
00540 segment_t *table = my_segment;
00541 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00542 __TBB_RETHROW();
00543 }
00544 }
00545
00547 concurrent_vector(size_type n, const_reference t, const allocator_type& a = allocator_type())
00548 : internal::allocator_base<T, A>(a)
00549 {
00550 vector_allocator_ptr = &internal_allocator;
00551 __TBB_TRY {
00552 internal_resize( n, sizeof(T), max_size(), static_cast<const void*>(&t), &destroy_array, &initialize_array_by );
00553 } __TBB_CATCH(...) {
00554 segment_t *table = my_segment;
00555 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00556 __TBB_RETHROW();
00557 }
00558 }
00559
00561 template<class I>
00562 concurrent_vector(I first, I last, const allocator_type &a = allocator_type())
00563 : internal::allocator_base<T, A>(a)
00564 {
00565 vector_allocator_ptr = &internal_allocator;
00566 __TBB_TRY {
00567 internal_assign_range(first, last, static_cast<is_integer_tag<std::numeric_limits<I>::is_integer> *>(0) );
00568 } __TBB_CATCH(...) {
00569 segment_t *table = my_segment;
00570 internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
00571 __TBB_RETHROW();
00572 }
00573 }
00574
00576 concurrent_vector& operator=( const concurrent_vector& vector ) {
00577 if( this != &vector )
00578 internal_assign(vector, sizeof(T), &destroy_array, &assign_array, ©_array);
00579 return *this;
00580 }
00581
00583 template<class M>
00584 concurrent_vector& operator=( const concurrent_vector<T, M>& vector ) {
00585 if( static_cast<void*>( this ) != static_cast<const void*>( &vector ) )
00586 internal_assign(vector.internal_vector_base(),
00587 sizeof(T), &destroy_array, &assign_array, ©_array);
00588 return *this;
00589 }
00590
00591
00592
00593
00595 #if TBB_DEPRECATED
00596
00597 size_type grow_by( size_type delta ) {
00598 return delta ? internal_grow_by( delta, sizeof(T), &initialize_array, NULL ) : my_early_size;
00599 }
00600 #else
00601
00602 iterator grow_by( size_type delta ) {
00603 return iterator(*this, delta ? internal_grow_by( delta, sizeof(T), &initialize_array, NULL ) : my_early_size);
00604 }
00605 #endif
00606
00608 #if TBB_DEPRECATED
00609
00610 size_type grow_by( size_type delta, const_reference t ) {
00611 return delta ? internal_grow_by( delta, sizeof(T), &initialize_array_by, static_cast<const void*>(&t) ) : my_early_size;
00612 }
00613 #else
00614
00615 iterator grow_by( size_type delta, const_reference t ) {
00616 return iterator(*this, delta ? internal_grow_by( delta, sizeof(T), &initialize_array_by, static_cast<const void*>(&t) ) : my_early_size);
00617 }
00618 #endif
00619
00621 #if TBB_DEPRECATED
00622
00624 void grow_to_at_least( size_type n ) {
00625 if( n ) internal_grow_to_at_least_with_result( n, sizeof(T), &initialize_array, NULL );
00626 };
00627 #else
00628
00632 iterator grow_to_at_least( size_type n ) {
00633 size_type m=0;
00634 if( n ) {
00635 m = internal_grow_to_at_least_with_result( n, sizeof(T), &initialize_array, NULL );
00636 if( m>n ) m=n;
00637 }
00638 return iterator(*this, m);
00639 };
00640 #endif
00641
00643 #if TBB_DEPRECATED
00644 size_type push_back( const_reference item )
00645 #else
00646
00647 iterator push_back( const_reference item )
00648 #endif
00649 {
00650 size_type k;
00651 void *ptr = internal_push_back(sizeof(T),k);
00652 internal_loop_guide loop(1, ptr);
00653 loop.init(&item);
00654 #if TBB_DEPRECATED
00655 return k;
00656 #else
00657 return iterator(*this, k, ptr);
00658 #endif
00659 }
00660
00662
00664 reference operator[]( size_type index ) {
00665 return internal_subscript(index);
00666 }
00667
00669 const_reference operator[]( size_type index ) const {
00670 return internal_subscript(index);
00671 }
00672
00674 reference at( size_type index ) {
00675 return internal_subscript_with_exceptions(index);
00676 }
00677
00679 const_reference at( size_type index ) const {
00680 return internal_subscript_with_exceptions(index);
00681 }
00682
00684 range_type range( size_t grainsize = 1 ) {
00685 return range_type( begin(), end(), grainsize );
00686 }
00687
00689 const_range_type range( size_t grainsize = 1 ) const {
00690 return const_range_type( begin(), end(), grainsize );
00691 }
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 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
00894 #pragma warning (push)
00895 #pragma warning (disable: 4701) // potentially uninitialized local variable "old"
00896 #endif
00897 template<typename T, class A>
00898 void concurrent_vector<T, A>::shrink_to_fit() {
00899 internal_segments_table old;
00900 __TBB_TRY {
00901 if( internal_compact( sizeof(T), &old, &destroy_array, ©_array ) )
00902 internal_free_segments( old.table, pointers_per_long_table, old.first_block );
00903 } __TBB_CATCH(...) {
00904 if( old.first_block )
00905 internal_free_segments( old.table, 1, old.first_block );
00906 __TBB_RETHROW();
00907 }
00908 }
00909 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
00910 #pragma warning (pop)
00911 #endif // warning 4701 is back
00912
00913 template<typename T, class A>
00914 void concurrent_vector<T, A>::internal_free_segments(void *table[], segment_index_t k, segment_index_t first_block) {
00915
00916 while( k > first_block ) {
00917 --k;
00918 T* array = static_cast<T*>(table[k]);
00919 table[k] = NULL;
00920 if( array > internal::vector_allocation_error_flag )
00921 this->my_allocator.deallocate( array, segment_size(k) );
00922 }
00923 T* array = static_cast<T*>(table[0]);
00924 if( array > internal::vector_allocation_error_flag ) {
00925 __TBB_ASSERT( first_block > 0, NULL );
00926 while(k > 0) table[--k] = NULL;
00927 this->my_allocator.deallocate( array, segment_size(first_block) );
00928 }
00929 }
00930
00931 template<typename T, class A>
00932 T& concurrent_vector<T, A>::internal_subscript( size_type index ) const {
00933 __TBB_ASSERT( index < my_early_size, "index out of bounds" );
00934 size_type j = index;
00935 segment_index_t k = segment_base_index_of( j );
00936 __TBB_ASSERT( (segment_t*)my_segment != my_storage || k < pointers_per_short_table, "index is being allocated" );
00937
00938 T* array = static_cast<T*>( tbb::internal::itt_hide_load_word(my_segment[k].array));
00939 __TBB_ASSERT( array != internal::vector_allocation_error_flag, "the instance is broken by bad allocation. Use at() instead" );
00940 __TBB_ASSERT( array, "index is being allocated" );
00941 return array[j];
00942 }
00943
00944 template<typename T, class A>
00945 T& concurrent_vector<T, A>::internal_subscript_with_exceptions( size_type index ) const {
00946 if( index >= my_early_size )
00947 internal::throw_exception(internal::eid_out_of_range);
00948 size_type j = index;
00949 segment_index_t k = segment_base_index_of( j );
00950 if( (segment_t*)my_segment == my_storage && k >= pointers_per_short_table )
00951 internal::throw_exception(internal::eid_segment_range_error);
00952 void *array = my_segment[k].array;
00953 if( array <= internal::vector_allocation_error_flag )
00954 internal::throw_exception(internal::eid_index_range_error);
00955 return static_cast<T*>(array)[j];
00956 }
00957
00958 template<typename T, class A> template<class I>
00959 void concurrent_vector<T, A>::internal_assign_iterators(I first, I last) {
00960 __TBB_ASSERT(my_early_size == 0, NULL);
00961 size_type n = std::distance(first, last);
00962 if( !n ) return;
00963 internal_reserve(n, sizeof(T), max_size());
00964 my_early_size = n;
00965 segment_index_t k = 0;
00966 size_type sz = segment_size( my_first_block );
00967 while( sz < n ) {
00968 internal_loop_guide loop(sz, my_segment[k].array);
00969 loop.iterate(first);
00970 n -= sz;
00971 if( !k ) k = my_first_block;
00972 else { ++k; sz <<= 1; }
00973 }
00974 internal_loop_guide loop(n, my_segment[k].array);
00975 loop.iterate(first);
00976 }
00977
00978 template<typename T, class A>
00979 void concurrent_vector<T, A>::initialize_array( void* begin, const void *, size_type n ) {
00980 internal_loop_guide loop(n, begin); loop.init();
00981 }
00982
00983 template<typename T, class A>
00984 void concurrent_vector<T, A>::initialize_array_by( void* begin, const void *src, size_type n ) {
00985 internal_loop_guide loop(n, begin); loop.init(src);
00986 }
00987
00988 template<typename T, class A>
00989 void concurrent_vector<T, A>::copy_array( void* dst, const void* src, size_type n ) {
00990 internal_loop_guide loop(n, dst); loop.copy(src);
00991 }
00992
00993 template<typename T, class A>
00994 void concurrent_vector<T, A>::assign_array( void* dst, const void* src, size_type n ) {
00995 internal_loop_guide loop(n, dst); loop.assign(src);
00996 }
00997
00998 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
00999
01000 #pragma warning (push)
01001 #pragma warning (disable: 4189)
01002 #endif
01003 template<typename T, class A>
01004 void concurrent_vector<T, A>::destroy_array( void* begin, size_type n ) {
01005 T* array = static_cast<T*>(begin);
01006 for( size_type j=n; j>0; --j )
01007 array[j-1].~T();
01008 }
01009 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
01010 #pragma warning (pop)
01011 #endif // warning 4189 is back
01012
01013
01014 template<typename T, class A1, class A2>
01015 inline bool operator==(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b) {
01016
01017 if(a.size() != b.size()) return false;
01018 typename concurrent_vector<T, A1>::const_iterator i(a.begin());
01019 typename concurrent_vector<T, A2>::const_iterator j(b.begin());
01020 for(; i != a.end(); ++i, ++j)
01021 if( !(*i == *j) ) return false;
01022 return true;
01023 }
01024
01025 template<typename T, class A1, class A2>
01026 inline bool operator!=(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
01027 { return !(a == b); }
01028
01029 template<typename T, class A1, class A2>
01030 inline bool operator<(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
01031 { return (std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end())); }
01032
01033 template<typename T, class A1, class A2>
01034 inline bool operator>(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
01035 { return b < a; }
01036
01037 template<typename T, class A1, class A2>
01038 inline bool operator<=(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
01039 { return !(b < a); }
01040
01041 template<typename T, class A1, class A2>
01042 inline bool operator>=(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
01043 { return !(a < b); }
01044
01045 template<typename T, class A>
01046 inline void swap(concurrent_vector<T, A> &a, concurrent_vector<T, A> &b)
01047 { a.swap( b ); }
01048
01049 }
01050
01051 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) && defined(_Wp64)
01052 #pragma warning (pop)
01053 #endif // warning 4267 is back
01054
01055 #endif