// | |
// detail/timer_queue.hpp | |
// ~~~~~~~~~~~~~~~~~~~~~~ | |
// | |
// Copyright (c) 2003-2011 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 BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP | |
#define BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP | |
#if defined(_MSC_VER) && (_MSC_VER >= 1200) | |
# pragma once | |
#endif // defined(_MSC_VER) && (_MSC_VER >= 1200) | |
#include <boost/asio/detail/config.hpp> | |
#include <cstddef> | |
#include <vector> | |
#include <boost/config.hpp> | |
#include <boost/limits.hpp> | |
#include <boost/asio/detail/op_queue.hpp> | |
#include <boost/asio/detail/timer_op.hpp> | |
#include <boost/asio/detail/timer_queue_base.hpp> | |
#include <boost/asio/error.hpp> | |
#include <boost/asio/time_traits.hpp> | |
#include <boost/asio/detail/push_options.hpp> | |
#include <boost/date_time/posix_time/posix_time_types.hpp> | |
#include <boost/asio/detail/pop_options.hpp> | |
#include <boost/asio/detail/push_options.hpp> | |
namespace boost { | |
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() : next_(0), prev_(0) {} | |
private: | |
friend class timer_queue; | |
// The operations waiting on the timer. | |
op_queue<timer_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, timer_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; | |
boost::posix_time::time_duration duration = Time_Traits::to_posix_duration( | |
Time_Traits::subtract(heap_[0].time_, Time_Traits::now())); | |
if (duration > boost::posix_time::milliseconds(max_duration)) | |
duration = boost::posix_time::milliseconds(max_duration); | |
else if (duration <= boost::posix_time::milliseconds(0)) | |
duration = boost::posix_time::milliseconds(0); | |
else if (duration < boost::posix_time::milliseconds(1)) | |
duration = boost::posix_time::milliseconds(1); | |
return duration.total_milliseconds(); | |
} | |
// 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; | |
boost::posix_time::time_duration duration = Time_Traits::to_posix_duration( | |
Time_Traits::subtract(heap_[0].time_, Time_Traits::now())); | |
if (duration > boost::posix_time::microseconds(max_duration)) | |
duration = boost::posix_time::microseconds(max_duration); | |
else if (duration <= boost::posix_time::microseconds(0)) | |
duration = boost::posix_time::microseconds(0); | |
else if (duration < boost::posix_time::microseconds(1)) | |
duration = boost::posix_time::microseconds(1); | |
return duration.total_microseconds(); | |
} | |
// Dequeue all timers not later than the current time. | |
virtual void get_ready_timers(op_queue<operation>& ops) | |
{ | |
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 the timers with the given token. | |
std::size_t cancel_timer(per_timer_data& timer, op_queue<operation>& ops) | |
{ | |
std::size_t num_cancelled = 0; | |
if (timer.prev_ != 0 || &timer == timers_) | |
{ | |
while (timer_op* op = timer.op_queue_.front()) | |
{ | |
op->ec_ = boost::asio::error::operation_aborted; | |
timer.op_queue_.pop(); | |
ops.push(op); | |
++num_cancelled; | |
} | |
remove_timer(timer); | |
} | |
return num_cancelled; | |
} | |
private: | |
// Move the item at the given index up the heap to its correct position. | |
void up_heap(std::size_t index) | |
{ | |
std::size_t parent = (index - 1) / 2; | |
while (index > 0 | |
&& Time_Traits::less_than(heap_[index].time_, heap_[parent].time_)) | |
{ | |
swap_heap(index, parent); | |
index = parent; | |
parent = (index - 1) / 2; | |
} | |
} | |
// 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(); | |
std::size_t parent = (index - 1) / 2; | |
if (index > 0 && Time_Traits::less_than( | |
heap_[index].time_, heap_[parent].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. | |
static bool is_positive_infinity(const boost::posix_time::ptime& time) | |
{ | |
return time == boost::posix_time::pos_infin; | |
} | |
// 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_; | |
}; | |
#if !defined(BOOST_ASIO_HEADER_ONLY) | |
struct forwarding_posix_time_traits : time_traits<boost::posix_time::ptime> {}; | |
// Template specialisation for the commonly used instantation. | |
template <> | |
class timer_queue<time_traits<boost::posix_time::ptime> > | |
: public timer_queue_base | |
{ | |
public: | |
// The time type. | |
typedef boost::posix_time::ptime time_type; | |
// The duration type. | |
typedef boost::posix_time::time_duration duration_type; | |
// Per-timer data. | |
typedef timer_queue<forwarding_posix_time_traits>::per_timer_data | |
per_timer_data; | |
// Constructor. | |
BOOST_ASIO_DECL timer_queue(); | |
// Destructor. | |
BOOST_ASIO_DECL virtual ~timer_queue(); | |
// 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. | |
BOOST_ASIO_DECL bool enqueue_timer(const time_type& time, | |
per_timer_data& timer, timer_op* op); | |
// Whether there are no timers in the queue. | |
BOOST_ASIO_DECL virtual bool empty() const; | |
// Get the time for the timer that is earliest in the queue. | |
BOOST_ASIO_DECL virtual long wait_duration_msec(long max_duration) const; | |
// Get the time for the timer that is earliest in the queue. | |
BOOST_ASIO_DECL virtual long wait_duration_usec(long max_duration) const; | |
// Dequeue all timers not later than the current time. | |
BOOST_ASIO_DECL virtual void get_ready_timers(op_queue<operation>& ops); | |
// Dequeue all timers. | |
BOOST_ASIO_DECL virtual void get_all_timers(op_queue<operation>& ops); | |
// Cancel and dequeue the timers with the given token. | |
BOOST_ASIO_DECL std::size_t cancel_timer( | |
per_timer_data& timer, op_queue<operation>& ops); | |
private: | |
timer_queue<forwarding_posix_time_traits> impl_; | |
}; | |
#endif // !defined(BOOST_ASIO_HEADER_ONLY) | |
} // namespace detail | |
} // namespace asio | |
} // namespace boost | |
#include <boost/asio/detail/pop_options.hpp> | |
#endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP |