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 | |
23 | namespace tbb { |
24 | |
25 | template<typename T> class concurrent_queue; |
26 | |
27 | //! @cond INTERNAL |
28 | namespace internal { |
29 | |
30 | class concurrent_queue_rep; |
31 | class concurrent_queue_iterator_rep; |
32 | template<typename Container, typename Value> class concurrent_queue_iterator; |
33 | |
34 | //! For internal use only. |
35 | /** Type-independent portion of concurrent_queue. |
36 | @ingroup containers */ |
37 | class 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... |
49 | public: |
50 | //! Prefix on a page |
51 | struct page { |
52 | page* next; |
53 | uintptr_t mask; |
54 | }; |
55 | |
56 | protected: |
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; |
65 | private: |
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; |
68 | protected: |
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 */ |
93 | class 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 ); |
103 | protected: |
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 */ |
131 | template<typename Container, typename Value> |
132 | class 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 |
137 | public: // 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 | } |
144 | public: |
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 | |
180 | template<typename C, typename T, typename U> |
181 | bool 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 | |
185 | template<typename C, typename T, typename U> |
186 | bool 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 */ |
197 | template<typename T> |
198 | class 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 | |
224 | public: |
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 | |
310 | template<typename T> |
311 | concurrent_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 | |