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.
node *	get ()
	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
struct Foo: public cds::intrusive::FreeList::node
{
    // Foo fields
};

// Simplified Foo allocator
class FooAllocator
{
public:
    // free-list clear() must be explicitly called before destroying the free-list object
    ~FooAllocator()
    {
        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 ));
    };

private:
    typedef cds::intrusive::FreeList::node freelist_node;
    cds::intrusive::FreeList m_FreeList;
};

Constructor & Destructor Documentation

~FreeList()

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

inline

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

Warning

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 )

inline

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/intrusive/free_list.h