2 Copyright 2005-2010 Intel Corporation. All Rights Reserved.
4 This file is part of Threading Building Blocks.
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.
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.
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
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.
29 #ifndef __TBB_concurrent_queue_H
30 #define __TBB_concurrent_queue_H
32 #include "_concurrent_queue_internal.h"
36 namespace strict_ppl {
38 //! A high-performance thread-safe non-blocking concurrent queue.
39 /** Multiple threads may each push and pop concurrently.
40 Assignment construction is not allowed.
41 @ingroup containers */
42 template<typename T, typename A = cache_aligned_allocator<T> >
43 class concurrent_queue: public internal::concurrent_queue_base_v3<T> {
44 template<typename Container, typename Value> friend class internal::concurrent_queue_iterator;
47 typedef typename A::template rebind<char>::other page_allocator_type;
48 page_allocator_type my_allocator;
50 //! Allocates a block of size n (bytes)
51 /*overide*/ virtual void *allocate_block( size_t n ) {
52 void *b = reinterpret_cast<void*>(my_allocator.allocate( n ));
54 internal::throw_exception(internal::eid_bad_alloc);
58 //! Deallocates block created by allocate_block.
59 /*override*/ virtual void deallocate_block( void *b, size_t n ) {
60 my_allocator.deallocate( reinterpret_cast<char*>(b), n );
64 //! Element type in the queue.
70 //! Const reference type
71 typedef const T& const_reference;
73 //! Integral type for representing size of the queue.
74 typedef size_t size_type;
76 //! Difference type for iterator
77 typedef ptrdiff_t difference_type;
80 typedef A allocator_type;
82 //! Construct empty queue
83 explicit concurrent_queue(const allocator_type& a = allocator_type()) :
88 //! [begin,end) constructor
89 template<typename InputIterator>
90 concurrent_queue( InputIterator begin, InputIterator end, const allocator_type& a = allocator_type()) :
93 for( ; begin != end; ++begin )
94 internal_push(&*begin);
98 concurrent_queue( const concurrent_queue& src, const allocator_type& a = allocator_type()) :
99 internal::concurrent_queue_base_v3<T>(), my_allocator( a )
107 //! Enqueue an item at tail of queue.
108 void push( const T& source ) {
109 internal_push( &source );
112 //! Attempt to dequeue an item from head of queue.
113 /** Does not wait for item to become available.
114 Returns true if successful; false otherwise. */
115 bool try_pop( T& result ) {
116 return internal_try_pop( &result );
119 //! Return the number of items in the queue; thread unsafe
120 size_type unsafe_size() const {return this->internal_size();}
122 //! Equivalent to size()==0.
123 bool empty() const {return this->internal_empty();}
125 //! Clear the queue. not thread-safe.
128 //! Return allocator object
129 allocator_type get_allocator() const { return this->my_allocator; }
131 typedef internal::concurrent_queue_iterator<concurrent_queue,T> iterator;
132 typedef internal::concurrent_queue_iterator<concurrent_queue,const T> const_iterator;
134 //------------------------------------------------------------------------
135 // The iterators are intended only for debugging. They are slow and not thread safe.
136 //------------------------------------------------------------------------
137 iterator unsafe_begin() {return iterator(*this);}
138 iterator unsafe_end() {return iterator();}
139 const_iterator unsafe_begin() const {return const_iterator(*this);}
140 const_iterator unsafe_end() const {return const_iterator();}
143 template<typename T, class A>
144 concurrent_queue<T,A>::~concurrent_queue() {
146 this->internal_finish_clear();
149 template<typename T, class A>
150 void concurrent_queue<T,A>::clear() {
153 this->internal_try_pop(&value);
157 } // namespace strict_ppl
159 //! A high-performance thread-safe blocking concurrent bounded queue.
160 /** This is the pre-PPL TBB concurrent queue which supports boundedness and blocking semantics.
161 Note that method names agree with the PPL-style concurrent queue.
162 Multiple threads may each push and pop concurrently.
163 Assignment construction is not allowed.
164 @ingroup containers */
165 template<typename T, class A = cache_aligned_allocator<T> >
166 class concurrent_bounded_queue: public internal::concurrent_queue_base_v3 {
167 template<typename Container, typename Value> friend class internal::concurrent_queue_iterator;
170 typedef typename A::template rebind<char>::other page_allocator_type;
171 page_allocator_type my_allocator;
173 typedef typename concurrent_queue_base_v3::padded_page<T> padded_page;
175 //! Class used to ensure exception-safety of method "pop"
176 class destroyer: internal::no_copy {
179 destroyer( T& value ) : my_value(value) {}
180 ~destroyer() {my_value.~T();}
183 T& get_ref( page& p, size_t index ) {
184 __TBB_ASSERT( index<items_per_page, NULL );
185 return (&static_cast<padded_page*>(static_cast<void*>(&p))->last)[index];
188 /*override*/ virtual void copy_item( page& dst, size_t index, const void* src ) {
189 new( &get_ref(dst,index) ) T(*static_cast<const T*>(src));
192 /*override*/ virtual void copy_page_item( page& dst, size_t dindex, const page& src, size_t sindex ) {
193 new( &get_ref(dst,dindex) ) T( get_ref( const_cast<page&>(src), sindex ) );
196 /*override*/ virtual void assign_and_destroy_item( void* dst, page& src, size_t index ) {
197 T& from = get_ref(src,index);
199 *static_cast<T*>(dst) = from;
202 /*overide*/ virtual page *allocate_page() {
203 size_t n = sizeof(padded_page) + (items_per_page-1)*sizeof(T);
204 page *p = reinterpret_cast<page*>(my_allocator.allocate( n ));
206 internal::throw_exception(internal::eid_bad_alloc);
210 /*override*/ virtual void deallocate_page( page *p ) {
211 size_t n = sizeof(padded_page) + items_per_page*sizeof(T);
212 my_allocator.deallocate( reinterpret_cast<char*>(p), n );
216 //! Element type in the queue.
217 typedef T value_type;
220 typedef A allocator_type;
223 typedef T& reference;
225 //! Const reference type
226 typedef const T& const_reference;
228 //! Integral type for representing size of the queue.
229 /** Notice that the size_type is a signed integral type.
230 This is because the size can be negative if there are pending pops without corresponding pushes. */
231 typedef std::ptrdiff_t size_type;
233 //! Difference type for iterator
234 typedef std::ptrdiff_t difference_type;
236 //! Construct empty queue
237 explicit concurrent_bounded_queue(const allocator_type& a = allocator_type()) :
238 concurrent_queue_base_v3( sizeof(T) ), my_allocator( a )
243 concurrent_bounded_queue( const concurrent_bounded_queue& src, const allocator_type& a = allocator_type()) :
244 concurrent_queue_base_v3( sizeof(T) ), my_allocator( a )
249 //! [begin,end) constructor
250 template<typename InputIterator>
251 concurrent_bounded_queue( InputIterator begin, InputIterator end, const allocator_type& a = allocator_type()) :
252 concurrent_queue_base_v3( sizeof(T) ), my_allocator( a )
254 for( ; begin != end; ++begin )
255 internal_push_if_not_full(&*begin);
259 ~concurrent_bounded_queue();
261 //! Enqueue an item at tail of queue.
262 void push( const T& source ) {
263 internal_push( &source );
266 //! Dequeue item from head of queue.
267 /** Block until an item becomes available, and then dequeue it. */
268 void pop( T& destination ) {
269 internal_pop( &destination );
272 //! Enqueue an item at tail of queue if queue is not already full.
273 /** Does not wait for queue to become not full.
274 Returns true if item is pushed; false if queue was already full. */
275 bool try_push( const T& source ) {
276 return internal_push_if_not_full( &source );
279 //! Attempt to dequeue an item from head of queue.
280 /** Does not wait for item to become available.
281 Returns true if successful; false otherwise. */
282 bool try_pop( T& destination ) {
283 return internal_pop_if_present( &destination );
286 //! Return number of pushes minus number of pops.
287 /** Note that the result can be negative if there are pops waiting for the
288 corresponding pushes. The result can also exceed capacity() if there
289 are push operations in flight. */
290 size_type size() const {return internal_size();}
292 //! Equivalent to size()<=0.
293 bool empty() const {return internal_empty();}
295 //! Maximum number of allowed elements
296 size_type capacity() const {
301 /** Setting the capacity to 0 causes subsequent try_push operations to always fail,
302 and subsequent push operations to block forever. */
303 void set_capacity( size_type new_capacity ) {
304 internal_set_capacity( new_capacity, sizeof(T) );
307 //! return allocator object
308 allocator_type get_allocator() const { return this->my_allocator; }
310 //! clear the queue. not thread-safe.
313 typedef internal::concurrent_queue_iterator<concurrent_bounded_queue,T> iterator;
314 typedef internal::concurrent_queue_iterator<concurrent_bounded_queue,const T> const_iterator;
316 //------------------------------------------------------------------------
317 // The iterators are intended only for debugging. They are slow and not thread safe.
318 //------------------------------------------------------------------------
319 iterator unsafe_begin() {return iterator(*this);}
320 iterator unsafe_end() {return iterator();}
321 const_iterator unsafe_begin() const {return const_iterator(*this);}
322 const_iterator unsafe_end() const {return const_iterator();}
326 template<typename T, class A>
327 concurrent_bounded_queue<T,A>::~concurrent_bounded_queue() {
329 internal_finish_clear();
332 template<typename T, class A>
333 void concurrent_bounded_queue<T,A>::clear() {
336 internal_pop_if_present(&value);
340 namespace deprecated {
342 //! A high-performance thread-safe blocking concurrent bounded queue.
343 /** This is the pre-PPL TBB concurrent queue which support boundedness and blocking semantics.
344 Note that method names agree with the PPL-style concurrent queue.
345 Multiple threads may each push and pop concurrently.
346 Assignment construction is not allowed.
347 @ingroup containers */
348 template<typename T, class A = cache_aligned_allocator<T> >
349 class concurrent_queue: public concurrent_bounded_queue<T,A> {
350 #if !__TBB_TEMPLATE_FRIENDS_BROKEN
351 template<typename Container, typename Value> friend class internal::concurrent_queue_iterator;
355 //! Construct empty queue
356 explicit concurrent_queue(const A& a = A()) :
357 concurrent_bounded_queue<T,A>( a )
362 concurrent_queue( const concurrent_queue& src, const A& a = A()) :
363 concurrent_bounded_queue<T,A>( src, a )
367 //! [begin,end) constructor
368 template<typename InputIterator>
369 concurrent_queue( InputIterator b /*begin*/, InputIterator e /*end*/, const A& a = A()) :
370 concurrent_bounded_queue<T,A>( b, e, a )
374 //! Enqueue an item at tail of queue if queue is not already full.
375 /** Does not wait for queue to become not full.
376 Returns true if item is pushed; false if queue was already full. */
377 bool push_if_not_full( const T& source ) {
378 return try_push( source );
381 //! Attempt to dequeue an item from head of queue.
382 /** Does not wait for item to become available.
383 Returns true if successful; false otherwise.
384 @deprecated Use try_pop()
386 bool pop_if_present( T& destination ) {
387 return try_pop( destination );
390 typedef typename concurrent_bounded_queue<T,A>::iterator iterator;
391 typedef typename concurrent_bounded_queue<T,A>::const_iterator const_iterator;
393 //------------------------------------------------------------------------
394 // The iterators are intended only for debugging. They are slow and not thread safe.
395 //------------------------------------------------------------------------
396 iterator begin() {return this->unsafe_begin();}
397 iterator end() {return this->unsafe_end();}
398 const_iterator begin() const {return this->unsafe_begin();}
399 const_iterator end() const {return this->unsafe_end();}
406 using deprecated::concurrent_queue;
408 using strict_ppl::concurrent_queue;
413 #endif /* __TBB_concurrent_queue_H */