Struct UniquePointer

pub struct UniquePointer<T: UniquePointee> { /* private fields */ }

experimental data structure that makes extensive use of unsafe rust to provide a shared pointer throughout the runtime of a rust program as transparently as possible.

UniquePointer’s design’s purpose is two-fold:

• Leverage the implementation of circular data structures such as Lisp cons cells.

• Making easier the task of practicing the implementation of basic computer science data-structures (e.g.: Binary Trees, Linked Lists etc) such that the concept of pointer is as close to C as possible in terms of developer experience and so when a CS teacher speaks in terms of pointers, students can use UniquePointer in their data-structures knowing that cloning their data-structures also means cloning the pointers transparently.

In fact, the author designed UniquePointer while studying the MIT CourseWare material of professor Erik Demaine in addition to studying lisp “cons” cells.

To this point the author reiterates: UniquePointer is an experimental data-structure designed primarily as a building-block of other data-structures in rust.

UniquePointer provides the methods UniquePointer::cast_mut and UniquePointer::cast_const not unlike those of raw pointers, and also implements the methods UniquePointer::as_ref and UniquePointer::as_mut with a signature compatible with that of the AsRef and AsMut traits such that users of raw pointers can migrate to UniquePointer without much difficulty.

UniquePointer is designed a way such that Enums and Structs using UniquePointer can safely clone UniquePointer while the memory address and provenance of its value is shared.

UniquePointer is able to extend lifetimes because it maintains its own reference counting outside of the rust compiler.

Reference Counting is provided by RefCounter which uses unsafe rust to ensure that ref counts are shared across cloned objects memory.

Both UniquePointer and RefCounter use relatively obscure rust techniques under the hood to allow writing in non-mut references in strategic occasions such as incrementing its reference count within its Clone implementation.

UniquePointer only supports Sized types, that is, Zero-Sized Types (ZSTs) are not supported.

Example

use unique_pointer::UniquePointer;

fn create_unique_pointer<'a>() -> UniquePointer<&'a str> {
    UniquePointer::from("string")
}
let mut value: UniquePointer<&'_ str> = create_unique_pointer();

assert_eq!(value.is_null(), false);

assert_eq!(value.is_allocated(), true);
assert!(value.addr() > 0, "address should not be null");
assert_eq!(value.is_written(), true);
assert_eq!(value.inner_ref(), &"string");

assert_eq!(value.read(), "string");
assert_eq!(value.as_ref(), Some(&"string"));

Caveats of UniquePointer:

• Only supports types that implement Debug
• Does not support ZSTs (Zero-Sized Types)
• UniquePointer IS NOT THREAD SAFE

Implementations

impl<'c, T: UniquePointee + 'c> UniquePointer<T>

pub fn null() -> UniquePointer<T>

creates a NULL UniquePointer ready to be written via write.

pub fn from_ref(src: &T) -> UniquePointer<T>

creates a new UniquePointer by effectively reading the value referenced by [src]

pub fn from_ref_mut(src: &mut T) -> UniquePointer<T>

from_ref_mut creates a new UniquePointer by effectively reading the value referenced by src

pub unsafe fn propagate(&self) -> UniquePointer<T>

produces a copy of a UniquePointer which is not a copy in the sense that UniquePointer::is_copy returns true.

Because of that rationale a double-free occurs if there are two or more “containers” (e.g.: [struct]s and [enum]s) implementing Drop and holding the same propagated UniquePointer instance. For this reason UniquePointer::propagate is unsafe.

UniquePointer::propagate can be relatively observed as a drop-in replacement to UniquePointer::clone for cases when, for instance, swapping UniquePointer “instances” between instances of UniquePointer-containing (structs, enums and/or unions) is desired.

Example

use unique_pointer::UniquePointer;
use std::fmt::Debug;
use std::cmp::PartialEq;

#[derive(Clone, Debug)]
pub struct BinaryTreeNode<T: Debug> {
    pub item: T,
    pub parent: UniquePointer<BinaryTreeNode<T>>,
    pub left: UniquePointer<BinaryTreeNode<T>>,
    pub right: UniquePointer<BinaryTreeNode<T>>,
}
impl<T: Debug> BinaryTreeNode<T> {
    pub fn new(item: T) -> BinaryTreeNode<T> {
        BinaryTreeNode {
            item,
            parent: UniquePointer::null(),
            left: UniquePointer::null(),
            right: UniquePointer::null(),
        }
    }

    pub fn rotate_left(&mut self) {
        if self.parent.is_null() {
            if self.right.is_not_null() {
                self.parent = unsafe { self.right.propagate() };
                self.right = UniquePointer::null();
            }
        }
    }

    pub fn set_parent(&mut self, parent: &mut BinaryTreeNode<T>) {
        self.parent = UniquePointer::read_only(parent);
    }

    pub fn set_left(&mut self, left: &mut BinaryTreeNode<T>) {
        left.set_parent(self);
        self.left = UniquePointer::read_only(left);
    }

    pub fn set_right(&mut self, right: &mut BinaryTreeNode<T>) {
        right.set_parent(self);
        self.right = UniquePointer::read_only(right);
    }
}

let mut node_a = BinaryTreeNode::new("A");
let mut node_b = BinaryTreeNode::new("B");
let mut node_c = BinaryTreeNode::new("C");
node_a.set_left(&mut node_b);
node_a.set_right(&mut node_c);

pub fn read_only(data: &T) -> UniquePointer<T>

calls [copy_from_ref] to create a read-only UniquePointer from a reference of T, useful for iterating over self-referential data structures.

Example:

pub fn copy_from_ref(data: &T, refs: usize) -> UniquePointer<T>

calls [copy_from_mut_ptr] to create a read-only UniquePointer from a reference of T, useful for iterating over self-referential data structures that use RefCounter to count refs.

Note: [read_only] might be a better alternative when T is a data structure that does not use RefCounter.

pub fn copy_from_mut_ptr(ptr: *mut T, refs: usize) -> UniquePointer<T>

creates a read-only UniquePointer from a reference of T, useful for iterating over self-referential data structures that use RefCounter to count refs.

Note: [read_only] might be a better alternative when T is a data structure that does not use RefCounter.

pub fn addr(&self) -> usize

returns the value containing both the provenance and memory address of a pointer

pub fn refs(&self) -> usize

returns the reference count of a UniquePointer

pub fn is_null(&self) -> bool

returns true if the UniquePointer is NULL.

pub fn is_not_null(&self) -> bool

returns true if the UniquePointer is not NULL. [is_not_null] is a idiomatic shortcut to negating a call to [is_null] such that the negation is less likely to be clearly visible.

pub fn is_not_copy(&self) -> bool

returns true if the UniquePointer is not a copy. [is_not_copy] is a idiomatic shortcut to negating a call to [is_copy] such that the negation is less likely to be clearly visible.

pub fn can_dealloc(&self) -> bool

returns true if the UniquePointer is not NULL and is not flagged as a copy, meaning it can be deallocated without concern for double-free.

pub fn is_allocated(&self) -> bool

returns true if the UniquePointer has been allocated and therefore is no longer a NULL pointer.

pub fn is_written(&self) -> bool

returns true if the UniquePointer has been written to

pub fn is_copy(&self) -> bool

returns true if a UniquePointer is a “copy” of another UniquePointer in the sense that dropping or “hard-deallocating” said UniquePointer does not incur a double-free.

pub fn alloc(&mut self)

allocates memory in a null UniquePointer

pub fn cast_mut(&self) -> *mut T

compatibility API to a raw mut pointer’s pointer::cast_mut.

pub fn cast_const(&self) -> *const T

compatibility API to a raw const pointer’s pointer::cast_const.

pub fn write(&mut self, data: T)

allocates memory and writes the given value into the newly allocated area.

pub fn write_ref_mut(&mut self, data: &mut T)

takes a mutable reference to a value and writes to a UniquePointer

pub fn write_ref(&mut self, data: &T)

takes a read-only reference to a value and writes to a UniquePointer

pub fn swap(&mut self, other: &mut Self)

swaps the memory addresses storing T with other UniquePointer

pub fn read(&self) -> T

reads data from memory UniquePointer. Panics if the pointer is either null or allocated but never written to.

pub fn try_read(&self) -> Option<T>

reads data from memory UniquePointer

pub fn inner_ref(&self) -> &'c T

obtains a read-only reference to the value inside UniquePointer but does not increment references

pub fn inner_mut(&mut self) -> &'c mut T

obtains a mutable reference to the value inside UniquePointer but does not increment references

pub fn as_ref(&self) -> Option<&'c T>

compatibility layer to [std::pointer::as_ref]

pub fn as_mut(&mut self) -> Option<&'c mut T>

compatibility layer to [std::pointer::as_mut]

pub fn dealloc(&mut self, soft: bool)

deallocates a UniquePointer.

The [soft] boolean argument indicates whether the UniquePointer should have its reference count decremented or deallocated immediately.

During “soft” deallocation (soft=true) calls to dealloc only really deallocate memory when the reference gets down to zero, until then each dealloc(true) call simply decrements the reference count.

Conversely during “hard” deallocation (soft=false) the UniquePointer in question gets immediately deallocated, possibly incurring a double-free or causing Undefined Behavior.

pub fn drop_in_place(&mut self)

deallocates the memory used by UniquePointer once its references get down to zero.

pub fn extend_lifetime<'t>(&self) -> &'t T

utility method to extend the lifetime of references of data created within a function.

Example

use unique_pointer::UniquePointer;

pub struct Data<'r> {
    value: &'r String,
}
impl <'r> Data<'r> {
    pub fn new<T: std::fmt::Display>(value: T) -> Data<'r> {
        let value = value.to_string();
        Data {
            value: UniquePointer::read_only(&value).extend_lifetime()
        }
    }
}

pub fn extend_lifetime_mut<'t>(&mut self) -> &'t mut T

utility method to extend the lifetime of references of data created within a function.

Example

use unique_pointer::UniquePointer;

pub struct Data<'r> {
    value: &'r mut String,
}
impl <'r> Data<'r> {
    pub fn new<T: std::fmt::Display>(value: T) -> Data<'r> {
        let value = value.to_string();
        Data {
            value: UniquePointer::read_only(&value).extend_lifetime_mut()
        }
    }
}

impl<T: UniquePointee> UniquePointer<T>

pub fn provenance_of_const_ptr(ptr: *const T) -> usize

helper method that returns the address and provenance of a const pointer

pub fn provenance_of_mut_ptr(ptr: *mut T) -> usize

helper method that returns the address and provenance of a mut pointer

pub fn provenance_of_ref(ptr: &T) -> usize

helper method that returns the address and provenance of a reference

pub fn provenance_of_mut(ptr: &mut T) -> usize

helper method that returns the address and provenance of a mutable reference

Trait Implementations

impl<T: UniquePointee> AsMut<T> for UniquePointer<T>

fn as_mut(&mut self) -> &mut T

Converts this type into a mutable reference of the (usually inferred) input type.

impl<T: UniquePointee> AsRef<T> for UniquePointer<T>

fn as_ref(&self) -> &T

Converts this type into a shared reference of the (usually inferred) input type.

impl<T> Clone for UniquePointer<T>

where T: Debug + UniquePointee,

The Clone implementation of UniquePointer is special because it flags cloned values as clones such that a double-free doesn not occur.

fn clone(&self) -> UniquePointer<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T> Debug for UniquePointer<T>

where T: Debug + UniquePointee,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: UniquePointee> Deref for UniquePointer<T>

type Target = T

The resulting type after dereferencing.

fn deref(&self) -> &T

Dereferences the value.

impl<T: UniquePointee> DerefMut for UniquePointer<T>

fn deref_mut(&mut self) -> &mut T

Mutably dereferences the value.

impl<T> Drop for UniquePointer<T>

where T: Debug + UniquePointee,

fn drop(&mut self)

Executes the destructor for this type.

impl<T> From<&T> for UniquePointer<T>

where T: Debug + UniquePointee,

fn from(data: &T) -> UniquePointer<T>

Converts to this type from the input type.

impl<T> From<&mut T> for UniquePointer<T>

where T: Debug + UniquePointee,

fn from(data: &mut T) -> UniquePointer<T>

Converts to this type from the input type.

impl<T> From<T> for UniquePointer<T>

where T: Debug + UniquePointee,

fn from(data: T) -> UniquePointer<T>

Converts to this type from the input type.

impl<T: UniquePointee + Hash> Hash for UniquePointer<T>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T: UniquePointee + Ord> Ord for UniquePointer<T>

fn cmp(&self, other: &Self) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<T: UniquePointee + PartialEq> PartialEq<T> for UniquePointer<T>

fn eq(&self, other: &T) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: UniquePointee + PartialEq> PartialEq for UniquePointer<T>

fn eq(&self, fles: &UniquePointer<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: UniquePointee + PartialOrd> PartialOrd<T> for UniquePointer<T>

fn partial_cmp(&self, other: &T) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T: UniquePointee + PartialOrd> PartialOrd for UniquePointer<T>

fn partial_cmp(&self, other: &UniquePointer<T>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<T> Pointer for UniquePointer<T>

where T: Debug + UniquePointee,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: UniquePointee + Eq> Eq for UniquePointer<T>