1 // 2 // detail/timer_queue.hpp 3 // ~~~~~~~~~~~~~~~~~~~~~~ 4 // 5 // Copyright (c) 2003-2015 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() : next_(0), prev_(0) {} 51 52 private: 53 friend class timer_queue; 54 55 // The operations waiting on the timer. 56 op_queue<wait_op> op_queue_; 57 58 // The index of the timer in the heap. 59 std::size_t heap_index_; 60 61 // Pointers to adjacent timers in a linked list. 62 per_timer_data* next_; 63 per_timer_data* prev_; 64 }; 65 66 // Constructor. timer_queue()67 timer_queue() 68 : timers_(), 69 heap_() 70 { 71 } 72 73 // Add a new timer to the queue. Returns true if this is the timer that is 74 // earliest in the queue, in which case the reactor's event demultiplexing 75 // function call may need to be interrupted and restarted. enqueue_timer(const time_type & time,per_timer_data & timer,wait_op * op)76 bool enqueue_timer(const time_type& time, per_timer_data& timer, wait_op* op) 77 { 78 // Enqueue the timer object. 79 if (timer.prev_ == 0 && &timer != timers_) 80 { 81 if (this->is_positive_infinity(time)) 82 { 83 // No heap entry is required for timers that never expire. 84 timer.heap_index_ = (std::numeric_limits<std::size_t>::max)(); 85 } 86 else 87 { 88 // Put the new timer at the correct position in the heap. This is done 89 // first since push_back() can throw due to allocation failure. 90 timer.heap_index_ = heap_.size(); 91 heap_entry entry = { time, &timer }; 92 heap_.push_back(entry); 93 up_heap(heap_.size() - 1); 94 } 95 96 // Insert the new timer into the linked list of active timers. 97 timer.next_ = timers_; 98 timer.prev_ = 0; 99 if (timers_) 100 timers_->prev_ = &timer; 101 timers_ = &timer; 102 } 103 104 // Enqueue the individual timer operation. 105 timer.op_queue_.push(op); 106 107 // Interrupt reactor only if newly added timer is first to expire. 108 return timer.heap_index_ == 0 && timer.op_queue_.front() == op; 109 } 110 111 // Whether there are no timers in the queue. empty() const112 virtual bool empty() const 113 { 114 return timers_ == 0; 115 } 116 117 // Get the time for the timer that is earliest in the queue. wait_duration_msec(long max_duration) const118 virtual long wait_duration_msec(long max_duration) const 119 { 120 if (heap_.empty()) 121 return max_duration; 122 123 return this->to_msec( 124 Time_Traits::to_posix_duration( 125 Time_Traits::subtract(heap_[0].time_, Time_Traits::now())), 126 max_duration); 127 } 128 129 // Get the time for the timer that is earliest in the queue. wait_duration_usec(long max_duration) const130 virtual long wait_duration_usec(long max_duration) const 131 { 132 if (heap_.empty()) 133 return max_duration; 134 135 return this->to_usec( 136 Time_Traits::to_posix_duration( 137 Time_Traits::subtract(heap_[0].time_, Time_Traits::now())), 138 max_duration); 139 } 140 141 // Dequeue all timers not later than the current time. get_ready_timers(op_queue<operation> & ops)142 virtual void get_ready_timers(op_queue<operation>& ops) 143 { 144 if (!heap_.empty()) 145 { 146 const time_type now = Time_Traits::now(); 147 while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0].time_)) 148 { 149 per_timer_data* timer = heap_[0].timer_; 150 ops.push(timer->op_queue_); 151 remove_timer(*timer); 152 } 153 } 154 } 155 156 // Dequeue all timers. get_all_timers(op_queue<operation> & ops)157 virtual void get_all_timers(op_queue<operation>& ops) 158 { 159 while (timers_) 160 { 161 per_timer_data* timer = timers_; 162 timers_ = timers_->next_; 163 ops.push(timer->op_queue_); 164 timer->next_ = 0; 165 timer->prev_ = 0; 166 } 167 168 heap_.clear(); 169 } 170 171 // 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)())172 std::size_t cancel_timer(per_timer_data& timer, op_queue<operation>& ops, 173 std::size_t max_cancelled = (std::numeric_limits<std::size_t>::max)()) 174 { 175 std::size_t num_cancelled = 0; 176 if (timer.prev_ != 0 || &timer == timers_) 177 { 178 while (wait_op* op = (num_cancelled != max_cancelled) 179 ? timer.op_queue_.front() : 0) 180 { 181 op->ec_ = boost::asio::error::operation_aborted; 182 timer.op_queue_.pop(); 183 ops.push(op); 184 ++num_cancelled; 185 } 186 if (timer.op_queue_.empty()) 187 remove_timer(timer); 188 } 189 return num_cancelled; 190 } 191 192 private: 193 // Move the item at the given index up the heap to its correct position. up_heap(std::size_t index)194 void up_heap(std::size_t index) 195 { 196 while (index > 0) 197 { 198 std::size_t parent = (index - 1) / 2; 199 if (!Time_Traits::less_than(heap_[index].time_, heap_[parent].time_)) 200 break; 201 swap_heap(index, parent); 202 index = parent; 203 } 204 } 205 206 // Move the item at the given index down the heap to its correct position. down_heap(std::size_t index)207 void down_heap(std::size_t index) 208 { 209 std::size_t child = index * 2 + 1; 210 while (child < heap_.size()) 211 { 212 std::size_t min_child = (child + 1 == heap_.size() 213 || Time_Traits::less_than( 214 heap_[child].time_, heap_[child + 1].time_)) 215 ? child : child + 1; 216 if (Time_Traits::less_than(heap_[index].time_, heap_[min_child].time_)) 217 break; 218 swap_heap(index, min_child); 219 index = min_child; 220 child = index * 2 + 1; 221 } 222 } 223 224 // Swap two entries in the heap. swap_heap(std::size_t index1,std::size_t index2)225 void swap_heap(std::size_t index1, std::size_t index2) 226 { 227 heap_entry tmp = heap_[index1]; 228 heap_[index1] = heap_[index2]; 229 heap_[index2] = tmp; 230 heap_[index1].timer_->heap_index_ = index1; 231 heap_[index2].timer_->heap_index_ = index2; 232 } 233 234 // Remove a timer from the heap and list of timers. remove_timer(per_timer_data & timer)235 void remove_timer(per_timer_data& timer) 236 { 237 // Remove the timer from the heap. 238 std::size_t index = timer.heap_index_; 239 if (!heap_.empty() && index < heap_.size()) 240 { 241 if (index == heap_.size() - 1) 242 { 243 heap_.pop_back(); 244 } 245 else 246 { 247 swap_heap(index, heap_.size() - 1); 248 heap_.pop_back(); 249 if (index > 0 && Time_Traits::less_than( 250 heap_[index].time_, heap_[(index - 1) / 2].time_)) 251 up_heap(index); 252 else 253 down_heap(index); 254 } 255 } 256 257 // Remove the timer from the linked list of active timers. 258 if (timers_ == &timer) 259 timers_ = timer.next_; 260 if (timer.prev_) 261 timer.prev_->next_ = timer.next_; 262 if (timer.next_) 263 timer.next_->prev_= timer.prev_; 264 timer.next_ = 0; 265 timer.prev_ = 0; 266 } 267 268 // Determine if the specified absolute time is positive infinity. 269 template <typename Time_Type> is_positive_infinity(const Time_Type &)270 static bool is_positive_infinity(const Time_Type&) 271 { 272 return false; 273 } 274 275 // Determine if the specified absolute time is positive infinity. 276 template <typename T, typename TimeSystem> is_positive_infinity(const boost::date_time::base_time<T,TimeSystem> & time)277 static bool is_positive_infinity( 278 const boost::date_time::base_time<T, TimeSystem>& time) 279 { 280 return time.is_pos_infinity(); 281 } 282 283 // Helper function to convert a duration into milliseconds. 284 template <typename Duration> to_msec(const Duration & d,long max_duration) const285 long to_msec(const Duration& d, long max_duration) const 286 { 287 if (d.ticks() <= 0) 288 return 0; 289 int64_t msec = d.total_milliseconds(); 290 if (msec == 0) 291 return 1; 292 if (msec > max_duration) 293 return max_duration; 294 return static_cast<long>(msec); 295 } 296 297 // Helper function to convert a duration into microseconds. 298 template <typename Duration> to_usec(const Duration & d,long max_duration) const299 long to_usec(const Duration& d, long max_duration) const 300 { 301 if (d.ticks() <= 0) 302 return 0; 303 int64_t usec = d.total_microseconds(); 304 if (usec == 0) 305 return 1; 306 if (usec > max_duration) 307 return max_duration; 308 return static_cast<long>(usec); 309 } 310 311 // The head of a linked list of all active timers. 312 per_timer_data* timers_; 313 314 struct heap_entry 315 { 316 // The time when the timer should fire. 317 time_type time_; 318 319 // The associated timer with enqueued operations. 320 per_timer_data* timer_; 321 }; 322 323 // The heap of timers, with the earliest timer at the front. 324 std::vector<heap_entry> heap_; 325 }; 326 327 } // namespace detail 328 } // namespace asio 329 } // namespace boost 330 331 #include <boost/asio/detail/pop_options.hpp> 332 333 #endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP 334