cds::intrusive Namespace Reference

Intrusive containers. More...

Namespaces
namespace	basket_queue
	Baskets queue related definitions.
namespace	cuckoo
	CuckooSet-related definitions.
namespace	lazy_list
	LazyList ordered list related definitions.
namespace	michael_deque
	MichaelDeque related definitions.
namespace	michael_list
	MichaelList ordered list related definitions.
namespace	michael_set
	MichaelHashSet related definitions.
namespace	opt
	Common options for intrusive containers.
namespace	optimistic_queue
	Optimistic queue related definitions.
namespace	single_link
	Definitions common for single-linked data structures.
namespace	skip_list
	SkipListSet related definitions.
namespace	split_list
	Split-ordered list related definitions.
namespace	striped_set
	StripedSet related definitions.

Data Structures
class	BasketQueue
	Basket lock-free queue (intrusive variant) More...
class	CuckooSet
	Cuckoo hash set. More...
struct	deque_stat
	Deque internal statistics. May be used for debugging or profiling. More...
struct	deque_dummy_stat
	Dummy deque statistics - no counting is performed. Support interface like deque_stat. More...
class	LazyList
	Lazy ordered single-linked list. More...
class	LazyList< gc::nogc, T, Traits >
	Lazy ordered single-linked list (template specialization for gc::nogc) More...
class	LazyList< cds::urcu::gc< RCU >, T, Traits >
	Lazy ordered single-linked list (template specialization for RCU) More...
class	MichaelDeque
	Michael's intrusive deque. More...
class	MichaelList
	Michael's lock-free ordered single-linked list. More...
class	MichaelList< gc::nogc, T, Traits >
	Michael's lock-free ordered single-linked list (template specialization for gc::nogc) More...
class	MichaelList< cds::urcu::gc< RCU >, T, Traits >
	Michael's lock-free ordered single-linked list (template specialization for RCU) More...
class	MichaelHashSet
	Michael's hash set. More...
class	MichaelHashSet< gc::nogc, OrderedList, Traits >
	Michael's hash set (template specialization for gc::nogc) More...
class	MichaelHashSet< cds::urcu::gc< RCU >, OrderedList, Traits >
	Michael's hash set, RCU specialization. More...
class	MoirQueue
	A variation of Michael & Scott's lock-free queue (intrusive variant) More...
class	MSQueue
	Michael & Scott's lock-free queue (intrusive variant) More...
struct	node_traits
	Container's node traits. More...
struct	get_node_traits
	Node traits selector metafunction. More...
class	OptimisticQueue
	Optimistic queue. More...
struct	queue_stat
	Queue internal statistics. May be used for debugging or profiling. More...
struct	queue_dummy_stat
	Dummy queue statistics - no counting is performed. Support interface like queue_stat. More...
class	SkipListSet
	Lock-free skip-list set. More...
class	SkipListSet< cds::gc::nogc, T, Traits >
	Lock-free skip-list set (template specialization for gc::nogc) More...
class	SkipListSet< cds::urcu::gc< RCU >, T, Traits >
	Lock-free skip-list set (template specialization for RCU) More...
class	SplitListSet
	Split-ordered list. More...
class	SplitListSet< gc::nogc, OrderedList, Traits >
	Split-ordered list (template specialization for gc::nogc) More...
class	SplitListSet< cds::urcu::gc< RCU >, OrderedList, Traits >
	Split-ordered list RCU specialization. More...
struct	stack_stat
	Stack internal statistics. May be used for debugging or profiling. More...
struct	stack_dummy_stat
	Dummy stack statistics - no counting is performed. Support interface like stack_stat. More...
class	StripedSet
	Striped hash set. More...
class	TreiberStack
	Treiber stack. More...
class	TsigasCycleQueue
	Non-blocking cyclic queue discovered by Philippas Tsigas and Yi Zhang. More...
class	VyukovMPMCCycleQueue
	Vyukov's MPMC bounded queue. More...

Detailed Description

Intrusive containers.

The namespace cds::intrusive contains intrusive lock-free containers. The idea comes from boost::intrusive library, see http://boost.org/doc/ as a good introduction to intrusive approach. The intrusive containers of libcds library is developed as close to boost::intrusive

In terms of lock-free approach, the main advantage of intrusive containers is that no memory allocation is performed to maintain container items. However, additional requirements is imposed for types and values that can be stored in intrusive container. See the container documentation for details.

Restriction for Gidenstam's garbage collector cds::gc::HRC: the Gidenstam's garbage collector makes additional requirements to type of item in intrusive container. Therefore, for this GC only base_hook is allowed as the value of opt::hook option.

Destroying items

It should be very careful when destroying an item removed from intrusive container. In other threads the references to popped item may exists some time after removing. To destroy the removed item in thread-safe manner you should call static function retire of garbage collector you use, for example:

struct destroyer  {
    void operator ()( my_type * p )
    {
        delete p    ;
    }
};

typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack ;
stack s ;

// ....

my_type * p = s.pop() ;

if ( p ) {
    // It is wrong
    // delete p ;

    // It is correct
    cds::gc:HP::retire< destroyer >( p ) ;
}

The situation becomes even more complicated when you want store items in different intrusive containers. In this case the best way is using reference counting:

struct my_type {
    ...
    std::atomic<unsigned int> nRefCount ;

    my_type()
        : nRefCount(0)
    {}
};

struct destroyer  {
    void operator ()( my_type * p )
    {
        if ( --p->nRefCount == 0 )
            delete p    ;   // delete only after no reference pointing to p
    }
};

typedef cds::intrusive::TreiberStack< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > stack ;
typedef cds::intrusive::MSQueue< cds::gc::HP, my_type, cds::opt::disposer< destroyer > > queue ;
stack s ;
queue q ;

my_type * v = new my_type() ;

v.nRefCount++   ; // increment counter before pushing the item to the stack
s.push(v)   ;

v.nRefCount++   ; // increment counter before pushing the item to the queue
q.push(v)   ;

// ....

my_type * ps = s.pop() ;
if ( ps ) {
    // It is wrong
    // delete ps ;

    // It is correct
    cds::gc:HP::retire< destroyer >( ps ) ;
}

my_type * pq = q.pop() ;
if ( pq ) {
    // It is wrong
    // delete pq ;

    // It is correct
    cds::gc:HP::retire< destroyer >( pq ) ;
}

Violation of these rules may lead to a crash.

Intrusive containers and Hazard Pointer-like garbage collectors

If you develop your intrusive container based on libcds library framework, you should take in the account the following. The main idea of garbage collectors (GC) based on Hazard Pointer schema is protecting a shared pointer by publishing it as a "hazard" one i.e. as a pointer that is changing at the current time and cannot be deleted at this moment. In intrusive container paradigm, the pointer to the node of the container and the pointer to the item stored in the container are not equal in the general case. However, any pointer to the node should be castable to the appropriate pointer to the container's item. In general, any item can be placed to some different intrusive containers simultaneously, and each of those container holds a unique pointer to its node that refers to the same item. When we protect a pointer, we want to protect an item pointer that is the invariant for any container stored that item. In your intrusive container, instead of protecting by GC's guard a pointer to an node you should convert it to the pointer to the item and then protect resulting item pointer. Otherwise an unpredictable result may occur.