will occur as soon as the last owner is gone. It is marked as non-sendable because it avoids the
overhead of atomic reference counting.
+The `downgrade` method can be used to create a non-owning `Weak` pointer to the box. A `Weak`
+pointer can be upgraded to an `Rc` pointer, but will return `None` if the value has already been
+freed.
+
+For example, a tree with parent pointers can be represented by putting the nodes behind `Strong`
+pointers, and then storing the parent pointers as `Weak` pointers.
+
*/
-use ptr::RawPtr;
-use unstable::intrinsics::transmute;
+use cast::transmute;
use ops::Drop;
-use kinds::NonManaged;
+use cmp::{Eq, Ord};
use clone::{Clone, DeepClone};
-use cmp::{Eq, TotalEq, Ord, TotalOrd, Ordering};
+use rt::global_heap::exchange_free;
+use ptr::read_ptr;
+use option::{Option, Some, None};
struct RcBox<T> {
value: T,
- count: uint
+ strong: uint,
+ weak: uint
}
/// Immutable reference counted pointer type
priv ptr: *mut RcBox<T>
}
-impl<T: NonManaged> Rc<T> {
+impl<T> Rc<T> {
/// Construct a new reference-counted box
- #[inline]
pub fn new(value: T) -> Rc<T> {
unsafe {
- Rc { ptr: transmute(~RcBox { value: value, count: 1 }) }
+ Rc { ptr: transmute(~RcBox { value: value, strong: 1, weak: 0 }) }
}
}
}
impl<T> Rc<T> {
/// Borrow the value contained in the reference-counted box
- #[inline]
- pub fn borrow<'r>(&'r self) -> &'r T {
+ #[inline(always)]
+ pub fn borrow<'a>(&'a self) -> &'a T {
unsafe { &(*self.ptr).value }
}
- /// Determine if two reference-counted pointers point to the same object
- #[inline]
- pub fn ptr_eq(&self, other: &Rc<T>) -> bool {
- self.ptr == other.ptr
+ /// Downgrade the reference-counted pointer to a weak reference
+ pub fn downgrade(&self) -> Weak<T> {
+ unsafe {
+ (*self.ptr).weak += 1;
+ Weak { ptr: self.ptr }
+ }
}
}
-impl<T: Eq> Eq for Rc<T> {
- #[inline]
- fn eq(&self, other: &Rc<T>) -> bool {
- unsafe { (*self.ptr).value == (*other.ptr).value }
+#[unsafe_destructor]
+impl<T> Drop for Rc<T> {
+ fn drop(&mut self) {
+ unsafe {
+ if self.ptr != 0 as *mut RcBox<T> {
+ (*self.ptr).strong -= 1;
+ if (*self.ptr).strong == 0 {
+ read_ptr(self.borrow()); // destroy the contained object
+ if (*self.ptr).weak == 0 {
+ exchange_free(self.ptr as *mut u8 as *i8)
+ }
+ }
+ }
+ }
}
+}
+impl<T> Clone for Rc<T> {
#[inline]
- fn ne(&self, other: &Rc<T>) -> bool {
- unsafe { (*self.ptr).value != (*other.ptr).value }
+ fn clone(&self) -> Rc<T> {
+ unsafe {
+ (*self.ptr).strong += 1;
+ Rc { ptr: self.ptr }
+ }
}
}
-impl<T: TotalEq> TotalEq for Rc<T> {
+impl<T: DeepClone> DeepClone for Rc<T> {
#[inline]
- fn equals(&self, other: &Rc<T>) -> bool {
- unsafe { (*self.ptr).value.equals(&(*other.ptr).value) }
+ fn deep_clone(&self) -> Rc<T> {
+ Rc::new(self.borrow().deep_clone())
}
}
+impl<T: Eq> Eq for Rc<T> {
+ #[inline(always)]
+ fn eq(&self, other: &Rc<T>) -> bool { *self.borrow() == *other.borrow() }
+
+ #[inline(always)]
+ fn ne(&self, other: &Rc<T>) -> bool { *self.borrow() != *other.borrow() }
+}
+
impl<T: Ord> Ord for Rc<T> {
- #[inline]
- fn lt(&self, other: &Rc<T>) -> bool {
- unsafe { (*self.ptr).value < (*other.ptr).value }
- }
+ #[inline(always)]
+ fn lt(&self, other: &Rc<T>) -> bool { *self.borrow() < *other.borrow() }
- #[inline]
- fn le(&self, other: &Rc<T>) -> bool {
- unsafe { (*self.ptr).value <= (*other.ptr).value }
- }
+ #[inline(always)]
+ fn le(&self, other: &Rc<T>) -> bool { *self.borrow() <= *other.borrow() }
- #[inline]
- fn ge(&self, other: &Rc<T>) -> bool {
- unsafe { (*self.ptr).value >= (*other.ptr).value }
- }
+ #[inline(always)]
+ fn gt(&self, other: &Rc<T>) -> bool { *self.borrow() > *other.borrow() }
- #[inline]
- fn gt(&self, other: &Rc<T>) -> bool {
- unsafe { (*self.ptr).value > (*other.ptr).value }
- }
+ #[inline(always)]
+ fn ge(&self, other: &Rc<T>) -> bool { *self.borrow() >= *other.borrow() }
}
-impl<T: TotalOrd> TotalOrd for Rc<T> {
- #[inline]
- fn cmp(&self, other: &Rc<T>) -> Ordering {
- unsafe { (*self.ptr).value.cmp(&(*other.ptr).value) }
- }
+/// Weak reference to a reference-counted box
+#[unsafe_no_drop_flag]
+#[no_send]
+pub struct Weak<T> {
+ priv ptr: *mut RcBox<T>
}
-impl<T> Clone for Rc<T> {
- #[inline]
- fn clone(&self) -> Rc<T> {
+impl<T> Weak<T> {
+ /// Upgrade a weak reference to a strong reference
+ pub fn upgrade(&self) -> Option<Rc<T>> {
unsafe {
- (*self.ptr).count += 1;
- Rc{ptr: self.ptr}
+ if (*self.ptr).strong == 0 {
+ None
+ } else {
+ (*self.ptr).strong += 1;
+ Some(Rc { ptr: self.ptr })
+ }
}
}
}
-impl<T: NonManaged + DeepClone> DeepClone for Rc<T> {
- #[inline]
- fn deep_clone(&self) -> Rc<T> {
- Rc::new(self.borrow().deep_clone())
- }
-}
-
#[unsafe_destructor]
-impl<T> Drop for Rc<T> {
+impl<T> Drop for Weak<T> {
fn drop(&mut self) {
unsafe {
- if self.ptr.is_not_null() {
- (*self.ptr).count -= 1;
- if (*self.ptr).count == 0 {
- let _: ~RcBox<T> = transmute(self.ptr);
+ if self.ptr != 0 as *mut RcBox<T> {
+ (*self.ptr).weak -= 1;
+ if (*self.ptr).weak == 0 && (*self.ptr).strong == 0 {
+ exchange_free(self.ptr as *mut u8 as *i8)
}
}
}
}
}
-#[cfg(test)]
-mod test_rc {
- use prelude::*;
- use super::*;
- use cell::RefCell;
-
- #[test]
- fn test_clone() {
- let x = Rc::new(RefCell::new(5));
- let y = x.clone();
- x.borrow().with_mut(|inner| {
- *inner = 20;
- });
- assert_eq!(y.borrow().with(|v| *v), 20);
+impl<T> Clone for Weak<T> {
+ #[inline]
+ fn clone(&self) -> Weak<T> {
+ unsafe {
+ (*self.ptr).weak += 1;
+ Weak { ptr: self.ptr }
+ }
}
+}
- #[test]
- fn test_deep_clone() {
- let x = Rc::new(RefCell::new(5));
- let y = x.deep_clone();
- x.borrow().with_mut(|inner| {
- *inner = 20;
- });
- assert_eq!(y.borrow().with(|v| *v), 5);
- }
+#[cfg(test)]
+mod tests {
+ use super::*;
+ use prelude::drop;
#[test]
- fn test_simple() {
+ fn test_live() {
let x = Rc::new(5);
- assert_eq!(*x.borrow(), 5);
+ let y = x.downgrade();
+ assert!(y.upgrade().is_some());
}
#[test]
- fn test_simple_clone() {
+ fn test_dead() {
let x = Rc::new(5);
- let y = x.clone();
- assert_eq!(*x.borrow(), 5);
- assert_eq!(*y.borrow(), 5);
- }
-
- #[test]
- fn test_destructor() {
- let x = Rc::new(~5);
- assert_eq!(**x.borrow(), 5);
+ let y = x.downgrade();
+ drop(x);
+ assert!(y.upgrade().is_none());
}
}