ceph/src/boost/libs/log/include/boost/log/detail/threadsafe_queue.hpp

   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_