]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // |
2 | // detail/timer_queue.hpp | |
3 | // ~~~~~~~~~~~~~~~~~~~~~~ | |
4 | // | |
5 | // Copyright (c) 2003-2016 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(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 | ||
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(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 |