wrc 0.4.2

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

use crate::inner::Inner;
use crate::weight::Weight;
use std::cell::Cell;
use std::cmp::Ordering;
use std::fmt;
use std::hash::{Hash, Hasher};
use std::ops::{Deref, DerefMut};
use std::ptr::NonNull;

// 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 it's weight is split in two, with half
/// allocated to the parent and half allocated to the child.  When a `WRC` is
/// dropped it's 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 it's 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.
///
/// ## Cycles
///
/// Currently there is no support in `WRC` for weak pointers or any other
/// cycle breaking. If your usage causes you to create cycles of references
/// you may want to investigate an alternative solution or manually force
/// destruction of those objects.
///
/// ## 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 `WTC<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> {
    // Since each WRC uses a `Cell<usize>` to store the reference's weight it's
    // mutating the weight isn't an entirely thread-safe operation, however
    // since WRC's never leave the stack this should be safe.
    weight: Cell<usize>,
    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> {
        // Allocate the ptr on the heap and set the weights of the values
        // to the default.
        let ptr = Box::new(Inner::new(data, DEFAULT_WEIGHT));
        WRC {
            weight: Cell::new(DEFAULT_WEIGHT),
            ptr: NonNull::new(Box::into_raw(ptr)).unwrap(),
        }
    }

    /// 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().get_weight()
    }

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

    /// 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.
    ///
    /// ## Examples
    /// ```
    /// use wrc::WRC;
    ///
    /// let five = WRC::new(5);
    /// WRC::clone(&five);
    /// ```
    #[inline]
    pub fn clone(wrc: &WRC<T>) -> WRC<T> {
        let existing_weight = wrc.get_weight();
        if existing_weight > 1 {
            let new_weight = existing_weight >> 1;
            wrc.drop_weight(new_weight);
            WRC {
                weight: Cell::new(new_weight),
                ptr: wrc.ptr,
            }
        } else {
            let ptr = wrc.inner();
            ptr.add_weight(DEFAULT_WEIGHT)
                .unwrap_or_else(|| panic!("Unable to add {:?} to WRC", existing_weight));
            WRC {
                weight: Cell::new(DEFAULT_WEIGHT),
                ptr: wrc.ptr,
            }
        }
    }
}

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

impl<T: ?Sized> Weight for WRC<T> {
    fn add_weight(&self, weight: usize) -> Option<usize> {
        let existing_weight = self.weight.get();
        let new_weight = existing_weight.checked_add(weight);
        match new_weight {
            Some(weight) => {
                self.weight.set(weight);
                Some(weight)
            }
            None => None,
        }
    }

    fn drop_weight(&self, weight: usize) -> Option<usize> {
        let existing_weight = self.weight.get();
        let new_weight = existing_weight.checked_sub(weight);
        match new_weight {
            Some(weight) => {
                self.weight.set(weight);
                Some(weight)
            }
            None => None,
        }
    }

    fn get_weight(&self) -> usize {
        self.weight.get()
    }
}

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.
    ///
    /// ## Examples
    /// ```
    /// use wrc::WRC;
    ///
    /// let five = WRC::new(5);
    /// five.clone();
    /// ```
    fn clone(&self) -> Self {
        WRC::clone(self)
    }
}

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 ptr = unsafe { self.ptr.as_ref() };
        let existing_weight = self.get_weight();
        let new_weight = ptr
            .drop_weight(existing_weight)
            .unwrap_or_else(|| panic!("Unable to drop {:?} from to WRC", existing_weight));
        if new_weight > 0 {
            return;
        }

        let ptr = self.ptr.as_ptr();
        let data = unsafe { Box::from_raw(ptr) };
        drop(data);
    }
}

impl<T> Deref for WRC<T> {
    /// The resulting type after dereferencing
    type Target = T;

    /// The method called to dereference a value
    #[inline]
    fn deref(&self) -> &Self::Target {
        self.inner().deref()
    }
}

impl<T> DerefMut for WRC<T> {
    /// The method called to mutably dereference a value.
    #[inline]
    fn deref_mut(&mut self) -> &mut T {
        unsafe { self.ptr.as_mut() }.deref_mut()
    }
}

impl<T: fmt::Display> fmt::Display for WRC<T> {
    /// Formats the value using the given formatter
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Display::fmt(self.inner(), f)
    }
}

impl<T: fmt::Debug> fmt::Debug for WRC<T> {
    /// Formats the value using the given formatter.
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        fmt::Debug::fmt(self.inner(), f)
    }
}

impl<T: PartialEq> PartialEq for WRC<T> {
    /// Equality for `WRC<T>`
    ///
    /// Two `WRC`'s are equal if their ptr values are equal.
    fn eq(&self, other: &WRC<T>) -> bool {
        self.inner() == other.inner()
    }
}

impl<T: PartialOrd> PartialOrd for WRC<T> {
    /// Partial comparison for two `WRC`'s
    ///
    /// The two are compared by calling `partial_cmp()` on their ptr values.
    fn partial_cmp(&self, other: &WRC<T>) -> Option<Ordering> {
        self.inner().partial_cmp(other.inner())
    }

    /// Less-than comparison for two `WRC`'s
    ///
    /// The two are compared by calling `<` on their ptr values.
    fn lt(&self, other: &WRC<T>) -> bool {
        self.inner() < other.inner()
    }

    /// Less-than or equal to comparison for two `WRC`'s
    ///
    /// The two are compared by calling `<=` on their ptr values.
    fn le(&self, other: &WRC<T>) -> bool {
        self.inner() <= other.inner()
    }

    /// Greater-than comparison for two `WRC`'s
    ///
    /// The two are compared by calling `>` on their ptr values.
    fn gt(&self, other: &WRC<T>) -> bool {
        self.inner() > other.inner()
    }

    /// Greater-than or equal comparison for two `WRC`'s
    ///
    /// The two are compared by calling `>=` on their ptr values.
    fn ge(&self, other: &WRC<T>) -> bool {
        self.inner() >= other.inner()
    }
}

impl<T: Ord> Ord for WRC<T> {
    /// Comparison for two `WRC`'s
    ///
    /// The two are compared by calling `cmp()` on their ptr values.
    fn cmp(&self, other: &WRC<T>) -> Ordering {
        self.inner().cmp(other.inner())
    }
}

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().hash(state)
    }
}