Classes | Public Types | Public Member Functions | Public Attributes | Private Types | Private Member Functions | Private Attributes
RTT::internal::ListLockFree< T > Class Template Reference

#include <ListLockFree.hpp>

Inheritance diagram for RTT::internal::ListLockFree< T >:
Inheritance graph
[legend]

List of all members.

Classes

struct  Item
struct  StorageImpl

Public Types

typedef T value_t

Public Member Functions

bool append (value_t item)
size_t append (const std::vector< T > &items)
template<class Function >
void apply (Function func)
template<class Function >
void apply_and_blank (Function func, value_t blank)
value_t back () const
size_t capacity () const
void clear ()
template<typename Pred >
bool delete_if (Pred pred)
bool empty () const
bool erase (value_t item)
bool erase_and_blank (value_t item, value_t blank)
template<class Function >
value_t find_if (Function func, value_t blank=value_t())
value_t front () const
void grow (size_t items=1)
 ListLockFree (unsigned int lsize, unsigned int threads=ORONUM_OS_MAX_THREADS)
void reserve (size_t lsize)
void shrink (size_t items=1)
size_t size () const
 ~ListLockFree ()

Public Attributes

const unsigned int MAX_THREADS
 The maximum number of threads.

Private Types

typedef std::vector< value_tBufferType
typedef BufferType::const_iterator CIterator
typedef BufferType::iterator Iterator
typedef boost::intrusive_ptr
< StorageImpl
Storage

Private Member Functions

size_t BufNum () const
ItemfindEmptyBuf (Storage &bufptr)
ItemlockAndGetActive (Storage &bufptr) const
ItemlockAndGetActive () const
ItemlockAndGetBlank (Storage &bufptr) const
Storage newStorage (size_t alloc, size_t items, bool init=true)
bool pointsTo (Item *p, const Storage &bf) const

Private Attributes

Item *volatile active
Item *volatile blankp
Storage bufs
size_t required

Detailed Description

template<class T>
class RTT::internal::ListLockFree< T >

A simple lock-free list implementation to append or erase data of type T. If T is a value type, no memory allocation is done during appending or erasing. The maximum number of threads which can access this object is defined by MAX_THREADS.

Parameters:
TThe value type to be stored in the list. If T is a type that does memory allocation or deallocation in copy-constructor or destructor, certain functions of this list will not be real-time. Example : ListLockFree is a list which holds values of type A.

Definition at line 85 of file ListLockFree.hpp.


Member Typedef Documentation

template<class T>
typedef std::vector<value_t> RTT::internal::ListLockFree< T >::BufferType [private]

Definition at line 97 of file ListLockFree.hpp.

template<class T>
typedef BufferType::const_iterator RTT::internal::ListLockFree< T >::CIterator [private]

Definition at line 99 of file ListLockFree.hpp.

template<class T>
typedef BufferType::iterator RTT::internal::ListLockFree< T >::Iterator [private]

Definition at line 98 of file ListLockFree.hpp.

template<class T>
typedef boost::intrusive_ptr<StorageImpl> RTT::internal::ListLockFree< T >::Storage [private]

The intrusive_ptr is far more thread-safe than the shared_ptr for 'reads' during 'assignments'.

Definition at line 126 of file ListLockFree.hpp.

template<class T>
typedef T RTT::internal::ListLockFree< T >::value_t

Definition at line 95 of file ListLockFree.hpp.


Constructor & Destructor Documentation

template<class T>
RTT::internal::ListLockFree< T >::ListLockFree ( unsigned int  lsize,
unsigned int  threads = ORONUM_OS_MAX_THREADS 
) [inline]

Create a lock-free list wich can store lsize elements.

Parameters:
lsizethe capacity of the list.
threadsthe number of threads which may concurrently read or write this buffer. Defaults to ORONUM_OS_MAX_THREADS, but you may lower this number in case not all threads will read this buffer. A lower number will consume less memory. '

Definition at line 164 of file ListLockFree.hpp.

template<class T>
RTT::internal::ListLockFree< T >::~ListLockFree ( ) [inline]

Definition at line 171 of file ListLockFree.hpp.


Member Function Documentation

template<class T>
bool RTT::internal::ListLockFree< T >::append ( value_t  item) [inline]

Append a single value to the list. This function calls the copy-constructor of item and may call the destructor of item

Parameters:
itemthe value to write
Returns:
false if the list is full.
Note:
This function is only real-time if the destructor or copy-constructor of of T is real-time.

Definition at line 344 of file ListLockFree.hpp.

template<class T>
size_t RTT::internal::ListLockFree< T >::append ( const std::vector< T > &  items) [inline]

Append a sequence of values to the list.

Parameters:
itemsthe values to append.
Returns:
the number of values written (may be less than d.size())
Note:
This function is only real-time if the destructor and copy-constructor of of T is real-time.

Definition at line 401 of file ListLockFree.hpp.

template<class T>
template<class Function >
void RTT::internal::ListLockFree< T >::apply ( Function  func) [inline]

Apply a function to the elements of the whole list.

Parameters:
funcThe function to apply.
Note:
Always real-time.

Definition at line 524 of file ListLockFree.hpp.

template<class T>
template<class Function >
void RTT::internal::ListLockFree< T >::apply_and_blank ( Function  func,
value_t  blank 
) [inline]

Apply a function to the non-blanked elements of the list. If during an apply_and_blank, the erase_and_blank function is called, that element will not be subject to func if not yet processed. You must not call this function concurrently from multiple threads.

Parameters:
funcThe function to apply.
blankThe 'blank' item. Each item of this list will be compared to this item using operator==(), if it matches, it is considered blank, and func is not applied.
See also:
erase_and_blank
Deprecated:
This complicated function is nowhere used.
Note:
This function is only real-time if the destructor and copy-constructor of of T is real-time.

Definition at line 552 of file ListLockFree.hpp.

template<class T>
value_t RTT::internal::ListLockFree< T >::back ( ) const [inline]

Returns the last element of the list.

Definition at line 385 of file ListLockFree.hpp.

template<class T>
size_t RTT::internal::ListLockFree< T >::BufNum ( ) const [inline, private]

Definition at line 150 of file ListLockFree.hpp.

template<class T>
size_t RTT::internal::ListLockFree< T >::capacity ( ) const [inline]

Returns the maximum number of elements this list can hold.

Note:
Always real-time.

Definition at line 178 of file ListLockFree.hpp.

template<class T>
void RTT::internal::ListLockFree< T >::clear ( ) [inline]

Clears all elements in the list.

Postcondition:
this->empty() == true
Note:
This function is not real-time if the destructor of of T is not real-time.

Definition at line 316 of file ListLockFree.hpp.

template<class T>
template<typename Pred >
bool RTT::internal::ListLockFree< T >::delete_if ( Pred  pred) [inline]

Erase a value from the list.

Parameters:
functioneach elements for which pred returns true are removed
Returns:
true if at least one element has been removed
Note:
This function is only real-time if the destructor and copy-constructor of of T is real-time.

Definition at line 480 of file ListLockFree.hpp.

template<class T>
bool RTT::internal::ListLockFree< T >::empty ( ) const [inline]

Returns true if this list is empty.

Note:
Always real-time.

Definition at line 206 of file ListLockFree.hpp.

template<class T>
bool RTT::internal::ListLockFree< T >::erase ( value_t  item) [inline]

Erase a value from the list.

Parameters:
itemis to be erased from the list.
Returns:
true if found and erased.
Note:
This function is only real-time if the destructor and copy-constructor of of T is real-time.

Definition at line 438 of file ListLockFree.hpp.

template<class T>
bool RTT::internal::ListLockFree< T >::erase_and_blank ( value_t  item,
value_t  blank 
) [inline]

Erase an element from the list and blank it if possible. If during an apply_and_blank, the erase_and_blank function is called, that element will not be subject to func if not yet processed. You may call this function concurrently from multiple threads.

Warning:
It is possible that item is being processed within apply_and_blank. In that case the 'blank' operation has no effect.
Parameters:
itemThe item to erase from the list.
blankThe 'blank' item to use to blank item from the list.
See also:
apply_and_blank
Deprecated:
This complicated function is nowhere used.
Note:
This function is only real-time if the destructor and copy-constructor of of T is real-time.

Definition at line 597 of file ListLockFree.hpp.

template<class T>
template<class Function >
value_t RTT::internal::ListLockFree< T >::find_if ( Function  func,
value_t  blank = value_t() 
) [inline]

Find an item in the list such that func( item ) == true.

Parameters:
blankThe value to return if not found.
Returns:
The item that matches func(item) or blank if none matches.
Note:
This function is only real-time if the copy-constructor of of T is real-time.

Definition at line 626 of file ListLockFree.hpp.

template<class T>
Item* RTT::internal::ListLockFree< T >::findEmptyBuf ( Storage bufptr) [inline, private]

Item returned is guaranteed to point into bufptr. This function calls all destructors of all old elements in the empty buf, by using the std::vector::clear() function. This means that if a destructor of T is not real-time, all functions calling this function are not real-time as well. For example, append() and erase().

Definition at line 649 of file ListLockFree.hpp.

template<class T>
value_t RTT::internal::ListLockFree< T >::front ( ) const [inline]

Returns the first element of the list.

Note:
This function is only real-time if the copy-constructor of of T is real-time.

Definition at line 373 of file ListLockFree.hpp.

template<class T>
void RTT::internal::ListLockFree< T >::grow ( size_t  items = 1) [inline]

Grow the capacity to contain at least n additional items. This method tries to avoid too much re-allocations, by growing a bit more than required every N invocations and growing nothing in between.

Parameters:
itemsThe number of items to at least additionally reserve.
Note:
Almost never real-time.

Definition at line 224 of file ListLockFree.hpp.

template<class T>
Item* RTT::internal::ListLockFree< T >::lockAndGetActive ( Storage bufptr) const [inline, private]

Item returned is guaranteed to point into bufptr.

Note:
Always real-time.

Definition at line 670 of file ListLockFree.hpp.

template<class T>
Item* RTT::internal::ListLockFree< T >::lockAndGetActive ( ) const [inline, private]

Only to be used by reserve() ! Caller must guarantee that active points to valid memory.

Note:
Always real-time

Definition at line 698 of file ListLockFree.hpp.

template<class T>
Item* RTT::internal::ListLockFree< T >::lockAndGetBlank ( Storage bufptr) const [inline, private]

Get the blank buffer or null if no apply_and_blank operation going on.

Definition at line 716 of file ListLockFree.hpp.

template<class T>
Storage RTT::internal::ListLockFree< T >::newStorage ( size_t  alloc,
size_t  items,
bool  init = true 
) [inline, private]

Definition at line 128 of file ListLockFree.hpp.

template<class T>
bool RTT::internal::ListLockFree< T >::pointsTo ( Item p,
const Storage bf 
) const [inline, private]

Definition at line 739 of file ListLockFree.hpp.

template<class T>
void RTT::internal::ListLockFree< T >::reserve ( size_t  lsize) [inline]

Reserve a capacity for this list. If you wish to invoke this method concurrently, guard it with a mutex. The other methods may be invoked concurrently with this method.

Parameters:
lsizethe minimal number of items this list will be able to hold. Will not drop below the current capacity() and this method will do nothing if lsize < this->capacity(). @ Not real-time if lsize <= this->capacity().

Definition at line 252 of file ListLockFree.hpp.

template<class T>
void RTT::internal::ListLockFree< T >::shrink ( size_t  items = 1) [inline]

Shrink the capacity with at most n items. This method does not actually free memory, it just prevents a (number of) subsequent grow() invocations to allocate more memory.

Parameters:
itemsThe number of items to at most remove from the capacity.
Note:
Always real-time.

Definition at line 238 of file ListLockFree.hpp.

template<class T>
size_t RTT::internal::ListLockFree< T >::size ( ) const [inline]

Returns the current number of elements in this list.

Note:
Always real-time.

Definition at line 192 of file ListLockFree.hpp.


Member Data Documentation

template<class T>
Item* volatile RTT::internal::ListLockFree< T >::active [private]

Definition at line 144 of file ListLockFree.hpp.

template<class T>
Item* volatile RTT::internal::ListLockFree< T >::blankp [private]

Definition at line 145 of file ListLockFree.hpp.

template<class T>
Storage RTT::internal::ListLockFree< T >::bufs [private]

Definition at line 143 of file ListLockFree.hpp.

template<class T>
const unsigned int RTT::internal::ListLockFree< T >::MAX_THREADS

The maximum number of threads.

The number of threads which may concurrently access this buffer.

Definition at line 93 of file ListLockFree.hpp.

template<class T>
size_t RTT::internal::ListLockFree< T >::required [private]

Definition at line 154 of file ListLockFree.hpp.


The documentation for this class was generated from the following file:


rtt
Author(s): RTT Developers
autogenerated on Thu Jan 2 2014 11:35:44