Statistics
| Revision:

root / tmp / org.txm.statsengine.r.core.win32 / res / win32 / library / BH / include / boost / asio / detail / timer_queue.hpp @ 2486

History | View | Annotate | Download (8.8 kB)

1
//
2
// detail/timer_queue.hpp
3
// ~~~~~~~~~~~~~~~~~~~~~~
4
//
5
// Copyright (c) 2003-2015 Christopher M. Kohlhoff (chris at kohlhoff dot com)
6
//
7
// Distributed under the Boost Software License, Version 1.0. (See accompanying
8
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
9
//
10

    
11
#ifndef BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP
12
#define BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP
13

    
14
#if defined(_MSC_VER) && (_MSC_VER >= 1200)
15
# pragma once
16
#endif // defined(_MSC_VER) && (_MSC_VER >= 1200)
17

    
18
#include <boost/asio/detail/config.hpp>
19
#include <cstddef>
20
#include <vector>
21
#include <boost/asio/detail/cstdint.hpp>
22
#include <boost/asio/detail/date_time_fwd.hpp>
23
#include <boost/asio/detail/limits.hpp>
24
#include <boost/asio/detail/op_queue.hpp>
25
#include <boost/asio/detail/timer_queue_base.hpp>
26
#include <boost/asio/detail/wait_op.hpp>
27
#include <boost/asio/error.hpp>
28

    
29
#include <boost/asio/detail/push_options.hpp>
30

    
31
namespace boost {
32
namespace asio {
33
namespace detail {
34

    
35
template <typename Time_Traits>
36
class timer_queue
37
  : public timer_queue_base
38
{
39
public:
40
  // The time type.
41
  typedef typename Time_Traits::time_type time_type;
42

    
43
  // The duration type.
44
  typedef typename Time_Traits::duration_type duration_type;
45

    
46
  // Per-timer data.
47
  class per_timer_data
48
  {
49
  public:
50
    per_timer_data() : next_(0), prev_(0) {}
51

    
52
  private:
53
    friend class timer_queue;
54

    
55
    // The operations waiting on the timer.
56
    op_queue<wait_op> op_queue_;
57

    
58
    // The index of the timer in the heap.
59
    std::size_t heap_index_;
60

    
61
    // Pointers to adjacent timers in a linked list.
62
    per_timer_data* next_;
63
    per_timer_data* prev_;
64
  };
65

    
66
  // Constructor.
67
  timer_queue()
68
    : timers_(),
69
      heap_()
70
  {
71
  }
72

    
73
  // Add a new timer to the queue. Returns true if this is the timer that is
74
  // earliest in the queue, in which case the reactor's event demultiplexing
75
  // function call may need to be interrupted and restarted.
76
  bool enqueue_timer(const time_type& time, per_timer_data& timer, wait_op* op)
77
  {
78
    // Enqueue the timer object.
79
    if (timer.prev_ == 0 && &timer != timers_)
80
    {
81
      if (this->is_positive_infinity(time))
82
      {
83
        // No heap entry is required for timers that never expire.
84
        timer.heap_index_ = (std::numeric_limits<std::size_t>::max)();
85
      }
86
      else
87
      {
88
        // Put the new timer at the correct position in the heap. This is done
89
        // first since push_back() can throw due to allocation failure.
90
        timer.heap_index_ = heap_.size();
91
        heap_entry entry = { time, &timer };
92
        heap_.push_back(entry);
93
        up_heap(heap_.size() - 1);
94
      }
95

    
96
      // Insert the new timer into the linked list of active timers.
97
      timer.next_ = timers_;
98
      timer.prev_ = 0;
99
      if (timers_)
100
        timers_->prev_ = &timer;
101
      timers_ = &timer;
102
    }
103

    
104
    // Enqueue the individual timer operation.
105
    timer.op_queue_.push(op);
106

    
107
    // Interrupt reactor only if newly added timer is first to expire.
108
    return timer.heap_index_ == 0 && timer.op_queue_.front() == op;
109
  }
110

    
111
  // Whether there are no timers in the queue.
112
  virtual bool empty() const
113
  {
114
    return timers_ == 0;
115
  }
116

    
117
  // Get the time for the timer that is earliest in the queue.
118
  virtual long wait_duration_msec(long max_duration) const
119
  {
120
    if (heap_.empty())
121
      return max_duration;
122

    
123
    return this->to_msec(
124
        Time_Traits::to_posix_duration(
125
          Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
126
        max_duration);
127
  }
128

    
129
  // Get the time for the timer that is earliest in the queue.
130
  virtual long wait_duration_usec(long max_duration) const
131
  {
132
    if (heap_.empty())
133
      return max_duration;
134

    
135
    return this->to_usec(
136
        Time_Traits::to_posix_duration(
137
          Time_Traits::subtract(heap_[0].time_, Time_Traits::now())),
138
        max_duration);
139
  }
140

    
141
  // Dequeue all timers not later than the current time.
142
  virtual void get_ready_timers(op_queue<operation>& ops)
143
  {
144
    if (!heap_.empty())
145
    {
146
      const time_type now = Time_Traits::now();
147
      while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0].time_))
148
      {
149
        per_timer_data* timer = heap_[0].timer_;
150
        ops.push(timer->op_queue_);
151
        remove_timer(*timer);
152
      }
153
    }
154
  }
155

    
156
  // Dequeue all timers.
157
  virtual void get_all_timers(op_queue<operation>& ops)
158
  {
159
    while (timers_)
160
    {
161
      per_timer_data* timer = timers_;
162
      timers_ = timers_->next_;
163
      ops.push(timer->op_queue_);
164
      timer->next_ = 0;
165
      timer->prev_ = 0;
166
    }
167

    
168
    heap_.clear();
169
  }
170

    
171
  // Cancel and dequeue operations for the given timer.
172
  std::size_t cancel_timer(per_timer_data& timer, op_queue<operation>& ops,
173
      std::size_t max_cancelled = (std::numeric_limits<std::size_t>::max)())
174
  {
175
    std::size_t num_cancelled = 0;
176
    if (timer.prev_ != 0 || &timer == timers_)
177
    {
178
      while (wait_op* op = (num_cancelled != max_cancelled)
179
          ? timer.op_queue_.front() : 0)
180
      {
181
        op->ec_ = boost::asio::error::operation_aborted;
182
        timer.op_queue_.pop();
183
        ops.push(op);
184
        ++num_cancelled;
185
      }
186
      if (timer.op_queue_.empty())
187
        remove_timer(timer);
188
    }
189
    return num_cancelled;
190
  }
191

    
192
private:
193
  // Move the item at the given index up the heap to its correct position.
194
  void up_heap(std::size_t index)
195
  {
196
    while (index > 0)
197
    {
198
      std::size_t parent = (index - 1) / 2;
199
      if (!Time_Traits::less_than(heap_[index].time_, heap_[parent].time_))
200
        break;
201
      swap_heap(index, parent);
202
      index = parent;
203
    }
204
  }
205

    
206
  // Move the item at the given index down the heap to its correct position.
207
  void down_heap(std::size_t index)
208
  {
209
    std::size_t child = index * 2 + 1;
210
    while (child < heap_.size())
211
    {
212
      std::size_t min_child = (child + 1 == heap_.size()
213
          || Time_Traits::less_than(
214
            heap_[child].time_, heap_[child + 1].time_))
215
        ? child : child + 1;
216
      if (Time_Traits::less_than(heap_[index].time_, heap_[min_child].time_))
217
        break;
218
      swap_heap(index, min_child);
219
      index = min_child;
220
      child = index * 2 + 1;
221
    }
222
  }
223

    
224
  // Swap two entries in the heap.
225
  void swap_heap(std::size_t index1, std::size_t index2)
226
  {
227
    heap_entry tmp = heap_[index1];
228
    heap_[index1] = heap_[index2];
229
    heap_[index2] = tmp;
230
    heap_[index1].timer_->heap_index_ = index1;
231
    heap_[index2].timer_->heap_index_ = index2;
232
  }
233

    
234
  // Remove a timer from the heap and list of timers.
235
  void remove_timer(per_timer_data& timer)
236
  {
237
    // Remove the timer from the heap.
238
    std::size_t index = timer.heap_index_;
239
    if (!heap_.empty() && index < heap_.size())
240
    {
241
      if (index == heap_.size() - 1)
242
      {
243
        heap_.pop_back();
244
      }
245
      else
246
      {
247
        swap_heap(index, heap_.size() - 1);
248
        heap_.pop_back();
249
        if (index > 0 && Time_Traits::less_than(
250
              heap_[index].time_, heap_[(index - 1) / 2].time_))
251
          up_heap(index);
252
        else
253
          down_heap(index);
254
      }
255
    }
256

    
257
    // Remove the timer from the linked list of active timers.
258
    if (timers_ == &timer)
259
      timers_ = timer.next_;
260
    if (timer.prev_)
261
      timer.prev_->next_ = timer.next_;
262
    if (timer.next_)
263
      timer.next_->prev_= timer.prev_;
264
    timer.next_ = 0;
265
    timer.prev_ = 0;
266
  }
267

    
268
  // Determine if the specified absolute time is positive infinity.
269
  template <typename Time_Type>
270
  static bool is_positive_infinity(const Time_Type&)
271
  {
272
    return false;
273
  }
274

    
275
  // Determine if the specified absolute time is positive infinity.
276
  template <typename T, typename TimeSystem>
277
  static bool is_positive_infinity(
278
      const boost::date_time::base_time<T, TimeSystem>& time)
279
  {
280
    return time.is_pos_infinity();
281
  }
282

    
283
  // Helper function to convert a duration into milliseconds.
284
  template <typename Duration>
285
  long to_msec(const Duration& d, long max_duration) const
286
  {
287
    if (d.ticks() <= 0)
288
      return 0;
289
    int64_t msec = d.total_milliseconds();
290
    if (msec == 0)
291
      return 1;
292
    if (msec > max_duration)
293
      return max_duration;
294
    return static_cast<long>(msec);
295
  }
296

    
297
  // Helper function to convert a duration into microseconds.
298
  template <typename Duration>
299
  long to_usec(const Duration& d, long max_duration) const
300
  {
301
    if (d.ticks() <= 0)
302
      return 0;
303
    int64_t usec = d.total_microseconds();
304
    if (usec == 0)
305
      return 1;
306
    if (usec > max_duration)
307
      return max_duration;
308
    return static_cast<long>(usec);
309
  }
310

    
311
  // The head of a linked list of all active timers.
312
  per_timer_data* timers_;
313

    
314
  struct heap_entry
315
  {
316
    // The time when the timer should fire.
317
    time_type time_;
318

    
319
    // The associated timer with enqueued operations.
320
    per_timer_data* timer_;
321
  };
322

    
323
  // The heap of timers, with the earliest timer at the front.
324
  std::vector<heap_entry> heap_;
325
};
326

    
327
} // namespace detail
328
} // namespace asio
329
} // namespace boost
330

    
331
#include <boost/asio/detail/pop_options.hpp>
332

    
333
#endif // BOOST_ASIO_DETAIL_TIMER_QUEUE_HPP