]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // |
2 | // detail/timer_queue.hpp | |
3 | // ~~~~~~~~~~~~~~~~~~~~~~ | |
4 | // | |
1e59de90 | 5 | // Copyright (c) 2003-2022 Christopher M. Kohlhoff (chris at kohlhoff dot com) |
7c673cae FG |
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: | |
b32b8144 FG |
50 | per_timer_data() : |
51 | heap_index_((std::numeric_limits<std::size_t>::max)()), | |
52 | next_(0), prev_(0) | |
53 | { | |
54 | } | |
7c673cae FG |
55 | |
56 | private: | |
57 | friend class timer_queue; | |
58 | ||
59 | // The operations waiting on the timer. | |
60 | op_queue<wait_op> op_queue_; | |
61 | ||
62 | // The index of the timer in the heap. | |
63 | std::size_t heap_index_; | |
64 | ||
65 | // Pointers to adjacent timers in a linked list. | |
66 | per_timer_data* next_; | |
67 | per_timer_data* prev_; | |
68 | }; | |
69 | ||
70 | // Constructor. | |
71 | timer_queue() | |
72 | : timers_(), | |
73 | heap_() | |
74 | { | |
75 | } | |
76 | ||
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) | |
81 | { | |
82 | // Enqueue the timer object. | |
83 | if (timer.prev_ == 0 && &timer != timers_) | |
84 | { | |
85 | if (this->is_positive_infinity(time)) | |
86 | { | |
87 | // No heap entry is required for timers that never expire. | |
88 | timer.heap_index_ = (std::numeric_limits<std::size_t>::max)(); | |
89 | } | |
90 | else | |
91 | { | |
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); | |
98 | } | |
99 | ||
100 | // Insert the new timer into the linked list of active timers. | |
101 | timer.next_ = timers_; | |
102 | timer.prev_ = 0; | |
103 | if (timers_) | |
104 | timers_->prev_ = &timer; | |
105 | timers_ = &timer; | |
106 | } | |
107 | ||
108 | // Enqueue the individual timer operation. | |
109 | timer.op_queue_.push(op); | |
110 | ||
111 | // Interrupt reactor only if newly added timer is first to expire. | |
112 | return timer.heap_index_ == 0 && timer.op_queue_.front() == op; | |
113 | } | |
114 | ||
115 | // Whether there are no timers in the queue. | |
116 | virtual bool empty() const | |
117 | { | |
118 | return timers_ == 0; | |
119 | } | |
120 | ||
121 | // Get the time for the timer that is earliest in the queue. | |
122 | virtual long wait_duration_msec(long max_duration) const | |
123 | { | |
124 | if (heap_.empty()) | |
125 | return max_duration; | |
126 | ||
127 | return this->to_msec( | |
128 | Time_Traits::to_posix_duration( | |
129 | Time_Traits::subtract(heap_[0].time_, Time_Traits::now())), | |
130 | max_duration); | |
131 | } | |
132 | ||
133 | // Get the time for the timer that is earliest in the queue. | |
134 | virtual long wait_duration_usec(long max_duration) const | |
135 | { | |
136 | if (heap_.empty()) | |
137 | return max_duration; | |
138 | ||
139 | return this->to_usec( | |
140 | Time_Traits::to_posix_duration( | |
141 | Time_Traits::subtract(heap_[0].time_, Time_Traits::now())), | |
142 | max_duration); | |
143 | } | |
144 | ||
145 | // Dequeue all timers not later than the current time. | |
146 | virtual void get_ready_timers(op_queue<operation>& ops) | |
147 | { | |
148 | if (!heap_.empty()) | |
149 | { | |
150 | const time_type now = Time_Traits::now(); | |
151 | while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0].time_)) | |
152 | { | |
153 | per_timer_data* timer = heap_[0].timer_; | |
1e59de90 TL |
154 | while (wait_op* op = timer->op_queue_.front()) |
155 | { | |
156 | timer->op_queue_.pop(); | |
157 | op->ec_ = boost::system::error_code(); | |
158 | ops.push(op); | |
159 | } | |
7c673cae FG |
160 | remove_timer(*timer); |
161 | } | |
162 | } | |
163 | } | |
164 | ||
165 | // Dequeue all timers. | |
166 | virtual void get_all_timers(op_queue<operation>& ops) | |
167 | { | |
168 | while (timers_) | |
169 | { | |
170 | per_timer_data* timer = timers_; | |
171 | timers_ = timers_->next_; | |
172 | ops.push(timer->op_queue_); | |
173 | timer->next_ = 0; | |
174 | timer->prev_ = 0; | |
175 | } | |
176 | ||
177 | heap_.clear(); | |
178 | } | |
179 | ||
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)()) | |
183 | { | |
184 | std::size_t num_cancelled = 0; | |
185 | if (timer.prev_ != 0 || &timer == timers_) | |
186 | { | |
187 | while (wait_op* op = (num_cancelled != max_cancelled) | |
188 | ? timer.op_queue_.front() : 0) | |
189 | { | |
190 | op->ec_ = boost::asio::error::operation_aborted; | |
191 | timer.op_queue_.pop(); | |
192 | ops.push(op); | |
193 | ++num_cancelled; | |
194 | } | |
195 | if (timer.op_queue_.empty()) | |
196 | remove_timer(timer); | |
197 | } | |
198 | return num_cancelled; | |
199 | } | |
200 | ||
1e59de90 TL |
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) | |
204 | { | |
205 | if (timer->prev_ != 0 || timer == timers_) | |
206 | { | |
207 | op_queue<wait_op> other_ops; | |
208 | while (wait_op* op = timer->op_queue_.front()) | |
209 | { | |
210 | timer->op_queue_.pop(); | |
211 | if (op->cancellation_key_ == cancellation_key) | |
212 | { | |
213 | op->ec_ = boost::asio::error::operation_aborted; | |
214 | ops.push(op); | |
215 | } | |
216 | else | |
217 | other_ops.push(op); | |
218 | } | |
219 | timer->op_queue_.push(other_ops); | |
220 | if (timer->op_queue_.empty()) | |
221 | remove_timer(*timer); | |
222 | } | |
223 | } | |
224 | ||
b32b8144 FG |
225 | // Move operations from one timer to another, empty timer. |
226 | void move_timer(per_timer_data& target, per_timer_data& source) | |
227 | { | |
228 | target.op_queue_.push(source.op_queue_); | |
229 | ||
230 | target.heap_index_ = source.heap_index_; | |
231 | source.heap_index_ = (std::numeric_limits<std::size_t>::max)(); | |
232 | ||
233 | if (target.heap_index_ < heap_.size()) | |
234 | heap_[target.heap_index_].timer_ = ⌖ | |
235 | ||
236 | if (timers_ == &source) | |
237 | timers_ = ⌖ | |
238 | if (source.prev_) | |
239 | source.prev_->next_ = ⌖ | |
240 | if (source.next_) | |
241 | source.next_->prev_= ⌖ | |
242 | target.next_ = source.next_; | |
243 | target.prev_ = source.prev_; | |
244 | source.next_ = 0; | |
245 | source.prev_ = 0; | |
246 | } | |
247 | ||
7c673cae FG |
248 | private: |
249 | // Move the item at the given index up the heap to its correct position. | |
250 | void up_heap(std::size_t index) | |
251 | { | |
252 | while (index > 0) | |
253 | { | |
254 | std::size_t parent = (index - 1) / 2; | |
255 | if (!Time_Traits::less_than(heap_[index].time_, heap_[parent].time_)) | |
256 | break; | |
257 | swap_heap(index, parent); | |
258 | index = parent; | |
259 | } | |
260 | } | |
261 | ||
262 | // Move the item at the given index down the heap to its correct position. | |
263 | void down_heap(std::size_t index) | |
264 | { | |
265 | std::size_t child = index * 2 + 1; | |
266 | while (child < heap_.size()) | |
267 | { | |
268 | std::size_t min_child = (child + 1 == heap_.size() | |
269 | || Time_Traits::less_than( | |
270 | heap_[child].time_, heap_[child + 1].time_)) | |
271 | ? child : child + 1; | |
272 | if (Time_Traits::less_than(heap_[index].time_, heap_[min_child].time_)) | |
273 | break; | |
274 | swap_heap(index, min_child); | |
275 | index = min_child; | |
276 | child = index * 2 + 1; | |
277 | } | |
278 | } | |
279 | ||
280 | // Swap two entries in the heap. | |
281 | void swap_heap(std::size_t index1, std::size_t index2) | |
282 | { | |
283 | heap_entry tmp = heap_[index1]; | |
284 | heap_[index1] = heap_[index2]; | |
285 | heap_[index2] = tmp; | |
286 | heap_[index1].timer_->heap_index_ = index1; | |
287 | heap_[index2].timer_->heap_index_ = index2; | |
288 | } | |
289 | ||
290 | // Remove a timer from the heap and list of timers. | |
291 | void remove_timer(per_timer_data& timer) | |
292 | { | |
293 | // Remove the timer from the heap. | |
294 | std::size_t index = timer.heap_index_; | |
295 | if (!heap_.empty() && index < heap_.size()) | |
296 | { | |
297 | if (index == heap_.size() - 1) | |
298 | { | |
92f5a8d4 | 299 | timer.heap_index_ = (std::numeric_limits<std::size_t>::max)(); |
7c673cae FG |
300 | heap_.pop_back(); |
301 | } | |
302 | else | |
303 | { | |
304 | swap_heap(index, heap_.size() - 1); | |
92f5a8d4 | 305 | timer.heap_index_ = (std::numeric_limits<std::size_t>::max)(); |
7c673cae FG |
306 | heap_.pop_back(); |
307 | if (index > 0 && Time_Traits::less_than( | |
308 | heap_[index].time_, heap_[(index - 1) / 2].time_)) | |
309 | up_heap(index); | |
310 | else | |
311 | down_heap(index); | |
312 | } | |
313 | } | |
314 | ||
315 | // Remove the timer from the linked list of active timers. | |
316 | if (timers_ == &timer) | |
317 | timers_ = timer.next_; | |
318 | if (timer.prev_) | |
319 | timer.prev_->next_ = timer.next_; | |
320 | if (timer.next_) | |
321 | timer.next_->prev_= timer.prev_; | |
322 | timer.next_ = 0; | |
323 | timer.prev_ = 0; | |
324 | } | |
325 | ||
326 | // Determine if the specified absolute time is positive infinity. | |
327 | template <typename Time_Type> | |
328 | static bool is_positive_infinity(const Time_Type&) | |
329 | { | |
330 | return false; | |
331 | } | |
332 | ||
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) | |
337 | { | |
338 | return time.is_pos_infinity(); | |
339 | } | |
340 | ||
341 | // Helper function to convert a duration into milliseconds. | |
342 | template <typename Duration> | |
343 | long to_msec(const Duration& d, long max_duration) const | |
344 | { | |
345 | if (d.ticks() <= 0) | |
346 | return 0; | |
347 | int64_t msec = d.total_milliseconds(); | |
348 | if (msec == 0) | |
349 | return 1; | |
350 | if (msec > max_duration) | |
351 | return max_duration; | |
352 | return static_cast<long>(msec); | |
353 | } | |
354 | ||
355 | // Helper function to convert a duration into microseconds. | |
356 | template <typename Duration> | |
357 | long to_usec(const Duration& d, long max_duration) const | |
358 | { | |
359 | if (d.ticks() <= 0) | |
360 | return 0; | |
361 | int64_t usec = d.total_microseconds(); | |
362 | if (usec == 0) | |
363 | return 1; | |
364 | if (usec > max_duration) | |
365 | return max_duration; | |
366 | return static_cast<long>(usec); | |
367 | } | |
368 | ||
369 | // The head of a linked list of all active timers. | |
370 | per_timer_data* timers_; | |
371 | ||
372 | struct heap_entry | |
373 | { | |
374 | // The time when the timer should fire. | |
375 | time_type time_; | |
376 | ||
377 | // The associated timer with enqueued operations. | |
378 | per_timer_data* timer_; | |
379 | }; | |
380 | ||
381 | // The heap of timers, with the earliest timer at the front. | |
382 | std::vector<heap_entry> heap_; | |
383 | }; | |
384 | ||
385 | } // namespace detail | |
386 | } // namespace asio | |
387 | } // namespace boost | |
388 | ||
389 | #include <boost/asio/detail/pop_options.hpp> | |
390 | ||
391 | #endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP |