1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118

//! `CactusRef` can be used to implement collections that own strong references
//! to themselves.
//!
//! # Doubly-linked List
//!
//! The following implements a doubly-linked list that is fully deallocated once
//! the `list` binding is dropped.
//!
//! ```rust
//! use std::cell::RefCell;
//! use std::iter;
//!
//! use cactusref::{Adopt, Rc};
//!
//! struct Node<T> {
//!     pub prev: Option<Rc<RefCell<Self>>>,
//!     pub next: Option<Rc<RefCell<Self>>>,
//!     pub data: T,
//! }
//!
//! struct List<T> {
//!     pub head: Option<Rc<RefCell<Node<T>>>>,
//! }
//!
//! impl<T> List<T> {
//!     fn pop(&mut self) -> Option<Rc<RefCell<Node<T>>>> {
//!         let head = self.head.take()?;
//!         let tail = head.borrow_mut().prev.take();
//!         let next = head.borrow_mut().next.take();
//!         if let Some(ref tail) = tail {
//!             Rc::unadopt(&head, tail);
//!             Rc::unadopt(tail, &head);
//!
//!             tail.borrow_mut().next.clone_from(&next);
//!             if let Some(ref next) = next {
//!                 unsafe {
//!                     Rc::adopt_unchecked(tail, next);
//!                 }
//!             }
//!         }
//!         if let Some(ref next) = next {
//!             Rc::unadopt(&head, next);
//!             Rc::unadopt(next, &head);
//!
//!             next.borrow_mut().prev.clone_from(&tail);
//!             if let Some(ref tail) = tail {
//!                 unsafe {
//!                     Rc::adopt_unchecked(next, tail);
//!                 }
//!             }
//!         }
//!         self.head = next;
//!         Some(head)
//!     }
//! }
//!
//! impl<T> From<Vec<T>> for List<T> {
//!     fn from(list: Vec<T>) -> Self {
//!         let nodes = list
//!             .into_iter()
//!             .map(|data| {
//!                 Rc::new(RefCell::new(Node {
//!                     prev: None,
//!                     next: None,
//!                     data,
//!                 }))
//!             })
//!             .collect::<Vec<_>>();
//!         for i in 0..nodes.len() - 1 {
//!             let curr = &nodes[i];
//!             let next = &nodes[i + 1];
//!             curr.borrow_mut().next = Some(Rc::clone(next));
//!             next.borrow_mut().prev = Some(Rc::clone(curr));
//!             unsafe {
//!                 Rc::adopt_unchecked(curr, next);
//!                 Rc::adopt_unchecked(next, curr);
//!             }
//!         }
//!         let tail = &nodes[nodes.len() - 1];
//!         let head = &nodes[0];
//!         tail.borrow_mut().next = Some(Rc::clone(head));
//!         head.borrow_mut().prev = Some(Rc::clone(tail));
//!         unsafe {
//!             Rc::adopt_unchecked(tail, head);
//!             Rc::adopt_unchecked(head, tail);
//!         }
//!
//!         let head = Rc::clone(head);
//!         Self { head: Some(head) }
//!     }
//! }
//!
//! let list = iter::repeat(())
//!     .map(|_| "a".repeat(1024 * 1024))
//!     .take(10)
//!     .collect::<Vec<_>>();
//! let mut list = List::from(list);
//!
//! let head = list.pop().unwrap();
//! assert_eq!(Rc::strong_count(&head), 1);
//! assert!(head.borrow().data.starts_with('a'));
//!
//! // The new head of the list is owned three times:
//! //
//! // - itself.
//! // - the `prev` pointer to it from it's next element.
//! // - the `next` pointer from the list's tail.
//! assert_eq!(list.head.as_ref().map(Rc::strong_count), Some(3));
//!
//! // The popped head is no longer part of the graph and can be safely dropped
//! // and deallocated.
//! let weak = Rc::downgrade(&head);
//! drop(head);
//! assert!(weak.upgrade().is_none());
//!
//! drop(list);
//! // all memory consumed by the list nodes is reclaimed.
//! ```