cds  2.2.0
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.
 
 
 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 items. 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: 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;
}
};
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
}
};
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.


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