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