concurrent_vector.h

00001 /*
00002     Copyright 2005-2010 Intel Corporation.  All Rights Reserved.
00003 
00004     The source code contained or described herein and all documents related
00005     to the source code ("Material") are owned by Intel Corporation or its
00006     suppliers or licensors.  Title to the Material remains with Intel
00007     Corporation or its suppliers and licensors.  The Material is protected
00008     by worldwide copyright laws and treaty provisions.  No part of the
00009     Material may be used, copied, reproduced, modified, published, uploaded,
00010     posted, transmitted, distributed, or disclosed in any way without
00011     Intel's prior express written permission.
00012 
00013     No license under any patent, copyright, trade secret or other
00014     intellectual property right is granted to or conferred upon you by
00015     disclosure or delivery of the Materials, either expressly, by
00016     implication, inducement, estoppel or otherwise.  Any license under such
00017     intellectual property rights must be express and approved by Intel in
00018     writing.
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     // Suppress "C++ exception handler used, but unwind semantics are not enabled" warning in STL headers
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     // VS2008/VC9 seems to have an issue; limits pull in math.h
00047     #pragma warning( push )
00048     #pragma warning( disable: 4985 )
00049 #endif
00050 #include <limits> /* std::numeric_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     // Workaround for overzealous compiler warnings in /Wp64 mode
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         // Basic types declarations
00081         typedef size_t segment_index_t;
00082         typedef size_t size_type;
00083 
00084         // Using enumerations due to Mac linking problems of static const variables
00085         enum {
00086             // Size constants
00087             default_initial_segments = 1, // 2 initial items
00089             pointers_per_short_table = 3, // to fit into 8 words of entire structure
00090             pointers_per_long_table = sizeof(segment_index_t) * 8 // one segment per bit
00091         };
00092 
00093         // Segment pointer. Can be zero-initialized
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 /* TBB_USE_ASSERT */
00101         };
00102  
00103         // Data fields
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         // Methods
00121 
00122         concurrent_vector_base_v3() {
00123             my_early_size = 0;
00124             my_first_block = 0; // here is not default_initial_segments
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; // fake value for k==0
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: // workaround for MSVC
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                 // Following test uses 2's-complement wizardry
00277                 if( (k& (k-2))==0 ) {
00278                     // k is a power of two that is at least k-2
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                 // Following test uses 2's-complement wizardry
00293                 if( (k& (k-2))==0 ) {
00294                     // k is a power of two that is at least k-2  
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         // STL support
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 } // namespace internal
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     // STL compatible types
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     // Assume ISO standard definition of std::reverse_iterator
00480     typedef std::reverse_iterator<iterator> reverse_iterator;
00481     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00482 #else
00483     // Use non-standard std::reverse_iterator
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 /* defined(_MSC_VER) && (_MSC_VER<1300) */
00487 
00488     //------------------------------------------------------------------------
00489     // Parallel algorithm support
00490     //------------------------------------------------------------------------
00491     typedef generic_range_type<iterator> range_type;
00492     typedef generic_range_type<const_iterator> const_range_type;
00493 
00494     //------------------------------------------------------------------------
00495     // STL compatible constructors & destructors
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), &copy_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), &copy_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, &copy_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, &copy_array);
00589         return *this;
00590     }
00591 
00592     //------------------------------------------------------------------------
00593     // Concurrent operations
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     // Capacity
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 /* TBB_DEPRECATED */
00730 
00732     void shrink_to_fit();
00733 
00735     size_type max_size() const {return (~size_type(0))/sizeof(T);}
00736 
00737     //------------------------------------------------------------------------
00738     // STL support
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         // base class destructor call should be then
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) // if exception raised, do zerroing on the rest of items
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, &copy_array ) )
00898             internal_free_segments( old.table, pointers_per_long_table, old.first_block ); // free joined and unnecessary segments
00899     } __TBB_CATCH(...) {
00900         if( old.first_block ) // free segment allocated for compacting. Only for support of exceptions in ctor of user T[ype]
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     // Free the arrays
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 ) // check for correct segment pointer
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     // no need in __TBB_load_with_acquire since thread works in own space or gets 
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 /* TBB_USE_THREADING_TOOLS */
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); // throw std::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); // throw std::range_error
00949     void *array = my_segment[k].array; // no need in __TBB_load_with_acquire
00950     if( array <= internal::vector_allocation_error_flag ) // check for correct segment pointer
00951         internal::throw_exception(internal::eid_index_range_error); // throw std::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     // Workaround for overzealous compiler warning
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(); // destructors are supposed to not throw any exceptions
01005 }
01006 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) 
01007     #pragma warning (pop)
01008 #endif // warning 4189 is back 
01009 
01010 // concurrent_vector's template functions
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     // Simply:    return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
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 } // namespace tbb
01047 
01048 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) && defined(_Wp64)
01049     #pragma warning (pop)
01050 #endif // warning 4267 is back
01051 
01052 #endif /* __TBB_concurrent_vector_H */

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

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

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