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)
Node *	get_unmarked_reference (Node *n)
Node *	get_marked_reference (Node *n)
Protected Attributes
MemoryPool< Node >	mpool
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:

• rtt/SortedList.hpp