IntrusiveList< T, DerivedListNode > Class Template Reference

IntrusiveList is a singly-linked list which requires its elements to derive from IntrusiveListNode (endowing them with the required forward links). More...

#include <IntrusiveList.h>

Inheritance diagram for IntrusiveList< T, DerivedListNode >:

RawIntrusiveList List of all members.

Public Member Functions

void push_front (T &element)
 Adds an element to the front of the list.
void push_back (T &element)
 Adds an element to the back of the list.
T & front () const
 
Returns:
a reference to the element at the front of the list

T & back () const
 
Returns:
a reference to the element at the back of the list

bool remove (T &element)
 Finds and removes a specified element by address (not equality).
uint size () const
 
Returns:
length of this list

bool empty () const
 
Returns:
true iff size() is zero

void clear (bool debugClear=true)
 Truncates this list to zero nodes.

Protected Member Functions

void push_front (IntrusiveListNode &t)
void push_back (IntrusiveListNode &t)
bool remove (IntrusiveListNode &)

Protected Attributes

uint nNodes
 Number of nodes in this list.
IntrusiveListNode * pFront
 First node in this list.
IntrusiveListNode * pBack
 Last node in this list.

Private Types

typedef RawIntrusiveList super

Detailed Description

template<class T, class DerivedListNode = IntrusiveListNode>
class IntrusiveList< T, DerivedListNode >

IntrusiveList is a singly-linked list which requires its elements to derive from IntrusiveListNode (endowing them with the required forward links).

This eliminates the need for dynamic allocation, which is important for some performance-critical uses. It is possible for elements to be members of multiple IntrusiveLists simultaneously; however, this requires that they derive from IntrusiveListNode multiple times (one for each link). Template parameter T is the datatype of the element stored; template parameter DerivedListNode is a class derived from IntrusiveListNode where T inherits from DerivedListNode. If T participates in only one IntrusiveList, then it can derive from IntrusiveListNode directly, and the default value for DerivedListNode can be used. Otherwise, one derivation of IntrusiveListNode per link should be defined (with an appropriate name to spell out its purpose) and specified as the DerivedListNode parameter.

Although method names have been chosen to match STL conventions, IntrusiveList is not a true STL container (likewise, IntrusiveListIter is not a true STL iterator).

Definition at line 53 of file IntrusiveList.h.

Member Typedef Documentation

template<class T, class DerivedListNode = IntrusiveListNode>
typedef RawIntrusiveList IntrusiveList< T, DerivedListNode >::super [private]

Definition at line 55 of file IntrusiveList.h.

Member Function Documentation

template<class T, class DerivedListNode = IntrusiveListNode>
void IntrusiveList< T, DerivedListNode >::push_front ( T &  element  )  [inline]

Adds an element to the front of the list.

Parameters:
element the element to add

Definition at line 63 of file IntrusiveList.h.

References RawIntrusiveList::push_front().

00064     {
00065         super::push_front(static_cast<DerivedListNode &>(element));
00066     }

template<class T, class DerivedListNode = IntrusiveListNode>
void IntrusiveList< T, DerivedListNode >::push_back ( T &  element  )  [inline]

Adds an element to the back of the list.

Parameters:
element the element to add

Definition at line 73 of file IntrusiveList.h.

References RawIntrusiveList::push_back().

Referenced by AioLinuxScheduler::deferLeftoverRequests().

00074     {
00075         super::push_back(static_cast<DerivedListNode &>(element));
00076     }

template<class T, class DerivedListNode = IntrusiveListNode>
T& IntrusiveList< T, DerivedListNode >::front (  )  const [inline]

Returns:
a reference to the element at the front of the list

Reimplemented from RawIntrusiveList.

Definition at line 81 of file IntrusiveList.h.

References RawIntrusiveList::front().

00082     {
00083         return static_cast<T &>(
00084             static_cast<DerivedListNode &>(super::front()));
00085     }

template<class T, class DerivedListNode = IntrusiveListNode>
T& IntrusiveList< T, DerivedListNode >::back (  )  const [inline]

Returns:
a reference to the element at the back of the list

Reimplemented from RawIntrusiveList.

Definition at line 90 of file IntrusiveList.h.

References RawIntrusiveList::back().

00091     {
00092         return static_cast<T &>(
00093             static_cast<DerivedListNode &>(super::back()));
00094     }

template<class T, class DerivedListNode = IntrusiveListNode>
bool IntrusiveList< T, DerivedListNode >::remove ( T &  element  )  [inline]

Finds and removes a specified element by address (not equality).

Parameters:
element the element to be removed
Returns:
true if found

Definition at line 103 of file IntrusiveList.h.

References RawIntrusiveList::remove().

00104     {
00105         return super::remove(
00106             static_cast<DerivedListNode &>(element));
00107     }

void RawIntrusiveList::push_front ( IntrusiveListNode &  t  )  [protected, inherited]

Definition at line 29 of file RawIntrusiveList.cpp.

References RawIntrusiveList::nNodes, RawIntrusiveList::pBack, RawIntrusiveList::pFront, and IntrusiveListNode::pNext.

Referenced by IntrusiveList< T, DerivedListNode >::push_front().

00030 {
00031     assert(!listNode.pNext);
00032     listNode.pNext = pFront;
00033     pFront = &listNode;
00034     if (!pBack) {
00035         pBack = pFront;
00036     }
00037     nNodes++;
00038 }

void RawIntrusiveList::push_back ( IntrusiveListNode &  t  )  [protected, inherited]

Definition at line 40 of file RawIntrusiveList.cpp.

References RawIntrusiveList::nNodes, RawIntrusiveList::pBack, RawIntrusiveList::pFront, and IntrusiveListNode::pNext.

Referenced by IntrusiveList< T, DerivedListNode >::push_back().

00041 {
00042     assert(!listNode.pNext);
00043     listNode.pNext = NULL;
00044     if (pBack) {
00045         pBack = pBack->pNext = &listNode;
00046     } else {
00047         pFront = pBack = &listNode;
00048     }
00049     nNodes++;
00050 }

bool RawIntrusiveList::remove ( IntrusiveListNode &   )  [protected, inherited]

Definition at line 68 of file RawIntrusiveList.cpp.

Referenced by IntrusiveList< T, DerivedListNode >::remove().

00069 {
00070     for (RawIntrusiveListMutator iter(*this); iter.getCurrent(); ++iter) {
00071         if (iter.getCurrent() == &listNode) {
00072             iter.detach();
00073             return 1;
00074         }
00075     }
00076     return 0;
00077 }

uint RawIntrusiveList::size (  )  const [inline, inherited]

Returns:
length of this list

Definition at line 85 of file RawIntrusiveList.h.

Referenced by AioLinuxScheduler::submitRequests().

00086     {
00087         return nNodes;
00088     }

bool RawIntrusiveList::empty (  )  const [inline, inherited]

Returns:
true iff size() is zero

Definition at line 93 of file RawIntrusiveList.h.

00094     {
00095         return nNodes ? false : true;
00096     }

void RawIntrusiveList::clear ( bool  debugClear = true  )  [inherited]

Truncates this list to zero nodes.

Parameters:
debugClear when true and a DEBUG build is in effect, pNext links of nodes are nulled out

Definition at line 52 of file RawIntrusiveList.cpp.

References RawIntrusiveList::nNodes, RawIntrusiveList::pBack, RawIntrusiveList::pFront, and IntrusiveListNode::pNext.

00053 {
00054     nNodes = 0;
00055 #ifdef DEBUG
00056     if (debugClear) {
00057         IntrusiveListNode *p = pFront;
00058         while (p) {
00059             IntrusiveListNode *pNext = p->pNext;
00060             p->pNext = NULL;
00061             p = pNext;
00062         }
00063     }
00064 #endif
00065     pFront = pBack = NULL;
00066 }

Member Data Documentation

uint RawIntrusiveList::nNodes [protected, inherited]

Number of nodes in this list.

Definition at line 46 of file RawIntrusiveList.h.

Referenced by RawIntrusiveList::clear(), RawIntrusiveListMutator::detach(), RawIntrusiveList::push_back(), and RawIntrusiveList::push_front().

IntrusiveListNode* RawIntrusiveList::pFront [protected, inherited]

First node in this list.

Definition at line 51 of file RawIntrusiveList.h.

Referenced by RawIntrusiveList::clear(), RawIntrusiveListMutator::demoteCurrToBack(), RawIntrusiveListMutator::demoteFrontBeforeCurr(), RawIntrusiveListMutator::detach(), RawIntrusiveListMutator::promoteCurrToFront(), RawIntrusiveList::push_back(), RawIntrusiveList::push_front(), RawIntrusiveListMutator::repositionToFront(), and RawIntrusiveListIter::repositionToFront().

IntrusiveListNode* RawIntrusiveList::pBack [protected, inherited]

Last node in this list.

Definition at line 56 of file RawIntrusiveList.h.

Referenced by RawIntrusiveList::clear(), RawIntrusiveListMutator::demoteCurrToBack(), RawIntrusiveListMutator::detach(), RawIntrusiveListMutator::promoteCurrToFront(), RawIntrusiveList::push_back(), and RawIntrusiveList::push_front().

The documentation for this class was generated from the following file:
Generated on Mon Jun 22 04:00:33 2009 for Fennel by  doxygen 1.5.1