Mon Aug 26 18:21:34 UTC 2002 Justin Michel <michel_j@ociweb.com>

5 files changed, 1020 insertions, 953 deletions

diff --git a/ChangeLog b/ChangeLog
index 9778b95dbcc..b075f78dbda 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+Mon Aug 26 18:21:34 UTC 2002  Justin Michel  <michel_j@ociweb.com>
+        
+        * ace/Timer_Wheel_T.cpp:
+        * ace/Timer_Wheel_T.h:
+        * tests/Timer_Queue_Test.cpp:
+
+          New and improved timer wheel implementation. 
+
 Mon Aug 26 09:51:12 UTC 2002  Johnny Willemsen  <jwillemsen@remedy.nl>
 
         * ace/FlReactor.{h,cpp}:
diff --git a/ChangeLogs/ChangeLog-03a b/ChangeLogs/ChangeLog-03a
index 9778b95dbcc..b075f78dbda 100644
--- a/ChangeLogs/ChangeLog-03a
+++ b/ChangeLogs/ChangeLog-03a
@@ -1,3 +1,11 @@
+Mon Aug 26 18:21:34 UTC 2002  Justin Michel  <michel_j@ociweb.com>
+        
+        * ace/Timer_Wheel_T.cpp:
+        * ace/Timer_Wheel_T.h:
+        * tests/Timer_Queue_Test.cpp:
+
+          New and improved timer wheel implementation. 
+
 Mon Aug 26 09:51:12 UTC 2002  Johnny Willemsen  <jwillemsen@remedy.nl>
 
         * ace/FlReactor.{h,cpp}:
diff --git a/ace/Timer_Wheel_T.cpp b/ace/Timer_Wheel_T.cpp
index 3c775185464..68df0a95d39 100644
--- a/ace/Timer_Wheel_T.cpp
+++ b/ace/Timer_Wheel_T.cpp
@@ -3,476 +3,539 @@
 #ifndef ACE_TIMER_WHEEL_T_C
 #define ACE_TIMER_WHEEL_T_C
 
-#include "ace/Timer_Wheel_T.h"
-
 #if !defined (ACE_LACKS_PRAGMA_ONCE)
 # pragma once
 #endif /* ACE_LACKS_PRAGMA_ONCE */
 
-#include "ace/High_Res_Timer.h"
+#include "ace/Timer_Wheel_T.h"
 #include "ace/Log_Msg.h"
 
 ACE_RCSID(ace, Timer_Wheel_T, "$Id$")
 
+
+// Design/implementation notes for ACE_Timer_Wheel_T.
+//
+// Each timer queue entry is represented by a ACE_Timer_Node.
+// The timing wheel is divided into a number of "spokes"; there are
+// spoke_count_ spokes in the wheel. Each timer is hashed into one of the
+// spokes. Entries within each spoke are linked in a double-linked list
+// in order of increasing expiration. The first ACE_Timer_Node in each
+// spoke is a "dummy node" that marks the end of the list of ACE_Timer_Nodes
+// in that spoke.
+//
+// The timer ID for a scheduled timer is formed by its spoke position in
+// the wheel, and the number of timers that have been inserted in that spoke
+// since the queue was initialized. N bits of the long timer_id are used
+// to determine the spoke, and M bits are used as a counter.
+// Each time a Node is inserted into a spoke, it's counter
+// is incremented. The count is kept in the timer ID field
+// of the dummy root Node. In the event of overflow of the counter, the spoke
+// must be searched for each new id to make sure it's not already in use. To
+// prevent having to do an exhaustive search each time, we keep extra data
+// in the dummy root Node. 
 /**
- * Just initializes the iterator with a ACE_Timer_Wheel_T and then calls
- * first() to initialize the rest of itself.
- *
- * @param wheel A reference for a timer queue to iterate over
- */
+* Default Constructor that sets defaults for spoke_count_ and resolution_
+* and doesn't do any preallocation.
+*
+* @param upcall_functor A pointer to a functor to use instead of the default
+* @param freelist       A pointer to a freelist to use instead of the default
+*/
 template <class TYPE, class FUNCTOR, class ACE_LOCK>
-ACE_Timer_Wheel_Iterator_T<TYPE,
-                           FUNCTOR,
-                           ACE_LOCK>::ACE_Timer_Wheel_Iterator_T (
-  ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK> &wheel
-  )
-  : timer_wheel_ (wheel)
+ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::ACE_Timer_Wheel_T 
+(FUNCTOR* upcall_functor
+ , FreeList* freelist
+ )
+: 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)
 {
-  this->first();
+  ACE_TRACE ("ACE_Timer_Wheel_T::ACE_Timer_Wheel_T");
+  this->open_i(0, ACE_DEFAULT_TIMER_WHEEL_SIZE, ACE_DEFAULT_TIMER_WHEEL_RESOLUTION);
 }
 
-
 /**
- * Destructor, at this level does nothing.
- */
+* Constructor that sets up the timing wheel and also may preallocate
+* some nodes on the free list
+*
+* @param wheelsize      The number of lists in the timer wheel
+* @param resolution     The time resolution in milliseconds used by the hashing function
+* @param prealloc       The number of entries to prealloc in the free_list
+* @param upcall_functor A pointer to a functor to use instead of the default
+* @param freelist       A pointer to a freelist to use instead of the default
+*/
 template <class TYPE, class FUNCTOR, class ACE_LOCK>
-ACE_Timer_Wheel_Iterator_T<TYPE,
-                           FUNCTOR,
-                           ACE_LOCK>::~ACE_Timer_Wheel_Iterator_T (void)
+ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::ACE_Timer_Wheel_T 
+( u_int spoke_count, 
+ u_int resolution, 
+ size_t prealloc, 
+ FUNCTOR* upcall_functor, 
+ FreeList* freelist
+ )
+: 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);
 }
 
-
-/**
- * Positions the iterator at the first position in the timing wheel
- * that contains something. pos_ will be set to the position of this entry
- * and list_item_ will point to the first entry in that position.  Since
- * this is an iterator,
- *
- * If the wheel is empty, pos_ will be equal timer_wheel_.wheel_size_ and
- * list_item_ would be 0.
- */
-template <class TYPE, class FUNCTOR, class ACE_LOCK> void
-ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::first (void)
-{
-  for (this->pos_ = 0;
-       this->pos_ < this->timer_wheel_.wheel_size_;
-       this->pos_++)
-    {
-      // Skip over empty entries
-      if (this->timer_wheel_.wheel_[this->pos_]->get_next ()
-          != this->timer_wheel_.wheel_[this->pos_])
-        {
-          this->list_item_ =
-            this->timer_wheel_.wheel_[this->pos_]->get_next ();
-          return;
-        }
+namespace {
+  int power2bits(int n, int min_bits, int max_bits) {
+    int max = (1 << max_bits) - 1;
+    if (n > max) {
+      return max_bits;
     }
-
-  // The queue is empty if we are here
-  this->list_item_ = 0;
-}
-
-
-/**
- * Positions the iterator at the next node in list or goes to the next
- * list
- */
-template <class TYPE, class FUNCTOR, class ACE_LOCK> void
-ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::next (void)
-{
-  if (this->isdone ())
-    return;
-
-  this->list_item_ =
-    this->list_item_->get_next ();
-
-  // If there is no more in the current list, go to the next
-  if (this->list_item_ == this->timer_wheel_.wheel_[this->pos_])
-    {
-      for (this->pos_++;
-           this->pos_ < this->timer_wheel_.wheel_size_;
-           this->pos_++)
-        {
-          // Check for an empty entry
-          if (this->timer_wheel_.wheel_[this->pos_]->get_next ()
-              != this->timer_wheel_.wheel_[this->pos_])
-            {
-              this->list_item_ =
-                this->timer_wheel_.wheel_[this->pos_]->get_next ();
-              return;
-            }
-        }
-
-      this->list_item_ = 0;
+    // 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;
+  }
 }
 
-
 /**
- * @return True when we there isn't anymore items (when list_item_ == 0)
- */
-template <class TYPE, class FUNCTOR, class ACE_LOCK> int
-ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::isdone (void) const
-{
-  return this->list_item_ == 0;
-}
-
-
-/**
- * @return The node at the current position in the sequence or 0 if the wheel
- *         is empty
- */
-template <class TYPE, class FUNCTOR, class ACE_LOCK> ACE_Timer_Node_T<TYPE> *
-ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::item (void)
+* 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>::open_i (size_t prealloc, u_int spokes, u_int res)
 {
-  if (this->isdone ())
-    return 0;
+  ACE_TRACE ("ACE_Timer_Wheel_T::open_i");
+  
+  this->gettimeofday (ACE_OS::gettimeofday);
 
-  return this->list_item_;
+  // 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_ + this->spoke_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));
 }
 
-
-/**
- * Constructor that sets up the timing wheel and also may preallocate
- * some nodes on the free list
- *
- * @param wheelsize      The number of lists in the timer wheel
- * @param resolution     The time resolution used by the hashing function
- * @param prealloc       The number of entries to prealloc in the free_list
- * @param upcall_functor A pointer to a functor to use instead of the default
- * @param freelist       A pointer to a freelist to use instead of the default
- */
+/// Destructor just cleans up its memory
 template <class TYPE, class FUNCTOR, class ACE_LOCK>
-ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::ACE_Timer_Wheel_T (
-  size_t wheelsize,
-  size_t resolution,
-  size_t prealloc,
-  FUNCTOR *upcall_functor,
-  ACE_Free_List<ACE_Timer_Node_T <TYPE> > *freelist
-  )
-  : ACE_Timer_Queue_T<TYPE,FUNCTOR,ACE_LOCK> (upcall_functor, freelist),
-    wheel_size_ (wheelsize),
-    resolution_ (resolution),
-    earliest_pos_ (0)
+ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::~ACE_Timer_Wheel_T (void)
 {
-  ACE_TRACE ("ACE_Timer_Wheel_T::ACE_Timer_Wheel_T");
-  size_t i;
-
-  this->gettimeofday (ACE_OS::gettimeofday);
-
-  // Create the timing wheel
-  ACE_NEW (this->wheel_,
-           ACE_Timer_Node_T<TYPE> *[wheelsize]);
-
-  // Create the dummy nodes
-  for (i = 0; i < wheelsize; i++)
+  ACE_TRACE ("ACE_Timer_spokes_T::~ACE_Timer_spokes_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>* a = root->get_next(); a != root;)
     {
-      ACE_Timer_Node_T<TYPE> *tempnode =
-        this->alloc_node ();
-      tempnode->set_next (tempnode);
-      tempnode->set_prev (tempnode);
-      this->wheel_[i] = tempnode;
+      ACE_Timer_Node_T<TYPE>* b = a->get_next();
+      this->upcall_functor().deletion(*this, a->get_type(), a->get_act());
+      a->set_prev(0);
+      a->set_next(0);
+      this->free_node (a);
+      a = b->get_next();
     }
-
-  // Do the preallocation
-  this->free_list_->resize (prealloc);
-
-  ACE_NEW (iterator_,
-           WHEEL_ITERATOR (*this));
+    delete root;
+  }
+  delete[] this->spokes_;
 }
 
-
-/**
- * Default Constructor that sets defaults for wheel_size_ and resolution_
- * and doesn't do any preallocation.
- *
- * @param upcall_functor A pointer to a functor to use instead of the default
- * @param 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 (
-  FUNCTOR *upcall_functor,
-  ACE_Free_List<ACE_Timer_Node_T <TYPE> > *freelist
-  )
-  : ACE_Timer_Queue_T<TYPE,FUNCTOR,ACE_LOCK> (upcall_functor, freelist),
-    wheel_size_ (ACE_DEFAULT_TIMER_WHEEL_SIZE),
-    resolution_ (ACE_DEFAULT_TIMER_WHEEL_RESOLUTION),
-    earliest_pos_ (0)
+/// Searches for a node by timer_id within one spoke.
+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
 {
-  ACE_TRACE ("ACE_Timer_Wheel_T::ACE_Timer_Wheel_T");
-  size_t i;
-
-  this->gettimeofday (ACE_OS::gettimeofday);
-
-  // Create the timing wheel
-  ACE_NEW (this->wheel_,
-           ACE_Timer_Node_T<TYPE> *[this->wheel_size_]);
-
-  // Create the dummy nodes
-  for (i = 0;
-       i < this->wheel_size_;
-       i++)
-    {
-      ACE_Timer_Node_T<TYPE> *tempnode = this->alloc_node ();
-      tempnode->set_next (tempnode);
-      tempnode->set_prev (tempnode);
-      this->wheel_[i] = tempnode;
+  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;
     }
-
-  ACE_NEW (iterator_,
-           WHEEL_ITERATOR (*this));
+  }
+  return 0;
 }
 
-// Destructor just cleans up its memory
-
-template <class TYPE, class FUNCTOR, class ACE_LOCK>
-ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::~ACE_Timer_Wheel_T (void)
+/// 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_node(long timer_id) const
 {
-  ACE_TRACE ("ACE_Timer_Wheel_T::~ACE_Timer_Wheel_T");
-
-  delete iterator_;
-
-  for (size_t i = 0;
-       i < this->wheel_size_;
-       i++)
-    {
-      // delete nodes until only the dummy node is left
-      while (this->wheel_[i]->get_next () != this->wheel_[i])
-        {
-          ACE_Timer_Node_T<TYPE> *next =
-            this->wheel_[i]->get_next ();
-          this->wheel_[i]->set_next (next->get_next ());
-          next->get_next ()->set_prev (this->wheel_[i]);
-          this->upcall_functor ().deletion (*this,
-                                            next->get_type (),
-                                            next->get_act ());
-          this->free_node (next);
-        }
-
-      // and now delete the dummy node
-      delete this->wheel_[i];
+  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;
+      }
     }
+  }
 
-  // finally delete the wheel
-  delete [] this->wheel_;
+  //ACE_ERROR((LM_ERROR, "Node not found.\n"));
+  return 0;
 }
 
-
 /**
- * Checks to see if <earliest_pos> points to a empty list (then it is empty).
- *
- * @return True if empty
- */
+* Check to see if the wheel is empty
+*
+* @return True if empty
+*/
 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::is_empty (void) const
 {
   ACE_TRACE ("ACE_Timer_Wheel_T::is_empty");
-
-  return this->wheel_[this->earliest_pos_]->get_next ()
-         == this->wheel_[this->earliest_pos_];
+  return timer_count_ == 0;
 }
 
 
 /**
- * @return First (earliest) node in the wheel_'s earliest_pos_ list
- */
+* @return First (earliest) node in the wheel_'s earliest_spoke_ list
+*/
 template <class TYPE, class FUNCTOR, class ACE_LOCK> const ACE_Time_Value &
 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::earliest_time (void) const
 {
   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;
+}
+
+/// 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> u_int
+ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::calculate_spoke(const ACE_Time_Value& t) const
+{
+  return ACE_static_cast(u_int, (t.msec() >> this->res_bits_) & (this->spoke_count_ - 1));
+}
+
+/// 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> long
+ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::generate_timer_id(u_int spoke) {
+
+  int cnt_bits = sizeof(long) * 8 - this->spoke_bits_;
+  int max_cnt = (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
+  long next_cnt = ACE_reinterpret_cast(long, root->get_act());
+  // 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()) {
+        int tmp = n->get_timer_id() >> this->spoke_bits_;
+        if (tmp > cnt && (tmp < next_cnt || next_cnt == 0)) {
+          next_cnt = tmp;
+        }
+      }
+      root->set_act(ACE_reinterpret_cast(void*, next_cnt));
+      return id;
+    }
+  }
 
-  return this->wheel_[this->earliest_pos_]->get_next ()->get_timer_value ();
+  return -1; // We did our best, but the spoke is full. 
 }
 
 /**
- * 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
- * (which is actually a pointer to the actual timer_node).
- *
- *  @param type            The data of the timer node
- *  @param act             Asynchronous Completion Token (AKA magic cookie)
- *  @param future_time     The time the timer is scheduled for (in absolute time)
- *  @param interval        If not ACE_Time_Value::zero, then this is a periodic
- *                         timer and interval is the time period
- *
- *  @return Unique identifier (can be used to cancel the timer).
- *          -1 on failure.
- */
+* 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.
+*
+*  @param type            The data of the timer node
+*  @param act             Asynchronous Completion Token (AKA magic cookie)
+*  @param future_time     The time the timer is scheduled for (absolute time)
+*  @param interval        If not ACE_Time_Value::zero, then this is a periodic
+*                         timer and interval is the time period
+*
+*  @return Unique identifier (can be used to cancel the timer).
+*          -1 on failure.
+*/
 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
-  )
+                                                      const TYPE& type,
+                                                      const void* act,
+                                                      const ACE_Time_Value& future_time,
+                                                      const ACE_Time_Value& interval
+                                                      )
 {
   ACE_TRACE ("ACE_Timer_Wheel_T::schedule");
   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
-
-  ACE_Timer_Node_T<TYPE> *tempnode = this->alloc_node ();
-
-  if (tempnode)
-    {
-      // Note that the timer_id is actually the pointer to the node
-
-      // Set the details of the node
-      tempnode->set (type,
-                     act,
-                     future_time,
-                     interval,
-                     0,
-                     0,
-                     (long) tempnode);
-
-      // Reschedule will insert it into the correct position
-      this->reschedule (tempnode);
-
-      return tempnode->get_timer_id ();
+  
+  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;
 }
 
+/**
+* Takes an ACE_Timer_Node and inserts it into the correct spokeition in
+* the correct list.  Also makes sure to update the earliest time.
+*
+* @param expired The timer node to reschedule
+*/
+template <class TYPE, class FUNCTOR, class ACE_LOCK> void
+ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::reschedule (ACE_Timer_Node_T<TYPE>* n)
+{
+  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);
+}
+
+/// The shared scheduling functionality between schedule() and reschedule()
+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)
+{
+  // 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;
+  }
+  // Note : It might be beneficial in the real world to check to see
+  // if the new timer belongs on the end of the spoke, but in testing
+  // it made no difference, so we just skip it. 
+
+  // We use <= here so that the timers with equal values will 
+  // be scheduled in the right order
+  ACE_Timer_Node_T<TYPE>* next = root->get_next();
+  while (next != root && next->get_timer_value() <= expire)
+    next = next->get_next();
+  
+  // insert before
+  n->set_prev(next->get_prev());
+  n->set_next(next);
+  next->get_prev()->set_next(n);
+  next->set_prev(n);
+}
+
 
 /**
- * Find the timer node by using the id as a pointer.  Then use set_interval()
- * on the node to update the interval.
- *
- * @param timer_id The timer identifier
- * @param interval The new interval
- *
- * @return 0 if successful, -1 if no.
- */
+* Find the timer node by using the id as a pointer.  Then use set_interval()
+* on the node to update the interval.
+*
+* @param timer_id The timer identifier
+* @param interval The new interval
+*
+* @return 0 if successful, -1 if no.
+*/
 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
-  )
+                                                            long timer_id,
+                                                            const ACE_Time_Value &interval
+                                                            )
 {
   ACE_TRACE ("ACE_Timer_Wheel_T::reset_interval");
   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
-
-  // Make sure we are getting a valid <timer_id>, not an error
-  // returned by <schedule>.
-  if (timer_id == -1)
-    return -1;
-
-  ACE_Timer_Node_T<TYPE> *node =
-    ACE_reinterpret_cast (ACE_Timer_Node_T<TYPE> *,
-                          timer_id);
-
-  // Check to see if the node looks like a true
-  // ACE_Timer_Node_T<TYPE>.
-  if (timer_id != node->get_timer_id ())
-    return -1;
-
-  node->set_interval (interval);
-  return 0;
+  ACE_Timer_Node_T<TYPE>* n = this->find_node(timer_id);
+  if (n != 0) {
+    n->set_interval(interval); // The interval will take effect the next time this node is expired.
+    return 0;
+  }
+  return -1;
 }
 
 
 /**
- * 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.
- *
- * @param type       The value to search for.
- * @param skip_close If this non-zero, the cancellation method of the
- *                   functor will not be called for each cancelled timer.
- *
- * @return 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.
+*
+* @param type       The value to search for.
+* @param skip_close If this non-zero, the cancellation method of the
+*                   functor will not be called for each cancelled timer.
+*
+* @return Number of timers cancelled
+*/
 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
-ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::cancel (const TYPE &type,
-                                                    int skip_close)
+ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::cancel (const TYPE& type, int skip_close)
 {
   ACE_TRACE ("ACE_Timer_Wheel_T::cancel");
   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
 
-  int number_of_cancellations = 0;
-  size_t i;
+  int num_canceled = 0; // Note : Technically this can overflow.
 
-  // Walk through the wheel
-  for (i = 0;
-       i < this->wheel_size_;
-       i++)
+  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)
     {
-
-      // Walk through the list.
-      for (ACE_Timer_Node_T<TYPE> *curr =
-             this->wheel_[i]->get_next ();
-           curr != this->wheel_[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) // Note: Typically Type is an ACE_Event_Handler*
         {
-          if (curr->get_type () == type)
-            {
-              // Cancel it and remove it.
-              number_of_cancellations++;
-
-              // Detach it from the list
-              ACE_Timer_Node_T<TYPE> *tempnode = curr;
-              curr->get_prev ()->set_next (curr->get_next ());
-              curr->get_next ()->set_prev (curr->get_prev ());
-
-              // Go on to the next and delete the detached node
-              curr = curr->get_next ();
-              this->free_node (tempnode);
-            }
-          else
-            curr = curr->get_next ();
+          ++num_canceled;
+          
+          if (n == first) {
+            recalc = 1;
+          }
+          
+          ACE_Timer_Node_T<TYPE>* tmp = n;
+          n = n->get_next();
+          int always_skip_close = 1; // todo : Is this correct?
+          this->cancel_i(tmp, always_skip_close);
         }
-    }
-
-  //  Look for a new earliest time
-
-  // Defaults to zero.
-  ACE_Time_Value earliest_time;
-
-  // Check every entry in the table
-  for (i = 0; i < this->wheel_size_; i++)
-    {
-      // Skip empty entries
-      if (this->wheel_[i]->get_next () != this->wheel_[i])
+        else
         {
-          // if initialization or if the time is earlier
-          if (earliest_time == ACE_Time_Value::zero
-              || this->wheel_[i]->get_timer_value () < earliest_time)
-            {
-              earliest_time =
-                this->wheel_[i]->get_next ()->get_timer_value ();
-              this->earliest_pos_ = i;
-            }
+          n = n->get_next();
         }
+      }
     }
-
-  if (skip_close == 0)
-    this->upcall_functor ().cancellation (*this,
-                                          type);
-  return number_of_cancellations;
+    
+    if (recalc)
+      this->recalc_earliest(last);
+  }
+
+  if (! skip_close) { //  && num_canceled > 0) {
+    this->upcall_functor().cancellation (*this, type);
+  }
+  return num_canceled;
 }
 
 
 /**
- * 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.
- *
- * @param timer_id   Timer Identifier
- * @param act        Asychronous Completion Token (AKA magic cookie):
- *                   If this is non-zero, stores the magic cookie of
- *                   the cancelled timer here.
- * @param skip_close If this non-zero, the cancellation method of the
- *                   functor will not be called.
- *
- * @return 1 for sucess and 0 if the timer_id wasn't found (or was
- *         found to be invalid)
- */
+* 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.
+*
+* @param timer_id   Timer Identifier
+* @param act        Asychronous Completion Token (AKA magic cookie):
+*                   If this is non-zero, stores the magic cookie of
+*                   the cancelled timer here.
+* @param skip_close If this non-zero, the cancellation method of the
+*                   functor will not be called.
+*
+* @return 1 for sucess and 0 if the timer_id wasn't found (or was
+*         found to be invalid)
+*/
 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::cancel (long timer_id,
                                                     const void **act,
@@ -480,205 +543,175 @@ ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::cancel (long timer_id,
 {
   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);
+    if (act != 0)
+      *act = n->get_act();
+    this->cancel_i(n, skip_close);
+    if (recalc)
+      this->recalc_earliest(last);
+    return 1;
+  }
+  return 0;
+}
 
-  // Make sure we are getting a valid <timer_id>, not an error
-  // returned by <schedule>.
-  if (timer_id == -1)
-    return 0;
-
-  ACE_Timer_Node_T<TYPE> *node =
-    ACE_reinterpret_cast (ACE_Timer_Node_T<TYPE> *,
-                          timer_id);
-
-  // Check to see if the node looks like a true ACE_Timer_Node_T<TYPE>.
-  if (timer_id == node->get_timer_id ())
-    {
-      node->get_next ()->set_prev (node->get_prev ());
-      node->get_prev ()->set_next (node->get_next ());
-
-      if (act != 0)
-        *act = node->get_act ();
-
-      if (skip_close == 0)
-        this->upcall_functor ().cancellation (*this,
-                                              node->get_type ());
-
-      // Find out what position it is in.
-      size_t pos = (node->get_timer_value ().usec () / this->resolution_)
-                   % this->wheel_size_;
-
-      this->free_node (node);
+/// Shared subset of the two cancel() methods. 
+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)
+{
+  //ACE_ERROR((LM_ERROR, "Canceling %x\n", (long) n));
+  this->unlink(n);
+  this->free_node (n);
+  if (! skip_close) {
+    this->upcall_functor().cancellation (*this, n->get_type());
+  }
+}
 
-      // Get the new earliest time if we have to
+/// 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> void
+ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::recalc_earliest(const ACE_Time_Value& last)
+{
+  if (this->is_empty()) // This is possible because we use a count for is_empty()
+    return;
 
-      if (pos == this->earliest_pos_)
-        {
-          ACE_Time_Value earliest_time; // defaults to zero
-
-          // Check every entry in the table
-          for (size_t i = 0; i < this->wheel_size_; i++)
-            {
-              // Skip empty entries
-              if (this->wheel_[i]->get_next () != this->wheel_[i])
-                {
-                  // if initialization or if the time is earlier
-                  if (earliest_time == ACE_Time_Value::zero
-                      || this->wheel_[i]->get_timer_value () < earliest_time)
-                    {
-                      earliest_time =
-                        this->wheel_[i]->get_next ()->get_timer_value ();
-                      this->earliest_pos_ = i;
-                    }
-                }
-            }
-        }
+  ACE_Time_Value et = ACE_Time_Value::zero;
+  
+  u_int spoke = this->earliest_spoke_;
 
-      return 1;
+  // 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;
+      }
     }
-
-  // Didn't find it if we are here
-  return 0;
+    if (++spoke >= this->spoke_count_) {
+      spoke = 0;
+    }
+  }
+  //ACE_ERROR((LM_ERROR, "We had to search the whole wheel.\n"));
 }
 
-
 /**
- * Dumps out the size of the wheel, the resolution, and the contents
- * of the wheel.
- */
+* Dumps out the size of the wheel, the resolution, and the contents
+* of the wheel.
+*/
 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::dump (void) const
 {
   ACE_TRACE ("ACE_Timer_Wheel_T::dump");
   ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
-
+  
   ACE_DEBUG ((LM_DEBUG,
-             ACE_LIB_TEXT ("\nwheel_size_ = %d"), this->wheel_size_));
+    ACE_LIB_TEXT ("\nspoke_count_ = %d"), this->spoke_count_));
   ACE_DEBUG ((LM_DEBUG,
-             ACE_LIB_TEXT ("\nresolution_ = %d"), this->resolution_));
+    ACE_LIB_TEXT ("\nresolution_ = %d"), 1 << this->res_bits_));
   ACE_DEBUG ((LM_DEBUG,
-             ACE_LIB_TEXT ("\nwheel_ = \n")));
-
-  for (size_t i = 0; i < this->wheel_size_; i++)
+    ACE_LIB_TEXT ("\nwheel_ = \n")));
+  
+  for (u_int i = 0; i < this->spoke_count_; ++i)
+  {
+    ACE_DEBUG ((LM_DEBUG, ACE_LIB_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())
     {
-      ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("%d\n"), i));
-      ACE_Timer_Node_T<TYPE> *temp = this->wheel_[i]->get_next ();
-      while (temp != this->wheel_[i])
-        {
-          temp->dump ();
-          temp = temp->get_next ();
-        }
+      n->dump ();
     }
-
+  }
+  
   ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
 }
 
 
 /**
- * Removes the earliest node and then find the new <earliest_pos_>
- *
- * @return The earliest timer node.
- */
+* Removes the earliest node and then find the new <earliest_spoke_>
+*
+* @return The earliest timer node.
+*/
 template <class TYPE, class FUNCTOR, class ACE_LOCK> ACE_Timer_Node_T<TYPE> *
 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::remove_first (void)
 {
   ACE_TRACE ("ACE_Timer_Wheel_T::remove_first");
+  return remove_first_expired(ACE_Time_Value::max_time);
+}
 
-  // Remove the item
-  ACE_Timer_Node_T<TYPE> *temp =
-    this->wheel_[this->earliest_pos_]->get_next ();
-  temp->get_prev ()->set_next (temp->get_next ());
-  temp->get_next ()->set_prev (temp->get_prev ());
-
-  ACE_Time_Value earliest_time;
-
-  // Check every entry in the table for the new earliest item
-  for (size_t i = 0;
-       i < this->wheel_size_;
-       i++)
-    {
-      // Check for an empty entry
-      if (this->wheel_[i]->get_next () != this->wheel_[i])
-        {
-          // if initialization or if the time is earlier
-          if (earliest_time == ACE_Time_Value::zero
-              || this->wheel_[i]->get_timer_value () < earliest_time)
-            {
-              earliest_time =
-                this->wheel_[i]->get_next ()->get_timer_value ();
-              this->earliest_pos_ = i;
-            }
-        }
-    }
-
-  return temp;
+template <class TYPE, class FUNCTOR, class ACE_LOCK> void
+ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::unlink (ACE_Timer_Node_T<TYPE>* n)
+{
+  --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);
 }
 
+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)
+{
+  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;
+}
 
 /**
- * Returns the earliest node without removing it
- *
- * @return The earliest timer node.
- */
-template <class TYPE, class FUNCTOR, class ACE_LOCK> ACE_Timer_Node_T<TYPE> *
+* Returns the earliest node without removing it
+*
+* @return The earliest timer node.
+*/
+template <class TYPE, class FUNCTOR, class ACE_LOCK> 
+ACE_Timer_Node_T<TYPE>*
 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::get_first (void)
 {
   ACE_TRACE ("ACE_Timer_Wheel_T::get_first");
-
-  return this->wheel_[this->earliest_pos_]->get_next ();
+  return this->get_first_i();
 }
 
-/**
- * Takes an ACE_Timer_Node and inserts it into the correct position in
- * the correct list.  Also makes sure to update the earliest time.
- *
- * @param expired The timer node to reschedule
- */
-template <class TYPE, class FUNCTOR, class ACE_LOCK> void
-ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::reschedule (
-  ACE_Timer_Node_T<TYPE> *expired
-  )
+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
 {
-  ACE_TRACE ("ACE_Timer_Wheel_T::reschedule");
-
-  size_t pos = (expired->get_timer_value ().usec () / this->resolution_)
-               % this->wheel_size_;
-
-  // See if we need to update the earliest time
-  if (this->is_empty ()
-      || expired->get_timer_value () < this->earliest_time ())
-    this->earliest_pos_ = pos;
-
-  // Insert time into dummy node.
-  this->wheel_[pos]->set_timer_value (expired->get_timer_value ());
-  ACE_Timer_Node_T<TYPE> *cursor =
-    this->wheel_[pos]->get_next ();
-
-  // Find position to insert
-  while (cursor->get_timer_value () < expired->get_timer_value ())
-    cursor = cursor->get_next ();
-
-  // Insert
-  expired->set_prev (cursor->get_prev ());
-  expired->set_next (cursor);
-  cursor->set_prev (expired);
-  expired->get_prev ()->set_next (expired);
+  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;
 }
 
+
 /**
- * @return The iterator
- */
-template <class TYPE, class FUNCTOR, class ACE_LOCK>
-ACE_Timer_Queue_Iterator_T<TYPE, FUNCTOR, ACE_LOCK> &
+* @return The iterator
+*/
+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)
 {
-  this->iterator_->first ();
+  this->iterator_->first();
   return *this->iterator_;
 }
 
 /**
- * Dummy version of expire to get rid of warnings in Sun CC 4.2
- * Just call the expire of the base class.
- */
+* Dummy version of expire to get rid of warnings in Sun CC 4.2
+* Just call the expire of the base class.
+*/
 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::expire ()
 {
@@ -686,135 +719,149 @@ ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::expire ()
 }
 
 /**
- * This is a specialized version of expire that is more suited for the
- * internal data representation.  Notice that we are still expiring
- * timers in order, even though this can be really speeded up if we
- * didn't worry about this.
- *
- * @param cur_time The time to expire timers up to.
- *
- * @return Number of timers expired
- */
+* This is a specialized version of expire that is more suited for the
+* internal data representation. 
+*
+* @param cur_time The time to expire timers up to.
+*
+* @return Number of timers expired
+*/
 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
-ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::expire (
-  const ACE_Time_Value &cur_time
-  )
+ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::expire (const ACE_Time_Value& cur_time)
 {
   ACE_TRACE ("ACE_Timer_Wheel_T::expire");
   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
 
-  int number_of_timers_expired = 0;
-  size_t i;
+  int expcount = 0;
+  ACE_Timer_Node_T<TYPE>* n = this->remove_first_expired(cur_time);
 
-  size_t earliest_pos = this->wheel_size_;
-  ACE_Time_Value earliest_time = cur_time;
+  while (n != 0) {
+    ++ expcount;
 
-  size_t next_earliest_pos = this->wheel_size_;
-  ACE_Time_Value next_earliest_time;
+    //ACE_ERROR((LM_ERROR, "Expiring %x\n", (long) n));
 
-  // Find the earliest time and location
-  for (i = 0; i < this->wheel_size_; i++)
-    {
-      if (this->wheel_[i]->get_next () != this->wheel_[i]
-          && this->wheel_[i]->get_next ()->get_timer_value ()
-             <= earliest_time)
-        {
-          earliest_pos = i;
-          earliest_time = this->wheel_[i]->get_next ()->get_timer_value ();
-        }
+    this->upcall (n->get_type(), n->get_act(), cur_time);
+
+    if (n->get_interval() > ACE_Time_Value::zero) {
+      n->set_timer_value(cur_time + n->get_interval());
+      this->reschedule(n);
+    } else {
+      this->free_node(n);
     }
 
-  // Check to see if the timer queue is empty
-  if (earliest_pos == this->wheel_size_)
-    return 0;
+    n = this->remove_first_expired(cur_time);
+  }
 
-  do
-    {
-      next_earliest_time = cur_time;
-      next_earliest_pos = this->wheel_size_;
+  //ACE_ERROR((LM_ERROR, "Expired %d nodes\n", expcount));
 
-      // Find the next earliest position and time.
-      for (i = 0; i < this->wheel_size_; i++)
-        {
-          if (i != earliest_pos
-              && this->wheel_[i]->get_next () != this->wheel_[i]
-              && this->wheel_[i]->get_next ()->get_timer_value ()
-                 <= next_earliest_time)
-            {
-              next_earliest_pos = i;
-              next_earliest_time =
-                this->wheel_[i]->get_next ()->get_timer_value ();
-            }
-        }
+  return expcount;
+}
 
-      // Keep expiring timers until we need to move to the next list
-      while (this->wheel_[earliest_pos]->get_next ()
-               != this->wheel_[earliest_pos]
-             && this->wheel_[earliest_pos]->get_next ()->get_timer_value ()
-                <= next_earliest_time)
-        {
-          // Remove the first node in the earliest position
-          ACE_Timer_Node_T<TYPE> *expired =
-            this->wheel_[earliest_pos]->get_next ();
-          this->wheel_[earliest_pos]->set_next (expired->get_next ());
-          expired->get_next ()->set_prev (this->wheel_[earliest_pos]);
-
-          TYPE &type = expired->get_type ();
-          const void *act = expired->get_act ();
-          int reclaim = 1;
-
-          // Check if this is an interval timer.
-          if (expired->get_interval () > ACE_Time_Value::zero)
-            {
-              // Make sure that we skip past values that have already
-              // "expired".
-              do
-                expired->set_timer_value (expired->get_timer_value ()
-                  + expired->get_interval ());
-              while (expired->get_timer_value () <= cur_time);
-
-              // Since this is an interval timer, we need to
-              // reschedule it.
-              this->reschedule (expired);
-              reclaim = 0;
-            }
-
-          // Call the functor.
-          this->upcall (type, act, cur_time);
-
-          if (reclaim)
-            // Free up the node and the token.
-            this->free_node (expired);
-
-          ++number_of_timers_expired;
-        }
+///////////////////////////////////////////////////////////////////////////
+// ACE_Timer_Wheel_Iterator_T
+ 
+/**
+* Just initializes the iterator with a ACE_Timer_Wheel_T and then calls
+* first() to initialize the rest of itself.
+*
+* @param wheel A reference for a timer queue to iterate over
+*/
+template <class TYPE, class FUNCTOR, class ACE_LOCK>
+ACE_Timer_Wheel_Iterator_T<TYPE,FUNCTOR,ACE_LOCK>::ACE_Timer_Wheel_Iterator_T 
+(Wheel& wheel)
+: timer_wheel_ (wheel)
+{
+  this->first();
+}
 
-      earliest_pos = next_earliest_pos;
-    }
-  while (earliest_pos != this->wheel_size_);
 
-  //  Look for a new earliest time
+/**
+* Destructor, at this level does nothing.
+*/
+template <class TYPE, class FUNCTOR, class ACE_LOCK>
+ACE_Timer_Wheel_Iterator_T<TYPE,
+FUNCTOR,
+ACE_LOCK>::~ACE_Timer_Wheel_Iterator_T (void)
+{
+}
+
+
+/**
+* spokeitions the iterator at the first spokeition in the timing wheel
+* that contains something. spoke_ will be set to the spokeition of this entry
+* and current_node_ will point to the first entry in that spokeition.  Since
+* this is an iterator,
+*
+* If the wheel is empty, spoke_ will be equal timer_wheel_.spoke_count_ and
+* current_node_ would be 0.
+*/
+template <class TYPE, class FUNCTOR, class ACE_LOCK> void
+ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::first (void)
+{
+  this->goto_next(0);
+}
+
 
-  earliest_time = ACE_Time_Value::zero;
+/**
+* spokeitions the iterator at the next node.
+*/
+template <class TYPE, class FUNCTOR, class ACE_LOCK> void
+ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::next (void)
+{
+  if (this->isdone())
+    return;
+
+  ACE_Timer_Node_T<TYPE>* n = this->current_node_->get_next();
+  ACE_Timer_Node_T<TYPE>* root = this->timer_wheel_.spokes_[this->spoke_];
+  if (n == root) {
+    this->goto_next(this->spoke_ + 1);
+  } else {
+    this->current_node_ = n;
+  }
+}
 
-  // Check every entry in the table
-  for (i = 0; i < this->wheel_size_; i++)
+/// Helper class for common functionality of next() and first()
+template <class TYPE, class FUNCTOR, class ACE_LOCK> void
+ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::goto_next(u_int start_spoke)
+{
+  // Find the first non-empty entry.
+  u_int sc = this->timer_wheel_.spoke_count_;
+  for (u_int i = start_spoke; i < sc; ++i)
+  {
+    ACE_Timer_Node_T<TYPE>* root = this->timer_wheel_.spokes_[i];
+    ACE_Timer_Node_T<TYPE>* n = root->get_next();
+    if (n != root)
     {
-      // Skip empty entries
-      if (this->wheel_[i]->get_next () != this->wheel_[i])
-        {
-          // if initialization or if the time is earlier
-          if (earliest_time == ACE_Time_Value::zero
-              || this->wheel_[i]->get_timer_value () < earliest_time)
-            {
-              earliest_time =
-                this->wheel_[i]->get_next ()->get_timer_value ();
-              this->earliest_pos_ = i;
-            }
-        }
+      this->spoke_ = i;
+      this->current_node_ = n;
+      return;
     }
+  }
+  // empty
+  this->spoke_ = sc;
+  this->current_node_ = 0;
+}
+
+
+/**
+* @return True when we there isn't anymore items (when current_node_ == 0)
+*/
+template <class TYPE, class FUNCTOR, class ACE_LOCK> int
+ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::isdone (void) const
+{
+  return this->current_node_ == 0;
+}
+
 
-  return number_of_timers_expired;
+/**
+* @return The node at the current spokeition in the sequence or 0 if the wheel
+*         is empty
+*/
+template <class TYPE, class FUNCTOR, class ACE_LOCK> ACE_Timer_Node_T<TYPE> *
+ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::item (void)
+{
+  return this->current_node_;
 }
 
+
 #endif /* ACE_TIMER_WHEEL_T_C */
diff --git a/ace/Timer_Wheel_T.h b/ace/Timer_Wheel_T.h
index 7086c29a58d..05d50248e93 100644
--- a/ace/Timer_Wheel_T.h
+++ b/ace/Timer_Wheel_T.h
@@ -30,7 +30,7 @@ class ACE_Timer_Wheel_T;
  * @brief Iterates over an <ACE_Timer_Wheel>.
  *
  * This is a generic iterator that can be used to visit every
- * node of a timer queue.  Be aware that it doesn't transverse
+ * node of a timer queue.  Be aware that it doesn't traverse
  * in the order of timeout values.
  */
 template <class TYPE, class FUNCTOR, class ACE_LOCK>
@@ -38,8 +38,11 @@ class ACE_Timer_Wheel_Iterator_T
   : public ACE_Timer_Queue_Iterator_T <TYPE, FUNCTOR, ACE_LOCK>
 {
 public:
+  typedef ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK> Wheel;
+  typedef ACE_Timer_Node_T<TYPE> Node;
+
   /// Constructor
-  ACE_Timer_Wheel_Iterator_T (ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK> &);
+  ACE_Timer_Wheel_Iterator_T (Wheel &);
 
   /// Destructor
   ~ACE_Timer_Wheel_Iterator_T (void);
@@ -54,30 +57,31 @@ public:
   virtual int isdone (void) const;
 
   /// Returns the node at the current position in the sequence
-  virtual ACE_Timer_Node_T<TYPE> *item (void);
+  virtual ACE_Timer_Node_T<TYPE>* item (void);
 
 protected:
   /// Pointer to the <ACE_Timer_List> that we are iterating over.
-  ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK> &timer_wheel_;
+  Wheel& timer_wheel_;
 
   /// Current position in the timing wheel
-  size_t pos_;
+  u_int spoke_;
 
   /// Pointer to the position in the the <pos_>th list
-  ACE_Timer_Node_T<TYPE> *list_item_;
+  ACE_Timer_Node_T<TYPE>* current_node_;
+private:
+  void goto_next(u_int start_spoke);
 };
 
 /**
  * @class ACE_Timer_Wheel_T
  *
- * @brief Provides a Timing Wheel version of Timer Queue.
+ * @brief 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 to the
- * <ACE_Timer_List> include using the pointer to the node as the
- * timer id (to speed up removing), 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
+ * linked lists of absolute times.  The enhancements over the
+ * @c 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)
@@ -87,24 +91,23 @@ class ACE_Timer_Wheel_T : public ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK>
 {
 public:
   /// Type of iterator
-  typedef ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK> WHEEL_ITERATOR;
-
+  typedef ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK> Iterator;
   /// Iterator is a friend
   friend class ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>;
-
+  typedef ACE_Timer_Node_T<TYPE> Node;
   /// Type inherited from
-  typedef ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK> INHERITED;
+  typedef ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK> Base;
+  typedef ACE_Free_List<Node> FreeList;
 
   /// Default constructor
-  ACE_Timer_Wheel_T (FUNCTOR *upcall_functor = 0,
-                     ACE_Free_List<ACE_Timer_Node_T <TYPE> > *freelist = 0);
+  ACE_Timer_Wheel_T (FUNCTOR* upcall_functor = 0, FreeList* freelist = 0);
 
   /// Constructor with opportunities to set the wheelsize and resolution
-  ACE_Timer_Wheel_T (size_t wheelsize,
-                     size_t resolution,
+  ACE_Timer_Wheel_T (u_int spoke_count,
+                     u_int resolution,
                      size_t prealloc = 0,
-                     FUNCTOR *upcall_functor = 0,
-                     ACE_Free_List<ACE_Timer_Node_T <TYPE> > *freelist = 0);
+                     FUNCTOR* upcall_functor = 0,
+                     FreeList* freelist = 0);
 
   /// Destructor
   virtual ~ACE_Timer_Wheel_T (void);
@@ -114,31 +117,31 @@ public:
 
   /// Returns the time of the earlier node in the <ACE_Timer_Wheel>.
   /// Must be called on a non-empty queue.
-  virtual const ACE_Time_Value &earliest_time (void) const;
+  virtual const ACE_Time_Value& earliest_time (void) const;
 
   /// Schedules a timer.
-  virtual long schedule (const TYPE &type,
-                         const void *act,
-                         const ACE_Time_Value &future_time,
-                         const ACE_Time_Value &interval
+  virtual long schedule (const TYPE& type,
+                         const void* act,
+                         const ACE_Time_Value& future_time,
+                         const ACE_Time_Value& interval
                            = ACE_Time_Value::zero);
 
   /// Changes the interval of a timer (and can make it periodic or non
   /// periodic by setting it to ACE_Time_Value::zero or not).
   virtual int reset_interval (long timer_id,
-                              const ACE_Time_Value &interval);
+                              const ACE_Time_Value& interval);
 
   /// Cancel all timer associated with <type>.  If <dont_call> is 0
   /// then the <functor> will be invoked.  Returns number of timers
   /// cancelled.
-  virtual int cancel (const TYPE &type,
+  virtual int cancel (const TYPE& type,
                       int dont_call_handle_close = 1);
 
   // Cancel a timer, storing the magic cookie in act (if nonzero).
   // Calls the functor if dont_call_handle_close is 0 and returns 1
   // on success
   virtual int cancel (long timer_id,
-                      const void **act = 0,
+                      const void** act = 0,
                       int dont_call_handle_close = 1);
 
   /// Run the <functor> for all timers whose values are <=
@@ -149,44 +152,54 @@ public:
   // Run the <functor> for all timers whose values are <= <cur_time>.
   // This does not account for <timer_skew>.  Returns the number of
   // timers canceled.
-  int expire (const ACE_Time_Value &);
+  int expire (const ACE_Time_Value&);
 
   /// Returns a pointer to this <ACE_Timer_Queue_T>'s iterator.
-  virtual ACE_Timer_Queue_Iterator_T<TYPE, FUNCTOR, ACE_LOCK> &iter (void);
+  virtual ACE_Timer_Queue_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>& iter (void);
 
   /// Removes the earliest node from the queue and returns it
-  virtual ACE_Timer_Node_T<TYPE> *remove_first (void);
+  virtual ACE_Timer_Node_T<TYPE>* remove_first (void);
 
   /// Dump the state of an object.
   virtual void dump (void) const;
 
   /// Reads the earliest node from the queue and returns it.
-  virtual ACE_Timer_Node_T<TYPE> *get_first (void);
-
+  virtual ACE_Timer_Node_T<TYPE>* get_first (void);
+  
 private:
-  /// Reschedule an "interval" node
+  // The following are documented in the .cpp file.
+  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;
+  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);
+  void cancel_i (ACE_Timer_Node_T<TYPE>* n, int skip_close);
+  void unlink (ACE_Timer_Node_T<TYPE>* n);
+  void recalc_earliest(const ACE_Time_Value& last);
 
+private:
   /// Timing Wheel.
-  ACE_Timer_Node_T<TYPE> **wheel_;
-
+  ACE_Timer_Node_T<TYPE>** spokes_;
   /// Size of the timing wheel.
-  size_t wheel_size_;
-
+  u_int spoke_count_;
+  /// Number of timer_id bits used for the spoke
+  int spoke_bits_;
+  /// Maximum number of timers per spoke
+  u_int max_per_spoke_;
   /// Resolution (in microsoconds) of the timing wheel.
-  size_t resolution_;
-
+  int res_bits_;
   /// Index of the list with the earliest time
-  size_t earliest_pos_;
-
-  /// Keeps track of the size of the queue
-  long size_;
-
+  u_int earliest_spoke_;
   /// Iterator used to expire timers.
-  WHEEL_ITERATOR *iterator_;
-
-  /// Pointer to the freelist of <ACE_Timer_Node_T<TYPE>>.
-  ACE_Timer_Node_T<TYPE> *freelist_;
+  Iterator* iterator_;
+  /// The total amount of time in one iteration of the wheel. (resolution * spoke_count)
+  ACE_Time_Value wheel_time_;
+  /// The total number of timers currently scheduled.
+  u_int timer_count_;
 
   // = Don't allow these operations for now.
   ACE_UNIMPLEMENTED_FUNC (
diff --git a/tests/Timer_Queue_Test.cpp b/tests/Timer_Queue_Test.cpp
index 5af87db2dea..dc95ef85b33 100644
--- a/tests/Timer_Queue_Test.cpp
+++ b/tests/Timer_Queue_Test.cpp
@@ -34,22 +34,19 @@
 
 ACE_RCSID(tests, Timer_Queue_Test, "$Id$")
 
-template <class T> void
-randomize_array (T array[], size_t size)
-{
-  size_t i;
-
-  // Randomize the array.
 
-  for (i = 0; i < size; i++)
-    {
-      int index = ACE_OS::rand() % size--;
-      T temp = array [index];
-      array [index] = array [size];
-      array [size] = temp;
-    }
+static void
+randomize_array (ACE_Time_Value array[], int size)
+{
+  for (int i = 0; i < size; ++i)
+  {
+    int index = ACE_OS::rand() % size--;
+    ACE_Time_Value temp = array [index];
+    array [index] = array [size];
+    array [size] = temp;
+  }
 }
-
+				
 // Number of iterations for the performance tests.  Some platforms
 // have a very high ACE_DEFAULT_TIMERS (HP-UX is 400), so limit this
 // to a reasonable run time.
@@ -66,25 +63,24 @@ class Example_Handler : public ACE_Event_Handler
 {
 public:
   Example_Handler (void): close_count_ (0) {}
-
+  
   virtual int handle_close (ACE_HANDLE, ACE_Reactor_Mask mask)
   {
     ACE_ASSERT (mask == ACE_Event_Handler::TIMER_MASK);
     this->close_count_++;
     return 0;
   }
-
+  
   virtual int handle_timeout (const ACE_Time_Value &,
-			      const void *arg)
+    const void *arg)
   {
     ACE_ASSERT (arg == (const void *) 42 || arg == (const void *)007);
-
-    if (arg != (const void *) 42)
-      return -1;
-    else
-      return 0;
+    if (arg == (const void*) 007) {
+      return -1; // This is the special value to trigger a handle_close
+    }
+    return 0;
   }
-
+  
   int close_count_;
   // Keeps track of the number of times that <handle_close> is called.
 };
@@ -93,316 +89,311 @@ static void
 test_functionality (ACE_Timer_Queue *tq)
 {
   Example_Handler eh;
-
+  
   ACE_ASSERT (tq->is_empty ());
   ACE_ASSERT (ACE_Time_Value::zero == ACE_Time_Value (0));
   long timer_id, timer_id2; 
- 
+  
   // Do a test on earliest_time.
   ACE_Time_Value earliest_time = tq->gettimeofday ();
-
+  
   timer_id = tq->schedule (&eh,
-                           (const void *) 1,
-                           earliest_time);
+    (const void *) 1,
+    earliest_time);
   
   ACE_OS::sleep (ACE_Time_Value (0, 10));
-    
+  
   timer_id2 = tq->schedule (&eh,
-                            (const void *) 1,
-                            tq->gettimeofday ());
-
+    (const void *) 1,
+    tq->gettimeofday ());
+  
   ACE_ASSERT (tq->earliest_time () == earliest_time);
-
+  
   tq->cancel (timer_id);
   tq->cancel (timer_id2);
   ACE_ASSERT (tq->is_empty () == 1);
-
+  ACE_ASSERT (eh.close_count_ == 0);
+  
   timer_id = tq->schedule (&eh,
-                           (const void *) 1, 
-			   tq->gettimeofday ());
+    (const void *) 1, 
+    tq->gettimeofday ());
   ACE_ASSERT (timer_id != -1);
   ACE_ASSERT (tq->is_empty () == 0); //==
-
+  
   ACE_ASSERT (tq->schedule (&eh,
-                            (const void *) 42,
-                            tq->gettimeofday ()) != -1);
+    (const void *) 42,
+    tq->gettimeofday ()) != -1);
   ACE_ASSERT (tq->is_empty () == 0); //==
   ACE_ASSERT (tq->schedule (&eh,
-                            (const void *) 42,
-                            tq->gettimeofday ()) != -1);
+    (const void *) 42,
+    tq->gettimeofday ()) != -1);
   ACE_ASSERT (tq->is_empty () == 0); //==
-
+  
   // The following method will trigger a call to <handle_close>.
+  ACE_ASSERT (eh.close_count_ == 0);
   ACE_ASSERT (tq->cancel (timer_id, 0, 0) == 1);
   ACE_ASSERT (tq->is_empty () == 0);
-
+  ACE_ASSERT (eh.close_count_ == 1);
+  
   ACE_ASSERT (tq->expire () == 2);
-
+  
   ACE_ASSERT (tq->schedule (&eh,
-                            (const void *) 007, 
-			    tq->gettimeofday ()) != -1);
+    (const void *) 007, 
+    tq->gettimeofday ()) != -1);
   ACE_ASSERT (tq->schedule (&eh,
-                            (const void *) 42,
-			   tq->gettimeofday () + ACE_Time_Value (100)) != -1);
+    (const void *) 42,
+    tq->gettimeofday () + ACE_Time_Value (100)) != -1);
   ACE_ASSERT (tq->schedule (&eh,
-                            (const void *) 42,
-                            tq->gettimeofday () + ACE_Time_Value (100)) != -1);
-
+    (const void *) 42,
+    tq->gettimeofday () + ACE_Time_Value (100)) != -1);
+  
   // The following will trigger a call to <handle_close> when it
   // cancels the second timer.  This happens because the first timer
   // has an <act> of 007, which causes eh.handle_timeout () to return
   // -1.  Since -1 is returned, all timers that use <eh> will be
   // cancelled (and <handle_close> will only be called on the first
   // timer that is cancelled).
+  ACE_ASSERT (eh.close_count_ == 1);
   ACE_ASSERT (tq->expire () == 1);
-  ACE_ASSERT (tq->is_empty () != 0);
+  ACE_ASSERT (eh.close_count_ == 2);
+  ACE_ASSERT (tq->is_empty () == 1);
+  //ACE_ASSERT (tq->cancel (&eh, 0) == 0);
   
   ACE_ASSERT (tq->schedule (&eh,
-                            (const void *) 4, 
-			    tq->gettimeofday ()) != -1);
+    (const void *) 4, 
+    tq->gettimeofday ()) != -1);
   ACE_ASSERT (tq->schedule (&eh,
-                            (const void *) 5, 
-			    tq->gettimeofday ()) != -1);
+    (const void *) 5, 
+    tq->gettimeofday ()) != -1);
   
   // The following method will trigger a call to <handle_close>.
+  ACE_ASSERT (eh.close_count_ == 2);
   ACE_ASSERT (tq->cancel (&eh, 0) == 2);
+  ACE_ASSERT (eh.close_count_ == 3); // Only one call to handle_close() even though two timers
   ACE_ASSERT (tq->is_empty ());
   ACE_ASSERT (tq->expire () == 0);
-
+  
   // This tests to make sure that <handle_close> is called when there
   // is only one timer of the type in the queue
+  ACE_ASSERT (eh.close_count_ == 3);
   ACE_ASSERT (tq->schedule (&eh,
-                            (const void *) 007, 
-			    tq->gettimeofday ()) != -1);
+    (const void *) 007, 
+    tq->gettimeofday ()) != -1);
   ACE_ASSERT (tq->expire () == 1);
-
+  ACE_ASSERT (eh.close_count_ == 4);
+  
   timer_id = tq->schedule (&eh,
-                           (const void *) 6,
-			   tq->gettimeofday ());
+    (const void *) 6,
+    tq->gettimeofday ());
   ACE_ASSERT (timer_id != -1);
   ACE_ASSERT (tq->schedule (&eh,
-                            (const void *) 7, 
-			    tq->gettimeofday ()) != -1);
-
+    (const void *) 7, 
+    tq->gettimeofday ()) != -1);
+  
+  ACE_ASSERT (eh.close_count_ == 4);
   // The following method will *not* trigger a call to <handle_close>.
   ACE_ASSERT (tq->cancel (timer_id) == 1);
+  ACE_ASSERT (eh.close_count_ == 4);
   ACE_ASSERT (tq->cancel (&eh) == 1);
+  ACE_ASSERT (eh.close_count_ == 4);
   ACE_ASSERT (tq->expire () == 0);
   ACE_ASSERT (eh.close_count_ == 4);
 }
 
 static void
 test_performance (ACE_Timer_Queue *tq,
-		  const ACE_TCHAR *test_name)
+                  const ACE_TCHAR *test_name)
 {
   Example_Handler eh;
   ACE_Profile_Timer timer;
   int i;
-
+  
   ACE_ASSERT (tq->is_empty ());
   ACE_ASSERT (ACE_Time_Value::zero == ACE_Time_Value (0));
-
+  
   // Test the amount of time required to schedule all the timers.
-
+  
   ACE_Time_Value *times;
   ACE_NEW (times, ACE_Time_Value[max_iterations]);
 
+  // Set up a bunch of times 50ms apart.
   for (i = 0; i < max_iterations; i++)
-    times[i] = tq->gettimeofday ();
+    times[i] = tq->gettimeofday() + ACE_Time_Value(0, i * 50 * 1000);
 
+  ACE_Time_Value last_time = times[max_iterations-1];
+  
   timer.start ();
-
+  
   for (i = 0; i < max_iterations; i++)
-    {
-      timer_ids[i] = tq->schedule (&eh, 
-				   (const void *) 42, 
-				   times[i]);
-      ACE_ASSERT (timer_ids[i] != -1);
-    }
-
+  {
+    timer_ids[i] = tq->schedule (&eh, 
+      (const void *) 42, 
+      times[i]);
+    ACE_ASSERT (timer_ids[i] != -1);
+  }
+  
   ACE_ASSERT (tq->is_empty () == 0);
-
+  
   timer.stop ();
-
+  
   ACE_Profile_Timer::ACE_Elapsed_Time et;
-
+  
   timer.elapsed_time (et);
-
+  
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("time to schedule %d timers for %s\n"), 
-	      max_iterations, test_name));
+    ACE_TEXT ("time to schedule %d timers for %s\n"), 
+    max_iterations, test_name));
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
-              et.real_time, et.user_time, et.system_time));
+    ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
+    et.real_time, et.user_time, et.system_time));
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("time per call = %f usecs\n"), 
-	      (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
-
+    ACE_TEXT ("time per call = %f usecs\n"), 
+    (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
+  
   // Test the amount of time required to cancel all the timers.
-
+  
   timer.start ();
-
+  
   for (i = max_iterations - 1; i >= 0; i--)
     tq->cancel (timer_ids[i]);
-
+  
   timer.stop ();
-
+  
   ACE_ASSERT (tq->is_empty ());
-
+  
   timer.elapsed_time (et);
-
+  
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("time to cancel %d timers for %s\n"),
-	      max_iterations, test_name));
+    ACE_TEXT ("time to cancel %d timers for %s\n"),
+    max_iterations, test_name));
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
-              et.real_time, et.user_time, et.system_time));
+    ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
+    et.real_time, et.user_time, et.system_time));
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("time per call = %f usecs\n"), 
-	      (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
-
+    ACE_TEXT ("time per call = %f usecs\n"), 
+    (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
+  
   // Test the amount of time required to schedule and expire all the
   // timers.
-
+  
   timer.start ();
-
+  
   for (i = 0; i < max_iterations; i++)
     ACE_ASSERT (tq->schedule (&eh, 
-			      (const void *) 42, 
-			      tq->gettimeofday ()) != -1);
-
+    (const void *) 42, 
+    times[i]) != -1);
+  
   ACE_ASSERT (tq->is_empty () == 0);
-
+  
   // Expire all the timers.
-  tq->expire ();
-
+  tq->expire (last_time + ACE_Time_Value(1));
+  
   timer.stop ();
-
-  if (!tq->is_empty ())
-    {
-      ACE_OS::sleep (ACE_Time_Value (1));
-      tq->expire ();
-    }
-
+  
   ACE_ASSERT (tq->is_empty ());
-
+  
   timer.elapsed_time (et);
-
+  
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("time to schedule and expire %d timers for %s\n"), 
-	      max_iterations, test_name));
+    ACE_TEXT ("time to schedule and expire %d timers for %s\n"), 
+    max_iterations, test_name));
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
-              et.real_time, et.user_time, et.system_time));
+    ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
+    et.real_time, et.user_time, et.system_time));
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("time per call = %f usecs\n"), 
-	      (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
+    ACE_TEXT ("time per call = %f usecs\n"), 
+    (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
+  
+  randomize_array(times, max_iterations);
 
   // Test the amount of time required to randomly cancel all the
-  // timers.
+  // timers. 
 
   for (i = 0; i < max_iterations; i++)
-    {
-      timer_ids[i] = tq->schedule (&eh, 
-                                   (const void *) 42,
-				   tq->gettimeofday ()); 
-      ACE_ASSERT (timer_ids[i] != -1);
-    }
-
+  {
+    timer_ids[i] = tq->schedule (&eh, 
+      (const void *) 42,
+      times[i]); 
+    ACE_ASSERT (timer_ids[i] != -1);
+  }
+  
   ACE_ASSERT (tq->is_empty () == 0);
-
+  
   timer.start ();
-
+  
   for (i = max_iterations - 1; i >= 0; i--)
     tq->cancel (timer_ids[i]);
-
-  if (!tq->is_empty ())
-    {
-      ACE_OS::sleep (ACE_Time_Value (1));
-      tq->expire ();
-    }
-
+  
   ACE_ASSERT (tq->is_empty ());
-
+  
   timer.stop ();
-
+  
   timer.elapsed_time (et);
-
+  
   ACE_DEBUG ((LM_DEBUG, 
-              ACE_TEXT ("time to randomly cancel %d timers for %s\n"), 
-              max_iterations,
-              test_name));
+    ACE_TEXT ("time to randomly cancel %d timers for %s\n"), 
+    max_iterations,
+    test_name));
   ACE_DEBUG ((LM_DEBUG, 
-              ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
-              et.real_time,
-              et.user_time,
-              et.system_time));
+    ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
+    et.real_time,
+    et.user_time,
+    et.system_time));
   ACE_DEBUG ((LM_DEBUG, 
-              ACE_TEXT ("time per call = %f usecs\n"), 
-              (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
-
+    ACE_TEXT ("time per call = %f usecs\n"), 
+    (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
+  
   // Test the amount of time required to randomly schedule all the timers.
-
-  ACE_Time_Value now = tq->gettimeofday ();
   
-  for (i = 0; i < max_iterations; i++)
-    times[i] = now - ACE_Time_Value (0, ACE_OS::rand () % 1000000);
-
   timer.start ();
-
+  
   for (i = 0; i < max_iterations; i++)
-    {
-      timer_ids[i] = tq->schedule (&eh, 
-				   (const void *) 42, 
-				   times[i]);
-      ACE_ASSERT (timer_ids[i] != -1);
-    }
-
+  {
+    timer_ids[i] = tq->schedule (&eh, 
+      (const void *) 42, 
+      times[i]);
+    ACE_ASSERT (timer_ids[i] != -1);
+  }
+  
   timer.stop ();
-
+  
   ACE_ASSERT (tq->is_empty () == 0);
-
+  
   timer.elapsed_time (et);
-
+  
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("time to randomly schedule %d timers for %s\n"), 
-	      max_iterations, test_name));
+    ACE_TEXT ("time to randomly schedule %d timers for %s\n"), 
+    max_iterations, test_name));
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
-              et.real_time,
-              et.user_time,
-              et.system_time));
+    ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
+    et.real_time,
+    et.user_time,
+    et.system_time));
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("time per call = %f usecs\n"), 
-	      (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
-
-  // Test the amount of time required to cancel all the timers.
-
+    ACE_TEXT ("time per call = %f usecs\n"), 
+    (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
+  
+  // Test the amount of time required to expire all the timers.
+  
   timer.start ();
-
-  tq->expire ();
-
-  if (!tq->is_empty ())
-    {
-      ACE_OS::sleep (ACE_Time_Value (1));
-      tq->expire ();
-    }
-
+  
+  tq->expire (last_time + ACE_Time_Value(1));
+  
   ACE_ASSERT (tq->is_empty ());
-
+  
   timer.stop ();
-
+  
   timer.elapsed_time (et);
-
+  
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("time to expire %d randomly scheduled timers for %s\n"),
-	      max_iterations, test_name));
+    ACE_TEXT ("time to expire %d randomly scheduled timers for %s\n"),
+    max_iterations, test_name));
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
-              et.real_time, et.user_time, et.system_time));
+    ACE_TEXT ("real time = %f secs, user time = %f secs, system time = %f secs\n"),
+    et.real_time, et.user_time, et.system_time));
   ACE_DEBUG ((LM_DEBUG, 
-	      ACE_TEXT ("time per call = %f usecs\n"), 
-	      (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
+    ACE_TEXT ("time per call = %f usecs\n"), 
+    (et.user_time / ACE_timer_t (max_iterations)) * 1000000));
   
   delete [] times;
 }
@@ -417,122 +408,122 @@ class Timer_Queue_Stack
 public:
   // = Initialization method
   Timer_Queue_Stack (ACE_Timer_Queue *queue,
-                     const ACE_TCHAR *name,
-                     Timer_Queue_Stack *next = NULL)
+    const ACE_TCHAR *name,
+    Timer_Queue_Stack *next = NULL)
     : queue_ (queue),
-      name_ (name),
-      next_ (next)
+    name_ (name),
+    next_ (next)
   {}
   // "Push" a new <queue> on the stack of <queue>s.
-
+  
   ACE_Timer_Queue *queue_;
   // Pointer to the subclass of <ACE_Timer_Queue> that we're testing.
   
   const ACE_TCHAR *name_;
   // Name of the Queue that we're testing.
-
+  
   Timer_Queue_Stack *next_;
   // Pointer to the next <Timer_Queue>.
 };
 
 int
-ACE_TMAIN (int argc, ACE_TCHAR *argv[])
+main (int argc, ACE_TCHAR *argv[])
 {
   ACE_START_TEST (ACE_TEXT ("Timer_Queue_Test"));
-
+  
   ACE_OS::srand (ACE_OS::time (0L));
- 
+  
   if (argc > 1)
     max_iterations = ACE_OS::atoi (argv[1]);
-
+  
   // = Perform initializations.
   
   Timer_Queue_Stack *tq_stack = NULL;
-
+  
   // Add new Timer_Queue implementations here.  Note that these will
-  // be executed in "reverse order" since we treat
-
+  // be executed in "reverse order".
+  
   // Timer_Hash (Heap)
   ACE_NEW_RETURN (tq_stack,
-                  Timer_Queue_Stack (new ACE_Timer_Hash_Heap,
-                                     ACE_TEXT ("ACE_Timer_Hash (Heap)"),
-                                     tq_stack),
-                  -1);
-
+    Timer_Queue_Stack (new ACE_Timer_Hash_Heap,
+    ACE_TEXT ("ACE_Timer_Hash (Heap)"),
+    tq_stack),
+    -1);
+  
   // Timer_Hash
   ACE_NEW_RETURN (tq_stack,
-                  Timer_Queue_Stack (new ACE_Timer_Hash,
-                                     ACE_TEXT ("ACE_Timer_Hash"),
-                                     tq_stack),
-                  -1);
-
+    Timer_Queue_Stack (new ACE_Timer_Hash,
+    ACE_TEXT ("ACE_Timer_Hash"),
+    tq_stack),
+    -1);
+  
   // Timer_stack
   ACE_NEW_RETURN (tq_stack,
-                  Timer_Queue_Stack (new ACE_Timer_List,
-                                     ACE_TEXT ("ACE_Timer_List"),
-                                     tq_stack),
-                  -1);
-
+    Timer_Queue_Stack (new ACE_Timer_List,
+    ACE_TEXT ("ACE_Timer_List"),
+    tq_stack),
+    -1);
+  
   // Timer_Wheel without preallocated memory
   ACE_NEW_RETURN (tq_stack,
-                  Timer_Queue_Stack (new ACE_Timer_Wheel,
-                                     ACE_TEXT ("ACE_Timer_Wheel (non-preallocated)"),
-                                     tq_stack),
-                  -1);
-
+    Timer_Queue_Stack (new ACE_Timer_Wheel,
+    ACE_TEXT ("ACE_Timer_Wheel (non-preallocated)"),
+    tq_stack),
+    -1);
+  
   // Timer_Wheel with preallocated memory.
   ACE_NEW_RETURN (tq_stack,
-                  Timer_Queue_Stack (new ACE_Timer_Wheel (ACE_DEFAULT_TIMER_WHEEL_SIZE, 
-                                                         ACE_DEFAULT_TIMER_WHEEL_RESOLUTION, 
-                                                         max_iterations),
-                                     ACE_TEXT ("ACE_Timer_Wheel (preallocated)"),
-                                     tq_stack),
-                  -1);
+    Timer_Queue_Stack (new ACE_Timer_Wheel (ACE_DEFAULT_TIMER_WHEEL_SIZE, 
+    ACE_DEFAULT_TIMER_WHEEL_RESOLUTION, 
+    max_iterations),
+    ACE_TEXT ("ACE_Timer_Wheel (preallocated)"),
+    tq_stack),
+    -1);
   // Timer_Heap without preallocated memory.
   ACE_NEW_RETURN (tq_stack,
-                  Timer_Queue_Stack (new ACE_Timer_Heap,
-                                     ACE_TEXT ("ACE_Timer_Heap (non-preallocated)"),
-                                     tq_stack),
-                  -1);
-
+    Timer_Queue_Stack (new ACE_Timer_Heap,
+    ACE_TEXT ("ACE_Timer_Heap (non-preallocated)"),
+    tq_stack),
+    -1);
+  
   // Timer_Heap with preallocate memory.
   ACE_NEW_RETURN (tq_stack,
-                  Timer_Queue_Stack (new ACE_Timer_Heap (max_iterations, 1),
-                                     ACE_TEXT ("ACE_Timer_Heap (preallocated)"),
-                                     tq_stack),
-                  -1);
-
+    Timer_Queue_Stack (new ACE_Timer_Heap (max_iterations, 1),
+    ACE_TEXT ("ACE_Timer_Heap (preallocated)"),
+    tq_stack),
+    -1);
+  
   // Timer_Heap without preallocated memory, using high-res time.
   (void) ACE_High_Res_Timer::global_scale_factor ();
   ACE_Timer_Heap *tq_heap = new ACE_Timer_Heap;
   tq_heap->gettimeofday (&ACE_High_Res_Timer::gettimeofday_hr);
   ACE_NEW_RETURN (tq_stack,
-                  Timer_Queue_Stack (tq_heap,
-                                     ACE_TEXT ("ACE_Timer_Heap (high-res timer)"),
-                                     tq_stack),
-                  -1);
+    Timer_Queue_Stack (tq_heap,
+    ACE_TEXT ("ACE_Timer_Heap (high-res timer)"),
+    tq_stack),
+    -1);
   
   // Create the Timer ID array
   ACE_NEW_RETURN (timer_ids,
 		  long[max_iterations],
-		  -1);
+      -1);
   
   Timer_Queue_Stack *tq_ptr = tq_stack;
-
+  
   while (tq_ptr != NULL)
-    {
-      ACE_DEBUG ((LM_DEBUG,
-                  ACE_TEXT ("**** starting test of %s\n"), 
-		  tq_ptr->name_));
-      test_functionality (tq_ptr->queue_);
-      test_performance (tq_ptr->queue_, 
-			tq_ptr->name_);
-      delete tq_ptr->queue_;
-      Timer_Queue_Stack *temp = tq_ptr;
-      tq_ptr = tq_ptr->next_;
-      delete temp;
-    }
-
+  {
+    ACE_DEBUG ((LM_DEBUG,
+      ACE_TEXT ("**** starting test of %s\n"), 
+      tq_ptr->name_));
+    test_functionality (tq_ptr->queue_);
+    test_performance (tq_ptr->queue_, 
+      tq_ptr->name_);
+    delete tq_ptr->queue_;
+    Timer_Queue_Stack *temp = tq_ptr;
+    tq_ptr = tq_ptr->next_;
+    delete temp;
+  }
+  
   delete [] timer_ids;
   
   ACE_END_TEST;