asio/include/asio/detail/timer_queue.hpp - third_party/asio - Git at Google

 //
 // detail/timer_queue.hpp
 // ~~~~~~~~~~~~~~~~~~~~~~
 //
 // Copyright (c) 2003-2015 Christopher M. Kohlhoff (chris at kohlhoff dot com)
 //
 // Distributed under the Boost Software License, Version 1.0. (See accompanying
 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 //

 #ifndef ASIO_DETAIL_TIMER_QUEUE_HPP
 #define ASIO_DETAIL_TIMER_QUEUE_HPP

 #if defined(_MSC_VER) && (_MSC_VER >= 1200)
 # pragma once
 #endif // defined(_MSC_VER) && (_MSC_VER >= 1200)

 #include "asio/detail/config.hpp"
 #include <cstddef>
 #include <vector>
 #include "asio/detail/cstdint.hpp"
 #include "asio/detail/date_time_fwd.hpp"
 #include "asio/detail/limits.hpp"
 #include "asio/detail/op_queue.hpp"
 #include "asio/detail/timer_queue_base.hpp"
 #include "asio/detail/wait_op.hpp"
 #include "asio/error.hpp"

 #include "asio/detail/push_options.hpp"

 namespace asio {
 namespace detail {

 template <typename Time_Traits>
 class timer_queue
   : public timer_queue_base
 {
 public:
   // The time type.
   typedef typename Time_Traits::time_type time_type;

   // The duration type.
   typedef typename Time_Traits::duration_type duration_type;

   // Per-timer data.
   class per_timer_data
   {
   public:
     per_timer_data() :
       heap_index_((std::numeric_limits<std::size_t>::max)()),
       next_(0), prev_(0)
     {
     }

   private:
     friend class timer_queue;

     // The operations waiting on the timer.
     op_queue<wait_op> op_queue_;

     // The index of the timer in the heap.
     std::size_t heap_index_;

     // Pointers to adjacent timers in a linked list.
     per_timer_data* next_;
     per_timer_data* prev_;
   };

   // Constructor.
   timer_queue()
     : timers_(),
       heap_()
   {
   }

   // Add a new timer to the queue. Returns true if this is the timer that is
   // earliest in the queue, in which case the reactor's event demultiplexing
   // function call may need to be interrupted and restarted.
   bool enqueue_timer(const time_type& time, per_timer_data& timer, wait_op* op)
   {
     // Enqueue the timer object.
     if (timer.prev_ == 0 && &timer != timers_)
     {
       if (this->is_positive_infinity(time))
       {
         // No heap entry is required for timers that never expire.
         timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
       }
       else
       {
         // Put the new timer at the correct position in the heap. This is done
         // first since push_back() can throw due to allocation failure.
         timer.heap_index_ = heap_.size();
         heap_entry entry = { time, &timer };
         heap_.push_back(entry);
         up_heap(heap_.size() - 1);
       }

       // Insert the new timer into the linked list of active timers.
       timer.next_ = timers_;
       timer.prev_ = 0;
       if (timers_)
         timers_->prev_ = &timer;
       timers_ = &timer;
     }

     // Enqueue the individual timer operation.
     timer.op_queue_.push(op);

     // Interrupt reactor only if newly added timer is first to expire.
     return timer.heap_index_ == 0 && timer.op_queue_.front() == op;
   }

   // Whether there are no timers in the queue.
   virtual bool empty() const
   {
     return timers_ == 0;
   }

   // Get the time for the timer that is earliest in the queue.
   virtual long wait_duration_msec(long max_duration) const
   {
     if (heap_.empty())
       return max_duration;

     return this->to_msec(
         Time_Traits::to_posix_duration(
           Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
         max_duration);
   }

   // Get the time for the timer that is earliest in the queue.
   virtual long wait_duration_usec(long max_duration) const
   {
     if (heap_.empty())
       return max_duration;

     return this->to_usec(
         Time_Traits::to_posix_duration(
           Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
         max_duration);
   }

   // Dequeue all timers not later than the current time.
   virtual void get_ready_timers(op_queue<operation>& ops)
   {
     if (!heap_.empty())
     {
       const time_type now = Time_Traits::now();
       while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0].time_))
       {
         per_timer_data* timer = heap_[0].timer_;
         ops.push(timer->op_queue_);
         remove_timer(*timer);
       }
     }
   }

   // Dequeue all timers.
   virtual void get_all_timers(op_queue<operation>& ops)
   {
     while (timers_)
     {
       per_timer_data* timer = timers_;
       timers_ = timers_->next_;
       ops.push(timer->op_queue_);
       timer->next_ = 0;
       timer->prev_ = 0;
     }

     heap_.clear();
   }

   // Cancel and dequeue operations for the given timer.
   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)())
   {
     std::size_t num_cancelled = 0;
     if (timer.prev_ != 0 || &timer == timers_)
     {
       while (wait_op* op = (num_cancelled != max_cancelled)
           ? timer.op_queue_.front() : 0)
       {
         op->ec_ = asio::error::operation_aborted;
         timer.op_queue_.pop();
         ops.push(op);
         ++num_cancelled;
       }
       if (timer.op_queue_.empty())
         remove_timer(timer);
     }
     return num_cancelled;
   }

   // Move operations from one timer to another, empty timer.
   void move_timer(per_timer_data& target, per_timer_data& source)
   {
     target.op_queue_.push(source.op_queue_);

     target.heap_index_ = source.heap_index_;
     source.heap_index_ = (std::numeric_limits<std::size_t>::max)();

     if (target.heap_index_ < heap_.size())
       heap_[target.heap_index_].timer_ = &target;

     if (timers_ == &source)
       timers_ = &target;
     if (source.prev_)
       source.prev_->next_ = &target;
     if (source.next_)
       source.next_->prev_= &target;
     target.next_ = source.next_;
     target.prev_ = source.prev_;
     source.next_ = 0;
     source.prev_ = 0;
   }

 private:
   // Move the item at the given index up the heap to its correct position.
   void up_heap(std::size_t index)
   {
     while (index > 0)
     {
       std::size_t parent = (index - 1) / 2;
       if (!Time_Traits::less_than(heap_[index].time_, heap_[parent].time_))
         break;
       swap_heap(index, parent);
       index = parent;
     }
   }

   // Move the item at the given index down the heap to its correct position.
   void down_heap(std::size_t index)
   {
     std::size_t child = index * 2 + 1;
     while (child < heap_.size())
     {
       std::size_t min_child = (child + 1 == heap_.size()
           || Time_Traits::less_than(
             heap_[child].time_, heap_[child + 1].time_))
         ? child : child + 1;
       if (Time_Traits::less_than(heap_[index].time_, heap_[min_child].time_))
         break;
       swap_heap(index, min_child);
       index = min_child;
       child = index * 2 + 1;
     }
   }

   // Swap two entries in the heap.
   void swap_heap(std::size_t index1, std::size_t index2)
   {
     heap_entry tmp = heap_[index1];
     heap_[index1] = heap_[index2];
     heap_[index2] = tmp;
     heap_[index1].timer_->heap_index_ = index1;
     heap_[index2].timer_->heap_index_ = index2;
   }

   // Remove a timer from the heap and list of timers.
   void remove_timer(per_timer_data& timer)
   {
     // Remove the timer from the heap.
     std::size_t index = timer.heap_index_;
     if (!heap_.empty() && index < heap_.size())
     {
       if (index == heap_.size() - 1)
       {
         heap_.pop_back();
       }
       else
       {
         swap_heap(index, heap_.size() - 1);
         heap_.pop_back();
         if (index > 0 && Time_Traits::less_than(
               heap_[index].time_, heap_[(index - 1) / 2].time_))
           up_heap(index);
         else
           down_heap(index);
       }
     }

     // Remove the timer from the linked list of active timers.
     if (timers_ == &timer)
       timers_ = timer.next_;
     if (timer.prev_)
       timer.prev_->next_ = timer.next_;
     if (timer.next_)
       timer.next_->prev_= timer.prev_;
     timer.next_ = 0;
     timer.prev_ = 0;
   }

   // Determine if the specified absolute time is positive infinity.
   template <typename Time_Type>
   static bool is_positive_infinity(const Time_Type&)
   {
     return false;
   }

   // Determine if the specified absolute time is positive infinity.
   template <typename T, typename TimeSystem>
   static bool is_positive_infinity(
       const boost::date_time::base_time<T, TimeSystem>& time)
   {
     return time.is_pos_infinity();
   }

   // Helper function to convert a duration into milliseconds.
   template <typename Duration>
   long to_msec(const Duration& d, long max_duration) const
   {
     if (d.ticks() <= 0)
       return 0;
     int64_t msec = d.total_milliseconds();
     if (msec == 0)
       return 1;
     if (msec > max_duration)
       return max_duration;
     return static_cast<long>(msec);
   }

   // Helper function to convert a duration into microseconds.
   template <typename Duration>
   long to_usec(const Duration& d, long max_duration) const
   {
     if (d.ticks() <= 0)
       return 0;
     int64_t usec = d.total_microseconds();
     if (usec == 0)
       return 1;
     if (usec > max_duration)
       return max_duration;
     return static_cast<long>(usec);
   }

   // The head of a linked list of all active timers.
   per_timer_data* timers_;

   struct heap_entry
   {
     // The time when the timer should fire.
     time_type time_;

     // The associated timer with enqueued operations.
     per_timer_data* timer_;
   };

   // The heap of timers, with the earliest timer at the front.
   std::vector<heap_entry> heap_;
 };

 } // namespace detail
 } // namespace asio

 #include "asio/detail/pop_options.hpp"

 #endif // ASIO_DETAIL_TIMER_QUEUE_HPP
	//
	// detail/timer_queue.hpp
	// ~~~~~~~~~~~~~~~~~~~~~~
	//
	// Copyright (c) 2003-2015 Christopher M. Kohlhoff (chris at kohlhoff dot com)
	//
	// Distributed under the Boost Software License, Version 1.0. (See accompanying
	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
	//

	#ifndef ASIO_DETAIL_TIMER_QUEUE_HPP
	#define ASIO_DETAIL_TIMER_QUEUE_HPP

	#if defined(_MSC_VER) && (_MSC_VER >= 1200)
	# pragma once
	#endif // defined(_MSC_VER) && (_MSC_VER >= 1200)

	#include "asio/detail/config.hpp"
	#include <cstddef>
	#include <vector>
	#include "asio/detail/cstdint.hpp"
	#include "asio/detail/date_time_fwd.hpp"
	#include "asio/detail/limits.hpp"
	#include "asio/detail/op_queue.hpp"
	#include "asio/detail/timer_queue_base.hpp"
	#include "asio/detail/wait_op.hpp"
	#include "asio/error.hpp"

	#include "asio/detail/push_options.hpp"

	namespace asio {
	namespace detail {

	template <typename Time_Traits>
	class timer_queue
	: public timer_queue_base
	{
	public:
	// The time type.
	typedef typename Time_Traits::time_type time_type;

	// The duration type.
	typedef typename Time_Traits::duration_type duration_type;

	// Per-timer data.
	class per_timer_data
	{
	public:
	per_timer_data() :
	heap_index_((std::numeric_limits<std::size_t>::max)()),
	next_(0), prev_(0)
	{
	}

	private:
	friend class timer_queue;

	// The operations waiting on the timer.
	op_queue<wait_op> op_queue_;

	// The index of the timer in the heap.
	std::size_t heap_index_;

	// Pointers to adjacent timers in a linked list.
	per_timer_data* next_;
	per_timer_data* prev_;
	};

	// Constructor.
	timer_queue()
	: timers_(),
	heap_()
	{
	}

	// Add a new timer to the queue. Returns true if this is the timer that is
	// earliest in the queue, in which case the reactor's event demultiplexing
	// function call may need to be interrupted and restarted.
	bool enqueue_timer(const time_type& time, per_timer_data& timer, wait_op* op)
	{
	// Enqueue the timer object.
	if (timer.prev_ == 0 && &timer != timers_)
	{
	if (this->is_positive_infinity(time))
	{
	// No heap entry is required for timers that never expire.
	timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
	}
	else
	{
	// Put the new timer at the correct position in the heap. This is done
	// first since push_back() can throw due to allocation failure.
	timer.heap_index_ = heap_.size();
	heap_entry entry = { time, &timer };
	heap_.push_back(entry);
	up_heap(heap_.size() - 1);
	}

	// Insert the new timer into the linked list of active timers.
	timer.next_ = timers_;
	timer.prev_ = 0;
	if (timers_)
	timers_->prev_ = &timer;
	timers_ = &timer;
	}

	// Enqueue the individual timer operation.
	timer.op_queue_.push(op);

	// Interrupt reactor only if newly added timer is first to expire.
	return timer.heap_index_ == 0 && timer.op_queue_.front() == op;
	}

	// Whether there are no timers in the queue.
	virtual bool empty() const
	{
	return timers_ == 0;
	}

	// Get the time for the timer that is earliest in the queue.
	virtual long wait_duration_msec(long max_duration) const
	{
	if (heap_.empty())
	return max_duration;

	return this->to_msec(
	Time_Traits::to_posix_duration(
	Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
	max_duration);
	}

	// Get the time for the timer that is earliest in the queue.
	virtual long wait_duration_usec(long max_duration) const
	{
	if (heap_.empty())
	return max_duration;

	return this->to_usec(
	Time_Traits::to_posix_duration(
	Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
	max_duration);
	}

	// Dequeue all timers not later than the current time.
	virtual void get_ready_timers(op_queue<operation>& ops)
	{
	if (!heap_.empty())
	{
	const time_type now = Time_Traits::now();
	while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0].time_))
	{
	per_timer_data* timer = heap_[0].timer_;
	ops.push(timer->op_queue_);
	remove_timer(*timer);
	}
	}
	}

	// Dequeue all timers.
	virtual void get_all_timers(op_queue<operation>& ops)
	{
	while (timers_)
	{
	per_timer_data* timer = timers_;
	timers_ = timers_->next_;
	ops.push(timer->op_queue_);
	timer->next_ = 0;
	timer->prev_ = 0;
	}

	heap_.clear();
	}

	// Cancel and dequeue operations for the given timer.
	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)())
	{
	std::size_t num_cancelled = 0;
	if (timer.prev_ != 0 \|\| &timer == timers_)
	{
	while (wait_op* op = (num_cancelled != max_cancelled)
	? timer.op_queue_.front() : 0)
	{
	op->ec_ = asio::error::operation_aborted;
	timer.op_queue_.pop();
	ops.push(op);
	++num_cancelled;
	}
	if (timer.op_queue_.empty())
	remove_timer(timer);
	}
	return num_cancelled;
	}

	// Move operations from one timer to another, empty timer.
	void move_timer(per_timer_data& target, per_timer_data& source)
	{
	target.op_queue_.push(source.op_queue_);

	target.heap_index_ = source.heap_index_;
	source.heap_index_ = (std::numeric_limits<std::size_t>::max)();

	if (target.heap_index_ < heap_.size())
	heap_[target.heap_index_].timer_ = &target;

	if (timers_ == &source)
	timers_ = &target;
	if (source.prev_)
	source.prev_->next_ = &target;
	if (source.next_)
	source.next_->prev_= &target;
	target.next_ = source.next_;
	target.prev_ = source.prev_;
	source.next_ = 0;
	source.prev_ = 0;
	}

	private:
	// Move the item at the given index up the heap to its correct position.
	void up_heap(std::size_t index)
	{
	while (index > 0)
	{
	std::size_t parent = (index - 1) / 2;
	if (!Time_Traits::less_than(heap_[index].time_, heap_[parent].time_))
	break;
	swap_heap(index, parent);
	index = parent;
	}
	}

	// Move the item at the given index down the heap to its correct position.
	void down_heap(std::size_t index)
	{
	std::size_t child = index * 2 + 1;
	while (child < heap_.size())
	{
	std::size_t min_child = (child + 1 == heap_.size()
	\|\| Time_Traits::less_than(
	heap_[child].time_, heap_[child + 1].time_))
	? child : child + 1;
	if (Time_Traits::less_than(heap_[index].time_, heap_[min_child].time_))
	break;
	swap_heap(index, min_child);
	index = min_child;
	child = index * 2 + 1;
	}
	}

	// Swap two entries in the heap.
	void swap_heap(std::size_t index1, std::size_t index2)
	{
	heap_entry tmp = heap_[index1];
	heap_[index1] = heap_[index2];
	heap_[index2] = tmp;
	heap_[index1].timer_->heap_index_ = index1;
	heap_[index2].timer_->heap_index_ = index2;
	}

	// Remove a timer from the heap and list of timers.
	void remove_timer(per_timer_data& timer)
	{
	// Remove the timer from the heap.
	std::size_t index = timer.heap_index_;
	if (!heap_.empty() && index < heap_.size())
	{
	if (index == heap_.size() - 1)
	{
	heap_.pop_back();
	}
	else
	{
	swap_heap(index, heap_.size() - 1);
	heap_.pop_back();
	if (index > 0 && Time_Traits::less_than(
	heap_[index].time_, heap_[(index - 1) / 2].time_))
	up_heap(index);
	else
	down_heap(index);
	}
	}

	// Remove the timer from the linked list of active timers.
	if (timers_ == &timer)
	timers_ = timer.next_;
	if (timer.prev_)
	timer.prev_->next_ = timer.next_;
	if (timer.next_)
	timer.next_->prev_= timer.prev_;
	timer.next_ = 0;
	timer.prev_ = 0;
	}

	// Determine if the specified absolute time is positive infinity.
	template <typename Time_Type>
	static bool is_positive_infinity(const Time_Type&)
	{
	return false;
	}

	// Determine if the specified absolute time is positive infinity.
	template <typename T, typename TimeSystem>
	static bool is_positive_infinity(
	const boost::date_time::base_time<T, TimeSystem>& time)
	{
	return time.is_pos_infinity();
	}

	// Helper function to convert a duration into milliseconds.
	template <typename Duration>
	long to_msec(const Duration& d, long max_duration) const
	{
	if (d.ticks() <= 0)
	return 0;
	int64_t msec = d.total_milliseconds();
	if (msec == 0)
	return 1;
	if (msec > max_duration)
	return max_duration;
	return static_cast<long>(msec);
	}

	// Helper function to convert a duration into microseconds.
	template <typename Duration>
	long to_usec(const Duration& d, long max_duration) const
	{
	if (d.ticks() <= 0)
	return 0;
	int64_t usec = d.total_microseconds();
	if (usec == 0)
	return 1;
	if (usec > max_duration)
	return max_duration;
	return static_cast<long>(usec);
	}

	// The head of a linked list of all active timers.
	per_timer_data* timers_;

	struct heap_entry
	{
	// The time when the timer should fire.
	time_type time_;

	// The associated timer with enqueued operations.
	per_timer_data* timer_;
	};

	// The heap of timers, with the earliest timer at the front.
	std::vector<heap_entry> heap_;
	};

	} // namespace detail
	} // namespace asio

	#include "asio/detail/pop_options.hpp"

	#endif // ASIO_DETAIL_TIMER_QUEUE_HPP