lockfree::FreeList Class Reference

A lock-free (*not* wait-free) statically-sized free-list implemented with CAS. More...

#include <free_list.h>

List of all members.

Public Member Functions

void * allocate ()
 Allocate a single block from this FreeList.
template<typename T >
void constructAll ()
 Construct all the blocks with a default constructor. If you call this you must call destructAll() prior to destroying this FreeList. This is mainly for use by the ObjectPool class, or for writing a similar class, and generally that class should be used instead of FreeList directly.
template<typename T >
void constructAll (const T &tmpl)
 Construct all the blocks with a specific template. If you call this you must call destructAll() prior to destroying this FreeList. This is mainly for use by the ObjectPool class, or for writing a similar class, and generally that class should be used instead of FreeList directly.
template<typename T >
void destructAll ()
 Destruct all the objects in this FreeList. You must have called constructAll() first.
void free (void const *mem)
 Free a block of memory allocated from this FreeList.
 FreeList (uint32_t block_size, uint32_t block_count)
 Constructor with initialization.
 FreeList ()
 Default constructor. You must call initialize() if you use this constructor.
bool hasOutstandingAllocations ()
 Returns whether or not this FreeList currently has any outstanding allocations.
void initialize (uint32_t block_size, uint32_t block_count)
 Initialize this FreeList. Only use if you used to default constructor.
bool owns (void const *mem)
 Returns whether or not this FreeList owns a block of memory.
 ~FreeList ()

Private Member Functions

uint32_t getTag (uint64_t val)
uint32_t getVal (uint64_t val)
void setTag (uint64_t &val, uint32_t tag)
void setVal (uint64_t &val, uint32_t v)

Private Attributes

ros::atomic_uint32_t alloc_count_
uint32_t block_count_
uint32_t block_size_
uint8_t * blocks_
ros::atomic_uint64_t head_
ros::atomic_uint32_t * next_

Detailed Description

A lock-free (*not* wait-free) statically-sized free-list implemented with CAS.

FreeList is implemented as a forward-linked list using indices instead of pointers. The array of blocks is allocated separately from the array of next indices, and both are always allocated aligned to a cache line.

Indices are stored as 32-bits with a 64-bit head index whose upper 32-bits are tagged to avoid ABA problems

Definition at line 67 of file free_list.h.


Constructor & Destructor Documentation

lockfree::FreeList::FreeList (  ) 

Default constructor. You must call initialize() if you use this constructor.

Definition at line 44 of file free_list.cpp.

lockfree::FreeList::FreeList ( uint32_t  block_size,
uint32_t  block_count 
)

Constructor with initialization.

Parameters:
block_size The size of each block allocate() will return
block_count The number of blocks to allocate

Definition at line 52 of file free_list.cpp.

lockfree::FreeList::~FreeList (  ) 

Definition at line 61 of file free_list.cpp.


Member Function Documentation

void * lockfree::FreeList::allocate (  ) 

Allocate a single block from this FreeList.

Returns:
0 if all blocks are allocated, a pointer to a memory block of size block_size_ otherwise

Definition at line 108 of file free_list.cpp.

template<typename T >
void lockfree::FreeList::constructAll (  )  [inline]

Construct all the blocks with a default constructor. If you call this you must call destructAll() prior to destroying this FreeList. This is mainly for use by the ObjectPool class, or for writing a similar class, and generally that class should be used instead of FreeList directly.

Note:
sizeof(T) must be less than or equal to block_size_

Definition at line 138 of file free_list.h.

template<typename T >
void lockfree::FreeList::constructAll ( const T &  tmpl  )  [inline]

Construct all the blocks with a specific template. If you call this you must call destructAll() prior to destroying this FreeList. This is mainly for use by the ObjectPool class, or for writing a similar class, and generally that class should be used instead of FreeList directly.

Parameters:
tmpl The object template to use
Note:
sizeof(T) must be less than or equal to block_size_

Definition at line 121 of file free_list.h.

template<typename T >
void lockfree::FreeList::destructAll (  )  [inline]

Destruct all the objects in this FreeList. You must have called constructAll() first.

Note:
sizeof(T) must equal block_size_

Definition at line 152 of file free_list.h.

void lockfree::FreeList::free ( void const *  mem  ) 

Free a block of memory allocated from this FreeList.

Parameters:
mem The block to be freed

Definition at line 170 of file free_list.cpp.

uint32_t lockfree::FreeList::getTag ( uint64_t  val  )  [inline, private]

Definition at line 171 of file free_list.h.

uint32_t lockfree::FreeList::getVal ( uint64_t  val  )  [inline, private]

Definition at line 176 of file free_list.h.

bool lockfree::FreeList::hasOutstandingAllocations (  ) 

Returns whether or not this FreeList currently has any outstanding allocations.

Definition at line 103 of file free_list.cpp.

void lockfree::FreeList::initialize ( uint32_t  block_size,
uint32_t  block_count 
)

Initialize this FreeList. Only use if you used to default constructor.

Parameters:
block_size The size of each block allocate() will return
block_count The number of blocks to allocate

Definition at line 72 of file free_list.cpp.

bool lockfree::FreeList::owns ( void const *  mem  ) 

Returns whether or not this FreeList owns a block of memory.

Parameters:
mem the block to check
Returns:
true if this FreeList owns the block, false otherwise

Definition at line 239 of file free_list.cpp.

void lockfree::FreeList::setTag ( uint64_t &  val,
uint32_t  tag 
) [inline, private]

Definition at line 181 of file free_list.h.

void lockfree::FreeList::setVal ( uint64_t &  val,
uint32_t  v 
) [inline, private]

Definition at line 186 of file free_list.h.


Member Data Documentation

ros::atomic_uint32_t lockfree::FreeList::alloc_count_ [private]

Definition at line 194 of file free_list.h.

Definition at line 197 of file free_list.h.

uint32_t lockfree::FreeList::block_size_ [private]

Definition at line 196 of file free_list.h.

uint8_t* lockfree::FreeList::blocks_ [private]

Definition at line 191 of file free_list.h.

ros::atomic_uint64_t lockfree::FreeList::head_ [private]

Definition at line 193 of file free_list.h.

ros::atomic_uint32_t* lockfree::FreeList::next_ [private]

Definition at line 192 of file free_list.h.


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


lockfree
Author(s): Josh Faust
autogenerated on Fri Jan 11 09:40:14 2013