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
typedef T value_t

Public Member Functions

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

Public Attributes

const unsigned int MAX_THREADS
 The maximum number of threads.

Private Types

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

Private Member Functions

size_t BufNum () const
size_t BufNum () const
Item * findEmptyBuf (Storage &bufptr)
Item * findEmptyBuf (Storage &bufptr)
Item * lockAndGetActive () const
Item * lockAndGetActive (Storage &bufptr) const
Item * lockAndGetActive () const
Item * lockAndGetActive (Storage &bufptr) const
Item * lockAndGetBlank (Storage &bufptr) const
Item * lockAndGetBlank (Storage &bufptr) const
Storage newStorage (size_t alloc, size_t items, bool init=true)
Storage newStorage (size_t alloc, size_t items, bool init=true)
bool pointsTo (Item *p, const Storage &bf) const
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:
T The 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 install/include/rtt/internal/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 rtt/internal/ListLockFree.hpp.

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

Definition at line 97 of file install/include/rtt/internal/ListLockFree.hpp.

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

Definition at line 99 of file rtt/internal/ListLockFree.hpp.

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

Definition at line 99 of file install/include/rtt/internal/ListLockFree.hpp.

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

Definition at line 98 of file rtt/internal/ListLockFree.hpp.

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

Definition at line 98 of file install/include/rtt/internal/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 rtt/internal/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 install/include/rtt/internal/ListLockFree.hpp.

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

Definition at line 95 of file rtt/internal/ListLockFree.hpp.

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

Definition at line 95 of file install/include/rtt/internal/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:
lsize the capacity of the list.
threads the 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 install/include/rtt/internal/ListLockFree.hpp.

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

Definition at line 171 of file install/include/rtt/internal/ListLockFree.hpp.

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:
lsize the capacity of the list.
threads the 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 rtt/internal/ListLockFree.hpp.

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

Definition at line 171 of file rtt/internal/ListLockFree.hpp.

Member Function Documentation

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:
items the 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 402 of file rtt/internal/ListLockFree.hpp.

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:
item the 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 345 of file rtt/internal/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:
items the 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 402 of file install/include/rtt/internal/ListLockFree.hpp.

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:
item the 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 345 of file install/include/rtt/internal/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:
func The function to apply.
Note:
Always real-time.

Definition at line 525 of file rtt/internal/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:
func The function to apply.
Note:
Always real-time.

Definition at line 525 of file install/include/rtt/internal/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:
func The function to apply.
blank The '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 553 of file rtt/internal/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:
func The function to apply.
blank The '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 553 of file install/include/rtt/internal/ListLockFree.hpp.

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

Returns the last element of the list.

Definition at line 386 of file rtt/internal/ListLockFree.hpp.

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

Returns the last element of the list.

Definition at line 386 of file install/include/rtt/internal/ListLockFree.hpp.

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

Definition at line 150 of file rtt/internal/ListLockFree.hpp.

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

Definition at line 150 of file install/include/rtt/internal/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 rtt/internal/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 install/include/rtt/internal/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 rtt/internal/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 install/include/rtt/internal/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:
function each 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 481 of file rtt/internal/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:
function each 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 481 of file install/include/rtt/internal/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 rtt/internal/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 install/include/rtt/internal/ListLockFree.hpp.

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

Erase a value from the list.

Parameters:
item is 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 439 of file rtt/internal/ListLockFree.hpp.

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

Erase a value from the list.

Parameters:
item is 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 439 of file install/include/rtt/internal/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:
item The item to erase from the list.
blank The '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 598 of file rtt/internal/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:
item The item to erase from the list.
blank The '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 598 of file install/include/rtt/internal/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:
blank The 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 627 of file rtt/internal/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:
blank The 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 627 of file install/include/rtt/internal/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 650 of file rtt/internal/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 650 of file install/include/rtt/internal/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 374 of file rtt/internal/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 374 of file install/include/rtt/internal/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:
items The number of items to at least additionally reserve.
Note:
Almost never real-time.

Definition at line 224 of file rtt/internal/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:
items The number of items to at least additionally reserve.
Note:
Almost never real-time.

Definition at line 224 of file install/include/rtt/internal/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 699 of file rtt/internal/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 671 of file rtt/internal/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 699 of file install/include/rtt/internal/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 671 of file install/include/rtt/internal/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 717 of file rtt/internal/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 717 of file install/include/rtt/internal/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 rtt/internal/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 install/include/rtt/internal/ListLockFree.hpp.

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

Definition at line 740 of file rtt/internal/ListLockFree.hpp.

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

Definition at line 740 of file install/include/rtt/internal/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:
lsize the 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 rtt/internal/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:
lsize the 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 install/include/rtt/internal/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:
items The number of items to at most remove from the capacity.
Note:
Always real-time.

Definition at line 238 of file rtt/internal/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:
items The number of items to at most remove from the capacity.
Note:
Always real-time.

Definition at line 238 of file install/include/rtt/internal/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 rtt/internal/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 install/include/rtt/internal/ListLockFree.hpp.

Member Data Documentation

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

Definition at line 144 of file install/include/rtt/internal/ListLockFree.hpp.

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

Definition at line 145 of file install/include/rtt/internal/ListLockFree.hpp.

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

Definition at line 143 of file install/include/rtt/internal/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 install/include/rtt/internal/ListLockFree.hpp.

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

Definition at line 154 of file install/include/rtt/internal/ListLockFree.hpp.

The documentation for this class was generated from the following files:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines

rtt
Author(s): RTT Developers
autogenerated on Fri Jan 11 09:50:03 2013