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