#include <Containers_T.h>
Inheritance diagram for ACE_Double_Linked_List< T >:
Public Types | |
typedef ACE_Double_Linked_List_Iterator< T > | ITERATOR |
typedef ACE_Double_Linked_List_Reverse_Iterator< T > | REVERSE_ITERATOR |
Public Member Functions | |
ACE_Double_Linked_List (ACE_Allocator *the_allocator=0) | |
ACE_Double_Linked_List (const ACE_Double_Linked_List< T > &) | |
Copy constructor. | |
void | operator= (const ACE_Double_Linked_List< T > &) |
Assignment operator. | |
~ACE_Double_Linked_List (void) | |
Destructor. | |
int | is_empty (void) const |
Returns 1 if the container is empty, 0 otherwise. | |
int | is_full (void) const |
The list is unbounded, so this always returns 0. | |
T * | insert_tail (T *new_item) |
T * | insert_head (T *new_item) |
T * | delete_head (void) |
Removes the head of the list and returns a pointer to that item. | |
T * | delete_tail (void) |
Removes the tail of the list and returns a pointer to that item. | |
void | reset (void) |
Empty the list. | |
int | get (T *&item, size_t slot=0) |
size_t | size (void) const |
The number of items in the queue. | |
void | dump (void) const |
Dump the state of an object. | |
int | remove (T *n) |
Use DNode address directly. | |
Public Attributes | |
ACE_ALLOC_HOOK_DECLARE | |
Declare the dynamic allocation hooks. | |
Protected Member Functions | |
void | delete_nodes (void) |
Delete all the nodes in the list. | |
void | copy_nodes (const ACE_Double_Linked_List< T > &rhs) |
Copy nodes from {rhs} into this list. | |
void | init_head (void) |
Setup header pointer. Called after we create the head node in ctor. | |
int | insert_element (T *new_item, int before=0, T *old_item=0) |
Constant time insert a new item into the list structure. | |
int | remove_element (T *item) |
Constant time delete an item from the list structure. | |
Protected Attributes | |
T * | head_ |
Head of the circular double-linked list. | |
size_t | size_ |
Size of this list. | |
ACE_Allocator * | allocator_ |
Allocation Strategy of the queue. | |
Friends | |
class | ACE_Double_Linked_List_Iterator_Base< T > |
class | ACE_Double_Linked_List_Iterator< T > |
class | ACE_Double_Linked_List_Reverse_Iterator< T > |
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. Notice that this class is an implementation of a very simple data structure. This is *NOT* a container class. You can use the class to implement other contains classes but it is *NOT* a general purpose container class. The parameter class *MUST* have members T* prev and T* next and users of this class are responsible to follow the general rules of using double-linked lists to maintaining the list integrity. If you need a double linked container class, use the DLList class which is a container but delegates to the Double_Linked_List class.
Requirements and Performance Characteristics
Definition at line 825 of file Containers_T.h.
|
Definition at line 833 of file Containers_T.h. |
|
Definition at line 834 of file Containers_T.h. |
|
Initialize an empy list using the allocation strategy specified by the user. If none is specified, then use default allocation strategy. Definition at line 663 of file Containers_T.cpp. References ACE_NEW_MALLOC, ACE_Double_Linked_List< T >::init_head(), and ACE_Allocator::instance().
00664 : size_ (0), allocator_ (alloc) 00665 { 00666 if (this->allocator_ == 0) 00667 this->allocator_ = ACE_Allocator::instance (); 00668 00669 ACE_NEW_MALLOC (this->head_, 00670 (T *) this->allocator_->malloc (sizeof (T)), 00671 T); 00672 this->init_head (); 00673 } |
|
Copy constructor. Create a double linked list that is a copy of the provided parameter. Definition at line 676 of file Containers_T.cpp. References ACE_NEW_MALLOC, ACE_Double_Linked_List< T >::copy_nodes(), ACE_Double_Linked_List< T >::init_head(), ACE_Allocator::instance(), and ACE_Double_Linked_List< T >::size_.
00677 : allocator_ (cx.allocator_) 00678 { 00679 if (this->allocator_ == 0) 00680 this->allocator_ = ACE_Allocator::instance (); 00681 00682 ACE_NEW_MALLOC (this->head_, 00683 (T *) this->allocator_->malloc (sizeof (T)), 00684 T); 00685 this->init_head (); 00686 this->copy_nodes (cx); 00687 this->size_ = cx.size_; 00688 } |
|
Destructor. Clean up the memory allocated for the nodes of the list. Definition at line 701 of file Containers_T.cpp. References ACE_DES_FREE, and ACE_Double_Linked_List< T >::delete_nodes().
00702 { 00703 this->delete_nodes (); 00704 00705 ACE_DES_FREE (head_, 00706 this->allocator_->free, 00707 T); 00708 00709 this->head_ = 0; 00710 } |
|
Copy nodes from {rhs} into this list. Copy the elements of the provided list by allocated new nodes and assigning them with the proper data. Definition at line 850 of file Containers_T.cpp. References ACE_NEW_MALLOC, ACE_Double_Linked_List_Iterator< T >::advance(), ACE_Double_Linked_List_Iterator_Base< T >::done(), ACE_Double_Linked_List< T >::insert_tail(), and ACE_Double_Linked_List_Iterator_Base< T >::next(). Referenced by ACE_Double_Linked_List< T >::ACE_Double_Linked_List(), and ACE_Double_Linked_List< T >::operator=().
00851 { 00852 for (ACE_Double_Linked_List_Iterator<T> iter (c); 00853 !iter.done (); 00854 iter.advance ()) 00855 { 00856 T* temp = 0; 00857 ACE_NEW_MALLOC (temp, 00858 (T *)this->allocator_->malloc (sizeof (T)), 00859 T (*iter.next ())); 00860 this->insert_tail (temp); 00861 } 00862 } |
|
Removes the head of the list and returns a pointer to that item. Removes and returns the first {item} in the list. Returns internal node's address on success, 0 if the queue was empty. This method will *not* free the internal node. Reimplemented in ACE_DLList< T >. Definition at line 740 of file Containers_T.cpp. References ACE_Double_Linked_List< T >::is_empty(), and ACE_Double_Linked_List< T >::remove_element(). Referenced by ACE_DLList< T >::delete_head(), and ACE_Thread_Manager::wait().
00741 { 00742 T *temp; 00743 00744 if (this->is_empty ()) 00745 return 0; 00746 00747 temp = static_cast<T *> (this->head_->next_); 00748 // Detach it from the list. 00749 this->remove_element (temp); 00750 return temp; 00751 } |
|
Delete all the nodes in the list. Removes and deallocates memory for all of the list nodes. Definition at line 837 of file Containers_T.cpp. References ACE_DES_FREE, ACE_Double_Linked_List< T >::is_empty(), and ACE_Double_Linked_List< T >::remove_element(). Referenced by ACE_Double_Linked_List< T >::operator=(), ACE_Double_Linked_List< T >::reset(), and ACE_Double_Linked_List< T >::~ACE_Double_Linked_List().
00838 { 00839 while (! this->is_empty ()) 00840 { 00841 T * temp = static_cast<T*> (this->head_->next_); 00842 this->remove_element (temp); 00843 ACE_DES_FREE (temp, 00844 this->allocator_->free, 00845 T); 00846 } 00847 } |
|
Removes the tail of the list and returns a pointer to that item. Removes and returns the last {item} in the list. Returns internal nodes's address on success, 0 if the queue was empty. This method will *not* free the internal node. Reimplemented in ACE_DLList< T >. Definition at line 754 of file Containers_T.cpp. References ACE_Double_Linked_List< T >::is_empty(), and ACE_Double_Linked_List< T >::remove_element(). Referenced by ACE_DLList< T >::delete_tail().
00755 { 00756 T *temp; 00757 00758 if (this->is_empty ()) 00759 return 0; 00760 00761 temp = static_cast <T *> (this->head_->prev_); 00762 // Detach it from the list. 00763 this->remove_element (temp); 00764 return temp; 00765 } |
|
Dump the state of an object.
Reimplemented in ACE_DLList< T >. Definition at line 794 of file Containers_T.cpp. Referenced by ACE_DLList< T >::dump().
00795 { 00796 #if defined (ACE_HAS_DUMP) 00797 // Dump the state of an object. 00798 #endif /* ACE_HAS_DUMP */ 00799 } |
|
Iterates through the list to the desired index and assigns the provides pointer with the address of the node occupying that index. Reimplemented in ACE_DLList< T >. Definition at line 774 of file Containers_T.cpp. References ACE_Double_Linked_List_Iterator< T >::advance(), ACE_Double_Linked_List_Iterator_Base< T >::done(), and ACE_Double_Linked_List_Iterator_Base< T >::next(). Referenced by ACE_DLList< T >::get().
00775 { 00776 ACE_Double_Linked_List_Iterator<T> iter (*this); 00777 00778 for (size_t i = 0; 00779 i < slot && !iter.done (); 00780 i++) 00781 iter.advance (); 00782 00783 item = iter.next (); 00784 return item ? 0 : -1; 00785 } |
|
Setup header pointer. Called after we create the head node in ctor. Initialize the head pointer so that the list has a dummy node. Definition at line 865 of file Containers_T.cpp. Referenced by ACE_Double_Linked_List< T >::ACE_Double_Linked_List().
|
|
Constant time insert a new item into the list structure. Insert a new_item 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. Definition at line 872 of file Containers_T.cpp. Referenced by ACE_Double_Linked_List< T >::insert_head(), and ACE_Double_Linked_List< T >::insert_tail().
00875 { 00876 if (old_item == 0) 00877 old_item = this->head_; 00878 00879 if (before) 00880 old_item = static_cast<T *> (old_item->prev_); 00881 00882 new_item->next_ = old_item->next_; 00883 new_item->next_->prev_ = new_item; 00884 new_item->prev_ = old_item; 00885 old_item->next_ = new_item; 00886 this->size_++; 00887 return 0; // Well, what will cause errors here? 00888 } |
|
Provides constant time insertion at the head of the list. Reimplemented in ACE_DLList< T >. Definition at line 733 of file Containers_T.cpp. References ACE_Double_Linked_List< T >::insert_element(). Referenced by ACE_DLList< T >::insert_head().
00734 { 00735 this->insert_element (new_item); // Insert it after <head_>, i.e., at head. 00736 return new_item; 00737 } |
|
Provides constant time insertion at the end of the list structure. Reimplemented in ACE_DLList< T >. Definition at line 725 of file Containers_T.cpp. References ACE_Double_Linked_List< T >::insert_element(). Referenced by ACE_Double_Linked_List< T >::copy_nodes(), ACE_DLList< T >::insert_tail(), and ACE_Thread_Manager::wait().
00726 { 00727 // Insert it before <head_>, i.e., at tail. 00728 this->insert_element (new_item, 1); 00729 return new_item; 00730 } |
|
Returns 1 if the container is empty, 0 otherwise. Performs constant time check to determine if the list is empty. Definition at line 713 of file Containers_T.cpp. References ACE_Double_Linked_List< T >::size(). Referenced by ACE_Double_Linked_List< T >::delete_head(), ACE_Double_Linked_List< T >::delete_nodes(), and ACE_Double_Linked_List< T >::delete_tail().
00714 { 00715 return this->size () ? 0 : 1; 00716 } |
|
The list is unbounded, so this always returns 0. Since the list is unbounded, the method simply returns 0. Definition at line 719 of file Containers_T.cpp.
00720 { 00721 return 0; // We have no bound. 00722 } |
|
Assignment operator. Perform a deep copy of the provided list by first deleting the nodes of the lhs and then copying the nodes of the rhs. Definition at line 691 of file Containers_T.cpp. References ACE_Double_Linked_List< T >::copy_nodes(), and ACE_Double_Linked_List< T >::delete_nodes().
00692 { 00693 if (this != &cx) 00694 { 00695 this->delete_nodes (); 00696 this->copy_nodes (cx); 00697 } 00698 } |
|
Use DNode address directly. Constant time removal of an item from the list using it's address. Definition at line 831 of file Containers_T.cpp. References ACE_Double_Linked_List< T >::remove_element(). Referenced by ACE_Double_Linked_List_Reverse_Iterator< T >::advance_and_remove(), ACE_Double_Linked_List_Iterator< T >::advance_and_remove(), and ACE_DLList< T >::remove().
00832 { 00833 return this->remove_element (n); 00834 } |
|
Constant time delete an item from the list structure. Remove item from the list. Return 0 if succeed, -1 otherwise. Notice that this function checks if item is {head_} and either its {next_} or {prev_} is NULL. The function resets item's {next_} and {prev_} to 0 to prevent clobbering the double-linked list if a user tries to remove the same node again. Definition at line 891 of file Containers_T.cpp. References ACE_Double_Linked_List< T >::size(). Referenced by ACE_Double_Linked_List< T >::delete_head(), ACE_Double_Linked_List< T >::delete_nodes(), ACE_Double_Linked_List< T >::delete_tail(), and ACE_Double_Linked_List< T >::remove().
00892 { 00893 // Notice that you have to ensure that item is an element of this 00894 // list. We can't do much checking here. 00895 00896 if (item == this->head_ || item->next_ == 0 00897 || item->prev_ == 0 || this->size () == 0) // Can't remove head 00898 return -1; 00899 00900 item->prev_->next_ = item->next_; 00901 item->next_->prev_ = item->prev_; 00902 item->next_ = item->prev_ = 0; // reset pointers to prevent double removal. 00903 this->size_--; 00904 return 0; 00905 } |
|
Empty the list. Reset the {ACE_Double_Linked_List} to be empty. Notice that since no one is interested in the items within, This operation will delete all items. Definition at line 768 of file Containers_T.cpp. References ACE_Double_Linked_List< T >::delete_nodes().
00769 { 00770 this->delete_nodes (); 00771 } |
|
The number of items in the queue. Constant time call to return the current size of the list. Definition at line 788 of file Containers_T.cpp. Referenced by ACE_Double_Linked_List< T >::is_empty(), and ACE_Double_Linked_List< T >::remove_element().
00789 { 00790 return this->size_; 00791 } |
|
Reimplemented in ACE_DLList< T >. Definition at line 829 of file Containers_T.h. |
|
Definition at line 828 of file Containers_T.h. |
|
Definition at line 830 of file Containers_T.h. |
|
Declare the dynamic allocation hooks.
Definition at line 945 of file Containers_T.h. |
|
Allocation Strategy of the queue.
Definition at line 994 of file Containers_T.h. |
|
Head of the circular double-linked list.
Definition at line 988 of file Containers_T.h. Referenced by ACE_Double_Linked_List_Iterator< T >::ACE_Double_Linked_List_Iterator(), ACE_Double_Linked_List_Reverse_Iterator< T >::ACE_Double_Linked_List_Reverse_Iterator(), ACE_Double_Linked_List_Reverse_Iterator< T >::reset(), and ACE_Double_Linked_List_Iterator< T >::reset(). |
|
Size of this list.
Definition at line 991 of file Containers_T.h. Referenced by ACE_Double_Linked_List< T >::ACE_Double_Linked_List(). |