summaryrefslogtreecommitdiff
path: root/boost/fiber/algo/detail/chase_lev_queue.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/fiber/algo/detail/chase_lev_queue.hpp')
-rw-r--r--boost/fiber/algo/detail/chase_lev_queue.hpp172
1 files changed, 0 insertions, 172 deletions
diff --git a/boost/fiber/algo/detail/chase_lev_queue.hpp b/boost/fiber/algo/detail/chase_lev_queue.hpp
deleted file mode 100644
index f51556020d..0000000000
--- a/boost/fiber/algo/detail/chase_lev_queue.hpp
+++ /dev/null
@@ -1,172 +0,0 @@
-
-// Copyright Oliver Kowalke 2013.
-// 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)
-
-#ifndef BOOST_FIBERS_ALGO_DETAIL_CHASE_LEV_QUEUE_H
-#define BOOST_FIBERS_ALGO_DETAIL_CHASE_LEV_QUEUE_H
-
-#include <atomic>
-#include <cstddef>
-#include <memory>
-#include <type_traits>
-#include <vector>
-
-#include <boost/assert.hpp>
-#include <boost/config.hpp>
-
-#include <boost/fiber/detail/config.hpp>
-#include <boost/fiber/context.hpp>
-
-// David Chase and Yossi Lev. Dynamic circular work-stealing deque.
-// In SPAA ’05: Proceedings of the seventeenth annual ACM symposium
-// on Parallelism in algorithms and architectures, pages 21–28,
-// New York, NY, USA, 2005. ACM.
-//
-// Nhat Minh Lê, Antoniu Pop, Albert Cohen, and Francesco Zappa Nardelli. 2013.
-// Correct and efficient work-stealing for weak memory models.
-// In Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice
-// of parallel programming (PPoPP '13). ACM, New York, NY, USA, 69-80.
-namespace boost {
-namespace fibers {
-namespace algo {
-namespace detail {
-
-class chase_lev_queue {
-private:
- class circular_buffer {
- private:
- typedef typename std::aligned_storage< sizeof( context *), alignof( context *) >::type storage_t;
-
- int64_t size_;
- context ** items;
- chase_lev_queue * queue_;
-
- public:
- circular_buffer( int64_t size, chase_lev_queue * queue) noexcept :
- size_{ size },
- items{ reinterpret_cast< context ** >( new storage_t[size_] ) },
- queue_{ queue } {
- }
-
- ~circular_buffer() {
- delete [] reinterpret_cast< storage_t * >( items);
- }
-
- int64_t size() const noexcept {
- return size_;
- }
-
- context * get( int64_t idx) noexcept {
- BOOST_ASSERT( 0 <= idx);
- return * (items + (idx & (size() - 1)));
- }
-
- void put( int64_t idx, context * ctx) noexcept {
- BOOST_ASSERT( 0 <= idx);
- * (items + (idx & (size() - 1))) = ctx;
- }
-
- circular_buffer * grow( int64_t top, int64_t bottom) {
- BOOST_ASSERT( 0 <= top);
- BOOST_ASSERT( 0 <= bottom);
- circular_buffer * buffer = new circular_buffer{ size() * 2, queue_ };
- queue_->old_buffers_.push_back( this);
- for ( int64_t i = top; i != bottom; ++i) {
- buffer->put( i, get( i) );
- }
- return buffer;
- }
- };
-
- std::atomic< int64_t > top_{ 0 };
- std::atomic< int64_t > bottom_{ 0 };
- std::atomic< circular_buffer * > buffer_;
- std::vector< circular_buffer * > old_buffers_;
-
-public:
- chase_lev_queue() :
- buffer_{ new circular_buffer{ 1024, this } } {
- old_buffers_.resize( 10);
- }
-
- ~chase_lev_queue() {
- delete buffer_.load( std::memory_order_seq_cst);
- for ( circular_buffer * buffer : old_buffers_) {
- delete buffer;
- }
- }
-
- chase_lev_queue( chase_lev_queue const&) = delete;
- chase_lev_queue( chase_lev_queue &&) = delete;
-
- chase_lev_queue & operator=( chase_lev_queue const&) = delete;
- chase_lev_queue & operator=( chase_lev_queue &&) = delete;
-
- bool empty() const noexcept {
- int64_t bottom = bottom_.load( std::memory_order_relaxed);
- int64_t top = top_.load( std::memory_order_relaxed);
- return bottom <= top;
- }
-
- void push( context * ctx) {
- int64_t bottom = bottom_.load( std::memory_order_relaxed);
- int64_t top = top_.load( std::memory_order_acquire);
- circular_buffer * buffer = buffer_.load( std::memory_order_relaxed);
- if ( (bottom - top) > buffer->size() - 1) {
- // queue is full
- buffer = buffer->grow( top, bottom);
- buffer_.store( buffer, std::memory_order_release);
- }
- buffer->put( bottom, ctx);
- std::atomic_thread_fence( std::memory_order_release);
- bottom_.store( bottom + 1, std::memory_order_relaxed);
- }
-
- context * pop() {
- int64_t bottom = bottom_.load( std::memory_order_relaxed) - 1;
- circular_buffer * buffer = buffer_.load( std::memory_order_relaxed);
- bottom_.store( bottom, std::memory_order_relaxed);
- std::atomic_thread_fence( std::memory_order_seq_cst);
- int64_t top = top_.load( std::memory_order_relaxed);
- context * ctx = nullptr;
- if ( top <= bottom) {
- // queue is not empty
- ctx = buffer->get( bottom);
- // last element
- if ( top == bottom) {
- if ( ! top_.compare_exchange_strong( top, top + 1,
- std::memory_order_seq_cst, std::memory_order_relaxed) ) {
- return nullptr;
- }
- bottom_.store( bottom + 1, std::memory_order_relaxed);
- }
- } else {
- // queue is empty
- bottom_.store( bottom + 1, std::memory_order_relaxed);
- }
- return ctx;
- }
-
- context * steal() {
- int64_t top = top_.load( std::memory_order_acquire);
- std::atomic_thread_fence( std::memory_order_seq_cst);
- int64_t bottom = bottom_.load( std::memory_order_acquire);
- context * ctx = nullptr;
- if ( top < bottom) {
- // queue is not empty
- circular_buffer * buffer = buffer_.load( std::memory_order_consume);
- ctx = buffer->get( top);
- if ( ! top_.compare_exchange_strong( top, top + 1,
- std::memory_order_seq_cst, std::memory_order_relaxed) ) {
- return nullptr;
- }
- }
- return ctx;
- }
-};
-
-}}}}
-
-#endif // #define BOOST_FIBERS_ALGO_DETAIL_CHASE_LEV_QUEUE_H