Swift
summaryrefslogtreecommitdiffstats
path: root/3rdParty/Boost/boost/asio/detail/timer_queue.hpp
diff options
context:
space:
mode:
authorRemko Tronçon <git@el-tramo.be>2009-06-01 08:48:42 (GMT)
committerRemko Tronçon <git@el-tramo.be>2009-06-01 09:24:28 (GMT)
commit2812bddd81f8a1b804c7460f4e14cd0aa393d129 (patch)
treed46294f35150c4f0f43deaf2d31fceaf945ae715 /3rdParty/Boost/boost/asio/detail/timer_queue.hpp
downloadswift-contrib-2812bddd81f8a1b804c7460f4e14cd0aa393d129.zip
swift-contrib-2812bddd81f8a1b804c7460f4e14cd0aa393d129.tar.bz2
Import.
Diffstat (limited to '3rdParty/Boost/boost/asio/detail/timer_queue.hpp')
-rw-r--r--3rdParty/Boost/boost/asio/detail/timer_queue.hpp438
1 files changed, 438 insertions, 0 deletions
diff --git a/3rdParty/Boost/boost/asio/detail/timer_queue.hpp b/3rdParty/Boost/boost/asio/detail/timer_queue.hpp
new file mode 100644
index 0000000..f5370e5
--- /dev/null
+++ b/3rdParty/Boost/boost/asio/detail/timer_queue.hpp
@@ -0,0 +1,438 @@
+//
+// 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.
+ std::auto_ptr<timer<Handler> > new_timer(
+ new timer<Handler>(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->next_ = result.first->second;
+ result.first->second = new_timer.get();
+ }
+
+ // Put the timer at the correct position in the heap.
+ new_timer->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