cactusref/doc/implementing_self_referential_data_structures.rs
1//! `CactusRef` can be used to implement collections that own strong references
2//! to themselves.
3//!
4//! # Doubly-linked List
5//!
6//! The following implements a doubly-linked list that is fully deallocated once
7//! the `list` binding is dropped.
8//!
9//! ```rust
10//! use std::cell::RefCell;
11//! use std::iter;
12//!
13//! use cactusref::{Adopt, Rc};
14//!
15//! struct Node<T> {
16//! pub prev: Option<Rc<RefCell<Self>>>,
17//! pub next: Option<Rc<RefCell<Self>>>,
18//! pub data: T,
19//! }
20//!
21//! struct List<T> {
22//! pub head: Option<Rc<RefCell<Node<T>>>>,
23//! }
24//!
25//! impl<T> List<T> {
26//! fn pop(&mut self) -> Option<Rc<RefCell<Node<T>>>> {
27//! let head = self.head.take()?;
28//! let tail = head.borrow_mut().prev.take();
29//! let next = head.borrow_mut().next.take();
30//! if let Some(ref tail) = tail {
31//! Rc::unadopt(&head, tail);
32//! Rc::unadopt(tail, &head);
33//!
34//! tail.borrow_mut().next.clone_from(&next);
35//! if let Some(ref next) = next {
36//! unsafe {
37//! Rc::adopt_unchecked(tail, next);
38//! }
39//! }
40//! }
41//! if let Some(ref next) = next {
42//! Rc::unadopt(&head, next);
43//! Rc::unadopt(next, &head);
44//!
45//! next.borrow_mut().prev.clone_from(&tail);
46//! if let Some(ref tail) = tail {
47//! unsafe {
48//! Rc::adopt_unchecked(next, tail);
49//! }
50//! }
51//! }
52//! self.head = next;
53//! Some(head)
54//! }
55//! }
56//!
57//! impl<T> From<Vec<T>> for List<T> {
58//! fn from(list: Vec<T>) -> Self {
59//! let nodes = list
60//! .into_iter()
61//! .map(|data| {
62//! Rc::new(RefCell::new(Node {
63//! prev: None,
64//! next: None,
65//! data,
66//! }))
67//! })
68//! .collect::<Vec<_>>();
69//! for i in 0..nodes.len() - 1 {
70//! let curr = &nodes[i];
71//! let next = &nodes[i + 1];
72//! curr.borrow_mut().next = Some(Rc::clone(next));
73//! next.borrow_mut().prev = Some(Rc::clone(curr));
74//! unsafe {
75//! Rc::adopt_unchecked(curr, next);
76//! Rc::adopt_unchecked(next, curr);
77//! }
78//! }
79//! let tail = &nodes[nodes.len() - 1];
80//! let head = &nodes[0];
81//! tail.borrow_mut().next = Some(Rc::clone(head));
82//! head.borrow_mut().prev = Some(Rc::clone(tail));
83//! unsafe {
84//! Rc::adopt_unchecked(tail, head);
85//! Rc::adopt_unchecked(head, tail);
86//! }
87//!
88//! let head = Rc::clone(head);
89//! Self { head: Some(head) }
90//! }
91//! }
92//!
93//! let list = iter::repeat(())
94//! .map(|_| "a".repeat(1024 * 1024))
95//! .take(10)
96//! .collect::<Vec<_>>();
97//! let mut list = List::from(list);
98//!
99//! let head = list.pop().unwrap();
100//! assert_eq!(Rc::strong_count(&head), 1);
101//! assert!(head.borrow().data.starts_with('a'));
102//!
103//! // The new head of the list is owned three times:
104//! //
105//! // - itself.
106//! // - the `prev` pointer to it from it's next element.
107//! // - the `next` pointer from the list's tail.
108//! assert_eq!(list.head.as_ref().map(Rc::strong_count), Some(3));
109//!
110//! // The popped head is no longer part of the graph and can be safely dropped
111//! // and deallocated.
112//! let weak = Rc::downgrade(&head);
113//! drop(head);
114//! assert!(weak.upgrade().is_none());
115//!
116//! drop(list);
117//! // all memory consumed by the list nodes is reclaimed.
118//! ```