2
* Copyright Andrey Semashev 2007 - 2013.
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)
8
* \file threadsafe_queue.hpp
9
* \author Andrey Semashev
12
* \brief This header is the Boost.Log library implementation, see the library documentation
13
* at http://www.boost.org/libs/log/doc/log.html.
16
#ifndef BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_
17
#define BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_
19
#include <boost/log/detail/config.hpp>
21
#ifdef BOOST_LOG_HAS_PRAGMA_ONCE
25
#ifndef BOOST_LOG_NO_THREADS
30
#include <boost/aligned_storage.hpp>
31
#include <boost/move/core.hpp>
32
#include <boost/move/utility.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>
39
BOOST_LOG_OPEN_NAMESPACE
43
//! Base class for the thread-safe queue implementation
44
struct threadsafe_queue_impl
48
// Explicitly mark the type so that it may alias other types
49
__attribute__ ((__may_alias__))
56
type_with_alignment< 2 * sizeof(void*) >::type alignment;
65
static BOOST_LOG_API threadsafe_queue_impl* create(node_base* first_node);
67
static BOOST_LOG_API void* operator new (std::size_t size);
68
static BOOST_LOG_API void operator delete (void* p, std::size_t);
70
virtual ~threadsafe_queue_impl() {}
71
virtual node_base* reset_last_node() = 0;
72
virtual bool unsafe_empty() = 0;
73
virtual void push(node_base* p) = 0;
74
virtual bool try_pop(node_base*& node_to_free, node_base*& node_with_value) = 0;
77
//! A helper class to compose some of the types used by the queue
78
template< typename T, typename AllocatorT >
79
struct threadsafe_queue_types
82
public threadsafe_queue_impl::node_base
84
typedef typename aligned_storage< sizeof(T), alignment_of< T >::value >::type storage_type;
88
explicit node(T const& val) { new (storage.address()) T(val); }
89
T& value() { return *static_cast< T* >(storage.address()); }
90
void destroy() { static_cast< T* >(storage.address())->~T(); }
93
typedef typename AllocatorT::BOOST_NESTED_TEMPLATE rebind< node >::other allocator_type;
97
* \brief An unbounded thread-safe queue
99
* The implementation is based on algorithms published in the "Simple, Fast,
100
* and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" article
101
* in PODC96 by Maged M. Michael and Michael L. Scott. Pseudocode is available here:
102
* http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html
104
* The implementation provides thread-safe \c push and \c try_pop operations, as well as
105
* a thread-unsafe \c empty operation. The queue imposes the following requirements
106
* on the element type:
108
* \li Default constructible, the default constructor must not throw.
109
* \li Copy constructible.
110
* \li Movable (i.e. there should be an efficient move assignment for this type).
112
* The last requirement is not mandatory but is crucial for decent performance.
114
template< typename T, typename AllocatorT = std::allocator< void > >
115
class threadsafe_queue :
116
private threadsafe_queue_types< T, AllocatorT >::allocator_type
119
typedef typename threadsafe_queue_types< T, AllocatorT >::allocator_type base_type;
120
typedef typename threadsafe_queue_types< T, AllocatorT >::node node;
122
//! A simple scope guard to automate memory reclaiming
123
struct auto_deallocate;
124
friend struct auto_deallocate;
125
struct auto_deallocate
127
auto_deallocate(base_type* alloc, node* dealloc, node* destr) :
129
m_pDeallocate(dealloc),
135
m_pAllocator->deallocate(m_pDeallocate, 1);
136
m_pDestroy->destroy();
140
base_type* m_pAllocator;
146
typedef T value_type;
147
typedef T& reference;
148
typedef T const& const_reference;
150
typedef T const* const_pointer;
151
typedef std::ptrdiff_t difference_type;
152
typedef std::size_t size_type;
153
typedef AllocatorT allocator_type;
157
* Default constructor, creates an empty queue. Unlike most containers,
158
* the constructor requires memory allocation.
160
* \throw std::bad_alloc if there is not sufficient memory
162
threadsafe_queue(base_type const& alloc = base_type()) :
165
node* p = base_type::allocate(1);
173
m_pImpl = threadsafe_queue_impl::create(p);
183
base_type::deallocate(p, 1);
188
throw std::bad_alloc();
199
while (try_pop(value));
202
// Remove the last dummy node
203
node* p = static_cast< node* >(m_pImpl->reset_last_node());
205
base_type::deallocate(p, 1);
211
* Checks if the queue is empty. Not thread-safe, the returned result may not be actual.
213
bool unsafe_empty() const { return m_pImpl->unsafe_empty(); }
216
* Puts a new element to the end of the queue. Thread-safe, can be called
217
* concurrently by several threads, and concurrently with the \c pop operation.
219
void push(const_reference value)
221
node* p = base_type::allocate(1);
230
base_type::deallocate(p, 1);
236
throw std::bad_alloc();
240
* Attempts to pop an element from the beginning of the queue. Thread-safe, can
241
* be called concurrently with the \c push operation. Should not be called by
242
* several threads concurrently.
244
bool try_pop(reference value)
246
threadsafe_queue_impl::node_base *dealloc, *destr;
247
if (m_pImpl->try_pop(dealloc, destr))
249
register node* p = static_cast< node* >(destr);
250
auto_deallocate guard(static_cast< base_type* >(this), static_cast< node* >(dealloc), p);
251
value = boost::move(p->value());
259
// Copying and assignment is prohibited
260
threadsafe_queue(threadsafe_queue const&);
261
threadsafe_queue& operator= (threadsafe_queue const&);
264
//! Pointer to the implementation
265
threadsafe_queue_impl* m_pImpl;
270
BOOST_LOG_CLOSE_NAMESPACE // namespace log
274
#include <boost/log/detail/footer.hpp>
276
#endif // BOOST_LOG_NO_THREADS
278
#endif // BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_
added
removed
boost/includes/boost/log/detail/threadsafe_queue.hpp
