14 #include <cds/version.h>
16 /** \mainpage CDS: Concurrent Data Structures library
18 This library is a collection of lock-free and lock-based fine-grained algorithms of data structures
19 like maps, queues, list etc. The library contains implementation of well-known data structures
20 and memory reclamation schemas for modern processor architectures. The library is written on C++11.
22 The main namespace for the library is \ref cds.
23 To see the full list of container's class go to <a href="modules.html">modules</a> tab.
25 Supported processor architectures and operating systems (OS) are:
26 - x86 [32bit] Linux, Windows, FreeBSD, MinGW
27 - amd64 (x86-64) [64bit] Linux, Windows, FreeBSD, MinGW
28 - ia64 (itanium) [64bit] Linux, HP-UX 11.23, HP-UX 11.31
29 - sparc [64bit] Sun Solaris
36 - MS Visual C++ 2013 Update 4 and above
37 - Intel C++ Compiler 15
39 For each lock-free data structure the \p CDS library presents several implementation based on published papers. For
40 example, there are several implementations of queue, each of them is divided by memory reclamation
41 schema used. However, any implementation supports common interface for the type of data structure.
43 To use any lock-free data structure, the following are needed:
44 - atomic operation library conforming with C++11 memory model.
45 The <b>libcds</b> can be built with \p std::atomic, \p boost::atomic or its own
46 @ref cds_cxx11_atomic "atomic implementation"
47 - safe memory reclamation (SMR) or garbage collecting (GC) algorithm.
49 SMR is the main part of lock-free data structs. The SMR solves the problem of safe
50 memory reclamation that is one of the main problem for lock-free programming.
51 The library contains the implementations of several light-weight \ref cds_garbage_collector "memory reclamation schemes":
52 - M.Michael's Hazard Pointer - see \p cds::gc::HP, \p cds::gc::DHP for more explanation
53 - User-space Read-Copy Update (RCU) - see \p cds::urcu namespace
54 - there is an empty \p cds::gc::nogc "GC" for append-only containers that do not support item reclamation.
56 Many GC requires a support from the thread. The library does not define the threading model you must use,
57 it is developed to support various ones; about incorporating <b>cds</b> library to your threading model see \p cds::threading.
59 \anchor cds_how_to_use
62 The main part of lock-free programming is SMR, so-called garbage collector, for safe memory reclamation.
63 The library provides several types of SMR schemes. One of widely used and well-tested is Hazard Pointer
64 memory reclamation schema discovered by M. Micheal and implemented in the library as \p cds::gc::HP class.
65 Usually, the application is based on only one type of GC.
67 In the next example we mean that you use Hazard Pointer \p cds::gc::HP - based containers.
69 First, in your code you should initialize \p cds library and Hazard Pointer in \p main() function:
71 #include <cds/init.h> // for cds::Initialize and cds::Terminate
72 #include <cds/gc/hp.h> // for cds::HP (Hazard Pointer) SMR
74 int main(int argc, char** argv)
80 // Initialize Hazard Pointer singleton
83 // If main thread uses lock-free containers
84 // the main thread should be attached to libcds infrastructure
85 cds::threading::Manager::attachThread();
87 // Now you can use HP-based containers in the main thread
96 Second, any of your thread should be attached to \p cds infrastructure.
98 #include <cds/gc/hp.h>
100 int myThreadEntryPoint(void *)
102 // Attach the thread to libcds infrastructure
103 cds::threading::Manager::attachThread();
105 // Now you can use HP-based containers in the thread
108 // Detach thread when terminating
109 cds::threading::Manager::detachThread();
113 After that, you can use \p cds lock-free containers safely without any external synchronization.
115 In some cases, you should work in an external thread. For example, your application
116 is a plug-in for a server that calls your code in a thread that has been created by the server.
117 In this case, you should use persistent mode of garbage collecting. In this mode, the thread attaches
118 to the GC singleton only if it is not attached yet and never call detaching:
120 #include <cds/gc/hp.h>
122 int plugin_entry_point()
124 // Attach the thread if it is not attached yet
125 if ( !cds::threading::Manager::isThreadAttached() )
126 cds::threading::Manager::attachThread();
128 // Do some work with HP-related containers
136 The <b>cds</b> is mostly header-only library. Only small part of library related to GC core functionality
139 The test projects depends on the following static library from \p boost:
145 Prerequisites: for building <b>cds</b> library and test suite you need:
146 - <a href="http://www.activestate.com/activeperl/downloads">perl</a> installed; \p PATH environment variable
147 should contain full path to Perl binary. Perl is used to generate large dictionary for testing purpose;
148 - <a href="http://www.boost.org/">boost library</a> 1.51 and above. You should create environment variable
149 \p BOOST_PATH containing full path to \p boost root directory (for example, <tt>C:\\libs\\boost_1_57_0</tt>).
151 Open solution file <tt>cds\projects\vcX\cds.sln</tt> where \p vcX is the version of
152 Microsoft Visual C++ you use: vc12 for MS VC 2013 Update 4, vc14 for MS VC 2015. The solution
153 contains \p cds project and a lot of test projects. Just build the library using solution.
155 <b>Warning</b>: the solution depends on \p BOOST_PATH environment variable that specifies full path
156 to \p boost library root directory. The test projects search \p boost libraries in:
157 - for 32bit: <tt>\$(BOOST_PATH)/stage/lib</tt>, <tt>\$(BOOST_PATH)/stage32/lib</tt>, and <tt>\$(BOOST_PATH)/bin</tt>.
158 - for 64bit: <tt>\$(BOOST_PATH)/stage64/lib</tt> and <tt>\$(BOOST_PATH)/bin</tt>.
162 For Unix-like systems GCC and Clang compilers are supported.
163 Use GCC 4.8+ compiler or Clang 3.3+ to build <b>cds</b> library. The distributive contains
164 makefile and <tt>build.sh</tt> script in <tt>build</tt> directory.
165 The <tt>build/sample</tt> directory contains sample scripts for different operating systems and
166 processor architectures.
167 The <tt>build.sh</tt> script supports the following options:
168 - <tt>-c toolset</tt> - Toolset name, possible values: <tt>gcc</tt> (default), <tt>clang</tt>, <tt>icc</tt>
169 - <tt>-x compiler</tt> - C++ compiler name (e.g. g++, g++-4.5 and so on)
170 - <tt>-p arch</tt> - processor architecture; possible values for arch are: x86, amd64 (x86_64), sparc, ia64, ppc64
171 - <tt>-o OStype</tt> - OS family; possible values for OStype are: linux, sunos (solaris), hpux, mingw
172 - <tt>-D define</tt> additional defines
173 - <tt>-b bits</tt> - bits to build, accepts 64, 32
174 - <tt>-l "options"</tt> - extra linker options (in quotes)
175 - <tt>-z "options"</tt> - extra compiler options (in quotes)
176 - <tt>--with-boost path</tt> - path to boost include
177 - <tt>--debug-cxx-options "options"</tt> - extra compiler options for debug target
178 - <tt>--debug-ld-options "options"</tt> - extra linker options for debug target
179 - <tt>--release-cxx-options "options"</tt> - extra compiler options for release target
180 - <tt>--release-ld-options "optons"</tt> - extra linker options for release target
181 - <tt>--clean</tt> - clean all before building
182 - <tt>--debug-test</tt> - make unit test in debug mode; by defalt release unit test generated
183 - <tt>--amd64-use-128bit</tt> - compile with supporting 128bit (16byte) CAS on amd64 (for am64 only)
185 @note Important for GCC compiler: all your projects that use \p libcds must be compiled with <b>-fno-strict-aliasing</b>
191 /// The main library namespace
195 \brief Basic typedefs and defines
197 You do not need include this header directly. All library header files depends on defs.h and include it.
201 CDS_COMPILER Compiler:
202 - CDS_COMPILER_MSVC Microsoft Visual C++
203 - CDS_COMPILER_GCC GNU C++
204 - CDS_COMPILER_CLANG clang
205 - CDS_COMPILER_UNKNOWN unknown compiler
207 CDS_COMPILER__NAME Character compiler name
209 CDS_COMPILER_VERSION Compliler version (number)
211 CDS_BUILD_BITS Resulting binary code:
216 CDS_POW2_BITS CDS_BUILD_BITS == 2**CDS_POW2_BITS
218 CDS_PROCESSOR_ARCH The processor architecture:
219 - CDS_PROCESSOR_X86 Intel x86 (32bit)
220 - CDS_PROCESSOR_AMD64 Amd64, Intel x86-64 (64bit)
221 - CDS_PROCESSOR_IA64 Intel IA64 (Itanium)
222 - CDS_PROCESSOR_SPARC Sparc
223 - CDS_PROCESSOR_PPC64 PowerPC64
224 - CDS_PROCESSOR_ARM7 ARM v7
225 - CDS_PROCESSOR_UNKNOWN undefined processor architecture
227 CDS_PROCESSOR__NAME The name (string) of processor architecture
229 CDS_OS_TYPE Operating system type:
230 - CDS_OS_UNKNOWN unknown OS
231 - CDS_OS_PTHREAD unknown OS with pthread
232 - CDS_OS_WIN32 Windows 32bit
233 - CDS_OS_WIN64 Windows 64bit
235 - CDS_OS_SUN_SOLARIS Sun Solaris
238 - CDS_OS_BSD FreeBSD, OpenBSD, NetBSD - common flag
239 - CDS_OS_FREE_BSD FreeBSD
240 - CDS_OS_OPEN_BSD OpenBSD
241 - CSD_OS_NET_BSD NetBSD
243 - CDS_OS_OSX Apple OS X
245 CDS_OS__NAME The name (string) of operating system type
247 CDS_OS_INTERFACE OS interface:
248 - CDS_OSI_UNIX Unix (POSIX)
249 - CDS_OSI_WINDOWS Windows
252 CDS_BUILD_TYPE Build type: 'RELEASE' or 'DEBUG' string
256 #if defined(_DEBUG) || !defined(NDEBUG)
258 # define CDS_BUILD_TYPE "DEBUG"
260 # define CDS_BUILD_TYPE "RELEASE"
263 /// Unused function argument
264 #define CDS_UNUSED(x) (void)(x)
266 // Supported compilers:
267 #define CDS_COMPILER_MSVC 1
268 #define CDS_COMPILER_GCC 2
269 #define CDS_COMPILER_INTEL 3
270 #define CDS_COMPILER_CLANG 4
271 #define CDS_COMPILER_UNKNOWN -1
273 // Supported processor architectures:
274 #define CDS_PROCESSOR_X86 1
275 #define CDS_PROCESSOR_IA64 2
276 #define CDS_PROCESSOR_SPARC 3
277 #define CDS_PROCESSOR_AMD64 4
278 #define CDS_PROCESSOR_PPC64 5 // PowerPC 64bit
279 #define CDS_PROCESSOR_ARM7 7
280 #define CDS_PROCESSOR_UNKNOWN -1
282 // Supported OS interfaces
283 #define CDS_OSI_UNKNOWN 0
284 #define CDS_OSI_UNIX 1
285 #define CDS_OSI_WINDOWS 2
287 // Supported operating systems (value of CDS_OS_TYPE):
288 #define CDS_OS_UNKNOWN -1
289 #define CDS_OS_WIN32 1
290 #define CDS_OS_WIN64 5
291 #define CDS_OS_LINUX 10
292 #define CDS_OS_SUN_SOLARIS 20
293 #define CDS_OS_HPUX 30
294 #define CDS_OS_AIX 50 // IBM AIX
295 #define CDS_OS_FREE_BSD 61
296 #define CDS_OS_OPEN_BSD 62
297 #define CDS_OS_NET_BSD 63
298 #define CDS_OS_MINGW 70
299 #define CDS_OS_OSX 80
300 #define CDS_OS_PTHREAD 100
302 #if defined(_MSC_VER)
303 # if defined(__ICL) || defined(__INTEL_COMPILER)
304 # define CDS_COMPILER CDS_COMPILER_INTEL
306 # define CDS_COMPILER CDS_COMPILER_MSVC
308 #elif defined(__clang__) // Clang checking must be before GCC since Clang defines __GCC__ too
309 # define CDS_COMPILER CDS_COMPILER_CLANG
310 #elif defined( __GCC__ ) || defined(__GNUC__)
311 # if defined(__ICL) || defined(__INTEL_COMPILER)
312 # define CDS_COMPILER CDS_COMPILER_INTEL
314 # define CDS_COMPILER CDS_COMPILER_GCC
317 # define CDS_COMPILER CDS_COMPILER_UNKNOWN
318 #endif // Compiler choice
321 // CDS_VERIFY: Debug - assert(_expr); Release - _expr
323 # define CDS_VERIFY( _expr ) assert( _expr )
324 # define CDS_DEBUG_ONLY( _expr ) _expr
326 # define CDS_VERIFY( _expr ) _expr
327 # define CDS_DEBUG_ONLY( _expr )
331 # define CDS_STRICT_DO(_expr) _expr
333 # define CDS_STRICT_DO( _expr )
337 // Compiler-specific defines
338 #include <cds/compiler/defs.h>
340 #define CDS_NOEXCEPT CDS_NOEXCEPT_SUPPORT
341 #define CDS_NOEXCEPT_( expr ) CDS_NOEXCEPT_SUPPORT_( expr )
343 #ifdef CDS_CXX11_INLINE_NAMESPACE_SUPPORT
344 # define CDS_CXX11_INLINE_NAMESPACE inline
346 # define CDS_CXX11_INLINE_NAMESPACE
349 /*************************************************************************
351 **************************************************************************/
355 /// any_type is used as a placeholder for auto-calculated type (usually in \p rebind templates)
360 #endif // #ifndef CDSLIB_DEFS_H