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 2015+ - 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.12.31] Version 2.3.2 is available for download.

Bugfix release

[2017.09.01] Version 2.3.1 is available for download.

Fixed bug in cds::gc::DHP when extending thread's retired array

[2017.07.31] Version 2.3.0 is available for download.

Changed: cds::gc::HP is totally refactored:

simplified internal structures;
added ability to specify an external allocator for internal data;
external API for gc::HP is slightly changed: now scan type cannot be changed on the fly; it can be specified only in construction time.

Changed: cds::gc::DHP is totally refactored to overcome some internal limitations. Now gc::DHP is fully adaptive variant of Hazard Pointer SMR, any dependencies on count of thread are removed, count of retired data and hazard pointers per thread are increased automaticaly by perforce. External API of gc::DHP class is changed: now only initial count of hazard pointers can be specified in the constructor. Like new gc::HP, the new gc::DHP supports an external allocator.

Changed: exception handling. Now, exceptions raise by invoking new cds::throw_exception() function. If you compile your code with exception disabled, the function prints an exception message to stdout and calls abort() instead of throwing.

Flat Combining: fixed memory-order bug that can lead to crash on weak ordered architecture like PowerPC or ARM

Added: erase_at( iterator ) function to MichaelHashSet/Map and SplitListSet/Map based on IterableList

Fixed a bug in BronsonAVLTreeMap::extract_min()/extract_max()/clear().

Removed: signal-handled threaded uRCU (cds::urcu::signal_threaded) due bad performance

Added more flat-combining queue tests, thanks to Marsel Galimullin.

Changed cmake scripts to support MacOS and ARMv7/ARMv8 (64 bit), thanks to Michail Komarov (https://github.com/Nemo1369)

Stress tests: removed command line parameter --detail-level and envvar CDSTEST_DETAIL_LEVEL for reducing compile time and executable size. To make full testset compile libcds with -DCDS_STRESS_TEST_LEVEL=N where N is 1 or 2.

Changed: refactoring cds::backoff::exponential and cds::backoff::delay back-off strategies to avoid static data members in template classes.

The library is extensively tested on x86-64, PowerPC and AArch64, thanks to GCC Compile Farm project