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

Timer_Heap_T.h

Go to the documentation of this file.
00001 /* -*- C++ -*- */
00002 
00003 //=============================================================================
00004 /**
00005  *  @file    Timer_Heap_T.h
00006  *
00007  *  $Id: Timer_Heap_T.h,v 1.1.1.4 2003/02/21 18:36:32 chad Exp $
00008  *
00009  *  @author Douglas C. Schmidt <schmidt@cs.wustl.edu>
00010  */
00011 //=============================================================================
00012 
00013 #ifndef ACE_TIMER_HEAP_T_H
00014 #define ACE_TIMER_HEAP_T_H
00015 #include "ace/pre.h"
00016 
00017 #include "ace/Timer_Queue_T.h"
00018 
00019 #if !defined (ACE_LACKS_PRAGMA_ONCE)
00020 # pragma once
00021 #endif /* ACE_LACKS_PRAGMA_ONCE */
00022 
00023 #include "ace/Free_List.h"
00024 #include "ace/Unbounded_Set.h"
00025 
00026 // Forward declaration
00027 template <class TYPE, class FUNCTOR, class ACE_LOCK>
00028 class ACE_Timer_Heap_T;
00029 
00030 /**
00031  * @class ACE_Timer_Heap_Iterator_T
00032  *
00033  * @brief Iterates over an <ACE_Timer_Heap_T>.
00034  *
00035  * This is a generic iterator that can be used to visit every
00036  * node of a timer queue.  Be aware that it doesn't transverse
00037  * in the order of timeout values.
00038  */
00039 template <class TYPE, class FUNCTOR, class ACE_LOCK>
00040 class ACE_Timer_Heap_Iterator_T : public ACE_Timer_Queue_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>
00041 {
00042 public:
00043   /// Constructor.
00044   ACE_Timer_Heap_Iterator_T (ACE_Timer_Heap_T<TYPE, FUNCTOR, ACE_LOCK> &);
00045 
00046   /// Destructor.
00047   ~ACE_Timer_Heap_Iterator_T (void);
00048 
00049   /// Positions the iterator at the earliest node in the Timer Queue
00050   virtual void first (void);
00051 
00052   /// Positions the iterator at the next node in the Timer Queue
00053   virtual void next (void);
00054 
00055   /// Returns true when there are no more nodes in the sequence
00056   virtual int isdone (void) const;
00057 
00058   /// Returns the node at the current position in the sequence
00059   virtual ACE_Timer_Node_T<TYPE> *item (void);
00060 
00061 protected:
00062   /// Pointer to the <ACE_Timer_Heap> that we are iterating over.
00063   ACE_Timer_Heap_T<TYPE, FUNCTOR, ACE_LOCK> &timer_heap_;
00064 
00065   /// Position in the array where the iterator is at
00066   size_t position_;
00067 };
00068 
00069 /**
00070  * @class ACE_Timer_Heap_T
00071  *
00072  * @brief Provides a very fast and predictable timer implementation.
00073  *
00074  * This implementation uses a heap-based callout queue of
00075  * absolute times.  Therefore, in the average and worst case,
00076  * scheduling, canceling, and expiring timers is O(log N) (where
00077  * N is the total number of timers).  In addition, we can also
00078  * preallocate as many @c ACE_Timer_Node objects as there are slots
00079  * in the heap.  This allows us to completely remove the need for
00080  * dynamic memory allocation, which is important for real-time
00081  * systems.
00082  */
00083 template <class TYPE, class FUNCTOR, class ACE_LOCK>
00084 class ACE_Timer_Heap_T : public ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK>
00085 {
00086 public:
00087   typedef ACE_Timer_Heap_Iterator_T<TYPE, FUNCTOR, ACE_LOCK> HEAP_ITERATOR;
00088   friend class ACE_Timer_Heap_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>;
00089 
00090   typedef ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK> INHERITED;
00091 
00092   // = Initialization and termination methods.
00093   /**
00094    * The Constructor creates a heap with specified number of elements.
00095    * This can also take in a upcall functor and freelist (if 0, then
00096    * defaults will be created).
00097    *
00098    * @param size The maximum number of timers that can be
00099    * inserted into the new object.
00100    * @param preallocated Default 0, if non-0 then all the memory
00101    * for the @c ACE_Timer_Node objects will be pre-allocated. This saves
00102    * time and is more predictable (though it requires more space).
00103    * Otherwise, timer nodes are allocated as needed.
00104    * @param freelist is the freelist of timer nodes.
00105    * @param upcall_functor If 0 Timer Heap will create a default FUNCTOR.
00106    */
00107   ACE_Timer_Heap_T (size_t size,
00108                     int preallocated = 0,
00109                     FUNCTOR *upcall_functor = 0,
00110                     ACE_Free_List<ACE_Timer_Node_T <TYPE> > *freelist = 0);
00111 
00112   /**
00113    * Default constructor. @c upcall_functor is the instance of the
00114    * FUNCTOR to be used by the queue. If @c upcall_functor is 0, Timer
00115    * Heap will create a default FUNCTOR.  @c freelist is the freelist of
00116    * timer nodes.  If 0, then a default freelist will be created.  The default
00117    * size will be ACE_DEFAULT_TIMERS and there will be no preallocation.
00118    */
00119   ACE_Timer_Heap_T (FUNCTOR *upcall_functor = 0,
00120                     ACE_Free_List<ACE_Timer_Node_T <TYPE> > *freelist = 0);
00121 
00122   /// Destructor.
00123   virtual ~ACE_Timer_Heap_T (void);
00124 
00125   /// True if heap is empty, else false.
00126   virtual int is_empty (void) const;
00127 
00128   /// Returns the time of the earliest node in the Timer_Queue.
00129   /// Must be called on a non-empty queue.
00130   virtual const ACE_Time_Value &earliest_time (void) const;
00131 
00132   /**
00133    * Schedule a timer that may optionally auto-reset.
00134    * Schedule <type> that will expire at <future_time>,
00135    * which is specified in absolute time.  If it expires then <act> is
00136    * passed in as the value to the <functor>.  If <interval> is != to
00137    * <ACE_Time_Value::zero> then it is used to reschedule the <type>
00138    * automatically, using relative time to the current <gettimeofday>.
00139    * This method returns a <timer_id> that uniquely identifies the the
00140    * <type> entry in an internal list.  This <timer_id> can be used to
00141    * cancel the timer before it expires.  The cancellation ensures
00142    * that <timer_ids> are unique up to values of greater than 2
00143    * billion timers.  As long as timers don't stay around longer than
00144    * this there should be no problems with accidentally deleting the
00145    * wrong timer.  Returns -1 on failure (which is guaranteed never to
00146    * be a valid <timer_id>).
00147    */
00148   virtual long schedule (const TYPE &type,
00149                          const void *act,
00150                          const ACE_Time_Value &future_time,
00151                          const ACE_Time_Value &interval = ACE_Time_Value::zero);
00152 
00153   /**
00154    * Resets the interval of the timer represented by <timer_id> to
00155    * <interval>, which is specified in relative time to the current
00156    * <gettimeofday>.  If <interval> is equal to
00157    * <ACE_Time_Value::zero>, the timer will become a non-rescheduling
00158    * timer.  Returns 0 if successful, -1 if not.
00159    */
00160   virtual int reset_interval (long timer_id,
00161                               const ACE_Time_Value &interval);
00162 
00163   /**
00164    * Cancel all timers associated with <type>.  If <dont_call> is 0
00165    * then the <functor> will be invoked.  Returns number of timers
00166    * cancelled.
00167    */
00168   virtual int cancel (const TYPE &type,
00169                       int dont_call_handle_close = 1);
00170 
00171   /**
00172    * Cancel the single timer that matches the <timer_id> value (which
00173    * was returned from the <schedule> method).  If act is non-NULL
00174    * then it will be set to point to the ``magic cookie'' argument
00175    * passed in when the timer was registered.  This makes it possible
00176    * to free up the memory and avoid memory leaks.  If <dont_call> is
00177    * 0 then the <functor> will be invoked.  Returns 1 if cancellation
00178    * succeeded and 0 if the <timer_id> wasn't found.
00179    */
00180   virtual int cancel (long timer_id,
00181                       const void **act = 0,
00182                       int dont_call_handle_close = 1);
00183 
00184   /// Returns a pointer to this <ACE_Timer_Queue>'s iterator.
00185   virtual ACE_Timer_Queue_Iterator_T<TYPE, FUNCTOR, ACE_LOCK> &iter (void);
00186 
00187   /**
00188    * Removes the earliest node from the queue and returns it. Note that
00189    * the timer is removed from the heap, but is not freed, and its ID
00190    * is not reclaimed. The caller is responsible for calling either
00191    * @c reschedule() or @c free_node() after this function returns. Thus,
00192    * this function is for support of @c ACE_Timer_Queue::expire and
00193    * should not be used unadvisedly in other conditions.
00194    */
00195   ACE_Timer_Node_T <TYPE> *remove_first (void);
00196 
00197   /// Dump the state of an object.
00198   virtual void dump (void) const;
00199 
00200   /// Reads the earliest node from the queue and returns it.
00201   virtual ACE_Timer_Node_T<TYPE> *get_first (void);
00202 
00203 protected:
00204   /// Reschedule an "interval" <ACE_Timer_Node>.
00205   virtual void reschedule (ACE_Timer_Node_T<TYPE> *);
00206 
00207   /// Factory method that allocates a new node (uses operator new if
00208   /// we're *not* preallocating, otherwise uses an internal freelist).
00209   virtual ACE_Timer_Node_T<TYPE> *alloc_node (void);
00210 
00211   /**
00212    * Factory method that frees a previously allocated node (uses
00213    * operator delete if we're *not* preallocating, otherwise uses an
00214    * internal freelist).
00215    */
00216   virtual void free_node (ACE_Timer_Node_T<TYPE> *);
00217 
00218 private:
00219   /// Remove and return the <slot>th <ACE_Timer_Node> and restore the
00220   /// heap property.
00221   ACE_Timer_Node_T<TYPE> *remove (size_t slot);
00222 
00223   /// Insert @a new_node into the heap and restore the heap property.
00224   void insert (ACE_Timer_Node_T<TYPE> *new_node);
00225 
00226   /**
00227    * Doubles the size of the heap and the corresponding timer_ids array.
00228    * If preallocation is used, will also double the size of the
00229    * preallocated array of ACE_Timer_Nodes.
00230    */
00231   void grow_heap (void);
00232 
00233   /// Restore the heap property, starting at <slot>.
00234   void reheap_up (ACE_Timer_Node_T<TYPE> *new_node,
00235                   size_t slot,
00236                   size_t parent);
00237 
00238   /// Restore the heap property, starting at <slot>.
00239   void reheap_down (ACE_Timer_Node_T<TYPE> *moved_node,
00240                     size_t slot,
00241                     size_t child);
00242 
00243   /// Copy <moved_node> into the <slot> slot of <heap_> and move
00244   /// <slot> into the corresponding slot in the <timer_id_> array.
00245   void copy (size_t slot, ACE_Timer_Node_T<TYPE> *moved_node);
00246 
00247   /**
00248    * Returns a timer id that uniquely identifies this timer.  This id
00249    * can be used to cancel a timer via the <cancel (int)> method.  The
00250    * timer id returned from this method will never == -1 to avoid
00251    * conflicts with other failure return values.
00252    */
00253   int timer_id (void);
00254 
00255   /// Pops and returns a new timer id from the freelist.
00256   int pop_freelist (void);
00257 
00258   /// Pushes <old_id> onto the freelist.
00259   void push_freelist (int old_id);
00260 
00261   /// Maximum size of the heap.
00262   size_t max_size_;
00263 
00264   /// Current size of the heap.
00265   size_t cur_size_;
00266 
00267   /// Number of heap entries in transition (removed from the queue, but
00268   /// not freed) and may be rescheduled or freed.
00269   size_t cur_limbo_;
00270 
00271   /// Iterator used to expire timers.
00272   HEAP_ITERATOR *iterator_;
00273 
00274   /**
00275    * Current contents of the Heap, which is organized as a "heap" of
00276    * <ACE_Timer_Node> *'s.  In this context, a heap is a "partially
00277    * ordered, almost complete" binary tree, which is stored in an
00278    * array.
00279    */
00280   ACE_Timer_Node_T<TYPE> **heap_;
00281 
00282   /**
00283    * An array of "pointers" that allows each <ACE_Timer_Node> in the
00284    * <heap_> to be located in O(1) time.  Basically, <timer_id_[i]>
00285    * contains the slot in the <heap_> array where an <ACE_Timer_Node>
00286    * * with timer id <i> resides.  Thus, the timer id passed back from
00287    * <schedule> is really a slot into the <timer_ids> array.  The
00288    * <timer_ids_> array serves two purposes: negative values are
00289    * indications of free timer IDs, whereas positive values are
00290    * "pointers" into the <heap_> array for assigned timer IDs.
00291    */
00292   ssize_t *timer_ids_;
00293 
00294   /// "Pointer" to the element in the <timer_ids_> array that was
00295   /// last given out as a timer ID.
00296   size_t timer_ids_curr_;
00297 
00298   /// Index representing the lowest timer ID that has been freed. When
00299   /// the timer_ids_next_ value wraps around, it starts back at this
00300   /// point.
00301   size_t timer_ids_min_free_;
00302 
00303   /**
00304    * If this is non-0, then we preallocate <max_size_> number of
00305    * <ACE_Timer_Node> objects in order to reduce dynamic allocation
00306    * costs.  In auto-growing implementation, this points to the
00307    * last array of nodes allocated.
00308    */
00309   ACE_Timer_Node_T<TYPE> *preallocated_nodes_;
00310 
00311   /// This points to the head of the <preallocated_nodes_> freelist,
00312   /// which is organized as a stack.
00313   ACE_Timer_Node_T<TYPE> *preallocated_nodes_freelist_;
00314 
00315   /// Set of pointers to the arrays of preallocated timer nodes.
00316   /// Used to delete the allocated memory when required.
00317   ACE_Unbounded_Set<ACE_Timer_Node_T<TYPE> *> preallocated_node_set_;
00318 
00319   // = Don't allow these operations for now.
00320   ACE_UNIMPLEMENTED_FUNC (ACE_Timer_Heap_T (const ACE_Timer_Heap_T<TYPE, FUNCTOR, ACE_LOCK> &))
00321   ACE_UNIMPLEMENTED_FUNC (void operator= (const ACE_Timer_Heap_T<TYPE, FUNCTOR, ACE_LOCK> &))
00322 };
00323 
00324 #if defined (ACE_TEMPLATES_REQUIRE_SOURCE) && !defined(ACE_HAS_BROKEN_HPUX_TEMPLATES)
00325 #include "ace/Timer_Heap_T.cpp"
00326 #endif /* ACE_TEMPLATES_REQUIRE_SOURCE && !ACE_HAS_BROKEN_HPUX_TEMPLATES */
00327 
00328 #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
00329 #pragma implementation ("Timer_Heap_T.cpp")
00330 #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */
00331 
00332 #include "ace/post.h"
00333 #endif /* ACE_TIMER_HEAP_T_H */

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