ProductPromotion
Logo

C++ Programming

made by https://0x3d.site

GitHub - khizmax/libcds: A C++ library of Concurrent Data Structures
A C++ library of Concurrent Data Structures. Contribute to khizmax/libcds development by creating an account on GitHub.
Visit Site

GitHub - khizmax/libcds: A C++ library of Concurrent Data Structures

GitHub - khizmax/libcds: A C++ library of Concurrent Data Structures

!!! STOP WAR !!!

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

More Resources
to explore the angular.

mail [email protected] to add your project or resources here 🔥.

Related Articles
to learn about angular.

FAQ's
to learn more about Angular JS.

mail [email protected] to add more queries here 🔍.

More Sites
to check out once you're finished browsing here.

0x3d
https://www.0x3d.site/
0x3d is designed for aggregating information.
NodeJS
https://nodejs.0x3d.site/
NodeJS Online Directory
Cross Platform
https://cross-platform.0x3d.site/
Cross Platform Online Directory
Open Source
https://open-source.0x3d.site/
Open Source Online Directory
Analytics
https://analytics.0x3d.site/
Analytics Online Directory
JavaScript
https://javascript.0x3d.site/
JavaScript Online Directory
GoLang
https://golang.0x3d.site/
GoLang Online Directory
Python
https://python.0x3d.site/
Python Online Directory
Swift
https://swift.0x3d.site/
Swift Online Directory
Rust
https://rust.0x3d.site/
Rust Online Directory
Scala
https://scala.0x3d.site/
Scala Online Directory
Ruby
https://ruby.0x3d.site/
Ruby Online Directory
Clojure
https://clojure.0x3d.site/
Clojure Online Directory
Elixir
https://elixir.0x3d.site/
Elixir Online Directory
Elm
https://elm.0x3d.site/
Elm Online Directory
Lua
https://lua.0x3d.site/
Lua Online Directory
C Programming
https://c-programming.0x3d.site/
C Programming Online Directory
C++ Programming
https://cpp-programming.0x3d.site/
C++ Programming Online Directory
R Programming
https://r-programming.0x3d.site/
R Programming Online Directory
Perl
https://perl.0x3d.site/
Perl Online Directory
Java
https://java.0x3d.site/
Java Online Directory
Kotlin
https://kotlin.0x3d.site/
Kotlin Online Directory
PHP
https://php.0x3d.site/
PHP Online Directory
React JS
https://react.0x3d.site/
React JS Online Directory
Angular
https://angular.0x3d.site/
Angular JS Online Directory