src/liballoc/rc.rs

   1 // Copyright 2013-2014 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 (the `Rc<T>` type).
  12 //!
  13 //! The `Rc<T>` type provides shared ownership of an immutable value. Destruction is deterministic,
  14 //! and will occur as soon as the last owner is gone. It is marked as non-sendable because it
  15 //! avoids the overhead of atomic reference counting.
  16 //!
  17 //! The `downgrade` method can be used to create a non-owning `Weak<T>` pointer to the box. A
  18 //! `Weak<T>` pointer can be upgraded to an `Rc<T>` pointer, but will return `None` if the value
  19 //! has already been dropped.
  20 //!
  21 //! For example, a tree with parent pointers can be represented by putting the nodes behind strong
  22 //! `Rc<T>` pointers, and then storing the parent pointers as `Weak<T>` pointers.
  23 //!
  24 //! # Examples
  25 //!
  26 //! Consider a scenario where a set of `Gadget`s are owned by a given `Owner`.  We want to have our
  27 //! `Gadget`s point to their `Owner`. We can't do this with unique ownership, because more than one
  28 //! gadget may belong to the same `Owner`. `Rc<T>` allows us to share an `Owner` between multiple
  29 //! `Gadget`s, and have the `Owner` remain allocated as long as any `Gadget` points at it.
  30 //!
  31 //! ```rust
  32 //! use std::rc::Rc;
  33 //!
  34 //! struct Owner {
  35 //!     name: String
  36 //!     // ...other fields
  37 //! }
  38 //!
  39 //! struct Gadget {
  40 //!     id: int,
  41 //!     owner: Rc<Owner>
  42 //!     // ...other fields
  43 //! }
  44 //!
  45 //! fn main() {
  46 //!     // Create a reference counted Owner.
  47 //!     let gadget_owner : Rc<Owner> = Rc::new(
  48 //!             Owner { name: String::from_str("Gadget Man") }
  49 //!     );
  50 //!
  51 //!     // Create Gadgets belonging to gadget_owner. To increment the reference
  52 //!     // count we clone the `Rc<T>` object.
  53 //!     let gadget1 = Gadget { id: 1, owner: gadget_owner.clone() };
  54 //!     let gadget2 = Gadget { id: 2, owner: gadget_owner.clone() };
  55 //!
  56 //!     drop(gadget_owner);
  57 //!
  58 //!     // Despite dropping gadget_owner, we're still able to print out the name of
  59 //!     // the Owner of the Gadgets. This is because we've only dropped the
  60 //!     // reference count object, not the Owner it wraps. As long as there are
  61 //!     // other `Rc<T>` objects pointing at the same Owner, it will remain allocated. Notice
  62 //!     // that the `Rc<T>` wrapper around Gadget.owner gets automatically dereferenced
  63 //!     // for us.
  64 //!     println!("Gadget {} owned by {}", gadget1.id, gadget1.owner.name);
  65 //!     println!("Gadget {} owned by {}", gadget2.id, gadget2.owner.name);
  66 //!
  67 //!     // At the end of the method, gadget1 and gadget2 get destroyed, and with
  68 //!     // them the last counted references to our Owner. Gadget Man now gets
  69 //!     // destroyed as well.
  70 //! }
  71 //! ```
  72 //!
  73 //! If our requirements change, and we also need to be able to traverse from Owner → Gadget, we
  74 //! will run into problems: an `Rc<T>` pointer from Owner → Gadget introduces a cycle between the
  75 //! objects. This means that their reference counts can never reach 0, and the objects will remain
  76 //! allocated: a memory leak. In order to get around this, we can use `Weak<T>` pointers. These
  77 //! pointers don't contribute to the total count.
  78 //!
  79 //! Rust actually makes it somewhat difficult to produce this loop in the first place: in order to
  80 //! end up with two objects that point at each other, one of them needs to be mutable. This is
  81 //! problematic because `Rc<T>` enforces memory safety by only giving out shared references to the
  82 //! object it wraps, and these don't allow direct mutation. We need to wrap the part of the object
  83 //! we wish to mutate in a `RefCell`, which provides *interior mutability*: a method to achieve
  84 //! mutability through a shared reference. `RefCell` enforces Rust's borrowing rules at runtime.
  85 //! Read the `Cell` documentation for more details on interior mutability.
  86 //!
  87 //! ```rust
  88 //! use std::rc::Rc;
  89 //! use std::rc::Weak;
  90 //! use std::cell::RefCell;
  91 //!
  92 //! struct Owner {
  93 //!     name: String,
  94 //!     gadgets: RefCell<Vec<Weak<Gadget>>>
  95 //!     // ...other fields
  96 //! }
  97 //!
  98 //! struct Gadget {
  99 //!     id: int,
 100 //!     owner: Rc<Owner>
 101 //!     // ...other fields
 102 //! }
 103 //!
 104 //! fn main() {
 105 //!     // Create a reference counted Owner. Note the fact that we've put the
 106 //!     // Owner's vector of Gadgets inside a RefCell so that we can mutate it
 107 //!     // through a shared reference.
 108 //!     let gadget_owner : Rc<Owner> = Rc::new(
 109 //!             Owner {
 110 //!                 name: "Gadget Man".to_string(),
 111 //!                 gadgets: RefCell::new(Vec::new())
 112 //!             }
 113 //!     );
 114 //!
 115 //!     // Create Gadgets belonging to gadget_owner as before.
 116 //!     let gadget1 = Rc::new(Gadget{id: 1, owner: gadget_owner.clone()});
 117 //!     let gadget2 = Rc::new(Gadget{id: 2, owner: gadget_owner.clone()});
 118 //!
 119 //!     // Add the Gadgets to their Owner. To do this we mutably borrow from
 120 //!     // the RefCell holding the Owner's Gadgets.
 121 //!     gadget_owner.gadgets.borrow_mut().push(gadget1.clone().downgrade());
 122 //!     gadget_owner.gadgets.borrow_mut().push(gadget2.clone().downgrade());
 123 //!
 124 //!     // Iterate over our Gadgets, printing their details out
 125 //!     for gadget_opt in gadget_owner.gadgets.borrow().iter() {
 126 //!
 127 //!         // gadget_opt is a Weak<Gadget>. Since weak pointers can't guarantee
 128 //!         // that their object is still allocated, we need to call upgrade() on them
 129 //!         // to turn them into a strong reference. This returns an Option, which
 130 //!         // contains a reference to our object if it still exists.
 131 //!         let gadget = gadget_opt.upgrade().unwrap();
 132 //!         println!("Gadget {} owned by {}", gadget.id, gadget.owner.name);
 133 //!     }
 134 //!
 135 //!     // At the end of the method, gadget_owner, gadget1 and gadget2 get
 136 //!     // destroyed. There are now no strong (`Rc<T>`) references to the gadgets.
 137 //!     // Once they get destroyed, the Gadgets get destroyed. This zeroes the
 138 //!     // reference count on Gadget Man, so he gets destroyed as well.
 139 //! }
 140 //! ```
 141
 142 #![stable]
 143
 144 use core::cell::Cell;
 145 use core::clone::Clone;
 146 use core::cmp::{PartialEq, PartialOrd, Eq, Ord, Ordering};
 147 use core::default::Default;
 148 use core::fmt;
 149 use core::kinds::marker;
 150 use core::mem::{transmute, min_align_of, size_of, forget};
 151 use core::ops::{Deref, Drop};
 152 use core::option::Option;
 153 use core::option::Option::{Some, None};
 154 use core::ptr;
 155 use core::ptr::RawPtr;
 156 use core::result::Result;
 157 use core::result::Result::{Ok, Err};
 158
 159 use heap::deallocate;
 160
 161 struct RcBox<T> {
 162     value: T,
 163     strong: Cell<uint>,
 164     weak: Cell<uint>
 165 }
 166
 167 /// An immutable reference-counted pointer type.
 168 ///
 169 /// See the [module level documentation](../index.html) for more.
 170 #[unsafe_no_drop_flag]
 171 #[stable]
 172 pub struct Rc<T> {
 173     // FIXME #12808: strange names to try to avoid interfering with
 174     // field accesses of the contained type via Deref
 175     _ptr: *mut RcBox<T>,
 176     _nosend: marker::NoSend,
 177     _noshare: marker::NoSync
 178 }
 179
 180 impl<T> Rc<T> {
 181     /// Constructs a new `Rc<T>`.
 182     ///
 183     /// # Examples
 184     ///
 185     /// ```
 186     /// use std::rc::Rc;
 187     ///
 188     /// let five = Rc::new(5i);
 189     /// ```
 190     #[stable]
 191     pub fn new(value: T) -> Rc<T> {
 192         unsafe {
 193             Rc {
 194                 // there is an implicit weak pointer owned by all the
 195                 // strong pointers, which ensures that the weak
 196                 // destructor never frees the allocation while the
 197                 // strong destructor is running, even if the weak
 198                 // pointer is stored inside the strong one.
 199                 _ptr: transmute(box RcBox {
 200                     value: value,
 201                     strong: Cell::new(1),
 202                     weak: Cell::new(1)
 203                 }),
 204                 _nosend: marker::NoSend,
 205                 _noshare: marker::NoSync
 206             }
 207         }
 208     }
 209
 210     /// Downgrades the `Rc<T>` to a `Weak<T>` reference.
 211     ///
 212     /// # Examples
 213     ///
 214     /// ```
 215     /// use std::rc::Rc;
 216     ///
 217     /// let five = Rc::new(5i);
 218     ///
 219     /// let weak_five = five.downgrade();
 220     /// ```
 221     #[experimental = "Weak pointers may not belong in this module"]
 222     pub fn downgrade(&self) -> Weak<T> {
 223         self.inc_weak();
 224         Weak {
 225             _ptr: self._ptr,
 226             _nosend: marker::NoSend,
 227             _noshare: marker::NoSync
 228         }
 229     }
 230 }
 231
 232 /// Get the number of weak references to this value.
 233 #[inline]
 234 #[experimental]
 235 pub fn weak_count<T>(this: &Rc<T>) -> uint { this.weak() - 1 }
 236
 237 /// Get the number of strong references to this value.
 238 #[inline]
 239 #[experimental]
 240 pub fn strong_count<T>(this: &Rc<T>) -> uint { this.strong() }
 241
 242 /// Returns true if there are no other `Rc` or `Weak<T>` values that share the same inner value.
 243 ///
 244 /// # Examples
 245 ///
 246 /// ```
 247 /// use std::rc;
 248 /// use std::rc::Rc;
 249 ///
 250 /// let five = Rc::new(5i);
 251 ///
 252 /// rc::is_unique(&five);
 253 /// ```
 254 #[inline]
 255 #[experimental]
 256 pub fn is_unique<T>(rc: &Rc<T>) -> bool {
 257     weak_count(rc) == 0 && strong_count(rc) == 1
 258 }
 259
 260 /// Unwraps the contained value if the `Rc<T>` is unique.
 261 ///
 262 /// If the `Rc<T>` is not unique, an `Err` is returned with the same `Rc<T>`.
 263 ///
 264 /// # Example
 265 ///
 266 /// ```
 267 /// use std::rc::{mod, Rc};
 268 ///
 269 /// let x = Rc::new(3u);
 270 /// assert_eq!(rc::try_unwrap(x), Ok(3u));
 271 ///
 272 /// let x = Rc::new(4u);
 273 /// let _y = x.clone();
 274 /// assert_eq!(rc::try_unwrap(x), Err(Rc::new(4u)));
 275 /// ```
 276 #[inline]
 277 #[experimental]
 278 pub fn try_unwrap<T>(rc: Rc<T>) -> Result<T, Rc<T>> {
 279     if is_unique(&rc) {
 280         unsafe {
 281             let val = ptr::read(&*rc); // copy the contained object
 282             // destruct the box and skip our Drop
 283             // we can ignore the refcounts because we know we're unique
 284             deallocate(rc._ptr as *mut u8, size_of::<RcBox<T>>(),
 285                         min_align_of::<RcBox<T>>());
 286             forget(rc);
 287             Ok(val)
 288         }
 289     } else {
 290         Err(rc)
 291     }
 292 }
 293
 294 /// Returns a mutable reference to the contained value if the `Rc<T>` is unique.
 295 ///
 296 /// Returns `None` if the `Rc<T>` is not unique.
 297 ///
 298 /// # Example
 299 ///
 300 /// ```
 301 /// use std::rc::{mod, Rc};
 302 ///
 303 /// let mut x = Rc::new(3u);
 304 /// *rc::get_mut(&mut x).unwrap() = 4u;
 305 /// assert_eq!(*x, 4u);
 306 ///
 307 /// let _y = x.clone();
 308 /// assert!(rc::get_mut(&mut x).is_none());
 309 /// ```
 310 #[inline]
 311 #[experimental]
 312 pub fn get_mut<'a, T>(rc: &'a mut Rc<T>) -> Option<&'a mut T> {
 313     if is_unique(rc) {
 314         let inner = unsafe { &mut *rc._ptr };
 315         Some(&mut inner.value)
 316     } else {
 317         None
 318     }
 319 }
 320
 321 impl<T: Clone> Rc<T> {
 322     /// Make a mutable reference from the given `Rc<T>`.
 323     ///
 324     /// This is also referred to as a copy-on-write operation because the inner data is cloned if
 325     /// the reference count is greater than one.
 326     ///
 327     /// # Examples
 328     ///
 329     /// ```
 330     /// use std::rc::Rc;
 331     ///
 332     /// let mut five = Rc::new(5i);
 333     ///
 334     /// let mut_five = five.make_unique();
 335     /// ```
 336     #[inline]
 337     #[experimental]
 338     pub fn make_unique(&mut self) -> &mut T {
 339         if !is_unique(self) {
 340             *self = Rc::new((**self).clone())
 341         }
 342         // This unsafety is ok because we're guaranteed that the pointer
 343         // returned is the *only* pointer that will ever be returned to T. Our
 344         // reference count is guaranteed to be 1 at this point, and we required
 345         // the `Rc<T>` itself to be `mut`, so we're returning the only possible
 346         // reference to the inner value.
 347         let inner = unsafe { &mut *self._ptr };
 348         &mut inner.value
 349     }
 350 }
 351
 352 #[experimental = "Deref is experimental."]
 353 impl<T> Deref<T> for Rc<T> {
 354     #[inline(always)]
 355     fn deref(&self) -> &T {
 356         &self.inner().value
 357     }
 358 }
 359
 360 #[unsafe_destructor]
 361 #[experimental = "Drop is experimental."]
 362 impl<T> Drop for Rc<T> {
 363     /// Drops the `Rc<T>`.
 364     ///
 365     /// This will decrement the strong reference count. If the strong reference count becomes zero
 366     /// and the only other references are `Weak<T>` ones, `drop`s the inner value.
 367     ///
 368     /// # Examples
 369     ///
 370     /// ```
 371     /// use std::rc::Rc;
 372     ///
 373     /// {
 374     ///     let five = Rc::new(5i);
 375     ///
 376     ///     // stuff
 377     ///
 378     ///     drop(five); // explict drop
 379     /// }
 380     /// {
 381     ///     let five = Rc::new(5i);
 382     ///
 383     ///     // stuff
 384     ///
 385     /// } // implicit drop
 386     /// ```
 387     fn drop(&mut self) {
 388         unsafe {
 389             if !self._ptr.is_null() {
 390                 self.dec_strong();
 391                 if self.strong() == 0 {
 392                     ptr::read(&**self); // destroy the contained object
 393
 394                     // remove the implicit "strong weak" pointer now
 395                     // that we've destroyed the contents.
 396                     self.dec_weak();
 397
 398                     if self.weak() == 0 {
 399                         deallocate(self._ptr as *mut u8, size_of::<RcBox<T>>(),
 400                                    min_align_of::<RcBox<T>>())
 401                     }
 402                 }
 403             }
 404         }
 405     }
 406 }
 407
 408 #[unstable = "Clone is unstable."]
 409 impl<T> Clone for Rc<T> {
 410     /// Makes a clone of the `Rc<T>`.
 411     ///
 412     /// This increases the strong reference count.
 413     ///
 414     /// # Examples
 415     ///
 416     /// ```
 417     /// use std::rc::Rc;
 418     ///
 419     /// let five = Rc::new(5i);
 420     ///
 421     /// five.clone();
 422     /// ```
 423     #[inline]
 424     fn clone(&self) -> Rc<T> {
 425         self.inc_strong();
 426         Rc { _ptr: self._ptr, _nosend: marker::NoSend, _noshare: marker::NoSync }
 427     }
 428 }
 429
 430 #[stable]
 431 impl<T: Default> Default for Rc<T> {
 432     /// Creates a new `Rc<T>`, with the `Default` value for `T`.
 433     ///
 434     /// # Examples
 435     ///
 436     /// ```
 437     /// use std::rc::Rc;
 438     /// use std::default::Default;
 439     ///
 440     /// let x: Rc<int> = Default::default();
 441     /// ```
 442     #[inline]
 443     fn default() -> Rc<T> {
 444         Rc::new(Default::default())
 445     }
 446 }
 447
 448 #[unstable = "PartialEq is unstable."]
 449 impl<T: PartialEq> PartialEq for Rc<T> {
 450     /// Equality for two `Rc<T>`s.
 451     ///
 452     /// Two `Rc<T>`s are equal if their inner value are equal.
 453     ///
 454     /// # Examples
 455     ///
 456     /// ```
 457     /// use std::rc::Rc;
 458     ///
 459     /// let five = Rc::new(5i);
 460     ///
 461     /// five == Rc::new(5i);
 462     /// ```
 463     #[inline(always)]
 464     fn eq(&self, other: &Rc<T>) -> bool { **self == **other }
 465
 466     /// Inequality for two `Rc<T>`s.
 467     ///
 468     /// Two `Rc<T>`s are unequal if their inner value are unequal.
 469     ///
 470     /// # Examples
 471     ///
 472     /// ```
 473     /// use std::rc::Rc;
 474     ///
 475     /// let five = Rc::new(5i);
 476     ///
 477     /// five != Rc::new(5i);
 478     /// ```
 479     #[inline(always)]
 480     fn ne(&self, other: &Rc<T>) -> bool { **self != **other }
 481 }
 482
 483 #[unstable = "Eq is unstable."]
 484 impl<T: Eq> Eq for Rc<T> {}
 485
 486 #[unstable = "PartialOrd is unstable."]
 487 impl<T: PartialOrd> PartialOrd for Rc<T> {
 488     /// Partial comparison for two `Rc<T>`s.
 489     ///
 490     /// The two are compared by calling `partial_cmp()` on their inner values.
 491     ///
 492     /// # Examples
 493     ///
 494     /// ```
 495     /// use std::rc::Rc;
 496     ///
 497     /// let five = Rc::new(5i);
 498     ///
 499     /// five.partial_cmp(&Rc::new(5i));
 500     /// ```
 501     #[inline(always)]
 502     fn partial_cmp(&self, other: &Rc<T>) -> Option<Ordering> {
 503         (**self).partial_cmp(&**other)
 504     }
 505
 506     /// Less-than comparison for two `Rc<T>`s.
 507     ///
 508     /// The two are compared by calling `<` on their inner values.
 509     ///
 510     /// # Examples
 511     ///
 512     /// ```
 513     /// use std::rc::Rc;
 514     ///
 515     /// let five = Rc::new(5i);
 516     ///
 517     /// five < Rc::new(5i);
 518     /// ```
 519     #[inline(always)]
 520     fn lt(&self, other: &Rc<T>) -> bool { **self < **other }
 521
 522     /// 'Less-than or equal to' comparison for two `Rc<T>`s.
 523     ///
 524     /// The two are compared by calling `<=` on their inner values.
 525     ///
 526     /// # Examples
 527     ///
 528     /// ```
 529     /// use std::rc::Rc;
 530     ///
 531     /// let five = Rc::new(5i);
 532     ///
 533     /// five <= Rc::new(5i);
 534     /// ```
 535     #[inline(always)]
 536     fn le(&self, other: &Rc<T>) -> bool { **self <= **other }
 537
 538     /// Greater-than comparison for two `Rc<T>`s.
 539     ///
 540     /// The two are compared by calling `>` on their inner values.
 541     ///
 542     /// # Examples
 543     ///
 544     /// ```
 545     /// use std::rc::Rc;
 546     ///
 547     /// let five = Rc::new(5i);
 548     ///
 549     /// five > Rc::new(5i);
 550     /// ```
 551     #[inline(always)]
 552     fn gt(&self, other: &Rc<T>) -> bool { **self > **other }
 553
 554     /// 'Greater-than or equal to' comparison for two `Rc<T>`s.
 555     ///
 556     /// The two are compared by calling `>=` on their inner values.
 557     ///
 558     /// # Examples
 559     ///
 560     /// ```
 561     /// use std::rc::Rc;
 562     ///
 563     /// let five = Rc::new(5i);
 564     ///
 565     /// five >= Rc::new(5i);
 566     /// ```
 567     #[inline(always)]
 568     fn ge(&self, other: &Rc<T>) -> bool { **self >= **other }
 569 }
 570
 571 #[unstable = "Ord is unstable."]
 572 impl<T: Ord> Ord for Rc<T> {
 573     /// Comparison for two `Rc<T>`s.
 574     ///
 575     /// The two are compared by calling `cmp()` on their inner values.
 576     ///
 577     /// # Examples
 578     ///
 579     /// ```
 580     /// use std::rc::Rc;
 581     ///
 582     /// let five = Rc::new(5i);
 583     ///
 584     /// five.partial_cmp(&Rc::new(5i));
 585     /// ```
 586     #[inline]
 587     fn cmp(&self, other: &Rc<T>) -> Ordering { (**self).cmp(&**other) }
 588 }
 589
 590 #[experimental = "Show is experimental."]
 591 impl<T: fmt::Show> fmt::Show for Rc<T> {
 592     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 593         (**self).fmt(f)
 594     }
 595 }
 596
 597 /// A weak version of `Rc<T>`.
 598 ///
 599 /// Weak references do not count when determining if the inner value should be dropped.
 600 ///
 601 /// See the [module level documentation](../index.html) for more.
 602 #[unsafe_no_drop_flag]
 603 #[experimental = "Weak pointers may not belong in this module."]
 604 pub struct Weak<T> {
 605     // FIXME #12808: strange names to try to avoid interfering with
 606     // field accesses of the contained type via Deref
 607     _ptr: *mut RcBox<T>,
 608     _nosend: marker::NoSend,
 609     _noshare: marker::NoSync
 610 }
 611
 612 #[experimental = "Weak pointers may not belong in this module."]
 613 impl<T> Weak<T> {
 614     /// Upgrades a weak reference to a strong reference.
 615     ///
 616     /// Upgrades the `Weak<T>` reference to an `Rc<T>`, if possible.
 617     ///
 618     /// Returns `None` if there were no strong references and the data was destroyed.
 619     ///
 620     /// # Examples
 621     ///
 622     /// ```
 623     /// use std::rc::Rc;
 624     ///
 625     /// let five = Rc::new(5i);
 626     ///
 627     /// let weak_five = five.downgrade();
 628     ///
 629     /// let strong_five: Option<Rc<_>> = weak_five.upgrade();
 630     /// ```
 631     pub fn upgrade(&self) -> Option<Rc<T>> {
 632         if self.strong() == 0 {
 633             None
 634         } else {
 635             self.inc_strong();
 636             Some(Rc { _ptr: self._ptr, _nosend: marker::NoSend, _noshare: marker::NoSync })
 637         }
 638     }
 639 }
 640
 641 #[unsafe_destructor]
 642 #[experimental = "Weak pointers may not belong in this module."]
 643 impl<T> Drop for Weak<T> {
 644     /// Drops the `Weak<T>`.
 645     ///
 646     /// This will decrement the weak reference count.
 647     ///
 648     /// # Examples
 649     ///
 650     /// ```
 651     /// use std::rc::Rc;
 652     ///
 653     /// {
 654     ///     let five = Rc::new(5i);
 655     ///     let weak_five = five.downgrade();
 656     ///
 657     ///     // stuff
 658     ///
 659     ///     drop(weak_five); // explict drop
 660     /// }
 661     /// {
 662     ///     let five = Rc::new(5i);
 663     ///     let weak_five = five.downgrade();
 664     ///
 665     ///     // stuff
 666     ///
 667     /// } // implicit drop
 668     /// ```
 669     fn drop(&mut self) {
 670         unsafe {
 671             if !self._ptr.is_null() {
 672                 self.dec_weak();
 673                 // the weak count starts at 1, and will only go to
 674                 // zero if all the strong pointers have disappeared.
 675                 if self.weak() == 0 {
 676                     deallocate(self._ptr as *mut u8, size_of::<RcBox<T>>(),
 677                                min_align_of::<RcBox<T>>())
 678                 }
 679             }
 680         }
 681     }
 682 }
 683
 684 #[experimental = "Weak pointers may not belong in this module."]
 685 impl<T> Clone for Weak<T> {
 686     /// Makes a clone of the `Weak<T>`.
 687     ///
 688     /// This increases the weak reference count.
 689     ///
 690     /// # Examples
 691     ///
 692     /// ```
 693     /// use std::rc::Rc;
 694     ///
 695     /// let weak_five = Rc::new(5i).downgrade();
 696     ///
 697     /// weak_five.clone();
 698     /// ```
 699     #[inline]
 700     fn clone(&self) -> Weak<T> {
 701         self.inc_weak();
 702         Weak { _ptr: self._ptr, _nosend: marker::NoSend, _noshare: marker::NoSync }
 703     }
 704 }
 705
 706 #[doc(hidden)]
 707 trait RcBoxPtr<T> {
 708     fn inner(&self) -> &RcBox<T>;
 709
 710     #[inline]
 711     fn strong(&self) -> uint { self.inner().strong.get() }
 712
 713     #[inline]
 714     fn inc_strong(&self) { self.inner().strong.set(self.strong() + 1); }
 715
 716     #[inline]
 717     fn dec_strong(&self) { self.inner().strong.set(self.strong() - 1); }
 718
 719     #[inline]
 720     fn weak(&self) -> uint { self.inner().weak.get() }
 721
 722     #[inline]
 723     fn inc_weak(&self) { self.inner().weak.set(self.weak() + 1); }
 724
 725     #[inline]
 726     fn dec_weak(&self) { self.inner().weak.set(self.weak() - 1); }
 727 }
 728
 729 impl<T> RcBoxPtr<T> for Rc<T> {
 730     #[inline(always)]
 731     fn inner(&self) -> &RcBox<T> { unsafe { &(*self._ptr) } }
 732 }
 733
 734 impl<T> RcBoxPtr<T> for Weak<T> {
 735     #[inline(always)]
 736     fn inner(&self) -> &RcBox<T> { unsafe { &(*self._ptr) } }
 737 }
 738
 739 #[cfg(test)]
 740 #[allow(experimental)]
 741 mod tests {
 742     use super::{Rc, Weak, weak_count, strong_count};
 743     use std::cell::RefCell;
 744     use std::option::Option;
 745     use std::option::Option::{Some, None};
 746     use std::result::Result::{Err, Ok};
 747     use std::mem::drop;
 748     use std::clone::Clone;
 749
 750     #[test]
 751     fn test_clone() {
 752         let x = Rc::new(RefCell::new(5i));
 753         let y = x.clone();
 754         *x.borrow_mut() = 20;
 755         assert_eq!(*y.borrow(), 20);
 756     }
 757
 758     #[test]
 759     fn test_simple() {
 760         let x = Rc::new(5i);
 761         assert_eq!(*x, 5);
 762     }
 763
 764     #[test]
 765     fn test_simple_clone() {
 766         let x = Rc::new(5i);
 767         let y = x.clone();
 768         assert_eq!(*x, 5);
 769         assert_eq!(*y, 5);
 770     }
 771
 772     #[test]
 773     fn test_destructor() {
 774         let x = Rc::new(box 5i);
 775         assert_eq!(**x, 5);
 776     }
 777
 778     #[test]
 779     fn test_live() {
 780         let x = Rc::new(5i);
 781         let y = x.downgrade();
 782         assert!(y.upgrade().is_some());
 783     }
 784
 785     #[test]
 786     fn test_dead() {
 787         let x = Rc::new(5i);
 788         let y = x.downgrade();
 789         drop(x);
 790         assert!(y.upgrade().is_none());
 791     }
 792
 793     #[test]
 794     fn weak_self_cyclic() {
 795         struct Cycle {
 796             x: RefCell<Option<Weak<Cycle>>>
 797         }
 798
 799         let a = Rc::new(Cycle { x: RefCell::new(None) });
 800         let b = a.clone().downgrade();
 801         *a.x.borrow_mut() = Some(b);
 802
 803         // hopefully we don't double-free (or leak)...
 804     }
 805
 806     #[test]
 807     fn is_unique() {
 808         let x = Rc::new(3u);
 809         assert!(super::is_unique(&x));
 810         let y = x.clone();
 811         assert!(!super::is_unique(&x));
 812         drop(y);
 813         assert!(super::is_unique(&x));
 814         let w = x.downgrade();
 815         assert!(!super::is_unique(&x));
 816         drop(w);
 817         assert!(super::is_unique(&x));
 818     }
 819
 820     #[test]
 821     fn test_strong_count() {
 822         let a = Rc::new(0u32);
 823         assert!(strong_count(&a) == 1);
 824         let w = a.downgrade();
 825         assert!(strong_count(&a) == 1);
 826         let b = w.upgrade().expect("upgrade of live rc failed");
 827         assert!(strong_count(&b) == 2);
 828         assert!(strong_count(&a) == 2);
 829         drop(w);
 830         drop(a);
 831         assert!(strong_count(&b) == 1);
 832         let c = b.clone();
 833         assert!(strong_count(&b) == 2);
 834         assert!(strong_count(&c) == 2);
 835     }
 836
 837     #[test]
 838     fn test_weak_count() {
 839         let a = Rc::new(0u32);
 840         assert!(strong_count(&a) == 1);
 841         assert!(weak_count(&a) == 0);
 842         let w = a.downgrade();
 843         assert!(strong_count(&a) == 1);
 844         assert!(weak_count(&a) == 1);
 845         drop(w);
 846         assert!(strong_count(&a) == 1);
 847         assert!(weak_count(&a) == 0);
 848         let c = a.clone();
 849         assert!(strong_count(&a) == 2);
 850         assert!(weak_count(&a) == 0);
 851         drop(c);
 852     }
 853
 854     #[test]
 855     fn try_unwrap() {
 856         let x = Rc::new(3u);
 857         assert_eq!(super::try_unwrap(x), Ok(3u));
 858         let x = Rc::new(4u);
 859         let _y = x.clone();
 860         assert_eq!(super::try_unwrap(x), Err(Rc::new(4u)));
 861         let x = Rc::new(5u);
 862         let _w = x.downgrade();
 863         assert_eq!(super::try_unwrap(x), Err(Rc::new(5u)));
 864     }
 865
 866     #[test]
 867     fn get_mut() {
 868         let mut x = Rc::new(3u);
 869         *super::get_mut(&mut x).unwrap() = 4u;
 870         assert_eq!(*x, 4u);
 871         let y = x.clone();
 872         assert!(super::get_mut(&mut x).is_none());
 873         drop(y);
 874         assert!(super::get_mut(&mut x).is_some());
 875         let _w = x.downgrade();
 876         assert!(super::get_mut(&mut x).is_none());
 877     }
 878
 879     #[test]
 880     fn test_cowrc_clone_make_unique() {
 881         let mut cow0 = Rc::new(75u);
 882         let mut cow1 = cow0.clone();
 883         let mut cow2 = cow1.clone();
 884
 885         assert!(75 == *cow0.make_unique());
 886         assert!(75 == *cow1.make_unique());
 887         assert!(75 == *cow2.make_unique());
 888
 889         *cow0.make_unique() += 1;
 890         *cow1.make_unique() += 2;
 891         *cow2.make_unique() += 3;
 892
 893         assert!(76 == *cow0);
 894         assert!(77 == *cow1);
 895         assert!(78 == *cow2);
 896
 897         // none should point to the same backing memory
 898         assert!(*cow0 != *cow1);
 899         assert!(*cow0 != *cow2);
 900         assert!(*cow1 != *cow2);
 901     }
 902
 903     #[test]
 904     fn test_cowrc_clone_unique2() {
 905         let mut cow0 = Rc::new(75u);
 906         let cow1 = cow0.clone();
 907         let cow2 = cow1.clone();
 908
 909         assert!(75 == *cow0);
 910         assert!(75 == *cow1);
 911         assert!(75 == *cow2);
 912
 913         *cow0.make_unique() += 1;
 914
 915         assert!(76 == *cow0);
 916         assert!(75 == *cow1);
 917         assert!(75 == *cow2);
 918
 919         // cow1 and cow2 should share the same contents
 920         // cow0 should have a unique reference
 921         assert!(*cow0 != *cow1);
 922         assert!(*cow0 != *cow2);
 923         assert!(*cow1 == *cow2);
 924     }
 925
 926     #[test]
 927     fn test_cowrc_clone_weak() {
 928         let mut cow0 = Rc::new(75u);
 929         let cow1_weak = cow0.downgrade();
 930
 931         assert!(75 == *cow0);
 932         assert!(75 == *cow1_weak.upgrade().unwrap());
 933
 934         *cow0.make_unique() += 1;
 935
 936         assert!(76 == *cow0);
 937         assert!(cow1_weak.upgrade().is_none());
 938     }
 939
 940 }