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:

[legend]
Collaboration diagram for ACE_Double_Linked_List:

[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)
| Initialize an empy list using the allocation strategy specified by the user. More...
| ACE_Double_Linked_List (const ACE_Double_Linked_List< T > &)
| Create a double linked list that is a copy of the provided parameter. More...
void | operator= (const ACE_Double_Linked_List< T > &)
| Perform a deep copy of the provided list by first deleting the nodes of the lhs and then copying the nodes of the rhs. More...
| ~ACE_Double_Linked_List (void)
| Clean up the memory allocated for the nodes of the list. More...
int | is_empty (void) const
| Performs constant time check to determine if the list is empty. More...
int | is_full (void) const
| Since the list is unbounded, the method simply returns 0. More...
T * | insert_tail (T *new_item)
| Provides constant time insertion at the end of the list structure. More...
T * | insert_head (T *new_item)
| Provides constant time insertion at the head of the list. More...
T * | delete_head (void)
| Removes and returns the first <item> in the list. More...
T * | delete_tail (void)
| Removes and returns the last <item> in the list. More...
void | reset (void)
| Reset the <ACE_Double_Linked_List> to be empty. More...
int | 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. More...
size_t | size (void) const
| Constant time call to return the current size of the list. More...
void | dump (void) const
| Dump the state of an object. More...
int | remove (T *n)
| Constant time removal of an item from the list using it's address. More...
## Public Attributes
| ACE_ALLOC_HOOK_DECLARE
| Declare the dynamic allocation hooks. More...
## Protected Methods
void | delete_nodes (void)
| Removes and deallocates memory for all of the list nodes. More...
void | copy_nodes (const ACE_Double_Linked_List< T > &rhs)
| Copy the elements of the provided list by allocated new nodes and assigning them with the proper data. More...
void | init_head (void)
| Initialize the head pointer so that the list has a dummy node. More...
int | insert_element (T *new_item, int before=0, T *old_item=0)
| Insert a <new_element> into the list. More...
int | remove_element (T *item)
| Remove an <item> from the list. 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

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

## Member Typedef Documentation

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

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

## Constructor & Destructor Documentation

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

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

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

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

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

| Clean up the memory allocated for the nodes of the list.

## Member Function Documentation

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

| Copy the elements of the provided list by allocated new nodes and assigning them with the proper data.

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

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

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

| Removes and deallocates memory for all of the list nodes.

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

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

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

| Dump the state of an object. Reimplemented in ACE_DLList.

template<class T>
int ACE_Double_Linked_List< T >::get | ( | T *& | item,
|  | size_t | index = 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.

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

| Initialize the head pointer so that the list has a dummy node.

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

| Insert a <new_element> 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.

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.

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.

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

| Performs constant time check to determine if the list is empty.

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

| Since the list is unbounded, the method simply returns 0.

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

| Perform a deep copy of the provided list by first deleting the nodes of the lhs and then copying the nodes of the rhs.

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

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

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

| Remove an <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.

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

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

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

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

## Friends And Related Function Documentation

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

| Reimplemented in ACE_DLList.

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

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

## Member Data Documentation

template<class T>
ACE_Double_Linked_List::ACE_ALLOC_HOOK_DECLARE

| Declare the dynamic allocation hooks.

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

| Allocation Strategy of the queue.

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

| Head of the circular double-linked list.

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

| Size of this list.

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

- Containers_T.h
- Containers_T.cpp