cds  2.2.0
cds::intrusive::FreeList Class Reference

Lock-free free list. More...

#include <cds/intrusive/free_list.h>

Data Structures

struct  node
 Free list node. More...

Public Member Functions

 FreeList ()
 Creates empty free list.
 ~FreeList ()
 Destroys the free list. Free-list must be empty. More...
void put (node *pNode)
 Puts pNode to the free list.
nodeget ()
 Gets a node from the free list. If the list is empty, returns nullptr.
bool empty () const
 Checks whether the free list is empty.
template<typename Disposer >
void clear (Disposer disp)
 Clears the free list (not atomic) More...

Detailed Description

Lock-free free list.

Free list is a helper class intended for reusing objects instead of freeing them completely; this avoids the overhead of malloc(), and also avoids its worst-case behavior of taking an operating system lock. So, the free list can be considered as a specialized allocator for objects of some type.

The algorithm is taken from this article. The algo does not require any SMR like Hazard Pointer to prevent ABA problem.

There is tagged pointers variant of free list for processors with double-width CAS support.

How to use

#include <cds/intrusive/free_list.h>
// Your struct should be derived from FreeList::node
// Foo fields
// Simplified Foo allocator
class FooAllocator
// free-list clear() must be explicitly called before destroying the free-list object
m_FreeList.clear( []( freelist_node * p ) { delete static_cast<Foo *>( p ); });
Foo * alloc()
freelist_node * p = m_FreeList.get();
if ( p )
return static_cast<Foo *>( p );
return new Foo;
void dealloc( Foo * p )
m_FreeList.put( static_cast<freelist_node *>( p ));
typedef cds::intrusive::FreeList::node freelist_node;

Constructor & Destructor Documentation

§ ~FreeList()

cds::intrusive::FreeList::~FreeList ( )

Destroys the free list. Free-list must be empty.

dtor does not free elements of the list. To free elements you should manually call clear() with an appropriate disposer.

Member Function Documentation

§ clear()

template<typename Disposer >
void cds::intrusive::FreeList::clear ( Disposer  disp)

Clears the free list (not atomic)

For each element disp disposer is called to free memory. The Disposer interface:

struct disposer
void operator()( FreeList::node * node );

This method must be explicitly called before the free list destructor.

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

cds 2.2.0 Developed by Maxim Khizhinsky aka khizmax 2007 - 2017
Autogenerated Wed Jan 4 2017 08:49:50 by Doxygen 1.8.12