src/liballoc/rc.rs

   1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
   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 core::mem::transmute;
  27 use core::cell::Cell;
  28 use core::clone::Clone;
  29 use core::cmp::{PartialEq, PartialOrd, Eq, Ord, Ordering};
  30 use core::kinds::marker;
  31 use core::ops::{Deref, Drop};
  32 use core::option::{Option, Some, None};
  33 use core::ptr;
  34 use core::ptr::RawPtr;
  35 use core::mem::{min_align_of, size_of};
  36 use core::fmt;
  37
  38 use heap::deallocate;
  39
  40 struct RcBox<T> {
  41     value: T,
  42     strong: Cell<uint>,
  43     weak: Cell<uint>
  44 }
  45
  46 /// Immutable reference counted pointer type
  47 #[unsafe_no_drop_flag]
  48 pub struct Rc<T> {
  49     // FIXME #12808: strange names to try to avoid interfering with
  50     // field accesses of the contained type via Deref
  51     _ptr: *mut RcBox<T>,
  52     _nosend: marker::NoSend,
  53     _noshare: marker::NoShare
  54 }
  55
  56 impl<T> Rc<T> {
  57     /// Construct a new reference-counted box
  58     pub fn new(value: T) -> Rc<T> {
  59         unsafe {
  60             Rc {
  61                 // there is an implicit weak pointer owned by all the
  62                 // strong pointers, which ensures that the weak
  63                 // destructor never frees the allocation while the
  64                 // strong destructor is running, even if the weak
  65                 // pointer is stored inside the strong one.
  66                 _ptr: transmute(box RcBox {
  67                     value: value,
  68                     strong: Cell::new(1),
  69                     weak: Cell::new(1)
  70                 }),
  71                 _nosend: marker::NoSend,
  72                 _noshare: marker::NoShare
  73             }
  74         }
  75     }
  76 }
  77
  78 impl<T> Rc<T> {
  79     /// Downgrade the reference-counted pointer to a weak reference
  80     pub fn downgrade(&self) -> Weak<T> {
  81         self.inc_weak();
  82         Weak {
  83             _ptr: self._ptr,
  84             _nosend: marker::NoSend,
  85             _noshare: marker::NoShare
  86         }
  87     }
  88 }
  89
  90 impl<T: Clone> Rc<T> {
  91     /// Acquires a mutable pointer to the inner contents by guaranteeing that
  92     /// the reference count is one (no sharing is possible).
  93     ///
  94     /// This is also referred to as a copy-on-write operation because the inner
  95     /// data is cloned if the reference count is greater than one.
  96     #[inline]
  97     #[experimental]
  98     pub fn make_unique<'a>(&'a mut self) -> &'a mut T {
  99         // Note that we hold a strong reference, which also counts as
 100         // a weak reference, so we only clone if there is an
 101         // additional reference of either kind.
 102         if self.strong() != 1 || self.weak() != 1 {
 103             *self = Rc::new(self.deref().clone())
 104         }
 105         // This unsafety is ok because we're guaranteed that the pointer
 106         // returned is the *only* pointer that will ever be returned to T. Our
 107         // reference count is guaranteed to be 1 at this point, and we required
 108         // the Rc itself to be `mut`, so we're returning the only possible
 109         // reference to the inner data.
 110         let inner = unsafe { &mut *self._ptr };
 111         &mut inner.value
 112     }
 113 }
 114
 115 impl<T> Deref<T> for Rc<T> {
 116     /// Borrow the value contained in the reference-counted box
 117     #[inline(always)]
 118     fn deref<'a>(&'a self) -> &'a T {
 119         &self.inner().value
 120     }
 121 }
 122
 123 #[unsafe_destructor]
 124 impl<T> Drop for Rc<T> {
 125     fn drop(&mut self) {
 126         unsafe {
 127             if !self._ptr.is_null() {
 128                 self.dec_strong();
 129                 if self.strong() == 0 {
 130                     ptr::read(self.deref()); // destroy the contained object
 131
 132                     // remove the implicit "strong weak" pointer now
 133                     // that we've destroyed the contents.
 134                     self.dec_weak();
 135
 136                     if self.weak() == 0 {
 137                         deallocate(self._ptr as *mut u8, size_of::<RcBox<T>>(),
 138                                    min_align_of::<RcBox<T>>())
 139                     }
 140                 }
 141             }
 142         }
 143     }
 144 }
 145
 146 impl<T> Clone for Rc<T> {
 147     #[inline]
 148     fn clone(&self) -> Rc<T> {
 149         self.inc_strong();
 150         Rc { _ptr: self._ptr, _nosend: marker::NoSend, _noshare: marker::NoShare }
 151     }
 152 }
 153
 154 impl<T: PartialEq> PartialEq for Rc<T> {
 155     #[inline(always)]
 156     fn eq(&self, other: &Rc<T>) -> bool { **self == **other }
 157     #[inline(always)]
 158     fn ne(&self, other: &Rc<T>) -> bool { **self != **other }
 159 }
 160
 161 impl<T: Eq> Eq for Rc<T> {}
 162
 163 impl<T: PartialOrd> PartialOrd for Rc<T> {
 164     #[inline(always)]
 165     fn lt(&self, other: &Rc<T>) -> bool { **self < **other }
 166
 167     #[inline(always)]
 168     fn le(&self, other: &Rc<T>) -> bool { **self <= **other }
 169
 170     #[inline(always)]
 171     fn gt(&self, other: &Rc<T>) -> bool { **self > **other }
 172
 173     #[inline(always)]
 174     fn ge(&self, other: &Rc<T>) -> bool { **self >= **other }
 175 }
 176
 177 impl<T: Ord> Ord for Rc<T> {
 178     #[inline]
 179     fn cmp(&self, other: &Rc<T>) -> Ordering { (**self).cmp(&**other) }
 180 }
 181
 182 impl<T: fmt::Show> fmt::Show for Rc<T> {
 183     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 184         (**self).fmt(f)
 185     }
 186 }
 187
 188 /// Weak reference to a reference-counted box
 189 #[unsafe_no_drop_flag]
 190 pub struct Weak<T> {
 191     // FIXME #12808: strange names to try to avoid interfering with
 192     // field accesses of the contained type via Deref
 193     _ptr: *mut RcBox<T>,
 194     _nosend: marker::NoSend,
 195     _noshare: marker::NoShare
 196 }
 197
 198 impl<T> Weak<T> {
 199     /// Upgrade a weak reference to a strong reference
 200     pub fn upgrade(&self) -> Option<Rc<T>> {
 201         if self.strong() == 0 {
 202             None
 203         } else {
 204             self.inc_strong();
 205             Some(Rc { _ptr: self._ptr, _nosend: marker::NoSend, _noshare: marker::NoShare })
 206         }
 207     }
 208 }
 209
 210 #[unsafe_destructor]
 211 impl<T> Drop for Weak<T> {
 212     fn drop(&mut self) {
 213         unsafe {
 214             if !self._ptr.is_null() {
 215                 self.dec_weak();
 216                 // the weak count starts at 1, and will only go to
 217                 // zero if all the strong pointers have disappeared.
 218                 if self.weak() == 0 {
 219                     deallocate(self._ptr as *mut u8, size_of::<RcBox<T>>(),
 220                                min_align_of::<RcBox<T>>())
 221                 }
 222             }
 223         }
 224     }
 225 }
 226
 227 impl<T> Clone for Weak<T> {
 228     #[inline]
 229     fn clone(&self) -> Weak<T> {
 230         self.inc_weak();
 231         Weak { _ptr: self._ptr, _nosend: marker::NoSend, _noshare: marker::NoShare }
 232     }
 233 }
 234
 235 #[doc(hidden)]
 236 trait RcBoxPtr<T> {
 237     fn inner<'a>(&'a self) -> &'a RcBox<T>;
 238
 239     #[inline]
 240     fn strong(&self) -> uint { self.inner().strong.get() }
 241
 242     #[inline]
 243     fn inc_strong(&self) { self.inner().strong.set(self.strong() + 1); }
 244
 245     #[inline]
 246     fn dec_strong(&self) { self.inner().strong.set(self.strong() - 1); }
 247
 248     #[inline]
 249     fn weak(&self) -> uint { self.inner().weak.get() }
 250
 251     #[inline]
 252     fn inc_weak(&self) { self.inner().weak.set(self.weak() + 1); }
 253
 254     #[inline]
 255     fn dec_weak(&self) { self.inner().weak.set(self.weak() - 1); }
 256 }
 257
 258 impl<T> RcBoxPtr<T> for Rc<T> {
 259     #[inline(always)]
 260     fn inner<'a>(&'a self) -> &'a RcBox<T> { unsafe { &(*self._ptr) } }
 261 }
 262
 263 impl<T> RcBoxPtr<T> for Weak<T> {
 264     #[inline(always)]
 265     fn inner<'a>(&'a self) -> &'a RcBox<T> { unsafe { &(*self._ptr) } }
 266 }
 267
 268 #[cfg(test)]
 269 #[allow(experimental)]
 270 mod tests {
 271     use super::{Rc, Weak};
 272     use std::cell::RefCell;
 273     use std::option::{Option, Some, None};
 274     use std::mem::drop;
 275     use std::clone::Clone;
 276
 277     #[test]
 278     fn test_clone() {
 279         let x = Rc::new(RefCell::new(5));
 280         let y = x.clone();
 281         *x.borrow_mut() = 20;
 282         assert_eq!(*y.borrow(), 20);
 283     }
 284
 285     #[test]
 286     fn test_simple() {
 287         let x = Rc::new(5);
 288         assert_eq!(*x, 5);
 289     }
 290
 291     #[test]
 292     fn test_simple_clone() {
 293         let x = Rc::new(5);
 294         let y = x.clone();
 295         assert_eq!(*x, 5);
 296         assert_eq!(*y, 5);
 297     }
 298
 299     #[test]
 300     fn test_destructor() {
 301         let x = Rc::new(box 5);
 302         assert_eq!(**x, 5);
 303     }
 304
 305     #[test]
 306     fn test_live() {
 307         let x = Rc::new(5);
 308         let y = x.downgrade();
 309         assert!(y.upgrade().is_some());
 310     }
 311
 312     #[test]
 313     fn test_dead() {
 314         let x = Rc::new(5);
 315         let y = x.downgrade();
 316         drop(x);
 317         assert!(y.upgrade().is_none());
 318     }
 319
 320     #[test]
 321     fn gc_inside() {
 322         // see issue #11532
 323         use std::gc::Gc;
 324         let a = Rc::new(RefCell::new(Gc::new(1)));
 325         assert!(a.try_borrow_mut().is_some());
 326     }
 327
 328     #[test]
 329     fn weak_self_cyclic() {
 330         struct Cycle {
 331             x: RefCell<Option<Weak<Cycle>>>
 332         }
 333
 334         let a = Rc::new(Cycle { x: RefCell::new(None) });
 335         let b = a.clone().downgrade();
 336         *a.x.borrow_mut() = Some(b);
 337
 338         // hopefully we don't double-free (or leak)...
 339     }
 340
 341     #[test]
 342     fn test_cowrc_clone_make_unique() {
 343         let mut cow0 = Rc::new(75u);
 344         let mut cow1 = cow0.clone();
 345         let mut cow2 = cow1.clone();
 346
 347         assert!(75 == *cow0.make_unique());
 348         assert!(75 == *cow1.make_unique());
 349         assert!(75 == *cow2.make_unique());
 350
 351         *cow0.make_unique() += 1;
 352         *cow1.make_unique() += 2;
 353         *cow2.make_unique() += 3;
 354
 355         assert!(76 == *cow0);
 356         assert!(77 == *cow1);
 357         assert!(78 == *cow2);
 358
 359         // none should point to the same backing memory
 360         assert!(*cow0 != *cow1);
 361         assert!(*cow0 != *cow2);
 362         assert!(*cow1 != *cow2);
 363     }
 364
 365     #[test]
 366     fn test_cowrc_clone_unique2() {
 367         let mut cow0 = Rc::new(75u);
 368         let cow1 = cow0.clone();
 369         let cow2 = cow1.clone();
 370
 371         assert!(75 == *cow0);
 372         assert!(75 == *cow1);
 373         assert!(75 == *cow2);
 374
 375         *cow0.make_unique() += 1;
 376
 377         assert!(76 == *cow0);
 378         assert!(75 == *cow1);
 379         assert!(75 == *cow2);
 380
 381         // cow1 and cow2 should share the same contents
 382         // cow0 should have a unique reference
 383         assert!(*cow0 != *cow1);
 384         assert!(*cow0 != *cow2);
 385         assert!(*cow1 == *cow2);
 386     }
 387
 388     #[test]
 389     fn test_cowrc_clone_weak() {
 390         let mut cow0 = Rc::new(75u);
 391         let cow1_weak = cow0.downgrade();
 392
 393         assert!(75 == *cow0);
 394         assert!(75 == *cow1_weak.upgrade().unwrap());
 395
 396         *cow0.make_unique() += 1;
 397
 398         assert!(76 == *cow0);
 399         assert!(cow1_weak.upgrade().is_none());
 400     }
 401
 402 }