git.sesse.net Git - casparcg/blob - tbb/include/tbb/concurrent_vector.h

   1 /*
   2     Copyright 2005-2011 Intel Corporation.  All Rights Reserved.
   3
   4     This file is part of Threading Building Blocks.
   5
   6     Threading Building Blocks is free software; you can redistribute it
   7     and/or modify it under the terms of the GNU General Public License
   8     version 2 as published by the Free Software Foundation.
   9
  10     Threading Building Blocks is distributed in the hope that it will be
  11     useful, but WITHOUT ANY WARRANTY; without even the implied warranty
  12     of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License
  16     along with Threading Building Blocks; if not, write to the Free Software
  17     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  18
  19     As a special exception, you may use this file as part of a free software
  20     library without restriction.  Specifically, if other files instantiate
  21     templates or use macros or inline functions from this file, or you compile
  22     this file and link it with other files to produce an executable, this
  23     file does not by itself cause the resulting executable to be covered by
  24     the GNU General Public License.  This exception does not however
  25     invalidate any other reasons why the executable file might be covered by
  26     the GNU General Public License.
  27 */
  28
  29 #ifndef __TBB_concurrent_vector_H
  30 #define __TBB_concurrent_vector_H
  31
  32 #include "tbb_stddef.h"
  33 #include "tbb_exception.h"
  34 #include "atomic.h"
  35 #include "cache_aligned_allocator.h"
  36 #include "blocked_range.h"
  37 #include "tbb_machine.h"
  38 #include "tbb_profiling.h"
  39 #include <new>
  40 #include <cstring>   // for memset()
  41
  42 #if !TBB_USE_EXCEPTIONS && _MSC_VER
  43     // Suppress "C++ exception handler used, but unwind semantics are not enabled" warning in STL headers
  44     #pragma warning (push)
  45     #pragma warning (disable: 4530)
  46 #endif
  47
  48 #include <algorithm>
  49 #include <iterator>
  50
  51 #if !TBB_USE_EXCEPTIONS && _MSC_VER
  52     #pragma warning (pop)
  53 #endif
  54
  55 #if _MSC_VER==1500 && !__INTEL_COMPILER
  56     // VS2008/VC9 seems to have an issue; limits pull in math.h
  57     #pragma warning( push )
  58     #pragma warning( disable: 4985 )
  59 #endif
  60 #include <limits> /* std::numeric_limits */
  61 #if _MSC_VER==1500 && !__INTEL_COMPILER
  62     #pragma warning( pop )
  63 #endif
  64
  65 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) && defined(_Wp64)
  66     // Workaround for overzealous compiler warnings in /Wp64 mode
  67     #pragma warning (push)
  68     #pragma warning (disable: 4267)
  69 #endif
  70
  71 namespace tbb {
  72
  73 template<typename T, class A = cache_aligned_allocator<T> >
  74 class concurrent_vector;
  75
  76 //! @cond INTERNAL
  77 namespace internal {
  78
  79     //! Bad allocation marker
  80     static void *const vector_allocation_error_flag = reinterpret_cast<void*>(size_t(63));
  81
  82     //! Base class of concurrent vector implementation.
  83     /** @ingroup containers */
  84     class concurrent_vector_base_v3 {
  85     protected:
  86
  87         // Basic types declarations
  88         typedef size_t segment_index_t;
  89         typedef size_t size_type;
  90
  91         // Using enumerations due to Mac linking problems of static const variables
  92         enum {
  93             // Size constants
  94             default_initial_segments = 1, // 2 initial items
  95             //! Number of slots for segment's pointers inside the class
  96             pointers_per_short_table = 3, // to fit into 8 words of entire structure
  97             pointers_per_long_table = sizeof(segment_index_t) * 8 // one segment per bit
  98         };
  99
 100         // Segment pointer. Can be zero-initialized
 101         struct segment_t {
 102             void* array;
 103 #if TBB_USE_ASSERT
 104             ~segment_t() {
 105                 __TBB_ASSERT( array <= internal::vector_allocation_error_flag, "should have been freed by clear" );
 106             }
 107 #endif /* TBB_USE_ASSERT */
 108         };
 109
 110         // Data fields
 111
 112         //! allocator function pointer
 113         void* (*vector_allocator_ptr)(concurrent_vector_base_v3 &, size_t);
 114
 115         //! count of segments in the first block
 116         atomic<size_type> my_first_block;
 117
 118         //! Requested size of vector
 119         atomic<size_type> my_early_size;
 120
 121         //! Pointer to the segments table
 122         atomic<segment_t*> my_segment;
 123
 124         //! embedded storage of segment pointers
 125         segment_t my_storage[pointers_per_short_table];
 126
 127         // Methods
 128
 129         concurrent_vector_base_v3() {
 130             my_early_size = 0;
 131             my_first_block = 0; // here is not default_initial_segments
 132             for( segment_index_t i = 0; i < pointers_per_short_table; i++)
 133                 my_storage[i].array = NULL;
 134             my_segment = my_storage;
 135         }
 136         __TBB_EXPORTED_METHOD ~concurrent_vector_base_v3();
 137
 138         static segment_index_t segment_index_of( size_type index ) {
 139             return segment_index_t( __TBB_Log2( index|1 ) );
 140         }
 141
 142         static segment_index_t segment_base( segment_index_t k ) {
 143             return (segment_index_t(1)<<k & ~segment_index_t(1));
 144         }
 145
 146         static inline segment_index_t segment_base_index_of( segment_index_t &index ) {
 147             segment_index_t k = segment_index_of( index );
 148             index -= segment_base(k);
 149             return k;
 150         }
 151
 152         static size_type segment_size( segment_index_t k ) {
 153             return segment_index_t(1)<<k; // fake value for k==0
 154         }
 155
 156         //! An operation on an n-element array starting at begin.
 157         typedef void (__TBB_EXPORTED_FUNC *internal_array_op1)(void* begin, size_type n );
 158
 159         //! An operation on n-element destination array and n-element source array.
 160         typedef void (__TBB_EXPORTED_FUNC *internal_array_op2)(void* dst, const void* src, size_type n );
 161
 162         //! Internal structure for compact()
 163         struct internal_segments_table {
 164             segment_index_t first_block;
 165             void* table[pointers_per_long_table];
 166         };
 167
 168         void __TBB_EXPORTED_METHOD internal_reserve( size_type n, size_type element_size, size_type max_size );
 169         size_type __TBB_EXPORTED_METHOD internal_capacity() const;
 170         void internal_grow( size_type start, size_type finish, size_type element_size, internal_array_op2 init, const void *src );
 171         size_type __TBB_EXPORTED_METHOD internal_grow_by( size_type delta, size_type element_size, internal_array_op2 init, const void *src );
 172         void* __TBB_EXPORTED_METHOD internal_push_back( size_type element_size, size_type& index );
 173         segment_index_t __TBB_EXPORTED_METHOD internal_clear( internal_array_op1 destroy );
 174         void* __TBB_EXPORTED_METHOD internal_compact( size_type element_size, void *table, internal_array_op1 destroy, internal_array_op2 copy );
 175         void __TBB_EXPORTED_METHOD internal_copy( const concurrent_vector_base_v3& src, size_type element_size, internal_array_op2 copy );
 176         void __TBB_EXPORTED_METHOD internal_assign( const concurrent_vector_base_v3& src, size_type element_size,
 177                               internal_array_op1 destroy, internal_array_op2 assign, internal_array_op2 copy );
 178         //! Obsolete
 179         void __TBB_EXPORTED_METHOD internal_throw_exception(size_type) const;
 180         void __TBB_EXPORTED_METHOD internal_swap(concurrent_vector_base_v3& v);
 181
 182         void __TBB_EXPORTED_METHOD internal_resize( size_type n, size_type element_size, size_type max_size, const void *src,
 183                                                     internal_array_op1 destroy, internal_array_op2 init );
 184         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 );
 185
 186         //! Deprecated entry point for backwards compatibility to TBB 2.1.
 187         void __TBB_EXPORTED_METHOD internal_grow_to_at_least( size_type new_size, size_type element_size, internal_array_op2 init, const void *src );
 188 private:
 189         //! Private functionality
 190         class helper;
 191         friend class helper;
 192     };
 193
 194     typedef concurrent_vector_base_v3 concurrent_vector_base;
 195
 196     //! Meets requirements of a forward iterator for STL and a Value for a blocked_range.*/
 197     /** Value is either the T or const T type of the container.
 198         @ingroup containers */
 199     template<typename Container, typename Value>
 200     class vector_iterator
 201     {
 202         //! concurrent_vector over which we are iterating.
 203         Container* my_vector;
 204
 205         //! Index into the vector
 206         size_t my_index;
 207
 208         //! Caches my_vector-&gt;internal_subscript(my_index)
 209         /** NULL if cached value is not available */
 210         mutable Value* my_item;
 211
 212         template<typename C, typename T>
 213         friend vector_iterator<C,T> operator+( ptrdiff_t offset, const vector_iterator<C,T>& v );
 214
 215         template<typename C, typename T, typename U>
 216         friend bool operator==( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
 217
 218         template<typename C, typename T, typename U>
 219         friend bool operator<( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
 220
 221         template<typename C, typename T, typename U>
 222         friend ptrdiff_t operator-( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
 223
 224         template<typename C, typename U>
 225         friend class internal::vector_iterator;
 226
 227 #if !defined(_MSC_VER) || defined(__INTEL_COMPILER)
 228         template<typename T, class A>
 229         friend class tbb::concurrent_vector;
 230 #else
 231 public: // workaround for MSVC
 232 #endif
 233
 234         vector_iterator( const Container& vector, size_t index, void *ptr = 0 ) :
 235             my_vector(const_cast<Container*>(&vector)),
 236             my_index(index),
 237             my_item(static_cast<Value*>(ptr))
 238         {}
 239
 240     public:
 241         //! Default constructor
 242         vector_iterator() : my_vector(NULL), my_index(~size_t(0)), my_item(NULL) {}
 243
 244         vector_iterator( const vector_iterator<Container,typename Container::value_type>& other ) :
 245             my_vector(other.my_vector),
 246             my_index(other.my_index),
 247             my_item(other.my_item)
 248         {}
 249
 250         vector_iterator operator+( ptrdiff_t offset ) const {
 251             return vector_iterator( *my_vector, my_index+offset );
 252         }
 253         vector_iterator &operator+=( ptrdiff_t offset ) {
 254             my_index+=offset;
 255             my_item = NULL;
 256             return *this;
 257         }
 258         vector_iterator operator-( ptrdiff_t offset ) const {
 259             return vector_iterator( *my_vector, my_index-offset );
 260         }
 261         vector_iterator &operator-=( ptrdiff_t offset ) {
 262             my_index-=offset;
 263             my_item = NULL;
 264             return *this;
 265         }
 266         Value& operator*() const {
 267             Value* item = my_item;
 268             if( !item ) {
 269                 item = my_item = &my_vector->internal_subscript(my_index);
 270             }
 271             __TBB_ASSERT( item==&my_vector->internal_subscript(my_index), "corrupt cache" );
 272             return *item;
 273         }
 274         Value& operator[]( ptrdiff_t k ) const {
 275             return my_vector->internal_subscript(my_index+k);
 276         }
 277         Value* operator->() const {return &operator*();}
 278
 279         //! Pre increment
 280         vector_iterator& operator++() {
 281             size_t k = ++my_index;
 282             if( my_item ) {
 283                 // Following test uses 2's-complement wizardry
 284                 if( (k& (k-2))==0 ) {
 285                     // k is a power of two that is at least k-2
 286                     my_item= NULL;
 287                 } else {
 288                     ++my_item;
 289                 }
 290             }
 291             return *this;
 292         }
 293
 294         //! Pre decrement
 295         vector_iterator& operator--() {
 296             __TBB_ASSERT( my_index>0, "operator--() applied to iterator already at beginning of concurrent_vector" );
 297             size_t k = my_index--;
 298             if( my_item ) {
 299                 // Following test uses 2's-complement wizardry
 300                 if( (k& (k-2))==0 ) {
 301                     // k is a power of two that is at least k-2
 302                     my_item= NULL;
 303                 } else {
 304                     --my_item;
 305                 }
 306             }
 307             return *this;
 308         }
 309
 310         //! Post increment
 311         vector_iterator operator++(int) {
 312             vector_iterator result = *this;
 313             operator++();
 314             return result;
 315         }
 316
 317         //! Post decrement
 318         vector_iterator operator--(int) {
 319             vector_iterator result = *this;
 320             operator--();
 321             return result;
 322         }
 323
 324         // STL support
 325
 326         typedef ptrdiff_t difference_type;
 327         typedef Value value_type;
 328         typedef Value* pointer;
 329         typedef Value& reference;
 330         typedef std::random_access_iterator_tag iterator_category;
 331     };
 332
 333     template<typename Container, typename T>
 334     vector_iterator<Container,T> operator+( ptrdiff_t offset, const vector_iterator<Container,T>& v ) {
 335         return vector_iterator<Container,T>( *v.my_vector, v.my_index+offset );
 336     }
 337
 338     template<typename Container, typename T, typename U>
 339     bool operator==( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
 340         return i.my_index==j.my_index && i.my_vector == j.my_vector;
 341     }
 342
 343     template<typename Container, typename T, typename U>
 344     bool operator!=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
 345         return !(i==j);
 346     }
 347
 348     template<typename Container, typename T, typename U>
 349     bool operator<( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
 350         return i.my_index<j.my_index;
 351     }
 352
 353     template<typename Container, typename T, typename U>
 354     bool operator>( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
 355         return j<i;
 356     }
 357
 358     template<typename Container, typename T, typename U>
 359     bool operator>=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
 360         return !(i<j);
 361     }
 362
 363     template<typename Container, typename T, typename U>
 364     bool operator<=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
 365         return !(j<i);
 366     }
 367
 368     template<typename Container, typename T, typename U>
 369     ptrdiff_t operator-( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
 370         return ptrdiff_t(i.my_index)-ptrdiff_t(j.my_index);
 371     }
 372
 373     template<typename T, class A>
 374     class allocator_base {
 375     public:
 376         typedef typename A::template
 377             rebind<T>::other allocator_type;
 378         allocator_type my_allocator;
 379
 380         allocator_base(const allocator_type &a = allocator_type() ) : my_allocator(a) {}
 381     };
 382
 383 } // namespace internal
 384 //! @endcond
 385
 386 //! Concurrent vector container
 387 /** concurrent_vector is a container having the following main properties:
 388     - It provides random indexed access to its elements. The index of the first element is 0.
 389     - It ensures safe concurrent growing its size (different threads can safely append new elements).
 390     - Adding new elements does not invalidate existing iterators and does not change indices of existing items.
 391
 392 @par Compatibility
 393     The class meets all Container Requirements and Reversible Container Requirements from
 394     C++ Standard (See ISO/IEC 14882:2003(E), clause 23.1). But it doesn't meet
 395     Sequence Requirements due to absence of insert() and erase() methods.
 396
 397 @par Exception Safety
 398     Methods working with memory allocation and/or new elements construction can throw an
 399     exception if allocator fails to allocate memory or element's default constructor throws one.
 400     Concurrent vector's element of type T must conform to the following requirements:
 401     - Throwing an exception is forbidden for destructor of T.
 402     - Default constructor of T must not throw an exception OR its non-virtual destructor must safely work when its object memory is zero-initialized.
 403     .
 404     Otherwise, the program's behavior is undefined.
 405 @par
 406     If an exception happens inside growth or assignment operation, an instance of the vector becomes invalid unless it is stated otherwise in the method documentation.
 407     Invalid state means:
 408     - There are no guaranties that all items were initialized by a constructor. The rest of items is zero-filled, including item where exception happens.
 409     - An invalid vector instance cannot be repaired; it is unable to grow anymore.
 410     - Size and capacity reported by the vector are incorrect, and calculated as if the failed operation were successful.
 411     - Attempt to access not allocated elements using operator[] or iterators results in access violation or segmentation fault exception, and in case of using at() method a C++ exception is thrown.
 412     .
 413     If a concurrent grow operation successfully completes, all the elements it has added to the vector will remain valid and accessible even if one of subsequent grow operations fails.
 414
 415 @par Fragmentation
 416     Unlike an STL vector, a concurrent_vector does not move existing elements if it needs
 417     to allocate more memory. The container is divided into a series of contiguous arrays of
 418     elements. The first reservation, growth, or assignment operation determines the size of
 419     the first array. Using small number of elements as initial size incurs fragmentation that
 420     may increase element access time. Internal layout can be optimized by method compact() that
 421     merges several smaller arrays into one solid.
 422
 423 @par Changes since TBB 2.1
 424     - Fixed guarantees of concurrent_vector::size() and grow_to_at_least() methods to assure elements are allocated.
 425     - Methods end()/rbegin()/back() are partly thread-safe since they use size() to get the end of vector
 426     - Added resize() methods (not thread-safe)
 427     - Added cbegin/cend/crbegin/crend methods
 428     - Changed return type of methods grow* and push_back to iterator
 429
 430 @par Changes since TBB 2.0
 431     - Implemented exception-safety guaranties
 432     - Added template argument for allocator
 433     - Added allocator argument in constructors
 434     - Faster index calculation
 435     - First growth call specifies a number of segments to be merged in the first allocation.
 436     - Fixed memory blow up for swarm of vector's instances of small size
 437     - Added grow_by(size_type n, const_reference t) growth using copying constructor to init new items.
 438     - Added STL-like constructors.
 439     - Added operators ==, < and derivatives
 440     - Added at() method, approved for using after an exception was thrown inside the vector
 441     - Added get_allocator() method.
 442     - Added assign() methods
 443     - Added compact() method to defragment first segments
 444     - Added swap() method
 445     - range() defaults on grainsize = 1 supporting auto grainsize algorithms.
 446
 447     @ingroup containers */
 448 template<typename T, class A>
 449 class concurrent_vector: protected internal::allocator_base<T, A>,
 450                          private internal::concurrent_vector_base {
 451 private:
 452     template<typename I>
 453     class generic_range_type: public blocked_range<I> {
 454     public:
 455         typedef T value_type;
 456         typedef T& reference;
 457         typedef const T& const_reference;
 458         typedef I iterator;
 459         typedef ptrdiff_t difference_type;
 460         generic_range_type( I begin_, I end_, size_t grainsize_ = 1) : blocked_range<I>(begin_,end_,grainsize_) {}
 461         template<typename U>
 462         generic_range_type( const generic_range_type<U>& r) : blocked_range<I>(r.begin(),r.end(),r.grainsize()) {}
 463         generic_range_type( generic_range_type& r, split ) : blocked_range<I>(r,split()) {}
 464     };
 465
 466     template<typename C, typename U>
 467     friend class internal::vector_iterator;
 468 public:
 469     //------------------------------------------------------------------------
 470     // STL compatible types
 471     //------------------------------------------------------------------------
 472     typedef internal::concurrent_vector_base_v3::size_type size_type;
 473     typedef typename internal::allocator_base<T, A>::allocator_type allocator_type;
 474
 475     typedef T value_type;
 476     typedef ptrdiff_t difference_type;
 477     typedef T& reference;
 478     typedef const T& const_reference;
 479     typedef T *pointer;
 480     typedef const T *const_pointer;
 481
 482     typedef internal::vector_iterator<concurrent_vector,T> iterator;
 483     typedef internal::vector_iterator<concurrent_vector,const T> const_iterator;
 484
 485 #if !defined(_MSC_VER) || _CPPLIB_VER>=300
 486     // Assume ISO standard definition of std::reverse_iterator
 487     typedef std::reverse_iterator<iterator> reverse_iterator;
 488     typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
 489 #else
 490     // Use non-standard std::reverse_iterator
 491     typedef std::reverse_iterator<iterator,T,T&,T*> reverse_iterator;
 492     typedef std::reverse_iterator<const_iterator,T,const T&,const T*> const_reverse_iterator;
 493 #endif /* defined(_MSC_VER) && (_MSC_VER<1300) */
 494
 495     //------------------------------------------------------------------------
 496     // Parallel algorithm support
 497     //------------------------------------------------------------------------
 498     typedef generic_range_type<iterator> range_type;
 499     typedef generic_range_type<const_iterator> const_range_type;
 500
 501     //------------------------------------------------------------------------
 502     // STL compatible constructors & destructors
 503     //------------------------------------------------------------------------
 504
 505     //! Construct empty vector.
 506     explicit concurrent_vector(const allocator_type &a = allocator_type())
 507         : internal::allocator_base<T, A>(a), internal::concurrent_vector_base()
 508     {
 509         vector_allocator_ptr = &internal_allocator;
 510     }
 511
 512     //! Copying constructor
 513     concurrent_vector( const concurrent_vector& vector, const allocator_type& a = allocator_type() )
 514         : internal::allocator_base<T, A>(a), internal::concurrent_vector_base()
 515     {
 516         vector_allocator_ptr = &internal_allocator;
 517         __TBB_TRY {
 518             internal_copy(vector, sizeof(T), &copy_array);
 519         } __TBB_CATCH(...) {
 520             segment_t *table = my_segment;
 521             internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
 522             __TBB_RETHROW();
 523         }
 524     }
 525
 526     //! Copying constructor for vector with different allocator type
 527     template<class M>
 528     concurrent_vector( const concurrent_vector<T, M>& vector, const allocator_type& a = allocator_type() )
 529         : internal::allocator_base<T, A>(a), internal::concurrent_vector_base()
 530     {
 531         vector_allocator_ptr = &internal_allocator;
 532         __TBB_TRY {
 533             internal_copy(vector.internal_vector_base(), sizeof(T), &copy_array);
 534         } __TBB_CATCH(...) {
 535             segment_t *table = my_segment;
 536             internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
 537             __TBB_RETHROW();
 538         }
 539     }
 540
 541     //! Construction with initial size specified by argument n
 542     explicit concurrent_vector(size_type n)
 543     {
 544         vector_allocator_ptr = &internal_allocator;
 545         __TBB_TRY {
 546             internal_resize( n, sizeof(T), max_size(), NULL, &destroy_array, &initialize_array );
 547         } __TBB_CATCH(...) {
 548             segment_t *table = my_segment;
 549             internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
 550             __TBB_RETHROW();
 551         }
 552     }
 553
 554     //! Construction with initial size specified by argument n, initialization by copying of t, and given allocator instance
 555     concurrent_vector(size_type n, const_reference t, const allocator_type& a = allocator_type())
 556         : internal::allocator_base<T, A>(a)
 557     {
 558         vector_allocator_ptr = &internal_allocator;
 559         __TBB_TRY {
 560             internal_resize( n, sizeof(T), max_size(), static_cast<const void*>(&t), &destroy_array, &initialize_array_by );
 561         } __TBB_CATCH(...) {
 562             segment_t *table = my_segment;
 563             internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
 564             __TBB_RETHROW();
 565         }
 566     }
 567
 568     //! Construction with copying iteration range and given allocator instance
 569     template<class I>
 570     concurrent_vector(I first, I last, const allocator_type &a = allocator_type())
 571         : internal::allocator_base<T, A>(a)
 572     {
 573         vector_allocator_ptr = &internal_allocator;
 574         __TBB_TRY {
 575             internal_assign_range(first, last, static_cast<is_integer_tag<std::numeric_limits<I>::is_integer> *>(0) );
 576         } __TBB_CATCH(...) {
 577             segment_t *table = my_segment;
 578             internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
 579             __TBB_RETHROW();
 580         }
 581     }
 582
 583     //! Assignment
 584     concurrent_vector& operator=( const concurrent_vector& vector ) {
 585         if( this != &vector )
 586             internal_assign(vector, sizeof(T), &destroy_array, &assign_array, &copy_array);
 587         return *this;
 588     }
 589
 590     //! Assignment for vector with different allocator type
 591     template<class M>
 592     concurrent_vector& operator=( const concurrent_vector<T, M>& vector ) {
 593         if( static_cast<void*>( this ) != static_cast<const void*>( &vector ) )
 594             internal_assign(vector.internal_vector_base(),
 595                 sizeof(T), &destroy_array, &assign_array, &copy_array);
 596         return *this;
 597     }
 598
 599     //------------------------------------------------------------------------
 600     // Concurrent operations
 601     //------------------------------------------------------------------------
 602     //! Grow by "delta" elements.
 603 #if TBB_DEPRECATED
 604     /** Returns old size. */
 605     size_type grow_by( size_type delta ) {
 606         return delta ? internal_grow_by( delta, sizeof(T), &initialize_array, NULL ) : my_early_size;
 607     }
 608 #else
 609     /** Returns iterator pointing to the first new element. */
 610     iterator grow_by( size_type delta ) {
 611         return iterator(*this, delta ? internal_grow_by( delta, sizeof(T), &initialize_array, NULL ) : my_early_size);
 612     }
 613 #endif
 614
 615     //! Grow by "delta" elements using copying constuctor.
 616 #if TBB_DEPRECATED
 617     /** Returns old size. */
 618     size_type grow_by( size_type delta, const_reference t ) {
 619         return delta ? internal_grow_by( delta, sizeof(T), &initialize_array_by, static_cast<const void*>(&t) ) : my_early_size;
 620     }
 621 #else
 622     /** Returns iterator pointing to the first new element. */
 623     iterator grow_by( size_type delta, const_reference t ) {
 624         return iterator(*this, delta ? internal_grow_by( delta, sizeof(T), &initialize_array_by, static_cast<const void*>(&t) ) : my_early_size);
 625     }
 626 #endif
 627
 628     //! Append minimal sequence of elements such that size()>=n.
 629 #if TBB_DEPRECATED
 630     /** The new elements are default constructed.  Blocks until all elements in range [0..n) are allocated.
 631         May return while other elements are being constructed by other threads. */
 632     void grow_to_at_least( size_type n ) {
 633         if( n ) internal_grow_to_at_least_with_result( n, sizeof(T), &initialize_array, NULL );
 634     };
 635 #else
 636     /** The new elements are default constructed.  Blocks until all elements in range [0..n) are allocated.
 637         May return while other elements are being constructed by other threads.
 638         Returns iterator that points to beginning of appended sequence.
 639         If no elements were appended, returns iterator pointing to nth element. */
 640     iterator grow_to_at_least( size_type n ) {
 641         size_type m=0;
 642         if( n ) {
 643             m = internal_grow_to_at_least_with_result( n, sizeof(T), &initialize_array, NULL );
 644             if( m>n ) m=n;
 645         }
 646         return iterator(*this, m);
 647     };
 648 #endif
 649
 650     //! Push item
 651 #if TBB_DEPRECATED
 652     size_type push_back( const_reference item )
 653 #else
 654     /** Returns iterator pointing to the new element. */
 655     iterator push_back( const_reference item )
 656 #endif
 657     {
 658         size_type k;
 659         void *ptr = internal_push_back(sizeof(T),k);
 660         internal_loop_guide loop(1, ptr);
 661         loop.init(&item);
 662 #if TBB_DEPRECATED
 663         return k;
 664 #else
 665         return iterator(*this, k, ptr);
 666 #endif
 667     }
 668
 669     //! Get reference to element at given index.
 670     /** This method is thread-safe for concurrent reads, and also while growing the vector,
 671         as long as the calling thread has checked that index&lt;size(). */
 672     reference operator[]( size_type index ) {
 673         return internal_subscript(index);
 674     }
 675
 676     //! Get const reference to element at given index.
 677     const_reference operator[]( size_type index ) const {
 678         return internal_subscript(index);
 679     }
 680
 681     //! Get reference to element at given index. Throws exceptions on errors.
 682     reference at( size_type index ) {
 683         return internal_subscript_with_exceptions(index);
 684     }
 685
 686     //! Get const reference to element at given index. Throws exceptions on errors.
 687     const_reference at( size_type index ) const {
 688         return internal_subscript_with_exceptions(index);
 689     }
 690
 691     //! Get range for iterating with parallel algorithms
 692     range_type range( size_t grainsize = 1) {
 693         return range_type( begin(), end(), grainsize );
 694     }
 695
 696     //! Get const range for iterating with parallel algorithms
 697     const_range_type range( size_t grainsize = 1 ) const {
 698         return const_range_type( begin(), end(), grainsize );
 699     }
 700     //------------------------------------------------------------------------
 701     // Capacity
 702     //------------------------------------------------------------------------
 703     //! Return size of vector. It may include elements under construction
 704     size_type size() const {
 705         size_type sz = my_early_size, cp = internal_capacity();
 706         return cp < sz ? cp : sz;
 707     }
 708
 709     //! Return true if vector is not empty or has elements under construction at least.
 710     bool empty() const {return !my_early_size;}
 711
 712     //! Maximum size to which array can grow without allocating more memory. Concurrent allocations are not included in the value.
 713     size_type capacity() const {return internal_capacity();}
 714
 715     //! Allocate enough space to grow to size n without having to allocate more memory later.
 716     /** Like most of the methods provided for STL compatibility, this method is *not* thread safe.
 717         The capacity afterwards may be bigger than the requested reservation. */
 718     void reserve( size_type n ) {
 719         if( n )
 720             internal_reserve(n, sizeof(T), max_size());
 721     }
 722
 723     //! Resize the vector. Not thread-safe.
 724     void resize( size_type n ) {
 725         internal_resize( n, sizeof(T), max_size(), NULL, &destroy_array, &initialize_array );
 726     }
 727
 728     //! Resize the vector, copy t for new elements. Not thread-safe.
 729     void resize( size_type n, const_reference t ) {
 730         internal_resize( n, sizeof(T), max_size(), static_cast<const void*>(&t), &destroy_array, &initialize_array_by );
 731     }
 732
 733 #if TBB_DEPRECATED
 734     //! An alias for shrink_to_fit()
 735     void compact() {shrink_to_fit();}
 736 #endif /* TBB_DEPRECATED */
 737
 738     //! Optimize memory usage and fragmentation.
 739     void shrink_to_fit();
 740
 741     //! Upper bound on argument to reserve.
 742     size_type max_size() const {return (~size_type(0))/sizeof(T);}
 743
 744     //------------------------------------------------------------------------
 745     // STL support
 746     //------------------------------------------------------------------------
 747
 748     //! start iterator
 749     iterator begin() {return iterator(*this,0);}
 750     //! end iterator
 751     iterator end() {return iterator(*this,size());}
 752     //! start const iterator
 753     const_iterator begin() const {return const_iterator(*this,0);}
 754     //! end const iterator
 755     const_iterator end() const {return const_iterator(*this,size());}
 756     //! start const iterator
 757     const_iterator cbegin() const {return const_iterator(*this,0);}
 758     //! end const iterator
 759     const_iterator cend() const {return const_iterator(*this,size());}
 760     //! reverse start iterator
 761     reverse_iterator rbegin() {return reverse_iterator(end());}
 762     //! reverse end iterator
 763     reverse_iterator rend() {return reverse_iterator(begin());}
 764     //! reverse start const iterator
 765     const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
 766     //! reverse end const iterator
 767     const_reverse_iterator rend() const {return const_reverse_iterator(begin());}
 768     //! reverse start const iterator
 769     const_reverse_iterator crbegin() const {return const_reverse_iterator(end());}
 770     //! reverse end const iterator
 771     const_reverse_iterator crend() const {return const_reverse_iterator(begin());}
 772     //! the first item
 773     reference front() {
 774         __TBB_ASSERT( size()>0, NULL);
 775         return static_cast<T*>(my_segment[0].array)[0];
 776     }
 777     //! the first item const
 778     const_reference front() const {
 779         __TBB_ASSERT( size()>0, NULL);
 780         return static_cast<const T*>(my_segment[0].array)[0];
 781     }
 782     //! the last item
 783     reference back() {
 784         __TBB_ASSERT( size()>0, NULL);
 785         return internal_subscript( size()-1 );
 786     }
 787     //! the last item const
 788     const_reference back() const {
 789         __TBB_ASSERT( size()>0, NULL);
 790         return internal_subscript( size()-1 );
 791     }
 792     //! return allocator object
 793     allocator_type get_allocator() const { return this->my_allocator; }
 794
 795     //! assign n items by copying t item
 796     void assign(size_type n, const_reference t) {
 797         clear();
 798         internal_resize( n, sizeof(T), max_size(), static_cast<const void*>(&t), &destroy_array, &initialize_array_by );
 799     }
 800
 801     //! assign range [first, last)
 802     template<class I>
 803     void assign(I first, I last) {
 804         clear(); internal_assign_range( first, last, static_cast<is_integer_tag<std::numeric_limits<I>::is_integer> *>(0) );
 805     }
 806
 807     //! swap two instances
 808     void swap(concurrent_vector &vector) {
 809         if( this != &vector ) {
 810             concurrent_vector_base_v3::internal_swap(static_cast<concurrent_vector_base_v3&>(vector));
 811             std::swap(this->my_allocator, vector.my_allocator);
 812         }
 813     }
 814
 815     //! Clear container while keeping memory allocated.
 816     /** To free up the memory, use in conjunction with method compact(). Not thread safe **/
 817     void clear() {
 818         internal_clear(&destroy_array);
 819     }
 820
 821     //! Clear and destroy vector.
 822     ~concurrent_vector() {
 823         segment_t *table = my_segment;
 824         internal_free_segments( reinterpret_cast<void**>(table), internal_clear(&destroy_array), my_first_block );
 825         // base class destructor call should be then
 826     }
 827
 828     const internal::concurrent_vector_base_v3 &internal_vector_base() const { return *this; }
 829 private:
 830     //! Allocate k items
 831     static void *internal_allocator(internal::concurrent_vector_base_v3 &vb, size_t k) {
 832         return static_cast<concurrent_vector<T, A>&>(vb).my_allocator.allocate(k);
 833     }
 834     //! Free k segments from table
 835     void internal_free_segments(void *table[], segment_index_t k, segment_index_t first_block);
 836
 837     //! Get reference to element at given index.
 838     T& internal_subscript( size_type index ) const;
 839
 840     //! Get reference to element at given index with errors checks
 841     T& internal_subscript_with_exceptions( size_type index ) const;
 842
 843     //! assign n items by copying t
 844     void internal_assign_n(size_type n, const_pointer p) {
 845         internal_resize( n, sizeof(T), max_size(), static_cast<const void*>(p), &destroy_array, p? &initialize_array_by : &initialize_array );
 846     }
 847
 848     //! helper class
 849     template<bool B> class is_integer_tag;
 850
 851     //! assign integer items by copying when arguments are treated as iterators. See C++ Standard 2003 23.1.1p9
 852     template<class I>
 853     void internal_assign_range(I first, I last, is_integer_tag<true> *) {
 854         internal_assign_n(static_cast<size_type>(first), &static_cast<T&>(last));
 855     }
 856     //! inline proxy assign by iterators
 857     template<class I>
 858     void internal_assign_range(I first, I last, is_integer_tag<false> *) {
 859         internal_assign_iterators(first, last);
 860     }
 861     //! assign by iterators
 862     template<class I>
 863     void internal_assign_iterators(I first, I last);
 864
 865     //! Construct n instances of T, starting at "begin".
 866     static void __TBB_EXPORTED_FUNC initialize_array( void* begin, const void*, size_type n );
 867
 868     //! Construct n instances of T, starting at "begin".
 869     static void __TBB_EXPORTED_FUNC initialize_array_by( void* begin, const void* src, size_type n );
 870
 871     //! Construct n instances of T, starting at "begin".
 872     static void __TBB_EXPORTED_FUNC copy_array( void* dst, const void* src, size_type n );
 873
 874     //! Assign n instances of T, starting at "begin".
 875     static void __TBB_EXPORTED_FUNC assign_array( void* dst, const void* src, size_type n );
 876
 877     //! Destroy n instances of T, starting at "begin".
 878     static void __TBB_EXPORTED_FUNC destroy_array( void* begin, size_type n );
 879
 880     //! Exception-aware helper class for filling a segment by exception-danger operators of user class
 881     class internal_loop_guide : internal::no_copy {
 882     public:
 883         const pointer array;
 884         const size_type n;
 885         size_type i;
 886         internal_loop_guide(size_type ntrials, void *ptr)
 887             : array(static_cast<pointer>(ptr)), n(ntrials), i(0) {}
 888         void init() {   for(; i < n; ++i) new( &array[i] ) T(); }
 889         void init(const void *src) { for(; i < n; ++i) new( &array[i] ) T(*static_cast<const T*>(src)); }
 890         void copy(const void *src) { for(; i < n; ++i) new( &array[i] ) T(static_cast<const T*>(src)[i]); }
 891         void assign(const void *src) { for(; i < n; ++i) array[i] = static_cast<const T*>(src)[i]; }
 892         template<class I> void iterate(I &src) { for(; i < n; ++i, ++src) new( &array[i] ) T( *src ); }
 893         ~internal_loop_guide() {
 894             if(i < n) // if exception raised, do zerroing on the rest of items
 895                 std::memset(array+i, 0, (n-i)*sizeof(value_type));
 896         }
 897     };
 898 };
 899
 900 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
 901 #pragma warning (push)
 902 #pragma warning (disable: 4701) // potentially uninitialized local variable "old"
 903 #endif
 904 template<typename T, class A>
 905 void concurrent_vector<T, A>::shrink_to_fit() {
 906     internal_segments_table old;
 907     __TBB_TRY {
 908         if( internal_compact( sizeof(T), &old, &destroy_array, &copy_array ) )
 909             internal_free_segments( old.table, pointers_per_long_table, old.first_block ); // free joined and unnecessary segments
 910     } __TBB_CATCH(...) {
 911         if( old.first_block ) // free segment allocated for compacting. Only for support of exceptions in ctor of user T[ype]
 912             internal_free_segments( old.table, 1, old.first_block );
 913         __TBB_RETHROW();
 914     }
 915 }
 916 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
 917 #pragma warning (pop)
 918 #endif // warning 4701 is back
 919
 920 template<typename T, class A>
 921 void concurrent_vector<T, A>::internal_free_segments(void *table[], segment_index_t k, segment_index_t first_block) {
 922     // Free the arrays
 923     while( k > first_block ) {
 924         --k;
 925         T* array = static_cast<T*>(table[k]);
 926         table[k] = NULL;
 927         if( array > internal::vector_allocation_error_flag ) // check for correct segment pointer
 928             this->my_allocator.deallocate( array, segment_size(k) );
 929     }
 930     T* array = static_cast<T*>(table[0]);
 931     if( array > internal::vector_allocation_error_flag ) {
 932         __TBB_ASSERT( first_block > 0, NULL );
 933         while(k > 0) table[--k] = NULL;
 934         this->my_allocator.deallocate( array, segment_size(first_block) );
 935     }
 936 }
 937
 938 template<typename T, class A>
 939 T& concurrent_vector<T, A>::internal_subscript( size_type index ) const {
 940     __TBB_ASSERT( index < my_early_size, "index out of bounds" );
 941     size_type j = index;
 942     segment_index_t k = segment_base_index_of( j );
 943     __TBB_ASSERT( (segment_t*)my_segment != my_storage || k < pointers_per_short_table, "index is being allocated" );
 944     // no need in __TBB_load_with_acquire since thread works in own space or gets
 945     T* array = static_cast<T*>( tbb::internal::itt_hide_load_word(my_segment[k].array));
 946     __TBB_ASSERT( array != internal::vector_allocation_error_flag, "the instance is broken by bad allocation. Use at() instead" );
 947     __TBB_ASSERT( array, "index is being allocated" );
 948     return array[j];
 949 }
 950
 951 template<typename T, class A>
 952 T& concurrent_vector<T, A>::internal_subscript_with_exceptions( size_type index ) const {
 953     if( index >= my_early_size )
 954         internal::throw_exception(internal::eid_out_of_range); // throw std::out_of_range
 955     size_type j = index;
 956     segment_index_t k = segment_base_index_of( j );
 957     if( (segment_t*)my_segment == my_storage && k >= pointers_per_short_table )
 958         internal::throw_exception(internal::eid_segment_range_error); // throw std::range_error
 959     void *array = my_segment[k].array; // no need in __TBB_load_with_acquire
 960     if( array <= internal::vector_allocation_error_flag ) // check for correct segment pointer
 961         internal::throw_exception(internal::eid_index_range_error); // throw std::range_error
 962     return static_cast<T*>(array)[j];
 963 }
 964
 965 template<typename T, class A> template<class I>
 966 void concurrent_vector<T, A>::internal_assign_iterators(I first, I last) {
 967     __TBB_ASSERT(my_early_size == 0, NULL);
 968     size_type n = std::distance(first, last);
 969     if( !n ) return;
 970     internal_reserve(n, sizeof(T), max_size());
 971     my_early_size = n;
 972     segment_index_t k = 0;
 973     size_type sz = segment_size( my_first_block );
 974     while( sz < n ) {
 975         internal_loop_guide loop(sz, my_segment[k].array);
 976         loop.iterate(first);
 977         n -= sz;
 978         if( !k ) k = my_first_block;
 979         else { ++k; sz <<= 1; }
 980     }
 981     internal_loop_guide loop(n, my_segment[k].array);
 982     loop.iterate(first);
 983 }
 984
 985 template<typename T, class A>
 986 void concurrent_vector<T, A>::initialize_array( void* begin, const void *, size_type n ) {
 987     internal_loop_guide loop(n, begin); loop.init();
 988 }
 989
 990 template<typename T, class A>
 991 void concurrent_vector<T, A>::initialize_array_by( void* begin, const void *src, size_type n ) {
 992     internal_loop_guide loop(n, begin); loop.init(src);
 993 }
 994
 995 template<typename T, class A>
 996 void concurrent_vector<T, A>::copy_array( void* dst, const void* src, size_type n ) {
 997     internal_loop_guide loop(n, dst); loop.copy(src);
 998 }
 999
1000 template<typename T, class A>
1001 void concurrent_vector<T, A>::assign_array( void* dst, const void* src, size_type n ) {
1002     internal_loop_guide loop(n, dst); loop.assign(src);
1003 }
1004
1005 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
1006     // Workaround for overzealous compiler warning
1007     #pragma warning (push)
1008     #pragma warning (disable: 4189)
1009 #endif
1010 template<typename T, class A>
1011 void concurrent_vector<T, A>::destroy_array( void* begin, size_type n ) {
1012     T* array = static_cast<T*>(begin);
1013     for( size_type j=n; j>0; --j )
1014         array[j-1].~T(); // destructors are supposed to not throw any exceptions
1015 }
1016 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
1017     #pragma warning (pop)
1018 #endif // warning 4189 is back
1019
1020 // concurrent_vector's template functions
1021 template<typename T, class A1, class A2>
1022 inline bool operator==(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b) {
1023     // Simply:    return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
1024     if(a.size() != b.size()) return false;
1025     typename concurrent_vector<T, A1>::const_iterator i(a.begin());
1026     typename concurrent_vector<T, A2>::const_iterator j(b.begin());
1027     for(; i != a.end(); ++i, ++j)
1028         if( !(*i == *j) ) return false;
1029     return true;
1030 }
1031
1032 template<typename T, class A1, class A2>
1033 inline bool operator!=(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
1034 {    return !(a == b); }
1035
1036 template<typename T, class A1, class A2>
1037 inline bool operator<(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
1038 {    return (std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end())); }
1039
1040 template<typename T, class A1, class A2>
1041 inline bool operator>(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
1042 {    return b < a; }
1043
1044 template<typename T, class A1, class A2>
1045 inline bool operator<=(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
1046 {    return !(b < a); }
1047
1048 template<typename T, class A1, class A2>
1049 inline bool operator>=(const concurrent_vector<T, A1> &a, const concurrent_vector<T, A2> &b)
1050 {    return !(a < b); }
1051
1052 template<typename T, class A>
1053 inline void swap(concurrent_vector<T, A> &a, concurrent_vector<T, A> &b)
1054 {    a.swap( b ); }
1055
1056 } // namespace tbb
1057
1058 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER) && defined(_Wp64)
1059     #pragma warning (pop)
1060 #endif // warning 4267 is back
1061
1062 #endif /* __TBB_concurrent_vector_H */