ACE_Double_Linked_List< T > Class Template Reference

A double-linked list implementation. More...

#include <Containers_T.h>

Collaboration diagram for ACE_Double_Linked_List< T >:

Collaboration graph
[legend]
List of all members.

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 >

Detailed Description

template<class T>
class ACE_Double_Linked_List< T >

A double-linked list implementation.

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 823 of file Containers_T.h.

Member Typedef Documentation

template<class T>
typedef ACE_Double_Linked_List_Iterator<T> ACE_Double_Linked_List< T >::ITERATOR

Definition at line 831 of file Containers_T.h.

template<class T>
typedef ACE_Double_Linked_List_Reverse_Iterator<T> ACE_Double_Linked_List< T >::REVERSE_ITERATOR

Definition at line 832 of file Containers_T.h.

Constructor & Destructor Documentation

template<class T>
ACE_Double_Linked_List< T >::ACE_Double_Linked_List ( ACE_Allocator *  the_allocator = 0  ) 

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, 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 }

template<class T>
ACE_Double_Linked_List< T >::ACE_Double_Linked_List ( const ACE_Double_Linked_List< T > &   ) 

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 >::allocator_, 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 }

template<class T>
ACE_Double_Linked_List< T >::~ACE_Double_Linked_List ( void   ) 

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, ACE_Double_Linked_List< T >::delete_nodes(), and ACE_Double_Linked_List< T >::head_.

00702 {
00703   this->delete_nodes ();
00704 
00705   ACE_DES_FREE (head_,
00706                 this->allocator_->free,
00707                 T);
00708 
00709   this->head_ = 0;
00710 }

Member Function Documentation

template<class T>
void ACE_Double_Linked_List< T >::copy_nodes ( const ACE_Double_Linked_List< T > &  rhs  )  [protected]

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 846 of file Containers_T.cpp.

References ACE_NEW_MALLOC, and ACE_Double_Linked_List< T >::insert_tail().

Referenced by ACE_Double_Linked_List< T >::ACE_Double_Linked_List(), and ACE_Double_Linked_List< T >::operator=().

00847 {
00848   for (ACE_Double_Linked_List_Iterator<T> iter (c);
00849        !iter.done ();
00850        iter.advance ())
00851     {
00852       T* temp = 0;
00853       ACE_NEW_MALLOC (temp,
00854                       (T *)this->allocator_->malloc (sizeof (T)),
00855                       T (*iter.next ()));
00856       this->insert_tail (temp);
00857     }
00858 }

template<class T>
T * ACE_Double_Linked_List< T >::delete_head ( void   ) 

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 >::head_, and ACE_Double_Linked_List< T >::remove_element().

Referenced by ACE_Thread_Manager::wait().

00741 {
00742   if (this->is_empty ())
00743     return 0;
00744 
00745   T *temp = static_cast<T *> (this->head_->next_);
00746   // Detach it from the list.
00747   this->remove_element (temp);
00748   return temp;
00749 }

template<class T>
void ACE_Double_Linked_List< T >::delete_nodes ( void   )  [protected]

Delete all the nodes in the list.

Removes and deallocates memory for all of the list nodes.

Definition at line 833 of file Containers_T.cpp.

References ACE_DES_FREE, 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().

00834 {
00835   while (! this->is_empty ())
00836     {
00837       T * temp = static_cast<T*> (this->head_->next_);
00838       this->remove_element (temp);
00839       ACE_DES_FREE (temp,
00840                     this->allocator_->free,
00841                     T);
00842     }
00843 }

template<class T>
T * ACE_Double_Linked_List< T >::delete_tail ( void   ) 

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 752 of file Containers_T.cpp.

References ACE_Double_Linked_List< T >::head_, and ACE_Double_Linked_List< T >::remove_element().

00753 {
00754   if (this->is_empty ())
00755     return 0;
00756 
00757   T *temp = static_cast <T *> (this->head_->prev_);
00758   // Detach it from the list.
00759   this->remove_element (temp);
00760   return temp;
00761 }

template<class T>
void ACE_Double_Linked_List< T >::dump ( void   )  const

Dump the state of an object.

Reimplemented in ACE_DLList< T >.

Definition at line 790 of file Containers_T.cpp.

00791 {
00792 #if defined (ACE_HAS_DUMP)
00793   // Dump the state of an object.
00794 #endif /* ACE_HAS_DUMP */
00795 }

template<class T>
int ACE_Double_Linked_List< T >::get ( T *&  item,
size_t  slot = 0 
)

Iterates through the list to the desired index and assigns the provides pointer with the address of the node occupying that index.

Definition at line 770 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().

00771 {
00772   ACE_Double_Linked_List_Iterator<T> iter (*this);
00773 
00774   for (size_t i = 0;
00775        i < slot && !iter.done ();
00776        i++)
00777     iter.advance ();
00778 
00779   item = iter.next ();
00780   return item ? 0 : -1;
00781 }

template<class T>
void ACE_Double_Linked_List< T >::init_head ( void   )  [protected]

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 861 of file Containers_T.cpp.

References ACE_Double_Linked_List< T >::head_.

Referenced by ACE_Double_Linked_List< T >::ACE_Double_Linked_List().

00862 {
00863   this->head_->next_ = this->head_;
00864   this->head_->prev_ = this->head_;
00865 }

template<class T>
int ACE_Double_Linked_List< T >::insert_element ( T *  new_item,
int  before = 0,
T *  old_item = 0 
) [protected]

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 868 of file Containers_T.cpp.

References ACE_Double_Linked_List< T >::head_, and ACE_Double_Linked_List< T >::size_.

Referenced by ACE_Double_Linked_List< T >::insert_head(), and ACE_Double_Linked_List< T >::insert_tail().

00871 {
00872   if (old_item == 0)
00873     old_item = this->head_;
00874 
00875   if (before)
00876     old_item = static_cast<T *> (old_item->prev_);
00877 
00878   new_item->next_ = old_item->next_;
00879   new_item->next_->prev_ = new_item;
00880   new_item->prev_ = old_item;
00881   old_item->next_ = new_item;
00882   ++this->size_;
00883   return 0;                     // Well, what will cause errors here?
00884 }

template<class T>
T * ACE_Double_Linked_List< T >::insert_head ( T *  new_item  ) 

Provides constant time insertion at the head of the list.

Definition at line 733 of file Containers_T.cpp.

References ACE_Double_Linked_List< T >::insert_element().

00734 {
00735   this->insert_element (new_item); // Insert it after <head_>, i.e., at head.
00736   return new_item;
00737 }

template<class T>
T * ACE_Double_Linked_List< T >::insert_tail ( T *  new_item  ) 

Provides constant time insertion at the end of the list structure.

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(), 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 }

template<class T>
int ACE_Double_Linked_List< T >::is_empty ( void   )  const

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().

00714 {
00715   return this->size () ? 0 : 1;
00716 }

template<class T>
int ACE_Double_Linked_List< T >::is_full ( void   )  const

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 }

template<class T>
void ACE_Double_Linked_List< T >::operator= ( const ACE_Double_Linked_List< T > &   ) 

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 }

template<class T>
int ACE_Double_Linked_List< T >::remove ( T *  n  ) 

Use DNode address directly.

Constant time removal of an item from the list using it's address.

Reimplemented in ACE_DLList< T >.

Definition at line 827 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(), and ACE_Double_Linked_List_Iterator< T >::advance_and_remove().

00828 {
00829   return this->remove_element (n);
00830 }

template<class T>
int ACE_Double_Linked_List< T >::remove_element ( T *  item  )  [protected]

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 887 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().

00888 {
00889   // Notice that you have to ensure that item is an element of this
00890   // list.  We can't do much checking here.
00891 
00892   if (item == this->head_ || item->next_ == 0
00893       || item->prev_ == 0 || this->size () == 0)      // Can't remove head
00894     return -1;
00895 
00896   item->prev_->next_ = item->next_;
00897   item->next_->prev_ = item->prev_;
00898   item->next_ = item->prev_ = 0; // reset pointers to prevent double removal.
00899   --this->size_;
00900   return 0;
00901 }

template<class T>
void ACE_Double_Linked_List< T >::reset ( void   ) 

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 764 of file Containers_T.cpp.

References ACE_Double_Linked_List< T >::delete_nodes().

00765 {
00766   this->delete_nodes ();
00767 }

template<class T>
size_t ACE_Double_Linked_List< T >::size ( void   )  const

The number of items in the queue.

Constant time call to return the current size of the list.

Definition at line 784 of file Containers_T.cpp.

References ACE_Double_Linked_List< T >::size_.

Referenced by ACE_Double_Linked_List< T >::is_empty().

00785 {
00786   return this->size_;
00787 }

Friends And Related Function Documentation

template<class T>
friend class ACE_Double_Linked_List_Iterator< T > [friend]

Reimplemented in ACE_DLList< T >.

Definition at line 827 of file Containers_T.h.

template<class T>
friend class ACE_Double_Linked_List_Iterator_Base< T > [friend]

Definition at line 826 of file Containers_T.h.

template<class T>
friend class ACE_Double_Linked_List_Reverse_Iterator< T > [friend]

Definition at line 828 of file Containers_T.h.

Member Data Documentation

template<class T>
ACE_Double_Linked_List< T >::ACE_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks.

Definition at line 943 of file Containers_T.h.

template<class T>
ACE_Allocator* ACE_Double_Linked_List< T >::allocator_ [protected]

Allocation Strategy of the queue.

Definition at line 992 of file Containers_T.h.

Referenced by ACE_Double_Linked_List< T >::ACE_Double_Linked_List().

template<class T>
T* ACE_Double_Linked_List< T >::head_ [protected]

Head of the circular double-linked list.

Definition at line 986 of file Containers_T.h.

Referenced by ACE_Double_Linked_List< T >::delete_head(), ACE_Double_Linked_List< T >::delete_tail(), ACE_Double_Linked_List< T >::init_head(), ACE_Double_Linked_List< T >::insert_element(), ACE_Double_Linked_List_Reverse_Iterator< T >::reset(), ACE_Double_Linked_List_Iterator< T >::reset(), and ACE_Double_Linked_List< T >::~ACE_Double_Linked_List().

template<class T>
size_t ACE_Double_Linked_List< T >::size_ [protected]

Size of this list.

Definition at line 989 of file Containers_T.h.

Referenced by ACE_Double_Linked_List< T >::ACE_Double_Linked_List(), ACE_Double_Linked_List< T >::insert_element(), ACE_Double_Linked_List< T >::remove_element(), and ACE_Double_Linked_List< T >::size().

The documentation for this class was generated from the following files:
Generated on Tue Feb 2 17:35:04 2010 for ACE by  doxygen 1.4.7