ids 0.1.4

This library provides several data structures, inspired by Bagwell's Ideal Hash Trees, with an automatic copy-on-write implementation, analogous that of Clojure, to maximize performance. It is compatible with `no_std` code, but does require `alloc`.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

//! Provides copy-on-write atomic reference-counting pointers, with context
//! tracking to enable in-place updates of shared algebraic data structures.

use core::{
    ops::{Deref, DerefMut},
    ptr::NonNull,
};

use alloc::{boxed::Box, sync::Arc};

/// An analogue to a `&'a mut Arc<T>` which enforces copy-on-write semantics.
///
/// This type has a complicated interface and is only intended to be used
/// internally as an implementation detail for traversing data structures like
/// those in this library.
pub struct Cowarc<'a, T> {
    inner: Inner<'a, T>,
}

impl<'a, T> Cowarc<'a, T> {
    /// Constructs a new copy-on-write reference which wraps an [`Arc`] to which
    /// we already have exclusive access (i.e., the root of a tree-like data
    /// structure).
    pub fn new_root(arc: &'a mut Arc<T>) -> Self {
        Self {
            inner: Inner::Root(arc),
        }
    }

    /// Constructs a new copy-on-write reference from its core parts.
    ///
    /// The pointer `child` provides shared access to the value, while calling
    /// `map` produces a pointer which provides exclusive access to the value.
    /// Pointers obtained from either must be valid for lifetime `'a` or until
    /// the subsequent call to `map`, which invalidates all previous pointers.
    pub unsafe fn new_child(
        child: NonNull<T>,
        map: Box<dyn FnMut() -> NonNull<T> + 'a>,
    ) -> Cowarc<'a, T>
    where
        T: Clone,
    {
        Cowarc {
            inner: Inner::Child { this: child, map },
        }
    }

    /// Converts the copy-on-write reference to an ordinary shared reference.
    pub fn into_ref(cowarc: Self) -> &'a T
    where
        T: Clone,
    {
        match cowarc.inner {
            Inner::Root(arc) => &*arc,
            Inner::Child { this, .. } => unsafe { this.as_ref() },
        }
    }

    /// Converts the copy-on-write reference to an ordinary mutable reference.
    pub fn into_mut(cowarc: Self) -> &'a mut T
    where
        T: Clone,
    {
        match cowarc.inner {
            Inner::Root(arc) => Arc::make_mut(arc),
            Inner::Child { mut map, .. } => unsafe { map().as_mut() },
        }
    }
}

impl<'a, T> Deref for Cowarc<'a, T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        match &self.inner {
            Inner::Root(arc) => &arc,
            Inner::Child { this, .. } => unsafe { this.as_ref() },
        }
    }
}

impl<'a, T: Clone> DerefMut for Cowarc<'a, T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        match &mut self.inner {
            Inner::Root(arc) => Arc::make_mut(arc),
            Inner::Child { this, map, .. } => unsafe {
                *this = map();
                this.as_mut()
            },
        }
    }
}

enum Inner<'a, T> {
    Root(&'a mut Arc<T>),
    Child {
        this: NonNull<T>,
        map: Box<dyn FnMut() -> NonNull<T> + 'a>,
    },
}