Data Structures | Public Types | Public Member Functions | Protected Attributes | Friends

IntrusiveDList< T, N, P > Class Template Reference

Intrusive doubly linked list container. More...

#include <IntrusiveDList.h>

Collaboration diagram for IntrusiveDList< T, N, P >:
Collaboration graph
[legend]

Data Structures

class  iterator
 STL style iterator for access to elements. More...

Public Types

typedef IntrusiveDList self
 Self reference type.
typedef T element_type
 Type of list element.

Public Member Functions

 IntrusiveDList ()
 Default constructor (empty list).
bool isEmpty () const
 Empty check.
self & prepend (T *elt)
 Add elt as the first element in the list.
self & append (T *elt)
 Add as the last element in the list.
T * takeHead ()
 Remove the first element of the list.
T * takeTail ()
 Remove the last element of the list.
self & insertAfter (T *target, T *elt)
 Insert a new element elt after target.
self & insertBefore (T *target, T *elt)
 Insert a new element elt before target.
self & take (T *elt)
 Take elt out of this list.
self & clear ()
 Remove all elements.
size_t getCount () const
iterator begin ()
 Get an iterator to the first element.
iterator end ()
 Get an iterator to past the last element.
T * getHead ()
 Get the first element.
T * getTail ()
 Get the last element.

Protected Attributes

T * _head
 First element in list.
T * _tail
 Last element in list.
size_t _count
 # of elements in list.

Friends

class iterator

Detailed Description

template<typename T, T *T::* N, T *T::* P>
class IntrusiveDList< T, N, P >

Intrusive doubly linked list container.

This holds items in a doubly linked list using members of the items. Elements are copied in to the list. No memory management is done by the list implementation.

To use this class a client should create the structure for elements of the list and ensure that it has two self pointers to be used by the list. For example,

      struct Elt {
        int _payload;
        Elt* _next;
        Elt* _prev;
      };

The list is declared as 

      typedef IntrusiveDList<Elt, &Elt::_next, &Elt::_prev> EltList;

An element can be in multiple types of lists simultaneously as long as each list type uses distinct members. It is not possible for an element to be in more than one list of the same type simultaneously. This is intrinsic to intrusive list support.

Element access is done by using either STL style iteration, or direct access to the member pointers. A client can have its own mechanism for getting an element to start, or use the getHead and/or getTail methods to get the first and last elements in the list respectively.

Note:
Due to bugs in various compilers or the C++ specification (or both) it is not possible in general to declare the element pointers in a super class. The template argument T must be exactly the same T as for the element pointers, even though a pointer to member of a superclass should be trivially coerced to a pointer to member of subclass. MSVC permits an explicit cast in this case, but gcc does not and therefore there is no way to do this. It is most vexing.

P.S. I think it's a compiler bug personally with regard to the type of an expression of the form &T::M is not T::* if M is declared in a superclass S. In that case the type is S::* which seems very wrong to me.

Definition at line 106 of file IntrusiveDList.h.

Member Typedef Documentation

template<typename T, T *T::* N, T *T::* P>
typedef T IntrusiveDList< T, N, P >::element_type

Type of list element.

Definition at line 110 of file IntrusiveDList.h.

template<typename T, T *T::* N, T *T::* P>
typedef IntrusiveDList IntrusiveDList< T, N, P >::self

Self reference type.

Definition at line 109 of file IntrusiveDList.h.

Constructor & Destructor Documentation

template<typename T, T *T::* N, T *T::* P>
IntrusiveDList< T, N, P >::IntrusiveDList (  )  [inline]

Default constructor (empty list).

Definition at line 182 of file IntrusiveDList.h.

Member Function Documentation

template<typename T, T *T::* N, T *T::* P>
self& IntrusiveDList< T, N, P >::append ( T *  elt  )  [inline]

Add as the last element in the list.

Returns:
This container.
Parameters:
elt Element to add.

Definition at line 201 of file IntrusiveDList.h.

Referenced by ts::detail::IpMapBase< N >::append().

template<typename T, T *T::* N, T *T::* P>
iterator IntrusiveDList< T, N, P >::begin (  )  [inline]

Get an iterator to the first element.

Definition at line 297 of file IntrusiveDList.h.

template<typename T, T *T::* N, T *T::* P>
self& IntrusiveDList< T, N, P >::clear ( void   )  [inline]

Remove all elements.

Note:
No memory management is done!
Returns:
This container.

Definition at line 292 of file IntrusiveDList.h.

Referenced by ts::detail::IpMapBase< N >::clear().

template<typename T, T *T::* N, T *T::* P>
iterator IntrusiveDList< T, N, P >::end (  )  [inline]

Get an iterator to past the last element.

Definition at line 299 of file IntrusiveDList.h.

template<typename T, T *T::* N, T *T::* P>
size_t IntrusiveDList< T, N, P >::getCount (  )  const [inline]
Returns:
Number of elements in the list.

Definition at line 294 of file IntrusiveDList.h.

Referenced by ts::detail::IpMapBase< N >::getCount().

template<typename T, T *T::* N, T *T::* P>
T* IntrusiveDList< T, N, P >::getHead (  )  [inline]

Get the first element.

Definition at line 301 of file IntrusiveDList.h.

Referenced by ts::detail::IpMapBase< N >::clear(), ts::detail::IpMapBase< Ip6Node >::getHead(), ts::detail::IpMapBase< N >::prepend(), ts::detail::IpMapBase< N >::print(), and ts::detail::IpMapBase< N >::validate().

template<typename T, T *T::* N, T *T::* P>
T* IntrusiveDList< T, N, P >::getTail (  )  [inline]

Get the last element.

Definition at line 303 of file IntrusiveDList.h.

Referenced by ts::detail::IpMapBase< N >::append(), and ts::detail::IpMapBase< Ip6Node >::getTail().

template<typename T, T *T::* N, T *T::* P>
self& IntrusiveDList< T, N, P >::insertAfter ( T *  target,
T *  elt 
) [inline]

Insert a new element elt after target.

The caller is responsible for ensuring target is in this list and elt is not in a list.

Returns:
This list.
Parameters:
target Target element in list.
elt Element to insert.

Definition at line 246 of file IntrusiveDList.h.

Referenced by ts::detail::IpMapBase< N >::insertAfter().

template<typename T, T *T::* N, T *T::* P>
self& IntrusiveDList< T, N, P >::insertBefore ( T *  target,
T *  elt 
) [inline]

Insert a new element elt before target.

The caller is responsible for ensuring target is in this list and elt is not in a list.

Returns:
This list.
Parameters:
target Target element in list.
elt Element to insert.

Definition at line 263 of file IntrusiveDList.h.

Referenced by ts::detail::IpMapBase< N >::insertBefore().

template<typename T, T *T::* N, T *T::* P>
bool IntrusiveDList< T, N, P >::isEmpty (  )  const [inline]

Empty check.

Returns:
true if the list is empty.

Definition at line 185 of file IntrusiveDList.h.

template<typename T, T *T::* N, T *T::* P>
self& IntrusiveDList< T, N, P >::prepend ( T *  elt  )  [inline]

Add elt as the first element in the list.

Returns:
This container.
Parameters:
elt Element to add.

Definition at line 188 of file IntrusiveDList.h.

Referenced by ts::detail::IpMapBase< N >::prepend().

template<typename T, T *T::* N, T *T::* P>
self& IntrusiveDList< T, N, P >::take ( T *  elt  )  [inline]

Take elt out of this list.

Returns:
This list.
Parameters:
elt Element to remove.

Definition at line 278 of file IntrusiveDList.h.

Referenced by ts::detail::IpMapBase< N >::remove().

template<typename T, T *T::* N, T *T::* P>
T* IntrusiveDList< T, N, P >::takeHead (  )  [inline]

Remove the first element of the list.

Returns:
A poiner to the removed item, or NULL if the list was empty.

Definition at line 214 of file IntrusiveDList.h.

template<typename T, T *T::* N, T *T::* P>
T* IntrusiveDList< T, N, P >::takeTail (  )  [inline]

Remove the last element of the list.

Returns:
A poiner to the removed item, or NULL if the list was empty.

Definition at line 229 of file IntrusiveDList.h.

Friends And Related Function Documentation

template<typename T, T *T::* N, T *T::* P>
friend class iterator [friend]

Definition at line 107 of file IntrusiveDList.h.

Referenced by IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::begin(), and IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::end().

Field Documentation

template<typename T, T *T::* N, T *T::* P>
size_t IntrusiveDList< T, N, P >::_count [protected]

# of elements in list.

Definition at line 307 of file IntrusiveDList.h.

Referenced by IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::append(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::clear(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::getCount(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::insertAfter(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::insertBefore(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::prepend(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::take(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::takeHead(), and IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::takeTail().

template<typename T, T *T::* N, T *T::* P>
T* IntrusiveDList< T, N, P >::_head [protected]

First element in list.

Definition at line 305 of file IntrusiveDList.h.

Referenced by IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::append(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::begin(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::clear(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::getHead(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::insertBefore(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::isEmpty(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::prepend(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::take(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::takeHead(), and IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::takeTail().

template<typename T, T *T::* N, T *T::* P>
T* IntrusiveDList< T, N, P >::_tail [protected]

Last element in list.

Definition at line 306 of file IntrusiveDList.h.

Referenced by IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::append(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::clear(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::getTail(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::insertAfter(), IntrusiveDList< T, N, P >::iterator::operator--(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::prepend(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::take(), IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::takeHead(), and IntrusiveDList< RBNode,&RBNode::_next,&RBNode::_prev >::takeTail().

The documentation for this class was generated from the following file:
Generated by  doxygen 1.7.1