11 #include <cds/version.h>
13 /** \mainpage CDS: Concurrent Data Structures library
15 This library is a collection of lock-free and lock-based fine-grained algorithms of data structures
16 like maps, queues, list etc. The library contains implementation of well-known data structures
17 and memory reclamation schemas for modern processor architectures.
19 Supported processor architectures and operating systems (OS) are:
20 - x86 [32bit] Linux, Windows, FreeBSD, MinGW
21 - amd64 (x86-64) [64bit] Linux, Windows, FreeBSD, MinGW
22 - ia64 (itanium) [64bit] Linux, HP-UX 11.23, HP-UX 11.31
23 - sparc [64bit] Sun Solaris
27 - GCC 4.3+ - for the UNIX-like OSes
28 - Clang 3.0+ - for Linux
29 - MS Visual C++ 2008 and above - for MS Windows
31 For each lock-free data structure the \p CDS library presents several implementation based on published papers. For
32 example, there are several implementations of queue, each of them is divided by memory reclamation
33 schema used. However, any implementation supports common interface for the type of data structure.
35 To implement any lock-free data structure, two things are needed:
36 - atomic operation library conforming with C++11 memory model. The <b>libcds</b> has such feature, see cds::cxx11_atomics namespace for
37 details and compiler-specific information.
38 - safe memory reclamation (SMR) or garbage collecting (GC) algorithm. The <b>libcds</b> has an implementation of several
39 well-known SMR algos, see below.
41 The main part of lock-free data structs is garbage collecting. The garbage collector (GC) solves the problem of safe
42 memory reclamation that is one of the main problems for lock-free programming.
43 The library contains the implementations of several light-weight \ref cds_garbage_collector "memory reclamation schemes":
44 - M.Michael's Hazard Pointer - see cds::gc::HP for more explanation
45 - Gidenstam's memory reclamation schema based on Hazard Pointer and reference counting - see cds::gc::HRC
46 - M.Herlihy and M.Moir's Pass The Buck algorithm - see cds::gc::PTB
47 - User-space Read-Copy Update (RCU) - see cds::urcu namespace
48 - there is cds::gc::nogc "GC" for containers that do not support item reclamation.
50 Many GC requires a support from the thread. The library does not define the threading model you must use,
51 it is developed to support various ones; about incorporating <b>cds</b> library to your threading model see cds::threading.
53 The main namespace for the library is \ref cds.
54 To see the full list of container's class go to <a href="modules.html">modules</a> tab.
58 The <b>cds</b> is mostly header-only library. Only small part of library related to GC core functionality
59 must be compiled. The test projects depends on the following static library from \p boost:
60 - <tt>boost_thread</tt>
61 - <tt>boost_date_time</tt>
65 Prerequisites: for building <b>cds</b> library and test suite you need:
66 - <a href="http://www.activestate.com/activeperl/downloads">perl</a> installed; \p PATH environment variable
67 should contain full path to Perl binary. Perl is used to generate large dictionary for testing purpose;
68 - <a href="http://www.boost.org/">boost library</a> 1.51 and above. You should create environment variable
69 \p BOOST_PATH containing full path to \p boost root directory (for example, <tt>C:\\libs\\boost_1_47_0</tt>).
71 Open solution file <tt>cds\projects\vcX\cds.sln</tt> where vcX - version of
72 Microsoft Visual C++ you use: vc9 for MS VC 2008, vc10 for MS VC 2010 and so on. The solution
73 contains <tt>cds</tt> project and several test projects. Just build the library using solution.
75 <b>Warning</b>: the solution depends on \p BOOST_PATH environment variable that specifies full path
76 to \p boost library root directory. The test projects search \p boost libraries in:
77 - for 32bit: \$(BOOST_PATH)/stage/lib, \$(BOOST_PATH)/stage32/lib, and \$(BOOST_PATH)/bin.
78 - for 64bit: \$(BOOST_PATH)/stage64/lib and \$(BOOST_PATH)/bin.
82 For Unix-like systems GCC and Clang compilers are supported.
83 Use GCC 4.3 (or above) compiler or Clang 3.0 or above to build <b>cds</b> library. The distributive contains
84 makefile and <tt>build.sh</tt> script in <tt>build</tt> directory.
85 The <tt>build/sample</tt> directory contains sample scripts for different operating systems and
86 processor architectures.
87 The <tt>build.sh</tt> script supports the following options:
88 - <tt>-c toolset</tt> - Toolset name, possible values: <tt>gcc</tt> (default), <tt>clang</tt>
89 - <tt>-x compiler</tt> - C++ compiler name (e.g. g++, g++-4.5 and so on)
90 - <tt>-p arch</tt> - processor architecture; possible values for arch are: x86, amd64 (x86_64), sparc, ia64
91 - <tt>-o OStype</tt> - OS family; possible values for OStype are: linux, sunos (solaris), hpux
92 - <tt>-D define</tt> additional defines
93 - <tt>-b bits</tt> - bits to build, accepts '64', '32'
94 - <tt>-l "options"</tt> - extra linker options (in quotes)
95 - <tt>-z "options"</tt> - extra compiler options (in quotes)
96 - <tt>--with-boost path</tt> - path to boost include
97 - <tt>--debug-cxx-options "options"</tt> - extra compiler options for debug target
98 - <tt>--debug-ld-options "options"</tt> - extra linker options for debug target
99 - <tt>--release-cxx-options "options"</tt> - extra compiler options for release target
100 - <tt>--release-ld-options "optons"</tt> - extra linker options for release target
101 - <tt>--clean</tt> - clean all before building
102 - <tt>--debug-test</tt> - make unit test in debug mode; by defalt release unit test generated
103 - <tt>--amd64-use-128bit</tt> - compile with supporting 128bit (16byte) CAS on amd64 (for am64 only)
105 <b>Important for GCC compiler</b>: all your projects that use <b>libcds</b> must be compiled with <b>-fno-strict-aliasing</b>
106 compiler flag. Also, the compiler option <tt>-std=c++0x</tt> is very useful.
108 \anchor cds_how_to_use
111 To use \p cds lock-free containers based on garbage collectors (GC) provided by library
112 your application must be linked with \p libcds.
114 The main part of lock-free programming is garbage collecting for safe memory reclamation.
115 The library provides several types of GC schemes. One of widely used and well-tested one is Hazard Pointer
116 memory reclamation schema discovered by M. Micheal and implemented in the library as cds::gc::HP class.
117 Usually, the application is based on only one type of GC.
119 In the next example we mean that your application uses Hazard Pointer (cds::gc::HP) - based containers.
120 Other GCs (cds::gc::HRC, cds::gc::PTB) are applied analogously.
122 First, in your code you should initialize \p cds library and a garbage collector in \p main function:
124 #include <cds/init.h> // for cds::Initialize and cds::Terminate
125 #include <cds/gc/hp.h> // for cds::HP (Hazard Pointer) garbage collector
127 int main(int argc, char** argv)
133 // Initialize Hazard Pointer singleton
136 // If main thread uses lock-free containers
137 // the main thread should be attached to libcds infrastructure
138 cds::threading::Manager::attachThread();
140 // Now you can use HP-based containers in the main thread
149 Second, any of your thread should be attached to \p cds infrastructure.
151 #include <cds/gc/hp.h>
153 int myThreadEntryPoint(void *)
155 // Attach the thread to libcds infrastructure
156 cds::threading::Manager::attachThread();
158 // Now you can use HP-based containers in the thread
161 // Detach thread when terminating
162 cds::threading::Manager::detachThread();
166 After that, you can use \p cds lock-free containers safely without any external synchronization.
168 In some cases, you should work in an external thread. For example, your application
169 is a plug-in for a server that calls your code in a thread that has been created by the server.
170 In this case, you should use persistent mode of garbage collecting. In this mode, the thread attaches
171 to the GC singleton only if it is not attached yet and never call detaching:
173 #include <cds/gc/hp.h>
175 int plugin_entry_point()
177 // Attach the thread if it is not attached yet
178 if ( !cds::threading::Manager::isThreadAttached() )
179 cds::threading::Manager::attachThread();
181 // Do some work with HP-related containers
189 /// The main library namespace
193 \brief Basic typedefs and defines
195 You do not need include this header directly. All library header files depends on defs.h and include it.
199 CDS_COMPILER Compiler:
200 - CDS_COMPILER_MSVC Microsoft Visual C++
201 - CDS_COMPILER_GCC GNU C++
202 - CDS_COMPILER_CLANG clang
203 - CDS_COMPILER_UNKNOWN unknown compiler
205 CDS_COMPILER__NAME Character compiler name
207 CDS_COMPILER_VERSION Compliler version (number)
209 CDS_BUILD_BITS Resulting binary code:
214 CDS_POW2_BITS CDS_BUILD_BITS == 2**CDS_POW2_BITS
216 CDS_PROCESSOR_ARCH The processor architecture:
217 - CDS_PROCESSOR_X86 Intel x86 (32bit)
218 - CDS_PROCESSOR_AMD64 Amd64, Intel x86-64 (64bit)
219 - CDS_PROCESSOR_IA64 Intel IA64 (Itanium)
220 - CDS_PROCESSOR_SPARC Sparc
221 - CDS_PROCESSOR_PPC64 PowerPC64
222 - CDS_PROCESSOR_ARM7 ARM v7
223 - CDS_PROCESSOR_UNKNOWN undefined processor architecture
225 CDS_PROCESSOR__NAME The name (string) of processor architecture
227 CDS_OS_TYPE Operating system type:
228 - CDS_OS_UNKNOWN unknown OS
229 - CDS_OS_PTHREAD unknown OS with pthread
230 - CDS_OS_WIN32 Windows 32bit
231 - CDS_OS_WIN64 Windows 64bit
233 - CDS_OS_SUN_SOLARIS Sun Solaris
236 - CDS_OS_BSD FreeBSD, OpenBSD, NetBSD - common flag
237 - CDS_OS_FREE_BSD FreeBSD
238 - CDS_OS_OPEN_BSD OpenBSD
239 - CSD_OS_NET_BSD NetBSD
241 - CDS_OS_OSX Apple OS X
243 CDS_OS__NAME The name (string) of operating system type
245 CDS_OS_INTERFACE OS interface:
246 - CDS_OSI_UNIX Unix (POSIX)
247 - CDS_OSI_WINDOWS Windows
250 CDS_BUILD_TYPE Build type: 'RELEASE' or 'DEBUG' string
254 #if defined(_DEBUG) || !defined(NDEBUG)
256 # define CDS_BUILD_TYPE "DEBUG"
258 # define CDS_BUILD_TYPE "RELEASE"
261 /// Unused function argument
262 #define CDS_UNUSED(x) (void)(x)
264 // Supported compilers:
265 #define CDS_COMPILER_MSVC 1
266 #define CDS_COMPILER_GCC 2
267 #define CDS_COMPILER_INTEL 3
268 #define CDS_COMPILER_CLANG 4
269 #define CDS_COMPILER_UNKNOWN -1
271 // Supported processor architectures:
272 #define CDS_PROCESSOR_X86 1
273 #define CDS_PROCESSOR_IA64 2
274 #define CDS_PROCESSOR_SPARC 3
275 #define CDS_PROCESSOR_AMD64 4
276 #define CDS_PROCESSOR_PPC64 5 // PowerPC 64bit
277 #define CDS_PROCESSOR_ARM7 7
278 #define CDS_PROCESSOR_UNKNOWN -1
280 // Supported OS interfaces
281 #define CDS_OSI_UNKNOWN 0
282 #define CDS_OSI_UNIX 1
283 #define CDS_OSI_WINDOWS 2
285 // Supported operating systems (value of CDS_OS_TYPE):
286 #define CDS_OS_UNKNOWN -1
287 #define CDS_OS_WIN32 1
288 #define CDS_OS_WIN64 5
289 #define CDS_OS_LINUX 10
290 #define CDS_OS_SUN_SOLARIS 20
291 #define CDS_OS_HPUX 30
292 #define CDS_OS_AIX 50 // IBM AIX
293 #define CDS_OS_FREE_BSD 61
294 #define CDS_OS_OPEN_BSD 62
295 #define CDS_OS_NET_BSD 63
296 #define CDS_OS_MINGW 70
297 #define CDS_OS_OSX 80
298 #define CDS_OS_PTHREAD 100
300 #if defined(_MSC_VER)
301 # if defined(__ICL) || defined(__INTEL_COMPILER)
302 # define CDS_COMPILER CDS_COMPILER_INTEL
304 # define CDS_COMPILER CDS_COMPILER_MSVC
306 #elif defined(__clang__) // Clang checking must be before GCC since Clang defines __GCC__ too
307 # define CDS_COMPILER CDS_COMPILER_CLANG
308 #elif defined( __GCC__ ) || defined(__GNUC__)
309 # if defined(__ICL) || defined(__INTEL_COMPILER)
310 # define CDS_COMPILER CDS_COMPILER_INTEL
312 # define CDS_COMPILER CDS_COMPILER_GCC
315 # define CDS_COMPILER CDS_COMPILER_UNKNOWN
316 #endif // Compiler choice
319 // CDS_VERIFY: Debug - assert(_expr); Release - _expr
321 # define CDS_VERIFY( _expr ) assert( _expr )
322 # define CDS_DEBUG_DO( _expr ) _expr
324 # define CDS_VERIFY( _expr ) _expr
325 # define CDS_DEBUG_DO( _expr )
329 # define CDS_STRICT_DO(_expr) _expr
331 # define CDS_STRICT_DO( _expr )
335 // Compiler-specific defines
336 #include <cds/compiler/defs.h>
337 // New C++11 features
338 #include <cds/details/cxx11_features.h>
340 #define CDS_NOEXCEPT CDS_NOEXCEPT_SUPPORT
341 #define CDS_NOEXCEPT_( expr ) CDS_NOEXCEPT_SUPPORT_( expr )
342 #ifndef CDS_NOEXCEPT_DEFAULTED
343 // Some compilers do not allow noexcept specification in defaulted function
344 // For example, GCC 4.6.x raise following error:
345 // void foo() noexcept = default
346 // error: function
\91foo
\92 defaulted on its first declaration must not have an exception-specification
347 // For such compiler empty CDS_NOEXCEPT_DEFAULTED must be defined
348 # define CDS_NOEXCEPT_DEFAULTED CDS_NOEXCEPT
349 # define CDS_NOEXCEPT_DEFAULTED_(expr) CDS_NOEXCEPT_( expr )
352 #if defined(CDS_CXX11_VARIADIC_TEMPLATE_SUPPORT) && defined(CDS_MOVE_SEMANTICS_SUPPORT)
353 # define CDS_EMPLACE_SUPPORT
356 #ifdef CDS_CXX11_INLINE_NAMESPACE_SUPPORT
357 # define CDS_CXX11_INLINE_NAMESPACE inline
359 # define CDS_CXX11_INLINE_NAMESPACE
363 // typedefs for back compatibility
366 typedef void * pointer_t;
368 /// 64bit unaligned int
369 typedef int64_t atomic64_unaligned;
371 /// 64bit unaligned unsigned int
372 typedef uint64_t atomic64u_unaligned;
374 /// 64bit aligned int
375 typedef atomic64_unaligned CDS_TYPE_ALIGNMENT(8) atomic64_aligned;
377 /// 64bit aligned unsigned int
378 typedef atomic64u_unaligned CDS_TYPE_ALIGNMENT(8) atomic64u_aligned;
380 /// 64bit atomic int (aligned)
381 typedef atomic64_aligned atomic64_t;
383 /// 64bit atomic unsigned int (aligned)
384 typedef atomic64u_aligned atomic64u_t;
387 typedef int32_t atomic32_t;
389 /// 32bit atomic unsigned int
390 typedef uint32_t atomic32u_t;
393 typedef atomic32_t atomic_t;
395 /// atomic unsigned int
396 typedef atomic32u_t unsigned_atomic_t;
398 /// atomic int sized as pointer
399 typedef intptr_t ptr_atomic_t;
401 /// atomic unsigned int sized as pointer
402 typedef uintptr_t uptr_atomic_t;
406 /*************************************************************************
408 **************************************************************************/
410 #include <cds/numtraits.h>
415 /// Helper template: converts volatile pointer to non-volatile one
416 template <typename T>
417 static inline T * non_volatile( T volatile * p ) { return const_cast<T *>( p ); }
419 template <typename T>
420 static inline T * non_volatile( T * p ) { return p; }
423 /// Base of all exceptions in the library
424 class Exception: public std::exception
427 std::string m_strMsg ; ///< Exception message
429 /// Create empty exception
432 /// Create exception with message
433 explicit Exception( const char * pszMsg )
436 /// Create exception with message
437 explicit Exception( const std::string& strMsg )
442 virtual ~Exception() throw()
445 /// Return exception message
446 virtual const char * what( ) const throw()
448 return m_strMsg.c_str();
453 # define CDS_PURE_VIRTUAL_FUNCTION_CALLED { assert(false); throw Exception("Pure virtual function called"); }
454 # define CDS_PURE_VIRTUAL_FUNCTION_CALLED_(method_name) { assert(false); throw Exception("Pure virtual function called " method_name ); }
457 /// any_type is used as a placeholder for auto-calculated type (usually in \p rebind templates)
460 /** \def CDS_DECLARE_EXCEPTION( _class, _msg )
461 Simplifying declaration of specific exception (usual within classes)
462 - @p _class - the class name of exception
463 - @p _msg - exception message (const char *)
465 #define CDS_DECLARE_EXCEPTION( _class, _msg ) \
466 struct _class: public std::exception { \
468 _class(): std::exception() {} \
469 virtual const char * what( ) const throw() { return _msg; } \
474 // This template function should be replaced with nullptr keyword when all compilers will support it
475 template <typename T>
476 static inline CDS_CONSTEXPR T null_ptr() CDS_NOEXCEPT
478 return reinterpret_cast<T>( NULL );
485 /// @defgroup cds_cxx11_stdlib_wrapper New C++11 standard library support
487 /// C++11 standard library wrapper namespace
488 /** @ingroup cds_cxx11_stdlib_wrapper
489 libcds needs support from new features defined in C++11 standard library.
490 In case when an old compiler and corresponding \p std library has no required feature
491 the \p boost library is used if possible. The \p %cds_std namespace is a wrapper for new C++11 stdlib classes:
492 - if the compiler supports new feature, this feature places (with \p using directive) into \p %cds_std namespace "as is"
493 - otherwise the \p boost analog is used and it places into \p %cds_std namespace too
495 For example, for class \p std::mutex the \p libcds does the following:
496 - for old compiler: \code
497 #include <boost/thread/mutex.hpp>
502 - for C++11-ready compiler: \code
509 Everywhere in \p libcds the class \p %cds_std::mutex is used instead of \p std::mutex.
511 Note, not all C++11 features are contained in \p %cds_std but only required by \p libcds.
513 In future when all compilers will be C++11-ready we can transform the \p libcds
514 to new C++11 standard library changing \p %cds_std namespace to native \p std.
520 # define cds_assert(X) assert(X)
522 # include <stdio.h> // snprintf
523 static inline void cds_assert_( bool bCond, char const * pszMsg, char const * pszFile, int nLine )
527 # if CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL
528 _snprintf_s( buf, sizeof(buf)/sizeof(buf[0]), _TRUNCATE, pszMsg, pszFile, nLine );
530 snprintf( buf, sizeof(buf)/sizeof(buf[0]), pszMsg, pszFile, nLine );
532 throw cds::Exception( buf );
535 # define cds_assert(X) cds_assert_( X, "%s (%d): Assert failed: " #X, __FILE__, __LINE__ );
539 #endif // #ifndef __CDS_DEFS_H