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 Rcs 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 Rcs.
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.
CactusRef can be used to implement self-referential data structures such as a doubly-linked list without using weak references.
Add this to your Cargo.toml:
[dependencies]
cactusref = "0.5.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.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.
CactusRef is no_std compatible with an optional and enabled by default
dependency on std. CactusRef depends on the alloc crate.
All features are enabled by default.
- std - Enable linking to the Rust Standard Library. Enabling this feature
adds
Errorimplementations to error types in this crate.
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.
![dependabot[bot] avatar](https://avatars.githubusercontent.com/in/29110?v=4 "dependabot[bot]")
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent