pub struct UniquePointer<T: Pointee> { /* private fields */ }
Expand description
UniquePointer
is an 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 as well as
to implement lisp cons cells
and ring-buffers.
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
- Only supports types that implement Debug
- Does not support ZSTs (Zero-Sized Types)
- UniquePointer IS NOT THREAD SAFE
§Lisp Cons Cell Example
use std::iter::Extend;
use unique_pointer::{RefCounter, UniquePointer};
#[derive(Debug, Hash)]
pub struct Cell<'c> {
head: UniquePointer<Value<'c>>,
tail: UniquePointer<Cell<'c>>,
refs: RefCounter,
length: usize,
}
impl<'c> Cell<'c> {
pub fn nil() -> Cell<'c> {
Cell {
head: UniquePointer::<Value<'c>>::null(),
tail: UniquePointer::<Cell<'c>>::null(),
refs: RefCounter::null(),
length: 0,
}
}
pub fn is_nil(&self) -> bool {
self.head.is_null() && self.tail.is_null()
}
pub fn new(value: Value<'c>) -> Cell<'c> {
let mut cell = Cell::nil();
cell.write(value);
cell
}
fn write(&mut self, value: Value<'c>) {
self.head.write(value);
self.refs.write(1);
self.length = 1;
}
fn swap_head(&mut self, other: &mut Self) {
self.head = unsafe {
let head = other.head.propagate();
other.head = self.head.propagate();
head
};
}
fn swap_refs(&mut self, other: &mut Self) {
self.refs = {
let refs = other.refs.clone();
other.refs = self.refs.clone();
refs
};
}
pub fn head(&self) -> Option<Value<'c>> {
self.head.try_read()
}
pub fn add(&mut self, new: &mut Cell<'c>) {
new.incr_ref();
self.incr_ref();
if self.head.is_null() {
unsafe {
if !new.head.is_null() {
self.swap_head(new);
}
if !new.tail.is_null() {
let tail = new.tail.inner_mut();
tail.swap_head(new);
self.swap_refs(new);
}
self.tail = UniquePointer::read_only(new);
}
} else {
if self.tail.is_null() {
self.tail = UniquePointer::read_only(new);
} else {
self.tail.inner_mut().add(new);
}
}
}
pub fn pop(&mut self) -> bool {
if !self.tail.is_null() {
self.tail.drop_in_place();
self.tail = UniquePointer::null();
true
} else if !self.head.is_null() {
self.head.drop_in_place();
self.head = UniquePointer::null();
true
} else {
false
}
}
pub fn is_empty(&self) -> bool {
self.len() > 0
}
pub fn len(&self) -> usize {
let mut len = 0;
if !self.head.is_null() {
len += 1
}
if let Some(tail) = self.tail() {
len += tail.len();
}
len
}
pub fn tail(&self) -> Option<&'c Cell<'c>> {
self.tail.as_ref()
}
pub fn values(&self) -> Vec<Value<'c>> {
let mut values = Vec::<Value>::new();
if let Some(head) = self.head() {
values.push(head.clone());
}
if let Some(tail) = self.tail() {
values.extend(tail.values());
}
values
}
fn incr_ref(&mut self) {
self.refs += 1;
if !self.tail.is_null() {
if let Some(tail) = self.tail.as_mut() {
tail.incr_ref();
}
}
}
fn decr_ref(&mut self) {
self.refs -= 1;
if !self.tail.is_null() {
if let Some(tail) = self.tail.as_mut() {
tail.decr_ref();
}
}
}
fn dealloc(&mut self) {
if self.refs > 0 {
self.decr_ref();
} else {
self.head.drop_in_place();
self.tail.drop_in_place();
}
}
}
impl<'c> From<Value<'c>> for Cell<'c> {
fn from(value: Value<'c>) -> Cell<'c> {
Cell::new(value)
}
}
impl<'c> From<&'c str> for Cell<'c> {
fn from(value: &'c str) -> Cell<'c> {
let value = Value::from(value);
Cell::new(value)
}
}
impl<'c> From<u8> for Cell<'c> {
fn from(value: u8) -> Cell<'c> {
Cell::new(Value::Byte(value))
}
}
impl<'c> From<u64> for Cell<'c> {
fn from(value: u64) -> Cell<'c> {
if value < u8::MAX.into() {
Cell::new(Value::Byte(value as u8))
} else {
Cell::new(Value::UInt(value))
}
}
}
impl<'c> From<i32> for Cell<'c> {
fn from(value: i32) -> Cell<'c> {
if let Ok(value) = TryInto::<u64>::try_into(value) {
Cell::new(Value::UInt(value))
} else {
Cell::new(Value::Int(value.into()))
}
}
}
impl<'c> From<i64> for Cell<'c> {
fn from(value: i64) -> Cell<'c> {
Cell::new(Value::from(value))
}
}
impl<'c> PartialEq<Cell<'c>> for Cell<'c> {
fn eq(&self, other: &Cell<'c>) -> bool {
if self.head.is_null() == other.head.is_null() {
true
} else if let Some(head) = self.head() {
if let Some(value) = other.head() {
return head == value && (self.tail() == other.tail());
} else {
false
}
} else {
false
}
}
}
impl<'c> Default for Cell<'c> {
fn default() -> Cell<'c> {
Cell::nil()
}
}
impl<'c> Clone for Cell<'c> {
fn clone(&self) -> Cell<'c> {
let mut cell = Cell::nil();
cell.refs = self.refs.clone();
if self.head.is_not_null() {
cell.head = self.head.clone();
}
if self.tail.is_not_null() {
cell.tail = self.tail.clone();
}
cell
}
}
impl<'c> Drop for Cell<'c> {
fn drop(&mut self) {
self.dealloc();
}
}
Implementations§
Source§impl<'c, T: Pointee + 'c> UniquePointer<T>
impl<'c, T: Pointee + 'c> UniquePointer<T>
Sourcepub fn null() -> UniquePointer<T>
pub fn null() -> UniquePointer<T>
creates a NULL UniquePointer
ready to be written via write.
Sourcepub fn from_ref(src: &T) -> UniquePointer<T>
pub fn from_ref(src: &T) -> UniquePointer<T>
creates a new UniquePointer
by effectively
reading the value referenced by src
Sourcepub fn from_ref_mut(src: &mut T) -> UniquePointer<T>
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
Sourcepub unsafe fn propagate(&self) -> UniquePointer<T>
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.: structs and enums)
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
and/or enums) is desired.
Example
use unique_pointer::UniquePointer;
use std::fmt::Debug;
use std::cmp::PartialEq;
#[derive(Clone, Debug, Hash)]
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);
Sourcepub unsafe fn unlock_reference<'t>(read_only: &T) -> &'t mut T
pub unsafe fn unlock_reference<'t>(read_only: &T) -> &'t mut T
unlock_reference
extends the lifetime of &T
to &'t T
and
unlocks &'t T
into a &'t mut T
This function is primarily designed to permit data-structures
implementing their own reference counting Clone
to “break
out” of a read-only reference, so to speak, so that its
references can be incremented.
Example
use std::fmt::Debug;
use unique_pointer::{RefCounter, UniquePointer};
#[derive(Debug, Hash)]
pub struct LinkedList<T: Debug + Clone> {
pub item: T,
pub next: UniquePointer<LinkedList<T>>,
pub refs: usize,
}
impl<T: Debug + Clone> LinkedList<T> {
pub fn new(item: T) -> LinkedList<T> {
LinkedList {
item,
next: UniquePointer::null(),
refs: 1,
}
}
pub fn item(&self) -> T {
self.item.clone()
}
fn incr_ref(&mut self) {
self.refs += 1;
}
fn decr_ref(&mut self) {
if self.refs > 0 {
self.refs -= 1;
}
}
fn dealloc(&mut self) {
self.decr_ref();
if self.next.is_not_null() {
self.next.inner_mut().dealloc()
}
if self.refs == 0 {
self.next.drop_in_place();
}
}
pub fn append(&mut self, value: T) -> LinkedList<T> {
let next = LinkedList::new(value);
self.next.write_ref(&next);
next
}
pub fn next(&self) -> Option<&LinkedList<T>> {
self.next.as_ref()
}
pub fn len(&self) -> usize {
let mut length = 1;
if let Some(next) = self.next() {
length += 1;
length += next.len();
}
length
}
}
impl<T: Debug + Clone> Clone for LinkedList<T> {
fn clone(&self) -> LinkedList<T> {
unsafe {
UniquePointer::<LinkedList<T>>::unlock_reference(self).incr_ref();
}
let mut list = LinkedList::new(self.item());
list.refs = self.refs;
list.next = self.next.clone();
list
}
}
impl<T: Debug + Clone> Drop for LinkedList<T> {
fn drop(&mut self) {
self.dealloc();
}
}
let mut a = LinkedList::new("a");
let mut b = a.append("b");
b.append("c");
assert_eq!(a.refs, 1);
assert_eq!(a.len(), 3);
let z = a.clone();
assert_eq!(z.len(), 3);
assert_eq!(a.refs, 2);
assert_eq!(z.refs, 2);
Sourcepub fn read_only(data: &T) -> UniquePointer<T>
pub fn read_only(data: &T) -> UniquePointer<T>
calls UniquePointer::copy_from_ref
to create a read-only UniquePointer
from a
reference of T
, useful for iterating over self-referential
data structures.
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()
}
}
}
Sourcepub fn copy_from_ref(data: &T, refs: usize) -> UniquePointer<T>
pub fn copy_from_ref(data: &T, refs: usize) -> UniquePointer<T>
calls UniquePointer::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: UniquePointer::read_only
might be a better alternative when T
is
a data structure that does not use RefCounter.
Sourcepub fn copy_from_mut_ptr(ptr: *mut T, refs: usize) -> UniquePointer<T>
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: UniquePointer::read_only
might be a better alternative when T
is
a data structure that does not use RefCounter.
Sourcepub fn addr(&self) -> usize
pub fn addr(&self) -> usize
returns the value containing both the provenance and memory address of a pointer
Sourcepub fn is_not_null(&self) -> bool
pub fn is_not_null(&self) -> bool
returns true if the UniquePointer
is not
NULL. UniquePointer::is_not_null
is a idiomatic shortcut
to negating a call to UniquePointer::is_null
such that the
negation is less likely to be clearly visible.
Sourcepub fn is_not_copy(&self) -> bool
pub fn is_not_copy(&self) -> bool
returns true if the UniquePointer
is not a
copy. UniquePointer::is_not_copy
is a idiomatic shortcut
to negating a call to UniquePointer::is_copy
such that the
negation is less likely to be clearly visible.
Sourcepub fn can_dealloc(&self) -> bool
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.
Sourcepub fn is_allocated(&self) -> bool
pub fn is_allocated(&self) -> bool
returns true if the UniquePointer
has been
allocated and therefore is no longer a NULL pointer.
Sourcepub fn is_written(&self) -> bool
pub fn is_written(&self) -> bool
returns true if the UniquePointer
has been written to
Sourcepub fn is_copy(&self) -> bool
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.
Sourcepub fn cast_mut(&self) -> *mut T
pub fn cast_mut(&self) -> *mut T
compatibility API to a raw mut pointer’s pointer::cast_mut
.
Sourcepub fn cast_const(&self) -> *const T
pub fn cast_const(&self) -> *const T
compatibility API to a raw const pointer’s pointer::cast_const
.
Sourcepub fn write(&mut self, data: T)
pub fn write(&mut self, data: T)
allocates memory and writes the given value into the newly allocated area.
Sourcepub fn write_ref_mut(&mut self, data: &mut T)
pub fn write_ref_mut(&mut self, data: &mut T)
takes a mutable reference to a value and
writes to a UniquePointer
Sourcepub fn write_ref(&mut self, data: &T)
pub fn write_ref(&mut self, data: &T)
takes a read-only reference to a value and
writes to a UniquePointer
Sourcepub fn swap(&mut self, other: &mut Self)
pub fn swap(&mut self, other: &mut Self)
swaps the memory addresses storing T
with other UniquePointer
Sourcepub fn read(&self) -> T
pub fn read(&self) -> T
reads data from memory UniquePointer
. Panics if
the pointer is either null or allocated but never written to.
Sourcepub fn inner_ref(&self) -> &'c T
pub fn inner_ref(&self) -> &'c T
obtains a read-only reference to the value inside
UniquePointer
but does not increment references
Sourcepub fn inner_mut(&mut self) -> &'c mut T
pub fn inner_mut(&mut self) -> &'c mut T
obtains a mutable reference to the value inside
UniquePointer
but does not increment references
Sourcepub fn as_mut(&mut self) -> Option<&'c mut T>
pub fn as_mut(&mut self) -> Option<&'c mut T>
compatibility layer to std::pointer::as_mut
Sourcepub fn into_box_unchecked(&self) -> Box<T>
pub fn into_box_unchecked(&self) -> Box<T>
Returns a Box<T>
without dropping T, panics if
UniquePointer points to null.
See into_box for a version that returns
Option<Box<T>>
.
Example boxing a type that does not implement Clone
use unique_pointer::UniquePointer;
use std::collections::BTreeMap;
use std::fmt::{Display, Debug, Formatter};
pub trait Matcher {
fn to_str(&self) -> String;
fn to_dbg(&self) -> String {
format!("{:#?}", self.to_str())
}
}
impl Debug for dyn Matcher {
fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
write!(f, "{}", self.to_str())
}
}
#[derive(Debug)]
pub enum Match {
Literal(String),
Rule(Box<Rule>),
Matcher(Box<dyn Matcher>),
Sequence(Vec<Box<dyn Matcher>>),
}
pub(crate) static mut RULES: BTreeMap<&'static str, UniquePointer<Match>> = BTreeMap::new();
#[allow(static_mut_refs)]
pub(crate) fn register_match<T: Display>(string: T, r#match: Match) -> Match {
unsafe {
RULES.insert(string.to_string().leak(), UniquePointer::from_ref(&r#match));
}
r#match
}
#[derive(Debug)]
pub struct Rule {
sym: String,
matcher: Match,
}
impl Rule {
pub fn new<S: ToString>(symbol: S, matcher: impl Into<Match>) -> Rule {
Rule {
sym: symbol.to_string(),
matcher: matcher.into(),
}
}
pub fn symbol(&self) -> &str {
self.sym.as_ref()
}
}
impl From<Rule> for Match {
fn from(rule: Rule) -> Match {
let rule = UniquePointer::from(rule);
let symbol = rule.inner_ref().symbol();
register_match(symbol, Match::Rule(rule.into_box_unchecked()))
}
}
Sourcepub fn into_box(&self) -> Option<Box<T>>
pub fn into_box(&self) -> Option<Box<T>>
Returns a Option<Box<T>>
without dropping T, returns None
if pointing to null.
See into_box_unchecked for a
version that returns Box<T>
.
Sourcepub fn dealloc(&mut self, soft: bool)
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.
Sourcepub fn drop_in_place(&mut self)
pub fn drop_in_place(&mut self)
deallocates the memory used by UniquePointer
once its references get down to zero.
Sourcepub fn extend_lifetime<'t>(&self) -> &'t T
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()
}
}
}
Sourcepub fn extend_lifetime_mut<'t>(&mut self) -> &'t mut T
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()
}
}
}
Source§impl<T: Pointee> UniquePointer<T>
impl<T: Pointee> UniquePointer<T>
Sourcepub fn provenance_of_const_ptr(ptr: *const T) -> usize
pub fn provenance_of_const_ptr(ptr: *const T) -> usize
helper method that returns the address and provenance of a const pointer
Sourcepub fn provenance_of_mut_ptr(ptr: *mut T) -> usize
pub fn provenance_of_mut_ptr(ptr: *mut T) -> usize
helper method that returns the address and provenance of a mut pointer
Sourcepub fn provenance_of_ref(ptr: &T) -> usize
pub fn provenance_of_ref(ptr: &T) -> usize
helper method that returns the address and provenance of a reference
Sourcepub fn provenance_of_mut(ptr: &mut T) -> usize
pub fn provenance_of_mut(ptr: &mut T) -> usize
helper method that returns the address and provenance of a mutable reference
Trait Implementations§
Source§impl<T: Pointee> AsMut<T> for UniquePointer<T>
impl<T: Pointee> AsMut<T> for UniquePointer<T>
Source§impl<T: Pointee> AsRef<T> for UniquePointer<T>
impl<T: Pointee> AsRef<T> for UniquePointer<T>
Source§impl<T: Pointee> Clone for UniquePointer<T>
The Clone implementation of UniquePointer
is special
because it flags cloned values as clones such that a double-free
doesn not occur.
impl<T: Pointee> Clone for UniquePointer<T>
The Clone implementation of UniquePointer
is special
because it flags cloned values as clones such that a double-free
doesn not occur.
Source§fn clone(&self) -> UniquePointer<T>
fn clone(&self) -> UniquePointer<T>
1.0.0 · Source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read more