This library is a collection of lock-free and lock-based fine-grained algorithms of data structures like maps, queues, list etc. The library contains implementation of well-known data structures and memory reclamation schemas for modern processor architectures. The library is written on C++11.

The main namespace for the library is cds. To see the full list of container's class go to modules tab.

Supported processor architectures and operating systems (OS) are:

x86 [32bit] Linux, Windows, FreeBSD, MinGW
amd64 (x86-64) [64bit] Linux, Windows, FreeBSD, MinGW
ia64 (itanium) [64bit] Linux, HP-UX 11.23, HP-UX 11.31
sparc [64bit] Sun Solaris
Mac OS X amd64
ppc64 Linux

Supported compilers:

GCC 4.8+
Clang 3.6+
MS Visual C++ 2015 and above
Intel C++ Compiler 15

For each lock-free data structure the CDS library presents several implementation based on published papers. For example, there are several implementations of queue, each of them is divided by memory reclamation schema used. However, any implementation supports common interface for the type of data structure.

To use any lock-free data structure, the following are needed:

atomic operation library conforming with C++11 memory model. The libcds can be built with std::atomic, boost::atomic or its own atomic implementation
safe memory reclamation (SMR) or garbage collecting (GC) algorithm.

SMR is the main part of lock-free data structs. The SMR solves the problem of safe memory reclamation that is one of the main problem for lock-free programming. The library contains the implementations of several light-weight memory reclamation schemes:

M.Michael's Hazard Pointer - see cds::gc::HP, cds::gc::DHP for more explanation
User-space Read-Copy Update (RCU) - see cds::urcu namespace
there is an empty cds::gc::nogc "GC" for append-only containers that do not support item reclamation.

Many GC requires a support from the thread. The library does not define the threading model you must use, it is developed to support various ones; about incorporating cds library to your threading model see cds::threading.

How to use

The main part of lock-free programming is SMR, so-called garbage collector, for safe memory reclamation. The library provides several types of SMR schemes. One of widely used and well-tested is Hazard Pointer memory reclamation schema discovered by M. Micheal and implemented in the library as cds::gc::HP class. Usually, the application is based on only one type of GC.

In the next example we mean that you use Hazard Pointer cds::gc::HP - based containers.

First, in your code you should initialize cds library and Hazard Pointer in main() function:

#include <cds/init.h>       // for cds::Initialize and cds::Terminate
#include <cds/gc/hp.h>      // for cds::HP (Hazard Pointer) SMR
int main(int argc, char** argv)
{
    // Initialize libcds
    cds::Initialize();
    {
        // Initialize Hazard Pointer singleton
        cds::gc::HP hpGC;
        // If main thread uses lock-free containers
        // the main thread should be attached to libcds infrastructure
        cds::threading::Manager::attachThread();
        // Now you can use HP-based containers in the main thread
        //...
    }
    // Terminate libcds
    cds::Terminate();
}

Second, any of your thread should be attached to cds infrastructure.

#include <cds/gc/hp.h>
int myThreadEntryPoint(void *)
{
    // Attach the thread to libcds infrastructure
    cds::threading::Manager::attachThread();
    // Now you can use HP-based containers in the thread
    //...
    // Detach thread when terminating
    cds::threading::Manager::detachThread();
}

After that, you can use cds lock-free containers safely without any external synchronization.

In some cases, you should work in an external thread. For example, your application is a plug-in for a server that calls your code in a thread that has been created by the server. In this case, you should use persistent mode of garbage collecting. In this mode, the thread attaches to the GC singleton only if it is not attached yet and never call detaching:

#include <cds/gc/hp.h>
int plugin_entry_point()
{
    // Attach the thread if it is not attached yet
    if ( !cds::threading::Manager::isThreadAttached())
        cds::threading::Manager::attachThread();
    // Do some work with HP-related containers
    ...
}

How to build

The cds is mostly header-only library. Only small part of library related to GC core functionality should be compiled. cds depends on C++ standard library only.

Test suite depends on:

boost.thread (thread-loal storage support), boost.system
google-test

Some parts of libcds may depend on DCAS (double-width compare-and-swap) atomic primitive if the target architecture supports it. For x86, cmake build script enables -mcx16 compiler flag that switches DCAS support on. You may manually disable DCAS support with the following command line flags in GCC/clang (for MS VC++ compiler DCAS is not supported):

-DCDS_DISABLE_128BIT_ATOMIC - for 64bit build
-DCDS_DISABLE_64BIT_ATOMIC - for 32bit build

Warning: All your projects AND libcds MUST be compiled with the same flags - either with DCAS support or without it.

Windows build

Prerequisites: for building cds library and test suite you need:

perl installed; PATH environment variable should contain full path to Perl binary. Perl is used to generate large dictionary for testing purpose;
boost library 1.51 and above. You should create environment variable BOOST_PATH containing full path to boost root directory (for example, C:\libs\boost_1_57_0).

Open solution file cds\projects\vc141\cds.sln with Microsoft VisualStudio 2017. The solution contains cds project and a lot of test projects. Just build the library using solution.

Warning: the solution depends on BOOST_PATH environment variable that specifies full path to boost library root directory. The test projects search boost libraries in:

for 32bit: $(BOOST_PATH)/stage/lib, $(BOOST_PATH)/stage32/lib, and $(BOOST_PATH)/bin.
for 64bit: $(BOOST_PATH)/stage64/lib and $(BOOST_PATH)/bin.

All tests are based on googletest framework. The following environment variables specify where to find gtest include and library directories:

GTEST_ROOT - gtest root directory. $(GTEST_ROOT)/include specifies full path to gtest include files;
GTEST_LIB64 - the path to 64bit gtest library dir;
GTEST_LIB32 - the path to 32bit gtest library dir.

*NIX build

For Unix-like systems GCC and Clang compilers are supported. Use GCC 4.8+ compiler or Clang 3.6+ to build cds library with CMake. See accompanying file /build/cmake/readme.md for more info.