| // |
| // timer_queue.hpp |
| // ~~~~~~~~~~~~~~~ |
| // |
| // Copyright (c) 2003-2008 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/push_options.hpp> |
| |
| #include <boost/asio/detail/push_options.hpp> |
| #include <cstddef> |
| #include <functional> |
| #include <limits> |
| #include <memory> |
| #include <vector> |
| #include <boost/config.hpp> |
| #include <boost/asio/detail/pop_options.hpp> |
| |
| #include <boost/asio/error.hpp> |
| #include <boost/asio/detail/handler_alloc_helpers.hpp> |
| #include <boost/asio/detail/hash_map.hpp> |
| #include <boost/asio/detail/noncopyable.hpp> |
| #include <boost/asio/detail/timer_queue_base.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; |
| |
| // Constructor. |
| timer_queue() |
| : timers_(), |
| heap_(), |
| cancelled_timers_(0), |
| complete_timers_(0) |
| { |
| } |
| |
| // 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. |
| template <typename Handler> |
| bool enqueue_timer(const time_type& time, Handler handler, void* token) |
| { |
| // Ensure that there is space for the timer in the heap. We reserve here so |
| // that the push_back below will not throw due to a reallocation failure. |
| heap_.reserve(heap_.size() + 1); |
| |
| // Create a new timer object. |
| typedef timer<Handler> timer_type; |
| typedef handler_alloc_traits<Handler, timer_type> alloc_traits; |
| raw_handler_ptr<alloc_traits> raw_ptr(handler); |
| handler_ptr<alloc_traits> new_timer(raw_ptr, time, handler, token); |
| |
| // Insert the new timer into the hash. |
| typedef typename hash_map<void*, timer_base*>::iterator iterator; |
| typedef typename hash_map<void*, timer_base*>::value_type value_type; |
| std::pair<iterator, bool> result = |
| timers_.insert(value_type(token, new_timer.get())); |
| if (!result.second) |
| { |
| result.first->second->prev_ = new_timer.get(); |
| new_timer.get()->next_ = result.first->second; |
| result.first->second = new_timer.get(); |
| } |
| |
| // Put the timer at the correct position in the heap. |
| new_timer.get()->heap_index_ = heap_.size(); |
| heap_.push_back(new_timer.get()); |
| up_heap(heap_.size() - 1); |
| bool is_first = (heap_[0] == new_timer.get()); |
| |
| // Ownership of the timer is transferred to the timer queue. |
| new_timer.release(); |
| |
| return is_first; |
| } |
| |
| // Whether there are no timers in the queue. |
| virtual bool empty() const |
| { |
| return heap_.empty(); |
| } |
| |
| // Get the time for the timer that is earliest in the queue. |
| virtual boost::posix_time::time_duration wait_duration() const |
| { |
| if (heap_.empty()) |
| return boost::posix_time::pos_infin; |
| return Time_Traits::to_posix_duration( |
| Time_Traits::subtract(heap_[0]->time_, Time_Traits::now())); |
| } |
| |
| // Dispatch the timers that are earlier than the specified time. |
| virtual void dispatch_timers() |
| { |
| const time_type now = Time_Traits::now(); |
| while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0]->time_)) |
| { |
| timer_base* t = heap_[0]; |
| remove_timer(t); |
| t->result_ = boost::system::error_code(); |
| t->prev_ = 0; |
| t->next_ = complete_timers_; |
| complete_timers_ = t; |
| } |
| } |
| |
| // Cancel the timers with the given token. Any timers pending for the token |
| // will be notified that they have been cancelled next time |
| // dispatch_cancellations is called. Returns the number of timers that were |
| // cancelled. |
| std::size_t cancel_timer(void* timer_token) |
| { |
| std::size_t num_cancelled = 0; |
| typedef typename hash_map<void*, timer_base*>::iterator iterator; |
| iterator it = timers_.find(timer_token); |
| if (it != timers_.end()) |
| { |
| timer_base* t = it->second; |
| while (t) |
| { |
| timer_base* next = t->next_; |
| remove_timer(t); |
| t->prev_ = 0; |
| t->next_ = cancelled_timers_; |
| cancelled_timers_ = t; |
| t = next; |
| ++num_cancelled; |
| } |
| } |
| return num_cancelled; |
| } |
| |
| // Dispatch any pending cancels for timers. |
| virtual void dispatch_cancellations() |
| { |
| while (cancelled_timers_) |
| { |
| timer_base* this_timer = cancelled_timers_; |
| this_timer->result_ = boost::asio::error::operation_aborted; |
| cancelled_timers_ = this_timer->next_; |
| this_timer->next_ = complete_timers_; |
| complete_timers_ = this_timer; |
| } |
| } |
| |
| // Complete any timers that are waiting to be completed. |
| virtual void complete_timers() |
| { |
| while (complete_timers_) |
| { |
| timer_base* this_timer = complete_timers_; |
| complete_timers_ = this_timer->next_; |
| this_timer->next_ = 0; |
| this_timer->complete(); |
| } |
| } |
| |
| // Destroy all timers. |
| virtual void destroy_timers() |
| { |
| typename hash_map<void*, timer_base*>::iterator i = timers_.begin(); |
| typename hash_map<void*, timer_base*>::iterator end = timers_.end(); |
| while (i != end) |
| { |
| timer_base* t = i->second; |
| typename hash_map<void*, timer_base*>::iterator old_i = i++; |
| timers_.erase(old_i); |
| destroy_timer_list(t); |
| } |
| heap_.clear(); |
| timers_.clear(); |
| destroy_timer_list(cancelled_timers_); |
| destroy_timer_list(complete_timers_); |
| } |
| |
| private: |
| // Base class for timer operations. Function pointers are used instead of |
| // virtual functions to avoid the associated overhead. |
| class timer_base |
| { |
| public: |
| // Delete the timer and post the handler. |
| void complete() |
| { |
| complete_func_(this, result_); |
| } |
| |
| // Delete the timer. |
| void destroy() |
| { |
| destroy_func_(this); |
| } |
| |
| protected: |
| typedef void (*complete_func_type)(timer_base*, |
| const boost::system::error_code&); |
| typedef void (*destroy_func_type)(timer_base*); |
| |
| // Constructor. |
| timer_base(complete_func_type complete_func, destroy_func_type destroy_func, |
| const time_type& time, void* token) |
| : complete_func_(complete_func), |
| destroy_func_(destroy_func), |
| time_(time), |
| token_(token), |
| next_(0), |
| prev_(0), |
| heap_index_( |
| std::numeric_limits<size_t>::max BOOST_PREVENT_MACRO_SUBSTITUTION()) |
| { |
| } |
| |
| // Prevent deletion through this type. |
| ~timer_base() |
| { |
| } |
| |
| private: |
| friend class timer_queue<Time_Traits>; |
| |
| // The function to be called to delete the timer and post the handler. |
| complete_func_type complete_func_; |
| |
| // The function to be called to delete the timer. |
| destroy_func_type destroy_func_; |
| |
| // The result of the timer operation. |
| boost::system::error_code result_; |
| |
| // The time when the timer should fire. |
| time_type time_; |
| |
| // The token associated with the timer. |
| void* token_; |
| |
| // The next timer known to the queue. |
| timer_base* next_; |
| |
| // The previous timer known to the queue. |
| timer_base* prev_; |
| |
| // The index of the timer in the heap. |
| size_t heap_index_; |
| }; |
| |
| // Adaptor class template for using handlers in timers. |
| template <typename Handler> |
| class timer |
| : public timer_base |
| { |
| public: |
| // Constructor. |
| timer(const time_type& time, Handler handler, void* token) |
| : timer_base(&timer<Handler>::complete_handler, |
| &timer<Handler>::destroy_handler, time, token), |
| handler_(handler) |
| { |
| } |
| |
| // Delete the timer and post the handler. |
| static void complete_handler(timer_base* base, |
| const boost::system::error_code& result) |
| { |
| // Take ownership of the timer object. |
| typedef timer<Handler> this_type; |
| this_type* this_timer(static_cast<this_type*>(base)); |
| typedef handler_alloc_traits<Handler, this_type> alloc_traits; |
| handler_ptr<alloc_traits> ptr(this_timer->handler_, this_timer); |
| |
| // Make a copy of the error_code and the handler so that the memory can |
| // be deallocated before the upcall is made. |
| boost::system::error_code ec(result); |
| Handler handler(this_timer->handler_); |
| |
| // Free the memory associated with the handler. |
| ptr.reset(); |
| |
| // Make the upcall. |
| handler(ec); |
| } |
| |
| // Delete the timer. |
| static void destroy_handler(timer_base* base) |
| { |
| // Take ownership of the timer object. |
| typedef timer<Handler> this_type; |
| this_type* this_timer(static_cast<this_type*>(base)); |
| typedef handler_alloc_traits<Handler, this_type> alloc_traits; |
| handler_ptr<alloc_traits> ptr(this_timer->handler_, this_timer); |
| |
| // A sub-object of the handler may be the true owner of the memory |
| // associated with the handler. Consequently, a local copy of the handler |
| // is required to ensure that any owning sub-object remains valid until |
| // after we have deallocated the memory here. |
| Handler handler(this_timer->handler_); |
| (void)handler; |
| |
| // Free the memory associated with the handler. |
| ptr.reset(); |
| } |
| |
| private: |
| Handler handler_; |
| }; |
| |
| // Move the item at the given index up the heap to its correct position. |
| void up_heap(size_t index) |
| { |
| 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(size_t index) |
| { |
| size_t child = index * 2 + 1; |
| while (child < heap_.size()) |
| { |
| 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(size_t index1, size_t index2) |
| { |
| timer_base* tmp = heap_[index1]; |
| heap_[index1] = heap_[index2]; |
| heap_[index2] = tmp; |
| heap_[index1]->heap_index_ = index1; |
| heap_[index2]->heap_index_ = index2; |
| } |
| |
| // Remove a timer from the heap and list of timers. |
| void remove_timer(timer_base* t) |
| { |
| // Remove the timer from the heap. |
| size_t index = t->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(); |
| 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 hash. |
| typedef typename hash_map<void*, timer_base*>::iterator iterator; |
| iterator it = timers_.find(t->token_); |
| if (it != timers_.end()) |
| { |
| if (it->second == t) |
| it->second = t->next_; |
| if (t->prev_) |
| t->prev_->next_ = t->next_; |
| if (t->next_) |
| t->next_->prev_ = t->prev_; |
| if (it->second == 0) |
| timers_.erase(it); |
| } |
| } |
| |
| // Destroy all timers in a linked list. |
| void destroy_timer_list(timer_base*& t) |
| { |
| while (t) |
| { |
| timer_base* next = t->next_; |
| t->next_ = 0; |
| t->destroy(); |
| t = next; |
| } |
| } |
| |
| // A hash of timer token to linked lists of timers. |
| hash_map<void*, timer_base*> timers_; |
| |
| // The heap of timers, with the earliest timer at the front. |
| std::vector<timer_base*> heap_; |
| |
| // The list of timers to be cancelled. |
| timer_base* cancelled_timers_; |
| |
| // The list of timers waiting to be completed. |
| timer_base* complete_timers_; |
| }; |
| |
| } // namespace detail |
| } // namespace asio |
| } // namespace boost |
| |
| #include <boost/asio/detail/pop_options.hpp> |
| |
| #endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP |