summaryrefslogtreecommitdiff
path: root/boost/log/detail/threadsafe_queue.hpp
blob: b8b3dbe60aef47979a20269b0d30de47c28c0af9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
/*
 *          Copyright Andrey Semashev 2007 - 2015.
 * Distributed under the Boost Software License, Version 1.0.
 *    (See accompanying file LICENSE_1_0.txt or copy at
 *          http://www.boost.org/LICENSE_1_0.txt)
 */
/*!
 * \file   threadsafe_queue.hpp
 * \author Andrey Semashev
 * \date   05.11.2010
 *
 * \brief  This header is the Boost.Log library implementation, see the library documentation
 *         at http://www.boost.org/doc/libs/release/libs/log/doc/html/index.html.
 */

#ifndef BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_
#define BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_

#include <boost/log/detail/config.hpp>

#ifdef BOOST_HAS_PRAGMA_ONCE
#pragma once
#endif

#ifndef BOOST_LOG_NO_THREADS

#include <new>
#include <memory>
#include <cstddef>
#include <boost/aligned_storage.hpp>
#include <boost/move/core.hpp>
#include <boost/move/utility_core.hpp>
#include <boost/type_traits/alignment_of.hpp>
#include <boost/type_traits/type_with_alignment.hpp>
#include <boost/log/detail/header.hpp>

namespace boost {

BOOST_LOG_OPEN_NAMESPACE

namespace aux {

//! Base class for the thread-safe queue implementation
struct threadsafe_queue_impl
{
    struct BOOST_LOG_MAY_ALIAS pointer_storage
    {
        union
        {
            void* data[2];
            type_with_alignment< 2 * sizeof(void*) >::type alignment;
        };
    };

    struct node_base
    {
        pointer_storage next;
    };

    static BOOST_LOG_API threadsafe_queue_impl* create(node_base* first_node);

    static BOOST_LOG_API void* operator new (std::size_t size);
    static BOOST_LOG_API void operator delete (void* p, std::size_t);

    virtual ~threadsafe_queue_impl() {}
    virtual node_base* reset_last_node() = 0;
    virtual bool unsafe_empty() = 0;
    virtual void push(node_base* p) = 0;
    virtual bool try_pop(node_base*& node_to_free, node_base*& node_with_value) = 0;
};

//! A helper class to compose some of the types used by the queue
template< typename T, typename AllocatorT >
struct threadsafe_queue_types
{
    struct node :
        public threadsafe_queue_impl::node_base
    {
        typedef typename aligned_storage< sizeof(T), alignment_of< T >::value >::type storage_type;
        storage_type storage;

        node() {}
        explicit node(T const& val) { new (storage.address()) T(val); }
        T& value() { return *static_cast< T* >(storage.address()); }
        void destroy() { static_cast< T* >(storage.address())->~T(); }
    };

    typedef typename AllocatorT::BOOST_NESTED_TEMPLATE rebind< node >::other allocator_type;
};

/*!
 * \brief An unbounded thread-safe queue
 *
 * The implementation is based on algorithms published in the "Simple, Fast,
 * and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" article
 * in PODC96 by Maged M. Michael and Michael L. Scott. Pseudocode is available here:
 * http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html
 *
 * The implementation provides thread-safe \c push and \c try_pop operations, as well as
 * a thread-unsafe \c empty operation. The queue imposes the following requirements
 * on the element type:
 *
 * \li Default constructible, the default constructor must not throw.
 * \li Copy constructible.
 * \li Movable (i.e. there should be an efficient move assignment for this type).
 *
 * The last requirement is not mandatory but is crucial for decent performance.
 */
template< typename T, typename AllocatorT = std::allocator< void > >
class threadsafe_queue :
    private threadsafe_queue_types< T, AllocatorT >::allocator_type
{
private:
    typedef typename threadsafe_queue_types< T, AllocatorT >::allocator_type base_type;
    typedef typename threadsafe_queue_types< T, AllocatorT >::node node;

    //! A simple scope guard to automate memory reclaiming
    struct auto_deallocate;
    friend struct auto_deallocate;
    struct auto_deallocate
    {
        auto_deallocate(base_type* alloc, node* dealloc, node* destr) :
            m_pAllocator(alloc),
            m_pDeallocate(dealloc),
            m_pDestroy(destr)
        {
        }
        ~auto_deallocate()
        {
            m_pAllocator->deallocate(m_pDeallocate, 1);
            m_pDestroy->destroy();
        }

    private:
        base_type* m_pAllocator;
        node* m_pDeallocate;
        node* m_pDestroy;
    };

public:
    typedef T value_type;
    typedef T& reference;
    typedef T const& const_reference;
    typedef T* pointer;
    typedef T const* const_pointer;
    typedef std::ptrdiff_t difference_type;
    typedef std::size_t size_type;
    typedef AllocatorT allocator_type;

public:
    /*!
     * Default constructor, creates an empty queue. Unlike most containers,
     * the constructor requires memory allocation.
     *
     * \throw std::bad_alloc if there is not sufficient memory
     */
    threadsafe_queue(base_type const& alloc = base_type()) :
        base_type(alloc)
    {
        node* p = base_type::allocate(1);
        if (p)
        {
            try
            {
                new (p) node();
                try
                {
                    m_pImpl = threadsafe_queue_impl::create(p);
                }
                catch (...)
                {
                    p->~node();
                    throw;
                }
            }
            catch (...)
            {
                base_type::deallocate(p, 1);
                throw;
            }
        }
        else
            throw std::bad_alloc();
    }
    /*!
     * Destructor
     */
    ~threadsafe_queue()
    {
        // Clear the queue
        if (!unsafe_empty())
        {
            value_type value;
            while (try_pop(value));
        }

        // Remove the last dummy node
        node* p = static_cast< node* >(m_pImpl->reset_last_node());
        p->~node();
        base_type::deallocate(p, 1);

        delete m_pImpl;
    }

    /*!
     * Checks if the queue is empty. Not thread-safe, the returned result may not be actual.
     */
    bool unsafe_empty() const { return m_pImpl->unsafe_empty(); }

    /*!
     * Puts a new element to the end of the queue. Thread-safe, can be called
     * concurrently by several threads, and concurrently with the \c pop operation.
     */
    void push(const_reference value)
    {
        node* p = base_type::allocate(1);
        if (p)
        {
            try
            {
                new (p) node(value);
            }
            catch (...)
            {
                base_type::deallocate(p, 1);
                throw;
            }
            m_pImpl->push(p);
        }
        else
            throw std::bad_alloc();
    }

    /*!
     * Attempts to pop an element from the beginning of the queue. Thread-safe, can
     * be called concurrently with the \c push operation. Should not be called by
     * several threads concurrently.
     */
    bool try_pop(reference value)
    {
        threadsafe_queue_impl::node_base *dealloc, *destr;
        if (m_pImpl->try_pop(dealloc, destr))
        {
            node* p = static_cast< node* >(destr);
            auto_deallocate guard(static_cast< base_type* >(this), static_cast< node* >(dealloc), p);
            value = boost::move(p->value());
            return true;
        }
        else
            return false;
    }

    // Copying and assignment is prohibited
    BOOST_DELETED_FUNCTION(threadsafe_queue(threadsafe_queue const&))
    BOOST_DELETED_FUNCTION(threadsafe_queue& operator= (threadsafe_queue const&))

private:
    //! Pointer to the implementation
    threadsafe_queue_impl* m_pImpl;
};

} // namespace aux

BOOST_LOG_CLOSE_NAMESPACE // namespace log

} // namespace boost

#include <boost/log/detail/footer.hpp>

#endif // BOOST_LOG_NO_THREADS

#endif // BOOST_LOG_DETAIL_THREADSAFE_QUEUE_HPP_INCLUDED_