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
    • Pass-the-Buck SMR
    • Gidenstam's Hazard Pointer with reference counting
    • 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 deque: Michael's algo
    • 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
  • 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 2008 + for MS Windows x86 32/64bit
  • GCC 4.3 +
    • 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.0 + for Linux x86 (32bit), amd64 (64bit), Mac OS X
Download the latest libcds version - source code, doxygen-generated documentation and test suite.
BSD license
[2013.12.29] Version 1.5.0 is available for download.

New: EllenBinTreeSet/Map - an implementation of unbalanced binary search tree

New: MSPriorityQueue - an array-based lock-based priority queue heap

Added support for Mac OS X

Added support for gcc 4.8, clang 3.3, MS VC++ 2013

Added support for boost.atomic for boost 1.54 and above has been modified to relax processor architecture and OS requirements

Some bugs have been fixed