Public Member Functions | Private Member Functions | Private Attributes | List of all members
lockfree::FreeList Class Reference

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

#include <free_list.h>

Public Member Functions

void * allocate ()
 Allocate a single block from this FreeList. More...
 
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. More...
 
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. More...
 
template<typename T >
void destructAll ()
 Destruct all the objects in this FreeList. You must have called constructAll() first. More...
 
void free (void const *mem)
 Free a block of memory allocated from this FreeList. More...
 
 FreeList ()
 Default constructor. You must call initialize() if you use this constructor. More...
 
 FreeList (uint32_t block_size, uint32_t block_count)
 Constructor with initialization. More...
 
bool hasOutstandingAllocations ()
 Returns whether or not this FreeList currently has any outstanding allocations. More...
 
void initialize (uint32_t block_size, uint32_t block_count)
 Initialize this FreeList. Only use if you used to default constructor. More...
 
bool owns (void const *mem)
 Returns whether or not this FreeList owns a block of memory. More...
 
 ~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

◆ FreeList() [1/2]

lockfree::FreeList::FreeList ( )

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

Definition at line 44 of file free_list.cpp.

◆ FreeList() [2/2]

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.

◆ ~FreeList()

lockfree::FreeList::~FreeList ( )

Definition at line 61 of file free_list.cpp.

Member Function Documentation

◆ allocate()

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.

◆ constructAll() [1/2]

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.

◆ constructAll() [2/2]

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.

◆ destructAll()

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.

◆ free()

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.

◆ getTag()

uint32_t lockfree::FreeList::getTag ( uint64_t  val)
inlineprivate

Definition at line 171 of file free_list.h.

◆ getVal()

uint32_t lockfree::FreeList::getVal ( uint64_t  val)
inlineprivate

Definition at line 176 of file free_list.h.

◆ hasOutstandingAllocations()

bool lockfree::FreeList::hasOutstandingAllocations ( )

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

Definition at line 103 of file free_list.cpp.

◆ initialize()

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.

◆ owns()

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.

◆ setTag()

void lockfree::FreeList::setTag ( uint64_t &  val,
uint32_t  tag 
)
inlineprivate

Definition at line 181 of file free_list.h.

◆ setVal()

void lockfree::FreeList::setVal ( uint64_t &  val,
uint32_t  v 
)
inlineprivate

Definition at line 186 of file free_list.h.

Member Data Documentation

◆ alloc_count_

ros::atomic_uint32_t lockfree::FreeList::alloc_count_
private

Definition at line 194 of file free_list.h.

◆ block_count_

uint32_t lockfree::FreeList::block_count_
private

Definition at line 197 of file free_list.h.

◆ block_size_

uint32_t lockfree::FreeList::block_size_
private

Definition at line 196 of file free_list.h.

◆ blocks_

uint8_t* lockfree::FreeList::blocks_
private

Definition at line 191 of file free_list.h.

◆ head_

ros::atomic_uint64_t lockfree::FreeList::head_
private

Definition at line 193 of file free_list.h.

◆ next_

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:


lockfree
Author(s): Josh Faust
autogenerated on Thu May 20 2021 02:25:30