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_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

◆ 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_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.

◆ ~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

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.

◆ 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

mem	The 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_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.

◆ owns()

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.

◆ 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:

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ FreeList() [1/2]

◆ FreeList() [2/2]

◆ ~FreeList()

Member Function Documentation

◆ allocate()

◆ constructAll() [1/2]

◆ constructAll() [2/2]

◆ destructAll()

◆ free()

◆ getTag()

◆ getVal()

◆ hasOutstandingAllocations()

◆ initialize()

◆ owns()

◆ setTag()

◆ setVal()

Member Data Documentation

◆ alloc_count_

◆ block_count_

◆ block_size_

◆ blocks_

◆ head_

◆ next_