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
//! A crate providing lock-free data structures and a solution for the "ABA
//! problem" related to pointers.
//!
//! The incinerator is the API which tries to solve the "ABA problem" when
//! related to pointer dropping. With incinerator, every thread has a local
//! deletion queue. Dropping a shared consist of first removing the pointer
//! from the shared context, then adding the pointer to the local queue. Then,
//! a global counter is checked. If the counter is zero, then the whole queue
//! is deleted, otherwise, the queue will only be deleted later.
//!
//! This counter is counting how many times the incinerator was asked to
//! "pause". A thread may pause the incinerator to load and use the shared
//! pointer, and this is why it is important to remove the pointer from the
//! shared context before deleting.
//!
//! This crate is under development, and there are plans for some structures.
//! We have:
//! - `[x]` Stack
//! - `[x]` Queue
//! - `[ ]` Deque
//! - `[x]` Map
//! - `[x]` Set
//!
//! # Performance Guide
//! In order to achieve a better time performance with lockfree, it is
//! recommended to avoid global locking things like heap allocation.
/// Provides convenient re-exports.
/// Incinerator API. The purpouse of this module is to solve the "ABA problem"
/// related to pointers while still being lock-free. Incinerator is a garbage
/// deleter which does not necessarilly deletes all garbage at the moment it
/// was added to the queue, i.e. it can be paused while still not-blocking any
/// thread.
///
/// Whenever a thread exits, its garbage queue is dropped.
/// # Example
/// ```rust
/// extern crate lockfree;
///
/// use lockfree::prelude::*;
/// use std::{
/// ptr::{null_mut, NonNull},
/// sync::{
/// atomic::{AtomicPtr, Ordering::*},
/// Arc,
/// },
/// thread,
/// };
///
/// unsafe fn create_ptr<T>(val: T) -> NonNull<T> {
/// NonNull::new_unchecked(Box::into_raw(Box::new(val)))
/// }
///
/// unsafe fn drop_ptr<T>(ptr: NonNull<T>) {
/// Box::from_raw(ptr.as_ptr());
/// }
///
/// let ptr = unsafe { create_ptr(55).as_ptr() };
/// let dummy_state = Arc::new(AtomicPtr::new(ptr));
///
/// let mut threads = Vec::with_capacity(16);
///
/// for i in 0 .. 16 {
/// let state = dummy_state.clone();
/// threads.push(thread::spawn(move || {
/// let ptr = incinerator::pause(|| {
/// let loaded = state.load(SeqCst);
/// let new = if let Some(num) = unsafe { loaded.as_ref() } {
/// i + num
/// } else {
/// i
/// };
/// state.swap(unsafe { create_ptr(new).as_ptr() }, SeqCst)
/// });
///
/// if let Some(nnptr) = NonNull::new(ptr) {
/// // dropping
/// unsafe { incinerator::add(nnptr, drop_ptr) }
/// }
/// }));
/// }
///
/// for thread in threads {
/// thread.join().unwrap();
/// }
///
/// if let Some(ptr) = NonNull::new(dummy_state.load(SeqCst)) {
/// assert!(unsafe { *ptr.as_ref() } <= 15 * 15);
/// unsafe { drop_ptr(ptr) }
/// }
/// ```
/// Atomic abstractions, such an atomic trait and atomic boxes.
/// A lock-free queue.
/// A lock-free stack.
/// A lock-free map.
/// A lock-free set.
/// Provides a doubly atomic reference counter.