1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
CDS C++ library
===============
[](http://badge.fury.io/gh/khizmax%2Flibcds)
[](https://github.com/khizmax/libcds/blob/master/LICENSE)
[](https://travis-ci.org/khizmax/libcds)
[](https://ci.appveyor.com/project/khizmax/libcds)
<!---
The coverity dataset is about 4G of size and about 1G in compressed state so it is a problem to upload it to the coverity server
[](https://scan.coverity.com/projects/4445)
-->
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](http://en.wikipedia.org/wiki/Hazard_pointer)
and user-space [RCU](http://en.wikipedia.org/wiki/Read-copy-update) 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](http://en.wikipedia.org/wiki/Non-blocking_algorithm) 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](http://mcg.cs.tau.ac.il/projects/projects/flat-combining) technique
- lock-free [skip-list](http://en.wikipedia.org/wiki/Skip_list)
- lock-free FeldmanHashMap/Set [Multi-Level Array Hash](http://samos-conference.com/Resources_Samos_Websites/Proceedings_Repository_SAMOS/2013/Files/2013-IC-20.pdf)
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
Evolution of libcds (Gource visualization by Landon Wilkins): https://www.youtube.com/watch?v=FHaJvVdmJ0w
**How to build**
- *nix: [use CMake](build/cmake/readme.md)
- 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.**
**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
[](https://www.openhub.net/p/khizmax-libcds)
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](http://people.csail.mit.edu/shanir/publications/Lock_Free.pdf)
- *FCStack* - flat-combining wrapper for *std::stack*
*Queue*
- *BasketQueue*: [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
[pdf](http://people.csail.mit.edu/shanir/publications/Baskets%20Queue.pdf)
- *MSQueue*:
* [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
[pdf](http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf)
* [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes"
[pdf](http://www.research.ibm.com/people/m/michael/podc-2002.pdf)
* [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
[pdf](http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf)
- *RWQueue*: [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
[pdf](http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf)
- *MoirQueue*: [2000] Simon Doherty, Lindsay Groves, Victor Luchangco, Mark Moir "Formal Verification of a practical lock-free queue algorithm"
[pdf](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.87.9954&rep=rep1&type=pdf)
- *OptimisticQueue*: [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
[pdf](https://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf)
- *SegmentedQueue*: [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency"
[pdf](http://mcg.cs.tau.ac.il/papers/opodis2010-quasi.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](http://www.research.ibm.com/people/m/michael/spaa-2002.pdf)
- *SplitOrderedList*: [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
[pdf](http://people.csail.mit.edu/shanir/publications/Split-Ordered_Lists.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](http://samos-conference.com/Resources_Samos_Websites/Proceedings_Repository_SAMOS/2013/Files/2013-IC-20.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](http://people.csail.mit.edu/shanir/publications/Lazy_Concurrent.pdf)
- *MichaelList*: [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
[pdf](http://www.research.ibm.com/people/m/michael/spaa-2002.pdf)
*Priority queue*
- *MSPriorityQueue*: [1996] G.Hunt, M.Michael, S. Parthasarathy, M.Scott "An efficient algorithm for concurrent priority queue heaps"
[pdf](http://web.cse.ohio-state.edu/dmrl/papers/heap96.pdf)
*Tree*
- *EllenBinTree*: [2010] F.Ellen, P.Fatourou, E.Ruppert, F.van Breugel "Non-blocking Binary Search Tree"
[pdf](http://www.cs.vu.nl/~tcs/cm/faith.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](https://ppl.stanford.edu/papers/ppopp207-bronson.pdf)
*SMR*
- Hazard Pointers
* [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes"
[pdf](http://www.research.ibm.com/people/m/michael/podc-2002.pdf)
* [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
[pdf](http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf)
* [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
[pdf](http://www.researchgate.net/profile/Andrei_Alexandrescu/publication/252573326_Lock-Free_Data_Structures_with_Hazard_Pointers/links/0deec529e7804288fe000000.pdf)
- User-space RCU
* [2009] M.Desnoyers "Low-Impact Operating System Tracing" PhD Thesis,
Chapter 6 "User-Level Implementations of Read-Copy Update"
[pdf](http://www.lttng.org/files/thesis/desnoyers-dissertation-2009-12-v27.pdf)
* [2011] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "User-Level
Implementations of Read-Copy Update"
[pdf](http://www.dorsal.polymtl.ca/sites/www.dorsal.polymtl.ca/files/publications/desnoyers-ieee-urcu-submitted.pdf)
*Flat Combining* technique
- [2010] Hendler, Incze, Shavit and Tzafrir "Flat Combining and the Synchronization-Parallelism Tradeoff"
[pdf](http://www.cs.bgu.ac.il/~hendlerd/papers/flat-combining.pdf)
|
