Imported Upstream version 1.49.0upstream/1.49.0

1 files changed, 335 insertions, 0 deletions

diff --git a/boost/asio/detail/timer_queue.hpp b/boost/asio/detail/timer_queue.hpp
new file mode 100644
index 0000000000..d14ba7caec
--- /dev/null
+++ b/boost/asio/detail/timer_queue.hpp
@@ -0,0 +1,335 @@
+//
+// detail/timer_queue.hpp
+// ~~~~~~~~~~~~~~~~~~~~~~
+//
+// Copyright (c) 2003-2012 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/cstdint.hpp>
+#include <boost/asio/detail/date_time_fwd.hpp>
+#include <boost/asio/detail/op_queue.hpp>
+#include <boost/asio/detail/timer_queue_base.hpp>
+#include <boost/asio/detail/wait_op.hpp>
+#include <boost/asio/error.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<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_ = boost::asio::error::operation_aborted;
+        timer.op_queue_.pop();
+        ops.push(op);
+        ++num_cancelled;
+      }
+      if (timer.op_queue_.empty())
+        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.
+  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;
+    boost::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;
+    boost::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
+} // namespace boost
+
+#include <boost/asio/detail/pop_options.hpp>
+
+#endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP