wrc 0.2.0

//! # WRC
//!
//! A thread-safe weight reference counting smart-pointer for Rust.
//!
//! 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 shated value
//! in the heap. When the last `WRC` pointer is dropped then the pointed-to
//! value is also dropped.
//!
//! ## 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.

use std::cell::Cell;
use std::ptr::Shared;
use std::ops::{Deref, CoerceUnsized};
use std::hash::{Hash, Hasher};
use std::cmp::Ordering;
use std::marker::Unsize;
use std::fmt;
use weight::Weight;
use inner::Inner;

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

// 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.
pub struct WRC<T: ?Sized> {
    weight: Cell<usize>,
    ptr: Shared<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: Shared::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 {
        unsafe { wrc.ptr.as_ref() }.get_weight()
    }

    #[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 + Unsize<U>, U: ?Sized> CoerceUnsized<WRC<U>> 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 {
        let existing_weight = self.get_weight();
        if existing_weight > 1 {
            let new_weight = existing_weight >> 1;
            self.drop_weight(new_weight);
            WRC {
                weight: Cell::new(new_weight),
                ptr: self.ptr
            }
        }
        else {
            let ptr = self.inner();
            ptr
                .add_weight(DEFAULT_WEIGHT)
                .expect(format!("Unable to add {:?} to WRC", existing_weight).as_str());
            WRC {
                weight: Cell::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 ptr = unsafe { self.ptr.as_ref() };
        let existing_weight = self.get_weight();
        let new_weight = ptr
            .drop_weight(existing_weight)
            .expect(format!("Unable to drop {:?} from to WRC", existing_weight).as_str());
        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 = Inner<T>;

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

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()
    }

    /// Inequality for `WRC<T>`
    ///
    /// Two `WRC`'s are unequal if their ptr values are unequal.
    fn ne(&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 comparisomn 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)
    }
}