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.
Supported processor architectures and operating systems (OS) are:
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 implement any lock-free data structure, two things are needed:
The main part of lock-free data structs is garbage collecting. The garbage collector (GC) solves the problem of safe memory reclamation that is one of the main problems for lock-free programming. The library contains the implementations of several light-weight memory reclamation schemes:
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.
The main namespace for the library is cds
The cds is mostly header-only library. Only small part of library related to GC core functionality must be compiled. The test projects depends on the following static library from
Prerequisites: for building cds library and test suite you need:
PATHenvironment variable should contain full path to Perl binary. Perl is used to generate large dictionary for testing purpose;
BOOST_PATHcontaining full path to
boostroot directory (for example,
Open solution file
cds\projects\vcX\cds.sln where vcX - version of Microsoft Visual C++ you use: vc9 for MS VC 2008, vc10 for MS VC 2010 and so on. The solution contains
cds project and several 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 Unix-like systems GCC and Clang compilers are supported. Use GCC 4.3 (or above) compiler or Clang 3.0 or above to build cds library. The distributive contains makefile and
build.sh script in
build directory. The
build/sample directory contains sample scripts for different operating systems and processor architectures. The
build.sh script supports the following options:
-c toolset- Toolset name, possible values:
-x compiler- C++ compiler name (e.g. g++, g++-4.5 and so on)
-p arch- processor architecture; possible values for arch are: x86, amd64 (x86_64), sparc, ia64
-o OStype- OS family; possible values for OStype are: linux, sunos (solaris), hpux
-D defineadditional defines
-b bits- bits to build, accepts '64', '32'
-l "options"- extra linker options (in quotes)
-z "options"- extra compiler options (in quotes)
–with-boost path- path to boost include
–debug-cxx-options "options"- extra compiler options for debug target
–debug-ld-options "options"- extra linker options for debug target
–release-cxx-options "options"- extra compiler options for release target
–release-ld-options "optons"- extra linker options for release target
–clean- clean all before building
–debug-test- make unit test in debug mode; by defalt release unit test generated
–amd64-use-128bit - compile with supporting 128bit (16byte) CAS on amd64 (for am64 only)
Important for GCC compiler: all your projects that use libcds must be compiled with -fno-strict-aliasing compiler flag. Also, the compiler option
-std=c++0x is very useful.
cds lock-free containers based on garbage collectors (GC) provided by library your application must be linked with
The main part of lock-free programming is garbage collecting for safe memory reclamation. The library provides several types of GC schemes. One of widely used and well-tested one 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.
First, in your code you should initialize
cds library and a garbage collector in
Second, any of your thread should be attached to
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: