Chris@16: /*
Chris@101:  *          Copyright Andrey Semashev 2007 - 2015.
Chris@16:  * Distributed under the Boost Software License, Version 1.0.
Chris@16:  *    (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:  *          http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  */
Chris@16: /*!
Chris@16:  * \file   threadsafe_queue.hpp
Chris@16:  * \author Andrey Semashev
Chris@16:  * \date   05.11.2010
Chris@16:  *
Chris@16:  * \brief  This header is the Boost.Log library implementation, see the library documentation
Chris@16:  *         at http://www.boost.org/doc/libs/release/libs/log/doc/html/index.html.
Chris@16:  */
Chris@16: 
Chris@16: #ifndef BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_
Chris@16: #define BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_
Chris@16: 
Chris@16: #include <boost/log/detail/config.hpp>
Chris@16: 
Chris@16: #ifdef BOOST_HAS_PRAGMA_ONCE
Chris@16: #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #ifndef BOOST_LOG_NO_THREADS
Chris@16: 
Chris@16: #include <new>
Chris@16: #include <memory>
Chris@16: #include <cstddef>
Chris@16: #include <boost/aligned_storage.hpp>
Chris@16: #include <boost/move/core.hpp>
Chris@16: #include <boost/move/utility.hpp>
Chris@16: #include <boost/type_traits/alignment_of.hpp>
Chris@16: #include <boost/type_traits/type_with_alignment.hpp>
Chris@16: #include <boost/log/detail/header.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16: BOOST_LOG_OPEN_NAMESPACE
Chris@16: 
Chris@16: namespace aux {
Chris@16: 
Chris@16: //! Base class for the thread-safe queue implementation
Chris@16: struct threadsafe_queue_impl
Chris@16: {
Chris@16:     struct
Chris@16: #if defined(__GNUC__)
Chris@16:         // Explicitly mark the type so that it may alias other types
Chris@16:         __attribute__ ((__may_alias__))
Chris@16: #endif
Chris@16:         pointer_storage
Chris@16:     {
Chris@16:         union
Chris@16:         {
Chris@16:             void* data[2];
Chris@16:             type_with_alignment< 2 * sizeof(void*) >::type alignment;
Chris@16:         };
Chris@16:     };
Chris@16: 
Chris@16:     struct node_base
Chris@16:     {
Chris@16:         pointer_storage next;
Chris@16:     };
Chris@16: 
Chris@16:     static BOOST_LOG_API threadsafe_queue_impl* create(node_base* first_node);
Chris@16: 
Chris@16:     static BOOST_LOG_API void* operator new (std::size_t size);
Chris@16:     static BOOST_LOG_API void operator delete (void* p, std::size_t);
Chris@16: 
Chris@16:     virtual ~threadsafe_queue_impl() {}
Chris@16:     virtual node_base* reset_last_node() = 0;
Chris@16:     virtual bool unsafe_empty() = 0;
Chris@16:     virtual void push(node_base* p) = 0;
Chris@16:     virtual bool try_pop(node_base*& node_to_free, node_base*& node_with_value) = 0;
Chris@16: };
Chris@16: 
Chris@16: //! A helper class to compose some of the types used by the queue
Chris@16: template< typename T, typename AllocatorT >
Chris@16: struct threadsafe_queue_types
Chris@16: {
Chris@16:     struct node :
Chris@16:         public threadsafe_queue_impl::node_base
Chris@16:     {
Chris@16:         typedef typename aligned_storage< sizeof(T), alignment_of< T >::value >::type storage_type;
Chris@16:         storage_type storage;
Chris@16: 
Chris@16:         node() {}
Chris@16:         explicit node(T const& val) { new (storage.address()) T(val); }
Chris@16:         T& value() { return *static_cast< T* >(storage.address()); }
Chris@16:         void destroy() { static_cast< T* >(storage.address())->~T(); }
Chris@16:     };
Chris@16: 
Chris@16:     typedef typename AllocatorT::BOOST_NESTED_TEMPLATE rebind< node >::other allocator_type;
Chris@16: };
Chris@16: 
Chris@16: /*!
Chris@16:  * \brief An unbounded thread-safe queue
Chris@16:  *
Chris@16:  * The implementation is based on algorithms published in the "Simple, Fast,
Chris@16:  * and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" article
Chris@16:  * in PODC96 by Maged M. Michael and Michael L. Scott. Pseudocode is available here:
Chris@16:  * http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html
Chris@16:  *
Chris@16:  * The implementation provides thread-safe \c push and \c try_pop operations, as well as
Chris@16:  * a thread-unsafe \c empty operation. The queue imposes the following requirements
Chris@16:  * on the element type:
Chris@16:  *
Chris@16:  * \li Default constructible, the default constructor must not throw.
Chris@16:  * \li Copy constructible.
Chris@16:  * \li Movable (i.e. there should be an efficient move assignment for this type).
Chris@16:  *
Chris@16:  * The last requirement is not mandatory but is crucial for decent performance.
Chris@16:  */
Chris@16: template< typename T, typename AllocatorT = std::allocator< void > >
Chris@16: class threadsafe_queue :
Chris@16:     private threadsafe_queue_types< T, AllocatorT >::allocator_type
Chris@16: {
Chris@16: private:
Chris@16:     typedef typename threadsafe_queue_types< T, AllocatorT >::allocator_type base_type;
Chris@16:     typedef typename threadsafe_queue_types< T, AllocatorT >::node node;
Chris@16: 
Chris@16:     //! A simple scope guard to automate memory reclaiming
Chris@16:     struct auto_deallocate;
Chris@16:     friend struct auto_deallocate;
Chris@16:     struct auto_deallocate
Chris@16:     {
Chris@16:         auto_deallocate(base_type* alloc, node* dealloc, node* destr) :
Chris@16:             m_pAllocator(alloc),
Chris@16:             m_pDeallocate(dealloc),
Chris@16:             m_pDestroy(destr)
Chris@16:         {
Chris@16:         }
Chris@16:         ~auto_deallocate()
Chris@16:         {
Chris@16:             m_pAllocator->deallocate(m_pDeallocate, 1);
Chris@16:             m_pDestroy->destroy();
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         base_type* m_pAllocator;
Chris@16:         node* m_pDeallocate;
Chris@16:         node* m_pDestroy;
Chris@16:     };
Chris@16: 
Chris@16: public:
Chris@16:     typedef T value_type;
Chris@16:     typedef T& reference;
Chris@16:     typedef T const& const_reference;
Chris@16:     typedef T* pointer;
Chris@16:     typedef T const* const_pointer;
Chris@16:     typedef std::ptrdiff_t difference_type;
Chris@16:     typedef std::size_t size_type;
Chris@16:     typedef AllocatorT allocator_type;
Chris@16: 
Chris@16: public:
Chris@16:     /*!
Chris@16:      * Default constructor, creates an empty queue. Unlike most containers,
Chris@16:      * the constructor requires memory allocation.
Chris@16:      *
Chris@16:      * \throw std::bad_alloc if there is not sufficient memory
Chris@16:      */
Chris@16:     threadsafe_queue(base_type const& alloc = base_type()) :
Chris@16:         base_type(alloc)
Chris@16:     {
Chris@16:         node* p = base_type::allocate(1);
Chris@16:         if (p)
Chris@16:         {
Chris@16:             try
Chris@16:             {
Chris@16:                 new (p) node();
Chris@16:                 try
Chris@16:                 {
Chris@16:                     m_pImpl = threadsafe_queue_impl::create(p);
Chris@16:                 }
Chris@16:                 catch (...)
Chris@16:                 {
Chris@16:                     p->~node();
Chris@16:                     throw;
Chris@16:                 }
Chris@16:             }
Chris@16:             catch (...)
Chris@16:             {
Chris@16:                 base_type::deallocate(p, 1);
Chris@16:                 throw;
Chris@16:             }
Chris@16:         }
Chris@16:         else
Chris@16:             throw std::bad_alloc();
Chris@16:     }
Chris@16:     /*!
Chris@16:      * Destructor
Chris@16:      */
Chris@16:     ~threadsafe_queue()
Chris@16:     {
Chris@16:         // Clear the queue
Chris@16:         if (!unsafe_empty())
Chris@16:         {
Chris@16:             value_type value;
Chris@16:             while (try_pop(value));
Chris@16:         }
Chris@16: 
Chris@16:         // Remove the last dummy node
Chris@16:         node* p = static_cast< node* >(m_pImpl->reset_last_node());
Chris@16:         p->~node();
Chris@16:         base_type::deallocate(p, 1);
Chris@16: 
Chris@16:         delete m_pImpl;
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:      * Checks if the queue is empty. Not thread-safe, the returned result may not be actual.
Chris@16:      */
Chris@16:     bool unsafe_empty() const { return m_pImpl->unsafe_empty(); }
Chris@16: 
Chris@16:     /*!
Chris@16:      * Puts a new element to the end of the queue. Thread-safe, can be called
Chris@16:      * concurrently by several threads, and concurrently with the \c pop operation.
Chris@16:      */
Chris@16:     void push(const_reference value)
Chris@16:     {
Chris@16:         node* p = base_type::allocate(1);
Chris@16:         if (p)
Chris@16:         {
Chris@16:             try
Chris@16:             {
Chris@16:                 new (p) node(value);
Chris@16:             }
Chris@16:             catch (...)
Chris@16:             {
Chris@16:                 base_type::deallocate(p, 1);
Chris@16:                 throw;
Chris@16:             }
Chris@16:             m_pImpl->push(p);
Chris@16:         }
Chris@16:         else
Chris@16:             throw std::bad_alloc();
Chris@16:     }
Chris@16: 
Chris@16:     /*!
Chris@16:      * Attempts to pop an element from the beginning of the queue. Thread-safe, can
Chris@16:      * be called concurrently with the \c push operation. Should not be called by
Chris@16:      * several threads concurrently.
Chris@16:      */
Chris@16:     bool try_pop(reference value)
Chris@16:     {
Chris@16:         threadsafe_queue_impl::node_base *dealloc, *destr;
Chris@16:         if (m_pImpl->try_pop(dealloc, destr))
Chris@16:         {
Chris@101:             node* p = static_cast< node* >(destr);
Chris@16:             auto_deallocate guard(static_cast< base_type* >(this), static_cast< node* >(dealloc), p);
Chris@16:             value = boost::move(p->value());
Chris@16:             return true;
Chris@16:         }
Chris@16:         else
Chris@16:             return false;
Chris@16:     }
Chris@16: 
Chris@16:     // Copying and assignment is prohibited
Chris@16:     BOOST_DELETED_FUNCTION(threadsafe_queue(threadsafe_queue const&))
Chris@16:     BOOST_DELETED_FUNCTION(threadsafe_queue& operator= (threadsafe_queue const&))
Chris@16: 
Chris@16: private:
Chris@16:     //! Pointer to the implementation
Chris@16:     threadsafe_queue_impl* m_pImpl;
Chris@16: };
Chris@16: 
Chris@16: } // namespace aux
Chris@16: 
Chris@16: BOOST_LOG_CLOSE_NAMESPACE // namespace log
Chris@16: 
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #include <boost/log/detail/footer.hpp>
Chris@16: 
Chris@16: #endif // BOOST_LOG_NO_THREADS
Chris@16: 
Chris@16: #endif // BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_