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 | |
28 | namespace tbb { |
29 | |
30 | template<typename T> |
31 | class concurrent_vector; |
32 | |
33 | //! @cond INTERNAL |
34 | namespace 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 ); |
116 | private: |
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->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 |
158 | public: // 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 */ |
305 | template<typename T> |
306 | class concurrent_vector: private internal::concurrent_vector_base { |
307 | public: |
308 | using internal::concurrent_vector_base::size_type; |
309 | private: |
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; |
324 | public: |
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),©_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,©_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<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);} |
451 | private: |
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 | |
468 | template<typename T> |
469 | T& 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 | |
476 | template<typename T> |
477 | void 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 | |
483 | template<typename T> |
484 | void 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 | |
491 | template<typename T> |
492 | void 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 | |
499 | template<typename T> |
500 | void 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 | |