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:
  • 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, Iterable list
    • intrusive and non-intrusive sets and maps: Michael hash-map, Split-ordere list by Ori Shalev & Nir Shavit, Skip-list, Feldman's multi-level array, Cuckoo hash map/set
    • Flat-combining wrappers for standard containers
  • Synchronization primitives - spin-lock with different back-off technique

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.6+ for Linux x86 (32bit), amd64 (64bit), Mac OS X
Download the latest libcds version - source code, doxygen-generated documentation and test suite.
License
BSD license
News
[2017.01.04] Version 2.2.0 is available for download.

Changed: CMake is used for build libcds. Ancient build.sh has been removed

Changed: unit and stress tests are migrated to googletest framework

Added: IterableList - an implementation of ordered list with thread-safe iterator. MichaelSet/Map and SplitListSet/Map support this type of ordered list and thread-safe iterable too.

Added: wait strategies for flat combining technique. Based on research by Marsel Galimullin and Nikolai Rapotkin.

Fixed: SkipList erase() and find() bugs that cause to infinite loop or to program crash in rare case.

Fixed: serious bug in MichaelSet::emplace() function New node was created twice from the arguments by move semantics. However, move semantics may change internal state of the argument that can lead to an incorrect element and even an incorrect key that breaks the set logic.

Fixed: bug in FeldmanHashSet::erase_at( iterator ): due an error in precondition checking the function may incorrectly return false.

Fixed: possible double-free case in flat combining algorithm. Thanks to Amila Jayasekara who pointed me to this problem

Changed: cds::opt::buffer option is divided to initialized (cds::opt::v::initialized_dynamic_buffer, cds::opt::v::initialized_static_buffer) and uninitialized (cds::opt::v::uninitialized_dynamic_buffer, cds::opt::v::uninitialized_static_buffer) ones. The old cds::opt::v::dynamic_buffer and cds::opt::v::static_buffer classes are removed.

Removed: TsigasCysleQueue (due undecidable ABA-problem)

Removed: Michael's allocator cds/memory/michael/allocator.h

Fixed: use-after-free bug in VyukovMPMCCycleQueue internal buffer. To prevent this bug the queue uses an uninitialized buffer now.

Fixed: rare priority inversion bug in MSPriorityQueue

Added: for minimizing runtime of stress test the detail level for some test is added. Command line argument --detail-level=N specifies what test should be ran: each test with level not greater than N will be ran. Instead of command line arg the enviromnent variable CDSTEST_DETAIL_LEVEL=N may be used. By default, the detail level is 0 that means only limited set of the test will be ran.