diff options
| -rw-r--r-- | ChangeLog-97a | 6 | ||||
| -rw-r--r-- | ace/LSOCK_Stream.h | 4 | ||||
| -rw-r--r-- | ace/Timer_Heap.cpp | 143 | ||||
| -rw-r--r-- | ace/Timer_Heap.h | 31 | ||||
| -rw-r--r-- | ace/Timer_List.cpp | 6 | ||||
| -rw-r--r-- | ace/Timer_List.h | 12 | ||||
| -rw-r--r-- | ace/Timer_Queue.h | 2 | ||||
| -rw-r--r-- | tests/Timer_Queue_Test.cpp | 94 |
8 files changed, 195 insertions, 103 deletions
diff --git a/ChangeLog-97a b/ChangeLog-97a index 6a2006ca745..79d662aa670 100644 --- a/ChangeLog-97a +++ b/ChangeLog-97a @@ -1,3 +1,9 @@ +Mon Jan 13 00:17:50 1997 Douglas C. Schmidt <schmidt@flamenco.cs.wustl.edu> + + * ace/LSOCK_Stream.h: Added a new typedef for PEER_ADDR that is + associated with ACE_UNIX_Addr. Thanks to Mark Rabotnikov + <mark@usp.elscintcorp.co.il> for suggesting this. + Sun Jan 12 16:59:52 1997 Douglas C. Schmidt <schmidt@flamenco.cs.wustl.edu> * ace/Timer_List.cpp (schedule): Cleanup the code so that (1) diff --git a/ace/LSOCK_Stream.h b/ace/LSOCK_Stream.h index ac8448fc13d..4903787777e 100644 --- a/ace/LSOCK_Stream.h +++ b/ace/LSOCK_Stream.h @@ -19,6 +19,7 @@ #define ACE_LOCAL_SOCK_STREAM_H #include "ace/SOCK_Stream.h" +#include "ace/UNIX_Addr.h" #include "ace/LSOCK.h" #if !defined (ACE_LACKS_UNIX_DOMAIN_SOCKETS) @@ -41,6 +42,9 @@ public: void set_handle (ACE_HANDLE fd); // Overrides set_handle from the base classes. + // = Meta-type info + typedef ACE_UNIX_Addr PEER_ADDR; + void dump (void) const; // Dump the state of an object. diff --git a/ace/Timer_Heap.cpp b/ace/Timer_Heap.cpp index b69872928eb..f32ab68bf88 100644 --- a/ace/Timer_Heap.cpp +++ b/ace/Timer_Heap.cpp @@ -14,15 +14,9 @@ ACE_Timer_Heap_Iterator::next (ACE_Timer_Node *&node, return 0; else { - node = this->timer_heap_.heap_[0]; + // Remove the first item and restore the heap property. - // Transfer the last element in the heap to the front and - // restore the heap property. - - this->timer_heap_.heap_[0] = - this->timer_heap_.heap_[--this->timer_heap_.cur_size_]; - - this->timer_heap_.reheap_down (); + node = this->timer_heap_.remove (0); return 1; } } @@ -72,49 +66,93 @@ ACE_Timer_Heap::dump (void) const this->heap_[index]->dump (); } -void -ACE_Timer_Heap::reheap_down (void) +ACE_Timer_Node * +ACE_Timer_Heap::remove (int index) +{ + ACE_Timer_Node *result = this->heap_[index]; + + this->cur_size_--; + + // Only try to reheapify if we're not deleting the last entry. + + if (index < this->cur_size_) + { + // Move the end node to the location being removed. + this->heap_[index] = this->heap_[this->cur_size_]; + + ACE_Timer_Node *moved_node = this->heap_[index]; + + // If we're at the top there's no place to go but down! + if (index == 0) + this->reheap_down (moved_node, 1); + + // If the moved_node->time_value_ is smaller than its parent it + // needs be moved up the heap. + else if (moved_node->timer_value_ < this->heap_[(index - 1) / 2]->timer_value_) + this->reheap_up (moved_node); + + // Call <reheap_down>, which will reheapify if the + // moved_node->time_value_ is larger than either of its children + // (who start at location <index + index>). + else + this->reheap_down (moved_node, index + index); + } + + return result; +} + +void +ACE_Timer_Heap::reheap_down (ACE_Timer_Node *moved_node, + int child_index) { int parent = 0; - int child = 1; - ACE_Timer_Node *temp = this->heap_[parent]; - // Restore the heap property. + // Restore the heap property after a deletion. - while (child < this->cur_size_) + for (int child = child_index; + child < this->cur_size_; + child += child + 1) // Multiple child by 2 and add 1. { + // Choose the smaller of the two children. if (child + 1 < this->cur_size_ - && this->heap_[child + 1]->timer_value_ > this->heap_[child]->timer_value_) + && this->heap_[child + 1]->timer_value_ < this->heap_[child]->timer_value_) child++; - if (this->heap_[child]->timer_value_ > temp->timer_value_) + // Perform a swap if the child has a larger timeout value than + // the front node. + if (this->heap_[child]->timer_value_ < moved_node->timer_value_) { this->heap_[parent] = this->heap_[child]; parent = child; - // Multiple child by 2 and add 1. - child += child + 1; } else break; } - this->heap_[parent] = temp; + // Insert moved_node into its final resting place. + this->heap_[parent] = moved_node; +} + +void +ACE_Timer_Heap::insert (ACE_Timer_Node *new_node) +{ + this->reheap_up (new_node); + this->cur_size_++; } void -ACE_Timer_Heap::reheap_up (void) +ACE_Timer_Heap::reheap_up (ACE_Timer_Node *new_node) { int parent; - int child = this->cur_size_ - 1; - ACE_Timer_Node *temp = this->heap_[child]; - - // Restore the heap property. + int child = this->cur_size_; + + // Restore the heap property after an insertion. while (child > 0) { parent = (child - 1) / 2; - if (temp->timer_value_ < this->heap_[parent]->timer_value_) + if (new_node->timer_value_ < this->heap_[parent]->timer_value_) { this->heap_[child] = this->heap_[parent]; child = parent; @@ -123,7 +161,7 @@ ACE_Timer_Heap::reheap_up (void) break; } - this->heap_[child] = temp; + this->heap_[child] = new_node; } // Reschedule a periodic timer. This function must be called with the @@ -134,10 +172,8 @@ ACE_Timer_Heap::reschedule (ACE_Timer_Node *expired) { ACE_TRACE ("ACE_Timer_Heap::reschedule"); - // Insert the <expired> node into the end of the heap and restore - // the heap property. - this->heap_[this->cur_size_++] = expired; - this->reheap_up (); + // Restore the heap property. + this->insert (expired); } // Insert a new handler that expires at time future_time; if interval @@ -174,7 +210,7 @@ ACE_Timer_Heap::schedule (ACE_Event_Handler *handler, timer_id), -1); - this->reheap_up (temp); + this->insert (temp); } return timer_id; @@ -184,12 +220,33 @@ ACE_Timer_Heap::schedule (ACE_Event_Handler *handler, // <timer_id> from the timer queue. int -ACE_Timer_Heap::cancel (int timer_id, const void **arg) +ACE_Timer_Heap::cancel (int timer_id, + const void **arg) { ACE_TRACE ("ACE_Timer_Heap::cancel"); ACE_MT (ACE_GUARD_RETURN (ACE_Recursive_Thread_Mutex, ace_mon, this->lock_, -1)); - return 0; + int i; + + // Try to locate the ACE_Timer_Node that matches the timer_id. + + for (i = 0; + i < this->cur_size_ && this->heap_[i]->timer_id_ != timer_id; + i++) + continue; + + if (i == this->cur_size_) + return 0; + else + { + ACE_Timer_Node *temp = this->remove (i); + + if (arg != 0) + *arg = temp->arg_; + + delete temp; + return 1; + } } // Locate and remove all values of <handler> from the timer queue. @@ -200,5 +257,23 @@ ACE_Timer_Heap::cancel (ACE_Event_Handler *handler) ACE_TRACE ("ACE_Timer_Heap::cancel"); ACE_MT (ACE_GUARD_RETURN (ACE_Recursive_Thread_Mutex, ace_mon, this->lock_, -1)); - return 0; + int number_of_cancellations = 0; + + // Try to locate the ACE_Timer_Node that matches the timer_id. + + for (int i = 0; + i < this->cur_size_; + ) + { + if (this->heap_[i]->handler_ == handler) + { + ACE_Timer_Node *temp = this->remove (i); + delete temp; + number_of_cancellations++; + } + else + i++; + } + + return number_of_cancellations; } diff --git a/ace/Timer_Heap.h b/ace/Timer_Heap.h index 873b7985509..40e7ea8588a 100644 --- a/ace/Timer_Heap.h +++ b/ace/Timer_Heap.h @@ -103,22 +103,6 @@ public: // Returns 1 if cancellation succeeded and 0 if the <timer_id> // wasn't found. - virtual int expire (const ACE_Time_Value ¤t_time); - // Run the <handle_timeout> method for all Timers whose values are - // <= <cur_time>. This does not account for <timer_skew>. Returns - // the number of <Event_Handler>s for which <handle_timeout> was - // called. - - virtual int expire (void); - // Run the <handle_timeout> method for all Timers whose values are - // <= <ACE_OS::gettimeofday>. Also accounts for <timer_skew>. - // Returns the number of <Event_Handler>s for which <handle_timeout> - // was called. - - virtual ACE_Time_Value *calculate_timeout (ACE_Time_Value *max); - // Determine the next event to timeout. Returns <max> if there are - // no pending timers or if all pending timers are longer than max. - virtual void dump (void) const; // Dump the state of an object. @@ -130,11 +114,18 @@ protected: // Returns a pointer to this <ACE_Timer_Queue>'s iterator. private: - void reheap_down (void); - // Called after a deletion to restore the heap property. + ACE_Timer_Node *remove (int index); + // Remove and return the <index>th <ACE_Timer_Node> and restore the + // heap property. + + void insert (ACE_Timer_Node *new_node); + // Insert <new_node> into the heap and restore the heap property. + + void reheap_up (ACE_Timer_Node *new_node); + // Restore the heap property. - void reheap_up (void); - // Called after an insertion to restore the heap property. + void reheap_down (ACE_Timer_Node *moved_node, int child_index); + // Restore the heap property, starting at <child_index>. size_t max_size_; // Maximum size of the heap. diff --git a/ace/Timer_List.cpp b/ace/Timer_List.cpp index 5b0be11591a..0d9cdd53047 100644 --- a/ace/Timer_List.cpp +++ b/ace/Timer_List.cpp @@ -1,11 +1,5 @@ #include "ace/Timer_List.h" -int -ACE_Timer_List::expire (void) -{ - return this->ACE_Timer_Queue::expire (); -} - ACE_Timer_List_Iterator::ACE_Timer_List_Iterator (ACE_Timer_List &list) : timer_list_ (list) { diff --git a/ace/Timer_List.h b/ace/Timer_List.h index 14b4c38b6e6..43c6b141f7b 100644 --- a/ace/Timer_List.h +++ b/ace/Timer_List.h @@ -109,18 +109,6 @@ public: // Returns 1 if cancellation succeeded and 0 if the <timer_id> // wasn't found. - virtual int expire (const ACE_Time_Value ¤t_time); - // Run the <handle_timeout> method for all Timers whose values are - // <= <cur_time>. This does not account for <timer_skew>. Returns - // the number of <Event_Handler>s for which <handle_timeout> was - // called. - - virtual int expire (void); - // Run the <handle_timeout> method for all Timers whose values are - // <= <ACE_OS::gettimeofday>. Also accounts for <timer_skew>. - // Returns the number of <Event_Handler>s for which <handle_timeout> - // was called. - private: virtual void reschedule (ACE_Timer_Node *); // Reschedule an "interval" <ACE_Timer_Node>. diff --git a/ace/Timer_Queue.h b/ace/Timer_Queue.h index 6c70cccd595..454ba44f0e1 100644 --- a/ace/Timer_Queue.h +++ b/ace/Timer_Queue.h @@ -150,7 +150,7 @@ public: // Returns 1 if cancellation succeeded and 0 if the <timer_id> // wasn't found. - virtual int expire (const ACE_Time_Value ¤t_time) = 0; + virtual int expire (const ACE_Time_Value ¤t_time); // Run the <handle_timeout> method for all Timers whose values are // <= <cur_time>. This does not account for <timer_skew>. Returns // the number of <Event_Handler>s for which <handle_timeout> was diff --git a/tests/Timer_Queue_Test.cpp b/tests/Timer_Queue_Test.cpp index 2ff194ba59f..356ae3f9add 100644 --- a/tests/Timer_Queue_Test.cpp +++ b/tests/Timer_Queue_Test.cpp @@ -16,15 +16,20 @@ // command line arguments are needed to run the test. // // = AUTHOR -// Prashant Jain +// Prashant Jain and Douglas C. Schmidt // // ============================================================================ +#include "ace/Profile_Timer.h" #include "ace/Timer_List.h" #include "ace/Timer_Heap.h" #include "test_config.h" -const int MAX_ITERATIONS = ACE_DEFAULT_MAX_TIMERS - 1; +// Number of iterations for the performance tests. +static const int MAX_ITERATIONS = ACE_DEFAULT_MAX_TIMERS; + +// Keep track of the timer ids that were assigned to us. +static int timer_ids[MAX_ITERATIONS]; class Example_Handler : public ACE_Event_Handler { @@ -42,29 +47,29 @@ test_functionality (ACE_Timer_Queue *tq) { Example_Handler eh; - ACE_ASSERT (tq.is_empty ()); + ACE_ASSERT (tq->is_empty ()); ACE_ASSERT (ACE_Time_Value::zero == ACE_Time_Value (0)); int timer_id; - timer_id = tq.schedule (&eh, (const void *) 1, ACE_OS::gettimeofday ()); + timer_id = tq->schedule (&eh, (const void *) 1, ACE_OS::gettimeofday ()); ACE_ASSERT (timer_id != -1); - ACE_ASSERT (tq.schedule (&eh, (const void *) 42, + ACE_ASSERT (tq->schedule (&eh, (const void *) 42, ACE_OS::gettimeofday ()) != -1); - ACE_ASSERT (tq.schedule (&eh, (const void *) 42, + ACE_ASSERT (tq->schedule (&eh, (const void *) 42, ACE_OS::gettimeofday ()) != -1); - ACE_ASSERT (tq.cancel (timer_id) == 1); - ACE_ASSERT (!tq.is_empty ()); + ACE_ASSERT (tq->cancel (timer_id) == 1); + ACE_ASSERT (!tq->is_empty ()); - ACE_ASSERT (tq.expire (ACE_OS::gettimeofday () == 1)); + ACE_ASSERT (tq->expire () == 2); - ACE_ASSERT (tq.schedule (&eh, (const void *) 4, ACE_OS::gettimeofday + ACE_ASSERT (tq->schedule (&eh, (const void *) 4, ACE_OS::gettimeofday ()) != -1); - ACE_ASSERT (tq.schedule (&eh, (const void *) 5, ACE_OS::gettimeofday + ACE_ASSERT (tq->schedule (&eh, (const void *) 5, ACE_OS::gettimeofday ()) != -1); - ACE_ASSERT (tq.cancel (&eh) == 2); - ACE_ASSERT (tq.is_empty ()); - ACE_ASSERT (tq.expire (ACE_OS::gettimeofday ()) == 0); + ACE_ASSERT (tq->cancel (&eh) == 2); + ACE_ASSERT (tq->is_empty ()); + ACE_ASSERT (tq->expire () == 0); } static void @@ -78,11 +83,19 @@ test_performance (ACE_Timer_Queue *tq, 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. + timer.start (); - // Test the amount of time required to schedule all the timers. for (i = 0; i < MAX_ITERATIONS; i++) - tq->schedule (&eh, (const void *) 42, ACE_OS::gettimeofday ()); + { + timer_ids[i] = tq->schedule (&eh, (const void *) 42, ACE_OS::gettimeofday ()); + ACE_ASSERT (timer_ids[i] != -1); + } + + ACE_ASSERT (!tq->is_empty ()); + + timer.stop (); ACE_Profile_Timer::ACE_Elapsed_Time et; @@ -95,21 +108,19 @@ test_performance (ACE_Timer_Queue *tq, ACE_DEBUG ((LM_DEBUG, "time per call = %f usecs\n", (et.real_time / double (MAX_ITERATIONS)) * 1000000)); - timer.start (); - - int timer_id = tq->schedule (&eh, (const void *) 42, - ACE_OS::gettimeofday ()); + // Test the amount of time required to cancel all the timers. We + // start from the "back" in order to measure the worst case + // performance for the <ACE_Timer_List> (which uses linear search). - ACE_ASSERT (timer_id); + timer.start (); - // Test the amount of time required to cancel all the timers (this - // takes advantage of the fact that <timer_ids> are always allocated - // contiguously starting at 0. - for (i = 0; i < MAX_ITERATIONS + 1; i++) - tq->cancel (timer_id--); + for (i = MAX_ITERATIONS - 1; i >= 0; i--) + tq->cancel (timer_ids[i]); ACE_ASSERT (tq->is_empty ()); + timer.stop (); + timer.elapsed_time (et); ACE_DEBUG ((LM_DEBUG, "time to cancel %d timers for %s\n", @@ -119,6 +130,29 @@ test_performance (ACE_Timer_Queue *tq, ACE_DEBUG ((LM_DEBUG, "time per call = %f usecs\n", (et.real_time / double (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, ACE_OS::gettimeofday ()) != -1); + + ACE_ASSERT (!tq->is_empty ()); + + // Expire all the timers. + tq->expire (); + + timer.stop (); + + timer.elapsed_time (et); + + ACE_DEBUG ((LM_DEBUG, "time to schedule and expire %d timers for %s\n", + MAX_ITERATIONS, test_name)); + ACE_DEBUG ((LM_DEBUG, "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, "time per call = %f usecs\n", + (et.real_time / double (MAX_ITERATIONS)) * 1000000)); } struct Timer_Queues @@ -133,9 +167,9 @@ struct Timer_Queues static Timer_Queues timer_queues[] = { { new ACE_Timer_List, "ACE_Timer_List" }, - { new ACE_Timer_Heap, "ACE_Timer_Queue" }, - { 0, 0 }; -} + { new ACE_Timer_Heap, "ACE_Timer_Heap" }, + { 0, 0 }, +}; int main (int, char *[]) @@ -145,7 +179,7 @@ main (int, char *[]) for (int i = 0; timer_queues[i].name_ != 0; i++) { test_performance (timer_queues[i].queue_, timer_queues[i].name_); - test_functionality (timer_queues[i].queue_, timer_queues[i].name_); + test_functionality (timer_queues[i].queue_); delete timer_queues[i].queue_; } |