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