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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
use {
crate::unsync::{EntryData, WeakList, WeakListElement},
alloc::rc::{Rc, Weak},
core::{
cell::UnsafeCell,
fmt::{Debug, Formatter},
mem,
},
};
impl<T> WeakListElement<T>
where
T: ?Sized,
{
/// Creates a new list element.
///
/// This object holds a weak reference to the `T`. When this object is dropped, it
/// automatically detaches itself from the list it is currently attached to.
///
/// Often, this object is directly contained in the `T`:
///
/// ```rust
/// use std::rc::Rc;
/// use weak_lists::WeakListElement;
///
/// struct Client {
/// element: WeakListElement<Client>,
/// }
///
/// let client = Rc::new_cyclic(|slf| Client {
/// element: WeakListElement::new(slf.clone()),
/// });
/// ```
///
/// Since only weak references are stored, this does not create any actual reference
/// cycles.
pub fn new(t: Weak<T>) -> Self {
Self {
t,
data: UnsafeCell::new(EntryData {
id: 0,
owner: Default::default(),
}),
}
}
/// Attaches the list element to a list.
///
/// If this object was previously attached to a list, it is automatically detached
/// from that list.
///
/// The list will only hold on a weak reference to this element and vice versa.
///
/// Any existing iterator over the list might or might not see this element, this is
/// unspecified.
///
/// # Examples
///
/// ```rust
/// use std::rc::Rc;
/// use weak_lists::{WeakList, WeakListElement};
///
/// struct Client {
/// element: WeakListElement<Client>,
/// }
///
/// let clients1 = WeakList::default();
///
/// let client = Rc::new_cyclic(|slf| Client {
/// element: WeakListElement::new(slf.clone()),
/// });
///
/// client.element.attach(&clients1);
///
/// assert!(clients1.iter().next().is_some());
///
/// let clients2 = WeakList::default();
///
/// client.element.attach(&clients2);
///
/// assert!(clients1.iter().next().is_none());
/// assert!(clients2.iter().next().is_some());
/// ```
pub fn attach(&self, to: &WeakList<T>) {
self.detach();
let data = unsafe {
// SAFETY:
// - While we hold this reference, we do not call any functions that might
// create additional references to self.data. This applies to all code that
// creates references to self.data.
// - Therefore, this is an exclusive reference to self.data.
// - In particular, the clone call below clones an Rc and is therefore safe.
// - The insert call only adds an element to a map and is therefore safe.
// - list_data.next_id cannot overflow, therefore the insert call returns none
// and no drop code runs. But even if it did run, it would run after all
// uses of the mutable references have concluded.
&mut *self.data.get()
};
data.owner = Rc::downgrade(&to.data);
let list_data = unsafe {
// SAFETY: See the previous safety comment.
&mut *to.data.get()
};
data.id = list_data.next_id;
list_data.next_id += 1;
list_data.members.insert(data.id, self.t.clone());
}
/// Detaches the element from its current list.
///
/// # Examples
///
/// ```rust
/// use std::rc::Rc;
/// use weak_lists::{WeakList, WeakListElement};
///
/// struct Client {
/// element: WeakListElement<Client>,
/// }
///
/// let clients = WeakList::default();
///
/// let client = Rc::new_cyclic(|slf| Client {
/// element: WeakListElement::new(slf.clone()),
/// });
///
/// client.element.attach(&clients);
///
/// assert!(clients.iter().next().is_some());
///
/// client.element.detach();
///
/// assert!(clients.iter().next().is_none());
/// ```
pub fn detach(&self) {
let data = unsafe {
// SAFETY:
// - While we hold this reference, we do not call any functions that might
// create additional references to self.data. This applies to all code that
// creates references to self.data.
// - Therefore, this is an exclusive reference to self.data.
// - All drop code below runs after the last use of the references has
// concluded. However, even if it did run, it could be shown that that code
// is harmless and does not run any code that depends on T.
&mut *self.data.get()
};
let prev = mem::take(&mut data.owner).upgrade();
if let Some(prev) = prev {
let list_data = unsafe {
// SAFETY: See the previous safety comment.
&mut *prev.get()
};
list_data.members.remove(&data.id);
}
}
}
impl<T> Drop for WeakListElement<T>
where
T: ?Sized,
{
fn drop(&mut self) {
self.detach();
}
}
impl<T> Debug for WeakListElement<T>
where
T: ?Sized,
{
fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
let data = unsafe {
// SAFETY:
// - While we hold this reference, we do not call any functions that might
// create additional references to self.data. This applies to all code that
// creates references to self.data.
// - Therefore, this is an exclusive reference to self.data.
&mut *self.data.get()
};
let owner = data.owner.upgrade();
let owner_id = owner.as_ref().map(Rc::as_ptr);
f.debug_struct("WeakListElement")
.field("list", &owner_id)
.finish_non_exhaustive()
}
}