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.
License
BSD license
News
[2016.01.06] Version 2.1.0 is available for download.

Added: FeldmanHashSet/Map - an interesting hash map algorithm based on multi-level array, requires perfect hashing or fixed-sized keys. Supports thread-safe bidirectional iterators.

Added: BronsonAVLTreeMap - Bronson's et al AVL tree implementation

Added: CMake build script, thanks to Eugeny Kalishenko

Changed: SplitList performance improving, thanks to Mike Krinkin

Changed: semantic of member functions extract(), get() and its variants for MichaelList RCU-based specialization: extract() does not require RCU locking, get() now returns special wrapper object of type raw_ptr, see doc. Thus, semantics of extract()/get() of all RCU-based set and maps based on MichaelList (MichaelSet/Map, SplitListSet/Map) has been changed too.

Changed: SplitListSet/Map functions get() and get_with() return special wrapper object of type raw_ptr, see doc.

Removed: SplitListSet/Map force_dispose() function.

cds::lock namespace is renamed to cds::sync. All classes defined in cds::lock namespace are moved to cds::sync with new names (for example, cds::lock::SpinLock is renamed to cds::sync::spin_lock). cds::lock namespace and its contents is deprecated, it is kept for backward compatibility.

The library has been checked by ThreadSanitizer, a lot of bugs has been fixed

Added support for clang 3.7 with libc++