A collection of high performance containers and utilities for concurrent and asynchronous programming.
features = ["serde"].HashMap is a concurrent hash map, optimized for highly parallel write-heavy workloads. HashMap is structured as a lock-free stack of entry bucket arrays. The entry bucket array is managed by EBR, thus enabling lock-free access to it and non-blocking container resizing. Each bucket is a fixed-size array of entries, and it is protected by a special read-write lock which provides both blocking and asynchronous methods.
Read/write access to an entry is serialized by the read-write lock in the bucket containing the entry. There are no container-level locks, therefore, the larger the container gets, the lower the chance of the bucket-level lock being contended.
Resizing of a HashMap is completely non-blocking and lock-free; resizing does not block any other read/write access to the container or resizing attempts. Resizing is analogous to pushing a new bucket array into a lock-free stack. Each entry in the old bucket array will be incrementally relocated to the new bucket array on future access to the container, and the old bucket array gets dropped eventually after it becomes empty.
An entry can be inserted if the key is unique. The inserted entry can be updated, read, and removed synchronously or asynchronously.
```rust use scc::HashMap;
let hashmap: HashMap
assert!(hashmap.insert(1, 0).isok()); asserteq!(hashmap.update(&1, |, v| { *v = 2; *v }).unwrap(), 2); asserteq!(hashmap.read(&1, |, v| *v).unwrap(), 2); asserteq!(hashmap.remove(&1).unwrap(), (1, 2));
hashmap.entry(7).orinsert(17); asserteq!(hashmap.read(&7, |_, v| *v).unwrap(), 17);
let futureinsert = hashmap.insertasync(2, 1); let futureremove = hashmap.removeasync(&1); ```
The Entry API of HashMap is useful if the workflow is complicated.
```rust use scc::HashMap;
let hashmap: HashMap
hashmap.entry(3).orinsert(7); asserteq!(hashmap.read(&3, |_, v| *v), Some(7));
hashmap.entry(4).andmodify(|v| { *v += 1 }).orinsert(5); asserteq!(hashmap.read(&4, |, v| *v), Some(5));
let futureentry = hashmap.entryasync(3); ```
HashMap does not provide an Iterator since it is impossible to confine the lifetime of Iterator::Item to the Iterator. The limitation can be circumvented by relying on interior mutability, e.g., let the returned reference hold a lock, however it will easily lead to a deadlock if not correctly used, and frequent acquisition of locks may impact performance. Therefore, Iterator is not implemented, instead, HashMap provides a number of methods to iterate over entries synchronously or asynchronously: any, any_async, prune, prune_async, retain, retain_async, scan, scan_async, OccupiedEntry::next, and OccupiedEntry::next_async.
```rust use scc::HashMap;
let hashmap: HashMap
assert!(hashmap.insert(1, 0).isok()); assert!(hashmap.insert(2, 1).isok());
// Entries can be modified or removed via retain.
let mut acc = 0;
hashmap.retain(|k, vmut| { acc += *k; *vmut = 2; true });
asserteq!(acc, 3);
asserteq!(hashmap.read(&1, |, v| *v).unwrap(), 2);
asserteq!(hashmap.read(&2, |_, v| *v).unwrap(), 2);
// any returns true as soon as an entry satisfying the predicate is found.
assert!(hashmap.insert(3, 2).is_ok());
assert!(hashmap.any(|k, _| *k == 3));
// Multiple entries can be removed through retain.
hashmap.retain(|k, v| *k == 1 && *v == 2);
// hash_map::OccupiedEntry also can return the next closest occupied entry.
let firstentry = hashmap.firstentry();
assert!(firstentry.issome());
let secondentry = firstentry.andthen(|e| e.next());
assert!(secondentry.is_none());
// Asynchronous iteration over entries using scan_async.
let futurescan = hashmap.scanasync(|k, v| println!("{k} {v}"));
```
HashSet is a special version of HashMap where the value type is ().
Most HashSet methods are identical to that of HashMap except that they do not receive a value argument, and some HashMap methods for value modification are not implemented for HashSet.
```rust use scc::HashSet;
let hashset: HashSet
assert!(hashset.read(&1, || true).isnone()); assert!(hashset.insert(1).isok()); assert!(hashset.read(&1, || true).unwrap());
let futureinsert = hashset.insertasync(2); let futureremove = hashset.removeasync(&1); ```
HashIndex is a read-optimized version of HashMap. In a HashIndex, not only is the memory of the bucket array managed by EBR, but also that of entry buckets is protected by EBR, enabling lock-free read access to individual entries.
The peek and peek_with methods are completely lock-free.
```rust use scc::HashIndex;
let hashindex: HashIndex
assert!(hashindex.insert(1, 0).is_ok());
// peek and peek_with are lock-free.
asserteq!(hashindex.peekwith(&1, |_, v| *v).unwrap(), 0);
let futureinsert = hashindex.insertasync(2, 1); let futureremove = hashindex.removeifasync(&1, || true); ```
The Entry API of HashIndex can be used to update an entry in-place.
```rust use scc::HashIndex;
let hashindex: HashIndex
if let Some(mut o) = hashindex.get(&1) { // Create a new version of the entry. o.update(2); };
if let Some(mut o) = hashindex.get(&1) { // Update the entry in-place. unsafe { *o.get_mut() = 3; } }; ```
An Iterator is implemented for HashIndex, because any derived references can survive as long as the associated ebr::Guard lives.
```rust use scc::ebr::Guard; use scc::HashIndex;
let hashindex: HashIndex
assert!(hashindex.insert(1, 0).is_ok());
// Existing values can be replaced with a new one. hashindex.get(&1).unwrap().update(1);
let guard = Guard::new();
// An ebr::Guard has to be supplied to iter.
let mut iter = hashindex.iter(&guard);
// The derived reference can live as long as guard.
let entryref = iter.next().unwrap();
asserteq!(iter.next(), None);
drop(hashindex);
// The entry can be read after hashindex is dropped.
asserteq!(entryref, (&1, &1));
```
HashCache is a concurrent sampling-based LRU cache that is based on the HashMap implementation. HashCache does not keep track of the least recently used entry in the entire cache, instead each bucket maintains a doubly linked list of occupied entries which is updated on access to entries in order to keep track of the least recently used entry within the bucket.
The LRU entry in a bucket is evicted when a new entry is being inserted and the bucket is full.
```rust use scc::HashCache;
let hashcache: HashCache
/// The capacity cannot exceed the maximum capacity. asserteq!(hashcache.capacityrange(), 128..=2048);
/// If the bucket corresponding to 1 or 2 is full, the LRU entry will be evicted.
assert!(hashcache.put(1, 0).isok());
assert!(hashcache.put(2, 0).isok());
/// 1 becomes the most recently accessed entry in the bucket.
assert!(hashcache.get(&1).is_some());
/// An entry can be normally removed. assert_eq!(hashcache.remove(&2).unwrap(), (2, 0)); ```
TreeIndex is a B-plus tree variant optimized for read operations. EBR protects the memory used by individual entries, thus enabling lock-free read access to them.
Read access is always lock-free and non-blocking. Write access to an entry is also lock-free and non-blocking as long as no structural changes are required. However, when nodes are being split or merged by a write operation, other write operations on keys in the affected range are blocked.
An entry can be inserted if the key is unique, and it can be read, and removed afterwards. Locks are acquired or awaited only when internal nodes are split or merged.
```rust use scc::TreeIndex;
let treeindex: TreeIndex
assert!(treeindex.insert(1, 2).is_ok());
// peek and peek_with are lock-free.
asserteq!(treeindex.peekwith(&1, |_, v| *v).unwrap(), 2);
assert!(treeindex.remove(&1));
let futureinsert = treeindex.insertasync(2, 3); let futureremove = treeindex.removeif_async(&1, |v| *v == 2); ```
Entries can be scanned without acquiring any locks.
```rust use scc::ebr::Guard; use scc::TreeIndex;
let treeindex: TreeIndex
assert!(treeindex.insert(1, 10).isok()); assert!(treeindex.insert(2, 11).isok()); assert!(treeindex.insert(3, 13).is_ok());
let guard = Guard::new();
// visitor iterates over entries without acquiring a lock.
let mut visitor = treeindex.iter(&guard);
asserteq!(visitor.next().unwrap(), (&1, &10));
asserteq!(visitor.next().unwrap(), (&2, &11));
asserteq!(visitor.next().unwrap(), (&3, &13));
assert!(visitor.next().isnone());
```
A specific range of keys can be scanned.
```rust use scc::ebr::Guard; use scc::TreeIndex;
let treeindex: TreeIndex
for i in 0..10 { assert!(treeindex.insert(i, 10).is_ok()); }
let guard = Guard::new();
asserteq!(treeindex.range(1..1, &guard).count(), 0); asserteq!(treeindex.range(4..8, &guard).count(), 4); assert_eq!(treeindex.range(4..=8, &guard).count(), 5); ```
Bag is a concurrent lock-free unordered container. Bag is completely opaque, disallowing access to contained instances until they are popped. Bag is especially efficient if the number of contained instances can be maintained under ARRAY_LEN (default: usize::BITS / 2)
```rust use scc::Bag;
let bag: Bag
bag.push(1); assert!(!bag.isempty()); asserteq!(bag.pop(), Some(1)); assert!(bag.is_empty()); ```
Queue is an EBR backed concurrent lock-free first-in-first-out container.
```rust use scc::Queue;
let queue: Queue
queue.push(1); assert!(queue.pushif(2, |e| e.mapor(false, |x| *x == 1)).is_ok()); assert!(queue.push_if(3, |e| e.map_or(false, |x| *x == 1)).iserr()); asserteq!(queue.pop().map(|e| *e), Some(1)); assert_eq!(queue.pop().map(|e| *e), Some(2)); assert!(queue.pop().is_none()); ```
Stack is an EBR backed concurrent lock-free last-in-first-out container.
```rust use scc::Stack;
let stack: Stack
stack.push(1); stack.push(2); asserteq!(stack.pop().map(|e| **e), Some(2)); asserteq!(stack.pop().map(|e| **e), Some(1)); assert!(stack.pop().is_none()); ```
The ebr module implements epoch-based reclamation and various types of auxiliary data structures to make use of it safely. Its epoch-based reclamation algorithm is similar to that implemented in crossbeam_epoch, however users may find it easier to use as the lifetime of an instance is safely managed. For instance, ebr::AtomicOwned and ebr::Owned automatically retire the contained instance and ebr::AtomicShared and ebr::Shared hold a reference-counted instance which is retired when the last strong reference is dropped.
Retired instances are stored in intrusive queues in thread-local storage, and therefore additional 16-byte space for Option<NonNull<dyn Collectible>> is allocated per instance.
The ebr module can be used without an unsafe block.
```rust use scc::ebr::{suspend, AtomicOwned, AtomicShared, Guard, Ptr, Shared, Tag};
use std::sync::atomic::Ordering::Relaxed;
// atomic_shared holds a strong reference to 17.
let atomic_shared: AtomicShared
// atomic_owned owns 19.
let atomic_owned: AtomicOwned
// guard prevents the garbage collector from dropping reachable instances.
let guard = Guard::new();
// ptr cannot outlive guard.
let mut ptr: Ptr
// atomic_shared can be tagged.
atomicshared.updatetag_if(Tag::First, |p| p.tag() == Tag::None, Relaxed, Relaxed);
// ptr is not tagged, so CAS fails.
assert!(atomicshared.compareexchange(
ptr,
(Some(Shared::new(18)), Tag::First),
Relaxed,
Relaxed,
&guard).is_err());
// ptr can be tagged.
ptr.set_tag(Tag::First);
// The return value of CAS is a handle to the instance that atomic_shared previously owned.
let prev: Shared
// 17 will be garbage-collected later.
drop(prev);
// ebr::AtomicShared can be converted into ebr::Shared.
let shared: Shared
// 18 and 19 will be garbage-collected later.
drop(shared);
drop(atomic_owned);
// 17 is still valid as guard keeps the garbage collector from dropping it.
asserteq!(*ptr.asref().unwrap(), 17);
// Execution of a closure can be deferred until all the current readers are gone. guard.defer_execute(|| println!("deferred")); drop(guard);
// If the thread is expected to lie dormant for a while, call suspend() to allow other threads
// to reclaim its own retired instances.
suspend();
```
LinkedList is a type trait that implements lock-free concurrent singly linked list operations, backed by EBR. It additionally provides a method for marking an entry of a linked list to denote a user-defined state.
```rust use scc::ebr::{AtomicShared, Guard, Shared}; use scc::LinkedList;
use std::sync::atomic::Ordering::Relaxed;
struct L(AtomicShared
let guard = Guard::new();
let head: L = L::default();
let tail: Shared
// A new entry is pushed. assert!(head.pushback(tail.clone(), false, Relaxed, &guard).isok()); assert!(!head.is_marked(Relaxed));
// Users can mark a flag on an entry. head.mark(Relaxed); assert!(head.is_marked(Relaxed));
// next_ptr traverses the linked list.
let nextptr = head.nextptr(Relaxed, &guard);
asserteq!(nextptr.as_ref().unwrap().1, 1);
// Once tail is deleted, it becomes invisible.
tail.deleteself(Relaxed);
assert!(head.nextptr(Relaxed, &guard).is_null());
```
Comparison with DashMap.