1 | /* |
2 | * Copyright Andrey Semashev 2007 - 2021. |
3 | * Distributed under the Boost Software License, Version 1.0. |
4 | * (See accompanying file LICENSE_1_0.txt or copy at |
5 | * http://www.boost.org/LICENSE_1_0.txt) |
6 | */ |
7 | /*! |
8 | * \file threadsafe_queue.hpp |
9 | * \author Andrey Semashev |
10 | * \date 05.11.2010 |
11 | * |
12 | * \brief This header is the Boost.Log library implementation, see the library documentation |
13 | * at http://www.boost.org/doc/libs/release/libs/log/doc/html/index.html. |
14 | */ |
15 | |
16 | #ifndef BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_ |
17 | #define BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_ |
18 | |
19 | #include <boost/log/detail/config.hpp> |
20 | |
21 | #ifdef BOOST_HAS_PRAGMA_ONCE |
22 | #pragma once |
23 | #endif |
24 | |
25 | #ifndef BOOST_LOG_NO_THREADS |
26 | |
27 | #include <new> |
28 | #include <memory> |
29 | #include <cstddef> |
30 | #include <boost/atomic/atomic.hpp> |
31 | #include <boost/move/core.hpp> |
32 | #include <boost/move/utility_core.hpp> |
33 | #include <boost/type_traits/alignment_of.hpp> |
34 | #include <boost/type_traits/aligned_storage.hpp> |
35 | #include <boost/log/utility/use_std_allocator.hpp> |
36 | #include <boost/log/detail/allocator_traits.hpp> |
37 | #include <boost/log/detail/header.hpp> |
38 | |
39 | namespace boost { |
40 | |
41 | BOOST_LOG_OPEN_NAMESPACE |
42 | |
43 | namespace aux { |
44 | |
45 | //! Base class for the thread-safe queue implementation |
46 | class threadsafe_queue_impl |
47 | { |
48 | public: |
49 | struct node_base |
50 | { |
51 | boost::atomic< node_base* > next; |
52 | }; |
53 | |
54 | protected: |
55 | threadsafe_queue_impl(); |
56 | ~threadsafe_queue_impl(); |
57 | |
58 | public: |
59 | static BOOST_LOG_API threadsafe_queue_impl* create(node_base* first_node); |
60 | static BOOST_LOG_API void destroy(threadsafe_queue_impl* impl) BOOST_NOEXCEPT; |
61 | |
62 | static BOOST_LOG_API node_base* reset_last_node(threadsafe_queue_impl* impl) BOOST_NOEXCEPT; |
63 | static BOOST_LOG_API bool unsafe_empty(const threadsafe_queue_impl* impl) BOOST_NOEXCEPT; |
64 | static BOOST_LOG_API void push(threadsafe_queue_impl* impl, node_base* p); |
65 | static BOOST_LOG_API bool try_pop(threadsafe_queue_impl* impl, node_base*& node_to_free, node_base*& node_with_value); |
66 | |
67 | // Copying and assignment is prohibited |
68 | BOOST_DELETED_FUNCTION(threadsafe_queue_impl(threadsafe_queue_impl const&)) |
69 | BOOST_DELETED_FUNCTION(threadsafe_queue_impl& operator= (threadsafe_queue_impl const&)) |
70 | }; |
71 | |
72 | //! Thread-safe queue node type |
73 | template< typename T > |
74 | struct threadsafe_queue_node : |
75 | public threadsafe_queue_impl::node_base |
76 | { |
77 | typedef typename aligned_storage< sizeof(T), alignment_of< T >::value >::type storage_type; |
78 | storage_type storage; |
79 | |
80 | BOOST_DEFAULTED_FUNCTION(threadsafe_queue_node(), {}) |
81 | explicit threadsafe_queue_node(T const& val) { new (storage.address()) T(val); } |
82 | T& value() BOOST_NOEXCEPT { return *static_cast< T* >(storage.address()); } |
83 | void destroy() BOOST_NOEXCEPT { static_cast< T* >(storage.address())->~T(); } |
84 | |
85 | // Copying and assignment is prohibited |
86 | BOOST_DELETED_FUNCTION(threadsafe_queue_node(threadsafe_queue_node const&)) |
87 | BOOST_DELETED_FUNCTION(threadsafe_queue_node& operator= (threadsafe_queue_node const&)) |
88 | }; |
89 | |
90 | /*! |
91 | * \brief An unbounded thread-safe queue |
92 | * |
93 | * The implementation is based on algorithms published in the "Simple, Fast, |
94 | * and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" article |
95 | * in PODC96 by Maged M. Michael and Michael L. Scott. Pseudocode is available here: |
96 | * http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html |
97 | * |
98 | * The implementation provides thread-safe \c push and \c try_pop operations, as well as |
99 | * a thread-unsafe \c empty operation. The queue imposes the following requirements |
100 | * on the element type: |
101 | * |
102 | * \li Default constructible, the default constructor must not throw. |
103 | * \li Copy constructible. |
104 | * \li Movable (i.e. there should be an efficient move assignment for this type). |
105 | * |
106 | * The last requirement is not mandatory but is crucial for decent performance. |
107 | */ |
108 | template< typename T, typename AllocatorT = use_std_allocator > |
109 | class threadsafe_queue : |
110 | private boost::log::aux::rebind_alloc< AllocatorT, threadsafe_queue_node< T > >::type |
111 | { |
112 | private: |
113 | typedef threadsafe_queue_node< T > node; |
114 | |
115 | public: |
116 | typedef typename boost::log::aux::rebind_alloc< AllocatorT, node >::type allocator_type; |
117 | typedef T value_type; |
118 | typedef T& reference; |
119 | typedef T const& const_reference; |
120 | typedef T* pointer; |
121 | typedef T const* const_pointer; |
122 | typedef std::ptrdiff_t difference_type; |
123 | typedef std::size_t size_type; |
124 | |
125 | private: |
126 | typedef boost::log::aux::allocator_traits< allocator_type > alloc_traits; |
127 | |
128 | //! A simple scope guard to automate memory reclaiming |
129 | struct auto_deallocate; |
130 | friend struct auto_deallocate; |
131 | struct auto_deallocate |
132 | { |
133 | auto_deallocate(allocator_type* alloc, node* dealloc, node* destr) BOOST_NOEXCEPT : |
134 | m_pAllocator(alloc), |
135 | m_pDeallocate(dealloc), |
136 | m_pDestroy(destr) |
137 | { |
138 | } |
139 | ~auto_deallocate() BOOST_NOEXCEPT |
140 | { |
141 | alloc_traits::destroy(*m_pAllocator, m_pDeallocate); |
142 | alloc_traits::deallocate(*m_pAllocator, m_pDeallocate, 1); |
143 | m_pDestroy->destroy(); |
144 | } |
145 | |
146 | private: |
147 | allocator_type* m_pAllocator; |
148 | node* m_pDeallocate; |
149 | node* m_pDestroy; |
150 | }; |
151 | |
152 | public: |
153 | /*! |
154 | * Default constructor, creates an empty queue. Unlike most containers, |
155 | * the constructor requires memory allocation. |
156 | * |
157 | * \throw std::bad_alloc if there is not sufficient memory |
158 | */ |
159 | threadsafe_queue(allocator_type const& alloc = allocator_type()) : |
160 | allocator_type(alloc) |
161 | { |
162 | node* p = alloc_traits::allocate(get_allocator(), 1); |
163 | if (BOOST_LIKELY(!!p)) |
164 | { |
165 | try |
166 | { |
167 | alloc_traits::construct(get_allocator(), p); |
168 | try |
169 | { |
170 | m_pImpl = threadsafe_queue_impl::create(first_node: p); |
171 | } |
172 | catch (...) |
173 | { |
174 | alloc_traits::destroy(get_allocator(), p); |
175 | throw; |
176 | } |
177 | } |
178 | catch (...) |
179 | { |
180 | alloc_traits::deallocate(get_allocator(), p, 1); |
181 | throw; |
182 | } |
183 | } |
184 | else |
185 | throw std::bad_alloc(); |
186 | } |
187 | /*! |
188 | * Destructor |
189 | */ |
190 | ~threadsafe_queue() BOOST_NOEXCEPT |
191 | { |
192 | // Clear the queue |
193 | if (!unsafe_empty()) |
194 | { |
195 | value_type value; |
196 | while (try_pop(value)) {} |
197 | } |
198 | |
199 | // Remove the last dummy node |
200 | node* p = static_cast< node* >(threadsafe_queue_impl::reset_last_node(impl: m_pImpl)); |
201 | alloc_traits::destroy(get_allocator(), p); |
202 | alloc_traits::deallocate(get_allocator(), p, 1); |
203 | |
204 | threadsafe_queue_impl::destroy(impl: m_pImpl); |
205 | } |
206 | |
207 | /*! |
208 | * Checks if the queue is empty. Not thread-safe, the returned result may not be actual. |
209 | */ |
210 | bool unsafe_empty() const BOOST_NOEXCEPT { return threadsafe_queue_impl::unsafe_empty(impl: m_pImpl); } |
211 | |
212 | /*! |
213 | * Puts a new element to the end of the queue. Thread-safe, can be called |
214 | * concurrently by several threads, and concurrently with the \c pop operation. |
215 | */ |
216 | void push(const_reference value) |
217 | { |
218 | node* p = alloc_traits::allocate(get_allocator(), 1); |
219 | if (BOOST_LIKELY(!!p)) |
220 | { |
221 | try |
222 | { |
223 | alloc_traits::construct(get_allocator(), p, value); |
224 | } |
225 | catch (...) |
226 | { |
227 | alloc_traits::deallocate(get_allocator(), p, 1); |
228 | throw; |
229 | } |
230 | threadsafe_queue_impl::push(impl: m_pImpl, p); |
231 | } |
232 | else |
233 | throw std::bad_alloc(); |
234 | } |
235 | |
236 | /*! |
237 | * Attempts to pop an element from the beginning of the queue. Thread-safe, can |
238 | * be called concurrently with the \c push operation. Should not be called by |
239 | * several threads concurrently. |
240 | */ |
241 | bool try_pop(reference value) |
242 | { |
243 | threadsafe_queue_impl::node_base *dealloc, *destr; |
244 | if (threadsafe_queue_impl::try_pop(impl: m_pImpl, node_to_free&: dealloc, node_with_value&: destr)) |
245 | { |
246 | node* p = static_cast< node* >(destr); |
247 | auto_deallocate guard(static_cast< allocator_type* >(this), static_cast< node* >(dealloc), p); |
248 | value = boost::move(p->value()); |
249 | return true; |
250 | } |
251 | else |
252 | return false; |
253 | } |
254 | |
255 | // Copying and assignment is prohibited |
256 | BOOST_DELETED_FUNCTION(threadsafe_queue(threadsafe_queue const&)) |
257 | BOOST_DELETED_FUNCTION(threadsafe_queue& operator= (threadsafe_queue const&)) |
258 | |
259 | private: |
260 | //! Returns the allocator instance |
261 | allocator_type& get_allocator() BOOST_NOEXCEPT { return *static_cast< allocator_type* >(this); } |
262 | |
263 | private: |
264 | //! Pointer to the implementation |
265 | threadsafe_queue_impl* m_pImpl; |
266 | }; |
267 | |
268 | } // namespace aux |
269 | |
270 | BOOST_LOG_CLOSE_NAMESPACE // namespace log |
271 | |
272 | } // namespace boost |
273 | |
274 | #include <boost/log/detail/footer.hpp> |
275 | |
276 | #endif // BOOST_LOG_NO_THREADS |
277 | |
278 | #endif // BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_ |
279 | |