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

//! Concurrent collections.
//!
//! This crate offers several collections that are designed for performance in multithreaded
//! contexts. They can be freely shared among multiple threads running in parallel, and
//! concurrently modified without the overhead of locking.
//!
//! <!--
//! Some of these data structures are lock-free. Others are not strictly speaking lock-free, but
//! still scale well with respect to the number of threads accessing them.
//! -->
//!
//! # Collections
//!
//! The following collections are available:
//!
//! * [`Stack`]: A lock-free stack.
//! * [`deque`]: A lock-free work-stealing deque.
//!
//! # Which collection should you use?
//!
//! ### Use a [`Stack`] when:
//!
//! * You want a simple shared collection where objects can be insert and removed.
//! * You want to avoid performance degradation due to locking.
//! * You want the last-in first-out order of elements.
//!
//! ### Use a [`deque`] when:
//!
//! * You want one thread inserting and removing objects, and multiple threads just removing them.
//! * You don't care about the order of elements.
//!
//! # Garbage collection
//!
//! An interesting problem concurrent collections deal with comes from the remove operation.
//! Suppose that a thread removes an element from a lock-free map, while another thread is reading
//! that same element at the same time. The first thread must wait until the second thread stops
//! reading the element. Only then it is safe to destruct it.
//!
//! Programming languages that come with garbage collectors solve this problem trivially. The
//! garbage collector will destruct the removed element when no thread can hold a reference to it
//! anymore.
//!
//! This crate implements a basic garbage collection mechanism, which is based on epochs (see the
//! `epoch` module). When an element gets removed from a concurrent collection, it is inserted into
//! a pile of garbage and marked with the current epoch. Every time a thread accesses a collection,
//! it checks the current epoch, attempts to increment it, and destructs some garbage that became
//! so old that no thread can be referencing it anymore.
//!
//! That is the general mechanism behind garbage collection, but the details are a bit more
//! complicated. Anyhow, garbage collection is designed to be fully automatic and something users
//! of concurrent collections don't have to worry about.
//!
//! [`Stack`]: stack/struct.Stack.html
//! [`deque`]: deque/fn.new.html

#![cfg_attr(feature = "nightly", feature(const_fn))]

extern crate either;

#[macro_use(defer)]
extern crate scopeguard;

pub mod deque;
pub mod epoch;
pub mod stack;

pub use stack::Stack;