Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

ACE_Double_Linked_List Class Template Reference

A double-linked list implementation. More...

#include <Containers_T.h>

Inheritance diagram for ACE_Double_Linked_List:

Inheritance graph
[legend]
Collaboration diagram for ACE_Double_Linked_List:

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 Methods

 ACE_Double_Linked_List (ACE_Allocator *alloc=0)
 construction. Use user specified allocation strategy if specified. More...

 ACE_Double_Linked_List (const ACE_Double_Linked_List< T > &)
 Copy constructor. More...

void operator= (const ACE_Double_Linked_List< T > &)
 Assignment operator. More...

 ~ACE_Double_Linked_List (void)
 Destructor. More...

int is_empty (void) const
 Returns 1 if the container is empty, 0 otherwise. More...

int is_full (void) const
 The list is unbounded, so this always returns 0. More...

T * insert_tail (T *new_item)
 Adds <new_item> to the tail of the list. Returns the new item that was inserted. More...

T * insert_head (T *new_item)
 Adds <new_item> to the head of the list.Returns the new item that was inserted. More...

T * delete_head (void)
 Removes the head of the list and returns a pointer to that item. More...

T * delete_tail (void)
 Removes the tail of the list and returns a pointer to that item. More...

void reset (void)
 Empty the list. More...

int get (T *&item, size_t slot=0)
 Get the <slot>th element in the set. Returns -1 if the element isn't in the range {0..<size> - 1}, else 0. More...

size_t size (void) const
 The number of items in the queue. More...

void dump (void) const
 Dump the state of an object. More...

int remove (T *n)
 Use DNode address directly. More...


Public Attributes

 ACE_ALLOC_HOOK_DECLARE
 Declare the dynamic allocation hooks. More...


Protected Methods

void delete_nodes (void)
 Delete all the nodes in the list. More...

void copy_nodes (const ACE_Double_Linked_List< T > &rhs)
 Copy nodes from <rhs> into this list. More...

void init_head (void)
 Setup header pointer. Called after we create the head node in ctor. More...

int insert_element (T *new_item, int before=0, T *old_item=0)
 Constant time insert a new item into the list structure. More...

int remove_element (T *item)
 Constant time delete an item from the list structure. More...


Protected Attributes

T * head_
 Head of the circular double-linked list. More...

size_t size_
 Size of this list. More...

ACE_Allocator * allocator_
 Allocation Strategy of the queue. More...


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

Member Typedef Documentation

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

Definition at line 830 of file Containers_T.h.

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

Definition at line 831 of file Containers_T.h.

Constructor & Destructor Documentation

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

construction. Use user specified allocation strategy if specified.

Initialize an empy list using the allocation strategy specified by the user. If none is specified, then use default allocation strategy.

Definition at line 651 of file Containers_T.cpp.

References ACE_NEW_MALLOC, allocator_, init_head, and ACE_Allocator::instance. 

00652   : size_ (0), allocator_ (alloc)
00653 {
00654   if (this->allocator_ == 0)
00655     this->allocator_ = ACE_Allocator::instance ();
00656 
00657   ACE_NEW_MALLOC (this->head_,
00658                   (T *) this->allocator_->malloc (sizeof (T)),
00659                   T);
00660   this->init_head ();
00661 }

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

References ACE_NEW_MALLOC, allocator_, copy_nodes, init_head, ACE_Allocator::instance, and size_. 

00665   : allocator_ (cx.allocator_)
00666 {
00667   if (this->allocator_ == 0)
00668     this->allocator_ = ACE_Allocator::instance ();
00669 
00670   ACE_NEW_MALLOC (this->head_,
00671                   (T *) this->allocator_->malloc (sizeof (T)),
00672                   T);
00673   this->init_head ();
00674   this->copy_nodes (cx);
00675   this->size_ = cx.size_;
00676 }

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

References ACE_DES_FREE, delete_nodes, and head_. 

00690 {
00691   this->delete_nodes ();
00692 
00693   ACE_DES_FREE (head_,
00694                 this->allocator_->free,
00695                 T);
00696 
00697   this->head_ = 0;
00698 }

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

References ACE_NEW_MALLOC, ACE_Double_Linked_List_Iterator::advance, ACE_Double_Linked_List_Iterator_Base::done, insert_tail, and ACE_Double_Linked_List_Iterator_Base::next.

Referenced by ACE_Double_Linked_List, and operator=. 

00839 {
00840   for (ACE_Double_Linked_List_Iterator<T> iter (c);
00841        !iter.done ();
00842        iter.advance ())
00843     {
00844       T* temp = 0;
00845       ACE_NEW_MALLOC (temp,
00846                       (T *)this->allocator_->malloc (sizeof (T)),
00847                       T (*iter.next ()));
00848       this->insert_tail (temp);
00849     }
00850 }

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.

Definition at line 728 of file Containers_T.cpp.

References is_empty, and remove_element. 

00729 {
00730   T *temp;
00731 
00732   if (this->is_empty ())
00733     return 0;
00734 
00735   temp = ACE_static_cast (T *,
00736                           this->head_->next_);
00737   // Detach it from the list.
00738   this->remove_element (temp);
00739   return temp;
00740 }

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

References ACE_DES_FREE, is_empty, and remove_element.

Referenced by operator=, reset, and ~ACE_Double_Linked_List. 

00826 {
00827   while (! this->is_empty ())
00828     {
00829       T * temp = ACE_static_cast (T*, this->head_->next_);
00830       this->remove_element (temp);
00831       ACE_DES_FREE (temp,
00832                     this->allocator_->free,
00833                     T);
00834     }
00835 }

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.

Definition at line 743 of file Containers_T.cpp.

References is_empty, and remove_element. 

00744 {
00745   T *temp;
00746 
00747   if (this->is_empty ())
00748     return 0;
00749 
00750   temp = ACE_static_cast (T *,
00751                           this->head_->prev_);
00752   // Detach it from the list.
00753   this->remove_element (temp);
00754   return temp;
00755 }

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

Dump the state of an object.

Reimplemented in ACE_DLList.

Definition at line 784 of file Containers_T.cpp. 

00785 {
00786   // Dump the state of an object.
00787 }

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

Get the <slot>th element in the set. Returns -1 if the element isn't in the range {0..<size> - 1}, else 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 764 of file Containers_T.cpp.

References ACE_Double_Linked_List_Iterator::advance, ACE_Double_Linked_List_Iterator_Base::done, and ACE_Double_Linked_List_Iterator_Base::next. 

00765 {
00766   ACE_Double_Linked_List_Iterator<T> iter (*this);
00767 
00768   for (size_t i = 0;
00769        i < slot && !iter.done ();
00770        i++)
00771     iter.advance ();
00772 
00773   item = iter.next ();
00774   return item ? 0 : -1;
00775 }

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

References head_.

Referenced by ACE_Double_Linked_List. 

00854 {
00855   this->head_->next_ = this->head_;
00856   this->head_->prev_ = this->head_;
00857 }

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

References head_, and size_.

Referenced by insert_head, and insert_tail. 

00863 {
00864   if (old_item == 0)
00865     old_item = this->head_;
00866 
00867   if (before)
00868     old_item = ACE_static_cast (T *,
00869                                 old_item->prev_);
00870 
00871   new_item->next_ = old_item->next_;
00872   new_item->next_->prev_ = new_item;
00873   new_item->prev_ = old_item;
00874   old_item->next_ = new_item;
00875   this->size_++;
00876   return 0;                     // Well, what will cause errors here?
00877 }

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

Adds <new_item> to the head of the list.Returns the new item that was inserted.

Provides constant time insertion at the head of the list.

Definition at line 721 of file Containers_T.cpp.

References insert_element. 

00722 {
00723   this->insert_element (new_item); // Insert it after <head_>, i.e., at head.
00724   return new_item;
00725 }

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

Adds <new_item> to the tail of the list. Returns the new item that was inserted.

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

Definition at line 713 of file Containers_T.cpp.

References insert_element.

Referenced by copy_nodes. 

00714 {
00715   // Insert it before <head_>, i.e., at tail.
00716   this->insert_element (new_item, 1);
00717   return new_item;
00718 }

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

References size.

Referenced by delete_head, delete_nodes, and delete_tail. 

00702 {
00703   return this->size () ? 0 : 1;
00704 }

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

00708 {
00709   return 0;                     // We have no bound.
00710 }

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

References copy_nodes, and delete_nodes. 

00680 {
00681   if (this != &cx)
00682     {
00683       this->delete_nodes ();
00684       this->copy_nodes (cx);
00685     }
00686 }

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.

Definition at line 819 of file Containers_T.cpp.

References remove_element.

Referenced by ACE_Double_Linked_List_Reverse_Iterator::advance_and_remove, and ACE_Double_Linked_List_Iterator::advance_and_remove. 

00820 {
00821   return this->remove_element (n);
00822 }

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

References head_, size, and size_.

Referenced by delete_head, delete_nodes, delete_tail, and remove. 

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

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

References delete_nodes. 

00759 {
00760   this->delete_nodes ();
00761 }

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

References size_.

Referenced by is_empty, and remove_element. 

00779 {
00780   return this->size_;
00781 }

Friends And Related Function Documentation

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

Reimplemented in ACE_DLList.

Definition at line 826 of file Containers_T.h.

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

Definition at line 825 of file Containers_T.h.

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

Definition at line 827 of file Containers_T.h.

Member Data Documentation

template<class T>
ACE_Double_Linked_List::ACE_ALLOC_HOOK_DECLARE
 

Declare the dynamic allocation hooks.

Definition at line 942 of file Containers_T.h.

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

Allocation Strategy of the queue.

Definition at line 991 of file Containers_T.h.

Referenced by ACE_Double_Linked_List.

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

Head of the circular double-linked list.

Definition at line 985 of file Containers_T.h.

Referenced by init_head, insert_element, remove_element, and ~ACE_Double_Linked_List.

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

Size of this list.

Definition at line 988 of file Containers_T.h.

Referenced by ACE_Double_Linked_List, insert_element, remove_element, and size.

The documentation for this class was generated from the following files:
Generated on Mon Jun 16 12:47:25 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002