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/allocator_traits.hpp> 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 ~threadsafe_queue_implboost::aux::threadsafe_queue_impl66 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 73 //! Thread-safe queue node type 74 template< typename T > 75 struct threadsafe_queue_node : 76 public threadsafe_queue_impl::node_base 77 { 78 typedef typename aligned_storage< sizeof(T), alignment_of< T >::value >::type storage_type; 79 storage_type storage; 80 threadsafe_queue_nodeboost::aux::threadsafe_queue_node81 BOOST_DEFAULTED_FUNCTION(threadsafe_queue_node(), {}) 82 explicit threadsafe_queue_node(T const& val) { new (storage.address()) T(val); } valueboost::aux::threadsafe_queue_node83 T& value() BOOST_NOEXCEPT { return *static_cast< T* >(storage.address()); } destroyboost::aux::threadsafe_queue_node84 void destroy() BOOST_NOEXCEPT { static_cast< T* >(storage.address())->~T(); } 85 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&)) 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 boost::log::aux::rebind_alloc< AllocatorT, threadsafe_queue_node< T > >::type 112 { 113 private: 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; 128 129 //! A simple scope guard to automate memory reclaiming 130 struct auto_deallocate; 131 friend struct auto_deallocate; 132 struct auto_deallocate 133 { auto_deallocateboost::aux::threadsafe_queue::auto_deallocate134 auto_deallocate(allocator_type* alloc, node* dealloc, node* destr) BOOST_NOEXCEPT : 135 m_pAllocator(alloc), 136 m_pDeallocate(dealloc), 137 m_pDestroy(destr) 138 { 139 } ~auto_deallocateboost::aux::threadsafe_queue::auto_deallocate140 ~auto_deallocate() BOOST_NOEXCEPT 141 { 142 alloc_traits::destroy(*m_pAllocator, m_pDeallocate); 143 alloc_traits::deallocate(*m_pAllocator, m_pDeallocate, 1); 144 m_pDestroy->destroy(); 145 } 146 147 private: 148 allocator_type* m_pAllocator; 149 node* m_pDeallocate; 150 node* m_pDestroy; 151 }; 152 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 */ threadsafe_queue(allocator_type const & alloc=allocator_type ())160 threadsafe_queue(allocator_type const& alloc = allocator_type()) : 161 allocator_type(alloc) 162 { 163 node* p = alloc_traits::allocate(get_allocator(), 1); 164 if (p) 165 { 166 try 167 { 168 alloc_traits::construct(get_allocator(), p); 169 try 170 { 171 m_pImpl = threadsafe_queue_impl::create(p); 172 } 173 catch (...) 174 { 175 alloc_traits::destroy(get_allocator(), p); 176 throw; 177 } 178 } 179 catch (...) 180 { 181 alloc_traits::deallocate(get_allocator(), p, 1); 182 throw; 183 } 184 } 185 else 186 throw std::bad_alloc(); 187 } 188 /*! 189 * Destructor 190 */ ~threadsafe_queue()191 ~threadsafe_queue() BOOST_NOEXCEPT 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()); 202 alloc_traits::destroy(get_allocator(), p); 203 alloc_traits::deallocate(get_allocator(), p, 1); 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 */ unsafe_empty() const211 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 */ push(const_reference value)217 void push(const_reference value) 218 { 219 node* p = alloc_traits::allocate(get_allocator(), 1); 220 if (p) 221 { 222 try 223 { 224 alloc_traits::construct(get_allocator(), p, value); 225 } 226 catch (...) 227 { 228 alloc_traits::deallocate(get_allocator(), p, 1); 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 */ try_pop(reference value)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); 248 auto_deallocate guard(static_cast< allocator_type* >(this), static_cast< node* >(dealloc), p); 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 260 private: 261 //! Returns the allocator instance get_allocator()262 allocator_type& get_allocator() BOOST_NOEXCEPT { return *static_cast< allocator_type* >(this); } 263 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_ 280