diff options
| -rw-r--r-- | ChangeLog | 14 | ||||
| -rw-r--r-- | ace/Node.cpp | 9 | ||||
| -rw-r--r-- | ace/Node.h | 1 | ||||
| -rw-r--r-- | ace/Unbounded_Set.cpp | 135 | ||||
| -rw-r--r-- | ace/Unbounded_Set.h | 17 | ||||
| -rw-r--r-- | ace/Unbounded_Set.inl | 4 | ||||
| -rw-r--r-- | tests/Makefile | 1 | ||||
| -rw-r--r-- | tests/Makefile.am | 3 | ||||
| -rw-r--r-- | tests/Makefile.bor | 1 | ||||
| -rw-r--r-- | tests/Unbounded_Set_Test.cpp | 69 | ||||
| -rw-r--r-- | tests/Unbounded_Set_Test.icc | 22 |
11 files changed, 260 insertions, 16 deletions
diff --git a/ChangeLog b/ChangeLog index 8715645ffcf..eafc88683fe 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,17 @@ +Mon Mar 24 13:16:29 CET 2003 Oliver Kellogg <oliver.kellogg@sysde.eads.net> + + * ace/Node.{h,cpp}: + * ace/Unbounded_Set.{h,inl,cpp}: + + Fix for Bugzilla bug 1460 supplied by Rudolf Weber + <rfweber@tesionmail.de>, adds a `deleted' flag to ACE_Node, and + adds corresponding management methods to ACE_Unbounded_Set. + + * tests/Unbounded_Set_Test.{cpp,icc}: New. + + * tests/Makefile, tests/Makefile.{am,bor}: + Add Unbounded_Set_Test.cpp, a regression test for bug 1460. + Sat Mar 22 11:58:12 2003 Douglas C. Schmidt <schmidt@tango.doc.wustl.edu> * ace/Configuration.cpp: When remove_section() was called the diff --git a/ace/Node.cpp b/ace/Node.cpp index 91e989d739b..f13b18cde86 100644 --- a/ace/Node.cpp +++ b/ace/Node.cpp @@ -23,14 +23,16 @@ ACE_Node<T>::~ACE_Node (void) template <class T> ACE_Node<T>::ACE_Node (const T &i, ACE_Node<T> *n) : next_ (n), - item_ (i) + item_ (i), + deleted_ (false) { // ACE_TRACE ("ACE_Node<T>::ACE_Node"); } template <class T> ACE_Node<T>::ACE_Node (ACE_Node<T> *n, int) - : next_ (n) + : next_ (n), + deleted_ (false) { // ACE_TRACE ("ACE_Node<T>::ACE_Node"); } @@ -38,7 +40,8 @@ ACE_Node<T>::ACE_Node (ACE_Node<T> *n, int) template <class T> ACE_Node<T>::ACE_Node (const ACE_Node<T> &s) : next_ (s.next_), - item_ (s.item_) + item_ (s.item_), + deleted_ (false) { // ACE_TRACE ("ACE_Node<T>::ACE_Node"); } diff --git a/ace/Node.h b/ace/Node.h index 3d69213bf26..65532c65ec5 100644 --- a/ace/Node.h +++ b/ace/Node.h @@ -63,6 +63,7 @@ private: /// Current value of the item in this node. T item_; + bool deleted_; }; #if defined (ACE_TEMPLATES_REQUIRE_SOURCE) diff --git a/ace/Unbounded_Set.cpp b/ace/Unbounded_Set.cpp index e1cf0708e6a..cc5fc9ea0a1 100644 --- a/ace/Unbounded_Set.cpp +++ b/ace/Unbounded_Set.cpp @@ -88,14 +88,17 @@ ACE_Unbounded_Set<T>::copy_nodes (const ACE_Unbounded_Set<T> &us) for (ACE_Node<T> *curr = us.head_->next_; curr != us.head_; curr = curr->next_) - this->insert_tail (curr->item_); + { + if (!curr->deleted_) + this->insert_tail (curr->item_); + } } template <class T> void ACE_Unbounded_Set<T>::delete_nodes (void) { ACE_Node<T> *curr = this->head_->next_; - + ACE_ASSERT (number_of_iterators_ == 0); // Keep looking until we've hit the dummy node. while (curr != this->head_) @@ -113,6 +116,32 @@ ACE_Unbounded_Set<T>::delete_nodes (void) this->head_->next_ = this->head_; } +template <class T> void +ACE_Unbounded_Set<T>::cleanup () +{ + /// curr is the address of the chaining + ACE_Node<T> **curr = &(this->head_->next_); + ACE_ASSERT (number_of_iterators_ == 0); + + // Keep looking until we've hit the dummy node. + while (*curr != this->head_) + { + if ((*curr)->deleted_) + { + ACE_Node<T> *temp = *curr; + *curr = (*curr)->next_; // skip the deleted, curr is still the same + ACE_DES_FREE_TEMPLATE (temp, + this->allocator_->free, + ACE_Node, + <T>); + } + else + { + curr = &((*curr)->next_); + } + } +} + template <class T> ACE_Unbounded_Set<T>::~ACE_Unbounded_Set (void) { @@ -132,7 +161,8 @@ template <class T> ACE_Unbounded_Set<T>::ACE_Unbounded_Set (ACE_Allocator *alloc) : head_ (0), cur_size_ (0), - allocator_ (alloc) + allocator_ (alloc), + number_of_iterators_ (0) { // ACE_TRACE ("ACE_Unbounded_Set<T>::ACE_Unbounded_Set"); @@ -150,7 +180,8 @@ template <class T> ACE_Unbounded_Set<T>::ACE_Unbounded_Set (const ACE_Unbounded_Set<T> &us) : head_ (0), cur_size_ (0), - allocator_ (us.allocator_) + allocator_ (us.allocator_), + number_of_iterators_ (0) { ACE_TRACE ("ACE_Unbounded_Set<T>::ACE_Unbounded_Set"); @@ -186,7 +217,7 @@ ACE_Unbounded_Set<T>::find (const T &item) const ACE_Node<T> *temp = this->head_->next_; // Keep looping until we find the item. - while (!(temp->item_ == item)) + while (!(temp->item_ == item && !temp->deleted_)) temp = temp->next_; // If we found the dummy node then it's not really there, otherwise, @@ -221,14 +252,22 @@ ACE_Unbounded_Set<T>::remove (const T &item) return -1; // Item was not found. else { - ACE_Node<T> *temp = curr->next_; - // Skip over the node that we're deleting. - curr->next_ = temp->next_; this->cur_size_--; - ACE_DES_FREE_TEMPLATE (temp, - this->allocator_->free, - ACE_Node, - <T>); + ACE_Node<T> *temp = curr->next_; + if(number_of_iterators_>0) + { + temp->deleted_=true; + } + else + { + // Skip over the node that we're deleting. + curr->next_ = temp->next_; + + ACE_DES_FREE_TEMPLATE (temp, + this->allocator_->free, + ACE_Node, + <T>); + } return 0; } } @@ -247,6 +286,20 @@ ACE_Unbounded_Set<T>::end (void) return ACE_Unbounded_Set_Iterator<T> (*this, 1); } +template <class T> void +ACE_Unbounded_Set<T>::iterator_add (void) +{ + number_of_iterators_++; +} + +template <class T> void +ACE_Unbounded_Set<T>::iterator_leave (void) +{ + ACE_ASSERT (number_of_iterators_>0); + number_of_iterators_--; + if (number_of_iterators_==0) + cleanup (); +} ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Set_Iterator) @@ -262,6 +315,32 @@ ACE_Unbounded_Set_Iterator<T>::ACE_Unbounded_Set_Iterator (ACE_Unbounded_Set<T> set_ (&s) { // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::ACE_Unbounded_Set_Iterator"); + set_->iterator_add(); +} + +template <class T> +ACE_Unbounded_Set_Iterator<T>::ACE_Unbounded_Set_Iterator (const ACE_Unbounded_Set_Iterator<T> &o) + : current_ (o.current_), set_ (o.set_) +{ + set_->iterator_add (); +} + +template <class T> void +ACE_Unbounded_Set_Iterator<T>::operator= (const ACE_Unbounded_Set_Iterator &o) +{ + if (this == &o) + return; + set_->iterator_leave (); + this->set_ = o.set_; + this->current_ = o.current_; + set_->iterator_add (); +} + + +template <class T> +ACE_Unbounded_Set_Iterator<T>::~ACE_Unbounded_Set_Iterator () +{ + set_->iterator_leave (); } template <class T> int @@ -269,6 +348,8 @@ ACE_Unbounded_Set_Iterator<T>::advance (void) { // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::advance"); this->current_ = this->current_->next_; + while(this->current_->deleted_ && this->current_ != this->set_->head_) + this->current_ = this->current_->next_; return this->current_ != this->set_->head_; } @@ -277,6 +358,8 @@ ACE_Unbounded_Set_Iterator<T>::first (void) { // ACE_TRACE ("ACE_Unbounded_Set_Iterator<T>::first"); this->current_ = this->set_->head_->next_; + while(this->current_->deleted_ && this->current_ != this->set_->head_) + this->current_ = this->current_->next_; return this->current_ != this->set_->head_; } @@ -365,6 +448,30 @@ ACE_Unbounded_Set_Const_Iterator<T>::ACE_Unbounded_Set_Const_Iterator (const ACE set_ (&s) { // ACE_TRACE ("ACE_Unbounded_Set_Const_Iterator<T>::ACE_Unbounded_Set_Const_Iterator"); + set_->iterator_add (); +} + +template <class T> +ACE_Unbounded_Set_Const_Iterator<T>::ACE_Unbounded_Set_Const_Iterator(const ACE_Unbounded_Set_Const_Iterator<T> &o):current_(o.current_),set_(o.set_) +{ + set_->iterator_add (); +} + +template <class T> +void ACE_Unbounded_Set_Const_Iterator<T>::operator=(const ACE_Unbounded_Set_Const_Iterator& o) +{ + if (this == &o) + return; + set_->iterator_leave (); + this->set_ = o.set_; + this->current_ = o.current_; + set_->iterator_add (); +} + +template <class T> +ACE_Unbounded_Set_Const_Iterator<T>::~ACE_Unbounded_Set_Const_Iterator() +{ + set_->iterator_leave (); } template <class T> int @@ -372,6 +479,8 @@ ACE_Unbounded_Set_Const_Iterator<T>::advance (void) { // ACE_TRACE ("ACE_Unbounded_Set_Const_Iterator<T>::advance"); this->current_ = this->current_->next_; + while(this->current_->deleted_ && this->current_ != this->set_->head_) + this->current_ = this->current_->next_; return this->current_ != this->set_->head_; } @@ -380,6 +489,8 @@ ACE_Unbounded_Set_Const_Iterator<T>::first (void) { // ACE_TRACE ("ACE_Unbounded_Set_Const_Iterator<T>::first"); this->current_ = this->set_->head_->next_; + while(this->current_->deleted_ && this->current_ != this->set_->head_) + this->current_ = this->current_->next_; return this->current_ != this->set_->head_; } diff --git a/ace/Unbounded_Set.h b/ace/Unbounded_Set.h index d4c882b6f5c..5978cbc819e 100644 --- a/ace/Unbounded_Set.h +++ b/ace/Unbounded_Set.h @@ -33,6 +33,9 @@ class ACE_Unbounded_Set_Iterator public: // = Initialization method. ACE_Unbounded_Set_Iterator (ACE_Unbounded_Set<T> &s, int end = 0); + ACE_Unbounded_Set_Iterator (const ACE_Unbounded_Set_Iterator &o); + void operator= (const ACE_Unbounded_Set_Iterator &o); + ~ACE_Unbounded_Set_Iterator (); // = Iteration methods. @@ -92,6 +95,9 @@ class ACE_Unbounded_Set_Const_Iterator public: // = Initialization method. ACE_Unbounded_Set_Const_Iterator (const ACE_Unbounded_Set<T> &s, int end = 0); + ACE_Unbounded_Set_Const_Iterator (const ACE_Unbounded_Set_Const_Iterator& o); + void operator= (const ACE_Unbounded_Set_Const_Iterator& o); + ~ACE_Unbounded_Set_Const_Iterator (); // = Iteration methods. @@ -278,6 +284,11 @@ public: ACE_Unbounded_Set_Iterator<T> begin (void); ACE_Unbounded_Set_Iterator<T> end (void); + /// An Iterator has to register itself here. + void iterator_add (); + /// An Iterator has to unregister itself here. + void iterator_leave (); + /// Declare the dynamic allocation hooks. ACE_ALLOC_HOOK_DECLARE; @@ -288,6 +299,9 @@ private: /// Copy nodes into this set. void copy_nodes (const ACE_Unbounded_Set<T> &); + /// Really delete all nodes marked for deletion. + void cleanup (); + /// Head of the linked list of Nodes. ACE_Node<T> *head_; @@ -296,6 +310,9 @@ private: /// Allocation strategy of the set. ACE_Allocator *allocator_; + + /// Number of iterators working on this set. + int number_of_iterators_; }; #if defined (__ACE_INLINE__) diff --git a/ace/Unbounded_Set.inl b/ace/Unbounded_Set.inl index 3f71cd2b498..fff0a0fcbb5 100644 --- a/ace/Unbounded_Set.inl +++ b/ace/Unbounded_Set.inl @@ -5,7 +5,9 @@ template <class T> ACE_INLINE int ACE_Unbounded_Set<T>::is_empty (void) const { ACE_TRACE ("ACE_Unbounded_Set<T>::is_empty"); - return this->head_ == this->head_->next_; + // Does not work if deleted elements are in the list: + // return this->head_ == this->head_->next_; + return size() == 0; } template <class T> ACE_INLINE int diff --git a/tests/Makefile b/tests/Makefile index 0943648d86d..c95c3fcdbc1 100644 --- a/tests/Makefile +++ b/tests/Makefile @@ -118,6 +118,7 @@ BIN = ACE_Test \ TSS_Test \ Vector_Test \ UPIPE_SAP_Test \ + Unbounded_Set_Test \ Upgradable_RW_Test BIN2 = Naming_Test \ diff --git a/tests/Makefile.am b/tests/Makefile.am index e6aa65cee7a..6be5d163752 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -130,6 +130,7 @@ check_PROGRAMS = \ Timeprobe_Test \ Timer_Queue_Test \ UPIPE_SAP_Test \ + Unbounded_Set_Test \ Upgradable_RW_Test \ \ Naming_Test \ @@ -304,6 +305,8 @@ UPIPE_SAP_Test_SOURCES = UPIPE_SAP_Test.cpp Upgradable_RW_Test_SOURCES = Upgradable_RW_Test.cpp \ Upgradable_RW_Test.h +Unbounded_Set_Test_SOURCES = Unbounded_Set_Test.cpp + XtReactor_Test_SOURCES = XtReactor_Test.cpp XtReactor_Test_LDADD = $(top_builddir)/ace/libACE.la @XTREACTOR_TEST_XLIBS@ diff --git a/tests/Makefile.bor b/tests/Makefile.bor index c7ea677ec08..07eddbc2036 100644 --- a/tests/Makefile.bor +++ b/tests/Makefile.bor @@ -120,6 +120,7 @@ NAMES = \ TP_Reactor_Test \ TSS_Test \ Vector_Test \ + Unbounded_Set_Test \ Upgradable_RW_Test \ UPIPE_SAP_Test \ XtReactor_Test diff --git a/tests/Unbounded_Set_Test.cpp b/tests/Unbounded_Set_Test.cpp new file mode 100644 index 00000000000..c7771b4d155 --- /dev/null +++ b/tests/Unbounded_Set_Test.cpp @@ -0,0 +1,69 @@ +// $Id$ + +// ============================================================================ +// +// = LIBRARY +// tests +// +// = FILENAME +// Unbounded_Set_Test.cpp +// +// = DESCRIPTION +// This test shall evolve to illustrate the use of ACE_Unbounded_Set. +// For the moment it only tests some insertion and removal, and acts +// as a regression test for Bugzilla bug 1460. +// No command line arguments are needed to run the test. +// +// = AUTHOR +// Rudolf Weber <rfweber@tesionmail.de>, +// ace/tests integration <Oliver.Kellogg@sysde.eads.net> +// +// ============================================================================ + +#include "test_config.h" +#include <ace/Unbounded_Set.h> + +ACE_RCSID(tests, Unbounded_Set_Test, "$Id$") + +struct MyNode +{ + int k; + MyNode () : k (0) {} + MyNode (int pk) : k (pk) {} + MyNode (const MyNode& o) : k (o.k) {} + bool operator== (const MyNode& o) { return (k == o.k); } +}; + +int main() +{ + int r; + MyNode node (1); + ACE_Unbounded_Set<MyNode> ubs; + + ACE_ASSERT (ubs.size () == 0); + + // Insert a node. Immediately remove it. + r = ubs.insert (node); + ACE_ASSERT (r == 0); + ACE_ASSERT (ubs.size () == 1); + r = ubs.remove (node); + ACE_ASSERT (r == 0); + ACE_ASSERT (ubs.size () == 0); + + // Insert a node. Remove it within an iterator. + int n_iterations = 0; + r = ubs.insert (node); + ACE_Unbounded_Set<MyNode>::ITERATOR end = ubs.end (); + for (ACE_Unbounded_Set<MyNode>::ITERATOR i = ubs.begin (); i != end; i++) + { + ACE_ASSERT (*i == node); + r = ubs.remove (*i); + n_iterations++; + } + ACE_ASSERT (n_iterations == 1); + ACE_ASSERT (r == 0); + ACE_ASSERT (ubs.size () == 0); + + return 0; +} + diff --git a/tests/Unbounded_Set_Test.icc b/tests/Unbounded_Set_Test.icc new file mode 100644 index 00000000000..7bfe45b0937 --- /dev/null +++ b/tests/Unbounded_Set_Test.icc @@ -0,0 +1,22 @@ +// $Id$ + +include "vacpp_setup.icc" +option + link(libSearchPath, platformLibSearchPath), + incl(searchPath, ".."), + link(linkWithMultiThreadLib,yes), + link(debug) + { + target type (exe) "Unbounded_Set_Test" + { + source type (cpp) "Unbounded_Set_Test.cpp" + if ($__IBMCPP__ >= 500) { + option macros(global) { + source type (hpp) "test_config.h" + } + source type (cpp) "test_config.h" + source type (cpp) "../ace/Unbounded_Set.cpp" + } + source type (lib) platformLinkLibs + } + } |