Public Member Functions | Private Member Functions | Private Attributes
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 (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 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 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 ()
 Default constructor. You must call initialize() if you use this constructor.
 FreeList (uint32_t block_size, uint32_t block_count)
 Constructor with initialization.
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_tnext_

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

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_sizeThe size of each block allocate() will return
block_countThe number of blocks to allocate

Definition at line 52 of file free_list.cpp.

Definition at line 61 of file free_list.cpp.


Member Function Documentation

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 ( 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:
tmplThe 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::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::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:
memThe 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.

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_sizeThe size of each block allocate() will return
block_countThe 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:
memthe 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

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.

Definition at line 193 of file free_list.h.

Definition at line 192 of file free_list.h.


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


lockfree
Author(s): Josh Faust
autogenerated on Mon Oct 6 2014 06:54:55