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_queue_H
18#define __TBB_concurrent_queue_H
19
20#include "tbb/tbb_stddef.h"
21#include <new>
22
23namespace tbb {
24
25template<typename T> class concurrent_queue;
26
27//! @cond INTERNAL
28namespace internal {
29
30class concurrent_queue_rep;
31class concurrent_queue_iterator_rep;
32template<typename Container, typename Value> class concurrent_queue_iterator;
33
34//! For internal use only.
35/** Type-independent portion of concurrent_queue.
36 @ingroup containers */
37class concurrent_queue_base: no_copy {
38 //! Internal representation
39 concurrent_queue_rep* my_rep;
40
41 friend class concurrent_queue_rep;
42 friend struct micro_queue;
43 friend class concurrent_queue_iterator_rep;
44 friend class concurrent_queue_iterator_base;
45
46 // In C++ 1998/2003 (but quite likely not beyond), friend micro_queue's rights
47 // do not apply to the declaration of micro_queue::pop_finalizer::my_page,
48 // as a member of a class nested within that friend class, so...
49public:
50 //! Prefix on a page
51 struct page {
52 page* next;
53 uintptr_t mask;
54 };
55
56protected:
57 //! Capacity of the queue
58 ptrdiff_t my_capacity;
59
60 //! Always a power of 2
61 size_t items_per_page;
62
63 //! Size of an item
64 size_t item_size;
65private:
66 virtual void copy_item( page& dst, size_t index, const void* src ) = 0;
67 virtual void assign_and_destroy_item( void* dst, page& src, size_t index ) = 0;
68protected:
69 __TBB_EXPORTED_METHOD concurrent_queue_base( size_t item_size );
70 virtual __TBB_EXPORTED_METHOD ~concurrent_queue_base();
71
72 //! Enqueue item at tail of queue
73 void __TBB_EXPORTED_METHOD internal_push( const void* src );
74
75 //! Dequeue item from head of queue
76 void __TBB_EXPORTED_METHOD internal_pop( void* dst );
77
78 //! Attempt to enqueue item onto queue.
79 bool __TBB_EXPORTED_METHOD internal_push_if_not_full( const void* src );
80
81 //! Attempt to dequeue item from queue.
82 /** NULL if there was no item to dequeue. */
83 bool __TBB_EXPORTED_METHOD internal_pop_if_present( void* dst );
84
85 //! Get size of queue
86 ptrdiff_t __TBB_EXPORTED_METHOD internal_size() const;
87
88 void __TBB_EXPORTED_METHOD internal_set_capacity( ptrdiff_t capacity, size_t element_size );
89};
90
91//! Type-independent portion of concurrent_queue_iterator.
92/** @ingroup containers */
93class concurrent_queue_iterator_base : no_assign{
94 //! concurrent_queue over which we are iterating.
95 /** NULL if one past last element in queue. */
96 concurrent_queue_iterator_rep* my_rep;
97
98 template<typename C, typename T, typename U>
99 friend bool operator==( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j );
100
101 template<typename C, typename T, typename U>
102 friend bool operator!=( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j );
103protected:
104 //! Pointer to current item
105 mutable void* my_item;
106
107 //! Default constructor
108 __TBB_EXPORTED_METHOD concurrent_queue_iterator_base() : my_rep(NULL), my_item(NULL) {}
109
110 //! Copy constructor
111 concurrent_queue_iterator_base( const concurrent_queue_iterator_base& i ) : my_rep(NULL), my_item(NULL) {
112 assign(i);
113 }
114
115 //! Construct iterator pointing to head of queue.
116 concurrent_queue_iterator_base( const concurrent_queue_base& queue );
117
118 //! Assignment
119 void __TBB_EXPORTED_METHOD assign( const concurrent_queue_iterator_base& i );
120
121 //! Advance iterator one step towards tail of queue.
122 void __TBB_EXPORTED_METHOD advance();
123
124 //! Destructor
125 __TBB_EXPORTED_METHOD ~concurrent_queue_iterator_base();
126};
127
128//! Meets requirements of a forward iterator for STL.
129/** Value is either the T or const T type of the container.
130 @ingroup containers */
131template<typename Container, typename Value>
132class concurrent_queue_iterator: public concurrent_queue_iterator_base {
133#if !defined(_MSC_VER) || defined(__INTEL_COMPILER)
134 template<typename T>
135 friend class ::tbb::concurrent_queue;
136#else
137public: // workaround for MSVC
138#endif
139 //! Construct iterator pointing to head of queue.
140 concurrent_queue_iterator( const concurrent_queue_base& queue ) :
141 concurrent_queue_iterator_base(queue)
142 {
143 }
144public:
145 concurrent_queue_iterator() {}
146
147 /** If Value==Container::value_type, then this routine is the copy constructor.
148 If Value==const Container::value_type, then this routine is a conversion constructor. */
149 concurrent_queue_iterator( const concurrent_queue_iterator<Container,typename Container::value_type>& other ) :
150 concurrent_queue_iterator_base(other)
151 {}
152
153 //! Iterator assignment
154 concurrent_queue_iterator& operator=( const concurrent_queue_iterator& other ) {
155 assign(other);
156 return *this;
157 }
158
159 //! Reference to current item
160 Value& operator*() const {
161 return *static_cast<Value*>(my_item);
162 }
163
164 Value* operator->() const {return &operator*();}
165
166 //! Advance to next item in queue
167 concurrent_queue_iterator& operator++() {
168 advance();
169 return *this;
170 }
171
172 //! Post increment
173 Value* operator++(int) {
174 Value* result = &operator*();
175 operator++();
176 return result;
177 }
178}; // concurrent_queue_iterator
179
180template<typename C, typename T, typename U>
181bool operator==( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j ) {
182 return i.my_item==j.my_item;
183}
184
185template<typename C, typename T, typename U>
186bool operator!=( const concurrent_queue_iterator<C,T>& i, const concurrent_queue_iterator<C,U>& j ) {
187 return i.my_item!=j.my_item;
188}
189
190} // namespace internal;
191//! @endcond
192
193//! A high-performance thread-safe queue.
194/** Multiple threads may each push and pop concurrently.
195 Assignment and copy construction are not allowed.
196 @ingroup containers */
197template<typename T>
198class concurrent_queue: public internal::concurrent_queue_base {
199 template<typename Container, typename Value> friend class internal::concurrent_queue_iterator;
200
201 //! Class used to ensure exception-safety of method "pop"
202 class destroyer {
203 T& my_value;
204 public:
205 destroyer( T& value ) : my_value(value) {}
206 ~destroyer() {my_value.~T();}
207 };
208
209 T& get_ref( page& pg, size_t index ) {
210 __TBB_ASSERT( index<items_per_page, NULL );
211 return static_cast<T*>(static_cast<void*>(&pg+1))[index];
212 }
213
214 virtual void copy_item( page& dst, size_t index, const void* src ) __TBB_override {
215 new( &get_ref(dst,index) ) T(*static_cast<const T*>(src));
216 }
217
218 virtual void assign_and_destroy_item( void* dst, page& src, size_t index ) __TBB_override {
219 T& from = get_ref(src,index);
220 destroyer d(from);
221 *static_cast<T*>(dst) = from;
222 }
223
224public:
225 //! Element type in the queue.
226 typedef T value_type;
227
228 //! Reference type
229 typedef T& reference;
230
231 //! Const reference type
232 typedef const T& const_reference;
233
234 //! Integral type for representing size of the queue.
235 /** Note that the size_type is a signed integral type.
236 This is because the size can be negative if there are pending pops without corresponding pushes. */
237 typedef std::ptrdiff_t size_type;
238
239 //! Difference type for iterator
240 typedef std::ptrdiff_t difference_type;
241
242 //! Construct empty queue
243 concurrent_queue() :
244 concurrent_queue_base( sizeof(T) )
245 {
246 }
247
248 //! Destroy queue
249 ~concurrent_queue();
250
251 //! Enqueue an item at tail of queue.
252 void push( const T& source ) {
253 internal_push( &source );
254 }
255
256 //! Dequeue item from head of queue.
257 /** Block until an item becomes available, and then dequeue it. */
258 void pop( T& destination ) {
259 internal_pop( &destination );
260 }
261
262 //! Enqueue an item at tail of queue if queue is not already full.
263 /** Does not wait for queue to become not full.
264 Returns true if item is pushed; false if queue was already full. */
265 bool push_if_not_full( const T& source ) {
266 return internal_push_if_not_full( &source );
267 }
268
269 //! Attempt to dequeue an item from head of queue.
270 /** Does not wait for item to become available.
271 Returns true if successful; false otherwise. */
272 bool pop_if_present( T& destination ) {
273 return internal_pop_if_present( &destination );
274 }
275
276 //! Return number of pushes minus number of pops.
277 /** Note that the result can be negative if there are pops waiting for the
278 corresponding pushes. The result can also exceed capacity() if there
279 are push operations in flight. */
280 size_type size() const {return internal_size();}
281
282 //! Equivalent to size()<=0.
283 bool empty() const {return size()<=0;}
284
285 //! Maximum number of allowed elements
286 size_type capacity() const {
287 return my_capacity;
288 }
289
290 //! Set the capacity
291 /** Setting the capacity to 0 causes subsequent push_if_not_full operations to always fail,
292 and subsequent push operations to block forever. */
293 void set_capacity( size_type new_capacity ) {
294 internal_set_capacity( new_capacity, sizeof(T) );
295 }
296
297 typedef internal::concurrent_queue_iterator<concurrent_queue,T> iterator;
298 typedef internal::concurrent_queue_iterator<concurrent_queue,const T> const_iterator;
299
300 //------------------------------------------------------------------------
301 // The iterators are intended only for debugging. They are slow and not thread safe.
302 //------------------------------------------------------------------------
303 iterator begin() {return iterator(*this);}
304 iterator end() {return iterator();}
305 const_iterator begin() const {return const_iterator(*this);}
306 const_iterator end() const {return const_iterator();}
307
308};
309
310template<typename T>
311concurrent_queue<T>::~concurrent_queue() {
312 while( !empty() ) {
313 T value;
314 internal_pop(&value);
315 }
316}
317
318} // namespace tbb
319
320#endif /* __TBB_concurrent_queue_H */
321