summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/asio/include/asio/detail/timer_queue.hpp
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/asio/include/asio/detail/timer_queue.hpp')
-rw-r--r--3rdparty/asio/include/asio/detail/timer_queue.hpp389
1 files changed, 389 insertions, 0 deletions
diff --git a/3rdparty/asio/include/asio/detail/timer_queue.hpp b/3rdparty/asio/include/asio/detail/timer_queue.hpp
new file mode 100644
index 00000000000..cb5f4fc3caa
--- /dev/null
+++ b/3rdparty/asio/include/asio/detail/timer_queue.hpp
@@ -0,0 +1,389 @@
+//
+// detail/timer_queue.hpp
+// ~~~~~~~~~~~~~~~~~~~~~~
+//
+// Copyright (c) 2003-2021 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_;
+ while (wait_op* op = timer->op_queue_.front())
+ {
+ timer->op_queue_.pop();
+ op->ec_ = asio::error_code();
+ ops.push(op);
+ }
+ 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;
+ }
+
+ // Cancel and dequeue a specific operation for the given timer.
+ void cancel_timer_by_key(per_timer_data* timer,
+ op_queue<operation>& ops, void* cancellation_key)
+ {
+ if (timer->prev_ != 0 || timer == timers_)
+ {
+ op_queue<wait_op> other_ops;
+ while (wait_op* op = timer->op_queue_.front())
+ {
+ timer->op_queue_.pop();
+ if (op->cancellation_key_ == cancellation_key)
+ {
+ op->ec_ = asio::error::operation_aborted;
+ ops.push(op);
+ }
+ else
+ other_ops.push(op);
+ }
+ timer->op_queue_.push(other_ops);
+ if (timer->op_queue_.empty())
+ remove_timer(*timer);
+ }
+ }
+
+ // 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)
+ {
+ timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
+ heap_.pop_back();
+ }
+ else
+ {
+ swap_heap(index, heap_.size() - 1);
+ timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
+ 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