boost/asio/detail/timer_queue.hpp

   1 //
   2 // detail/timer_queue.hpp
   3 // ~~~~~~~~~~~~~~~~~~~~~~
   4 //
   5 // Copyright (c) 2003-2014 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     std::size_t parent = (index - 1) / 2;
 197     while (index > 0
 198         && Time_Traits::less_than(heap_[index].time_, heap_[parent].time_))
 199     {
 200       swap_heap(index, parent);
 201       index = parent;
 202       parent = (index - 1) / 2;
 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         std::size_t parent = (index - 1) / 2;
 250         if (index > 0 && Time_Traits::less_than(
 251               heap_[index].time_, heap_[parent].time_))
 252           up_heap(index);
 253         else
 254           down_heap(index);
 255       }
 256     }
 257
 258     // Remove the timer from the linked list of active timers.
 259     if (timers_ == &timer)
 260       timers_ = timer.next_;
 261     if (timer.prev_)
 262       timer.prev_->next_ = timer.next_;
 263     if (timer.next_)
 264       timer.next_->prev_= timer.prev_;
 265     timer.next_ = 0;
 266     timer.prev_ = 0;
 267   }
 268
 269   // Determine if the specified absolute time is positive infinity.
 270   template <typename Time_Type>
 271   static bool is_positive_infinity(const Time_Type&)
 272   {
 273     return false;
 274   }
 275
 276   // Determine if the specified absolute time is positive infinity.
 277   template <typename T, typename TimeSystem>
 278   static bool is_positive_infinity(
 279       const boost::date_time::base_time<T, TimeSystem>& time)
 280   {
 281     return time.is_pos_infinity();
 282   }
 283
 284   // Helper function to convert a duration into milliseconds.
 285   template <typename Duration>
 286   long to_msec(const Duration& d, long max_duration) const
 287   {
 288     if (d.ticks() <= 0)
 289       return 0;
 290     int64_t msec = d.total_milliseconds();
 291     if (msec == 0)
 292       return 1;
 293     if (msec > max_duration)
 294       return max_duration;
 295     return static_cast<long>(msec);
 296   }
 297
 298   // Helper function to convert a duration into microseconds.
 299   template <typename Duration>
 300   long to_usec(const Duration& d, long max_duration) const
 301   {
 302     if (d.ticks() <= 0)
 303       return 0;
 304     int64_t usec = d.total_microseconds();
 305     if (usec == 0)
 306       return 1;
 307     if (usec > max_duration)
 308       return max_duration;
 309     return static_cast<long>(usec);
 310   }
 311
 312   // The head of a linked list of all active timers.
 313   per_timer_data* timers_;
 314
 315   struct heap_entry
 316   {
 317     // The time when the timer should fire.
 318     time_type time_;
 319
 320     // The associated timer with enqueued operations.
 321     per_timer_data* timer_;
 322   };
 323
 324   // The heap of timers, with the earliest timer at the front.
 325   std::vector<heap_entry> heap_;
 326 };
 327
 328 } // namespace detail
 329 } // namespace asio
 330 } // namespace boost
 331
 332 #include <boost/asio/detail/pop_options.hpp>
 333
 334 #endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP