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=

Member Typedef Documentation

template<class T>

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

template<class T>

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

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.

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.

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.

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.

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

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.

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

template<class T >

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

Dump the state of an object.

Reimplemented in ACE_DLList< T >.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.