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 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.

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.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.

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.