Implement an intrusive double linked list. More...

#include <Intrusive_List.h>

Collaboration diagram for ACE_Intrusive_List< T >:

Public Member Functions
	ACE_Intrusive_List (void)
	~ACE_Intrusive_List (void)
	Destructor.
bool	is_empty (void) const
	Returns true if the container is empty, otherwise returns false.
bool	empty (void) const
void	push_front (T *node)
	Insert an element at the beginning of the list.
void	push_back (T *node)
	Insert an element at the end of the list.
T *	pop_front (void)
	Remove the element at the beginning of the list.
T *	pop_back (void)
	Remove the element at the end of the list.
T *	head (void) const
	Get the element at the head of the queue.
T *	tail (void) const
	Get the element at the tail of the queue.
void	remove (T *node)
	Remove a element from the list.
void	swap (ACE_Intrusive_List< T > &rhs)
	Swap two lists.
void	unsafe_remove (T *node)
	Remove a element from the list without checking.
Private Member Functions
Disallow copying

	ACE_Intrusive_List (const ACE_Intrusive_List< T > &)
ACE_Intrusive_List< T > &	operator= (const ACE_Intrusive_List< T > &)
Private Attributes
T *	head_
	Head of the list.
T *	tail_
	Tail of the list.

Detailed Description

template<class T>
class ACE_Intrusive_List< T >

Implement an intrusive double linked list.

Intrusive lists assume that the elements they contain the pointers required to build the list. They are useful as light-weight containers and free-lists.

The template argument T must implement the following methods:

T* T::next () const;
void T::next (T *);
T* T::prev () const;
void T::prev (T* );

A simple way to satisfy the Intrusive_List requirements would be to implement a helper class:

class My_Object : public ACE_Intrusive_List_Node<My_Object> {
....
};

typedef ACE_Intrusive_List<My_Object> My_Object_List;

However, ACE is supported on platforms that would surely get confused using such templates.

Todo:: The ACE_Message_Queue is an example of an intrusive list (or queue) but it is not implemented in terms of this class.

Definition at line 58 of file Intrusive_List.h.

Constructor & Destructor Documentation

template<class T >

ACE_Intrusive_List< T >::ACE_Intrusive_List ( void )

Constructor. Use user specified allocation strategy if specified.

Definition at line 19 of file Intrusive_List.cpp.

  : head_ (0)
  , tail_ (0)
{
}

template<class T >

ACE_Intrusive_List< T >::~ACE_Intrusive_List ( void )

Destructor.

Definition at line 26 of file Intrusive_List.cpp.

{
}

template<class T>

ACE_Intrusive_List< T >::ACE_Intrusive_List ( const ACE_Intrusive_List< T > & ) [private]

Member Function Documentation

template<class T >

bool ACE_Intrusive_List< T >::empty ( void ) const [inline]

Returns true if the container is empty, otherwise returns false.

Deprecated:: Use is_empty() instead.

Definition at line 16 of file Intrusive_List.inl.

{
  return this->is_empty ();
}

template<class T >

T * ACE_Intrusive_List< T >::head ( void ) const [inline]

Get the element at the head of the queue.

Definition at line 22 of file Intrusive_List.inl.

{
  return this->head_;
}

template<class T >

bool ACE_Intrusive_List< T >::is_empty ( void ) const [inline]

Returns true if the container is empty, otherwise returns false.

Definition at line 10 of file Intrusive_List.inl.

{
  return this->head_ == 0;
}

template<class T>

ACE_Intrusive_List<T>& ACE_Intrusive_List< T >::operator= ( const ACE_Intrusive_List< T > & ) [private]

template<class T >

T * ACE_Intrusive_List< T >::pop_back ( void )

Remove the element at the end of the list.

Definition at line 80 of file Intrusive_List.cpp.

{
  T *node = this->tail_;
  if (node != 0)
    {
      this->unsafe_remove (node);
    }
  return node;
}

template<class T >

T * ACE_Intrusive_List< T >::pop_front ( void )

Remove the element at the beginning of the list.

Definition at line 69 of file Intrusive_List.cpp.

{
  T *node = this->head_;
  if (node != 0)
    {
      this->unsafe_remove (node);
    }
  return node;
}

template<class T>

void ACE_Intrusive_List< T >::push_back ( T * node )

Insert an element at the end of the list.

Definition at line 31 of file Intrusive_List.cpp.

{
  if (this->tail_ == 0)
    {
      this->tail_ = node;
      this->head_ = node;
      node->next (0);
      node->prev (0);
    }
  else
    {
      this->tail_->next (node);
      node->prev (this->tail_);
      node->next (0);
      this->tail_ = node;
    }
}

template<class T>

void ACE_Intrusive_List< T >::push_front ( T * node )

Insert an element at the beginning of the list.

Definition at line 50 of file Intrusive_List.cpp.

{
  if (this->head_ == 0)
    {
      this->tail_ = node;
      this->head_ = node;
      node->next (0);
      node->prev (0);
    }
  else
    {
      this->head_->prev (node);
      node->next (this->head_);
      node->prev (0);
      this->head_ = node;
    }
}

template<class T>

void ACE_Intrusive_List< T >::remove ( T * node )

Remove a element from the list.

Verify that the element is still in the list before removing it.

Definition at line 91 of file Intrusive_List.cpp.

{
  for (T *i = this->head_; i != 0; i = i->next ())
    {
      if (node == i)
        {
          this->unsafe_remove (node);
          return;
        }
    }
}

template<class T>

void ACE_Intrusive_List< T >::swap ( ACE_Intrusive_List< T > & rhs ) [inline]

Swap two lists.

Definition at line 34 of file Intrusive_List.inl.

{
  std::swap(head_, rhs.head_);
  std::swap(tail_, rhs.tail_);
}

template<class T >

T * ACE_Intrusive_List< T >::tail ( void ) const [inline]

Get the element at the tail of the queue.

Definition at line 28 of file Intrusive_List.inl.

{
  return this->tail_;
}

template<class T>

void ACE_Intrusive_List< T >::unsafe_remove ( T * node )

Remove a element from the list without checking.

No attempts are performed to check if T* really belongs to the list. The effects of removing an invalid element are unspecified

Definition at line 104 of file Intrusive_List.cpp.

{
  if (node->prev () != 0)
    node->prev ()->next (node->next ());
  else
    this->head_ = node->next ();

  if (node->next () != 0)
    node->next ()->prev (node->prev ());
  else
    this->tail_ = node->prev ();

  node->next (0);
  node->prev (0);
}

Member Data Documentation

template<class T>

T* ACE_Intrusive_List< T >::head_ [private]

Head of the list.

Definition at line 123 of file Intrusive_List.h.

template<class T>

T* ACE_Intrusive_List< T >::tail_ [private]

Tail of the list.

Definition at line 126 of file Intrusive_List.h.

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

ACE_Intrusive_List< T > Class Template Reference

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class T> class ACE_Intrusive_List< T >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class T>
class ACE_Intrusive_List< T >