wrc 2.1.0

//! # Wrc
//!
//! A thread-safe weight reference counting smart-pointer for Rust.
//!

use crate::inner::Inner;
use std::cmp::Ordering;
use std::fmt;
use std::hash::{Hash, Hasher};
use std::ops::Deref;
use std::ptr::NonNull;
use std::sync::atomic::{self, AtomicUsize};

// The default weight allows for 16 clones before more weight is allocated.
const DEFAULT_WEIGHT: usize = 1 << 16;

/// # Wrc
///
/// A thread-safe weight reference counting smart-pointer for Rust.
///
/// ## Weighted Reference Counting
///
/// By using weights instead of direct reference counting `Wrc` requires
/// roughly half as many synchronisation operations and writes to the heap.
/// Every time a `Wrc` is cloned its weight is split in two, with half
/// allocated to the parent and half allocated to the child.  When a `Wrc` is
/// dropped its weight is removed from the total.  When the total weight
/// declines to zero then the referenced object is dropped.
///
/// The type `Wrc<T>` provides shared ownership of type `T`, allocated on the
/// heap. Invoking `clone` on `Wrc` produces a new pointer to the shared value
/// in the heap. When the last `Wrc` pointer is dropped then the pointed-to
/// value is also dropped.
///
/// See [Wikipedia](https://en.wikipedia.org/wiki/Reference_counting#Weighted_reference_counting)
/// for more information about weighted reference counting.
///
/// ## Thread Safety
///
/// `Wrc<T>` uses atomic operations for its weight manipulations. This means
/// that it is thread-safe. The disadvantage is that atomic operations are more
/// expensive than ordinary memory accesses.  The use of the weighted reference
/// counting algorithm drastically reduces the number of synchronisation
/// operations required to keep track of references.
///
/// ## Breaking Cycles with `Weak`
///
/// The [`downgrade`][Wrc::downgrade] method can be used to create a
/// non-owning [`Weak`] pointer. A `Weak` pointer can be [`upgrade`]d to a
/// `Wrc`, but this will return `None` if the value stored in the allocation
/// has already been dropped. In other words, `Weak` pointers do not keep the
/// value alive.
///
/// A cycle between `Wrc` pointers will never be deallocated. For this reason,
/// `Weak` is used to break cycles. For example, a tree could have strong
/// `Wrc` pointers from parent nodes to children, and `Weak` pointers from
/// children back to their parents.
///
/// [`upgrade`]: Weak::upgrade
///
/// ## Cloning references
///
/// Creating a new reference from an existing reference counted pointer is done
/// using the `Clone` trait, implemented for `Wrc<T>`.
///
/// ## `Deref` behaviour
///
/// `Wrc<T>` automatically dereferences to `T` (via the `Deref` trait), so you
/// can call `T`'s methods on a value of type `Wrc<T>`.
///
/// ## Examples
///
/// Sharing some immutable data between threads:
///
/// ```
/// use wrc::Wrc;
/// use std::thread;
///
/// let five = Wrc::new(5);
///
/// for _ in 0..10 {
///     let five = five.clone();
///
///     thread::spawn(move || {
///         println!("{:?}", five);
///     });
/// }
/// ```
///
/// Sharing a mutable `AtomicUsize`:
///
/// ```
/// use wrc::Wrc;
/// use std::sync::atomic::{AtomicUsize, Ordering};
/// use std::thread;
///
/// let val = Wrc::new(AtomicUsize::new(5));
///
/// for _ in 0..10 {
///     let val = val.clone();
///
///     thread::spawn(move || {
///         let v = val.fetch_add(1, Ordering::SeqCst);
///         println!("{:?}", v);
///     });
/// }
/// ```
///
/// See the [rc documentation](https://doc.rust-lang.org/std/rc/#examples) for
/// more examples of reference counting in general.
pub struct Wrc<T: ?Sized> {
    weight: AtomicUsize,
    ptr: NonNull<Inner<T>>,
}

impl<T> Wrc<T> {
    /// Construct a new `Wrc<T>`.
    ///
    /// ## Examples
    /// ```
    /// use wrc::Wrc;
    /// let five = Wrc::new(5);
    /// ```
    #[inline]
    pub fn new(data: T) -> Wrc<T> {
        let ptr = Box::new(Inner::new(data, DEFAULT_WEIGHT, DEFAULT_WEIGHT));
        Wrc {
            weight: AtomicUsize::new(DEFAULT_WEIGHT),
            ptr: NonNull::new(Box::into_raw(ptr)).unwrap(),
        }
    }

    /// Returns a mutable reference to the inner value if there are no other
    /// `Wrc` pointers to the same allocation.
    ///
    /// Returns `None` otherwise, because it is not safe to mutate a shared
    /// value.
    ///
    /// ## Examples
    ///
    /// ```
    /// use wrc::Wrc;
    ///
    /// let mut x = Wrc::new(3);
    /// *Wrc::get_mut(&mut x).unwrap() = 4;
    /// assert_eq!(*x, 4);
    ///
    /// let _y = x.clone();
    /// assert!(Wrc::get_mut(&mut x).is_none());
    /// ```
    #[inline]
    pub fn get_mut(this: &mut Wrc<T>) -> Option<&mut T> {
        let local_weight = this.weight.load(atomic::Ordering::Acquire);
        let total_weight = this.inner().strong_weight();
        let weak_weight = this.inner().weak_weight();
        // Must hold all strong weight AND no weak references exist
        // (weak_weight == DEFAULT_WEIGHT means only the implicit weak ref from strong refs)
        if local_weight == total_weight && weak_weight == DEFAULT_WEIGHT {
            Some(unsafe { &mut this.ptr.as_mut().data })
        } else {
            None
        }
    }

    /// Creates a new [`Weak`] pointer to this allocation.
    ///
    /// # Panics
    ///
    /// Panics if adding weak weight would overflow `usize`. This is extremely
    /// unlikely in practice as it would require creating 2^48 weak references.
    ///
    /// ## Examples
    ///
    /// ```
    /// use wrc::Wrc;
    ///
    /// let five = Wrc::new(5);
    /// let weak_five = Wrc::downgrade(&five);
    /// ```
    pub fn downgrade(this: &Wrc<T>) -> Weak<T> {
        this.inner().add_weak_weight(DEFAULT_WEIGHT);
        Weak {
            weight: AtomicUsize::new(DEFAULT_WEIGHT),
            ptr: this.ptr,
        }
    }

    /// Return the total weight of all references.
    /// Only used for testing.  You're unlikely to need it.
    pub fn total_weight(wrc: &Wrc<T>) -> usize {
        wrc.inner().strong_weight()
    }

    /// Returns `true` if two `Wrc`s point to the same allocation.
    pub fn ptr_eq(this: &Wrc<T>, other: &Wrc<T>) -> bool {
        this.ptr == other.ptr
    }

    #[inline]
    fn inner(&self) -> &Inner<T> {
        unsafe { self.ptr.as_ref() }
    }
}

unsafe impl<T: ?Sized + Sync + Send> Send for Wrc<T> {}
unsafe impl<T: ?Sized + Sync + Send> Sync for Wrc<T> {}

impl<T: ?Sized> Wrc<T> {
    #[inline]
    pub(crate) fn local_weight(&self) -> usize {
        self.weight.load(atomic::Ordering::Relaxed)
    }

    #[inline]
    fn drop_local_weight(&self, weight: usize) -> usize {
        let old = self.weight.fetch_sub(weight, atomic::Ordering::Relaxed);
        debug_assert!(old >= weight, "local weight underflow");
        old - weight
    }
}

impl<T> Clone for Wrc<T> {
    /// Makes a clone of the `Wrc` pointer.
    ///
    /// This creates another pointer with the same ptr value, dividing the
    /// weight evenly between the new reference and the old reference.
    ///
    /// # Panics
    ///
    /// Panics if adding strong weight would overflow `usize`. This is extremely
    /// unlikely in practice as it would require approximately 2^48 weight
    /// reallocation operations.
    ///
    /// ## Examples
    /// ```
    /// use wrc::Wrc;
    ///
    /// let five = Wrc::new(5);
    /// five.clone();
    /// ```
    fn clone(&self) -> Self {
        let existing_weight = self.local_weight();
        if existing_weight > 1 {
            let new_weight = existing_weight >> 1;
            self.drop_local_weight(new_weight);
            Wrc {
                weight: AtomicUsize::new(new_weight),
                ptr: self.ptr,
            }
        } else {
            self.inner().add_strong_weight(DEFAULT_WEIGHT);
            Wrc {
                weight: AtomicUsize::new(DEFAULT_WEIGHT),
                ptr: self.ptr,
            }
        }
    }
}

impl<T: ?Sized> Drop for Wrc<T> {
    /// Drops the `Wrc`.
    ///
    /// This will decrement the total weight of the referenced object by the
    /// weight of this reference.
    ///
    /// ## Examples
    /// ```
    /// use wrc::Wrc;
    ///
    /// struct Foo;
    ///
    /// impl Drop for Foo {
    ///     fn drop(&mut self) {
    ///         println!("dropped!");
    ///     }
    /// }
    ///
    /// let foo = Wrc::new(Foo);
    /// let foo2 = foo.clone();
    ///
    /// drop(foo);  // Doesn't print anything
    /// drop(foo2); // Prints "dropped!"
    /// ```
    fn drop(&mut self) {
        let inner = unsafe { self.ptr.as_ref() };
        let existing_weight = self.local_weight();
        let new_weight = inner.drop_strong_weight(existing_weight);

        if new_weight > 0 {
            return;
        }

        atomic::fence(atomic::Ordering::Acquire);
        unsafe {
            std::mem::ManuallyDrop::drop(&mut self.ptr.as_mut().data);
        }

        let new_weak_weight = inner.drop_weak_weight(DEFAULT_WEIGHT);

        if new_weak_weight > 0 {
            return;
        }

        atomic::fence(atomic::Ordering::Acquire);
        unsafe {
            let _ = Box::from_raw(self.ptr.as_ptr());
        }
    }
}

impl<T> Deref for Wrc<T> {
    type Target = T;

    #[inline]
    fn deref(&self) -> &Self::Target {
        &self.inner().data
    }
}

impl<T: fmt::Display> fmt::Display for Wrc<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Display::fmt(&*self.inner().data, f)
    }
}

impl<T: fmt::Debug> fmt::Debug for Wrc<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Debug::fmt(&*self.inner().data, f)
    }
}

impl<T: PartialEq> PartialEq for Wrc<T> {
    fn eq(&self, other: &Wrc<T>) -> bool {
        *self.inner().data == *other.inner().data
    }
}

impl<T: PartialOrd> PartialOrd for Wrc<T> {
    fn partial_cmp(&self, other: &Wrc<T>) -> Option<Ordering> {
        (*self.inner().data).partial_cmp(&*other.inner().data)
    }
}

impl<T: Ord> Ord for Wrc<T> {
    fn cmp(&self, other: &Wrc<T>) -> Ordering {
        (*self.inner().data).cmp(&*other.inner().data)
    }
}

impl<T: Eq> Eq for Wrc<T> {}

impl<T: Default> Default for Wrc<T> {
    /// Creates a new `Wrc<T>` with the `Default` value of `T`.
    fn default() -> Wrc<T> {
        Wrc::new(Default::default())
    }
}

impl<T: Hash> Hash for Wrc<T> {
    fn hash<H: Hasher>(&self, state: &mut H) {
        (*self.inner().data).hash(state)
    }
}

impl<T> AsRef<T> for Wrc<T> {
    fn as_ref(&self) -> &T {
        self.deref()
    }
}

impl<T> std::borrow::Borrow<T> for Wrc<T> {
    fn borrow(&self) -> &T {
        self.deref()
    }
}

impl<T> From<T> for Wrc<T> {
    fn from(value: T) -> Self {
        Wrc::new(value)
    }
}

/// `Weak` is a version of [`Wrc`] that holds a non-owning reference to the
/// managed allocation.
///
/// The allocation is accessed by calling [`upgrade`] on the `Weak` pointer,
/// which returns an [`Option`]`<`[`Wrc`]`<T>>`.
///
/// Since a `Weak` reference does not contribute to ownership, it will not
/// prevent the value stored in the allocation from being dropped, and `Weak`
/// itself makes no guarantees about the value still being present. Thus it
/// may return `None` when [`upgrade`]d. Note however that a `Weak` reference
/// *does* prevent the allocation itself (the backing store) from being
/// deallocated.
///
/// A `Weak` pointer is useful for keeping a temporary reference to the
/// allocation managed by [`Wrc`] without preventing its inner value from being
/// dropped. It is also used to prevent circular references between [`Wrc`]
/// pointers, since mutual owning references would never allow either [`Wrc`]
/// to be dropped.
///
/// The typical way to obtain a `Weak` pointer is to call [`Wrc::downgrade`].
///
/// [`upgrade`]: Weak::upgrade
pub struct Weak<T: ?Sized> {
    weight: AtomicUsize,
    ptr: NonNull<Inner<T>>,
}

unsafe impl<T: ?Sized + Sync + Send> Send for Weak<T> {}
unsafe impl<T: ?Sized + Sync + Send> Sync for Weak<T> {}

impl<T: ?Sized> Weak<T> {
    #[inline]
    fn inner(&self) -> &Inner<T> {
        unsafe { self.ptr.as_ref() }
    }

    #[inline]
    fn get_weight(&self) -> usize {
        self.weight.load(atomic::Ordering::Relaxed)
    }

    #[inline]
    fn drop_weight(&self, weight: usize) -> usize {
        let old = self.weight.fetch_sub(weight, atomic::Ordering::Relaxed);
        debug_assert!(old >= weight, "weak local weight underflow");
        old - weight
    }
}

impl<T> Weak<T> {
    /// Attempts to upgrade the `Weak` pointer to a [`Wrc`], delaying dropping
    /// of the inner value if successful.
    ///
    /// Returns `None` if the inner value has since been dropped.
    ///
    /// ## Examples
    ///
    /// ```
    /// use wrc::Wrc;
    ///
    /// let five = Wrc::new(5);
    /// let weak_five = Wrc::downgrade(&five);
    ///
    /// let strong_five = weak_five.upgrade();
    /// assert!(strong_five.is_some());
    ///
    /// drop(five);
    /// drop(strong_five);
    ///
    /// assert!(weak_five.upgrade().is_none());
    /// ```
    pub fn upgrade(&self) -> Option<Wrc<T>> {
        if self.inner().try_add_strong_weight(DEFAULT_WEIGHT) {
            Some(Wrc {
                weight: AtomicUsize::new(DEFAULT_WEIGHT),
                ptr: self.ptr,
            })
        } else {
            None
        }
    }
}

impl<T: ?Sized> Clone for Weak<T> {
    fn clone(&self) -> Self {
        let existing_weight = self.get_weight();
        if existing_weight > 1 {
            let new_weight = existing_weight >> 1;
            self.drop_weight(new_weight);
            Weak {
                weight: AtomicUsize::new(new_weight),
                ptr: self.ptr,
            }
        } else {
            self.inner().add_weak_weight(DEFAULT_WEIGHT);
            Weak {
                weight: AtomicUsize::new(DEFAULT_WEIGHT),
                ptr: self.ptr,
            }
        }
    }
}

impl<T: ?Sized> Drop for Weak<T> {
    fn drop(&mut self) {
        let inner = unsafe { self.ptr.as_ref() };
        let existing_weight = self.get_weight();
        let new_weight = inner.drop_weak_weight(existing_weight);

        if new_weight > 0 {
            return;
        }

        atomic::fence(atomic::Ordering::Acquire);
        unsafe {
            let _ = Box::from_raw(self.ptr.as_ptr());
        }
    }
}

impl<T: ?Sized + fmt::Debug> fmt::Debug for Weak<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "(Weak)")
    }
}