#include <Containers_T.h>
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 > |
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
typedef ACE_Double_Linked_List_Iterator<T> ACE_Double_Linked_List< T >::ITERATOR |
typedef ACE_Double_Linked_List_Reverse_Iterator<T> ACE_Double_Linked_List< T >::REVERSE_ITERATOR |
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.
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.
ACE_Double_Linked_List< T >::~ACE_Double_Linked_List | ( | void | ) | [inline] |
Destructor.
Clean up the memory allocated for the nodes of the list.
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.
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.
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.
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.
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.
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 >.
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 >.
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.
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.
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.
void ACE_Double_Linked_List< T >::dump | ( | void | ) | const [inline] |
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 >.
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.
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.
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.
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.
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.
friend class ACE_Double_Linked_List_Iterator_Base< T > [friend] |
friend class ACE_Double_Linked_List_Iterator< T > [friend] |
Reimplemented in ACE_DLList< T >.
friend class ACE_Double_Linked_List_Reverse_Iterator< T > [friend] |
ACE_Double_Linked_List< T >::ACE_ALLOC_HOOK_DECLARE |
Declare the dynamic allocation hooks.
T* ACE_Double_Linked_List< T >::head_ [protected] |
Head of the circular double-linked list.
size_t ACE_Double_Linked_List< T >::size_ [protected] |
Size of this list.
ACE_Allocator* ACE_Double_Linked_List< T >::allocator_ [protected] |
Allocation Strategy of the queue.