]>
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> | |
35 | #include <boost/log/detail/header.hpp> | |
36 | ||
37 | namespace boost { | |
38 | ||
39 | BOOST_LOG_OPEN_NAMESPACE | |
40 | ||
41 | namespace aux { | |
42 | ||
43 | //! Base class for the thread-safe queue implementation | |
44 | struct threadsafe_queue_impl | |
45 | { | |
46 | struct BOOST_LOG_MAY_ALIAS pointer_storage | |
47 | { | |
48 | union | |
49 | { | |
50 | void* data[2]; | |
51 | type_with_alignment< 2 * sizeof(void*) >::type alignment; | |
52 | }; | |
53 | }; | |
54 | ||
55 | struct node_base | |
56 | { | |
57 | pointer_storage next; | |
58 | }; | |
59 | ||
60 | static BOOST_LOG_API threadsafe_queue_impl* create(node_base* first_node); | |
61 | ||
62 | static BOOST_LOG_API void* operator new (std::size_t size); | |
63 | static BOOST_LOG_API void operator delete (void* p, std::size_t); | |
64 | ||
65 | virtual ~threadsafe_queue_impl() {} | |
66 | virtual node_base* reset_last_node() = 0; | |
67 | virtual bool unsafe_empty() = 0; | |
68 | virtual void push(node_base* p) = 0; | |
69 | virtual bool try_pop(node_base*& node_to_free, node_base*& node_with_value) = 0; | |
70 | }; | |
71 | ||
72 | //! A helper class to compose some of the types used by the queue | |
73 | template< typename T, typename AllocatorT > | |
74 | struct threadsafe_queue_types | |
75 | { | |
76 | struct node : | |
77 | public threadsafe_queue_impl::node_base | |
78 | { | |
79 | typedef typename aligned_storage< sizeof(T), alignment_of< T >::value >::type storage_type; | |
80 | storage_type storage; | |
81 | ||
82 | node() {} | |
83 | explicit node(T const& val) { new (storage.address()) T(val); } | |
84 | T& value() { return *static_cast< T* >(storage.address()); } | |
85 | void destroy() { static_cast< T* >(storage.address())->~T(); } | |
86 | }; | |
87 | ||
88 | typedef typename AllocatorT::BOOST_NESTED_TEMPLATE rebind< node >::other allocator_type; | |
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 : | |
111 | private threadsafe_queue_types< T, AllocatorT >::allocator_type | |
112 | { | |
113 | private: | |
114 | typedef typename threadsafe_queue_types< T, AllocatorT >::allocator_type base_type; | |
115 | typedef typename threadsafe_queue_types< T, AllocatorT >::node node; | |
116 | ||
117 | //! A simple scope guard to automate memory reclaiming | |
118 | struct auto_deallocate; | |
119 | friend struct auto_deallocate; | |
120 | struct auto_deallocate | |
121 | { | |
122 | auto_deallocate(base_type* alloc, node* dealloc, node* destr) : | |
123 | m_pAllocator(alloc), | |
124 | m_pDeallocate(dealloc), | |
125 | m_pDestroy(destr) | |
126 | { | |
127 | } | |
128 | ~auto_deallocate() | |
129 | { | |
130 | m_pAllocator->deallocate(m_pDeallocate, 1); | |
131 | m_pDestroy->destroy(); | |
132 | } | |
133 | ||
134 | private: | |
135 | base_type* m_pAllocator; | |
136 | node* m_pDeallocate; | |
137 | node* m_pDestroy; | |
138 | }; | |
139 | ||
140 | public: | |
141 | typedef T value_type; | |
142 | typedef T& reference; | |
143 | typedef T const& const_reference; | |
144 | typedef T* pointer; | |
145 | typedef T const* const_pointer; | |
146 | typedef std::ptrdiff_t difference_type; | |
147 | typedef std::size_t size_type; | |
148 | typedef AllocatorT allocator_type; | |
149 | ||
150 | public: | |
151 | /*! | |
152 | * Default constructor, creates an empty queue. Unlike most containers, | |
153 | * the constructor requires memory allocation. | |
154 | * | |
155 | * \throw std::bad_alloc if there is not sufficient memory | |
156 | */ | |
157 | threadsafe_queue(base_type const& alloc = base_type()) : | |
158 | base_type(alloc) | |
159 | { | |
160 | node* p = base_type::allocate(1); | |
161 | if (p) | |
162 | { | |
163 | try | |
164 | { | |
165 | new (p) node(); | |
166 | try | |
167 | { | |
168 | m_pImpl = threadsafe_queue_impl::create(p); | |
169 | } | |
170 | catch (...) | |
171 | { | |
172 | p->~node(); | |
173 | throw; | |
174 | } | |
175 | } | |
176 | catch (...) | |
177 | { | |
178 | base_type::deallocate(p, 1); | |
179 | throw; | |
180 | } | |
181 | } | |
182 | else | |
183 | throw std::bad_alloc(); | |
184 | } | |
185 | /*! | |
186 | * Destructor | |
187 | */ | |
188 | ~threadsafe_queue() | |
189 | { | |
190 | // Clear the queue | |
191 | if (!unsafe_empty()) | |
192 | { | |
193 | value_type value; | |
194 | while (try_pop(value)); | |
195 | } | |
196 | ||
197 | // Remove the last dummy node | |
198 | node* p = static_cast< node* >(m_pImpl->reset_last_node()); | |
199 | p->~node(); | |
200 | base_type::deallocate(p, 1); | |
201 | ||
202 | delete m_pImpl; | |
203 | } | |
204 | ||
205 | /*! | |
206 | * Checks if the queue is empty. Not thread-safe, the returned result may not be actual. | |
207 | */ | |
208 | bool unsafe_empty() const { return m_pImpl->unsafe_empty(); } | |
209 | ||
210 | /*! | |
211 | * Puts a new element to the end of the queue. Thread-safe, can be called | |
212 | * concurrently by several threads, and concurrently with the \c pop operation. | |
213 | */ | |
214 | void push(const_reference value) | |
215 | { | |
216 | node* p = base_type::allocate(1); | |
217 | if (p) | |
218 | { | |
219 | try | |
220 | { | |
221 | new (p) node(value); | |
222 | } | |
223 | catch (...) | |
224 | { | |
225 | base_type::deallocate(p, 1); | |
226 | throw; | |
227 | } | |
228 | m_pImpl->push(p); | |
229 | } | |
230 | else | |
231 | throw std::bad_alloc(); | |
232 | } | |
233 | ||
234 | /*! | |
235 | * Attempts to pop an element from the beginning of the queue. Thread-safe, can | |
236 | * be called concurrently with the \c push operation. Should not be called by | |
237 | * several threads concurrently. | |
238 | */ | |
239 | bool try_pop(reference value) | |
240 | { | |
241 | threadsafe_queue_impl::node_base *dealloc, *destr; | |
242 | if (m_pImpl->try_pop(dealloc, destr)) | |
243 | { | |
244 | node* p = static_cast< node* >(destr); | |
245 | auto_deallocate guard(static_cast< base_type* >(this), static_cast< node* >(dealloc), p); | |
246 | value = boost::move(p->value()); | |
247 | return true; | |
248 | } | |
249 | else | |
250 | return false; | |
251 | } | |
252 | ||
253 | // Copying and assignment is prohibited | |
254 | BOOST_DELETED_FUNCTION(threadsafe_queue(threadsafe_queue const&)) | |
255 | BOOST_DELETED_FUNCTION(threadsafe_queue& operator= (threadsafe_queue const&)) | |
256 | ||
257 | private: | |
258 | //! Pointer to the implementation | |
259 | threadsafe_queue_impl* m_pImpl; | |
260 | }; | |
261 | ||
262 | } // namespace aux | |
263 | ||
264 | BOOST_LOG_CLOSE_NAMESPACE // namespace log | |
265 | ||
266 | } // namespace boost | |
267 | ||
268 | #include <boost/log/detail/footer.hpp> | |
269 | ||
270 | #endif // BOOST_LOG_NO_THREADS | |
271 | ||
272 | #endif // BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_ |