RTT::SortedList< DataType_ > Class Template Reference

A single-linked sorted list algorithm invented by Timothy L. More...

#include <rtt/SortedList.hpp>

List of all members.

Public Types

typedef DataType_ DataType

Public Member Functions

 SortedList ()
 Create an empty list.
void reserve (size_t n=1)
 Reserve memory for one list item.
void shrink (size_t n=1)
 Free memory for one list item.
bool empty () const
 Inspect if the list is empty.
bool insert (const DataType &key)
 Insert a new node.
bool erase (const DataType &search_key)
 Erase a node.
bool hasKey (const DataType &search_key)
 Check if a node is present.
template<class Function >
void applyOnData (const Function &f)
 Applies a function to all elements.
template<class Function >
void applyOnCopy (const Function &f)
 This is a safer version of apply() with respect to concurrent erasure/insertion.

Protected Types

typedef NodeType Node
 Node type.
typedef NodeType::NodeType_sptr Node_sptr
 Node shared pointer type.

Protected Member Functions

Node_sptr search (const DataType &search_key, Node_sptr &left_node)
bool is_marked_reference (Node *n)
Nodeget_unmarked_reference (Node *n)
Nodeget_marked_reference (Node *n)

Protected Attributes

MemoryPool< Nodempool
Node_sptr head
Node_sptr tail

Detailed Description

template<class DataType_>
class RTT::SortedList< DataType_ >

A single-linked sorted list algorithm invented by Timothy L.

Harris. This implementation is only for 32bit computers. You may not insert the same item more than once.

The difference between this implementation and Harris' is that we use a self-invented memory pool (MemoryPool) for lock-free/hard real-time memory management and an apply() function to manipulate the data within the SortedList.

Parameters:
DataType_ Must be a pointer type or integer or any object which has or for which you defined an operator<() and operator==() since the list is sorted.
Deprecated:
This class is nowhere used and not unit tested.

Definition at line 63 of file SortedList.hpp.


Member Function Documentation

template<class DataType_ >
template<class Function >
void RTT::SortedList< DataType_ >::applyOnCopy ( const Function &  f  )  [inline]

This is a safer version of apply() with respect to concurrent erasure/insertion.

First a copy of the data is made, then the node is checked if it is still present, if so the function is applied on the copied data, thus the data is for sure not corrupted.

Definition at line 301 of file SortedList.hpp.

template<class DataType_ >
template<class Function >
void RTT::SortedList< DataType_ >::applyOnData ( const Function &  f  )  [inline]

Applies a function to all elements.

For example:

         SortedList<CallBackInterface*> sl;
         // insert elements...
         // call the 'callback' function on each element:
         sl.apply( boost::bind(&CallBackInterface::callback, _1) );
         
Parameters:
f A Function object to apply to each element.
Warning:
You may not apply functions to the elements which change the relative results of operator<() or operator==() of the contained elements.

Definition at line 270 of file SortedList.hpp.

template<class DataType_ >
bool RTT::SortedList< DataType_ >::erase ( const DataType &  search_key  )  [inline]

Erase a node.

Parameters:
key An inserted key object.
Returns:
true on success, false if key not present in list.

Definition at line 219 of file SortedList.hpp.

References RTT::OS::CAS(), and RTT::MemoryPool< T >::deallocate().

template<class DataType_ >
bool RTT::SortedList< DataType_ >::hasKey ( const DataType &  search_key  )  [inline]

Check if a node is present.

Parameters:
key A key object.
Returns:
true if present, false if key not present in list.

Definition at line 244 of file SortedList.hpp.

template<class DataType_ >
bool RTT::SortedList< DataType_ >::insert ( const DataType &  key  )  [inline]

Insert a new node.

Parameters:
key A not yet inserted key object.
Returns:
true on success, false if key already present in list.

Definition at line 196 of file SortedList.hpp.

References RTT::MemoryPool< T >::allocate(), RTT::OS::CAS(), and RTT::MemoryPool< T >::deallocate().


The documentation for this class was generated from the following file:
Generated on Thu Dec 23 13:22:44 2010 for Orocos Real-Time Toolkit by  doxygen 1.6.3