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