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