RTT::SingleList< DataType_ > Class Template Reference

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

#include <rtt/SingleList.hpp>

List of all members.

Public Types
typedef DataType_	DataType
Public Member Functions
	SingleList ()
	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	searchKey (const DataType &search_key, Node_sptr &left_node)
template<class F >
Node_sptr	searchEnd (const F &foo, 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::SingleList< DataType_ >

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

Harris. It will never work on 8bit computers as implemented here but 16, 32, 64,... computers are fine. You may not insert the same item more than once.

Note:

This list is not, and should not, be used in the Orocos Framework.

See also:

ListLockFree for a far better lock-free list implementation.

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 SingleList.

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 single.

Definition at line 65 of file SingleList.hpp.

---

Member Function Documentation

template<class DataType_ >

template<class Function >

void RTT::SingleList< 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 340 of file SingleList.hpp.

template<class DataType_ >

template<class Function >

void RTT::SingleList< DataType_ >::applyOnData

(

const Function &

f

)

[inline]

Applies a function to all elements.

For example:

         SingleList<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 309 of file SingleList.hpp.

template<class DataType_ >

bool RTT::SingleList< 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 258 of file SingleList.hpp.

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

template<class DataType_ >

bool RTT::SingleList< 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 283 of file SingleList.hpp.

template<class DataType_ >

bool RTT::SingleList< 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 235 of file SingleList.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/SingleList.hpp