A C++ library of Concurrent Data Structures

Overview

CDS C++ library

Codacy Badge GitHub version License Build Status Build status

The Concurrent Data Structures (CDS) library is a collection of concurrent containers that don't require external (manual) synchronization for shared access, and safe memory reclamation (SMR) algorithms like Hazard Pointer and user-space RCU that is used as an epoch-based SMR.

CDS is mostly header-only template library. Only SMR core implementation is segregated to .so/.dll file.

The library contains the implementations of the following containers:

  • lock-free stack with optional elimination support
  • several algo for lock-free queue, including classic Michael & Scott algorithm and its derivatives, the flat combining queue, the segmented queue.
  • several implementation of unordered set/map - lock-free and fine-grained lock-based
  • flat-combining technique
  • lock-free skip-list
  • lock-free FeldmanHashMap/Set Multi-Level Array Hash with thread-safe bidirectional iterator support
  • Bronson's et al algorithm for fine-grained lock-based AVL tree

Generally, each container has an intrusive and non-intrusive (STL-like) version belonging to cds::intrusive and cds::container namespace respectively.

Version 2.x of the library is written on C++11 and can be compiled by GCC 4.8+, clang 3.6+, Intel C++ 15+, and MS VC++ 14 (2015) and above

Download the latest release from http://sourceforge.net/projects/libcds/files/

See online doxygen-generated doc here: http://libcds.sourceforge.net/doc/cds-api/index.html

How to build

  • *nix: use CMake
  • Windows: use MS Visual C++ 2017 project

Some parts of libcds may depend on DCAS (double-width compare-and-swap) atomic primitive if the target architecture supports it. For x86, cmake build script enables -mcx16 compiler flag that switches DCAS support on. You may manually disable DCAS support with the following command line flags in GCC/clang (for MS VC++ compiler DCAS is not supported):

  • -DCDS_DISABLE_128BIT_ATOMIC - for 64bit build
  • -DCDS_DISABLE_64BIT_ATOMIC - for 32bit build

All your projects AND libcds MUST be compiled with the same flags - either with DCAS support or without it.

**Building libcds -use vcpkg

You can download and install libcds using the vcpkg dependency manager:

git clone https://github.com/Microsoft/vcpkg.git
cd vcpkg
./bootstrap-vcpkg.sh
./vcpkg integrate install
vcpkg install libcds

The libcds port in vcpkg is kept up to date by Microsoft team members and community contributors. If the version is out of date, please create an issue or pull request on the vcpkg repository.

Pull request requirements

  • Pull-request to master branch will be unconditionally rejected
  • integration branch is intended for pull-request. Usually, integration branch is the same as master
  • dev branch is intended for main developing. Usually, it contains unstable code

Project stats

References

Stack

  • TreiberStack: [1986] R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
  • Elimination back-off implementation is based on idea from [2004] Danny Hendler, Nir Shavit, Lena Yerushalmi "A Scalable Lock-free Stack Algorithm" pdf
  • FCStack - flat-combining wrapper for std::stack

Queue

  • BasketQueue: [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue" pdf
  • MSQueue:
    • [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms" pdf
    • [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes" pdf
    • [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" pdf
  • RWQueue: [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms" pdf
  • MoirQueue: [2000] Simon Doherty, Lindsay Groves, Victor Luchangco, Mark Moir "Formal Verification of a practical lock-free queue algorithm" pdf
  • OptimisticQueue: [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues" pdf
  • SegmentedQueue: [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency" pdf
  • FCQueue - flat-combining wrapper for std::queue
  • VyukovMPMCCycleQueue Dmitry Vyukov (see http://www.1024cores.net)

Deque

  • flat-combining deque based on stl::deque

Map, set

  • MichaelHashMap: [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets" pdf
  • SplitOrderedList: [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables" pdf
  • StripedMap, StripedSet: [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
  • CuckooMap, CuckooSet: [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
  • SkipListMap, SkipListSet: [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
  • FeldmanHashMap, FeldmanHashSet: [2013] Steven Feldman, Pierre LaBorde, Damian Dechev "Concurrent Multi-level Arrays: Wait-free Extensible Hash Maps". Supports thread-safe bidirectional iterators pdf

Ordered single-linked list

  • LazyList: [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit "A Lazy Concurrent List-Based Set Algorithm" pdf
  • MichaelList: [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets" pdf

Priority queue

  • MSPriorityQueue: [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott "An efficient algorithm for concurrent priority queue heaps" pdf

Tree

  • EllenBinTree: [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree" pdf
  • BronsonAVLTreeMap - lock-based fine-grained AVL-tree implementation: [2010] Nathan Bronson, Jared Casper, Hassan Chafi, Kunle Olukotun "A Practical Concurrent Binary Search Tree" pdf

SMR

  • Hazard Pointers
    • [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes" pdf
    • [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" pdf
    • [2004] Andrei Alexandrescu, Maged Michael "Lock-free Data Structures with Hazard Pointers" pdf
  • User-space RCU
    • [2009] M.Desnoyers "Low-Impact Operating System Tracing" PhD Thesis, Chapter 6 "User-Level Implementations of Read-Copy Update" pdf
    • [2011] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "User-Level Implementations of Read-Copy Update" pdf

Flat Combining technique

  • [2010] Hendler, Incze, Shavit and Tzafrir "Flat Combining and the Synchronization-Parallelism Tradeoff" pdf
Issues
  • cache aware queue for multiple producers-consumers

    cache aware queue for multiple producers-consumers

    I will try to make an intrusive version, if I understand how it should be implemented. May need to change the interface of the container, and to make it richer.

    opened by hardened-steel 18
  • Can't build on Mac OS X

    Can't build on Mac OS X

    Hello!

    Please take look at this:

    cd build
    bash build.sh 
    compiler version=g++ 4.2.1
    Building with the following options ...
    Processor: x86
    Platform: darwin
    C Compiler: gcc
    C++ Compiler: g++
    C++ Compiler version: 4.2.1
    Bits to build: 0
    Compile options:  -m32 -fPIC -march=native -I 
    Link options:  -m32 -fPIC 
    Link options (for test cds-unit app):  -m32 -fPIC 
    PATH=/opt/local/bin:/opt/local/sbin:/usr/local/bin:/usr/bin:/bin:/usr/sbin:/sbin:/usr/local/go/bin
    LD_LIBRARY_PATH=
    BIN_PATH=../bin/gcc-x86-darwin-0
    OBJ_PATH=../obj/gcc-x86-darwin-0
    Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
    Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
    Build started
    ---------------------------------
    Make debug library
    g++ -std=c++11 -c  -D_DEBUG -O0 -g  -m32 -fPIC -march=native -I  -D_REENTRANT -D_POSIX_PTHREAD_SEMANTICS -D_FILE_OFFSET_BITS=64 -I..  -o ../obj/gcc-x86-darwin-0/debug/hp_gc.o ../src/hp_gc.cpp
    g++ -std=c++11 -c  -D_DEBUG -O0 -g  -m32 -fPIC -march=native -I  -D_REENTRANT -D_POSIX_PTHREAD_SEMANTICS -D_FILE_OFFSET_BITS=64 -I..  -o ../obj/gcc-x86-darwin-0/debug/init.o ../src/init.cpp
    In file included from ../src/init.cpp:19:
    ../cds/threading/details/cxx11_manager.h:18:16: error: thread-local storage is unsupported for the current target
            static thread_local ThreadDataPlaceholder CDS_DATA_ALIGNMENT(8) s_threadData;
                   ^
    ../cds/threading/details/cxx11_manager.h:19:16: error: thread-local storage is unsupported for the current target
            static thread_local ThreadData * s_pThreadData;
                   ^
    ../src/init.cpp:43:5: error: thread-local storage is unsupported for the current target
        thread_local threading::cxx11_internal::ThreadDataPlaceholder CDS_DATA_ALIGNMENT(8) threading::cxx11_internal::s_threadData;
        ^
    ../src/init.cpp:44:5: error: thread-local storage is unsupported for the current target
        thread_local threading::ThreadData * threading::cxx11_internal::s_pThreadData = nullptr;
        ^
    4 errors generated.
    make: *** [../obj/gcc-x86-darwin-0/debug/init.o] Error 1
    ```bash
    
    clang:
    ```bash
    clang --version
    Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
    Target: x86_64-apple-darwin14.1.0
    Thread model: posix
    

    OS: Mac OS X Yosemite

    opened by pavel-odintsov 17
  • Fix MinGW compilation

    Fix MinGW compilation

    • CDS_BUILD_LIB definition was missing in CMake which is reponsible for specifying dllexport attributes
    • CMake considers shared library a "runtime" on DLL platforms, so the install(TARGETS ...) call needs a RUNTIME DESTINATION option
    • One missing cast that caused a "Invalid conversion" compile error
    opened by lukas-w 7
  • Can't build on FreeBSD 10

    Can't build on FreeBSD 10

    Hello, again!

    There we have multiple issues with original FreeBSD's make.

    bash build.sh -c clang -x clang
    compiler version=clang 4.2.1
    Building with the following options ...
    Processor: amd64
    Platform: freebsd
    C Compiler: clang
    C++ Compiler: clang
    C++ Compiler version: 4.2.1
    Bits to build: 0
    Compile options:  -m64 -fPIC -march=native  -I 
    Link options:  -m64 -fPIC 
    Link options (for test cds-unit app):  -m64 -fPIC 
    PATH=/sbin:/bin:/usr/sbin:/usr/bin:/usr/games:/usr/local/sbin:/usr/local/bin:/root/bin
    LD_LIBRARY_PATH=
    BIN_PATH=../bin/clang-amd64-freebsd-0
    OBJ_PATH=../obj/clang-amd64-freebsd-0
    FreeBSD clang version 3.4.1 (tags/RELEASE_34/dot1-final 208032) 20140512
    Build started
    ---------------------------------
    Make debug library
    make: "/usr/local/src/libcds/build/Makefile" line 14: Missing dependency operator
    make: "/usr/local/src/libcds/build/Makefile" line 20: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 21: Missing dependency operator
    make: "/usr/local/src/libcds/build/Makefile" line 24: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 27: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 30: Need an operator
    make: "../projects/../projects/source.libcds.mk" line 2: Need an operator
    make: "../projects/../projects/source.libcds.mk" line 3: Need an operator
    make: "../projects/../projects/source.libcds.mk" line 4: Need an operator
    make: "../projects/../projects/source.libcds.mk" line 5: Need an operator
    make: "../projects/../projects/source.libcds.mk" line 6: Need an operator
    make: "../projects/../projects/source.libcds.mk" line 7: Need an operator
    make: "../projects/../projects/source.libcds.mk" line 8: Need an operator
    make: "../projects/../projects/source.libcds.mk" line 9: Need an operator
    make: "../projects/../projects/source.libcds.mk" line 10: Need an operator
    make: "../projects/../projects/source.libcds.mk" line 11: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 49: Missing dependency operator
    make: "/usr/local/src/libcds/build/Makefile" line 52: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 53: Missing dependency operator
    make: "/usr/local/src/libcds/build/Makefile" line 56: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 59: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 60: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 65: Missing dependency operator
    make: "/usr/local/src/libcds/build/Makefile" line 78: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 92: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 175: Missing dependency operator
    make: "/usr/local/src/libcds/build/Makefile" line 179: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 181: warning: duplicate script for target "make_test" ignored
    make: "/usr/local/src/libcds/build/Makefile" line 178: warning: using previous script for "make_test" defined here
    make: "/usr/local/src/libcds/build/Makefile" line 182: warning: duplicate script for target "make_test" ignored
    make: "/usr/local/src/libcds/build/Makefile" line 178: warning: using previous script for "make_test" defined here
    make: "/usr/local/src/libcds/build/Makefile" line 183: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 224: Missing dependency operator
    make: "/usr/local/src/libcds/build/Makefile" line 228: Need an operator
    make: "/usr/local/src/libcds/build/Makefile" line 230: warning: duplicate script for target "make_debug_test" ignored
    make: "/usr/local/src/libcds/build/Makefile" line 227: warning: using previous script for "make_debug_test" defined here
    make: "/usr/local/src/libcds/build/Makefile" line 231: warning: duplicate script for target "make_debug_test" ignored
    make: "/usr/local/src/libcds/build/Makefile" line 227: warning: using previous script for "make_debug_test" defined here
    make: "/usr/local/src/libcds/build/Makefile" line 232: Need an operator
    make: Fatal errors encountered -- cannot continue
    make: stopped in /usr/local/src/libcds/build
    
    opened by pavel-odintsov 6
  • Rename cds::gc::PTB to cds::gc::DHP

    Rename cds::gc::PTB to cds::gc::DHP

    The current Pass-the-Buck GC (cds::gc::PTB) implementation is not original pass-the-buck algo but it is nearly to Unbounded Hazard Pointer schema. So, it should be renamed to cds::gc::DHP (dynamic hazard pointer) in all code and tests.

    enhancement 
    opened by khizmax 6
  • Unification of container declaration

    Unification of container declaration

    Now, there are two types of container declarations:

    1. template <class GC, typename T, typename... Options> class type1;
    2. template <class GC, typename T, typename Traits = container_ns::traits > class type2;

    The first type of declaration is used mostly for simple containers like stacks and queues. That type of declaration leads to very long mangling names and to giant complicated debugging output. It is necessary to rewrite type1 declaration to type2 for all libcds containers.

    enhancement 
    opened by khizmax 6
  • Remove cds::gc::HRC

    Remove cds::gc::HRC

    Remove cds::gc::HRC SMR, reason:

    1. It is complex and unstable GC
    2. It is inefficient GC - no performance benefit

    Remove all container's specialization for gc::HRC

    enhancement 
    opened by khizmax 6
  • Supporting stateful allocators through stateful disposers

    Supporting stateful allocators through stateful disposers

    Hi,

    I'm trying to use LibCDS in a context where I have custom allocators that may contain state. I'm struggling to make this work, and I think the reason is that only stateless disposers are supported. Here's a toy example to express the problem I'm running into:

    template <typename T, typename Allocator, typename GC>
    class MyList {
        Allocator allocator_;
    
        struct rcu_disposer {
            void operator()(Node<T>* node) const {
                allocator_.deallocate(node);
            //  ^^^^^^^^^^ Can't have access to the allocator because the
            //             disposer can't be stateful!
            }
        };
    
    public:
        explicit MyList(Allocator const& alloc)
            : allocator_{alloc} // important: the allocator is stateful
        { }
    
        void erase(int i) {
            Node<T>* removed_node = remove_node_from_list(i);
            GC::template retire_ptr<rcu_disposer>(removed_node);
        }
    };
    

    Here, my allocator may contain state. Hence, I want my disposer, who is going to call deallocate(), to hold a reference to that allocator. If I understand correctly, this is impossible to achieve with LibCDS because only the type of the disposer can be passed to retire_ptr, but no instance of that type. Instead, I think being able to do the following would solve my problem:

    template <typename T, typename Allocator, typename GC>
    class MyList {
        Allocator allocator_;
    
        struct rcu_disposer {
            Allocator& alloc_;
            void operator()(Node<T>* node) const {
                alloc_.deallocate(node);
            }
        };
    
    public:
        explicit MyList(Allocator const& alloc)
            : allocator_{alloc} // important: the allocator is stateful
        { }
    
        void erase(int i) {
            Node<T>* removed_node = remove_node_from_list(i);
            rcu_disposer disposer{allocator_};
            GC::template retire_ptr<rcu_disposer>(removed_node, disposer);
        }
    };
    

    Hence, I have the following questions:

    • Is my use case of stateful allocators supported by LibCDS today, and if so, how can I do it?
    • If this is not supported, is there desire to add support for it?

    Thanks!

    opened by ldionne 5
  • crash TestIntrusiveStack::Elimination_DHP_member_disposer_relaxed . clang 3.5/libc++

    crash TestIntrusiveStack::Elimination_DHP_member_disposer_relaxed . clang 3.5/libc++

    In release mode, this test crashes. In debug mode, it deadlocks. I have attached the call stacks of both.

    RELEASE

    ./test-hdr 
    libcds version 2.1.0
    Test started 2015-May-12 20:58:34
    Using test config file: test.conf
    System topology:
        Logical processor count: 8
    
    Use in-place scan strategy for Hazard Pointer memory reclamation algorithm
         Hazard Pointer count: 72
      Max thread count for HP: 100
    Retired HP array capacity: 1600
    
    TestIntrusiveStack::Elimination_DHP_member_disposer_relaxed
    thread_init_fini::init_fini
            Thread init/fini test,
        thread count=8 pass count=100000...
               Duration=1.13611Segmentation fault (core dumped)
    
    
    Core was generated by `./test-hdr'.
    Program terminated with signal 11, Segmentation fault.
    #0  0x00007f4d245f57e0 in boost::detail::thread_data_base::~thread_data_base() () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
    (gdb) where
    #0  0x00007f4d245f57e0 in boost::detail::thread_data_base::~thread_data_base() () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
    #1  0x000000000991fa69 in boost::detail::thread_data<boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > > >::~thread_data() ()
    #2  0x00007f4d245f778e in boost::detail::sp_counted_base::release() () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
    #3  0x00000000079ec7dc in boost::thread::~thread() ()
    #4  0x00000000079ebf5f in thread_init_fini::Thread::~Thread() ()
    #5  0x000000000991ed42 in CppUnitMini::ThreadPool::~ThreadPool() ()
    #6  0x00000000079ebd61 in thread_init_fini::init_fini() ()
    #7  0x00000000079eb772 in thread_init_fini::myRun(char const*, bool) ()
    #8  0x000000000990b228 in CppUnitMini::TestCase::run(CppUnitMini::Reporter*, char const*, bool) ()
    #9  0x000000000990d0a9 in main ()
    (gdb) thread apply all backtrace
    
    Thread 3 (Thread 0x7f4d228ec700 (LWP 7728)):
    #0  [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
    #1  0x00007f4d23f4ebc6 in std::__1::condition_variable::wait(std::__1::unique_lock<std::__1::mutex>&) () from /usr/lib/x86_64-linux-gnu/libc++.so.1
    #2  0x000000000990eb4b in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::execute() ()
    #3  0x000000000990ea9e in void* std::__1::__thread_proxy<std::__1::tuple<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> >(void*) ()
    #4  0x00007f4d241cff6e in start_thread (arg=0x7f4d228ec700) at pthread_create.c:311
    #5  0x00007f4d236f49cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113
    
    Thread 2 (Thread 0x7f4d230ed700 (LWP 7727)):
    #0  [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
    #1  0x00007f4d23f4ebc6 in std::__1::condition_variable::wait(std::__1::unique_lock<std::__1::mutex>&) () from /usr/lib/x86_64-linux-gnu/libc++.so.1
    #2  0x000000000990eb4b in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::execute() ()
    #3  0x000000000990ea9e in void* std::__1::__thread_proxy<std::__1::tuple<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> >(void*) ()
    #4  0x00007f4d241cff6e in start_thread (arg=0x7f4d230ed700) at pthread_create.c:311
    #5  0x00007f4d236f49cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113
    
    Thread 1 (Thread 0x7f4d24bf5840 (LWP 7726)):
    #0  0x00007f4d245f57e0 in boost::detail::thread_data_base::~thread_data_base() () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
    #1  0x000000000991fa69 in boost::detail::thread_data<boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > > >::~thread_data() ()
    #2  0x00007f4d245f778e in boost::detail::sp_counted_base::release() () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
    #3  0x00000000079ec7dc in boost::thread::~thread() ()
    #4  0x00000000079ebf5f in thread_init_fini::Thread::~Thread() ()
    #5  0x000000000991ed42 in CppUnitMini::ThreadPool::~ThreadPool() ()
    #6  0x00000000079ebd61 in thread_init_fini::init_fini() ()
    #7  0x00000000079eb772 in thread_init_fini::myRun(char const*, bool) ()
    #8  0x000000000990b228 in CppUnitMini::TestCase::run(CppUnitMini::Reporter*, char const*, bool) ()
    #9  0x000000000990d0a9 in main ()
    

    DEBUG.

    clang 3.5 DEBUG build. -stdlib=libc++
    
    bin ❯ ./test-hdr 
    libcds version 2.1.0
    Test started 2015-May-12 05:33:55
    Using test config file: test-debug.conf
    System topology:
        Logical processor count: 8
    
    Use in-place scan strategy for Hazard Pointer memory reclamation algorithm
         Hazard Pointer count: 72
      Max thread count for HP: 100
    Retired HP array capacity: 1600
    
    
    TestIntrusiveStack::Elimination_DHP_member_disposer_relaxed
    thread_init_fini::init_fini
            Thread init/fini test,
        thread count=4 pass count=100000...
    
    (gdb) info threads
      Id   Target Id         Frame 
      6    Thread 0x7f43aa373700 (LWP 4014) "test-hdr" [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
      5    Thread 0x7f43a9b72700 (LWP 4015) "test-hdr" [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
      4    Thread 0x7f43a9371700 (LWP 4016) "test-hdr" [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
      3    Thread 0x7f43a3fff700 (LWP 4018) "test-hdr" [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
      2    Thread 0x7f43a37fe700 (LWP 4019) "test-hdr" [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
    * 1    Thread 0x7f43abe97840 (LWP 4013) "test-hdr" [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
    
    
    (gdb) thread apply all backtrace
    
    Thread 6 (Thread 0x7f43aa373700 (LWP 4014)):
    #0  [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
    #1  0x00007f43ab1d4bc6 in std::__1::condition_variable::wait(std::__1::unique_lock<std::__1::mutex>&) () from /usr/lib/x86_64-linux-gnu/libc++.so.1
    #2  0x0000000017d71e8a in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::execute (this=0x3173ebd8)
        at /home/khegeman/dev/libcds/cds/urcu/dispose_thread.h:85
    #3  0x0000000017d71475 in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::dispose_thread_starter::thread_func (pThis=0x3173ebd8)
        at /home/khegeman/dev/libcds/cds/urcu/dispose_thread.h:38
    #4  0x0000000017d71b25 in __invoke<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> (__f=<unknown type in /home/khegeman/build/libcds_clangdebuglibc/bin/test-hdr, CU 0x87b9d58, DIE 0x87dddcc>, 
        __args=<unknown type in /home/khegeman/build/libcds_clangdebuglibc/bin/test-hdr, CU 0x87b9d58, DIE 0x87dddd4>) at /usr/include/c++/v1/__functional_base:413
    #5  __thread_execute<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*, 1> (__t=...) at /usr/include/c++/v1/thread:332
    #6  std::__1::__thread_proxy<std::__1::tuple<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> > (__vp=0x3173d5e0) at /usr/include/c++/v1/thread:342
    #7  0x00007f43ab455f6e in start_thread (arg=0x7f43aa373700) at pthread_create.c:311
    #8  0x00007f43aa97a9cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113
    
    Thread 5 (Thread 0x7f43a9b72700 (LWP 4015)):
    #0  [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
    #1  0x00007f43ab1d4bc6 in std::__1::condition_variable::wait(std::__1::unique_lock<std::__1::mutex>&) () from /usr/lib/x86_64-linux-gnu/libc++.so.1
    #2  0x0000000017d71e8a in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::execute (this=0x3173f078)
        at /home/khegeman/dev/libcds/cds/urcu/dispose_thread.h:85
    #3  0x0000000017d71475 in cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >::dispose_thread_starter::thread_func (pThis=0x3173f078)
        at /home/khegeman/dev/libcds/cds/urcu/dispose_thread.h:38
    #4  0x0000000017d71b25 in __invoke<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> (__f=<unknown type in /home/khegeman/build/libcds_clangdebuglibc/bin/test-hdr, CU 0x87b9d58, DIE 0x87dddcc>, 
        __args=<unknown type in /home/khegeman/build/libcds_clangdebuglibc/bin/test-hdr, CU 0x87b9d58, DIE 0x87dddd4>) at /usr/include/c++/v1/__functional_base:413
    #5  __thread_execute<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*, 1> (__t=...) at /usr/include/c++/v1/thread:332
    #6  std::__1::__thread_proxy<std::__1::tuple<void (*)(cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*), cds::urcu::dispose_thread<cds::container::VyukovMPMCCycleQueue<cds::urcu::epoch_retired_ptr, cds::container::vyukov_queue::traits> >*> > (__vp=0x3173f150) at /usr/include/c++/v1/thread:342
    #7  0x00007f43ab455f6e in start_thread (arg=0x7f43a9b72700) at pthread_create.c:311
    #8  0x00007f43aa97a9cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113
    
    Thread 4 (Thread 0x7f43a9371700 (LWP 4016)):
    #0  [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
    #1  0x0000000017da9ce0 in boost::condition_variable::wait (this=0x31780ff8, m=...) at /usr/include/boost/thread/pthread/condition_variable.hpp:73
    #2  0x0000000017da634a in boost::barrier::wait (this=0x31780fd0) at /usr/include/boost/thread/barrier.hpp:233
    #3  0x0000000017da4b60 in CppUnitMini::ThreadPool::onThreadFiniDone (this=0x7ffff4bc89f0) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:127
    #4  0x0000000017da4995 in CppUnitMini::TestThread::run (this=0x3177e410) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:29
    #5  0x0000000017da4905 in CppUnitMini::TestThread::threadEntryPoint (pInst=0x3177e410) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:11
    #6  0x0000000017da9845 in boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> >::operator()<void (*)(CppUnitMini::TestThread*), boost::_bi::list0> (this=0x317819d8, 
        [email protected]: 0x17da48f0 <CppUnitMini::TestThread::threadEntryPoint(CppUnitMini::TestThread*)>, a=...) at /usr/include/boost/bind/bind.hpp:253
    #7  0x0000000017da97cf in boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > >::operator() (this=0x317819d0)
        at /usr/include/boost/bind/bind_template.hpp:20
    #8  0x0000000017da85cc in boost::detail::thread_data<boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > > >::run (this=0x31781830)
        at /usr/include/boost/thread/detail/thread.hpp:116
    #9  0x00007f43ab87a94a in ?? () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
    #10 0x00007f43ab455f6e in start_thread (arg=0x7f43a9371700) at pthread_create.c:311
    #11 0x00007f43aa97a9cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113
    
    Thread 3 (Thread 0x7f43a3fff700 (LWP 4018)):
    #0  [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
    #1  0x0000000017da9ce0 in boost::condition_variable::wait (this=0x31780ff8, m=...) at /usr/include/boost/thread/pthread/condition_variable.hpp:73
    #2  0x0000000017da634a in boost::barrier::wait (this=0x31780fd0) at /usr/include/boost/thread/barrier.hpp:233
    #3  0x0000000017da4b60 in CppUnitMini::ThreadPool::onThreadFiniDone (this=0x7ffff4bc89f0) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:127
    #4  0x0000000017da4995 in CppUnitMini::TestThread::run (this=0x3177af20) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:29
    #5  0x0000000017da4905 in CppUnitMini::TestThread::threadEntryPoint (pInst=0x3177af20) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:11
    #6  0x0000000017da9845 in boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> >::operator()<void (*)(CppUnitMini::TestThread*), boost::_bi::list0> (this=0x31783318, 
        [email protected]: 0x17da48f0 <CppUnitMini::TestThread::threadEntryPoint(CppUnitMini::TestThread*)>, a=...) at /usr/include/boost/bind/bind.hpp:253
    #7  0x0000000017da97cf in boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > >::operator() (this=0x31783310)
        at /usr/include/boost/bind/bind_template.hpp:20
    #8  0x0000000017da85cc in boost::detail::thread_data<boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > > >::run (this=0x31783170)
        at /usr/include/boost/thread/detail/thread.hpp:116
    #9  0x00007f43ab87a94a in ?? () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
    #10 0x00007f43ab455f6e in start_thread (arg=0x7f43a3fff700) at pthread_create.c:311
    #11 0x00007f43aa97a9cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113
    
    Thread 2 (Thread 0x7f43a37fe700 (LWP 4019)):
    #0  [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
    #1  0x0000000017da9ce0 in boost::condition_variable::wait (this=0x31780ff8, m=...) at /usr/include/boost/thread/pthread/condition_variable.hpp:73
    #2  0x0000000017da634a in boost::barrier::wait (this=0x31780fd0) at /usr/include/boost/thread/barrier.hpp:233
    #3  0x0000000017da4b60 in CppUnitMini::ThreadPool::onThreadFiniDone (this=0x7ffff4bc89f0) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:127
    #4  0x0000000017da4995 in CppUnitMini::TestThread::run (this=0x31781d20) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:29
    #5  0x0000000017da4905 in CppUnitMini::TestThread::threadEntryPoint (pInst=0x31781d20) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:11
    #6  0x0000000017da9845 in boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> >::operator()<void (*)(CppUnitMini::TestThread*), boost::_bi::list0> (this=0x31769db8, 
        [email protected]: 0x17da48f0 <CppUnitMini::TestThread::threadEntryPoint(CppUnitMini::TestThread*)>, a=...) at /usr/include/boost/bind/bind.hpp:253
    #7  0x0000000017da97cf in boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > >::operator() (this=0x31769db0)
        at /usr/include/boost/bind/bind_template.hpp:20
    #8  0x0000000017da85cc in boost::detail::thread_data<boost::_bi::bind_t<void, void (*)(CppUnitMini::TestThread*), boost::_bi::list1<boost::_bi::value<CppUnitMini::TestThread*> > > >::run (this=0x31769c10)
        at /usr/include/boost/thread/detail/thread.hpp:116
    #9  0x00007f43ab87a94a in ?? () from /usr/lib/x86_64-linux-gnu/libboost_thread.so.1.53.0
    #10 0x00007f43ab455f6e in start_thread (arg=0x7f43a37fe700) at pthread_create.c:311
    #11 0x00007f43aa97a9cd in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:113
    
    Thread 1 (Thread 0x7f43abe97840 (LWP 4013)):
    #0  [email protected]@GLIBC_2.3.2 () at ../nptl/sysdeps/unix/sysv/linux/x86_64/pthread_cond_wait.S:185
    #1  0x0000000017da9ce0 in boost::condition_variable::wait (this=0x31780ff8, m=...) at /usr/include/boost/thread/pthread/condition_variable.hpp:73
    #2  0x0000000017da634a in boost::barrier::wait (this=0x31780fd0) at /usr/include/boost/thread/barrier.hpp:233
    #3  0x0000000017da5310 in CppUnitMini::ThreadPool::run (this=0x7ffff4bc89f0) at /home/khegeman/dev/libcds/tests/cppunit/thread.cpp:82
    #4  0x0000000014ef2261 in thread_init_fini::init_fini (this=0x3154e338 <_ZL5local>) at /home/khegeman/dev/libcds/tests/test-hdr/misc/thread_init_fini.cpp:62
    #5  0x0000000014ef190a in thread_init_fini::myRun (this=0x3154e338 <_ZL5local>, in_name=0x181b8f10 "", invert=false) at /home/khegeman/dev/libcds/tests/test-hdr/misc/thread_init_fini.cpp:73
    #6  0x0000000017d68c99 in CppUnitMini::TestCase::run (in_reporter=0x3173d600, in_testName=0x181b8f10 "", invert=false) at /home/khegeman/dev/libcds/tests/cppunit/test_main.cpp:111
    #7  0x0000000017d6b9d1 in main (argc=1, argv=0x7ffff4bc97e8) at /home/khegeman/dev/libcds/tests/cppunit/test_main.cpp:447
    
    opened by khegeman 5
  • make m_nAttachCount atomic

    make m_nAttachCount atomic

    m_nAttachCount might be concurrently accessed by multi-threads when they try to initialize thread data. If not being atomic protected, non-main thread might get the chance to call detach_thread here https://github.com/khizmax/libcds/blob/777f7a5aae463085ebf987af232ff976e97ca529/src/thread_data.cpp#L42 and eventually failed at here https://github.com/khizmax/libcds/blob/777f7a5aae463085ebf987af232ff976e97ca529/src/hp.cpp#L474

    opened by weilewei 4
  • Added osx to travis

    Added osx to travis

    Добавил в travis-ci сборки в виртуальных машинах OSX. Изменил в test/include/cds_test/fixture.h как Вы предлагали, это помогло с ошибками в тестах.

    Очереди на вм с OSX очень долгие, что очень удленяет сборку. Можно будет, позже, премешать сборки linux и osx, таким образом, чтобы пока нет свободных osx-машин сбоирались linux сборки.

    opened by mgalimullin 4
  • Why KV list's update() method have no argument with Value to insert ?

    Why KV list's update() method have no argument with Value to insert ?

    Is there any strong reason to not accept Value at update() ?

    For example, MichaelKVList::insert() is declared as

            template <typename K, typename V>
            bool insert( K&& key, V&& val )
    

    while there is no update() with V argument.

    Yes, we could pass functor that will assing new value to the newly inserted item but there is time window between item insertion and functor execution when another thread could find just inserted item with empty second and all it can do is to spin until second will be initialized.

    Why not pass V into update() ? Am I missing something ?

    opened by hvlad 0
  • Cannot build properly on MacOS Big Sur 11.2.3 (Apple M1)

    Cannot build properly on MacOS Big Sur 11.2.3 (Apple M1)

    Operating sytem: macOS Big Sure v11.2.3 CPU: Apple M1 Compiler:

    Apple clang version 12.0.0 (clang-1200.0.32.29)
    Target: arm64-apple-darwin20.3.0
    Thread model: posix
    InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin
    

    Commands and output:

    > cmake -DCMAKE_BUILD_TYPE=RELEASE [PATH_OF_SOURCE_CODE]
    > make -j4
    
    [  8%] Building CXX object CMakeFiles/cds.dir/src/urcu_sh.cpp.o
    [  8%] Building CXX object CMakeFiles/cds-s.dir/src/dhp.cpp.o
    [ 16%] Building CXX object CMakeFiles/cds.dir/src/hp_thread_local.cpp.o
    [ 12%] Building CXX object CMakeFiles/cds-s.dir/src/hp_thread_local.cpp.o
    clang: warning: argument unused during compilation: '-mcx16' [-Wunused-command-line-argument]
    clang: warning: argument unused during compilation: '-mcx16' [-Wunused-command-line-argument]
    clang: warning: argument unused during compilation: '-mcx16' [-Wunused-command-line-argument]
    clang: warning: argument unused during compilation: '-mcx16' [-Wunused-command-line-argument]
    /Users/xiaoliangwu/Workspace/libcds_source_code/src/hp_thread_local.cpp:39:46: error: invalid operands to binary expression
          ('cds::OS::posix::ThreadId' (aka '_opaque_pthread_t *') and 'int')
            if (cds::OS::get_current_thread_id() % 2 == 0) { // % 2 with ThreadId structure?
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~
    /Users/xiaoliangwu/Workspace/libcds_source_code/src/hp_thread_local.cpp:47:46: error: invalid operands to binary expression
          ('cds::OS::posix::ThreadId' (aka '_opaque_pthread_t *') and 'int')
            if (cds::OS::get_current_thread_id() % 2 == 0) { // % 2 with ThreadId structure?
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~
    /Users/xiaoliangwu/Workspace/libcds_source_code/src/hp_thread_local.cpp:39:46: error: invalid operands to binary expression
          ('cds::OS::posix::ThreadId' (aka '_opaque_pthread_t *') and 'int')
            if (cds::OS::get_current_thread_id() % 2 == 0) { // % 2 with ThreadId structure?
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~
    /Users/xiaoliangwu/Workspace/libcds_source_code/src/hp_thread_local.cpp:47:46: error: invalid operands to binary expression
          ('cds::OS::posix::ThreadId' (aka '_opaque_pthread_t *') and 'int')
            if (cds::OS::get_current_thread_id() % 2 == 0) { // % 2 with ThreadId structure?
                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~
    2 errors generated.
    2 errors generated.
    make[2]: *** [CMakeFiles/cds-s.dir/src/hp_thread_local.cpp.o] Error 1
    make[2]: *** Waiting for unfinished jobs....
    make[2]: *** [CMakeFiles/cds.dir/src/hp_thread_local.cpp.o] Error 1
    make[2]: *** Waiting for unfinished jobs....
    [ 20%] Building CXX object CMakeFiles/cds-s.dir/src/urcu_gp.cpp.o
    clang: warning: argument unused during compilation: '-mcx16' [-Wunused-command-line-argument]
    [ 25%] Building CXX object CMakeFiles/cds.dir/src/thread_data.cpp.o
    clang: warning: argument unused during compilation: '-mcx16' [-Wunused-command-line-argument]
    make[1]: *** [CMakeFiles/cds-s.dir/all] Error 2
    make[1]: *** Waiting for unfinished jobs....
    make[1]: *** [CMakeFiles/cds.dir/all] Error 2
    make: *** [all] Error 2
    
    opened by xwu64 0
  • BronsonAVLTreeMap segfaults

    BronsonAVLTreeMap segfaults

    Here's a test program that reproduces this issue

    #include <omp.h>
    
    #include <vector>
    #include <map>
    #include <random>
    #include <iostream>
    
    #include <cds/init.h>
    #include <cds/urcu/general_buffered.h>
    #include <cds/container/bronson_avltree_map_rcu.h>
    
    using namespace cds::container;
    typedef cds::urcu::gc< cds::urcu::general_buffered<> > rcu_gpb;
    
    typedef std::pair<int, int> intp_t;
    static std::vector<intp_t> ref_vals;
    static std::map<int, int> sorted_vals;
    static const int N = 1000000;
    
    using namespace cds::container;
    typedef cds::urcu::gc< cds::urcu::general_buffered<> > rcu_gpb;
    
    void create_reference(int n) {
        std::mt19937 rng(112233L);
        ref_vals.resize(n);
        sorted_vals.clear();
        int i = 0;
        while (i < n) {
            int val = rng();
            auto it = sorted_vals.find(val);
            if (it != sorted_vals.end())
                continue;
            auto p = std::make_pair(val, val + 1);
            sorted_vals.insert(it, p);
            ref_vals[i] = p;
            i++;
        }
        std::cout << "Init complete, max element: " << sorted_vals.rbegin()->first + 1 << std::endl;
    }
    
    int main() {
        cds::Initialize();
        rcu_gpb rcuGPB;
    
        BronsonAVLTreeMap<rcu_gpb, int, int> map;
        create_reference(N);
        int t = std::thread::hardware_concurrency();
        #pragma omp parallel num_threads(t)
        {
            cds::threading::Manager::attachThread();
            #pragma omp for
            for (int i = 0; i < N; i++)
                map.insert(ref_vals[i].first, ref_vals[i].second);
            cds::threading::Manager::detachThread();
        }
        cds::Terminate();
        return 0;
    }
    
    opened by bnicolae 2
  • Impossible to build on visual studio (C2491 and C2720)

    Impossible to build on visual studio (C2491 and C2720)

    Hi, I'm posting this issue because I planned to use this library in one of my projects however it seems like the visual studio build is failing because of __declspec(dllimport) errors. I generated the vs solution from cmake since i'm using it as a dependency of my library.

    2>C:\Users\SeleDreams\OneDrive\Documents\CodeVoiceLib\libs\libcds\src\init.cpp(29): error C2720: 'cds::threading::wintls::Manager::Holder::m_key' : spécificateur de classe de stockage '__declspec(dllimport)' non conforme sur les membres 2>C:\Users\SeleDreams\OneDrive\Documents\CodeVoiceLib\libs\libcds\src\init.cpp(29): error C2491: 'cds::threading::wintls::Manager::Holder::m_key' : définition de données membres static dllimport non autorisée 2>C:\Users\SeleDreams\OneDrive\Documents\CodeVoiceLib\libs\libcds\src\init.cpp(52): error C2491: 'cds::details::check_hpstat_enabled' : définition de fonction dllimport non autorisée 2>C:\Users\SeleDreams\OneDrive\Documents\CodeVoiceLib\libs\libcds\src\init.cpp(67): error C2491: 'cds::details::init_first_call' : définition de fonction dllimport non autorisée 2>C:\Users\SeleDreams\OneDrive\Documents\CodeVoiceLib\libs\libcds\src\init.cpp(72): error C2491: 'cds::details::fini_last_call' : définition de fonction dllimport non autorisée

    opened by SeleDreams 2
Releases(v2.3.3)
  • v2.3.3(Dec 31, 2018)

    Maintenance release

    • Minimum CMake version is 3.0.2
    • Changed software license from BSD to Boost
    • Removed '#pragma lib' for Windows build
    • Bugfix and minor improvements
    Source code(tar.gz)
    Source code(zip)
  • v2.3.2(Dec 31, 2017)

    Maintenance release - Added: apply( Func f ) method to containers based on flat combining. This method allows to execute any function over underlying container in exclusive mode. - Removed: -fno-strict-aliasing requirement - Fixed: a serious bug in WeakRingBuffer::front() - Fixed: memcpy bug in CuckooHash with store_hash feature

    Source code(tar.gz)
    Source code(zip)
  • v2.3.1(Sep 1, 2017)

    Maintenance release

    • issue #81: bug in gc::DHP when extending thread's retired array
    • Improved CMake scripts for simplifying libcds intergration with other projects:
            find_package(LibCDS)
            add_library(mylib INTERFACE)
            target_link_libraries(mylib INTERFACE LibCDS::cds)
    
    Source code(tar.gz)
    Source code(zip)
  • v2.3.0(Jul 31, 2017)

    • Changed: cds::gc::HP is totally refactored:
      • simplified internal structures;
      • added ability to specify an external allocator for internal data;
      • external API for gc::HP is slightly changed: now scan type cannot be changed on the fly; it can be specified only in construction time.
    • Changed: cds::gc::DHP is totally refactored to overcome some internal limitations. Now gc::DHP is fully adaptive variant of Hazard Pointer SMR, any dependencies on count of thread are removed, count of retired data and hazard pointers per thread are increased automaticaly by perforce. External API of gc::DHP class is changed: now only initial count of hazard pointers can be specified in the constructor. Like new gc::HP, the new gc::DHP supports an external allocator.
    • Changed: exception handling. Now, exceptions raise by invoking new cds::throw_exception() function. If you compile your code with exception disabled, the function prints an exception message to stdout and calls abort() instead of throwing.
    • Flat Combining: fixed memory-order bug that can lead to crash on weak ordered architecture like PowerPC or ARM
    • Added: erase_at( iterator ) function to MichaelHashSet/Map and SplitListSet/Map based on IterableList
    • Fixed a bug in BronsonAVLTreeMap::extract_min()/extract_max()/clear().
    • Removed: signal-handled threaded uRCU (cds::urcu::signal_threaded) due bad performance
    • Added more flat-combining queue tests, thanks to Marsel Galimullin.
    • Changed cmake scripts to support MacOS and ARMv7/ARMv8 (64 bit), thanks to Michail Komarov (https://github.com/Nemo1369)
    • Stress tests: removed command line parameter --detail-level and envvar CDSTEST_DETAIL_LEVEL for reducing compile time and executable size. To make full testset compile libcds with -DCDS_STRESS_TEST_LEVEL=N where N is 1 or 2.
    • Changed: refactoring cds::backoff::exponential and cds::backoff::delay back-off strategies to avoid static data members in template classes.
    • The library is extensively tested on x86-64, PowerPC and AArch64, thanks to GCC Compile Farm project
    Source code(tar.gz)
    Source code(zip)
  • v2.2.0(Jan 4, 2017)

    • Changed: CMake is used for build libcds. Ancient build.sh has been removed
    • Changed: unit and stress tests are migrated to googletest framework
    • Added: IterableList - an implementation of ordered list with thread-safe iterator. MichaelSet/Map and SplitListSet/Map support this type of ordered list and thread-safe iterable too.
    • Added: wait strategies for flat combining technique. Based on research by Marsel Galimullin and Nikolai Rapotkin.
    • Fixed: SkipList erase() and find() bugs that cause to infinite loop or to program crash in rare case.
    • Fixed: serious bug in MichaelSet::emplace() function. New node was created twice from the arguments by move semantics. However, move semantics may change internal state of the argument that can lead to an incorrect element and even an incorrect key that breaks the set logic.
    • Fixed: bug in FeldmanHashSet::erase_at( iterator ): due an error in precondition checking the function may incorrectly return false.
    • Fixed: possible double-free case in flat combining algorithm. Thanks to Amila Jayasekara who pointed me to this problem
    • Changed: cds::opt::buffer option is divided to initialized (cds::opt::v::initialized_dynamic_buffer, cds::opt::v::initialized_static_buffer) and uninitialized (cds::opt::v::uninitialized_dynamic_buffer, cds::opt::v::uninitialized_static_buffer) ones. The old cds::opt::v::dynamic_buffer and cds::opt::v::static_buffer classes are removed.
    • Removed: TsigasCysleQueue (due undecidable ABA-problem)
    • Removed: Michael's allocator cds/memory/michael/allocator.h
    • Fixed: use-after-free bug in VyukovMPMCCycleQueue internal buffer. To prevent this bug the queue uses an uninitialized buffer now.
    • Fixed: rare priority inversion bug in MSPriorityQueue
    • Added: for minimizing runtime of stress test the detail level for some test is added. Command line argument --detail-level=N specifies what test should be ran: each test with level not greater than N will be ran. Instead of command line arg the enviromnent variable CDSTEST_DETAIL_LEVEL=N may be used. By default, the detail level is 0 that means only limited set of the test will be ran.
    Source code(tar.gz)
    Source code(zip)
  • v2.1.0(Jan 6, 2016)

    General release
    - Added: FeldmanHashSet/Map - an interesting hash map algorithm
      based on multi-level array, requires perfect hashing or fixed-sized keys.
      Supports thread-safe bidirectional iterators.
    - Added: BronsonAVLTreeMap - Bronson's et al AVL tree implementation
    - Added: CMake build script, thanks to Eugeny Kalishenko
    - Changed: SplitList performance improving, thanks to Mike Krinkin
    - Changed: semantic of member functions extract(), get() and its
      variants for MichaelList RCU-based specialization: extract() does not
      require RCU locking, get() now returns special wrapper object of type raw_ptr,
      see doc.
      Thus, semantics of extract()/get() of all RCU-based set and maps based on 
      MichaelList (MichaelSet/Map, SplitListSet/Map) has been changed too.
    - Changed: SplitListSet/Map functions get() and get_with() return special wrapper
      object of type raw_ptr, see doc.
    - Removed: SplitListSet/Map force_dispose() function.
    - cds::lock namespace is renamed to cds::sync. All classes defined in cds::lock namespace 
      are moved to cds::sync with new names (for example, cds:: lock ::SpinLock is renamed to
      cds::sync::spin_lock). cds::lock namespace and its contents is deprecated, it is kept 
      for backward compatibility.
    - The library has been checked by ThreadSanitizer, a lot of bugs has been fixed
    - Added support for clang 3.7 with libc++ 
    
    Source code(tar.gz)
    Source code(zip)
A C++ library providing various concurrent data structures and reclamation schemes.

xenium xenium is a header-only library that provides a collection of concurrent data structures and memory reclamation algorithms. The data structures

Manuel Pöter 309 Jun 19, 2022
Concurrency Kit 2.1k Jun 18, 2022
Concurrent data structures in C++

Junction is a library of concurrent data structures in C++. It contains several hash map implementations: junction::ConcurrentMap_Crude junction::Conc

Jeff Preshing 1.2k Jun 15, 2022
:copyright: Concurrent Programming Library (Coroutine) for C11

libconcurrent tiny asymmetric-coroutine library. Description asymmetric-coroutine bidirectional communication by yield_value/resume_value native conte

sharow 347 Jun 5, 2022
A fast multi-producer, multi-consumer lock-free concurrent queue for C++11

moodycamel::ConcurrentQueue An industrial-strength lock-free queue for C++. Note: If all you need is a single-producer, single-consumer queue, I have

Cameron 6.8k Jun 24, 2022
A bounded multi-producer multi-consumer concurrent queue written in C++11

MPMCQueue.h A bounded multi-producer multi-consumer concurrent queue written in C++11. It's battle hardened and used daily in production: In the Frost

Erik Rigtorp 719 Jun 19, 2022
stdgpu: Efficient STL-like Data Structures on the GPU

stdgpu: Efficient STL-like Data Structures on the GPU Features | Examples | Documentation | Building | Integration | Contributing | License | Contact

Patrick Stotko 705 Jun 27, 2022
An optimized C library for math, parallel processing and data movement

PAL: The Parallel Architectures Library The Parallel Architectures Library (PAL) is a compact C library with optimized routines for math, synchronizat

Parallella 295 Jun 10, 2022
Bolt is a C++ template library optimized for GPUs. Bolt provides high-performance library implementations for common algorithms such as scan, reduce, transform, and sort.

Bolt is a C++ template library optimized for heterogeneous computing. Bolt is designed to provide high-performance library implementations for common

null 356 Jun 17, 2022
oneAPI DPC++ Library (oneDPL) https://software.intel.com/content/www/us/en/develop/tools/oneapi/components/dpc-library.html

oneAPI DPC++ Library (oneDPL) The oneAPI DPC++ Library (oneDPL) aims to work with the oneAPI DPC++ Compiler to provide high-productivity APIs to devel

oneAPI-SRC 624 Jun 21, 2022
ArrayFire: a general purpose GPU library.

ArrayFire is a general-purpose library that simplifies the process of developing software that targets parallel and massively-parallel architectures i

ArrayFire 3.8k Jun 20, 2022
A C++ GPU Computing Library for OpenCL

Boost.Compute Boost.Compute is a GPU/parallel-computing library for C++ based on OpenCL. The core library is a thin C++ wrapper over the OpenCL API an

Boost.org 1.3k Jun 22, 2022
C++React: A reactive programming library for C++11.

C++React is reactive programming library for C++14. It enables the declarative definition of data dependencies between state and event flows. Based on

Sebastian 952 Jun 19, 2022
A library for enabling task-based multi-threading. It allows execution of task graphs with arbitrary dependencies.

Fiber Tasking Lib This is a library for enabling task-based multi-threading. It allows execution of task graphs with arbitrary dependencies. Dependenc

RichieSams 768 Jun 25, 2022
The C++ Standard Library for Parallelism and Concurrency

Documentation: latest, development (master) HPX HPX is a C++ Standard Library for Concurrency and Parallelism. It implements all of the corresponding

The STE||AR Group 1.9k Jun 23, 2022
OpenCL based GPU accelerated SPH fluid simulation library

libclsph An OpenCL based GPU accelerated SPH fluid simulation library Can I see it in action? Demo #1 Demo #2 Why? Libclsph was created to explore the

null 46 Jun 15, 2022
A header-only C++ library for task concurrency

transwarp Doxygen documentation transwarp is a header-only C++ library for task concurrency. It allows you to easily create a graph of tasks where eve

Christian Blume 570 Jun 24, 2022
VexCL is a C++ vector expression template library for OpenCL/CUDA/OpenMP

VexCL VexCL is a vector expression template library for OpenCL/CUDA. It has been created for ease of GPGPU development with C++. VexCL strives to redu

Denis Demidov 671 May 25, 2022
Simple and fast C library implementing a thread-safe API to manage hash-tables, linked lists, lock-free ring buffers and queues

libhl C library implementing a set of APIs to efficiently manage some basic data structures such as : hashtables, linked lists, queues, trees, ringbuf

Andrea Guzzo 381 Jun 15, 2022