1 // 2 // detail/timer_queue.hpp 3 // ~~~~~~~~~~~~~~~~~~~~~~ 4 // 5 // Copyright (c) 2003-2019 Christopher M. Kohlhoff (chris at kohlhoff dot com) 6 // 7 // Distributed under the Boost Software License, Version 1.0. (See accompanying 8 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 9 // 10 11 #ifndef BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP 12 #define BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP 13 14 #if defined(_MSC_VER) && (_MSC_VER >= 1200) 15 # pragma once 16 #endif // defined(_MSC_VER) && (_MSC_VER >= 1200) 17 18 #include <boost/asio/detail/config.hpp> 19 #include <cstddef> 20 #include <vector> 21 #include <boost/asio/detail/cstdint.hpp> 22 #include <boost/asio/detail/date_time_fwd.hpp> 23 #include <boost/asio/detail/limits.hpp> 24 #include <boost/asio/detail/op_queue.hpp> 25 #include <boost/asio/detail/timer_queue_base.hpp> 26 #include <boost/asio/detail/wait_op.hpp> 27 #include <boost/asio/error.hpp> 28 29 #include <boost/asio/detail/push_options.hpp> 30 31 namespace boost { 32 namespace asio { 33 namespace detail { 34 35 template <typename Time_Traits> 36 class timer_queue 37 : public timer_queue_base 38 { 39 public: 40 // The time type. 41 typedef typename Time_Traits::time_type time_type; 42 43 // The duration type. 44 typedef typename Time_Traits::duration_type duration_type; 45 46 // Per-timer data. 47 class per_timer_data 48 { 49 public: per_timer_data()50 per_timer_data() : 51 heap_index_((std::numeric_limits<std::size_t>::max)()), 52 next_(0), prev_(0) 53 { 54 } 55 56 private: 57 friend class timer_queue; 58 59 // The operations waiting on the timer. 60 op_queue<wait_op> op_queue_; 61 62 // The index of the timer in the heap. 63 std::size_t heap_index_; 64 65 // Pointers to adjacent timers in a linked list. 66 per_timer_data* next_; 67 per_timer_data* prev_; 68 }; 69 70 // Constructor. timer_queue()71 timer_queue() 72 : timers_(), 73 heap_() 74 { 75 } 76 77 // Add a new timer to the queue. Returns true if this is the timer that is 78 // earliest in the queue, in which case the reactor's event demultiplexing 79 // function call may need to be interrupted and restarted. enqueue_timer(const time_type & time,per_timer_data & timer,wait_op * op)80 bool enqueue_timer(const time_type& time, per_timer_data& timer, wait_op* op) 81 { 82 // Enqueue the timer object. 83 if (timer.prev_ == 0 && &timer != timers_) 84 { 85 if (this->is_positive_infinity(time)) 86 { 87 // No heap entry is required for timers that never expire. 88 timer.heap_index_ = (std::numeric_limits<std::size_t>::max)(); 89 } 90 else 91 { 92 // Put the new timer at the correct position in the heap. This is done 93 // first since push_back() can throw due to allocation failure. 94 timer.heap_index_ = heap_.size(); 95 heap_entry entry = { time, &timer }; 96 heap_.push_back(entry); 97 up_heap(heap_.size() - 1); 98 } 99 100 // Insert the new timer into the linked list of active timers. 101 timer.next_ = timers_; 102 timer.prev_ = 0; 103 if (timers_) 104 timers_->prev_ = &timer; 105 timers_ = &timer; 106 } 107 108 // Enqueue the individual timer operation. 109 timer.op_queue_.push(op); 110 111 // Interrupt reactor only if newly added timer is first to expire. 112 return timer.heap_index_ == 0 && timer.op_queue_.front() == op; 113 } 114 115 // Whether there are no timers in the queue. empty() const116 virtual bool empty() const 117 { 118 return timers_ == 0; 119 } 120 121 // Get the time for the timer that is earliest in the queue. wait_duration_msec(long max_duration) const122 virtual long wait_duration_msec(long max_duration) const 123 { 124 if (heap_.empty()) 125 return max_duration; 126 127 return this->to_msec( 128 Time_Traits::to_posix_duration( 129 Time_Traits::subtract(heap_[0].time_, Time_Traits::now())), 130 max_duration); 131 } 132 133 // Get the time for the timer that is earliest in the queue. wait_duration_usec(long max_duration) const134 virtual long wait_duration_usec(long max_duration) const 135 { 136 if (heap_.empty()) 137 return max_duration; 138 139 return this->to_usec( 140 Time_Traits::to_posix_duration( 141 Time_Traits::subtract(heap_[0].time_, Time_Traits::now())), 142 max_duration); 143 } 144 145 // Dequeue all timers not later than the current time. get_ready_timers(op_queue<operation> & ops)146 virtual void get_ready_timers(op_queue<operation>& ops) 147 { 148 if (!heap_.empty()) 149 { 150 const time_type now = Time_Traits::now(); 151 while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0].time_)) 152 { 153 per_timer_data* timer = heap_[0].timer_; 154 ops.push(timer->op_queue_); 155 remove_timer(*timer); 156 } 157 } 158 } 159 160 // Dequeue all timers. get_all_timers(op_queue<operation> & ops)161 virtual void get_all_timers(op_queue<operation>& ops) 162 { 163 while (timers_) 164 { 165 per_timer_data* timer = timers_; 166 timers_ = timers_->next_; 167 ops.push(timer->op_queue_); 168 timer->next_ = 0; 169 timer->prev_ = 0; 170 } 171 172 heap_.clear(); 173 } 174 175 // Cancel and dequeue operations for the given timer. cancel_timer(per_timer_data & timer,op_queue<operation> & ops,std::size_t max_cancelled=(std::numeric_limits<std::size_t>::max)())176 std::size_t cancel_timer(per_timer_data& timer, op_queue<operation>& ops, 177 std::size_t max_cancelled = (std::numeric_limits<std::size_t>::max)()) 178 { 179 std::size_t num_cancelled = 0; 180 if (timer.prev_ != 0 || &timer == timers_) 181 { 182 while (wait_op* op = (num_cancelled != max_cancelled) 183 ? timer.op_queue_.front() : 0) 184 { 185 op->ec_ = boost::asio::error::operation_aborted; 186 timer.op_queue_.pop(); 187 ops.push(op); 188 ++num_cancelled; 189 } 190 if (timer.op_queue_.empty()) 191 remove_timer(timer); 192 } 193 return num_cancelled; 194 } 195 196 // Move operations from one timer to another, empty timer. move_timer(per_timer_data & target,per_timer_data & source)197 void move_timer(per_timer_data& target, per_timer_data& source) 198 { 199 target.op_queue_.push(source.op_queue_); 200 201 target.heap_index_ = source.heap_index_; 202 source.heap_index_ = (std::numeric_limits<std::size_t>::max)(); 203 204 if (target.heap_index_ < heap_.size()) 205 heap_[target.heap_index_].timer_ = ⌖ 206 207 if (timers_ == &source) 208 timers_ = ⌖ 209 if (source.prev_) 210 source.prev_->next_ = ⌖ 211 if (source.next_) 212 source.next_->prev_= ⌖ 213 target.next_ = source.next_; 214 target.prev_ = source.prev_; 215 source.next_ = 0; 216 source.prev_ = 0; 217 } 218 219 private: 220 // Move the item at the given index up the heap to its correct position. up_heap(std::size_t index)221 void up_heap(std::size_t index) 222 { 223 while (index > 0) 224 { 225 std::size_t parent = (index - 1) / 2; 226 if (!Time_Traits::less_than(heap_[index].time_, heap_[parent].time_)) 227 break; 228 swap_heap(index, parent); 229 index = parent; 230 } 231 } 232 233 // Move the item at the given index down the heap to its correct position. down_heap(std::size_t index)234 void down_heap(std::size_t index) 235 { 236 std::size_t child = index * 2 + 1; 237 while (child < heap_.size()) 238 { 239 std::size_t min_child = (child + 1 == heap_.size() 240 || Time_Traits::less_than( 241 heap_[child].time_, heap_[child + 1].time_)) 242 ? child : child + 1; 243 if (Time_Traits::less_than(heap_[index].time_, heap_[min_child].time_)) 244 break; 245 swap_heap(index, min_child); 246 index = min_child; 247 child = index * 2 + 1; 248 } 249 } 250 251 // Swap two entries in the heap. swap_heap(std::size_t index1,std::size_t index2)252 void swap_heap(std::size_t index1, std::size_t index2) 253 { 254 heap_entry tmp = heap_[index1]; 255 heap_[index1] = heap_[index2]; 256 heap_[index2] = tmp; 257 heap_[index1].timer_->heap_index_ = index1; 258 heap_[index2].timer_->heap_index_ = index2; 259 } 260 261 // Remove a timer from the heap and list of timers. remove_timer(per_timer_data & timer)262 void remove_timer(per_timer_data& timer) 263 { 264 // Remove the timer from the heap. 265 std::size_t index = timer.heap_index_; 266 if (!heap_.empty() && index < heap_.size()) 267 { 268 if (index == heap_.size() - 1) 269 { 270 timer.heap_index_ = (std::numeric_limits<std::size_t>::max)(); 271 heap_.pop_back(); 272 } 273 else 274 { 275 swap_heap(index, heap_.size() - 1); 276 timer.heap_index_ = (std::numeric_limits<std::size_t>::max)(); 277 heap_.pop_back(); 278 if (index > 0 && Time_Traits::less_than( 279 heap_[index].time_, heap_[(index - 1) / 2].time_)) 280 up_heap(index); 281 else 282 down_heap(index); 283 } 284 } 285 286 // Remove the timer from the linked list of active timers. 287 if (timers_ == &timer) 288 timers_ = timer.next_; 289 if (timer.prev_) 290 timer.prev_->next_ = timer.next_; 291 if (timer.next_) 292 timer.next_->prev_= timer.prev_; 293 timer.next_ = 0; 294 timer.prev_ = 0; 295 } 296 297 // Determine if the specified absolute time is positive infinity. 298 template <typename Time_Type> is_positive_infinity(const Time_Type &)299 static bool is_positive_infinity(const Time_Type&) 300 { 301 return false; 302 } 303 304 // Determine if the specified absolute time is positive infinity. 305 template <typename T, typename TimeSystem> is_positive_infinity(const boost::date_time::base_time<T,TimeSystem> & time)306 static bool is_positive_infinity( 307 const boost::date_time::base_time<T, TimeSystem>& time) 308 { 309 return time.is_pos_infinity(); 310 } 311 312 // Helper function to convert a duration into milliseconds. 313 template <typename Duration> to_msec(const Duration & d,long max_duration) const314 long to_msec(const Duration& d, long max_duration) const 315 { 316 if (d.ticks() <= 0) 317 return 0; 318 int64_t msec = d.total_milliseconds(); 319 if (msec == 0) 320 return 1; 321 if (msec > max_duration) 322 return max_duration; 323 return static_cast<long>(msec); 324 } 325 326 // Helper function to convert a duration into microseconds. 327 template <typename Duration> to_usec(const Duration & d,long max_duration) const328 long to_usec(const Duration& d, long max_duration) const 329 { 330 if (d.ticks() <= 0) 331 return 0; 332 int64_t usec = d.total_microseconds(); 333 if (usec == 0) 334 return 1; 335 if (usec > max_duration) 336 return max_duration; 337 return static_cast<long>(usec); 338 } 339 340 // The head of a linked list of all active timers. 341 per_timer_data* timers_; 342 343 struct heap_entry 344 { 345 // The time when the timer should fire. 346 time_type time_; 347 348 // The associated timer with enqueued operations. 349 per_timer_data* timer_; 350 }; 351 352 // The heap of timers, with the earliest timer at the front. 353 std::vector<heap_entry> heap_; 354 }; 355 356 } // namespace detail 357 } // namespace asio 358 } // namespace boost 359 360 #include <boost/asio/detail/pop_options.hpp> 361 362 #endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP 363