Single-threaded, cycle-aware, reference-counting pointers. ‘Rc’ stands for ‘Reference Counted’.
Rc<T> provides shared ownership of a value of type
allocated in the heap. Invoking
Rc produces a new pointer
to the same value in the heap. When the last externally reachable
pointer to a given value is destroyed, the pointed-to value is also
Rc can detect and deallocate cycles of
Rcs through the use of
Adopt. Cycle detection is opt-in and no reachability checks are
performed unless graphs have adoptions.
CactusRef depends on several unstable Rust features and can only be built on a nightly toolchain.
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.
Rc in CactusRef is derived from
std::rc::Rc and CactusRef
implements most of the API from
CactusRef does not implement the following APIs that are present on
CactusRef cannot be used with unsized types like
If you do not depend on these APIs, CactusRef is a drop-in replacement for
CactusRef smart pointers can be used to implement a tracing garbage
collector local to a graph objects. Graphs of CactusRefs are cycle-aware and
can deallocate a cycle of strong references that is otherwise unreachable
from the rest of the object graph, unlike
CactusRef relies on proper use of
to maintain bookkeeping about the object graph for breaking cycles. These
functions are unsafe because improperly managing the bookkeeping can cause
Rc drop implementation to deallocate cycles while they are still
externally reachable. Failure to uphold
Adopt’s safety invariants will
result in undefined behavior and held
Rcs that point to members of the
now deallocated cycle may dangle.
CactusRef makes a best-effort attempt to abort the program if it detects an
access to a dangling
Adopt to log bookkeeping entries for strong ownership
links to other
Rcs that may form a cycle. The ownership links tracked by
these bookkeeping entries form an object graph of reachable
Rc uses these entries to conduct a reachability trace of the
object graph to determine if it is part of an orphaned cycle. An orphaned
cycle is a cycle where the only strong references to all nodes in the cycle
come from other nodes in the cycle.
Cycle detection is a zero-cost abstraction. If you never
drop uses the same implementation as
std::rc::Rc (and leaks in the same way as
std::rc::Rc if you form a
cycle of strong references). The only costs you pay are the memory costs of
one empty hash map used to track adoptions and an if statement to check if
these structures are empty on
Cycle detection uses breadth-first search for traversing the object graph. The algorithm supports arbitrarily large object graphs and will not overflow the stack during the reachability trace.
Examples of implementing self-referential data structures with CactusRef.
CactusRef can be used to implement collections that own strong references
A single-threaded reference-counting pointer. ‘Rc’ stands for ‘Reference Counted’.