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


Member Typedef Documentation


Constructor & Destructor Documentation

template<class T>
ACE_Double_Linked_List< T >::ACE_Double_Linked_List ( ACE_Allocator the_allocator = 0  )  [inline]

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.

template<class T>
ACE_Double_Linked_List< T >::ACE_Double_Linked_List ( const ACE_Double_Linked_List< T > &  cx  )  [inline]

Copy constructor.

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   )  [inline]

Destructor.

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


Member Function Documentation

template<class T>
void ACE_Double_Linked_List< T >::operator= ( const ACE_Double_Linked_List< T > &  cx  )  [inline]

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.

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

Returns 1 if the container is empty, 0 otherwise.

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

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

The list is unbounded, so this always returns 0.

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

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

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.

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

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.

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

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

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

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

template<class T>
void ACE_Double_Linked_List< T >::reset ( void   )  [inline]

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.

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

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.

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

The number of items in the queue.

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

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

Dump the state of an object.

Reimplemented in ACE_DLList< T >.

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

Use DNode address directly.

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

Reimplemented in ACE_DLList< T >.

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

Delete all the nodes in the list.

Removes and deallocates memory for all of the list nodes.

template<class T>
void ACE_Double_Linked_List< T >::copy_nodes ( const ACE_Double_Linked_List< T > &  rhs  )  [inline, 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.

template<class T>
void ACE_Double_Linked_List< T >::init_head ( void   )  [inline, 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.

template<class T>
int ACE_Double_Linked_List< T >::insert_element ( T *  new_item,
int  before = 0,
T *  old_item = 0 
) [inline, 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.

template<class T>
int ACE_Double_Linked_List< T >::remove_element ( T *  item  )  [inline, 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.


Friends And Related Function Documentation

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

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

Reimplemented in ACE_DLList< T >.

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


Member Data Documentation

Declare the dynamic allocation hooks.

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

Head of the circular double-linked list.

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

Size of this list.

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

Allocation Strategy of the queue.


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

Generated on Wed Apr 23 02:38:54 2008 for ACE by  doxygen 1.5.5