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

ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK > 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< TYPE, FUNCTOR, ACE_LOCK >:

Inheritance graph
[legend]
Collaboration diagram for ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >:

Collaboration graph
[legend]
List of all members.

Public Types

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

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

typedef ACE_Free_List< Node > FreeList

Public Methods

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

 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.

virtual ~ACE_Timer_Wheel_T (void)
 Destructor.

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

virtual const ACE_Time_Value & earliest_time (void) const
virtual int reset_interval (long timer_id, const ACE_Time_Value &interval)
virtual int cancel (const TYPE &type, int dont_call_handle_close=1)
virtual int cancel (long timer_id, const void **act=0, int dont_call_handle_close=1)
virtual int expire (void)
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.

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

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

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


Protected Methods

virtual long schedule_i (const TYPE &type, const void *act, const ACE_Time_Value &future_time, const ACE_Time_Value &interval)
 Schedules a timer.


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.

ACE_Timer_Node_T< TYPE > * find_node (long timer_id) const
u_int calculate_spoke (const ACE_Time_Value &expire) const
long generate_timer_id (u_int spoke)
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().

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

void unlink (ACE_Timer_Node_T< TYPE > *n)
void recalc_earliest (const ACE_Time_Value &last)
int power2bits (int n, int min_bits, int max_bits)
 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.

u_int spoke_count_
 Size of the timing wheel.

int spoke_bits_
 Number of timer_id bits used for the spoke.

u_int max_per_spoke_
 Maximum number of timers per spoke.

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

u_int earliest_spoke_
 Index of the list with the earliest time.

Iterator * iterator_
 Iterator used to expire timers.

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

u_int timer_count_
 The total number of timers currently scheduled.


Friends

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

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)

Member Typedef Documentation

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

Type inherited from.

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

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

Type of iterator.

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

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

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

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

Destructor.

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 &    t )  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.

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< TYPE, FUNCTOR, ACE_LOCK >.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::cancel (  const TYPE &    type,
int    dont_call_handle_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.

Implements ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

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 )  [private]
 

Shared subset of the two cancel() methods.

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< TYPE, FUNCTOR, ACE_LOCK >.

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.

Implements ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

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< TYPE, FUNCTOR, ACE_LOCK >.

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.

Reimplemented from ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

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.

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.

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.

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< TYPE, FUNCTOR, ACE_LOCK >.

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]
 

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< TYPE, FUNCTOR, ACE_LOCK >.

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< TYPE, FUNCTOR, ACE_LOCK >.

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.

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>
int ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::power2bits (  int    n,
int    min_bits,
int    max_bits
)  [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().

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< TYPE, FUNCTOR, ACE_LOCK >.

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]
 

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< TYPE, FUNCTOR, ACE_LOCK >.

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).

Implements ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

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().

template<class TYPE, class FUNCTOR, class ACE_LOCK>
long ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >::schedule_i (  const TYPE &    type,
const void *    act,
const ACE_Time_Value &    future_time,
const ACE_Time_Value &    interval
)  [protected, 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< TYPE, FUNCTOR, ACE_LOCK >.

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]
 

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.

Member Data Documentation

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

Index of the list with the earliest time.

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

Iterator used to expire timers.

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

Maximum number of timers per spoke.

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

Resolution (in microsoconds) of the timing wheel.

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

Number of timer_id bits used for the spoke.

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

Size of the timing wheel.

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

Timing Wheel.

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

The total number of timers currently scheduled.

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

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

The documentation for this class was generated from the following files:
Generated on Wed Jan 14 22:49:10 2004 for ACE by doxygen1.2.18