unique_pointer/unique_pointer.rs
1use std::alloc::Layout;
2use std::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
3use std::convert::{AsMut, AsRef};
4use std::fmt::{Debug, Formatter, Pointer};
5use std::hash::{Hash, Hasher};
6use std::ops::{Deref, DerefMut};
7
8use crate::{Pointee, RefCounter};
9
10pub const ISACOPY: u8 = 0b0001;
11pub const ISALLOC: u8 = 0b0010;
12pub const WRITTEN: u8 = 0b0100;
13
14/// `UniquePointer` is an experimental data structure that makes
15/// extensive use of unsafe rust to provide a shared pointer
16/// throughout the runtime of a rust program as transparently as
17/// possible.
18///
19/// [UniquePointer](Self)'s design's purpose is two-fold:
20///
21/// - Leverage the implementation of circular data structures such as
22/// Lisp cons cells.
23///
24/// - Making easier the task of practicing the implementation of basic
25/// computer science data-structures (e.g.: Binary Trees, Linked Lists
26/// etc) such that the concept of pointer is as close to C as possible
27/// in terms of developer experience and so when a CS teacher speaks
28/// in terms of pointers, students can use [UniquePointer](Self) in their
29/// data-structures knowing that cloning their data-structures also
30/// means cloning the pointers transparently.
31///
32/// In fact, the [author](https://github.com/gabrielfalcao/) designed
33/// `UniquePointer` while studying the MIT CourseWare material of
34/// professor [Erik Demaine](https://github.com/edemaine) as well as
35/// to implement lisp [cons](https://en.wikipedia.org/wiki/Cons) cells
36/// and ring-buffers.
37///
38/// To this point the author reiterates: `UniquePointer` is an
39/// **experimental** data-structure designed primarily as a
40/// building-block of other data-structures in rust.
41///
42/// `UniquePointer` provides the methods [`UniquePointer::cast_mut`]
43/// and [`UniquePointer::cast_const`] not unlike those of raw
44/// pointers, and also implements the methods
45/// [`UniquePointer::as_ref`] and [`UniquePointer::as_mut`] with a
46/// signature compatible with that of the [AsRef] and [AsMut]
47/// traits such that users of raw pointers can migrate to
48/// [UniquePointer](Self) without much difficulty.
49///
50/// `UniquePointer` is designed a way such that Enums and Structs
51/// using `UniquePointer` can safely clone `UniquePointer` while the
52/// memory address and provenance of its value is shared.
53///
54/// [UniquePointer](Self) is able to extend lifetimes because it maintains
55/// its own reference counting outside of the rust compiler.
56///
57/// Reference Counting is provided by [RefCounter] which uses unsafe
58/// rust to ensure that ref counts are shared across cloned objects
59/// memory.
60///
61/// Both [UniquePointer](Self) and [RefCounter] use relatively obscure
62/// rust techniques under the hood to allow writing in non-mut
63/// references in strategic occasions such as incrementing its
64/// reference count within its [Clone] implementation.
65///
66/// UniquePointer only supports [Sized] types, that is, [Zero-Sized
67/// Types](https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts)
68/// (ZSTs) are not supported.
69///
70/// Example
71///
72/// ```
73/// use unique_pointer::UniquePointer;
74///
75/// fn create_unique_pointer<'a>() -> UniquePointer<&'a str> {
76/// UniquePointer::from("string")
77/// }
78/// let mut value: UniquePointer<&'_ str> = create_unique_pointer();
79///
80/// assert_eq!(value.is_null(), false);
81///
82/// assert_eq!(value.is_allocated(), true);
83/// assert!(value.addr() > 0, "address should not be null");
84/// assert_eq!(value.is_written(), true);
85/// assert_eq!(value.inner_ref(), &"string");
86///
87/// assert_eq!(value.read(), "string");
88/// assert_eq!(value.as_ref(), Some(&"string"));
89/// ```
90///
91/// # Caveats
92///
93/// - Only supports types that implement [Debug]
94/// - Does not support [ZSTs](https://doc.rust-lang.org/nomicon/exotic-sizes.html#zero-sized-types-zsts) (Zero-Sized Types)
95/// - [UniquePointer](Self) **IS NOT THREAD SAFE**
96///
97/// # Lisp Cons Cell Example
98///
99/// ```
100/// use std::iter::Extend;
101///
102/// use unique_pointer::{RefCounter, UniquePointer};
103/// # use std::borrow::Cow;
104/// # use std::convert::{AsMut, AsRef};
105/// #
106/// # #[derive(Clone, PartialOrd, Ord, Default, PartialEq, Eq, Hash)]
107/// # pub enum Value<'c> {
108/// # #[default]
109/// # Nil,
110/// # String(Cow<'c, str>),
111/// # Byte(u8),
112/// # UInt(u64),
113/// # Int(i64),
114/// # }
115/// # impl<'c> Value<'_> {
116/// # pub fn nil() -> Value<'c> {
117/// # Value::Nil
118/// # }
119/// #
120/// # pub fn is_nil(&self) -> bool {
121/// # if *self == Value::Nil {
122/// # true
123/// # } else {
124/// # false
125/// # }
126/// # }
127/// # }
128/// #
129/// # impl<'c> Drop for Value<'c> {
130/// # fn drop(&mut self) {}
131/// # }
132/// #
133/// # impl std::fmt::Display for Value<'_> {
134/// # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
135/// # write!(
136/// # f,
137/// # "{}",
138/// # match self {
139/// # Value::Nil => "nil".to_string(),
140/// # Value::String(h) => format!("{}", h),
141/// # Value::Byte(h) => format!("{}", h),
142/// # Value::UInt(h) => format!("{}", h),
143/// # Value::Int(h) => format!("{}", h),
144/// # }
145/// # )
146/// # }
147/// # }
148/// # impl std::fmt::Debug for Value<'_> {
149/// # fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
150/// # write!(
151/// # f,
152/// # "{}",
153/// # match self {
154/// # Value::Nil => "nil".to_string(),
155/// # Value::String(h) => format!("{:#?}", h),
156/// # Value::Byte(h) => format!("{}u8", h),
157/// # Value::UInt(h) => format!("{}u64", h),
158/// # Value::Int(h) => format!("{}i64", h),
159/// # }
160/// # )
161/// # }
162/// # }
163/// #
164/// # impl<'c> From<u8> for Value<'c> {
165/// # fn from(value: u8) -> Value<'c> {
166/// # Value::Byte(value)
167/// # }
168/// # }
169/// # impl<'c> From<u64> for Value<'c> {
170/// # fn from(value: u64) -> Value<'c> {
171/// # Value::UInt(value)
172/// # }
173/// # }
174/// # impl<'c> From<i64> for Value<'c> {
175/// # fn from(value: i64) -> Value<'c> {
176/// # Value::Int(value)
177/// # }
178/// # }
179/// # impl<'c> From<&'c str> for Value<'c> {
180/// # fn from(value: &'c str) -> Value<'c> {
181/// # Value::String(Cow::from(value))
182/// # }
183/// # }
184/// # impl<'c> From<Cow<'c, str>> for Value<'c> {
185/// # fn from(value: Cow<'c, str>) -> Value<'c> {
186/// # Value::from(value.into_owned())
187/// # }
188/// # }
189/// # impl<'c> From<&'c mut str> for Value<'c> {
190/// # fn from(value: &'c mut str) -> Value<'c> {
191/// # Value::String(Cow::<'c, str>::Borrowed(&*value))
192/// # }
193/// # }
194/// # impl<'c> From<String> for Value<'c> {
195/// # fn from(value: String) -> Value<'c> {
196/// # Value::String(Cow::from(value))
197/// # }
198/// # }
199/// # impl<'c> From<Option<String>> for Value<'c> {
200/// # fn from(value: Option<String>) -> Value<'c> {
201/// # match value {
202/// # None => Value::Nil,
203/// # Some(value) => Value::from(value),
204/// # }
205/// # }
206/// # }
207/// #
208/// # impl<'c> AsRef<Value<'c>> for Value<'c> {
209/// # fn as_ref(&self) -> &Value<'c> {
210/// # unsafe { &*self }
211/// # }
212/// # }
213/// # impl<'c> AsMut<Value<'c>> for Value<'c> {
214/// # fn as_mut(&mut self) -> &mut Value<'c> {
215/// # unsafe { &mut *self }
216/// # }
217/// # }
218/// #
219/// # impl<'c> PartialEq<&Value<'c>> for Value<'c> {
220/// # fn eq(&self, other: &&Value<'c>) -> bool {
221/// # let other = unsafe { &**other };
222/// # self == other
223/// # }
224/// # }
225/// #
226/// # impl<'c> PartialEq<&mut Value<'c>> for Value<'c> {
227/// # fn eq(&self, other: &&mut Value<'c>) -> bool {
228/// # let other = unsafe { &**other };
229/// # self == other
230/// # }
231/// # }
232/// #
233///
234/// #[derive(Debug, Hash)]
235/// pub struct Cell<'c> {
236/// head: UniquePointer<Value<'c>>,
237/// tail: UniquePointer<Cell<'c>>,
238/// refs: RefCounter,
239/// length: usize,
240/// }
241///
242/// impl<'c> Cell<'c> {
243/// pub fn nil() -> Cell<'c> {
244/// Cell {
245/// head: UniquePointer::<Value<'c>>::null(),
246/// tail: UniquePointer::<Cell<'c>>::null(),
247/// refs: RefCounter::null(),
248/// length: 0,
249/// }
250/// }
251///
252/// pub fn is_nil(&self) -> bool {
253/// self.head.is_null() && self.tail.is_null()
254/// }
255///
256/// pub fn new(value: Value<'c>) -> Cell<'c> {
257/// let mut cell = Cell::nil();
258/// cell.write(value);
259/// cell
260/// }
261///
262/// fn write(&mut self, value: Value<'c>) {
263/// self.head.write(value);
264/// self.refs.write(1);
265/// self.length = 1;
266/// }
267///
268/// fn swap_head(&mut self, other: &mut Self) {
269/// self.head = unsafe {
270/// let head = other.head.propagate();
271/// other.head = self.head.propagate();
272/// head
273/// };
274/// }
275///
276/// fn swap_refs(&mut self, other: &mut Self) {
277/// self.refs = {
278/// let refs = other.refs.clone();
279/// other.refs = self.refs.clone();
280/// refs
281/// };
282/// }
283///
284/// pub fn head(&self) -> Option<Value<'c>> {
285/// self.head.try_read()
286/// }
287///
288/// pub fn add(&mut self, new: &mut Cell<'c>) {
289/// new.incr_ref();
290/// self.incr_ref();
291/// if self.head.is_null() {
292/// unsafe {
293/// if !new.head.is_null() {
294/// self.swap_head(new);
295/// }
296///
297/// if !new.tail.is_null() {
298/// let tail = new.tail.inner_mut();
299/// tail.swap_head(new);
300/// self.swap_refs(new);
301/// }
302/// self.tail = UniquePointer::read_only(new);
303/// }
304/// } else {
305/// if self.tail.is_null() {
306/// self.tail = UniquePointer::read_only(new);
307/// } else {
308/// self.tail.inner_mut().add(new);
309/// }
310/// }
311/// }
312///
313/// pub fn pop(&mut self) -> bool {
314/// if !self.tail.is_null() {
315/// self.tail.drop_in_place();
316/// self.tail = UniquePointer::null();
317/// true
318/// } else if !self.head.is_null() {
319/// self.head.drop_in_place();
320/// self.head = UniquePointer::null();
321/// true
322/// } else {
323/// false
324/// }
325/// }
326///
327/// pub fn is_empty(&self) -> bool {
328/// self.len() > 0
329/// }
330///
331/// pub fn len(&self) -> usize {
332/// let mut len = 0;
333/// if !self.head.is_null() {
334/// len += 1
335/// }
336/// if let Some(tail) = self.tail() {
337/// len += tail.len();
338/// }
339/// len
340/// }
341///
342/// pub fn tail(&self) -> Option<&'c Cell<'c>> {
343/// self.tail.as_ref()
344/// }
345///
346/// pub fn values(&self) -> Vec<Value<'c>> {
347/// let mut values = Vec::<Value>::new();
348/// if let Some(head) = self.head() {
349/// values.push(head.clone());
350/// }
351/// if let Some(tail) = self.tail() {
352/// values.extend(tail.values());
353/// }
354/// values
355/// }
356///
357/// fn incr_ref(&mut self) {
358/// self.refs += 1;
359/// if !self.tail.is_null() {
360/// if let Some(tail) = self.tail.as_mut() {
361/// tail.incr_ref();
362/// }
363/// }
364/// }
365///
366/// fn decr_ref(&mut self) {
367/// self.refs -= 1;
368/// if !self.tail.is_null() {
369/// if let Some(tail) = self.tail.as_mut() {
370/// tail.decr_ref();
371/// }
372/// }
373/// }
374///
375/// fn dealloc(&mut self) {
376/// if self.refs > 0 {
377/// self.decr_ref();
378/// } else {
379/// self.head.drop_in_place();
380/// self.tail.drop_in_place();
381/// }
382/// }
383/// }
384///
385/// impl<'c> From<Value<'c>> for Cell<'c> {
386/// fn from(value: Value<'c>) -> Cell<'c> {
387/// Cell::new(value)
388/// }
389/// }
390/// impl<'c> From<&'c str> for Cell<'c> {
391/// fn from(value: &'c str) -> Cell<'c> {
392/// let value = Value::from(value);
393/// Cell::new(value)
394/// }
395/// }
396/// impl<'c> From<u8> for Cell<'c> {
397/// fn from(value: u8) -> Cell<'c> {
398/// Cell::new(Value::Byte(value))
399/// }
400/// }
401/// impl<'c> From<u64> for Cell<'c> {
402/// fn from(value: u64) -> Cell<'c> {
403/// if value < u8::MAX.into() {
404/// Cell::new(Value::Byte(value as u8))
405/// } else {
406/// Cell::new(Value::UInt(value))
407/// }
408/// }
409/// }
410/// impl<'c> From<i32> for Cell<'c> {
411/// fn from(value: i32) -> Cell<'c> {
412/// if let Ok(value) = TryInto::<u64>::try_into(value) {
413/// Cell::new(Value::UInt(value))
414/// } else {
415/// Cell::new(Value::Int(value.into()))
416/// }
417/// }
418/// }
419/// impl<'c> From<i64> for Cell<'c> {
420/// fn from(value: i64) -> Cell<'c> {
421/// Cell::new(Value::from(value))
422/// }
423/// }
424///
425/// impl<'c> PartialEq<Cell<'c>> for Cell<'c> {
426/// fn eq(&self, other: &Cell<'c>) -> bool {
427/// if self.head.is_null() == other.head.is_null() {
428/// true
429/// } else if let Some(head) = self.head() {
430/// if let Some(value) = other.head() {
431/// return head == value && (self.tail() == other.tail());
432/// } else {
433/// false
434/// }
435/// } else {
436/// false
437/// }
438/// }
439/// }
440///
441/// impl<'c> Default for Cell<'c> {
442/// fn default() -> Cell<'c> {
443/// Cell::nil()
444/// }
445/// }
446/// impl<'c> Clone for Cell<'c> {
447/// fn clone(&self) -> Cell<'c> {
448/// let mut cell = Cell::nil();
449/// cell.refs = self.refs.clone();
450/// if self.head.is_not_null() {
451/// cell.head = self.head.clone();
452/// }
453/// if self.tail.is_not_null() {
454/// cell.tail = self.tail.clone();
455/// }
456/// cell
457/// }
458/// }
459/// impl<'c> Drop for Cell<'c> {
460/// fn drop(&mut self) {
461/// self.dealloc();
462/// }
463/// }
464/// ```
465///
466#[doc(alias = "Pointer")]
467pub struct UniquePointer<T: Pointee> {
468 mut_addr: usize,
469 mut_ptr: *mut T,
470 refs: RefCounter,
471 flags: u8,
472}
473impl<'c, T: Pointee + 'c> UniquePointer<T> {
474 /// creates a NULL `UniquePointer` ready to be written via [write].
475 pub fn null() -> UniquePointer<T> {
476 UniquePointer {
477 mut_addr: 0,
478 mut_ptr: std::ptr::null_mut::<T>(),
479 refs: RefCounter::new(),
480 flags: 0,
481 }
482 }
483
484 /// creates a new `UniquePointer` by effectively
485 /// reading the value referenced by **`src`**
486 ///
487 pub fn from_ref(src: &T) -> UniquePointer<T> {
488 let mut up = UniquePointer::<T>::null();
489 up.write_ref(src);
490 up
491 }
492
493 /// `from_ref_mut` creates a new `UniquePointer` by effectively
494 /// reading the value referenced by **`src`**
495 ///
496 pub fn from_ref_mut(src: &mut T) -> UniquePointer<T> {
497 let mut up = UniquePointer::<T>::null();
498 up.write_ref_mut(src);
499 up
500 }
501
502 /// is designed for use within the [Clone] implementation
503 /// of `UniquePointer`.
504 ///
505 /// The [copy] method creates a NULL `UniquePointer` flagged as
506 /// [`is_copy`] such that a double-free does not happen in
507 /// [dealloc].
508 fn copy() -> UniquePointer<T> {
509 let mut up = UniquePointer::<T>::null();
510 up.flags = up.flags | (ISACOPY);
511 up
512 }
513
514 /// produces a copy of a `UniquePointer` which is not a copy in
515 /// the sense that [`UniquePointer::is_copy`] returns true.
516 ///
517 /// Because of that rationale a double-free occurs if there are
518 /// two or more "containers" (e.g.: [struct](std#keyword.struct.html)s and [enum](std#keyword.enum.html)s)
519 /// implementing [Drop] and holding the same propagated
520 /// `UniquePointer` instance. For this reason
521 /// [`UniquePointer::propagate`] is unsafe.
522 ///
523 /// [`UniquePointer::propagate`] can be relatively observed as a
524 /// drop-in replacement to [`UniquePointer::clone`] for cases
525 /// when, for instance, swapping `UniquePointer` "instances"
526 /// between instances of `UniquePointer`-containing (structs
527 /// and/or enums) is desired.
528 ///
529 /// Example
530 ///
531 /// ```
532 /// use unique_pointer::UniquePointer;
533 /// use std::fmt::Debug;
534 /// use std::cmp::PartialEq;
535 ///
536 /// #[derive(Clone, Debug, Hash)]
537 /// pub struct BinaryTreeNode<T: Debug> {
538 /// pub item: T,
539 /// pub parent: UniquePointer<BinaryTreeNode<T>>,
540 /// pub left: UniquePointer<BinaryTreeNode<T>>,
541 /// pub right: UniquePointer<BinaryTreeNode<T>>,
542 /// }
543 /// impl<T: Debug> BinaryTreeNode<T> {
544 /// pub fn new(item: T) -> BinaryTreeNode<T> {
545 /// BinaryTreeNode {
546 /// item,
547 /// parent: UniquePointer::null(),
548 /// left: UniquePointer::null(),
549 /// right: UniquePointer::null(),
550 /// }
551 /// }
552 ///
553 /// pub fn rotate_left(&mut self) {
554 /// if self.parent.is_null() {
555 /// if self.right.is_not_null() {
556 /// self.parent = unsafe { self.right.propagate() };
557 /// self.right = UniquePointer::null();
558 /// }
559 /// }
560 /// }
561 ///
562 /// pub fn set_parent(&mut self, parent: &mut BinaryTreeNode<T>) {
563 /// self.parent = UniquePointer::read_only(parent);
564 /// }
565 ///
566 /// pub fn set_left(&mut self, left: &mut BinaryTreeNode<T>) {
567 /// left.set_parent(self);
568 /// self.left = UniquePointer::read_only(left);
569 /// }
570 ///
571 /// pub fn set_right(&mut self, right: &mut BinaryTreeNode<T>) {
572 /// right.set_parent(self);
573 /// self.right = UniquePointer::read_only(right);
574 /// }
575 /// }
576 ///
577 /// let mut node_a = BinaryTreeNode::new("A");
578 /// let mut node_b = BinaryTreeNode::new("B");
579 /// let mut node_c = BinaryTreeNode::new("C");
580 /// node_a.set_left(&mut node_b);
581 /// node_a.set_right(&mut node_c);
582 ///
583 /// ```
584 pub unsafe fn propagate(&self) -> UniquePointer<T> {
585 self.incr_ref();
586 let mut back_node = UniquePointer::<T>::null();
587 back_node.set_mut_ptr(self.mut_ptr, false);
588 back_node.refs = self.refs.clone();
589 back_node.flags = self.flags;
590 back_node
591 }
592 /// `unlock_reference` extends the lifetime of `&T` to `&'t T` and
593 /// unlocks `&'t T` into a `&'t mut T`
594 ///
595 /// This function is primarily designed to permit data-structures
596 /// implementing their own reference counting [`Clone`] to "break
597 /// out" of a read-only reference, so to speak, so that its
598 /// references can be incremented.
599 ///
600 /// Example
601 ///
602 /// ```
603 /// use std::fmt::Debug;
604 /// use unique_pointer::{RefCounter, UniquePointer};
605 ///
606 /// #[derive(Debug, Hash)]
607 /// pub struct LinkedList<T: Debug + Clone> {
608 /// pub item: T,
609 /// pub next: UniquePointer<LinkedList<T>>,
610 /// pub refs: usize,
611 /// }
612 /// impl<T: Debug + Clone> LinkedList<T> {
613 /// pub fn new(item: T) -> LinkedList<T> {
614 /// LinkedList {
615 /// item,
616 /// next: UniquePointer::null(),
617 /// refs: 1,
618 /// }
619 /// }
620 /// pub fn item(&self) -> T {
621 /// self.item.clone()
622 /// }
623 /// fn incr_ref(&mut self) {
624 /// self.refs += 1;
625 /// }
626 /// fn decr_ref(&mut self) {
627 /// if self.refs > 0 {
628 /// self.refs -= 1;
629 /// }
630 /// }
631 /// fn dealloc(&mut self) {
632 /// self.decr_ref();
633 /// if self.next.is_not_null() {
634 /// self.next.inner_mut().dealloc()
635 /// }
636 /// if self.refs == 0 {
637 /// self.next.drop_in_place();
638 /// }
639 /// }
640 /// pub fn append(&mut self, value: T) -> LinkedList<T> {
641 /// let next = LinkedList::new(value);
642 /// self.next.write_ref(&next);
643 /// next
644 /// }
645 ///
646 /// pub fn next(&self) -> Option<&LinkedList<T>> {
647 /// self.next.as_ref()
648 /// }
649 ///
650 /// pub fn len(&self) -> usize {
651 /// let mut length = 1;
652 ///
653 /// if let Some(next) = self.next() {
654 /// length += 1;
655 /// length += next.len();
656 /// }
657 /// length
658 /// }
659 /// }
660 /// impl<T: Debug + Clone> Clone for LinkedList<T> {
661 /// fn clone(&self) -> LinkedList<T> {
662 /// unsafe {
663 /// UniquePointer::<LinkedList<T>>::unlock_reference(self).incr_ref();
664 /// }
665 /// let mut list = LinkedList::new(self.item());
666 /// list.refs = self.refs;
667 /// list.next = self.next.clone();
668 /// list
669 /// }
670 /// }
671 /// impl<T: Debug + Clone> Drop for LinkedList<T> {
672 /// fn drop(&mut self) {
673 /// self.dealloc();
674 /// }
675 /// }
676 /// let mut a = LinkedList::new("a");
677 /// let mut b = a.append("b");
678 /// b.append("c");
679 ///
680 /// assert_eq!(a.refs, 1);
681 /// assert_eq!(a.len(), 3);
682 /// let z = a.clone();
683 /// assert_eq!(z.len(), 3);
684 /// assert_eq!(a.refs, 2);
685 /// assert_eq!(z.refs, 2);
686 /// ```
687 #[allow(mutable_transmutes)]
688 pub unsafe fn unlock_reference<'t>(read_only: &T) -> &'t mut T {
689 let extended = unsafe { std::mem::transmute::<&T, &'t T>(read_only) };
690 let unlocked = unsafe { std::mem::transmute::<&'t T, &'t mut T>(extended) };
691 unlocked
692 }
693 /// calls [`UniquePointer::copy_from_ref`] to create a *read-only* `UniquePointer` from a
694 /// reference of `T`, useful for iterating over self-referential
695 /// data structures.
696 ///
697 /// Example:
698 ///
699 /// ```
700 /// use unique_pointer::UniquePointer;
701 ///
702 /// pub struct Data<'r> {
703 /// value: &'r String,
704 /// }
705 /// impl <'r> Data<'r> {
706 /// pub fn new<T: std::fmt::Display>(value: T) -> Data<'r> {
707 /// let value = value.to_string();
708 /// Data {
709 /// value: UniquePointer::read_only(&value).extend_lifetime()
710 /// }
711 /// }
712 /// }
713 /// ```
714 pub fn read_only(data: &T) -> UniquePointer<T> {
715 UniquePointer::copy_from_ref(data, 1)
716 }
717
718 /// calls [`UniquePointer::copy_from_mut_ptr`] to create a *read-only*
719 /// `UniquePointer` from a reference of `T`, useful for
720 /// iterating over self-referential data structures that use
721 /// [RefCounter] to count refs.
722 ///
723 /// Note: [`UniquePointer::read_only`] might be a better alternative when `T` is
724 /// a data structure that does not use [RefCounter].
725 pub fn copy_from_ref(data: &T, refs: usize) -> UniquePointer<T> {
726 let ptr = (data as *const T).cast_mut();
727 UniquePointer::copy_from_mut_ptr(ptr, refs)
728 }
729
730 /// creates a *read-only* `UniquePointer`
731 /// from a reference of `T`, useful for iterating over
732 /// self-referential data structures that use [RefCounter] to
733 /// count refs.
734 ///
735 /// Note: [`UniquePointer::read_only`] might be a better alternative when `T` is
736 /// a data structure that does not use [RefCounter].
737 pub fn copy_from_mut_ptr(ptr: *mut T, refs: usize) -> UniquePointer<T> {
738 let addr = UniquePointer::provenance_of_mut_ptr(ptr);
739 let refs = RefCounter::from(refs);
740 UniquePointer {
741 mut_addr: addr,
742 mut_ptr: ptr,
743 refs: refs,
744 flags: (ISACOPY | ISALLOC | WRITTEN),
745 }
746 }
747
748 /// returns the value containing both the provenance and
749 /// memory address of a pointer
750 pub fn addr(&self) -> usize {
751 self.mut_addr
752 }
753
754 /// returns the reference count of a `UniquePointer`
755 pub fn refs(&self) -> usize {
756 *self.refs
757 }
758
759 /// returns true if the `UniquePointer` is NULL.
760 pub fn is_null(&self) -> bool {
761 let mut_is_null = self.mut_ptr.is_null();
762 #[cfg(feature = "null-check")]
763 if mut_is_null {
764 assert!(self.mut_addr == 0);
765 } else {
766 assert!(self.mut_addr != 0);
767 }
768 let is_null = mut_is_null;
769 is_null
770 }
771
772 /// returns true if the `UniquePointer` is not
773 /// NULL. [`UniquePointer::is_not_null`] is a idiomatic shortcut
774 /// to negating a call to [`UniquePointer::is_null`] such that the
775 /// negation is less likely to be clearly visible.
776 pub fn is_not_null(&self) -> bool {
777 !self.is_null()
778 }
779
780 /// returns true if the `UniquePointer` is not a
781 /// copy. [`UniquePointer::is_not_copy`] is a idiomatic shortcut
782 /// to negating a call to [`UniquePointer::is_copy`] such that the
783 /// negation is less likely to be clearly visible.
784 pub fn is_not_copy(&self) -> bool {
785 !self.is_copy()
786 }
787
788 /// returns true if the `UniquePointer` is not NULL
789 /// and is not flagged as a copy, meaning it can be deallocated
790 /// without concern for double-free.
791 pub fn can_dealloc(&self) -> bool {
792 ((self.flags & ISALLOC) == ISALLOC) && self.is_not_copy() && self.is_not_null()
793 }
794
795 /// returns true if the `UniquePointer` has been
796 /// allocated and therefore is no longer a NULL pointer.
797 pub fn is_allocated(&self) -> bool {
798 let is_allocated = ((self.flags & ISALLOC) == ISALLOC) && self.is_not_null();
799 is_allocated
800 }
801
802 /// returns true if the `UniquePointer` has been written to
803 pub fn is_written(&self) -> bool {
804 let is_written = ((self.flags & WRITTEN) == WRITTEN) && self.is_allocated();
805 is_written
806 }
807
808 /// returns true if a `UniquePointer` is a "copy" of
809 /// another `UniquePointer` in the sense that dropping or
810 /// "hard-deallocating" said `UniquePointer` does not incur a
811 /// double-free.
812 pub fn is_copy(&self) -> bool {
813 ((self.flags & ISACOPY) == ISACOPY)
814 }
815
816 /// allocates memory in a null `UniquePointer`
817 pub fn alloc(&mut self) {
818 if self.is_allocated() {
819 return;
820 }
821
822 let layout = Layout::new::<T>();
823 let mut_ptr = unsafe {
824 let ptr = std::alloc::alloc_zeroed(layout);
825 if ptr.is_null() {
826 std::alloc::handle_alloc_error(layout);
827 }
828 ptr as *mut T
829 };
830 self.set_mut_ptr(mut_ptr, false);
831 self.flags |= ISALLOC;
832 }
833
834 /// compatibility API to a raw mut pointer's [`pointer::cast_mut`].
835 pub fn cast_mut(&self) -> *mut T {
836 if self.is_null() {
837 panic!("{:#?}", self);
838 } else {
839 self.mut_ptr
840 }
841 }
842
843 /// compatibility API to a raw const pointer's [`pointer::cast_const`].
844 pub fn cast_const(&self) -> *const T {
845 if self.is_null() {
846 panic!("{:#?}", self);
847 } else {
848 self.mut_ptr.cast_const()
849 }
850 }
851
852 /// allocates memory and writes the given value into the
853 /// newly allocated area.
854 pub fn write(&mut self, data: T) {
855 self.alloc();
856
857 unsafe {
858 self.mut_ptr.write(data);
859 }
860
861 self.flags |= (WRITTEN);
862 }
863
864 /// takes a mutable reference to a value and
865 /// writes to a `UniquePointer`
866 pub fn write_ref_mut(&mut self, data: &mut T) {
867 self.alloc();
868 unsafe {
869 let ptr = data as *mut T;
870 ptr.copy_to(self.mut_ptr, 1);
871 };
872 self.flags |= (WRITTEN);
873 }
874
875 /// takes a read-only reference to a value and
876 /// writes to a `UniquePointer`
877 pub fn write_ref(&mut self, data: &T) {
878 self.alloc();
879 unsafe {
880 let ptr = data as *const T;
881 ptr.copy_to(self.mut_ptr, 1);
882 };
883 self.flags |= (WRITTEN);
884 }
885
886 /// swaps the memory addresses storing `T` with other `UniquePointer`
887 pub fn swap(&mut self, other: &mut Self) {
888 if self.is_null() && other.is_null() {
889 return;
890 }
891 if self.mut_ptr.is_null() {
892 self.alloc();
893 }
894 if other.mut_ptr.is_null() {
895 other.alloc();
896 }
897 unsafe {
898 self.mut_ptr.swap(other.mut_ptr);
899 }
900 }
901
902 /// reads data from memory `UniquePointer`. Panics if
903 /// the pointer is either null or allocated but never written to.
904 pub fn read(&self) -> T {
905 if !self.is_written() {
906 panic!("{:#?} not written", self);
907 }
908 let ptr = self.cast_const();
909 unsafe { ptr.read() }
910 }
911
912 /// reads data from memory `UniquePointer`
913 pub fn try_read(&self) -> Option<T> {
914 if self.is_null() {
915 return None;
916 }
917 if self.is_written() {
918 Some(self.read())
919 } else {
920 None
921 }
922 }
923
924 /// obtains a read-only reference to the value inside
925 /// `UniquePointer` but does not increment references
926 pub fn inner_ref(&self) -> &'c T {
927 if self.mut_ptr.is_null() {
928 panic!("NULL POINTER: {:#?}", self);
929 }
930 unsafe { std::mem::transmute::<&T, &'c T>(&*self.cast_const()) }
931 }
932
933 /// obtains a mutable reference to the value inside
934 /// `UniquePointer` but does not increment references
935 pub fn inner_mut(&mut self) -> &'c mut T {
936 if self.mut_ptr.is_null() {
937 panic!("NULL POINTER: {:#?}", self);
938 }
939 unsafe { std::mem::transmute::<&mut T, &'c mut T>(&mut *self.mut_ptr) }
940 }
941
942 /// compatibility layer to [`std::pointer::as_ref`]
943 pub fn as_ref(&self) -> Option<&'c T> {
944 if self.is_written() {
945 Some(self.inner_ref())
946 } else {
947 None
948 }
949 }
950
951 /// compatibility layer to [`std::pointer::as_mut`](std#primitive.pointer.html#formatting-parameters)
952 pub fn as_mut(&mut self) -> Option<&'c mut T> {
953 if self.is_written() {
954 Some(self.inner_mut())
955 } else {
956 None
957 }
958 }
959
960 /// deallocates a `UniquePointer`.
961 ///
962 /// The [soft] boolean argument indicates whether the
963 /// `UniquePointer` should have its reference count decremented or
964 /// deallocated immediately.
965 ///
966 /// During "soft" deallocation (`soft=true`) calls to `dealloc`
967 /// only really deallocate memory when the reference gets down to
968 /// zero, until then each `dealloc(true)` call simply decrements
969 /// the reference count.
970 ///
971 /// Conversely during "hard" deallocation (`soft=false`) the
972 /// UniquePointer in question gets immediately deallocated,
973 /// possibly incurring a double-free or causing Undefined
974 /// Behavior.
975 pub fn dealloc(&mut self, soft: bool) {
976 if self.is_null() {
977 return;
978 }
979 if soft && self.refs > 0 {
980 self.decr_ref();
981 } else {
982 self.free();
983 }
984 }
985
986 /// sets the internal raw pointer of a `UniquePointer`.
987 ///
988 /// Prior to setting the new pointer, it checks whether the
989 /// internal pointer is non-null and matches its provenance
990 /// address, such that "copies" do not incur a double-free.
991 ///
992 /// When [ptr] is a NULL pointer and the internal pointer of
993 /// `UniquePointer` in question is NOT NULL, then it is
994 /// deallocated prior to setting it to NULL.
995 fn set_mut_ptr(&mut self, ptr: *mut T, dealloc: bool) {
996 if ptr.is_null() {
997 if dealloc && self.is_allocated() {
998 self.flags = 0;
999 self.mut_addr = 0;
1000 let layout = Layout::new::<T>();
1001 unsafe {
1002 std::alloc::dealloc(self.mut_ptr as *mut u8, layout);
1003 };
1004 self.mut_ptr = std::ptr::null_mut::<T>();
1005 }
1006
1007 self.set_mut_addr(0);
1008 } else {
1009 self.set_mut_addr(UniquePointer::<T>::provenance_of_mut_ptr(ptr));
1010 }
1011 self.mut_ptr = ptr;
1012 }
1013
1014 /// deallocates the memory used by `UniquePointer`
1015 /// once its references get down to zero.
1016 pub fn drop_in_place(&mut self) {
1017 self.dealloc(true);
1018 }
1019
1020 fn set_mut_addr(&mut self, addr: usize) {
1021 self.mut_addr = addr;
1022 }
1023
1024 /// is internally used by [dealloc] when the number of
1025 /// references gets down to zero in a "soft" deallocation and
1026 /// immediately in a "hard" deallocation.
1027 ///
1028 /// See [dealloc] for more information regarding the difference
1029 /// between "soft" and "hard" deallocation.
1030 fn free(&mut self) {
1031 if !self.can_dealloc() {
1032 return;
1033 }
1034 if !self.is_null() {
1035 self.set_mut_ptr(std::ptr::null_mut::<T>(), false);
1036 self.refs.drain();
1037 }
1038 self.flags = 0;
1039 }
1040
1041 /// utility method to extend the lifetime
1042 /// of references of data created within a function.
1043 ///
1044 /// Example
1045 ///
1046 /// ```
1047 /// use unique_pointer::UniquePointer;
1048 ///
1049 /// pub struct Data<'r> {
1050 /// value: &'r String,
1051 /// }
1052 /// impl <'r> Data<'r> {
1053 /// pub fn new<T: std::fmt::Display>(value: T) -> Data<'r> {
1054 /// let value = value.to_string();
1055 /// Data {
1056 /// value: UniquePointer::read_only(&value).extend_lifetime()
1057 /// }
1058 /// }
1059 /// }
1060 /// ```
1061 pub fn extend_lifetime<'t>(&self) -> &'t T {
1062 unsafe { std::mem::transmute::<&T, &'t T>(self.inner_ref()) }
1063 }
1064
1065 /// utility method to extend the lifetime
1066 /// of references of data created within a function.
1067 ///
1068 /// Example
1069 ///
1070 /// ```
1071 /// use unique_pointer::UniquePointer;
1072 ///
1073 /// pub struct Data<'r> {
1074 /// value: &'r mut String,
1075 /// }
1076 /// impl <'r> Data<'r> {
1077 /// pub fn new<T: std::fmt::Display>(value: T) -> Data<'r> {
1078 /// let value = value.to_string();
1079 /// Data {
1080 /// value: UniquePointer::read_only(&value).extend_lifetime_mut()
1081 /// }
1082 /// }
1083 /// }
1084 /// ```
1085 pub fn extend_lifetime_mut<'t>(&mut self) -> &'t mut T {
1086 unsafe { std::mem::transmute::<&mut T, &'t mut T>(self.inner_mut()) }
1087 }
1088}
1089
1090impl<T: Pointee> UniquePointer<T> {
1091 /// helper method that returns the
1092 /// address and provenance of a const pointer
1093 pub fn provenance_of_const_ptr(ptr: *const T) -> usize {
1094 ptr.expose_provenance()
1095 }
1096
1097 /// helper method that returns the
1098 /// address and provenance of a mut pointer
1099 pub fn provenance_of_mut_ptr(ptr: *mut T) -> usize {
1100 ptr.expose_provenance()
1101 }
1102
1103 /// helper method that returns the
1104 /// address and provenance of a reference
1105 pub fn provenance_of_ref(ptr: &T) -> usize {
1106 (&raw const ptr).expose_provenance()
1107 }
1108
1109 /// helper method that returns the
1110 /// address and provenance of a mutable reference
1111 pub fn provenance_of_mut(mut ptr: &mut T) -> usize {
1112 (&raw mut ptr).expose_provenance()
1113 }
1114}
1115
1116#[allow(unused)]
1117impl<'c, T: Pointee + 'c> UniquePointer<T> {
1118 /// unsafe method that turns a "self reference"
1119 /// into a mutable "self reference"
1120 unsafe fn meta_mut(&'c self) -> &'c mut UniquePointer<T> {
1121 unsafe {
1122 let ptr = self.meta_mut_ptr();
1123 let up = &mut *ptr;
1124 std::mem::transmute::<&mut UniquePointer<T>, &'c mut UniquePointer<T>>(up)
1125 }
1126 }
1127
1128 /// unsafe method that turns a [`*mut UniquePointer`] from a "self reference"
1129 unsafe fn meta_mut_ptr(&self) -> *mut UniquePointer<T> {
1130 let ptr = self as *const UniquePointer<T>;
1131 unsafe {
1132 let ptr: *mut UniquePointer<T> =
1133 std::mem::transmute::<*const UniquePointer<T>, *mut UniquePointer<T>>(ptr);
1134 ptr
1135 }
1136 }
1137}
1138#[allow(invalid_reference_casting)]
1139impl<T: Pointee> UniquePointer<T> {
1140 fn incr_ref(&self) {
1141 if self.is_null() {
1142 return;
1143 }
1144 self.refs.incr();
1145 }
1146
1147 fn decr_ref(&self) {
1148 if self.refs == 0 {
1149 return;
1150 }
1151 self.refs.decr();
1152 }
1153}
1154impl<T: Pointee> AsRef<T> for UniquePointer<T> {
1155 fn as_ref(&self) -> &T {
1156 if self.is_null() {
1157 panic!("null pointer: {:#?}", self);
1158 }
1159 self.inner_ref()
1160 }
1161}
1162impl<T: Pointee> AsMut<T> for UniquePointer<T> {
1163 fn as_mut(&mut self) -> &mut T {
1164 if self.is_null() {
1165 panic!("null pointer: {:#?}", self);
1166 }
1167 self.inner_mut()
1168 }
1169}
1170
1171impl<T: Pointee> Deref for UniquePointer<T> {
1172 type Target = T;
1173
1174 fn deref(&self) -> &T {
1175 self.inner_ref()
1176 }
1177}
1178
1179impl<T: Pointee> DerefMut for UniquePointer<T> {
1180 fn deref_mut(&mut self) -> &mut T {
1181 self.inner_mut()
1182 }
1183}
1184
1185impl<T: Pointee> Drop for UniquePointer<T>
1186where
1187 T: Debug,
1188{
1189 fn drop(&mut self) {
1190 self.drop_in_place();
1191 }
1192}
1193
1194impl<T: Pointee> From<&T> for UniquePointer<T>
1195where
1196 T: Debug,
1197{
1198 fn from(data: &T) -> UniquePointer<T> {
1199 UniquePointer::<T>::from_ref(data)
1200 }
1201}
1202impl<T: Pointee> From<&mut T> for UniquePointer<T>
1203where
1204 T: Debug,
1205{
1206 fn from(data: &mut T) -> UniquePointer<T> {
1207 UniquePointer::<T>::from_ref_mut(data)
1208 }
1209}
1210impl<T: Pointee> From<T> for UniquePointer<T>
1211where
1212 T: Debug,
1213{
1214 fn from(data: T) -> UniquePointer<T> {
1215 let mut up = UniquePointer::<T>::null();
1216 up.write(data);
1217 up
1218 }
1219}
1220/// The [Clone] implementation of `UniquePointer` is special
1221/// because it flags cloned values as clones such that a double-free
1222/// doesn not occur.
1223impl<T: Pointee> Clone for UniquePointer<T>
1224where
1225 T: Debug,
1226{
1227 fn clone(&self) -> UniquePointer<T> {
1228 self.incr_ref();
1229 let mut clone = UniquePointer::<T>::copy();
1230 clone.set_mut_ptr(self.mut_ptr, false);
1231 clone.refs = self.refs.clone();
1232 clone.flags = self.flags;
1233 clone
1234 }
1235}
1236
1237impl<T: Pointee> Pointer for UniquePointer<T>
1238where
1239 T: Debug,
1240{
1241 fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
1242 write!(f, "{:016x}", self.addr())
1243 }
1244}
1245
1246impl<T: Pointee> Debug for UniquePointer<T>
1247where
1248 T: Debug,
1249{
1250 fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
1251 write!(
1252 f,
1253 "UniquePointer{}",
1254 [
1255 format!("{:016x}", self.addr()),
1256 if self.is_not_null() {
1257 [
1258 format!("[src={:#?}]", self.inner_ref()),
1259 format!("[refs={}]", self.refs),
1260 ]
1261 .join("")
1262 } else {
1263 [
1264 format!("[refs={}]", self.refs),
1265 format!("[alloc={}]", self.is_allocated()),
1266 format!("[written={}]", self.is_written()),
1267 ]
1268 .join("")
1269 },
1270 format!("[is_copy={}]", self.is_copy()),
1271 ]
1272 .join("")
1273 )
1274 }
1275}
1276
1277impl<T: Pointee + PartialEq> PartialEq<UniquePointer<T>> for UniquePointer<T> {
1278 fn eq(&self, fles: &UniquePointer<T>) -> bool {
1279 if self.addr() == fles.addr() {
1280 return true;
1281 }
1282 if self.is_null() {
1283 let eq = fles.is_null();
1284 return eq;
1285 }
1286 self.inner_ref().eq(fles.inner_ref())
1287 }
1288}
1289impl<T: Pointee + Eq> Eq for UniquePointer<T> {}
1290impl<T: Pointee + PartialOrd> PartialOrd<UniquePointer<T>> for UniquePointer<T> {
1291 fn partial_cmp(&self, other: &UniquePointer<T>) -> Option<Ordering> {
1292 if self.is_null() {
1293 return None;
1294 }
1295 if self.addr() == other.addr() {
1296 return Some(Ordering::Equal);
1297 }
1298 self.inner_ref().partial_cmp(other.inner_ref())
1299 }
1300}
1301
1302impl<T: Pointee + PartialOrd> PartialOrd<T> for UniquePointer<T> {
1303 fn partial_cmp(&self, other: &T) -> Option<Ordering> {
1304 if self.is_null() {
1305 return None;
1306 }
1307 self.inner_ref().partial_cmp(other)
1308 }
1309}
1310impl<T: Pointee + PartialEq> PartialEq<T> for UniquePointer<T> {
1311 fn eq(&self, other: &T) -> bool {
1312 if self.is_null() {
1313 return false;
1314 }
1315 self.inner_ref().eq(other)
1316 }
1317}
1318
1319impl<T: Pointee + Ord> Ord for UniquePointer<T> {
1320 fn cmp(&self, other: &Self) -> Ordering {
1321 if self.is_null() {
1322 return Ordering::Less;
1323 }
1324 self.inner_ref().cmp(other.inner_ref())
1325 }
1326}
1327
1328impl<T: Pointee + Hash> Hash for UniquePointer<T> {
1329 fn hash<H: Hasher>(&self, state: &mut H) {
1330 self.inner_ref().hash(state)
1331 }
1332}
1333
1334// impl<T: Deref, S: Deref> PartialEq<&UniquePointer<S>> for UniquePointer<T>
1335// where
1336// T: PartialEq<S::Target> + Pointee,
1337// S: Pointee,
1338// {
1339// fn eq(&self, other: &&UniquePointer<S>) -> bool {
1340// T::eq(self, other)
1341// }
1342
1343// fn ne(&self, other: &&UniquePointer<S>) -> bool {
1344// T::ne(self, other)
1345// }
1346// }
1347
1348// impl<T: Deref, S: Deref> PartialEq<UniquePointer<S>> for UniquePointer<T>
1349// where
1350// T: PartialEq<S::Target> + Pointee,
1351// S: Pointee,
1352// {
1353// fn eq(&self, other: &UniquePointer<S>) -> bool {
1354// T::eq(self, other)
1355// }
1356
1357// fn ne(&self, other: &UniquePointer<S>) -> bool {
1358// T::ne(self, other)
1359// }
1360// }
1361
1362// impl<T: Deref<Target: Eq> + Eq + PartialEq<<T as Deref>::Target>> Eq for UniquePointer<T> where
1363// T: Pointee
1364// {
1365// }
1366
1367// impl<T: Deref, S: Deref> PartialOrd<UniquePointer<S>> for UniquePointer<T>
1368// where
1369// T: PartialOrd<S::Target> + Pointee,
1370// S: Pointee,
1371// {
1372// fn partial_cmp(&self, other: &UniquePointer<S>) -> Option<Ordering> {
1373// T::partial_cmp(self, other)
1374// }
1375
1376// fn lt(&self, other: &UniquePointer<S>) -> bool {
1377// T::lt(self, other)
1378// }
1379
1380// fn le(&self, other: &UniquePointer<S>) -> bool {
1381// T::le(self, other)
1382// }
1383
1384// fn gt(&self, other: &UniquePointer<S>) -> bool {
1385// T::gt(self, other)
1386// }
1387
1388// fn ge(&self, other: &UniquePointer<S>) -> bool {
1389// T::ge(self, other)
1390// }
1391// }
1392
1393// impl<T: Deref<Target: Ord> + Ord + PartialOrd<<T as Deref>::Target>> Ord for UniquePointer<T>
1394// where
1395// T: Pointee,
1396// {
1397// fn cmp(&self, other: &Self) -> Ordering {
1398// T::cmp(self, other)
1399// }
1400// }
1401
1402// impl<T: Deref<Target: Hash> + Hash> Hash for UniquePointer<T>
1403// where
1404// T: Pointee,
1405// {
1406// fn hash<H: Hasher>(&self, state: &mut H) {
1407// T::hash(self, state);
1408// }
1409// }