1/*
2 Copyright (c) 2005-2019 Intel Corporation
3
4 Licensed under the Apache License, Version 2.0 (the "License");
5 you may not use this file except in compliance with the License.
6 You may obtain a copy of the License at
7
8 http://www.apache.org/licenses/LICENSE-2.0
9
10 Unless required by applicable law or agreed to in writing, software
11 distributed under the License is distributed on an "AS IS" BASIS,
12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 See the License for the specific language governing permissions and
14 limitations under the License.
15*/
16
17#ifndef __TBB_concurrent_vector_H
18#define __TBB_concurrent_vector_H
19
20#include "tbb/tbb_stddef.h"
21#include "tbb/atomic.h"
22#include "tbb/cache_aligned_allocator.h"
23#include "tbb/blocked_range.h"
24#include "tbb/tbb_machine.h"
25#include <new>
26#include <iterator>
27
28namespace tbb {
29
30template<typename T>
31class concurrent_vector;
32
33//! @cond INTERNAL
34namespace internal {
35
36 //! Base class of concurrent vector implementation.
37 /** @ingroup containers */
38 class concurrent_vector_base {
39 protected:
40
41 // Basic types declarations
42 typedef unsigned long segment_index_t;
43 typedef size_t size_type;
44
45 //! Log2 of "min_segment_size".
46 static const int lg_min_segment_size = 4;
47
48 //! Minimum size (in physical items) of a segment.
49 static const int min_segment_size = segment_index_t(1)<<lg_min_segment_size;
50
51 static segment_index_t segment_index_of( size_t index ) {
52 uintptr_t i = index|1<<(lg_min_segment_size-1);
53 uintptr_t j = __TBB_Log2(i);
54 return segment_index_t(j-(lg_min_segment_size-1));
55 }
56
57 static segment_index_t segment_base( segment_index_t k ) {
58 return min_segment_size>>1<<k & -min_segment_size;
59 }
60
61 static segment_index_t segment_size( segment_index_t k ) {
62 segment_index_t result = k==0 ? min_segment_size : min_segment_size/2<<k;
63 __TBB_ASSERT( result==segment_base(k+1)-segment_base(k), NULL );
64 return result;
65 }
66
67 void __TBB_EXPORTED_METHOD internal_reserve( size_type n, size_type element_size, size_type max_size );
68
69 size_type __TBB_EXPORTED_METHOD internal_capacity() const;
70
71 //! Requested size of vector
72 atomic<size_type> my_early_size;
73
74 /** Can be zero-initialized. */
75 struct segment_t {
76 /** Declared volatile because in weak memory model, must have ld.acq/st.rel */
77 void* volatile array;
78#if TBB_USE_ASSERT
79 ~segment_t() {
80 __TBB_ASSERT( !array, "should have been set to NULL by clear" );
81 }
82#endif /* TBB_USE_ASSERT */
83 };
84
85 // Data fields
86
87 //! Pointer to the segments table
88 atomic<segment_t*> my_segment;
89
90 //! embedded storage of segment pointers
91 segment_t my_storage[2];
92
93 // Methods
94
95 concurrent_vector_base() {
96 my_early_size = 0;
97 my_storage[0].array = NULL;
98 my_storage[1].array = NULL;
99 my_segment = my_storage;
100 }
101
102 //! An operation on an n-element array starting at begin.
103 typedef void(__TBB_EXPORTED_FUNC *internal_array_op1)(void* begin, size_type n );
104
105 //! An operation on n-element destination array and n-element source array.
106 typedef void(__TBB_EXPORTED_FUNC *internal_array_op2)(void* dst, const void* src, size_type n );
107
108 void __TBB_EXPORTED_METHOD internal_grow_to_at_least( size_type new_size, size_type element_size, internal_array_op1 init );
109 void internal_grow( size_type start, size_type finish, size_type element_size, internal_array_op1 init );
110 size_type __TBB_EXPORTED_METHOD internal_grow_by( size_type delta, size_type element_size, internal_array_op1 init );
111 void* __TBB_EXPORTED_METHOD internal_push_back( size_type element_size, size_type& index );
112 void __TBB_EXPORTED_METHOD internal_clear( internal_array_op1 destroy, bool reclaim_storage );
113 void __TBB_EXPORTED_METHOD internal_copy( const concurrent_vector_base& src, size_type element_size, internal_array_op2 copy );
114 void __TBB_EXPORTED_METHOD internal_assign( const concurrent_vector_base& src, size_type element_size,
115 internal_array_op1 destroy, internal_array_op2 assign, internal_array_op2 copy );
116private:
117 //! Private functionality that does not cross DLL boundary.
118 class helper;
119 friend class helper;
120 };
121
122 //! Meets requirements of a forward iterator for STL and a Value for a blocked_range.*/
123 /** Value is either the T or const T type of the container.
124 @ingroup containers */
125 template<typename Container, typename Value>
126 class vector_iterator
127#if defined(_WIN64) && defined(_MSC_VER)
128 // Ensure that Microsoft's internal template function _Val_type works correctly.
129 : public std::iterator<std::random_access_iterator_tag,Value>
130#endif /* defined(_WIN64) && defined(_MSC_VER) */
131 {
132 //! concurrent_vector over which we are iterating.
133 Container* my_vector;
134
135 //! Index into the vector
136 size_t my_index;
137
138 //! Caches my_vector-&gt;internal_subscript(my_index)
139 /** NULL if cached value is not available */
140 mutable Value* my_item;
141
142 template<typename C, typename T, typename U>
143 friend bool operator==( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
144
145 template<typename C, typename T, typename U>
146 friend bool operator<( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
147
148 template<typename C, typename T, typename U>
149 friend ptrdiff_t operator-( const vector_iterator<C,T>& i, const vector_iterator<C,U>& j );
150
151 template<typename C, typename U>
152 friend class internal::vector_iterator;
153
154#if !defined(_MSC_VER) || defined(__INTEL_COMPILER)
155 template<typename T>
156 friend class tbb::concurrent_vector;
157#else
158public: // workaround for MSVC
159#endif
160
161 vector_iterator( const Container& vector, size_t index ) :
162 my_vector(const_cast<Container*>(&vector)),
163 my_index(index),
164 my_item(NULL)
165 {}
166
167 public:
168 //! Default constructor
169 vector_iterator() : my_vector(NULL), my_index(~size_t(0)), my_item(NULL) {}
170
171 vector_iterator( const vector_iterator<Container,typename Container::value_type>& other ) :
172 my_vector(other.my_vector),
173 my_index(other.my_index),
174 my_item(other.my_item)
175 {}
176
177 vector_iterator operator+( ptrdiff_t offset ) const {
178 return vector_iterator( *my_vector, my_index+offset );
179 }
180 friend vector_iterator operator+( ptrdiff_t offset, const vector_iterator& v ) {
181 return vector_iterator( *v.my_vector, v.my_index+offset );
182 }
183 vector_iterator operator+=( ptrdiff_t offset ) {
184 my_index+=offset;
185 my_item = NULL;
186 return *this;
187 }
188 vector_iterator operator-( ptrdiff_t offset ) const {
189 return vector_iterator( *my_vector, my_index-offset );
190 }
191 vector_iterator operator-=( ptrdiff_t offset ) {
192 my_index-=offset;
193 my_item = NULL;
194 return *this;
195 }
196 Value& operator*() const {
197 Value* item = my_item;
198 if( !item ) {
199 item = my_item = &my_vector->internal_subscript(my_index);
200 }
201 __TBB_ASSERT( item==&my_vector->internal_subscript(my_index), "corrupt cache" );
202 return *item;
203 }
204 Value& operator[]( ptrdiff_t k ) const {
205 return my_vector->internal_subscript(my_index+k);
206 }
207 Value* operator->() const {return &operator*();}
208
209 //! Pre increment
210 vector_iterator& operator++() {
211 size_t k = ++my_index;
212 if( my_item ) {
213 // Following test uses 2's-complement wizardry and fact that
214 // min_segment_size is a power of 2.
215 if( (k& k-concurrent_vector<Container>::min_segment_size)==0 ) {
216 // k is a power of two that is at least k-min_segment_size
217 my_item= NULL;
218 } else {
219 ++my_item;
220 }
221 }
222 return *this;
223 }
224
225 //! Pre decrement
226 vector_iterator& operator--() {
227 __TBB_ASSERT( my_index>0, "operator--() applied to iterator already at beginning of concurrent_vector" );
228 size_t k = my_index--;
229 if( my_item ) {
230 // Following test uses 2's-complement wizardry and fact that
231 // min_segment_size is a power of 2.
232 if( (k& k-concurrent_vector<Container>::min_segment_size)==0 ) {
233 // k is a power of two that is at least k-min_segment_size
234 my_item= NULL;
235 } else {
236 --my_item;
237 }
238 }
239 return *this;
240 }
241
242 //! Post increment
243 vector_iterator operator++(int) {
244 vector_iterator result = *this;
245 operator++();
246 return result;
247 }
248
249 //! Post decrement
250 vector_iterator operator--(int) {
251 vector_iterator result = *this;
252 operator--();
253 return result;
254 }
255
256 // STL support
257
258 typedef ptrdiff_t difference_type;
259 typedef Value value_type;
260 typedef Value* pointer;
261 typedef Value& reference;
262 typedef std::random_access_iterator_tag iterator_category;
263 };
264
265 template<typename Container, typename T, typename U>
266 bool operator==( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
267 return i.my_index==j.my_index;
268 }
269
270 template<typename Container, typename T, typename U>
271 bool operator!=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
272 return !(i==j);
273 }
274
275 template<typename Container, typename T, typename U>
276 bool operator<( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
277 return i.my_index<j.my_index;
278 }
279
280 template<typename Container, typename T, typename U>
281 bool operator>( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
282 return j<i;
283 }
284
285 template<typename Container, typename T, typename U>
286 bool operator>=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
287 return !(i<j);
288 }
289
290 template<typename Container, typename T, typename U>
291 bool operator<=( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
292 return !(j<i);
293 }
294
295 template<typename Container, typename T, typename U>
296 ptrdiff_t operator-( const vector_iterator<Container,T>& i, const vector_iterator<Container,U>& j ) {
297 return ptrdiff_t(i.my_index)-ptrdiff_t(j.my_index);
298 }
299
300} // namespace internal
301//! @endcond
302
303//! Concurrent vector
304/** @ingroup containers */
305template<typename T>
306class concurrent_vector: private internal::concurrent_vector_base {
307public:
308 using internal::concurrent_vector_base::size_type;
309private:
310 template<typename I>
311 class generic_range_type: public blocked_range<I> {
312 public:
313 typedef T value_type;
314 typedef T& reference;
315 typedef const T& const_reference;
316 typedef I iterator;
317 typedef ptrdiff_t difference_type;
318 generic_range_type( I begin_, I end_, size_t grainsize_ ) : blocked_range<I>(begin_,end_,grainsize_) {}
319 generic_range_type( generic_range_type& r, split ) : blocked_range<I>(r,split()) {}
320 };
321
322 template<typename C, typename U>
323 friend class internal::vector_iterator;
324public:
325 typedef T& reference;
326 typedef const T& const_reference;
327 typedef T value_type;
328 typedef ptrdiff_t difference_type;
329
330 //! Construct empty vector.
331 concurrent_vector() {}
332
333 //! Copy a vector.
334 concurrent_vector( const concurrent_vector& vector ) : internal::concurrent_vector_base()
335 { internal_copy(vector,sizeof(T),&copy_array); }
336
337 //! Assignment
338 concurrent_vector& operator=( const concurrent_vector& vector ) {
339 if( this!=&vector )
340 internal_assign(vector,sizeof(T),&destroy_array,&assign_array,&copy_array);
341 return *this;
342 }
343
344 //! Clear and destroy vector.
345 ~concurrent_vector() {internal_clear(&destroy_array,/*reclaim_storage=*/true);}
346
347 //------------------------------------------------------------------------
348 // Concurrent operations
349 //------------------------------------------------------------------------
350 //! Grow by "delta" elements.
351 /** Returns old size. */
352 size_type grow_by( size_type delta ) {
353 return delta ? internal_grow_by( delta, sizeof(T), &initialize_array ) : my_early_size.load();
354 }
355
356 //! Grow array until it has at least n elements.
357 void grow_to_at_least( size_type n ) {
358 if( my_early_size<n )
359 internal_grow_to_at_least( n, sizeof(T), &initialize_array );
360 };
361
362 //! Push item
363 size_type push_back( const_reference item ) {
364 size_type k;
365 new( internal_push_back(sizeof(T),k) ) T(item);
366 return k;
367 }
368
369 //! Get reference to element at given index.
370 /** This method is thread-safe for concurrent reads, and also while growing the vector,
371 as long as the calling thread has checked that index&lt;size(). */
372 reference operator[]( size_type index ) {
373 return internal_subscript(index);
374 }
375
376 //! Get const reference to element at given index.
377 const_reference operator[]( size_type index ) const {
378 return internal_subscript(index);
379 }
380
381 //------------------------------------------------------------------------
382 // STL support (iterators)
383 //------------------------------------------------------------------------
384 typedef internal::vector_iterator<concurrent_vector,T> iterator;
385 typedef internal::vector_iterator<concurrent_vector,const T> const_iterator;
386
387#if !defined(_MSC_VER) || _CPPLIB_VER>=300
388 // Assume ISO standard definition of std::reverse_iterator
389 typedef std::reverse_iterator<iterator> reverse_iterator;
390 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
391#else
392 // Use non-standard std::reverse_iterator
393 typedef std::reverse_iterator<iterator,T,T&,T*> reverse_iterator;
394 typedef std::reverse_iterator<const_iterator,T,const T&,const T*> const_reverse_iterator;
395#endif /* defined(_MSC_VER) && (_MSC_VER<1300) */
396
397 // Forward sequence
398 iterator begin() {return iterator(*this,0);}
399 iterator end() {return iterator(*this,size());}
400 const_iterator begin() const {return const_iterator(*this,0);}
401 const_iterator end() const {return const_iterator(*this,size());}
402
403 // Reverse sequence
404 reverse_iterator rbegin() {return reverse_iterator(end());}
405 reverse_iterator rend() {return reverse_iterator(begin());}
406 const_reverse_iterator rbegin() const {return const_reverse_iterator(end());}
407 const_reverse_iterator rend() const {return const_reverse_iterator(begin());}
408
409 //------------------------------------------------------------------------
410 // Support for TBB algorithms (ranges)
411 //------------------------------------------------------------------------
412 typedef generic_range_type<iterator> range_type;
413 typedef generic_range_type<const_iterator> const_range_type;
414
415 //! Get range to use with parallel algorithms
416 range_type range( size_t grainsize = 1 ) {
417 return range_type( begin(), end(), grainsize );
418 }
419
420 //! Get const range for iterating with parallel algorithms
421 const_range_type range( size_t grainsize = 1 ) const {
422 return const_range_type( begin(), end(), grainsize );
423 }
424
425 //------------------------------------------------------------------------
426 // Size and capacity
427 //------------------------------------------------------------------------
428 //! Return size of vector.
429 size_type size() const {return my_early_size;}
430
431 //! Return false if vector is not empty.
432 bool empty() const {return !my_early_size;}
433
434 //! Maximum size to which array can grow without allocating more memory.
435 size_type capacity() const {return internal_capacity();}
436
437 //! Allocate enough space to grow to size n without having to allocate more memory later.
438 /** Like most of the methods provided for STL compatibility, this method is *not* thread safe.
439 The capacity afterwards may be bigger than the requested reservation. */
440 void reserve( size_type n ) {
441 if( n )
442 internal_reserve(n, sizeof(T), max_size());
443 }
444
445 //! Upper bound on argument to reserve.
446 size_type max_size() const {return (~size_t(0))/sizeof(T);}
447
448 //! Not thread safe
449 /** Does not change capacity. */
450 void clear() {internal_clear(&destroy_array,/*reclaim_storage=*/false);}
451private:
452 //! Get reference to element at given index.
453 T& internal_subscript( size_type index ) const;
454
455 //! Construct n instances of T, starting at "begin".
456 static void __TBB_EXPORTED_FUNC initialize_array( void* begin, size_type n );
457
458 //! Construct n instances of T, starting at "begin".
459 static void __TBB_EXPORTED_FUNC copy_array( void* dst, const void* src, size_type n );
460
461 //! Assign n instances of T, starting at "begin".
462 static void __TBB_EXPORTED_FUNC assign_array( void* dst, const void* src, size_type n );
463
464 //! Destroy n instances of T, starting at "begin".
465 static void __TBB_EXPORTED_FUNC destroy_array( void* begin, size_type n );
466};
467
468template<typename T>
469T& concurrent_vector<T>::internal_subscript( size_type index ) const {
470 __TBB_ASSERT( index<size(), "index out of bounds" );
471 segment_index_t k = segment_index_of( index );
472 size_type j = index-segment_base(k);
473 return static_cast<T*>(my_segment[k].array)[j];
474}
475
476template<typename T>
477void concurrent_vector<T>::initialize_array( void* begin, size_type n ) {
478 T* array = static_cast<T*>(begin);
479 for( size_type j=0; j<n; ++j )
480 new( &array[j] ) T();
481}
482
483template<typename T>
484void concurrent_vector<T>::copy_array( void* dst, const void* src, size_type n ) {
485 T* d = static_cast<T*>(dst);
486 const T* s = static_cast<const T*>(src);
487 for( size_type j=0; j<n; ++j )
488 new( &d[j] ) T(s[j]);
489}
490
491template<typename T>
492void concurrent_vector<T>::assign_array( void* dst, const void* src, size_type n ) {
493 T* d = static_cast<T*>(dst);
494 const T* s = static_cast<const T*>(src);
495 for( size_type j=0; j<n; ++j )
496 d[j] = s[j];
497}
498
499template<typename T>
500void concurrent_vector<T>::destroy_array( void* begin, size_type n ) {
501 T* array = static_cast<T*>(begin);
502 for( size_type j=n; j>0; --j )
503 array[j-1].~T();
504}
505
506} // namespace tbb
507
508#endif /* __TBB_concurrent_vector_H */
509