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: |
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(index: 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&: *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(h: 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. |
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(index1: index, index2: 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(index1: index, index2: 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(index1: index, index2: 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 | |