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

Timer_Wheel_T.cpp

Go to the documentation of this file.
00001 // $Id: Timer_Wheel_T.cpp,v 1.1.1.4 2003/02/21 18:36:32 chad Exp $
00002 
00003 #ifndef ACE_TIMER_WHEEL_T_C
00004 #define ACE_TIMER_WHEEL_T_C
00005 
00006 #if !defined (ACE_LACKS_PRAGMA_ONCE)
00007 # pragma once
00008 #endif /* ACE_LACKS_PRAGMA_ONCE */
00009 
00010 #include "ace/Timer_Wheel_T.h"
00011 #include "ace/Log_Msg.h"
00012 
00013 ACE_RCSID(ace, Timer_Wheel_T, "$Id: Timer_Wheel_T.cpp,v 1.1.1.4 2003/02/21 18:36:32 chad Exp $")
00014 
00015 
00016 // Design/implementation notes for ACE_Timer_Wheel_T.
00017 //
00018 // Each timer queue entry is represented by a ACE_Timer_Node.
00019 // The timing wheel is divided into a number of "spokes"; there are
00020 // spoke_count_ spokes in the wheel. Each timer is hashed into one of the
00021 // spokes. Entries within each spoke are linked in a double-linked list
00022 // in order of increasing expiration. The first ACE_Timer_Node in each
00023 // spoke is a "dummy node" that marks the end of the list of ACE_Timer_Nodes
00024 // in that spoke.
00025 //
00026 // The timer ID for a scheduled timer is formed by its spoke position in
00027 // the wheel, and the number of timers that have been inserted in that spoke
00028 // since the queue was initialized. N bits of the long timer_id are used
00029 // to determine the spoke, and M bits are used as a counter.
00030 // Each time a Node is inserted into a spoke, it's counter
00031 // is incremented. The count is kept in the timer ID field
00032 // of the dummy root Node. In the event of overflow of the counter, the spoke
00033 // must be searched for each new id to make sure it's not already in use. To
00034 // prevent having to do an exhaustive search each time, we keep extra data
00035 // in the dummy root Node.
00036 /**
00037 * Default Constructor that sets defaults for spoke_count_ and resolution_
00038 * and doesn't do any preallocation.
00039 *
00040 * @param upcall_functor A pointer to a functor to use instead of the default
00041 * @param freelist       A pointer to a freelist to use instead of the default
00042 */
00043 template <class TYPE, class FUNCTOR, class ACE_LOCK>
00044 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::ACE_Timer_Wheel_T
00045 (FUNCTOR* upcall_functor
00046  , FreeList* freelist
00047  )
00048 : Base (upcall_functor, freelist)
00049 , spokes_(0)
00050 , spoke_count_(0) // calculated in open_i
00051 , spoke_bits_(0)
00052 , res_bits_ (0)
00053 , earliest_spoke_ (0)
00054 , iterator_(0)
00055 , timer_count_(0)
00056 {
00057   ACE_TRACE ("ACE_Timer_Wheel_T::ACE_Timer_Wheel_T");
00058   this->open_i (0,
00059                 ACE_DEFAULT_TIMER_WHEEL_SIZE,
00060                 ACE_DEFAULT_TIMER_WHEEL_RESOLUTION);
00061 }
00062 
00063 /**
00064 * Constructor that sets up the timing wheel and also may preallocate
00065 * some nodes on the free list
00066 *
00067 * @param spoke_count    The number of lists in the timer wheel
00068 * @param resolution     The time resolution in milliseconds used by the hashing function
00069 * @param prealloc       The number of entries to prealloc in the free_list
00070 * @param upcall_functor A pointer to a functor to use instead of the default
00071 * @param freelist       A pointer to a freelist to use instead of the default
00072 */
00073 template <class TYPE, class FUNCTOR, class ACE_LOCK>
00074 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::ACE_Timer_Wheel_T
00075   (u_int spoke_count,
00076    u_int resolution,
00077    size_t prealloc,
00078    FUNCTOR* upcall_functor,
00079    FreeList* freelist)
00080 : Base (upcall_functor, freelist)
00081 , spokes_ (0)
00082 , spoke_count_ (0) // calculated in open_i
00083 , spoke_bits_ (0)
00084 , res_bits_ (0)
00085 , earliest_spoke_ (0)
00086 , iterator_ (0)
00087 , timer_count_ (0)
00088 {
00089   ACE_TRACE ("ACE_Timer_Wheel_T::ACE_Timer_Wheel_T");
00090   this->open_i (prealloc, spoke_count, resolution);
00091 }
00092 
00093 namespace {
00094   int power2bits(int n, int min_bits, int max_bits) {
00095     int max = (1 << max_bits) - 1;
00096     if (n > max) {
00097       return max_bits;
00098     }
00099     // count the bits in n.
00100     int i = 0;
00101     int tmp = n;
00102     do {
00103       tmp >>= 1;
00104       ++i;
00105     } while (tmp != 0);
00106 
00107     if (i <= min_bits) {
00108       return min_bits;
00109     }
00110     // Which is nearest?
00111     int a = (1 << i) - n;
00112     int b = (1 << (i - 1)) - n;
00113     if (b < 0)
00114       b = -b;
00115     if (b < a)
00116       return i - 1;
00117     return i;
00118   }
00119 }
00120 
00121 /**
00122 * Initialize the queue. Uses the established members for all needed
00123 * information.
00124 */
00125 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
00126 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::open_i
00127   (size_t prealloc, u_int spokes, u_int res)
00128 {
00129   ACE_TRACE ("ACE_Timer_Wheel_T::open_i");
00130 
00131   this->gettimeofday (ACE_OS::gettimeofday);
00132 
00133   // Rather than waste bits in our timer id, we might as well round up
00134   // the spoke count to the next power of two - 1 . (i.e 1,3,7,15,...127,etc.)
00135   const int MIN_SPOKE_BITS = 3;  // Allow between 8 and 4096 spokes
00136   const int MAX_SPOKE_BITS = 12;
00137   const int MAX_RES_BITS = 20;   // 20 is plenty, even on 64 bit platforms.
00138 
00139   this->spoke_bits_ = power2bits (spokes, MIN_SPOKE_BITS, MAX_SPOKE_BITS);
00140   this->res_bits_ = power2bits (res, 1, MAX_RES_BITS);
00141 
00142   this->spoke_count_ = 1 << this->spoke_bits_;
00143 
00144   this->free_list_->resize (prealloc + this->spoke_count_);
00145 
00146   this->wheel_time_.msec (1 << (this->res_bits_ + this->spoke_bits_));
00147 
00148   ACE_NEW (this->spokes_, ACE_Timer_Node_T<TYPE>* [this->spoke_count_]);
00149 
00150   // Create the root nodes. These will be treated specially
00151   for (u_int i = 0; i < this->spoke_count_; ++i)
00152   {
00153     ACE_Timer_Node_T<TYPE>* root = this->alloc_node ();
00154     root->set (0, 0, ACE_Time_Value::zero, ACE_Time_Value::zero, root, root, 0);
00155     this->spokes_[i] = root;
00156   }
00157 
00158   ACE_NEW (iterator_, Iterator (*this));
00159 }
00160 
00161 /// Destructor just cleans up its memory
00162 template <class TYPE, class FUNCTOR, class ACE_LOCK>
00163 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::~ACE_Timer_Wheel_T (void)
00164 {
00165   ACE_TRACE ("ACE_Timer_Wheel_T::~ACE_Timer_Wheel_T");
00166 
00167   delete iterator_;
00168 
00169   for (u_int i = 0; i < this->spoke_count_; ++i)
00170   {
00171     // Free all the nodes starting at the root
00172     ACE_Timer_Node_T<TYPE>* root = this->spokes_[i];
00173     for (ACE_Timer_Node_T<TYPE>* n = root->get_next (); n != root;)
00174     {
00175       ACE_Timer_Node_T<TYPE>* next = n->get_next ();
00176       this->upcall_functor ().deletion (*this, n->get_type (), n->get_act ());
00177       this->free_node (n);
00178       n = next;
00179     }
00180     delete root;
00181   }
00182   delete[] this->spokes_;
00183 }
00184 
00185 /// Searches for a node by timer_id within one spoke.
00186 template <class TYPE, class FUNCTOR, class ACE_LOCK>
00187 ACE_Timer_Node_T<TYPE>*
00188 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::find_spoke_node
00189   (u_int spoke, long timer_id) const
00190 {
00191   ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
00192   for (ACE_Timer_Node_T<TYPE>* n = root->get_next ();
00193        n != root;
00194        n = n->get_next ())
00195     {
00196       if (n->get_timer_id () == timer_id)
00197         return n;
00198     }
00199   return 0;
00200 }
00201 
00202 /// Searches all spokes for a node matching the specified timer_id
00203 /// Uses the spoke encoded in the timer_id as a starting place.
00204 template <class TYPE, class FUNCTOR, class ACE_LOCK>
00205 ACE_Timer_Node_T<TYPE>*
00206 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::find_node (long timer_id) const
00207 {
00208   if (timer_id == -1)
00209     return 0;
00210 
00211   // Search the spoke where timer_id was originally scheduled
00212   u_int spoke_mask = this->spoke_count_ - 1;
00213   u_int start = timer_id & spoke_mask;
00214   ACE_Timer_Node_T<TYPE>* n = this->find_spoke_node (start, timer_id);
00215   if (n != 0)
00216     return n;
00217 
00218   //ACE_ERROR((LM_ERROR, "Node not found in original spoke.\n"));
00219 
00220   // Search the rest of the spokes
00221   for (u_int i = 0; i < this->spoke_count_; ++i)
00222     {
00223       if (i != start)
00224         { // already searched this one
00225           n = this->find_spoke_node (i, timer_id);
00226           if (n != 0)
00227             return n;
00228         }
00229     }
00230 
00231   //ACE_ERROR((LM_ERROR, "Node not found.\n"));
00232   return 0;
00233 }
00234 
00235 /**
00236 * Check to see if the wheel is empty
00237 *
00238 * @return True if empty
00239 */
00240 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
00241 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::is_empty (void) const
00242 {
00243   ACE_TRACE ("ACE_Timer_Wheel_T::is_empty");
00244   return timer_count_ == 0;
00245 }
00246 
00247 
00248 /**
00249 * @return First (earliest) node in the wheel_'s earliest_spoke_ list
00250 */
00251 template <class TYPE, class FUNCTOR, class ACE_LOCK> const ACE_Time_Value &
00252 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::earliest_time (void) const
00253 {
00254   ACE_TRACE ("ACE_Timer_Wheel_T::earliest_time");
00255   ACE_Timer_Node_T<TYPE>* n = this->get_first_i ();
00256   if (n != 0)
00257     return n->get_timer_value ();
00258   return ACE_Time_Value::zero;
00259 }
00260 
00261 /// Uses a simple hash to find which spoke to use based on when the
00262 /// timer is due to expire. Hopefully the 64bit int operations avoid
00263 /// any overflow problems.
00264 template <class TYPE, class FUNCTOR, class ACE_LOCK> u_int
00265 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::calculate_spoke
00266   (const ACE_Time_Value& t) const
00267 {
00268   return ACE_static_cast(u_int, (t.msec () >> this->res_bits_) & (this->spoke_count_ - 1));
00269 }
00270 
00271 /// Generates a unique timer_id for the given spoke. It should be pretty
00272 /// fast until the point where the counter overflows.  At that time you
00273 /// have to do exhaustive searches within the spoke to ensure that a particular
00274 /// timer id is not already in use. Some optimizations are in place so
00275 /// that this hopefully doesn't have to happen often.
00276 template <class TYPE, class FUNCTOR, class ACE_LOCK> long
00277 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::generate_timer_id (u_int spoke)
00278 {
00279 
00280   int cnt_bits = sizeof (long) * 8 - this->spoke_bits_;
00281   long max_cnt = ((long)1 << cnt_bits) - 1;
00282   if (spoke == this->spoke_count_)
00283     --max_cnt; // Because -1 is used as a special invalid timer_id.
00284 
00285   ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
00286 
00287   if (root == root->get_next ())
00288     root->set_act(0);
00289 
00290   // We use this field to keep track of the next counter value that
00291   // may be in use. Of course it may have expired, so we just use
00292   // this field so that we know when we don't have to check for duplicates
00293 #if defined (ACE_WIN64)
00294   // The cast below is legit... we know that long is shorter than a
00295   // pointer, but are only using it as a 'long' storage area.
00296 #  pragma warning(push)
00297 #  pragma warning(disable : 4311)
00298 #endif /* ACE_WIN64 */
00299   long next_cnt = ACE_reinterpret_cast (long, root->get_act ());
00300 #if defined (ACE_WIN64)
00301 #  pragma warning(pop)
00302 #endif /* ACE_WIN64 */
00303 
00304   // This field is used as a counter instead of a timer_id.
00305   long cnt = root->get_timer_id ();
00306 
00307   if (cnt >= max_cnt && root == root->get_next ())
00308     {
00309       // Special case when we overflow on an empty spoke. We can just
00310       // wrap the count around without searching for duplicates. We only
00311       // want to do this when the counter overflows, so that we return
00312       // unique timer_id values as often as possible.
00313       root->set_timer_id (1);
00314       return spoke;
00315     }
00316   else if (cnt >= max_cnt)
00317     { // overflow
00318       cnt = 0; // try again starting at zero
00319     }
00320   else if (next_cnt == 0 || cnt < next_cnt)
00321     {
00322       root->set_timer_id (cnt + 1);
00323       return (cnt << this->spoke_bits_) | spoke;
00324     }
00325 
00326   //ACE_ERROR((LM_ERROR, "Timer id overflow. We have to search now.\n"));
00327 
00328   // We've run out of consecutive id numbers so now we have to search
00329   // for a unique id.
00330   // We'll try increasing numbers until we find one that is not in use,
00331   // and we'll record the next highest number so that we can avoid this
00332   // search as often as possible.
00333   for (; cnt < max_cnt - 1; ++cnt)
00334     {
00335       long id = (cnt << this->spoke_bits_) | spoke;
00336       ACE_Timer_Node_T<TYPE>* n = this->find_spoke_node (spoke, id);
00337       if (n == 0)
00338         {
00339           root->set_timer_id (cnt + 1);
00340           // Now we need to find the next highest cnt in use
00341           next_cnt = 0;
00342           for (; n != root; n = n->get_next ())
00343             {
00344               long tmp = n->get_timer_id () >> this->spoke_bits_;
00345               if (tmp > cnt && (tmp < next_cnt || next_cnt == 0))
00346                 next_cnt = tmp;
00347             }
00348 #if defined (ACE_WIN64)
00349           // The cast below is legit... we know we're storing a long in
00350           // a pointer, but are only using it as a 'long' storage area.
00351 #  pragma warning(push)
00352 #  pragma warning(disable : 4312)
00353 #endif /* ACE_WIN64 */
00354           root->set_act (ACE_reinterpret_cast (void*, next_cnt));
00355 #if defined (ACE_WIN64)
00356 #  pragma warning(pop)
00357 #endif /* ACE_WIN64 */
00358           return id;
00359         }
00360     }
00361 
00362   return -1; // We did our best, but the spoke is full.
00363 }
00364 
00365 /**
00366 * Creates a ACE_Timer_Node_T based on the input parameters.  Then inserts
00367 * the node into the wheel using reschedule ().  Then returns a timer_id.
00368 *
00369 *  @param type            The data of the timer node
00370 *  @param act             Asynchronous Completion Token (AKA magic cookie)
00371 *  @param future_time     The time the timer is scheduled for (absolute time)
00372 *  @param interval        If not ACE_Time_Value::zero, then this is a periodic
00373 *                         timer and interval is the time period
00374 *
00375 *  @return Unique identifier (can be used to cancel the timer).
00376 *          -1 on failure.
00377 */
00378 template <class TYPE, class FUNCTOR, class ACE_LOCK> long
00379 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::schedule (
00380                                                       const TYPE& type,
00381                                                       const void* act,
00382                                                       const ACE_Time_Value& future_time,
00383                                                       const ACE_Time_Value& interval
00384                                                       )
00385 {
00386   ACE_TRACE ("ACE_Timer_Wheel_T::schedule");
00387   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
00388 
00389   ACE_Timer_Node_T<TYPE>* n = this->alloc_node ();
00390 
00391   if (n != 0)
00392     {
00393       u_int spoke = calculate_spoke (future_time);
00394       long id = generate_timer_id (spoke);
00395 
00396       //ACE_ERROR((LM_ERROR, "Scheduling %x spoke:%d id:%d\n", (long) n, spoke, id));
00397 
00398       if (id != -1)
00399         {
00400           n->set (type, act, future_time, interval, 0, 0, id);
00401           this->schedule_i (n, spoke, future_time);
00402         }
00403       return id;
00404     }
00405 
00406   // Failure return
00407   errno = ENOMEM;
00408   return -1;
00409 }
00410 
00411 /**
00412 * Takes an ACE_Timer_Node and inserts it into the correct position in
00413 * the correct list.  Also makes sure to update the earliest time.
00414 *
00415 * @param n The timer node to reschedule
00416 */
00417 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
00418 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::reschedule (ACE_Timer_Node_T<TYPE>* n)
00419 {
00420   ACE_TRACE ("ACE_Timer_Wheel_T::reschedule");
00421   const ACE_Time_Value& expire = n->get_timer_value ();
00422   u_int spoke = calculate_spoke (expire);
00423   this->schedule_i (n, spoke, expire);
00424 }
00425 
00426 /// The shared scheduling functionality between schedule() and reschedule()
00427 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
00428 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::schedule_i
00429   (ACE_Timer_Node_T<TYPE>* n,
00430    u_int spoke,
00431    const ACE_Time_Value& expire)
00432 {
00433   // See if we need to update the earliest time
00434   if (this->is_empty() || expire < this->earliest_time ())
00435     this->earliest_spoke_ = spoke;
00436 
00437   ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
00438   ACE_Timer_Node_T<TYPE>* last = root->get_prev ();
00439 
00440   ++timer_count_;
00441 
00442   // If the spoke is empty
00443   if (last == root) {
00444     n->set_prev (root);
00445     n->set_next (root);
00446     root->set_prev (n);
00447     root->set_next (n);
00448     return;
00449   }
00450 
00451   // We always want to search backwards from the tail of the list, because
00452   // this minimizes the search in the extreme case when lots of timers are
00453   // scheduled for exactly the same time
00454   ACE_Timer_Node_T<TYPE>* p = root->get_prev ();
00455   while (p != root && p->get_timer_value () > expire)
00456     p = p->get_prev ();
00457 
00458   // insert after
00459   n->set_prev (p);
00460   n->set_next (p->get_next ());
00461   p->get_next ()->set_prev (n);
00462   p->set_next (n);
00463 }
00464 
00465 
00466 /**
00467 * Find the timer node by using the id as a pointer.  Then use set_interval()
00468 * on the node to update the interval.
00469 *
00470 * @param timer_id The timer identifier
00471 * @param interval The new interval
00472 *
00473 * @return 0 if successful, -1 if no.
00474 */
00475 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
00476 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::reset_interval (long timer_id,
00477                                                             const ACE_Time_Value &interval
00478                                                             )
00479 {
00480   ACE_TRACE ("ACE_Timer_Wheel_T::reset_interval");
00481   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
00482   ACE_Timer_Node_T<TYPE>* n = this->find_node (timer_id);
00483   if (n != 0)
00484     {
00485       // The interval will take effect the next time this node is expired.
00486       n->set_interval (interval);
00487       return 0;
00488     }
00489   return -1;
00490 }
00491 
00492 
00493 /**
00494 * Goes through every list in the wheel and whenever we find one with the
00495 * correct type value, we remove it and continue.  At the end make sure
00496 * we reset the earliest time value in case the earliest timers were
00497 * removed.
00498 *
00499 * @param type       The value to search for.
00500 * @param skip_close If this non-zero, the cancellation method of the
00501 *                   functor will not be called for each cancelled timer.
00502 *
00503 * @return Number of timers cancelled
00504 */
00505 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
00506 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::cancel (const TYPE& type, int skip_close)
00507 {
00508   ACE_TRACE ("ACE_Timer_Wheel_T::cancel");
00509   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
00510 
00511   int num_canceled = 0; // Note : Technically this can overflow.
00512 
00513   if (!this->is_empty ())
00514     {
00515       ACE_Timer_Node_T<TYPE>* first = this->get_first ();
00516       ACE_Time_Value last = first->get_timer_value ();
00517       int recalc = 0;
00518 
00519       for (u_int i = 0; i < this->spoke_count_; ++i)
00520         {
00521           ACE_Timer_Node_T<TYPE>* root = this->spokes_[i];
00522           for (ACE_Timer_Node_T<TYPE>* n = root->get_next (); n != root; )
00523             {
00524               if (n->get_type () == type)
00525                 {
00526                   ++num_canceled;
00527                   if (n == first)
00528                     recalc = 1;
00529 
00530                   ACE_Timer_Node_T<TYPE>* tmp = n;
00531                   n = n->get_next ();
00532                   int always_skip_close = 1; // todo : Is this correct?
00533                   this->cancel_i (tmp, always_skip_close);
00534                 }
00535               else
00536                 {
00537                   n = n->get_next ();
00538                 }
00539             }
00540         }
00541 
00542       if (recalc)
00543         this->recalc_earliest (last);
00544     }
00545 
00546   if (!skip_close)  //  && num_canceled > 0)
00547     this->upcall_functor().cancellation (*this, type);
00548 
00549   return num_canceled;
00550 }
00551 
00552 
00553 /**
00554 * Cancels the single timer that is specified by the timer_id.  In this
00555 * case the timer_id is actually a pointer to the node, so we cast it
00556 * to the node.  This can be dangerous if the timer_id is made up
00557 * (or deleted twice) so we do a little sanity check.  Finally we update
00558 * the earliest time in case the earliest timer was removed.
00559 *
00560 * @param timer_id   Timer Identifier
00561 * @param act        Asychronous Completion Token (AKA magic cookie):
00562 *                   If this is non-zero, stores the magic cookie of
00563 *                   the cancelled timer here.
00564 * @param skip_close If this non-zero, the cancellation method of the
00565 *                   functor will not be called.
00566 *
00567 * @return 1 for sucess and 0 if the timer_id wasn't found (or was
00568 *         found to be invalid)
00569 */
00570 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
00571 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::cancel (long timer_id,
00572                                                     const void **act,
00573                                                     int skip_close)
00574 {
00575   ACE_TRACE ("ACE_Timer_Wheel_T::cancel");
00576   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
00577   ACE_Timer_Node_T<TYPE>* n = this->find_node (timer_id);
00578   if (n != 0)
00579     {
00580       ACE_Time_Value last = n->get_timer_value ();
00581       int recalc = (this->get_first_i () == n);
00582       if (act != 0)
00583         *act = n->get_act ();
00584       this->cancel_i (n, skip_close);
00585       if (recalc)
00586         this->recalc_earliest (last);
00587       return 1;
00588     }
00589   return 0;
00590 }
00591 
00592 /// Shared subset of the two cancel() methods.
00593 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
00594 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::cancel_i (ACE_Timer_Node_T<TYPE>* n, int skip_close)
00595 {
00596   //ACE_ERROR((LM_ERROR, "Canceling %x\n", (long) n));
00597   this->unlink (n);
00598   this->free_node (n);
00599   if (!skip_close)
00600     this->upcall_functor ().cancellation (*this, n->get_type ());
00601 }
00602 
00603 /// There are a few places where we have to figure out which timer
00604 /// will expire next. This method makes the assumption that spokes
00605 /// are always sorted, and that timers are always in the correct spoke
00606 /// determined from their expiration time. 
00607 /// The last time is always passed in, even though you can often calculate
00608 /// it as get_first()->get_timer_value().
00609 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
00610 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::recalc_earliest
00611   (const ACE_Time_Value& last)
00612 {
00613   // This is possible because we use a count for is_empty()
00614   if (this->is_empty ())
00615     return;
00616 
00617   ACE_Time_Value et = ACE_Time_Value::zero;
00618   
00619   u_int spoke = this->earliest_spoke_;
00620 
00621   // We will have to go around the wheel at most one time.
00622   for (u_int i = 0; i < this->spoke_count_; ++i)
00623     {
00624       ACE_Timer_Node_T<TYPE>* root = this->spokes_[spoke];
00625       ACE_Timer_Node_T<TYPE>* n = root->get_next ();
00626       if (n != root)
00627         {
00628           ACE_Time_Value t = n->get_timer_value ();
00629           if (t < last + this->wheel_time_)
00630             {
00631               this->earliest_spoke_ = spoke;
00632               return;
00633             }
00634           else if (et == ACE_Time_Value::zero || t < et)
00635             {
00636               et = t;
00637             }
00638         }
00639       if (++spoke >= this->spoke_count_)
00640         spoke = 0;
00641     }
00642   //ACE_ERROR((LM_ERROR, "We had to search the whole wheel.\n"));
00643 }
00644 
00645 /**
00646 * Dumps out the size of the wheel, the resolution, and the contents
00647 * of the wheel.
00648 */
00649 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
00650 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::dump (void) const
00651 {
00652   ACE_TRACE ("ACE_Timer_Wheel_T::dump");
00653   ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
00654   
00655   ACE_DEBUG ((LM_DEBUG,
00656     ACE_LIB_TEXT ("\nspoke_count_ = %d"), this->spoke_count_));
00657   ACE_DEBUG ((LM_DEBUG,
00658     ACE_LIB_TEXT ("\nresolution_ = %d"), 1 << this->res_bits_));
00659   ACE_DEBUG ((LM_DEBUG,
00660     ACE_LIB_TEXT ("\nwheel_ = \n")));
00661   
00662   for (u_int i = 0; i < this->spoke_count_; ++i)
00663     {
00664       ACE_DEBUG ((LM_DEBUG, ACE_LIB_TEXT ("%d\n"), i));
00665       ACE_Timer_Node_T<TYPE>* root = this->spokes_[i];
00666       for (ACE_Timer_Node_T<TYPE>* n = root->get_next ();
00667            n != root;
00668            n = n->get_next ())
00669         {
00670           n->dump ();
00671         }
00672     }
00673   
00674   ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
00675 }
00676 
00677 
00678 /**
00679 * Removes the earliest node and then find the new <earliest_spoke_>
00680 *
00681 * @return The earliest timer node.
00682 */
00683 template <class TYPE, class FUNCTOR, class ACE_LOCK> ACE_Timer_Node_T<TYPE> *
00684 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::remove_first (void)
00685 {
00686   ACE_TRACE ("ACE_Timer_Wheel_T::remove_first");
00687   return remove_first_expired (ACE_Time_Value::max_time);
00688 }
00689 
00690 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
00691 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::unlink (ACE_Timer_Node_T<TYPE>* n)
00692 {
00693   ACE_TRACE ("ACE_Timer_Wheel_T::unlink");
00694   --timer_count_;
00695   n->get_prev ()->set_next (n->get_next ());
00696   n->get_next ()->set_prev (n->get_prev ());
00697   n->set_prev (0);
00698   n->set_next (0);
00699 }
00700 
00701 template <class TYPE, class FUNCTOR, class ACE_LOCK> ACE_Timer_Node_T<TYPE> *
00702 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::remove_first_expired (const ACE_Time_Value& now)
00703 {
00704   ACE_Timer_Node_T<TYPE>* n = this->get_first ();
00705   if (n != 0 && n->get_timer_value() <= now)
00706     {
00707       this->unlink (n);
00708       this->recalc_earliest (n->get_timer_value ());
00709       return n;
00710     }
00711   return 0;
00712 }
00713 
00714 /**
00715 * Returns the earliest node without removing it
00716 *
00717 * @return The earliest timer node.
00718 */
00719 template <class TYPE, class FUNCTOR, class ACE_LOCK> 
00720 ACE_Timer_Node_T<TYPE>*
00721 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::get_first (void)
00722 {
00723   ACE_TRACE ("ACE_Timer_Wheel_T::get_first");
00724   return this->get_first_i ();
00725 }
00726 
00727 template <class TYPE, class FUNCTOR, class ACE_LOCK> 
00728 ACE_Timer_Node_T<TYPE>*
00729 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::get_first_i (void) const
00730 {
00731   ACE_Timer_Node_T<TYPE>* root = this->spokes_[this->earliest_spoke_];
00732   ACE_Timer_Node_T<TYPE>* first = root->get_next ();
00733   if (first != root)
00734     return first;
00735   return 0;
00736 }
00737 
00738 
00739 /**
00740 * @return The iterator
00741 */
00742 template <class TYPE, class FUNCTOR, class ACE_LOCK> 
00743 ACE_Timer_Queue_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>&
00744 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::iter (void)
00745 {
00746   this->iterator_->first ();
00747   return *this->iterator_;
00748 }
00749 
00750 /**
00751 * Dummy version of expire to get rid of warnings in Sun CC 4.2
00752 * Just call the expire of the base class.
00753 */
00754 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
00755 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::expire ()
00756 {
00757   return ACE_Timer_Queue_T<TYPE,FUNCTOR,ACE_LOCK>::expire ();
00758 }
00759 
00760 /**
00761 * This is a specialized version of expire that is more suited for the
00762 * internal data representation. 
00763 *
00764 * @param cur_time The time to expire timers up to.
00765 *
00766 * @return Number of timers expired
00767 */
00768 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
00769 ACE_Timer_Wheel_T<TYPE, FUNCTOR, ACE_LOCK>::expire (const ACE_Time_Value& cur_time)
00770 {
00771   ACE_TRACE ("ACE_Timer_Wheel_T::expire");
00772   ACE_MT (ACE_GUARD_RETURN (ACE_LOCK, ace_mon, this->mutex_, -1));
00773 
00774   int expcount = 0;
00775   ACE_Timer_Node_T<TYPE>* n = this->remove_first_expired (cur_time);
00776 
00777   while (n != 0)
00778     {
00779       ++ expcount;
00780 
00781       //ACE_ERROR((LM_ERROR, "Expiring %x\n", (long) n));
00782 
00783       this->upcall (n->get_type (), n->get_act (), cur_time);
00784 
00785       if (n->get_interval () > ACE_Time_Value::zero)
00786         {
00787           n->set_timer_value (cur_time + n->get_interval ());
00788           this->reschedule (n);
00789         }
00790       else
00791         {
00792           this->free_node (n);
00793         }
00794 
00795       n = this->remove_first_expired (cur_time);
00796     }
00797 
00798   //ACE_ERROR((LM_ERROR, "Expired %d nodes\n", expcount));
00799 
00800   return expcount;
00801 }
00802 
00803 ///////////////////////////////////////////////////////////////////////////
00804 // ACE_Timer_Wheel_Iterator_T
00805  
00806 /**
00807 * Just initializes the iterator with a ACE_Timer_Wheel_T and then calls
00808 * first() to initialize the rest of itself.
00809 *
00810 * @param wheel A reference for a timer queue to iterate over
00811 */
00812 template <class TYPE, class FUNCTOR, class ACE_LOCK>
00813 ACE_Timer_Wheel_Iterator_T<TYPE,FUNCTOR,ACE_LOCK>::ACE_Timer_Wheel_Iterator_T 
00814 (Wheel& wheel)
00815 : timer_wheel_ (wheel)
00816 {
00817   this->first();
00818 }
00819 
00820 
00821 /**
00822 * Destructor, at this level does nothing.
00823 */
00824 template <class TYPE, class FUNCTOR, class ACE_LOCK>
00825 ACE_Timer_Wheel_Iterator_T<TYPE,
00826 FUNCTOR,
00827 ACE_LOCK>::~ACE_Timer_Wheel_Iterator_T (void)
00828 {
00829 }
00830 
00831 
00832 /**
00833 * Positions the iterator at the first position in the timing wheel
00834 * that contains something. spoke_ will be set to the spoke position of
00835 * this entry and current_node_ will point to the first entry in that spoke.
00836 *
00837 * If the wheel is empty, spoke_ will be equal timer_wheel_.spoke_count_ and
00838 * current_node_ would be 0.
00839 */
00840 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
00841 ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::first (void)
00842 {
00843   this->goto_next(0);
00844 }
00845 
00846 
00847 /**
00848 * Positions the iterator at the next node.
00849 */
00850 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
00851 ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::next (void)
00852 {
00853   if (this->isdone())
00854     return;
00855 
00856   ACE_Timer_Node_T<TYPE>* n = this->current_node_->get_next ();
00857   ACE_Timer_Node_T<TYPE>* root = this->timer_wheel_.spokes_[this->spoke_];
00858   if (n == root)
00859     this->goto_next (this->spoke_ + 1);
00860   else
00861     this->current_node_ = n;
00862 }
00863 
00864 /// Helper class for common functionality of next() and first()
00865 template <class TYPE, class FUNCTOR, class ACE_LOCK> void
00866 ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::goto_next (u_int start_spoke)
00867 {
00868   // Find the first non-empty entry.
00869   u_int sc = this->timer_wheel_.spoke_count_;
00870   for (u_int i = start_spoke; i < sc; ++i)
00871   {
00872     ACE_Timer_Node_T<TYPE>* root = this->timer_wheel_.spokes_[i];
00873     ACE_Timer_Node_T<TYPE>* n = root->get_next ();
00874     if (n != root)
00875       {
00876         this->spoke_ = i;
00877         this->current_node_ = n;
00878         return;
00879       }
00880   }
00881   // empty
00882   this->spoke_ = sc;
00883   this->current_node_ = 0;
00884 }
00885 
00886 
00887 /**
00888 * @return True when we there aren't any more items (when current_node_ == 0)
00889 */
00890 template <class TYPE, class FUNCTOR, class ACE_LOCK> int
00891 ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::isdone (void) const
00892 {
00893   return this->current_node_ == 0;
00894 }
00895 
00896 
00897 /**
00898 * @return The node at the current spokeition in the sequence or 0 if the wheel
00899 *         is empty
00900 */
00901 template <class TYPE, class FUNCTOR, class ACE_LOCK> ACE_Timer_Node_T<TYPE> *
00902 ACE_Timer_Wheel_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>::item (void)
00903 {
00904   return this->current_node_;
00905 }
00906 
00907 
00908 #endif /* ACE_TIMER_WHEEL_T_C */

Generated on Mon Jun 16 11:21:53 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002