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
31namespace boost {
32namespace asio {
33namespace detail {
34
35template <typename Time_Traits>
36class timer_queue
37 : public timer_queue_base
38{
39public:
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:
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.
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.
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.
112 virtual bool empty() const
113 {
114 return timers_ == 0;
115 }
116
117 // Get the time for the timer that is earliest in the queue.
118 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.
130 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.
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.
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.
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
192private:
193 // Move the item at the given index up the heap to its correct position.
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.
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.
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.
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>
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>
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>
285 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>
299 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