src/liballoc/arc.rs

   1 // Copyright 2012-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 #![stable(feature = "rust1", since = "1.0.0")]
  12
  13 //! Threadsafe reference-counted boxes (the `Arc<T>` type).
  14 //!
  15 //! The `Arc<T>` type provides shared ownership of an immutable value.
  16 //! Destruction is deterministic, and will occur as soon as the last owner is
  17 //! gone. It is marked as `Send` because it uses atomic reference counting.
  18 //!
  19 //! If you do not need thread-safety, and just need shared ownership, consider
  20 //! the [`Rc<T>` type](../rc/struct.Rc.html). It is the same as `Arc<T>`, but
  21 //! does not use atomics, making it both thread-unsafe as well as significantly
  22 //! faster when updating the reference count.
  23 //!
  24 //! The `downgrade` method can be used to create a non-owning `Weak<T>` pointer
  25 //! to the box. A `Weak<T>` pointer can be upgraded to an `Arc<T>` pointer, but
  26 //! will return `None` if the value has already been dropped.
  27 //!
  28 //! For example, a tree with parent pointers can be represented by putting the
  29 //! nodes behind strong `Arc<T>` pointers, and then storing the parent pointers
  30 //! as `Weak<T>` pointers.
  31 //!
  32 //! # Examples
  33 //!
  34 //! Sharing some immutable data between threads:
  35 //!
  36 //! ```no_run
  37 //! use std::sync::Arc;
  38 //! use std::thread;
  39 //!
  40 //! let five = Arc::new(5);
  41 //!
  42 //! for _ in 0..10 {
  43 //!     let five = five.clone();
  44 //!
  45 //!     thread::spawn(move || {
  46 //!         println!("{:?}", five);
  47 //!     });
  48 //! }
  49 //! ```
  50 //!
  51 //! Sharing mutable data safely between threads with a `Mutex`:
  52 //!
  53 //! ```no_run
  54 //! use std::sync::{Arc, Mutex};
  55 //! use std::thread;
  56 //!
  57 //! let five = Arc::new(Mutex::new(5));
  58 //!
  59 //! for _ in 0..10 {
  60 //!     let five = five.clone();
  61 //!
  62 //!     thread::spawn(move || {
  63 //!         let mut number = five.lock().unwrap();
  64 //!
  65 //!         *number += 1;
  66 //!
  67 //!         println!("{}", *number); // prints 6
  68 //!     });
  69 //! }
  70 //! ```
  71
  72 use boxed::Box;
  73
  74 use core::prelude::*;
  75
  76 use core::atomic;
  77 use core::atomic::Ordering::{Relaxed, Release, Acquire, SeqCst};
  78 use core::fmt;
  79 use core::cmp::Ordering;
  80 use core::mem::{min_align_of_val, size_of_val};
  81 use core::intrinsics::drop_in_place;
  82 use core::mem;
  83 use core::nonzero::NonZero;
  84 use core::ops::{Deref, CoerceUnsized};
  85 use core::marker::Unsize;
  86 use core::hash::{Hash, Hasher};
  87 use heap::deallocate;
  88
  89 /// An atomically reference counted wrapper for shared state.
  90 ///
  91 /// # Examples
  92 ///
  93 /// In this example, a large vector of floats is shared between several threads.
  94 /// With simple pipes, without `Arc`, a copy would have to be made for each
  95 /// thread.
  96 ///
  97 /// When you clone an `Arc<T>`, it will create another pointer to the data and
  98 /// increase the reference counter.
  99 ///
 100 /// ```
 101 /// # #![feature(alloc, core)]
 102 /// use std::sync::Arc;
 103 /// use std::thread;
 104 ///
 105 /// fn main() {
 106 ///     let numbers: Vec<_> = (0..100u32).collect();
 107 ///     let shared_numbers = Arc::new(numbers);
 108 ///
 109 ///     for _ in 0..10 {
 110 ///         let child_numbers = shared_numbers.clone();
 111 ///
 112 ///         thread::spawn(move || {
 113 ///             let local_numbers = &child_numbers[..];
 114 ///
 115 ///             // Work with the local numbers
 116 ///         });
 117 ///     }
 118 /// }
 119 /// ```
 120 #[unsafe_no_drop_flag]
 121 #[stable(feature = "rust1", since = "1.0.0")]
 122 pub struct Arc<T: ?Sized> {
 123     // FIXME #12808: strange name to try to avoid interfering with
 124     // field accesses of the contained type via Deref
 125     _ptr: NonZero<*mut ArcInner<T>>,
 126 }
 127
 128 unsafe impl<T: ?Sized + Sync + Send> Send for Arc<T> { }
 129 unsafe impl<T: ?Sized + Sync + Send> Sync for Arc<T> { }
 130
 131 impl<T: ?Sized + Unsize<U>, U: ?Sized> CoerceUnsized<Arc<U>> for Arc<T> {}
 132
 133 /// A weak pointer to an `Arc`.
 134 ///
 135 /// Weak pointers will not keep the data inside of the `Arc` alive, and can be
 136 /// used to break cycles between `Arc` pointers.
 137 #[unsafe_no_drop_flag]
 138 #[unstable(feature = "alloc",
 139            reason = "Weak pointers may not belong in this module.")]
 140 pub struct Weak<T: ?Sized> {
 141     // FIXME #12808: strange name to try to avoid interfering with
 142     // field accesses of the contained type via Deref
 143     _ptr: NonZero<*mut ArcInner<T>>,
 144 }
 145
 146 unsafe impl<T: ?Sized + Sync + Send> Send for Weak<T> { }
 147 unsafe impl<T: ?Sized + Sync + Send> Sync for Weak<T> { }
 148
 149 #[stable(feature = "rust1", since = "1.0.0")]
 150 impl<T: ?Sized + fmt::Debug> fmt::Debug for Weak<T> {
 151     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 152         write!(f, "(Weak)")
 153     }
 154 }
 155
 156 struct ArcInner<T: ?Sized> {
 157     strong: atomic::AtomicUsize,
 158     weak: atomic::AtomicUsize,
 159     data: T,
 160 }
 161
 162 unsafe impl<T: ?Sized + Sync + Send> Send for ArcInner<T> {}
 163 unsafe impl<T: ?Sized + Sync + Send> Sync for ArcInner<T> {}
 164
 165 impl<T> Arc<T> {
 166     /// Constructs a new `Arc<T>`.
 167     ///
 168     /// # Examples
 169     ///
 170     /// ```
 171     /// use std::sync::Arc;
 172     ///
 173     /// let five = Arc::new(5);
 174     /// ```
 175     #[inline]
 176     #[stable(feature = "rust1", since = "1.0.0")]
 177     pub fn new(data: T) -> Arc<T> {
 178         // Start the weak pointer count as 1 which is the weak pointer that's
 179         // held by all the strong pointers (kinda), see std/rc.rs for more info
 180         let x: Box<_> = box ArcInner {
 181             strong: atomic::AtomicUsize::new(1),
 182             weak: atomic::AtomicUsize::new(1),
 183             data: data,
 184         };
 185         Arc { _ptr: unsafe { NonZero::new(mem::transmute(x)) } }
 186     }
 187 }
 188
 189 impl<T: ?Sized> Arc<T> {
 190     /// Downgrades the `Arc<T>` to a `Weak<T>` reference.
 191     ///
 192     /// # Examples
 193     ///
 194     /// ```
 195     /// # #![feature(alloc)]
 196     /// use std::sync::Arc;
 197     ///
 198     /// let five = Arc::new(5);
 199     ///
 200     /// let weak_five = five.downgrade();
 201     /// ```
 202     #[unstable(feature = "alloc",
 203                reason = "Weak pointers may not belong in this module.")]
 204     pub fn downgrade(&self) -> Weak<T> {
 205         // See the clone() impl for why this is relaxed
 206         self.inner().weak.fetch_add(1, Relaxed);
 207         Weak { _ptr: self._ptr }
 208     }
 209 }
 210
 211 impl<T: ?Sized> Arc<T> {
 212     #[inline]
 213     fn inner(&self) -> &ArcInner<T> {
 214         // This unsafety is ok because while this arc is alive we're guaranteed
 215         // that the inner pointer is valid. Furthermore, we know that the
 216         // `ArcInner` structure itself is `Sync` because the inner data is
 217         // `Sync` as well, so we're ok loaning out an immutable pointer to these
 218         // contents.
 219         unsafe { &**self._ptr }
 220     }
 221
 222     // Non-inlined part of `drop`.
 223     #[inline(never)]
 224     unsafe fn drop_slow(&mut self) {
 225         let ptr = *self._ptr;
 226
 227         // Destroy the data at this time, even though we may not free the box
 228         // allocation itself (there may still be weak pointers lying around).
 229         drop_in_place(&mut (*ptr).data);
 230
 231         if self.inner().weak.fetch_sub(1, Release) == 1 {
 232             atomic::fence(Acquire);
 233             deallocate(ptr as *mut u8, size_of_val(&*ptr), min_align_of_val(&*ptr))
 234         }
 235     }
 236 }
 237
 238 /// Get the number of weak references to this value.
 239 #[inline]
 240 #[unstable(feature = "alloc")]
 241 pub fn weak_count<T: ?Sized>(this: &Arc<T>) -> usize { this.inner().weak.load(SeqCst) - 1 }
 242
 243 /// Get the number of strong references to this value.
 244 #[inline]
 245 #[unstable(feature = "alloc")]
 246 pub fn strong_count<T: ?Sized>(this: &Arc<T>) -> usize { this.inner().strong.load(SeqCst) }
 247
 248
 249 /// Returns a mutable reference to the contained value if the `Arc<T>` is unique.
 250 ///
 251 /// Returns `None` if the `Arc<T>` is not unique.
 252 ///
 253 /// This function is marked **unsafe** because it is racy if weak pointers
 254 /// are active.
 255 ///
 256 /// # Examples
 257 ///
 258 /// ```
 259 /// # #![feature(alloc)]
 260 /// extern crate alloc;
 261 /// # fn main() {
 262 /// use alloc::arc::{Arc, get_mut};
 263 ///
 264 /// # unsafe {
 265 /// let mut x = Arc::new(3);
 266 /// *get_mut(&mut x).unwrap() = 4;
 267 /// assert_eq!(*x, 4);
 268 ///
 269 /// let _y = x.clone();
 270 /// assert!(get_mut(&mut x).is_none());
 271 /// # }
 272 /// # }
 273 /// ```
 274 #[inline]
 275 #[unstable(feature = "alloc")]
 276 pub unsafe fn get_mut<T: ?Sized>(this: &mut Arc<T>) -> Option<&mut T> {
 277     // FIXME(#24880) potential race with upgraded weak pointers here
 278     if strong_count(this) == 1 && weak_count(this) == 0 {
 279         // This unsafety is ok because we're guaranteed that the pointer
 280         // returned is the *only* pointer that will ever be returned to T. Our
 281         // reference count is guaranteed to be 1 at this point, and we required
 282         // the Arc itself to be `mut`, so we're returning the only possible
 283         // reference to the inner data.
 284         let inner = &mut **this._ptr;
 285         Some(&mut inner.data)
 286     } else {
 287         None
 288     }
 289 }
 290
 291 #[stable(feature = "rust1", since = "1.0.0")]
 292 impl<T: ?Sized> Clone for Arc<T> {
 293     /// Makes a clone of the `Arc<T>`.
 294     ///
 295     /// This increases the strong reference count.
 296     ///
 297     /// # Examples
 298     ///
 299     /// ```
 300     /// # #![feature(alloc)]
 301     /// use std::sync::Arc;
 302     ///
 303     /// let five = Arc::new(5);
 304     ///
 305     /// five.clone();
 306     /// ```
 307     #[inline]
 308     fn clone(&self) -> Arc<T> {
 309         // Using a relaxed ordering is alright here, as knowledge of the
 310         // original reference prevents other threads from erroneously deleting
 311         // the object.
 312         //
 313         // As explained in the [Boost documentation][1], Increasing the
 314         // reference counter can always be done with memory_order_relaxed: New
 315         // references to an object can only be formed from an existing
 316         // reference, and passing an existing reference from one thread to
 317         // another must already provide any required synchronization.
 318         //
 319         // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
 320         self.inner().strong.fetch_add(1, Relaxed);
 321         Arc { _ptr: self._ptr }
 322     }
 323 }
 324
 325 #[stable(feature = "rust1", since = "1.0.0")]
 326 impl<T: ?Sized> Deref for Arc<T> {
 327     type Target = T;
 328
 329     #[inline]
 330     fn deref(&self) -> &T {
 331         &self.inner().data
 332     }
 333 }
 334
 335 impl<T: Clone> Arc<T> {
 336     /// Make a mutable reference from the given `Arc<T>`.
 337     ///
 338     /// This is also referred to as a copy-on-write operation because the inner
 339     /// data is cloned if the reference count is greater than one.
 340     ///
 341     /// This method is marked **unsafe** because it is racy if weak pointers
 342     /// are active.
 343     ///
 344     /// # Examples
 345     ///
 346     /// ```
 347     /// # #![feature(alloc)]
 348     /// use std::sync::Arc;
 349     ///
 350     /// # unsafe {
 351     /// let mut five = Arc::new(5);
 352     ///
 353     /// let mut_five = five.make_unique();
 354     /// # }
 355     /// ```
 356     #[inline]
 357     #[unstable(feature = "alloc")]
 358     pub unsafe fn make_unique(&mut self) -> &mut T {
 359         // FIXME(#24880) potential race with upgraded weak pointers here
 360         //
 361         // Note that we hold a strong reference, which also counts as a weak
 362         // reference, so we only clone if there is an additional reference of
 363         // either kind.
 364         if self.inner().strong.load(SeqCst) != 1 ||
 365            self.inner().weak.load(SeqCst) != 1 {
 366             *self = Arc::new((**self).clone())
 367         }
 368         // As with `get_mut()`, the unsafety is ok because our reference was
 369         // either unique to begin with, or became one upon cloning the contents.
 370         let inner = &mut **self._ptr;
 371         &mut inner.data
 372     }
 373 }
 374
 375 #[stable(feature = "rust1", since = "1.0.0")]
 376 impl<T: ?Sized> Drop for Arc<T> {
 377     /// Drops the `Arc<T>`.
 378     ///
 379     /// This will decrement the strong reference count. If the strong reference
 380     /// count becomes zero and the only other references are `Weak<T>` ones,
 381     /// `drop`s the inner value.
 382     ///
 383     /// # Examples
 384     ///
 385     /// ```
 386     /// # #![feature(alloc)]
 387     /// use std::sync::Arc;
 388     ///
 389     /// {
 390     ///     let five = Arc::new(5);
 391     ///
 392     ///     // stuff
 393     ///
 394     ///     drop(five); // explicit drop
 395     /// }
 396     /// {
 397     ///     let five = Arc::new(5);
 398     ///
 399     ///     // stuff
 400     ///
 401     /// } // implicit drop
 402     /// ```
 403     #[inline]
 404     fn drop(&mut self) {
 405         // This structure has #[unsafe_no_drop_flag], so this drop glue may run
 406         // more than once (but it is guaranteed to be zeroed after the first if
 407         // it's run more than once)
 408         let ptr = *self._ptr;
 409         // if ptr.is_null() { return }
 410         if ptr as *mut u8 as usize == 0 || ptr as *mut u8 as usize == mem::POST_DROP_USIZE {
 411             return
 412         }
 413
 414         // Because `fetch_sub` is already atomic, we do not need to synchronize
 415         // with other threads unless we are going to delete the object. This
 416         // same logic applies to the below `fetch_sub` to the `weak` count.
 417         if self.inner().strong.fetch_sub(1, Release) != 1 { return }
 418
 419         // This fence is needed to prevent reordering of use of the data and
 420         // deletion of the data.  Because it is marked `Release`, the decreasing
 421         // of the reference count synchronizes with this `Acquire` fence. This
 422         // means that use of the data happens before decreasing the reference
 423         // count, which happens before this fence, which happens before the
 424         // deletion of the data.
 425         //
 426         // As explained in the [Boost documentation][1],
 427         //
 428         // > It is important to enforce any possible access to the object in one
 429         // > thread (through an existing reference) to *happen before* deleting
 430         // > the object in a different thread. This is achieved by a "release"
 431         // > operation after dropping a reference (any access to the object
 432         // > through this reference must obviously happened before), and an
 433         // > "acquire" operation before deleting the object.
 434         //
 435         // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
 436         atomic::fence(Acquire);
 437
 438         unsafe {
 439             self.drop_slow()
 440         }
 441     }
 442 }
 443
 444 #[unstable(feature = "alloc",
 445            reason = "Weak pointers may not belong in this module.")]
 446 impl<T: ?Sized> Weak<T> {
 447     /// Upgrades a weak reference to a strong reference.
 448     ///
 449     /// Upgrades the `Weak<T>` reference to an `Arc<T>`, if possible.
 450     ///
 451     /// Returns `None` if there were no strong references and the data was
 452     /// destroyed.
 453     ///
 454     /// # Examples
 455     ///
 456     /// ```
 457     /// # #![feature(alloc)]
 458     /// use std::sync::Arc;
 459     ///
 460     /// let five = Arc::new(5);
 461     ///
 462     /// let weak_five = five.downgrade();
 463     ///
 464     /// let strong_five: Option<Arc<_>> = weak_five.upgrade();
 465     /// ```
 466     pub fn upgrade(&self) -> Option<Arc<T>> {
 467         // We use a CAS loop to increment the strong count instead of a
 468         // fetch_add because once the count hits 0 it must never be above 0.
 469         let inner = self.inner();
 470         loop {
 471             let n = inner.strong.load(SeqCst);
 472             if n == 0 { return None }
 473             let old = inner.strong.compare_and_swap(n, n + 1, SeqCst);
 474             if old == n { return Some(Arc { _ptr: self._ptr }) }
 475         }
 476     }
 477
 478     #[inline]
 479     fn inner(&self) -> &ArcInner<T> {
 480         // See comments above for why this is "safe"
 481         unsafe { &**self._ptr }
 482     }
 483 }
 484
 485 #[unstable(feature = "alloc",
 486            reason = "Weak pointers may not belong in this module.")]
 487 impl<T: ?Sized> Clone for Weak<T> {
 488     /// Makes a clone of the `Weak<T>`.
 489     ///
 490     /// This increases the weak reference count.
 491     ///
 492     /// # Examples
 493     ///
 494     /// ```
 495     /// # #![feature(alloc)]
 496     /// use std::sync::Arc;
 497     ///
 498     /// let weak_five = Arc::new(5).downgrade();
 499     ///
 500     /// weak_five.clone();
 501     /// ```
 502     #[inline]
 503     fn clone(&self) -> Weak<T> {
 504         // See comments in Arc::clone() for why this is relaxed
 505         self.inner().weak.fetch_add(1, Relaxed);
 506         Weak { _ptr: self._ptr }
 507     }
 508 }
 509
 510 #[stable(feature = "rust1", since = "1.0.0")]
 511 impl<T: ?Sized> Drop for Weak<T> {
 512     /// Drops the `Weak<T>`.
 513     ///
 514     /// This will decrement the weak reference count.
 515     ///
 516     /// # Examples
 517     ///
 518     /// ```
 519     /// # #![feature(alloc)]
 520     /// use std::sync::Arc;
 521     ///
 522     /// {
 523     ///     let five = Arc::new(5);
 524     ///     let weak_five = five.downgrade();
 525     ///
 526     ///     // stuff
 527     ///
 528     ///     drop(weak_five); // explicit drop
 529     /// }
 530     /// {
 531     ///     let five = Arc::new(5);
 532     ///     let weak_five = five.downgrade();
 533     ///
 534     ///     // stuff
 535     ///
 536     /// } // implicit drop
 537     /// ```
 538     fn drop(&mut self) {
 539         let ptr = *self._ptr;
 540
 541         // see comments above for why this check is here
 542         if ptr as *mut u8 as usize == 0 || ptr as *mut u8 as usize == mem::POST_DROP_USIZE {
 543             return
 544         }
 545
 546         // If we find out that we were the last weak pointer, then its time to
 547         // deallocate the data entirely. See the discussion in Arc::drop() about
 548         // the memory orderings
 549         if self.inner().weak.fetch_sub(1, Release) == 1 {
 550             atomic::fence(Acquire);
 551             unsafe { deallocate(ptr as *mut u8,
 552                                 size_of_val(&*ptr),
 553                                 min_align_of_val(&*ptr)) }
 554         }
 555     }
 556 }
 557
 558 #[stable(feature = "rust1", since = "1.0.0")]
 559 impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
 560     /// Equality for two `Arc<T>`s.
 561     ///
 562     /// Two `Arc<T>`s are equal if their inner value are equal.
 563     ///
 564     /// # Examples
 565     ///
 566     /// ```
 567     /// use std::sync::Arc;
 568     ///
 569     /// let five = Arc::new(5);
 570     ///
 571     /// five == Arc::new(5);
 572     /// ```
 573     fn eq(&self, other: &Arc<T>) -> bool { *(*self) == *(*other) }
 574
 575     /// Inequality for two `Arc<T>`s.
 576     ///
 577     /// Two `Arc<T>`s are unequal if their inner value are unequal.
 578     ///
 579     /// # Examples
 580     ///
 581     /// ```
 582     /// use std::sync::Arc;
 583     ///
 584     /// let five = Arc::new(5);
 585     ///
 586     /// five != Arc::new(5);
 587     /// ```
 588     fn ne(&self, other: &Arc<T>) -> bool { *(*self) != *(*other) }
 589 }
 590 #[stable(feature = "rust1", since = "1.0.0")]
 591 impl<T: ?Sized + PartialOrd> PartialOrd for Arc<T> {
 592     /// Partial comparison for two `Arc<T>`s.
 593     ///
 594     /// The two are compared by calling `partial_cmp()` on their inner values.
 595     ///
 596     /// # Examples
 597     ///
 598     /// ```
 599     /// use std::sync::Arc;
 600     ///
 601     /// let five = Arc::new(5);
 602     ///
 603     /// five.partial_cmp(&Arc::new(5));
 604     /// ```
 605     fn partial_cmp(&self, other: &Arc<T>) -> Option<Ordering> {
 606         (**self).partial_cmp(&**other)
 607     }
 608
 609     /// Less-than comparison for two `Arc<T>`s.
 610     ///
 611     /// The two are compared by calling `<` on their inner values.
 612     ///
 613     /// # Examples
 614     ///
 615     /// ```
 616     /// use std::sync::Arc;
 617     ///
 618     /// let five = Arc::new(5);
 619     ///
 620     /// five < Arc::new(5);
 621     /// ```
 622     fn lt(&self, other: &Arc<T>) -> bool { *(*self) < *(*other) }
 623
 624     /// 'Less-than or equal to' comparison for two `Arc<T>`s.
 625     ///
 626     /// The two are compared by calling `<=` on their inner values.
 627     ///
 628     /// # Examples
 629     ///
 630     /// ```
 631     /// use std::sync::Arc;
 632     ///
 633     /// let five = Arc::new(5);
 634     ///
 635     /// five <= Arc::new(5);
 636     /// ```
 637     fn le(&self, other: &Arc<T>) -> bool { *(*self) <= *(*other) }
 638
 639     /// Greater-than comparison for two `Arc<T>`s.
 640     ///
 641     /// The two are compared by calling `>` on their inner values.
 642     ///
 643     /// # Examples
 644     ///
 645     /// ```
 646     /// use std::sync::Arc;
 647     ///
 648     /// let five = Arc::new(5);
 649     ///
 650     /// five > Arc::new(5);
 651     /// ```
 652     fn gt(&self, other: &Arc<T>) -> bool { *(*self) > *(*other) }
 653
 654     /// 'Greater-than or equal to' comparison for two `Arc<T>`s.
 655     ///
 656     /// The two are compared by calling `>=` on their inner values.
 657     ///
 658     /// # Examples
 659     ///
 660     /// ```
 661     /// use std::sync::Arc;
 662     ///
 663     /// let five = Arc::new(5);
 664     ///
 665     /// five >= Arc::new(5);
 666     /// ```
 667     fn ge(&self, other: &Arc<T>) -> bool { *(*self) >= *(*other) }
 668 }
 669 #[stable(feature = "rust1", since = "1.0.0")]
 670 impl<T: ?Sized + Ord> Ord for Arc<T> {
 671     fn cmp(&self, other: &Arc<T>) -> Ordering { (**self).cmp(&**other) }
 672 }
 673 #[stable(feature = "rust1", since = "1.0.0")]
 674 impl<T: ?Sized + Eq> Eq for Arc<T> {}
 675
 676 #[stable(feature = "rust1", since = "1.0.0")]
 677 impl<T: ?Sized + fmt::Display> fmt::Display for Arc<T> {
 678     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 679         fmt::Display::fmt(&**self, f)
 680     }
 681 }
 682
 683 #[stable(feature = "rust1", since = "1.0.0")]
 684 impl<T: ?Sized + fmt::Debug> fmt::Debug for Arc<T> {
 685     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 686         fmt::Debug::fmt(&**self, f)
 687     }
 688 }
 689
 690 #[stable(feature = "rust1", since = "1.0.0")]
 691 impl<T> fmt::Pointer for Arc<T> {
 692     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 693         fmt::Pointer::fmt(&*self._ptr, f)
 694     }
 695 }
 696
 697 #[stable(feature = "rust1", since = "1.0.0")]
 698 impl<T: Default> Default for Arc<T> {
 699     #[stable(feature = "rust1", since = "1.0.0")]
 700     fn default() -> Arc<T> { Arc::new(Default::default()) }
 701 }
 702
 703 #[stable(feature = "rust1", since = "1.0.0")]
 704 impl<T: ?Sized + Hash> Hash for Arc<T> {
 705     fn hash<H: Hasher>(&self, state: &mut H) {
 706         (**self).hash(state)
 707     }
 708 }
 709
 710 #[cfg(test)]
 711 mod tests {
 712     use std::clone::Clone;
 713     use std::sync::mpsc::channel;
 714     use std::mem::drop;
 715     use std::ops::Drop;
 716     use std::option::Option;
 717     use std::option::Option::{Some, None};
 718     use std::sync::atomic;
 719     use std::sync::atomic::Ordering::{Acquire, SeqCst};
 720     use std::thread;
 721     use std::vec::Vec;
 722     use super::{Arc, Weak, get_mut, weak_count, strong_count};
 723     use std::sync::Mutex;
 724
 725     struct Canary(*mut atomic::AtomicUsize);
 726
 727     impl Drop for Canary
 728     {
 729         fn drop(&mut self) {
 730             unsafe {
 731                 match *self {
 732                     Canary(c) => {
 733                         (*c).fetch_add(1, SeqCst);
 734                     }
 735                 }
 736             }
 737         }
 738     }
 739
 740     #[test]
 741     fn manually_share_arc() {
 742         let v = vec!(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
 743         let arc_v = Arc::new(v);
 744
 745         let (tx, rx) = channel();
 746
 747         let _t = thread::spawn(move || {
 748             let arc_v: Arc<Vec<i32>> = rx.recv().unwrap();
 749             assert_eq!((*arc_v)[3], 4);
 750         });
 751
 752         tx.send(arc_v.clone()).unwrap();
 753
 754         assert_eq!((*arc_v)[2], 3);
 755         assert_eq!((*arc_v)[4], 5);
 756     }
 757
 758     #[test]
 759     fn test_arc_get_mut() {
 760         unsafe {
 761             let mut x = Arc::new(3);
 762             *get_mut(&mut x).unwrap() = 4;
 763             assert_eq!(*x, 4);
 764             let y = x.clone();
 765             assert!(get_mut(&mut x).is_none());
 766             drop(y);
 767             assert!(get_mut(&mut x).is_some());
 768             let _w = x.downgrade();
 769             assert!(get_mut(&mut x).is_none());
 770         }
 771     }
 772
 773     #[test]
 774     fn test_cowarc_clone_make_unique() {
 775         unsafe {
 776             let mut cow0 = Arc::new(75);
 777             let mut cow1 = cow0.clone();
 778             let mut cow2 = cow1.clone();
 779
 780             assert!(75 == *cow0.make_unique());
 781             assert!(75 == *cow1.make_unique());
 782             assert!(75 == *cow2.make_unique());
 783
 784             *cow0.make_unique() += 1;
 785             *cow1.make_unique() += 2;
 786             *cow2.make_unique() += 3;
 787
 788             assert!(76 == *cow0);
 789             assert!(77 == *cow1);
 790             assert!(78 == *cow2);
 791
 792             // none should point to the same backing memory
 793             assert!(*cow0 != *cow1);
 794             assert!(*cow0 != *cow2);
 795             assert!(*cow1 != *cow2);
 796         }
 797     }
 798
 799     #[test]
 800     fn test_cowarc_clone_unique2() {
 801         let mut cow0 = Arc::new(75);
 802         let cow1 = cow0.clone();
 803         let cow2 = cow1.clone();
 804
 805         assert!(75 == *cow0);
 806         assert!(75 == *cow1);
 807         assert!(75 == *cow2);
 808
 809         unsafe {
 810             *cow0.make_unique() += 1;
 811         }
 812
 813         assert!(76 == *cow0);
 814         assert!(75 == *cow1);
 815         assert!(75 == *cow2);
 816
 817         // cow1 and cow2 should share the same contents
 818         // cow0 should have a unique reference
 819         assert!(*cow0 != *cow1);
 820         assert!(*cow0 != *cow2);
 821         assert!(*cow1 == *cow2);
 822     }
 823
 824     #[test]
 825     fn test_cowarc_clone_weak() {
 826         let mut cow0 = Arc::new(75);
 827         let cow1_weak = cow0.downgrade();
 828
 829         assert!(75 == *cow0);
 830         assert!(75 == *cow1_weak.upgrade().unwrap());
 831
 832         unsafe {
 833             *cow0.make_unique() += 1;
 834         }
 835
 836         assert!(76 == *cow0);
 837         assert!(cow1_weak.upgrade().is_none());
 838     }
 839
 840     #[test]
 841     fn test_live() {
 842         let x = Arc::new(5);
 843         let y = x.downgrade();
 844         assert!(y.upgrade().is_some());
 845     }
 846
 847     #[test]
 848     fn test_dead() {
 849         let x = Arc::new(5);
 850         let y = x.downgrade();
 851         drop(x);
 852         assert!(y.upgrade().is_none());
 853     }
 854
 855     #[test]
 856     fn weak_self_cyclic() {
 857         struct Cycle {
 858             x: Mutex<Option<Weak<Cycle>>>
 859         }
 860
 861         let a = Arc::new(Cycle { x: Mutex::new(None) });
 862         let b = a.clone().downgrade();
 863         *a.x.lock().unwrap() = Some(b);
 864
 865         // hopefully we don't double-free (or leak)...
 866     }
 867
 868     #[test]
 869     fn drop_arc() {
 870         let mut canary = atomic::AtomicUsize::new(0);
 871         let x = Arc::new(Canary(&mut canary as *mut atomic::AtomicUsize));
 872         drop(x);
 873         assert!(canary.load(Acquire) == 1);
 874     }
 875
 876     #[test]
 877     fn drop_arc_weak() {
 878         let mut canary = atomic::AtomicUsize::new(0);
 879         let arc = Arc::new(Canary(&mut canary as *mut atomic::AtomicUsize));
 880         let arc_weak = arc.downgrade();
 881         assert!(canary.load(Acquire) == 0);
 882         drop(arc);
 883         assert!(canary.load(Acquire) == 1);
 884         drop(arc_weak);
 885     }
 886
 887     #[test]
 888     fn test_strong_count() {
 889         let a = Arc::new(0u32);
 890         assert!(strong_count(&a) == 1);
 891         let w = a.downgrade();
 892         assert!(strong_count(&a) == 1);
 893         let b = w.upgrade().expect("");
 894         assert!(strong_count(&b) == 2);
 895         assert!(strong_count(&a) == 2);
 896         drop(w);
 897         drop(a);
 898         assert!(strong_count(&b) == 1);
 899         let c = b.clone();
 900         assert!(strong_count(&b) == 2);
 901         assert!(strong_count(&c) == 2);
 902     }
 903
 904     #[test]
 905     fn test_weak_count() {
 906         let a = Arc::new(0u32);
 907         assert!(strong_count(&a) == 1);
 908         assert!(weak_count(&a) == 0);
 909         let w = a.downgrade();
 910         assert!(strong_count(&a) == 1);
 911         assert!(weak_count(&a) == 1);
 912         let x = w.clone();
 913         assert!(weak_count(&a) == 2);
 914         drop(w);
 915         drop(x);
 916         assert!(strong_count(&a) == 1);
 917         assert!(weak_count(&a) == 0);
 918         let c = a.clone();
 919         assert!(strong_count(&a) == 2);
 920         assert!(weak_count(&a) == 0);
 921         let d = c.downgrade();
 922         assert!(weak_count(&c) == 1);
 923         assert!(strong_count(&c) == 2);
 924
 925         drop(a);
 926         drop(c);
 927         drop(d);
 928     }
 929
 930     #[test]
 931     fn show_arc() {
 932         let a = Arc::new(5u32);
 933         assert_eq!(format!("{:?}", a), "5");
 934     }
 935
 936     // Make sure deriving works with Arc<T>
 937     #[derive(Eq, Ord, PartialEq, PartialOrd, Clone, Debug, Default)]
 938     struct Foo { inner: Arc<i32> }
 939
 940     #[test]
 941     fn test_unsized() {
 942         let x: Arc<[i32]> = Arc::new([1, 2, 3]);
 943         assert_eq!(format!("{:?}", x), "[1, 2, 3]");
 944         let y = x.clone().downgrade();
 945         drop(x);
 946         assert!(y.upgrade().is_none());
 947     }
 948 }