ACE_Double_Linked_List< T > Class Template Reference

A double-linked list implementation. More...

#include <Containers_T.h>

Inheritance diagram for ACE_Double_Linked_List< T >:

[legend]Collaboration diagram for ACE_Double_Linked_List< T >:

[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

• 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  )

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

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_. : 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 701 of file Containers_T.cpp. References ACE_DES_FREE, and ACE_Double_Linked_List< T >::delete_nodes(). { 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 846 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=(). { 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 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(). { 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 833 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(). { 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 752 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(). { 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 790 of file Containers_T.cpp. Referenced by ACE_DLList< T >::dump(). { #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 )

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 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(). Referenced by ACE_DLList< T >::get(). { 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 861 of file Containers_T.cpp. Referenced by ACE_Double_Linked_List< T >::ACE_Double_Linked_List(). { 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 868 of file Containers_T.cpp. Referenced by ACE_Double_Linked_List< T >::insert_head(), and ACE_Double_Linked_List< T >::insert_tail(). { 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  )

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

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(). { // 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 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(). { 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 719 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 > &   )

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(). { 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. 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(), ACE_Double_Linked_List_Iterator< T >::advance_and_remove(), and ACE_DLList< T >::remove(). { 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 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(). { // 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 764 of file Containers_T.cpp. References ACE_Double_Linked_List< T >::delete_nodes(). { 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 784 of file Containers_T.cpp. Referenced by ACE_Double_Linked_List< T >::is_empty(), and ACE_Double_Linked_List< T >::remove_element(). { 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. 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().

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

---

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

• Containers_T.h
• Containers_T.cpp

---