concurrent_vector.h

00001 /*
00002     Copyright 2005-2012 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 "tbb_profiling.h"
00031 #include <new>
00032 #include <cstring>   // for memset()
00033 
00034 #if !TBB_USE_EXCEPTIONS && _MSC_VER
00035     // Suppress "C++ exception handler used, but unwind semantics are not enabled" warning in STL headers
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     // VS2008/VC9 seems to have an issue; limits pull in math.h
00049     #pragma warning( push )
00050     #pragma warning( disable: 4985 )
00051 #endif
00052 #include <limits> /* std::numeric_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     // Workaround for overzealous compiler warnings in /Wp64 mode
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         // Basic types declarations
00080         typedef size_t segment_index_t;
00081         typedef size_t size_type;
00082 
00083         // Using enumerations due to Mac linking problems of static const variables
00084         enum {
00085             // Size constants
00086             default_initial_segments = 1, // 2 initial items
00088             pointers_per_short_table = 3, // to fit into 8 words of entire structure
00089             pointers_per_long_table = sizeof(segment_index_t) * 8 // one segment per bit
00090         };
00091 
00092         // Segment pointer. Can be zero-initialized
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 /* TBB_USE_ASSERT */
00100         };
00101 
00102         // Data fields
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         // Methods
00120 
00121         concurrent_vector_base_v3() {
00122             my_early_size = 0;
00123             my_first_block = 0; // here is not default_initial_segments
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; // fake value for k==0
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: // workaround for MSVC
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                 // Following test uses 2's-complement wizardry
00276                 if( (k& (k-2))==0 ) {
00277                     // k is a power of two that is at least k-2
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                 // Following test uses 2's-complement wizardry
00292                 if( (k& (k-2))==0 ) {
00293                     // k is a power of two that is at least k-2  
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         // STL support
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 } // namespace internal
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     // STL compatible types
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     // Assume ISO standard definition of std::reverse_iterator
00479     typedef std::reverse_iterator<iterator> reverse_iterator;
00480     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
00481 #else
00482     // Use non-standard std::reverse_iterator
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 /* defined(_MSC_VER) && (_MSC_VER<1300) */
00486 
00487     //------------------------------------------------------------------------
00488     // Parallel algorithm support
00489     //------------------------------------------------------------------------
00490     typedef generic_range_type<iterator> range_type;
00491     typedef generic_range_type<const_iterator> const_range_type;
00492 
00493     //------------------------------------------------------------------------
00494     // STL compatible constructors & destructors
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), &copy_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), &copy_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, &copy_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, &copy_array);
00588         return *this;
00589     }
00590 
00591     //------------------------------------------------------------------------
00592     // Concurrent operations
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     // 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 zeroing on the rest of items
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, &copy_array ) )
00902             internal_free_segments( old.table, pointers_per_long_table, old.first_block ); // free joined and unnecessary segments
00903     } __TBB_CATCH(...) {
00904         if( old.first_block ) // free segment allocated for compacting. Only for support of exceptions in ctor of user T[ype]
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     // Free the arrays
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 ) // check for correct segment pointer
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     // no need in __TBB_load_with_acquire since thread works in own space or gets 
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); // throw std::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); // throw std::range_error
00952     void *array = my_segment[k].array; // no need in __TBB_load_with_acquire
00953     if( array <= internal::vector_allocation_error_flag ) // check for correct segment pointer
00954         internal::throw_exception(internal::eid_index_range_error); // throw std::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     // Workaround for overzealous compiler warning
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(); // destructors are supposed to not throw any exceptions
01008 }
01009 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
01010     #pragma warning (pop)
01011 #endif // warning 4189 is back
01012 
01013 // concurrent_vector's template functions
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     // Simply:    return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
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 } // namespace tbb
01050 
01051 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) && defined(_Wp64)
01052     #pragma warning (pop)
01053 #endif // warning 4267 is back
01054 
01055 #endif /* __TBB_concurrent_vector_H */

Copyright © 2005-2012 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.