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//! ```
cactusref/doc/implementing_self_referential_data_structures.rs

cactusref/doc/
implementing_self_referential_data_structures.rs
