cds::intrusive Namespace Reference

Intrusive containers. More...

Namespaces
	basket_queue
	BasketQueue -related definitions.
	cuckoo
	CuckooSet-related definitions.
	ellen_bintree
	EllenBinTree related declarations.
	fcqueue
	FCQueue related definitions
	fcstack
	FCStack related definitions.
	feldman_hashset
	FeldmanHashSet related definitions.
	iterable_list
	IterableList ordered list related definitions
	lazy_list
	LazyList ordered list related definitions.
	michael_list
	MichaelList ordered list related definitions.
	michael_set
	MichaelHashSet related definitions.
	mspriority_queue
	MSPriorityQueue related definitions.
	msqueue
	MSQueue related definitions.
	opt
	Common options for intrusive containers.
	optimistic_queue
	OptimisticQueue related definitions
	segmented_queue
	SegmentedQueue -related declarations.
	single_link
	Definitions common for single-linked data structures.
	skip_list
	SkipListSet related definitions.
	split_list
	Split-ordered list related definitions.
	striped_set
	StripedSet related definitions.
	treiber_stack
	TreiberStack related definitions.
	vyukov_queue
	VyukovMPMCCycleQueue related definitions.

Data Structures
class	BasketQueue
	Basket lock-free queue (intrusive variant) More...
class	CachedFreeList
	Cached free list. More...
class	CuckooSet
	Cuckoo hash set. More...
class	EllenBinTree
	Ellen's et al binary search tree. More...
class	EllenBinTree< cds::urcu::gc< RCU >, Key, T, Traits >
	Ellen's et al binary search tree (RCU specialization) More...
class	FCQueue
	Flat-combining intrusive queue. More...
class	FCStack
	Flat-combining intrusive stack. More...
class	FeldmanHashSet
	Intrusive hash set based on multi-level array. More...
class	FeldmanHashSet< cds::urcu::gc< RCU >, T, Traits >
	Intrusive hash set based on multi-level array, RCU specialization. More...
class	FreeList
	Lock-free free list. More...
struct	get_node_traits
	Node traits selector metafunction. More...
class	IterableList
	Iterable lock-free ordered single-linked list. More...
class	LazyList
	Lazy ordered single-linked list. More...
class	LazyList< cds::urcu::gc< RCU >, T, Traits >
	Lazy ordered single-linked list (template specialization for RCU) More...
class	LazyList< gc::nogc, T, Traits >
	Lazy single-linked list (template specialization for gc::nogc) More...
class	MichaelHashSet
	Michael's hash set. More...
class	MichaelHashSet< cds::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	MichaelList
	Michael's lock-free ordered single-linked list. More...
class	MichaelList< cds::urcu::gc< RCU >, T, Traits >
	Michael's lock-free ordered single-linked list (template specialization for RCU) More...
class	MichaelList< gc::nogc, T, Traits >
	Michael's lock-free ordered single-linked list (template specialization for gc::nogc) More...
class	MoirQueue
	A variation of Michael & Scott's lock-free queue (intrusive variant) More...
class	MSPriorityQueue
	Michael & Scott array-based lock-based concurrent priority queue heap. More...
class	MSQueue
	Michael & Scott's intrusive lock-free queue. More...
struct	node_traits
	Container's node traits. More...
class	OptimisticQueue
	Optimistic intruive lock-free queue. More...
class	SegmentedQueue
	Segmented queue. 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< cds::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...
class	StripedSet
	Striped hash set. More...
class	TaggedFreeList
	Lock-free free list based on tagged pointers (required double-width CAS) More...
class	TreiberStack
	Treiber intrusive stack. 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 elements. However, additional requirements are imposed for types and values that can be stored in intrusive container. See the container documentation for details.

Tags

Many hooks and nodes for intrusive containers contain template argument Tag. This argument serves as a tag, so you can derive from more than one container's node and hence put an object in multiple intrusive containers at the same time. An incomplete type can serve as a tag. If you specify two hooks, you must specify a different tag for each one. Example:

struct tag1;
cds::intrusive::treiber_stack::node< cds::gc::HP, tag<tag1> >

If no tag is specified the default cds::opt::none will be used.

Inserting items

Many intrusive and non-intrusive (standard-like) containers in the library have the member functions that take a functor argument to initialize the inserted item after it has been successfully inserted, for example:

template <typename Q, typename Func>
bool insert( Q& key, Func f );

template <typename Q, typename Func>
std::pair<bool, bool> update( Q& key, Func f, bool bAllowInsert = true );

The first member function calls f functor iif a new item has been inserted. The functor takes two parameter: a reference to inserted item and key.

The second member function, update(), allows to insert a new item to the container if key is not found, or to find the item with key and to perform some action with it. The f signature is:

void f( bool bNew, item_type& item, Q& key );

where bNew is a flag to indicate whether item is a new created node or not.

Such functions should be used with caution in multi-threaded environment since they can cause races. The library does not synchronize access to container's items, so many threads can access to one item simultaneously. For example, for insert member function the following race is possible:

// Suppose, Foo is a complex structure with int key field
SomeContainer<Foo> q;

Thread 1                                  Thread 2

q.insert( Foo(5),                         q.find( 5, []( Foo& item ) {
    []( Foo& item ){                         // access to item fields
       // complex initialization             ...
       item.f1 = ...;                     });
       ...
    });

Execute sequence:

Find 5 in the container.
Key 5 is not found
Create a new item                         Find key 5
    with calling Foo(5) ctor
Insert the new item
                                          The key 5 is found -
                                             call the functor     (!)
Perform complex
   initialization -
   call the functor

(!): Thread 2 found the key and call its functor on incomplete initialized item. Simultaneous access to the item also is possible. In this case Thread 1 is initializing the item, thread 2 is reading (or writing) the item's fields. In any case, Thread 2 can read uninitialized or incomplete initialized fields.

update() member function race. Suppose, thread 1 and thread 2 perform the following code:

q.update( 5, []( bool bNew, Foo& item, int  arg )
   {
      // bNew: true if the new element has been created
      //       false otherwise
      if ( bNew ) {
         // initialize item
         item.f1=...;
         //...
      }
      else {
         // do some work
         if ( !item.f1 )
            item.f1 = ...;
         else {
           //...
         }
         //...
      }
   }
);

Execute sequence:

Thread 1                                  Thread 2
key 5 not found
insert new item Foo(5)                    Find 5
                                          Key 5 found
                                          call the functor with
                                             bNew = false        (!)
call the functor with
   bNew = true

(!): Thread 2 executes its functor on incomplete initialized item.

To protect your code from such races you can use some item-level synchronization, for example:

struct Foo {
   spinlock lock;       // item-level lock
   bool initialized = false;    // initialization flag
   // other fields
   // ....
};

q.update( 5, []( bool bNew, Foo& item, int  arg )
    {
        // Lock access to the item
        std::unique_lock( item.lock );

        if ( !item.initialized ) {
            // initialize item
            item.f1=...;
            //...
            item.initialized = true; // mark the item as initialized
        }
        else {
            // do some work
            if ( !item.f1 )
                item.f1 = ...;
            else {
                //...
            }
            //...
        }
    }
);

If the item-level synchronization is not suitable, you should not use any inserting member function with post-insert functor argument.

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" 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 a node of the container and the pointer to a item stored in the container are not equal in the general case. However, any pointer to node should be castable to appropriate pointer to container's item. In general, any item can be placed to two or more intrusive containers simultaneously, and each of those container holds an 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 node you should cast it to the pointer to item and then protect that item pointer. Otherwise an unpredictable result may occur.