Concurrent Data Structures (libcds)
CDS is a C++ template library of lock-free and fine-grained algorithms. It contains a collection of concurrent data structure implementations:
  • Atomic operations with memory ordering support for x86, amd64, Itanium, Sparc processor architectures
  • Safe memory reclamation (SMR) algorithms:
    • Michael's Hazard Pointer
    • User-space RCU
  • Data structures - a lot of intrusive and non-intrusive container algorithms for different SMR schemas
    • intrusive and non-intrusive stacks
    • intrusive and non-intrusive queues: Michael & Scott lock-free and read/write lock-based, Moir et al algo, Ladan-Mozes & Shavit optimistic queue, basket queue, bounded (ring-buffered) algos
    • intrusive and non-intrusive ordered lists: Michael's algo, Lazy list algo
    • intrusive and non-intrusive sets and maps: Michael hash-map, Split-ordere list by Ori Shalev & Nir Shavit, Skip-list, Cuckoo hash map/set
    • Flat-combining wrappers for standard containers
  • Synchronization primitives - spin-lock with different back-off technique
  • Michael's memory allocator. See cds::memory::michael::Heap in documentation

The library is mostly header-only with small kernel in .dll (.so) file for core SMR functionality and a small set of static data. See online documentation for detailed reference of CDS features.

Supported compilers, operating systems and processor architectures are:
  • MS Visual Studio 2013 Update 4 - for MS Windows x86 32/64bit
  • GCC 4.8+
    • Linux: x86 (32bit), amd64 (64bit), IA64 Itanium (64bit), Sparc (64bit)
    • Solaris: Sparc 64bit
    • HP-UX: IA64 64bit
    • FreeBSD: x86 (32bit), amd64 (64bit)
    • MinGW
    • Mac OS X
  • Clang 3.3+ for Linux x86 (32bit), amd64 (64bit), Mac OS X
Download the latest libcds version - source code, doxygen-generated documentation and test suite.
BSD license
[2014.12.30] Version 2.0.0 is available for download.

The library has been rewritten to support at least C++11. Compilers: GCC 4.8+, clang 3.3+, MS Visual C++ 12 (2013) Update 4 an above.

MichaelDeque has been removed, reason: the implementation is heavy-weighted, inefficient, and unstable

cds::gc::HRC garbage collector has been removed, reason: the implementation is inefficient and unstable

cds::gc::PTB garbage collector has been renamed to cds::gc::DHP - dynamic hazard pointers

All container's declaration except StripedSet has been unified to the following traits-based form:
class Container< GC, T, Traits >

New member function pop_with(Func) is added to cds::container::TreiberStack

New member functions enqueue_with(Func), dequeue_with(Func) are added to

  • cds::container::MSQueue
  • cds::container::MoirQueue
  • cds::container::BasketQueue
  • cds::container::OptimisticQueue
  • cds::container::RWQueue
  • cds::container::SegmentedQueue
  • cds::container::TsigasCycleQueue
  • cds::container::VyukovMPMCCycleQueue

New member functions push_with(Func) and pop_with(Func) is added to cds::container::MSPriorityQueue

SegmentedQueue: add padding option into segmented_queue::traits to eliminate false sharing.

guarded_ptr and exempt_ptr have move semantics now. The container's extract() and get() member functions return the objects of that type.

Improved cds::gc::HP and cds::gc::DHP internal implementation

Map's member function insert_key() has been renamed to insert_with()

cds/cxx11_atomic.h has been renamed to cds/algo/atomic.h

cds/refcounter.h has been removed