1 ////////////////////////////////////////////////////////////////////////////////
2 //  Copyright (c) 2012 Bryce Adelstein-Lelbach
3 //
4 //  Distributed under the Boost Software License, Version 1.0. (See accompanying
5 //  file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 ////////////////////////////////////////////////////////////////////////////////
7 
8 #if !defined(HPX_FB3518C8_4493_450E_A823_A9F8A3185B2D)
9 #define HPX_FB3518C8_4493_450E_A823_A9F8A3185B2D
10 
11 #include <hpx/config.hpp>
12 
13 #include <hpx/util/lockfree/deque.hpp>
14 
15 #include <cstddef>
16 #include <cstdint>
17 
18 namespace hpx { namespace threads { namespace policies
19 {
20 
21 struct lockfree_fifo;
22 struct lockfree_lifo;
23 
24 // FIFO
25 template <typename T>
26 struct lockfree_fifo_backend
27 {
28     typedef boost::lockfree::deque<T> container_type;
29     typedef T value_type;
30     typedef T& reference;
31     typedef T const& const_reference;
32     typedef std::uint64_t size_type;
33 
lockfree_fifo_backendhpx::threads::policies::lockfree_fifo_backend34     lockfree_fifo_backend(
35         size_type initial_size = 0
36       , size_type num_thread = size_type(-1)
37         )
38       : queue_(std::size_t(initial_size))
39     {}
40 
pushhpx::threads::policies::lockfree_fifo_backend41     bool push(const_reference val, bool /*other_end*/ = false)
42     {
43         return queue_.push_left(val);
44     }
45 
pophpx::threads::policies::lockfree_fifo_backend46     bool pop(reference val, bool steal = true)
47     {
48         return queue_.pop_right(val);
49     }
50 
emptyhpx::threads::policies::lockfree_fifo_backend51     bool empty()
52     {
53         return queue_.empty();
54     }
55 
56   private:
57     container_type queue_;
58 };
59 
60 struct lockfree_fifo
61 {
62     template <typename T>
63     struct apply
64     {
65         typedef lockfree_fifo_backend<T> type;
66     };
67 };
68 
69 // LIFO
70 template <typename T>
71 struct lockfree_lifo_backend
72 {
73     typedef boost::lockfree::deque<T> container_type;
74     typedef T value_type;
75     typedef T& reference;
76     typedef T const& const_reference;
77     typedef std::uint64_t size_type;
78 
lockfree_lifo_backendhpx::threads::policies::lockfree_lifo_backend79     lockfree_lifo_backend(
80         size_type initial_size = 0
81       , size_type num_thread = size_type(-1)
82         )
83       : queue_(std::size_t(initial_size))
84     {}
85 
pushhpx::threads::policies::lockfree_lifo_backend86     bool push(const_reference val, bool other_end = false)
87     {
88         if (other_end)
89             return queue_.push_right(val);
90         return queue_.push_left(val);
91     }
92 
pophpx::threads::policies::lockfree_lifo_backend93     bool pop(reference val, bool steal = true)
94     {
95         return queue_.pop_left(val);
96     }
97 
emptyhpx::threads::policies::lockfree_lifo_backend98     bool empty()
99     {
100         return queue_.empty();
101     }
102 
103   private:
104     container_type queue_;
105 };
106 
107 struct lockfree_lifo
108 {
109     template <typename T>
110     struct apply
111     {
112         typedef lockfree_lifo_backend<T> type;
113     };
114 };
115 
116 ///////////////////////////////////////////////////////////////////////////////
117 // FIFO + stealing at opposite end.
118 #if defined(HPX_HAVE_ABP_SCHEDULER)
119 struct lockfree_abp_fifo;
120 struct lockfree_abp_lifo;
121 
122 template <typename T>
123 struct lockfree_abp_fifo_backend
124 {
125     typedef boost::lockfree::deque<T> container_type;
126     typedef T value_type;
127     typedef T& reference;
128     typedef T const& const_reference;
129     typedef std::uint64_t size_type;
130 
lockfree_abp_fifo_backendhpx::threads::policies::lockfree_abp_fifo_backend131     lockfree_abp_fifo_backend(
132         size_type initial_size = 0
133       , size_type num_thread = size_type(-1)
134         )
135       : queue_(std::size_t(initial_size))
136     {}
137 
pushhpx::threads::policies::lockfree_abp_fifo_backend138     bool push(const_reference val, bool /*other_end*/ = false)
139     {
140         return queue_.push_left(val);
141     }
142 
pophpx::threads::policies::lockfree_abp_fifo_backend143     bool pop(reference val, bool steal = true)
144     {
145         if (steal)
146             return queue_.pop_left(val);
147         return queue_.pop_right(val);
148     }
149 
emptyhpx::threads::policies::lockfree_abp_fifo_backend150     bool empty()
151     {
152         return queue_.empty();
153     }
154 
155   private:
156     container_type queue_;
157 };
158 
159 struct lockfree_abp_fifo
160 {
161     template <typename T>
162     struct apply
163     {
164         typedef lockfree_abp_fifo_backend<T> type;
165     };
166 };
167 
168 ///////////////////////////////////////////////////////////////////////////////
169 // LIFO + stealing at opposite end.
170 // E.g. ABP (Arora, Blumofe and Plaxton) queuing
171 // http://dl.acm.org/citation.cfm?id=277678
172 template <typename T>
173 struct lockfree_abp_lifo_backend
174 {
175     typedef boost::lockfree::deque<T> container_type;
176     typedef T value_type;
177     typedef T& reference;
178     typedef T const& const_reference;
179     typedef std::uint64_t size_type;
180 
lockfree_abp_lifo_backendhpx::threads::policies::lockfree_abp_lifo_backend181     lockfree_abp_lifo_backend(
182         size_type initial_size = 0
183       , size_type num_thread = size_type(-1)
184         )
185       : queue_(std::size_t(initial_size))
186     {}
187 
pushhpx::threads::policies::lockfree_abp_lifo_backend188     bool push(const_reference val, bool other_end = false)
189     {
190         if (other_end)
191             return queue_.push_right(val);
192         return queue_.push_left(val);
193     }
194 
pophpx::threads::policies::lockfree_abp_lifo_backend195     bool pop(reference val, bool steal = true)
196     {
197         if (steal)
198             return queue_.pop_right(val);
199         return queue_.pop_left(val);
200     }
201 
emptyhpx::threads::policies::lockfree_abp_lifo_backend202     bool empty()
203     {
204         return queue_.empty();
205     }
206 
207   private:
208     container_type queue_;
209 };
210 
211 struct lockfree_abp_lifo
212 {
213     template <typename T>
214     struct apply
215     {
216         typedef lockfree_abp_lifo_backend<T> type;
217     };
218 };
219 
220 #endif // HPX_HAVE_ABP_SCHEDULER
221 
222 }}}
223 
224 #endif // HPX_FB3518C8_4493_450E_A823_A9F8A3185B2D
225 
226