Subject: [Boost-commit] svn:boost r85192 - in branches/release: boost/lockfree boost/lockfree/detail libs/lockfree
From: tim_at_[hidden]
Date: 2013-08-02 13:09:29
Author: timblechmann
Date: 2013-08-02 13:09:29 EDT (Fri, 02 Aug 2013)
New Revision: 85192
URL: http://svn.boost.org/trac/boost/changeset/85192
Log:
lockfree: merge changes from trunk
Properties modified:
branches/release/boost/lockfree/ (props changed)
branches/release/libs/lockfree/ (props changed)
Text files modified:
branches/release/boost/lockfree/detail/copy_payload.hpp | 17 +++
branches/release/boost/lockfree/detail/freelist.hpp | 4
branches/release/boost/lockfree/spsc_queue.hpp | 187 +++++++++++++++++++--------------------
branches/release/boost/lockfree/stack.hpp | 54 ++++++-----
4 files changed, 140 insertions(+), 122 deletions(-)
Modified: branches/release/boost/lockfree/detail/copy_payload.hpp
==============================================================================
--- branches/release/boost/lockfree/detail/copy_payload.hpp Fri Aug 2 07:29:51 2013 (r85191)
+++ branches/release/boost/lockfree/detail/copy_payload.hpp 2013-08-02 13:09:29 EDT (Fri, 02 Aug 2013) (r85192)
@@ -44,6 +44,23 @@
copy_type::copy(t, u);
}
+template <typename T>
+struct consume_via_copy
+{
+ consume_via_copy(T & out):
+ out(out)
+ {}
+
+ template <typename U>
+ void operator()(U & element)
+ {
+ copy_payload(element, out);
+ }
+
+ T & out;
+};
+
+
}}}
#endif /* BOOST_LOCKFREE_DETAIL_COPY_PAYLOAD_HPP_INCLUDED */
Modified: branches/release/boost/lockfree/detail/freelist.hpp
==============================================================================
--- branches/release/boost/lockfree/detail/freelist.hpp Fri Aug 2 07:29:51 2013 (r85191)
+++ branches/release/boost/lockfree/detail/freelist.hpp 2013-08-02 13:09:29 EDT (Fri, 02 Aug 2013) (r85192)
@@ -1,6 +1,6 @@
// lock-free freelist
//
-// Copyright (C) 2008, 2009, 2011 Tim Blechmann
+// Copyright (C) 2008-2013 Tim Blechmann
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -110,7 +110,7 @@
~freelist_stack(void)
{
- tagged_node_ptr current (pool_);
+ tagged_node_ptr current = pool_.load();
while (current) {
freelist_node * current_ptr = current.get_ptr();
Modified: branches/release/boost/lockfree/spsc_queue.hpp
==============================================================================
--- branches/release/boost/lockfree/spsc_queue.hpp Fri Aug 2 07:29:51 2013 (r85191)
+++ branches/release/boost/lockfree/spsc_queue.hpp 2013-08-02 13:09:29 EDT (Fri, 02 Aug 2013) (r85192)
@@ -1,7 +1,7 @@
// lock-free single-producer/single-consumer ringbuffer
// this algorithm is implemented in various projects (linux kernel)
//
-// Copyright (C) 2009, 2011 Tim Blechmann
+// Copyright (C) 2009-2013 Tim Blechmann
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
@@ -11,13 +11,17 @@
#define BOOST_LOCKFREE_SPSC_QUEUE_HPP_INCLUDED
#include <algorithm>
+#include <memory>
-#include <boost/array.hpp>
+#include <boost/aligned_storage.hpp>
#include <boost/assert.hpp>
#ifdef BOOST_NO_CXX11_DELETED_FUNCTIONS
#include <boost/noncopyable.hpp>
#endif
#include <boost/static_assert.hpp>
+#include <boost/utility.hpp>
+
+#include <boost/type_traits/has_trivial_destructor.hpp>
#include <boost/lockfree/detail/atomic.hpp>
#include <boost/lockfree/detail/branch_hints.hpp>
@@ -84,13 +88,13 @@
bool push(T const & t, T * buffer, size_t max_size)
{
- size_t write_index = write_index_.load(memory_order_relaxed); // only written from push thread
- size_t next = next_index(write_index, max_size);
+ const size_t write_index = write_index_.load(memory_order_relaxed); // only written from push thread
+ const size_t next = next_index(write_index, max_size);
if (next == read_index_.load(memory_order_acquire))
return false; /* ringbuffer is full */
- buffer[write_index] = t;
+ new (buffer + write_index) T(t); // copy-construct
write_index_.store(next, memory_order_release);
@@ -99,41 +103,15 @@
size_t push(const T * input_buffer, size_t input_count, T * internal_buffer, size_t max_size)
{
- size_t write_index = write_index_.load(memory_order_relaxed); // only written from push thread
- const size_t read_index = read_index_.load(memory_order_acquire);
- const size_t avail = write_available(write_index, read_index, max_size);
-
- if (avail == 0)
- return 0;
-
- input_count = (std::min)(input_count, avail);
-
- size_t new_write_index = write_index + input_count;
-
- if (write_index + input_count > max_size) {
- /* copy data in two sections */
- size_t count0 = max_size - write_index;
-
- std::copy(input_buffer, input_buffer + count0, internal_buffer + write_index);
- std::copy(input_buffer + count0, input_buffer + input_count, internal_buffer);
- new_write_index -= max_size;
- } else {
- std::copy(input_buffer, input_buffer + input_count, internal_buffer + write_index);
-
- if (new_write_index == max_size)
- new_write_index = 0;
- }
-
- write_index_.store(new_write_index, memory_order_release);
- return input_count;
+ return push(input_buffer, input_buffer + input_count, internal_buffer, max_size) - input_buffer;
}
template <typename ConstIterator>
ConstIterator push(ConstIterator begin, ConstIterator end, T * internal_buffer, size_t max_size)
{
- // FIXME: avoid std::distance and std::advance
+ // FIXME: avoid std::distance
- size_t write_index = write_index_.load(memory_order_relaxed); // only written from push thread
+ const size_t write_index = write_index_.load(memory_order_relaxed); // only written from push thread
const size_t read_index = read_index_.load(memory_order_acquire);
const size_t avail = write_available(write_index, read_index, max_size);
@@ -145,20 +123,18 @@
size_t new_write_index = write_index + input_count;
- ConstIterator last = begin;
- std::advance(last, input_count);
+ const ConstIterator last = boost::next(begin, input_count);
if (write_index + input_count > max_size) {
/* copy data in two sections */
- size_t count0 = max_size - write_index;
- ConstIterator midpoint = begin;
- std::advance(midpoint, count0);
+ const size_t count0 = max_size - write_index;
+ const ConstIterator midpoint = boost::next(begin, count0);
- std::copy(begin, midpoint, internal_buffer + write_index);
- std::copy(midpoint, last, internal_buffer);
+ std::uninitialized_copy(begin, midpoint, internal_buffer + write_index);
+ std::uninitialized_copy(midpoint, last, internal_buffer);
new_write_index -= max_size;
} else {
- std::copy(begin, last, internal_buffer + write_index);
+ std::uninitialized_copy(begin, last, internal_buffer + write_index);
if (new_write_index == max_size)
new_write_index = 0;
@@ -170,21 +146,23 @@
bool pop (T & ret, T * buffer, size_t max_size)
{
- size_t write_index = write_index_.load(memory_order_acquire);
- size_t read_index = read_index_.load(memory_order_relaxed); // only written from pop thread
+ const size_t write_index = write_index_.load(memory_order_acquire);
+ const size_t read_index = read_index_.load(memory_order_relaxed); // only written from pop thread
if (empty(write_index, read_index))
return false;
ret = buffer[read_index];
+ buffer[read_index].~T();
+
size_t next = next_index(read_index, max_size);
read_index_.store(next, memory_order_release);
return true;
}
- size_t pop (T * output_buffer, size_t output_count, const T * internal_buffer, size_t max_size)
+ size_t pop (T * output_buffer, size_t output_count, T * internal_buffer, size_t max_size)
{
const size_t write_index = write_index_.load(memory_order_acquire);
- size_t read_index = read_index_.load(memory_order_relaxed); // only written from pop thread
+ const size_t read_index = read_index_.load(memory_order_relaxed); // only written from pop thread
const size_t avail = read_available(write_index, read_index, max_size);
@@ -197,15 +175,15 @@
if (read_index + output_count > max_size) {
/* copy data in two sections */
- size_t count0 = max_size - read_index;
- size_t count1 = output_count - count0;
+ const size_t count0 = max_size - read_index;
+ const size_t count1 = output_count - count0;
- std::copy(internal_buffer + read_index, internal_buffer + max_size, output_buffer);
- std::copy(internal_buffer, internal_buffer + count1, output_buffer + count0);
+ copy_and_delete(internal_buffer + read_index, internal_buffer + max_size, output_buffer);
+ copy_and_delete(internal_buffer, internal_buffer + count1, output_buffer + count0);
new_read_index -= max_size;
} else {
- std::copy(internal_buffer + read_index, internal_buffer + read_index + output_count, output_buffer);
+ copy_and_delete(internal_buffer + read_index, internal_buffer + read_index + output_count, output_buffer);
if (new_read_index == max_size)
new_read_index = 0;
}
@@ -215,10 +193,10 @@
}
template <typename OutputIterator>
- size_t pop (OutputIterator it, const T * internal_buffer, size_t max_size)
+ size_t pop (OutputIterator it, T * internal_buffer, size_t max_size)
{
const size_t write_index = write_index_.load(memory_order_acquire);
- size_t read_index = read_index_.load(memory_order_relaxed); // only written from pop thread
+ const size_t read_index = read_index_.load(memory_order_relaxed); // only written from pop thread
const size_t avail = read_available(write_index, read_index, max_size);
if (avail == 0)
@@ -228,15 +206,15 @@
if (read_index + avail > max_size) {
/* copy data in two sections */
- size_t count0 = max_size - read_index;
- size_t count1 = avail - count0;
+ const size_t count0 = max_size - read_index;
+ const size_t count1 = avail - count0;
- it = std::copy(internal_buffer + read_index, internal_buffer + max_size, it);
- std::copy(internal_buffer, internal_buffer + count1, it);
+ it = copy_and_delete(internal_buffer + read_index, internal_buffer + max_size, it);
+ copy_and_delete(internal_buffer, internal_buffer + count1, it);
new_read_index -= max_size;
} else {
- std::copy(internal_buffer + read_index, internal_buffer + read_index + avail, it);
+ copy_and_delete(internal_buffer + read_index, internal_buffer + read_index + avail, it);
if (new_read_index == max_size)
new_read_index = 0;
}
@@ -282,34 +260,58 @@
{
return write_index == read_index;
}
+
+ template< class OutputIterator >
+ OutputIterator copy_and_delete( T * first, T * last, OutputIterator out )
+ {
+ if (boost::has_trivial_destructor<T>::value) {
+ return std::copy(first, last, out); // will use memcpy if possible
+ } else {
+ for (; first != last; ++first, ++out) {
+ *out = *first;
+ first->~T();
+ }
+ return out;
+ }
+ }
};
template <typename T, std::size_t MaxSize>
class compile_time_sized_ringbuffer:
public ringbuffer_base<T>
{
- typedef std::size_t size_t;
+ typedef std::size_t size_type;
static const std::size_t max_size = MaxSize + 1;
- boost::array<T, max_size> array_;
+
+ typedef typename boost::aligned_storage<max_size * sizeof(T),
+ boost::alignment_of<T>::value
+ >::type storage_type;
+
+ storage_type storage_;
+
+ T * data()
+ {
+ return static_cast<T*>(storage_.address());
+ }
public:
bool push(T const & t)
{
- return ringbuffer_base<T>::push(t, array_.c_array(), max_size);
+ return ringbuffer_base<T>::push(t, data(), max_size);
}
bool pop(T & ret)
{
- return ringbuffer_base<T>::pop(ret, array_.c_array(), max_size);
+ return ringbuffer_base<T>::pop(ret, data(), max_size);
}
- size_t push(T const * t, size_t size)
+ size_type push(T const * t, size_type size)
{
- return ringbuffer_base<T>::push(t, size, array_.c_array(), max_size);
+ return ringbuffer_base<T>::push(t, size, data(), max_size);
}
- template <size_t size>
- size_t push(T const (&t)[size])
+ template <size_type size>
+ size_type push(T const (&t)[size])
{
return push(t, size);
}
@@ -317,24 +319,24 @@
template <typename ConstIterator>
ConstIterator push(ConstIterator begin, ConstIterator end)
{
- return ringbuffer_base<T>::push(begin, end, array_.c_array(), max_size);
+ return ringbuffer_base<T>::push(begin, end, data(), max_size);
}
- size_t pop(T * ret, size_t size)
+ size_type pop(T * ret, size_type size)
{
- return ringbuffer_base<T>::pop(ret, size, array_.c_array(), max_size);
+ return ringbuffer_base<T>::pop(ret, size, data(), max_size);
}
- template <size_t size>
- size_t pop(T (&ret)[size])
+ template <size_type size>
+ size_type pop(T (&ret)[size])
{
return pop(ret, size);
}
template <typename OutputIterator>
- size_t pop(OutputIterator it)
+ size_type pop(OutputIterator it)
{
- return ringbuffer_base<T>::pop(it, array_.c_array(), max_size);
+ return ringbuffer_base<T>::pop(it, data(), max_size);
}
};
@@ -343,44 +345,37 @@
public ringbuffer_base<T>,
private Alloc
{
- typedef std::size_t size_t;
- size_t max_elements_;
+ typedef std::size_t size_type;
+ size_type max_elements_;
typedef typename Alloc::pointer pointer;
pointer array_;
public:
- explicit runtime_sized_ringbuffer(size_t max_elements):
+ explicit runtime_sized_ringbuffer(size_type max_elements):
max_elements_(max_elements + 1)
{
- // TODO: we don't necessarily need to construct all elements
array_ = Alloc::allocate(max_elements_);
- for (size_t i = 0; i != max_elements_; ++i)
- Alloc::construct(array_ + i, T());
}
template <typename U>
- runtime_sized_ringbuffer(typename Alloc::template rebind<U>::other const & alloc, size_t max_elements):
+ runtime_sized_ringbuffer(typename Alloc::template rebind<U>::other const & alloc, size_type max_elements):
Alloc(alloc), max_elements_(max_elements + 1)
{
- // TODO: we don't necessarily need to construct all elements
array_ = Alloc::allocate(max_elements_);
- for (size_t i = 0; i != max_elements_; ++i)
- Alloc::construct(array_ + i, T());
}
- runtime_sized_ringbuffer(Alloc const & alloc, size_t max_elements):
+ runtime_sized_ringbuffer(Alloc const & alloc, size_type max_elements):
Alloc(alloc), max_elements_(max_elements + 1)
{
- // TODO: we don't necessarily need to construct all elements
array_ = Alloc::allocate(max_elements_);
- for (size_t i = 0; i != max_elements_; ++i)
- Alloc::construct(array_ + i, T());
}
~runtime_sized_ringbuffer(void)
{
- for (size_t i = 0; i != max_elements_; ++i)
- Alloc::destroy(array_ + i);
+ // destroy all remaining items
+ T out;
+ while (pop(out)) {};
+
Alloc::deallocate(array_, max_elements_);
}
@@ -394,13 +389,13 @@
return ringbuffer_base<T>::pop(ret, &*array_, max_elements_);
}
- size_t push(T const * t, size_t size)
+ size_type push(T const * t, size_type size)
{
return ringbuffer_base<T>::push(t, size, &*array_, max_elements_);
}
- template <size_t size>
- size_t push(T const (&t)[size])
+ template <size_type size>
+ size_type push(T const (&t)[size])
{
return push(t, size);
}
@@ -411,19 +406,19 @@
return ringbuffer_base<T>::push(begin, end, array_, max_elements_);
}
- size_t pop(T * ret, size_t size)
+ size_type pop(T * ret, size_type size)
{
return ringbuffer_base<T>::pop(ret, size, array_, max_elements_);
}
- template <size_t size>
- size_t pop(T (&ret)[size])
+ template <size_type size>
+ size_type pop(T (&ret)[size])
{
return pop(ret, size);
}
template <typename OutputIterator>
- size_t pop(OutputIterator it)
+ size_type pop(OutputIterator it)
{
return ringbuffer_base<T>::pop(it, array_, max_elements_);
}
Modified: branches/release/boost/lockfree/stack.hpp
==============================================================================
--- branches/release/boost/lockfree/stack.hpp Fri Aug 2 07:29:51 2013 (r85191)
+++ branches/release/boost/lockfree/stack.hpp 2013-08-02 13:09:29 EDT (Fri, 02 Aug 2013) (r85192)
@@ -435,21 +435,9 @@
bool pop(U & ret)
{
BOOST_STATIC_ASSERT((boost::is_convertible<T, U>::value));
- tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
-
- for (;;) {
- node * old_tos_pointer = pool.get_pointer(old_tos);
- if (!old_tos_pointer)
- return false;
-
- tagged_node_handle new_tos(old_tos_pointer->next, old_tos.get_next_tag());
+ detail::consume_via_copy<U> consumer(ret);
- if (tos.compare_exchange_weak(old_tos, new_tos)) {
- detail::copy_payload(old_tos_pointer->v, ret);
- pool.template destruct<true>(old_tos);
- return true;
- }
- }
+ return consume_one(consumer);
}
@@ -505,24 +493,42 @@
template <typename Functor>
bool consume_one(Functor & f)
{
- T element;
- bool success = pop(element);
- if (success)
- f(element);
+ tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
+
+ for (;;) {
+ node * old_tos_pointer = pool.get_pointer(old_tos);
+ if (!old_tos_pointer)
+ return false;
- return success;
+ tagged_node_handle new_tos(old_tos_pointer->next, old_tos.get_next_tag());
+
+ if (tos.compare_exchange_weak(old_tos, new_tos)) {
+ f(old_tos_pointer->v);
+ pool.template destruct<true>(old_tos);
+ return true;
+ }
+ }
}
/// \copydoc boost::lockfree::stack::consume_one(Functor & rhs)
template <typename Functor>
bool consume_one(Functor const & f)
{
- T element;
- bool success = pop(element);
- if (success)
- f(element);
+ tagged_node_handle old_tos = tos.load(detail::memory_order_consume);
- return success;
+ for (;;) {
+ node * old_tos_pointer = pool.get_pointer(old_tos);
+ if (!old_tos_pointer)
+ return false;
+
+ tagged_node_handle new_tos(old_tos_pointer->next, old_tos.get_next_tag());
+
+ if (tos.compare_exchange_weak(old_tos, new_tos)) {
+ f(old_tos_pointer->v);
+ pool.template destruct<true>(old_tos);
+ return true;
+ }
+ }
}
/** consumes all elements via a functor