• Stars
    star
    143
  • Rank 257,007 (Top 6 %)
  • Language
    Rust
  • License
    MIT License
  • Created over 5 years ago
  • Updated 30 days ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

🌵 Cycle-Aware Reference Counting in Rust

CactusRef

GitHub Actions Discord Twitter
Crate API API trunk

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

More Repositories

1

artichoke

💎 Artichoke is a Ruby made with Rust
Rust
3,041
star
2

ferrocarril

🚆 Experiments to embed Ruby on Rails in Rust with mruby
Rust
62
star
3

playground

🎡 Artichoke Ruby Wasm Playground
Rust
43
star
4

jasper

🧳 Single-binary packaging for Ruby applications that supports native and Wasm targets
34
star
5

intaglio

🗃 UTF-8 string, byte string, and C string interner
Rust
26
star
6

boba

💦 Rust implementation of the Bubble Babble binary data encoding
Rust
13
star
7

rand_mt

🌪 Mersenne Twister implementation backed by rand_core
Rust
12
star
8

strftime-ruby

⏳ Ruby `Time#strftime` parser and formatter
Rust
12
star
9

roe

🍣 Unicode case converters
Rust
9
star
10

nightly

🌌 Nightly builds of Artichoke Ruby
Python
9
star
11

focaccia

🍞 no_std Unicode case folding comparisons
Rust
9
star
12

www.artichokeruby.org

🌐 Artichoke Ruby project website
HTML
7
star
13

raw-parts

🪣 Types for a `Vec`'s raw parts
Rust
6
star
14

strudel

🥐 🥮 Rust port and drop-in replacement for the `st_hash` C hash table library
Rust
5
star
15

clang-format

✏️ clang-format runner for CI
JavaScript
5
star
16

qed

∎ Compile-time assertion macros
Rust
5
star
17

posix-space

🔭 Determine if a byte is a space in the POSIX locale
Rust
5
star
18

project-infrastructure

🛠 Infrastructure as code for the Artichoke open source project
HCL
5
star
19

docker-artichoke-nightly

🐳 Docker builds for nightly Artichoke
Dockerfile
5
star
20

artichoke.github.io

⏭ Redirect to Artichoke project website
JavaScript
4
star
21

spec-state

💎📈 Records historical ruby/spec compliance for Artichoke
4
star
22

generate_third_party

📜 Generate listings of third party licenses for Artichoke Ruby
Ruby
4
star
23

ruby-file-expand-path

📂 Rust port of path normalization from MRI Ruby.
Ruby
4
star
24

setup-rust

⛓ GitHub Actions for setting up Rust toolchains
Ruby
4
star
25

sysdir-rs

🍎 📁 Rust bindings to `sysdir` API on Apple platforms
Rust
3
star
26

known-folders-rs

🪟 📁 Rust bindings to the Known Folders API on Windows
Rust
2
star
27

logo

🖼 Project logos for Artichoke Ruby
PostScript
2
star
28

rubyconf

📽 RubyConf presentations
HTML
2
star
29

artichoke-ci

🏗 CI infrastructure and images for Artichoke
Shell
1
star
30

rubyconf2019.artichoke.run

📸 A snapshot of artichoke.run that runs the playground as of RubyConf 2019
JavaScript
1
star