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
39namespace boost {
40
41BOOST_LOG_OPEN_NAMESPACE
42
43namespace aux {
44
45//! Base class for the thread-safe queue implementation
46class threadsafe_queue_impl
47{
48public:
49 struct node_base
50 {
51 boost::atomic< node_base* > next;
52 };
53
54protected:
55 threadsafe_queue_impl();
56 ~threadsafe_queue_impl();
57
58public:
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
73template< typename T >
74struct 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 */
108template< typename T, typename AllocatorT = use_std_allocator >
109class threadsafe_queue :
110 private boost::log::aux::rebind_alloc< AllocatorT, threadsafe_queue_node< T > >::type
111{
112private:
113 typedef threadsafe_queue_node< T > node;
114
115public:
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
125private:
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
152public:
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
259private:
260 //! Returns the allocator instance
261 allocator_type& get_allocator() BOOST_NOEXCEPT { return *static_cast< allocator_type* >(this); }
262
263private:
264 //! Pointer to the implementation
265 threadsafe_queue_impl* m_pImpl;
266};
267
268} // namespace aux
269
270BOOST_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

source code of boost/libs/log/include/boost/log/detail/threadsafe_queue.hpp