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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

use crate::{NotSelfRefVecItem, PinnedVec};

/// `PinnedVecSimple` is a `PinnedVec` where the elements satisfy the trait bound
/// `T: NotSelfRefVecItem.
///
/// In other words, elements of the vector does not hold references to other
/// elements of the same vector.
/// Note that this is satisfied for all `std::vec::Vec`s.
///
/// On the other hand, `PinnedVec` is designed to conveniently build more complex
/// data structures while holding children of these data structures in a vec-like
/// layout for better cache locality and to reduce heap allocations.
///
/// These structures often contain child structures referencing each other;
/// such as the `parent` or `children` relations of a tree.
/// `PinnedVec` aims at guaranteeing that these internal references are kept valid.
/// This makes methods `insert`, `remove` and `pop` unsafe.
///
/// Since the aforementioned safety concern is absent when elements do not hold such internal references;
/// i.e., when `T: NotSelfRefVecItem`,
/// such vectors automatically implement `PinnedVecSimple` which enables safe calls
/// to these methods.
///
/// # Safety
///
/// Picking the more conservative and safer approach;
/// the default versions of methods `insert`, `remove` and `pop` are unsafe.
///
/// In order to be able to make safe calls to these methods,
/// once must explicitly implement `NotSelfRefVecItem` for the element type.
/// This is a marker trait, and hence, easy to implement.
///
/// For convenience,
/// this crate already contains implementations for the primitive structs
/// such as numbers, string or bool.
pub trait PinnedVecSimple<T>: PinnedVec<T>
where
    T: NotSelfRefVecItem,
{
    /// Inserts an element at position index within the vector, shifting all elements after it to the right.
    ///
    /// # Panics
    /// Panics if `index >= len`.
    ///
    /// # Safety
    ///
    /// `insert` operation for a `PinnedVecSimple` where the elements are `T: NotSelfRefVecItem` is **safe**;
    /// in this case, pinned vector shares the same safety requirements as `std::vec::Vec` which is readily
    /// provided by the borrow checker.
    fn insert(&mut self, index: usize, element: T);
    /// Removes and returns the element at position index within the vector, shifting all elements after it to the left.
    ///
    /// # Panics
    ///
    /// Panics if index is out of bounds.
    ///
    /// # Safety
    ///
    /// `remove` operation for a `PinnedVecSimple` where the elements are `T: NotSelfRefVecItem` is **safe**;
    /// in this case, pinned vector shares the same safety requirements as `std::vec::Vec` which is readily
    /// provided by the borrow checker.
    fn remove(&mut self, index: usize) -> T;
    /// Removes the last element from a vector and returns it, or None if it is empty.
    ///
    /// # Safety
    ///
    /// `pop` operation for a `PinnedVecSimple` where the elements are `T: NotSelfRefVecItem` is **safe**;
    /// in this case, pinned vector shares the same safety requirements as `std::vec::Vec` which is readily
    /// provided by the borrow checker.
    fn pop(&mut self) -> Option<T>;
    /// Swaps two elements in the slice.
    ///
    /// If `a` equals to `b`, it's guaranteed that elements won't change value.
    ///
    /// # Arguments
    ///
    /// * a - The index of the first element
    /// * b - The index of the second element
    ///
    /// # Safety
    ///
    /// `swap` operation for a `PinnedVecSimple` where the elements are `T: NotSelfRefVecItem` is **safe**;
    /// in this case, pinned vector shares the same safety requirements as `std::vec::Vec` which is readily
    /// provided by the borrow checker.
    fn swap(&mut self, a: usize, b: usize);
    /// Shortens the vector, keeping the first `len` elements and dropping
    /// the rest.
    ///
    /// If `len` is greater than the vector's current length, this has no
    /// effect.
    fn truncate(&mut self, len: usize);
    /// Creates and returns a clone of the vector.
    ///
    /// # Safety
    ///
    /// `clone` operation for a `PinnedVecSimple` where the elements are `T: NotSelfRefVecItem` is **safe**;
    /// in this case, pinned vector shares the same safety requirements as `std::vec::Vec` which is readily
    /// provided by the borrow checker.
    fn clone(&self) -> Self
    where
        T: Clone;
}

impl<T, V> PinnedVecSimple<T> for V
where
    T: NotSelfRefVecItem,
    V: PinnedVec<T>,
{
    #[inline(always)]
    fn insert(&mut self, index: usize, element: T) {
        unsafe { self.unsafe_insert(index, element) }
    }
    #[inline(always)]
    fn remove(&mut self, index: usize) -> T {
        unsafe { self.unsafe_remove(index) }
    }
    #[inline(always)]
    fn pop(&mut self) -> Option<T> {
        unsafe { self.unsafe_pop() }
    }
    #[inline(always)]
    fn swap(&mut self, a: usize, b: usize) {
        unsafe { self.unsafe_swap(a, b) }
    }
    #[inline(always)]
    fn truncate(&mut self, len: usize) {
        unsafe { self.unsafe_truncate(len) }
    }

    #[inline(always)]
    fn clone(&self) -> Self
    where
        T: Clone,
    {
        unsafe { self.unsafe_clone() }
    }
}