2 // detail/timer_queue.hpp
3 // ~~~~~~~~~~~~~~~~~~~~~~
5 // Copyright (c) 2003-2022 Christopher M. Kohlhoff (chris at kohlhoff dot com)
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)
11 #ifndef BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP
12 #define BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP
14 #if defined(_MSC_VER) && (_MSC_VER >= 1200)
16 #endif // defined(_MSC_VER) && (_MSC_VER >= 1200)
18 #include <boost/asio/detail/config.hpp>
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>
29 #include <boost/asio/detail/push_options.hpp>
35 template <typename Time_Traits>
37 : public timer_queue_base
41 typedef typename Time_Traits::time_type time_type;
44 typedef typename Time_Traits::duration_type duration_type;
51 heap_index_((std::numeric_limits<std::size_t>::max)()),
57 friend class timer_queue;
59 // The operations waiting on the timer.
60 op_queue<wait_op> op_queue_;
62 // The index of the timer in the heap.
63 std::size_t heap_index_;
65 // Pointers to adjacent timers in a linked list.
66 per_timer_data* next_;
67 per_timer_data* prev_;
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.
80 bool enqueue_timer(const time_type& time, per_timer_data& timer, wait_op* op)
82 // Enqueue the timer object.
83 if (timer.prev_ == 0 && &timer != timers_)
85 if (this->is_positive_infinity(time))
87 // No heap entry is required for timers that never expire.
88 timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
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);
100 // Insert the new timer into the linked list of active timers.
101 timer.next_ = timers_;
104 timers_->prev_ = &timer;
108 // Enqueue the individual timer operation.
109 timer.op_queue_.push(op);
111 // Interrupt reactor only if newly added timer is first to expire.
112 return timer.heap_index_ == 0 && timer.op_queue_.front() == op;
115 // Whether there are no timers in the queue.
116 virtual bool empty() const
121 // Get the time for the timer that is earliest in the queue.
122 virtual long wait_duration_msec(long max_duration) const
127 return this->to_msec(
128 Time_Traits::to_posix_duration(
129 Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
133 // Get the time for the timer that is earliest in the queue.
134 virtual long wait_duration_usec(long max_duration) const
139 return this->to_usec(
140 Time_Traits::to_posix_duration(
141 Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
145 // Dequeue all timers not later than the current time.
146 virtual void get_ready_timers(op_queue<operation>& ops)
150 const time_type now = Time_Traits::now();
151 while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0].time_))
153 per_timer_data* timer = heap_[0].timer_;
154 while (wait_op* op = timer->op_queue_.front())
156 timer->op_queue_.pop();
157 op->ec_ = boost::system::error_code();
160 remove_timer(*timer);
165 // Dequeue all timers.
166 virtual void get_all_timers(op_queue<operation>& ops)
170 per_timer_data* timer = timers_;
171 timers_ = timers_->next_;
172 ops.push(timer->op_queue_);
180 // Cancel and dequeue operations for the given timer.
181 std::size_t cancel_timer(per_timer_data& timer, op_queue<operation>& ops,
182 std::size_t max_cancelled = (std::numeric_limits<std::size_t>::max)())
184 std::size_t num_cancelled = 0;
185 if (timer.prev_ != 0 || &timer == timers_)
187 while (wait_op* op = (num_cancelled != max_cancelled)
188 ? timer.op_queue_.front() : 0)
190 op->ec_ = boost::asio::error::operation_aborted;
191 timer.op_queue_.pop();
195 if (timer.op_queue_.empty())
198 return num_cancelled;
201 // Cancel and dequeue a specific operation for the given timer.
202 void cancel_timer_by_key(per_timer_data* timer,
203 op_queue<operation>& ops, void* cancellation_key)
205 if (timer->prev_ != 0 || timer == timers_)
207 op_queue<wait_op> other_ops;
208 while (wait_op* op = timer->op_queue_.front())
210 timer->op_queue_.pop();
211 if (op->cancellation_key_ == cancellation_key)
213 op->ec_ = boost::asio::error::operation_aborted;
219 timer->op_queue_.push(other_ops);
220 if (timer->op_queue_.empty())
221 remove_timer(*timer);
225 // Move operations from one timer to another, empty timer.
226 void move_timer(per_timer_data& target, per_timer_data& source)
228 target.op_queue_.push(source.op_queue_);
230 target.heap_index_ = source.heap_index_;
231 source.heap_index_ = (std::numeric_limits<std::size_t>::max)();
233 if (target.heap_index_ < heap_.size())
234 heap_[target.heap_index_].timer_ = ⌖
236 if (timers_ == &source)
239 source.prev_->next_ = ⌖
241 source.next_->prev_= ⌖
242 target.next_ = source.next_;
243 target.prev_ = source.prev_;
249 // Move the item at the given index up the heap to its correct position.
250 void up_heap(std::size_t index)
254 std::size_t parent = (index - 1) / 2;
255 if (!Time_Traits::less_than(heap_[index].time_, heap_[parent].time_))
257 swap_heap(index, parent);
262 // Move the item at the given index down the heap to its correct position.
263 void down_heap(std::size_t index)
265 std::size_t child = index * 2 + 1;
266 while (child < heap_.size())
268 std::size_t min_child = (child + 1 == heap_.size()
269 || Time_Traits::less_than(
270 heap_[child].time_, heap_[child + 1].time_))
272 if (Time_Traits::less_than(heap_[index].time_, heap_[min_child].time_))
274 swap_heap(index, min_child);
276 child = index * 2 + 1;
280 // Swap two entries in the heap.
281 void swap_heap(std::size_t index1, std::size_t index2)
283 heap_entry tmp = heap_[index1];
284 heap_[index1] = heap_[index2];
286 heap_[index1].timer_->heap_index_ = index1;
287 heap_[index2].timer_->heap_index_ = index2;
290 // Remove a timer from the heap and list of timers.
291 void remove_timer(per_timer_data& timer)
293 // Remove the timer from the heap.
294 std::size_t index = timer.heap_index_;
295 if (!heap_.empty() && index < heap_.size())
297 if (index == heap_.size() - 1)
299 timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
304 swap_heap(index, heap_.size() - 1);
305 timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
307 if (index > 0 && Time_Traits::less_than(
308 heap_[index].time_, heap_[(index - 1) / 2].time_))
315 // Remove the timer from the linked list of active timers.
316 if (timers_ == &timer)
317 timers_ = timer.next_;
319 timer.prev_->next_ = timer.next_;
321 timer.next_->prev_= timer.prev_;
326 // Determine if the specified absolute time is positive infinity.
327 template <typename Time_Type>
328 static bool is_positive_infinity(const Time_Type&)
333 // Determine if the specified absolute time is positive infinity.
334 template <typename T, typename TimeSystem>
335 static bool is_positive_infinity(
336 const boost::date_time::base_time<T, TimeSystem>& time)
338 return time.is_pos_infinity();
341 // Helper function to convert a duration into milliseconds.
342 template <typename Duration>
343 long to_msec(const Duration& d, long max_duration) const
347 int64_t msec = d.total_milliseconds();
350 if (msec > max_duration)
352 return static_cast<long>(msec);
355 // Helper function to convert a duration into microseconds.
356 template <typename Duration>
357 long to_usec(const Duration& d, long max_duration) const
361 int64_t usec = d.total_microseconds();
364 if (usec > max_duration)
366 return static_cast<long>(usec);
369 // The head of a linked list of all active timers.
370 per_timer_data* timers_;
374 // The time when the timer should fire.
377 // The associated timer with enqueued operations.
378 per_timer_data* timer_;
381 // The heap of timers, with the earliest timer at the front.
382 std::vector<heap_entry> heap_;
385 } // namespace detail
389 #include <boost/asio/detail/pop_options.hpp>
391 #endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP