dep/ACE_wrappers/ace/Timer_Heap_T.h

   1 // -*- C++ -*-
   2
   3 //=============================================================================
   4 /**
   5  *  @file    Timer_Heap_T.h
   6  *
   7  *  $Id: Timer_Heap_T.h 80826 2008-03-04 14:51:23Z wotte $
   8  *
   9  *  @author Douglas C. Schmidt <schmidt@cs.wustl.edu>
  10  */
  11 //=============================================================================
  12
  13 #ifndef ACE_TIMER_HEAP_T_H
  14 #define ACE_TIMER_HEAP_T_H
  15 #include /**/ "ace/pre.h"
  16
  17 #include "ace/Timer_Queue_T.h"
  18
  19 #if !defined (ACE_LACKS_PRAGMA_ONCE)
  20 # pragma once
  21 #endif /* ACE_LACKS_PRAGMA_ONCE */
  22
  23 #include "ace/Free_List.h"
  24 #include "ace/Unbounded_Set.h"
  25
  26 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
  27
  28 // Forward declaration
  29 template <class TYPE, class FUNCTOR, class ACE_LOCK>
  30 class ACE_Timer_Heap_T;
  31
  32 /**
  33  * @class ACE_Timer_Heap_Iterator_T
  34  *
  35  * @brief Iterates over an ACE_Timer_Heap_T.
  36  *
  37  * This is a generic iterator that can be used to visit every
  38  * node of a timer queue.  Be aware that it doesn't transverse
  39  * in the order of timeout values.
  40  */
  41 template <class TYPE, class FUNCTOR, class ACE_LOCK>
  42 class ACE_Timer_Heap_Iterator_T : public ACE_Timer_Queue_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>
  43 {
  44 public:
  45   /// Constructor.
  46   ACE_Timer_Heap_Iterator_T (ACE_Timer_Heap_T<TYPE, FUNCTOR, ACE_LOCK> &);
  47
  48   /// Destructor.
  49   ~ACE_Timer_Heap_Iterator_T (void);
  50
  51   /// Positions the iterator at the earliest node in the Timer Queue
  52   virtual void first (void);
  53
  54   /// Positions the iterator at the next node in the Timer Queue
  55   virtual void next (void);
  56
  57   /// Returns true when there are no more nodes in the sequence
  58   virtual bool isdone (void) const;
  59
  60   /// Returns the node at the current position in the sequence
  61   virtual ACE_Timer_Node_T<TYPE> *item (void);
  62
  63 protected:
  64   /// Pointer to the ACE_Timer_Heap that we are iterating over.
  65   ACE_Timer_Heap_T<TYPE, FUNCTOR, ACE_LOCK> &timer_heap_;
  66
  67   /// Position in the array where the iterator is at
  68   size_t position_;
  69 };
  70
  71 /**
  72  * @class ACE_Timer_Heap_T
  73  *
  74  * @brief Provides a very fast and predictable timer implementation.
  75  *
  76  * This implementation uses a heap-based callout queue of
  77  * absolute times.  Therefore, in the average and worst case,
  78  * scheduling, canceling, and expiring timers is O(log N) (where
  79  * N is the total number of timers).  In addition, we can also
  80  * preallocate as many @c ACE_Timer_Node objects as there are slots
  81  * in the heap.  This allows us to completely remove the need for
  82  * dynamic memory allocation, which is important for real-time
  83  * systems.
  84  */
  85 template <class TYPE, class FUNCTOR, class ACE_LOCK>
  86 class ACE_Timer_Heap_T : public ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK>
  87 {
  88 public:
  89   typedef ACE_Timer_Heap_Iterator_T<TYPE, FUNCTOR, ACE_LOCK> HEAP_ITERATOR;
  90   friend class ACE_Timer_Heap_Iterator_T<TYPE, FUNCTOR, ACE_LOCK>;
  91
  92   typedef ACE_Timer_Queue_T<TYPE, FUNCTOR, ACE_LOCK> INHERITED;
  93
  94   // = Initialization and termination methods.
  95   /**
  96    * The Constructor creates a heap with specified number of elements.
  97    * This can also take in a upcall functor and freelist (if 0, then
  98    * defaults will be created).
  99    *
 100    * @param size The maximum number of timers that can be
 101    * inserted into the new object.
 102    * @param preallocated Default false, true then all the memory
 103    * for the @c ACE_Timer_Node objects will be pre-allocated. This saves
 104    * time and is more predictable (though it requires more space).
 105    * Otherwise, timer nodes are allocated as needed.
 106    * @param freelist is the freelist of timer nodes.
 107    * @param upcall_functor If 0 Timer Heap will create a default FUNCTOR.
 108    */
 109   ACE_Timer_Heap_T (size_t size,
 110                     bool preallocated = false,
 111                     FUNCTOR *upcall_functor = 0,
 112                     ACE_Free_List<ACE_Timer_Node_T <TYPE> > *freelist = 0);
 113
 114   /**
 115    * Default constructor. @c upcall_functor is the instance of the
 116    * FUNCTOR to be used by the queue. If @c upcall_functor is 0, Timer
 117    * Heap will create a default FUNCTOR.  @c freelist is the freelist of
 118    * timer nodes.  If 0, then a default freelist will be created.  The default
 119    * size will be ACE_DEFAULT_TIMERS and there will be no preallocation.
 120    */
 121   ACE_Timer_Heap_T (FUNCTOR *upcall_functor = 0,
 122                     ACE_Free_List<ACE_Timer_Node_T <TYPE> > *freelist = 0);
 123
 124   /// Destructor.
 125   virtual ~ACE_Timer_Heap_T (void);
 126
 127   /// True if heap is empty, else false.
 128   virtual bool is_empty (void) const;
 129
 130   /// Returns the time of the earliest node in the Timer_Queue.
 131   /// Must be called on a non-empty queue.
 132   virtual const ACE_Time_Value &earliest_time (void) const;
 133
 134   /**
 135    * Resets the interval of the timer represented by @a timer_id to
 136    * @a interval, which is specified in relative time to the current
 137    * <gettimeofday>.  If @a interval is equal to
 138    * ACE_Time_Value::zero, the timer will become a non-rescheduling
 139    * timer.  Returns 0 if successful, -1 if not.
 140    */
 141   virtual int reset_interval (long timer_id,
 142                               const ACE_Time_Value &interval);
 143
 144   /**
 145    * Cancel all timers associated with @a type.  If @a dont_call_handle_close
 146    * is 0then the <functor> will be invoked.  Returns number of timers
 147    * cancelled.
 148    */
 149   virtual int cancel (const TYPE &type,
 150                       int dont_call_handle_close = 1);
 151
 152   /**
 153    * Cancel the single timer that matches the @a timer_id value (which
 154    * was returned from the <schedule> method).  If act is non-NULL
 155    * then it will be set to point to the ``magic cookie'' argument
 156    * passed in when the timer was registered.  This makes it possible
 157    * to free up the memory and avoid memory leaks. If @a dont_call_handle_close
 158    * is 0 then the <functor> will be invoked.  Returns 1 if cancellation
 159    * succeeded and 0 if the @a timer_id wasn't found.
 160    */
 161   virtual int cancel (long timer_id,
 162                       const void **act = 0,
 163                       int dont_call_handle_close = 1);
 164
 165   /// Returns a pointer to this ACE_Timer_Queue's iterator.
 166   virtual ACE_Timer_Queue_Iterator_T<TYPE, FUNCTOR, ACE_LOCK> &iter (void);
 167
 168   /**
 169    * Removes the earliest node from the queue and returns it. Note that
 170    * the timer is removed from the heap, but is not freed, and its ID
 171    * is not reclaimed. The caller is responsible for calling either
 172    * @c reschedule() or @c free_node() after this function returns. Thus,
 173    * this function is for support of @c ACE_Timer_Queue::expire and
 174    * should not be used unadvisedly in other conditions.
 175    */
 176   ACE_Timer_Node_T <TYPE> *remove_first (void);
 177
 178   /// Dump the state of an object.
 179   virtual void dump (void) const;
 180
 181   /// Reads the earliest node from the queue and returns it.
 182   virtual ACE_Timer_Node_T<TYPE> *get_first (void);
 183
 184 protected:
 185
 186   /**
 187    * Schedule a timer that may optionally auto-reset.
 188    * Schedule @a type that will expire at @a future_time,
 189    * which is specified in absolute time.  If it expires then @a act is
 190    * passed in as the value to the <functor>.  If @a interval is != to
 191    * ACE_Time_Value::zero then it is used to reschedule the @a type
 192    * automatically, using relative time to the current <gettimeofday>.
 193    * This method returns a <timer_id> that uniquely identifies the the
 194    * @a type entry in an internal list.  This <timer_id> can be used to
 195    * cancel the timer before it expires.  The cancellation ensures
 196    * that <timer_ids> are unique up to values of greater than 2
 197    * billion timers.  As long as timers don't stay around longer than
 198    * this there should be no problems with accidentally deleting the
 199    * wrong timer.  Returns -1 on failure (which is guaranteed never to
 200    * be a valid <timer_id>).
 201    */
 202   virtual long schedule_i (const TYPE &type,
 203                            const void *act,
 204                            const ACE_Time_Value &future_time,
 205                            const ACE_Time_Value &interval);
 206
 207   /// Reschedule an "interval" ACE_Timer_Node.
 208   virtual void reschedule (ACE_Timer_Node_T<TYPE> *);
 209
 210   /// Factory method that allocates a new node (uses operator new if
 211   /// we're *not* preallocating, otherwise uses an internal freelist).
 212   virtual ACE_Timer_Node_T<TYPE> *alloc_node (void);
 213
 214   /**
 215    * Factory method that frees a previously allocated node (uses
 216    * operator delete if we're *not* preallocating, otherwise uses an
 217    * internal freelist).
 218    */
 219   virtual void free_node (ACE_Timer_Node_T<TYPE> *);
 220
 221 private:
 222   /// Remove and return the @a sloth ACE_Timer_Node and restore the
 223   /// heap property.
 224   ACE_Timer_Node_T<TYPE> *remove (size_t slot);
 225
 226   /// Insert @a new_node into the heap and restore the heap property.
 227   void insert (ACE_Timer_Node_T<TYPE> *new_node);
 228
 229   /**
 230    * Doubles the size of the heap and the corresponding timer_ids array.
 231    * If preallocation is used, will also double the size of the
 232    * preallocated array of ACE_Timer_Nodes.
 233    */
 234   void grow_heap (void);
 235
 236   /// Restore the heap property, starting at @a slot.
 237   void reheap_up (ACE_Timer_Node_T<TYPE> *new_node,
 238                   size_t slot,
 239                   size_t parent);
 240
 241   /// Restore the heap property, starting at @a slot.
 242   void reheap_down (ACE_Timer_Node_T<TYPE> *moved_node,
 243                     size_t slot,
 244                     size_t child);
 245
 246   /// Copy @a moved_node into the @a slot slot of <heap_> and move
 247   /// @a slot into the corresponding slot in the <timer_id_> array.
 248   void copy (size_t slot, ACE_Timer_Node_T<TYPE> *moved_node);
 249
 250   /**
 251    * Returns a timer id that uniquely identifies this timer.  This id
 252    * can be used to cancel a timer via the <cancel (int)> method.  The
 253    * timer id returned from this method will never == -1 to avoid
 254    * conflicts with other failure return values.
 255    */
 256   long timer_id (void);
 257
 258   /// Pops and returns a new timer id from the freelist.
 259   long pop_freelist (void);
 260
 261   /// Pushes @a old_id onto the freelist.
 262   void push_freelist (long old_id);
 263
 264   /// Maximum size of the heap.
 265   size_t max_size_;
 266
 267   /// Current size of the heap.
 268   size_t cur_size_;
 269
 270   /// Number of heap entries in transition (removed from the queue, but
 271   /// not freed) and may be rescheduled or freed.
 272   size_t cur_limbo_;
 273
 274   /// Iterator used to expire timers.
 275   HEAP_ITERATOR *iterator_;
 276
 277   /**
 278    * Current contents of the Heap, which is organized as a "heap" of
 279    * ACE_Timer_Node *'s.  In this context, a heap is a "partially
 280    * ordered, almost complete" binary tree, which is stored in an
 281    * array.
 282    */
 283   ACE_Timer_Node_T<TYPE> **heap_;
 284
 285   /**
 286    * An array of "pointers" that allows each ACE_Timer_Node in the
 287    * <heap_> to be located in O(1) time.  Basically, <timer_id_[i]>
 288    * contains the slot in the <heap_> array where an ACE_Timer_Node
 289    * * with timer id \<i\> resides.  Thus, the timer id passed back from
 290    * <schedule> is really a slot into the <timer_ids> array.  The
 291    * <timer_ids_> array serves two purposes: negative values are
 292    * indications of free timer IDs, whereas positive values are
 293    * "pointers" into the <heap_> array for assigned timer IDs.
 294    */
 295   ssize_t *timer_ids_;
 296
 297   /// "Pointer" to the element in the <timer_ids_> array that was
 298   /// last given out as a timer ID.
 299   size_t timer_ids_curr_;
 300
 301   /// Index representing the lowest timer ID that has been freed. When
 302   /// the timer_ids_next_ value wraps around, it starts back at this
 303   /// point.
 304   size_t timer_ids_min_free_;
 305
 306   /**
 307    * If this is non-0, then we preallocate <max_size_> number of
 308    * ACE_Timer_Node objects in order to reduce dynamic allocation
 309    * costs.  In auto-growing implementation, this points to the
 310    * last array of nodes allocated.
 311    */
 312   ACE_Timer_Node_T<TYPE> *preallocated_nodes_;
 313
 314   /// This points to the head of the <preallocated_nodes_> freelist,
 315   /// which is organized as a stack.
 316   ACE_Timer_Node_T<TYPE> *preallocated_nodes_freelist_;
 317
 318   /// Set of pointers to the arrays of preallocated timer nodes.
 319   /// Used to delete the allocated memory when required.
 320   ACE_Unbounded_Set<ACE_Timer_Node_T<TYPE> *> preallocated_node_set_;
 321
 322   // = Don't allow these operations for now.
 323   ACE_UNIMPLEMENTED_FUNC (ACE_Timer_Heap_T (const ACE_Timer_Heap_T<TYPE, FUNCTOR, ACE_LOCK> &))
 324   ACE_UNIMPLEMENTED_FUNC (void operator= (const ACE_Timer_Heap_T<TYPE, FUNCTOR, ACE_LOCK> &))
 325 };
 326
 327 ACE_END_VERSIONED_NAMESPACE_DECL
 328
 329 #if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
 330 #include "ace/Timer_Heap_T.cpp"
 331 #endif /* ACE_TEMPLATES_REQUIRE_SOURCE */
 332
 333 #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
 334 #pragma implementation ("Timer_Heap_T.cpp")
 335 #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */
 336
 337 #include /**/ "ace/post.h"
 338 #endif /* ACE_TIMER_HEAP_T_H */