Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

ACE_Timer_Wheel_T Class Template Reference

Provides a Timing Wheel version of ACE_Timer_Queue. More...

#include <Timer_Wheel_T.h>

Inheritance diagram for ACE_Timer_Wheel_T:

Inheritance graph
[legend]
Collaboration diagram for ACE_Timer_Wheel_T:

Collaboration graph
[legend]
List of all members.

Public Types

typedef ACE_Timer_Wheel_Iterator_T<
TYPE, FUNCTOR, ACE_LOCK > 		Iterator
 Type of iterator. More...

typedef ACE_Timer_Node_T<
TYPE > 		Node
typedef ACE_Timer_Queue_T<
TYPE, FUNCTOR, ACE_LOCK > 		Base
 Type inherited from. More...

typedef ACE_Free_List< Node > FreeList

Public Methods

 ACE_Timer_Wheel_T (FUNCTOR *upcall_functor=0, FreeList *freelist=0)
 Default constructor. More...

 ACE_Timer_Wheel_T (u_int spoke_count, u_int resolution, size_t prealloc=0, FUNCTOR *upcall_functor=0, FreeList *freelist=0)
 Constructor with opportunities to set the wheelsize and resolution. More...

virtual ~ACE_Timer_Wheel_T (void)
 Destructor. More...

virtual int is_empty (void) const
 True if queue is empty, else false. More...

virtual const ACE_Time_Value & earliest_time (void) const
 Returns the time of the earlier node in the <ACE_Timer_Wheel>. Must be called on a non-empty queue. More...

virtual long schedule (const TYPE &type, const void *act, const ACE_Time_Value &future_time, const ACE_Time_Value &interval=ACE_Time_Value::zero)
 Schedules a timer. More...

virtual int reset_interval (long timer_id, const ACE_Time_Value &interval)
 Changes the interval of a timer (and can make it periodic or non periodic by setting it to ACE_Time_Value::zero or not). More...

virtual int cancel (const TYPE &type, int dont_call_handle_close=1)
 Cancel all timer associated with <type>. If <dont_call> is 0 then the <functor> will be invoked. Returns number of timers cancelled. More...

virtual int cancel (long timer_id, const void **act=0, int dont_call_handle_close=1)
virtual int expire (void)
 Run the <functor> for all timers whose values are <= <ACE_OS::gettimeofday>. Also accounts for <timer_skew>. Returns the number of timers canceled. More...

int expire (const ACE_Time_Value &)
virtual ACE_Timer_Queue_Iterator_T<
TYPE, FUNCTOR, ACE_LOCK > & 		iter (void)
 Returns a pointer to this <ACE_Timer_Queue_T>'s iterator. More...

virtual ACE_Timer_Node_T<
TYPE > * 		remove_first (void)
 Removes the earliest node from the queue and returns it. More...

virtual void dump (void) const
 Dump the state of an object. More...

virtual ACE_Timer_Node_T<
TYPE > * 		get_first (void)
 Reads the earliest node from the queue and returns it. More...


Private Methods

ACE_Timer_Node_T< TYPE > * get_first_i (void) const
ACE_Timer_Node_T< TYPE > * remove_first_expired (const ACE_Time_Value &now)
void open_i (size_t prealloc, u_int spokes, u_int res)
virtual void reschedule (ACE_Timer_Node_T< TYPE > *)
ACE_Timer_Node_T< TYPE > * find_spoke_node (u_int spoke, long timer_id) const
 Searches for a node by timer_id within one spoke. More...

ACE_Timer_Node_T< TYPE > * find_node (long timer_id) const
 Searches all spokes for a node matching the specified timer_id Uses the spoke encoded in the timer_id as a starting place. More...

u_int calculate_spoke (const ACE_Time_Value &expire) const
 Uses a simple hash to find which spoke to use based on when the timer is due to expire. Hopefully the 64bit int operations avoid any overflow problems. More...

long generate_timer_id (u_int spoke)
 Generates a unique timer_id for the given spoke. It should be pretty fast until the point where the counter overflows. At that time you have to do exhaustive searches within the spoke to ensure that a particular timer id is not already in use. Some optimizations are in place so that this hopefully doesn't have to happen often. More...

void schedule_i (ACE_Timer_Node_T< TYPE > *n, u_int spoke, const ACE_Time_Value &expire)
 The shared scheduling functionality between schedule() and reschedule(). More...

void cancel_i (ACE_Timer_Node_T< TYPE > *n, int skip_close)
 Shared subset of the two cancel() methods. More...

void unlink (ACE_Timer_Node_T< TYPE > *n)
void recalc_earliest (const ACE_Time_Value &last)
 There are a few places where we have to figure out which timer will expire next. This method makes the assumption that spokes are always sorted, and that timers are always in the correct spoke determined from their expiration time. The last time is always passed in, even though you can often calculate it as get_first()->get_timer_value(). More...

 ACE_Timer_Wheel_T (const ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK > &)
void operator= (const ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK > &)

Private Attributes

ACE_Timer_Node_T< TYPE > ** spokes_
 Timing Wheel. More...

u_int spoke_count_
 Size of the timing wheel. More...

int spoke_bits_
 Number of timer_id bits used for the spoke. More...

u_int max_per_spoke_
 Maximum number of timers per spoke. More...

int res_bits_
 Resolution (in microsoconds) of the timing wheel. More...

u_int earliest_spoke_
 Index of the list with the earliest time. More...

Iterator * iterator_
 Iterator used to expire timers. More...

ACE_Time_Value wheel_time_
 The total amount of time in one iteration of the wheel. (resolution * spoke_count). More...

u_int timer_count_
 The total number of timers currently scheduled. More...


Friends

class ACE_Timer_Wheel_Iterator_T< TYPE, FUNCTOR, ACE_LOCK >
 Iterator is a friend. More...

Detailed Description

template<class TYPE, class FUNCTOR, class ACE_LOCK>
class ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >

Provides a Timing Wheel version of ACE_Timer_Queue.

This implementation uses a hash table of ordered doubly- linked lists of absolute times. The enhancements over the ACE_Timer_List include adding a free list and the ability to preallocate nodes. Timer Wheel is based on the timing wheel implementation used in Adam M. Costello and George Varghese's paper "Redesigning the BSD Callout and Timer Facilities" (http://dworkin.wustl.edu/~varghese/PAPERS/newbsd.ps.Z)

Definition at line 90 of file Timer_Wheel_T.h.

Member Typedef Documentation

template<class TYPE, class FUNCTOR, class ACE_LOCK>
typedef ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK> ACE_Timer_Wheel_T::Base
 

Type inherited from.

Definition at line 99 of file Timer_Wheel_T.h.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
typedef ACE_Free_List<Node> ACE_Timer_Wheel_T::FreeList
 

Definition at line 100 of file Timer_Wheel_T.h.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
typedef ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK> ACE_Timer_Wheel_T::Iterator
 

Type of iterator.

Definition at line 94 of file Timer_Wheel_T.h.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
typedef ACE_Timer_Node_T<TYPE> ACE_Timer_Wheel_T::Node
 

Definition at line 97 of file Timer_Wheel_T.h.

Constructor & Destructor Documentation

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::ACE_Timer_Wheel_T (  FUNCTOR *    upcall_functor = 0,
FreeList *    freelist = 0
) 
 

Default constructor.

Default Constructor that sets defaults for spoke_count_ and resolution_ and doesn't do any preallocation.

Parameters:
upcall_functor  A pointer to a functor to use instead of the default
freelist  A pointer to a freelist to use instead of the default

Definition at line 45 of file Timer_Wheel_T.cpp.

References ACE_DEFAULT_TIMER_WHEEL_RESOLUTION, ACE_DEFAULT_TIMER_WHEEL_SIZE, and ACE_TRACE. 

00048 : Base (upcall_functor, freelist)
00049 , spokes_(0)
00050 , spoke_count_(0) // calculated in open_i
00051 , spoke_bits_(0)
00052 , res_bits_ (0)
00053 , earliest_spoke_ (0)
00054 , iterator_(0)
00055 , timer_count_(0)
00056 {
00057   ACE_TRACE ("ACE_Timer_Wheel_T::ACE_Timer_Wheel_T");
00058   this->open_i (0,
00059                 ACE_DEFAULT_TIMER_WHEEL_SIZE,
00060                 ACE_DEFAULT_TIMER_WHEEL_RESOLUTION);
00061 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::ACE_Timer_Wheel_T (  u_int    spoke_count,
u_int    resolution,
size_t    prealloc = 0,
FUNCTOR *    upcall_functor = 0,
FreeList *    freelist = 0
) 
 

Constructor with opportunities to set the wheelsize and resolution.

Constructor that sets up the timing wheel and also may preallocate some nodes on the free list

Parameters:
spoke_count  The number of lists in the timer wheel
resolution  The time resolution in milliseconds used by the hashing function
prealloc  The number of entries to prealloc in the free_list
upcall_functor  A pointer to a functor to use instead of the default
freelist  A pointer to a freelist to use instead of the default

Definition at line 75 of file Timer_Wheel_T.cpp.

References ACE_TRACE. 

00080 : Base (upcall_functor, freelist)
00081 , spokes_ (0)
00082 , spoke_count_ (0) // calculated in open_i
00083 , spoke_bits_ (0)
00084 , res_bits_ (0)
00085 , earliest_spoke_ (0)
00086 , iterator_ (0)
00087 , timer_count_ (0)
00088 {
00089   ACE_TRACE ("ACE_Timer_Wheel_T::ACE_Timer_Wheel_T");
00090   this->open_i (prealloc, spoke_count, resolution);
00091 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::~ACE_Timer_Wheel_T (  void    )  [virtual]
 

Destructor.

Definition at line 163 of file Timer_Wheel_T.cpp.

References ACE_TRACE, ACE_Timer_Queue_T::free_node, ACE_Timer_Node_T::get_act, ACE_Timer_Node_T::get_next, ACE_Timer_Node_T::get_type, iterator_, spoke_count_, spokes_, and ACE_Timer_Queue_T::upcall_functor. 

00164 {
00165   ACE_TRACE ("ACE_Timer_Wheel_T::~ACE_Timer_Wheel_T");
00166 
00167   delete iterator_;
00168 
00169   for (u_int i = 0; i < this->spoke_count_; ++i)
00170   {
00171     // Free all the nodes starting at the root
00172     ACE_Timer_Node_T<TYPE>* root = this->spokes_[i];
00173     for (ACE_Timer_Node_T<TYPE>* n = root->get_next (); n != root;)
00174     {
00175       ACE_Timer_Node_T<TYPE>* next = n->get_next ();
00176       this->upcall_functor ().deletion (*this, n->get_type (), n->get_act ());
00177       this->free_node (n);
00178       n = next;
00179     }
00180     delete root;
00181   }
00182   delete[] this->spokes_;
00183 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::ACE_Timer_Wheel_T (  const ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK > &    )  [private]
 

Member Function Documentation

template<class TYPE, class FUNCTOR, class ACE_LOCK>
u_int ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::calculate_spoke (  const ACE_Time_Value &    expire )  const [private]
 

Uses a simple hash to find which spoke to use based on when the timer is due to expire. Hopefully the 64bit int operations avoid any overflow problems.

Definition at line 266 of file Timer_Wheel_T.cpp.

Referenced by reschedule, and schedule. 

00267 {
00268   return ACE_static_cast(u_int, (t.msec () >> this->res_bits_) & (this->spoke_count_ - 1));
00269 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::cancel (  long    timer_id,
const void **    act = 0,
int    skip_close = 1
)  [virtual]
 

Cancels the single timer that is specified by the timer_id. In this case the timer_id is actually a pointer to the node, so we cast it to the node. This can be dangerous if the timer_id is made up (or deleted twice) so we do a little sanity check. Finally we update the earliest time in case the earliest timer was removed.

Parameters:
timer_id  Timer Identifier
act  Asychronous Completion Token (AKA magic cookie): If this is non-zero, stores the magic cookie of the cancelled timer here.
skip_close  If this non-zero, the cancellation method of the functor will not be called.
Returns:
1 for sucess and 0 if the timer_id wasn't found (or was found to be invalid)

Implements ACE_Timer_Queue_T.

Definition at line 571 of file Timer_Wheel_T.cpp.

References ACE_GUARD_RETURN, ACE_MT, ACE_TRACE, cancel_i, find_node, ACE_Timer_Node_T::get_act, get_first_i, ACE_Timer_Node_T::get_timer_value, and recalc_earliest. 

00574 {
00575   ACE_TRACE ("ACE_Timer_Wheel_T::cancel");
00576   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
00577   ACE_Timer_Node_T<TYPE>* n = this->find_node (timer_id);
00578   if (n != 0)
00579     {
00580       ACE_Time_Value last = n->get_timer_value ();
00581       int recalc = (this->get_first_i () == n);
00582       if (act != 0)
00583         *act = n->get_act ();
00584       this->cancel_i (n, skip_close);
00585       if (recalc)
00586         this->recalc_earliest (last);
00587       return 1;
00588     }
00589   return 0;
00590 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::cancel (  const TYPE &    type,
int    skip_close = 1
)  [virtual]
 

Cancel all timer associated with <type>. If <dont_call> is 0 then the <functor> will be invoked. Returns number of timers cancelled.

Goes through every list in the wheel and whenever we find one with the correct type value, we remove it and continue. At the end make sure we reset the earliest time value in case the earliest timers were removed.

Parameters:
type  The value to search for.
skip_close  If this non-zero, the cancellation method of the functor will not be called for each cancelled timer.
Returns:
Number of timers cancelled

Implements ACE_Timer_Queue_T.

Definition at line 506 of file Timer_Wheel_T.cpp.

References ACE_GUARD_RETURN, ACE_MT, ACE_TRACE, cancel_i, get_first, ACE_Timer_Node_T::get_next, ACE_Timer_Node_T::get_timer_value, ACE_Timer_Node_T::get_type, is_empty, recalc_earliest, spoke_count_, spokes_, and ACE_Timer_Queue_T::upcall_functor. 

00507 {
00508   ACE_TRACE ("ACE_Timer_Wheel_T::cancel");
00509   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
00510 
00511   int num_canceled = 0; // Note : Technically this can overflow.
00512 
00513   if (!this->is_empty ())
00514     {
00515       ACE_Timer_Node_T<TYPE>* first = this->get_first ();
00516       ACE_Time_Value last = first->get_timer_value ();
00517       int recalc = 0;
00518 
00519       for (u_int i = 0; i < this->spoke_count_; ++i)
00520         {
00521           ACE_Timer_Node_T<TYPE>* root = this->spokes_[i];
00522           for (ACE_Timer_Node_T<TYPE>* n = root->get_next (); n != root; )
00523             {
00524               if (n->get_type () == type)
00525                 {
00526                   ++num_canceled;
00527                   if (n == first)
00528                     recalc = 1;
00529 
00530                   ACE_Timer_Node_T<TYPE>* tmp = n;
00531                   n = n->get_next ();
00532                   int always_skip_close = 1; // todo : Is this correct?
00533                   this->cancel_i (tmp, always_skip_close);
00534                 }
00535               else
00536                 {
00537                   n = n->get_next ();
00538                 }
00539             }
00540         }
00541 
00542       if (recalc)
00543         this->recalc_earliest (last);
00544     }
00545 
00546   if (!skip_close)  //  && num_canceled > 0)
00547     this->upcall_functor().cancellation (*this, type);
00548 
00549   return num_canceled;
00550 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::cancel_i (  ACE_Timer_Node_T< TYPE > *    n,
int    skip_close
)  [private]
 

Shared subset of the two cancel() methods.

Definition at line 594 of file Timer_Wheel_T.cpp.

References ACE_Timer_Queue_T::free_node, ACE_Timer_Node_T::get_type, unlink, and ACE_Timer_Queue_T::upcall_functor.

Referenced by cancel. 

00595 {
00596   //ACE_ERROR((LM_ERROR, "Canceling %x\n", (long) n));
00597   this->unlink (n);
00598   this->free_node (n);
00599   if (!skip_close)
00600     this->upcall_functor ().cancellation (*this, n->get_type ());
00601 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::dump (  void    )  const [virtual]
 

Dump the state of an object.

Dumps out the size of the wheel, the resolution, and the contents of the wheel.

Reimplemented from ACE_Timer_Queue_T.

Definition at line 650 of file Timer_Wheel_T.cpp.

References ACE_BEGIN_DUMP, ACE_DEBUG, ACE_END_DUMP, ACE_LIB_TEXT, ACE_TRACE, ACE_Timer_Node_T::dump, ACE_Timer_Node_T::get_next, LM_DEBUG, spoke_count_, and spokes_. 

00651 {
00652   ACE_TRACE ("ACE_Timer_Wheel_T::dump");
00653   ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
00654   
00655   ACE_DEBUG ((LM_DEBUG,
00656     ACE_LIB_TEXT ("\nspoke_count_ = %d"), this->spoke_count_));
00657   ACE_DEBUG ((LM_DEBUG,
00658     ACE_LIB_TEXT ("\nresolution_ = %d"), 1 << this->res_bits_));
00659   ACE_DEBUG ((LM_DEBUG,
00660     ACE_LIB_TEXT ("\nwheel_ = \n")));
00661   
00662   for (u_int i = 0; i < this->spoke_count_; ++i)
00663     {
00664       ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("%d\n"), i));
00665       ACE_Timer_Node_T<TYPE>* root = this->spokes_[i];
00666       for (ACE_Timer_Node_T<TYPE>* n = root->get_next ();
00667            n != root;
00668            n = n->get_next ())
00669         {
00670           n->dump ();
00671         }
00672     }
00673   
00674   ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
00675 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
const ACE_Time_Value & ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::earliest_time (  void    )  const [virtual]
 

Returns the time of the earlier node in the <ACE_Timer_Wheel>. Must be called on a non-empty queue.

Returns:
First (earliest) node in the wheel_'s earliest_spoke_ list

Implements ACE_Timer_Queue_T.

Definition at line 252 of file Timer_Wheel_T.cpp.

References ACE_TRACE, get_first_i, ACE_Timer_Node_T::get_timer_value, and ACE_Time_Value::zero. 

00253 {
00254   ACE_TRACE ("ACE_Timer_Wheel_T::earliest_time");
00255   ACE_Timer_Node_T<TYPE>* n = this->get_first_i ();
00256   if (n != 0)
00257     return n->get_timer_value ();
00258   return ACE_Time_Value::zero;
00259 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::expire (  const ACE_Time_Value &    cur_time )  [virtual]
 

This is a specialized version of expire that is more suited for the internal data representation.

Parameters:
cur_time  The time to expire timers up to.
Returns:
Number of timers expired

Reimplemented from ACE_Timer_Queue_T.

Definition at line 769 of file Timer_Wheel_T.cpp.

References ACE_GUARD_RETURN, ACE_MT, ACE_TRACE, ACE_Timer_Queue_T::free_node, ACE_Timer_Node_T::get_act, ACE_Timer_Node_T::get_interval, ACE_Timer_Node_T::get_type, remove_first_expired, reschedule, ACE_Timer_Node_T::set_timer_value, ACE_Timer_Queue_T::upcall, and ACE_Time_Value::zero. 

00770 {
00771   ACE_TRACE ("ACE_Timer_Wheel_T::expire");
00772   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
00773 
00774   int expcount = 0;
00775   ACE_Timer_Node_T<TYPE>* n = this->remove_first_expired (cur_time);
00776 
00777   while (n != 0)
00778     {
00779       ++ expcount;
00780 
00781       //ACE_ERROR((LM_ERROR, "Expiring %x\n", (long) n));
00782 
00783       this->upcall (n->get_type (), n->get_act (), cur_time);
00784 
00785       if (n->get_interval () > ACE_Time_Value::zero)
00786         {
00787           n->set_timer_value (cur_time + n->get_interval ());
00788           this->reschedule (n);
00789         }
00790       else
00791         {
00792           this->free_node (n);
00793         }
00794 
00795       n = this->remove_first_expired (cur_time);
00796     }
00797 
00798   //ACE_ERROR((LM_ERROR, "Expired %d nodes\n", expcount));
00799 
00800   return expcount;
00801 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::expire (  void    )  [virtual]
 

Run the <functor> for all timers whose values are <= <ACE_OS::gettimeofday>. Also accounts for <timer_skew>. Returns the number of timers canceled.

Dummy version of expire to get rid of warnings in Sun CC 4.2 Just call the expire of the base class.

Reimplemented from ACE_Timer_Queue_T.

Definition at line 755 of file Timer_Wheel_T.cpp.

References ACE_Timer_Queue_T::expire.

Referenced by reschedule. 

00756 {
00757   return ACE_Timer_Queue_T<TYPE,FUNCTOR,ACE_LOCK>::expire ();
00758 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T< TYPE > * ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::find_node (  long    timer_id )  const [private]
 

Searches all spokes for a node matching the specified timer_id Uses the spoke encoded in the timer_id as a starting place.

Definition at line 206 of file Timer_Wheel_T.cpp.

References find_spoke_node, and spoke_count_.

Referenced by cancel, and reset_interval. 

00207 {
00208   if (timer_id == -1)
00209     return 0;
00210 
00211   // Search the spoke where timer_id was originally scheduled
00212   u_int spoke_mask = this->spoke_count_ - 1;
00213   u_int start = timer_id & spoke_mask;
00214   ACE_Timer_Node_T<TYPE>* n = this->find_spoke_node (start, timer_id);
00215   if (n != 0)
00216     return n;
00217 
00218   //ACE_ERROR((LM_ERROR, "Node not found in original spoke.\n"));
00219 
00220   // Search the rest of the spokes
00221   for (u_int i = 0; i < this->spoke_count_; ++i)
00222     {
00223       if (i != start)
00224         { // already searched this one
00225           n = this->find_spoke_node (i, timer_id);
00226           if (n != 0)
00227             return n;
00228         }
00229     }
00230 
00231   //ACE_ERROR((LM_ERROR, "Node not found.\n"));
00232   return 0;
00233 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T< TYPE > * ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::find_spoke_node (  u_int    spoke,
long    timer_id
)  const [private]
 

Searches for a node by timer_id within one spoke.

Definition at line 189 of file Timer_Wheel_T.cpp.

References ACE_Timer_Node_T::get_next, and ACE_Timer_Node_T::get_timer_id.

Referenced by find_node, and generate_timer_id. 

00190 {
00191   ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
00192   for (ACE_Timer_Node_T<TYPE>* n = root->get_next ();
00193        n != root;
00194        n = n->get_next ())
00195     {
00196       if (n->get_timer_id () == timer_id)
00197         return n;
00198     }
00199   return 0;
00200 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
long ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::generate_timer_id (  u_int    spoke )  [private]
 

Generates a unique timer_id for the given spoke. It should be pretty fast until the point where the counter overflows. At that time you have to do exhaustive searches within the spoke to ensure that a particular timer id is not already in use. Some optimizations are in place so that this hopefully doesn't have to happen often.

Definition at line 277 of file Timer_Wheel_T.cpp.

References find_spoke_node, ACE_Timer_Node_T::get_act, ACE_Timer_Node_T::get_next, ACE_Timer_Node_T::get_timer_id, ACE_Timer_Node_T::set_act, ACE_Timer_Node_T::set_timer_id, spoke_bits_, spoke_count_, and spokes_.

Referenced by schedule. 

00278 {
00279 
00280   int cnt_bits = sizeof (long) * 8 - this->spoke_bits_;
00281   long max_cnt = ((long)1 << cnt_bits) - 1;
00282   if (spoke == this->spoke_count_)
00283     --max_cnt; // Because -1 is used as a special invalid timer_id.
00284 
00285   ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
00286 
00287   if (root == root->get_next ())
00288     root->set_act(0);
00289 
00290   // We use this field to keep track of the next counter value that
00291   // may be in use. Of course it may have expired, so we just use
00292   // this field so that we know when we don't have to check for duplicates
00293 #if defined (ACE_WIN64)
00294   // The cast below is legit... we know that long is shorter than a
00295   // pointer, but are only using it as a 'long' storage area.
00296 #  pragma warning(push)
00297 #  pragma warning(disable : 4311)
00298 #endif /* ACE_WIN64 */
00299   long next_cnt = ACE_reinterpret_cast (long, root->get_act ());
00300 #if defined (ACE_WIN64)
00301 #  pragma warning(pop)
00302 #endif /* ACE_WIN64 */
00303 
00304   // This field is used as a counter instead of a timer_id.
00305   long cnt = root->get_timer_id ();
00306 
00307   if (cnt >= max_cnt && root == root->get_next ())
00308     {
00309       // Special case when we overflow on an empty spoke. We can just
00310       // wrap the count around without searching for duplicates. We only
00311       // want to do this when the counter overflows, so that we return
00312       // unique timer_id values as often as possible.
00313       root->set_timer_id (1);
00314       return spoke;
00315     }
00316   else if (cnt >= max_cnt)
00317     { // overflow
00318       cnt = 0; // try again starting at zero
00319     }
00320   else if (next_cnt == 0 || cnt < next_cnt)
00321     {
00322       root->set_timer_id (cnt + 1);
00323       return (cnt << this->spoke_bits_) | spoke;
00324     }
00325 
00326   //ACE_ERROR((LM_ERROR, "Timer id overflow. We have to search now.\n"));
00327 
00328   // We've run out of consecutive id numbers so now we have to search
00329   // for a unique id.
00330   // We'll try increasing numbers until we find one that is not in use,
00331   // and we'll record the next highest number so that we can avoid this
00332   // search as often as possible.
00333   for (; cnt < max_cnt - 1; ++cnt)
00334     {
00335       long id = (cnt << this->spoke_bits_) | spoke;
00336       ACE_Timer_Node_T<TYPE>* n = this->find_spoke_node (spoke, id);
00337       if (n == 0)
00338         {
00339           root->set_timer_id (cnt + 1);
00340           // Now we need to find the next highest cnt in use
00341           next_cnt = 0;
00342           for (; n != root; n = n->get_next ())
00343             {
00344               long tmp = n->get_timer_id () >> this->spoke_bits_;
00345               if (tmp > cnt && (tmp < next_cnt || next_cnt == 0))
00346                 next_cnt = tmp;
00347             }
00348 #if defined (ACE_WIN64)
00349           // The cast below is legit... we know we're storing a long in
00350           // a pointer, but are only using it as a 'long' storage area.
00351 #  pragma warning(push)
00352 #  pragma warning(disable : 4312)
00353 #endif /* ACE_WIN64 */
00354           root->set_act (ACE_reinterpret_cast (void*, next_cnt));
00355 #if defined (ACE_WIN64)
00356 #  pragma warning(pop)
00357 #endif /* ACE_WIN64 */
00358           return id;
00359         }
00360     }
00361 
00362   return -1; // We did our best, but the spoke is full.
00363 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T< TYPE > * ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::get_first (  void    )  [virtual]
 

Reads the earliest node from the queue and returns it.

Returns the earliest node without removing it

Returns:
The earliest timer node.

Implements ACE_Timer_Queue_T.

Definition at line 721 of file Timer_Wheel_T.cpp.

References ACE_TRACE, and get_first_i.

Referenced by cancel, and remove_first_expired. 

00722 {
00723   ACE_TRACE ("ACE_Timer_Wheel_T::get_first");
00724   return this->get_first_i ();
00725 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T< TYPE > * ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::get_first_i (  void    )  const [private]
 

Definition at line 729 of file Timer_Wheel_T.cpp.

References earliest_spoke_, ACE_Timer_Node_T::get_next, and spokes_.

Referenced by cancel, earliest_time, and get_first. 

00730 {
00731   ACE_Timer_Node_T<TYPE>* root = this->spokes_[this->earliest_spoke_];
00732   ACE_Timer_Node_T<TYPE>* first = root->get_next ();
00733   if (first != root)
00734     return first;
00735   return 0;
00736 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::is_empty (  void    )  const [virtual]
 

True if queue is empty, else false.

Check to see if the wheel is empty

Returns:
True if empty

Implements ACE_Timer_Queue_T.

Definition at line 241 of file Timer_Wheel_T.cpp.

References ACE_TRACE, and timer_count_.

Referenced by cancel. 

00242 {
00243   ACE_TRACE ("ACE_Timer_Wheel_T::is_empty");
00244   return timer_count_ == 0;
00245 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Queue_Iterator_T< TYPE, FUNCTOR, ACE_LOCK > & ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::iter (  void    )  [virtual]
 

Returns a pointer to this <ACE_Timer_Queue_T>'s iterator.

Returns:
The iterator

Implements ACE_Timer_Queue_T.

Definition at line 744 of file Timer_Wheel_T.cpp.

References ACE_Timer_Wheel_Iterator_T::first, and iterator_. 

00745 {
00746   this->iterator_->first ();
00747   return *this->iterator_;
00748 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::open_i (  size_t    prealloc,
u_int    spokes,
u_int    res
)  [private]
 

Initialize the queue. Uses the established members for all needed information.

Definition at line 127 of file Timer_Wheel_T.cpp.

References ACE_NEW, ACE_TRACE, ACE_OS::gettimeofday, power2bits, ACE_Timer_Node_T::set, spoke_count_, and ACE_Time_Value::zero. 

00128 {
00129   ACE_TRACE ("ACE_Timer_Wheel_T::open_i");
00130 
00131   this->gettimeofday (ACE_OS::gettimeofday);
00132 
00133   // Rather than waste bits in our timer id, we might as well round up
00134   // the spoke count to the next power of two - 1 . (i.e 1,3,7,15,...127,etc.)
00135   const int MIN_SPOKE_BITS = 3;  // Allow between 8 and 4096 spokes
00136   const int MAX_SPOKE_BITS = 12;
00137   const int MAX_RES_BITS = 20;   // 20 is plenty, even on 64 bit platforms.
00138 
00139   this->spoke_bits_ = power2bits (spokes, MIN_SPOKE_BITS, MAX_SPOKE_BITS);
00140   this->res_bits_ = power2bits (res, 1, MAX_RES_BITS);
00141 
00142   this->spoke_count_ = 1 << this->spoke_bits_;
00143 
00144   this->free_list_->resize (prealloc + this->spoke_count_);
00145 
00146   this->wheel_time_.msec (1 << (this->res_bits_ + this->spoke_bits_));
00147 
00148   ACE_NEW (this->spokes_, ACE_Timer_Node_T<TYPE>* [this->spoke_count_]);
00149 
00150   // Create the root nodes. These will be treated specially
00151   for (u_int i = 0; i < this->spoke_count_; ++i)
00152   {
00153     ACE_Timer_Node_T<TYPE>* root = this->alloc_node ();
00154     root->set (0, 0, ACE_Time_Value::zero, ACE_Time_Value::zero, root, root, 0);
00155     this->spokes_[i] = root;
00156   }
00157 
00158   ACE_NEW (iterator_, Iterator (*this));
00159 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::operator= (  const ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK > &    )  [private]
 

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::recalc_earliest (  const ACE_Time_Value &    last )  [private]
 

There are a few places where we have to figure out which timer will expire next. This method makes the assumption that spokes are always sorted, and that timers are always in the correct spoke determined from their expiration time. The last time is always passed in, even though you can often calculate it as get_first()->get_timer_value().

Definition at line 611 of file Timer_Wheel_T.cpp.

References ACE_Timer_Node_T::get_next, ACE_Timer_Node_T::get_timer_value, is_empty, and ACE_Time_Value::zero.

Referenced by cancel, and remove_first_expired. 

00612 {
00613   // This is possible because we use a count for is_empty()
00614   if (this->is_empty ())
00615     return;
00616 
00617   ACE_Time_Value et = ACE_Time_Value::zero;
00618   
00619   u_int spoke = this->earliest_spoke_;
00620 
00621   // We will have to go around the wheel at most one time.
00622   for (u_int i = 0; i < this->spoke_count_; ++i)
00623     {
00624       ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
00625       ACE_Timer_Node_T<TYPE>* n = root->get_next ();
00626       if (n != root)
00627         {
00628           ACE_Time_Value t = n->get_timer_value ();
00629           if (t < last + this->wheel_time_)
00630             {
00631               this->earliest_spoke_ = spoke;
00632               return;
00633             }
00634           else if (et == ACE_Time_Value::zero || t < et)
00635             {
00636               et = t;
00637             }
00638         }
00639       if (++spoke >= this->spoke_count_)
00640         spoke = 0;
00641     }
00642   //ACE_ERROR((LM_ERROR, "We had to search the whole wheel.\n"));
00643 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T< TYPE > * ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::remove_first (  void    )  [virtual]
 

Removes the earliest node from the queue and returns it.

Removes the earliest node and then find the new <earliest_spoke_>

Returns:
The earliest timer node.

Implements ACE_Timer_Queue_T.

Definition at line 684 of file Timer_Wheel_T.cpp.

References ACE_TRACE, ACE_Time_Value::max_time, and remove_first_expired. 

00685 {
00686   ACE_TRACE ("ACE_Timer_Wheel_T::remove_first");
00687   return remove_first_expired (ACE_Time_Value::max_time);
00688 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T< TYPE > * ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::remove_first_expired (  const ACE_Time_Value &    now )  [private]
 

Definition at line 702 of file Timer_Wheel_T.cpp.

References get_first, ACE_Timer_Node_T::get_timer_value, recalc_earliest, and unlink.

Referenced by expire, and remove_first. 

00703 {
00704   ACE_Timer_Node_T<TYPE>* n = this->get_first ();
00705   if (n != 0 && n->get_timer_value() <= now)
00706     {
00707       this->unlink (n);
00708       this->recalc_earliest (n->get_timer_value ());
00709       return n;
00710     }
00711   return 0;
00712 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::reschedule (  ACE_Timer_Node_T< TYPE > *    n )  [private, virtual]
 

Takes an ACE_Timer_Node and inserts it into the correct position in the correct list. Also makes sure to update the earliest time.

Parameters:
n  The timer node to reschedule

Implements ACE_Timer_Queue_T.

Definition at line 418 of file Timer_Wheel_T.cpp.

References ACE_TRACE, calculate_spoke, expire, ACE_Timer_Node_T::get_timer_value, and schedule_i.

Referenced by expire. 

00419 {
00420   ACE_TRACE ("ACE_Timer_Wheel_T::reschedule");
00421   const ACE_Time_Value& expire = n->get_timer_value ();
00422   u_int spoke = calculate_spoke (expire);
00423   this->schedule_i (n, spoke, expire);
00424 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::reset_interval (  long    timer_id,
const ACE_Time_Value &    interval
)  [virtual]
 

Changes the interval of a timer (and can make it periodic or non periodic by setting it to ACE_Time_Value::zero or not).

Find the timer node by using the id as a pointer. Then use set_interval() on the node to update the interval.

Parameters:
timer_id  The timer identifier
interval  The new interval
Returns:
0 if successful, -1 if no.

Implements ACE_Timer_Queue_T.

Definition at line 476 of file Timer_Wheel_T.cpp.

References ACE_GUARD_RETURN, ACE_MT, ACE_TRACE, find_node, and ACE_Timer_Node_T::set_interval. 

00479 {
00480   ACE_TRACE ("ACE_Timer_Wheel_T::reset_interval");
00481   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
00482   ACE_Timer_Node_T<TYPE>* n = this->find_node (timer_id);
00483   if (n != 0)
00484     {
00485       // The interval will take effect the next time this node is expired.
00486       n->set_interval (interval);
00487       return 0;
00488     }
00489   return -1;
00490 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
long ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::schedule (  const TYPE &    type,
const void *    act,
const ACE_Time_Value &    future_time,
const ACE_Time_Value &    interval = ACE_Time_Value::zero
)  [virtual]
 

Schedules a timer.

Creates a ACE_Timer_Node_T based on the input parameters. Then inserts the node into the wheel using reschedule (). Then returns a timer_id.

Parameters:
type  The data of the timer node
act  Asynchronous Completion Token (AKA magic cookie)
future_time  The time the timer is scheduled for (absolute time)
interval  If not ACE_Time_Value::zero, then this is a periodic timer and interval is the time period
Returns:
Unique identifier (can be used to cancel the timer). -1 on failure.

Implements ACE_Timer_Queue_T.

Definition at line 379 of file Timer_Wheel_T.cpp.

References ACE_GUARD_RETURN, ACE_MT, ACE_TRACE, ACE_Timer_Queue_T::alloc_node, calculate_spoke, generate_timer_id, schedule_i, and ACE_Timer_Node_T::set. 

00385 {
00386   ACE_TRACE ("ACE_Timer_Wheel_T::schedule");
00387   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
00388 
00389   ACE_Timer_Node_T<TYPE>* n = this->alloc_node ();
00390 
00391   if (n != 0)
00392     {
00393       u_int spoke = calculate_spoke (future_time);
00394       long id = generate_timer_id (spoke);
00395 
00396       //ACE_ERROR((LM_ERROR, "Scheduling %x spoke:%d id:%d\n", (long) n, spoke, id));
00397 
00398       if (id != -1)
00399         {
00400           n->set (type, act, future_time, interval, 0, 0, id);
00401           this->schedule_i (n, spoke, future_time);
00402         }
00403       return id;
00404     }
00405 
00406   // Failure return
00407   errno = ENOMEM;
00408   return -1;
00409 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::schedule_i (  ACE_Timer_Node_T< TYPE > *    n,
u_int    spoke,
const ACE_Time_Value &    expire
)  [private]
 

The shared scheduling functionality between schedule() and reschedule().

Definition at line 429 of file Timer_Wheel_T.cpp.

References ACE_Timer_Node_T::get_next, ACE_Timer_Node_T::get_prev, ACE_Timer_Node_T::get_timer_value, is_empty, ACE_Timer_Node_T::set_next, and ACE_Timer_Node_T::set_prev.

Referenced by reschedule, and schedule. 

00432 {
00433   // See if we need to update the earliest time
00434   if (this->is_empty() || expire < this->earliest_time ())
00435     this->earliest_spoke_ = spoke;
00436 
00437   ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
00438   ACE_Timer_Node_T<TYPE>* last = root->get_prev ();
00439 
00440   ++timer_count_;
00441 
00442   // If the spoke is empty
00443   if (last == root) {
00444     n->set_prev (root);
00445     n->set_next (root);
00446     root->set_prev (n);
00447     root->set_next (n);
00448     return;
00449   }
00450 
00451   // We always want to search backwards from the tail of the list, because
00452   // this minimizes the search in the extreme case when lots of timers are
00453   // scheduled for exactly the same time
00454   ACE_Timer_Node_T<TYPE>* p = root->get_prev ();
00455   while (p != root && p->get_timer_value () > expire)
00456     p = p->get_prev ();
00457 
00458   // insert after
00459   n->set_prev (p);
00460   n->set_next (p->get_next ());
00461   p->get_next ()->set_prev (n);
00462   p->set_next (n);
00463 }

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::unlink (  ACE_Timer_Node_T< TYPE > *    n )  [private]
 

Definition at line 691 of file Timer_Wheel_T.cpp.

References ACE_TRACE, ACE_Timer_Node_T::get_next, ACE_Timer_Node_T::get_prev, ACE_Timer_Node_T::set_next, ACE_Timer_Node_T::set_prev, and timer_count_.

Referenced by cancel_i, and remove_first_expired. 

00692 {
00693   ACE_TRACE ("ACE_Timer_Wheel_T::unlink");
00694   --timer_count_;
00695   n->get_prev ()->set_next (n->get_next ());
00696   n->get_next ()->set_prev (n->get_prev ());
00697   n->set_prev (0);
00698   n->set_next (0);
00699 }

Friends And Related Function Documentation

template<class TYPE, class FUNCTOR, class ACE_LOCK>
friend class ACE_Timer_Wheel_Iterator_T< TYPE, FUNCTOR, ACE_LOCK > [friend]
 

Iterator is a friend.

Definition at line 96 of file Timer_Wheel_T.h.

Member Data Documentation

template<class TYPE, class FUNCTOR, class ACE_LOCK>
u_int ACE_Timer_Wheel_T::earliest_spoke_ [private]
 

Index of the list with the earliest time.

Definition at line 196 of file Timer_Wheel_T.h.

Referenced by get_first_i.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
Iterator* ACE_Timer_Wheel_T::iterator_ [private]
 

Iterator used to expire timers.

Definition at line 198 of file Timer_Wheel_T.h.

Referenced by iter, and ~ACE_Timer_Wheel_T.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
u_int ACE_Timer_Wheel_T::max_per_spoke_ [private]
 

Maximum number of timers per spoke.

Definition at line 192 of file Timer_Wheel_T.h.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Wheel_T::res_bits_ [private]
 

Resolution (in microsoconds) of the timing wheel.

Definition at line 194 of file Timer_Wheel_T.h.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Wheel_T::spoke_bits_ [private]
 

Number of timer_id bits used for the spoke.

Definition at line 190 of file Timer_Wheel_T.h.

Referenced by generate_timer_id.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
u_int ACE_Timer_Wheel_T::spoke_count_ [private]
 

Size of the timing wheel.

Definition at line 188 of file Timer_Wheel_T.h.

Referenced by cancel, dump, find_node, generate_timer_id, ACE_Timer_Wheel_Iterator_T::goto_next, open_i, and ~ACE_Timer_Wheel_T.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T<TYPE>** ACE_Timer_Wheel_T::spokes_ [private]
 

Timing Wheel.

Definition at line 186 of file Timer_Wheel_T.h.

Referenced by cancel, dump, generate_timer_id, get_first_i, ACE_Timer_Wheel_Iterator_T::goto_next, ACE_Timer_Wheel_Iterator_T::next, and ~ACE_Timer_Wheel_T.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
u_int ACE_Timer_Wheel_T::timer_count_ [private]
 

The total number of timers currently scheduled.

Definition at line 202 of file Timer_Wheel_T.h.

Referenced by is_empty, and unlink.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Time_Value ACE_Timer_Wheel_T::wheel_time_ [private]
 

The total amount of time in one iteration of the wheel. (resolution * spoke_count).

Definition at line 200 of file Timer_Wheel_T.h.

The documentation for this class was generated from the following files:
Generated on Mon Jun 16 12:58:11 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002