boost/asio/detail/timer_queue.hpp

   1 //
   2 // detail/timer_queue.hpp
   3 // ~~~~~~~~~~~~~~~~~~~~~~
   4 //
   5 // Copyright (c) 2003-2019 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() :
  51       heap_index_((std::numeric_limits<std::size_t>::max)()),
  52       next_(0), prev_(0)
  53     {
  54     }
  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_;
 154         ops.push(timer->op_queue_);
 155         remove_timer(*timer);
 156       }
 157     }
 158   }
 159
 160   // Dequeue all timers.
 161   virtual void get_all_timers(op_queue<operation>& ops)
 162   {
 163     while (timers_)
 164     {
 165       per_timer_data* timer = timers_;
 166       timers_ = timers_->next_;
 167       ops.push(timer->op_queue_);
 168       timer->next_ = 0;
 169       timer->prev_ = 0;
 170     }
 171
 172     heap_.clear();
 173   }
 174
 175   // Cancel and dequeue operations for the given timer.
 176   std::size_t cancel_timer(per_timer_data& timer, op_queue<operation>& ops,
 177       std::size_t max_cancelled = (std::numeric_limits<std::size_t>::max)())
 178   {
 179     std::size_t num_cancelled = 0;
 180     if (timer.prev_ != 0 || &timer == timers_)
 181     {
 182       while (wait_op* op = (num_cancelled != max_cancelled)
 183           ? timer.op_queue_.front() : 0)
 184       {
 185         op->ec_ = boost::asio::error::operation_aborted;
 186         timer.op_queue_.pop();
 187         ops.push(op);
 188         ++num_cancelled;
 189       }
 190       if (timer.op_queue_.empty())
 191         remove_timer(timer);
 192     }
 193     return num_cancelled;
 194   }
 195
 196   // Move operations from one timer to another, empty timer.
 197   void move_timer(per_timer_data& target, per_timer_data& source)
 198   {
 199     target.op_queue_.push(source.op_queue_);
 200
 201     target.heap_index_ = source.heap_index_;
 202     source.heap_index_ = (std::numeric_limits<std::size_t>::max)();
 203
 204     if (target.heap_index_ < heap_.size())
 205       heap_[target.heap_index_].timer_ = &target;
 206
 207     if (timers_ == &source)
 208       timers_ = &target;
 209     if (source.prev_)
 210       source.prev_->next_ = &target;
 211     if (source.next_)
 212       source.next_->prev_= &target;
 213     target.next_ = source.next_;
 214     target.prev_ = source.prev_;
 215     source.next_ = 0;
 216     source.prev_ = 0;
 217   }
 218
 219 private:
 220   // Move the item at the given index up the heap to its correct position.
 221   void up_heap(std::size_t index)
 222   {
 223     while (index > 0)
 224     {
 225       std::size_t parent = (index - 1) / 2;
 226       if (!Time_Traits::less_than(heap_[index].time_, heap_[parent].time_))
 227         break;
 228       swap_heap(index, parent);
 229       index = parent;
 230     }
 231   }
 232
 233   // Move the item at the given index down the heap to its correct position.
 234   void down_heap(std::size_t index)
 235   {
 236     std::size_t child = index * 2 + 1;
 237     while (child < heap_.size())
 238     {
 239       std::size_t min_child = (child + 1 == heap_.size()
 240           || Time_Traits::less_than(
 241             heap_[child].time_, heap_[child + 1].time_))
 242         ? child : child + 1;
 243       if (Time_Traits::less_than(heap_[index].time_, heap_[min_child].time_))
 244         break;
 245       swap_heap(index, min_child);
 246       index = min_child;
 247       child = index * 2 + 1;
 248     }
 249   }
 250
 251   // Swap two entries in the heap.
 252   void swap_heap(std::size_t index1, std::size_t index2)
 253   {
 254     heap_entry tmp = heap_[index1];
 255     heap_[index1] = heap_[index2];
 256     heap_[index2] = tmp;
 257     heap_[index1].timer_->heap_index_ = index1;
 258     heap_[index2].timer_->heap_index_ = index2;
 259   }
 260
 261   // Remove a timer from the heap and list of timers.
 262   void remove_timer(per_timer_data& timer)
 263   {
 264     // Remove the timer from the heap.
 265     std::size_t index = timer.heap_index_;
 266     if (!heap_.empty() && index < heap_.size())
 267     {
 268       if (index == heap_.size() - 1)
 269       {
 270         timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
 271         heap_.pop_back();
 272       }
 273       else
 274       {
 275         swap_heap(index, heap_.size() - 1);
 276         timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
 277         heap_.pop_back();
 278         if (index > 0 && Time_Traits::less_than(
 279               heap_[index].time_, heap_[(index - 1) / 2].time_))
 280           up_heap(index);
 281         else
 282           down_heap(index);
 283       }
 284     }
 285
 286     // Remove the timer from the linked list of active timers.
 287     if (timers_ == &timer)
 288       timers_ = timer.next_;
 289     if (timer.prev_)
 290       timer.prev_->next_ = timer.next_;
 291     if (timer.next_)
 292       timer.next_->prev_= timer.prev_;
 293     timer.next_ = 0;
 294     timer.prev_ = 0;
 295   }
 296
 297   // Determine if the specified absolute time is positive infinity.
 298   template <typename Time_Type>
 299   static bool is_positive_infinity(const Time_Type&)
 300   {
 301     return false;
 302   }
 303
 304   // Determine if the specified absolute time is positive infinity.
 305   template <typename T, typename TimeSystem>
 306   static bool is_positive_infinity(
 307       const boost::date_time::base_time<T, TimeSystem>& time)
 308   {
 309     return time.is_pos_infinity();
 310   }
 311
 312   // Helper function to convert a duration into milliseconds.
 313   template <typename Duration>
 314   long to_msec(const Duration& d, long max_duration) const
 315   {
 316     if (d.ticks() <= 0)
 317       return 0;
 318     int64_t msec = d.total_milliseconds();
 319     if (msec == 0)
 320       return 1;
 321     if (msec > max_duration)
 322       return max_duration;
 323     return static_cast<long>(msec);
 324   }
 325
 326   // Helper function to convert a duration into microseconds.
 327   template <typename Duration>
 328   long to_usec(const Duration& d, long max_duration) const
 329   {
 330     if (d.ticks() <= 0)
 331       return 0;
 332     int64_t usec = d.total_microseconds();
 333     if (usec == 0)
 334       return 1;
 335     if (usec > max_duration)
 336       return max_duration;
 337     return static_cast<long>(usec);
 338   }
 339
 340   // The head of a linked list of all active timers.
 341   per_timer_data* timers_;
 342
 343   struct heap_entry
 344   {
 345     // The time when the timer should fire.
 346     time_type time_;
 347
 348     // The associated timer with enqueued operations.
 349     per_timer_data* timer_;
 350   };
 351
 352   // The heap of timers, with the earliest timer at the front.
 353   std::vector<heap_entry> heap_;
 354 };
 355
 356 } // namespace detail
 357 } // namespace asio
 358 } // namespace boost
 359
 360 #include <boost/asio/detail/pop_options.hpp>
 361
 362 #endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP