From 1496689c75876a0b530b5607fb613c69e9e691a0 Mon Sep 17 00:00:00 2001 From: schmidt Date: Sat, 26 Apr 1997 18:48:06 +0000 Subject: *** empty log message *** --- ace/Timer_Heap_T.h | 241 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 241 insertions(+) create mode 100644 ace/Timer_Heap_T.h (limited to 'ace/Timer_Heap_T.h') diff --git a/ace/Timer_Heap_T.h b/ace/Timer_Heap_T.h new file mode 100644 index 00000000000..3c212c991f1 --- /dev/null +++ b/ace/Timer_Heap_T.h @@ -0,0 +1,241 @@ +/* -*- C++ -*- */ +// $Id$ + +// ============================================================================ +// +// = LIBRARY +// ace +// +// = FILENAME +// Timer_Heap_T.h +// +// = AUTHOR +// Doug Schmidt +// +// ============================================================================ + +#if !defined (ACE_TIMER_HEAP_T_H) +#define ACE_TIMER_HEAP_T_H + +#include "ace/Timer_Queue.h" +#include "ace/Set.h" + +// Forward declaration +template +class ACE_Timer_Heap_T; + +template +class ACE_Timer_Heap_Iterator_T : public ACE_Timer_Queue_Iterator_T + // = TITLE + // Iterates over an . + // + // = DESCRIPTION + // This is a special type of iterator that "advances" by moving + // the head of the timer queue up by one every time. +{ +public: + ACE_Timer_Heap_Iterator_T (ACE_Timer_Heap_T &); + // Constructor. + + virtual int next (NODE *&timer_node, + const ACE_Time_Value &cur_time); + // Pass back the next that hasn't been seen yet, if its + // <= . In addition, moves the timer queue + // forward by one node. Returns 0 when all have been + // seen, else 1. + +protected: + ACE_Timer_Heap_T &timer_heap_; + // Pointer to the that we are iterating over. +}; + +template +class ACE_Timer_Heap_T : public ACE_Timer_Queue_T + // = TITLE + // Provides a very fast and predictable timer implementation. + // + // = DESCRIPTION + // + // This implementation uses a heap-based callout queue of + // absolute times. Therefore, in the average and worst case, + // scheduling, canceling, and expiring timers is O(log N) (where + // N is the total number of timers). In addition, we can also + // preallocate as many as there are slots in + // the heap. This allows us to completely remove the need for + // dynamic memory allocation, which is important for real-time + // systems. +{ +public: + typedef ACE_Timer_Heap_Iterator_T HEAP_ITERATOR; + friend HEAP_ITERATOR; + + typedef ACE_Timer_Queue_T INHERITED; + + // = Initialization and termination methods. + ACE_Timer_Heap_T (size_t size = ACE_DEFAULT_TIMERS, + int preallocated = 0, + FUNCTOR *upcall_functor = 0); + // The Constructor creates a heap with elements. If + // is non-0 then we'll pre-allocate all the memory + // for the . This saves time and is more + // predictable (though it requires more space). Otherwise, we'll + // just allocate the nodes as we need them. + + virtual ~ACE_Timer_Heap_T (void); + // Destructor. + + virtual int is_empty (void) const; + // True if heap is empty, else false. + + virtual const ACE_Time_Value &earliest_time (void) const; + // Returns the time of the earlier node in the Timer_Queue. + + virtual int schedule (const TYPE &type, + const void *act, + const ACE_Time_Value &delay, + const ACE_Time_Value &interval = ACE_Time_Value::zero); + // Schedule that will expire after amount of time. + // If it expires then is passed in as the value to the + // . If is != to then it + // is used to reschedule the automatically. This method + // returns a that uniquely identifies the the + // entry in an internal list. This can be used to cancel + // the timer before it expires. The cancellation ensures that + // are unique up to values of greater than 2 billion + // timers. As long as timers don't stay around longer than this + // there should be no problems with accidentally deleting the wrong + // timer. Returns -1 on failure (which is guaranteed never to be a + // valid ). + + virtual int cancel (const TYPE &type, + int dont_call_handle_close = 1); + // Cancel all timer associated with . If is 0 + // then the will be invoked. Returns number of timers + // cancelled. + + virtual int cancel (int timer_id, + const void **act = 0, + int dont_call_handle_close = 1); + // Cancel the single timer that matches the value (which + // was returned from the method). If act is non-NULL + // then it will be set to point to the ``magic cookie'' argument + // passed in when the timer was registered. This makes it possible + // to free up the memory and avoid memory leaks. If is + // 0 then the will be invoked. Returns 1 if cancellation + // succeeded and 0 if the wasn't found. + + virtual void dump (void) const; + // Dump the state of an object. + +protected: + virtual void reschedule (NODE *); + // Reschedule an "interval" . + + virtual ITERATOR &iter (void); + // Returns a pointer to this 's iterator. + + virtual NODE *alloc_node (void); + // Factory method that allocates a new node (uses operator new if + // we're *not* preallocating, otherwise uses an internal freelist). + + virtual void free_node (NODE *); + // Factory method that frees a previously allocated node (uses + // operatord delete if we're *not* preallocating, otherwise uses an + // internal freelist). + +private: + NODE *remove (size_t index); + // Remove and return the th and restore the + // heap property. + + void insert (NODE *new_node); + // Insert into the heap and restore the heap property. + + void grow_heap (void); + // Doubles the size of the heap and the corresponding timer_ids array. + // If preallocation is used, will also double the size of the + // preallocated array of ACE_Timer_Nodes. + + void reheap_up (NODE *new_node, + size_t index, + size_t parent); + // Restore the heap property, starting at . + + void reheap_down (NODE *moved_node, + size_t index, + size_t child); + // Restore the heap property, starting at . + + void copy (int index, NODE *moved_node); + // Copy into the slot of and move + // into the corresponding slot in the array. + + int timer_id (void); + // Returns a timer id that uniquely identifies this timer. This id + // can be used to cancel a timer via the method. The + // timer id returned from this method will never == -1 to avoid + // conflicts with other failure return values. + + int pop_freelist (void); + // Pops and returns a new timer id from the freelist. + + void push_freelist (int old_id); + // Pushes onto the freelist. + + size_t max_size_; + // Maximum size of the heap. + + size_t cur_size_; + // Current size of the heap. + + HEAP_ITERATOR iterator_; + // Iterator used to expire timers. + + NODE **heap_; + // Current contents of the Heap, which is organized as a "heap" of + // *'s. In this context, a heap is a "partially + // ordered, almost complete" binary tree, which is stored in an + // array. + + int *timer_ids_; + // An array of "pointers" that allows each in the + // to be located in O(1) time. Basically, + // contains the index in the array where an + // * with timer id resides. Thus, the timer id passed back from + // is really an index into the array. The + // array serves two purposes: negative values are + // treated as "pointers" for the , whereas positive + // values are treated as "pointers" into the array. + + int timer_ids_freelist_; + // "Pointer" to the first element in the freelist contained within + // the array, which is organized as a stack. + + NODE *preallocated_nodes_; + // If this is non-0, then we preallocate number of + // objects in order to reduce dynamic allocation + // costs. In auto-growing implementation, this points to the + // last array of nodes allocated. + + NODE *preallocated_nodes_freelist_; + // This points to the head of the freelist, + // which is organized as a stack. + + ACE_Unbounded_Set preallocated_node_set_; + // Set of pointers to the arrays of preallocated timer nodes. + // Used to delete the allocated memory when required. + + // = Don't allow these operations for now. + ACE_Timer_Heap_T (const ACE_Timer_Heap_T &); + void operator= (const ACE_Timer_Heap_T &); +}; + +#if defined (ACE_TEMPLATES_REQUIRE_SOURCE) +#include "ace/Timer_Heap_T.cpp" +#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ + +#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) +#pragma implementation ("Timer_Heap_T.cpp") +#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ + +#endif /* ACE_TIMER_HEAP_T_H */ -- cgit v1.2.1