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 ops::Drop;
  28 use cmp::{Eq, Ord};
  29 use clone::{Clone, DeepClone};
  30 use rt::global_heap::exchange_free;
  31 use ptr::read_ptr;
  32 use option::{Option, Some, None};
  33
  34 struct RcBox<T> {
  35     value: T,
  36     strong: uint,
  37     weak: uint
  38 }
  39
  40 /// Immutable reference counted pointer type
  41 #[unsafe_no_drop_flag]
  42 #[no_send]
  43 pub struct Rc<T> {
  44     priv ptr: *mut RcBox<T>
  45 }
  46
  47 impl<T> Rc<T> {
  48     /// Construct a new reference-counted box
  49     pub fn new(value: T) -> Rc<T> {
  50         unsafe {
  51             Rc { ptr: transmute(~RcBox { value: value, strong: 1, weak: 0 }) }
  52         }
  53     }
  54 }
  55
  56 impl<T> Rc<T> {
  57     /// Borrow the value contained in the reference-counted box
  58     #[inline(always)]
  59     pub fn borrow<'a>(&'a self) -> &'a T {
  60         unsafe { &(*self.ptr).value }
  61     }
  62
  63     /// Downgrade the reference-counted pointer to a weak reference
  64     pub fn downgrade(&self) -> Weak<T> {
  65         unsafe {
  66             (*self.ptr).weak += 1;
  67             Weak { ptr: self.ptr }
  68         }
  69     }
  70 }
  71
  72 #[unsafe_destructor]
  73 impl<T> Drop for Rc<T> {
  74     fn drop(&mut self) {
  75         unsafe {
  76             if self.ptr != 0 as *mut RcBox<T> {
  77                 (*self.ptr).strong -= 1;
  78                 if (*self.ptr).strong == 0 {
  79                     read_ptr(self.borrow()); // destroy the contained object
  80                     if (*self.ptr).weak == 0 {
  81                         exchange_free(self.ptr as *mut u8 as *i8)
  82                     }
  83                 }
  84             }
  85         }
  86     }
  87 }
  88
  89 impl<T> Clone for Rc<T> {
  90     #[inline]
  91     fn clone(&self) -> Rc<T> {
  92         unsafe {
  93             (*self.ptr).strong += 1;
  94             Rc { ptr: self.ptr }
  95         }
  96     }
  97 }
  98
  99 impl<T: DeepClone> DeepClone for Rc<T> {
 100     #[inline]
 101     fn deep_clone(&self) -> Rc<T> {
 102         Rc::new(self.borrow().deep_clone())
 103     }
 104 }
 105
 106 impl<T: Eq> Eq for Rc<T> {
 107     #[inline(always)]
 108     fn eq(&self, other: &Rc<T>) -> bool { *self.borrow() == *other.borrow() }
 109
 110     #[inline(always)]
 111     fn ne(&self, other: &Rc<T>) -> bool { *self.borrow() != *other.borrow() }
 112 }
 113
 114 impl<T: Ord> Ord for Rc<T> {
 115     #[inline(always)]
 116     fn lt(&self, other: &Rc<T>) -> bool { *self.borrow() < *other.borrow() }
 117
 118     #[inline(always)]
 119     fn le(&self, other: &Rc<T>) -> bool { *self.borrow() <= *other.borrow() }
 120
 121     #[inline(always)]
 122     fn gt(&self, other: &Rc<T>) -> bool { *self.borrow() > *other.borrow() }
 123
 124     #[inline(always)]
 125     fn ge(&self, other: &Rc<T>) -> bool { *self.borrow() >= *other.borrow() }
 126 }
 127
 128 /// Weak reference to a reference-counted box
 129 #[unsafe_no_drop_flag]
 130 #[no_send]
 131 pub struct Weak<T> {
 132     priv ptr: *mut RcBox<T>
 133 }
 134
 135 impl<T> Weak<T> {
 136     /// Upgrade a weak reference to a strong reference
 137     pub fn upgrade(&self) -> Option<Rc<T>> {
 138         unsafe {
 139             if (*self.ptr).strong == 0 {
 140                 None
 141             } else {
 142                 (*self.ptr).strong += 1;
 143                 Some(Rc { ptr: self.ptr })
 144             }
 145         }
 146     }
 147 }
 148
 149 #[unsafe_destructor]
 150 impl<T> Drop for Weak<T> {
 151     fn drop(&mut self) {
 152         unsafe {
 153             if self.ptr != 0 as *mut RcBox<T> {
 154                 (*self.ptr).weak -= 1;
 155                 if (*self.ptr).weak == 0 && (*self.ptr).strong == 0 {
 156                     exchange_free(self.ptr as *mut u8 as *i8)
 157                 }
 158             }
 159         }
 160     }
 161 }
 162
 163 impl<T> Clone for Weak<T> {
 164     #[inline]
 165     fn clone(&self) -> Weak<T> {
 166         unsafe {
 167             (*self.ptr).weak += 1;
 168             Weak { ptr: self.ptr }
 169         }
 170     }
 171 }
 172
 173 #[cfg(test)]
 174 mod tests {
 175     use super::*;
 176     use prelude::drop;
 177
 178     #[test]
 179     fn test_live() {
 180         let x = Rc::new(5);
 181         let y = x.downgrade();
 182         assert!(y.upgrade().is_some());
 183     }
 184
 185     #[test]
 186     fn test_dead() {
 187         let x = Rc::new(5);
 188         let y = x.downgrade();
 189         drop(x);
 190         assert!(y.upgrade().is_none());
 191     }
 192 }