cds/details/defs.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_DEFS_H
   4 #define __CDS_DEFS_H
   5
   6 #include <stddef.h>
   7 #include <assert.h>
   8 #include <cstdint>
   9 #include <exception>
  10 #include <string>
  11 #include <memory>
  12
  13 #include <cds/version.h>
  14
  15 /** \mainpage CDS: Concurrent Data Structures library
  16
  17    This library is a collection of lock-free and lock-based fine-grained algorithms of data structures
  18    like maps, queues, list etc. The library contains implementation of well-known data structures
  19    and memory reclamation schemas for modern processor architectures.
  20
  21    Supported processor architectures and operating systems (OS) are:
  22       - x86 [32bit] Linux, Windows, FreeBSD, MinGW
  23       - amd64 (x86-64) [64bit] Linux, Windows, FreeBSD, MinGW
  24       - ia64 (itanium) [64bit] Linux, HP-UX 11.23, HP-UX 11.31
  25       - sparc [64bit] Sun Solaris
  26       - Mac OS X amd64
  27
  28    Supported compilers:
  29       - GCC 4.3+ - for the UNIX-like OSes
  30       - Clang 3.0+ - for Linux
  31       - MS Visual C++ 2008 and above - for MS Windows
  32
  33    For each lock-free data structure the \p CDS library presents several implementation based on published papers. For
  34    example, there are several implementations of queue, each of them is divided by memory reclamation
  35    schema used. However, any implementation supports common interface for the type of data structure.
  36
  37    To implement any lock-free data structure, two things are needed:
  38    - atomic operation library conforming with C++11 memory model. The <b>libcds</b> has such feature, see cds::cxx11_atomic namespace for
  39      details and compiler-specific information.
  40    - safe memory reclamation (SMR) or garbage collecting (GC) algorithm. The <b>libcds</b> has an implementation of several
  41      well-known SMR algos, see below.
  42
  43    The main part of lock-free data structs is garbage collecting. The garbage collector (GC) solves the problem of safe
  44    memory reclamation that is one of the main problems for lock-free programming.
  45    The library contains the implementations of several light-weight \ref cds_garbage_collector "memory reclamation schemes":
  46    - M.Michael's Hazard Pointer - \p see cds::gc::HP, \p cds::gc::DHP for more explanation
  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.
  49
  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.
  52
  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.
  55
  56    \par How to build
  57
  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>
  62
  63    \par Windows build
  64
  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>).
  70
  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.
  74
  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.
  79
  80    \par *NIX build
  81
  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)
 104
 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.
 107
 108    \anchor cds_how_to_use
 109    \par How to use
 110
 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.
 113
 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.
 118
 119    In the next example we mean that your application uses Hazard Pointer (cds::gc::HP) - based containers.
 120
 121     First, in your code you should initialize \p cds library and a garbage collector in \p main function:
 122     \code
 123     #include <cds/init.h>       // for cds::Initialize and cds::Terminate
 124     #include <cds/gc/hp.h>      // for cds::HP (Hazard Pointer) garbage collector
 125
 126     int main(int argc, char** argv)
 127     {
 128         // Initialize libcds
 129         cds::Initialize();
 130
 131         {
 132             // Initialize Hazard Pointer singleton
 133             cds::gc::HP hpGC;
 134
 135             // If main thread uses lock-free containers
 136             // the main thread should be attached to libcds infrastructure
 137             cds::threading::Manager::attachThread();
 138
 139             // Now you can use HP-based containers in the main thread
 140             //...
 141         }
 142
 143         // Terminate libcds
 144         cds::Terminate();
 145     }
 146     \endcode
 147
 148     Second, any of your thread should be attached to \p cds infrastructure.
 149     \code
 150     #include <cds/gc/hp.h>
 151
 152     int myThreadEntryPoint(void *)
 153     {
 154         // Attach the thread to libcds infrastructure
 155         cds::threading::Manager::attachThread();
 156
 157         // Now you can use HP-based containers in the thread
 158         //...
 159
 160         // Detach thread when terminating
 161         cds::threading::Manager::detachThread();
 162     }
 163     \endcode
 164
 165     After that, you can use \p cds lock-free containers safely without any external synchronization.
 166
 167     In some cases, you should work in an external thread. For example, your application
 168     is a plug-in for a server that calls your code in a thread that has been created by the server.
 169     In this case, you should use persistent mode of garbage collecting. In this mode, the thread attaches
 170     to the GC singleton only if it is not attached yet and never call detaching:
 171     \code
 172     #include <cds/gc/hp.h>
 173
 174     int plugin_entry_point()
 175     {
 176         // Attach the thread if it is not attached yet
 177         if ( !cds::threading::Manager::isThreadAttached() )
 178             cds::threading::Manager::attachThread();
 179
 180         // Do some work with HP-related containers
 181         ...
 182     }
 183     \endcode
 184
 185 */
 186
 187
 188 /// The main library namespace
 189 namespace cds {}
 190
 191 /*
 192     \brief Basic typedefs and defines
 193
 194     You do not need include this header directly. All library header files depends on defs.h and include it.
 195
 196     Defines macros:
 197
 198     CDS_COMPILER        Compiler:
 199                     - CDS_COMPILER_MSVC     Microsoft Visual C++
 200                     - CDS_COMPILER_GCC      GNU C++
 201                     - CDS_COMPILER_CLANG    clang
 202                     - CDS_COMPILER_UNKNOWN  unknown compiler
 203
 204     CDS_COMPILER__NAME    Character compiler name
 205
 206     CDS_COMPILER_VERSION    Compliler version (number)
 207
 208     CDS_BUILD_BITS    Resulting binary code:
 209                     - 32        32bit
 210                     - 64        64bit
 211                     - -1        undefined
 212
 213     CDS_POW2_BITS    CDS_BUILD_BITS == 2**CDS_POW2_BITS
 214
 215     CDS_PROCESSOR_ARCH    The processor architecture:
 216                     - CDS_PROCESSOR_X86     Intel x86 (32bit)
 217                     - CDS_PROCESSOR_AMD64   Amd64, Intel x86-64 (64bit)
 218                     - CDS_PROCESSOR_IA64    Intel IA64 (Itanium)
 219                     - CDS_PROCESSOR_SPARC   Sparc
 220                     - CDS_PROCESSOR_PPC64   PowerPC64
 221                     - CDS_PROCESSOR_ARM7    ARM v7
 222                     - CDS_PROCESSOR_UNKNOWN undefined processor architecture
 223
 224     CDS_PROCESSOR__NAME    The name (string) of processor architecture
 225
 226     CDS_OS_TYPE        Operating system type:
 227                     - CDS_OS_UNKNOWN        unknown OS
 228                     - CDS_OS_PTHREAD        unknown OS with pthread
 229                     - CDS_OS_WIN32          Windows 32bit
 230                     - CDS_OS_WIN64          Windows 64bit
 231                     - CDS_OS_LINUX          Linux
 232                     - CDS_OS_SUN_SOLARIS    Sun Solaris
 233                     - CDS_OS_HPUX           HP-UX
 234                     - CDS_OS_AIX            IBM AIX
 235                     - CDS_OS_BSD            FreeBSD, OpenBSD, NetBSD - common flag
 236                     - CDS_OS_FREE_BSD       FreeBSD
 237                     - CDS_OS_OPEN_BSD       OpenBSD
 238                     - CSD_OS_NET_BSD        NetBSD
 239                     - CDS_OS_MINGW          MinGW
 240                     - CDS_OS_OSX            Apple OS X
 241
 242     CDS_OS__NAME        The name (string) of operating system type
 243
 244     CDS_OS_INTERFACE OS interface:
 245                     - CDS_OSI_UNIX             Unix (POSIX)
 246                     - CDS_OSI_WINDOWS          Windows
 247
 248
 249     CDS_BUILD_TYPE    Build type: 'RELEASE' or 'DEBUG' string
 250
 251 */
 252
 253 #if defined(_DEBUG) || !defined(NDEBUG)
 254 #    define    CDS_DEBUG
 255 #    define    CDS_BUILD_TYPE    "DEBUG"
 256 #else
 257 #    define    CDS_BUILD_TYPE    "RELEASE"
 258 #endif
 259
 260 /// Unused function argument
 261 #define CDS_UNUSED(x)   (void)(x)
 262
 263 // Supported compilers:
 264 #define CDS_COMPILER_MSVC        1
 265 #define CDS_COMPILER_GCC         2
 266 #define CDS_COMPILER_INTEL       3
 267 #define CDS_COMPILER_CLANG       4
 268 #define CDS_COMPILER_UNKNOWN    -1
 269
 270 // Supported processor architectures:
 271 #define CDS_PROCESSOR_X86       1
 272 #define CDS_PROCESSOR_IA64      2
 273 #define CDS_PROCESSOR_SPARC     3
 274 #define CDS_PROCESSOR_AMD64     4
 275 #define CDS_PROCESSOR_PPC64     5   // PowerPC 64bit
 276 #define CDS_PROCESSOR_ARM7      7
 277 #define CDS_PROCESSOR_UNKNOWN   -1
 278
 279 // Supported OS interfaces
 280 #define CDS_OSI_UNKNOWN          0
 281 #define CDS_OSI_UNIX             1
 282 #define CDS_OSI_WINDOWS          2
 283
 284 // Supported operating systems (value of CDS_OS_TYPE):
 285 #define CDS_OS_UNKNOWN          -1
 286 #define CDS_OS_WIN32            1
 287 #define CDS_OS_WIN64            5
 288 #define CDS_OS_LINUX            10
 289 #define CDS_OS_SUN_SOLARIS      20
 290 #define CDS_OS_HPUX             30
 291 #define CDS_OS_AIX              50  // IBM AIX
 292 #define CDS_OS_FREE_BSD         61
 293 #define CDS_OS_OPEN_BSD         62
 294 #define CDS_OS_NET_BSD          63
 295 #define CDS_OS_MINGW            70
 296 #define CDS_OS_OSX              80
 297 #define CDS_OS_PTHREAD          100
 298
 299 #if defined(_MSC_VER)
 300 #   if defined(__ICL) || defined(__INTEL_COMPILER)
 301 #       define CDS_COMPILER CDS_COMPILER_INTEL
 302 #   else
 303 #       define CDS_COMPILER CDS_COMPILER_MSVC
 304 #   endif
 305 #elif defined(__clang__)    // Clang checking must be before GCC since Clang defines __GCC__ too
 306 #   define CDS_COMPILER CDS_COMPILER_CLANG
 307 #elif defined( __GCC__ ) || defined(__GNUC__)
 308 #   if defined(__ICL) || defined(__INTEL_COMPILER)
 309 #       define CDS_COMPILER CDS_COMPILER_INTEL
 310 #   else
 311 #       define CDS_COMPILER CDS_COMPILER_GCC
 312 #   endif
 313 #else
 314 #    define CDS_COMPILER CDS_COMPILER_UNKNOWN
 315 #endif  // Compiler choice
 316
 317
 318 // CDS_VERIFY: Debug - assert(_expr); Release - _expr
 319 #ifdef CDS_DEBUG
 320 #   define CDS_VERIFY( _expr )    assert( _expr )
 321 #   define CDS_DEBUG_ONLY( _expr )        _expr
 322 #else
 323 #   define CDS_VERIFY( _expr )    _expr
 324 #   define CDS_DEBUG_ONLY( _expr )
 325 #endif
 326
 327 #ifdef CDS_STRICT
 328 #   define CDS_STRICT_DO(_expr)         _expr
 329 #else
 330 #   define CDS_STRICT_DO( _expr )
 331 #endif
 332
 333
 334 // Compiler-specific defines
 335 #include <cds/compiler/defs.h>
 336
 337 #define CDS_NOEXCEPT            CDS_NOEXCEPT_SUPPORT
 338 #define CDS_NOEXCEPT_( expr )   CDS_NOEXCEPT_SUPPORT_( expr )
 339
 340 #ifdef CDS_CXX11_INLINE_NAMESPACE_SUPPORT
 341 #   define CDS_CXX11_INLINE_NAMESPACE   inline
 342 #else
 343 #   define CDS_CXX11_INLINE_NAMESPACE
 344 #endif
 345
 346 //@cond
 347 // typedefs for back compatibility
 348 namespace cds {
 349     /// Atomic pointer
 350     typedef void *            pointer_t;
 351
 352     /// 64bit unaligned int
 353     typedef int64_t     atomic64_unaligned;
 354
 355     /// 64bit unaligned unsigned int
 356     typedef uint64_t  atomic64u_unaligned;
 357
 358     /// 64bit aligned int
 359     typedef atomic64_unaligned CDS_TYPE_ALIGNMENT(8)    atomic64_aligned;
 360
 361     /// 64bit aligned unsigned int
 362     typedef atomic64u_unaligned CDS_TYPE_ALIGNMENT(8)   atomic64u_aligned;
 363
 364     /// 64bit atomic int (aligned)
 365     typedef atomic64_aligned    atomic64_t;
 366
 367     /// 64bit atomic unsigned int (aligned)
 368     typedef atomic64u_aligned   atomic64u_t;
 369
 370     /// 32bit atomic int
 371     typedef int32_t     atomic32_t;
 372
 373     /// 32bit atomic unsigned int
 374     typedef uint32_t    atomic32u_t;
 375
 376     /// atomic int
 377     typedef atomic32_t          atomic_t;
 378
 379     /// atomic unsigned int
 380     typedef atomic32u_t         unsigned_atomic_t;
 381
 382     /// atomic int sized as pointer
 383     typedef intptr_t ptr_atomic_t;
 384
 385     /// atomic unsigned int sized as pointer
 386     typedef uintptr_t uptr_atomic_t;
 387 } // namespace cds
 388 //@endcond
 389
 390 /*************************************************************************
 391  Common things
 392 **************************************************************************/
 393
 394 namespace cds {
 395
 396     /// Base of all exceptions in the library
 397     class Exception: public std::exception
 398     {
 399     protected:
 400         std::string    m_strMsg    ;    ///< Exception message
 401     public:
 402         /// Create empty exception
 403         Exception()
 404         {}
 405         /// Create exception with message
 406         explicit Exception( const char * pszMsg )
 407             : m_strMsg( pszMsg )
 408         {}
 409         /// Create exception with message
 410         explicit Exception( const std::string& strMsg )
 411             :m_strMsg( strMsg )
 412         {}
 413
 414         /// Destructor
 415         virtual ~Exception() throw()
 416         {}
 417
 418         /// Return exception message
 419         virtual const char * what( ) const throw()
 420         {
 421             return m_strMsg.c_str();
 422         }
 423     };
 424
 425     /// any_type is used as a placeholder for auto-calculated type (usually in \p rebind templates)
 426     struct any_type {};
 427
 428 } // namespace cds
 429
 430 #endif // #ifndef __CDS_DEFS_H