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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
//! Concurrent maps and sets based on [skip lists].
//!
//! This crate provides the types [`SkipMap`] and [`SkipSet`].
//! These data structures provide an interface similar to [`BTreeMap`] and [`BTreeSet`],
//! respectively, except they support safe concurrent access across
//! multiple threads.
//!
//! # Concurrent access
//! [`SkipMap`] and [`SkipSet`] implement [`Send`] and [`Sync`],
//! so they can be shared across threads with ease.
//!
//! Methods which mutate the map, such as [`insert`],
//! take `&self` rather than `&mut self`. This allows
//! them to be invoked concurrently.
//!
//! ```
//! use crossbeam_skiplist::SkipMap;
//! use crossbeam_utils::thread::scope;
//!
//! let person_ages = SkipMap::new();
//!
//! scope(|s| {
//!     // Insert entries into the map from multiple threads.
//!     s.spawn(|_| {
//!         person_ages.insert("Spike Garrett", 22);
//!         person_ages.insert("Stan Hancock", 47);
//!         person_ages.insert("Rea Bryan", 234);
//!
//!         assert_eq!(person_ages.get("Spike Garrett").unwrap().value(), &22);
//!     });
//!     s.spawn(|_| {
//!         person_ages.insert("Bryon Conroy", 65);
//!         person_ages.insert("Lauren Reilly", 2);
//!     });
//! }).unwrap();
//!
//! assert!(person_ages.contains_key("Spike Garrett"));
//! person_ages.remove("Rea Bryan");
//! assert!(!person_ages.contains_key("Rea Bryan"));
//!
//! ```
//!
//! Concurrent access to skip lists is lock-free and sound.
//! Threads won't get blocked waiting for other threads to finish operating
//! on the map.
//!
//! Be warned that, because of this lock-freedom, it's easy to introduce
//! race conditions into your code. For example:
//! ```no_run
//! use crossbeam_skiplist::SkipSet;
//! use crossbeam_utils::thread::scope;
//!
//! let numbers = SkipSet::new();
//! scope(|s| {
//!     // Spawn a thread which will remove 5 from the set.
//!     s.spawn(|_| {
//!         numbers.remove(&5);
//!     });
//!
//!     // While the thread above is running, insert a value into the set.
//!     numbers.insert(5);
//!
//!     // This check can fail!
//!     // The other thread may remove the value
//!     // before we perform this check.
//!     assert!(numbers.contains(&5));
//! }).unwrap();
//! ```
//!
//! In effect, a _single_ operation on the map, such as [`insert`],
//! operates atomically: race conditions are impossible. However,
//! concurrent calls to functions can become interleaved across
//! threads, introducing non-determinism.
//!
//! To avoid this sort of race condition, never assume that a collection's
//! state will remain the same across multiple lines of code. For instance,
//! in the example above, the problem arises from the assumption that
//! the map won't be mutated between the calls to `insert` and `contains`.
//! In sequential code, this would be correct. But when multiple
//! threads are introduced, more care is needed.
//!
//! Note that race conditions do not violate Rust's memory safety rules.
//! A race between multiple threads can never cause memory errors or
//! segfaults. A race condition is a _logic error_ in its entirety.
//!
//! # Mutable access to elements
//! [`SkipMap`] and [`SkipSet`] provide no way to retrieve a mutable reference
//! to a value. Since access methods can be called concurrently, providing
//! e.g. a `get_mut` function could cause data races.
//!
//! A solution to the above is to have the implementation wrap
//! each value in a lock. However, this has some repercussions:
//! * The map would no longer be lock-free, inhibiting scalability
//! and allowing for deadlocks.
//! * If a user of the map doesn't need mutable access, then they pay
//! the price of locks without actually needing them.
//!
//! Instead, the approach taken by this crate gives more control to the user.
//! If mutable access is needed, then you can use interior mutability,
//! such as [`RwLock`]: `SkipMap<Key, RwLock<Value>>`.
//!
//! # Garbage collection
//! A problem faced by many concurrent data structures
//! is choosing when to free unused memory. Care must be
//! taken to prevent use-after-frees and double-frees, both
//! of which cause undefined behavior.
//!
//! Consider the following sequence of events operating on a [`SkipMap`]:
//! * Thread A calls [`get`] and holds a reference to a value in the map.
//! * Thread B removes that key from the map.
//! * Thread A now attempts to access the value.
//!
//! What happens here? If the map implementation frees the memory
//! belonging to a value when it is
//! removed, then a user-after-free occurs, resulting in memory corruption.
//!
//! To solve the above, this crate uses the _epoch-based memory reclamation_ mechanism
//! implemented in [`crossbeam-epoch`]. Simplified, a value removed from the map
//! is not freed until after all references to it have been dropped. This mechanism
//! is similar to the garbage collection found in some languages, such as Java, except
//! it operates solely on the values inside the map.
//!
//! This garbage collection scheme functions automatically; users don't have to worry about it.
//! However, keep in mind that holding [`Entry`] handles to entries in the map will prevent
//! that memory from being freed until at least after the handles are dropped.
//!
//! # Performance versus B-trees
//! In general, when you need concurrent writes
//! to an ordered collection, skip lists are a reasonable choice.
//! However, they can be substantially slower than B-trees
//! in some scenarios.
//!
//! The main benefit of a skip list over a `RwLock<BTreeMap>`
//! is that it allows concurrent writes to progress without
//! mutual exclusion. However, when the frequency
//! of writes is low, this benefit isn't as useful.
//! In these cases, a shared [`BTreeMap`] may be a faster option.
//!
//! These guidelines should be taken with a grain of salt—performance
//! in practice varies depending on your use case.
//! In the end, the best way to choose between [`BTreeMap`] and [`SkipMap`]
//! is to benchmark them in your own application.
//!
//! # Alternatives
//! This crate implements _ordered_ maps and sets, akin to [`BTreeMap`] and [`BTreeSet`].
//! In many situations, however, a defined order on elements is not required. For these
//! purposes, unordered maps will suffice. In addition, unordered maps
//! often have better performance characteristics than their ordered alternatives.
//!
//! Crossbeam [does not currently provide a concurrent unordered map](https://github.com/crossbeam-rs/rfcs/issues/32).
//! That said, here are some other crates which may suit you:
//! * [`DashMap`](https://docs.rs/dashmap) implements a novel concurrent hash map
//! with good performance characteristics.
//! * [`flurry`](https://docs.rs/flurry) is a Rust port of Java's `ConcurrentHashMap`.
//!
//! [`insert`]: SkipMap::insert
//! [`get`]: SkipMap::get
//! [`Entry`]: map::Entry
//! [skip lists]: https://en.wikipedia.org/wiki/Skip_list
//! [`crossbeam-epoch`]: https://docs.rs/crossbeam-epoch
//! [`BTreeMap`]: std::collections::BTreeMap
//! [`BTreeSet`]: std::collections::BTreeSet
//! [`RwLock`]: std::sync::RwLock
//!
//! # Examples
//! [`SkipMap`] basic usage:
//! ```
//! use crossbeam_skiplist::SkipMap;
//!
//! // Note that the variable doesn't have to be mutable:
//! // SkipMap methods take &self to support concurrent access.
//! let movie_reviews = SkipMap::new();
//!
//! // Insert some key-value pairs.
//! movie_reviews.insert("Office Space",       "Deals with real issues in the workplace.");
//! movie_reviews.insert("Pulp Fiction",       "Masterpiece.");
//! movie_reviews.insert("The Godfather",      "Very enjoyable.");
//! movie_reviews.insert("The Blues Brothers", "Eye lyked it a lot.");
//!
//! // Get the value associated with a key.
//! // get() returns an Entry, which gives
//! // references to the key and value.
//! let pulp_fiction = movie_reviews.get("Pulp Fiction").unwrap();
//! assert_eq!(*pulp_fiction.key(), "Pulp Fiction");
//! assert_eq!(*pulp_fiction.value(), "Masterpiece.");
//!
//! // Remove a key-value pair.
//! movie_reviews.remove("The Blues Brothers");
//! assert!(movie_reviews.get("The Blues Brothers").is_none());
//!
//! // Iterate over the reviews. Since SkipMap
//! // is an ordered map, the iterator will yield
//! // keys in lexicographical order.
//! for entry in &movie_reviews {
//!     let movie = entry.key();
//!     let review = entry.value();
//!     println!("{}: \"{}\"", movie, review);
//! }
//! ```
//!
//! [`SkipSet`] basic usage:
//! ```
//! use crossbeam_skiplist::SkipSet;
//!
//! let books = SkipSet::new();
//!
//! // Add some books to the set.
//! books.insert("A Dance With Dragons");
//! books.insert("To Kill a Mockingbird");
//! books.insert("The Odyssey");
//! books.insert("The Great Gatsby");
//!
//! // Check for a specific one.
//! if !books.contains("The Winds of Winter") {
//!    println!("We have {} books, but The Winds of Winter ain't one.",
//!             books.len());
//! }
//!
//! // Remove a book from the set.
//! books.remove("To Kill a Mockingbird");
//! assert!(!books.contains("To Kill a Mockingbird"));
//!
//! // Iterate over the books in the set.
//! // Values are returned in lexicographical order.
//! for entry in &books {
//!     let book = entry.value();
//!     println!("{}", book);
//! }
//! ```

#![doc(test(
    no_crate_inject,
    attr(
        deny(warnings, rust_2018_idioms),
        allow(dead_code, unused_assignments, unused_variables)
    )
))]
#![warn(
    missing_docs,
    missing_debug_implementations,
    rust_2018_idioms,
    unreachable_pub
)]
#![cfg_attr(not(feature = "std"), no_std)]

use cfg_if::cfg_if;

#[cfg(not(crossbeam_no_atomic_cas))]
cfg_if! {
    if #[cfg(feature = "alloc")] {
        extern crate alloc;

        use crossbeam_epoch as epoch;
        use crossbeam_utils as utils;

        pub mod base;
        #[doc(inline)]
        pub use crate::base::SkipList;
    }
}

cfg_if! {
    if #[cfg(feature = "std")] {
        pub mod map;
        #[doc(inline)]
        pub use crate::map::SkipMap;

        pub mod set;
        #[doc(inline)]
        pub use crate::set::SkipSet;
    }
}