Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
concurrent_queue.h
Go to the documentation of this file.
1/*
2 Copyright (c) 2005-2020 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_queue_H
18#define __TBB_concurrent_queue_H
19
20#define __TBB_concurrent_queue_H_include_area
22
25
26namespace tbb {
27
28namespace strict_ppl {
29
31
34template<typename T, typename A = cache_aligned_allocator<T> >
36 template<typename Container, typename Value> friend class internal::concurrent_queue_iterator;
37
41
43 virtual void *allocate_block( size_t n ) __TBB_override {
44 void *b = reinterpret_cast<void*>(my_allocator.allocate( n ));
45 if( !b )
47 return b;
48 }
49
51 virtual void deallocate_block( void *b, size_t n ) __TBB_override {
52 my_allocator.deallocate( reinterpret_cast<char*>(b), n );
53 }
54
55 static void copy_construct_item(T* location, const void* src){
56 new (location) T(*static_cast<const T*>(src));
57 }
58
59#if __TBB_CPP11_RVALUE_REF_PRESENT
60 static void move_construct_item(T* location, const void* src) {
61 new (location) T( std::move(*static_cast<T*>(const_cast<void*>(src))) );
62 }
63#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
64public:
66 typedef T value_type;
67
69 typedef T& reference;
70
72 typedef const T& const_reference;
73
75 typedef size_t size_type;
76
78 typedef ptrdiff_t difference_type;
79
81 typedef A allocator_type;
82
85 my_allocator( a )
86 {
87 }
88
90 template<typename InputIterator>
91 concurrent_queue( InputIterator begin, InputIterator end, const allocator_type& a = allocator_type()) :
92 my_allocator( a )
93 {
94 for( ; begin != end; ++begin )
95 this->push(*begin);
96 }
97
101 {
102 this->assign( src, copy_construct_item );
103 }
104
105#if __TBB_CPP11_RVALUE_REF_PRESENT
109 {
110 this->internal_swap( src );
111 }
112
115 {
116 // checking that memory allocated by one instance of allocator can be deallocated
117 // with another
118 if( my_allocator == src.my_allocator) {
119 this->internal_swap( src );
120 } else {
121 // allocators are different => performing per-element move
122 this->assign( src, move_construct_item );
123 src.clear();
124 }
125 }
126#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
127
130
132 void push( const T& source ) {
133 this->internal_push( &source, copy_construct_item );
134 }
135
136#if __TBB_CPP11_RVALUE_REF_PRESENT
137 void push( T&& source ) {
138 this->internal_push( &source, move_construct_item );
139 }
140
141#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
142 template<typename... Arguments>
143 void emplace( Arguments&&... args ) {
144 push( T(std::forward<Arguments>( args )...) );
145 }
146#endif //__TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
147#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
148
150
152 bool try_pop( T& result ) {
153 return this->internal_try_pop( &result );
154 }
155
157 size_type unsafe_size() const {return this->internal_size();}
158
160 bool empty() const {return this->internal_empty();}
161
163 void clear() ;
164
166 allocator_type get_allocator() const { return this->my_allocator; }
167
170
171 //------------------------------------------------------------------------
172 // The iterators are intended only for debugging. They are slow and not thread safe.
173 //------------------------------------------------------------------------
174 iterator unsafe_begin() {return iterator(*this);}
178} ;
179
180#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
181// Deduction guide for the constructor from two iterators
182template<typename InputIterator,
183 typename T = typename std::iterator_traits<InputIterator>::value_type,
184 typename A = cache_aligned_allocator<T>
185> concurrent_queue(InputIterator, InputIterator, const A& = A())
187#endif /* __TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
188
189template<typename T, class A>
191 clear();
192 this->internal_finish_clear();
193}
194
195template<typename T, class A>
197 T value;
198 while( !empty() ) try_pop(value);
199}
200
201} // namespace strict_ppl
202
204
209template<typename T, class A = cache_aligned_allocator<T> >
211 template<typename Container, typename Value> friend class internal::concurrent_queue_iterator;
213
216
219
223 public:
226 };
227
228 T& get_ref( page& p, size_t index ) {
229 __TBB_ASSERT( index<items_per_page, NULL );
230 return (&static_cast<padded_page*>(static_cast<void*>(&p))->last)[index];
231 }
232
233 virtual void copy_item( page& dst, size_t index, const void* src ) __TBB_override {
234 new( &get_ref(dst,index) ) T(*static_cast<const T*>(src));
235 }
236
237#if __TBB_CPP11_RVALUE_REF_PRESENT
238 virtual void move_item( page& dst, size_t index, const void* src ) __TBB_override {
239 new( &get_ref(dst,index) ) T( std::move(*static_cast<T*>(const_cast<void*>(src))) );
240 }
241#else
242 virtual void move_item( page&, size_t, const void* ) __TBB_override {
243 __TBB_ASSERT( false, "Unreachable code" );
244 }
245#endif
246
247 virtual void copy_page_item( page& dst, size_t dindex, const page& src, size_t sindex ) __TBB_override {
248 new( &get_ref(dst,dindex) ) T( get_ref( const_cast<page&>(src), sindex ) );
249 }
250
251#if __TBB_CPP11_RVALUE_REF_PRESENT
252 virtual void move_page_item( page& dst, size_t dindex, const page& src, size_t sindex ) __TBB_override {
253 new( &get_ref(dst,dindex) ) T( std::move(get_ref( const_cast<page&>(src), sindex )) );
254 }
255#else
256 virtual void move_page_item( page&, size_t, const page&, size_t ) __TBB_override {
257 __TBB_ASSERT( false, "Unreachable code" );
258 }
259#endif
260
261 virtual void assign_and_destroy_item( void* dst, page& src, size_t index ) __TBB_override {
262 T& from = get_ref(src,index);
263 destroyer d(from);
264 *static_cast<T*>(dst) = tbb::internal::move( from );
265 }
266
268 size_t n = sizeof(padded_page) + (items_per_page-1)*sizeof(T);
269 page *p = reinterpret_cast<page*>(my_allocator.allocate( n ));
270 if( !p )
272 return p;
273 }
274
276 size_t n = sizeof(padded_page) + (items_per_page-1)*sizeof(T);
277 my_allocator.deallocate( reinterpret_cast<char*>(p), n );
278 }
279
280public:
282 typedef T value_type;
283
285 typedef A allocator_type;
286
288 typedef T& reference;
289
291 typedef const T& const_reference;
292
294
296 typedef std::ptrdiff_t size_type;
297
299 typedef std::ptrdiff_t difference_type;
300
303 concurrent_queue_base_v8( sizeof(T) ), my_allocator( a )
304 {
305 }
306
309 : concurrent_queue_base_v8( sizeof(T) ), my_allocator( a )
310 {
311 assign( src );
312 }
313
314#if __TBB_CPP11_RVALUE_REF_PRESENT
318 {
319 internal_swap( src );
320 }
321
323 : concurrent_queue_base_v8( sizeof(T) ), my_allocator( a )
324 {
325 // checking that memory allocated by one instance of allocator can be deallocated
326 // with another
327 if( my_allocator == src.my_allocator) {
328 this->internal_swap( src );
329 } else {
330 // allocators are different => performing per-element move
331 this->move_content( src );
332 src.clear();
333 }
334 }
335#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
336
338 template<typename InputIterator>
339 concurrent_bounded_queue( InputIterator begin, InputIterator end,
340 const allocator_type& a = allocator_type())
341 : concurrent_queue_base_v8( sizeof(T) ), my_allocator( a )
342 {
343 for( ; begin != end; ++begin )
345 }
346
349
351 void push( const T& source ) {
352 internal_push( &source );
353 }
354
355#if __TBB_CPP11_RVALUE_REF_PRESENT
357 void push( T&& source ) {
358 internal_push_move( &source );
359 }
360
361#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
362 template<typename... Arguments>
363 void emplace( Arguments&&... args ) {
364 push( T(std::forward<Arguments>( args )...) );
365 }
366#endif /* __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT */
367#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
368
370
371 void pop( T& destination ) {
372 internal_pop( &destination );
373 }
374
375#if TBB_USE_EXCEPTIONS
377 void abort() {
379 }
380#endif
381
383
385 bool try_push( const T& source ) {
386 return internal_push_if_not_full( &source );
387 }
388
389#if __TBB_CPP11_RVALUE_REF_PRESENT
391
393 bool try_push( T&& source ) {
394 return internal_push_move_if_not_full( &source );
395 }
396#if __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT
397 template<typename... Arguments>
398 bool try_emplace( Arguments&&... args ) {
399 return try_push( T(std::forward<Arguments>( args )...) );
400 }
401#endif /* __TBB_CPP11_VARIADIC_TEMPLATES_PRESENT */
402#endif /* __TBB_CPP11_RVALUE_REF_PRESENT */
403
405
407 bool try_pop( T& destination ) {
408 return internal_pop_if_present( &destination );
409 }
410
412
415 size_type size() const {return internal_size();}
416
418 bool empty() const {return internal_empty();}
419
422 return my_capacity;
423 }
424
426
428 void set_capacity( size_type new_capacity ) {
429 internal_set_capacity( new_capacity, sizeof(T) );
430 }
431
433 allocator_type get_allocator() const { return this->my_allocator; }
434
436 void clear() ;
437
440
441 //------------------------------------------------------------------------
442 // The iterators are intended only for debugging. They are slow and not thread safe.
443 //------------------------------------------------------------------------
444 iterator unsafe_begin() {return iterator(*this);}
448
449};
450
451#if __TBB_CPP17_DEDUCTION_GUIDES_PRESENT
452// guide for concurrent_bounded_queue(InputIterator, InputIterator, ...)
453template<typename InputIterator,
454 typename T = typename std::iterator_traits<InputIterator>::value_type,
455 typename A = cache_aligned_allocator<T>
456> concurrent_bounded_queue(InputIterator, InputIterator, const A& = A())
457-> concurrent_bounded_queue<T, A>;
458#endif /* __TBB_CPP17_DEDUCTION_GUIDES_PRESENT */
459
460template<typename T, class A>
462 clear();
463 internal_finish_clear();
464}
465
466template<typename T, class A>
468 T value;
469 while( try_pop(value) ) /*noop*/;
470}
471
473
474} // namespace tbb
475
477#undef __TBB_concurrent_queue_H_include_area
478
479#endif /* __TBB_concurrent_queue_H */
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
#define __TBB_override
Definition: tbb_stddef.h:240
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp end
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp begin
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
void const char const char int ITT_FORMAT __itt_group_sync p
STL namespace.
The graph class.
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()
auto last(Container &c) -> decltype(begin(c))
Meets "allocator" requirements of ISO C++ Standard, Section 20.1.5.
A high-performance thread-safe non-blocking concurrent queue.
static void move_construct_item(T *location, const void *src)
concurrent_queue(concurrent_queue &&src, const allocator_type &a)
tbb::internal::allocator_rebind< A, char >::type page_allocator_type
Allocator type.
const_iterator unsafe_end() const
size_type unsafe_size() const
Return the number of items in the queue; thread unsafe.
static void copy_construct_item(T *location, const void *src)
concurrent_queue(InputIterator begin, InputIterator end, const allocator_type &a=allocator_type())
[begin,end) constructor
const T & const_reference
Const reference type.
concurrent_queue(const allocator_type &a=allocator_type())
Construct empty queue.
virtual void deallocate_block(void *b, size_t n) __TBB_override
Deallocates block created by allocate_block.
ptrdiff_t difference_type
Difference type for iterator.
internal::concurrent_queue_iterator< concurrent_queue, const T > const_iterator
void emplace(Arguments &&... args)
void push(const T &source)
Enqueue an item at tail of queue.
size_t size_type
Integral type for representing size of the queue.
virtual void * allocate_block(size_t n) __TBB_override
Allocates a block of size n (bytes)
bool try_pop(T &result)
Attempt to dequeue an item from head of queue.
internal::concurrent_queue_iterator< concurrent_queue, T > iterator
const_iterator unsafe_begin() const
concurrent_queue(concurrent_queue &&src)
Move constructors.
void clear()
Clear the queue. not thread-safe.
bool empty() const
Equivalent to size()==0.
concurrent_queue(const concurrent_queue &src, const allocator_type &a=allocator_type())
Copy constructor.
allocator_type get_allocator() const
Return allocator object.
T value_type
Element type in the queue.
A high-performance thread-safe blocking concurrent bounded queue.
bool try_push(const T &source)
Enqueue an item at tail of queue if queue is not already full.
void emplace(Arguments &&... args)
internal::concurrent_queue_iterator< concurrent_bounded_queue, const T > const_iterator
concurrent_bounded_queue(concurrent_bounded_queue &&src)
Move constructors.
void clear()
clear the queue. not thread-safe.
bool try_pop(T &destination)
Attempt to dequeue an item from head of queue.
size_type size() const
Return number of pushes minus number of pops.
virtual void deallocate_page(page *p) __TBB_override
custom de-allocator
internal::concurrent_queue_iterator< concurrent_bounded_queue, T > iterator
virtual void move_page_item(page &dst, size_t dindex, const page &src, size_t sindex) __TBB_override
concurrent_queue_base_v3::padded_page< T > padded_page
T & get_ref(page &p, size_t index)
bool try_emplace(Arguments &&... args)
virtual void copy_page_item(page &dst, size_t dindex, const page &src, size_t sindex) __TBB_override
bool empty() const
Equivalent to size()<=0.
void push(T &&source)
Move an item at tail of queue.
T value_type
Element type in the queue.
std::ptrdiff_t difference_type
Difference type for iterator.
void set_capacity(size_type new_capacity)
Set the capacity.
virtual page * allocate_page() __TBB_override
custom allocator
concurrent_bounded_queue(const allocator_type &a=allocator_type())
Construct empty queue.
void pop(T &destination)
Dequeue item from head of queue.
const_iterator unsafe_begin() const
virtual void assign_and_destroy_item(void *dst, page &src, size_t index) __TBB_override
bool try_push(T &&source)
Move an item at tail of queue if queue is not already full.
size_type capacity() const
Maximum number of allowed elements.
tbb::internal::allocator_rebind< A, char >::type page_allocator_type
concurrent_queue_base_v3::copy_specifics copy_specifics
virtual void move_item(page &dst, size_t index, const void *src) __TBB_override
concurrent_bounded_queue(const concurrent_bounded_queue &src, const allocator_type &a=allocator_type())
Copy constructor.
page_allocator_type my_allocator
Allocator type.
allocator_type get_allocator() const
return allocator object
~concurrent_bounded_queue()
Destroy queue.
const_iterator unsafe_end() const
void push(const T &source)
Enqueue an item at tail of queue.
std::ptrdiff_t size_type
Integral type for representing size of the queue.
concurrent_bounded_queue(concurrent_bounded_queue &&src, const allocator_type &a)
virtual void copy_item(page &dst, size_t index, const void *src) __TBB_override
const T & const_reference
Const reference type.
concurrent_bounded_queue(InputIterator begin, InputIterator end, const allocator_type &a=allocator_type())
[begin,end) constructor
Class used to ensure exception-safety of method "pop".
allocator_traits< Alloc >::template rebind_alloc< T >::other type
void internal_push(const void *src, item_constructor_t construct_item)
Enqueue item at tail of queue.
void internal_swap(concurrent_queue_base_v3 &src)
swap internal representation
void assign(const concurrent_queue_base_v3 &src, item_constructor_t construct_item)
copy or move internal representation
bool internal_empty() const
check if the queue is empty; thread safe
size_t internal_size() const
Get size of queue; result may be invalid if queue is modified concurrently.
bool internal_try_pop(void *dst)
Attempt to dequeue item from queue.
Meets requirements of a forward iterator for STL.
Meets requirements of a forward iterator for STL.
void __TBB_EXPORTED_METHOD internal_pop(void *dst)
Dequeue item from head of queue.
void __TBB_EXPORTED_METHOD internal_abort()
Abort all pending queue operations.
void __TBB_EXPORTED_METHOD assign(const concurrent_queue_base_v3 &src)
copy internal representation
void __TBB_EXPORTED_METHOD internal_set_capacity(ptrdiff_t capacity, size_t element_size)
Set the queue capacity.
void __TBB_EXPORTED_METHOD internal_push(const void *src)
Enqueue item at tail of queue using copy operation.
bool __TBB_EXPORTED_METHOD internal_push_if_not_full(const void *src)
Attempt to enqueue item onto queue using copy operation.
bool __TBB_EXPORTED_METHOD internal_pop_if_present(void *dst)
Attempt to dequeue item from queue.
ptrdiff_t my_capacity
Capacity of the queue.
void internal_swap(concurrent_queue_base_v3 &src)
swap queues
ptrdiff_t __TBB_EXPORTED_METHOD internal_size() const
Get size of queue.
bool __TBB_EXPORTED_METHOD internal_empty() const
Check if the queue is empty.
bool __TBB_EXPORTED_METHOD internal_push_move_if_not_full(const void *src)
Attempt to enqueue item onto queue using move operation.
void __TBB_EXPORTED_METHOD internal_push_move(const void *src)
Enqueue item at tail of queue using move operation.
void __TBB_EXPORTED_METHOD move_content(concurrent_queue_base_v8 &src)
move items
Base class for types that should not be copied or assigned.
Definition: tbb_stddef.h:330

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.