-//$$CDS-header$$
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
+
+ Source code repo: http://github.com/khizmax/libcds/
+ Download: http://sourceforge.net/projects/libcds/files/
+
+ Redistribution and use in source and binary forms, with or without
+ modification, are permitted provided that the following conditions are met:
+
+ * Redistributions of source code must retain the above copyright notice, this
+ list of conditions and the following disclaimer.
+
+ * Redistributions in binary form must reproduce the above copyright notice,
+ this list of conditions and the following disclaimer in the documentation
+ and/or other materials provided with the distribution.
-#ifndef __CDS_DEFS_H
-#define __CDS_DEFS_H
+ THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+*/
+
+#ifndef CDSLIB_DEFS_H
+#define CDSLIB_DEFS_H
+#include <stddef.h>
#include <assert.h>
#include <cstdint>
#include <exception>
+#include <stdexcept>
#include <string>
#include <memory>
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.
+ and memory reclamation schemas for modern processor architectures. The library is written on C++11.
+
+ The main namespace for the library is \ref cds.
+ To see the full list of container's class go to <a href="modules.html">modules</a> tab.
Supported processor architectures and operating systems (OS) are:
- x86 [32bit] Linux, Windows, FreeBSD, MinGW
- ia64 (itanium) [64bit] Linux, HP-UX 11.23, HP-UX 11.31
- sparc [64bit] Sun Solaris
- Mac OS X amd64
+ - ppc64 Linux
Supported compilers:
- - GCC 4.3+ - for the UNIX-like OSes
- - Clang 3.0+ - for Linux
- - MS Visual C++ 2008 and above - for MS Windows
+ - GCC 4.8+
+ - Clang 3.6+
+ - MS Visual C++ 2013 Update 4 and above
+ - Intel C++ Compiler 15
For each lock-free data structure the \p 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:
- - atomic operation library conforming with C++11 memory model. The <b>libcds</b> has such feature, see cds::cxx11_atomic namespace for
- details and compiler-specific information.
- - safe memory reclamation (SMR) or garbage collecting (GC) algorithm. The <b>libcds</b> has an implementation of several
- well-known SMR algos, see below.
+ To use any lock-free data structure, the following are needed:
+ - atomic operation library conforming with C++11 memory model.
+ The <b>libcds</b> can be built with \p std::atomic, \p boost::atomic or its own
+ @ref cds_cxx11_atomic "atomic implementation"
+ - safe memory reclamation (SMR) or garbage collecting (GC) algorithm.
- 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.
+ SMR is the main part of lock-free data structs. The SMR solves the problem of safe
+ memory reclamation that is one of the main problem for lock-free programming.
The library contains the implementations of several light-weight \ref cds_garbage_collector "memory reclamation schemes":
- - M.Michael's Hazard Pointer - see cds::gc::HP for more explanation
- - Gidenstam's memory reclamation schema based on Hazard Pointer and reference counting - see cds::gc::HRC
- - M.Herlihy and M.Moir's Pass The Buck algorithm - see cds::gc::PTB
- - User-space Read-Copy Update (RCU) - see cds::urcu namespace
- - there is cds::gc::nogc "GC" for containers that do not support item reclamation.
+ - M.Michael's Hazard Pointer - see \p cds::gc::HP, \p cds::gc::DHP for more explanation
+ - User-space Read-Copy Update (RCU) - see \p cds::urcu namespace
+ - there is an empty \p cds::gc::nogc "GC" for append-only containers that do not support item reclamation.
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 <b>cds</b> library to your threading model see cds::threading.
-
- The main namespace for the library is \ref cds.
- To see the full list of container's class go to <a href="modules.html">modules</a> tab.
-
- \par How to build
-
- The <b>cds</b> 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 \p boost:
- - <tt>boost_thread</tt>
- - <tt>boost_date_time</tt>
-
- \par Windows build
-
- Prerequisites: for building <b>cds</b> library and test suite you need:
- - <a href="http://www.activestate.com/activeperl/downloads">perl</a> installed; \p PATH environment variable
- should contain full path to Perl binary. Perl is used to generate large dictionary for testing purpose;
- - <a href="http://www.boost.org/">boost library</a> 1.51 and above. You should create environment variable
- \p BOOST_PATH containing full path to \p boost root directory (for example, <tt>C:\\libs\\boost_1_47_0</tt>).
-
- Open solution file <tt>cds\projects\vcX\cds.sln</tt> 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 <tt>cds</tt> project and several test projects. Just build the library using solution.
-
- <b>Warning</b>: the solution depends on \p BOOST_PATH environment variable that specifies full path
- to \p boost library root directory. The test projects search \p boost libraries in:
- - for 32bit: \$(BOOST_PATH)/stage/lib, \$(BOOST_PATH)/stage32/lib, and \$(BOOST_PATH)/bin.
- - for 64bit: \$(BOOST_PATH)/stage64/lib and \$(BOOST_PATH)/bin.
-
- \par *NIX build
-
- 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 <b>cds</b> library. The distributive contains
- makefile and <tt>build.sh</tt> script in <tt>build</tt> directory.
- The <tt>build/sample</tt> directory contains sample scripts for different operating systems and
- processor architectures.
- The <tt>build.sh</tt> script supports the following options:
- - <tt>-c toolset</tt> - Toolset name, possible values: <tt>gcc</tt> (default), <tt>clang</tt>
- - <tt>-x compiler</tt> - C++ compiler name (e.g. g++, g++-4.5 and so on)
- - <tt>-p arch</tt> - processor architecture; possible values for arch are: x86, amd64 (x86_64), sparc, ia64
- - <tt>-o OStype</tt> - OS family; possible values for OStype are: linux, sunos (solaris), hpux
- - <tt>-D define</tt> additional defines
- - <tt>-b bits</tt> - bits to build, accepts '64', '32'
- - <tt>-l "options"</tt> - extra linker options (in quotes)
- - <tt>-z "options"</tt> - extra compiler options (in quotes)
- - <tt>--with-boost path</tt> - path to boost include
- - <tt>--debug-cxx-options "options"</tt> - extra compiler options for debug target
- - <tt>--debug-ld-options "options"</tt> - extra linker options for debug target
- - <tt>--release-cxx-options "options"</tt> - extra compiler options for release target
- - <tt>--release-ld-options "optons"</tt> - extra linker options for release target
- - <tt>--clean</tt> - clean all before building
- - <tt>--debug-test</tt> - make unit test in debug mode; by defalt release unit test generated
- - <tt>--amd64-use-128bit</tt> - compile with supporting 128bit (16byte) CAS on amd64 (for am64 only)
-
- <b>Important for GCC compiler</b>: all your projects that use <b>libcds</b> must be compiled with <b>-fno-strict-aliasing</b>
- compiler flag. Also, the compiler option <tt>-std=c++0x</tt> is very useful.
+ it is developed to support various ones; about incorporating <b>cds</b> library to your threading model see \p cds::threading.
\anchor cds_how_to_use
\par How to use
- To use \p cds lock-free containers based on garbage collectors (GC) provided by library
- your application must be linked with \p libcds.
-
- 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.
+ The main part of lock-free programming is SMR, so-called garbage collector, for safe memory reclamation.
+ The library provides several types of SMR schemes. One of widely used and well-tested is Hazard Pointer
+ memory reclamation schema discovered by M. Micheal and implemented in the library as \p cds::gc::HP class.
Usually, the application is based on only one type of GC.
- In the next example we mean that your application uses Hazard Pointer (cds::gc::HP) - based containers.
- Other GCs (cds::gc::HRC, cds::gc::PTB) are applied analogously.
+ In the next example we mean that you use Hazard Pointer \p cds::gc::HP - based containers.
- First, in your code you should initialize \p cds library and a garbage collector in \p main function:
+ First, in your code you should initialize \p cds library and Hazard Pointer in \p main() function:
\code
#include <cds/init.h> // for cds::Initialize and cds::Terminate
- #include <cds/gc/hp.h> // for cds::HP (Hazard Pointer) garbage collector
+ #include <cds/gc/hp.h> // for cds::HP (Hazard Pointer) SMR
int main(int argc, char** argv)
{
int plugin_entry_point()
{
// Attach the thread if it is not attached yet
- if ( !cds::threading::Manager::isThreadAttached() )
+ if ( !cds::threading::Manager::isThreadAttached())
cds::threading::Manager::attachThread();
// Do some work with HP-related containers
}
\endcode
+
+ \par How to build
+
+ The <b>cds</b> is mostly header-only library. Only small part of library related to GC core functionality
+ should be compiled.
+
+ External dependenies: the tests depends on:
+ - \p boost.thread (thread-loal storage support), boost.system
+ - \p google-test
+
+ \par Windows build
+
+ Prerequisites: for building <b>cds</b> library and test suite you need:
+ - <a href="http://www.activestate.com/activeperl/downloads">perl</a> installed; \p PATH environment variable
+ should contain full path to Perl binary. Perl is used to generate large dictionary for testing purpose;
+ - <a href="http://www.boost.org/">boost library</a> 1.51 and above. You should create environment variable
+ \p BOOST_PATH containing full path to \p boost root directory (for example, <tt>C:\\libs\\boost_1_57_0</tt>).
+
+ Open solution file <tt>cds\projects\vc14\cds.sln</tt> with Microsoft VisualStudio 2015.
+ The solution contains \p cds project and a lot of test projects. Just build the library using solution.
+
+ <b>Warning</b>: the solution depends on \p BOOST_PATH environment variable that specifies full path
+ to \p boost library root directory. The test projects search \p boost libraries in:
+ - for 32bit: <tt>\$(BOOST_PATH)/stage/lib</tt>, <tt>\$(BOOST_PATH)/stage32/lib</tt>, and <tt>\$(BOOST_PATH)/bin</tt>.
+ - for 64bit: <tt>\$(BOOST_PATH)/stage64/lib</tt> and <tt>\$(BOOST_PATH)/bin</tt>.
+
+ All tests are based on googletest framework. The following environment variables specify
+ where to find gtest include and library directories:
+ - \p GTEST_ROOT - gtest root directory. <tt>\$(GTEST_ROOT)/include</tt> specifies full path to
+ gtest include files;
+ - \p GTEST_LIB64 - the path to 64bit gtest library dir;
+ - \p GTEST_LIB32 - the path to 32bit gtest library dir.
+
+ \par *NIX build
+
+ For Unix-like systems GCC and Clang compilers are supported.
+ Use GCC 4.8+ compiler or Clang 3.6+ to build <b>cds</b> library with CMake.
+ See accompanying file <tt>/build/cmake/readme.md</tt> for more info.
+
+ @note Important for GCC compiler: all your projects that use \p libcds must be compiled with <b>-fno-strict-aliasing</b>
+ compiler flag.
+
*/
- CDS_PROCESSOR_SPARC Sparc
- CDS_PROCESSOR_PPC64 PowerPC64
- CDS_PROCESSOR_ARM7 ARM v7
+ - CDS_PROCESSOR_ARM8 ARM v8
- CDS_PROCESSOR_UNKNOWN undefined processor architecture
CDS_PROCESSOR__NAME The name (string) of processor architecture
#define CDS_PROCESSOR_AMD64 4
#define CDS_PROCESSOR_PPC64 5 // PowerPC 64bit
#define CDS_PROCESSOR_ARM7 7
+#define CDS_PROCESSOR_ARM8 8
#define CDS_PROCESSOR_UNKNOWN -1
// Supported OS interfaces
#if defined(_MSC_VER)
# if defined(__ICL) || defined(__INTEL_COMPILER)
# define CDS_COMPILER CDS_COMPILER_INTEL
+# elif defined(__clang__)
+# define CDS_COMPILER CDS_COMPILER_CLANG
# else
# define CDS_COMPILER CDS_COMPILER_MSVC
# endif
// CDS_VERIFY: Debug - assert(_expr); Release - _expr
#ifdef CDS_DEBUG
-# define CDS_VERIFY( _expr ) assert( _expr )
-# define CDS_DEBUG_DO( _expr ) _expr
+# define CDS_VERIFY( _expr ) assert( _expr )
+# define CDS_VERIFY_FALSE( _expr ) assert( !( _expr ))
+# define CDS_DEBUG_ONLY( _expr ) _expr
#else
# define CDS_VERIFY( _expr ) _expr
-# define CDS_DEBUG_DO( _expr )
+# define CDS_VERIFY_FALSE( _expr ) _expr
+# define CDS_DEBUG_ONLY( _expr )
#endif
#ifdef CDS_STRICT
#define CDS_NOEXCEPT CDS_NOEXCEPT_SUPPORT
#define CDS_NOEXCEPT_( expr ) CDS_NOEXCEPT_SUPPORT_( expr )
-#ifndef CDS_NOEXCEPT_DEFAULTED
- // Some compilers do not allow noexcept specification in defaulted function
- // For example, GCC 4.6.x raise following error:
- // void foo() noexcept = default
- // error: function \91foo\92 defaulted on its first declaration must not have an exception-specification
- // For such compiler empty CDS_NOEXCEPT_DEFAULTED must be defined
-# define CDS_NOEXCEPT_DEFAULTED CDS_NOEXCEPT
-# define CDS_NOEXCEPT_DEFAULTED_(expr) CDS_NOEXCEPT_( expr )
-#endif
#ifdef CDS_CXX11_INLINE_NAMESPACE_SUPPORT
# define CDS_CXX11_INLINE_NAMESPACE inline
# define CDS_CXX11_INLINE_NAMESPACE
#endif
-//@cond
-// typedefs for back compatibility
-namespace cds {
- /// Atomic pointer
- typedef void * pointer_t;
-
- /// 64bit unaligned int
- typedef int64_t atomic64_unaligned;
-
- /// 64bit unaligned unsigned int
- typedef uint64_t atomic64u_unaligned;
-
- /// 64bit aligned int
- typedef atomic64_unaligned CDS_TYPE_ALIGNMENT(8) atomic64_aligned;
-
- /// 64bit aligned unsigned int
- typedef atomic64u_unaligned CDS_TYPE_ALIGNMENT(8) atomic64u_aligned;
-
- /// 64bit atomic int (aligned)
- typedef atomic64_aligned atomic64_t;
-
- /// 64bit atomic unsigned int (aligned)
- typedef atomic64u_aligned atomic64u_t;
-
- /// 32bit atomic int
- typedef int32_t atomic32_t;
-
- /// 32bit atomic unsigned int
- typedef uint32_t atomic32u_t;
-
- /// atomic int
- typedef atomic32_t atomic_t;
-
- /// atomic unsigned int
- typedef atomic32u_t unsigned_atomic_t;
-
- /// atomic int sized as pointer
- typedef intptr_t ptr_atomic_t;
-
- /// atomic unsigned int sized as pointer
- typedef uintptr_t uptr_atomic_t;
-} // namespace cds
-//@endcond
-
/*************************************************************************
Common things
**************************************************************************/
-#include <cds/details/numtraits.h>
-
namespace cds {
- /// Base of all exceptions in the library
- class Exception: public std::exception
- {
- protected:
- std::string m_strMsg ; ///< Exception message
- public:
- /// Create empty exception
- Exception()
- {}
- /// Create exception with message
- explicit Exception( const char * pszMsg )
- : m_strMsg( pszMsg )
- {}
- /// Create exception with message
- explicit Exception( const std::string& strMsg )
- :m_strMsg( strMsg )
- {}
-
- /// Destructor
- virtual ~Exception() throw()
- {}
-
- /// Return exception message
- virtual const char * what( ) const throw()
- {
- return m_strMsg.c_str();
- }
- };
-
-//@cond
-# define CDS_PURE_VIRTUAL_FUNCTION_CALLED { assert(false); throw Exception("Pure virtual function called"); }
-# define CDS_PURE_VIRTUAL_FUNCTION_CALLED_(method_name) { assert(false); throw Exception("Pure virtual function called " method_name ); }
-//@endcond
-
/// any_type is used as a placeholder for auto-calculated type (usually in \p rebind templates)
struct any_type {};
- /** \def CDS_DECLARE_EXCEPTION( _class, _msg )
- Simplifying declaration of specific exception (usual within classes)
- - @p _class - the class name of exception
- - @p _msg - exception message (const char *)
- */
-#define CDS_DECLARE_EXCEPTION( _class, _msg ) \
- struct _class: public std::exception { \
- public: \
- _class(): std::exception() {} \
- virtual const char * what( ) const throw() { return _msg; } \
- }
-
} // namespace cds
-
-//@cond
-#ifdef _DEBUG
-# define cds_assert(X) assert(X)
-#else
-# include <stdio.h> // snprintf
- static inline void cds_assert_( bool bCond, char const * pszMsg, char const * pszFile, int nLine )
- {
- if ( !bCond ) {
- char buf[4096];
-# if CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL
- _snprintf_s( buf, sizeof(buf)/sizeof(buf[0]), _TRUNCATE, pszMsg, pszFile, nLine );
-# else
- snprintf( buf, sizeof(buf)/sizeof(buf[0]), pszMsg, pszFile, nLine );
-# endif
- throw cds::Exception( buf );
- }
- }
-# define cds_assert(X) cds_assert_( X, "%s (%d): Assert failed: " #X, __FILE__, __LINE__ );
-#endif
-//@endcond
-
-#endif // #ifndef __CDS_DEFS_H
+#endif // #ifndef CDSLIB_DEFS_H
projects / libcds.git / blobdiff