diff options
author | nw1 <nw1@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 1997-10-16 03:49:35 +0000 |
---|---|---|
committer | nw1 <nw1@ae88bc3d-4319-0410-8dbf-d08b4c9d3795> | 1997-10-16 03:49:35 +0000 |
commit | 791def41394ca14cf0a5faff984b7fac924034da (patch) | |
tree | 2a33af29fb95b167bec87402a3fa3b02753d36ea | |
parent | 840c657ad5baad85a798a1323842d02b2b997dfa (diff) | |
download | ATCD-791def41394ca14cf0a5faff984b7fac924034da.tar.gz |
*** empty log message ***
-rw-r--r-- | ace/Containers.cpp | 287 | ||||
-rw-r--r-- | ace/Containers.h | 248 | ||||
-rw-r--r-- | ace/Containers.i | 97 |
3 files changed, 528 insertions, 104 deletions
diff --git a/ace/Containers.cpp b/ace/Containers.cpp index d78dab66e51..d77dc18511f 100644 --- a/ace/Containers.cpp +++ b/ace/Containers.cpp @@ -630,6 +630,274 @@ ACE_Unbounded_Queue_Iterator<T>::next (T *&item) } } +//-------------------------------------------------- +#if defined (NANBOR_EXP_CODES) +ACE_ALLOC_HOOK_DEFINE(ACE_Double_Linked_List_Iterator) + +template <class T> +ACE_Double_Linked_List_Iterator<T>::ACE_Double_Linked_List_Iterator +(ACE_Double_Linked_List<T> &dll) + : ACE_Double_Linked_List_Iterator_Base (dll) +{ +} + +template <class T> ACE_DNode<T> * +ACE_Double_Linked_List_Iterator<T>::next (void) +{ + return this->not_done (); +} + +template <class T> int +ACE_Double_Linked_List_Iterator<T>::next (T *&item) +{ + ACE_DNode<T> *ptr = this->not_done (); + + if (ptr != 0) + { + item = &ptr->item_; + return 1; + } + else + return 0; +} + +template <class T> int +ACE_Double_Linked_List_Iterator<T>::advance (void) +{ + return (this->do_advance () ? 1 : 0); +} + +template <class T> int +ACE_Double_Linked_List_Iterator<T>::done (void) const +{ + return (this->not_done () ? 0 : 1); +} + +template <class T> void +ACE_Double_Linked_List_Iterator<T>::dump (void) const +{ + // Dump the state of an object. +} + +ACE_ALLOC_HOOK_DEFINE(ACE_Double_Linked_List) + +template <class T> +ACE_Double_Linked_List<T>:: ACE_Double_Linked_List (ACE_Allocator *alloc) + : allocator_ (alloc) +{ + if (this->allocator_ == 0) + this->allocator_ = ACE_Allocator::instance (); + + delete this->head_; + ACE_NEW_MALLOC (this->head_, + (ACE_DNode<T>*) this->allocator_->malloc (sizeof (ACE_DNode<T>)), + ACE_DNode<T>); + + this->init_head (); +} + +template <class T> +ACE_Double_Linked_List<T>::ACE_Double_Linked_List (const ACE_Double_Linked_List<T> &cx) + : allocator_ (cx.allocator_) +{ + if (this->allocator_ == 0) + this->allocator_ = ACE_Allocator::instance (); + + ACE_NEW_MALLOC (this->head_, + (ACE_DNode<T>*) this->allocator_->malloc (sizeof (ACE_DNode<T>)), + ACE_DNode<T>); + this->init_head (); + this->copy_nodes (cx); +} + +template <class T> void +ACE_Double_Linked_List<T>::operator= (const ACE_Double_Linked_List<T> &cx) +{ + if (this != &cx) + { + this->delete_nodes (); + this->copy_nodes (cx); + } +} + +template <class T> +ACE_Double_Linked_List<T>::~ACE_Double_Linked_List (void) +{ + this->delete_nodes (); + ACE_DES_FREE_TEMPLATE (this->head_, this->allocator_->free, + ACE_DNode, <T>); + this->head_ = 0; +} + +template <class T> int +ACE_Double_Linked_List<T>::is_empty (void) const +{ + return (this->size () ? 0 : 1); +} + +template <class T> int +ACE_Double_Linked_List<T>::is_full (void) const +{ + return 0; // We have no bound. +} + +template <class T> ACE_DNode<T> * +ACE_Double_Linked_List<T>::insert_tail (const T &new_item) +{ + ACE_DNode<T> *temp; + + // Create a new dummy node. + ACE_NEW_MALLOC_RETURN (temp, + (ACE_DNode<T>*) this->allocator_->malloc (sizeof (ACE_DNode<T>)), + ACE_DNode<T> (new_item), -1); + + this->insert_element (temp, 1); // Insert it before <head_>, i.e., at tail. + return 0; +} + +template <class T> ACE_DNode<T> * +ACE_Double_Linked_List<T>::insert_head (const T &new_item) +{ + ACE_DNode<T> *temp; + + // Create a new dummy node. + ACE_NEW_MALLOC_RETURN (temp, + (ACE_DNode<T>*) this->allocator_->malloc (sizeof (ACE_DNode<T>)), + ACE_DNode<T> (new_item), -1); + + this->insert_element (temp); // Insert it after <head_>, i.e., at head. + return 0; +} + +template <class T> int +ACE_Double_Linked_List<T>::delete_head (T &item) +{ + ACE_DNode<T> *temp; + + if (this->is_empty ()) + return -1; + + temp = this->head_->next_; + item = temp->item_; + this->remove_element (temp); // Detach it from the list. + ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free, + ACE_DNode, <T>); + return 0; +} + +template <class T> int +ACE_Double_Linked_List<T>::delete_tail (T &item) +{ + ACE_DNode<T> *temp; + + if (this->is_empty ()) + return -1; + + temp = this->head_->prev_; + item = temp->item_; + this->remove_element (temp); // Detach it from the list. + ACE_DES_FREE_TEMPLATE (temp, this->allocator_->free, + ACE_DNode, <T>); + return 0; +} + +template <class T> void +ACE_Double_Linked_List<T>::reset (void) +{ + this->delete_nodes (); +} + +template <class T> int +ACE_Double_Linked_List<T>::get (T *&item, size_t index = 0) const +{ + ACE_Double_Linked_List_Iterator<T> iter (*this); + + for (size_t i = 0; i < index && !iter.done (); i++, iter.advance ()) + ; + if (iter.next (item)) + return 0; + else + return -1; +} + +template <class T> int +ACE_Double_Linked_List<T>::set (const T &item, size_t index) +{ + ACE_Double_Linked_List_Iterator<T> iter (*this); + + for (size_t i = 0; i < index && !iter.done (); i++, iter.advance ()) + ; + ACE_DNode<T> *temp = iter.next (); + if (temp) + { + temp->item_ = item; + return 0; + } + else + return -1; +} + +template <class T> size_t +ACE_Double_Linked_List<T>::size (void) const +{ + return this->size_; +} + +template <class T> void +ACE_Double_Linked_List<T>::dump (void) const +{ + // Dump the state of an object. +} + +template <class T> ACE_DNode<T> * +ACE_Double_Linked_List<T>::find (const T &item) +{ + ACE_Double_Linked_List_Iterator<T> iter (*this); + + for (;!iter.done (); iter.advance ()) + { + ACE_DNode<T> *temp = iter.next (); + if (temp->item_ == item) + return temp; + } + return 0; +} + +template <class T> int +ACE_Double_Linked_List<T>::remove (const T &item) +{ + ACE_DNode<T> *temp = this->find (item); + if (temp != 0) + return this->remove (temp); + else + return -1; +} + +template <class T> int +ACE_Double_Linked_List<T>::remove (ACE_DNode<T> *n) +{ + return this->remove_element (n); +} + +template <class T> void +ACE_Double_Linked_List<T>::delete_nodes (void) +{ + while (! this->is_empty ()) + this->remove_element (this->head_->next_); +} + +template <class T> void +ACE_Double_Linked_List<T>::copy_nodes (const ACE_Double_Linked_List<T> &c) +{ + ACE_Double_Linked_List_Iterator<T> iter (c); + + for (; !iter.done (); iter.advance ()) + this->insert_head (iter.next ()->item_); +} + +#endif /* NANBOR_EXP_CODE */ +//-------------------------------------------------- + ACE_ALLOC_HOOK_DEFINE(ACE_Fixed_Set) template <class T, size_t SIZE> size_t @@ -1069,6 +1337,25 @@ ACE_Node<T>::ACE_Node (const ACE_Node<T> &s) // ACE_TRACE ("ACE_Node<T>::ACE_Node"); } +#if defined (NANBOT_EXP_CODES) +template <class T> +ACE_DNode<T>::ACE_DNode (const T &i, ACE_DNode<T> *n, ACE_DNode<T> *p) + : ACE_DNode_Base (n, p), item_ (i) +{ +} + +template <class T> +ACE_DNode<T>::ACE_DNode (const ACE_DNode<T> &i) + : ACE_DNode_Base (i.next_, i.prev_), item_ (i.item_) +{ +} + +template <class T> +ACE_DNode<T>::~ACE_DNode (void) +{ +} +#endif /* NANBOR_EXP_CODES */ + ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Set) template <class T> int diff --git a/ace/Containers.h b/ace/Containers.h index 09d7f1dd056..f065d07f754 100644 --- a/ace/Containers.h +++ b/ace/Containers.h @@ -204,56 +204,129 @@ class ACE_DNode_Base // linked list should have. // // = DESCRIPTION - // Basic functionalities an element in double linked - // lists. + // Basic functionalities an element in double-linked + // lists. This is an abstract class and can't be + // instantiated. { - public: + friend class ACE_Double_Linked_List_Iterator_Base; + friend class ACE_Double_Linked_List_Base; + +public: ACE_DNode_Base (void); // Default do nothing ctor. - ACE_DNode_Base (ACE_DNode_Base *n, ACE_DNode_Base *p); + // ACE_DNode_Base (ACE_DNode_Base *n, ACE_DNode_Base *p); // Build and set ctor. - void next (ACE_DNode_Base *n) = 0; - // Set <next_> ptr. - - ACE_DNode_Base *next (void) = 0; - // Get <next_> ptr. - - void prev (ACE_DNode_Base *p) = 0; - // Set <prev_> ptr. - - ACE_DNode_Base *prev (void) = 0; - // Get <prev_> ptr. - - protected: +protected: ACE_DNode_Base *prev_; // Pointer to previous element in the list. ACE_DNode_Base *next_; // Pointer to next element in the list. }; -#endif /* NANBOR_EXP_CODES */ -#if defined (NANBOR_DISABLED_EXP_CODES) +class ACE_Double_Linked_List_Base; +// forward declaration + +class ACE_Double_Linked_List_Iterator_Base + // = TITLE + // Basic double-linked list iterator functionalities. + // + // = DESCRIPTION + // +{ +public: + ACE_Double_Linked_List_Iterator_Base + (ACE_Double_Linked_List_Base &dll); + // Constructor. + +protected: + ACE_DNode_Base *not_done (void) ; + // Check if we reach the end of the list. Can also be used to get + // the *current* element in the list. Return the address of the + // current item if there are still elements left , 0 if we run out of element. + + ACE_DNode_Base *do_advance (void); + // Advance to the next element in the list. Return the address of the + // next element if there are more, 0 otherwise. + + // @@ This function seems redundant. +// ACE_DNode_Base *next (void); +// // Get the next unvisit element from the list. Return address if succeed, +// // 0 otherwise. + + ACE_DNode_Base *current_; + // Remember where we are. + + ACE_Double_Linked_List_Base &dllist_; +}; + +class ACE_Double_Linked_List_Base + // = TITLE + // Basic double-linked list implementation. + // + // = DESCRIPTION + // This is a barebone implementation of double-linked lists. + // It only provide a minimum set of functionalities to + // work. You must subclass from it and other related classes + // for them to work correctly. +{ + friend class ACE_Double_Linked_List_Iterator_Base; + +public: + size_t size (void); + // Return current size of the list. + +protected: + // We hide these function here because they are not supposed to + // be used directly. Notice that all these functions have only + // limited error detections. + + ACE_Double_Linked_List_Base (void); + // Default ctor. + + void init_head (void); + // Setup header pointer. Called after we create the head node in ctor. + + int insert_element (ACE_DNode_Base *new_item, + int before = 0, + ACE_DNode_Base *old_item = 0); + // Insert a <new_element> into the list. It will be added before + // or after <old_item>. Default is to insert the new item *after* + // <head_>. Return 0 if succeed, -1 if error occured. + + int remove_element (ACE_DNode_Base *item); + // Remove an <item> from the list. Return 0 if succeed, -1 otherwise. + // Notice that this function only checks if item is <head_>. Users + // must ensure the item is in the list. + + ACE_Double_Linked_List_Iterator_Base *iter (void); + // Iterator factory. + + ACE_DNode_Base *head_; + // Head of the circular double-linked list. + + size_t size_; + // Size of this list. +}; + template <class T> -class ACE_DNode : public ACE_Node<T> +class ACE_DNode : public ACE_DNode_Base // = TITLE -// Implementation element in a Double Linked List. +// Implementation element in a Double-linked List. { friend class ACE_Double_Linked_List<T>; friend class ACE_Double_Linked_List_Iterator<T>; protected: - ACE_DNode (const T &i, ACE_DNode<T> *n, ACE_DNode<T> *p); - ACE_DNode (ACE_DNode<T> *n = 0, ACE_DNode<T> *p = 0); + ACE_DNode (const T &i, ACE_DNode<T> *n = 0, ACE_DNode<T> *p = 0); ACE_DNode (const ACE_DNode<T> &i); ~ACE_DNode (void); - - ACE_DNode<T> *prev_; - // Pointer to prev element in the list of <ACE_DNode>s. + + T item_; }; -#endif /* NANBOR_DISABLED_EXP_CODES */ +#endif /* NANBOR_EXP_CODES */ template <class T> class ACE_Unbounded_Stack @@ -507,64 +580,38 @@ protected: // Allocation Strategy of the queue. }; -#if defined (NANBOR_DISABLED_EXP_CODES) -template <class T> -class ACE_Unbounded_Stack_Iterator - // = TITLE - // Implement an iterator over an unbounded Stack. -{ -public: - // = Initialization method. - ACE_Unbounded_Stack_Iterator (ACE_Unbounded_Stack<T> &); - - // = Iteration methods. - - int next (T *&next_item); - // Pass back the <next_item> that hasn't been seen in the Stack. - // Returns 0 when all items have been seen, else 1. - - int advance (void); - // Move forward by one element in the Stack. Returns 0 when all the - // items in the Stack have been seen, else 1. - - int done (void) const; - // Returns 1 when all items have been seen, else 0. - - void dump (void) const; - // Dump the state of an object. - - ACE_ALLOC_HOOK_DECLARE; - // Declare the dynamic allocation hooks. - -private: - ACE_Node<T> *current_; - // Pointer to the current node in the iteration. - - ACE_Unbounded_Stack<T> &stack_; - // Pointer to the Stack we're iterating over. -}; - +#if defined (NANBOR_EXP_CODES) template <class T> class ACE_Double_Linked_List; template <class T> class ACE_Double_Linked_List_Iterator // = TITLE - // Implement an iterator over a double-linked list. + // Implement an iterator over a container double-linked list + // + // = DESCRIPTION + // Iterate thru the double-linked list. This class provide + // an interface that let users access the internal element + // addresses directly, which (IMHO) seems to break the + // encasulation. { public: // = Initialization method. - ACE_Double_Linked_List (ACE_Double_Linked_List<T> &); + ACE_Double_Linked_List_Iterator (ACE_Double_Linked_List<T> &); // = Iteration methods. + ACE_DNode<T> *next (void); + // Return the address of next (current) unvisited ACE_DNode, + // 0 if there is no more element available. + int next (T *&next_item); - // Pass back the <next_item> that hasn't been seen in the queue. + // Pass back the <next_item> that hasn't been seen in the Stack. // Returns 0 when all items have been seen, else 1. int advance (void); - // Move forward by one element in the set. Returns 0 when all the - // items in the queue have been seen, else 1. + // Move forward by one element in the Stack. Returns 0 when all the + // items in the Stack have been seen, else 1. int done (void) const; // Returns 1 when all items have been seen, else 0. @@ -574,22 +621,16 @@ public: ACE_ALLOC_HOOK_DECLARE; // Declare the dynamic allocation hooks. - -private: - ACE_DNode<T> *current_; - // Pointer to the current node in the iteration. - - ACE_Double_Linked_List<T> &list_; - // Pointer to the queue we're iterating over. }; + template <class T> class ACE_Double_Linked_List // = TITLE - // A double linked list implementation. + // A double-linked list implementation. // // = DESCRIPTION - // This implementation of an unbounded double linked list uses a circular + // This implementation of an unbounded double-linked list uses a circular // linked list with a dummy node. It is pretty much like the ACE_Unbounded_Queue // except that it allows removing of a specific element from a specific location. { @@ -600,14 +641,14 @@ public: // construction. Use user specified allocation strategy // if specified. - ACE_Double_Linked_List (const ACE_Double_Linked_list<T> &); + ACE_Double_Linked_List (const ACE_Double_Linked_List<T> &); // Copy constructor. - void operator= (const ACE_Double_linked_List<T> &); + void operator= (const ACE_Double_Linked_List<T> &); // Assignment operator. ~ACE_Double_Linked_List (void); - // construction. + // Destructor. // = Check boundary conditions. @@ -619,22 +660,28 @@ public: // = Classic queue operations. - int enqueue_tail (const T &new_item); - // Adds <new_item> to the tail of the queue. Returns 0 on success, + ACE_DNode<T> *insert_tail (const T &new_item); + // Adds <new_item> to the tail of the list. Returns 0 on success, // -1 on failure. - int enqueue_head (const T &new_item); - // Adds <new_item> to the head of the queue. Returns 0 on success, + ACE_DNode<T> *insert_head (const T &new_item); + // Adds <new_item> to the head of the list. Returns 0 on success, // -1 on failure. - int dequeue_head (T &item); - // Removes and returns the first <item> on the queue. Returns 0 on - // success, -1 if the queue was empty. + int delete_head (T &item); + // Removes and returns the first <item> in the list. Returns 0 on + // success, -1 if the queue was empty. This method will free the + // internal node. + + int delete_tail (T &item); + // Removes and returns the last <item> in the list. Returns 0 on + // success, -1 if the queue was empty. This method will free the + // internal node. // = Additional utility methods. void reset (void); - // Reset the <ACE_Unbounded_Queue> to be empty. + // Reset the <ACE_Double_Linked_List> to be empty. int get (T *&item, size_t index = 0) const; // Get the <index>th element in the set. Returns -1 if the element @@ -657,8 +704,10 @@ public: // an address if succeed, 0 otherwise. int remove (const T &item); - // This function will iterate thru the double linked list and - // remove it from the list. return 0 if succeed, -1 otherwise. + // This function will iterate thru the double-linked list and remove + // it from the list. Return Node address if succeed, 0 otherwise. + // Notice that this method will *not* free the internal node. The + // node is simple unlinked from the list. int remove (ACE_DNode<T> *n); // Use DNode address directly. @@ -667,25 +716,16 @@ public: // Declare the dynamic allocation hooks. protected: - void add_node (ACE_DNode<T> *new_node, ACE_DNode<T> *target, int after = 1); - // Add an node before/after a current list element. - void delete_nodes (void); - // Delete all the nodes in the queue. - - void copy_nodes (const ACE_Unbounded_Queue<T> &); - // Copy nodes into this queue. + // Delete all the nodes in the list. - ACE_DNode<T> *head_; - // Pointer to the dummy node in the circular linked Queue. - - size_t cur_size_; - // Current size of the queue. + void copy_nodes (const ACE_Double_Linked_List<T> &); + // Copy nodes into this list. ACE_Allocator *allocator_; // Allocation Strategy of the queue. }; -#endif /* NANBOR_DISABLED_EXP_CODES */ +#endif /* NANBOR_EXP_CODES */ template <class T> class ACE_Unbounded_Set_Iterator diff --git a/ace/Containers.i b/ace/Containers.i index 0bd32f2e470..e352695e692 100644 --- a/ace/Containers.i +++ b/ace/Containers.i @@ -124,6 +124,103 @@ ACE_Fixed_Stack<T, SIZE>::size (void) const } //---------------------------------------- +#if defined (NANBOR_EXP_CODES) +ACE_INLINE +ACE_DNode_Base::ACE_DNode_Base (void) +{ +} + +// ACE_INLINE +// ACE_DNode_Base::ACE_DNode_Base (ACE_DNode_Base *n, ACE_DNode_Base *p) +// : next_ (n), prev_ (p) +// { +// } + +ACE_INLINE +ACE_Double_Linked_List_Iterator_Base::ACE_Double_Linked_List_Iterator_Base +(ACE_Double_Linked_List_Base &dll) + : dllist_ (dll) +{ + this->current_ = dll.head_->next_; // Initialize head ptr. +} + +ACE_INLINE ACE_DNode_Base * +ACE_Double_Linked_List_Iterator_Base::not_done (void) +{ + if (this->current_ != this->dllist_.head_) + return this->current_; + else + return 0; +} + +ACE_INLINE ACE_DNode_Base * +ACE_Double_Linked_List_Iterator_Base::do_advance (void) +{ + if (this->not_done ()) + { + this->current_ = this->current_->next_; + return this->not_done (); + } + else + return 0; +} + +ACE_INLINE +ACE_Double_Linked_List_Base::ACE_Double_Linked_List_Base (void) + : head_ (0), size_ (0) +{ +} + +ACE_INLINE void +ACE_Double_Linked_List_Base::init_head (void) +{ + this->head_->next_ = this->head_->prev_ = this->head_; +} + +ACE_INLINE size_t +ACE_Double_Linked_List_Base::size (void) +{ + return this->size_; +} + +ACE_INLINE int +ACE_Double_Linked_List_Base::insert_element (ACE_DNode_Base *new_item, + int before, + ACE_DNode_Base *old_item) +{ + if (old_item == 0) + old_item = this->head_; + if (before) + old_item = old_item->prev_; + + (new_item->next_ = old_item->next_)->prev_ = new_item; + (new_item->prev_ = old_item)->next_ = new_item; + this->size_++; + return 0; // Well, what will cause errors here? +} + +ACE_INLINE int +ACE_Double_Linked_List_Base::remove_element (ACE_DNode_Base *item) +{ + // Notice that you have to ensure that item is an element of this + // list. We can't do much checking here. + if (item == this->head_ || this->size () == 0) // Can't remove head + return -1; + (item->prev_->next_ = item->next_)->prev_ = item->prev_; + this->size_--; + return 0; +} + +ACE_INLINE ACE_Double_Linked_List_Iterator_Base * +ACE_Double_Linked_List_Base::iter (void) +{ + ACE_Double_Linked_List_Iterator_Base *itr; + ACE_NEW_RETURN (itr, ACE_Double_Linked_List_Iterator_Base (*this), 0); + return itr; +} + +#endif /* NANBOR_EXP_CODES */ +//---------------------------------------- template <class T> ACE_INLINE int ACE_Unbounded_Stack<T>::is_empty (void) const |