src/libstd/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 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     priv ptr: *mut RcBox<T>,
  47     priv nosend: marker::NoSend,
  48     priv 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(~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     priv ptr: *mut RcBox<T>,
 155     priv nosend: marker::NoSend,
 156     priv 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 #[allow(missing_doc)]
 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(~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 }