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 >:

Collaboration diagram for ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK >:

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 Member Functions
	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 bool	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 &current_time)
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 Member Functions
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 Member Functions
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)

Definition at line 92 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< TYPE, FUNCTOR, ACE_LOCK >::Base

Type inherited from.

Definition at line 101 of file Timer_Wheel_T.h.

template<class TYPE, class FUNCTOR, class ACE_LOCK>

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

Definition at line 102 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< TYPE, FUNCTOR, ACE_LOCK >::Iterator

Type of iterator.

Definition at line 96 of file Timer_Wheel_T.h.

template<class TYPE, class FUNCTOR, class ACE_LOCK>

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

Definition at line 99 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 46 of file Timer_Wheel_T.cpp.

: Base (upcall_functor, freelist)
, spokes_(0)
, spoke_count_(0) // calculated in open_i
, spoke_bits_(0)
, res_bits_ (0)
, earliest_spoke_ (0)
, iterator_(0)
, timer_count_(0)
{
  ACE_TRACE ("ACE_Timer_Wheel_T::ACE_Timer_Wheel_T");
  this->open_i (0,
                ACE_DEFAULT_TIMER_WHEEL_SIZE,
                ACE_DEFAULT_TIMER_WHEEL_RESOLUTION);
}

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 76 of file Timer_Wheel_T.cpp.

: Base (upcall_functor, freelist)
, spokes_ (0)
, spoke_count_ (0) // calculated in open_i
, spoke_bits_ (0)
, res_bits_ (0)
, earliest_spoke_ (0)
, iterator_ (0)
, timer_count_ (0)
{
  ACE_TRACE ("ACE_Timer_Wheel_T::ACE_Timer_Wheel_T");
  this->open_i (prealloc, spoke_count, resolution);
}

template<class TYPE , class FUNCTOR , class ACE_LOCK >

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

Destructor.

Destructor just cleans up its memory.

Definition at line 168 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::~ACE_Timer_Wheel_T");

  delete iterator_;

  for (u_int i = 0; i < this->spoke_count_; ++i)
  {
    // Free all the nodes starting at the root
    ACE_Timer_Node_T<TYPE>* root = this->spokes_[i];
    for (ACE_Timer_Node_T<TYPE>* n = root->get_next (); n != root;)
    {
      ACE_Timer_Node_T<TYPE>* next = n->get_next ();
      this->upcall_functor ().deletion (*this,
                                        n->get_type (),
                                        n->get_act ());
      this->free_node (n);
      n = next;
    }
    delete root;
  }
  delete[] this->spokes_;
}

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.

Definition at line 273 of file Timer_Wheel_T.cpp.

{
  return static_cast<u_int> ((t.msec () >> this->res_bits_) & (this->spoke_count_ - 1));
}

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

Definition at line 510 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::cancel");

  int num_canceled = 0; // Note : Technically this can overflow.
  int cookie = 0;

  ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));

  if (!this->is_empty ())
    {
      ACE_Timer_Node_T<TYPE>* first = this->get_first ();
      ACE_Time_Value last = first->get_timer_value ();
      int recalc = 0;

      for (u_int i = 0; i < this->spoke_count_; ++i)
        {
          ACE_Timer_Node_T<TYPE>* root = this->spokes_[i];
          for (ACE_Timer_Node_T<TYPE>* n = root->get_next (); n != root; )
            {
              if (n->get_type () == type)
                {
                  ++num_canceled;
                  if (n == first)
                    recalc = 1;

                  ACE_Timer_Node_T<TYPE>* tmp = n;
                  n = n->get_next ();

                  this->cancel_i (tmp);
                }
              else
                {
                  n = n->get_next ();
                }
            }
        }

      if (recalc)
        this->recalc_earliest (last);
    }

  // Call the close hooks.

  // cancel_type() called once per <type>.
  this->upcall_functor ().cancel_type (*this,
                                       type,
                                       skip_close,
                                       cookie);

  for (int i = 0;
       i < num_canceled;
       ++i)
    {
      // cancel_timer() called once per <timer>.
      this->upcall_functor ().cancel_timer (*this,
                                            type,
                                            skip_close,
                                            cookie);
    }

  return num_canceled;
}

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

Definition at line 593 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::cancel");
  ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
  ACE_Timer_Node_T<TYPE>* n = this->find_node (timer_id);
  if (n != 0)
    {
      ACE_Time_Value last = n->get_timer_value ();

      int recalc = (this->get_first_i () == n);

      // Call the close hooks.
      int cookie = 0;

      // cancel_type() called once per <type>.
      this->upcall_functor ().cancel_type (*this,
                                           n->get_type (),
                                           skip_close,
                                           cookie);

      // cancel_timer() called once per <timer>.
      this->upcall_functor ().cancel_timer (*this,
                                            n->get_type (),
                                            skip_close,
                                            cookie);
      if (act != 0)
        *act = n->get_act ();

      this->cancel_i (n);

      if (recalc)
        this->recalc_earliest (last);

      return 1;
    }
  return 0;
}

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.

Definition at line 635 of file Timer_Wheel_T.cpp.

{
  this->unlink (n);
  this->free_node (n);
}

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

Definition at line 691 of file Timer_Wheel_T.cpp.

{
#if defined (ACE_HAS_DUMP)
  ACE_TRACE ("ACE_Timer_Wheel_T::dump");
  ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));

  ACE_DEBUG ((LM_DEBUG,
    ACE_TEXT ("\nspoke_count_ = %d"), this->spoke_count_));
  ACE_DEBUG ((LM_DEBUG,
    ACE_TEXT ("\nresolution_ = %d"), 1 << this->res_bits_));
  ACE_DEBUG ((LM_DEBUG,
    ACE_TEXT ("\nwheel_ =\n")));

  for (u_int i = 0; i < this->spoke_count_; ++i)
    {
      ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("%d\n"), i));
      ACE_Timer_Node_T<TYPE>* root = this->spokes_[i];
      for (ACE_Timer_Node_T<TYPE>* n = root->get_next ();
           n != root;
           n = n->get_next ())
        {
          n->dump ();
        }
    }

  ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
#endif /* ACE_HAS_DUMP */
}

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

Definition at line 259 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::earliest_time");
  ACE_Timer_Node_T<TYPE>* n = this->get_first_i ();
  if (n != 0)
    return n->get_timer_value ();
  return ACE_Time_Value::zero;
}

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

Definition at line 798 of file Timer_Wheel_T.cpp.

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

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

Definition at line 812 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::expire");

  int expcount = 0;

  ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));

  ACE_Timer_Node_T<TYPE>* n = this->remove_first_expired (cur_time);

  while (n != 0)
    {
      ++expcount;

      //ACE_ERROR((LM_ERROR, "Expiring %x\n", (long) n));

      ACE_Timer_Node_Dispatch_Info_T<TYPE> info;

      // Get the dispatch info
      n->get_dispatch_info (info);

      if (n->get_interval () > ACE_Time_Value::zero)
        {
          // Make sure that we skip past values that have already
          // "expired".
          this->recompute_next_abs_interval_time (n, cur_time);

          this->reschedule (n);
        }
      else
        {
          this->free_node (n);
        }

      const void *upcall_act = 0;

      this->preinvoke (info, cur_time, upcall_act);

      this->upcall (info, cur_time);

      this->postinvoke (info, cur_time, upcall_act);

      n = this->remove_first_expired (cur_time);
    }

  return expcount;
}

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 213 of file Timer_Wheel_T.cpp.

{
  if (timer_id == -1)
    return 0;

  // Search the spoke where timer_id was originally scheduled
  u_int spoke_mask = this->spoke_count_ - 1;
  u_int start = timer_id & spoke_mask;
  ACE_Timer_Node_T<TYPE>* n = this->find_spoke_node (start, timer_id);
  if (n != 0)
    return n;

  //ACE_ERROR((LM_ERROR, "Node not found in original spoke.\n"));

  // Search the rest of the spokes
  for (u_int i = 0; i < this->spoke_count_; ++i)
    {
      if (i != start)
        { // already searched this one
          n = this->find_spoke_node (i, timer_id);
          if (n != 0)
            return n;
        }
    }

  //ACE_ERROR((LM_ERROR, "Node not found.\n"));
  return 0;
}

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 196 of file Timer_Wheel_T.cpp.

{
  ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
  for (ACE_Timer_Node_T<TYPE>* n = root->get_next ();
       n != root;
       n = n->get_next ())
    {
      if (n->get_timer_id () == timer_id)
        return n;
    }
  return 0;
}

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 284 of file Timer_Wheel_T.cpp.

{

  int cnt_bits = sizeof (long) * 8 - this->spoke_bits_;
  long max_cnt = ((long)1 << cnt_bits) - 1;
  if (spoke == this->spoke_count_)
    --max_cnt; // Because -1 is used as a special invalid timer_id.

  ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];

  if (root == root->get_next ())
    root->set_act(0);

  // We use this field to keep track of the next counter value that
  // may be in use. Of course it may have expired, so we just use
  // this field so that we know when we don't have to check for duplicates
#if defined (ACE_WIN64)
  // The cast below is legit... we know that long is shorter than a
  // pointer, but are only using it as a 'long' storage area.
#  pragma warning(push)
#  pragma warning(disable : 4311)
#endif /* ACE_WIN64 */
  long next_cnt = reinterpret_cast<long> (root->get_act ());
#if defined (ACE_WIN64)
#  pragma warning(pop)
#endif /* ACE_WIN64 */

  // This field is used as a counter instead of a timer_id.
  long cnt = root->get_timer_id ();

  if (cnt >= max_cnt && root == root->get_next ())
    {
      // Special case when we overflow on an empty spoke. We can just
      // wrap the count around without searching for duplicates. We only
      // want to do this when the counter overflows, so that we return
      // unique timer_id values as often as possible.
      root->set_timer_id (1);
      return spoke;
    }
  else if (cnt >= max_cnt)
    { // overflow
      cnt = 0; // try again starting at zero
    }
  else if (next_cnt == 0 || cnt < next_cnt)
    {
      root->set_timer_id (cnt + 1);
      return (cnt << this->spoke_bits_) | spoke;
    }

  //ACE_ERROR((LM_ERROR, "Timer id overflow. We have to search now.\n"));

  // We've run out of consecutive id numbers so now we have to search
  // for a unique id.
  // We'll try increasing numbers until we find one that is not in use,
  // and we'll record the next highest number so that we can avoid this
  // search as often as possible.
  for (; cnt < max_cnt - 1; ++cnt)
    {
      long id = (cnt << this->spoke_bits_) | spoke;
      ACE_Timer_Node_T<TYPE>* n = this->find_spoke_node (spoke, id);
      if (n == 0)
        {
          root->set_timer_id (cnt + 1);
          // Now we need to find the next highest cnt in use
          next_cnt = 0;
          for (; n != root; n = n->get_next ())
            {
              long tmp = n->get_timer_id () >> this->spoke_bits_;
              if (tmp > cnt && (tmp < next_cnt || next_cnt == 0))
                next_cnt = tmp;
            }
#if defined (ACE_WIN64)
          // The cast below is legit... we know we're storing a long in
          // a pointer, but are only using it as a 'long' storage area.
#  pragma warning(push)
#  pragma warning(disable : 4312)
#endif /* ACE_WIN64 */
          root->set_act (reinterpret_cast<void*> (next_cnt));
#if defined (ACE_WIN64)
#  pragma warning(pop)
#endif /* ACE_WIN64 */
          return id;
        }
    }

  return -1; // We did our best, but the spoke is full.
}

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

Definition at line 764 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::get_first");
  return this->get_first_i ();
}

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 772 of file Timer_Wheel_T.cpp.

{
  ACE_Timer_Node_T<TYPE>* root = this->spokes_[this->earliest_spoke_];
  ACE_Timer_Node_T<TYPE>* first = root->get_next ();
  if (first != root)
    return first;
  return 0;
}

template<class TYPE , class FUNCTOR , class ACE_LOCK >

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

Definition at line 248 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::is_empty");
  return timer_count_ == 0;
}

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

Definition at line 787 of file Timer_Wheel_T.cpp.

{
  this->iterator_->first ();
  return *this->iterator_;
}

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 132 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::open_i");

  this->gettimeofday (ACE_OS::gettimeofday);

  // Rather than waste bits in our timer id, we might as well round up
  // the spoke count to the next power of two - 1 . (i.e 1,3,7,15,...127,etc.)
  const int MIN_SPOKE_BITS = 3;  // Allow between 8 and 4096 spokes
  const int MAX_SPOKE_BITS = 12;
  const int MAX_RES_BITS = 20;   // 20 is plenty, even on 64 bit platforms.

  this->spoke_bits_ = power2bits (spokes, MIN_SPOKE_BITS, MAX_SPOKE_BITS);
  this->res_bits_ = power2bits (res, 1, MAX_RES_BITS);

  this->spoke_count_ = 1 << this->spoke_bits_;

  this->free_list_->resize (prealloc + this->spoke_count_);

  this->wheel_time_.msec (1 << (this->res_bits_));

  ACE_NEW (this->spokes_, ACE_Timer_Node_T<TYPE>* [this->spoke_count_]);

  // Create the root nodes. These will be treated specially
  for (u_int i = 0; i < this->spoke_count_; ++i)
  {
    ACE_Timer_Node_T<TYPE>* root = this->alloc_node ();
    root->set (0, 0, ACE_Time_Value::zero, ACE_Time_Value::zero, root, root, 0);
    this->spokes_[i] = root;
  }

  ACE_NEW (iterator_, Iterator (*this));
}

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]`

Definition at line 95 of file Timer_Wheel_T.cpp.

{
  int max = (1 << max_bits) - 1;
  if (n > max)
    return max_bits;

  // count the bits in n.
  int i = 0;
  int tmp = n;
  do
    {
      tmp >>= 1;
      ++i;
    }
  while (tmp != 0);

  if (i <= min_bits)
    return min_bits;

  // Which is nearest?
  int a = (1 << i) - n;
  int b = (1 << (i - 1)) - n;
  if (b < 0)
    b = -b;
  if (b < a)
    return i - 1;
  return i;
}

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 649 of file Timer_Wheel_T.cpp.

{
  // This is possible because we use a count for is_empty()
  if (this->is_empty ())
    return;

  ACE_Time_Value et = ACE_Time_Value::zero;
  u_int es = 0;
  u_int spoke = this->earliest_spoke_;

  // We will have to go around the wheel at most one time.
  for (u_int i = 0; i < this->spoke_count_; ++i)
    {
      ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
      ACE_Timer_Node_T<TYPE>* n = root->get_next ();
      if (n != root)
        {
          ACE_Time_Value t = n->get_timer_value ();
          if (t < last + this->wheel_time_)
            {
              this->earliest_spoke_ = spoke;
              return;
            }
          else if (et == ACE_Time_Value::zero || t < et)
            {
              et = t;
              es = spoke;
            }
        }
      if (++spoke >= this->spoke_count_)
        spoke = 0;
    }

  this->earliest_spoke_ = es;
  //ACE_ERROR((LM_ERROR, "We had to search the whole wheel.\n"));
}

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

Definition at line 727 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::remove_first");
  return remove_first_expired (ACE_Time_Value::max_time);
}

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 745 of file Timer_Wheel_T.cpp.

{
  ACE_Timer_Node_T<TYPE>* n = this->get_first ();
  if (n != 0 && n->get_timer_value() <= now)
    {
      this->unlink (n);
      this->recalc_earliest (n->get_timer_value ());
      return n;
    }
  return 0;
}

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

Definition at line 422 of file Timer_Wheel_T.cpp.

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

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

Definition at line 480 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::reset_interval");
  ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
  ACE_Timer_Node_T<TYPE>* n = this->find_node (timer_id);
  if (n != 0)
    {
      // The interval will take effect the next time this node is expired.
      n->set_interval (interval);
      return 0;
    }
  return -1;
}

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

Definition at line 386 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::schedule_i");

  ACE_Timer_Node_T<TYPE>* n = this->alloc_node ();

  if (n != 0)
    {
      u_int spoke = calculate_spoke (future_time);
      long id = generate_timer_id (spoke);

      //ACE_ERROR((LM_ERROR, "Scheduling %x spoke:%d id:%d\n", (long) n, spoke, id));

      if (id != -1)
        {
          n->set (type, act, future_time, interval, 0, 0, id);
          this->schedule_i (n, spoke, future_time);
        }
      return id;
    }

  // Failure return
  errno = ENOMEM;
  return -1;
}

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 433 of file Timer_Wheel_T.cpp.

{
  // See if we need to update the earliest time
  if (this->is_empty() || expire < this->earliest_time ())
    this->earliest_spoke_ = spoke;

  ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
  ACE_Timer_Node_T<TYPE>* last = root->get_prev ();

  ++timer_count_;

  // If the spoke is empty
  if (last == root) {
    n->set_prev (root);
    n->set_next (root);
    root->set_prev (n);
    root->set_next (n);
    return;
  }

  // We always want to search backwards from the tail of the list, because
  // this minimizes the search in the extreme case when lots of timers are
  // scheduled for exactly the same time
  ACE_Timer_Node_T<TYPE>* p = root->get_prev ();
  while (p != root && p->get_timer_value () > expire)
    p = p->get_prev ();

  // insert after
  n->set_prev (p);
  n->set_next (p->get_next ());
  p->get_next ()->set_prev (n);
  p->set_next (n);
}

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 734 of file Timer_Wheel_T.cpp.

{
  ACE_TRACE ("ACE_Timer_Wheel_T::unlink");
  --timer_count_;
  n->get_prev ()->set_next (n->get_next ());
  n->get_next ()->set_prev (n->get_prev ());
  n->set_prev (0);
  n->set_next (0);
}

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 98 of file Timer_Wheel_T.h.

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.

Definition at line 201 of file Timer_Wheel_T.h.

template<class TYPE, class FUNCTOR, class ACE_LOCK>

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

Iterator used to expire timers.

Definition at line 203 of file Timer_Wheel_T.h.

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.

Definition at line 197 of file Timer_Wheel_T.h.

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.

Definition at line 199 of file Timer_Wheel_T.h.

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.

Definition at line 195 of file Timer_Wheel_T.h.

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.

Definition at line 193 of file Timer_Wheel_T.h.

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.

Definition at line 191 of file Timer_Wheel_T.h.

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.

Definition at line 207 of file Timer_Wheel_T.h.

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

Definition at line 205 of file Timer_Wheel_T.h.

The documentation for this class was generated from the following files:

ACE_Timer_Wheel_T< TYPE, FUNCTOR, ACE_LOCK > Class Template Reference

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Friends

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

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