Chris@16: //
Chris@16: // detail/timer_queue.hpp
Chris@16: // ~~~~~~~~~~~~~~~~~~~~~~
Chris@16: //
Chris@101: // Copyright (c) 2003-2015 Christopher M. Kohlhoff (chris at kohlhoff dot com)
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See accompanying
Chris@16: // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: 
Chris@16: #ifndef BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP
Chris@16: #define BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP
Chris@16: 
Chris@16: #if defined(_MSC_VER) && (_MSC_VER >= 1200)
Chris@16: # pragma once
Chris@16: #endif // defined(_MSC_VER) && (_MSC_VER >= 1200)
Chris@16: 
Chris@16: #include <boost/asio/detail/config.hpp>
Chris@16: #include <cstddef>
Chris@16: #include <vector>
Chris@16: #include <boost/asio/detail/cstdint.hpp>
Chris@16: #include <boost/asio/detail/date_time_fwd.hpp>
Chris@16: #include <boost/asio/detail/limits.hpp>
Chris@16: #include <boost/asio/detail/op_queue.hpp>
Chris@16: #include <boost/asio/detail/timer_queue_base.hpp>
Chris@16: #include <boost/asio/detail/wait_op.hpp>
Chris@16: #include <boost/asio/error.hpp>
Chris@16: 
Chris@16: #include <boost/asio/detail/push_options.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace asio {
Chris@16: namespace detail {
Chris@16: 
Chris@16: template <typename Time_Traits>
Chris@16: class timer_queue
Chris@16:   : public timer_queue_base
Chris@16: {
Chris@16: public:
Chris@16:   // The time type.
Chris@16:   typedef typename Time_Traits::time_type time_type;
Chris@16: 
Chris@16:   // The duration type.
Chris@16:   typedef typename Time_Traits::duration_type duration_type;
Chris@16: 
Chris@16:   // Per-timer data.
Chris@16:   class per_timer_data
Chris@16:   {
Chris@16:   public:
Chris@16:     per_timer_data() : next_(0), prev_(0) {}
Chris@16: 
Chris@16:   private:
Chris@16:     friend class timer_queue;
Chris@16: 
Chris@16:     // The operations waiting on the timer.
Chris@16:     op_queue<wait_op> op_queue_;
Chris@16: 
Chris@16:     // The index of the timer in the heap.
Chris@16:     std::size_t heap_index_;
Chris@16: 
Chris@16:     // Pointers to adjacent timers in a linked list.
Chris@16:     per_timer_data* next_;
Chris@16:     per_timer_data* prev_;
Chris@16:   };
Chris@16: 
Chris@16:   // Constructor.
Chris@16:   timer_queue()
Chris@16:     : timers_(),
Chris@16:       heap_()
Chris@16:   {
Chris@16:   }
Chris@16: 
Chris@16:   // Add a new timer to the queue. Returns true if this is the timer that is
Chris@16:   // earliest in the queue, in which case the reactor's event demultiplexing
Chris@16:   // function call may need to be interrupted and restarted.
Chris@16:   bool enqueue_timer(const time_type& time, per_timer_data& timer, wait_op* op)
Chris@16:   {
Chris@16:     // Enqueue the timer object.
Chris@16:     if (timer.prev_ == 0 && &timer != timers_)
Chris@16:     {
Chris@16:       if (this->is_positive_infinity(time))
Chris@16:       {
Chris@16:         // No heap entry is required for timers that never expire.
Chris@16:         timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
Chris@16:       }
Chris@16:       else
Chris@16:       {
Chris@16:         // Put the new timer at the correct position in the heap. This is done
Chris@16:         // first since push_back() can throw due to allocation failure.
Chris@16:         timer.heap_index_ = heap_.size();
Chris@16:         heap_entry entry = { time, &timer };
Chris@16:         heap_.push_back(entry);
Chris@16:         up_heap(heap_.size() - 1);
Chris@16:       }
Chris@16: 
Chris@16:       // Insert the new timer into the linked list of active timers.
Chris@16:       timer.next_ = timers_;
Chris@16:       timer.prev_ = 0;
Chris@16:       if (timers_)
Chris@16:         timers_->prev_ = &timer;
Chris@16:       timers_ = &timer;
Chris@16:     }
Chris@16: 
Chris@16:     // Enqueue the individual timer operation.
Chris@16:     timer.op_queue_.push(op);
Chris@16: 
Chris@16:     // Interrupt reactor only if newly added timer is first to expire.
Chris@16:     return timer.heap_index_ == 0 && timer.op_queue_.front() == op;
Chris@16:   }
Chris@16: 
Chris@16:   // Whether there are no timers in the queue.
Chris@16:   virtual bool empty() const
Chris@16:   {
Chris@16:     return timers_ == 0;
Chris@16:   }
Chris@16: 
Chris@16:   // Get the time for the timer that is earliest in the queue.
Chris@16:   virtual long wait_duration_msec(long max_duration) const
Chris@16:   {
Chris@16:     if (heap_.empty())
Chris@16:       return max_duration;
Chris@16: 
Chris@16:     return this->to_msec(
Chris@16:         Time_Traits::to_posix_duration(
Chris@16:           Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
Chris@16:         max_duration);
Chris@16:   }
Chris@16: 
Chris@16:   // Get the time for the timer that is earliest in the queue.
Chris@16:   virtual long wait_duration_usec(long max_duration) const
Chris@16:   {
Chris@16:     if (heap_.empty())
Chris@16:       return max_duration;
Chris@16: 
Chris@16:     return this->to_usec(
Chris@16:         Time_Traits::to_posix_duration(
Chris@16:           Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
Chris@16:         max_duration);
Chris@16:   }
Chris@16: 
Chris@16:   // Dequeue all timers not later than the current time.
Chris@16:   virtual void get_ready_timers(op_queue<operation>& ops)
Chris@16:   {
Chris@16:     if (!heap_.empty())
Chris@16:     {
Chris@16:       const time_type now = Time_Traits::now();
Chris@16:       while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0].time_))
Chris@16:       {
Chris@16:         per_timer_data* timer = heap_[0].timer_;
Chris@16:         ops.push(timer->op_queue_);
Chris@16:         remove_timer(*timer);
Chris@16:       }
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   // Dequeue all timers.
Chris@16:   virtual void get_all_timers(op_queue<operation>& ops)
Chris@16:   {
Chris@16:     while (timers_)
Chris@16:     {
Chris@16:       per_timer_data* timer = timers_;
Chris@16:       timers_ = timers_->next_;
Chris@16:       ops.push(timer->op_queue_);
Chris@16:       timer->next_ = 0;
Chris@16:       timer->prev_ = 0;
Chris@16:     }
Chris@16: 
Chris@16:     heap_.clear();
Chris@16:   }
Chris@16: 
Chris@16:   // Cancel and dequeue operations for the given timer.
Chris@16:   std::size_t cancel_timer(per_timer_data& timer, op_queue<operation>& ops,
Chris@16:       std::size_t max_cancelled = (std::numeric_limits<std::size_t>::max)())
Chris@16:   {
Chris@16:     std::size_t num_cancelled = 0;
Chris@16:     if (timer.prev_ != 0 || &timer == timers_)
Chris@16:     {
Chris@16:       while (wait_op* op = (num_cancelled != max_cancelled)
Chris@16:           ? timer.op_queue_.front() : 0)
Chris@16:       {
Chris@16:         op->ec_ = boost::asio::error::operation_aborted;
Chris@16:         timer.op_queue_.pop();
Chris@16:         ops.push(op);
Chris@16:         ++num_cancelled;
Chris@16:       }
Chris@16:       if (timer.op_queue_.empty())
Chris@16:         remove_timer(timer);
Chris@16:     }
Chris@16:     return num_cancelled;
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@16:   // Move the item at the given index up the heap to its correct position.
Chris@16:   void up_heap(std::size_t index)
Chris@16:   {
Chris@101:     while (index > 0)
Chris@16:     {
Chris@101:       std::size_t parent = (index - 1) / 2;
Chris@101:       if (!Time_Traits::less_than(heap_[index].time_, heap_[parent].time_))
Chris@101:         break;
Chris@16:       swap_heap(index, parent);
Chris@16:       index = parent;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   // Move the item at the given index down the heap to its correct position.
Chris@16:   void down_heap(std::size_t index)
Chris@16:   {
Chris@16:     std::size_t child = index * 2 + 1;
Chris@16:     while (child < heap_.size())
Chris@16:     {
Chris@16:       std::size_t min_child = (child + 1 == heap_.size()
Chris@16:           || Time_Traits::less_than(
Chris@16:             heap_[child].time_, heap_[child + 1].time_))
Chris@16:         ? child : child + 1;
Chris@16:       if (Time_Traits::less_than(heap_[index].time_, heap_[min_child].time_))
Chris@16:         break;
Chris@16:       swap_heap(index, min_child);
Chris@16:       index = min_child;
Chris@16:       child = index * 2 + 1;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   // Swap two entries in the heap.
Chris@16:   void swap_heap(std::size_t index1, std::size_t index2)
Chris@16:   {
Chris@16:     heap_entry tmp = heap_[index1];
Chris@16:     heap_[index1] = heap_[index2];
Chris@16:     heap_[index2] = tmp;
Chris@16:     heap_[index1].timer_->heap_index_ = index1;
Chris@16:     heap_[index2].timer_->heap_index_ = index2;
Chris@16:   }
Chris@16: 
Chris@16:   // Remove a timer from the heap and list of timers.
Chris@16:   void remove_timer(per_timer_data& timer)
Chris@16:   {
Chris@16:     // Remove the timer from the heap.
Chris@16:     std::size_t index = timer.heap_index_;
Chris@16:     if (!heap_.empty() && index < heap_.size())
Chris@16:     {
Chris@16:       if (index == heap_.size() - 1)
Chris@16:       {
Chris@16:         heap_.pop_back();
Chris@16:       }
Chris@16:       else
Chris@16:       {
Chris@16:         swap_heap(index, heap_.size() - 1);
Chris@16:         heap_.pop_back();
Chris@16:         if (index > 0 && Time_Traits::less_than(
Chris@101:               heap_[index].time_, heap_[(index - 1) / 2].time_))
Chris@16:           up_heap(index);
Chris@16:         else
Chris@16:           down_heap(index);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     // Remove the timer from the linked list of active timers.
Chris@16:     if (timers_ == &timer)
Chris@16:       timers_ = timer.next_;
Chris@16:     if (timer.prev_)
Chris@16:       timer.prev_->next_ = timer.next_;
Chris@16:     if (timer.next_)
Chris@16:       timer.next_->prev_= timer.prev_;
Chris@16:     timer.next_ = 0;
Chris@16:     timer.prev_ = 0;
Chris@16:   }
Chris@16: 
Chris@16:   // Determine if the specified absolute time is positive infinity.
Chris@16:   template <typename Time_Type>
Chris@16:   static bool is_positive_infinity(const Time_Type&)
Chris@16:   {
Chris@16:     return false;
Chris@16:   }
Chris@16: 
Chris@16:   // Determine if the specified absolute time is positive infinity.
Chris@16:   template <typename T, typename TimeSystem>
Chris@16:   static bool is_positive_infinity(
Chris@16:       const boost::date_time::base_time<T, TimeSystem>& time)
Chris@16:   {
Chris@16:     return time.is_pos_infinity();
Chris@16:   }
Chris@16: 
Chris@16:   // Helper function to convert a duration into milliseconds.
Chris@16:   template <typename Duration>
Chris@16:   long to_msec(const Duration& d, long max_duration) const
Chris@16:   {
Chris@16:     if (d.ticks() <= 0)
Chris@16:       return 0;
Chris@16:     int64_t msec = d.total_milliseconds();
Chris@16:     if (msec == 0)
Chris@16:       return 1;
Chris@16:     if (msec > max_duration)
Chris@16:       return max_duration;
Chris@16:     return static_cast<long>(msec);
Chris@16:   }
Chris@16: 
Chris@16:   // Helper function to convert a duration into microseconds.
Chris@16:   template <typename Duration>
Chris@16:   long to_usec(const Duration& d, long max_duration) const
Chris@16:   {
Chris@16:     if (d.ticks() <= 0)
Chris@16:       return 0;
Chris@16:     int64_t usec = d.total_microseconds();
Chris@16:     if (usec == 0)
Chris@16:       return 1;
Chris@16:     if (usec > max_duration)
Chris@16:       return max_duration;
Chris@16:     return static_cast<long>(usec);
Chris@16:   }
Chris@16: 
Chris@16:   // The head of a linked list of all active timers.
Chris@16:   per_timer_data* timers_;
Chris@16: 
Chris@16:   struct heap_entry
Chris@16:   {
Chris@16:     // The time when the timer should fire.
Chris@16:     time_type time_;
Chris@16: 
Chris@16:     // The associated timer with enqueued operations.
Chris@16:     per_timer_data* timer_;
Chris@16:   };
Chris@16: 
Chris@16:   // The heap of timers, with the earliest timer at the front.
Chris@16:   std::vector<heap_entry> heap_;
Chris@16: };
Chris@16: 
Chris@16: } // namespace detail
Chris@16: } // namespace asio
Chris@16: } // namespace boost
Chris@16: 
Chris@16: #include <boost/asio/detail/pop_options.hpp>
Chris@16: 
Chris@16: #endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP