ACE/ace/Timer_Wheel_T.h

   1 // -*- C++ -*-
   2
   3 //=============================================================================
   4 /**
   5  *  @file    Timer_Wheel_T.h
   6  *
   7  *  @author Darrell Brunsch <brunsch@cs.wustl.edu>
   8  */
   9 //=============================================================================
  10
  11 #ifndef ACE_TIMER_WHEEL_T_H
  12 #define ACE_TIMER_WHEEL_T_H
  13 #include /**/ "ace/pre.h"
  14
  15 #include "ace/Timer_Queue_T.h"
  16 #include "ace/Copy_Disabled.h"
  17
  18 #if !defined (ACE_LACKS_PRAGMA_ONCE)
  19 # pragma once
  20 #endif /* ACE_LACKS_PRAGMA_ONCE */
  21
  22 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
  23
  24 // Forward declaration
  25 template <class TYPE, class FUNCTOR, class ACE_LOCK, typename TIME_POLICY>
  26 class ACE_Timer_Wheel_T;
  27
  28 /**
  29  * @class ACE_Timer_Wheel_Iterator_T
  30  *
  31  * @brief Iterates over an ACE_Timer_Wheel.
  32  *
  33  * This is a generic iterator that can be used to visit every
  34  * node of a timer queue.  Be aware that it doesn't traverse
  35  * in the order of timeout values.
  36  */
  37 template <class TYPE, class FUNCTOR, class ACE_LOCK, typename TIME_POLICY = ACE_Default_Time_Policy>
  38 class ACE_Timer_Wheel_Iterator_T
  39   : public ACE_Timer_Queue_Iterator_T <TYPE>
  40 {
  41 public:
  42   typedef ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK, TIME_POLICY> Wheel;
  43   typedef ACE_Timer_Node_T<TYPE> Node;
  44
  45   /// Constructor
  46   ACE_Timer_Wheel_Iterator_T (Wheel &);
  47
  48   /// Destructor
  49   virtual ~ACE_Timer_Wheel_Iterator_T (void);
  50
  51   /// Positions the iterator at the earliest node in the Timer Queue
  52   virtual void first (void);
  53
  54   /// Positions the iterator at the next node in the Timer Queue
  55   virtual void next (void);
  56
  57   /// Returns true when there are no more nodes in the sequence
  58   virtual bool isdone (void) const;
  59
  60   /// Returns the node at the current position in the sequence
  61   virtual ACE_Timer_Node_T<TYPE>* item (void);
  62
  63 protected:
  64   /// Pointer to the ACE_Timer_List that we are iterating over.
  65   Wheel& timer_wheel_;
  66
  67   /// Current position in the timing wheel
  68   u_int spoke_;
  69
  70   /// Pointer to the position in the the <pos_>th list
  71   ACE_Timer_Node_T<TYPE>* current_node_;
  72 private:
  73   void goto_next(u_int start_spoke);
  74 };
  75
  76 /**
  77  * @class ACE_Timer_Wheel_T
  78  *
  79  * @brief Provides a Timing Wheel version of ACE_Timer_Queue.
  80  *
  81  * This implementation uses a hash table of ordered doubly-
  82  * linked lists of absolute times.  The enhancements over the
  83  * @c ACE_Timer_List include adding a free list and the ability
  84  * to preallocate nodes.  Timer Wheel is based on the timing
  85  * wheel implementation used in Adam M. Costello and
  86  * George Varghese's paper "Redesigning the BSD Callout and
  87  * Timer Facilities"
  88  * (http://dworkin.wustl.edu/~varghese/PAPERS/newbsd.ps.Z)
  89  */
  90 template <class TYPE, class FUNCTOR, class ACE_LOCK, typename TIME_POLICY = ACE_Default_Time_Policy>
  91 class ACE_Timer_Wheel_T
  92   : public ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK, TIME_POLICY>
  93 {
  94 public:
  95   /// Type of iterator
  96   typedef ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK, TIME_POLICY> Iterator;
  97   /// Iterator is a friend
  98   friend class ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK, TIME_POLICY>;
  99   typedef ACE_Timer_Node_T<TYPE> Node;
 100   /// Type inherited from
 101   typedef ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK, TIME_POLICY> Base_Timer_Queue;
 102   typedef ACE_Free_List<Node> FreeList;
 103
 104   /// Default constructor
 105   ACE_Timer_Wheel_T (FUNCTOR* upcall_functor = 0, FreeList* freelist = 0,
 106                      TIME_POLICY const & time_policy = TIME_POLICY());
 107
 108   /// Constructor with opportunities to set the wheelsize and resolution
 109   ACE_Timer_Wheel_T (u_int spoke_count,
 110                      u_int resolution,
 111                      size_t prealloc = 0,
 112                      FUNCTOR* upcall_functor = 0,
 113                      FreeList* freelist = 0,
 114                      TIME_POLICY const & time_policy = TIME_POLICY());
 115
 116   /// Destructor
 117   virtual ~ACE_Timer_Wheel_T (void);
 118
 119   /// True if queue is empty, else false.
 120   virtual bool is_empty (void) const;
 121
 122   /// Returns the time of the earlier node in the ACE_Timer_Wheel.
 123   /// Must be called on a non-empty queue.
 124   virtual const ACE_Time_Value& earliest_time (void) const;
 125
 126   /// Changes the interval of a timer (and can make it periodic or non
 127   /// periodic by setting it to ACE_Time_Value::zero or not).
 128   virtual int reset_interval (long timer_id,
 129                               const ACE_Time_Value& interval);
 130
 131   /// Cancel all timer associated with @a type.  If @a dont_call_handle_close is
 132   /// 0 then the <functor> will be invoked.  Returns number of timers
 133   /// cancelled.
 134   virtual int cancel (const TYPE& type,
 135                       int dont_call_handle_close = 1);
 136
 137   // Cancel a timer, storing the magic cookie in act (if nonzero).
 138   // Calls the functor if dont_call_handle_close is 0 and returns 1
 139   // on success
 140   virtual int cancel (long timer_id,
 141                       const void** act = 0,
 142                       int dont_call_handle_close = 1);
 143
 144   /**
 145    * Destroy timer queue. Cancels all timers.
 146    */
 147   virtual int close (void);
 148
 149   /// Run the <functor> for all timers whose values are <=
 150   /// <ACE_OS::gettimeofday>.  Also accounts for <timer_skew>.  Returns
 151   /// the number of timers canceled.
 152   virtual int expire (void);
 153
 154   // Run the <functor> for all timers whose values are <= @a current_time.
 155   // This does not account for <timer_skew>.  Returns the number of
 156   // timers canceled.
 157   int expire (const ACE_Time_Value& current_time);
 158
 159   /// Returns a pointer to this <ACE_Timer_Queue_T>'s iterator.
 160   virtual ACE_Timer_Queue_Iterator_T<TYPE> & iter (void);
 161
 162   /// Removes the earliest node from the queue and returns it
 163   virtual ACE_Timer_Node_T<TYPE>* remove_first (void);
 164
 165   /// Dump the state of an object.
 166   virtual void dump (void) const;
 167
 168   /// Reads the earliest node from the queue and returns it.
 169   virtual ACE_Timer_Node_T<TYPE>* get_first (void);
 170
 171 protected:
 172   /// Schedules a timer.
 173   virtual long schedule_i (const TYPE& type,
 174                            const void* act,
 175                            const ACE_Time_Value& future_time,
 176                            const ACE_Time_Value& interval);
 177
 178 private:
 179   // The following are documented in the .cpp file.
 180   ACE_Timer_Node_T<TYPE>* get_first_i (void) const;
 181   ACE_Timer_Node_T<TYPE>* remove_first_expired (const ACE_Time_Value& now);
 182   void open_i (size_t prealloc, u_int spokes, u_int res);
 183   virtual void reschedule (ACE_Timer_Node_T<TYPE> *);
 184   ACE_Timer_Node_T<TYPE>* find_spoke_node(u_int spoke, long timer_id) const;
 185   ACE_Timer_Node_T<TYPE>* find_node(long timer_id) const;
 186   u_int calculate_spoke(const ACE_Time_Value& expire) const;
 187   long generate_timer_id(u_int spoke);
 188   void schedule_i (ACE_Timer_Node_T<TYPE>* n, u_int spoke, const ACE_Time_Value& expire);
 189   void cancel_i (ACE_Timer_Node_T<TYPE>* n);
 190   void unlink (ACE_Timer_Node_T<TYPE>* n);
 191   void recalc_earliest(const ACE_Time_Value& last);
 192
 193 private:
 194   int power2bits (int n, int min_bits, int max_bits);
 195
 196   /// Timing Wheel.
 197   ACE_Timer_Node_T<TYPE>** spokes_;
 198   /// Size of the timing wheel.
 199   u_int spoke_count_;
 200   /// Number of timer_id bits used for the spoke
 201   int spoke_bits_;
 202   /// Resolution (in microsoconds) of the timing wheel.
 203   int res_bits_;
 204   /// Index of the list with the earliest time
 205   u_int earliest_spoke_;
 206   /// Iterator used to expire timers.
 207   Iterator* iterator_;
 208   /// The total amount of time in one iteration of the wheel. (resolution * spoke_count)
 209   ACE_Time_Value wheel_time_;
 210   /// The total number of timers currently scheduled.
 211   u_int timer_count_;
 212 };
 213
 214 ACE_END_VERSIONED_NAMESPACE_DECL
 215
 216 #if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
 217 #include "ace/Timer_Wheel_T.cpp"
 218 #endif /* ACE_TEMPLATES_REQUIRE_SOURCE */
 219
 220 #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
 221 #pragma implementation ("Timer_Wheel_T.cpp")
 222 #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */
 223
 224 #include /**/ "ace/post.h"
 225 #endif /* ACE_TIMER_WHEEL_T_H */