A double-linked list implementation. More...

#include <Containers_T.h>

Collaboration 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 >

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

Internal Structure Double Linked List
Duplicates allowed? Yes
Random access allowed? No
Search speed N/A
Insert/replace speed Linear
Iterator still valid after change to container? Yes
Frees memory for removed elements? No
Items inserted by Value
Requirements for contained type
1. Default constructor
2. Copy constructor
3. operator=

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 )

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

  : size_ (0), allocator_ (alloc)
{
  if (this->allocator_ == 0)
    this->allocator_ = ACE_Allocator::instance ();

  ACE_NEW_MALLOC (this->head_,
                  (T *) this->allocator_->malloc (sizeof (T)),
                  T);
  this->init_head ();
}

template<class T>

ACE_Double_Linked_List< T >::ACE_Double_Linked_List ( const ACE_Double_Linked_List< T > & cx )

Copy constructor.

Create a double linked list that is a copy of the provided parameter.

Definition at line 678 of file Containers_T.cpp.

  : allocator_ (cx.allocator_)
{
  if (this->allocator_ == 0)
    this->allocator_ = ACE_Allocator::instance ();

  ACE_NEW_MALLOC (this->head_,
                  (T *) this->allocator_->malloc (sizeof (T)),
                  T);
  this->init_head ();
  this->copy_nodes (cx);
  this->size_ = cx.size_;
}

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

{
  this->delete_nodes ();

  ACE_DES_FREE (head_,
                this->allocator_->free,
                T);

  this->head_ = 0;
}

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

{
  for (ACE_Double_Linked_List_Iterator<T> iter (c);
       !iter.done ();
       iter.advance ())
    {
      T* temp = 0;
      ACE_NEW_MALLOC (temp,
                      (T *)this->allocator_->malloc (sizeof (T)),
                      T (*iter.next ()));
      this->insert_tail (temp);
    }
}

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

{
  if (this->is_empty ())
    return 0;

  T *temp = static_cast<T *> (this->head_->next_);
  // Detach it from the list.
  this->remove_element (temp);
  return temp;
}

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

{
  while (! this->is_empty ())
    {
      T * temp = static_cast<T*> (this->head_->next_);
      this->remove_element (temp);
      ACE_DES_FREE (temp,
                    this->allocator_->free,
                    T);
    }
}

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

{
  if (this->is_empty ())
    return 0;

  T *temp = static_cast <T *> (this->head_->prev_);
  // Detach it from the list.
  this->remove_element (temp);
  return temp;
}

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

{
#if defined (ACE_HAS_DUMP)
  // Dump the state of an object.
#endif /* ACE_HAS_DUMP */
}

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

{
  ACE_Double_Linked_List_Iterator<T> iter (*this);

  for (size_t i = 0;
       i < slot && !iter.done ();
       i++)
    iter.advance ();

  item = iter.next ();
  return item ? 0 : -1;
}

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

{
  this->head_->next_ = this->head_;
  this->head_->prev_ = this->head_;
}

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

{
  if (old_item == 0)
    old_item = this->head_;

  if (before)
    old_item = static_cast<T *> (old_item->prev_);

  new_item->next_ = old_item->next_;
  new_item->next_->prev_ = new_item;
  new_item->prev_ = old_item;
  old_item->next_ = new_item;
  ++this->size_;
  return 0;                     // Well, what will cause errors here?
}

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

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

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

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

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

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

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

{
  return 0;                     // We have no bound.
}

template<class T>

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

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

{
  if (this != &cx)
    {
      this->delete_nodes ();
      this->copy_nodes (cx);
    }
}

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

{
  return this->remove_element (n);
}

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

{
  // 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_ || item->next_ == 0
      || item->prev_ == 0 || this->size () == 0)      // Can't remove head
    return -1;

  item->prev_->next_ = item->next_;
  item->next_->prev_ = item->prev_;
  item->next_ = item->prev_ = 0; // reset pointers to prevent double removal.
  --this->size_;
  return 0;
}

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

{
  this->delete_nodes ();
}

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

{
  return this->size_;
}

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.

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.

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.

The documentation for this class was generated from the following files:

ACE_Double_Linked_List< T > Class Template Reference

Public Types

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Friends

Detailed Description

template<class T> class ACE_Double_Linked_List< T >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class T>
class ACE_Double_Linked_List< T >