timer_queue.hpp
Go to the documentation of this file.
00001 //
00002 // timer_queue.hpp
00003 // ~~~~~~~~~~~~~~~
00004 //
00005 // Copyright (c) 2003-2008 Christopher M. Kohlhoff (chris at kohlhoff dot com)
00006 //
00007 // Distributed under the Boost Software License, Version 1.0. (See accompanying
00008 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
00009 //
00010 
00011 #ifndef ASIO_DETAIL_TIMER_QUEUE_HPP
00012 #define ASIO_DETAIL_TIMER_QUEUE_HPP
00013 
00014 #if defined(_MSC_VER) && (_MSC_VER >= 1200)
00015 # pragma once
00016 #endif // defined(_MSC_VER) && (_MSC_VER >= 1200)
00017 
00018 #include "asio/detail/push_options.hpp"
00019 
00020 #include "asio/detail/push_options.hpp"
00021 #include <cstddef>
00022 #include <functional>
00023 #include <limits>
00024 #include <memory>
00025 #include <vector>
00026 #include <boost/config.hpp>
00027 #include "asio/detail/pop_options.hpp"
00028 
00029 #include "asio/error.hpp"
00030 #include "asio/detail/handler_alloc_helpers.hpp"
00031 #include "asio/detail/hash_map.hpp"
00032 #include "asio/detail/noncopyable.hpp"
00033 #include "asio/detail/timer_queue_base.hpp"
00034 
00035 namespace asio {
00036 namespace detail {
00037 
00038 template <typename Time_Traits>
00039 class timer_queue
00040   : public timer_queue_base
00041 {
00042 public:
00043   // The time type.
00044   typedef typename Time_Traits::time_type time_type;
00045 
00046   // The duration type.
00047   typedef typename Time_Traits::duration_type duration_type;
00048 
00049   // Constructor.
00050   timer_queue()
00051     : timers_(),
00052       heap_(),
00053       cancelled_timers_(0),
00054       complete_timers_(0)
00055   {
00056   }
00057 
00058   // Add a new timer to the queue. Returns true if this is the timer that is
00059   // earliest in the queue, in which case the reactor's event demultiplexing
00060   // function call may need to be interrupted and restarted.
00061   template <typename Handler>
00062   bool enqueue_timer(const time_type& time, Handler handler, void* token)
00063   {
00064     // Ensure that there is space for the timer in the heap. We reserve here so
00065     // that the push_back below will not throw due to a reallocation failure.
00066     heap_.reserve(heap_.size() + 1);
00067 
00068     // Create a new timer object.
00069     std::auto_ptr<timer<Handler> > new_timer(
00070         new timer<Handler>(time, handler, token));
00071 
00072     // Insert the new timer into the hash.
00073     typedef typename hash_map<void*, timer_base*>::iterator iterator;
00074     typedef typename hash_map<void*, timer_base*>::value_type value_type;
00075     std::pair<iterator, bool> result =
00076       timers_.insert(value_type(token, new_timer.get()));
00077     if (!result.second)
00078     {
00079       result.first->second->prev_ = new_timer.get();
00080       new_timer->next_ = result.first->second;
00081       result.first->second = new_timer.get();
00082     }
00083 
00084     // Put the timer at the correct position in the heap.
00085     new_timer->heap_index_ = heap_.size();
00086     heap_.push_back(new_timer.get());
00087     up_heap(heap_.size() - 1);
00088     bool is_first = (heap_[0] == new_timer.get());
00089 
00090     // Ownership of the timer is transferred to the timer queue.
00091     new_timer.release();
00092 
00093     return is_first;
00094   }
00095 
00096   // Whether there are no timers in the queue.
00097   virtual bool empty() const
00098   {
00099     return heap_.empty();
00100   }
00101 
00102   // Get the time for the timer that is earliest in the queue.
00103   virtual boost::posix_time::time_duration wait_duration() const
00104   {
00105     if (heap_.empty())
00106       return boost::posix_time::pos_infin;
00107     return Time_Traits::to_posix_duration(
00108         Time_Traits::subtract(heap_[0]->time_, Time_Traits::now()));
00109   }
00110 
00111   // Dispatch the timers that are earlier than the specified time.
00112   virtual void dispatch_timers()
00113   {
00114     const time_type now = Time_Traits::now();
00115     while (!heap_.empty() && !Time_Traits::less_than(now, heap_[0]->time_))
00116     {
00117       timer_base* t = heap_[0];
00118       remove_timer(t);
00119       t->result_ = asio::error_code();
00120       t->prev_ = 0;
00121       t->next_ = complete_timers_;
00122       complete_timers_ = t;
00123     }
00124   }
00125 
00126   // Cancel the timers with the given token. Any timers pending for the token
00127   // will be notified that they have been cancelled next time
00128   // dispatch_cancellations is called. Returns the number of timers that were
00129   // cancelled.
00130   std::size_t cancel_timer(void* timer_token)
00131   {
00132     std::size_t num_cancelled = 0;
00133     typedef typename hash_map<void*, timer_base*>::iterator iterator;
00134     iterator it = timers_.find(timer_token);
00135     if (it != timers_.end())
00136     {
00137       timer_base* t = it->second;
00138       while (t)
00139       {
00140         timer_base* next = t->next_;
00141         remove_timer(t);
00142         t->prev_ = 0;
00143         t->next_ = cancelled_timers_;
00144         cancelled_timers_ = t;
00145         t = next;
00146         ++num_cancelled;
00147       }
00148     }
00149     return num_cancelled;
00150   }
00151 
00152   // Dispatch any pending cancels for timers.
00153   virtual void dispatch_cancellations()
00154   {
00155     while (cancelled_timers_)
00156     {
00157       timer_base* this_timer = cancelled_timers_;
00158       this_timer->result_ = asio::error::operation_aborted;
00159       cancelled_timers_ = this_timer->next_;
00160       this_timer->next_ = complete_timers_;
00161       complete_timers_ = this_timer;
00162     }
00163   }
00164 
00165   // Complete any timers that are waiting to be completed.
00166   virtual void complete_timers()
00167   {
00168     while (complete_timers_)
00169     {
00170       timer_base* this_timer = complete_timers_;
00171       complete_timers_ = this_timer->next_;
00172       this_timer->next_ = 0;
00173       this_timer->complete();
00174     }
00175   }
00176 
00177   // Destroy all timers.
00178   virtual void destroy_timers()
00179   {
00180     typename hash_map<void*, timer_base*>::iterator i = timers_.begin();
00181     typename hash_map<void*, timer_base*>::iterator end = timers_.end();
00182     while (i != end)
00183     {
00184       timer_base* t = i->second;
00185       typename hash_map<void*, timer_base*>::iterator old_i = i++;
00186       timers_.erase(old_i);
00187       destroy_timer_list(t);
00188     }
00189     heap_.clear();
00190     timers_.clear();
00191     destroy_timer_list(cancelled_timers_);
00192     destroy_timer_list(complete_timers_);
00193   }
00194 
00195 private:
00196   // Base class for timer operations. Function pointers are used instead of
00197   // virtual functions to avoid the associated overhead.
00198   class timer_base
00199   {
00200   public:
00201     // Delete the timer and post the handler.
00202     void complete()
00203     {
00204       complete_func_(this, result_);
00205     }
00206 
00207     // Delete the timer.
00208     void destroy()
00209     {
00210       destroy_func_(this);
00211     }
00212 
00213   protected:
00214     typedef void (*complete_func_type)(timer_base*,
00215         const asio::error_code&);
00216     typedef void (*destroy_func_type)(timer_base*);
00217 
00218     // Constructor.
00219     timer_base(complete_func_type complete_func, destroy_func_type destroy_func,
00220         const time_type& time, void* token)
00221       : complete_func_(complete_func),
00222         destroy_func_(destroy_func),
00223         time_(time),
00224         token_(token),
00225         next_(0),
00226         prev_(0),
00227         heap_index_(
00228             std::numeric_limits<size_t>::max BOOST_PREVENT_MACRO_SUBSTITUTION())
00229     {
00230     }
00231 
00232     // Prevent deletion through this type.
00233     ~timer_base()
00234     {
00235     }
00236 
00237   private:
00238     friend class timer_queue<Time_Traits>;
00239 
00240     // The function to be called to delete the timer and post the handler.
00241     complete_func_type complete_func_;
00242 
00243     // The function to be called to delete the timer.
00244     destroy_func_type destroy_func_;
00245 
00246     // The result of the timer operation.
00247     asio::error_code result_;
00248 
00249     // The time when the timer should fire.
00250     time_type time_;
00251 
00252     // The token associated with the timer.
00253     void* token_;
00254 
00255     // The next timer known to the queue.
00256     timer_base* next_;
00257 
00258     // The previous timer known to the queue.
00259     timer_base* prev_;
00260 
00261     // The index of the timer in the heap.
00262     size_t heap_index_;
00263   };
00264 
00265   // Adaptor class template for using handlers in timers.
00266   template <typename Handler>
00267   class timer
00268     : public timer_base
00269   {
00270   public:
00271     // Constructor.
00272     timer(const time_type& time, Handler handler, void* token)
00273       : timer_base(&timer<Handler>::complete_handler,
00274           &timer<Handler>::destroy_handler, time, token),
00275         handler_(handler)
00276     {
00277     }
00278 
00279     // Delete the timer and post the handler.
00280     static void complete_handler(timer_base* base,
00281         const asio::error_code& result)
00282     {
00283       // Take ownership of the timer object.
00284       typedef timer<Handler> this_type;
00285       this_type* this_timer(static_cast<this_type*>(base));
00286       typedef handler_alloc_traits<Handler, this_type> alloc_traits;
00287       handler_ptr<alloc_traits> ptr(this_timer->handler_, this_timer);
00288 
00289       // Make a copy of the error_code and the handler so that the memory can
00290       // be deallocated before the upcall is made.
00291       asio::error_code ec(result);
00292       Handler handler(this_timer->handler_);
00293 
00294       // Free the memory associated with the handler.
00295       ptr.reset();
00296 
00297       // Make the upcall.
00298       handler(ec);
00299     }
00300 
00301     // Delete the timer.
00302     static void destroy_handler(timer_base* base)
00303     {
00304       // Take ownership of the timer object.
00305       typedef timer<Handler> this_type;
00306       this_type* this_timer(static_cast<this_type*>(base));
00307       typedef handler_alloc_traits<Handler, this_type> alloc_traits;
00308       handler_ptr<alloc_traits> ptr(this_timer->handler_, this_timer);
00309 
00310       // A sub-object of the handler may be the true owner of the memory
00311       // associated with the handler. Consequently, a local copy of the handler
00312       // is required to ensure that any owning sub-object remains valid until
00313       // after we have deallocated the memory here.
00314       Handler handler(this_timer->handler_);
00315       (void)handler;
00316 
00317       // Free the memory associated with the handler.
00318       ptr.reset();
00319     }
00320 
00321   private:
00322     Handler handler_;
00323   };
00324 
00325   // Move the item at the given index up the heap to its correct position.
00326   void up_heap(size_t index)
00327   {
00328     size_t parent = (index - 1) / 2;
00329     while (index > 0
00330         && Time_Traits::less_than(heap_[index]->time_, heap_[parent]->time_))
00331     {
00332       swap_heap(index, parent);
00333       index = parent;
00334       parent = (index - 1) / 2;
00335     }
00336   }
00337 
00338   // Move the item at the given index down the heap to its correct position.
00339   void down_heap(size_t index)
00340   {
00341     size_t child = index * 2 + 1;
00342     while (child < heap_.size())
00343     {
00344       size_t min_child = (child + 1 == heap_.size()
00345           || Time_Traits::less_than(
00346             heap_[child]->time_, heap_[child + 1]->time_))
00347         ? child : child + 1;
00348       if (Time_Traits::less_than(heap_[index]->time_, heap_[min_child]->time_))
00349         break;
00350       swap_heap(index, min_child);
00351       index = min_child;
00352       child = index * 2 + 1;
00353     }
00354   }
00355 
00356   // Swap two entries in the heap.
00357   void swap_heap(size_t index1, size_t index2)
00358   {
00359     timer_base* tmp = heap_[index1];
00360     heap_[index1] = heap_[index2];
00361     heap_[index2] = tmp;
00362     heap_[index1]->heap_index_ = index1;
00363     heap_[index2]->heap_index_ = index2;
00364   }
00365 
00366   // Remove a timer from the heap and list of timers.
00367   void remove_timer(timer_base* t)
00368   {
00369     // Remove the timer from the heap.
00370     size_t index = t->heap_index_;
00371     if (!heap_.empty() && index < heap_.size())
00372     {
00373       if (index == heap_.size() - 1)
00374       {
00375         heap_.pop_back();
00376       }
00377       else
00378       {
00379         swap_heap(index, heap_.size() - 1);
00380         heap_.pop_back();
00381         size_t parent = (index - 1) / 2;
00382         if (index > 0 && Time_Traits::less_than(
00383               heap_[index]->time_, heap_[parent]->time_))
00384           up_heap(index);
00385         else
00386           down_heap(index);
00387       }
00388     }
00389 
00390     // Remove the timer from the hash.
00391     typedef typename hash_map<void*, timer_base*>::iterator iterator;
00392     iterator it = timers_.find(t->token_);
00393     if (it != timers_.end())
00394     {
00395       if (it->second == t)
00396         it->second = t->next_;
00397       if (t->prev_)
00398         t->prev_->next_ = t->next_;
00399       if (t->next_)
00400         t->next_->prev_ = t->prev_;
00401       if (it->second == 0)
00402         timers_.erase(it);
00403     }
00404   }
00405 
00406   // Destroy all timers in a linked list.
00407   void destroy_timer_list(timer_base*& t)
00408   {
00409     while (t)
00410     {
00411       timer_base* next = t->next_;
00412       t->next_ = 0;
00413       t->destroy();
00414       t = next;
00415     }
00416   }
00417 
00418   // A hash of timer token to linked lists of timers.
00419   hash_map<void*, timer_base*> timers_;
00420 
00421   // The heap of timers, with the earliest timer at the front.
00422   std::vector<timer_base*> heap_;
00423 
00424   // The list of timers to be cancelled.
00425   timer_base* cancelled_timers_;
00426 
00427   // The list of timers waiting to be completed.
00428   timer_base* complete_timers_;
00429 };
00430 
00431 } // namespace detail
00432 } // namespace asio
00433 
00434 #include "asio/detail/pop_options.hpp"
00435 
00436 #endif // ASIO_DETAIL_TIMER_QUEUE_HPP
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines


Castor
Author(s): Carpe Noctem
autogenerated on Fri Nov 8 2013 11:05:39