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

Add flat combining (FC) technique and FC-based containers: FCStack, FCQueue, FCDeque, FCPriorityQueue

Add elimination back-off feature to TreiberStack class

Add SegmentedQueue - an unfair queue implementation

New member functions for sets and maps:
Functions get() and get_with() search a key and return the pointer to item found in safe manner.
Function extract() searches a key, unlinks the item found from the container and returns pointer to item in safe manner.
The functions get(), get_with(), extract(), extract_with(), extract_min(), extract_max() has been added to the following container:

  • SkipListSet, SkipListMap
  • EllenBinTree, EllenBinTreeSet, EllenBinTreeMap
The functions get(), get_with(), extract(), extract_with() has been added to the following container:
  • MichaelList, LazyList
  • MichaelHashSet, MichaelHashMap
  • SplitListSet, SplitListMap

Fix a serious bug in cds::gc::HRC

Changed MSPriorityQueue to simplify interface and to fix possible pop() deadlock

Fix a bug in BasketQueue

Fix EllenBinTree crash under high contention

Changed: the thread manager detach order to prevent crashing of signal-handled RCU in some case

Changed: cds::gc::HP calls Scan() when a thread is detached. This prevents accumulating retired data

Changed: minimal boost version is 1.51

Removed: file cds/lock/rwlock.h