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