1 2 // Copyright Oliver Kowalke 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 #ifndef BOOST_FIBERS_DETAIL_SPINLOCK_QUEUE_H 9 #define BOOST_FIBERS_DETAIL_SPINLOCK_QUEUE_H 10 11 #include <cstddef> 12 #include <cstring> 13 #include <mutex> 14 15 #include <boost/config.hpp> 16 17 #include <boost/fiber/context.hpp> 18 #include <boost/fiber/detail/config.hpp> 19 #include <boost/fiber/detail/spinlock.hpp> 20 21 #ifdef BOOST_HAS_ABI_HEADERS 22 # include BOOST_ABI_PREFIX 23 #endif 24 25 namespace boost { 26 namespace fibers { 27 namespace detail { 28 29 class context_spinlock_queue { 30 private: 31 typedef context * slot_type; 32 33 mutable spinlock splk_{}; 34 std::size_t pidx_{ 0 }; 35 std::size_t cidx_{ 0 }; 36 std::size_t capacity_; 37 slot_type * slots_; 38 resize_()39 void resize_() { 40 slot_type * old_slots = slots_; 41 slots_ = new slot_type[2*capacity_]; 42 std::size_t offset = capacity_ - cidx_; 43 std::memcpy( slots_, old_slots + cidx_, offset * sizeof( slot_type) ); 44 if ( 0 < cidx_) { 45 std::memcpy( slots_ + offset, old_slots, pidx_ * sizeof( slot_type) ); 46 } 47 cidx_ = 0; 48 pidx_ = capacity_ - 1; 49 capacity_ *= 2; 50 delete [] old_slots; 51 } 52 is_full_() const53 bool is_full_() const noexcept { 54 return cidx_ == ((pidx_ + 1) % capacity_); 55 } 56 is_empty_() const57 bool is_empty_() const noexcept { 58 return cidx_ == pidx_; 59 } 60 61 public: context_spinlock_queue(std::size_t capacity=4096)62 context_spinlock_queue( std::size_t capacity = 4096) : 63 capacity_{ capacity } { 64 slots_ = new slot_type[capacity_]; 65 } 66 ~context_spinlock_queue()67 ~context_spinlock_queue() { 68 delete [] slots_; 69 } 70 71 context_spinlock_queue( context_spinlock_queue const&) = delete; 72 context_spinlock_queue & operator=( context_spinlock_queue const&) = delete; 73 empty() const74 bool empty() const noexcept { 75 spinlock_lock lk{ splk_ }; 76 return is_empty_(); 77 } 78 push(context * c)79 void push( context * c) { 80 spinlock_lock lk{ splk_ }; 81 if ( is_full_() ) { 82 resize_(); 83 } 84 slots_[pidx_] = c; 85 pidx_ = (pidx_ + 1) % capacity_; 86 } 87 pop()88 context * pop() { 89 spinlock_lock lk{ splk_ }; 90 context * c = nullptr; 91 if ( ! is_empty_() ) { 92 c = slots_[cidx_]; 93 cidx_ = (cidx_ + 1) % capacity_; 94 } 95 return c; 96 } 97 steal()98 context * steal() { 99 spinlock_lock lk{ splk_ }; 100 context * c = nullptr; 101 if ( ! is_empty_() ) { 102 c = slots_[cidx_]; 103 if ( c->is_context( type::pinned_context) ) { 104 return nullptr; 105 } 106 cidx_ = (cidx_ + 1) % capacity_; 107 } 108 return c; 109 } 110 }; 111 112 }}} 113 114 #ifdef BOOST_HAS_ABI_HEADERS 115 # include BOOST_ABI_SUFFIX 116 #endif 117 118 #endif // BOOST_FIBERS_DETAIL_SPINLOCK_QUEUE_H 119