2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
43 #include <cds/version.h>
45 /** \mainpage CDS: Concurrent Data Structures library
47 This library is a collection of lock-free and lock-based fine-grained algorithms of data structures
48 like maps, queues, list etc. The library contains implementation of well-known data structures
49 and memory reclamation schemas for modern processor architectures. The library is written on C++11.
51 The main namespace for the library is \ref cds.
52 To see the full list of container's class go to <a href="modules.html">modules</a> tab.
54 Supported processor architectures and operating systems (OS) are:
55 - x86 [32bit] Linux, Windows, FreeBSD, MinGW
56 - amd64 (x86-64) [64bit] Linux, Windows, FreeBSD, MinGW
57 - ia64 (itanium) [64bit] Linux, HP-UX 11.23, HP-UX 11.31
58 - sparc [64bit] Sun Solaris
65 - MS Visual C++ 2013 Update 4 and above
66 - Intel C++ Compiler 15
68 For each lock-free data structure the \p CDS library presents several implementation based on published papers. For
69 example, there are several implementations of queue, each of them is divided by memory reclamation
70 schema used. However, any implementation supports common interface for the type of data structure.
72 To use any lock-free data structure, the following are needed:
73 - atomic operation library conforming with C++11 memory model.
74 The <b>libcds</b> can be built with \p std::atomic, \p boost::atomic or its own
75 @ref cds_cxx11_atomic "atomic implementation"
76 - safe memory reclamation (SMR) or garbage collecting (GC) algorithm.
78 SMR is the main part of lock-free data structs. The SMR solves the problem of safe
79 memory reclamation that is one of the main problem for lock-free programming.
80 The library contains the implementations of several light-weight \ref cds_garbage_collector "memory reclamation schemes":
81 - M.Michael's Hazard Pointer - see \p cds::gc::HP, \p cds::gc::DHP for more explanation
82 - User-space Read-Copy Update (RCU) - see \p cds::urcu namespace
83 - there is an empty \p cds::gc::nogc "GC" for append-only containers that do not support item reclamation.
85 Many GC requires a support from the thread. The library does not define the threading model you must use,
86 it is developed to support various ones; about incorporating <b>cds</b> library to your threading model see \p cds::threading.
88 \anchor cds_how_to_use
91 The main part of lock-free programming is SMR, so-called garbage collector, for safe memory reclamation.
92 The library provides several types of SMR schemes. One of widely used and well-tested is Hazard Pointer
93 memory reclamation schema discovered by M. Micheal and implemented in the library as \p cds::gc::HP class.
94 Usually, the application is based on only one type of GC.
96 In the next example we mean that you use Hazard Pointer \p cds::gc::HP - based containers.
98 First, in your code you should initialize \p cds library and Hazard Pointer in \p main() function:
100 #include <cds/init.h> // for cds::Initialize and cds::Terminate
101 #include <cds/gc/hp.h> // for cds::HP (Hazard Pointer) SMR
103 int main(int argc, char** argv)
109 // Initialize Hazard Pointer singleton
112 // If main thread uses lock-free containers
113 // the main thread should be attached to libcds infrastructure
114 cds::threading::Manager::attachThread();
116 // Now you can use HP-based containers in the main thread
125 Second, any of your thread should be attached to \p cds infrastructure.
127 #include <cds/gc/hp.h>
129 int myThreadEntryPoint(void *)
131 // Attach the thread to libcds infrastructure
132 cds::threading::Manager::attachThread();
134 // Now you can use HP-based containers in the thread
137 // Detach thread when terminating
138 cds::threading::Manager::detachThread();
142 After that, you can use \p cds lock-free containers safely without any external synchronization.
144 In some cases, you should work in an external thread. For example, your application
145 is a plug-in for a server that calls your code in a thread that has been created by the server.
146 In this case, you should use persistent mode of garbage collecting. In this mode, the thread attaches
147 to the GC singleton only if it is not attached yet and never call detaching:
149 #include <cds/gc/hp.h>
151 int plugin_entry_point()
153 // Attach the thread if it is not attached yet
154 if ( !cds::threading::Manager::isThreadAttached())
155 cds::threading::Manager::attachThread();
157 // Do some work with HP-related containers
165 The <b>cds</b> is mostly header-only library. Only small part of library related to GC core functionality
166 should be compiled. <b>cds</b> depends on C++ standard library only.
168 Test suite depends on:
169 - \p boost.thread (thread-loal storage support), boost.system
172 Some parts of libcds may depend on DCAS (double-width compare-and-swap) atomic primitive if
173 the target architecture supports it. For x86, cmake build script enables -mcx16 compiler flag that
174 switches DCAS support on. You may manually disable DCAS support with the following command line flags
175 in GCC/clang (for MS VC++ compiler DCAS is not supported):
176 - \p -DCDS_DISABLE_128BIT_ATOMIC - for 64bit build
177 - \p -DCDS_DISABLE_64BIT_ATOMIC - for 32bit build
179 @warning All your projects AND libcds MUST be compiled with the same flags - either with DCAS support or without it.
183 Prerequisites: for building <b>cds</b> library and test suite you need:
184 - <a href="http://www.activestate.com/activeperl/downloads">perl</a> installed; \p PATH environment variable
185 should contain full path to Perl binary. Perl is used to generate large dictionary for testing purpose;
186 - <a href="http://www.boost.org/">boost library</a> 1.51 and above. You should create environment variable
187 \p BOOST_PATH containing full path to \p boost root directory (for example, <tt>C:\\libs\\boost_1_57_0</tt>).
189 Open solution file <tt>cds\projects\vc141\cds.sln</tt> with Microsoft VisualStudio 2017.
190 The solution contains \p cds project and a lot of test projects. Just build the library using solution.
192 <b>Warning</b>: the solution depends on \p BOOST_PATH environment variable that specifies full path
193 to \p boost library root directory. The test projects search \p boost libraries in:
194 - for 32bit: <tt>\$(BOOST_PATH)/stage/lib</tt>, <tt>\$(BOOST_PATH)/stage32/lib</tt>, and <tt>\$(BOOST_PATH)/bin</tt>.
195 - for 64bit: <tt>\$(BOOST_PATH)/stage64/lib</tt> and <tt>\$(BOOST_PATH)/bin</tt>.
197 All tests are based on googletest framework. The following environment variables specify
198 where to find gtest include and library directories:
199 - \p GTEST_ROOT - gtest root directory. <tt>\$(GTEST_ROOT)/include</tt> specifies full path to
201 - \p GTEST_LIB64 - the path to 64bit gtest library dir;
202 - \p GTEST_LIB32 - the path to 32bit gtest library dir.
206 For Unix-like systems GCC and Clang compilers are supported.
207 Use GCC 4.8+ compiler or Clang 3.6+ to build <b>cds</b> library with CMake.
208 See accompanying file <tt>/build/cmake/readme.md</tt> for more info.
212 /// The main library namespace
216 \brief Basic typedefs and defines
218 You do not need include this header directly. All library header files depends on defs.h and include it.
222 CDS_COMPILER Compiler:
223 - CDS_COMPILER_MSVC Microsoft Visual C++
224 - CDS_COMPILER_GCC GNU C++
225 - CDS_COMPILER_CLANG clang
226 - CDS_COMPILER_UNKNOWN unknown compiler
228 CDS_COMPILER__NAME Character compiler name
230 CDS_COMPILER_VERSION Compliler version (number)
232 CDS_BUILD_BITS Resulting binary code:
237 CDS_POW2_BITS CDS_BUILD_BITS == 2**CDS_POW2_BITS
239 CDS_PROCESSOR_ARCH The processor architecture:
240 - CDS_PROCESSOR_X86 Intel x86 (32bit)
241 - CDS_PROCESSOR_AMD64 Amd64, Intel x86-64 (64bit)
242 - CDS_PROCESSOR_IA64 Intel IA64 (Itanium)
243 - CDS_PROCESSOR_SPARC Sparc
244 - CDS_PROCESSOR_PPC64 PowerPC64
245 - CDS_PROCESSOR_ARM7 ARM v7
246 - CDS_PROCESSOR_ARM8 ARM v8
247 - CDS_PROCESSOR_UNKNOWN undefined processor architecture
249 CDS_PROCESSOR__NAME The name (string) of processor architecture
251 CDS_OS_TYPE Operating system type:
252 - CDS_OS_UNKNOWN unknown OS
253 - CDS_OS_PTHREAD unknown OS with pthread
254 - CDS_OS_WIN32 Windows 32bit
255 - CDS_OS_WIN64 Windows 64bit
257 - CDS_OS_SUN_SOLARIS Sun Solaris
260 - CDS_OS_BSD FreeBSD, OpenBSD, NetBSD - common flag
261 - CDS_OS_FREE_BSD FreeBSD
262 - CDS_OS_OPEN_BSD OpenBSD
263 - CSD_OS_NET_BSD NetBSD
265 - CDS_OS_OSX Apple OS X
267 CDS_OS__NAME The name (string) of operating system type
269 CDS_OS_INTERFACE OS interface:
270 - CDS_OSI_UNIX Unix (POSIX)
271 - CDS_OSI_WINDOWS Windows
274 CDS_BUILD_TYPE Build type: 'RELEASE' or 'DEBUG' string
278 #if defined(_DEBUG) || !defined(NDEBUG)
280 # define CDS_BUILD_TYPE "DEBUG"
282 # define CDS_BUILD_TYPE "RELEASE"
285 /// Unused function argument
286 #define CDS_UNUSED(x) (void)(x)
288 // Supported compilers:
289 #define CDS_COMPILER_MSVC 1
290 #define CDS_COMPILER_GCC 2
291 #define CDS_COMPILER_INTEL 3
292 #define CDS_COMPILER_CLANG 4
293 #define CDS_COMPILER_UNKNOWN -1
295 // Supported processor architectures:
296 #define CDS_PROCESSOR_X86 1
297 #define CDS_PROCESSOR_IA64 2
298 #define CDS_PROCESSOR_SPARC 3
299 #define CDS_PROCESSOR_AMD64 4
300 #define CDS_PROCESSOR_PPC64 5 // PowerPC 64bit
301 #define CDS_PROCESSOR_ARM7 7
302 #define CDS_PROCESSOR_ARM8 8
303 #define CDS_PROCESSOR_UNKNOWN -1
305 // Supported OS interfaces
306 #define CDS_OSI_UNKNOWN 0
307 #define CDS_OSI_UNIX 1
308 #define CDS_OSI_WINDOWS 2
310 // Supported operating systems (value of CDS_OS_TYPE):
311 #define CDS_OS_UNKNOWN -1
312 #define CDS_OS_WIN32 1
313 #define CDS_OS_WIN64 5
314 #define CDS_OS_LINUX 10
315 #define CDS_OS_SUN_SOLARIS 20
316 #define CDS_OS_HPUX 30
317 #define CDS_OS_AIX 50 // IBM AIX
318 #define CDS_OS_FREE_BSD 61
319 #define CDS_OS_OPEN_BSD 62
320 #define CDS_OS_NET_BSD 63
321 #define CDS_OS_MINGW 70
322 #define CDS_OS_OSX 80
323 #define CDS_OS_PTHREAD 100
325 #if defined(_MSC_VER)
326 # if defined(__ICL) || defined(__INTEL_COMPILER)
327 # define CDS_COMPILER CDS_COMPILER_INTEL
328 # elif defined(__clang__)
329 # define CDS_COMPILER CDS_COMPILER_CLANG
331 # define CDS_COMPILER CDS_COMPILER_MSVC
333 #elif defined(__clang__) // Clang checking must be before GCC since Clang defines __GCC__ too
334 # define CDS_COMPILER CDS_COMPILER_CLANG
335 #elif defined( __GCC__ ) || defined(__GNUC__)
336 # if defined(__ICL) || defined(__INTEL_COMPILER)
337 # define CDS_COMPILER CDS_COMPILER_INTEL
339 # define CDS_COMPILER CDS_COMPILER_GCC
342 # define CDS_COMPILER CDS_COMPILER_UNKNOWN
343 #endif // Compiler choice
346 // CDS_VERIFY: Debug - assert(_expr); Release - _expr
348 # define CDS_VERIFY( _expr ) assert( _expr )
349 # define CDS_VERIFY_FALSE( _expr ) assert( !( _expr ))
350 # define CDS_DEBUG_ONLY( _expr ) _expr
351 # define CDS_VERIFY_EQ( expr, val ) assert( expr == val )
353 # define CDS_VERIFY( _expr ) _expr
354 # define CDS_VERIFY_FALSE( _expr ) _expr
355 # define CDS_DEBUG_ONLY( _expr )
356 # define CDS_VERIFY_EQ( expr, val ) expr
360 # define CDS_STRICT_DO(_expr) _expr
362 # define CDS_STRICT_DO( _expr )
366 # define cds_assert( expr ) assert( expr )
368 static inline void cds_assert( bool expr ) {
374 // Compiler-specific defines
375 #include <cds/compiler/defs.h>
377 #define CDS_NOEXCEPT CDS_NOEXCEPT_SUPPORT
378 #define CDS_NOEXCEPT_( expr ) CDS_NOEXCEPT_SUPPORT_( expr )
380 #ifdef CDS_CXX11_INLINE_NAMESPACE_SUPPORT
381 # define CDS_CXX11_INLINE_NAMESPACE inline
383 # define CDS_CXX11_INLINE_NAMESPACE
386 /*************************************************************************
388 **************************************************************************/
392 /// any_type is used as a placeholder for auto-calculated type (usually in \p rebind templates)
397 #endif // #ifndef CDSLIB_DEFS_H