ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK > Class Template Reference

Provides a very fast and predictable timer implementation. More...

#include <Timer_Heap_T.h>

Inheritance diagram for ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >:

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

Collaboration graph
[legend]
List of all members.

Public Types

typedef ACE_Timer_Heap_Iterator_T<
TYPE, FUNCTOR, ACE_LOCK > 
HEAP_ITERATOR
typedef ACE_Timer_Queue_T<
TYPE, FUNCTOR, ACE_LOCK > 
INHERITED

Public Member Functions

 ACE_Timer_Heap_T (size_t size, int preallocated=0, FUNCTOR *upcall_functor=0, ACE_Free_List< ACE_Timer_Node_T< TYPE > > *freelist=0)
 ACE_Timer_Heap_T (FUNCTOR *upcall_functor=0, ACE_Free_List< ACE_Timer_Node_T< TYPE > > *freelist=0)
virtual ~ACE_Timer_Heap_T (void)
 Destructor.
virtual int is_empty (void) const
 True if heap is empty, else false.
virtual const ACE_Time_Valueearliest_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 ACE_Timer_Queue_Iterator_T<
TYPE, FUNCTOR, ACE_LOCK > & 
iter (void)
 Returns a pointer to this <ACE_Timer_Queue>'s iterator.
ACE_Timer_Node_T< TYPE > * remove_first (void)
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 Member Functions

virtual long schedule_i (const TYPE &type, const void *act, const ACE_Time_Value &future_time, const ACE_Time_Value &interval)
virtual void reschedule (ACE_Timer_Node_T< TYPE > *)
 Reschedule an "interval" <ACE_Timer_Node>.
virtual ACE_Timer_Node_T<
TYPE > * 
alloc_node (void)
virtual void free_node (ACE_Timer_Node_T< TYPE > *)

Private Member Functions

ACE_Timer_Node_T< TYPE > * remove (size_t slot)
void insert (ACE_Timer_Node_T< TYPE > *new_node)
 Insert new_node into the heap and restore the heap property.
void grow_heap (void)
void reheap_up (ACE_Timer_Node_T< TYPE > *new_node, size_t slot, size_t parent)
 Restore the heap property, starting at <slot>.
void reheap_down (ACE_Timer_Node_T< TYPE > *moved_node, size_t slot, size_t child)
 Restore the heap property, starting at <slot>.
void copy (size_t slot, ACE_Timer_Node_T< TYPE > *moved_node)
int timer_id (void)
int pop_freelist (void)
 Pops and returns a new timer id from the freelist.
void push_freelist (int old_id)
 Pushes <old_id> onto the freelist.
 ACE_Timer_Heap_T (const ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK > &)
void operator= (const ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK > &)

Private Attributes

size_t max_size_
 Maximum size of the heap.
size_t cur_size_
 Current size of the heap.
size_t cur_limbo_
HEAP_ITERATORiterator_
 Iterator used to expire timers.
ACE_Timer_Node_T< TYPE > ** heap_
ssize_ttimer_ids_
size_t timer_ids_curr_
size_t timer_ids_min_free_
ACE_Timer_Node_T< TYPE > * preallocated_nodes_
ACE_Timer_Node_T< TYPE > * preallocated_nodes_freelist_
ACE_Unbounded_Set< ACE_Timer_Node_T<
TYPE > * > 
preallocated_node_set_

Friends

class ACE_Timer_Heap_Iterator_T< TYPE, FUNCTOR, ACE_LOCK >

Detailed Description

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

Provides a very fast and predictable timer implementation.

This implementation uses a heap-based callout queue of absolute times. Therefore, in the average and worst case, scheduling, canceling, and expiring timers is O(log N) (where N is the total number of timers). In addition, we can also preallocate as many ACE_Timer_Node objects as there are slots in the heap. This allows us to completely remove the need for dynamic memory allocation, which is important for real-time systems.


Member Typedef Documentation

template<class TYPE, class FUNCTOR, class ACE_LOCK>
typedef ACE_Timer_Heap_Iterator_T<TYPE, FUNCTOR, ACE_LOCK> ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::HEAP_ITERATOR
 

template<class TYPE, class FUNCTOR, class ACE_LOCK>
typedef ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK> ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::INHERITED
 


Constructor & Destructor Documentation

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::ACE_Timer_Heap_T size_t  size,
int  preallocated = 0,
FUNCTOR *  upcall_functor = 0,
ACE_Free_List< ACE_Timer_Node_T< TYPE > > *  freelist = 0
 

The Constructor creates a heap with specified number of elements. This can also take in a upcall functor and freelist (if 0, then defaults will be created).

Parameters:
size The maximum number of timers that can be inserted into the new object.
preallocated Default 0, if non-0 then all the memory for the ACE_Timer_Node objects will be pre-allocated. This saves time and is more predictable (though it requires more space). Otherwise, timer nodes are allocated as needed.
freelist is the freelist of timer nodes.
upcall_functor If 0 Timer Heap will create a default FUNCTOR.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::ACE_Timer_Heap_T FUNCTOR *  upcall_functor = 0,
ACE_Free_List< ACE_Timer_Node_T< TYPE > > *  freelist = 0
 

Default constructor. upcall_functor is the instance of the FUNCTOR to be used by the queue. If upcall_functor is 0, Timer Heap will create a default FUNCTOR. freelist is the freelist of timer nodes. If 0, then a default freelist will be created. The default size will be ACE_DEFAULT_TIMERS and there will be no preallocation.

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

Destructor.

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


Member Function Documentation

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T< TYPE > * ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::alloc_node void   )  [protected, virtual]
 

Factory method that allocates a new node (uses operator new if we're *not* preallocating, otherwise uses an internal freelist).

Reimplemented from ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::cancel long  timer_id,
const void **  act = 0,
int  dont_call_handle_close = 1
[virtual]
 

Cancel the single timer that matches the <timer_id> value (which was returned from the <schedule> method). If act is non-NULL then it will be set to point to the ``magic cookie'' argument passed in when the timer was registered. This makes it possible to free up the memory and avoid memory leaks. If <dont_call> is 0 then the <functor> will be invoked. Returns 1 if cancellation succeeded and 0 if the <timer_id> wasn't found.

Implements ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::cancel const TYPE &  type,
int  dont_call_handle_close = 1
[virtual]
 

Cancel all timers 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_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::copy size_t  slot,
ACE_Timer_Node_T< TYPE > *  moved_node
[private]
 

Copy <moved_node> into the <slot> slot of <heap_> and move <slot> into the corresponding slot in the <timer_id_> array.

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

Dump the state of an object.

Reimplemented from ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

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

Returns the time of the earliest node in the Timer_Queue. 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>
void ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::free_node ACE_Timer_Node_T< TYPE > *   )  [protected, virtual]
 

Factory method that frees a previously allocated node (uses operator delete if we're *not* preallocating, otherwise uses an internal freelist).

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_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::get_first void   )  [virtual]
 

Reads the earliest node from the queue and returns it.

Implements ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::grow_heap void   )  [private]
 

Doubles the size of the heap and the corresponding timer_ids array. If preallocation is used, will also double the size of the preallocated array of ACE_Timer_Nodes.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::insert ACE_Timer_Node_T< TYPE > *  new_node  )  [private]
 

Insert new_node into the heap and restore the heap property.

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

True if heap is empty, else false.

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_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::iter void   )  [virtual]
 

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

Implements ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

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

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::pop_freelist void   )  [private]
 

Pops and returns a new timer id from the freelist.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::push_freelist int  old_id  )  [private]
 

Pushes <old_id> onto the freelist.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::reheap_down ACE_Timer_Node_T< TYPE > *  moved_node,
size_t  slot,
size_t  child
[private]
 

Restore the heap property, starting at <slot>.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::reheap_up ACE_Timer_Node_T< TYPE > *  new_node,
size_t  slot,
size_t  parent
[private]
 

Restore the heap property, starting at <slot>.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T< TYPE > * ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::remove size_t  slot  )  [private]
 

Remove and return the <slot>th <ACE_Timer_Node> and restore the heap property.

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

Removes the earliest node from the queue and returns it. Note that the timer is removed from the heap, but is not freed, and its ID is not reclaimed. The caller is responsible for calling either reschedule() or free_node() after this function returns. Thus, this function is for support of ACE_Timer_Queue::expire and should not be used unadvisedly in other conditions.

Implements ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
void ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::reschedule ACE_Timer_Node_T< TYPE > *   )  [protected, virtual]
 

Reschedule an "interval" <ACE_Timer_Node>.

Implements ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::reset_interval long  timer_id,
const ACE_Time_Value interval
[virtual]
 

Resets the interval of the timer represented by <timer_id> to <interval>, which is specified in relative time to the current <gettimeofday>. If <interval> is equal to <ACE_Time_Value::zero>, the timer will become a non-rescheduling timer. Returns 0 if successful, -1 if not.

Implements ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
long ACE_Timer_Heap_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]
 

Schedule a timer that may optionally auto-reset. Schedule <type> that will expire at <future_time>, which is specified in absolute time. If it expires then <act> is passed in as the value to the <functor>. If <interval> is != to <ACE_Time_Value::zero> then it is used to reschedule the <type> automatically, using relative time to the current <gettimeofday>. This method returns a <timer_id> that uniquely identifies the the <type> entry in an internal list. This <timer_id> can be used to cancel the timer before it expires. The cancellation ensures that <timer_ids> are unique up to values of greater than 2 billion timers. As long as timers don't stay around longer than this there should be no problems with accidentally deleting the wrong timer. Returns -1 on failure (which is guaranteed never to be a valid <timer_id>).

Implements ACE_Timer_Queue_T< TYPE, FUNCTOR, ACE_LOCK >.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
int ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::timer_id void   )  [private]
 

Returns a timer id that uniquely identifies this timer. This id can be used to cancel a timer via the <cancel (int)> method. The timer id returned from this method will never == -1 to avoid conflicts with other failure return values.


Friends And Related Function Documentation

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


Member Data Documentation

template<class TYPE, class FUNCTOR, class ACE_LOCK>
size_t ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::cur_limbo_ [private]
 

Number of heap entries in transition (removed from the queue, but not freed) and may be rescheduled or freed.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
size_t ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::cur_size_ [private]
 

Current size of the heap.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T<TYPE>** ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::heap_ [private]
 

Current contents of the Heap, which is organized as a "heap" of <ACE_Timer_Node> *'s. In this context, a heap is a "partially ordered, almost complete" binary tree, which is stored in an array.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
HEAP_ITERATOR* ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::iterator_ [private]
 

Iterator used to expire timers.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
size_t ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::max_size_ [private]
 

Maximum size of the heap.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Unbounded_Set<ACE_Timer_Node_T<TYPE> *> ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::preallocated_node_set_ [private]
 

Set of pointers to the arrays of preallocated timer nodes. Used to delete the allocated memory when required.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T<TYPE>* ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::preallocated_nodes_ [private]
 

If this is non-0, then we preallocate <max_size_> number of <ACE_Timer_Node> objects in order to reduce dynamic allocation costs. In auto-growing implementation, this points to the last array of nodes allocated.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ACE_Timer_Node_T<TYPE>* ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::preallocated_nodes_freelist_ [private]
 

This points to the head of the <preallocated_nodes_> freelist, which is organized as a stack.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
ssize_t* ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::timer_ids_ [private]
 

An array of "pointers" that allows each <ACE_Timer_Node> in the <heap_> to be located in O(1) time. Basically, <timer_id_[i]> contains the slot in the <heap_> array where an <ACE_Timer_Node> * with timer id <i> resides. Thus, the timer id passed back from <schedule> is really a slot into the <timer_ids> array. The <timer_ids_> array serves two purposes: negative values are indications of free timer IDs, whereas positive values are "pointers" into the <heap_> array for assigned timer IDs.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
size_t ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::timer_ids_curr_ [private]
 

"Pointer" to the element in the <timer_ids_> array that was last given out as a timer ID.

template<class TYPE, class FUNCTOR, class ACE_LOCK>
size_t ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::timer_ids_min_free_ [private]
 

Index representing the lowest timer ID that has been freed. When the timer_ids_next_ value wraps around, it starts back at this point.


The documentation for this class was generated from the following files:
Generated on Wed Nov 23 15:50:59 2005 for ACE by  doxygen 1.4.5