(index<- ) ./libstd/rc.rs
git branch: * master 5200215 auto merge of #14035 : alexcrichton/rust/experimental, r=huonw
modified: Fri May 9 13:02:28 2014
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 /*! Task-local reference-counted boxes (`Rc` type)
12
13 The `Rc` type provides shared ownership of an immutable value. Destruction is deterministic, and
14 will occur as soon as the last owner is gone. It is marked as non-sendable because it avoids the
15 overhead of atomic reference counting.
16
17 The `downgrade` method can be used to create a non-owning `Weak` pointer to the box. A `Weak`
18 pointer can be upgraded to an `Rc` pointer, but will return `None` if the value has already been
19 freed.
20
21 For example, a tree with parent pointers can be represented by putting the nodes behind `Strong`
22 pointers, and then storing the parent pointers as `Weak` pointers.
23
24 */
25
26 use cast::transmute;
27 use cell::Cell;
28 use clone::Clone;
29 use cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering};
30 use kinds::marker;
31 use ops::{Deref, Drop};
32 use option::{Option, Some, None};
33 use ptr;
34 use ptr::RawPtr;
35 use rt::global_heap::exchange_free;
36
37 struct RcBox<T> {
38 value: T,
39 strong: Cell<uint>,
40 weak: Cell<uint>
41 }
42
43 /// Immutable reference counted pointer type
44 #[unsafe_no_drop_flag]
45 pub struct Rc<T> {
46 ptr: *mut RcBox<T>,
47 nosend: marker::NoSend,
48 noshare: marker::NoShare
49 }
50
51 impl<T> Rc<T> {
52 /// Construct a new reference-counted box
53 pub fn new(value: T) -> Rc<T> {
54 unsafe {
55 Rc {
56 // there is an implicit weak pointer owned by all the
57 // strong pointers, which ensures that the weak
58 // destructor never frees the allocation while the
59 // strong destructor is running, even if the weak
60 // pointer is stored inside the strong one.
61 ptr: transmute(box RcBox {
62 value: value,
63 strong: Cell::new(1),
64 weak: Cell::new(1)
65 }),
66 nosend: marker::NoSend,
67 noshare: marker::NoShare
68 }
69 }
70 }
71 }
72
73 impl<T> Rc<T> {
74 /// Downgrade the reference-counted pointer to a weak reference
75 pub fn downgrade(&self) -> Weak<T> {
76 self.inc_weak();
77 Weak {
78 ptr: self.ptr,
79 nosend: marker::NoSend,
80 noshare: marker::NoShare
81 }
82 }
83 }
84
85 impl<T> Deref<T> for Rc<T> {
86 /// Borrow the value contained in the reference-counted box
87 #[inline(always)]
88 fn deref<'a>(&'a self) -> &'a T {
89 &self.inner().value
90 }
91 }
92
93 #[unsafe_destructor]
94 impl<T> Drop for Rc<T> {
95 fn drop(&mut self) {
96 unsafe {
97 if !self.ptr.is_null() {
98 self.dec_strong();
99 if self.strong() == 0 {
100 ptr::read(self.deref()); // destroy the contained object
101
102 // remove the implicit "strong weak" pointer now
103 // that we've destroyed the contents.
104 self.dec_weak();
105
106 if self.weak() == 0 {
107 exchange_free(self.ptr as *u8)
108 }
109 }
110 }
111 }
112 }
113 }
114
115 impl<T> Clone for Rc<T> {
116 #[inline]
117 fn clone(&self) -> Rc<T> {
118 self.inc_strong();
119 Rc { ptr: self.ptr, nosend: marker::NoSend, noshare: marker::NoShare }
120 }
121 }
122
123 impl<T: Eq> Eq for Rc<T> {
124 #[inline(always)]
125 fn eq(&self, other: &Rc<T>) -> bool { **self == **other }
126 #[inline(always)]
127 fn ne(&self, other: &Rc<T>) -> bool { **self != **other }
128 }
129
130 impl<T: TotalEq> TotalEq for Rc<T> {}
131
132 impl<T: Ord> Ord for Rc<T> {
133 #[inline(always)]
134 fn lt(&self, other: &Rc<T>) -> bool { **self < **other }
135
136 #[inline(always)]
137 fn le(&self, other: &Rc<T>) -> bool { **self <= **other }
138
139 #[inline(always)]
140 fn gt(&self, other: &Rc<T>) -> bool { **self > **other }
141
142 #[inline(always)]
143 fn ge(&self, other: &Rc<T>) -> bool { **self >= **other }
144 }
145
146 impl<T: TotalOrd> TotalOrd for Rc<T> {
147 #[inline]
148 fn cmp(&self, other: &Rc<T>) -> Ordering { (**self).cmp(&**other) }
149 }
150
151 /// Weak reference to a reference-counted box
152 #[unsafe_no_drop_flag]
153 pub struct Weak<T> {
154 ptr: *mut RcBox<T>,
155 nosend: marker::NoSend,
156 noshare: marker::NoShare
157 }
158
159 impl<T> Weak<T> {
160 /// Upgrade a weak reference to a strong reference
161 pub fn upgrade(&self) -> Option<Rc<T>> {
162 if self.strong() == 0 {
163 None
164 } else {
165 self.inc_strong();
166 Some(Rc { ptr: self.ptr, nosend: marker::NoSend, noshare: marker::NoShare })
167 }
168 }
169 }
170
171 #[unsafe_destructor]
172 impl<T> Drop for Weak<T> {
173 fn drop(&mut self) {
174 unsafe {
175 if !self.ptr.is_null() {
176 self.dec_weak();
177 // the weak count starts at 1, and will only go to
178 // zero if all the strong pointers have disappeared.
179 if self.weak() == 0 {
180 exchange_free(self.ptr as *u8)
181 }
182 }
183 }
184 }
185 }
186
187 impl<T> Clone for Weak<T> {
188 #[inline]
189 fn clone(&self) -> Weak<T> {
190 self.inc_weak();
191 Weak { ptr: self.ptr, nosend: marker::NoSend, noshare: marker::NoShare }
192 }
193 }
194
195 #[doc(hidden)]
196 trait RcBoxPtr<T> {
197 fn inner<'a>(&'a self) -> &'a RcBox<T>;
198
199 #[inline]
200 fn strong(&self) -> uint { self.inner().strong.get() }
201
202 #[inline]
203 fn inc_strong(&self) { self.inner().strong.set(self.strong() + 1); }
204
205 #[inline]
206 fn dec_strong(&self) { self.inner().strong.set(self.strong() - 1); }
207
208 #[inline]
209 fn weak(&self) -> uint { self.inner().weak.get() }
210
211 #[inline]
212 fn inc_weak(&self) { self.inner().weak.set(self.weak() + 1); }
213
214 #[inline]
215 fn dec_weak(&self) { self.inner().weak.set(self.weak() - 1); }
216 }
217
218 impl<T> RcBoxPtr<T> for Rc<T> {
219 #[inline(always)]
220 fn inner<'a>(&'a self) -> &'a RcBox<T> { unsafe { &(*self.ptr) } }
221 }
222
223 impl<T> RcBoxPtr<T> for Weak<T> {
224 #[inline(always)]
225 fn inner<'a>(&'a self) -> &'a RcBox<T> { unsafe { &(*self.ptr) } }
226 }
227
228 #[cfg(test)]
229 mod tests {
230 use prelude::*;
231 use super::*;
232 use cell::RefCell;
233
234 #[test]
235 fn test_clone() {
236 let x = Rc::new(RefCell::new(5));
237 let y = x.clone();
238 *x.borrow_mut() = 20;
239 assert_eq!(*y.borrow(), 20);
240 }
241
242 #[test]
243 fn test_simple() {
244 let x = Rc::new(5);
245 assert_eq!(*x, 5);
246 }
247
248 #[test]
249 fn test_simple_clone() {
250 let x = Rc::new(5);
251 let y = x.clone();
252 assert_eq!(*x, 5);
253 assert_eq!(*y, 5);
254 }
255
256 #[test]
257 fn test_destructor() {
258 let x = Rc::new(box 5);
259 assert_eq!(**x, 5);
260 }
261
262 #[test]
263 fn test_live() {
264 let x = Rc::new(5);
265 let y = x.downgrade();
266 assert!(y.upgrade().is_some());
267 }
268
269 #[test]
270 fn test_dead() {
271 let x = Rc::new(5);
272 let y = x.downgrade();
273 drop(x);
274 assert!(y.upgrade().is_none());
275 }
276
277 #[test]
278 fn gc_inside() {
279 // see issue #11532
280 use gc::Gc;
281 let a = Rc::new(RefCell::new(Gc::new(1)));
282 assert!(a.try_borrow_mut().is_some());
283 }
284
285 #[test]
286 fn weak_self_cyclic() {
287 struct Cycle {
288 x: RefCell<Option<Weak<Cycle>>>
289 }
290
291 let a = Rc::new(Cycle { x: RefCell::new(None) });
292 let b = a.clone().downgrade();
293 *a.x.borrow_mut() = Some(b);
294
295 // hopefully we don't double-free (or leak)...
296 }
297 }
libstd/rc.rs:195:15-195:15 -trait- definition:
trait RcBoxPtr<T> {
fn inner<'a>(&'a self) -> &'a RcBox<T>;
#[inline]
references:- 2218: impl<T> RcBoxPtr<T> for Rc<T> {
219: #[inline(always)]
--
223: impl<T> RcBoxPtr<T> for Weak<T> {
224: #[inline(always)]
libstd/rc.rs:36:1-36:1 -struct- definition:
struct RcBox<T> {
value: T,
strong: Cell<uint>,
references:- 645: pub struct Rc<T> {
46: ptr: *mut RcBox<T>,
47: nosend: marker::NoSend,
--
153: pub struct Weak<T> {
154: ptr: *mut RcBox<T>,
155: nosend: marker::NoSend,
--
219: #[inline(always)]
220: fn inner<'a>(&'a self) -> &'a RcBox<T> { unsafe { &(*self.ptr) } }
221: }
--
224: #[inline(always)]
225: fn inner<'a>(&'a self) -> &'a RcBox<T> { unsafe { &(*self.ptr) } }
226: }
libstd/rc.rs:152:23-152:23 -struct- definition:
pub struct Weak<T> {
ptr: *mut RcBox<T>,
nosend: marker::NoSend,
references:- 8190: self.inc_weak();
191: Weak { ptr: self.ptr, nosend: marker::NoSend, noshare: marker::NoShare }
192: }
--
223: impl<T> RcBoxPtr<T> for Weak<T> {
224: #[inline(always)]
libstd/rc.rs:44:23-44:23 -struct- definition:
pub struct Rc<T> {
ptr: *mut RcBox<T>,
nosend: marker::NoSend,
references:- 24165: self.inc_strong();
166: Some(Rc { ptr: self.ptr, nosend: marker::NoSend, noshare: marker::NoShare })
167: }
--
218: impl<T> RcBoxPtr<T> for Rc<T> {
219: #[inline(always)]
libstd/hash/mod.rs:
249: impl<S: Writer, T: Hash<S>> Hash<S> for Rc<T> {
250: #[inline]
libstd/rc.rs:
133: #[inline(always)]
134: fn lt(&self, other: &Rc<T>) -> bool { **self < **other }