CactusRef
Single-threaded, cycle-aware, reference-counting pointers. 'Rc' stands for 'Reference Counted'.
What if, hear me out, we put a hash map in a smart pointer?
CactusRef is a single-threaded, reference-counted smart pointer that can
deallocate cycles without having to resort to weak pointers. Rc
from
std
can be difficult to work with because creating a cycle of Rc
s will
result in a memory leak.
CactusRef is a near drop-in replacement for std::rc::Rc
which introduces
additional APIs for bookkeeping ownership relationships in a graph of Rc
s.
Combining CactusRef's adoption APIs for tracking links in the object graph and driving garbage collection with Rust's drop glue implements a kind of tracing garbage collector. Graphs of CactusRefs detect cycles local to the graph of connected CactusRefs and do not need to scan the whole heap as is typically required in a tracing garbage collector.
Cycles of CactusRefs are deterministically collected and deallocated when they are no longer reachable from outside of the cycle.
Self-referential Data Structures
CactusRef can be used to implement self-referential data structures such as a doubly-linked list without using weak references.
Usage
Add this to your Cargo.toml
:
[dependencies]
cactusref = "0.3.0"
CactusRef is mostly a drop-in replacement for std::rc::Rc
, which can be used
like:
use cactusref::Rc;
let node = Rc::new(123_i32);
let another = Rc::clone(&node);
assert_eq!(Rc::strong_count(&another), 2);
let weak = Rc::downgrade(&node);
assert!(weak.upgrade().is_some());
Or start making self-referential data structures like:
use std::cell::RefCell;
use cactusref::{Adopt, Rc};
struct Node {
next: Option<Rc<RefCell<Node>>>,
data: i32,
}
let left = Node { next: None, data: 123 };
let left = Rc::new(RefCell::new(left));
let right = Node { next: Some(Rc::clone(&left)), data: 456 };
let right = Rc::new(RefCell::new(right));
unsafe {
// bookkeep that `right` has added an owning ref to `left`.
Rc::adopt_unchecked(&right, &left);
}
left.borrow_mut().next = Some(Rc::clone(&right));
unsafe {
// bookkeep that `left` has added an owning ref to `right`.
Rc::adopt_unchecked(&left, &right);
}
let mut node = Rc::clone(&left);
// this loop will print:
//
// > traversing ring and found node with data = 123
// > traversing ring and found node with data = 456
// > traversing ring and found node with data = 123
// > traversing ring and found node with data = 456
// > traversing ring and found node with data = 123
for _ in 0..5 {
println!("traversing ring and found node with data = {}", node.borrow().data);
let next = if let Some(ref next) = node.borrow().next {
Rc::clone(next)
} else {
break;
};
node = next;
}
assert_eq!(Rc::strong_count(&node), 3);
drop(node);
drop(left);
drop(right);
// All members of the ring are garbage collected and deallocated.
Maturity
CactusRef is experimental. This crate has several limitations:
- CactusRef is nightly only.
- Cycle detection requires unsafe code to use.
CactusRef is a non-trivial extension to std::rc::Rc
and has not been proven to
be safe. Although CactusRef makes a best effort to abort the program if it
detects a dangling Rc
, this crate may be unsound.
no_std
CactusRef is no_std
compatible with an optional and enabled by default
dependency on std
. CactusRef depends on the alloc
crate.
Crate features
All features are enabled by default.
- std - Enable linking to the Rust Standard Library. Enabling this feature
adds
Error
implementations to error types in this crate.
License
CactusRef is licensed with the MIT License (c) Ryan Lopopolo.
CactusRef is derived from Rc
in the Rust standard library @
f586d79d
which is dual licensed with the MIT
License and Apache 2.0 License.