Realistic 3D camera system
3D camera system components
timer_queue.hpp
Go to the documentation of this file.
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 ASIO_DETAIL_TIMER_QUEUE_HPP
12 #define 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 "asio/detail/config.hpp"
19 #include <cstddef>
20 #include <vector>
21 #include "asio/detail/cstdint.hpp"
23 #include "asio/detail/limits.hpp"
24 #include "asio/detail/op_queue.hpp"
26 #include "asio/detail/wait_op.hpp"
27 #include "asio/error.hpp"
28 
30 
31 namespace asio {
32 namespace detail {
33 
34 template <typename Time_Traits>
36  : public timer_queue_base
37 {
38 public:
39  // The time type.
40  typedef typename Time_Traits::time_type time_type;
41 
42  // The duration type.
43  typedef typename Time_Traits::duration_type duration_type;
44 
45  // Per-timer data.
47  {
48  public:
49  per_timer_data() : next_(0), prev_(0) {}
50 
51  private:
52  friend class timer_queue;
53 
54  // The operations waiting on the timer.
55  op_queue<wait_op> op_queue_;
56 
57  // The index of the timer in the heap.
58  std::size_t heap_index_;
59 
60  // Pointers to adjacent timers in a linked list.
61  per_timer_data* next_;
62  per_timer_data* prev_;
63  };
64 
65  // Constructor.
67  : timers_(),
68  heap_()
69  {
70  }
71 
72  // Add a new timer to the queue. Returns true if this is the timer that is
73  // earliest in the queue, in which case the reactor's event demultiplexing
74  // function call may need to be interrupted and restarted.
75  bool enqueue_timer(const time_type& time, per_timer_data& timer, wait_op* op)
76  {
77  // Enqueue the timer object.
78  if (timer.prev_ == 0 && &timer != timers_)
79  {
80  if (this->is_positive_infinity(time))
81  {
82  // No heap entry is required for timers that never expire.
83  timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
84  }
85  else
86  {
87  // Put the new timer at the correct position in the heap. This is done
88  // first since push_back() can throw due to allocation failure.
89  timer.heap_index_ = heap_.size();
90  heap_entry entry = { time, &timer };
91  heap_.push_back(entry);
92  up_heap(heap_.size() - 1);
93  }
94 
95  // Insert the new timer into the linked list of active timers.
96  timer.next_ = timers_;
97  timer.prev_ = 0;
98  if (timers_)
99  timers_->prev_ = &timer;
100  timers_ = &timer;
101  }
102 
103  // Enqueue the individual timer operation.
104  timer.op_queue_.push(op);
105 
106  // Interrupt reactor only if newly added timer is first to expire.
107  return timer.heap_index_ == 0 && timer.op_queue_.front() == op;
108  }
109 
110  // Whether there are no timers in the queue.
111  virtual bool empty() const
112  {
113  return timers_ == 0;
114  }
115 
116  // Get the time for the timer that is earliest in the queue.
117  virtual long wait_duration_msec(long max_duration) const
118  {
119  if (heap_.empty())
120  return max_duration;
121 
122  return this->to_msec(
123  Time_Traits::to_posix_duration(
124  Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
125  max_duration);
126  }
127 
128  // Get the time for the timer that is earliest in the queue.
129  virtual long wait_duration_usec(long max_duration) const
130  {
131  if (heap_.empty())
132  return max_duration;
133 
134  return this->to_usec(
135  Time_Traits::to_posix_duration(
136  Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
137  max_duration);
138  }
139 
140  // Dequeue all timers not later than the current time.
142  {
143  if (!heap_.empty())
144  {
145  const time_type now = Time_Traits::now();
146  while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0].time_))
147  {
148  per_timer_data* timer = heap_[0].timer_;
149  ops.push(timer->op_queue_);
150  remove_timer(*timer);
151  }
152  }
153  }
154 
155  // Dequeue all timers.
157  {
158  while (timers_)
159  {
160  per_timer_data* timer = timers_;
161  timers_ = timers_->next_;
162  ops.push(timer->op_queue_);
163  timer->next_ = 0;
164  timer->prev_ = 0;
165  }
166 
167  heap_.clear();
168  }
169 
170  // Cancel and dequeue operations for the given timer.
172  std::size_t max_cancelled = (std::numeric_limits<std::size_t>::max)())
173  {
174  std::size_t num_cancelled = 0;
175  if (timer.prev_ != 0 || &timer == timers_)
176  {
177  while (wait_op* op = (num_cancelled != max_cancelled)
178  ? timer.op_queue_.front() : 0)
179  {
181  timer.op_queue_.pop();
182  ops.push(op);
183  ++num_cancelled;
184  }
185  if (timer.op_queue_.empty())
186  remove_timer(timer);
187  }
188  return num_cancelled;
189  }
190 
191 private:
192  // Move the item at the given index up the heap to its correct position.
193  void up_heap(std::size_t index)
194  {
195  while (index > 0)
196  {
197  std::size_t parent = (index - 1) / 2;
198  if (!Time_Traits::less_than(heap_[index].time_, heap_[parent].time_))
199  break;
200  swap_heap(index, parent);
201  index = parent;
202  }
203  }
204 
205  // Move the item at the given index down the heap to its correct position.
206  void down_heap(std::size_t index)
207  {
208  std::size_t child = index * 2 + 1;
209  while (child < heap_.size())
210  {
211  std::size_t min_child = (child + 1 == heap_.size()
212  || Time_Traits::less_than(
213  heap_[child].time_, heap_[child + 1].time_))
214  ? child : child + 1;
215  if (Time_Traits::less_than(heap_[index].time_, heap_[min_child].time_))
216  break;
217  swap_heap(index, min_child);
218  index = min_child;
219  child = index * 2 + 1;
220  }
221  }
222 
223  // Swap two entries in the heap.
224  void swap_heap(std::size_t index1, std::size_t index2)
225  {
226  heap_entry tmp = heap_[index1];
227  heap_[index1] = heap_[index2];
228  heap_[index2] = tmp;
229  heap_[index1].timer_->heap_index_ = index1;
230  heap_[index2].timer_->heap_index_ = index2;
231  }
232 
233  // Remove a timer from the heap and list of timers.
234  void remove_timer(per_timer_data& timer)
235  {
236  // Remove the timer from the heap.
237  std::size_t index = timer.heap_index_;
238  if (!heap_.empty() && index < heap_.size())
239  {
240  if (index == heap_.size() - 1)
241  {
242  heap_.pop_back();
243  }
244  else
245  {
246  swap_heap(index, heap_.size() - 1);
247  heap_.pop_back();
248  if (index > 0 && Time_Traits::less_than(
249  heap_[index].time_, heap_[(index - 1) / 2].time_))
250  up_heap(index);
251  else
252  down_heap(index);
253  }
254  }
255 
256  // Remove the timer from the linked list of active timers.
257  if (timers_ == &timer)
258  timers_ = timer.next_;
259  if (timer.prev_)
260  timer.prev_->next_ = timer.next_;
261  if (timer.next_)
262  timer.next_->prev_= timer.prev_;
263  timer.next_ = 0;
264  timer.prev_ = 0;
265  }
266 
267  // Determine if the specified absolute time is positive infinity.
268  template <typename Time_Type>
269  static bool is_positive_infinity(const Time_Type&)
270  {
271  return false;
272  }
273 
274  // Determine if the specified absolute time is positive infinity.
275  template <typename T, typename TimeSystem>
276  static bool is_positive_infinity(
278  {
279  return time.is_pos_infinity();
280  }
281 
282  // Helper function to convert a duration into milliseconds.
283  template <typename Duration>
284  long to_msec(const Duration& d, long max_duration) const
285  {
286  if (d.ticks() <= 0)
287  return 0;
288  int64_t msec = d.total_milliseconds();
289  if (msec == 0)
290  return 1;
291  if (msec > max_duration)
292  return max_duration;
293  return static_cast<long>(msec);
294  }
295 
296  // Helper function to convert a duration into microseconds.
297  template <typename Duration>
298  long to_usec(const Duration& d, long max_duration) const
299  {
300  if (d.ticks() <= 0)
301  return 0;
302  int64_t usec = d.total_microseconds();
303  if (usec == 0)
304  return 1;
305  if (usec > max_duration)
306  return max_duration;
307  return static_cast<long>(usec);
308  }
309 
310  // The head of a linked list of all active timers.
311  per_timer_data* timers_;
312 
313  struct heap_entry
314  {
315  // The time when the timer should fire.
316  time_type time_;
317 
318  // The associated timer with enqueued operations.
319  per_timer_data* timer_;
320  };
321 
322  // The heap of timers, with the earliest timer at the front.
323  std::vector<heap_entry> heap_;
324 };
325 
326 } // namespace detail
327 } // namespace asio
328 
330 
331 #endif // ASIO_DETAIL_TIMER_QUEUE_HPP
virtual void get_ready_timers(op_queue< operation > &ops)
Operation cancelled.
Definition: error.hpp:161
virtual long wait_duration_usec(long max_duration) const
Time_Traits::time_type time_type
Definition: timer_queue.hpp:40
virtual bool empty() const
virtual long wait_duration_msec(long max_duration) const
virtual void get_all_timers(op_queue< operation > &ops)
void push(Operation *h)
Definition: op_queue.hpp:104
bool enqueue_timer(const time_type &time, per_timer_data &timer, wait_op *op)
Definition: timer_queue.hpp:75
Time_Traits::duration_type duration_type
Definition: timer_queue.hpp:43
std::size_t cancel_timer(per_timer_data &timer, op_queue< operation > &ops, std::size_t max_cancelled=(std::numeric_limits< std::size_t >::max)())